source: src/main/java/negotiator/boaframework/opponentmodel/nash/AIssueEvaluationNumerical.java

Last change on this file 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.1 KB
Line 
1package negotiator.boaframework.opponentmodel.nash;
2
3import java.util.ArrayList;
4
5import genius.core.issue.Issue;
6import genius.core.issue.Value;
7
8/**
9 * This is the base class for numerical issueEvaluations. All numerical IssueEvaluations assume that the utilityfunction
10 * of the issue consist out of 3 points that form a triangle:
11 * - A point at the left side of the function, which has zero utility.
12 * - A point somewhere in between the left and right point, which has max utility.
13 * - A point at the right side of the function, which has zero utility.
14 *
15 * We then assume that the function is a straight line from the left point, to the middle point, to the right point.
16 * The middle max utility point is calculated by the offered values of the negotiator. The earlier the value is offered,
17 * the more important we think it is. To estimate the utility of an offered value, we then interpolate between the left and middle point,
18 * or the right and middle point.
19 *
20 * @author Roland van der Linden
21 *
22 */
23public abstract class AIssueEvaluationNumerical extends AIssueEvaluation
24{
25 // **************************************
26 // Fields
27 // **************************************
28
29 //The three points with which we estimate the utility function.
30 protected double leftZeroUtilityValue, rightZeroUtilityValue, maxUtilityValue;
31 //This is the range of OUR OWN utility function. We assume that the range of the opponent is almost equal to it.
32 protected Range ourNonZeroUtilityRange;
33 //These are the values that have been offered by the negotiator in the past.
34 protected ArrayList<Value> offeredValueHistory;
35
36
37 // **************************************
38 // Constructor & init
39 // **************************************
40
41 /**
42 * This will construct a new numerical IssueEvaluation.
43 * @param issue The issue we are evaluating.
44 * @param ourNonZeroUtilityRange The range of OUR OWN utilityfunction.
45 */
46 public AIssueEvaluationNumerical(Issue issue, Range ourNonZeroUtilityRange)
47 {
48 super(issue);
49
50 this.ourNonZeroUtilityRange = ourNonZeroUtilityRange;
51 this.offeredValueHistory = new ArrayList<Value>(250);
52 }
53
54
55 // **************************************
56 // Update
57 // **************************************
58
59 /**
60 * This updates the numerical issueEvaluation with a newly offered value.
61 * We first save the new value in our history, and then receiveMessage the max utility point and left and right zero utility points.
62 */
63 @Override
64 public void updateIssueEvaluation(Value chosenValue)
65 {
66 super.updateIssueEvaluation(chosenValue);
67
68 //Save the newly offered value into the list.
69 this.offeredValueHistory.add(chosenValue);
70
71 //Update the value where the utility is 1.
72 this.updateMaxUtilityValue();
73
74 //Update the values where the utility becomes 0 (left and right).
75 this.updateZeroUtilityValues();
76 }
77
78 /**
79 * This method updates the max utility value. We do this based on the history of offered values by the negotiator.
80 * We do not just take the average: The earlier a bid has been done, the higher the importance we give it.
81 * To calculate this factor, we use the following mechanism:
82 *
83 * maxUtilityValue = 0.5 (+rest) * first offered value
84 * + 0.25 * second offered value
85 * + 0.125 * third offeredd value
86 * + ...
87 *
88 */
89 protected void updateMaxUtilityValue()
90 {
91 int n = this.offeredValueHistory.size();
92
93 double newMaxUtilityValue = 0;
94
95 for(int i = 0; i < n; i++)
96 {
97 double contributionWeight = 0;
98 double numericalValue = this.getNumericalValue(this.offeredValueHistory.get(i));
99
100 //The first value has an additional contribution because otherwise that is unused.
101 if(i == 0)
102 contributionWeight = (Math.pow(0.5, i + 1) + Math.pow(0.5, n));
103 else
104 contributionWeight = (Math.pow(0.5, i + 1));
105
106 newMaxUtilityValue += (contributionWeight * numericalValue);
107 }
108
109 this.maxUtilityValue = newMaxUtilityValue;
110 }
111
112 /**
113 * This method updates the zero utility values. We do this based on our max utility value,
114 * and the length of OUR OWN range. We assume this range is equal to ours.
115 */
116 protected void updateZeroUtilityValues()
117 {
118 double ourRangeSize = this.ourNonZeroUtilityRange.getLength();
119 double halfOurRangeSize = ourRangeSize / 2.0;
120
121 double newLeftZeroUtilityValue = this.maxUtilityValue - halfOurRangeSize;
122 double newRightZeroUtilityValue = this.maxUtilityValue + halfOurRangeSize;
123
124 if(newLeftZeroUtilityValue < this.getIssueLowerBound())
125 {
126 double difference = Math.abs(this.getIssueLowerBound() - newLeftZeroUtilityValue);
127 double freeSpaceOnRightSide = this.getIssueUpperBound() - newRightZeroUtilityValue;
128 double usedDifference = Math.min(difference, freeSpaceOnRightSide);
129 newRightZeroUtilityValue += usedDifference;
130 }
131
132 if(newRightZeroUtilityValue > this.getIssueUpperBound())
133 {
134 double difference = Math.abs(newRightZeroUtilityValue - this.getIssueUpperBound());
135 double freeSpaceOnLeftSide = newLeftZeroUtilityValue - this.getIssueLowerBound();
136 double usedDifference = Math.min(difference, freeSpaceOnLeftSide);
137 newLeftZeroUtilityValue += usedDifference;
138 }
139
140 this.leftZeroUtilityValue = newLeftZeroUtilityValue;
141 this.rightZeroUtilityValue = newRightZeroUtilityValue;
142 }
143
144
145 // **************************************
146 // Getters
147 // **************************************
148
149 /**
150 * This returns the normalized weight for the given value. We calculate this value on two rules:
151 * - If the value lies in between the left and max point or the right and middle point:
152 * We interpolate between the two points, with utility 1 at the middle point and utility 0 at the other point.
153 * - If the value does not lie within this range:
154 * We return utility 0 (outside the range of positive utility).
155 */
156 @Override
157 public double getNormalizedValueWeight(Value value)
158 {
159 //We do not allow valueWeight requests when no values have been offered yet.
160 if(!this.isFirstValueOffered())
161 throw new IllegalStateException("ValueWeights can not be calculated when not values have been offered yet.");
162
163 double numericalValue = this.getNumericalValue(value);
164
165 //Test whether the value lies within the left zero utility and max utility values
166 if(numericalValue >= leftZeroUtilityValue && numericalValue <= maxUtilityValue)
167 return getNormalizedInterpolatedWeight(leftZeroUtilityValue, maxUtilityValue, numericalValue);
168 //Test whether the value lies within the max utility and right zero utility values.
169 else if(numericalValue >= maxUtilityValue && numericalValue <= rightZeroUtilityValue)
170 return getNormalizedInterpolatedWeight(rightZeroUtilityValue, maxUtilityValue, numericalValue);
171 //The value does not lie within the range where the utility is >0, so it's weight is zero.
172 else
173 return 0;
174 }
175
176 /**
177 * This method executes the interpolation between the max utility point and the left or right zero utility point.
178 * We return the interpolated utility value for the inBetweenValue
179 * @param zeroPoint The point where the utility is zero.
180 * @param maxPoint The point where the utility is one.
181 * @param inBetweenValue The value for which we wish to know the utility.
182 * @return The interpolated utility, based on the location of the inBetweenValue.
183 */
184 protected double getNormalizedInterpolatedWeight(double zeroPoint, double maxPoint, double inBetweenValue)
185 {
186 return Math.abs((inBetweenValue - zeroPoint) / (maxPoint - zeroPoint));
187 }
188
189 /**
190 * This return the actual numerical value that resides inside the Value object.
191 * @param value
192 * @return
193 */
194 protected abstract double getNumericalValue(Value value);
195
196 /**
197 * This function must be implemented by the subclass to return the lower bound of the issue under evaluation.
198 * Since this class only works with abstract classes Value and Issue, we cannot extract the bound
199 * in this class.
200 * @return
201 */
202 public abstract double getIssueLowerBound();
203
204 /**
205 * This function must be implemented by the subclass to return the upper bound of the issue under evaluation.
206 * Since this class only works with abstract classes Value and Issue, we cannot extract the bound
207 * in this class.
208 * @return
209 */
210 public abstract double getIssueUpperBound();
211
212 /**
213 * This method returns the length of the range of our issue.
214 * @return
215 */
216 public double getIssueRangeLength()
217 {
218 return this.getIssueUpperBound() - this.getIssueLowerBound();
219 }
220
221 /**
222 * This returns the standard deviation of the list of offered values by the opponent.
223 * @return
224 */
225 public double getOfferedValuesStandardDeviation()
226 {
227 ArrayList<Double> valueList = convertToNumericalValues(this.offeredValueHistory);
228 return StatisticsUtil.getStandardDeviation(valueList);
229 }
230
231
232 // **************************************
233 // Other methods
234 // **************************************
235
236 /**
237 * This method converts a list of Value objects to a list containing the actual numerical values that reside inside them.
238 * @param values
239 * @return
240 */
241 private ArrayList<Double> convertToNumericalValues(ArrayList<Value> values)
242 {
243 ArrayList<Double> result = new ArrayList<Double>(values.size());
244 for(Value v : values)
245 result.add(this.getNumericalValue(v));
246
247 return result;
248 }
249
250 /**
251 * This returns a string representation of the issueEvaluation.
252 * @return The string representation.
253 */
254 public String toString()
255 {
256 String result = super.toString();
257 String nl = "\n";
258 String pre = " ";
259
260 result += "===== Boundaries =====" + nl;
261 result += pre + "lower = " + this.getIssueLowerBound() + nl;
262 result += pre + "upper = " + this.getIssueUpperBound() + nl;
263 result += "===== Utility Piramid Values =====" + nl;
264 result += pre + "left = " + leftZeroUtilityValue + nl;
265 result += pre + "max = " + maxUtilityValue + nl;
266 result += pre + "right = " + rightZeroUtilityValue + nl;
267 result += "===== offeredValueHistory =====" + nl;
268 result += pre + offeredValueHistory.toString() + nl;
269 result += "##### END #####" + nl;
270
271 return result;
272 }
273
274}
Note: See TracBrowser for help on using the repository browser.