source: src/main/java/agents/bayesianopponentmodel/BayesianOpponentModel.java@ 1

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

Initial import : Genius 9.0.0
File size: 17.0 KB
Line 
1package agents.bayesianopponentmodel;
2
3import java.util.ArrayList;
4import java.util.List;
5
6import genius.core.Bid;
7import genius.core.issue.Issue;
8import genius.core.issue.IssueDiscrete;
9import genius.core.issue.IssueReal;
10import genius.core.utility.AdditiveUtilitySpace;
11import genius.core.utility.EVALFUNCTYPE;
12import genius.core.utility.EvaluatorDiscrete;
13import genius.core.utility.EvaluatorReal;
14
15/**
16 * Implementation of the unscalable Bayesian Model. Only working with
17 * {@link AdditiveUtilitySpace}
18 *
19 * Opponent Modelling in Automated Multi-Issue Negotiation Using Bayesian
20 * Learning by K. Hindriks, D. Tykhonov
21 */
22public class BayesianOpponentModel extends OpponentModel {
23
24 private AdditiveUtilitySpace fUS;
25 private WeightHypothesis[] fWeightHyps;
26 private ArrayList<ArrayList<EvaluatorHypothesis>> fEvaluatorHyps;
27 private ArrayList<EvaluatorHypothesis[]> fEvalHyps;
28 private ArrayList<UtilitySpaceHypothesis> fUSHyps;
29 private boolean fUseMostProbableHypsOnly = false;
30 private ArrayList<UtilitySpaceHypothesis> fMostProbableUSHyps;
31 private double fPreviousBidUtility;
32 private double EXPECTED_CONCESSION_STEP = 0.035;
33 private double SIGMA = 0.25;
34 private boolean USE_DOMAIN_KNOWLEDGE = false;
35 List<Issue> issues;
36
37 public BayesianOpponentModel(AdditiveUtilitySpace pUtilitySpace) {
38 if (pUtilitySpace == null)
39 throw new NullPointerException("pUtilitySpace=null");
40 fDomain = pUtilitySpace.getDomain();
41 fPreviousBidUtility = 1;
42 fUS = pUtilitySpace;
43 fBiddingHistory = new ArrayList<Bid>();
44 issues = fDomain.getIssues();
45 int lNumberOfHyps = factorial(issues.size());
46 fWeightHyps = new WeightHypothesis[lNumberOfHyps/* +1 */];
47 // generate all possible ordering combinations of the weights
48 int index = 0;
49 double[] P = new double[issues.size()];
50 // take care of weights normalization
51 for (int i = 0; i < issues.size(); i++)
52 P[i] = (i + 1)
53 / ((double) ((issues.size() * (fDomain.getIssues().size() + 1)) / 2.0));
54 // build all possible orderings of the weights from P
55 antilex(new Integer(index), fWeightHyps, P,
56 fDomain.getIssues().size() - 1);
57 // add the all equal hyp
58 /*
59 * WeightHypothesis allEqual = new WeightHypothesis(fDomain); for(int
60 * i=0;i< issues.size();i++) allEqual.setWeight(i,
61 * 1./((double)(issues.size()))); //set uniform probability distribution
62 * to the weights hyps fWeightHyps[fWeightHyps.length-1] = allEqual;
63 */
64 for (int i = 0; i < fWeightHyps.length; i++)
65 fWeightHyps[i].setProbability(1. / fWeightHyps.length);
66 // generate all possible hyps of evaluation functions (arraylist with
67 // length issues with an arraylist of length values for each issue)
68 fEvaluatorHyps = new ArrayList<ArrayList<EvaluatorHypothesis>>();
69 int lTotalTriangularFns = 1;
70 for (int i = 0; i < fUS.getNrOfEvaluators(); i++) {
71 ArrayList<EvaluatorHypothesis> lEvalHyps = new ArrayList<EvaluatorHypothesis>();
72 lEvalHyps = new ArrayList<EvaluatorHypothesis>();
73 fEvaluatorHyps.add(lEvalHyps);
74 switch (fUS.getEvaluator(issues.get(i).getNumber()).getType()) {
75
76 case REAL:
77 // EvaluatorReal lEval = (EvaluatorReal)(fUS.getEvaluator(i));
78 IssueReal lIssue = (IssueReal) (fDomain.getIssues().get(i));
79 EvaluatorReal lHypEval = new EvaluatorReal();
80 EvaluatorHypothesis lEvaluatorHypothesis;
81 if (USE_DOMAIN_KNOWLEDGE) {
82 // uphill
83 lHypEval = new EvaluatorReal();
84 lHypEval.setUpperBound(lIssue.getUpperBound());
85 lHypEval.setLowerBound(lIssue.getLowerBound());
86 lHypEval.setType(EVALFUNCTYPE.LINEAR);
87 lHypEval.addParam(1,
88 1. / (lHypEval.getUpperBound() - lHypEval
89 .getLowerBound()));
90 lHypEval.addParam(
91 0,
92 -lHypEval.getLowerBound()
93 / (lHypEval.getUpperBound() - lHypEval
94 .getLowerBound()));
95 lEvaluatorHypothesis = new EvaluatorHypothesis(lHypEval);
96 lEvaluatorHypothesis.setDesc("uphill");
97 lEvalHyps.add(lEvaluatorHypothesis);
98
99 } else {
100 // uphill
101 lHypEval = new EvaluatorReal();
102 lHypEval.setUpperBound(lIssue.getUpperBound());
103 lHypEval.setLowerBound(lIssue.getLowerBound());
104 lHypEval.setType(EVALFUNCTYPE.LINEAR);
105 lHypEval.addParam(1,
106 1. / (lHypEval.getUpperBound() - lHypEval
107 .getLowerBound()));
108 lHypEval.addParam(
109 0,
110 -lHypEval.getLowerBound()
111 / (lHypEval.getUpperBound() - lHypEval
112 .getLowerBound()));
113 lEvaluatorHypothesis = new EvaluatorHypothesis(lHypEval);
114 lEvaluatorHypothesis.setDesc("uphill");
115 lEvalHyps.add(lEvaluatorHypothesis);
116 // downhill
117 lHypEval = new EvaluatorReal();
118 lHypEval.setUpperBound(lIssue.getUpperBound());
119 lHypEval.setLowerBound(lIssue.getLowerBound());
120 lHypEval.setType(EVALFUNCTYPE.LINEAR);
121 lHypEval.addParam(
122 1,
123 -1.0
124 / (lHypEval.getUpperBound() - lHypEval
125 .getLowerBound()));
126 lHypEval.addParam(
127 0,
128 1.0
129 + lHypEval.getLowerBound()
130 / (lHypEval.getUpperBound() - lHypEval
131 .getLowerBound()));
132 lEvaluatorHypothesis = new EvaluatorHypothesis(lHypEval);
133 lEvalHyps.add(lEvaluatorHypothesis);
134 lEvaluatorHypothesis.setDesc("downhill");
135 // triangular
136 for (int k = 1; k <= lTotalTriangularFns; k++) {
137 // triangular
138 lHypEval = new EvaluatorReal();
139 lHypEval.setUpperBound(lIssue.getUpperBound());
140 lHypEval.setLowerBound(lIssue.getLowerBound());
141 lHypEval.setType(EVALFUNCTYPE.TRIANGULAR);
142 lHypEval.addParam(0, lHypEval.getLowerBound());
143 lHypEval.addParam(1, lHypEval.getUpperBound());
144 lHypEval.addParam(
145 2,
146 lHypEval.getLowerBound()
147 + (double) k
148 * (lHypEval.getUpperBound() - lHypEval
149 .getLowerBound())
150 / (lTotalTriangularFns + 1));
151 lEvaluatorHypothesis = new EvaluatorHypothesis(lHypEval);
152 lEvaluatorHypothesis.setProbability((double) 1 / 3);
153 lEvalHyps.add(lEvaluatorHypothesis);
154 lEvaluatorHypothesis.setDesc("triangular");
155 }
156 }
157 for (int k = 0; k < lEvalHyps.size(); k++) {
158 lEvalHyps.get(k).setProbability(
159 (double) 1 / lEvalHyps.size());
160 }
161
162 break;
163 // for each issue three possible hypothesis are generated
164 case DISCRETE:
165 lEvalHyps = new ArrayList<EvaluatorHypothesis>();
166 fEvaluatorHyps.add(lEvalHyps);
167 // EvaluatorReal lEval = (EvaluatorReal)(fUS.getEvaluator(i));
168 IssueDiscrete lDiscIssue = (IssueDiscrete) (fDomain.getIssues()
169 .get(i));
170 if (USE_DOMAIN_KNOWLEDGE) {
171 // uphill
172 EvaluatorDiscrete lDiscreteEval = new EvaluatorDiscrete();
173 for (int j = 0; j < lDiscIssue.getNumberOfValues(); j++)
174 lDiscreteEval.addEvaluation(lDiscIssue.getValue(j),
175 1000 * j);
176 lEvaluatorHypothesis = new EvaluatorHypothesis(
177 lDiscreteEval);
178 lEvaluatorHypothesis.setDesc("uphill");
179 lEvalHyps.add(lEvaluatorHypothesis);
180
181 } else {
182 // uphill (from 1 to 1000 * valueCount + 1)
183 EvaluatorDiscrete lDiscreteEval = new EvaluatorDiscrete();
184 for (int j = 0; j < lDiscIssue.getNumberOfValues(); j++)
185 lDiscreteEval.addEvaluation(lDiscIssue.getValue(j),
186 1000 * j + 1);
187 lEvaluatorHypothesis = new EvaluatorHypothesis(
188 lDiscreteEval);
189 lEvaluatorHypothesis.setDesc("uphill");
190 lEvalHyps.add(lEvaluatorHypothesis);
191 // downhill
192 lDiscreteEval = new EvaluatorDiscrete();
193 for (int j = 0; j < lDiscIssue.getNumberOfValues(); j++)
194 lDiscreteEval
195 .addEvaluation(lDiscIssue.getValue(j),
196 1000 * (lDiscIssue.getNumberOfValues()
197 - j - 1) + 1);
198 lEvaluatorHypothesis = new EvaluatorHypothesis(
199 lDiscreteEval);
200 lEvalHyps.add(lEvaluatorHypothesis);
201 lEvaluatorHypothesis.setDesc("downhill");
202 // triangular
203 lDiscreteEval = new EvaluatorDiscrete();
204 int halfway = lDiscIssue.getNumberOfValues() / 2;
205 for (int j = 0; j < lDiscIssue.getNumberOfValues(); j++)
206 if (j < halfway)
207 lDiscreteEval.addEvaluation(lDiscIssue.getValue(j),
208 1000 * j + 1);
209 // (double)j/(((double)(lDiscIssue.getNumberOfValues()-2))/2));
210 else
211 lDiscreteEval
212 .addEvaluation(
213 lDiscIssue.getValue(j),
214 1000 * (lDiscIssue
215 .getNumberOfValues() - j - 1) + 1);
216 // 1.0-(j-((double)(lDiscIssue.getNumberOfValues())-1)/2)/(((double)(lDiscIssue.getNumberOfValues())-1)-((double)(lDiscIssue.getNumberOfValues())-1)/2));
217 lEvaluatorHypothesis = new EvaluatorHypothesis(
218 lDiscreteEval);
219 lEvalHyps.add(lEvaluatorHypothesis);
220 lEvaluatorHypothesis.setDesc("triangular");
221 }
222 break;
223
224 }
225 }
226 // each issue is estimated by a uphill, downhill, or triangular function
227 // an hypothesis about the space, is therefore a choice for uphill,
228 // downhill, or triangular for each issue.
229 // For example; if there are 6 issues, then there are 3^6 possible
230 // combinations for the issues alone!
231 buildEvaluationHyps();
232 // createFrom all hypothesis, all combinations of weights hypothesis and
233 // evaluations.
234 // For example, if there are 6 issues, then there are 6! possible weight
235 // orderings, which
236 // with all 3^6 evaluation hypothesis leads to 6! * 3^6 combinations.
237 buildUniformHyps();
238 }
239
240 private void buildUniformHyps() {
241 fUSHyps = new ArrayList<UtilitySpaceHypothesis>();
242 for (int i = 0; i < fWeightHyps.length; i++) {
243 // EvaluatorHypothesis[] lEvalHyps = new
244 // EvaluatorHypothesis[fUS.getNrOfEvaluators()];
245 for (int j = 0; j < fEvalHyps.size(); j++) {
246 UtilitySpaceHypothesis lUSHyp = new UtilitySpaceHypothesis(
247 fDomain, fUS, fWeightHyps[i], fEvalHyps.get(j));
248 fUSHyps.add(lUSHyp);
249 }
250 }
251 // normalize intial utilities
252 for (int i = 0; i < fUSHyps.size(); i++) {
253 fUSHyps.get(i).setProbability(1 / (double) (fUSHyps.size()));
254 }
255 }
256
257 private void reverse(double[] P, int m) {
258 int i = 0, j = m;
259 while (i < j) {
260 // swap elements i and j
261 double lTmp = P[i];
262 P[i] = P[j];
263 P[j] = lTmp;
264 ++i;
265 --j;
266 }
267 }
268
269 private Integer antilex(Integer index, WeightHypothesis[] hyps, double[] P,
270 int m) {
271 if (m == 0) {
272 WeightHypothesis lWH = new WeightHypothesis(fDomain);
273 for (int i = 0; i < P.length; i++)
274 lWH.setWeight(i, P[i]);
275 hyps[index] = lWH;
276 index++;
277 } else {
278 for (int i = 0; i <= m; i++) {
279 index = antilex(index, hyps, P, m - 1);
280 if (i < m) {
281 // swap elements i and m
282 double lTmp = P[i];
283 P[i] = P[m];
284 P[m] = lTmp;
285 reverse(P, m - 1);
286 } // if
287 }
288 }
289 return index;
290 }
291
292 private double conditionalDistribution(double pUtility,
293 double pPreviousBidUtility) {
294 // TODO: check this conditionb
295 if (pPreviousBidUtility < pUtility)
296 return 0;
297 else {
298
299 double x = (pPreviousBidUtility - pUtility) / pPreviousBidUtility;
300 double lResult = 1 / (SIGMA * Math.sqrt(2 * Math.PI))
301 * Math.exp(-(x * x) / (2 * SIGMA * SIGMA));
302 return lResult;
303 }
304 }
305
306 public void updateBeliefs(Bid pBid) throws Exception {
307 fBiddingHistory.add(pBid);
308 if (haveSeenBefore(pBid))
309 return;
310 // calculate full probability for the given bid
311 double lFullProb = 0;
312 double lMaxProb = 0;
313 for (int i = 0; i < fUSHyps.size(); i++) {
314 UtilitySpaceHypothesis hyp = fUSHyps.get(i);
315 double condDistrib = hyp.getProbability()
316 * conditionalDistribution(fUSHyps.get(i).getUtility(pBid),
317 fPreviousBidUtility);
318 lFullProb += condDistrib;
319 if (condDistrib > lMaxProb)
320 lMaxProb = condDistrib;
321 hyp.setProbability(condDistrib);
322 }
323 if (fUseMostProbableHypsOnly)
324 fMostProbableUSHyps = new ArrayList<UtilitySpaceHypothesis>();
325 // receiveMessage the weights hyps and evaluators hyps
326 double lMostProbableHypFullProb = 0;
327 for (int i = 0; i < fUSHyps.size(); i++) {
328 UtilitySpaceHypothesis hyp = fUSHyps.get(i);
329 double normalizedProbability = hyp.getProbability() / lFullProb;
330 hyp.setProbability(normalizedProbability);
331 if (fUseMostProbableHypsOnly)
332 if (normalizedProbability > lMaxProb * 0.99 / lFullProb) {
333 fMostProbableUSHyps.add(hyp);
334 lMostProbableHypFullProb += normalizedProbability;
335 }
336 }
337 if (fUseMostProbableHypsOnly) {
338 for (int i = 0; i < fMostProbableUSHyps.size(); i++) {
339 UtilitySpaceHypothesis hyp = fMostProbableUSHyps.get(i);
340 double normalizedProbability = hyp.getProbability()
341 / lMostProbableHypFullProb;
342 hyp.setProbability(normalizedProbability);
343 }
344 }
345
346 /*
347 * sortHyps(); for(int i=0;i<10;i++) {
348 * System.out.println(fUSHyps.get(i).toString()); }
349 */
350 System.out.println("BA: Using "
351 + String.valueOf(fMostProbableUSHyps.size()) + " out of "
352 + String.valueOf(fUSHyps.size()) + "hyps");
353 System.out.println(getMaxHyp().toString());
354 // calculate utility of the next partner's bid according to the
355 // concession functions
356 fPreviousBidUtility = fPreviousBidUtility - EXPECTED_CONCESSION_STEP;
357 // findMinMaxUtility();
358 }
359
360 private void buildEvaluationHypsRecursive(
361 ArrayList<EvaluatorHypothesis[]> pHyps,
362 EvaluatorHypothesis[] pEval, int m) {
363 if (m == 0) {
364 ArrayList<EvaluatorHypothesis> lEvalHyps = fEvaluatorHyps.get(fUS
365 .getNrOfEvaluators() - 1);
366 for (int i = 0; i < lEvalHyps.size(); i++) {
367 pEval[fUS.getNrOfEvaluators() - 1] = lEvalHyps.get(i);
368 EvaluatorHypothesis[] lTmp = new EvaluatorHypothesis[fUS
369 .getNrOfEvaluators()];
370 // copy to temp array
371 for (int j = 0; j < lTmp.length; j++)
372 lTmp[j] = pEval[j];
373 pHyps.add(lTmp);
374 }
375 } else {
376 ArrayList<EvaluatorHypothesis> lEvalHyps = fEvaluatorHyps.get(fUS
377 .getNrOfEvaluators() - m - 1);
378 for (int i = 0; i < lEvalHyps.size(); i++) {
379 pEval[fUS.getNrOfEvaluators() - m - 1] = lEvalHyps.get(i);
380 buildEvaluationHypsRecursive(pHyps, pEval, m - 1);
381 }
382 }
383 }
384
385 private void buildEvaluationHyps() {
386 fEvalHyps = new ArrayList<EvaluatorHypothesis[]>();
387 EvaluatorHypothesis[] lTmp = new EvaluatorHypothesis[fUS
388 .getNrOfEvaluators()];
389 buildEvaluationHypsRecursive(fEvalHyps, lTmp,
390 fUS.getNrOfEvaluators() - 1);
391 }
392
393 public double getExpectedUtility(Bid pBid) throws Exception {
394 double lExpectedUtility = 0;
395 if (fUseMostProbableHypsOnly && (fMostProbableUSHyps != null)) {
396 for (int i = 0; i < fMostProbableUSHyps.size(); i++) {
397 UtilitySpaceHypothesis lUSHyp = fMostProbableUSHyps.get(i);
398 double p = lUSHyp.getProbability();
399 double u = lUSHyp.getUtility(pBid);
400 lExpectedUtility += p * u;
401 }
402 } else {
403 for (int i = 0; i < fUSHyps.size(); i++) {
404 UtilitySpaceHypothesis lUSHyp = fUSHyps.get(i);
405 double p = lUSHyp.getProbability();
406 double u = lUSHyp.getUtility(pBid);
407 lExpectedUtility += p * u;
408 }
409 }
410 return lExpectedUtility;
411 }
412
413 public double getExpectedWeight(int pIssueNumber) {
414 double lExpectedWeight = 0;
415 for (int i = 0; i < fUSHyps.size(); i++) {
416 UtilitySpaceHypothesis lUSHyp = fUSHyps.get(i);
417 double p = lUSHyp.getProbability();
418 double u = lUSHyp.getHeightHyp().getWeight(pIssueNumber);
419 lExpectedWeight += p * u;
420 }
421 return lExpectedWeight;
422 }
423
424 public double getNormalizedWeight(Issue i, int startingNumber) {
425 double sum = 0;
426 for (Issue issue : fDomain.getIssues()) {
427 sum += getExpectedWeight(issue.getNumber() - startingNumber);
428 }
429 return (getExpectedWeight(i.getNumber() - startingNumber)) / sum;
430 }
431
432 private UtilitySpaceHypothesis getMaxHyp() {
433 UtilitySpaceHypothesis lHyp = fUSHyps.get(0);
434 for (int i = 0; i < fUSHyps.size(); i++) {
435 if (lHyp.getProbability() < fUSHyps.get(i).getProbability())
436 lHyp = fUSHyps.get(i);
437 }
438 return lHyp;
439 }
440
441 /*
442 * public double getExpectedUtility(Bid pBid) { double lExpectedUtility = 0;
443 * for(int i=0;i<fWeightHyps.length;i++) { WeightHypothesis lWeightHyp =
444 * fWeightHyps[i]; double p = lWeightHyp.getProbability(); double u = 0;
445 * for(int j=0;j<fEvalHyps.size();j++) { EvaluatorHypothesis[] lHyp =
446 * fEvalHyps.get(j); //calculate evaluation value and probability for(int
447 * k=0;k<lHyp.length;k++) { p = p*lHyp[k].getProbability(); u = u +
448 * lWeightHyp
449 * .getWeight(k)*(Double)(lHyp[k].getEvaluator().getEvaluation(fUS, pBid,
450 * k)); } lExpectedUtility = lExpectedUtility+ p*u; } } return 0; }
451 */
452 // Evaluate n!
453 private int factorial(int n) {
454 if (n <= 1) // base case
455 return 1;
456 else
457 return n * factorial(n - 1);
458 }
459
460 public void setMostProbableUSHypsOnly(boolean value) {
461 fUseMostProbableHypsOnly = value;
462 }
463
464 protected class HypsComparator implements java.util.Comparator {
465 public int compare(Object o1, Object o2) throws ClassCastException {
466 if (!(o1 instanceof UtilitySpaceHypothesis)) {
467 throw new ClassCastException();
468 }
469 if (!(o2 instanceof UtilitySpaceHypothesis)) {
470 throw new ClassCastException();
471 }
472 double d1 = ((UtilitySpaceHypothesis) o1).getProbability();
473 double d2 = ((UtilitySpaceHypothesis) o2).getProbability();
474
475 if (d1 > d2) {
476 return -1;
477 } else if (d1 < d2) {
478 return 1;
479 } else {
480 return 0;
481 }
482 }
483 }
484
485}
Note: See TracBrowser for help on using the repository browser.