source: src/main/java/parties/in4010/q12015/group13/USBNAT.java@ 148

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

#41 ROLL BACK of rev.126 . So this version is equal to rev. 125

File size: 10.7 KB
Line 
1package parties.in4010.q12015.group13;
2
3import java.util.ArrayList;
4import java.util.Collections;
5import java.util.Comparator;
6import java.util.HashMap;
7import java.util.Iterator;
8import java.util.LinkedList;
9import java.util.List;
10import java.util.Map.Entry;
11
12import genius.core.AgentID;
13import genius.core.Bid;
14import genius.core.actions.Accept;
15import genius.core.actions.Action;
16import genius.core.actions.Offer;
17import genius.core.issue.Issue;
18import genius.core.issue.Value;
19import genius.core.parties.AbstractNegotiationParty;
20import genius.core.parties.NegotiationInfo;
21
22/**
23 * Multipary negotiator which tries to find bids that the opponent would accept,
24 * but will still satisfy it's own utility requirements
25 *
26 */
27public class USBNAT extends AbstractNegotiationParty {
28
29 HashMap<Object, FrequencyOpponentModel> opponents = new HashMap();
30 HashMap<Object, ArrayList<Bid>> accepts = new HashMap();
31 HashMap<Object, LinkedList<Bid>> rejects = new HashMap();
32 Bid lastBid = null;
33 double n = 0.1; // n for the frequency model
34 ArrayList<Bid> allBids = null; // all possible bids (sorted on our utility)
35
36 private double absoluteMinimum = 1;
37 private final double tries = 10;// Sine periods
38 private final double momentum = 0.05;
39 private final double start = 0.6; // When we start negotiating
40 private final int rejectsSize = 10;
41
42 private int rounds = 0; // current round
43 private boolean even = false; // used for giving max bids per 2 rounds
44
45 private final int panic = 5; // How many rounds left till we start to panic
46
47 @Override
48 public void init(NegotiationInfo info) {
49 super.init(info);
50
51 absoluteMinimum = Math.max(0.05, utilitySpace.getReservationValueUndiscounted());
52
53 allBids = generateAllBids();
54 }
55
56 /**
57 * Utility function Combination of a line from 1 to absolute minimum and a
58 * sine
59 *
60 * @param t
61 * current time (from 0 to 1)
62 * @return The minimum utility we should go for at this time (ignoring other
63 * agents)
64 */
65 private double getMinUtility(double t) {
66 double sin = Math.sin(tries * 2 * Math.PI * t + 1.5 * Math.PI);
67 double half = (1 - absoluteMinimum) / 2 + absoluteMinimum;
68 double dist = 1 - half;
69 return 0.7 * (1 - (1 - absoluteMinimum) * t) + 0.3 * (half + dist * sin);
70 }
71
72 /**
73 * @return For each opponent, the minimum utility we expect he would accept
74 */
75 private HashMap<Object, Double> getMinUtils() {
76 HashMap<Object, Double> ret = new HashMap(accepts.size());
77
78 for (Entry<Object, ArrayList<Bid>> entry : accepts.entrySet()) {
79 ArrayList<Bid> acc = entry.getValue();
80 FrequencyOpponentModel model = opponents.get(entry.getKey());
81 double min = 1;
82
83 for (Bid b : acc) {
84 double util = model.estimateUtility(b);
85
86 if (util < min) {
87 min = util;
88 }
89 }
90
91 double maxRejected = 0;
92
93 for (Bid rejected : rejects.get(entry.getKey())) {
94 double util = model.estimateUtility(rejected);
95
96 if (util > maxRejected) {
97 maxRejected = util;
98 }
99 }
100
101 ret.put(entry.getKey(), Math.max(min, maxRejected + momentum));
102 }
103
104 return ret;
105 }
106
107 /**
108 *
109 * @param b
110 * a bid
111 * @param minUtils
112 * a hashmap generated by getMinUtils
113 * @return true iff we expect every other agent would accept this bid
114 */
115 private boolean isAcceptable(Bid b, HashMap<Object, Double> minUtils) {
116 for (Entry<Object, Double> entry : minUtils.entrySet()) {
117 if (opponents.get(entry.getKey()).estimateUtility(b) < entry.getValue()) {
118 return false;
119 }
120 }
121
122 return true;
123 }
124
125 /**
126 * Generates the Best Acceptable Bid
127 *
128 * @param minUtils
129 * generated by getMinUtils
130 * @param myMin
131 * own minimum utility
132 * @return The bid that maximizes our utility, but still would get accepted
133 * by the other agents and has an utility (for us) of more than
134 * myMin. Null if this bid does not exist.
135 */
136 private Bid generateBAB(HashMap<Object, Double> minUtils, double myMin) {
137 Iterator<Bid> it = allBids.iterator();
138
139 while (it.hasNext()) {
140 Bid b = it.next();
141
142 if (!rejected(b)) {
143 if (myMin > getUtility(b)) {
144 return null;
145 }
146
147 if (isAcceptable(b, minUtils)) {
148 return b;
149 }
150 }
151 }
152
153 return null;
154 }
155
156 // Max Bid over Minimum
157 /**
158 * Generated the Maximum Bid over Minimum
159 *
160 * @param minUtility
161 * our minimum utility
162 * @return A bid that maximizes the (minimum) utility of the other agents
163 * but still statisfies out minimum utility
164 */
165 private Bid generateMBM(double minUtility) {
166 double max = 0;
167 Bid bestBid = allBids.get(0);
168
169 for (Bid b : allBids) {
170 if (getUtility(b) >= minUtility && !rejected(b)) {
171 double min = 1;
172
173 for (FrequencyOpponentModel model : opponents.values()) {
174 double util = model.estimateUtility(b);
175
176 if (util < min) {
177 min = util;
178 }
179 }
180
181 if (bestBid == null || max < min) {
182 max = min;
183 bestBid = b;
184 }
185 }
186 }
187
188 return bestBid;
189 }
190
191 /**
192 * Generate a bid using the info about our opponents
193 *
194 * @return the bid
195 */
196 private Bid generateBidJ() {
197 double time = getTimeLine().getTime();
198
199 if (time < start) {
200 return allBids.get(0);
201 }
202
203 HashMap<Object, Double> minUtils = getMinUtils();
204 double max = 0;
205
206 for (Double util : minUtils.values()) {
207 if (util > max) {
208 max = util;
209 }
210 }
211
212 double minUtility = Math.max(max - momentum, getMinUtility((time - start) / (1 - start)));
213
214 Bid b = generateBAB(minUtils, minUtility);
215
216 if (b != null) {
217 return b;
218 } else {
219 return generateMBM(minUtility);
220 }
221 }
222
223 /**
224 * Find maximum utility Nash Equilibrium
225 *
226 * @return nash bid
227 */
228 public Bid getNash() {
229 double nash = -1;
230 Bid ret = null;
231 for (Bid option : allBids) {
232 double nashv = getUtility(option);
233 for (Entry<Object, FrequencyOpponentModel> entry : opponents.entrySet()) {
234 nashv = nashv * entry.getValue().estimateUtility(option);
235 }
236 if (nashv > nash) {
237 nash = nashv;
238 ret = option;
239 }
240
241 }
242 return ret;
243 }
244
245 /**
246 * @return maximum utility bid that everyone else has already accepted
247 */
248 private Bid findMaxAccepted() {
249 double max = 0;
250 Bid ret = null;
251
252 for (Bid b : allBids) {
253 if (!rejected(b)) {
254 double util = getUtility(b);
255
256 if (util > max) {
257 max = util;
258 ret = b;
259 }
260 }
261 }
262
263 return ret;
264 }
265
266 /**
267 * @return our "panic" bid
268 */
269 private Bid findPanicBid() {
270 Bid max = findMaxAccepted();
271 Bid nash = getNash();
272
273 if (max == null || getUtility(nash) >= getUtility(max)) {
274 max = nash;
275 }
276
277 return max;
278 }
279
280 private ArrayList<Bid> generateAllBids() {
281 List<Issue> issues = utilitySpace.getDomain().getIssues();
282
283 ArrayList<Bid> ret = new ArrayList();
284
285 for (HashMap<Integer, Value> values : getAllBids(issues, 0)) {
286 try {
287 Bid bid = new Bid(utilitySpace.getDomain(), values);
288 ret.add(bid);
289 } catch (Exception ex) {
290 System.err.println("Could not create bid");
291 System.err.println(ex.getMessage());
292 }
293 }
294
295 Collections.sort(ret, new Comparator<Bid>() {
296 @Override
297 public int compare(Bid a, Bid b) {
298 if (getUtility(b) > getUtility(a)) {
299 return 1;
300 } else if (getUtility(b) == getUtility(a)) {
301 return 0;
302 } else {
303 return -1;
304 }
305 }
306
307 });
308
309 return ret;
310 }
311
312 private static ArrayList<HashMap<Integer, Value>> getAllBids(List<Issue> issues, int from) {
313 Issue issue = issues.get(from);
314
315 ArrayList<HashMap<Integer, Value>> bids;
316
317 if (from == issues.size() - 1) {
318 bids = new ArrayList();
319 bids.add(new HashMap());
320 } else {
321 bids = getAllBids(issues, from + 1);
322 }
323
324 ArrayList<Value> values = Util.getValues(issue);
325
326 ArrayList<HashMap<Integer, Value>> ret = new ArrayList();
327
328 for (Value v : values) {
329 for (HashMap<Integer, Value> bid : bids) {
330 HashMap<Integer, Value> newBid = new HashMap(bid);
331 newBid.put(issue.getNumber(), v);
332 ret.add(newBid);
333 }
334 }
335
336 return ret;
337 }
338
339 @Override
340 public Action chooseAction(List<Class<? extends Action>> list) {
341 try {
342 rounds++;
343
344 // Panic Mode (try to ignore very long first rounds by checking if
345 // we are already after start)
346 double roundsLeft = Util.estimatedRoundsLeft(getTimeLine(), rounds);
347 if (getTimeLine().getTime() >= start && roundsLeft <= panic) {
348 if (roundsLeft <= 2 && getUtility(lastBid) > absoluteMinimum) {
349 return new Accept(getPartyId(), lastBid);
350 } else {
351 Bid b = findPanicBid();
352 if (getUtility(b) <= getUtility(lastBid) && getUtility(lastBid) > absoluteMinimum) {
353 return new Accept(getPartyId(), lastBid);
354 } else if (getUtility(b) > absoluteMinimum) {
355 return new Offer(getPartyId(), b);
356 }
357 }
358 }
359
360 // Normal mode
361 even = !even;
362 Bid b = generateBidJ();
363 if (getUtility(b) > getUtility(lastBid)) {
364 b = even ? b : allBids.get(0);
365 lastBid = b;
366 return new Offer(getPartyId(), b);
367 } else {
368 return new Accept(getPartyId(), lastBid);
369 }
370 } catch (Exception ex) {
371 System.err.println("Exception in chooseAction: " + ex.getMessage());
372 return new Accept(getPartyId(), lastBid);
373 }
374 }
375
376 @Override
377 public void receiveMessage(AgentID sender, Action action) {
378 try {
379 super.receiveMessage(sender, action);
380
381 if (sender == null) {
382 return;
383 }
384
385 if (!opponents.containsKey(sender)) {
386 opponents.put(sender, new BetterFOM(getUtilitySpace().getDomain(), n));
387 accepts.put(sender, new ArrayList<Bid>());
388 rejects.put(sender, new LinkedList<Bid>());
389 }
390
391 if (action instanceof Offer) {
392 if (lastBid != null) {
393 addReject(sender, lastBid);
394 }
395 lastBid = ((Offer) action).getBid();
396 FrequencyOpponentModel OM = opponents.get(sender);
397 OM.addBid(lastBid);
398
399 accepts.get(sender).add(lastBid);
400 } else if (action instanceof Accept) {
401 accepts.get(sender).add(lastBid);
402 }
403
404 } catch (Exception ex) {
405 System.err.println("Exception in receiveMessage: " + ex.getMessage());
406 }
407 }
408
409 public void addReject(Object sender, Bid b) {
410 // Don't fill rejects with our maximum bid
411 if (b.equals(allBids.get(0))) {
412 return;
413 }
414
415 LinkedList<Bid> list = rejects.get(sender);
416
417 list.addLast(b);
418
419 if (list.size() > rejectsSize) {
420 list.removeFirst();
421 }
422 }
423
424 public boolean rejected(Bid b) {
425 boolean rejected = false;
426 Iterator<LinkedList<Bid>> it = rejects.values().iterator();
427
428 while (it.hasNext() && !rejected) {
429 rejected = it.next().contains(b);
430 }
431
432 return rejected;
433 }
434
435 @Override
436 public String getDescription() {
437 return "in4010.q12015.group13 USBNAT";
438 }
439}
Note: See TracBrowser for help on using the repository browser.