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

Last change on this file since 1 was 1, checked in by wouter, 4 years ago

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