source: src/main/java/parties/in4010/q12015/group5/Group5.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: 9.1 KB
Line 
1package parties.in4010.q12015.group5;
2
3import java.util.List;
4
5import java.util.ArrayList;
6import java.util.HashMap;
7import java.util.Map;
8import java.util.Set;
9
10import genius.core.AgentID;
11import genius.core.Bid;
12import genius.core.actions.Accept;
13import genius.core.actions.Action;
14import genius.core.actions.Offer;
15import genius.core.bidding.BidDetails;
16import genius.core.boaframework.SortedOutcomeSpace;
17import genius.core.parties.AbstractNegotiationParty;
18import genius.core.parties.NegotiationInfo;
19import genius.core.utility.AdditiveUtilitySpace;
20
21/**
22 * NegotiationParty for Group 5. This agent moves closer to the estimated Nash
23 * point as time progresses. For an extended explanation of what our agent does,
24 * see our report.
25 */
26public class Group5 extends AbstractNegotiationParty {
27
28 /**
29 * All possible bids from the SortedOutcomeSpace.
30 */
31 private List<BidDetails> allOutcomes;
32
33 /**
34 * The last bid that has been made by any agent (including us).
35 */
36 private Bid lastBid;
37
38 /**
39 * The models that we build for every opponent.
40 */
41 private Map<Object, OpponentModel> opponentModels;
42
43 /**
44 * The SortedOutcomeSpace of our UtilitySpace.
45 */
46 private SortedOutcomeSpace sos;
47
48 /**
49 * The threshold above which we will always accept.
50 */
51 private double utilityThreshold;
52
53 /*
54 * (non-Javadoc)
55 *
56 * @see negotiator.parties.AbstractNegotiationParty#init(negotiator.utility.
57 * UtilitySpace, negotiator.Deadline, negotiator.session.TimeLineInfo, long,
58 * negotiator.AgentID)
59 */
60 @Override
61 public void init(NegotiationInfo info) {
62 super.init(info);
63 opponentModels = new HashMap<Object, OpponentModel>();
64 sos = new SortedOutcomeSpace(getUtilitySpace());
65 allOutcomes = sos.getAllOutcomes();
66
67 double minBid = sos.getMinBidPossible().getMyUndiscountedUtil();
68 utilityThreshold = 1 - (1 - minBid) * 0.1; // Get top 90%
69 }
70
71 /**
72 * All offers proposed by the other parties will be received as a message.
73 * You can use this information to your advantage, for example to predict
74 * their utility.
75 *
76 * @param sender
77 * The party that did the action.
78 * @param action
79 * The action that party did.
80 */
81 @Override
82 public void receiveMessage(AgentID sender, Action action) {
83 super.receiveMessage(sender, action);
84
85 try {
86 if (action instanceof Offer) {
87 lastBid = ((Offer) action).getBid();
88 updateModel(sender, lastBid);
89 } else if (action instanceof Accept) {
90 updateModel(sender, lastBid);
91 }
92 } catch (Exception e) {
93 e.printStackTrace();
94 }
95 }
96
97 /**
98 * Each round this method gets called and ask you to accept or offer. The
99 * first party in the first round is a bit different, it can only propose an
100 * offer.
101 *
102 * @param validActions
103 * Either a list containing both accept and offer or only offer.
104 * @return The chosen action.
105 */
106 @Override
107 public Action chooseAction(List<Class<? extends Action>> validActions) {
108 try {
109 Bid bid = generateBid();
110 if (acceptBid(bid))
111 return new Accept(getPartyId(), lastBid);
112 else {
113 lastBid = bid;
114 return new Offer(getPartyId(), new Bid(bid));
115 }
116 } catch (Exception e) {
117 e.printStackTrace();
118 // Accepting is always
119 // better than crashing
120 return new Accept(getPartyId(), lastBid);
121 }
122 }
123
124 /**
125 * Generates a new bid according to the bidding strategy. Finds a bid by
126 * looping through all bids and - Calculate the Nash score for the bid based
127 * on the opponent models. - Calculate own utility for the bid. - Take the
128 * weighted average of own utility and the Nash score. This weighted average
129 * starts at 100% own utility and moves to 100% theoretical Nash point. Of
130 * these the top 5 is chosen and from those the one with the highest utility
131 * is chosen.
132 *
133 * @return The preferred bid based on the chosen strategy.
134 * @throws Exception
135 */
136 private Bid generateBid() throws Exception {
137 Double time = timeline.getTime();
138 double ownFactor = 1 - (time * time); // 1 - x^2
139 double nashFactor = 1 - ownFactor;
140
141 // Get modeled utility spaces for opponents
142 Set<Object> opponents = opponentModels.keySet();
143 Map<Object, AdditiveUtilitySpace> opponentUtilSpaces = new HashMap<Object, AdditiveUtilitySpace>();
144 for (Object opponent : opponents) {
145 opponentUtilSpaces.put(opponent, opponentModels.get(opponent).getUtilitySpace());
146 }
147
148 // weightedAverages contains the top 5 weighted averages found
149 Map<BidDetails, Double> weightedAverages = new HashMap<BidDetails, Double>();
150 weightedAverages.put(null, 0.);
151 for (BidDetails bid : allOutcomes) {
152 // First find the minimum in order to know which one we should
153 // replace if we find a better one.
154 double min = Double.MAX_VALUE;
155 BidDetails minBid = null;
156 for (BidDetails mapBid : weightedAverages.keySet()) {
157 double mapAvg = weightedAverages.get(mapBid);
158 if (mapAvg <= min) {
159 min = mapAvg;
160 minBid = mapBid;
161 }
162 }
163
164 // If based on our utility alone we won't make it, break because:
165 // - Adding the opponents utilities to the nash will only decrease
166 // the value (because U <= 1)
167 // - The list is sorted in decreasing order so all next bids will be
168 // worse.
169 double ourUtil = bid.getMyUndiscountedUtil();
170 if (ownFactor * ourUtil + nashFactor * ourUtil < min)
171 break;
172
173 double nash = ourUtil;
174 for (Object opponent : opponents) {
175 AdditiveUtilitySpace opponentUtilSpace = opponentUtilSpaces.get(opponent);
176 nash *= opponentUtilSpace.getUtility(bid.getBid());
177 }
178
179 double weightedAverage = ownFactor * ourUtil + nashFactor * nash;
180 if (weightedAverage > min) {
181 if (weightedAverages.size() >= 5) {
182 weightedAverages.remove(minBid);
183 }
184
185 weightedAverages.put(bid, weightedAverage);
186 }
187 }
188
189 // Find the one that gives the highest utility of the top 5.
190 double max = 0;
191 BidDetails maxBid = null;
192 for (BidDetails mapBid : weightedAverages.keySet()) {
193 double mapUtil = mapBid.getMyUndiscountedUtil();
194 if (mapUtil > max) {
195 max = mapUtil;
196 maxBid = mapBid;
197 }
198 }
199
200 return maxBid.getBid();
201 }
202
203 // Accept when either:
204 // - It is above our minimum
205 // - It is better than we would bid
206 // - (late in the bidding), it is better than all the bids in the previous
207 // window
208 /**
209 * Decides whether to accept the last bid based on the bid that was
210 * generated by the bidding strategy. Acceptance strategy is as follows.
211 * Accept when either: - The bid is above our threshold This is a linear
212 * function from the top 100% of the space to the top 80% of the space - The
213 * bid is better than the bid generated by the strategy. - When 0.95 of the
214 * negotiation has passed, accept if we don't expect a better bid. This is
215 * the case if the bid is better than all the bids we have seen in the
216 * previous time window.
217 *
218 * @param bid
219 * The bid generated by the bidding strategy.
220 * @return Whether to accept the current bid.
221 * @throws Exception
222 */
223 private boolean acceptBid(Bid bid) throws Exception {
224 double time = timeline.getTime();
225 double minUtility = getUtilityThreshold(time / 0.5);
226 double lastUtility = (lastBid != null) ? utilitySpace.getUtility(lastBid) : 0;
227 double bidUtility = utilitySpace.getUtility(bid);
228 if (lastUtility >= minUtility || lastUtility >= bidUtility)
229 return true;
230
231 if (time >= 0.95) {
232 List<Bid> opponentBids = new ArrayList<Bid>();
233 for (Object opponent : opponentModels.keySet()) {
234 opponentBids.addAll(opponentModels.get(opponent).getBidHistory(1 - time));
235 }
236 double maxUtility = 0;
237 for (Bid oppBid : opponentBids) {
238 double utility = utilitySpace.getUtility(oppBid);
239 if (utility > maxUtility) {
240 maxUtility = utility;
241 }
242 }
243 if (bidUtility >= maxUtility)
244 return true;
245 }
246
247 return false;
248 }
249
250 /**
251 * Linear function from 1 to utilityThreshold, multiplied by the factor (to
252 * reach it sooner, for example)
253 *
254 * @param factor
255 * The factor by which to multiply
256 * @return The utilty above which we will always accept.
257 */
258 private double getUtilityThreshold(double factor) {
259 return 1 - (1 - utilityThreshold) * factor;
260 }
261
262 /**
263 * Updates the opponent model with the specified opponents new bid. If no
264 * model is yet present, one will be created and added to the list.
265 *
266 * @param opponent
267 * The opponent of which the model needs to be updated.
268 * @param newBid
269 * The new bid of the opponent
270 * @throws Exception
271 */
272 private void updateModel(AgentID opponent, Bid newBid) throws Exception {
273 OpponentModel opponentModel = opponentModels.get(opponent);
274 if (opponentModel == null) {
275 opponentModel = new OpponentModel(utilitySpace.getDomain(), newBid);
276 opponentModels.put(opponent, opponentModel);
277 } else {
278 opponentModel.updateModel(newBid);
279 }
280 }
281
282 /*
283 * (non-Javadoc)
284 *
285 * @see negotiator.parties.AbstractNegotiationParty#getDescription()
286 */
287 @Override
288 public String getDescription() {
289 return "I heard you like parties so we created a party to negotiate about your party";
290 }
291}
Note: See TracBrowser for help on using the repository browser.