[75] | 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 |
|
---|