source: src/main/java/genius/core/analysis/MultilateralAnalysis.java

Last change on this file was 153, checked in by Aron Hammond, 6 years ago

Added function to calculate opposition to MultiLateralAnalysis.java

Moved code to add RLBOA listeners to RLBOAUtils is misc package

!! close SessionInfo after tournament; this caused /tmp/ to fill up with GeniusData files

This commit finalized the RLBOA project and it is now ready for use

Our own package (uva.project.:

  • Moved to agents.rlboa
  • Added opponents and strategies that are mentioned in the report
  • Change class hierarchy, agents can now extend from RLBOAagentBilateral to inherit RL functionality.
  • States extend from AbstractState
File size: 11.6 KB
Line 
1package genius.core.analysis;
2
3import java.util.ArrayList;
4import java.util.Arrays;
5import java.util.List;
6
7import genius.core.Bid;
8import genius.core.BidIterator;
9import genius.core.Domain;
10import genius.core.parties.PartyWithUtility;
11import genius.core.utility.AdditiveUtilitySpace;
12import genius.core.utility.UtilitySpace;
13import genius.core.utility.UtilitySpaceTools;
14
15/**
16 * Start on analysis of the multi party tournament. Code in this class is mainly
17 * adapted from the bilateral analysis which is in the other classes of this
18 * package (negotiator.analysis)
19 *
20 * @author David Festen
21 */
22public class MultilateralAnalysis {
23 /**
24 * Maximum number of bids to analyse
25 */
26 public static final int ENUMERATION_CUTOFF = 100000;
27
28 /**
29 * List of all bid points in the domain.
30 */
31 private ArrayList<BidPoint> bidPoints;
32
33 /**
34 * Cached Pareto frontier.
35 */
36 private List<BidPoint> paretoFrontier = null; // null if not yet computed
37
38 /**
39 * Cached Nash solution. The solution is assumed to be unique.
40 */
41 private BidPoint nash = null; // null if not yet computed
42
43 private final BidPoint agreement;
44
45 private final List<? extends PartyWithUtility> parties;
46
47 /**
48 * Collection of utility spaces constituting the space.
49 */
50 private List<UtilitySpace> utilitySpaces;
51
52 /**
53 * Domain of the utility spaces.
54 *
55 */
56 private Domain domain;
57
58 private Bid agreedBid;
59
60 private final Double endTime;
61
62 /**
63 * @param parties
64 * @param agreedBid
65 * agreement, or null if there is no agreement.
66 * @param endTime
67 * the time in range [0,1] at which the negotiation ended where 0
68 * is the start and 1 the deadline time/round. If null,
69 * undiscounted utilities will be used.
70 */
71 public MultilateralAnalysis(List<? extends PartyWithUtility> parties,
72 Bid agreedBid, Double endTime) {
73 // System.out.print("Generating analysis... ");
74
75 this.parties = parties;
76 this.agreedBid = agreedBid;
77
78 this.endTime = endTime;
79
80 initializeUtilitySpaces(getUtilitySpaces());
81 buildSpace(true);
82
83 Double[] utils = new Double[utilitySpaces.size()];
84 if (agreedBid == null) {
85 for (int i = 0; i < utilitySpaces.size(); i++)
86 utils[i] = 0.0;
87 } else {
88 utils = getUtils(agreedBid);
89 }
90 agreement = new BidPoint(agreedBid, utils);
91
92 // System.out.println("done");
93
94 }
95
96 public static ArrayList<double[][]> getPartyBidSeries(
97 ArrayList<ArrayList<Double[]>> partyUtilityHistoryList) {
98
99 ArrayList<double[][]> bidSeries = new ArrayList<double[][]>();
100 double[][] product = new double[2][partyUtilityHistoryList.get(0)
101 .size()];
102 try {
103
104 for (int i = 0; i < partyUtilityHistoryList.size() - 1; i++) {
105
106 double[][] xPartyUtilities = new double[2][partyUtilityHistoryList
107 .get(i).size()];
108 int index = 0;
109
110 for (Double[] utilityHistory : partyUtilityHistoryList.get(i)) {
111
112 xPartyUtilities[0][index] = utilityHistory[0];
113 xPartyUtilities[1][index] = utilityHistory[1];
114
115 product[0][index] = utilityHistory[0];
116 if (i == 0) // for the first agent
117 product[1][index] = utilityHistory[1];
118 else
119 product[1][index] *= utilityHistory[1];
120 index++;
121 }
122
123 bidSeries.add(xPartyUtilities);
124 }
125 bidSeries.add(product);
126
127 } catch (Exception e) {
128 e.printStackTrace();
129 return null;
130 }
131
132 return bidSeries;
133 }
134
135 public List<UtilitySpace> getUtilitySpaces() {
136 List<UtilitySpace> spaces = new ArrayList<UtilitySpace>();
137 for (PartyWithUtility p : parties) {
138 spaces.add(p.getUtilitySpace());
139 }
140 return spaces;
141 }
142
143 /**
144 * Create the space with all bid points from all the
145 * {@link AdditiveUtilitySpace}s.
146 *
147 * @param excludeBids
148 * if true do not store the real bids.
149 * @throws Exception
150 * if utility can not be computed for some point.
151 */
152 private void buildSpace(boolean excludeBids) {
153
154 bidPoints = new ArrayList<BidPoint>();
155 BidIterator lBidIterator = new BidIterator(domain);
156
157 // if low memory mode, do not store the actual. At the time of writing
158 // this
159 // has no side-effects
160 int iterationNumber = 0;
161 while (lBidIterator.hasNext()) {
162 if (++iterationNumber > ENUMERATION_CUTOFF) {
163 // System.out.printf("Could not enumerate complete bid space, "
164 // +
165 // "enumerated first %d bids... ", ENUMERATION_CUTOFF);
166 break;
167 }
168 Bid bid = lBidIterator.next();
169 Double[] utils = getUtils(bid);
170 if (excludeBids) {
171 bidPoints.add(new BidPoint(null, utils));
172 } else {
173 bidPoints.add(new BidPoint(bid, utils));
174 }
175 }
176 }
177
178 /**
179 * @return current utility values for all parties as an array
180 */
181 private Double[] getUtils(Bid bid) {
182 Double[] utils = new Double[utilitySpaces.size()];
183 for (int i = 0; i < utilitySpaces.size(); i++) {
184 utils[i] = getUtility(bid, utilitySpaces.get(i));
185 }
186 return utils;
187 }
188
189 /**
190 * @param bid
191 * @return utility of a bid, discounted if {@link #endTime} is not null
192 */
193 private Double getUtility(Bid bid, UtilitySpace us) {
194 return endTime == null ? us.getUtility(bid)
195 : us.discount(us.getUtility(bid), endTime);
196 }
197
198 /**
199 * Returns the Pareto frontier. If the Pareto frontier is unknown, then it
200 * is computed using an efficient algorithm. If the utility space contains
201 * more than 500000 bids, then a suboptimal algorithm is used.
202 *
203 * @return The Pareto frontier. The order is ascending utilityA.
204 */
205 public List<BidPoint> getParetoFrontier() {
206 boolean isBidSpaceAvailable = !bidPoints.isEmpty();
207 if (paretoFrontier == null) {
208 if (isBidSpaceAvailable) {
209 paretoFrontier = computeParetoFrontier(bidPoints).getFrontier();
210 return paretoFrontier;
211 }
212
213 ArrayList<BidPoint> subPareto = new ArrayList<BidPoint>();
214 BidIterator lBidIterator = new BidIterator(domain);
215 ArrayList<BidPoint> tmpBidPoints = new ArrayList<BidPoint>();
216 boolean isSplit = false;
217 int count = 0;
218 while (lBidIterator.hasNext() && count < ENUMERATION_CUTOFF) {
219 Bid bid = lBidIterator.next();
220 Double[] utils = getUtils(bid);
221 tmpBidPoints.add(new BidPoint(bid, utils));
222 count++;
223 if (count > 500000) {
224 subPareto.addAll(
225 computeParetoFrontier(tmpBidPoints).getFrontier());
226 tmpBidPoints = new ArrayList<BidPoint>();
227 count = 0;
228 isSplit = true;
229 }
230 }
231 // Add the remainder to the sub-Pareto frontier
232 if (tmpBidPoints.size() > 0)
233 subPareto.addAll(
234 computeParetoFrontier(tmpBidPoints).getFrontier());
235
236 if (isSplit)
237 paretoFrontier = computeParetoFrontier(subPareto).getFrontier(); // merge
238 // sub-pareto's
239 else
240 paretoFrontier = subPareto;
241 }
242 return paretoFrontier;
243 }
244
245 /**
246 * Private because it should be called only with the bids as built by
247 * BuildSpace.
248 *
249 * @param points
250 * the ArrayList<BidPoint> as computed by
251 * {@link #buildSpace(boolean)} and stored in bid points.
252 * @return the sorted pareto frontier of the bid points.
253 */
254 private ParetoFrontier computeParetoFrontier(List<BidPoint> points) {
255 ParetoFrontier frontier = new ParetoFrontier();
256 for (BidPoint p : points)
257 frontier.mergeIntoFrontier(p);
258
259 frontier.sort();
260 return frontier;
261 }
262
263 /**
264 * Method which returns a list of the Pareto efficient bids.
265 *
266 * @return Pareto-efficient bids.
267 */
268 public List<Bid> getParetoFrontierBids() {
269 ArrayList<Bid> bids = new ArrayList<Bid>();
270 List<BidPoint> points = getParetoFrontier();
271 for (BidPoint p : points)
272 bids.add(p.getBid());
273 return bids;
274 }
275
276 /**
277 * Initializes the utility spaces by checking if they are valid. This
278 * procedure also clones the spaces such that manipulating them is not
279 * useful for an agent.
280 *
281 * @param utilitySpaces
282 * to be initialized and validated.
283 * @throws NullPointerException
284 * if one of the utility spaces is null.
285 */
286 private void initializeUtilitySpaces(List<UtilitySpace> utilitySpaces) {
287 this.utilitySpaces = new ArrayList<UtilitySpace>(utilitySpaces);
288
289 for (UtilitySpace utilitySpace : utilitySpaces)
290 if (utilitySpace == null)
291 throw new NullPointerException("util space is null");
292
293 domain = this.utilitySpaces.get(0).getDomain();
294
295 for (UtilitySpace space : utilitySpaces) {
296 new UtilitySpaceTools(space).checkReadyForNegotiation(domain);
297 }
298 }
299
300 public double getSocialWelfare() {
301 double totalUtility = 0;
302 if (agreedBid != null) {
303 for (PartyWithUtility agent : parties) {
304 totalUtility += getUtility(agreedBid, agent.getUtilitySpace());
305 }
306 }
307 return totalUtility;
308 }
309
310 /**
311 *
312 * @return distance of agreement to nash point
313 */
314 public double getDistanceToNash() {
315 return agreement.getDistance(getNashPoint());
316 }
317
318 /**
319 *
320 * @return distance of agreement to pareto frontier, or
321 * {@link Double#POSITIVE_INFINITY} if there is no pareto frontier.
322 */
323 public double getDistanceToPareto() {
324 double distance = Double.POSITIVE_INFINITY;
325 for (BidPoint paretoBid : getParetoFrontier()) {
326 double paretoDistance = agreement.getDistance(paretoBid);
327 if (paretoDistance < distance) {
328 distance = paretoDistance;
329 }
330 }
331 return distance;
332 }
333
334 public BidPoint getNashPoint() {
335 if (nash != null)
336 return nash;
337 if (getParetoFrontier().size() < 1) {
338 return new BidPoint(null, 0.0, 0.0);
339 }
340 double maxP = -1;
341 double[] agentResValue = new double[utilitySpaces.size()];
342 for (int i = 0; i < utilitySpaces.size(); i++)
343 if (utilitySpaces.get(i).getReservationValue() != null)
344 agentResValue[i] = utilitySpaces.get(i).getReservationValue();
345 else
346 agentResValue[i] = .0;
347 for (BidPoint p : paretoFrontier) {
348 double utilOfP = 1;
349 for (int i = 0; i < utilitySpaces.size(); i++)
350 utilOfP = utilOfP * (p.getUtility(i) - agentResValue[i]);
351
352 if (utilOfP > maxP) {
353 nash = p;
354 maxP = utilOfP;
355 }
356 }
357 return nash;
358 }
359
360 /**
361 * @return a (not necessarily unique) social welfare optimal point. Returns
362 * null if there are no bids in the space.
363 */
364
365 public BidPoint getSocialwelfarePoint() {
366 double max = -1;
367 BidPoint maxBid = null;
368
369 for (BidPoint paretoBid : getParetoFrontier()) {
370 double welfare = paretoBid.getSocialWelfare();
371 if (welfare > max) {
372 maxBid = paretoBid;
373 max = welfare;
374 }
375 }
376 return maxBid;
377 }
378
379 /**
380 * @return kalai-smorodinsky point, or BidPoint(null, 0,0) if utilspace is
381 * empty.
382 */
383 public BidPoint getKalaiPoint() {
384 double asymmetry = 2;
385 if (getParetoFrontier().size() < 1) {
386 return new BidPoint(null, 0.0, 0.0);
387 }
388 BidPoint kalaiSmorodinsky = null;
389 // every point in space will have lower asymmetry than this.
390 for (BidPoint p : paretoFrontier) {
391 double asymofp = 0;
392 for (int i = 0; i < parties.size(); i++) {
393 for (int j = i + 1; j < parties.size(); j++) {
394 asymofp += Math.abs(p.getUtility(i) - p.getUtility(j));
395 }
396 }
397
398 if (asymofp < asymmetry) {
399 kalaiSmorodinsky = p;
400 asymmetry = asymofp;
401 }
402 }
403 return kalaiSmorodinsky;
404 }
405
406 public double getOpposition() {
407 double opposition = Double.POSITIVE_INFINITY;
408 Double[] perfectOutcomeUtils = new Double[this.utilitySpaces.size()];
409 Arrays.fill(perfectOutcomeUtils, 1.0);
410
411 BidPoint virtualBestBid = new BidPoint(null, perfectOutcomeUtils);
412 for (BidPoint bidPoint : bidPoints) {
413 double dist = bidPoint.getDistance(virtualBestBid);
414 if (dist < opposition) {
415 opposition = dist;
416 }
417 }
418
419 return opposition;
420 }
421
422 /**
423 *
424 * @return agreement, or null if there is no agreement
425 */
426 public Bid getAgreement() {
427 return agreedBid;
428 }
429
430}
Note: See TracBrowser for help on using the repository browser.