[127] | 1 | package parties.feedbackmediator.partialopponentmodel;
|
---|
| 2 |
|
---|
| 3 | import java.util.ArrayList;
|
---|
| 4 | import java.util.HashMap;
|
---|
| 5 | import java.util.List;
|
---|
| 6 | import java.util.Map;
|
---|
| 7 | import java.util.Random;
|
---|
| 8 |
|
---|
| 9 | import genius.core.AgentID;
|
---|
| 10 | import genius.core.Bid;
|
---|
| 11 | import genius.core.actions.GiveFeedback;
|
---|
| 12 | import genius.core.issue.Issue;
|
---|
| 13 | import genius.core.issue.Value;
|
---|
| 14 |
|
---|
| 15 | public class PartialPreferenceModels {
|
---|
| 16 | /*
|
---|
| 17 | * The models for each agent
|
---|
| 18 | */
|
---|
| 19 | private Map<AgentID, ValuePreferenceGraphMap> preferenceOrderingMap;
|
---|
| 20 | private List<Issue> issues;
|
---|
| 21 |
|
---|
| 22 | /**
|
---|
| 23 | *
|
---|
| 24 | * @param firstBid
|
---|
| 25 | * the first bid that was placed.
|
---|
| 26 | * @param feedbacks
|
---|
| 27 | * the feedbacks received on the first bid. This is only used to
|
---|
| 28 | * create {@link #preferenceOrderingMap}
|
---|
| 29 | */
|
---|
| 30 | public PartialPreferenceModels(Bid firstBid, List<GiveFeedback> feedbacks) {
|
---|
| 31 | // maybe we can get the bid directly and use also domain knowledge
|
---|
| 32 | // later...
|
---|
| 33 |
|
---|
| 34 | preferenceOrderingMap = new HashMap<>();
|
---|
| 35 |
|
---|
| 36 | issues = firstBid.getIssues();
|
---|
| 37 | // Add all agents in feedbacks to the {@link #preferenceOrderingMap}
|
---|
| 38 |
|
---|
| 39 | for (GiveFeedback feedback : feedbacks) {
|
---|
| 40 | AgentID partyID = feedback.getAgent();
|
---|
| 41 |
|
---|
| 42 | if (!preferenceOrderingMap.containsKey(partyID)) {
|
---|
| 43 | preferenceOrderingMap.put(partyID, new ValuePreferenceGraphMap(firstBid));
|
---|
| 44 | }
|
---|
| 45 | }
|
---|
| 46 |
|
---|
| 47 | }
|
---|
| 48 |
|
---|
| 49 | public void init() {
|
---|
| 50 |
|
---|
| 51 | }
|
---|
| 52 |
|
---|
| 53 | public void updateIssuePreferenceList(int issueIndex, Value previousValue, Value currentValue,
|
---|
| 54 | List<GiveFeedback> feedbacks) {
|
---|
| 55 |
|
---|
| 56 | /**
|
---|
| 57 | * Update all preferences with the new feedback
|
---|
| 58 | */
|
---|
| 59 | for (GiveFeedback feedback : feedbacks) {
|
---|
| 60 | preferenceOrderingMap.get(feedback.getAgent()).updateValuePreferenceGraph(issueIndex, previousValue,
|
---|
| 61 | currentValue, feedback.getFeedback());
|
---|
| 62 |
|
---|
| 63 | }
|
---|
| 64 | }
|
---|
| 65 |
|
---|
| 66 | public boolean mayImproveMajority(int issueIndex, Value previousValue, Value newValue) {
|
---|
| 67 |
|
---|
| 68 | int count = 0;
|
---|
| 69 |
|
---|
| 70 | for (ValuePreferenceGraphMap partyPreferenceMap : preferenceOrderingMap.values()) {
|
---|
| 71 |
|
---|
| 72 | if (partyPreferenceMap.isLessPreferredThan(issueIndex, newValue, previousValue))
|
---|
| 73 | count++;
|
---|
| 74 | }
|
---|
| 75 |
|
---|
| 76 | if (count < ((double) preferenceOrderingMap.size() / 2))
|
---|
| 77 | return true;
|
---|
| 78 | else
|
---|
| 79 | return false;
|
---|
| 80 | }
|
---|
| 81 |
|
---|
| 82 | public boolean mayImproveAll(int issueIndex, Value previousValue, Value newValue) {
|
---|
| 83 |
|
---|
| 84 | for (ValuePreferenceGraphMap partyPreferenceMap : preferenceOrderingMap.values()) {
|
---|
| 85 |
|
---|
| 86 | if (partyPreferenceMap.isLessPreferredThan(issueIndex, newValue, previousValue))
|
---|
| 87 | return false;
|
---|
| 88 | }
|
---|
| 89 | return false;
|
---|
| 90 | }
|
---|
| 91 |
|
---|
| 92 | public Value getNashValue(int issueIndex) {
|
---|
| 93 |
|
---|
| 94 | Value nashValue = null;
|
---|
| 95 | double nashProduct = -1.0;
|
---|
| 96 | double currentProduct;
|
---|
| 97 | /*
|
---|
| 98 | * if there exists only one value, return it.
|
---|
| 99 | */
|
---|
| 100 | if (getFirstPrefOrdering().getAllValues(issueIndex).size() == 1)
|
---|
| 101 | return getFirstPrefOrdering().getAllValues(issueIndex).get(0);
|
---|
| 102 |
|
---|
| 103 | for (Value currentValue : getFirstPrefOrdering().getAllValues(issueIndex)) {
|
---|
| 104 |
|
---|
| 105 | currentProduct = 1.0;
|
---|
| 106 | for (ValuePreferenceGraphMap valueMap : preferenceOrderingMap.values()) {
|
---|
| 107 | currentProduct *= valueMap.getEstimatedUtility(issueIndex, currentValue);
|
---|
| 108 | }
|
---|
| 109 | if (currentProduct > nashProduct) {
|
---|
| 110 | nashProduct = currentProduct;
|
---|
| 111 | nashValue = currentValue;
|
---|
| 112 | }
|
---|
| 113 | }
|
---|
| 114 |
|
---|
| 115 | return nashValue;
|
---|
| 116 |
|
---|
| 117 | }
|
---|
| 118 |
|
---|
| 119 | public ArrayList<Value> getNashValues(int issueIndex) {
|
---|
| 120 |
|
---|
| 121 | ArrayList<Value> nashValues = new ArrayList<Value>();
|
---|
| 122 | double nashProduct = -1;
|
---|
| 123 | double currentProduct;
|
---|
| 124 |
|
---|
| 125 | /*
|
---|
| 126 | * if there exists only one value, return it.
|
---|
| 127 | */
|
---|
| 128 | if (getFirstPrefOrdering().getAllValues(issueIndex).size() == 1)
|
---|
| 129 | nashValues.add(getFirstPrefOrdering().getAllValues(issueIndex).get(0));
|
---|
| 130 | else {
|
---|
| 131 |
|
---|
| 132 | for (Value currentValue : getFirstPrefOrdering().getAllValues(issueIndex)) {
|
---|
| 133 |
|
---|
| 134 | currentProduct = 1.0;
|
---|
| 135 | for (ValuePreferenceGraphMap valueMap : preferenceOrderingMap.values()) {
|
---|
| 136 | currentProduct *= valueMap.getEstimatedUtility(issueIndex, currentValue);
|
---|
| 137 | }
|
---|
| 138 | if (currentProduct > nashProduct) {
|
---|
| 139 | nashValues.clear();
|
---|
| 140 | nashProduct = currentProduct;
|
---|
| 141 | nashValues.add(currentValue);
|
---|
| 142 | } else if (currentProduct == nashProduct)
|
---|
| 143 | nashValues.add(currentValue);
|
---|
| 144 | }
|
---|
| 145 | }
|
---|
| 146 |
|
---|
| 147 | return nashValues;
|
---|
| 148 |
|
---|
| 149 | }
|
---|
| 150 |
|
---|
| 151 | public double estimateSumUtility(Bid currentBid) throws Exception {
|
---|
| 152 |
|
---|
| 153 | double utility = 0.0;
|
---|
| 154 | for (ValuePreferenceGraphMap valueMap : preferenceOrderingMap.values()) {
|
---|
| 155 | utility += valueMap.estimateUtility(currentBid);
|
---|
| 156 | }
|
---|
| 157 | return utility;
|
---|
| 158 |
|
---|
| 159 | }
|
---|
| 160 |
|
---|
| 161 | public double estimateProductUtility(Bid currentBid) throws Exception {
|
---|
| 162 |
|
---|
| 163 | double utility = 1;
|
---|
| 164 | for (ValuePreferenceGraphMap valueMap : preferenceOrderingMap.values()) {
|
---|
| 165 | utility *= valueMap.estimateUtility(currentBid);
|
---|
| 166 | }
|
---|
| 167 | return utility;
|
---|
| 168 |
|
---|
| 169 | }
|
---|
| 170 |
|
---|
| 171 | /**
|
---|
| 172 | * because of the time constraint, I wrote the simple sorting but not
|
---|
| 173 | * efficient (since there are no much nash bids, it will not be a problem)
|
---|
| 174 | */
|
---|
| 175 | public void sortBidsWrtSumUtility(ArrayList<Bid> bidList) throws Exception {
|
---|
| 176 |
|
---|
| 177 | for (int i = 0; i < bidList.size(); i++) {
|
---|
| 178 |
|
---|
| 179 | for (int j = i + 1; j < bidList.size(); j++) {
|
---|
| 180 |
|
---|
| 181 | if (estimateSumUtility(bidList.get(i)) < estimateSumUtility(bidList.get(j))) {
|
---|
| 182 | Bid temp = new Bid(bidList.get(i));
|
---|
| 183 | bidList.set(i, bidList.get(j));
|
---|
| 184 | bidList.set(j, temp);
|
---|
| 185 | }
|
---|
| 186 |
|
---|
| 187 | }
|
---|
| 188 | }
|
---|
| 189 | }
|
---|
| 190 |
|
---|
| 191 | /**
|
---|
| 192 | * because of the time constraint, I wrote the simple sorting but not
|
---|
| 193 | * efficient (since there are no much nash bids, it will not be a problem)
|
---|
| 194 | */
|
---|
| 195 | public void sortBidsWrtProductUtility(ArrayList<Bid> bidList) throws Exception {
|
---|
| 196 |
|
---|
| 197 | for (int i = 0; i < bidList.size(); i++) {
|
---|
| 198 |
|
---|
| 199 | for (int j = i + 1; j < bidList.size(); j++) {
|
---|
| 200 |
|
---|
| 201 | if (estimateProductUtility(bidList.get(i)) < estimateProductUtility(bidList.get(j))) {
|
---|
| 202 | Bid temp = new Bid(bidList.get(i));
|
---|
| 203 | bidList.set(i, bidList.get(j));
|
---|
| 204 | bidList.set(j, temp);
|
---|
| 205 | }
|
---|
| 206 |
|
---|
| 207 | }
|
---|
| 208 | }
|
---|
| 209 | }
|
---|
| 210 |
|
---|
| 211 | public ArrayList<Bid> estimatePossibleNashBids(Bid sampleBid) throws Exception {
|
---|
| 212 |
|
---|
| 213 | ArrayList<Bid> nashBids = new ArrayList<Bid>();
|
---|
| 214 | HashMap<Integer, ArrayList<Value>> nashIssueValues = new HashMap<Integer, ArrayList<Value>>();
|
---|
| 215 |
|
---|
| 216 | Bid firstBid = new Bid(sampleBid);
|
---|
| 217 |
|
---|
| 218 | for (Issue currentIssue : issues) {
|
---|
| 219 | nashIssueValues.put(currentIssue.getNumber(), getNashValues(currentIssue.getNumber()));
|
---|
| 220 | firstBid = firstBid.putValue(currentIssue.getNumber(),
|
---|
| 221 | nashIssueValues.get(currentIssue.getNumber()).get(0));
|
---|
| 222 | }
|
---|
| 223 |
|
---|
| 224 | nashBids.add(firstBid);
|
---|
| 225 |
|
---|
| 226 | int currentIndex;
|
---|
| 227 | for (Issue currentIssue : issues) {
|
---|
| 228 | currentIndex = currentIssue.getNumber();
|
---|
| 229 |
|
---|
| 230 | for (Value currentValue : nashIssueValues.get(currentIndex)) {
|
---|
| 231 |
|
---|
| 232 | for (int i = 0; i < nashBids.size(); i++) {
|
---|
| 233 | Bid currentBid = new Bid(nashBids.get(i));
|
---|
| 234 | currentBid = currentBid.putValue(currentIndex, currentValue);
|
---|
| 235 | if (!nashBids.contains(currentBid))
|
---|
| 236 | nashBids.add(currentBid);
|
---|
| 237 | }
|
---|
| 238 | }
|
---|
| 239 |
|
---|
| 240 | }
|
---|
| 241 |
|
---|
| 242 | sortBidsWrtSumUtility(nashBids);
|
---|
| 243 | return nashBids;
|
---|
| 244 | }
|
---|
| 245 |
|
---|
| 246 | public ArrayList<Value> getIncomparableValues(int issueIndex, Value currentValue) {
|
---|
| 247 |
|
---|
| 248 | ArrayList<Value> incomparableValues = new ArrayList<Value>();
|
---|
| 249 | Value incomparable;
|
---|
| 250 | for (ValuePreferenceGraphMap valueMap : preferenceOrderingMap.values()) {
|
---|
| 251 | incomparable = valueMap.getIncomparableValue(issueIndex, currentValue);
|
---|
| 252 | if (incomparable != null)
|
---|
| 253 | incomparableValues.add(incomparable);
|
---|
| 254 | }
|
---|
| 255 |
|
---|
| 256 | return incomparableValues;
|
---|
| 257 |
|
---|
| 258 | }
|
---|
| 259 |
|
---|
| 260 | public Value getIncomparableValue(int issueIndex, Value currentValue, Random random) {
|
---|
| 261 |
|
---|
| 262 | ArrayList<Value> incomparableValues = getIncomparableValues(issueIndex, currentValue);
|
---|
| 263 |
|
---|
| 264 | if (incomparableValues.size() == 0)
|
---|
| 265 | return null;
|
---|
| 266 |
|
---|
| 267 | return (incomparableValues.get(random.nextInt(incomparableValues.size())));
|
---|
| 268 |
|
---|
| 269 | }
|
---|
| 270 |
|
---|
| 271 | public ArrayList<Value> getAllPossibleValues(int issueIndex) {
|
---|
| 272 | return getFirstPrefOrdering().getAllValues(issueIndex);
|
---|
| 273 | }
|
---|
| 274 |
|
---|
| 275 | /**
|
---|
| 276 | * Find a value not yet used by first agent.
|
---|
| 277 | *
|
---|
| 278 | * @param issueIndex
|
---|
| 279 | * @return
|
---|
| 280 | */
|
---|
| 281 | public Value getMissingValue(int issueIndex) {
|
---|
| 282 | return getFirstPrefOrdering().getMissingValue(issueIndex);
|
---|
| 283 | }
|
---|
| 284 |
|
---|
| 285 | @Override
|
---|
| 286 | public String toString() {
|
---|
| 287 | StringBuffer buffy = new StringBuffer("Partial Preference Model");
|
---|
| 288 |
|
---|
| 289 | for (AgentID agentID : preferenceOrderingMap.keySet()) {
|
---|
| 290 | buffy.append("\n For party -" + agentID + "\n");
|
---|
| 291 | buffy.append(preferenceOrderingMap.get(agentID).toString());
|
---|
| 292 | }
|
---|
| 293 |
|
---|
| 294 | return (buffy.toString());
|
---|
| 295 |
|
---|
| 296 | }
|
---|
| 297 |
|
---|
| 298 | /**
|
---|
| 299 | * HACK Callers of this are using a hack: they use the first agent's info to
|
---|
| 300 | * access info that is shared between the agents.
|
---|
| 301 | *
|
---|
| 302 | * @return first agent's {@link #preferenceOrderingMap}
|
---|
| 303 | */
|
---|
| 304 | private ValuePreferenceGraphMap getFirstPrefOrdering() {
|
---|
| 305 | if (preferenceOrderingMap.isEmpty()) {
|
---|
| 306 | throw new IllegalStateException("no agents registered yet");
|
---|
| 307 | }
|
---|
| 308 | return preferenceOrderingMap.values().iterator().next();
|
---|
| 309 | }
|
---|
| 310 |
|
---|
[1] | 311 | } |
---|