source: voting/src/main/java/geniusweb/voting/CollectedVotesWithValue.java@ 52

Last change on this file since 52 was 52, checked in by ruud, 14 months ago

Fixed small issues in domaineditor.
File size: 9.2 KB
Line 
1package geniusweb.voting;
2
3import java.util.ArrayList;
4import java.util.Collections;
5import java.util.HashMap;
6import java.util.HashSet;
7import java.util.List;
8import java.util.Map;
9import java.util.Set;
10
11import geniusweb.actions.PartyId;
12import geniusweb.actions.VoteWithValue;
13import geniusweb.actions.Votes;
14import geniusweb.actions.VotesWithValue;
15import geniusweb.ip.inputOutput.Input;
16import geniusweb.ip.inputOutput.Output;
17import geniusweb.ip.ipSolver.IPSolver;
18import geniusweb.ip.mainSolver.Result;
19import geniusweb.issuevalue.Bid;
20import tudelft.utilities.immutablelist.Tuple;
21
22/**
23 * Utility class. Typically contains all the votes collected from 1 round. Can
24 * find the best combinations of votes, eg to get the maximum consensus group.
25 * Basically a copy of {@link CollectedVotesWithValue} but for
26 * {@link VotesWithValue}.
27 * <p>
28 * immutable.
29 */
30public class CollectedVotesWithValue {
31 private final Map<PartyId, VotesWithValue> allvotes;
32 private final Map<PartyId, Integer> powers;
33
34 // caching
35 private transient Map<Bid, Set<VoteWithValue>> allBids = null;
36 private transient Map<PartyId, Bid> maxAgreements = null;
37 // parties must have fixed order.
38 private transient List<PartyId> parties;
39
40 /**
41 *
42 * @param votesMap the {@link Votes} done for each party
43 * @param power the power of each party. The power is an integer number.
44 * In the voting process, the party powers add up to form
45 * the total voting power. This set may contain parties that
46 * are not in newmap. The maximum number of parties is 32
47 * (memory constraints)
48 */
49 public CollectedVotesWithValue(Map<PartyId, VotesWithValue> votesMap,
50 Map<PartyId, Integer> power) {
51 this.allvotes = new HashMap<>(votesMap);
52 this.powers = new HashMap<>(power);
53 // respect insertion order of votesMap, useful
54 // for testing in combination with LinkedHashMap
55 parties = new ArrayList<PartyId>(votesMap.keySet());
56
57 if (!powers.keySet().containsAll(allvotes.keySet())) {
58 throw new IllegalArgumentException(
59 "All voting parties must have a power");
60 }
61 if (parties.size() > 32)
62 throw new IllegalArgumentException(
63 "Exceeded max number of 32 parties- won't fit in memory");
64 }
65
66 /**
67 * @return all the votes placed so far
68 */
69 public Map<PartyId, VotesWithValue> getVotes() {
70 return Collections.unmodifiableMap(allvotes);
71 }
72
73 /**
74 * @return the powers of all parties
75 */
76 public Map<PartyId, Integer> getPowers() {
77 return Collections.unmodifiableMap(powers);
78 }
79
80 /**
81 * @return a map containing for each {@link Bid}s a subset of
82 * {@link PartyId}s that placed a satisfied vote for that bid, such
83 * that the subset has maximum power. Maximum power means that there
84 * is no other subset of satisfied votes for that bid with more
85 * group power. There may be other subsets of equal power for the
86 * bid. If there are no concensus possibilities at all for a bid,
87 * the bid is not placed in the map.
88 */
89 public Map<PartyId, Bid> getMaxAgreements() {
90 if (maxAgreements == null)
91 maxAgreements = getMaxAgreements1();
92 return maxAgreements;
93 }
94
95 /**
96 * @return all bids that were voted on and the votes for that bid. This
97 * basically reverses keys and values in {@link #allvotes}
98 */
99 public Map<Bid, Set<VoteWithValue>> getAllBids() {
100 if (allBids == null)
101 allBids = getAllBids1();
102 return allBids;
103 }
104
105 /**
106 * @return the list of all parties, in the exact order as used internally
107 */
108 public List<PartyId> getParties() {
109 return Collections.unmodifiableList(parties);
110 }
111
112 @Override
113 public int hashCode() {
114 final int prime = 31;
115 int result = 1;
116 result = prime * result
117 + ((allvotes == null) ? 0 : allvotes.hashCode());
118 result = prime * result + ((powers == null) ? 0 : powers.hashCode());
119 return result;
120 }
121
122 @Override
123 public boolean equals(Object obj) {
124 if (this == obj)
125 return true;
126 if (obj == null)
127 return false;
128 if (getClass() != obj.getClass())
129 return false;
130 CollectedVotesWithValue other = (CollectedVotesWithValue) obj;
131 if (allvotes == null) {
132 if (other.allvotes != null)
133 return false;
134 } else if (!allvotes.equals(other.allvotes))
135 return false;
136 if (powers == null) {
137 if (other.powers != null)
138 return false;
139 } else if (!powers.equals(other.powers))
140 return false;
141 return true;
142 }
143
144 @Override
145 public String toString() {
146 return "CollectedVotesWithValue[" + allvotes + "," + powers + "]";
147 }
148
149 /**
150 * @see #getMaxAgreements()
151 */
152 private Map<PartyId, Bid> getMaxAgreements1() {
153 int numOfAgents = parties.size();
154 if (numOfAgents == 0)
155 return Collections.emptyMap();
156
157 double[] coalitionValues = getCoalitionValues();
158 double acceptableRatio = 100;
159 Input input = new Input(numOfAgents, coalitionValues, acceptableRatio);
160 Result result = new Result(input);
161 Output output = new Output(input);
162
163 IPSolver ipSolver = new IPSolver();
164 ipSolver.solve(input, output, result);
165 int[][] coalitions = result.get_ipBestCSFound();
166
167 // coalitions now contains array like [[3, 4], [1, 2]]
168 // indicating which parties are in coalitions.
169 Map<PartyId, Bid> agreements = new HashMap<>();
170 for (int n = 0; n < coalitions.length; n++) {
171 Set<PartyId> active = getParties(coalitions[n]);
172 Tuple<Bid, Integer> bestcoalition = getBestCoalition(active);
173 if (bestcoalition != null) {
174 Bid bestbid = bestcoalition.get1();
175 for (PartyId party : active) {
176 agreements.put(party, bestbid);
177 }
178 }
179 }
180 return agreements;
181 }
182
183 /**
184 * @return array of the maximum goalition value for each possible coalition,
185 * structured as required for the IP algorithm: arrey element k
186 * contains the best coalition with members
187 * {@link #getActiveParties(int)}
188 */
189 protected double[] getCoalitionValues() {
190 int numOfAgents = parties.size();
191 double[] coalitionValues = new double[1 << numOfAgents];
192
193 for (int n = 0; n < 1 << numOfAgents; n++) {
194 Tuple<Bid, Integer> best = getBestCoalition(getActiveParties(n));
195 coalitionValues[n] = best == null ? 0 : best.get2();
196 }
197 return coalitionValues;
198 }
199
200 /**
201 * @param active the set of active parties to consider for a coalition.
202 * @return the Bid and the coalition value of the bid. This searches the bid
203 * that all parties can accept and has the highest sum of values.
204 * Returns null if there is no coalition possible
205 */
206 protected Tuple<Bid, Integer> getBestCoalition(Set<PartyId> active) {
207 if (active.isEmpty())
208 return null;
209 PartyId firstparty = active.iterator().next();
210 if (!allvotes.containsKey(firstparty))
211 return null;
212 Integer power = getPower(active);
213 Bid bestBid = null;
214 Integer bestValue = 0;
215 for (VoteWithValue vote : allvotes.get(firstparty).getVotes()) {
216 Integer val = getBidValue(active, vote.getBid(), power);
217 if (val > bestValue) {
218 bestBid = vote.getBid();
219 bestValue = val;
220 }
221 }
222 if (bestBid == null)
223 return null;
224 return new Tuple<Bid, Integer>(bestBid, bestValue);
225 }
226
227 /***
228 *
229 * @param active the active parties
230 * @param bid the bid to evaluate
231 * @param power the power of the set of active parties
232 * @return the sum of the values for this bid, or 0 if this bid is
233 * unacceptable: a party did not vote for that bid, or if the actual
234 * power of the active parties is outside the acceptable range for a
235 * vote.
236 */
237 private Integer getBidValue(Set<PartyId> active, Bid bid, int power) {
238 int value = 0;
239 for (PartyId party : active) {
240 VoteWithValue vote = allvotes.get(party).getVote(bid);
241 if (vote == null || power < vote.getMinPower()
242 || power > vote.getMaxPower())
243 return 0;
244 value = value + vote.getValue();
245 }
246 return value;
247 }
248
249 /**
250 * @param n a coalition number, where 1 at bit position k indicates party k
251 * is active.
252 * @return the active parties in the n bit-indicator
253 */
254 protected Set<PartyId> getActiveParties(int n) {
255 Set<PartyId> activeparties = new HashSet<>();
256 for (PartyId party : parties) {
257 if ((n & 1) == 1) {
258 activeparties.add(party);
259 }
260 n = n >> 1;
261 }
262 return activeparties;
263 }
264
265 /**
266 *
267 * @param partynrs the party numbers in the coalition. WARNING the first
268 * party number is assumed to be 1, instead of the usual 0.
269 * This to match the working of the IP library that starts
270 * counting at 1.
271 * @return list of {@link PartyId}s
272 */
273 protected Set<PartyId> getParties(int[] partynrs) {
274 Set<PartyId> active = new HashSet<PartyId>(partynrs.length);
275 for (int n = 0; n < partynrs.length; n++) {
276 active.add(parties.get(partynrs[n] - 1));
277 }
278 return active;
279 }
280
281 private Map<Bid, Set<VoteWithValue>> getAllBids1() {
282 Map<Bid, Set<VoteWithValue>> bids = new HashMap<>();
283 for (VotesWithValue votes : allvotes.values()) {
284 for (VoteWithValue vote : votes.getVotes()) {
285 Bid bid = vote.getBid();
286 Set<VoteWithValue> list = bids.get(bid);
287 if (list == null)
288 list = new HashSet<VoteWithValue>();
289 list.add(vote);
290 bids.put(bid, list);
291 }
292 }
293 return bids;
294 }
295
296 /**
297 *
298 * @param activeparties a list of parties
299 * @return total voting power of the parties
300 */
301 protected Integer getPower(Set<PartyId> activeparties) {
302 return activeparties.stream().map(p -> powers.get(p)).reduce(0,
303 Integer::sum);
304 }
305}
Note: See TracBrowser for help on using the repository browser.