source: opponentmodel/src/main/java/geniusweb/opponentmodel/bayesian/BayesianOpponentModel.java@ 52

Last change on this file since 52 was 52, checked in by ruud, 14 months ago

Fixed small issues in domaineditor.
File size: 19.4 KB
Line 
1package geniusweb.opponentmodel.bayesian;
2
3import java.math.BigDecimal;
4import java.util.ArrayList;
5import java.util.Collections;
6import java.util.HashMap;
7import java.util.LinkedList;
8import java.util.List;
9import java.util.Map;
10import java.util.stream.Collectors;
11
12import geniusweb.actions.Action;
13import geniusweb.actions.Offer;
14import geniusweb.issuevalue.Bid;
15import geniusweb.issuevalue.DiscreteValue;
16import geniusweb.issuevalue.DiscreteValueSet;
17import geniusweb.issuevalue.Domain;
18import geniusweb.issuevalue.NumberValueSet;
19import geniusweb.issuevalue.Value;
20import geniusweb.issuevalue.ValueSet;
21import geniusweb.opponentmodel.FrequencyOpponentModel;
22import geniusweb.opponentmodel.OpponentModel;
23import geniusweb.profile.utilityspace.DiscreteValueSetUtilities;
24import geniusweb.profile.utilityspace.UtilitySpace;
25import geniusweb.profile.utilityspace.ValueSetUtilities;
26import geniusweb.progress.Progress;
27import geniusweb.references.Parameters;
28import tudelft.utilities.immutablelist.Range;
29
30/**
31 * <b>Warning</b>. This model is available for research and testing, and as
32 * example. Use of this is not recommended. We recommend using the
33 * {@link FrequencyOpponentModel} instead.
34 * <p>
35 * Implementation of the Bayesian Opponent Model. This model uses a set of
36 * {@link TriangleValueSetUtilities} (several for each issue) as hypotheses.
37 * Each hypothesis has a probability. Bayesian inference is used with each
38 * received bids to update these probabilities.
39 * <p>
40 * See: Opponent Modelling in Automated Multi-Issue Negotiation Using Bayesian
41 * Learning, Koen Hindriks, Dmytro Tykhonov, Proc. of 7th Int. Conf. on
42 * Autonomous Agentsand Multiagent Systems (AAMAS 2008), Padgham, Parkes,
43 * Müller and Parsons (eds.), May, 12-16., 2008, Estoril, Portugal, pp.
44 * 331-338.
45 * <h2>Parameters</h2>
46 * <ul>
47 * <li>sigma: see {@link #getSigma()}
48 * <li>decay: see {@link #getDecay()}
49 * </ul>
50 */
51public class BayesianOpponentModel implements UtilitySpace, OpponentModel {
52 private static final double DEFAULT_DECAY = 0.003;
53 private static final double DEFAULT_SIGMA = 0.25;
54 private static final int NWEIGHTS = 11; /* MAGIC NR OF WEIGHTS. */
55 private static final int NEVALUATORS = 6; // magic #numbervaluesetevaluators
56
57 /** Hypotheses are normalized PER ISSUE, so not in total. */
58 private final Map<String, List<WeightHypothesis>> weightHypoMap = new HashMap<>();
59 private final Map<String, List<EvaluatorHypothesis>> evaluatorHypoMap = new HashMap<>();
60 private final List<Bid> bidHistory = new LinkedList<>();
61 private final Domain domain;
62 private final double sigma;
63 private final double decay;
64 /**
65 * Cached per-issue weights, computed from {@link #weightHypoMap} and scaled
66 * to sum to 1
67 */
68 private final transient Map<String, Double> normalizedWeightsMap = new HashMap<>();
69
70 /**
71 * Empty constructor. If used, {@link #with(Domain, Bid)} must be called
72 * before further use
73 */
74 public BayesianOpponentModel() {
75 domain = null;
76 sigma = DEFAULT_SIGMA;
77 decay = DEFAULT_DECAY;
78 }
79
80 /**
81 * Creates initial settings with default settings (sigma=0.25, decay=0.003).
82 *
83 * @param domain the {@link Domain}
84 */
85 public BayesianOpponentModel(final Domain domain) {
86 this(domain, initialEvaluators(domain), initialWeightHyps(domain),
87 Collections.emptyList(), DEFAULT_SIGMA, DEFAULT_DECAY);
88 }
89
90 /**
91 *
92 * @param dom the {@link Domain}
93 * @param evaluatorHypos the hashmap with the evaluator hypotheses for all
94 * issues. For each issue, the sum of the hypothesis P
95 * values must be =1
96 * @param weightHypos the hashmap with the weight hypotheses for all
97 * issues. For each issue, the sum of the hypothesis P
98 * values must be =1
99 * @param history List with all previous bids, first bid is the
100 * oldest. Used to check if bid is repeated and to
101 * estimate bid utility
102 * @param sigma The spread σ of the conditional distribution. See
103 * {@link #getSigma()} and {@link #DEFAULT_SIGMA}.
104 * Must be in [0.00001, 100000] but these extremes
105 * seem unusable in practice.
106 * @param decay The expected concession rate of the opponent
107 * against time. see {@link #getDecay()} and
108 * {@link #DEFAULT_DECAY}. Must be in [0,1] where 0
109 * means no concession and 1 full concession in 1
110 * timestep.
111 */
112 public BayesianOpponentModel(final Domain dom,
113 final Map<String, List<EvaluatorHypothesis>> evaluatorHypos,
114 final Map<String, List<WeightHypothesis>> weightHypos,
115 final List<Bid> history, double sigma, double decay) {
116 if (dom == null || evaluatorHypos == null || weightHypos == null
117 || history == null)
118 throw new IllegalArgumentException("Parameters must not be null");
119 checkNormalized(evaluatorHypos);
120 checkNormalized(weightHypos);
121 if (sigma < 0.00001 || sigma > 100000)
122 throw new IllegalArgumentException(
123 "sigma must be in [0.00001, 100000], got " + sigma);
124 if (decay < 0 || decay > 1)
125 throw new IllegalArgumentException(
126 "decay must be in [0,1] but got " + decay);
127
128 this.domain = dom;
129 this.bidHistory.addAll(history);
130 this.weightHypoMap.putAll(weightHypos);
131 this.evaluatorHypoMap.putAll(evaluatorHypos);
132 this.normalizedWeightsMap.putAll(getNormalizedWeights(weightHypos));
133 this.sigma = sigma;
134 this.decay = decay;
135 }
136
137 @Override
138 public String getName() {
139 if (domain == null)
140 throw new IllegalStateException("model is not initialized");
141
142 return "FreqOppModel" + this.hashCode() + "For" + domain;
143 }
144
145 @Override
146 public Domain getDomain() {
147 return domain;
148 }
149
150 @Override
151 public Bid getReservationBid() {
152 return null;
153 }
154
155 @Override
156 public BayesianOpponentModel with(Domain newDomain, Bid newResBid) {
157 if (newDomain == null) {
158 throw new NullPointerException("domain must not be null");
159 }
160 return new BayesianOpponentModel(newDomain);
161 }
162
163 @Override
164 public BayesianOpponentModel with(final Action action,
165 final Progress progress) {
166 if (!(action instanceof Offer))
167 return this;
168 Bid bid = ((Offer) action).getBid();
169 if (bidHistory.contains(bid))
170 return this;
171 List<Bid> newHistory = new LinkedList<>(bidHistory);
172 newHistory.add(bid);
173
174 Map<String, List<EvaluatorHypothesis>> newEvaluatorHyps = updatedEvaluationFns(
175 bid);
176 Map<String, List<WeightHypothesis>> newWeightHypos = weightHypoMap;
177 if (!(bidHistory.isEmpty()))
178 newWeightHypos = updatedWeights(bid);
179
180 return new BayesianOpponentModel(domain, newEvaluatorHyps,
181 newWeightHypos, newHistory, sigma, decay);
182 }
183
184 @Override
185 public BigDecimal getUtility(final Bid bid) {
186 return BigDecimal.valueOf(getPartialUtility(bid, null));
187 }
188
189 @Override
190 public int hashCode() {
191 final int prime = 31;
192 int result = 1;
193 result = prime * result
194 + ((bidHistory == null) ? 0 : bidHistory.hashCode());
195 result = prime * result + ((domain == null) ? 0 : domain.hashCode());
196 result = prime * result + ((evaluatorHypoMap == null) ? 0
197 : evaluatorHypoMap.hashCode());
198 result = prime * result
199 + ((weightHypoMap == null) ? 0 : weightHypoMap.hashCode());
200 return result;
201 }
202
203 @Override
204 public boolean equals(Object obj) {
205 if (this == obj)
206 return true;
207 if (obj == null)
208 return false;
209 if (getClass() != obj.getClass())
210 return false;
211 BayesianOpponentModel other = (BayesianOpponentModel) obj;
212 if (bidHistory == null) {
213 if (other.bidHistory != null)
214 return false;
215 } else if (!bidHistory.equals(other.bidHistory))
216 return false;
217 if (domain == null) {
218 if (other.domain != null)
219 return false;
220 } else if (!domain.equals(other.domain))
221 return false;
222 if (evaluatorHypoMap == null) {
223 if (other.evaluatorHypoMap != null)
224 return false;
225 } else if (!evaluatorHypoMap.equals(other.evaluatorHypoMap))
226 return false;
227 if (weightHypoMap == null) {
228 if (other.weightHypoMap != null)
229 return false;
230 } else if (!weightHypoMap.equals(other.weightHypoMap))
231 return false;
232 return true;
233 }
234
235 @Override
236 public String toString() {
237 return "BayesianOpponentModel[" + domain + "," + evaluatorHypoMap + ","
238 + weightHypoMap + "]";
239 }
240
241 @Override
242 public OpponentModel with(Parameters parameters) {
243 double newsigma = parameters.getDouble("sigma", DEFAULT_SIGMA, 0.00001,
244 100000d);
245 double newdecay = parameters.getDouble("decay", DEFAULT_DECAY, 0d, 1d);
246 return new BayesianOpponentModel(domain, evaluatorHypoMap,
247 weightHypoMap, bidHistory, newsigma, newdecay);
248 }
249
250 /**
251 *
252 * @return map with the estimated weights (values) of all issues (keys). The
253 * weights sum approximately to 1 (there may be rounding errors
254 * here).
255 */
256 public Map<String, Double> getWeights() {
257 return Collections.unmodifiableMap(normalizedWeightsMap);
258 }
259
260 /**
261 *
262 * @return list with {@link Bid}s received so far. Duplicates are excluded.
263 */
264 public List<Bid> getBidHistory() {
265 return Collections.unmodifiableList(bidHistory);
266 }
267
268 /**
269 *
270 * @return The spread σ of the conditional distribution. This defines the
271 * certainty of the agent about its opponent’s negotiation tactics.
272 * If an agent is certain about the utility of an opponent’s bid bt
273 * then σ can be set to a low value. A higher level of certainty
274 * increases the learning speed, since hypotheses predicting an
275 * incorrect utility value of a bid in that case would get assigned
276 * an increasingly lower probability, and vice versa. Overestimating
277 * the level of certainty, however, may lead to incorrect results,
278 * and some care should to be taken to assign the right value to σ.
279 * Value 0.25 is recommended. Must be in [0.00001, 100000] but these
280 * extremes seem unusable in practice.
281 */
282 public double getSigma() {
283 return sigma;
284 }
285
286 /**
287 * @return the decay value which is the expected concession rate of the
288 * opponent against time.. We use linear functions to estimate the
289 * predicted utility value: u’(bt) = 1- decay·t. This assumption
290 * allows us to compute the conditional probability P(bt|hj)
291 * representing the probability of a bid bt at time t.
292 */
293 public double getDecay() {
294 return decay;
295 }
296
297 /*************** private *****************/
298 /**
299 * @return initial weight hypotheses for each issue. weights are set to
300 * linearly increase from 0 for issue 1 to 1 for last issue.
301 */
302 private static Map<String, List<WeightHypothesis>> initialWeightHyps(
303 final Domain domain) {
304
305 List<WeightHypothesis> WeightHyps = new ArrayList<>();
306 for (int j = 0; j < NWEIGHTS; j++) {
307 double weight = (double) j / (NWEIGHTS - 1);
308 WeightHypothesis lHyp = new WeightHypothesis(weight,
309 Math.exp(-0.4 * j));
310 WeightHyps.add(lHyp);
311 }
312 final List<WeightHypothesis> normalizedW = normalize(WeightHyps);
313
314 return domain.getIssues().stream()
315 .collect(Collectors.toMap(is -> is, is -> normalizedW));
316 }
317
318 /**
319 * @param domain the {@link Domain}
320 * @return the initial evaluators for the domain. This amounts to a set of
321 * triangle-shaped utility functions for each issue.
322 */
323 protected static Map<String, List<EvaluatorHypothesis>> initialEvaluators(
324 final Domain domain) {
325 final List<String> issues = new ArrayList<String>(domain.getIssues());
326 final Map<String, List<EvaluatorHypothesis>> evaluatorHyposMap = new HashMap<>();
327
328 for (String issue : issues) {
329 List<EvaluatorHypothesis> hypos = new ArrayList<>();
330 ValueSet vals = domain.getValues(issue);
331
332 if (vals instanceof NumberValueSet) {
333 Range range = ((NumberValueSet) vals).getRange();
334 double P = 1d / NEVALUATORS;
335
336 double low = range.getLow().doubleValue();
337 double step = (range.getHigh().doubleValue()
338 - range.getLow().doubleValue()) / (NEVALUATORS - 1);
339 for (int k = 0; k < NEVALUATORS; k++) {
340 double midvalue;
341 if (k == NEVALUATORS - 1) // avoid round error
342 midvalue = range.getHigh().doubleValue();
343 else
344 midvalue = low + k * step;
345 ValueSetUtilities lHypEval = new TriangleValueSetUtilities(
346 range.getLow(), BigDecimal.ZERO,
347 BigDecimal.valueOf(midvalue), BigDecimal.ONE,
348 range.getHigh(), BigDecimal.ZERO);
349 hypos.add(new EvaluatorHypothesis(lHypEval, P));
350 }
351
352 } else if (vals instanceof DiscreteValueSet) {
353 int nvals = vals.size().intValue();
354 double P = 1d / nvals;
355
356 // add one triangle for each issuevalue, with peak at value
357 Map<DiscreteValue, BigDecimal> valueUtils = new HashMap<>();
358 for (int peakpos = 0; peakpos < nvals; peakpos++) {
359 for (int j = 0; j < nvals; j++) {
360 DiscreteValue val = ((DiscreteValueSet) vals).get(j);
361 if (peakpos != 0 && j <= peakpos) {
362 valueUtils.put(val,
363 BigDecimal.valueOf((double) j / peakpos));
364 } else {
365 valueUtils.put(val, BigDecimal.valueOf(
366 (nvals - j - 1) / (nvals - peakpos - 1)));
367 }
368 }
369 hypos.add(new EvaluatorHypothesis(
370 new DiscreteValueSetUtilities(valueUtils), P));
371 }
372 }
373
374 evaluatorHyposMap.put(issue, normalize(hypos));
375 }
376 return evaluatorHyposMap;
377 }
378
379 /**
380 * @param util utility of current bid
381 * @param prevUtil utility of last received bid
382 * @return a value in &lt; 0, 1 ]. Higher means that |util-prevUtil| is
383 * smaller.
384 * <p>
385 * NOTE: the paper calls for dividing this value by (sigma sqrt(2
386 * pi)). This just scales the distance to have a peak value of 1.59,
387 * which leads to P values >1 in the rest of the computation, Also
388 * the values are scaled down anyway after that by a normalization,
389 * which makes the entire scaling just a problem. This scale factor
390 * was therefore removed.
391 */
392 private double distance(double util, double prevUtil) {
393 double x = (prevUtil - util) / prevUtil;
394 return Math.exp(-(x * x) / (2.0 * sigma * sigma));
395 }
396
397 /**
398 * @param issue the name of the issue to test
399 * @param value the value to evaluate. Should be a valid value for issue.
400 * @return the current hypothezized utility of issues
401 * @throws NullPointerException if value is not valid for issue
402 */
403 private Double getHypoUtility(String issue, Value value) {
404 return evaluatorHypoMap.get(issue).stream()
405 .map(hypo -> hypo.getProbability()
406 * hypo.getEvaluator().getUtility(value).doubleValue())
407 .mapToDouble(f -> f).sum();
408 }
409
410 /**
411 *
412 * @return map, with key=issue and value=expected weight of issue = sum of
413 * weightHyps[pIssueNumber].probability * weight/sum where sum is
414 * the sum of raw weights, such that sum of weights is 1.
415 */
416 private static Map<String, Double> getNormalizedWeights(
417 Map<String, List<WeightHypothesis>> weightHypoMap) {
418 Map<String, Double> wmap = new HashMap<>();
419
420 for (String issue : weightHypoMap.keySet()) {
421 double w = weightHypoMap.get(issue).stream()
422 .map(hypo -> hypo.getProbability() * hypo.getWeight())
423 .mapToDouble(f -> f).sum();
424
425 wmap.put(issue, w);
426 }
427 // normalize the map.
428 double sum = wmap.values().stream().mapToDouble(f -> f).sum();
429 if (sum != 0) {
430 wmap = wmap.entrySet().stream().collect(Collectors.toMap(
431 entry -> entry.getKey(), entry -> entry.getValue() / sum));
432 }
433
434 return wmap;
435 }
436
437 /**
438 *
439 * @param bid the {@link Bid} to evaluate
440 * @param ignoreIssue the issue in the bid to ignore. If null or issue is
441 * not part of the domain, a full utility is computed.
442 * @return the estimated utility of issue pIssueIndex, according to the
443 * standing hypotheses, but without issue.
444 */
445 private double getPartialUtility(Bid bid, String ignoreIssue) {
446 // calculate partial utility w/o issue pIssueIndex
447 double u = 0;
448 for (String issue : bid.getIssues()) {
449 if (issue.equals(ignoreIssue))
450 continue;
451 u = u + normalizedWeightsMap.get(issue)
452 * getHypoUtility(issue, bid.getValue(issue));
453 }
454 return u;
455 }
456
457 /**
458 * @param bid the bid that came in
459 * @return Map of updated WeightHypotheses for all issues
460 */
461 protected Map<String, List<WeightHypothesis>> updatedWeights(Bid bid) {
462 Map<String, List<WeightHypothesis>> newHypoMap = new HashMap<>();
463
464 for (String issue : domain.getIssues()) {
465 ArrayList<WeightHypothesis> weighHypos = new ArrayList<>();
466
467 for (WeightHypothesis hypo : weightHypoMap.get(issue)) {
468 double util = hypo.getWeight()
469 * getHypoUtility(issue, bid.getValue(issue))
470 + getPartialUtility(bid, issue);
471
472 double p = hypo.getProbability()
473 * distance(util, getPrevBidUtility());
474 WeightHypothesis lHyp = hypo.with(p);
475 weighHypos.add(lHyp);
476 }
477
478 newHypoMap.put(issue, normalize(weighHypos));
479 }
480 return newHypoMap;
481 }
482
483 /**
484 * @param lBid the bid that came in
485 * @return a set of new {@link EvaluatorHypothesis}
486 */
487 protected Map<String, List<EvaluatorHypothesis>> updatedEvaluationFns(
488 Bid lBid) {
489 Map<String, List<EvaluatorHypothesis>> evalHypoMap = new HashMap<>();
490
491 for (String issue : domain.getIssues()) {
492 List<EvaluatorHypothesis> hypos = new ArrayList<EvaluatorHypothesis>();
493
494 for (EvaluatorHypothesis lHyp : evaluatorHypoMap.get(issue)) {
495 // update P. This is the heart of the algorithm.
496 double p = (lHyp.getProbability()
497 * distance(
498 getPartialUtility(lBid, issue)
499 + normalizedWeightsMap.get(issue) * lHyp
500 .getEvaluator()
501 .getUtility(
502 lBid.getValue(issue))
503 .doubleValue(),
504 getPrevBidUtility()));
505 hypos.add(lHyp.with(p));
506 }
507
508 evalHypoMap.put(issue, normalize(hypos));
509 }
510 return evalHypoMap;
511 }
512
513 /**
514 * @param hypos the list of {@link Hypothesis} to be normalized (sum of P =
515 * 1).
516 * @return same list of hypotheses, but with all P scaled with same factor
517 * so that the sum of all {@link Hypothesis#getProbability()} = 1.
518 */
519 @SuppressWarnings("unchecked")
520 private static <T extends Hypothesis> List<T> normalize(List<T> hypos) {
521 final double sum = hypos.stream().map(hypo -> hypo.getProbability())
522 .mapToDouble(f -> f).sum();
523 return hypos.stream()
524 .map(hypo -> (T) hypo.with(hypo.getProbability() / sum))
525 .collect(Collectors.toList());
526 }
527
528 /**
529 * Check that the P's sum to 1 (with some allowance for round errors).
530 *
531 * @param <T> the type of {@link Hypothesis} in the map.
532 * @param hypomap a map of {@link Hypothesis}
533 */
534 private static <T extends Hypothesis> void checkNormalized(
535 Map<String, List<T>> hypomap) {
536 for (List<T> hypos : hypomap.values()) {
537 double sum = hypos.stream().map(hypo -> hypo.getProbability())
538 .mapToDouble(f -> f).sum();
539 if (Math.abs(sum - 1d) > 0.0000001)
540 throw new IllegalArgumentException(
541 "Sum of P's is not 1 " + hypos);
542 }
543 }
544
545 /**
546 * @return estimated opponent utility of previous bid.. Assumes linear
547 * decreasing utility. See paper.
548 */
549 private double getPrevBidUtility() {
550 // Notice the decay constant is mush maller than in the paper.
551 return Math.max(0d, 1d - decay * (bidHistory.size() - 1));
552 }
553
554}
Note: See TracBrowser for help on using the repository browser.