1 | package geniusweb.bidspace;
|
---|
2 |
|
---|
3 | import java.math.BigDecimal;
|
---|
4 | import java.math.BigInteger;
|
---|
5 | import java.util.Collections;
|
---|
6 | import java.util.HashMap;
|
---|
7 | import java.util.List;
|
---|
8 | import java.util.Map;
|
---|
9 | import java.util.stream.Collectors;
|
---|
10 |
|
---|
11 | import geniusweb.issuevalue.Bid;
|
---|
12 | import geniusweb.issuevalue.Domain;
|
---|
13 | import geniusweb.issuevalue.Value;
|
---|
14 | import geniusweb.profile.utilityspace.LinearAdditive;
|
---|
15 | import tudelft.utilities.immutablelist.AbstractImmutableList;
|
---|
16 | import tudelft.utilities.immutablelist.FixedList;
|
---|
17 | import tudelft.utilities.immutablelist.ImmutableList;
|
---|
18 | import tudelft.utilities.immutablelist.JoinedList;
|
---|
19 | import tudelft.utilities.immutablelist.MapList;
|
---|
20 | import tudelft.utilities.immutablelist.Tuple;
|
---|
21 |
|
---|
22 | /**
|
---|
23 | * Tool class containing functions dealing with utilities of all bids in a given
|
---|
24 | * {@link LinearAdditive}. This class caches previously computed values to
|
---|
25 | * accelerate the calls and subsequent calls. Re-use the object to keep/reuse
|
---|
26 | * the cache.
|
---|
27 | * <h2>Rounding</h2> Internally, utilities of bids are rounded to the given
|
---|
28 | * precision. This may cause inclusion/exclusion of some bids in the results.
|
---|
29 | * See {@link #BidsWithUtility(LinearAdditive, int)} for more details
|
---|
30 | */
|
---|
31 | public class BidsWithUtility {
|
---|
32 |
|
---|
33 | private final List<IssueInfo> issueInfo;
|
---|
34 | private final int precision; // #digits used for Intervals
|
---|
35 |
|
---|
36 | /**
|
---|
37 | * cache. Key = call arguments for {@link #get(int, Interval)}. Value=return
|
---|
38 | * value of that call.
|
---|
39 | */
|
---|
40 | private final Map<Tuple<Integer, Interval>, ImmutableList<Bid>> cache = new HashMap<>();
|
---|
41 |
|
---|
42 | /**
|
---|
43 | * Default constructor, uses default precision 6. This value seems practical
|
---|
44 | * for the common range of issues, utilities and weights. See
|
---|
45 | * {@link #BidsWithUtility(LinearAdditive, int)} for more details on the
|
---|
46 | * precision.
|
---|
47 | *
|
---|
48 | * @param space the {@link LinearAdditive} to analyze
|
---|
49 | */
|
---|
50 | public BidsWithUtility(LinearAdditive space) {
|
---|
51 | this(space, 6);
|
---|
52 | }
|
---|
53 |
|
---|
54 | /**
|
---|
55 | *
|
---|
56 | * @param space the {@link LinearAdditive} to analyze
|
---|
57 | * @param precision the number of digits to use for computations. In
|
---|
58 | * practice, 6 seems a good default value.
|
---|
59 | * <p>
|
---|
60 | * All utilities * weight are rounded to this number of
|
---|
61 | * digits. This value should match the max number of
|
---|
62 | * (digits used in the weight of an issue + number of
|
---|
63 | * digits used in the issue utility). To determine the
|
---|
64 | * optimal value, one may consider the step size of the
|
---|
65 | * issues, and the range of interest. For instance if the
|
---|
66 | * utility function has values 1/3 and 2/3, then these have
|
---|
67 | * an 'infinite' number of relevant digits. But if the goal
|
---|
68 | * is to search bids between utility 0.1 and 0.2, then
|
---|
69 | * computing in 2 digits might already be sufficient.
|
---|
70 | * <p>
|
---|
71 | * This algorithm has memory and space complexity O(
|
---|
72 | * |nissues| 10^precision ). For spaces up to 7 issues, 7
|
---|
73 | * digits should be feasible; for 9 issues, 6 digits may be
|
---|
74 | * the maximum.
|
---|
75 | */
|
---|
76 | public BidsWithUtility(LinearAdditive space, int precision) {
|
---|
77 | this(getInfo(space, precision), precision);
|
---|
78 | }
|
---|
79 |
|
---|
80 | /**
|
---|
81 | *
|
---|
82 | * @param issuesInfo List of the relevant issues (in order of relevance) and
|
---|
83 | * all info of each issue.
|
---|
84 | * @param precision the number of digits used in Intervals.
|
---|
85 | */
|
---|
86 | public BidsWithUtility(List<IssueInfo> issuesInfo, int precision) {
|
---|
87 | if (issuesInfo == null || issuesInfo.isEmpty()) {
|
---|
88 | throw new IllegalArgumentException(
|
---|
89 | "sortedissues list must contain at least 1 element");
|
---|
90 | }
|
---|
91 |
|
---|
92 | this.issueInfo = issuesInfo;
|
---|
93 | this.precision = precision;
|
---|
94 |
|
---|
95 | }
|
---|
96 |
|
---|
97 | /**
|
---|
98 | * @return the (rounded) utility {@link Interval} of this space: minimum and
|
---|
99 | * maximum achievable utility.
|
---|
100 | */
|
---|
101 | public Interval getRange() {
|
---|
102 | return getRange(issueInfo.size() - 1);
|
---|
103 | }
|
---|
104 |
|
---|
105 | /**
|
---|
106 | *
|
---|
107 | * @param range the minimum and maximum utility required of the bids. to be
|
---|
108 | * included (both ends inclusive).
|
---|
109 | * @return a list with bids that have a (rounded) utility inside range.
|
---|
110 | * possibly empty.
|
---|
111 | */
|
---|
112 | public ImmutableList<Bid> getBids(Interval range) {
|
---|
113 | return get(issueInfo.size() - 1, range.round(precision));
|
---|
114 | }
|
---|
115 |
|
---|
116 | public List<IssueInfo> getInfo() {
|
---|
117 | return Collections.unmodifiableList(issueInfo);
|
---|
118 | }
|
---|
119 |
|
---|
120 | /**
|
---|
121 | *
|
---|
122 | * @param isMax the extreme bid required
|
---|
123 | * @return the extreme bid, either the minimum if isMax=false or maximum if
|
---|
124 | * isMax=true
|
---|
125 | */
|
---|
126 | public Bid getExtremeBid(boolean isMax) {
|
---|
127 | Map<String, Value> map = new HashMap<>();
|
---|
128 | for (IssueInfo info : issueInfo) {
|
---|
129 | map.put(info.getName(), info.getExtreme(isMax));
|
---|
130 | }
|
---|
131 | return new Bid(map);
|
---|
132 | }
|
---|
133 |
|
---|
134 | /**
|
---|
135 | * Create partial BidsWithUtil list considering only issues 0..n, with
|
---|
136 | * utilities in given range.
|
---|
137 | *
|
---|
138 | * @param n the number of issueRanges to consider, we consider 0..n here.
|
---|
139 | * The recursion decreases n until n=0
|
---|
140 | * @param goal the minimum and maximum utility required of the bids. to be
|
---|
141 | * included (both ends inclusive)
|
---|
142 | * @return BidsWithUtil list, possibly empty.
|
---|
143 | */
|
---|
144 | protected ImmutableList<Bid> get(int n, Interval goal) {
|
---|
145 | if (goal == null) {
|
---|
146 | throw new NullPointerException("Interval=null");
|
---|
147 | }
|
---|
148 |
|
---|
149 | // clamp goal into what is reachable. Avoid caching empty
|
---|
150 | goal = goal.intersect(getRange(n));
|
---|
151 | if (goal.isEmpty()) {
|
---|
152 | return new FixedList<>();
|
---|
153 | }
|
---|
154 |
|
---|
155 | Tuple<Integer, Interval> cachetuple = new Tuple<>(n, goal);
|
---|
156 | ImmutableList<Bid> cached = cache.get(cachetuple);
|
---|
157 | if (cached != null) {
|
---|
158 | // hits++;
|
---|
159 | return cached;
|
---|
160 | }
|
---|
161 |
|
---|
162 | ImmutableList<Bid> result = checkedGet(n, goal);
|
---|
163 | cache.put(cachetuple, result);
|
---|
164 | return result;
|
---|
165 | }
|
---|
166 |
|
---|
167 | private static List<IssueInfo> getInfo(LinearAdditive space2,
|
---|
168 | int precision) {
|
---|
169 | Domain dom = space2.getDomain();
|
---|
170 | return space2.getDomain().getIssues().stream()
|
---|
171 | .map(issue -> new IssueInfo(issue, dom.getValues(issue),
|
---|
172 | space2.getUtilities().get(issue),
|
---|
173 | space2.getWeight(issue), precision))
|
---|
174 | .collect(Collectors.toList());
|
---|
175 | }
|
---|
176 |
|
---|
177 | private ImmutableList<Bid> checkedGet(int n, Interval goal) {
|
---|
178 | IssueInfo info = issueInfo.get(n);
|
---|
179 | // issue is the first issuesWithRange.
|
---|
180 | String issue = issueInfo.get(n).getName();
|
---|
181 |
|
---|
182 | if (n == 0)
|
---|
183 | return new OneIssueSubset(info, goal);
|
---|
184 |
|
---|
185 | // make new list, joining all sub-lists
|
---|
186 | ImmutableList<Bid> fulllist = new FixedList<>();
|
---|
187 | for (Value val : info.getValues()) {
|
---|
188 | BigDecimal weightedutil = info.getWeightedUtil(val);
|
---|
189 | Interval subgoal = goal.subtract(weightedutil);
|
---|
190 | // recurse: get list of bids for the subspace
|
---|
191 | ImmutableList<Bid> partialbids = get(n - 1, subgoal);
|
---|
192 |
|
---|
193 | Bid bid = new Bid(issue, val);
|
---|
194 | ImmutableList<Bid> fullbids = new MapList<Bid, Bid>(
|
---|
195 | pbid -> pbid.merge(bid), partialbids);
|
---|
196 | if (!fullbids.size().equals(BigInteger.ZERO))
|
---|
197 | fulllist = new JoinedList<Bid>(fullbids, fulllist);
|
---|
198 | }
|
---|
199 | return fulllist;
|
---|
200 | }
|
---|
201 |
|
---|
202 | /**
|
---|
203 | * @param n the maximum issuevalue utility to include. Use n=index of last
|
---|
204 | * issue s= (#issues in the domain - 1) for the full range of this
|
---|
205 | * domain.
|
---|
206 | * @return Interval (min, max) of the total weighted utility Interval of
|
---|
207 | * issues 0..n. All weighted utilities have been rounded to the set
|
---|
208 | * {@link #precision}
|
---|
209 | */
|
---|
210 | private Interval getRange(int n) {
|
---|
211 | Interval value = Interval.ZERO;
|
---|
212 | for (int i = 0; i <= n; i++) {
|
---|
213 | value = value.add(issueInfo.get(i).getInterval());
|
---|
214 | }
|
---|
215 | return value;
|
---|
216 | }
|
---|
217 |
|
---|
218 | }
|
---|
219 |
|
---|
220 | /**
|
---|
221 | * List of all one-issue bids that have utility inside given interval.
|
---|
222 | */
|
---|
223 | class OneIssueSubset extends AbstractImmutableList<Bid> {
|
---|
224 | private final IssueInfo info;
|
---|
225 | private final Interval interval;
|
---|
226 | private BigInteger size;
|
---|
227 |
|
---|
228 | /**
|
---|
229 | *
|
---|
230 | * @param info the {@link IssueInfo}
|
---|
231 | * @param interval a utility interval (weighted)
|
---|
232 | */
|
---|
233 | OneIssueSubset(IssueInfo info, Interval interval) {
|
---|
234 | this.info = info;
|
---|
235 | this.interval = interval;
|
---|
236 | this.size = BigInteger.valueOf(info.subsetSize(interval));
|
---|
237 | }
|
---|
238 |
|
---|
239 | @Override
|
---|
240 | public Bid get(BigInteger index) {
|
---|
241 | return new Bid(info.getName(),
|
---|
242 | info.subset(interval).get(index.intValue()));
|
---|
243 | }
|
---|
244 |
|
---|
245 | @Override
|
---|
246 | public BigInteger size() {
|
---|
247 | return size;
|
---|
248 | }
|
---|
249 |
|
---|
250 | } |
---|