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
RevLine 
[1]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;
[29]10import java.util.ArrayList;
[1]11import java.util.Arrays;
[29]12import java.util.Collection;
13import java.util.Collections;
14import java.util.HashMap;
[1]15import java.util.HashSet;
[29]16import java.util.List;
[1]17import java.util.Random;
[29]18import java.util.Set;
[1]19import java.util.logging.Level;
[29]20
[1]21import geniusweb.actions.Accept;
22import geniusweb.actions.Action;
23import geniusweb.actions.Comparison;
24import geniusweb.actions.ElicitComparison;
25import geniusweb.actions.Offer;
26import geniusweb.actions.PartyId;
[29]27import geniusweb.inform.ActionDone;
28import geniusweb.inform.Finished;
29import geniusweb.inform.Inform;
30import geniusweb.inform.Settings;
31import geniusweb.inform.YourTurn;
[1]32import geniusweb.issuevalue.Bid;
33import geniusweb.issuevalue.ValueSet;
34import geniusweb.party.Capabilities;
35import geniusweb.party.DefaultParty;
[29]36import geniusweb.profile.Profile;
[1]37import geniusweb.profileconnection.ProfileConnectionFactory;
38import geniusweb.profileconnection.ProfileInterface;
39import geniusweb.progress.Progress;
40import geniusweb.progress.ProgressRounds;
41import tudelft.utilities.logging.Reporter;
42
43/**
[29]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.
[1]50 *
51 */
52public class AngelParty extends DefaultParty {
53
54//*****************************************************************************************************************
55 // BACK END variables
[29]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
[1]60
61 // BID SPACE INFORMATION -> remove if there is a super easy way to access this
[29]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
[1]72
73 // MEMORY -> recording all of the estimates for updating and evaluating
[29]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
[1]78
[29]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
[1]108//*****************************************************************************************************************
109 // Create agent
110 public AngelParty() {
111 }
112
113 public AngelParty(Reporter reporter) {
[29]114 super(reporter); // for debugging -> Allegedly
[1]115 }
[29]116
[1]117//*****************************************************************************************************************
118 // Have the back end handled
[29]119 // TODO certify that there is no conflict between this and the desired ANGEL
120 // protocol
[1]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;
[29]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
[1]130 this.issues = new HashSet<String>(profileint.getProfile().getDomain().getIssues());
[29]131 this.m = this.issues.size();
132 for (String issue : this.issues) {
[1]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) {
[29]138 this.e = (double) settings.getParameters().get("elicitationcost");
[1]139 }
140 this.T = ((ProgressRounds) settings.getProgress()).getTotalRounds();
141 if (!already_initialized) {
[29]142 // System.out.println(getName() + " is initializing information ");
143 // System.out.println(getName()+"'s profile is
144 // "+estimatedProfile.getBids().toString());
[1]145 // Initialize all estimates, offer our best bid
[29]146 for (Bid bid : estimatedProfile.getBids()) {
[1]147 bid = fillBidIssues(bid);
148 }
149 initAngelComparisons(estimatedProfile);
150 d = estimatedProfile.getBids().size();
151 Double[] normalUtils = initNormalUtils();
[29]152 for (int idx = 0; idx < normalUtils.length; idx++) {
153 // System.out.print(" "+normalUtils[idx]);
[1]154 }
155 initAngelWeights(estimatedProfile, normalUtils);
156 initOppWeights();
157 initAngelUtils(estimatedProfile, normalUtils);
158 initOppUtils();
159 initAngelConfidences(estimatedProfile);
160 initOppConfidences();
[29]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
[1]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
[29]169 for (ArrayList<Bid> comparison : comparisons) {
[1]170 if (isFault(comparison)) {
171 handleFaultForComparison(comparison);
172 }
173 }
174 // adjust confidences
[29]175 for (String issue : issues) {
176 for (geniusweb.issuevalue.Value lambda : issueValues.get(issue)) {
177 adjustConfidenceForIssueValue(issue, lambda, comparisons);
[1]178 }
179 }
[29]180 // System.out.println("Now there are this many faults:
181 // "+countFaults(comparisons)+" out of "+comparisons.size()+" comparisons");
[1]182 }
183 } else if (info instanceof ActionDone) {
184 Action otheract = ((ActionDone) info).getAction();
[29]185 // System.out.println(getName()+" received action "+ otheract.toString());
[1]186 if (otheract instanceof Offer) {
187 lastReceivedBid = ((Offer) otheract).getBid();
188 lastReceivedBid = fillBidIssues(lastReceivedBid);
[29]189 // System.out.println(getName()+" evaluated the offer "+ lastReceivedBid+" as
190 // "+calculateBidUtility(lastReceivedBid));
[1]191 double lastUtil = calculateBidUtility(lastReceivedBid);
192 double bestUtil = calculateBidUtility(highestReceivedBid);
[29]193 if (lastUtil > bestUtil) {
[1]194 highestReceivedBid = lastReceivedBid;
195 }
196 } else if (otheract instanceof Comparison) {
[29]197 estimatedProfile = estimatedProfile.with(((Comparison) otheract).getBid(),
[1]198 ((Comparison) otheract).getWorse());
[29]199 for (Bid better : ((Comparison) otheract).getBetter()) {
[1]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();
[29]206 for (Bid worse : ((Comparison) otheract).getWorse()) {
[1]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
[29]213 for (ArrayList<Bid> comparison : newComparisons) {
[1]214 comparisons.add(comparison);
215 }
216 int beforeFaultsNewInfo = countFaults(newComparisons);
217 int beforeFaultsTotalInfo = countFaults(comparisons);
218 // move through new comparisons and perform fault adjustments
[29]219 for (ArrayList<Bid> comparison : newComparisons) {
[1]220 if (isFault(comparison)) {
221 handleFaultForComparison(comparison);
222 }
223 }
224 // adjust confidences
[29]225 for (String issue : issues) {
226 for (geniusweb.issuevalue.Value lambda : issueValues.get(issue)) {
227 adjustConfidenceForIssueValue(issue, lambda, newComparisons);
[1]228 }
229 }
[29]230 // System.out.println(getName()+" updated personal estimates, weights are now:
231 // "+aW.toString());
[1]232 int afterFaultsNewInfo = countFaults(newComparisons);
233 int afterFaultsTotalInfo = countFaults(comparisons);
234 // TODO log these results if they were unfavorable
235 if (beforeFaultsNewInfo < afterFaultsNewInfo) {
[29]236 // System.out.println("%%%%%%%%% Faults in new info before update: "+
237 // beforeFaultsNewInfo +" after: "+afterFaultsNewInfo);
238 }
[1]239 if (beforeFaultsTotalInfo < afterFaultsTotalInfo) {
[29]240 // System.out.println("%%%%%%%%% Faults in total before update:
241 // "+beforeFaultsTotalInfo+" after: "+afterFaultsTotalInfo);
242 }
[1]243 try {
244 myTurn();
[29]245 } catch (Exception e) {
[1]246 throw new RuntimeException("Error inside myTurn", e);
247 }
248 }
249 } else if (info instanceof YourTurn) {
250 try {
251 myTurn();
[29]252 } catch (Exception e) {
[1]253 throw new RuntimeException("Error inside myTurn", e);
254 }
255 } else if (info instanceof Finished) {
[29]256 // System.out.println(getName()+" received info -> Finished");
[1]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() {
[29]266 return new Capabilities(new HashSet<>(Arrays.asList("SHAOP")), Collections.singleton(Profile.class));
[1]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
[29]278 // code the ANGEL protocol by ^
[1]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;
[29]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.
[1]288 if (t != tmav) {
289 recalculateMAV(T, t);
[29]290 // System.out.println(getName()+" has a new mav of "+mav+" on round "+t);
[1]291 }
292 if (!already_initialized) {
[29]293 Bid bestBid = estimatedProfile.getBids().get(estimatedProfile.getBids().size() - 1);
[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);
[29]302 if (shouldElicit(co, e) && action == null && co != lastElicitedBid) {
303 // System.out.println(getName() + " is eliciting info about "+co);
[1]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 }
[29]309 if (action == null && lastReceivedBid != null) {
[1]310 // check to see if we want to accept the opponent's offer
311 boolean acceptable = isGood(lastReceivedBid, mav);
312 if (acceptable) {
[29]313 // System.out.println(getName() + " is accepting an offer: mav="+mav+" expected
314 // value="+calculateBidUtility(lastReceivedBid));
[1]315 action = new Accept(me, lastReceivedBid);
316 }
317 // TODO update opponent estimates based on their offer
[29]318 // every time they reject our offer and give a new co, we assume opp believes co
319 // >= angel_last_offer
[1]320 else if (lastSentOffer != null) {
[29]321 // System.out.println(getName() + " is updating opponent model ");
[1]322 ArrayList<Bid> comparison = new ArrayList<Bid>();
323 comparison.add(lastReceivedBid);
324 comparison.add(lastSentOffer);
325 oppComparisons.add(comparison);
[29]326 // Since we have new information, update the utility estimates based on the
327 // known space.
[1]328 int beforeFaults = countFaultsOpp(oppComparisons);
[29]329 for (ArrayList<Bid> comp : oppComparisons) {
[1]330 if (isFault(comp)) {
[29]331 handleFaultForComparisonOpp(comp);
[1]332 }
333 }
334 // Now update the opp confidence estimations based on the results.
[29]335 for (String issue : issues) {
336 for (geniusweb.issuevalue.Value lambda : issueValues.get(issue)) {
337 adjustConfidenceForIssueValueOpp(issue, lambda, oppComparisons);
[1]338 }
339 }
340 int afterFaults = countFaultsOpp(oppComparisons);
[29]341 if (beforeFaults < afterFaults) {
342 ;
343 }
[1]344 }
345 if (progress instanceof ProgressRounds) {
346 progress = ((ProgressRounds) progress).advance();
347 }
348 }
[29]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);
[1]353 action = new ElicitComparison(me, co, estimatedProfile.getBids());
354 tmav = t;
[29]355 t -= 1;
[1]356 lastElicitedBid = co;
357 // Note: estimates updated from the inform change method, not here.
358 }
[29]359 if (action == null) {
360 // System.out.println(getName() + " is offering bid "+co+" with expected utility
361 // "+calculateBidUtility(co));
[1]362 action = new Offer(me, co);
363 lastSentOffer = co;
364 }
[29]365 // System.out.println(getName()+"'s action is "+action.toString());
366 getConnection().send(action);
[1]367 }
[29]368
[1]369//*****************************************************************************************************************
370 // Initialization routines
[29]371
372 private Double[] initNormalUtils() {
[1]373 // Use these utilities for initial bid evaluations
374 Double[] normalUtils = new Double[d];
375 normalUtils[0] = 0.0;
[29]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) {
[1]383 contender = (random.nextGaussian() + .5);
384 }
385 tempNorms[i] = contender;
386 }
387 Arrays.sort(tempNorms);
[29]388
389 for (int i = 0; i < d - 2; i++) {
390 normalUtils[i + 1] = tempNorms[i];
[1]391 }
392 return normalUtils;
393 }
[29]394
[1]395 private void initAngelWeights(SimpleLinearOrdering providedBids, Double[] utils) {
[29]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)
[1]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
[29]402 for (String issue : issues) {
403 bestLambdas.put(issue, bids.get(d - 1).getValue(issue));
[1]404 }
[29]405 for (String issue : issues) {
[1]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
[29]413 for (String issue : issues) {
414 highSums.put(issue, 0.0);
415 lowSums.put(issue, 0.0);
[1]416 highCounts.put(issue, 0);
417 lowCounts.put(issue, 0);
418 }
[29]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++) {
[1]423 Bid curr = bids.get(bid);
[29]424 for (String issue : issues) {
[1]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 }
[29]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.
[1]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;
[29]442 for (String issue : issues) {
443 Double amt = highSums.get(issue) / highCounts.get(issue) - lowSums.get(issue) / lowCounts.get(issue) + 1.0;
[1]444 weights.put(issue, amt);
445 sum += amt;
446 }
[29]447 for (String issue : issues) {
448 aW.put(issue, weights.get(issue) / sum);
449 }
[1]450 }
[29]451
[1]452 private void initOppWeights() {
453 // Initialize the weights for the opponent estimates
[29]454 Double avg = 1.0 / m;
455 for (String issue : issues) {
[1]456 oW.put(issue, avg);
457 }
458 }
[29]459
[1]460 private void initAngelUtils(SimpleLinearOrdering providedBids, Double[] utils) {
[29]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
[1]468 // For each issue value:
[29]469 // utility estimate is avg(bid containing issue value)
[1]470 // If there is an issue value that is not present in any of the bids,
[29]471 // it gets the median value of all issue values in same issue.
[1]472 List<Bid> bids = providedBids.getBids();
[29]473 for (String issue : issues) {
[1]474 HashSet<geniusweb.issuevalue.Value> unseenLambdas = new HashSet<geniusweb.issuevalue.Value>();
475 au.put(issue, new HashMap<geniusweb.issuevalue.Value, Double>());
[29]476 for (geniusweb.issuevalue.Value lambda : issueValues.get(issue)) {
[1]477 // If lambda for the issue is in the best bid, set the utility to 1
[29]478 Bid bestBid = bids.get(d - 1);
[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)) {
[29]483 au.get(issue).put(lambda, 1.0);
484 } else if (worstLambda.equals(lambda)) {
485 au.get(issue).put(lambda, 0.0);
[1]486 }
[29]487 // Now loop through all of the remaining bids, checking if bid[issue] has
488 // lambda.
[1]489 else {
490 int count = 0;
[29]491 Double sum = 0.0;
492 for (int bid = 1; bid < d - 1; bid++) {
[1]493 geniusweb.issuevalue.Value lambdaPrime = bids.get(bid).getValue(issue);
494 if (lambdaPrime.equals(lambda)) {
495 count += 1;
496 sum += utils[bid];
497 }
498 }
[29]499 if (count == 0) {
[1]500 unseenLambdas.add(lambda);
[29]501 } else {
502 au.get(issue).put(lambda, sum / count);
[1]503 }
504 }
505 }
[29]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
[1]509 List<Double> sortedValues = new ArrayList<Double>(au.get(issue).values());
510 Collections.sort(sortedValues);
511 int knownLambdas = sortedValues.size();
512 Double median;
[29]513 if (knownLambdas % 2 == 0) {
514 int firstIdx = knownLambdas / 2;
515 int secondIdx = firstIdx - 1;
[1]516 Double firstVal = sortedValues.get(firstIdx);
517 Double secondVal = sortedValues.get(secondIdx);
[29]518 median = (firstVal + secondVal / 2.0);
519 } else {
520 int idx = knownLambdas / 2;
[1]521 median = sortedValues.get(idx);
522 }
523 // Now assign the median value to every lambda in unseenLambdas
[29]524 for (geniusweb.issuevalue.Value lambda : unseenLambdas) {
[1]525 au.get(issue).put(lambda, median);
526 }
527 }
528 }
[29]529
[1]530 private void initOppUtils() {
531 // Init the opponent utility estimates. They start as .5 for each lambda
[29]532 for (String issue : issues) {
[1]533 ou.put(issue, new HashMap<geniusweb.issuevalue.Value, Double>());
[29]534 for (geniusweb.issuevalue.Value lambda : issueValues.get(issue)) {
535 ou.get(issue).put(lambda, 0.5);
[1]536 }
537 }
538 }
[29]539
[1]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();
[29]544 Bid bestBid = bids.get(d - 1);
[1]545 Bid worstBid = bids.get(0);
[29]546 for (String issue : issues) {
[1]547 ac.put(issue, new HashMap<geniusweb.issuevalue.Value, Double>());
[29]548 for (geniusweb.issuevalue.Value lambda : issueValues.get(issue)) {
[1]549 if (bestBid.getValue(issue).equals(lambda) || worstBid.getValue(issue).equals(lambda)) {
[29]550 ac.get(issue).put(lambda, 1.0);
551 } else {
552 ac.get(issue).put(lambda, 0.8);
[1]553 }
554 }
555 }
556 }
557
558 private void initOppConfidences() {
559 // Confidence in all values for the opponent start at .5
[29]560 for (String issue : issues) {
[1]561 oc.put(issue, new HashMap<geniusweb.issuevalue.Value, Double>());
[29]562 for (geniusweb.issuevalue.Value lambda : issueValues.get(issue)) {
563 oc.get(issue).put(lambda, 0.8);
[1]564 }
565 }
566 }
[29]567
[1]568 private void initAngelComparisons(SimpleLinearOrdering providedBids) {
569 List<Bid> bids = providedBids.getBids();
570 int stop = bids.size();
[29]571 for (int lowIdx = 0; lowIdx < stop; lowIdx++) {
572 for (int highIdx = 0; highIdx < stop; highIdx++) {
[1]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
[29]585 private Bid fillBidIssues(Bid bid) {
[1]586 // If a bid does not contain a value for every issue, then fill it
[29]587 // with the item worth 0 from that issue (from the worst bid)
[1]588 if (bid.getIssues().size() == issues.size()) {
589 return bid;
590 }
[29]591 // System.out.println(" FILLING A BID ");
[1]592 HashMap<String, geniusweb.issuevalue.Value> newBid = new HashMap<String, geniusweb.issuevalue.Value>();
593 Set<String> hadIssues = bid.getIssues();
[29]594 for (String issue : issues) {
[1]595 if (hadIssues.contains(issue)) {
596 newBid.put(issue, bid.getValue(issue));
[29]597 } else {
[1]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 }
[29]605
[1]606 private void handleFaultForComparison(ArrayList<Bid> comparison) {
607 // Given one comparison, this adjusts the estimates for
[29]608 // weights and then issueValue utility so that the
609 // resulting estimates are equal.
[1]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>();
[29]615 Double sum = 0.0;
616 for (String issue : issues) {
[1]617 Double w_issue = aW.get(issue);
618 Double u_issue = au.get(issue).get(tooHigh.getValue(issue));
[29]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();
[1]621 alteredWeights.put(issue, w_alt);
622 sum += w_alt;
623 }
624 double temp_sum = 0.0;
[29]625 for (String issue : issues) {
626 aW.put(issue, alteredWeights.get(issue) / sum);
627 temp_sum += alteredWeights.get(issue) / sum;
[1]628 }
[29]629 assert (temp_sum - 1.0 < .00001 && temp_sum - 1.0 > -.00001);
630 Double distributeAmt = 0.0;
[1]631 int count = 1;
[29]632 for (String issue : issues) {
[1]633 if (ac.get(issue).get(tooHigh.getValue(issue)).equals(1.0)) {
634 count += 1;
[29]635 distributeAmt += originalEst.get(issue) - aW.get(issue) * au.get(issue).get(tooHigh.getValue(issue));
[1]636 }
637 }
[29]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);
[1]642 // TODO, figure out why this might be happening
[29]643 if (newVal > .99) {
644 newVal = .99;
645 }
[1]646 au.get(issue).put(tooHigh.getValue(issue), newVal);
647 }
648 }
649 }
[29]650
[1]651 private void handleFaultForBatchOfComparisons(HashSet<ArrayList<Bid>> comparisons) {
652 // TODO write this method for updating utility and weight estimates from
[29]653 // new information all at once, if we want that functionality.
[1]654 ;
655 }
[29]656
[1]657 private int countFaults(HashSet<ArrayList<Bid>> comparisons) {
658 // Note: A comparison is a collection of two bids such that bid1 >= bid2.
[29]659 // This method iterates over a collection of comparisons and
660 // counts the number of faults in the collection.
[1]661 int numFaults = 0;
[29]662 for (ArrayList<Bid> comparison : comparisons) {
[1]663 Double highVal = calculateBidUtility(comparison.get(0));
664 Double lowVal = calculateBidUtility(comparison.get(1));
[29]665 if (highVal < lowVal) {
666 numFaults += 1;
[1]667 }
668 }
669 return numFaults;
670 }
[29]671
672 private void adjustConfidenceForIssueValue(String issue, geniusweb.issuevalue.Value lambda,
673 HashSet<ArrayList<Bid>> comparisons) {
[1]674 // Goes through a collection of comparisons and counts the number of faults
[29]675 // where lambda is in a bid. Then confidence is adjusted.
676 if (ac.get(issue).get(lambda).equals(1.0)) {
677 return;
678 }
[1]679 int faults = 0;
[29]680 for (ArrayList<Bid> comparison : comparisons) {
[1]681 Double highVal = calculateBidUtility(comparison.get(0));
682 Double lowVal = calculateBidUtility(comparison.get(1));
[29]683 if (highVal < lowVal) {
[1]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 }
[29]691 // Adjust the confidence as the average of the old confidence and the new
692 // confidence
[1]693 Double oldConf = ac.get(issue).get(lambda);
[29]694 Double newConf = (oldConf + (1.0 - faults) / comparisons.size()) / 2;
[1]695 ac.get(issue).put(lambda, newConf);
696 }
[29]697
[1]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);
[29]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 }
[1]711 Double end = Math.max(reserve, hiOpp);
[29]712 if (round <= .7 * Rounds) {
[1]713 Double y2 = 1.0;
[29]714 Double y1 = (1 - .3 * (1 - end));
[1]715 int x2 = 0;
[29]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));
[1]729 Double y1 = end;
[29]730 Double x2 = .8 * Rounds;
[1]731 int x1 = Rounds;
[29]732 Double m = (y2 - y1) / (x2 - x1);
733 Double b = y2 - (m * x2);
734 this.mav = m * round + b;
[1]735 }
[29]736 if (mav < Math.max(reserve, hiOpp)) {
737 this.mav = Math.max(reserve, hiOpp);
738 }
[1]739 }
[29]740
741 private Bid counterOffer(Bid previousOpponentOffer, Bid highestOpponentOffer, Bid previousAngelOffer) {
[1]742 // Main idea: create three counter offers by adjusting
[29]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
[1]749 // For previousAngelOffer, call the bidStepDown method.
[29]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.
[1]758 Bid bid1 = null;
759 Bid bid2 = null;
760 Bid bid3 = null;
[29]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 }
[1]770 Double est1 = calculateBidUtility(bid1);
771 Double est2 = calculateBidUtility(bid2);
772 Double est3 = calculateBidUtility(bid3);
[29]773 if (est1 >= mav && est1 >= est2 && est1 >= est3) {
774 // System.out.println(getName()+" Made counter offer by modifying prev opp
775 // offer");
[1]776 return bid1;
[29]777 } else if (est2 >= mav && est2 >= est1 && est2 >= est3) {
778 // System.out.println(getName()+" Made counter offer by modifying highest opp
779 // offer");
[1]780 return bid2;
[29]781 } else if (est3 >= mav && est3 >= est1 && est3 >= est2) {
782 // System.out.println(getName()+" Made counter offer by modifying previous own
783 // offer");
[1]784 return bid3;
[29]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;
[1]790 return known;
[29]791
792 } else if (calculateBidUtility(previousAngelOffer) > mav) {
793 // System.out.println(getName()+" Made counter offer by sending previous offer
794 // again ");
[1]795 return previousAngelOffer;
[29]796 } else {
797 // System.out.println(getName()+" DEFAULTED TO BEST BID CO ");
[1]798 return estimatedProfile.getBids().get(estimatedProfile.getBids().size() - 1);
799 }
800 }
[29]801
[1]802 private boolean shouldElicit(Bid counteroffer, Double elicitationCost) {
803 // Is the expected value gained > elicitation cost
[29]804 if (estimatedProfile.contains(counteroffer)) {
805 return false;
806 }
[1]807 boolean needMoreInfo = false;
808 Double expectedValueOfKnowledge = calculateBidUtility(counteroffer)
[29]809 - calculateConfidenceScaledBidUtility(counteroffer);
810 // System.out.println(getName()+"'s expected value of knowledge is
811 // "+expectedValueOfKnowledge);
812 if (expectedValueOfKnowledge > spent + elicitationCost) {
[1]813 spent += elicitationCost;
814 needMoreInfo = true;
815 }
816 return needMoreInfo;
817 }
[29]818
[1]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
[29]823 // than the minimum accepted utility
[1]824 // Make sure not to accept a bid known to be worse than reservation
825 if (estimatedProfile.contains(bid) && estimatedProfile.contains(reservation)) {
[29]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 }
[1]834 }
[29]835 if (bidx < ridx) {
836 return false;
837 }
[1]838 }
[29]839 for (ArrayList<Bid> comparison : comparisons) {
840 if (comparison.get(0).equals(reservation) && comparison.get(0).equals(bid)) {
841 return false;
842 }
[1]843 }
844 boolean acceptable = false;
845 Double expectedValue = calculateBidUtility(bid);
[29]846 if (expectedValue >= mav) {
[1]847 acceptable = true;
848 }
849 return acceptable;
850 }
[29]851
[1]852 private Double calculateBidUtility(Bid bid) {
853 // Implement the linear additive function U(omega): Omega -> [0,1]
854 // SUM( weight*utility )
[29]855 if (bid == null) {
[1]856 return 0.0;
857 }
[29]858
859 Double utility = 0.0;
[1]860 HashMap<String, ArrayList<Double>> vals = new HashMap<String, ArrayList<Double>>();
861 HashMap<String, geniusweb.issuevalue.Value> theBid = new HashMap(bid.getIssueValues());
[29]862 for (String issue : theBid.keySet()) {
[1]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 }
[29]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;
[1]875 }
[29]876
[1]877 private Double calculateConfidenceScaledBidUtility(Bid bid) {
878 // scaled estimation = SUM( weight*utility*confidence )
[29]879 if (bid == null) {
[1]880 return 0.0;
881 }
[29]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));
[1]888 }
[29]889 return scaledUtility;
[1]890 }
[29]891
[1]892 private Bid bidStepDown(Bid greedyBid) {
893 // Take a bid that we consider really good
[29]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****
[1]901 greedyBid = fillBidIssues(greedyBid);
[29]902 String pivotIss = "";
903 for (String issue : issues) {
904 pivotIss = issue;
905 break;
906 }
[1]907 Double highestDiff = 0.0;
[29]908 for (String issue : issues) {
909 Double difference = oW.get(issue) - aW.get(issue);
910 if (difference > highestDiff) {
[1]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));
[29]918 for (geniusweb.issuevalue.Value lambda : issueValues.get(pivotIss)) {
[1]919 Double util = au.get(pivotIss).get(lambda);
920 if (util > low && util < high) {
[29]921 low = util;
[1]922 nextLowestLambda = lambda;
923 }
924 }
925 HashMap<String, geniusweb.issuevalue.Value> newBid = new HashMap<String, geniusweb.issuevalue.Value>();
[29]926 for (String issue : issues) {
[1]927 if (issue.equals(pivotIss)) {
[29]928 if (nextLowestLambda != null) {
929 newBid.put(issue, nextLowestLambda);
930 } else {
931 newBid.put(issue, greedyBid.getValue(issue));
932 }
933 } else {
[1]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 }
[29]941
[1]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
[29]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****
[1]950 ickyBid = fillBidIssues(ickyBid);
951 String pivotIss = "";
952 Double highestDiff = 0.0;
[29]953 for (String issue : issues) {
954 Double difference = aW.get(issue) - oW.get(issue);
[1]955 if (difference > highestDiff) {
956 highestDiff = difference;
957 pivotIss = issue;
958 }
959 }
[29]960 geniusweb.issuevalue.Value bestLambdaInIssue = (estimatedProfile.getBids()
961 .get(estimatedProfile.getBids().size() - 1)).getValue(pivotIss);
[1]962 HashMap<String, geniusweb.issuevalue.Value> newBid = new HashMap<String, geniusweb.issuevalue.Value>();
[29]963 for (String issue : issues) {
[1]964 if (issue.equals(pivotIss)) {
965 newBid.put(issue, bestLambdaInIssue);
[29]966 } else {
[1]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));
[29]979 if (highVal < lowVal) {
[1]980 fault = true;
981 }
982 return fault;
983 }
984
985 public String getName() {
986 return me.toString();
987 }
[29]988
[1]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 )
[29]994 if (bid == null) {
[1]995 return 0.0;
996 }
[29]997
998 Double utility = 0.0;
[1]999 HashMap<String, geniusweb.issuevalue.Value> theBid = new HashMap(bid.getIssueValues());
[29]1000 for (String issue : theBid.keySet()) {
[1]1001 utility += oW.get(issue) * ou.get(issue).get(theBid.get(issue));
1002 }
[29]1003 return utility;
[1]1004 }
[29]1005
[1]1006 private int countFaultsOpp(HashSet<ArrayList<Bid>> comparisons) {
1007 int numFaults = 0;
[29]1008 for (ArrayList<Bid> comparison : comparisons) {
[1]1009 Double highVal = calculateBidUtilityOpp(comparison.get(0));
1010 Double lowVal = calculateBidUtilityOpp(comparison.get(1));
[29]1011 if (highVal < lowVal) {
1012 numFaults += 1;
[1]1013 }
1014 }
1015 return numFaults;
1016 }
1017
1018 private void handleFaultForComparisonOpp(ArrayList<Bid> comparison) {
1019 // Given one comparison, this adjusts the estimates for
[29]1020 // weights and then issueValue utility so that the
1021 // resulting estimates are equal.
[1]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>();
[29]1027 Double sum = 0.0;
1028 for (String issue : issues) {
[1]1029 Double w_issue = oW.get(issue);
1030 Double u_issue = ou.get(issue).get(tooHigh.getValue(issue));
[29]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();
[1]1033 alteredWeights.put(issue, w_alt);
1034 sum += w_alt;
1035 }
[29]1036 for (String issue : issues) {
1037 oW.put(issue, alteredWeights.get(issue) / sum);
[1]1038 }
[29]1039 Double distributeAmt = 0.0;
[1]1040 int count = 1;
[29]1041 for (String issue : issues) {
1042 if (oc.get(issue).get(tooHigh.getValue(issue)).equals(1.0)) {
[1]1043 count += 1;
[29]1044 distributeAmt += originalEst.get(issue) - oW.get(issue) * ou.get(issue).get(tooHigh.getValue(issue));
[1]1045 }
1046 }
[29]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);
[1]1051 ou.get(issue).put(tooHigh.getValue(issue), newVal);
1052 }
1053 }
1054 }
[29]1055
1056 private void adjustConfidenceForIssueValueOpp(String issue, geniusweb.issuevalue.Value lambda,
1057 HashSet<ArrayList<Bid>> comparisons) {
[1]1058 int faults = 0;
[29]1059 for (ArrayList<Bid> comparison : comparisons) {
[1]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 }
[29]1068 // Adjust the confidence as the average of the old confidence and the new
1069 // confidence
[1]1070 Double oldConf = oc.get(issue).get(lambda);
[29]1071 Double newConf = (oldConf + (1.0 - faults) / comparisons.size()) / 2;
[1]1072 oc.get(issue).put(lambda, newConf);
1073 }
1074}
Note: See TracBrowser for help on using the repository browser.