source: src/main/java/genius/core/analysis/BidSpace.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: 17.1 KB
Line 
1package genius.core.analysis;
2
3import java.io.BufferedReader;
4import java.io.File;
5import java.io.FileReader;
6import java.io.IOException;
7import java.util.ArrayList;
8import java.util.List;
9
10import genius.core.Bid;
11import genius.core.BidIterator;
12import genius.core.Domain;
13import genius.core.exceptions.AnalysisException;
14import genius.core.utility.AbstractUtilitySpace;
15import genius.core.utility.AdditiveUtilitySpace;
16import genius.core.utility.UtilitySpace;
17
18/**
19 * A collection of utilityspaces can be viewed as a space in which a bid is
20 * assigned multiple point corresponding to the utility of the bid for different
21 * agents. We refer to this space as a BidSpace. This class allows to calculate
22 * the properties of this space.
23 *
24 * @author Dmytro Tykhonov, Tim Baarslag, Wouter Pasman
25 */
26public class BidSpace {
27
28 /** Collection of utility spaces constituting the space. */
29 private AbstractUtilitySpace[] utilspaces;
30 /** Domain of the utility spaces. */
31 private Domain domain;
32 /** List of all bidpoints in the domain. */
33 public ArrayList<BidPoint> bidPoints;
34
35 /** Cached Pareto frontier. */
36 List<BidPoint> paretoFrontier = null; // null if not yet computed
37 /**
38 * Cached Kalai-Smorodinsky solution. The solution is assumed to be unique.
39 */
40 BidPoint kalaiSmorodinsky = null; // null if not yet computed
41 /** Cached Nash solution. The solution is assumed to be unique. */
42 BidPoint nash = null; // null if not yet computed
43
44 /**
45 * Default constructor used to construct a multidimensional bidding space.
46 * Warning: this call iterates over ALL possible bids.
47 *
48 * @param utilityspaces
49 * of which the bidding space consists.
50 * @throws Exception
51 * is thrown when one of the utility spaces is corrupt.
52 */
53 public BidSpace(AbstractUtilitySpace... utilityspaces) throws Exception {
54 initializeUtilitySpaces(utilityspaces);
55 buildSpace(true);
56 }
57
58 /**
59 * Constructor to createFrom a BidSpace given exactly two utility spaces.
60 * The main difference is that if excludeBids is true, then only the bid
61 * points are saved. This has is a good way to save memory. Warning: this
62 * call iterates over ALL possible bids.
63 *
64 * @param utilityspaceA
65 * utilityspace of agent A.
66 * @param utilityspaceB
67 * utilityspace of agent B.
68 * @param excludeBids
69 * if the real bids should be saved or not.
70 * @throws Exception
71 * is thrown when one of the utility spaces is corrupt.
72 */
73 public BidSpace(AbstractUtilitySpace utilityspaceA, AbstractUtilitySpace utilityspaceB, boolean excludeBids)
74 throws Exception {
75 AbstractUtilitySpace[] spaces = { utilityspaceA, utilityspaceB };
76 initializeUtilitySpaces(spaces);
77 buildSpace(excludeBids);
78 }
79
80 /**
81 * Constructor which is identical to its three parameter version, except for
82 * the argument skipCheckSpaceB. Independent of the value of this parameter,
83 * this constructor skips the security checks for the second utilityspace.
84 * This is interesting if you use the utility of an opponent model in which
85 * some variables of the utilityspace may not be set. Warning: this call
86 * iterates over ALL possible bids.
87 *
88 * @param utilityspaceA
89 * utilityspace of agent A.
90 * @param utilityspaceB
91 * utilityspace of agent B.
92 * @param excludeBids
93 * if the real bids should be saved or not.
94 * @param skipCheckSpaceB
95 * skip security checks for the utilityspace of agent B.
96 * @throws Exception
97 * if something goes wrong when calculating the utility of a
98 * bid.
99 */
100 public BidSpace(AbstractUtilitySpace utilityspaceA, AbstractUtilitySpace utilityspaceB, boolean excludeBids,
101 boolean skipCheckSpaceB) throws Exception {
102 if (utilityspaceA == null || utilityspaceB == null)
103 throw new NullPointerException("util space is null");
104 AbstractUtilitySpace[] spaces = { utilityspaceA, utilityspaceB };
105 utilspaces = spaces.clone();
106 domain = utilspaces[0].getDomain();
107 utilityspaceA.checkReadyForNegotiation(domain);
108 buildSpace(excludeBids);
109 }
110
111 /**
112 * Initializes the utility spaces by checking if they are valid. This
113 * procedure also clones the spaces such that manipulating them is not
114 * useful for an agent.
115 *
116 * @param utilityspaces
117 * to be initialized and validated.
118 * @throws Exception
119 * if one of the utility spaces is null.
120 */
121 private void initializeUtilitySpaces(AbstractUtilitySpace[] utilityspaces) throws Exception {
122 utilspaces = utilityspaces.clone();
123 for (UtilitySpace utilitySpace : utilityspaces) {
124 if (utilitySpace == null)
125 throw new NullPointerException("util space is null: " + utilityspaces);
126 }
127 domain = utilspaces[0].getDomain();
128 for (AbstractUtilitySpace space : utilityspaces) {
129 space.checkReadyForNegotiation(domain);
130 }
131 }
132
133 // RA: This method checks whether or not the Pareto file exists
134 private boolean checkParetoFileExist(String filePathStr) {
135
136 File f = new File(filePathStr);
137 if (f.exists())
138 return true;
139 else
140 return false;
141 }
142
143 private void readParetoFromFile(String fileName, boolean isAgentAHasProfile1) {
144
145 this.paretoFrontier = new ArrayList<BidPoint>();
146 this.bidPoints = new ArrayList<BidPoint>();
147 try {
148 FileReader input = new FileReader(fileName);
149 BufferedReader bufRead = new BufferedReader(input);
150 String line;
151 Double[] utility = new Double[2];
152 do {
153 line = bufRead.readLine();
154 if (line != null) {
155 int index = line.indexOf(",");
156 if (index > 0) {
157 if (isAgentAHasProfile1) {
158 utility[0] = Double.parseDouble(line.substring(0, line.indexOf(",")));
159 utility[1] = Double.parseDouble(line.substring(line.indexOf(",") + 1));
160 } else {
161 utility[1] = Double.parseDouble(line.substring(0, line.indexOf(",")));
162 utility[0] = Double.parseDouble(line.substring(line.indexOf(",") + 1));
163 }
164
165 BidPoint bidpt = new BidPoint(null, utility);
166 this.paretoFrontier.add(bidpt);
167 }
168 }
169
170 } while (line != null);
171
172 } catch (IOException e) {
173 // If another exception is generated, print a stack trace
174 e.printStackTrace();
175 }
176
177 System.out.println(this.paretoFrontier);
178 }
179
180 /**
181 * Create the space with all bid points from all the
182 * {@link AdditiveUtilitySpace}s.
183 *
184 * @param excludeBids
185 * if true do not store the real bids.
186 * @throws exception
187 * if utility can not be computed for some point.
188 */
189 private void buildSpace(boolean excludeBids) throws Exception {
190
191 String fname = utilspaces[0].getFileName();
192 if (fname == null) {
193 fname = "";
194 }
195
196 // RA:
197 if (fname.contains("profile-1.xml")) {
198 String fileName = fname.replaceAll("profile-1.xml", "pareto.xml");
199 if (checkParetoFileExist(fileName)) {
200 readParetoFromFile(fileName, true);
201 return;
202 }
203 } else if (fname.contains("profile-2.xml")) {
204 String fileName = fname.replaceAll("profile-2.xml", "pareto.xml");
205 if (checkParetoFileExist(fileName)) {
206 readParetoFromFile(fileName, false);
207 return;
208 }
209 }
210
211 bidPoints = new ArrayList<BidPoint>();
212 BidIterator lBidIter = new BidIterator(domain);
213
214 // if low memory mode, do not store the actual. At the time of writing
215 // this
216 // has no side-effects
217 while (lBidIter.hasNext()) {
218 Bid bid = lBidIter.next();
219 Double[] utils = new Double[utilspaces.length];
220 for (int i = 0; i < utilspaces.length; i++) {
221 utils[i] = utilspaces[i].getUtility(bid);
222 }
223 if (excludeBids) {
224 bidPoints.add(new BidPoint(null, utils));
225 } else {
226 bidPoints.add(new BidPoint(bid, utils));
227 }
228 }
229 // System.out.println("Real outcome space:");
230 // System.out.println(bidPoints);
231 }
232
233 /**
234 * Returns the Pareto fronier. If the Pareto frontier is unknown, then it is
235 * computed using an efficient algorithm. If the utilityspace contains more
236 * than 500000 bids, then a suboptimal algorithm is used.
237 *
238 * @return The Pareto frontier. The order is ascending utilityA.
239 * @throws Exception
240 * if the utility of a bid can not be calculated.
241 */
242 public List<BidPoint> getParetoFrontier() throws Exception {
243 boolean isBidSpaceAvailable = !bidPoints.isEmpty();
244 if (paretoFrontier == null) {
245 if (isBidSpaceAvailable) {
246 paretoFrontier = computeParetoFrontier(bidPoints).getFrontier();
247 return paretoFrontier;
248 }
249
250 ArrayList<BidPoint> subPareto = new ArrayList<BidPoint>();
251 BidIterator lBidIter = new BidIterator(domain);
252 ArrayList<BidPoint> tmpBidPoints = new ArrayList<BidPoint>();
253 boolean isSplitted = false;
254 int count = 0;
255 while (lBidIter.hasNext()) {
256 Bid bid = lBidIter.next();
257 Double[] utils = new Double[utilspaces.length];
258 for (int i = 0; i < utilspaces.length; i++)
259 utils[i] = utilspaces[i].getUtility(bid);
260 tmpBidPoints.add(new BidPoint(bid, utils));
261 count++;
262 if (count > 500000) {
263 subPareto.addAll(computeParetoFrontier(tmpBidPoints).getFrontier());
264 tmpBidPoints = new ArrayList<BidPoint>();
265 count = 0;
266 isSplitted = true;
267 }
268 }
269 // Add the remainder to the sub-Pareto frontier
270 if (tmpBidPoints.size() > 0)
271 subPareto.addAll(computeParetoFrontier(tmpBidPoints).getFrontier());
272
273 if (isSplitted)
274 paretoFrontier = computeParetoFrontier(subPareto).getFrontier(); // merge
275 // sub-pareto's
276 else
277 paretoFrontier = subPareto;
278 }
279 return paretoFrontier;
280 }
281
282 /**
283 * Private because it should be called only with the bids as built by
284 * BuildSpace.
285 *
286 * @param points
287 * the ArrayList<BidPoint> as computed by BuildSpace and stored
288 * in bidpoints.
289 * @return the sorted pareto frontier of the bidpoints.
290 * @throws Exception
291 * if problem occurs
292 */
293 private ParetoFrontier computeParetoFrontier(List<BidPoint> points) throws Exception {
294 ParetoFrontier frontier = new ParetoFrontier();
295 for (BidPoint p : points)
296 frontier.mergeIntoFrontier(p);
297
298 frontier.sort();
299 return frontier;
300 }
301
302 /**
303 * Method which returns a list of the Pareto efficient bids.
304 *
305 * @return Pareto-efficient bids.
306 * @throws Exception
307 * if the utility of a bid cannot be calculated
308 */
309 public List<Bid> getParetoFrontierBids() throws Exception {
310 ArrayList<Bid> bids = new ArrayList<Bid>();
311 List<BidPoint> points = getParetoFrontier();
312 for (BidPoint p : points)
313 bids.add(p.getBid());
314 return bids;
315 }
316
317 /**
318 * Calculates Kalai-Smorodinsky optimal outcome. Assumes that Pareto
319 * frontier is already built. Kalai-Smorodinsky is the point on
320 * paretofrontier that has least difference in utilities for A and B.
321 *
322 * @return the Kalai-Smorodinsky BidPoint.
323 * @throws Exception
324 * when the Pareto frontier is invalid.
325 */
326 public BidPoint getKalaiSmorodinsky() throws Exception {
327 if (kalaiSmorodinsky != null)
328 return kalaiSmorodinsky;
329 if (getParetoFrontier().size() < 1)
330 throw new AnalysisException("kalaiSmorodinsky product: Pareto frontier is unavailable.");
331 double asymmetry = 2; // every point in space will have lower asymmetry
332 // than this.
333 for (BidPoint p : paretoFrontier) {
334 double asymofp = 0;
335 for (int i = 0; i < utilspaces.length; i++) {
336 for (int j = i + 1; j < utilspaces.length; j++) {
337 asymofp += Math.abs(p.getUtility(i) - p.getUtility(j));
338 }
339 }
340
341 if (asymofp < asymmetry) {
342 kalaiSmorodinsky = p;
343 asymmetry = asymofp;
344 }
345 }
346 return kalaiSmorodinsky;
347 }
348
349 /**
350 * Calculates the undiscounted Nash optimal outcome. Assumes that Pareto
351 * frontier is already built. Nash is the point on paretofrontier that has
352 * max product of utilities for A and B.
353 *
354 * @return the Nash BidPoint.
355 * @throws Exception
356 * when the Pareto frontier is invalid.
357 */
358 public BidPoint getNash() throws Exception {
359 if (nash != null)
360 return nash;
361 if (getParetoFrontier().size() < 1)
362 throw new AnalysisException("Nash product: Pareto frontier is unavailable.");
363 double maxp = -1;
364 double[] agentResValue = new double[utilspaces.length];
365 for (int i = 0; i < utilspaces.length; i++)
366 if (utilspaces[i].getReservationValue() != null)
367 agentResValue[i] = utilspaces[i].getReservationValue();
368 else
369 agentResValue[i] = .0;
370 for (BidPoint p : paretoFrontier) {
371 double utilofp = 1;
372 for (int i = 0; i < utilspaces.length; i++)
373 utilofp = utilofp * (p.getUtility(i) - agentResValue[i]);
374
375 if (utilofp > maxp) {
376 nash = p;
377 maxp = utilofp;
378 }
379 }
380 return nash;
381 }
382
383 /**
384 * Returns the nearest Pareto-optimal bid given the opponent's utility
385 * (agent B).
386 *
387 * @param opponentUtility
388 * the utility for the opponent.
389 * @return the utility of us on the pareto curve.
390 * @throws Exception
391 * if getPareto fails or other cases, e.g. paretoFrontier
392 * contains utilityB = NaN, which may occur if the opponent
393 * model creating the utility space is corrupt.
394 */
395 public double ourUtilityOnPareto(double opponentUtility) throws Exception {
396
397 if (opponentUtility < 0. || opponentUtility > 1.)
398 throw new Exception("opponentUtil " + opponentUtility + " is out of [0,1].");
399 List<BidPoint> pareto = getParetoFrontier();
400 // our utility is along A axis, opp util along B axis.
401
402 // add endpoints to pareto curve such that utilB spans [0,1] entirely
403 if (pareto.get(0).getUtility(1) < 1)
404 pareto.add(0, new BidPoint(null, new Double[] { 0., 1. }));
405 if (pareto.get(pareto.size() - 1).getUtility(1) > 0)
406 pareto.add(new BidPoint(null, new Double[] { 1., 0. }));
407 if (pareto.size() < 2)
408 throw new Exception("Pareto has only 1 point?!" + pareto);
409 // pareto is monotonically descending in utilB direction.
410 int i = 0;
411 while (!(pareto.get(i).getUtility(1) >= opponentUtility && opponentUtility > pareto.get(i + 1).getUtility(1)))
412 i++;
413
414 double oppUtil1 = pareto.get(i).getUtility(1); // this is the high value
415 double oppUtil2 = pareto.get(i + 1).getUtility(1); // the low value
416 double f = (opponentUtility - oppUtil1) / (oppUtil2 - oppUtil1); // f in
417 // [0,1]
418 // is
419 // relative
420 // distance
421 // from
422 // point
423 // i.
424 // close to point i means f~0. close to i+1 means f~1
425 double lininterpol = (1 - f) * pareto.get(i).getUtility(0) + f * pareto.get(i + 1).getUtility(0);
426 return lininterpol;
427 }
428
429 /**
430 * @return string representation of the BidSpace, which is basically a long
431 * list of all bid its bid points.
432 */
433 public String toString() {
434 return bidPoints.toString();
435 }
436
437 /**
438 * Finds the bid with the minimal distance
439 * weightA*DeltaUtilA^2+weightB*DeltaUtilB^2 where DeltaUtilA is the
440 * difference between given utilA and the actual utility of the bid.
441 *
442 * @param utilA
443 * the agent-A utility of the point to be found.
444 * @param utilB
445 * the agent-B utility of the point to be found.
446 * @param weightA
447 * weight in A direction.
448 * @param weightB
449 * weight in B direction.
450 * @param excludeList
451 * Bids to be excluded from the search.
452 * @return best point, or null if none remaining.
453 */
454 public BidPoint getNearestBidPoint(double utilA, double utilB, double weightA, double weightB,
455 ArrayList<Bid> excludeList) {
456 System.out.println("determining nearest bid to " + utilA + "," + utilB);
457 System.out.println("excludes=" + excludeList);
458 double mindist = 9.; // paretospace distances are always smaller than 2
459 BidPoint bestPoint = null;
460 double r;
461 for (BidPoint p : bidPoints) {
462 boolean contains = false;
463 for (Bid b : excludeList) {
464 if (b.equals(p.getBid())) {
465 contains = true;
466 break;
467 }
468 }
469 if (contains)
470 continue;
471 r = weightA * Math.pow((p.getUtility(0) - utilA), 2) + weightB * Math.pow((p.getUtility(1) - utilB), 2);
472 if (r < mindist) {
473 mindist = r;
474 bestPoint = p;
475 }
476 }
477 System.out.println("point found=" + bestPoint.getBid());
478 if (excludeList.size() > 1)
479 System.out.println("bid equals exclude(1):" + bestPoint.getBid().equals(excludeList.get(1)));
480 return bestPoint;
481 }
482
483 /**
484 * Method which given a bid point determines the distance to the nearest
485 * Pareto-optimal bid. If the distance is small, than the bid is near
486 * Pareto-optimal.
487 *
488 * @param bid
489 * for which the smallest distance to the Pareto frontier is
490 * found.
491 * @return distance to the nearest Pareto-optimal bid.
492 */
493 public double distanceToNearestParetoBid(BidPoint bid) {
494 if (paretoFrontier == null) {
495 try {
496 paretoFrontier = getParetoFrontier();
497 } catch (Exception e) {
498 e.printStackTrace();
499 }
500 }
501 double distance = Double.POSITIVE_INFINITY;
502 for (BidPoint paretoBid : paretoFrontier) {
503 double paretoDistance = bid.getDistance(paretoBid);
504 if (paretoDistance < distance) {
505 distance = paretoDistance;
506 }
507 }
508 return distance;
509 }
510}
Note: See TracBrowser for help on using the repository browser.