source: src/main/java/agents/bayesianopponentmodel/PerfectBayesianOpponentModelScalable.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: 16.1 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.EvaluatorInteger;
14import genius.core.utility.EvaluatorReal;
15
16/**
17 * Version of the standard Scalable Bayesian Model which uses the opponent's
18 * utilityspace to calculate the real utility of the opponent's bid. This is
19 * equivalent to having complete knowledge about the opponent's decision
20 * function.
21 *
22 * KNOWN BUGS: (similar to original BayesianOpponentModelScalable) 1. Opponent
23 * model does not take the opponent's strategy into account, in contrast to the
24 * original paper which depicts an assumption about the opponent'strategy which
25 * adapts over time.
26 *
27 * 2. The opponent model becomes invalid after a while as NaN occurs in some
28 * hypotheses, corrupting the overall estimation.
29 *
30 * @author Mark Hendrikx
31 */
32public class PerfectBayesianOpponentModelScalable extends OpponentModel {
33
34 private AdditiveUtilitySpace fUS;
35 private ArrayList<ArrayList<WeightHypothesis2>> fWeightHyps;
36 private ArrayList<ArrayList<EvaluatorHypothesis>> fEvaluatorHyps;
37
38 List<Issue> issues;
39 private double[] fExpectedWeights;
40 private AdditiveUtilitySpace opponentSpace;
41
42 public PerfectBayesianOpponentModelScalable(
43 AdditiveUtilitySpace pUtilitySpace) {
44 fDomain = pUtilitySpace.getDomain();
45 issues = fDomain.getIssues();
46 fUS = pUtilitySpace;
47 fBiddingHistory = new ArrayList<Bid>();
48 fExpectedWeights = new double[pUtilitySpace.getDomain().getIssues()
49 .size()];
50 fWeightHyps = new ArrayList<ArrayList<WeightHypothesis2>>();
51 // generate all possible ordering combinations of the weights
52
53 initWeightHyps();
54 // generate all possible hyps of evaluation functions
55 fEvaluatorHyps = new ArrayList<ArrayList<EvaluatorHypothesis>>();
56 int lTotalTriangularFns = 4;
57 for (int i = 0; i < fUS.getNrOfEvaluators(); i++) {
58 ArrayList<EvaluatorHypothesis> lEvalHyps;
59 EvaluatorReal lHypEvalReal;
60 EvaluatorInteger lHypEvalInteger;
61 EvaluatorHypothesis lEvaluatorHypothesis;
62 switch (fUS.getEvaluator(issues.get(i).getNumber()).getType()) {
63
64 case REAL:
65 lEvalHyps = new ArrayList<EvaluatorHypothesis>();
66 fEvaluatorHyps.add(lEvalHyps);
67 // EvaluatorReal lEval = (EvaluatorReal)(fUS.getEvaluator(i));
68 IssueReal lIssue = (IssueReal) (fDomain.getIssues().get(i));
69 // uphill
70 EvaluatorReal lHypEval;
71 lHypEval = new EvaluatorReal();
72 lHypEval.setUpperBound(lIssue.getUpperBound());
73 lHypEval.setLowerBound(lIssue.getLowerBound());
74 lHypEval.setType(EVALFUNCTYPE.LINEAR);
75 lHypEval.addParam(1, (double) 1
76 / (lHypEval.getUpperBound() - lHypEval.getLowerBound()));
77 lHypEval.addParam(
78 0,
79 -lHypEval.getLowerBound()
80 / (lHypEval.getUpperBound() - lHypEval
81 .getLowerBound()));
82 lEvaluatorHypothesis = new EvaluatorHypothesis(lHypEval);
83 lEvaluatorHypothesis.setDesc("uphill");
84 lEvalHyps.add(lEvaluatorHypothesis);
85 // downhill
86 lHypEval = new EvaluatorReal();
87 lHypEval.setUpperBound(lIssue.getUpperBound());
88 lHypEval.setLowerBound(lIssue.getLowerBound());
89 lHypEval.setType(EVALFUNCTYPE.LINEAR);
90 lHypEval.addParam(1, -(double) 1
91 / (lHypEval.getUpperBound() - lHypEval.getLowerBound()));
92 lHypEval.addParam(0, (double) 1 + lHypEval.getLowerBound()
93 / (lHypEval.getUpperBound() - lHypEval.getLowerBound()));
94 lEvaluatorHypothesis = new EvaluatorHypothesis(lHypEval);
95 lEvalHyps.add(lEvaluatorHypothesis);
96 lEvaluatorHypothesis.setDesc("downhill");
97 for (int k = 1; k <= lTotalTriangularFns; k++) {
98 // triangular
99 lHypEval = new EvaluatorReal();
100 lHypEval.setUpperBound(lIssue.getUpperBound());
101 lHypEval.setLowerBound(lIssue.getLowerBound());
102 lHypEval.setType(EVALFUNCTYPE.TRIANGULAR);
103 lHypEval.addParam(0, lHypEval.getLowerBound());
104 lHypEval.addParam(1, lHypEval.getUpperBound());
105 double lMaxPoint = lHypEval.getLowerBound()
106 + (double) k
107 * (lHypEval.getUpperBound() - lHypEval
108 .getLowerBound())
109 / (lTotalTriangularFns + 1);
110 lHypEval.addParam(2, lMaxPoint);
111 lEvaluatorHypothesis = new EvaluatorHypothesis(lHypEval);
112 lEvalHyps.add(lEvaluatorHypothesis);
113 lEvaluatorHypothesis.setDesc("triangular "
114 + String.format("%1.2f", lMaxPoint));
115 }
116 for (int k = 0; k < lEvalHyps.size(); k++) {
117 lEvalHyps.get(k).setProbability(
118 (double) 1 / lEvalHyps.size());
119 }
120
121 break;
122 case DISCRETE:
123 lEvalHyps = new ArrayList<EvaluatorHypothesis>();
124 fEvaluatorHyps.add(lEvalHyps);
125 // EvaluatorReal lEval = (EvaluatorReal)(fUS.getEvaluator(i));
126 IssueDiscrete lDiscIssue = (IssueDiscrete) (fDomain.getIssues()
127 .get(i));
128 // uphill
129 EvaluatorDiscrete lDiscreteEval = new EvaluatorDiscrete();
130 for (int j = 0; j < lDiscIssue.getNumberOfValues(); j++)
131 lDiscreteEval.addEvaluation(lDiscIssue.getValue(j),
132 1000 * j + 1);
133 lEvaluatorHypothesis = new EvaluatorHypothesis(lDiscreteEval);
134 lEvaluatorHypothesis.setProbability((double) 1 / 3);
135 lEvaluatorHypothesis.setDesc("uphill");
136 lEvalHyps.add(lEvaluatorHypothesis);
137 // downhill
138 lDiscreteEval = new EvaluatorDiscrete();
139 for (int j = 0; j < lDiscIssue.getNumberOfValues(); j++)
140 lDiscreteEval
141 .addEvaluation(
142 lDiscIssue.getValue(j),
143 1000 * (lDiscIssue.getNumberOfValues() - j - 1) + 1);
144 lEvaluatorHypothesis = new EvaluatorHypothesis(lDiscreteEval);
145 lEvaluatorHypothesis.setProbability((double) 1 / 3);
146 lEvalHyps.add(lEvaluatorHypothesis);
147 lEvaluatorHypothesis.setDesc("downhill");
148 if (lDiscIssue.getNumberOfValues() > 2) {
149 lTotalTriangularFns = lDiscIssue.getNumberOfValues() - 1;
150 for (int k = 1; k < lTotalTriangularFns; k++) {
151 // triangular. Wouter: we need to CHECK this.
152 lDiscreteEval = new EvaluatorDiscrete();
153 for (int j = 0; j < lDiscIssue.getNumberOfValues(); j++)
154 if (j < k) {
155 lDiscreteEval.addEvaluation(
156 lDiscIssue.getValue(j), 1000 * j / k);
157 } else {
158 // lEval =
159 // (1.0-(double)(j-k)/(lDiscIssue.getNumberOfValues()-1.0-k));
160 lDiscreteEval.addEvaluation(
161 lDiscIssue.getValue(j),
162 1000
163 * (lDiscIssue
164 .getNumberOfValues()
165 - j - 1)
166 / (lDiscIssue
167 .getNumberOfValues()
168 - k - 1) + 1);
169 }
170 lEvaluatorHypothesis = new EvaluatorHypothesis(
171 lDiscreteEval);
172 lEvalHyps.add(lEvaluatorHypothesis);
173 lEvaluatorHypothesis.setDesc("triangular "
174 + String.valueOf(k));
175 }// for
176 }// if
177 for (int k = 0; k < lEvalHyps.size(); k++) {
178 lEvalHyps.get(k).setProbability(
179 (double) 1 / lEvalHyps.size());
180 }
181 break;
182 }// switch
183 }
184 for (int i = 0; i < fExpectedWeights.length; i++)
185 fExpectedWeights[i] = getExpectedWeight(i);
186
187 // printEvalsDistribution();
188 }
189
190 void initWeightHyps() {
191 int lWeightHypsNumber = 11;
192 for (int i = 0; i < fUS.getDomain().getIssues().size(); i++) {
193 ArrayList<WeightHypothesis2> lWeightHyps = new ArrayList<WeightHypothesis2>();
194 for (int j = 0; j < lWeightHypsNumber; j++) {
195 WeightHypothesis2 lHyp = new WeightHypothesis2(fDomain);
196 lHyp.setProbability((1.0 - ((double) j + 1.0)
197 / lWeightHypsNumber)
198 * (1.0 - ((double) j + 1.0) / lWeightHypsNumber)
199 * (1.0 - ((double) j + 1.0) / lWeightHypsNumber));
200 lHyp.setWeight((double) j / (lWeightHypsNumber - 1));
201 lWeightHyps.add(lHyp);
202 }
203 double lN = 0;
204 for (int j = 0; j < lWeightHypsNumber; j++) {
205 lN += lWeightHyps.get(j).getProbability();
206 }
207 for (int j = 0; j < lWeightHypsNumber; j++) {
208 lWeightHyps.get(j).setProbability(
209 lWeightHyps.get(j).getProbability() / lN);
210 }
211
212 fWeightHyps.add(lWeightHyps);
213 }
214 }
215
216 private double conditionalDistribution(double pUtility,
217 double pPreviousBidUtility) {
218 // TODO: check this condition
219 // if(pPreviousBidUtility<pUtility) return 0;
220 // else {
221 double lSigma = 0.25;
222 double x = (pPreviousBidUtility - pUtility) / pPreviousBidUtility;
223 double lResult = 1.0 / (lSigma * Math.sqrt(2.0 * Math.PI))
224 * Math.exp(-(x * x) / (2.0 * lSigma * lSigma));
225 return lResult;
226 // }
227 }
228
229 public double getExpectedEvaluationValue(Bid pBid, int pIssueNumber)
230 throws Exception {
231 double lExpectedEval = 0;
232 for (int j = 0; j < fEvaluatorHyps.get(pIssueNumber).size(); j++) {
233 lExpectedEval = lExpectedEval
234 + fEvaluatorHyps.get(pIssueNumber).get(j).getProbability()
235 * fEvaluatorHyps
236 .get(pIssueNumber)
237 .get(j)
238 .getEvaluator()
239 .getEvaluation(fUS, pBid,
240 issues.get(pIssueNumber).getNumber());
241 }
242 return lExpectedEval;
243
244 }
245
246 public double getExpectedWeight(int pIssueNumber) {
247 double lExpectedWeight = 0;
248 for (int i = 0; i < fWeightHyps.get(pIssueNumber).size(); i++) {
249 lExpectedWeight += fWeightHyps.get(pIssueNumber).get(i)
250 .getProbability()
251 * fWeightHyps.get(pIssueNumber).get(i).getWeight();
252 }
253 return lExpectedWeight;
254 }
255
256 private double getPartialUtility(Bid pBid, int pIssueIndex)
257 throws Exception {
258 // calculate partial utility w/o issue pIssueIndex
259 double u = 0;
260 for (int j = 0; j < fDomain.getIssues().size(); j++) {
261 if (pIssueIndex == j)
262 continue;
263 // calculate expected weight of the issue
264 double w = 0;
265 for (int k = 0; k < fWeightHyps.get(j).size(); k++)
266 w += fWeightHyps.get(j).get(k).getProbability()
267 * fWeightHyps.get(j).get(k).getWeight();
268 u = u + w * getExpectedEvaluationValue(pBid, j);
269 }
270 return u;
271 }
272
273 public void updateWeights(double opponentUtility) throws Exception {
274 Bid lBid = fBiddingHistory.get(fBiddingHistory.size() - 1);
275 ArrayList<ArrayList<WeightHypothesis2>> lWeightHyps = new ArrayList<ArrayList<WeightHypothesis2>>();
276 // make new hyps array
277 for (int i = 0; i < fWeightHyps.size(); i++) {
278 ArrayList<WeightHypothesis2> lTmp = new ArrayList<WeightHypothesis2>();
279 for (int j = 0; j < fWeightHyps.get(i).size(); j++) {
280 WeightHypothesis2 lHyp = new WeightHypothesis2(fUS.getDomain());
281 lHyp.setWeight(fWeightHyps.get(i).get(j).getWeight());
282 lHyp.setProbability(fWeightHyps.get(i).get(j).getProbability());
283 lTmp.add(lHyp);
284 }
285 lWeightHyps.add(lTmp);
286 }
287
288 // for(int k=0;k<5;k++) {
289 for (int j = 0; j < fDomain.getIssues().size(); j++) {
290 double lN = 0;
291 double lUtility = 0;
292 for (int i = 0; i < fWeightHyps.get(j).size(); i++) {
293 // if(!lBid.getValue(j).equals(lPreviousBid.getValue(j))) {
294 lUtility = fWeightHyps.get(j).get(i).getWeight()
295 * getExpectedEvaluationValue(lBid, j)
296 + getPartialUtility(lBid, j);
297 lN += fWeightHyps.get(j).get(i).getProbability()
298 * conditionalDistribution(lUtility, opponentUtility);
299 /*
300 * } else { lN += fWeightHyps.get(j).get(i).getProbability(); }
301 */
302 }
303 // 2. receiveMessage probabilities
304 for (int i = 0; i < fWeightHyps.get(j).size(); i++) {
305 // if(!lBid.getValue(j).equals(lPreviousBid.getValue(j))) {
306 lUtility = fWeightHyps.get(j).get(i).getWeight()
307 * getExpectedEvaluationValue(lBid, j)
308 + getPartialUtility(lBid, j);
309 lWeightHyps
310 .get(j)
311 .get(i)
312 .setProbability(
313 fWeightHyps.get(j).get(i).getProbability()
314 * conditionalDistribution(lUtility,
315 opponentUtility) / lN);
316 /*
317 * } else {
318 * lWeightHyps.get(j).get(i).setProbability(fWeightHyps.
319 * get(j).get(i).getProbability()/lN); }
320 */
321 }
322 }
323 // }
324 fWeightHyps = lWeightHyps;
325 }
326
327 public void updateEvaluationFns(double opponentUtility) throws Exception {
328 Bid lBid = fBiddingHistory.get(fBiddingHistory.size() - 1);
329 // make new hyps array
330 // for(int k=0;k<5;k++){
331 ArrayList<ArrayList<EvaluatorHypothesis>> lEvaluatorHyps = new ArrayList<ArrayList<EvaluatorHypothesis>>();
332 for (int i = 0; i < fEvaluatorHyps.size(); i++) {
333 ArrayList<EvaluatorHypothesis> lTmp = new ArrayList<EvaluatorHypothesis>();
334 for (int j = 0; j < fEvaluatorHyps.get(i).size(); j++) {
335 EvaluatorHypothesis lHyp = new EvaluatorHypothesis(
336 fEvaluatorHyps.get(i).get(j).getEvaluator());
337 lHyp.setDesc(fEvaluatorHyps.get(i).get(j).getDesc());
338 lHyp.setProbability(fEvaluatorHyps.get(i).get(j)
339 .getProbability());
340 lTmp.add(lHyp);
341 }
342 lEvaluatorHyps.add(lTmp);
343 }
344
345 // 1. calculate the normalization factor
346
347 for (int i = 0; i < fDomain.getIssues().size(); i++) {
348 // 1. calculate the normalization factor
349 double lN = 0;
350 for (int j = 0; j < fEvaluatorHyps.get(i).size(); j++) {
351 EvaluatorHypothesis lHyp = fEvaluatorHyps.get(i).get(j);
352 lN += lHyp.getProbability()
353 * conditionalDistribution(
354 getPartialUtility(lBid, i)
355 + getExpectedWeight(i)
356 * (lHyp.getEvaluator().getEvaluation(
357 fUS, lBid, issues.get(i)
358 .getNumber())),
359 opponentUtility);
360 }
361 // 2. receiveMessage probabilities
362 for (int j = 0; j < fEvaluatorHyps.get(i).size(); j++) {
363 EvaluatorHypothesis lHyp = fEvaluatorHyps.get(i).get(j);
364 lEvaluatorHyps
365 .get(i)
366 .get(j)
367 .setProbability(
368 lHyp.getProbability()
369 * conditionalDistribution(
370 getPartialUtility(lBid, i)
371 + getExpectedWeight(i)
372 * (lHyp.getEvaluator()
373 .getEvaluation(
374 fUS,
375 lBid,
376 issues.get(
377 i)
378 .getNumber())),
379 opponentUtility) / lN);
380 }
381 }
382 fEvaluatorHyps = lEvaluatorHyps;
383 }
384
385 public boolean haveSeenBefore(Bid pBid) {
386 for (Bid tmpBid : fBiddingHistory) {
387 if (pBid.equals(tmpBid))
388 return true;
389 }
390 return false;
391 }
392
393 public void updateBeliefs(Bid pBid) throws Exception {
394 if (haveSeenBefore(pBid))
395 return;
396 fBiddingHistory.add(pBid);
397 double opponentUtility = opponentSpace.getUtility(pBid);
398 // do not receiveMessage the bids if it is the first bid
399 if (fBiddingHistory.size() > 1) {
400
401 // receiveMessage the weights
402 updateWeights(opponentUtility);
403 // receiveMessage evaluation functions
404 updateEvaluationFns(opponentUtility);
405 } else {
406 // do not receiveMessage the weights
407 // receiveMessage evaluation functions
408 updateEvaluationFns(opponentUtility);
409 } // if
410
411 // System.out.println(getMaxHyp().toString());
412 // calculate utility of the next partner's bid according to the
413 // concession functions
414 for (int i = 0; i < fExpectedWeights.length; i++) {
415 fExpectedWeights[i] = getExpectedWeight(i);
416 }
417 findMinMaxUtility();
418 // printBestHyp();
419 }
420
421 /**
422 * Plan: cache the results for pBid in a Hash table. empty the hash table
423 * whenever updateWeights or updateEvaluationFns is called.
424 *
425 * @param pBid
426 * @return weeighted utility where weights represent likelihood of each
427 * hypothesis
428 * @throws Exception
429 */
430 public double getExpectedUtility(Bid pBid) throws Exception {
431 // calculate expected utility
432 double u = 0;
433 for (int j = 0; j < fDomain.getIssues().size(); j++) {
434 // calculate expected weight of the issue
435 double w = fExpectedWeights[j];
436 /*
437 * for(int k=0;k<fWeightHyps.get(j).size();k++) w +=
438 * fWeightHyps.get(
439 * j).get(k).getProbability()*fWeightHyps.get(j).get(
440 * k).getWeight();(
441 */
442 u = u + w * getExpectedEvaluationValue(pBid, j);
443 }
444
445 return u;
446 }
447
448 public double getNormalizedWeight(Issue i, int startingNumber) {
449 double sum = 0;
450 for (Issue issue : fDomain.getIssues()) {
451 sum += getExpectedWeight(issue.getNumber() - startingNumber);
452 }
453 return (getExpectedWeight(i.getNumber() - startingNumber)) / sum;
454 }
455
456 public void setOpponentUtilitySpace(
457 AdditiveUtilitySpace opponentUtilitySpace) {
458 this.opponentSpace = opponentUtilitySpace;
459 }
460}
Note: See TracBrowser for help on using the repository browser.