source: anac2020/Anaconda/src/main/java/geniusweb/exampleparties/anaconda/Anaconda.java

Last change on this file was 57, checked in by wouter, 3 years ago

fix supported profile type
File size: 12.3 KB
Line 
1package geniusweb.exampleparties.anaconda;
2
3import java.io.IOException;
4import java.util.ArrayList;
5import java.util.Arrays;
6import java.util.Collections;
7import java.util.HashSet;
8import java.util.List;
9import java.util.Random;
10import java.util.logging.Level;
11
12import javax.websocket.DeploymentException;
13
14import geniusweb.actions.Accept;
15import geniusweb.actions.Action;
16import geniusweb.actions.Comparison;
17import geniusweb.actions.ElicitComparison;
18import geniusweb.actions.Offer;
19import geniusweb.actions.PartyId;
20import geniusweb.bidspace.AllBidsList;
21import geniusweb.inform.ActionDone;
22import geniusweb.inform.Finished;
23import geniusweb.inform.Inform;
24import geniusweb.inform.Settings;
25import geniusweb.inform.YourTurn;
26import geniusweb.issuevalue.Bid;
27import geniusweb.party.Capabilities;
28import geniusweb.party.DefaultParty;
29import geniusweb.profile.PartialOrdering;
30import geniusweb.profileconnection.ProfileConnectionFactory;
31import geniusweb.profileconnection.ProfileInterface;
32import geniusweb.progress.Progress;
33import geniusweb.progress.ProgressRounds;
34import tudelft.utilities.logging.Reporter;
35
36public class Anaconda extends DefaultParty {
37
38 // constants
39 public static final double DEFAULT_ELICITATATION_COST = 0.01d;
40 private final Random rand = new Random();
41 private selfMap impMap;
42 private oponnentMap opponentImpMap;
43
44 private Bid receivedBid;
45
46 // variables
47 private int partial_order_bids_count = 0;
48 private ArrayList<Bid> selfBidsHistory = new ArrayList<Bid>();
49 private ArrayList<Bid> oppBidsHistory = new ArrayList<Bid>();
50
51 // parameters
52 private int bid_space_size;
53
54 // new for GeniusWeb
55 private ProfileInterface profileint;
56 private PartyId me;
57 private Progress progress;
58 private Action lastReceivedAction = null;
59 private AllBidsList allbids; // all bids in domain.
60
61 private int topN = 106;
62 private Bid reservation_bid = null;
63 private double elicitation_cost;
64 private int lower_bound_rank;
65 private int minimal_lower_bound_rank;
66 private int dynamic_lower_bound_rank;
67
68 public Anaconda() {
69 super();
70 }
71
72 public Anaconda(Reporter reporter) {
73 super(reporter);
74 }
75
76 @Override
77 public void notifyChange(Inform info) {
78 try {
79 if (info instanceof Settings) {
80 init((Settings) info);
81 } else if (info instanceof ActionDone) {
82 lastReceivedAction = ((ActionDone) info).getAction();
83 if (lastReceivedAction instanceof Offer) {
84 this.receivedBid = ((Offer) lastReceivedAction).getBid();
85 this.oppBidsHistory.add(this.receivedBid);
86 } else if (lastReceivedAction instanceof Comparison) {
87 // TODO: update MLB
88 Bid currentBid = ((Comparison) lastReceivedAction).getBid();
89 List<Bid> worseBids = ((Comparison) lastReceivedAction).getWorse();
90 List<Bid> betterBids = ((Comparison) lastReceivedAction).getBetter();
91 for (Bid worseBid : worseBids) {
92 this.impMap.comparison_update(currentBid, worseBid);
93 }
94 for (Bid betterBid : betterBids) {
95 this.impMap.comparison_update(betterBid, currentBid);
96 }
97 for (Bid betterBid : betterBids) {
98 for (Bid worseBid : worseBids) {
99 this.impMap.comparison_update(betterBid, worseBid);
100 }
101 }
102
103 this.partial_order_bids_count++;
104 this.impMap.updateBidsRank(allbids);
105 }
106 } else if (info instanceof YourTurn) {
107 double time = progress.get(System.currentTimeMillis());
108
109 // elicit - assume async
110 double lower_imp = this.impMap.rank_to_importance(this.lower_bound_rank);
111 double upper_imp = this.impMap.getMaxBidImp();
112 Bid b_star = this.getBidStar(lower_imp, upper_imp);
113 // TODO: add flag for single elicit
114 if (this.should_elicit(b_star)) {
115 Bid elicit_bid = this.impMap.getBidForElicit(lower_imp, upper_imp, allbids);
116 ElicitComparison elicit_action = new ElicitComparison(me, elicit_bid, (List<Bid>) this.allbids);
117 getConnection().send(elicit_action);
118 }
119
120 // update
121 this.update_params(time);
122 // action
123 Action action = chooseAction();
124 getConnection().send(action);
125
126 if (action instanceof Offer) {
127 Bid sent_bid = ((Offer) action).getBid();
128 this.selfBidsHistory.add(sent_bid);
129 }
130
131 if (progress instanceof ProgressRounds) {
132 progress = ((ProgressRounds) progress).advance();
133 }
134 } else if (info instanceof Finished) {
135 getReporter().log(Level.INFO, "Final ourcome:" + info);
136 }
137 } catch (Exception e) {
138 throw new RuntimeException("Failed to handle info", e);
139 }
140 }
141
142 private void update_params(double time) {
143 // linear decay
144 this.lower_bound_rank = (int) Math
145 .round((this.bid_space_size - 1) - time * ((this.bid_space_size - 1) - this.minimal_lower_bound_rank));
146 }
147
148 @Override
149 public Capabilities getCapabilities() {
150 return new Capabilities(new HashSet<>(Arrays.asList("SHAOP")), Collections.singleton(PartialOrdering.class));
151 }
152
153 @Override
154 public String getDescription() {
155 return "ANAC 2020 Anaconda SHAOP.";
156 }
157
158 private void init(Settings info) throws IOException, DeploymentException {
159 this.me = info.getID();
160 this.progress = info.getProgress();
161
162 this.profileint = ProfileConnectionFactory.create(info.getProfile().getURI(), getReporter());
163 PartialOrdering partialprofile = (PartialOrdering) profileint.getProfile();
164
165 this.reservation_bid = this.profileint.getProfile().getReservationBid();
166 this.elicitation_cost = DEFAULT_ELICITATATION_COST; // TODO: complete
167 allbids = new AllBidsList(partialprofile.getDomain());
168 this.bid_space_size = allbids.size().intValue();
169
170 this.impMap = new selfMap(partialprofile);
171 this.opponentImpMap = new oponnentMap(partialprofile);
172
173 // bids from our profile.
174 List<Bid> orderedbids = new SimpleLinearOrdering(profileint.getProfile()).getBids();
175
176 // Update my importance map
177 this.impMap.initial_update(orderedbids, allbids);
178 this.partial_order_bids_count = orderedbids.size();
179
180 // LB and MLB
181 this.lower_bound_rank = this.bid_space_size - 1;
182 double RB_sigma = Math.sqrt(bid_variance(this.reservation_bid));
183 double U_RB = this.impMap.getImportance(this.reservation_bid);
184 int RB_rank_abs = this.impMap.importanceToRankAbs(U_RB);
185 int rise = this.impMap.importanceToRankAbs(U_RB + RB_sigma) - RB_rank_abs;
186 int fall = RB_rank_abs - this.impMap.importanceToRankAbs(U_RB - RB_sigma);
187 int RB_sigma_rank_abs = (int) Math.round((rise + fall) / 2.0);
188 this.minimal_lower_bound_rank = RB_rank_abs + RB_sigma_rank_abs;
189 }
190
191 private Action chooseAction() {
192 // start competition - offer our max importance bid
193 if (!(this.lastReceivedAction instanceof Offer)) {
194 return new Offer(me, this.impMap.getBidInRank(this.bid_space_size - 1));
195 }
196
197 // accept
198 double received_bid_imp = this.impMap.getImportance(this.receivedBid);
199 int received_bid_rank = this.impMap.importanceToRankAbs(received_bid_imp);
200
201 if (received_bid_rank >= this.lower_bound_rank) {
202 return new Accept(me, this.receivedBid);
203 }
204
205 // offer
206 double lower_imp = this.impMap.rank_to_importance(this.lower_bound_rank);
207 double upper_imp = this.impMap.getMaxBidImp();
208 List<Bid> bids_intersection = this.getIntersectingBids(lower_imp, upper_imp);
209
210 // no intersection
211 Bid bid_offer = null;
212
213 if (bids_intersection.isEmpty()) {
214 List<Bid> optionalBids = this.opponentImpMap.getTopBids(bids_intersection, this.topN);
215 bid_offer = optionalBids.get(rand.nextInt(optionalBids.size()));
216 }
217 //
218 else {
219 Bid best_bid = this.impMap.getBestBid(bids_intersection);
220 this.dynamic_lower_bound_rank = this.impMap.importanceToRankAbs(this.impMap.getImportance(best_bid));
221 bid_offer = best_bid;
222 }
223
224 return new Offer(me, bid_offer);
225 }
226
227 private List<Bid> getIntersectingBids(double lower_imp, double upper_imp) {
228 List<Bid> self_bids = this.impMap.getBidsInRange(lower_imp, upper_imp, this.allbids);
229 List<Bid> opp_bids = this.getOppOptionalBids();
230 HashSet<Bid> self_bids_hash = new HashSet<Bid>(self_bids);
231
232 List<Bid> intersection = new ArrayList<Bid>();
233
234 for (Bid bid : opp_bids) {
235 if (self_bids_hash.contains(bid)) {
236 intersection.add(bid);
237 }
238 }
239
240 return intersection;
241 }
242
243 private List<Bid> getOppOptionalBids() {
244 double opp_lower_bound = this.find_OLB();
245 List<Bid> optionalBids = this.opponentImpMap.getBidsInRange(opp_lower_bound, Double.MAX_VALUE, this.allbids);
246
247 return optionalBids;
248 }
249
250 // elicit comparison
251 private Double bid_variance(Bid bid) {
252 return bid_variance(bid, 0);
253 }
254
255 private Double bid_variance(Bid bid, int n_diff) {
256 Double variance = 0.0;
257
258 for (String issue : bid.getIssues()) {
259 List<impUnit> currentIssueList = this.impMap.get(issue);
260 for (impUnit currentUnit : currentIssueList) {
261 int n = currentUnit.total_count + n_diff;
262 Double p = currentUnit.probability;
263
264 variance += issue_variance(n, p);
265 }
266 }
267
268 return variance;
269 }
270
271 private Double issue_variance(int n, Double p) {
272 if (n < 2) {
273 return 0.0;
274 }
275
276 Double variance = 0.0;
277 // E(x)
278 Double E1 = 0.0;
279 // E(x^2)
280 Double E2 = 0.0;
281
282 // init for k = 2
283 int n_choose_k = n * (n - 1) / 2;
284 Double pow_p_k = p * p;
285 Double pow_1_p_n_k = Math.pow(1 - p, n - 2);
286
287 for (int k = 2; k <= n; k++) {
288 Double log_k = Math.log(k);
289 Double val = n_choose_k * pow_p_k * pow_1_p_n_k * log_k;
290 E1 += val;
291 E2 += val * log_k;
292
293 // update
294 pow_p_k *= p;
295 pow_1_p_n_k /= 1 - p;
296 n_choose_k *= (n - k);
297 n_choose_k /= (k + 1);
298 }
299
300 // Var(x) = E(x^2) - (E(x)^2)
301 variance = E2 - E1 * E1;
302 return variance;
303 }
304
305 private boolean should_elicit(Bid b_star) {
306 double time = progress.get(System.currentTimeMillis());
307
308 double U_b_star = this.impMap.getImportance(b_star);
309
310 double U_RB = this.impMap.getImportance(this.reservation_bid);
311
312 double RB_sigma = Math.sqrt(bid_variance(this.reservation_bid));
313 // n -> n + N -2
314 int N = this.partial_order_bids_count;
315 double RB_sigma_new = Math.sqrt(bid_variance(this.reservation_bid, N - 2));
316
317 int RB_rank_abs = this.impMap.importanceToRankAbs(U_RB);
318 int rise = this.impMap.importanceToRankAbs(U_RB + RB_sigma) - RB_rank_abs;
319 int fall = RB_rank_abs - this.impMap.importanceToRankAbs(U_RB - RB_sigma);
320 int RB_sigma_rank_abs = (int) Math.round((rise + fall) / 2.0);
321
322 rise = this.impMap.importanceToRankAbs(U_RB + RB_sigma_new) - RB_rank_abs;
323 fall = RB_rank_abs - this.impMap.importanceToRankAbs(U_RB - RB_sigma_new);
324 int RB_sigma_new_rank_abs = (int) Math.round((rise + fall) / 2.0);
325
326 double U_OLB = this.find_OLB(); // minimum opp. imp map value(opp. bids history)
327 double OLB = this.impMap.importanceToRankAbs(U_OLB) / this.bid_space_size;
328 double ORB = 0.5; // prior
329
330 double OMLB_prior = ORB + (1.0 * RB_sigma_rank_abs / this.bid_space_size);
331 if (OLB < OMLB_prior) {
332 Bid bid_almost_worst = this.impMap.getBidInRank(1);
333 double bid_sigma = Math.sqrt(bid_variance(bid_almost_worst));
334 double U_bid = this.impMap.getImportance(bid_almost_worst);
335 int bid_sigma_rank_abs = this.impMap.importanceToRankAbs(U_bid + bid_sigma)
336 - this.impMap.importanceToRankAbs(U_bid);
337 double bid_sigma_rank = bid_sigma_rank_abs / this.bid_space_size;
338
339 double projection = (1 - OLB) * time;
340
341 OMLB_prior = Math.max(bid_sigma_rank, projection);
342 }
343
344 double alpha = time;
345 double OMLB = alpha * OLB + (1 - alpha) * OMLB_prior;
346 double seg_OMLB = 1 - OMLB;
347
348 double p_diff = 1.0 * (RB_sigma_new_rank_abs - RB_sigma_rank_abs) * seg_OMLB / this.bid_space_size;
349
350 return (this.elicitation_cost / (U_b_star - U_RB)) < p_diff;
351 }
352
353 private double find_OLB() {
354 double min_bid_imp = Double.POSITIVE_INFINITY;
355
356 for (Bid bid : this.oppBidsHistory) {
357 double bid_imp = this.opponentImpMap.getImportance(bid);
358
359 if (bid_imp < min_bid_imp) {
360 min_bid_imp = bid_imp;
361 }
362 }
363
364 return min_bid_imp;
365 }
366
367 private Bid getBidStar(double lower_imp, double upper_imp) {
368 List<Bid> optionalBids = this.getIntersectingBids(lower_imp, upper_imp);
369
370 if (optionalBids.isEmpty()) {
371 double RB_imp = this.impMap.getImportance(this.reservation_bid);
372 int RB_rank = this.impMap.importanceToRankAbs(RB_imp);
373 int best_rank = this.bid_space_size - 1;
374 int mid_bid_imp = Math.round((RB_rank + best_rank) / 2);
375 Bid bid = this.impMap.getBidInRank(mid_bid_imp);
376 return bid;
377 }
378
379 // return best bid from optional bids
380 Bid bid = this.impMap.getBestBid(optionalBids);
381 return bid;
382 }
383}
Note: See TracBrowser for help on using the repository browser.