source: src/main/java/agents/ai2014/group5/BiddingStrategy.java@ 127

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

Initial import : Genius 9.0.0
File size: 9.0 KB
Line 
1package agents.ai2014.group5;
2
3import java.util.ArrayList;
4import java.util.Collections;
5import java.util.HashMap;
6import java.util.List;
7import java.util.Map;
8import java.util.Random;
9
10import genius.core.Bid;
11import genius.core.Domain;
12import genius.core.issue.Value;
13import genius.core.issue.ValueDiscrete;
14
15/**
16 * Implementation of the bidding strategy. 1) In the first round the agent will
17 * offer a bid with max utility for itself. 2) In the subsequent rounds, until a
18 * specific time has elapsed, the agent will bid selfishly and only concede a
19 * tiny bit. This is because the opponent models are unreliable in the
20 * beginning. 3) Afterwards, it will use a tit-for-tat strategy to hopefully
21 * reach a Nash point, while increasingly concede utility in the later rounds.
22 * To achieve this it will interact with the opponent models to compare the
23 * estimated utilities of the opponents when deciding on bids.
24 */
25public class BiddingStrategy {
26 // The minimum utility for our agent that we will consider when computing
27 // bids
28 private static final double MIN_UTIL = 0.3;
29
30 private Random randGen;
31
32 // Domain of agent, all bids in this domain, and best bids in domain
33 private Domain domain;
34 private List<Bid> allBids;
35 private List<Bid> maxBids;
36
37 // The agent and fields from the agent
38 private Group5 agent;
39 private Map<String, OpponentModel> opponentModels;
40 private List<Map<String, Integer>> values;
41 private List<Map<Integer, String>> valuesRev;
42
43 // Currently calculated Nash point
44 private Bid curNash;
45
46 // The last bid made by us
47 public Bid lastBid;
48
49 // The last bid and most recent bid received from an opponent
50 public Bid prevOpponentBid, currentOpponentBid;
51
52 // The current round
53 public int round = 0;
54
55 // The deadline (can be null!)
56 public Integer deadline;
57
58 public BiddingStrategy(Domain domain,
59 Map<String, OpponentModel> opponentModels,
60 List<Map<String, Integer>> values,
61 List<Map<Integer, String>> valuesRev, Group5 agent) {
62 this.domain = domain;
63 this.opponentModels = opponentModels;
64 this.values = values;
65 this.valuesRev = valuesRev;
66 this.agent = agent;
67 this.randGen = new Random();
68 this.maxBids = new ArrayList<Bid>();
69
70 createAllBids();
71 }
72
73 /**
74 * Computes all bids in the domain that have an utility of at least
75 * {@link #MIN_UTIL}.
76 */
77 private void createAllBids() {
78 // Count bids
79 List<Integer> numValuesEach = new ArrayList<Integer>();
80 int numBids = 1;
81 for (int i = 0; i < values.size(); i++) {
82 int x = values.get(i).size();
83 numValuesEach.add(x);
84 numBids *= x;
85 }
86
87 // Compute bids represented as lists of value indices
88 List<List<Integer>> bidIndices = new ArrayList<List<Integer>>(
89 Collections.nCopies(numBids, (List<Integer>) null));
90 for (int i = 0; i < bidIndices.size(); i++) {
91 bidIndices.set(i, new ArrayList<Integer>(values.size()));
92 }
93 int bound = numBids;
94 for (int i : numValuesEach) {
95 bound /= i;
96 int count = 0;
97 int j = 0;
98 for (List<Integer> k : bidIndices) {
99 k.add(j);
100 count++;
101 if (count == bound) {
102 j++;
103 count = 0;
104 }
105 if (j == i) {
106 j = 0;
107 }
108 }
109 }
110
111 // Create actual bids from value indices lists
112 allBids = new ArrayList<Bid>();
113 for (int i = 0; i < bidIndices.size(); i++) {
114 Bid bid = createBid(bidIndices.get(i));
115 if (agent.getUtility(bid) >= MIN_UTIL) {
116 allBids.add(bid);
117 }
118 }
119 }
120
121 private Bid createBid(List<Integer> valueIndices) {
122 HashMap<Integer, Value> v = new HashMap<Integer, Value>();
123 for (int i = 0; i < valuesRev.size(); i++) {
124 String vname = valuesRev.get(i).get(valueIndices.get(i));
125 v.put(i + 1, new ValueDiscrete(vname));
126 }
127 try {
128 return new Bid(domain, v);
129 } catch (Exception e) {
130 agent.println("Error: cannot create bid " + v);
131 }
132 return null;
133 }
134
135 /**
136 * Creates a bid according to the bidding strategy See the documentation of
137 * this class above for a description of the bidding strategy
138 */
139 public Bid generateBid() {
140 // New round, new Nash point
141 round++;
142 updateNashProduct();
143
144 // 1) Offer the best bid for us in the first round
145 if (lastBid == null || currentOpponentBid == null) {
146 return generateMaxBid();
147 }
148
149 // 2.1) Allow to concede a bit more each round
150 int cutoff = deadline == null ? 10 : Math.max(deadline / 2, 10);
151 double maxConcession = 0.01;
152 if (deadline != null) {
153 // double c = 2.25;
154 double c = 3.5;
155 maxConcession = Math.exp((round - cutoff) / (deadline / c))
156 / (1.5 * Math.exp(c));
157 agent.println("Max concession: " + maxConcession);
158 }
159
160 // 2.2) Do not use the opponent models in the beginning as they are
161 // unreliable
162 if (round <= cutoff) {
163 Bid b = selfishStep(maxConcession);
164 if (b == null) {
165 agent.println("Warning: could not make a selfish offer");
166 return null;
167 }
168 agent.println("Made selfish move: " + agent.getUtility(b) + ", "
169 + b);
170 return b;
171 }
172
173 // 3.1) Estimate Nash point
174 if (curNash == null) {
175 // Huh
176 Bid b = selfishStep(maxConcession);
177 agent.println("No Nash bid!?");
178 return b;
179 }
180
181 // 3.2) Find concession towards Nash point
182 double nashBidUtil = agent.getUtility(curNash);
183 double prevOpponentBidUtil = agent.getUtility(prevOpponentBid);
184 double curOpponentBidUtil = agent.getUtility(currentOpponentBid);
185 double opponentConcession = (prevOpponentBidUtil - curOpponentBidUtil)
186 / Math.abs(nashBidUtil - prevOpponentBidUtil);
187
188 // 3.3) Mirror bid in our utility relative to Nash utility
189 double lastBidUtil = agent.getUtility(lastBid);
190 double concession = opponentConcession
191 * Math.abs(nashBidUtil - lastBidUtil);
192 concession = Math.min(maxConcession, concession);
193 if (Double.isNaN(opponentConcession) || opponentConcession < 0.001) {
194 // But if the opponent did not succeed in increasing our utility
195 // then do not concede too much of our utility when offering the
196 // next bid
197 concession = 0.01;
198 }
199
200 // 3.4) Make a nice move
201 Bid niceMove = niceStepClosestsNash(lastBid, agent.getUtility(lastBid),
202 concession);
203 if (niceMove == null || niceMove.equals(lastBid)) {
204 agent.println("Warning: could not make a new nice move (making selfish move instead): "
205 + niceMove);
206 return selfishStep(maxConcession);
207 }
208 agent.println("Made nice move: " + agent.getUtility(niceMove) + ", "
209 + niceMove);
210 return niceMove;
211 }
212
213 /**
214 * Product of the (estimated) utilities of all agents, including us
215 */
216 public double utilityProduct(Bid bid) {
217 double p = agent.getUtility(bid);
218 for (OpponentModel m : opponentModels.values()) {
219 p *= m.expectedUtilityOf(bid);
220 }
221 return p;
222 }
223
224 /**
225 * Finds a bid with the maximal utility product Should be called at every
226 * round
227 */
228 private void updateNashProduct() {
229 double max = Double.MIN_VALUE;
230 for (Bid bid : allBids) {
231 double u = utilityProduct(bid);
232 if (u > max) {
233 max = u;
234 curNash = bid;
235 }
236 }
237 }
238
239 /**
240 * A bid that is the best possible for us
241 */
242 private Bid generateMaxBid() {
243 if (maxBids.size() == 0) {
244 double max = Double.MIN_VALUE;
245 for (Bid bid : allBids) {
246 max = Math.max(agent.getUtility(bid), max);
247 }
248 for (Bid bid : allBids) {
249 if (Math.abs(agent.getUtility(bid) - max) < 0.001) {
250 maxBids.add(bid);
251 }
252 }
253 agent.println("Found " + maxBids.size() + " max bids");
254 }
255 if (maxBids.size() > 0) {
256 int randomIndex = randGen.nextInt(maxBids.size());
257 return maxBids.get(randomIndex);
258 }
259 return null;
260 }
261
262 /**
263 * Distance to Nash product projected to our utility
264 */
265 private double distanceToNash(Bid bid) {
266 return Math.abs(utilityProduct(curNash) - utilityProduct(bid));
267 }
268
269 /**
270 * Finds the bid closest to the estimated Nash product with an utility
271 * approximately equal to <code>curUtil</code> but with a difference of up
272 * to <code>concession</code>.
273 */
274 private Bid niceStepClosestsNash(Bid lastBid, double curUtil,
275 double concession) {
276 if (Double.isNaN(concession)) {
277 agent.println("Warning: concession is NaN");
278 concession = 0.001;
279 }
280 double minDist = Double.MAX_VALUE;
281 Bid niceBid = null;
282 for (Bid bid : allBids) {
283 if (lastBid != null && lastBid.equals(bid)) {
284 continue;
285 }
286 double util = agent.getUtility(bid);
287 if (Math.abs(curUtil - util) <= concession) {
288 double dist = distanceToNash(bid);
289 if (dist < minDist) {
290 minDist = dist;
291 niceBid = bid;
292 }
293 }
294 }
295 return niceBid;
296 }
297
298 /**
299 * Finds a good bid that does not consider the opponent's preferences
300 */
301 private Bid selfishStep(double concession) {
302 if (Double.isNaN(concession)) {
303 agent.println("Warning: concession is NaN");
304 concession = 0.05;
305 }
306 List<Bid> bids = new ArrayList<Bid>();
307 for (Bid bid : allBids) {
308 double util = agent.getUtility(bid);
309 if (Math.abs(1.0 - util) <= concession) {
310 bids.add(bid);
311 }
312 }
313 if (bids.size() == 0) {
314 return null;
315 }
316 int randomIndex = randGen.nextInt(bids.size());
317 return bids.get(randomIndex);
318 }
319
320 public void updateOffer(Bid bid) {
321 prevOpponentBid = currentOpponentBid;
322 currentOpponentBid = bid;
323 }
324
325 public void setDeadline(Integer newDeadline) {
326 if (newDeadline != null && newDeadline != deadline) {
327 deadline = newDeadline;
328 }
329 }
330}
Note: See TracBrowser for help on using the repository browser.