1 | /**
|
---|
2 | *
|
---|
3 | */
|
---|
4 | package bargainingchips.analysis;
|
---|
5 |
|
---|
6 | import java.util.List;
|
---|
7 |
|
---|
8 | import java.util.ArrayList;
|
---|
9 | import java.util.Collections;
|
---|
10 | import java.util.Comparator;
|
---|
11 |
|
---|
12 | import java.io.Serializable;
|
---|
13 |
|
---|
14 | /**
|
---|
15 | *
|
---|
16 | * This class is for storing Pareto-frontier by adding bundles at analysis time.
|
---|
17 | * It adapts {@link genius.core.analysis.ParetoFrontier}.
|
---|
18 | *
|
---|
19 | */
|
---|
20 |
|
---|
21 | public class ParetoFrontier implements Serializable {
|
---|
22 |
|
---|
23 | /**
|
---|
24 | *
|
---|
25 | */
|
---|
26 | private static final long serialVersionUID = 1L;
|
---|
27 | /** List holding the Pareto-frontier bids. */
|
---|
28 | private List<BundleUtilityPoint> frontier;
|
---|
29 |
|
---|
30 | /**
|
---|
31 | * Create an empty list to store the Pareto-frontier.
|
---|
32 | */
|
---|
33 | public ParetoFrontier() {
|
---|
34 | frontier = new ArrayList<BundleUtilityPoint>();
|
---|
35 | }
|
---|
36 |
|
---|
37 | /**
|
---|
38 | * Determines if a bid should be added to the Pareto-frontier. A bid is
|
---|
39 | * added when it strictly dominates a bid in the Pareto-frontier OR when it
|
---|
40 | * is equal to a bid in the Pareto-frontier.
|
---|
41 | *
|
---|
42 | * @param bidpoint
|
---|
43 | * bid to be added to the Pareto-frontier.
|
---|
44 | */
|
---|
45 | public void mergeIntoFrontier(BundleUtilityPoint bundleutilitypoint) {
|
---|
46 | for (BundleUtilityPoint f : frontier) {
|
---|
47 | if (bundleutilitypoint.isStrictlyDominatedBy(f)) {
|
---|
48 | // the bundleutilitypoint is dominated, and therefore not added
|
---|
49 | return;
|
---|
50 | }
|
---|
51 | if (f.isStrictlyDominatedBy(bundleutilitypoint)) {
|
---|
52 | // the bundleutilitypoint dominates a Pareto-bid, which is therefore
|
---|
53 | // replaced
|
---|
54 | merge(bundleutilitypoint, f);
|
---|
55 | return;
|
---|
56 | }
|
---|
57 | }
|
---|
58 | // the bid must be equal to an existing bid, therefore add it
|
---|
59 | frontier.add(bundleutilitypoint);
|
---|
60 | }
|
---|
61 |
|
---|
62 | /**
|
---|
63 | * Adds a bid to the Pareto frontier
|
---|
64 | *
|
---|
65 | * @param newParetoBid
|
---|
66 | * new Pareto bid.
|
---|
67 | * @param dominatedParetoBid
|
---|
68 | * old Pareto bid which must now be removed.
|
---|
69 | */
|
---|
70 | private void merge(BundleUtilityPoint newParetoBid, BundleUtilityPoint dominatedParetoBid) {
|
---|
71 | // remove dominated bid.
|
---|
72 | frontier.remove(dominatedParetoBid);
|
---|
73 | // there might still be more bids which should be removed.
|
---|
74 | ArrayList<BundleUtilityPoint> toBeRemoved = new ArrayList<BundleUtilityPoint>();
|
---|
75 | for (BundleUtilityPoint f : frontier) {
|
---|
76 | if (f.isStrictlyDominatedBy(newParetoBid)) // delete dominated
|
---|
77 | // frontier points
|
---|
78 | toBeRemoved.add(f);
|
---|
79 | }
|
---|
80 | frontier.removeAll(toBeRemoved);
|
---|
81 | frontier.add(newParetoBid);
|
---|
82 | }
|
---|
83 |
|
---|
84 | /**
|
---|
85 | * Returns true if the given BundleUtilityPoint is not part of the Pareto-frontier.
|
---|
86 | *
|
---|
87 | * @param bid
|
---|
88 | * to be checked if it is Pareto-optimal.
|
---|
89 | * @return true if NOT pareto-optimal bid.
|
---|
90 | */
|
---|
91 | public boolean isBelowFrontier(BundleUtilityPoint bid) {
|
---|
92 | for (BundleUtilityPoint f : this.getFrontier())
|
---|
93 | if (bid.isStrictlyDominatedBy(f))
|
---|
94 | return true;
|
---|
95 | return false;
|
---|
96 | }
|
---|
97 |
|
---|
98 | /**
|
---|
99 | * Order the bids based on the utility for agent A.
|
---|
100 | */
|
---|
101 | public void sort() {
|
---|
102 | Collections.sort(frontier, new Comparator<BundleUtilityPoint>() {
|
---|
103 | @Override
|
---|
104 | public int compare(BundleUtilityPoint x, BundleUtilityPoint y) {
|
---|
105 | if (x.getUtilityA() < y.getUtilityA())
|
---|
106 | return -1;
|
---|
107 | else if (x.getUtilityA() > y.getUtilityA())
|
---|
108 | return 1;
|
---|
109 | else
|
---|
110 | return 0;
|
---|
111 | }
|
---|
112 | });
|
---|
113 | }
|
---|
114 |
|
---|
115 | /**
|
---|
116 | * Returns the Pareto-optimal frontier.
|
---|
117 | *
|
---|
118 | * @return Pareto-optimal frontier.
|
---|
119 | */
|
---|
120 | public List<BundleUtilityPoint> getFrontier() {
|
---|
121 | return frontier;
|
---|
122 | }
|
---|
123 | } |
---|