source: src/main/java/agents/anac/y2014/Gangster/Gangster.java@ 316

Last change on this file since 316 was 1, checked in by Wouter Pasman, 6 years ago

Initial import : Genius 9.0.0
File size: 10.5 KB
Line 
1package agents.anac.y2014.Gangster;
2
3import java.util.ArrayList;
4import java.util.List;
5
6import genius.core.Agent;
7import genius.core.Bid;
8import genius.core.actions.Accept;
9import genius.core.actions.Action;
10import genius.core.actions.Offer;
11import genius.core.bidding.BidDetails;
12import genius.core.issue.Issue;
13import genius.core.utility.NonlinearUtilitySpace;
14
15//
16//
17//
18// @author Dave de Jonge
19//
20//
21public class Gangster extends Agent {
22
23 double RESERVATION_VALUE = 0.0;
24 int NUM_ISSUES = -1;
25 double DISCOUNT_FACTOR;
26
27 // PARAMETERS
28 // concession
29 int MINIMAL_MAX_DISTANCE = 5;
30 int INITIAL_MAX_DISTANCE;
31 private int DECREASE_THRESHOLD = 4; // if local search finds more than this
32 // amount of altruistic bids, decrease
33 // the max distance.
34 int DECREASE_AMOUNT = 1; // the amount by which the max distance is
35 // decreased each time this happens
36 double DEADLINE_MARGIN = 0.01; // we aim to reach u_star at t_star, which
37 // equals DISCOUNT_FACTOR - DEADLINE_MARGIN
38 double INITIAL_TARGET_UTILITY = 0.995;
39
40 // regression
41 int NUM_INTERVALS = 100; // we take one sample per interval.
42 double WINDOW_SIZE = 0.1; // we look only at a certain number of intervals
43 // in the past. e.g. if num intervals is 100 and
44 // window size is 0.1, then the window consists
45 // of 10 intervals.
46 int MiN_NUM_SAMPLES = 5; // the minimum numbers of samples we need before
47 // doing regression.
48
49 // storage
50 final int MAX_CAPACITY = 2 * 1000; // maximum size to avoid decrease in
51 // performance.
52 final int MAX_SIZE_AFTER_CLEANING = 2 * 250; // 2 times the minimum size we
53 // need to maintain good
54 // results.
55 final int EXPECTED_NUM_PROPOSALS = 180 * 100; // the number of proposals we
56 // expect to receive during
57 // the entire negotiation.
58
59 // genetic algorithm
60 final int INIT_GENERATION_SIZE = 120; // the size of the initial generation.
61 final int NUM_SURVIVORS = 10; // the number of samples that survive from
62 // each generation.
63 int MAX_NUM_GENERATIONS = 10; // the maximum number of generations befor the
64 // gen alg returns.
65 int MIN_DISTANCE = 1; // the minimum distance between any pair of elements
66 // in a survivor set.
67
68 String name = "Gangster";
69 String version = "1.0";
70
71 List<Issue> issues;
72 Bid latestReceivedBid;
73 double latestReceivedUtility;
74 int numProposalsReceived = 0;
75
76 GenAlg genAlg;
77 BidStorage bidStorage;
78
79 ArrayList<BidDetails> globalSearchResults = null;
80 int nextSelfishBidToPropose = 0;
81 int maxDistance;
82
83 private int numGoodResultsFromLocalSearch;
84 private ExtendedBidDetails lastProposedByUs;
85
86 /**
87 * init is called when a next session starts with the same opponent.
88 */
89 @Override
90 public void init() {
91
92 try {
93
94 // 0. Make sure it works in linear cases ;)
95 if (!(utilitySpace instanceof NonlinearUtilitySpace)) {
96 return;
97 }
98
99 issues = utilitySpace.getDomain().getIssues();
100
101 RESERVATION_VALUE = utilitySpace.getReservationValueUndiscounted();
102 NUM_ISSUES = issues.size();
103 DISCOUNT_FACTOR = utilitySpace.getDiscountFactor();
104
105 // set the initial maxDistance;
106 maxDistance = (int) Math.round(1.5 * NUM_ISSUES);
107 numGoodResultsFromLocalSearch = 0;
108
109 bidStorage = new BidStorage(MAX_CAPACITY, MAX_SIZE_AFTER_CLEANING,
110 EXPECTED_NUM_PROPOSALS);
111
112 if (utilitySpace instanceof NonlinearUtilitySpace) {
113 genAlg = new GenAlg((NonlinearUtilitySpace) utilitySpace,
114 INIT_GENERATION_SIZE, NUM_SURVIVORS,
115 MAX_NUM_GENERATIONS, MIN_DISTANCE);
116
117 }
118 } catch (Exception e) {
119
120 }
121 }
122
123 @Override
124 public void ReceiveMessage(Action opponentAction) {
125
126 try {
127
128 // update history
129 if (opponentAction instanceof Offer) { // NOTE: an offer is a bid,
130 // together with the id of
131 // the agent that made the
132 // offer.
133
134 double time = timeline.getTime();
135
136 // store the bid and its utility, this is necessary in case we
137 // want to accept it.
138 latestReceivedBid = ((Offer) opponentAction).getBid();
139 latestReceivedUtility = utilitySpace
140 .getUtility(latestReceivedBid);
141
142 // 0. Make sure it works in linear cases ;)
143 if (!(utilitySpace instanceof NonlinearUtilitySpace)) {
144 return;
145 }
146
147 numProposalsReceived++;
148
149 if (latestReceivedUtility > RESERVATION_VALUE) {
150 BidDetails bd = new BidDetails(latestReceivedBid,
151 latestReceivedUtility, time);
152 bidStorage.addOpponentBid(bd);
153 }
154
155 }
156
157 } catch (Exception e) {
158
159 latestReceivedUtility = 0;
160 }
161
162 }
163
164 @Override
165 public Action chooseAction() {
166
167 try {
168
169 // 0. Make sure it works in linear cases ;)
170 if (!(utilitySpace instanceof NonlinearUtilitySpace)) {
171
172 if (latestReceivedUtility > 0.8) {
173 return new Accept(getAgentID(), latestReceivedBid);
174 }
175
176 Bid returnBid = utilitySpace.getDomain().getRandomBid(null);
177 return new Offer(getAgentID(), returnBid);
178 }
179
180 // 1. Get current time (value between 0 and 1, where 1 represents
181 // the deadline).
182 double time = timeline.getTime();
183
184 // 2. Calculate the minimum utility we are going to demand this
185 // turn.
186 // get the best bid proposed so far by opponent, in the past time n
187 // time units.
188 double ourTargetUtility = getTargetUtility(time,
189 DISCOUNT_FACTOR - DEADLINE_MARGIN);
190
191 bidStorage.setTargetUtility(ourTargetUtility);
192
193 if (latestReceivedUtility >= ourTargetUtility) {
194
195 // ACCEPT BID
196 return new Accept(getAgentID(), latestReceivedBid);
197
198 }
199
200 // 3. Get the maximum distance to the latest bid from the opponent.
201 maxDistance = getMaxDistance(time, maxDistance,
202 numGoodResultsFromLocalSearch);
203
204 // 4. Do global search. Repeat it until we have found something
205 // selfish enough.
206 while (!bidStorage.weHaveSelfishEnoughBids()) {
207
208 ArrayList<BidDetails> globalSearchResults = genAlg
209 .globalSearch();
210
211 bidStorage.addAll(globalSearchResults, false);
212
213 // recalculate target utility.
214
215 ourTargetUtility = getTargetUtility(timeline.getTime(),
216 DISCOUNT_FACTOR - DEADLINE_MARGIN);
217
218 bidStorage.setTargetUtility(ourTargetUtility);
219
220 }
221
222 // 5. Do local search.
223 // initiate a genetic algorithm that searches within the allowed
224 // space.
225 // the returned values are always altruistic enough so we don't need
226 // to repeat this.
227 if (latestReceivedBid != null) {
228
229 ArrayList<BidDetails> localSearchResults = genAlg
230 .localSearch(latestReceivedBid, maxDistance);
231
232 // count how many bids we have found that are both selfish
233 // enough and altruistic enough. Note that we already know they
234 // must be altruistic enough, so
235 // We only need to test wether they are selfish enough.
236 numGoodResultsFromLocalSearch = 0;
237 for (BidDetails bd : localSearchResults) {
238 if (bd.getMyUndiscountedUtil() > 0.9 * ourTargetUtility) {
239 numGoodResultsFromLocalSearch++;
240 }
241 }
242
243 bidStorage.addAll(localSearchResults, true);
244 }
245
246 // 6. Get the best bid of all possible bids in storage
247 ExtendedBidDetails nextBid = bidStorage.getNext(ourTargetUtility,
248 maxDistance);
249
250 if (nextBid == null) {
251 proposeOrAccept(time, lastProposedByUs, ourTargetUtility);
252 }
253
254 // 7. Propose it, or accept an earlier proposal from the opponent
255 return proposeOrAccept(time, nextBid, ourTargetUtility);
256
257 } catch (Exception e) {
258
259 if (lastProposedByUs == null || lastProposedByUs.bidDetails == null
260 || lastProposedByUs.bidDetails.getBid() == null) {
261 return new Offer(getAgentID(),
262 utilitySpace.getDomain().getRandomBid(null));
263 }
264
265 return new Offer(getAgentID(),
266 lastProposedByUs.bidDetails.getBid());
267
268 }
269
270 }
271
272 private int getMaxDistance(double time, int previousValue,
273 int numSelfishAndAltruisticBids) {
274
275 if (numSelfishAndAltruisticBids > DECREASE_THRESHOLD
276 && previousValue > MINIMAL_MAX_DISTANCE) {
277 return previousValue - DECREASE_AMOUNT;
278 } else {
279 return previousValue;
280 }
281
282 }
283
284 /**
285 * Compares my bid with the latest received proposal from the opponent and
286 * converts the best one of the two in an Action, which is returned.
287 *
288 * @param myExtendedBid
289 * @return
290 * @throws Exception
291 */
292 Action proposeOrAccept(double time, ExtendedBidDetails myExtendedBid,
293 double ourTargetUtility) throws Exception {
294
295 BidDetails earlierProposal = bidStorage.getReproposableBid(time,
296 ourTargetUtility, (1 - time) + 0.01);
297
298 if (earlierProposal != null) {
299
300 // repropose the bid
301 bidStorage.addBidProposedByUs(earlierProposal.getBid());
302 return new Offer(getAgentID(), earlierProposal.getBid());
303
304 } else {
305
306 this.lastProposedByUs = myExtendedBid;
307
308 bidStorage.addBidProposedByUs(myExtendedBid.bidDetails.getBid());
309
310 // remove the bid from the list of candidates to propose. This way
311 // we keep the storage clean, cause we know we will never propose it
312 // again anyway.
313 bidStorage.removeBid(myExtendedBid);
314
315 return new Offer(getAgentID(), myExtendedBid.bidDetails.getBid());
316 }
317
318 }
319
320 double previousCalculationTime = 0; // the time at which we did the previous
321 // calculation of the target utility.
322 double previousTarget = INITIAL_TARGET_UTILITY; // the previous value of the
323 // target utility
324
325 double getTargetUtility(double time, double t_star) {
326
327 double u_star = bidStorage.getBestOfferedUtility(time,
328 (1 - time) + 0.01);
329
330 if (time < t_star) {
331 return getTargetUtility1(time, t_star, u_star);
332 } else {
333 return u_star;
334 }
335
336 }
337
338 double getTargetUtility1(double time, double t_star, double u_star) {
339
340 double high = 0.5 * (1 + u_star); // half-way between bestProposedSoFar
341 // and 1.
342 // double low = 0.5* (u_star + RESERVATION_VALUE); //half-way between
343 // bestProposedSoFar and rv.
344 double low = u_star;
345
346 double finalTargetUtility = (high - low)
347 * Math.pow((t_star - time), 0.3) + low;
348
349 // calculate which part of the interval has passed since last
350 // calculation
351 double ratio = (t_star - time) / (t_star - previousCalculationTime);
352
353 // target utility decreases linearly from the previous value to the
354 // final value
355 double currentTargetUtility = ratio
356 * (previousTarget - finalTargetUtility) + finalTargetUtility;
357
358 // System.out.println("Current target utility: " +
359 // currentTargetUtility);
360
361 // reset these two values for the next calculation.
362 previousCalculationTime = time;
363 previousTarget = currentTargetUtility;
364
365 return currentTargetUtility;
366 }
367
368 @Override
369 public String getName() {
370
371 return name;
372 }
373
374 @Override
375 public String getVersion() {
376 return version;
377 }
378
379 @Override
380 public String getDescription() {
381 return "ANAC2014 compatible with non-linear utility spaces";
382 }
383
384}
Note: See TracBrowser for help on using the repository browser.