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

Last change on this file since 14 was 1, checked in by wouter, 4 years ago

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