source: src/main/java/bargainingchips/players/NiceTitForTatNegotiationAgent.java@ 341

Last change on this file since 341 was 340, checked in by Tim Baarslag, 5 years ago

Change BilateralProtocol loop to avoid busy wait; note that this fixes only a part of the busy wait problem.

Package structure now in line with latest Acumex discussions.

Pinpointed error avoidance in Agent.
File size: 20.2 KB
Line 
1package bargainingchips.players;
2
3import static java.lang.Math.pow;
4
5import java.util.ArrayList;
6import java.util.List;
7import java.util.Random;
8import java.util.concurrent.BlockingQueue;
9
10import bargainingchips.Bundle;
11import bargainingchips.NegotiationContext;
12import bargainingchips.OutcomeSpace;
13import bargainingchips.actions.Bid;
14import bargainingchips.actions.FinalAccept;
15import bargainingchips.actions.Offer;
16import bargainingchips.actions.OfferBy;
17import bargainingchips.actions.OfferType;
18import bargainingchips.actions.PreAccept;
19import bargainingchips.analysis.BundleUtilityPoint;
20import bargainingchips.analysis.BundleUtilitySpace;
21import bargainingchips.messaging.coordination.CoordinationMessage;
22import bargainingchips.messaging.status.StatusMessage;
23import bargainingchips.outcomes.Outcome;
24import bargainingchips.players.Agent;
25import bargainingchips.utilityfunctions.UtilityFunction;
26import bargainingchips.players.history.BidEvent;
27import bargainingchips.players.history.BidEventHistory;
28import bargainingchips.players.history.BidEventHistoryKeeper;
29
30//import agents.bayesianopponentmodel.BayesianOpponentModelScalable;
31//import agents.bayesianopponentmodel.OpponentModelUtilSpace;
32
33//import bargainingchips.players.TitForTatNegotiationAgent.BayesianOpponentModelScalable;
34
35/**
36 * @version 1
37 *
38 * This TitForTatNegotiatingAgent adapts {@link /NegotiatorGUI/src/main/java/agents/anac/y2011/Nice_Tit_for_Tat} [1],
39 * according to Bargaining Chips definitions. Tit-for-Tat strategy has been successful in reaching Nash equilibrium,
40 * a pessimistic solution (not the optimistic Pareto solution) in repeated infinite Prisoners' Dilemma games assuming
41 * the definition given for `rationality'. Although, not all humans and also all rational humans behaves under that
42 * definition for rationality, but this class is as a test base skeleton for other agents which uses Tit-For-Tat.
43 *
44 * [1] T. Baarslag, K. Hindriks, C. Jonker, A tit for tat negotiation strategy for real-time bilateral negotiations,
45 * Complex Automated Negotiations, 229-233 (2013).
46 *
47 *
48 * @author Faria Nassiri-Mofakham
49 *
50 */
51
52public abstract class NiceTitForTatNegotiationAgent extends HistoryAgent
53{
54 private static final double TIME_USED_TO_DETERMINE_OPPONENT_STARTING_POINT = 0.01;
55
56 private Offer lastReceivedOffer = null;
57
58 /**
59 * Indicates the number of times we have offered the best bid by the
60 * opponent so far (which means we are very close to the deadline and wanted
61 * to accept)
62 */
63 private int offeredOpponentBestBid = 0;
64
65 private long DOMAINSIZE;
66 private List<Bundle> space;
67
68 //private BayesianOpponentModelScalable opponentModel;
69
70 private double myNashUtility;
71
72 private double initialGap;
73 private final boolean TEST_EQUIVALENCE = false;
74 private Random random100;
75
76
77 public NiceTitForTatNegotiationAgent(String name, UtilityFunction u, NegotiationContext nc,
78 BlockingQueue<Offer> in,
79 BlockingQueue<OfferBy> out,
80 BlockingQueue<CoordinationMessage> cin,
81 BlockingQueue<StatusMessage> cout) {
82 super(name, u, nc, in, out, cin, cout);
83 }
84
85 @Override
86 public void init() {
87 super.init();
88 space = outcomeSpace.getAllBids(); //getNumberOfPossibleBids();
89 //prepareOpponentModel();
90 DOMAINSIZE = space.size();
91 if (TEST_EQUIVALENCE) {
92 random100 = new Random(100);
93 } else {
94 random100 = new Random();
95 }
96 log("Domain size: " + DOMAINSIZE);
97 }
98
99//**
100 protected void prepareOpponentModel() {
101// opponentModel = new BayesianOpponentModelScalable( // for OPPONENT MODEL
102// (AdditiveUtilitySpace) utilitySpace);
103 }
104
105 @Override
106// public Bundle chooseCounterBid() {
107 protected Bundle getNextBid()
108 {
109// OutcomeSpace outcomeSpace = negotiationContext.getOutcomeSpace();
110// return outcomeSpace.getBidNearUtility(getTargetUtility(), u, this);
111// Bundle opponentLastBid = lastReceivedOffer;
112
113 Bundle opponentLastBid = getOpponentLastBid();
114
115 double time = getTime();
116 log("---------- t = " + time + "----------\n");
117
118// // If we have time, we receiveMessage the opponent model
119// if (canUpdateBeliefs(time)) { // for OPPONENT MODEL
120// updateBeliefs(opponentLastBid);
121// updateMyNashUtility();
122// }
123
124 double myUtilityOfOpponentLastBid = getUtility(opponentLastBid);
125 double maximumOfferedUtilityByOpponent = opponentHistory
126 .getMaximumUtility();
127 double minimumOfferedUtilityByOpponent = opponentHistory
128 .getMinimumUtility();
129
130 double minUtilityOfOpponentFirstBids = getMinimumUtilityOfOpponentFirstBids(
131 myUtilityOfOpponentLastBid);
132
133 double opponentConcession = maximumOfferedUtilityByOpponent
134 - minUtilityOfOpponentFirstBids;
135 /**
136 * Measures how far away the opponent is from myNashUtility. 0 =
137 * farthest, 1 = closest
138 */
139 double opponentConcedeFactor = Math.min(1, opponentConcession
140 / (myNashUtility - minUtilityOfOpponentFirstBids));
141 double myConcession = opponentConcedeFactor * (1 - myNashUtility);
142
143 double myCurrentTargetUtility = 1 - myConcession;
144
145 log("Min/Max utility offered by opponent was "
146 + round2(minimumOfferedUtilityByOpponent) + "/"
147 + round2(maximumOfferedUtilityByOpponent)
148 + ". (Right now, he offers me "
149 + round2(myUtilityOfOpponentLastBid) + ")\n"
150 + "The minimum of his first few bids is "
151 + round2(minUtilityOfOpponentFirstBids)
152 + " so his concession is " + round2(opponentConcession)
153 + ", which is at " + percentage(opponentConcedeFactor) + "%\n"
154 + "So I concede the same factor and my concession is "
155 + round2(myConcession)
156 + ". Therefore, my current target util is "
157 + round2(myCurrentTargetUtility));
158
159 initialGap = 1 - minUtilityOfOpponentFirstBids;
160 double gapToNash = Math.max(0, myCurrentTargetUtility - myNashUtility);
161
162 double bonus = getBonus();
163 double tit = bonus * gapToNash;
164 myCurrentTargetUtility -= tit;
165 log("The gap to Nash is then " + round2(gapToNash)
166 + ". I will add another bonus of " + round2(tit) + " (="
167 + percentage(bonus) + "%)" + " to have a target util of "
168 + myCurrentTargetUtility);
169
170 List<Bundle> myBids = getBidsOfUtility(myCurrentTargetUtility);
171 Bundle myBid = getBestBidForOpponent(myBids);
172 myBid = makeAppropriate(myBid);
173 log(" so I choose a bid with util " + getUtility(myBid));
174 return myBid;
175 }
176
177 /**
178 * Decides if we have enough time to receiveMessage opponent model and Nash
179 * point. On large domains, this may take 3 seconds.
180 *
181 * @param time
182 */
183 private boolean canUpdateBeliefs(double time) {
184 // in the last seconds we don't want to lose any time
185 if (time > 0.99)
186 return false;
187
188 // in a big domain, we stop updating half-way
189 if (isDomainBig())
190 if (time > 0.5)
191 return false;
192
193 return true;
194 }
195
196 /**
197 * Returns a small bonus multiplier to our target utility if we have to be
198 * fast.
199 *
200 * discount = 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 bonus = 0.5 0.3
201 * 0.1
202 *
203 * Normal domains: time = 0.91 to 0.96 bonus = 0.0 to 1.0
204 *
205 * Big domains: time = 0.85 to 0.9 bonus = 0.0 to 1.0
206 */
207 private double getBonus() {
208 double discountFactor = outcomeSpace.getDiscountFactor();
209 double discountBonus = 0.5 - 0.4 * discountFactor;
210 if (discountFactor < 1)
211 log("Discount = " + discountFactor
212 + ", so we set discount bonus to "
213 + percentage(discountBonus) + "%.");
214
215 boolean isBigDomain = DOMAINSIZE > 3000;
216 double timeBonus = 0;
217 double time = getTime();
218 double minTime = 0.91;
219 if (isBigDomain)
220 minTime = 0.85;
221 if (time > minTime) {
222 if (isBigDomain)
223 log("We have a big domain of size " + DOMAINSIZE
224 + ", so we start the time bonus from t = " + minTime);
225 timeBonus = Math.min(1, 20 * (time - minTime));
226 log("t = " + round2(time) + ", so we set time bonus to "
227 + percentage(timeBonus) + "%.");
228 }
229
230 double bonus = Math.max(discountBonus, timeBonus);
231 if (bonus < 0)
232 bonus = 0;
233 if (bonus > 1)
234 bonus = 1;
235 return bonus;
236 }
237
238 private void updateMyNashUtility() throws Exception {
239 BundleUtilitySpace bs=null;
240 try {
241 bs = new BundleUtilitySpace(outcomeSpace,outcomeSpace, true, false);
242 } catch (Exception e1) {
243 e1.printStackTrace();
244 }//null;
245 myNashUtility = 0.7;
246 try {
247 double nashMultiplier = getNashMultiplier(initialGap);
248// if (DOMAINSIZE < 200000) { // by OPPONENT MODEL
249// bs = new BundleUtilitySpace(outcomeSpace,
250// new OpponentModelUtilSpace(opponentModel), true, false);
251 BundleUtilityPoint nash = bs.getNash();
252 if (nash != null && nash.getUtilityA() != null)
253 myNashUtility = nash.getUtilityA();
254
255 myNashUtility *= nashMultiplier;
256
257 // don't ask for too much or too little
258 if (myNashUtility > 1)
259 myNashUtility = 1;
260 if (myNashUtility < 0.5)
261 myNashUtility = 0.5;
262 } catch (Exception e) {
263 e.printStackTrace();
264 }
265 }
266
267 /**
268 * If the gap is big (e.g. 0.8) the multiplier is smaller than 1 (e.g. 0.92)
269 * If the gap is small (e.g. 0.2) the multiplier is bigger than 1 (e.g.
270 * 1.28)
271 */
272 private double getNashMultiplier(double gap) {
273 double mult = 1.4 - 0.6 * gap;
274 if (mult < 0)
275 mult = 0;
276 return mult;
277 }
278
279 private void updateBeliefs(Bundle opponentLastBid) {
280// try { // by OPPONENT MODEL
281// opponentModel.updateBeliefs(opponentLastBid);
282// } catch (Exception e) {
283// e.printStackTrace();
284// }
285 }
286
287 /**
288 * Gives us our utility of the starting point of our opponent. This is used
289 * as a reference whether the opponent concedes or not.
290 */
291 private double getMinimumUtilityOfOpponentFirstBids(
292 double myUtilityOfOpponentLastBid) {
293 BidEventHistory firstBids = opponentHistory.filterBetweenTime(0,
294 TIME_USED_TO_DETERMINE_OPPONENT_STARTING_POINT);
295 double firstBidsMinUtility;
296 if (firstBids.size() == 0)
297 firstBidsMinUtility = opponentHistory.getFirstBidEvent()
298 .getMyUtility();
299 else
300 firstBidsMinUtility = firstBids.getMinimumUtility();
301 return firstBidsMinUtility;
302 }
303
304 /**
305 * Prevents the agent from overshooting. Replaces the planned bid (i.e, {@link Bundle}) by
306 * something more appropriate if there was a bid by the opponent that is
307 * better than our planned bid.
308 */
309 private Bundle makeAppropriate(Bundle myPlannedBid) {
310 Bundle bestBidByOpponent = opponentHistory.getBestBid();
311 // Bid by opponent is better than our planned bid
312 double bestUtilityByOpponent = getUtility(bestBidByOpponent);
313 double myPlannedUtility = getUtility(myPlannedBid);
314 if (bestUtilityByOpponent >= myPlannedUtility) {
315 log("Opponent previously made a better offer to me than my planned util "
316 + myPlannedUtility + ", namely " + bestUtilityByOpponent
317 + ", so I make that bid instead.");
318 return bestBidByOpponent;
319 }
320 return myPlannedBid;
321 }
322
323 @Override
324 public Bundle chooseOpeningBid() {
325 try {
326 return outcomeSpace.getMaxBidPossible(u);
327 } catch (Exception e) {
328 e.printStackTrace();
329 return outcomeSpace.getRandom(random100); // get a bid in random
330 }
331 }
332
333 @Override
334 public Bundle chooseFirstCounterBid() {
335 if (TEST_EQUIVALENCE) {
336// try {
337// opponentModel.updateBeliefs( // using OPPONENT MODEL
338// opponentHistory.getLastBidDetails().getBid());
339// } catch (Exception e) {
340// e.printStackTrace();
341// }
342 }
343 return chooseOpeningBid();
344 }
345
346 @Override
347 public boolean isAcceptable(Bundle plannedBid) {
348 double time = getTime();
349 Bundle opponentBid = getOpponentLastBid();
350 Bundle myNextBid = plannedBid;
351
352 if (utility(opponentBid) >= utility(myNextBid))
353 return true;
354
355 if (time < 0.98)
356 return false;
357
358 double offeredUtility = opponentHistory.getLastBidEvent()
359 .getMyUtility();
360 double now = time;
361 double timeLeft = 1 - now;
362 log("<======= new AC ========= (t = " + round3(now) + ", remaining: "
363 + round3(timeLeft) + ")");
364
365 // if we will still see a lot of bids (more than enoughBidsToCome), we
366 // do not accept
367 BidEventHistory recentBids = opponentHistory
368 .filterBetweenTime(now - timeLeft, now);
369 int recentBidsSize = recentBids.size();
370 int enoughBidsToCome = 10;
371 if (isDomainBig())
372 enoughBidsToCome = 40;
373 if (recentBidsSize > enoughBidsToCome) {
374 log("I expect to see " + recentBidsSize
375 + " more bids. I will only consider accepting when it falls below "
376 + enoughBidsToCome);
377 return false;
378 }
379
380 // v2.0
381 double window = timeLeft;
382 // double window = 5 * timeLeft;
383 BidEventHistory recentBetterBids = opponentHistory.filterBetween(
384 offeredUtility, 1, now - window, now);
385 int n = recentBetterBids.size();
386 double p = timeLeft / window;
387 if (p > 1)
388 p = 1;
389
390 double pAllMiss = Math.pow(1 - p, n);
391 if (n == 0)
392 pAllMiss = 1;
393 double pAtLeastOneHit = 1 - pAllMiss;
394
395 double avg = recentBetterBids.getAverageUtility();
396
397 double expectedUtilOfWaitingForABetterBid = pAtLeastOneHit * avg;
398
399 log("In the previous time window of size " + window + " I have seen "
400 + n + " better offers (out of a total of " + recentBidsSize
401 + ") than " + round2(offeredUtility)
402 + ", with avg util " + round2(avg));
403 log("p = " + p + ", so pAtLeastOneHit = " + pAtLeastOneHit);
404 log("expectedUtilOfWaitingForABetterBid = "
405 + round2(expectedUtilOfWaitingForABetterBid));
406 log("Acceptable? "
407 + (offeredUtility > expectedUtilOfWaitingForABetterBid));
408 log("========================>\n");
409 if (offeredUtility > expectedUtilOfWaitingForABetterBid)
410 return true;
411 return false;
412 }
413
414
415 @Override
416 protected Offer sendOffer()
417 {
418 Offer myAction = null;
419
420 // Nothing received yet
421 if (lastReceivedOffer == null)
422 {
423 Bundle myBid = chooseOpeningBid(); //getNextBid();
424 remember(new Offer(myBid,OfferType.BID));
425 return new Bid(myBid);
426 }
427
428 // Our last bid got accepted. We are also accepting (and we should notify the coordinator).
429 if (lastReceivedOffer.isPreAccept())
430 return new FinalAccept(lastReceivedOffer);
431
432 Bundle lastReceivedBid = lastReceivedOffer.getBundle();
433
434 // Accept
435 if (isAcceptable(lastReceivedBid))
436 return new PreAccept(lastReceivedOffer);
437 // Counter offer based actions
438 else
439 {
440 // we are the second
441 if (getMyLastBid() == null)
442 {
443 Bundle firstCounterBid = chooseFirstCounterBid();
444 // Check to see if we want to accept the first offer
445 if (isAcceptable(firstCounterBid))
446 {
447 myAction = makeAcceptAction();
448 return myAction;
449 }
450 else
451 {
452 myAction = new Offer(firstCounterBid,OfferType.BID);
453 remember(myAction);
454 return new Bid(firstCounterBid);
455 }
456 }
457
458 // We make a normal counter-offer
459 Bundle counterBid = chooseCounterBid();
460 // Check to see if we want to accept
461 if (isAcceptable(counterBid))
462 {
463 myAction = makeAcceptAction();
464 return myAction;
465 }
466 else
467 {
468 myAction = new Offer(counterBid, OfferType.BID);
469 remember(myAction);
470 return new Bid(counterBid);
471 }
472
473// if (myAction == null)
474// { // need this code to check equivalence
475// myAction = new Offer(counterBid, OfferType.BID);
476//
477// remember(myAction);
478// return new Bid(counterBid);
479// }
480 }
481 //return new Bid(chooseCounterBid());
482 }
483
484
485 @SuppressWarnings("unused")
486 @Override
487 public Offer makeAcceptAction() {
488 log("We are in the final phase because the AC accepted. We have offered the best bid of our opponent "
489 + offeredOpponentBestBid + " time(s).");
490
491 // However, if it wants to accept and we have some time left, we try to
492 // replace it with the best offer so far
493 Bundle opponentBid = getOpponentLastBid();
494 double offeredUtility = utility(opponentBid);
495 double now = getTime();
496 double timeLeft = 1 - now;
497 BidEventHistory recentBids = opponentHistory
498 .filterBetweenTime(now - timeLeft, now);
499 int expectedBids = recentBids.size();
500 Bundle bestBid = opponentHistory.getBestBid();
501 double bestBidUtility = utility(bestBid);
502 log("We expect to see " + expectedBids
503 + " more bids. The AC wants to accept the offer of utility "
504 + round2(offeredUtility) + " (max offered = "
505 + round2(bestBidUtility) + ").");
506
507 if (TEST_EQUIVALENCE) {
508 // we expect to see more bids, that are strictly better than what we
509 // are about to offer
510 if (!(expectedBids > 1 && bestBidUtility > offeredUtility)) {
511 return new PreAccept(new Offer(opponentBid,OfferType.BID));
512 }
513 } else {
514 // we expect to see more bids, that are strictly better than what we
515 // are about to offer
516 if (expectedBids > 1 && bestBidUtility > offeredUtility
517 && offeredOpponentBestBid <= 3) {
518 log("Which is not enough, so we will not accept now. Instead, we offer the opponent's best bid so far, which gives us utility "
519 + utility(bestBid));
520 offeredOpponentBestBid++;
521 return new Bid(bestBid);
522 } else {
523 log("Therefore, we will accept now.");
524 return new PreAccept(new Offer(opponentBid,OfferType.BID));
525 }
526 }
527 return null;
528 }
529
530 private double utility(Bundle b) {
531 try {
532 return u.getUtility(b);
533 } catch (Exception e) {
534 e.printStackTrace();
535 return 0;
536 }
537 }
538
539 protected static void log(String s) {
540 }
541
542 /**
543 * Rounds to two decimals
544 */
545 public static double round2(double x) {
546 return Math.round(100 * x) / 100d;
547 }
548
549 /**
550 * Rounds to 3 decimals
551 */
552 public static double round3(double x) {
553 return Math.round(1000 * x) / 1000d;
554 }
555
556 public static double percentage(double x) {
557 return Math.round(1000 * x) / 10d;
558 }
559
560 /**
561 * Get all bids in a utility range.
562 */
563 private List<Bundle> getBidsOfUtility(double lowerBound, double upperBound) {
564 // In big domains, we need to find only this amount of bids around the
565 // target. Should be at least 2.
566 final int limit = 2;
567
568 List<Bundle> bidsInRange = new ArrayList<Bundle>();
569 for (Bundle b : space)
570 try {
571 double util = u.getUtility(b);
572 if (util >= lowerBound && util <= upperBound)
573 bidsInRange.add(b);
574
575 // In big domains, break early
576 if (isDomainBig() && bidsInRange.size() >= limit)
577
578 return bidsInRange;
579 } catch (Exception e) {
580 e.printStackTrace();
581 }
582 return bidsInRange;
583 }
584
585 /**
586 * Get all bids in a utility range.
587 */
588 private List<Bundle> getBidsOfUtility(double target) {
589 if (target > 1)
590 target = 1;
591
592 double min = target * 0.98;
593 double max = target + 0.04;
594 do {
595 max += 0.01;
596 List<Bundle> bids = getBidsOfUtility(min, max);
597 int size = bids.size();
598
599 log(size + " bids found in [" + round2(min) + ", " + round2(max)
600 + "]");
601 // We need at least 2 bids. Or if max = 1, then we settle for 1 bid.
602 if (size > 1 || (max >= 1 && size > 0)) {
603 log(size + " bids of target utility " + round2(target)
604 + " found in [" + round2(min) + ", " + round2(max)
605 + "]");
606 return bids;
607 }
608 } while (max <= 1);
609
610 // Weird if this happens
611 ArrayList<Bundle> best = new ArrayList<Bundle>();
612 best.add(chooseOpeningBid());
613 return best;
614 }
615
616 private boolean isDomainBig() {
617 return DOMAINSIZE > 10000;
618 }
619
620 private Bundle getBestBidForOpponent(List<Bundle> bids) {
621 // We first make a bid history for the opponent, then pick the best one.
622 BidEventHistory possibleBidHistory = new BidEventHistory();
623 for (Bundle b : bids) {
624 double utility;
625 try {
626 utility =0; //utility = opponentModel.getNormalizedUtility(b);
627 BidEvent bidEvent = new BidEvent(b, utility, 0);
628 possibleBidHistory.add(bidEvent);
629 } catch (Exception e) {
630 e.printStackTrace();
631 }
632 }
633
634 // Pick the top 3 to 20 bids, depending on the domain size
635 int n = (int) Math.round(bids.size() / 10.0);
636 if (n < 3)
637 n = 3;
638 if (n > 20)
639 n = 20;
640
641 BidEventHistory bestN = possibleBidHistory.getBestBidHistory(n);
642 BidEvent randomBestN = bestN.getRandom(random100);
643 log("Random bid chosen out of the top " + n + " of " + bids.size()
644 + " bids, with opp util: "
645 + round2(randomBestN.getMyUtility()));
646 return randomBestN.getBid();
647
648 }
649
650// @Override
651// public SupportedNegotiationSetting getSupportedNegotiationSetting() {
652// return SupportedNegotiationSetting.getLinearUtilitySpaceInstance();
653// }
654
655 @Override
656 public String toDescription()
657 {
658 return name + " with u = " + u + " using " + this.getClass().getSimpleName() + " strategy ";
659 }
660
661}
662
Note: See TracBrowser for help on using the repository browser.