1 | import copy
|
---|
2 | from decimal import Decimal
|
---|
3 | from geniusweb.bidspace.AllBidsList import AllBidsList
|
---|
4 | from geniusweb.bidspace.BidsWithUtility import BidsWithUtility
|
---|
5 | from geniusweb.bidspace.Interval import Interval
|
---|
6 | from geniusweb.issuevalue.Bid import Bid
|
---|
7 | from geniusweb.issuevalue.Domain import Domain
|
---|
8 | from geniusweb.profile.utilityspace.LinearAdditiveUtilitySpace import (
|
---|
9 | LinearAdditiveUtilitySpace,
|
---|
10 | )
|
---|
11 | from .opponent_model import OpponentModel
|
---|
12 | from .time_estimator import TimeEstimator
|
---|
13 |
|
---|
14 | # Debug flags for testing
|
---|
15 | test_use_updates = True
|
---|
16 | test_use_safety = True
|
---|
17 |
|
---|
18 | class BidChooser():
|
---|
19 | def __init__(self, profile: LinearAdditiveUtilitySpace, opponent_model: OpponentModel, lowest_acceptable: float):
|
---|
20 | self.profile = profile
|
---|
21 | self.domain = profile.getDomain()
|
---|
22 | self.opponent_model = opponent_model
|
---|
23 | self.lowest_acceptable = lowest_acceptable
|
---|
24 | self.lowest_with_bids = lowest_acceptable
|
---|
25 | self.count = 0
|
---|
26 | self.UPDATE_PERIOD = 100
|
---|
27 | self.FLOAT_ERROR = 0.00001
|
---|
28 |
|
---|
29 | self.all_values = None
|
---|
30 | self.opponent_best_values = None
|
---|
31 | self.max_n_values = None
|
---|
32 | bid_dict = {}
|
---|
33 | for issue, valueset in self.profile.getUtilities().items():
|
---|
34 | bid_dict[issue] = max(self.domain.getValues(issue), key = lambda v: valueset.getUtility(v))
|
---|
35 | best_bid = Bid(bid_dict)
|
---|
36 | self.bid_pool = [(best_bid, 1.0)]
|
---|
37 |
|
---|
38 | self.best_received_bid = None
|
---|
39 | self.best_received_util = 0.0
|
---|
40 | self.counting_down = False
|
---|
41 | self.countdown = None
|
---|
42 |
|
---|
43 | self.initialize_global()
|
---|
44 |
|
---|
45 | def initialize_global(self):
|
---|
46 | self_utilities = self.profile.getUtilities()
|
---|
47 |
|
---|
48 | # Generate all values (not needed)
|
---|
49 | all_values = {issue: [v for v in valueset] for issue, valueset in self.domain.getIssuesValues().items()}
|
---|
50 | for issue in self.domain.getIssues():
|
---|
51 | values = self.domain.getValues(issue)
|
---|
52 | valueset_utilities = self_utilities[issue]
|
---|
53 | all_values[issue] = {v: float(valueset_utilities.getUtility(v)) for v in values}
|
---|
54 | all_values[issue] = dict(sorted(all_values[issue].items(), key = lambda v: v[1], reverse = True))
|
---|
55 |
|
---|
56 | self.all_values = all_values
|
---|
57 |
|
---|
58 | def update_bid(self, bid: Bid):
|
---|
59 | if not test_use_updates:
|
---|
60 | return None
|
---|
61 | if self.best_received_bid is None or self.best_received_util < float(self.profile.getUtility(bid)):
|
---|
62 | self.best_received_bid = bid
|
---|
63 | self.best_received_util = float(self.profile.getUtility(bid))
|
---|
64 | old_lowest = self.lowest_with_bids
|
---|
65 | self.lowest_with_bids = max(self.best_received_util, self.lowest_acceptable)
|
---|
66 | if self.lowest_with_bids != old_lowest and self.bid_pool is not None:
|
---|
67 | self._regenerate_bid_pool()
|
---|
68 |
|
---|
69 | def update_lowest_acceptable(self, lowest_acceptable: float):
|
---|
70 | self.lowest_acceptable = lowest_acceptable
|
---|
71 | old_lowest = self.lowest_acceptable
|
---|
72 | self.lowest_with_bids = max(lowest_acceptable, self.best_received_util)
|
---|
73 | if old_lowest != self.lowest_with_bids:
|
---|
74 | self._regenerate_bid_pool()
|
---|
75 |
|
---|
76 | def choose_bid(self, offers_left: int, time: float):
|
---|
77 | self._update_bid_pool()
|
---|
78 | if not self.counting_down:
|
---|
79 | if offers_left < len(self.bid_pool) * 2:
|
---|
80 | self.counting_down = True
|
---|
81 | self.countdown = min(len(self.bid_pool), offers_left)
|
---|
82 | else:
|
---|
83 | return self.bid_pool[-1][0]
|
---|
84 | if self.counting_down:
|
---|
85 | self.countdown -= 1
|
---|
86 | if test_use_safety: # No matter how bad the time estimate is, don't concede faster than linear in bid order
|
---|
87 | self.countdown = max(self.countdown, int((1.0 - time) * len(self.bid_pool)))
|
---|
88 | if self.countdown > offers_left * 2:
|
---|
89 | self.countdown = offers_left * 2
|
---|
90 | if self.countdown < offers_left / 2: # TODO consider not reassigning value if offers_left is properly low (10 or fewer?)
|
---|
91 | self.countdown = int(offers_left / 2)
|
---|
92 | if self.countdown >= len(self.bid_pool):
|
---|
93 | return self.bid_pool[-1][0]
|
---|
94 | return self.bid_pool[max(self.countdown, 0)][0]
|
---|
95 |
|
---|
96 | def _update_bid_pool(self):
|
---|
97 | self.count += 1
|
---|
98 | if self.count % self.UPDATE_PERIOD == 0 or self.count == 1:
|
---|
99 | self._regenerate_bid_pool()
|
---|
100 |
|
---|
101 | def _regenerate_bid_pool(self):
|
---|
102 | self._construct_opponent_best_values()
|
---|
103 | self._construct_max_n(n = 2)
|
---|
104 | self._construct_bid_pool(lowest_acceptable = self.lowest_with_bids - self.FLOAT_ERROR)
|
---|
105 |
|
---|
106 | def _construct_opponent_best_values(self):
|
---|
107 | self_utilities = self.profile.getUtilities()
|
---|
108 |
|
---|
109 | # Generate all values at least as good as opponnet's best
|
---|
110 | # Should still be sorted
|
---|
111 | self.opponent_best_values = {}
|
---|
112 | for issue in self.all_values:
|
---|
113 | opp_val_utils = self.opponent_model.get_value_utils(issue)
|
---|
114 | self_val_utils = self_utilities[issue]
|
---|
115 | opp_best_value = max(opp_val_utils, key = lambda v: opp_val_utils[v])
|
---|
116 | opp_best_self_util = self.all_values[issue][opp_best_value]
|
---|
117 | self.opponent_best_values[issue] = {v: self_util for v, self_util in self.all_values[issue].items() if self_util >= opp_best_self_util}
|
---|
118 |
|
---|
119 | def _construct_max_n(self, n: int):
|
---|
120 | # Max n includes our best, their best, and up to n - 2 more
|
---|
121 | # Current implementation uses our best n - 2.
|
---|
122 | # TODO Consider using some other method such as their second / third best
|
---|
123 | self.max_n_values = {}
|
---|
124 | for issue, values in self.opponent_best_values.items():
|
---|
125 | val_count = len(values)
|
---|
126 | self.max_n_values[issue] = {}
|
---|
127 | for i, (value, util) in enumerate(values.items()):
|
---|
128 | if i < n - 1 or i == val_count - 1:
|
---|
129 | self.max_n_values[issue][value] = util
|
---|
130 |
|
---|
131 | def _construct_bid_pool(self, lowest_acceptable: float):
|
---|
132 | issue_weights = {issue: float(self.profile.getWeight(issue)) for issue in list(self.max_n_values.keys())}
|
---|
133 | issue_weights_sorted = dict(sorted(issue_weights.items(), key = lambda i: i[1], reverse = True))
|
---|
134 | issue_list = list(issue_weights_sorted.keys())
|
---|
135 | new_bid_pool = []
|
---|
136 | self._recur(self.max_n_values, issue_list, issue_weights_sorted, [], 1.0 - lowest_acceptable, new_bid_pool)
|
---|
137 | new_bid_pool = sorted([(bid, float(self.profile.getUtility(bid))) for bid in new_bid_pool], key = lambda bid: bid[1])
|
---|
138 | if self.best_received_util == self.lowest_with_bids:
|
---|
139 | last_bid = new_bid_pool[-1][0]
|
---|
140 | if last_bid != self.best_received_bid:
|
---|
141 | new_bid_pool.insert(0, ((self.best_received_bid, float(self.profile.getUtility(self.best_received_bid)))))
|
---|
142 | self.bid_pool = new_bid_pool
|
---|
143 |
|
---|
144 | def _recur(self, max_n_values: dict, issue_list: list, issue_weights: dict, bid: list, accumulated_loss: float, bids: list):
|
---|
145 | issue = issue_list[len(bid)]
|
---|
146 | last = len(bid) == len(issue_list) - 1
|
---|
147 | weight = issue_weights[issue]
|
---|
148 | for value, util in max_n_values[issue].items():
|
---|
149 | new_accumulated_loss = accumulated_loss - weight * (1.0 - util)
|
---|
150 | if new_accumulated_loss < 0.0:
|
---|
151 | continue
|
---|
152 | if not last:
|
---|
153 | new_bid = copy.copy(bid)
|
---|
154 | new_bid.append((issue, value))
|
---|
155 | self._recur(max_n_values, issue_list, issue_weights, new_bid, new_accumulated_loss, bids)
|
---|
156 | if last:
|
---|
157 | last_bid = copy.copy(bid)
|
---|
158 | last_bid.append((issue, value))
|
---|
159 | bids.append(Bid(dict(last_bid)))
|
---|
160 |
|
---|