source: anac2020/Angel/src/main/java/geniusweb/exampleparties/simpleshaop/AngelParty.java

Last change on this file was 29, checked in by wouter, 3 years ago

#3
File size: 41.9 KB
Line 
1// WORKING ANGEL AGENT
2/**
3 * TODO Current changes that need to be made outside of the methods:
4 * 3. Experiment with batch updating for comparisons (requires filling out the method under main routines)
5 */
6
7package geniusweb.exampleparties.simpleshaop;
8
9import java.io.IOException;
10import java.util.ArrayList;
11import java.util.Arrays;
12import java.util.Collection;
13import java.util.Collections;
14import java.util.HashMap;
15import java.util.HashSet;
16import java.util.List;
17import java.util.Random;
18import java.util.Set;
19import java.util.logging.Level;
20
21import geniusweb.actions.Accept;
22import geniusweb.actions.Action;
23import geniusweb.actions.Comparison;
24import geniusweb.actions.ElicitComparison;
25import geniusweb.actions.Offer;
26import geniusweb.actions.PartyId;
27import geniusweb.inform.ActionDone;
28import geniusweb.inform.Finished;
29import geniusweb.inform.Inform;
30import geniusweb.inform.Settings;
31import geniusweb.inform.YourTurn;
32import geniusweb.issuevalue.Bid;
33import geniusweb.issuevalue.ValueSet;
34import geniusweb.party.Capabilities;
35import geniusweb.party.DefaultParty;
36import geniusweb.profile.Profile;
37import geniusweb.profileconnection.ProfileConnectionFactory;
38import geniusweb.profileconnection.ProfileInterface;
39import geniusweb.progress.Progress;
40import geniusweb.progress.ProgressRounds;
41import tudelft.utilities.logging.Reporter;
42
43/**
44 * ANGEL is a Shaop Party that will use an intuitive heuristic to model
45 * opponents and estimate the values of bids. Weights and the utilities of
46 * individual issue values are learned over time. Estimations are made with a
47 * linear additive utility function of weights*utilities, and then additionaly
48 * processed with a confidence measure. Elicitation Requests are made when the
49 * expected value gain exceeds the elicitation cost.
50 *
51 */
52public class AngelParty extends DefaultParty {
53
54//*****************************************************************************************************************
55 // BACK END variables
56 private PartyId me; // Identifies ANGEL
57 private final Random random = new Random(); // Used for the Gaussian Distribution
58 protected ProfileInterface profileint; // Will allow us to access info about Domain or Profile
59 private Progress progress; // ~TODO~ Understand this
60
61 // BID SPACE INFORMATION -> remove if there is a super easy way to access this
62 private int m; // m is the number of issues
63 private int d; // d is the number of bids in the partial preference profile
64 private Double e = 0.01; // elicitation cost, denoted 'epsilon'
65 private Double spent = 0.0; // Whenever we elicit, keep track of how much has been spent
66 private Bid reservation; // Best alternative to negotiated agreement
67 private Double reserve_utility; // Reserve is in the form of a bid, not a value, so reserve_utility is an
68 // estimation.
69 private int T; // number of rounds
70 private int t = 0; // current round, updated manually
71 private int tmav = -1; // the last round t on which mav was updated
72
73 // MEMORY -> recording all of the estimates for updating and evaluating
74 // This models both our human's and the opponent's utility functions
75 private HashSet<String> issues; // Conveniently storing the Issues for access
76 private HashMap<String, ValueSet> issueValues = new HashMap(); // Conveniently storing the IssueValues, accessed via
77 // the Issues
78
79 private HashMap<String, HashMap<geniusweb.issuevalue.Value, Double>> au = new HashMap(); // angel
80 // estimated_utilites[issue][issueval]
81 // = estimate
82 private HashMap<String, Double> aW = new HashMap(); // angel estimated_weights[issue] = estimate
83 private HashMap<String, HashMap<geniusweb.issuevalue.Value, Double>> ac = new HashMap(); // angel
84 // issval_confindences[issue][issueval]
85 // = estimate
86
87 private HashMap<String, HashMap<geniusweb.issuevalue.Value, Double>> ou = new HashMap(); // Estimated utilities for
88 // the opponent
89 private HashMap<String, Double> oW = new HashMap(); // Estimated weights for the opponent's issues
90 private HashMap<String, HashMap<geniusweb.issuevalue.Value, Double>> oc = new HashMap(); // Confidence in ou
91
92 private Bid highestReceivedBid; // opponents highest offer so far
93 private Bid lastReceivedBid; // last received offer from opponent
94 private Bid lastSentOffer; // our previous offer
95 private int stepsDown = 0; // used to possible pick counter offer if ^^^ do not work
96
97 // Additional random memory components
98 private HashSet<ArrayList<Bid>> comparisons = new HashSet(); // Collection of all one-one comparisons, bid1 >= bid2
99 private HashSet<ArrayList<Bid>> oppComparisons = new HashSet(); // Comparisons like for ourselves made from opp
100 // offers, models opp
101 private SimpleLinearOrdering estimatedProfile; // The ordering of all known bids
102 // TODO ^ stop using the getUtility method, estimate utility with
103 // function U
104 private boolean already_initialized = false; // Just to make sure that the agent gets initialized properly
105 private Double mav = 1.0; // Minimum accepted value, number to decay when conceding
106 private Bid lastElicitedBid; // Used for filling comparisons
107
108//*****************************************************************************************************************
109 // Create agent
110 public AngelParty() {
111 }
112
113 public AngelParty(Reporter reporter) {
114 super(reporter); // for debugging -> Allegedly
115 }
116
117//*****************************************************************************************************************
118 // Have the back end handled
119 // TODO certify that there is no conflict between this and the desired ANGEL
120 // protocol
121 // Probably best to leave these methods alone (for the most part)
122 @Override
123 public void notifyChange(Inform info) {
124 try {
125 if (info instanceof Settings) {
126 Settings settings = (Settings) info;
127 this.profileint = ProfileConnectionFactory.create(settings.getProfile().getURI(), getReporter());
128 this.estimatedProfile = new SimpleLinearOrdering(profileint.getProfile());
129 this.reservation = profileint.getProfile().getReservationBid(); // Boy howdy I hope this works
130 this.issues = new HashSet<String>(profileint.getProfile().getDomain().getIssues());
131 this.m = this.issues.size();
132 for (String issue : this.issues) {
133 this.issueValues.put(issue, profileint.getProfile().getDomain().getValues(issue));
134 }
135 this.me = settings.getID();
136 this.progress = settings.getProgress();
137 if (settings.getParameters().get("elicitationcost") != null) {
138 this.e = (double) settings.getParameters().get("elicitationcost");
139 }
140 this.T = ((ProgressRounds) settings.getProgress()).getTotalRounds();
141 if (!already_initialized) {
142 // System.out.println(getName() + " is initializing information ");
143 // System.out.println(getName()+"'s profile is
144 // "+estimatedProfile.getBids().toString());
145 // Initialize all estimates, offer our best bid
146 for (Bid bid : estimatedProfile.getBids()) {
147 bid = fillBidIssues(bid);
148 }
149 initAngelComparisons(estimatedProfile);
150 d = estimatedProfile.getBids().size();
151 Double[] normalUtils = initNormalUtils();
152 for (int idx = 0; idx < normalUtils.length; idx++) {
153 // System.out.print(" "+normalUtils[idx]);
154 }
155 initAngelWeights(estimatedProfile, normalUtils);
156 initOppWeights();
157 initAngelUtils(estimatedProfile, normalUtils);
158 initOppUtils();
159 initAngelConfidences(estimatedProfile);
160 initOppConfidences();
161 // System.out.println(getName()+" init the utils to " +au);
162 // System.out.println(getName()+" init the weights to " +aW);
163 // System.out.println("Just after initialization, there are this many faults:
164 // "+countFaults(comparisons)+" out of "+comparisons.size()+" comparisons");
165
166 // Now adjust to see if the number of faults goes down significantly / at all
167 // move through new comparisons and perform fault adjustments
168
169 for (ArrayList<Bid> comparison : comparisons) {
170 if (isFault(comparison)) {
171 handleFaultForComparison(comparison);
172 }
173 }
174 // adjust confidences
175 for (String issue : issues) {
176 for (geniusweb.issuevalue.Value lambda : issueValues.get(issue)) {
177 adjustConfidenceForIssueValue(issue, lambda, comparisons);
178 }
179 }
180 // System.out.println("Now there are this many faults:
181 // "+countFaults(comparisons)+" out of "+comparisons.size()+" comparisons");
182 }
183 } else if (info instanceof ActionDone) {
184 Action otheract = ((ActionDone) info).getAction();
185 // System.out.println(getName()+" received action "+ otheract.toString());
186 if (otheract instanceof Offer) {
187 lastReceivedBid = ((Offer) otheract).getBid();
188 lastReceivedBid = fillBidIssues(lastReceivedBid);
189 // System.out.println(getName()+" evaluated the offer "+ lastReceivedBid+" as
190 // "+calculateBidUtility(lastReceivedBid));
191 double lastUtil = calculateBidUtility(lastReceivedBid);
192 double bestUtil = calculateBidUtility(highestReceivedBid);
193 if (lastUtil > bestUtil) {
194 highestReceivedBid = lastReceivedBid;
195 }
196 } else if (otheract instanceof Comparison) {
197 estimatedProfile = estimatedProfile.with(((Comparison) otheract).getBid(),
198 ((Comparison) otheract).getWorse());
199 for (Bid better : ((Comparison) otheract).getBetter()) {
200 ArrayList<Bid> comparison = new ArrayList<Bid>();
201 comparison.add(better);
202 comparison.add(lastElicitedBid);
203 comparisons.add(comparison);
204 }
205 HashSet<ArrayList<Bid>> newComparisons = new HashSet();
206 for (Bid worse : ((Comparison) otheract).getWorse()) {
207 ArrayList<Bid> comparison = new ArrayList<Bid>();
208 comparison.add(lastElicitedBid);
209 comparison.add(worse);
210 newComparisons.add(comparison);
211 }
212 // add each new comparison to comparisons
213 for (ArrayList<Bid> comparison : newComparisons) {
214 comparisons.add(comparison);
215 }
216 int beforeFaultsNewInfo = countFaults(newComparisons);
217 int beforeFaultsTotalInfo = countFaults(comparisons);
218 // move through new comparisons and perform fault adjustments
219 for (ArrayList<Bid> comparison : newComparisons) {
220 if (isFault(comparison)) {
221 handleFaultForComparison(comparison);
222 }
223 }
224 // adjust confidences
225 for (String issue : issues) {
226 for (geniusweb.issuevalue.Value lambda : issueValues.get(issue)) {
227 adjustConfidenceForIssueValue(issue, lambda, newComparisons);
228 }
229 }
230 // System.out.println(getName()+" updated personal estimates, weights are now:
231 // "+aW.toString());
232 int afterFaultsNewInfo = countFaults(newComparisons);
233 int afterFaultsTotalInfo = countFaults(comparisons);
234 // TODO log these results if they were unfavorable
235 if (beforeFaultsNewInfo < afterFaultsNewInfo) {
236 // System.out.println("%%%%%%%%% Faults in new info before update: "+
237 // beforeFaultsNewInfo +" after: "+afterFaultsNewInfo);
238 }
239 if (beforeFaultsTotalInfo < afterFaultsTotalInfo) {
240 // System.out.println("%%%%%%%%% Faults in total before update:
241 // "+beforeFaultsTotalInfo+" after: "+afterFaultsTotalInfo);
242 }
243 try {
244 myTurn();
245 } catch (Exception e) {
246 throw new RuntimeException("Error inside myTurn", e);
247 }
248 }
249 } else if (info instanceof YourTurn) {
250 try {
251 myTurn();
252 } catch (Exception e) {
253 throw new RuntimeException("Error inside myTurn", e);
254 }
255 } else if (info instanceof Finished) {
256 // System.out.println(getName()+" received info -> Finished");
257 getReporter().log(Level.INFO, "Final ourcome:" + info);
258 }
259 } catch (Exception e) {
260 throw new RuntimeException("Failed to handle info", e);
261 }
262 }
263
264 @Override
265 public Capabilities getCapabilities() {
266 return new Capabilities(new HashSet<>(Arrays.asList("SHAOP")), Collections.singleton(Profile.class));
267 }
268
269 @Override
270 public String getDescription() {
271 return "Greedy concession strategy, elicits information from COB "
272 + "when there is low confidence in best counter-offer prediction. Requires elicitationcost parameter to be set."
273 + " Original design by Andrew DeVoss and Robert Geraghty";
274 }
275
276//*****************************************************************************************************************
277 // Executing the heuristic by calling the methods defined later
278 // code the ANGEL protocol by ^
279 /**
280 * Called when it's (still) our turn and we should take some action. Also
281 * Updates the progress if necessary.
282 */
283 private void myTurn() throws IOException {
284 Action action = null;
285 // System.out.println(getName()+" is taking a turn ");
286 t += 1; // Update the turn, making sure that this is counter-balanced if an elicitation
287 // request is made.
288 if (t != tmav) {
289 recalculateMAV(T, t);
290 // System.out.println(getName()+" has a new mav of "+mav+" on round "+t);
291 }
292 if (!already_initialized) {
293 Bid bestBid = estimatedProfile.getBids().get(estimatedProfile.getBids().size() - 1);
294 lastSentOffer = bestBid;
295 action = new Offer(me, bestBid);
296 already_initialized = true;
297 if (progress instanceof ProgressRounds) {
298 progress = ((ProgressRounds) progress).advance();
299 }
300 }
301 Bid co = counterOffer(lastReceivedBid, highestReceivedBid, lastSentOffer);
302 if (shouldElicit(co, e) && action == null && co != lastElicitedBid) {
303 // System.out.println(getName() + " is eliciting info about "+co);
304 action = new ElicitComparison(me, co, estimatedProfile.getBids());
305 tmav = t;
306 lastElicitedBid = co;
307 // Note: estimates updated from the inform change method, not here.
308 }
309 if (action == null && lastReceivedBid != null) {
310 // check to see if we want to accept the opponent's offer
311 boolean acceptable = isGood(lastReceivedBid, mav);
312 if (acceptable) {
313 // System.out.println(getName() + " is accepting an offer: mav="+mav+" expected
314 // value="+calculateBidUtility(lastReceivedBid));
315 action = new Accept(me, lastReceivedBid);
316 }
317 // TODO update opponent estimates based on their offer
318 // every time they reject our offer and give a new co, we assume opp believes co
319 // >= angel_last_offer
320 else if (lastSentOffer != null) {
321 // System.out.println(getName() + " is updating opponent model ");
322 ArrayList<Bid> comparison = new ArrayList<Bid>();
323 comparison.add(lastReceivedBid);
324 comparison.add(lastSentOffer);
325 oppComparisons.add(comparison);
326 // Since we have new information, update the utility estimates based on the
327 // known space.
328 int beforeFaults = countFaultsOpp(oppComparisons);
329 for (ArrayList<Bid> comp : oppComparisons) {
330 if (isFault(comp)) {
331 handleFaultForComparisonOpp(comp);
332 }
333 }
334 // Now update the opp confidence estimations based on the results.
335 for (String issue : issues) {
336 for (geniusweb.issuevalue.Value lambda : issueValues.get(issue)) {
337 adjustConfidenceForIssueValueOpp(issue, lambda, oppComparisons);
338 }
339 }
340 int afterFaults = countFaultsOpp(oppComparisons);
341 if (beforeFaults < afterFaults) {
342 ;
343 }
344 }
345 if (progress instanceof ProgressRounds) {
346 progress = ((ProgressRounds) progress).advance();
347 }
348 }
349 // If we don't accept, package the next bid, see if we should elicit, repackage
350 // when necessary
351 if (action == null && co != lastElicitedBid && shouldElicit(co, e)) {
352 // System.out.println(getName() + " is eliciting info about "+co);
353 action = new ElicitComparison(me, co, estimatedProfile.getBids());
354 tmav = t;
355 t -= 1;
356 lastElicitedBid = co;
357 // Note: estimates updated from the inform change method, not here.
358 }
359 if (action == null) {
360 // System.out.println(getName() + " is offering bid "+co+" with expected utility
361 // "+calculateBidUtility(co));
362 action = new Offer(me, co);
363 lastSentOffer = co;
364 }
365 // System.out.println(getName()+"'s action is "+action.toString());
366 getConnection().send(action);
367 }
368
369//*****************************************************************************************************************
370 // Initialization routines
371
372 private Double[] initNormalUtils() {
373 // Use these utilities for initial bid evaluations
374 Double[] normalUtils = new Double[d];
375 normalUtils[0] = 0.0;
376 normalUtils[d - 1] = 1.0;
377 // now create d - 2 comparisons by sampling from N(.5, 1), clipping to [0, 1],
378 // and then ordering
379 Double[] tempNorms = new Double[d - 2];
380 for (int i = 0; i < d - 2; i++) {
381 Double contender = (random.nextGaussian() + .5);
382 while (contender < 0 || contender > 1) {
383 contender = (random.nextGaussian() + .5);
384 }
385 tempNorms[i] = contender;
386 }
387 Arrays.sort(tempNorms);
388
389 for (int i = 0; i < d - 2; i++) {
390 normalUtils[i + 1] = tempNorms[i];
391 }
392 return normalUtils;
393 }
394
395 private void initAngelWeights(SimpleLinearOrdering providedBids, Double[] utils) {
396 // Iterate over the ordering of bids. Work with bid if it contains lambda in
397 // best/worst bids
398 // weight = avg(bid with best lambda) - avg(bid with worst lambda)
399 HashMap<String, geniusweb.issuevalue.Value> bestLambdas = new HashMap<String, geniusweb.issuevalue.Value>();
400 HashMap<String, geniusweb.issuevalue.Value> worstLambdas = new HashMap<String, geniusweb.issuevalue.Value>();
401 List<Bid> bids = providedBids.getBids(); // I checked, this is actually sorted
402 for (String issue : issues) {
403 bestLambdas.put(issue, bids.get(d - 1).getValue(issue));
404 }
405 for (String issue : issues) {
406 worstLambdas.put(issue, bids.get(0).getValue(issue));
407 }
408 HashMap<String, Double> highSums = new HashMap<String, Double>();
409 HashMap<String, Integer> highCounts = new HashMap<String, Integer>();
410 HashMap<String, Double> lowSums = new HashMap<String, Double>();
411 HashMap<String, Integer> lowCounts = new HashMap<String, Integer>();
412 // Fill the initial sums and counts with 0s
413 for (String issue : issues) {
414 highSums.put(issue, 0.0);
415 lowSums.put(issue, 0.0);
416 highCounts.put(issue, 0);
417 lowCounts.put(issue, 0);
418 }
419 // Even though we are iterating over all of the bids, we need to know the bid
420 // number
421 // so that we can retrieve the corresponding bid utility.
422 for (int bid = 0; bid < d; bid++) {
423 Bid curr = bids.get(bid);
424 for (String issue : issues) {
425 if (curr.getValue(issue).equals(bestLambdas.get(issue))) {
426 highSums.put(issue, highSums.get(issue) + utils[bid]);
427 highCounts.put(issue, highCounts.get(issue) + 1);
428 }
429 if (curr.getValue(issue).equals(worstLambdas.get(issue))) {
430 lowSums.put(issue, lowSums.get(issue) + utils[bid]);
431 lowCounts.put(issue, lowCounts.get(issue) + 1);
432 }
433 }
434 }
435 // Now we have a count of total val of issues with lambda in best and worst
436 // bids,
437 // and associated counts for computing the average.
438 // We want to compute the average, and then normalize by the sum.
439 // Add 1.0 to each value (ensuring positive) then divide by sum.
440 HashMap<String, Double> weights = new HashMap<String, Double>();
441 Double sum = 0.0;
442 for (String issue : issues) {
443 Double amt = highSums.get(issue) / highCounts.get(issue) - lowSums.get(issue) / lowCounts.get(issue) + 1.0;
444 weights.put(issue, amt);
445 sum += amt;
446 }
447 for (String issue : issues) {
448 aW.put(issue, weights.get(issue) / sum);
449 }
450 }
451
452 private void initOppWeights() {
453 // Initialize the weights for the opponent estimates
454 Double avg = 1.0 / m;
455 for (String issue : issues) {
456 oW.put(issue, avg);
457 }
458 }
459
460 private void initAngelUtils(SimpleLinearOrdering providedBids, Double[] utils) {
461 // If this is not efficient enough, we could instead loop through all of the
462 // bids once
463 // and update values for each of the issue values inside during the singular
464 // pass through.
465 // I chose to do it this way because it feels more intuitive, though less
466 // efficient. -Andrew
467
468 // For each issue value:
469 // utility estimate is avg(bid containing issue value)
470 // If there is an issue value that is not present in any of the bids,
471 // it gets the median value of all issue values in same issue.
472 List<Bid> bids = providedBids.getBids();
473 for (String issue : issues) {
474 HashSet<geniusweb.issuevalue.Value> unseenLambdas = new HashSet<geniusweb.issuevalue.Value>();
475 au.put(issue, new HashMap<geniusweb.issuevalue.Value, Double>());
476 for (geniusweb.issuevalue.Value lambda : issueValues.get(issue)) {
477 // If lambda for the issue is in the best bid, set the utility to 1
478 Bid bestBid = bids.get(d - 1);
479 Bid worstBid = bids.get(0);
480 geniusweb.issuevalue.Value bestLambda = bestBid.getValue(issue);
481 geniusweb.issuevalue.Value worstLambda = worstBid.getValue(issue);
482 if (bestLambda.equals(lambda)) {
483 au.get(issue).put(lambda, 1.0);
484 } else if (worstLambda.equals(lambda)) {
485 au.get(issue).put(lambda, 0.0);
486 }
487 // Now loop through all of the remaining bids, checking if bid[issue] has
488 // lambda.
489 else {
490 int count = 0;
491 Double sum = 0.0;
492 for (int bid = 1; bid < d - 1; bid++) {
493 geniusweb.issuevalue.Value lambdaPrime = bids.get(bid).getValue(issue);
494 if (lambdaPrime.equals(lambda)) {
495 count += 1;
496 sum += utils[bid];
497 }
498 }
499 if (count == 0) {
500 unseenLambdas.add(lambda);
501 } else {
502 au.get(issue).put(lambda, sum / count);
503 }
504 }
505 }
506 // Finally, assign to each of the unseen lambdas the MEDIAN value of all of the
507 // other issue values within the same issue.
508 // Get the MEDIAN
509 List<Double> sortedValues = new ArrayList<Double>(au.get(issue).values());
510 Collections.sort(sortedValues);
511 int knownLambdas = sortedValues.size();
512 Double median;
513 if (knownLambdas % 2 == 0) {
514 int firstIdx = knownLambdas / 2;
515 int secondIdx = firstIdx - 1;
516 Double firstVal = sortedValues.get(firstIdx);
517 Double secondVal = sortedValues.get(secondIdx);
518 median = (firstVal + secondVal / 2.0);
519 } else {
520 int idx = knownLambdas / 2;
521 median = sortedValues.get(idx);
522 }
523 // Now assign the median value to every lambda in unseenLambdas
524 for (geniusweb.issuevalue.Value lambda : unseenLambdas) {
525 au.get(issue).put(lambda, median);
526 }
527 }
528 }
529
530 private void initOppUtils() {
531 // Init the opponent utility estimates. They start as .5 for each lambda
532 for (String issue : issues) {
533 ou.put(issue, new HashMap<geniusweb.issuevalue.Value, Double>());
534 for (geniusweb.issuevalue.Value lambda : issueValues.get(issue)) {
535 ou.get(issue).put(lambda, 0.5);
536 }
537 }
538 }
539
540 private void initAngelConfidences(SimpleLinearOrdering providedBids) {
541 // Confidence in lambdas in best/worst bids = 1
542 // otherwise confidence = .8
543 List<Bid> bids = providedBids.getBids();
544 Bid bestBid = bids.get(d - 1);
545 Bid worstBid = bids.get(0);
546 for (String issue : issues) {
547 ac.put(issue, new HashMap<geniusweb.issuevalue.Value, Double>());
548 for (geniusweb.issuevalue.Value lambda : issueValues.get(issue)) {
549 if (bestBid.getValue(issue).equals(lambda) || worstBid.getValue(issue).equals(lambda)) {
550 ac.get(issue).put(lambda, 1.0);
551 } else {
552 ac.get(issue).put(lambda, 0.8);
553 }
554 }
555 }
556 }
557
558 private void initOppConfidences() {
559 // Confidence in all values for the opponent start at .5
560 for (String issue : issues) {
561 oc.put(issue, new HashMap<geniusweb.issuevalue.Value, Double>());
562 for (geniusweb.issuevalue.Value lambda : issueValues.get(issue)) {
563 oc.get(issue).put(lambda, 0.8);
564 }
565 }
566 }
567
568 private void initAngelComparisons(SimpleLinearOrdering providedBids) {
569 List<Bid> bids = providedBids.getBids();
570 int stop = bids.size();
571 for (int lowIdx = 0; lowIdx < stop; lowIdx++) {
572 for (int highIdx = 0; highIdx < stop; highIdx++) {
573 Bid low = bids.get(lowIdx);
574 Bid high = bids.get(highIdx);
575 ArrayList<Bid> comparison = new ArrayList<Bid>();
576 comparison.add(high);
577 comparison.add(low);
578 comparisons.add(comparison);
579 }
580 }
581 }
582
583//*****************************************************************************************************************
584 // Main routines for ANGEL during the action of the negotiation
585 private Bid fillBidIssues(Bid bid) {
586 // If a bid does not contain a value for every issue, then fill it
587 // with the item worth 0 from that issue (from the worst bid)
588 if (bid.getIssues().size() == issues.size()) {
589 return bid;
590 }
591 // System.out.println(" FILLING A BID ");
592 HashMap<String, geniusweb.issuevalue.Value> newBid = new HashMap<String, geniusweb.issuevalue.Value>();
593 Set<String> hadIssues = bid.getIssues();
594 for (String issue : issues) {
595 if (hadIssues.contains(issue)) {
596 newBid.put(issue, bid.getValue(issue));
597 } else {
598 geniusweb.issuevalue.Value lambda = estimatedProfile.getBids().get(0).getValue(issue);
599 newBid.put(issue, lambda);
600 }
601 }
602 Bid filledBid = new Bid(newBid);
603 return filledBid;
604 }
605
606 private void handleFaultForComparison(ArrayList<Bid> comparison) {
607 // Given one comparison, this adjusts the estimates for
608 // weights and then issueValue utility so that the
609 // resulting estimates are equal.
610 Bid tooHigh = comparison.get(1);
611 Bid tooLow = comparison.get(0);
612 Double difference = calculateBidUtility(tooLow) - calculateBidUtility(tooHigh);
613 HashMap<String, Double> alteredWeights = new HashMap<String, Double>();
614 HashMap<String, Double> originalEst = new HashMap<String, Double>();
615 Double sum = 0.0;
616 for (String issue : issues) {
617 Double w_issue = aW.get(issue);
618 Double u_issue = au.get(issue).get(tooHigh.getValue(issue));
619 originalEst.put(issue, w_issue * u_issue);
620 Double w_alt = 1 + w_issue - ac.get(issue).get(tooHigh.getValue(issue)) * difference / issues.size();
621 alteredWeights.put(issue, w_alt);
622 sum += w_alt;
623 }
624 double temp_sum = 0.0;
625 for (String issue : issues) {
626 aW.put(issue, alteredWeights.get(issue) / sum);
627 temp_sum += alteredWeights.get(issue) / sum;
628 }
629 assert (temp_sum - 1.0 < .00001 && temp_sum - 1.0 > -.00001);
630 Double distributeAmt = 0.0;
631 int count = 1;
632 for (String issue : issues) {
633 if (ac.get(issue).get(tooHigh.getValue(issue)).equals(1.0)) {
634 count += 1;
635 distributeAmt += originalEst.get(issue) - aW.get(issue) * au.get(issue).get(tooHigh.getValue(issue));
636 }
637 }
638 for (String issue : issues) {
639 if (!ac.get(issue).get(tooHigh.getValue(issue)).equals(1.0)) {
640 Double newVal = (originalEst.get(issue) - (difference / issues.size() + distributeAmt / count))
641 / aW.get(issue);
642 // TODO, figure out why this might be happening
643 if (newVal > .99) {
644 newVal = .99;
645 }
646 au.get(issue).put(tooHigh.getValue(issue), newVal);
647 }
648 }
649 }
650
651 private void handleFaultForBatchOfComparisons(HashSet<ArrayList<Bid>> comparisons) {
652 // TODO write this method for updating utility and weight estimates from
653 // new information all at once, if we want that functionality.
654 ;
655 }
656
657 private int countFaults(HashSet<ArrayList<Bid>> comparisons) {
658 // Note: A comparison is a collection of two bids such that bid1 >= bid2.
659 // This method iterates over a collection of comparisons and
660 // counts the number of faults in the collection.
661 int numFaults = 0;
662 for (ArrayList<Bid> comparison : comparisons) {
663 Double highVal = calculateBidUtility(comparison.get(0));
664 Double lowVal = calculateBidUtility(comparison.get(1));
665 if (highVal < lowVal) {
666 numFaults += 1;
667 }
668 }
669 return numFaults;
670 }
671
672 private void adjustConfidenceForIssueValue(String issue, geniusweb.issuevalue.Value lambda,
673 HashSet<ArrayList<Bid>> comparisons) {
674 // Goes through a collection of comparisons and counts the number of faults
675 // where lambda is in a bid. Then confidence is adjusted.
676 if (ac.get(issue).get(lambda).equals(1.0)) {
677 return;
678 }
679 int faults = 0;
680 for (ArrayList<Bid> comparison : comparisons) {
681 Double highVal = calculateBidUtility(comparison.get(0));
682 Double lowVal = calculateBidUtility(comparison.get(1));
683 if (highVal < lowVal) {
684 Bid highBid = comparison.get(0);
685 Bid lowBid = comparison.get(1);
686 if (highBid.getValue(issue).equals(lambda) || lowBid.getValue(issue).equals(lambda)) {
687 faults += 1;
688 }
689 }
690 }
691 // Adjust the confidence as the average of the old confidence and the new
692 // confidence
693 Double oldConf = ac.get(issue).get(lambda);
694 Double newConf = (oldConf + (1.0 - faults) / comparisons.size()) / 2;
695 ac.get(issue).put(lambda, newConf);
696 }
697
698 private void recalculateMAV(int Rounds, int round) {
699 // Decay the MAV over the rounds, conservatively at first.
700 // For rounds<80% of Rounds, decay 10% of the way
701 // For rounds 80%-90% of Rounds, decay 20% of the way
702 // For rounds > 90%, decay the rest of the way
703 // The decay is linear between 1 and max(highestOppOfferUtil, reservationUtil)
704 Double hiOpp = calculateBidUtility(highestReceivedBid);
705 Double reserve = calculateBidUtility(reservation);
706 // change mav to slightly lower than hiOpp to prevent being overly greedy in the
707 // final rounds
708 if (hiOpp > reserve) {
709 hiOpp = hiOpp - .2 * (hiOpp - reserve);
710 }
711 Double end = Math.max(reserve, hiOpp);
712 if (round <= .7 * Rounds) {
713 Double y2 = 1.0;
714 Double y1 = (1 - .3 * (1 - end));
715 int x2 = 0;
716 Double x1 = .7 * Rounds;
717 Double m = (y2 - y1) / (x2 - x1);
718 this.mav = m * round + 1;
719 } else if (round <= .8 * Rounds) {
720 Double y2 = (1 - .3 * (1 - end));
721 Double y1 = (1 - .5 * (1 - end));
722 Double x2 = .7 * Rounds;
723 Double x1 = .8 * Rounds;
724 Double m = (y2 - y1) / (x2 - x1);
725 Double b = y2 - (m * x2);
726 this.mav = m * round + b;
727 } else {
728 Double y2 = (1 - .5 * (1 - end));
729 Double y1 = end;
730 Double x2 = .8 * Rounds;
731 int x1 = Rounds;
732 Double m = (y2 - y1) / (x2 - x1);
733 Double b = y2 - (m * x2);
734 this.mav = m * round + b;
735 }
736 if (mav < Math.max(reserve, hiOpp)) {
737 this.mav = Math.max(reserve, hiOpp);
738 }
739 }
740
741 private Bid counterOffer(Bid previousOpponentOffer, Bid highestOpponentOffer, Bid previousAngelOffer) {
742 // Main idea: create three counter offers by adjusting
743 // our previous offer, opp previous offer, opp highest offer
744 // ensure that the values are higher than the MAV
745 // select the offer with the highest expected return weighted by confidence(?)
746
747 // For the previousOpponentOffer and the highestOpponentOffer, we want to call
748 // the bidStepUp method
749 // For previousAngelOffer, call the bidStepDown method.
750
751 // This is just a temporary idea for how to package the next counter-offer until
752 // we get the agent functional.
753 // check the ****SCALED?***** utility of each of the packaged offers. If none of
754 // them are higher than
755 // the minimum accepted value, check the previous offer. If it is also evaluated
756 // as not high enough
757 // then instead, default to the best bid in our bid list.
758 Bid bid1 = null;
759 Bid bid2 = null;
760 Bid bid3 = null;
761 if (previousOpponentOffer != null) {
762 bid1 = bidStepUp(previousOpponentOffer);
763 }
764 if (highestOpponentOffer != null) {
765 bid2 = bidStepUp(highestOpponentOffer);
766 }
767 if (previousAngelOffer != null) {
768 bid3 = bidStepDown(previousAngelOffer);
769 }
770 Double est1 = calculateBidUtility(bid1);
771 Double est2 = calculateBidUtility(bid2);
772 Double est3 = calculateBidUtility(bid3);
773 if (est1 >= mav && est1 >= est2 && est1 >= est3) {
774 // System.out.println(getName()+" Made counter offer by modifying prev opp
775 // offer");
776 return bid1;
777 } else if (est2 >= mav && est2 >= est1 && est2 >= est3) {
778 // System.out.println(getName()+" Made counter offer by modifying highest opp
779 // offer");
780 return bid2;
781 } else if (est3 >= mav && est3 >= est1 && est3 >= est2) {
782 // System.out.println(getName()+" Made counter offer by modifying previous own
783 // offer");
784 return bid3;
785 } else if (stepsDown < d && calculateBidUtility(estimatedProfile.getBids().get(d - 1 - stepsDown)) > mav) {
786 // System.out.println(getName()+" Made counter offer by stepping down in
787 // profile");
788 Bid known = estimatedProfile.getBids().get(d - 1 - stepsDown);
789 stepsDown += 1;
790 return known;
791
792 } else if (calculateBidUtility(previousAngelOffer) > mav) {
793 // System.out.println(getName()+" Made counter offer by sending previous offer
794 // again ");
795 return previousAngelOffer;
796 } else {
797 // System.out.println(getName()+" DEFAULTED TO BEST BID CO ");
798 return estimatedProfile.getBids().get(estimatedProfile.getBids().size() - 1);
799 }
800 }
801
802 private boolean shouldElicit(Bid counteroffer, Double elicitationCost) {
803 // Is the expected value gained > elicitation cost
804 if (estimatedProfile.contains(counteroffer)) {
805 return false;
806 }
807 boolean needMoreInfo = false;
808 Double expectedValueOfKnowledge = calculateBidUtility(counteroffer)
809 - calculateConfidenceScaledBidUtility(counteroffer);
810 // System.out.println(getName()+"'s expected value of knowledge is
811 // "+expectedValueOfKnowledge);
812 if (expectedValueOfKnowledge > spent + elicitationCost) {
813 spent += elicitationCost;
814 needMoreInfo = true;
815 }
816 return needMoreInfo;
817 }
818
819//*****************************************************************************************************************
820 // Random subroutines that flush the main routines
821 private boolean isGood(Bid bid, Double mav) {
822 // Check that the estimated utility of the bid is higher
823 // than the minimum accepted utility
824 // Make sure not to accept a bid known to be worse than reservation
825 if (estimatedProfile.contains(bid) && estimatedProfile.contains(reservation)) {
826 int bidx = 0;
827 int ridx = 0;
828 for (int i = 0; i < estimatedProfile.getBids().size(); i++) {
829 if (estimatedProfile.getBids().get(i).equals(bid)) {
830 bidx = i;
831 } else if (estimatedProfile.getBids().get(i).equals(reservation)) {
832 ridx = i;
833 }
834 }
835 if (bidx < ridx) {
836 return false;
837 }
838 }
839 for (ArrayList<Bid> comparison : comparisons) {
840 if (comparison.get(0).equals(reservation) && comparison.get(0).equals(bid)) {
841 return false;
842 }
843 }
844 boolean acceptable = false;
845 Double expectedValue = calculateBidUtility(bid);
846 if (expectedValue >= mav) {
847 acceptable = true;
848 }
849 return acceptable;
850 }
851
852 private Double calculateBidUtility(Bid bid) {
853 // Implement the linear additive function U(omega): Omega -> [0,1]
854 // SUM( weight*utility )
855 if (bid == null) {
856 return 0.0;
857 }
858
859 Double utility = 0.0;
860 HashMap<String, ArrayList<Double>> vals = new HashMap<String, ArrayList<Double>>();
861 HashMap<String, geniusweb.issuevalue.Value> theBid = new HashMap(bid.getIssueValues());
862 for (String issue : theBid.keySet()) {
863 utility += aW.get(issue) * au.get(issue).get(theBid.get(issue));
864 ArrayList<Double> weightUtil = new ArrayList<Double>();
865 weightUtil.add(aW.get(issue));
866 weightUtil.add(au.get(issue).get(theBid.get(issue)));
867 vals.put(issue, weightUtil);
868 }
869 if (utility > 1.0) {
870 // System.out.println("\n\n\n*****UTILITY OF "+utility+"\n\n\n");
871 // System.out.println(vals.toString());
872 assert (!(utility > 1.00001));
873 }
874 return utility;
875 }
876
877 private Double calculateConfidenceScaledBidUtility(Bid bid) {
878 // scaled estimation = SUM( weight*utility*confidence )
879 if (bid == null) {
880 return 0.0;
881 }
882 Double scaledUtility = 0.0;
883 HashMap<String, geniusweb.issuevalue.Value> theBid = new HashMap<String, geniusweb.issuevalue.Value>(
884 bid.getIssueValues());
885 for (String issue : theBid.keySet()) {
886 scaledUtility += aW.get(issue) * au.get(issue).get(theBid.get(issue))
887 * ac.get(issue).get(theBid.get(issue));
888 }
889 return scaledUtility;
890 }
891
892 private Bid bidStepDown(Bid greedyBid) {
893 // Take a bid that we consider really good
894 // and slightly lower the value of it with opponent model, changing only one
895 // issue value
896 // We want to change the value in the issue with greatest difference = (their
897 // issue weight - our issue weight)
898
899 // TODO perhaps repeat the pick and replace movement until the estimated value >
900 // mav****
901 greedyBid = fillBidIssues(greedyBid);
902 String pivotIss = "";
903 for (String issue : issues) {
904 pivotIss = issue;
905 break;
906 }
907 Double highestDiff = 0.0;
908 for (String issue : issues) {
909 Double difference = oW.get(issue) - aW.get(issue);
910 if (difference > highestDiff) {
911 highestDiff = difference;
912 pivotIss = issue;
913 }
914 }
915 geniusweb.issuevalue.Value nextLowestLambda = null;
916 Double low = -2.0;
917 Double high = au.get(pivotIss).get(greedyBid.getValue(pivotIss));
918 for (geniusweb.issuevalue.Value lambda : issueValues.get(pivotIss)) {
919 Double util = au.get(pivotIss).get(lambda);
920 if (util > low && util < high) {
921 low = util;
922 nextLowestLambda = lambda;
923 }
924 }
925 HashMap<String, geniusweb.issuevalue.Value> newBid = new HashMap<String, geniusweb.issuevalue.Value>();
926 for (String issue : issues) {
927 if (issue.equals(pivotIss)) {
928 if (nextLowestLambda != null) {
929 newBid.put(issue, nextLowestLambda);
930 } else {
931 newBid.put(issue, greedyBid.getValue(issue));
932 }
933 } else {
934 geniusweb.issuevalue.Value lambda = greedyBid.getValue(issue);
935 newBid.put(issue, lambda);
936 }
937 }
938 Bid bid = new Bid(newBid);
939 return bid;
940 }
941
942 private Bid bidStepUp(Bid ickyBid) {
943 // Take a bid that we think is not good enough
944 // and alter it so that we like it better by changing only one issue value
945 // We want to change the value in the issue with greatest difference = (our
946 // issue weight - their issue weight)
947
948 // TODO perhaps repeat the pick and replace movement until the estimated value >
949 // mav****
950 ickyBid = fillBidIssues(ickyBid);
951 String pivotIss = "";
952 Double highestDiff = 0.0;
953 for (String issue : issues) {
954 Double difference = aW.get(issue) - oW.get(issue);
955 if (difference > highestDiff) {
956 highestDiff = difference;
957 pivotIss = issue;
958 }
959 }
960 geniusweb.issuevalue.Value bestLambdaInIssue = (estimatedProfile.getBids()
961 .get(estimatedProfile.getBids().size() - 1)).getValue(pivotIss);
962 HashMap<String, geniusweb.issuevalue.Value> newBid = new HashMap<String, geniusweb.issuevalue.Value>();
963 for (String issue : issues) {
964 if (issue.equals(pivotIss)) {
965 newBid.put(issue, bestLambdaInIssue);
966 } else {
967 geniusweb.issuevalue.Value lambda = ickyBid.getValue(issue);
968 newBid.put(issue, lambda);
969 }
970 }
971 Bid bid = new Bid(newBid);
972 return bid;
973 }
974
975 private boolean isFault(ArrayList<Bid> comparison) {
976 boolean fault = false;
977 Double highVal = calculateBidUtility(comparison.get(0));
978 Double lowVal = calculateBidUtility(comparison.get(1));
979 if (highVal < lowVal) {
980 fault = true;
981 }
982 return fault;
983 }
984
985 public String getName() {
986 return me.toString();
987 }
988
989//*****************************************************************************************************************
990 // Routines for Opponent updating
991 private Double calculateBidUtilityOpp(Bid bid) {
992 // Implement the linear additive function U(omega): Omega -> [0,1]
993 // SUM( weight*utility )
994 if (bid == null) {
995 return 0.0;
996 }
997
998 Double utility = 0.0;
999 HashMap<String, geniusweb.issuevalue.Value> theBid = new HashMap(bid.getIssueValues());
1000 for (String issue : theBid.keySet()) {
1001 utility += oW.get(issue) * ou.get(issue).get(theBid.get(issue));
1002 }
1003 return utility;
1004 }
1005
1006 private int countFaultsOpp(HashSet<ArrayList<Bid>> comparisons) {
1007 int numFaults = 0;
1008 for (ArrayList<Bid> comparison : comparisons) {
1009 Double highVal = calculateBidUtilityOpp(comparison.get(0));
1010 Double lowVal = calculateBidUtilityOpp(comparison.get(1));
1011 if (highVal < lowVal) {
1012 numFaults += 1;
1013 }
1014 }
1015 return numFaults;
1016 }
1017
1018 private void handleFaultForComparisonOpp(ArrayList<Bid> comparison) {
1019 // Given one comparison, this adjusts the estimates for
1020 // weights and then issueValue utility so that the
1021 // resulting estimates are equal.
1022 Bid tooHigh = comparison.get(1);
1023 Bid tooLow = comparison.get(0);
1024 Double difference = calculateBidUtilityOpp(tooLow) - calculateBidUtilityOpp(tooHigh);
1025 HashMap<String, Double> alteredWeights = new HashMap<String, Double>();
1026 HashMap<String, Double> originalEst = new HashMap<String, Double>();
1027 Double sum = 0.0;
1028 for (String issue : issues) {
1029 Double w_issue = oW.get(issue);
1030 Double u_issue = ou.get(issue).get(tooHigh.getValue(issue));
1031 originalEst.put(issue, w_issue * u_issue);
1032 Double w_alt = 1 + w_issue - oc.get(issue).get(tooHigh.getValue(issue)) * difference / issues.size();
1033 alteredWeights.put(issue, w_alt);
1034 sum += w_alt;
1035 }
1036 for (String issue : issues) {
1037 oW.put(issue, alteredWeights.get(issue) / sum);
1038 }
1039 Double distributeAmt = 0.0;
1040 int count = 1;
1041 for (String issue : issues) {
1042 if (oc.get(issue).get(tooHigh.getValue(issue)).equals(1.0)) {
1043 count += 1;
1044 distributeAmt += originalEst.get(issue) - oW.get(issue) * ou.get(issue).get(tooHigh.getValue(issue));
1045 }
1046 }
1047 for (String issue : issues) {
1048 if (!oc.get(issue).get(tooHigh.getValue(issue)).equals(1.0)) {
1049 Double newVal = (originalEst.get(issue) - (difference / issues.size() + distributeAmt / count))
1050 / oW.get(issue);
1051 ou.get(issue).put(tooHigh.getValue(issue), newVal);
1052 }
1053 }
1054 }
1055
1056 private void adjustConfidenceForIssueValueOpp(String issue, geniusweb.issuevalue.Value lambda,
1057 HashSet<ArrayList<Bid>> comparisons) {
1058 int faults = 0;
1059 for (ArrayList<Bid> comparison : comparisons) {
1060 if (isFault(comparison)) {
1061 Collection<geniusweb.issuevalue.Value> highLambdas = comparison.get(0).getIssueValues().values();
1062 Collection<geniusweb.issuevalue.Value> lowLambdas = comparison.get(1).getIssueValues().values();
1063 if (highLambdas.contains(lambda) || lowLambdas.contains(lambda)) {
1064 faults += 1;
1065 }
1066 }
1067 }
1068 // Adjust the confidence as the average of the old confidence and the new
1069 // confidence
1070 Double oldConf = oc.get(issue).get(lambda);
1071 Double newConf = (oldConf + (1.0 - faults) / comparisons.size()) / 2;
1072 oc.get(issue).put(lambda, newConf);
1073 }
1074}
Note: See TracBrowser for help on using the repository browser.