source: src/main/java/agents/anac/y2011/ValueModelAgent/ValueModelAgent.java

Last change on this file was 127, checked in by Wouter Pasman, 6 years ago

#41 ROLL BACK of rev.126 . So this version is equal to rev. 125

File size: 16.3 KB
Line 
1package agents.anac.y2011.ValueModelAgent;
2
3import java.util.Random;
4
5import genius.core.Agent;
6import genius.core.Bid;
7import genius.core.BidIterator;
8import genius.core.SupportedNegotiationSetting;
9import genius.core.actions.Accept;
10import genius.core.actions.Action;
11import genius.core.actions.ActionWithBid;
12import genius.core.actions.Offer;
13import genius.core.utility.AdditiveUtilitySpace;
14
15//This agent uses a very complex form of temporal difference reinforcement
16//learning to learn opponent's utility space.
17//The learning is focused on finding the amount of utility lost by
18//opponent for each value.
19//However, as the bid (expected) utilities represent the decrease in all
20//issues, we needed away to decide which values should change the most.
21//We use estimations of standard deviation and reliability to decide how
22//to make the split.
23//The reliability is also used to decide the learning factor of the individual
24//learning.
25//The agent then tries to slow down the compromise rate, until we have to be fair.
26
27//This is the agent of Asaf, Dror and Gal.
28public class ValueModelAgent extends Agent {
29 private ValueModeler opponentUtilModel = null;
30 private BidList allBids = null;
31 private BidList approvedBids = null;
32 private BidList iteratedBids = null;
33 private Action actionOfPartner = null;
34 private Action myLastAction = null;
35 private Bid myLastBid = null;
36 private int bidCount;
37 public BidList opponentBids;
38 public BidList ourBids;
39 private OpponentModeler opponent;
40 private double lowestAcceptable;
41 private double lowestApproved;
42 public double opponentStartbidUtil;
43 public double opponentMaxBidUtil;
44 private Bid opponentMaxBid;
45 public double myMaximumUtility;
46 private int amountOfApproved;
47 public double noChangeCounter;
48 private boolean retreatMode;
49 private double concessionInOurUtility;
50 private double concessionInTheirUtility;
51 private ValueSeperatedBids seperatedBids;
52 private final boolean TEST_EQUIVALENCE = false;
53 Random random100;
54 Random random200;
55 int round = 0;
56
57 private Action lAction = null;
58
59 private double opponentUtil;
60
61 @Override
62 public void init() {
63 @SuppressWarnings("unused")
64 // it's not unused, check space type.
65 AdditiveUtilitySpace a = (AdditiveUtilitySpace) utilitySpace;
66 opponentUtilModel = null;
67 allBids = null;
68 approvedBids = null;
69 actionOfPartner = null;
70 bidCount = 0;
71 opponentBids = new BidList();
72 ourBids = new BidList();
73 iteratedBids = new BidList();
74 seperatedBids = new ValueSeperatedBids();
75 lowestAcceptable = 0.7;
76 lowestApproved = 1;
77 amountOfApproved = 0;
78 opponentMaxBidUtil = 0;
79 myMaximumUtility = 1;
80 noChangeCounter = 0;
81 retreatMode = false;
82 concessionInOurUtility = 0;
83 concessionInTheirUtility = 0;
84
85 if (TEST_EQUIVALENCE) {
86 random100 = new Random(100);
87 random200 = new Random(200);
88 } else {
89 random100 = new Random();
90 random200 = new Random();
91 }
92 }
93
94 @Override
95 public void ReceiveMessage(Action opponentAction) {
96 round++;
97 actionOfPartner = opponentAction;
98 }
99
100 // remember our new bid
101 private void bidSelected(BidWrapper bid) {
102 bid.sentByUs = true;
103 ourBids.addIfNew(bid);
104 myLastBid = bid.bid;
105 if (opponentUtilModel != null)
106 seperatedBids.bidden(bid.bid, bidCount);
107 }
108
109 // remember our new bid in all needed data structures
110 private void bidSelectedByOpponent(Bid bid) {
111 BidWrapper opponentBid = new BidWrapper(bid, utilitySpace,
112 myMaximumUtility);
113 opponentBid.lastSentBid = bidCount;
114 opponentBid.sentByThem = true;
115 if (opponentBids.addIfNew(opponentBid)) {
116 noChangeCounter = 0;
117 } else {
118 noChangeCounter++;
119 }
120 try {
121 double opponentUtil = utilitySpace.getUtility(bid)
122 / myMaximumUtility;
123 if (opponentMaxBidUtil < opponentUtil) {
124 opponentMaxBidUtil = opponentUtil;
125 opponentMaxBid = bid;
126 }
127 if (opponentUtilModel.initialized) {
128 double concession = opponentUtil - opponentStartbidUtil;
129 if (concession > concessionInOurUtility)
130 concessionInOurUtility = concession;
131 // concession,opponentUtil,opponentStartbidUtil);
132 // assumed utility he lost (should be lower
133 // if our opponent is smart, but lets be honest
134 // it is quite possible we missevaluated so lets
135 // use our opponent utility instead
136 ValueDecrease val = opponentUtilModel
137 .utilityLoss(opponentBid.bid);
138 concession = val.getDecrease();
139 if (concession > concessionInTheirUtility)
140 concessionInTheirUtility = concession;
141 seperatedBids.bidden(bid, bidCount);
142
143 }
144 } catch (Exception ex) {
145 ex.printStackTrace();
146 }
147 }
148
149 private boolean setApprovedThreshold(double threshold, boolean clear) {
150 if (clear) {
151 approvedBids.bids.clear();
152 seperatedBids.clear();
153 }
154 int i;
155 if (clear)
156 i = 0;
157 else
158 i = amountOfApproved;
159 for (; i < allBids.bids.size(); i++) {
160 if (allBids.bids.get(i).ourUtility < threshold) {
161 break;
162 }
163 approvedBids.bids.add(allBids.bids.get(i));
164 seperatedBids.addApproved(allBids.bids.get(i));
165 }
166 lowestApproved = threshold;
167 boolean added = amountOfApproved != i;
168 amountOfApproved = i;
169 return added;
170 }
171
172 @Override
173 public Action chooseAction() {
174 Bid opponentBid = null;
175 lAction = null;
176 try {
177 // our first bid, initializing
178
179 if (allBids == null) {
180 allBids = new BidList();
181 approvedBids = new BidList();
182 opponentUtilModel = new ValueModeler();
183 seperatedBids.init((AdditiveUtilitySpace) utilitySpace,
184 opponentUtilModel);
185 myMaximumUtility = utilitySpace
186 .getUtility(utilitySpace.getMaxUtilityBid());
187 BidIterator iter = new BidIterator(utilitySpace.getDomain());
188 while (iter.hasNext()) {
189 Bid tmpBid = iter.next();
190 try {
191 BidWrapper wrap = new BidWrapper(tmpBid, utilitySpace,
192 myMaximumUtility);
193 allBids.bids.add(wrap);
194 // }
195 } catch (Exception ex) {
196 ex.printStackTrace();
197 BidWrapper wrap = new BidWrapper(tmpBid, utilitySpace,
198 myMaximumUtility);
199 allBids.bids.add(wrap);
200 }
201 } // while
202 allBids.sortByOurUtil();
203
204 setApprovedThreshold(0.98, false);
205
206 iteratedBids.bids.add(allBids.bids.get(0));
207 }
208 // first bid is the highest bid
209 if (bidCount == 0) {
210 lAction = new Offer(getAgentID(), allBids.bids.get(0).bid);
211 bidSelected(allBids.bids.get(0));
212 }
213
214 // treat opponent's offer
215 if (actionOfPartner instanceof Offer) {
216 opponentBid = ((Offer) actionOfPartner).getBid();
217 opponentUtil = utilitySpace.getUtility(opponentBid)
218 / myMaximumUtility;
219 bidSelectedByOpponent(opponentBid);
220
221 if (opponent == null) {
222 opponentStartbidUtil = opponentUtil;
223 opponent = new OpponentModeler(bidCount,
224 (AdditiveUtilitySpace) utilitySpace, timeline,
225 ourBids, opponentBids, opponentUtilModel, allBids,
226 this);
227 opponentUtilModel.initialize(
228 (AdditiveUtilitySpace) utilitySpace, opponentBid);
229 approvedBids.sortByOpponentUtil(opponentUtilModel);
230 } else {
231 opponent.tick();
232 if (noChangeCounter == 0) {
233 double opponentExpectedBidValue = opponent
234 .guessCurrentBidUtil();
235 opponentUtilModel.assumeBidWorth(opponentBid,
236 1 - opponentExpectedBidValue, 0.02);
237 }
238
239 }
240 // it seems like I should try to accept
241 // his best bid (assuming its still on the table)
242 // if its a good enough bid to be reasonable
243 // (we don't accept 0.3,0.92 around here...)
244 // currently by reasonable we mean that we will
245 // get most of what would be a "fair" distribution
246 // of the utility
247
248 if (timeline.getTime() > 0.9 && timeline.getTime() <= 0.96) {
249 chickenGame(0.039, 0, 0.7);
250 }
251 if (timeline.getTime() > 0.96 && timeline.getTime() <= 0.97) {
252 chickenGame(0.019, 0.5, 0.65);
253
254 }
255 if (timeline.getTime() > 0.98 && timeline.getTime() <= 0.99) {
256
257 if (opponentUtil >= lowestApproved - 0.01) {
258 return new Accept(getAgentID(), opponentBid);
259 }
260 if (bidCount % 5 == 0) {
261 exploreScan();
262 } else
263 bestScan();
264 }
265 if (timeline.getTime() > 0.99 && timeline.getTime() <= 0.995) {
266 chickenGame(0.004, 0.8, 0.6);
267
268 }
269
270 if (timeline.getTime() > 0.995) {
271
272 if (opponentMaxBidUtil > 0.55) {
273
274 // they might have a bug and not accept, so
275 // if their offer is close enough accept
276 if (opponentUtil >= opponentMaxBidUtil * 0.99) {
277 return new Accept(getAgentID(), opponentBid);
278 } else
279 return new Offer(getAgentID(), opponentMaxBid);
280 }
281 bestScan();
282 // this will probably not work but what can we
283 // do? he dosn't even give us 50%!
284 }
285
286 if (lAction != null) {
287 myLastAction = lAction;
288 bidCount++;
289 return lAction;
290 }
291
292 // if our opponent settled enough for us we accept, and there is
293 // a discount factor we accept
294 // if(opponent.expectedDiscountRatioToConvergence()*opponentUtil
295 // > lowestApproved){
296 if ((opponentUtil > lowestApproved)// || opponentUtil>0.98)
297 && (utilitySpace.isDiscounted()
298 || opponentUtil > 0.975)) {
299 return new Accept(getAgentID(), opponentBid);
300 }
301
302 // otherwise we try to stretch it out
303 if (opponentUtil > lowestApproved * 0.99
304 && !utilitySpace.isDiscounted()) {
305 lowestApproved += 0.01;
306 setApprovedThreshold(lowestApproved, true);
307 retreatMode = true;
308 }
309 if (bidCount > 0 && bidCount < 4) {
310
311 lAction = new Offer(getAgentID(), allBids.bids.get(0).bid);
312 bidSelected(allBids.bids.get(bidCount));
313 }
314 if (bidCount >= 4) {
315
316 // utility he gave us
317 double concession = opponentUtil - opponentStartbidUtil;
318 // assumed utility he lost (should be lower
319 // if our opponent is smart, but lets be honest
320 // it is quite possible we missevaluated so lets
321 // use our opponent utility instead
322 // double concession2 =
323 // opponentUtilModel.utilityLoss(opponentBid).getDecrease();
324 double concession2 = 1 - opponent.guessCurrentBidUtil();
325 double minConcession = concession < concession2 ? concession
326 : concession2;
327 minConcession = minConcessionMaker(minConcession,
328 1 - opponentMaxBidUtil);
329
330 if (minConcession > (1 - lowestApproved)) {
331 if (lowestAcceptable > (1 - minConcession)) {
332 lowestApproved = lowestAcceptable;
333 } else {
334 lowestApproved = 1 - minConcession;
335 }
336 if (lowestApproved < opponentMaxBidUtil)
337 lowestApproved = opponentMaxBidUtil + 0.001;
338
339 if (setApprovedThreshold(lowestApproved, false)) {
340 approvedBids.sortByOpponentUtil(opponentUtilModel);
341 }
342 }
343
344 if (bidCount % 5 == 0) {
345 exploreScan();
346 } else
347 bestScan();
348 }
349
350 }
351
352 if (lAction == null) {
353 lAction = myLastAction;
354 }
355 } catch (Exception e) {
356 if (myLastBid == null) {
357 try {
358 return new Offer(getAgentID(),
359 utilitySpace.getMaxUtilityBid());
360 } catch (Exception e2) {
361 return new Accept(getAgentID(), opponentBid);
362 }
363 }
364 lAction = new Offer(getAgentID(), myLastBid);
365 }
366 myLastAction = lAction;
367 bidCount++;
368 return lAction;
369 }
370
371 public void bestScan() {
372 approvedBids.sortByOpponentUtil(opponentUtilModel);
373
374 // find the "best" bid for opponent
375 // and choose it if we didn't send it to opponent
376 for (int i = 0; i < approvedBids.bids.size(); i++) {
377 BidWrapper tempBid = approvedBids.bids.get(i);
378 if (!tempBid.sentByUs) {
379 lAction = new Offer(getAgentID(), tempBid.bid);
380 bidSelected(tempBid);
381 break;
382 }
383 }
384 if (lAction == null) {
385 int maxIndex = approvedBids.bids.size() / 4;
386 BidWrapper tempBid = approvedBids.bids
387 .get((int) (random200.nextDouble() * maxIndex));
388 lAction = new Offer(getAgentID(), tempBid.bid);
389 bidSelected(tempBid);
390 }
391 }
392
393 public void exploreScan() {
394 BidWrapper tempBid = seperatedBids.explore(bidCount);
395 if (tempBid != null) {
396 lAction = new Offer(getAgentID(), tempBid.bid);
397 bidSelected(tempBid);
398 } else
399 bestScan();
400 }
401
402 public void chickenGame(double timeToGive, double concessionPortion,
403 double acceptableThresh) {
404 // set timeToGive to be 0.005 unless each turn is very
405 // large
406 // double timeToGive =
407 // 0.005>(opponent.delta*4)?0.005:(opponent.delta*4);
408 double concessionLeft = lowestApproved - opponentMaxBidUtil;
409 double planedThresh = lowestApproved
410 - concessionPortion * concessionLeft;
411 if (acceptableThresh > planedThresh)
412 planedThresh = acceptableThresh;
413 setApprovedThreshold(planedThresh, false);
414 approvedBids.sortByOpponentUtil(opponentUtilModel);
415
416 if (opponentUtil >= planedThresh - 0.01) {
417 lAction = new Accept(getAgentID(),
418 ((ActionWithBid) actionOfPartner).getBid());
419 return;
420 }
421 if (1.0 - timeline.getTime() - timeToGive > 0) {
422 if (!TEST_EQUIVALENCE) {
423 sleep(1.0 - timeline.getTime() - timeToGive);
424 }
425 }
426 if (retreatMode || opponentMaxBidUtil >= planedThresh - 0.01) {
427 lAction = new Offer(getAgentID(), opponentMaxBid);
428 }
429 // offer him the best bid for him amongst the
430 // bids that are above our limit
431 else {
432 approvedBids.bids.get(0);
433 // return new Offer(getAgentID(), approvedBids.bids.get(0).bid);
434 }
435 }
436
437 double theirMaxUtilities[] = new double[21];
438 double ourMinUtilities[] = new double[21];
439
440 private double minConcessionMaker(double minConcession,
441 double concessionLeft) {
442 theirMaxUtilities[0] = opponentStartbidUtil;
443 ourMinUtilities[0] = 1;
444 double t = timeline.getTime();
445 int tind = (int) (timeline.getTime() * 20) + 1;
446 double segPortion = (t - (tind - 1) * 0.05) / 0.05;
447 if (ourMinUtilities[tind] == 0)
448 ourMinUtilities[tind] = 1;
449 if (ourMinUtilities[tind - 1] == 0)
450 ourMinUtilities[tind - 1] = lowestApproved;
451 if (lowestApproved < ourMinUtilities[tind])
452 ourMinUtilities[tind] = lowestApproved;
453 if (opponentMaxBidUtil > theirMaxUtilities[tind])
454 theirMaxUtilities[tind] = opponentMaxBidUtil;
455 double d = utilitySpace.getDiscountFactor();
456 double defaultVal = 1 - ourMinUtilities[tind - 1];
457 if (tind == 1 || tind >= 19)
458 return defaultVal;
459 if (ourMinUtilities[tind - 2] == 0)
460 ourMinUtilities[tind - 2] = lowestApproved;
461 // if(defaultVal>minConcession) return minConcession;
462 boolean theyMoved = theirMaxUtilities[tind]
463 - theirMaxUtilities[tind - 2] > 0.01;
464 boolean weMoved = ourMinUtilities[tind - 2]
465 - ourMinUtilities[tind - 1] > 0;
466 double returnVal = defaultVal;
467
468 if (!utilitySpace.isDiscounted()) {
469 // first 10% is reserved for 0.98...
470 if (tind > 2) {
471 // if we havn't compromised in the last session
472 if (!weMoved) {
473 // we didn't move, they did
474 if (theyMoved) {
475 // return defaultVal;
476 } else if (tind <= 16) {
477 returnVal = defaultVal + 0.02;
478 // give concession only if we think they conceded more!
479 if (returnVal > minConcession * 2 / 3)
480 returnVal = minConcession * 2 / 3;
481
482 }
483 }
484 }
485
486 // the negotiation is ending and they are not moving its time for
487 // compromize
488 if (tind > 16 && !theyMoved) {
489 // Compromise another portion every time...
490 returnVal = (concessionLeft - defaultVal) / (21 - tind)
491 + defaultVal;
492 if (returnVal > minConcession + 0.05)
493 returnVal = minConcession + 0.05;
494
495 }
496 // return defaultVal;
497
498 } else {
499 double discountEstimate = d * 0.05;
500 double expectedRoundGain = theirMaxUtilities[tind - 1]
501 - theirMaxUtilities[tind - 2] - discountEstimate;
502
503 if (tind <= 16) {
504 returnVal = defaultVal + 0.02;
505 if (defaultVal - expectedRoundGain > returnVal)
506 returnVal = defaultVal - expectedRoundGain;
507 if (returnVal > minConcession)
508 returnVal = minConcession;
509
510 } else {
511 // Compromise another portion every time...
512 returnVal = (concessionLeft - defaultVal) / (21 - tind)
513 + defaultVal;
514 }
515 }
516 // making a concession in steps. its slower but safer
517 returnVal = defaultVal + (returnVal - defaultVal) * segPortion;
518 return returnVal;
519 }
520
521 @Override
522 public String getName() {
523 return "Value Model Agent";
524 }
525
526 @Override
527 public SupportedNegotiationSetting getSupportedNegotiationSetting() {
528 return SupportedNegotiationSetting.getLinearUtilitySpaceInstance();
529 }
530
531 @Override
532 public String getDescription() {
533 return "ANAC2011";
534 }
535}
Note: See TracBrowser for help on using the repository browser.