source: src/main/java/bargainingchips/analysis/BundleUtilitySpace.java@ 341

Last change on this file since 341 was 339, checked in by Faria Nassiri Mofakham, 5 years ago

BargainingChips creates bob calling BargainingBuyer. OutcomeSpace is Iterable<Bundle>, also getAllBids, getRandom, getRandom(r), getAverageUtility(u), size(), checkReadyForNegotiation, getName(), getUtility(u, b), getReservationValue(u), and getDiscountFactor added. An update on Bid getSampleBid type. An update on Agent. A history' package of BidEvent, BidEventHistory, BidEventHisoryKeeper, BidEventSortedUtility, and BidEventStrictSortedUtility added. HistoryAgent added. An analysis' package of BundleUtilityPoint, BundleUtilitySpace, and ParetoFrontier added. BargainingAgent added. TitForTatNegotiationAgent. Now, Buyer extended to BargainingBuyer which is created using Boulware or TitForTatNegotiationAgent using one among 9 utility functions. Name of strategy added toDescription in BoulwareAgent. A few small updates on several utility function classes.

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