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

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

Initial import : Genius 9.0.0
File size: 19.2 KB
Line 
1package agents.anac.y2011.IAMhaggler2011;
2
3import java.util.ArrayList;
4
5import agents.Jama.Matrix;
6import agents.org.apache.commons.math.MathException;
7import agents.org.apache.commons.math.MaxIterationsExceededException;
8import agents.org.apache.commons.math.special.Erf;
9import agents.uk.ac.soton.ecs.gp4j.bmc.BasicPrior;
10import agents.uk.ac.soton.ecs.gp4j.bmc.GaussianProcessMixture;
11import agents.uk.ac.soton.ecs.gp4j.bmc.GaussianProcessMixturePrediction;
12import agents.uk.ac.soton.ecs.gp4j.bmc.GaussianProcessRegressionBMC;
13import agents.uk.ac.soton.ecs.gp4j.gp.covariancefunctions.CovarianceFunction;
14import agents.uk.ac.soton.ecs.gp4j.gp.covariancefunctions.Matern3CovarianceFunction;
15import agents.uk.ac.soton.ecs.gp4j.gp.covariancefunctions.NoiseCovarianceFunction;
16import agents.uk.ac.soton.ecs.gp4j.gp.covariancefunctions.SumCovarianceFunction;
17import genius.core.Agent;
18import genius.core.Bid;
19import genius.core.SupportedNegotiationSetting;
20import genius.core.actions.Accept;
21import genius.core.actions.Action;
22import genius.core.actions.EndNegotiation;
23import genius.core.actions.Offer;
24import genius.core.utility.AdditiveUtilitySpace;
25
26/**
27 * @author Colin Williams
28 *
29 * The IAMhaggler Agent, created for ANAC 2011. Designed by C. R.
30 * Williams, V. Robu, E. H. Gerding and N. R. Jennings.
31 *
32 */
33public class IAMhaggler2011 extends Agent {
34
35 protected double RISK_PARAMETER = 3.0;
36 private Matrix utilitySamples;
37 private Matrix timeSamples;
38 private Matrix utility;
39 private GaussianProcessRegressionBMC regression;
40 private double lastRegressionTime = 0;
41 private double lastRegressionUtility = 1;
42 private ArrayList<Double> opponentTimes = new ArrayList<Double>();
43 private ArrayList<Double> opponentUtilities = new ArrayList<Double>();
44 private double maxUtilityInTimeSlot;
45 private int lastTimeSlot = -1;
46 private Matrix means;
47 private Matrix variances;
48 private double maxUtility;
49 private Bid bestReceivedBid;
50 private double previousTargetUtility;
51 protected BidCreator bidCreator;
52
53 private static enum ActionType {
54 ACCEPT, BREAKOFF, OFFER, START;
55 }
56
57 protected double MAXIMUM_ASPIRATION = 0.9;
58 private Action messageOpponent;
59 protected Action myLastAction = null;
60 protected Bid myLastBid = null;
61 protected double acceptMultiplier = 1.02;
62 private ArrayList<Bid> opponentBids;
63
64 public IAMhaggler2011() {
65 }
66
67 /*
68 * (non-Javadoc)
69 *
70 * @see agents.southampton.SouthamptonAgent#init()
71 */
72 @Override
73 public void init() {
74 myLastBid = null;
75 myLastAction = null;
76
77 opponentBids = new ArrayList<Bid>();
78
79 double discountingFactor = 0.5;
80 try {
81 discountingFactor = utilitySpace.getDiscountFactor();
82 } catch (Exception ex) {
83 ex.printStackTrace();
84 }
85 if (discountingFactor == 0)
86 discountingFactor = 1;
87 makeUtilitySamples(100);
88 makeTimeSamples(100);
89 Matrix discounting = generateDiscountingFunction(discountingFactor);
90 Matrix risk = generateRiskFunction(RISK_PARAMETER);
91 utility = risk.arrayTimes(discounting);
92
93 BasicPrior[] bps = { new BasicPrior(11, 0.252, 0.5),
94 new BasicPrior(11, 0.166, 0.5), new BasicPrior(1, .01, 1.0) };
95 CovarianceFunction cf = new SumCovarianceFunction(
96 Matern3CovarianceFunction.getInstance(),
97 NoiseCovarianceFunction.getInstance());
98
99 regression = new GaussianProcessRegressionBMC();
100 regression.setCovarianceFunction(cf);
101 regression.setPriors(bps);
102
103 maxUtility = 0;
104 previousTargetUtility = 1;
105
106 bidCreator = new RandomBidCreator();
107 }
108
109 @Override
110 public String getName() {
111 return "IAMhaggler2011";
112 }
113
114 /**
115 * Create an m-by-1 matrix of utility samples.
116 *
117 * @param m
118 * The sample size.
119 */
120 private void makeUtilitySamples(int m) {
121 double[] utilitySamplesArray = new double[m];
122 {
123 for (int i = 0; i < utilitySamplesArray.length; i++) {
124 utilitySamplesArray[i] = 1.0 - (i + 0.5) / (m + 1.0);
125 }
126 }
127 utilitySamples = new Matrix(utilitySamplesArray,
128 utilitySamplesArray.length);
129 }
130
131 /**
132 * Create a 1-by-n matrix of time samples.
133 *
134 * @param n
135 * The sample size.
136 */
137 private void makeTimeSamples(int n) {
138 double[] timeSamplesArray = new double[n + 1];
139 {
140 for (int i = 0; i < timeSamplesArray.length; i++) {
141 timeSamplesArray[i] = ((double) i) / ((double) n);
142 }
143 }
144 timeSamples = new Matrix(timeSamplesArray, 1);
145 }
146
147 /*
148 * (non-Javadoc)
149 *
150 * @see agents.southampton.SouthamptonAgent#proposeInitialBid()
151 */
152 protected Bid proposeInitialBid() throws Exception {
153 return utilitySpace.getMaxUtilityBid();
154 }
155
156 /*
157 * (non-Javadoc)
158 *
159 * @see agents.southampton.SouthamptonAgent#proposeNextBid(negotiator.Bid)
160 */
161 protected Bid proposeNextBid(Bid opponentBid) throws Exception {
162 double opponentUtility = utilitySpace.getUtility(opponentBid);
163
164 if (opponentUtility > maxUtility) {
165 bestReceivedBid = opponentBid;
166 maxUtility = opponentUtility;
167 }
168
169 double targetUtility = getTarget(opponentUtility, timeline.getTime());
170
171 if (targetUtility <= maxUtility && previousTargetUtility > maxUtility)
172 return bestReceivedBid;
173 previousTargetUtility = targetUtility;
174 // Now get a random bid in the range targetUtility � 0.025
175 return bidCreator.getBid((AdditiveUtilitySpace) utilitySpace,
176 targetUtility - 0.025, targetUtility + 0.025);
177 }
178
179 /**
180 * Get the target at a given time, recording the opponent's utility.
181 *
182 * @param opponentUtility
183 * The utility of the most recent offer made by the opponent.
184 * @param time
185 * The current time.
186 * @return the target.
187 */
188 protected double getTarget(double opponentUtility, double time) {
189 // Calculate the current time slot
190 int timeSlot = (int) Math.floor(time * 36);
191
192 boolean regressionUpdateRequired = false;
193 if (lastTimeSlot == -1) {
194 regressionUpdateRequired = true;
195 }
196
197 // If the time slot has changed
198 if (timeSlot != lastTimeSlot) {
199 if (lastTimeSlot != -1) {
200 // Store the data from the time slot
201 opponentTimes.add((lastTimeSlot + 0.5) / 36.0);
202 opponentUtilities.add(maxUtilityInTimeSlot);
203 // Flag regression receiveMessage required
204 regressionUpdateRequired = true;
205 }
206 // Update the time slot
207 lastTimeSlot = timeSlot;
208 // Reset the max utility
209 maxUtilityInTimeSlot = 0;
210 }
211
212 // Calculate the maximum utility observed in the current time slot
213 maxUtilityInTimeSlot = Math.max(maxUtilityInTimeSlot, opponentUtility);
214
215 if (timeSlot == 0) {
216 return 1.0 - time / 2.0;
217 }
218
219 if (regressionUpdateRequired) {
220 double[] x = new double[opponentTimes.size()];
221 double[] xAdjust = new double[opponentTimes.size()];
222 double[] y = new double[opponentUtilities.size()];
223 double[] timeSamplesAdjust = new double[timeSamples
224 .getColumnDimension()];
225
226 int i;
227 i = 0;
228 for (double d : opponentTimes) {
229 x[i++] = d;
230 }
231 i = 0;
232 double intercept = opponentUtilities.get(0);
233 double gradient = 0.9 - intercept;
234 for (double d : opponentTimes) {
235 xAdjust[i++] = intercept + (gradient * d);
236 }
237 i = 0;
238 for (double d : timeSamples.getRowPackedCopy()) {
239 timeSamplesAdjust[i++] = intercept + (gradient * d);
240 }
241 i = 0;
242 for (double d : opponentUtilities) {
243 y[i++] = d;
244 }
245
246 Matrix matrixX = new Matrix(x, x.length);
247 Matrix matrixXAdjust = new Matrix(xAdjust, xAdjust.length);
248 Matrix matrixY = new Matrix(y, y.length);
249 Matrix matrixTimeSamplesAdjust = new Matrix(timeSamplesAdjust,
250 timeSamplesAdjust.length);
251
252 matrixY.minusEquals(matrixXAdjust);
253
254 GaussianProcessMixture predictor = regression
255 .calculateRegression(matrixX, matrixY);
256
257 GaussianProcessMixturePrediction prediction = predictor
258 .calculatePrediction(timeSamples.transpose());
259
260 // Store the means and variances
261 means = prediction.getMean().plus(matrixTimeSamplesAdjust);
262 variances = prediction.getVariance();
263 }
264
265 Pair<Matrix, Matrix> acceptMatrices = generateProbabilityAccept(means,
266 variances, time);
267 Matrix probabilityAccept = acceptMatrices.fst;
268 Matrix cumulativeAccept = acceptMatrices.snd;
269
270 Matrix probabilityExpectedUtility = probabilityAccept
271 .arrayTimes(utility);
272 Matrix cumulativeExpectedUtility = cumulativeAccept.arrayTimes(utility);
273
274 Pair<Double, Double> bestAgreement = getExpectedBestAgreement(
275 probabilityExpectedUtility, cumulativeExpectedUtility, time);
276 double bestTime = bestAgreement.fst;
277 double bestUtility = bestAgreement.snd;
278
279 double targetUtility = lastRegressionUtility
280 + ((time - lastRegressionTime)
281 * (bestUtility - lastRegressionUtility)
282 / (bestTime - lastRegressionTime));
283
284 // Store the target utility and time
285 lastRegressionUtility = targetUtility;
286 lastRegressionTime = time;
287
288 return targetUtility;
289 }
290
291 /**
292 * Generate an n-by-m matrix representing the effect of the discounting
293 * factor for a given utility-time combination. The combinations are given
294 * by the time and utility samples stored in timeSamples and utilitySamples
295 * respectively.
296 *
297 * @param discountingFactor
298 * The discounting factor, in the range (0, 1].
299 * @return An n-by-m matrix representing the discounted utilities.
300 */
301 private Matrix generateDiscountingFunction(double discountingFactor) {
302 double[] discountingSamples = timeSamples.getRowPackedCopy();
303 double[][] m = new double[utilitySamples.getRowDimension()][timeSamples
304 .getColumnDimension()];
305 for (int i = 0; i < m.length; i++) {
306 for (int j = 0; j < m[i].length; j++) {
307 m[i][j] = Math.pow(discountingFactor, discountingSamples[j]);
308 }
309 }
310 return new Matrix(m);
311 }
312
313 /**
314 * Generate an (n-1)-by-m matrix representing the probability of acceptance
315 * for a given utility-time combination. The combinations are given by the
316 * time and utility samples stored in timeSamples and utilitySamples
317 * respectively.
318 *
319 * @param mean
320 * The means, at each of the sample time points.
321 * @param variance
322 * The variances, at each of the sample time points.
323 * @param time
324 * The current time, in the range [0, 1].
325 * @return An (n-1)-by-m matrix representing the probability of acceptance.
326 */
327 private Pair<Matrix, Matrix> generateProbabilityAccept(Matrix mean,
328 Matrix variance, double time) {
329 int i = 0;
330 for (; i < timeSamples.getColumnDimension(); i++) {
331 if (timeSamples.get(0, i) > time)
332 break;
333 }
334 Matrix cumulativeAccept = new Matrix(utilitySamples.getRowDimension(),
335 timeSamples.getColumnDimension(), 0);
336 Matrix probabilityAccept = new Matrix(utilitySamples.getRowDimension(),
337 timeSamples.getColumnDimension(), 0);
338
339 double interval = 1.0 / utilitySamples.getRowDimension();
340
341 for (; i < timeSamples.getColumnDimension(); i++) {
342 double s = Math.sqrt(2 * variance.get(i, 0));
343 double m = mean.get(i, 0);
344
345 double minp = (1.0 - (0.5 * (1 + erf(
346 (utilitySamples.get(0, 0) + (interval / 2.0) - m) / s))));
347 double maxp = (1.0 - (0.5 * (1 + erf(
348 (utilitySamples.get(utilitySamples.getRowDimension() - 1, 0)
349 - (interval / 2.0) - m) / s))));
350
351 for (int j = 0; j < utilitySamples.getRowDimension(); j++) {
352 double utility = utilitySamples.get(j, 0);
353 double p = (1.0 - (0.5 * (1 + erf((utility - m) / s))));
354 double p1 = (1.0 - (0.5
355 * (1 + erf((utility - (interval / 2.0) - m) / s))));
356 double p2 = (1.0 - (0.5
357 * (1 + erf((utility + (interval / 2.0) - m) / s))));
358
359 cumulativeAccept.set(j, i, (p - minp) / (maxp - minp));
360 probabilityAccept.set(j, i, (p1 - p2) / (maxp - minp));
361 }
362 }
363 return new Pair<Matrix, Matrix>(probabilityAccept, cumulativeAccept);
364 }
365
366 /**
367 * Wrapper for the erf function.
368 *
369 * @param x
370 * @return
371 */
372 private double erf(double x) {
373 if (x > 6)
374 return 1;
375 if (x < -6)
376 return -1;
377 try {
378 double d = Erf.erf(x);
379 if (d > 1)
380 return 1;
381 if (d < -1)
382 return -1;
383 return d;
384 } catch (MaxIterationsExceededException e) {
385 if (x > 0)
386 return 1;
387 else
388 return -1;
389 } catch (MathException e) {
390 e.printStackTrace();
391 return 0;
392 }
393 }
394
395 /**
396 * Generate an n-by-m matrix representing the risk based utility for a given
397 * utility-time combination. The combinations are given by the time and
398 * utility samples stored in timeSamples and utilitySamples
399 *
400 * @param riskParameter
401 * The risk parameter.
402 * @return an n-by-m matrix representing the risk based utility.
403 */
404 protected Matrix generateRiskFunction(double riskParameter) {
405 double mmin = generateRiskFunction(riskParameter, 0.0);
406 double mmax = generateRiskFunction(riskParameter, 1.0);
407 double range = mmax - mmin;
408
409 double[] riskSamples = utilitySamples.getColumnPackedCopy();
410 double[][] m = new double[utilitySamples.getRowDimension()][timeSamples
411 .getColumnDimension()];
412 for (int i = 0; i < m.length; i++) {
413 double val;
414 if (range == 0) {
415 val = riskSamples[i];
416 } else {
417 val = (generateRiskFunction(riskParameter, riskSamples[i])
418 - mmin) / range;
419 }
420 for (int j = 0; j < m[i].length; j++) {
421 m[i][j] = val;
422 }
423 }
424 return new Matrix(m);
425 }
426
427 /**
428 * Generate the risk based utility for a given actual utility.
429 *
430 * @param riskParameter
431 * The risk parameter.
432 * @param utility
433 * The actual utility to calculate the risk based utility from.
434 * @return the risk based utility.
435 */
436 protected double generateRiskFunction(double riskParameter,
437 double utility) {
438 return Math.pow(utility, riskParameter);
439 }
440
441 /**
442 * Get a pair representing the time and utility value of the expected best
443 * agreement.
444 *
445 * @param expectedValues
446 * A matrix of expected utility values at the sampled time and
447 * utilities given by timeSamples and utilitySamples
448 * respectively.
449 * @param time
450 * The current time.
451 * @return a pair representing the time and utility value of the expected
452 * best agreement.
453 */
454 private Pair<Double, Double> getExpectedBestAgreement(
455 Matrix probabilityExpectedValues, Matrix cumulativeExpectedValues,
456 double time) {
457 Matrix probabilityFutureExpectedValues = getFutureExpectedValues(
458 probabilityExpectedValues, time);
459 Matrix cumulativeFutureExpectedValues = getFutureExpectedValues(
460 cumulativeExpectedValues, time);
461
462 double[][] probabilityFutureExpectedValuesArray = probabilityFutureExpectedValues
463 .getArray();
464 double[][] cumulativeFutureExpectedValuesArray = cumulativeFutureExpectedValues
465 .getArray();
466
467 Double bestX = null;
468 Double bestY = null;
469
470 double[] colSums = new double[probabilityFutureExpectedValuesArray[0].length];
471 double bestColSum = 0;
472 int bestCol = 0;
473
474 for (int x = 0; x < probabilityFutureExpectedValuesArray[0].length; x++) {
475 colSums[x] = 0;
476 for (int y = 0; y < probabilityFutureExpectedValuesArray.length; y++) {
477 colSums[x] += probabilityFutureExpectedValuesArray[y][x];
478 }
479
480 if (colSums[x] >= bestColSum) {
481 bestColSum = colSums[x];
482 bestCol = x;
483 }
484 }
485
486 int bestRow = 0;
487 double bestRowValue = 0;
488
489 for (int y = 0; y < cumulativeFutureExpectedValuesArray.length; y++) {
490 double expectedValue = cumulativeFutureExpectedValuesArray[y][bestCol];
491 if (expectedValue > bestRowValue) {
492 bestRowValue = expectedValue;
493 bestRow = y;
494 }
495 }
496
497 bestX = timeSamples.get(0,
498 bestCol + probabilityExpectedValues.getColumnDimension()
499 - probabilityFutureExpectedValues.getColumnDimension());
500 bestY = utilitySamples.get(bestRow, 0);
501
502 return new Pair<Double, Double>(bestX, bestY);
503 }
504
505 /**
506 * Get a matrix of expected utility values at the sampled time and utilities
507 * given by timeSamples and utilitySamples, for times in the future.
508 *
509 * @param expectedValues
510 * A matrix of expected utility values at the sampled time and
511 * utilities given by timeSamples and utilitySamples
512 * respectively.
513 * @param time
514 * The current time.
515 * @return a matrix of expected utility values for future time.
516 */
517 private Matrix getFutureExpectedValues(Matrix expectedValues, double time) {
518 int i = 0;
519 for (; i < timeSamples.getColumnDimension(); i++) {
520 if (timeSamples.get(0, i) > time)
521 break;
522 }
523 return expectedValues.getMatrix(0, expectedValues.getRowDimension() - 1,
524 i, expectedValues.getColumnDimension() - 1);
525 }
526
527 /*
528 * (non-Javadoc)
529 *
530 * @see negotiator.Agent#ReceiveMessage(negotiator.actions.Action)
531 */
532 @Override
533 public final void ReceiveMessage(Action opponentAction) {
534 // Store the received opponentAction
535 messageOpponent = opponentAction;
536 }
537
538 /**
539 * Handle an opponent's offer.
540 *
541 * @param opponentBid
542 * The bid made by the opponent.
543 * @return the action that we should take in response to the opponent's
544 * offer.
545 * @throws Exception
546 */
547 private Action handleOffer(Bid opponentBid) throws Exception {
548 Action chosenAction = null;
549
550 if (myLastAction == null) {
551 // Special case to handle first action
552 Bid b = proposeInitialBid();
553 myLastBid = b;
554 chosenAction = new Offer(this.getAgentID(), b);
555 } else if (utilitySpace.getUtility(opponentBid)
556 * acceptMultiplier >= utilitySpace.getUtility(myLastBid)) {
557 // Accept opponent's bid based on my previous bid.
558 chosenAction = new Accept(this.getAgentID(), opponentBid);
559 opponentBids.add(opponentBid);
560 } else if (utilitySpace.getUtility(opponentBid)
561 * acceptMultiplier >= MAXIMUM_ASPIRATION) {
562 // Accept opponent's bid based on my previous bid.
563 chosenAction = new Accept(this.getAgentID(), opponentBid);
564 opponentBids.add(opponentBid);
565 } else {
566 Bid plannedBid = proposeNextBid(opponentBid);
567 chosenAction = new Offer(this.getAgentID(), plannedBid);
568
569 if (utilitySpace.getUtility(opponentBid)
570 * acceptMultiplier >= utilitySpace.getUtility(plannedBid)) {
571 // Accept opponent's bid based on my planned bid.
572 chosenAction = new Accept(this.getAgentID(), opponentBid);
573 }
574 opponentBids.add(opponentBid);
575 }
576
577 return chosenAction;
578 }
579
580 /**
581 * Gets the version number.
582 *
583 * @return the version number.
584 */
585 @Override
586 public String getVersion() {
587 return "2.0";
588 }
589
590 /*
591 * (non-Javadoc)
592 *
593 * @see negotiator.Agent#chooseAction()
594 */
595 @Override
596 public final Action chooseAction() {
597 Action chosenAction = null;
598 Bid opponentBid = null;
599
600 try {
601 switch (getActionType(this.messageOpponent)) {
602 case OFFER:
603 opponentBid = ((Offer) this.messageOpponent).getBid();
604 chosenAction = handleOffer(opponentBid);
605 break;
606 case ACCEPT:
607 case BREAKOFF:
608 break;
609 default:
610 if (this.myLastAction == null) {
611 chosenAction = new Offer(getAgentID(), proposeInitialBid());
612 } else {
613 chosenAction = this.myLastAction;
614 }
615 break;
616 }
617
618 } catch (Exception e) {
619 e.printStackTrace();
620 chosenAction = new Offer(this.getAgentID(), myLastBid);
621 }
622 myLastAction = chosenAction;
623 if (myLastAction instanceof Offer) {
624 Bid b = ((Offer) myLastAction).getBid();
625 myLastBid = b;
626 }
627
628 return chosenAction;
629 }
630
631 /**
632 * Get the action type of a given action.
633 *
634 * @param action
635 * The action.
636 * @return The action type of the action.
637 */
638 private ActionType getActionType(Action action) {
639 ActionType actionType = ActionType.START;
640 if (action instanceof Offer)
641 actionType = ActionType.OFFER;
642 else if (action instanceof Accept)
643 actionType = ActionType.ACCEPT;
644 else if (action instanceof EndNegotiation)
645 actionType = ActionType.BREAKOFF;
646 return actionType;
647 }
648
649 @Override
650 public SupportedNegotiationSetting getSupportedNegotiationSetting() {
651 return SupportedNegotiationSetting.getLinearUtilitySpaceInstance();
652 }
653
654 @Override
655 public String getDescription() {
656 return "ANAC2011";
657 }
658}
Note: See TracBrowser for help on using the repository browser.