1 | package agents.anac.y2011.HardHeaded;
|
---|
2 |
|
---|
3 | import java.util.HashMap;
|
---|
4 | import java.util.LinkedList;
|
---|
5 | import java.util.Map.Entry;
|
---|
6 | import java.util.Random;
|
---|
7 | import java.util.TreeMap;
|
---|
8 |
|
---|
9 | import genius.core.Agent;
|
---|
10 | import genius.core.Bid;
|
---|
11 | import genius.core.Domain;
|
---|
12 | import genius.core.SupportedNegotiationSetting;
|
---|
13 | import genius.core.actions.Accept;
|
---|
14 | import genius.core.actions.Action;
|
---|
15 | import genius.core.actions.Offer;
|
---|
16 | import genius.core.issue.IssueDiscrete;
|
---|
17 | import genius.core.issue.Objective;
|
---|
18 | import genius.core.issue.ValueDiscrete;
|
---|
19 | import genius.core.utility.AdditiveUtilitySpace;
|
---|
20 | import genius.core.utility.Evaluator;
|
---|
21 | import genius.core.utility.EvaluatorDiscrete;
|
---|
22 |
|
---|
23 | /**
|
---|
24 | * This class contains main agent methods and algorithms that agent uses in a
|
---|
25 | * negotiation session based on Alternating Offers protocol.
|
---|
26 | *
|
---|
27 | * @author Siamak Hajizadeh, Thijs van Krimpen, Daphne Looije
|
---|
28 | *
|
---|
29 | */
|
---|
30 | public class KLH extends Agent {
|
---|
31 | private BidHistory bidHistory;
|
---|
32 | private BidSelector BSelector;
|
---|
33 | private double MINIMUM_BID_UTILITY = 0.585D;
|
---|
34 | private final int TOP_SELECTED_BIDS = 4;
|
---|
35 | private final double LEARNING_COEF = 0.2D;
|
---|
36 | private final int LEARNING_VALUE_ADDITION = 1;
|
---|
37 | private final double UTILITY_TOLORANCE = 0.01D;
|
---|
38 | private double Ka = 0.05;
|
---|
39 | private double e = 0.05;
|
---|
40 | private double discountF = 1D;
|
---|
41 | private double lowestYetUtility = 1D;
|
---|
42 |
|
---|
43 | private LinkedList<Entry<Double, Bid>> offerQueue = null;
|
---|
44 | private Bid opponentLastBid = null;
|
---|
45 | private boolean firstRound = true;
|
---|
46 |
|
---|
47 | private Domain domain = null;
|
---|
48 | private AdditiveUtilitySpace oppUtility = null;
|
---|
49 | private int numberOfIssues = 0;
|
---|
50 |
|
---|
51 | private double maxUtil = 1;
|
---|
52 | private double minUtil = MINIMUM_BID_UTILITY;
|
---|
53 |
|
---|
54 | private Bid opponentbestbid = null;
|
---|
55 | private Entry<Double, Bid> opponentbestentry;
|
---|
56 |
|
---|
57 | private final boolean TEST_EQUIVALENCE = false;
|
---|
58 | private Random random100;
|
---|
59 | private Random random200;
|
---|
60 | int round;
|
---|
61 |
|
---|
62 | /**
|
---|
63 | * handles some initializations. it is called when agent object is created
|
---|
64 | * to start a negotiation session
|
---|
65 | *
|
---|
66 | */
|
---|
67 | @Override
|
---|
68 | public void init() {
|
---|
69 | BSelector = new BidSelector(utilitySpace);
|
---|
70 | bidHistory = new BidHistory(utilitySpace);
|
---|
71 | oppUtility = (AdditiveUtilitySpace) utilitySpace.copy();
|
---|
72 | offerQueue = new LinkedList<Entry<Double, Bid>>();
|
---|
73 | domain = utilitySpace.getDomain();
|
---|
74 | numberOfIssues = domain.getIssues().size();
|
---|
75 |
|
---|
76 | if (utilitySpace.getDiscountFactor() <= 1D
|
---|
77 | && utilitySpace.getDiscountFactor() > 0D)
|
---|
78 | discountF = utilitySpace.getDiscountFactor();
|
---|
79 |
|
---|
80 | Entry<Double, Bid> highestBid = BSelector.BidList.lastEntry();
|
---|
81 |
|
---|
82 | try {
|
---|
83 | maxUtil = utilitySpace.getUtility(highestBid.getValue());
|
---|
84 | } catch (Exception e) {
|
---|
85 | e.printStackTrace();
|
---|
86 | }
|
---|
87 |
|
---|
88 | if (TEST_EQUIVALENCE) {
|
---|
89 | random100 = new Random(100);
|
---|
90 | random200 = new Random(200);
|
---|
91 | } else {
|
---|
92 | random100 = new Random();
|
---|
93 | random200 = new Random();
|
---|
94 | }
|
---|
95 |
|
---|
96 | // double highestUtil = highestBid.getKey();
|
---|
97 | // double secondUtil = highestUtil;
|
---|
98 |
|
---|
99 | // retrieves the 5th highest utility,
|
---|
100 | // then checked whether this can still be reached with the current Ka
|
---|
101 | // value
|
---|
102 | // for(int a=0;a<5;a++)
|
---|
103 | // {
|
---|
104 | // secondUtil = BSelector.BidList.lowerEntry(secondUtil).getKey();
|
---|
105 | // }
|
---|
106 | // if(secondUtil < maxUtil-Ka*(maxUtil-minUtil))
|
---|
107 | // {
|
---|
108 | // Ka = (maxUtil-secondUtil)/(maxUtil-minUtil);
|
---|
109 | // }
|
---|
110 |
|
---|
111 | // get the number of issues and set a weight for each equal to
|
---|
112 | // 1/number_of_issues
|
---|
113 | // the initialization of opponent's preference profile
|
---|
114 | double w = 1D / numberOfIssues;
|
---|
115 | for (Entry<Objective, Evaluator> e : oppUtility.getEvaluators()) {
|
---|
116 | oppUtility.unlock(e.getKey());
|
---|
117 | e.getValue().setWeight(w);
|
---|
118 | try {
|
---|
119 | // set the initial weight for each value of each issue to 1.
|
---|
120 | for (ValueDiscrete vd : ((IssueDiscrete) e.getKey())
|
---|
121 | .getValues())
|
---|
122 | ((EvaluatorDiscrete) e.getValue()).setEvaluation(vd, 1);
|
---|
123 | } catch (Exception ex) {
|
---|
124 | ex.printStackTrace();
|
---|
125 | }
|
---|
126 | }
|
---|
127 | if (utilitySpace.getReservationValue() != null)
|
---|
128 | MINIMUM_BID_UTILITY = utilitySpace.getReservationValue();
|
---|
129 | }
|
---|
130 |
|
---|
131 | @Override
|
---|
132 | public String getVersion() {
|
---|
133 | return "1.2";
|
---|
134 | }
|
---|
135 |
|
---|
136 | @Override
|
---|
137 | public String getName() {
|
---|
138 | return "HardHeaded";
|
---|
139 | }
|
---|
140 |
|
---|
141 | /**
|
---|
142 | * Receives opponent's action
|
---|
143 | *
|
---|
144 | */
|
---|
145 | @Override
|
---|
146 | public void ReceiveMessage(Action pAction) {
|
---|
147 | double opbestvalue;
|
---|
148 | if (pAction instanceof Offer) {
|
---|
149 | opponentLastBid = ((Offer) pAction).getBid();
|
---|
150 | bidHistory.addOpponentBid(opponentLastBid);
|
---|
151 | updateLearner();
|
---|
152 | try {
|
---|
153 | if (opponentbestbid == null)
|
---|
154 | opponentbestbid = opponentLastBid;
|
---|
155 | else if (utilitySpace.getUtility(opponentLastBid) > utilitySpace
|
---|
156 | .getUtility(opponentbestbid)) {
|
---|
157 | opponentbestbid = opponentLastBid;
|
---|
158 | }
|
---|
159 |
|
---|
160 | opbestvalue = BSelector.BidList
|
---|
161 | .floorEntry(utilitySpace.getUtility(opponentbestbid))
|
---|
162 | .getKey();
|
---|
163 |
|
---|
164 | while (!BSelector.BidList.floorEntry(opbestvalue).getValue()
|
---|
165 | .equals(opponentbestbid)) {
|
---|
166 | opbestvalue = BSelector.BidList.lowerEntry(opbestvalue)
|
---|
167 | .getKey();
|
---|
168 | }
|
---|
169 | opponentbestentry = BSelector.BidList.floorEntry(opbestvalue);
|
---|
170 | } catch (Exception ex) {
|
---|
171 | ex.printStackTrace();
|
---|
172 | }
|
---|
173 | }
|
---|
174 |
|
---|
175 | }
|
---|
176 |
|
---|
177 | /**
|
---|
178 | * Contains an object of type {@link AdditiveUtilitySpace} that is updated
|
---|
179 | * over time and as bids are received, to match the preference profile of
|
---|
180 | * the opponent.
|
---|
181 | *
|
---|
182 | */
|
---|
183 |
|
---|
184 | private void updateLearner() {
|
---|
185 |
|
---|
186 | if (bidHistory.getOpponentBidCount() < 2)
|
---|
187 | return;
|
---|
188 |
|
---|
189 | int numberOfUnchanged = 0;
|
---|
190 | HashMap<Integer, Integer> lastDiffSet = bidHistory
|
---|
191 | .BidDifferenceofOpponentsLastTwo();
|
---|
192 |
|
---|
193 | // counting the number of unchanged issues
|
---|
194 | for (Integer i : lastDiffSet.keySet()) {
|
---|
195 | if (lastDiffSet.get(i) == 0)
|
---|
196 | numberOfUnchanged++;
|
---|
197 | }
|
---|
198 |
|
---|
199 | // This is the value to be added to weights of unchanged issues before
|
---|
200 | // normalization.
|
---|
201 | // Also the value that is taken as the minimum possible weight,
|
---|
202 | // (therefore defining the maximum possible also).
|
---|
203 | double goldenValue = LEARNING_COEF / numberOfIssues;
|
---|
204 | // The total sum of weights before normalization.
|
---|
205 | double totalSum = 1D + goldenValue * numberOfUnchanged;
|
---|
206 | // The maximum possible weight
|
---|
207 | double maximumWeight = 1D - (numberOfIssues) * goldenValue / totalSum;
|
---|
208 |
|
---|
209 | // re-weighing issues while making sure that the sum remains 1
|
---|
210 | for (Integer i : lastDiffSet.keySet()) {
|
---|
211 | if (lastDiffSet.get(i) == 0
|
---|
212 | && oppUtility.getWeight(i) < maximumWeight)
|
---|
213 | oppUtility.setWeight(domain.getObjectivesRoot().getObjective(i),
|
---|
214 | (oppUtility.getWeight(i) + goldenValue) / totalSum);
|
---|
215 | else
|
---|
216 | oppUtility.setWeight(domain.getObjectivesRoot().getObjective(i),
|
---|
217 | oppUtility.getWeight(i) / totalSum);
|
---|
218 | }
|
---|
219 |
|
---|
220 | // Then for each issue value that has been offered last time, a constant
|
---|
221 | // value is added to its corresponding ValueDiscrete.
|
---|
222 | try {
|
---|
223 | for (Entry<Objective, Evaluator> e : oppUtility.getEvaluators()) {
|
---|
224 |
|
---|
225 | ((EvaluatorDiscrete) e.getValue()).setEvaluation(
|
---|
226 | opponentLastBid.getValue(
|
---|
227 | ((IssueDiscrete) e.getKey()).getNumber()),
|
---|
228 | (LEARNING_VALUE_ADDITION + ((EvaluatorDiscrete) e
|
---|
229 | .getValue()).getEvaluationNotNormalized(
|
---|
230 | ((ValueDiscrete) opponentLastBid
|
---|
231 | .getValue(((IssueDiscrete) e
|
---|
232 | .getKey())
|
---|
233 | .getNumber())))));
|
---|
234 | }
|
---|
235 | } catch (Exception ex) {
|
---|
236 | ex.printStackTrace();
|
---|
237 | }
|
---|
238 | }
|
---|
239 |
|
---|
240 | /**
|
---|
241 | * This function calculates the concession amount based on remaining time,
|
---|
242 | * initial parameters, and, the discount factor.
|
---|
243 | *
|
---|
244 | * @return double: concession step
|
---|
245 | */
|
---|
246 | public double get_p() {
|
---|
247 |
|
---|
248 | double time = timeline.getTime();
|
---|
249 | double Fa;
|
---|
250 | double p = 1D;
|
---|
251 | double step_point = discountF;
|
---|
252 | double tempMax = maxUtil;
|
---|
253 | double tempMin = minUtil;
|
---|
254 | double tempE = e;
|
---|
255 | double ignoreDiscountThreshold = 0.9D;
|
---|
256 |
|
---|
257 | if (step_point >= ignoreDiscountThreshold) {
|
---|
258 | Fa = Ka + (1 - Ka) * Math.pow(time / step_point, 1D / e);
|
---|
259 | p = minUtil + (1 - Fa) * (maxUtil - minUtil);
|
---|
260 | } else if (time <= step_point) {
|
---|
261 | tempE = e / step_point;
|
---|
262 | Fa = Ka + (1 - Ka) * Math.pow(time / step_point, 1D / tempE);
|
---|
263 | tempMin += Math.abs(tempMax - tempMin) * step_point;
|
---|
264 | p = tempMin + (1 - Fa) * (tempMax - tempMin);
|
---|
265 | } else {
|
---|
266 | // Ka = (maxUtil - (tempMax -
|
---|
267 | // tempMin*step_point))/(maxUtil-minUtil);
|
---|
268 | tempE = 30D;
|
---|
269 | Fa = (Ka + (1 - Ka) * Math
|
---|
270 | .pow((time - step_point) / (1 - step_point), 1D / tempE));
|
---|
271 | tempMax = tempMin + Math.abs(tempMax - tempMin) * step_point;
|
---|
272 | p = tempMin + (1 - Fa) * (tempMax - tempMin);
|
---|
273 | }
|
---|
274 | return p;
|
---|
275 | }
|
---|
276 |
|
---|
277 | /**
|
---|
278 | * This is the main strategy of that determines the behavior of the agent.
|
---|
279 | * It uses a concession function that in accord with remaining time decides
|
---|
280 | * which bids should be offered. Also using the learned opponent utility, it
|
---|
281 | * tries to offer more acceptable bids.
|
---|
282 | *
|
---|
283 | * @return {@link Action} that contains agents decision
|
---|
284 | */
|
---|
285 | @Override
|
---|
286 | public Action chooseAction() {
|
---|
287 | round++;
|
---|
288 | Entry<Double, Bid> newBid = null;
|
---|
289 | Action newAction = null;
|
---|
290 |
|
---|
291 | double p = get_p();
|
---|
292 |
|
---|
293 | try {
|
---|
294 | if (firstRound) {
|
---|
295 | firstRound = !firstRound;
|
---|
296 | newBid = BSelector.BidList.lastEntry();
|
---|
297 | offerQueue.add(newBid);
|
---|
298 | }
|
---|
299 |
|
---|
300 | // if the offers queue has yet bids to be offered, skip this.
|
---|
301 | // otherwise select some new bids to be offered
|
---|
302 | else if (offerQueue.isEmpty() || offerQueue == null) {
|
---|
303 | // calculations of concession step according to time
|
---|
304 |
|
---|
305 | TreeMap<Double, Bid> newBids = new TreeMap<Double, Bid>();
|
---|
306 | newBid = BSelector.BidList
|
---|
307 | .lowerEntry(bidHistory.getMyLastBid().getKey());
|
---|
308 | newBids.put(newBid.getKey(), newBid.getValue());
|
---|
309 |
|
---|
310 | if (newBid.getKey() < p) {
|
---|
311 | int indexer = bidHistory.getMyBidCount();
|
---|
312 | indexer = (int) Math
|
---|
313 | .floor(indexer * random100.nextDouble());
|
---|
314 | newBids.remove(newBid.getKey());
|
---|
315 | newBids.put(bidHistory.getMyBid(indexer).getKey(),
|
---|
316 | bidHistory.getMyBid(indexer).getValue());
|
---|
317 | }
|
---|
318 |
|
---|
319 | double firstUtil = newBid.getKey();
|
---|
320 |
|
---|
321 | Entry<Double, Bid> addBid = BSelector.BidList
|
---|
322 | .lowerEntry(firstUtil);
|
---|
323 | double addUtil = addBid.getKey();
|
---|
324 | int count = 0;
|
---|
325 |
|
---|
326 | while ((firstUtil - addUtil) < UTILITY_TOLORANCE
|
---|
327 | && addUtil >= p) {
|
---|
328 | newBids.put(addUtil, addBid.getValue());
|
---|
329 | addBid = BSelector.BidList.lowerEntry(addUtil);
|
---|
330 | addUtil = addBid.getKey();
|
---|
331 | count = count + 1;
|
---|
332 | }
|
---|
333 |
|
---|
334 | // adding selected bids to offering queue
|
---|
335 | if (newBids.size() <= TOP_SELECTED_BIDS) {
|
---|
336 | offerQueue.addAll(newBids.entrySet());
|
---|
337 | } else {
|
---|
338 | int addedSofar = 0;
|
---|
339 | Entry<Double, Bid> bestBid = null;
|
---|
340 |
|
---|
341 | while (addedSofar <= TOP_SELECTED_BIDS) {
|
---|
342 | bestBid = newBids.lastEntry();
|
---|
343 | // selecting the one bid with the most utility for the
|
---|
344 | // opponent.
|
---|
345 | for (Entry<Double, Bid> e : newBids.entrySet()) {
|
---|
346 | if (oppUtility.getUtility(e.getValue()) > oppUtility
|
---|
347 | .getUtility(bestBid.getValue())) {
|
---|
348 | bestBid = e;
|
---|
349 | }
|
---|
350 | }
|
---|
351 | offerQueue.add(bestBid);
|
---|
352 | newBids.remove(bestBid.getKey());
|
---|
353 | addedSofar++;
|
---|
354 | }
|
---|
355 | }
|
---|
356 | // if opponentbest entry is better for us then the offer que
|
---|
357 | // then replace the top entry
|
---|
358 |
|
---|
359 | if (offerQueue.getFirst().getKey() < opponentbestentry
|
---|
360 | .getKey()) {
|
---|
361 | offerQueue.addFirst(opponentbestentry);
|
---|
362 | }
|
---|
363 | }
|
---|
364 |
|
---|
365 | // if no bids are selected there must be a problem
|
---|
366 | if (offerQueue.isEmpty() || offerQueue == null) {
|
---|
367 | Bid bestBid1 = domain.getRandomBid(random200);
|
---|
368 | if (opponentLastBid != null
|
---|
369 | && utilitySpace.getUtility(bestBid1) <= utilitySpace
|
---|
370 | .getUtility(opponentLastBid)) {
|
---|
371 | newAction = new Accept(getAgentID(), opponentLastBid);
|
---|
372 | } else if (bestBid1 == null) {
|
---|
373 | newAction = new Accept(getAgentID(), opponentLastBid);
|
---|
374 | } else {
|
---|
375 | newAction = new Offer(getAgentID(), bestBid1);
|
---|
376 | if (utilitySpace.getUtility(bestBid1) < lowestYetUtility)
|
---|
377 | lowestYetUtility = utilitySpace.getUtility(bestBid1);
|
---|
378 | }
|
---|
379 | }
|
---|
380 |
|
---|
381 | // if opponent's suggested bid is better than the one we just
|
---|
382 | // selected, then accept it
|
---|
383 | if (opponentLastBid != null && (utilitySpace
|
---|
384 | .getUtility(opponentLastBid) > lowestYetUtility
|
---|
385 | || utilitySpace.getUtility(
|
---|
386 | offerQueue.getFirst().getValue()) <= utilitySpace
|
---|
387 | .getUtility(opponentLastBid))) {
|
---|
388 | newAction = new Accept(getAgentID(), opponentLastBid);
|
---|
389 | }
|
---|
390 | // else offer a new bid
|
---|
391 | else {
|
---|
392 | Entry<Double, Bid> offer = offerQueue.remove();
|
---|
393 | bidHistory.addMyBid(offer);
|
---|
394 | if (offer.getKey() < lowestYetUtility) {
|
---|
395 |
|
---|
396 | lowestYetUtility = utilitySpace
|
---|
397 | .getUtility(offer.getValue());
|
---|
398 | }
|
---|
399 | newAction = new Offer(getAgentID(), offer.getValue());
|
---|
400 | }
|
---|
401 | } catch (Exception e) {
|
---|
402 | e.printStackTrace();
|
---|
403 | }
|
---|
404 |
|
---|
405 | return newAction;
|
---|
406 | }
|
---|
407 |
|
---|
408 | @Override
|
---|
409 | public SupportedNegotiationSetting getSupportedNegotiationSetting() {
|
---|
410 | return SupportedNegotiationSetting.getLinearUtilitySpaceInstance();
|
---|
411 | }
|
---|
412 |
|
---|
413 | @Override
|
---|
414 | public String getDescription() {
|
---|
415 | return "ANAC2011";
|
---|
416 | }
|
---|
417 | }
|
---|