source: src/main/java/genius/core/protocol/AlternatingMultipleOffersProtocol.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: 9.7 KB
Line 
1package genius.core.protocol;
2
3import java.util.ArrayList;
4import java.util.Collection;
5import java.util.List;
6import java.util.Map;
7
8import genius.core.Bid;
9import genius.core.actions.Accept;
10import genius.core.actions.Action;
11import genius.core.actions.Offer;
12import genius.core.actions.OfferForVoting;
13import genius.core.actions.Reject;
14import genius.core.parties.NegotiationParty;
15import genius.core.session.Round;
16import genius.core.session.Session;
17import genius.core.session.Turn;
18
19/**
20 * Implementation of an alternating offer protocol using voting consensus.
21 * <p/>
22 * Protocol in short:
23 *
24 * <pre>
25 * Round 1: Each agent makes their own offer.
26 * Round 2: Each agent votes (accept/reject) for each offer on the table.
27 *
28 * If there is one offer that everyone accepts, the negotiation ends with this offer.
29 * Otherwise, the process continues until reaching deadline or agreement.
30 * </pre>
31 *
32 * <h1>Detailed description</h1>
33 * <p>
34 *
35 *
36 * The AMOP protocol is an alternating offers protocol in which all players get
37 * the same opportunities. That is, every bid that is made in a round is
38 * available to all agents before they vote on these bids. This implemented in
39 * the following way: The AMOP protocol has a bidding phase followed by voting
40 * phases. In the bidding phase all negotiators put their offer on the table. In
41 * the voting phases all participants vote on all of the bids on the negotiation
42 * table. If one of the bids on the negotiation table is accepted by all of the
43 * parties, then the negotiation ends with this bid. This is an iterative
44 * process continuing until reaching an agreement or reaching the deadline. The
45 * essential difference with the SAOP protocol is that the players do not
46 * override the offers made by others and the agents can take all offers into
47 * account before they vote on the proposals.
48 * </p>
49 *
50 * @author David Festen
51 * @author Reyhan Aydogan
52 * @author Catholijn Jonker
53 * @author W.Pasman modification to improve testability
54 */
55public class AlternatingMultipleOffersProtocol extends DefaultMultilateralProtocol {
56 // keeps track of max number of accepts that an offer got.
57 // this value never resets. It should not be here.
58 private int maxNumberOfVotes = 0;
59
60 /**
61 * Get the round structure used by this algorithm.
62 * <p/>
63 * Structure:
64 *
65 * <pre>
66 * Round 1: Each agent makes their own offer.
67 * Round 2: Each agent votes (accept/reject) for each offer on the table.
68 * </pre>
69 *
70 * @param parties
71 * The parties currently participating
72 * @param session
73 * The complete session history
74 * @return A list of possible actions
75 */
76 @Override
77 public Round getRoundStructure(List<NegotiationParty> parties, Session session) {
78 Round round = createRound();
79
80 // NOTE: while roundnumber is normally one-based, in this function it's
81 // zero based as you are initializing the
82 // new round right in this function
83 if (session.getRoundNumber() % 2 == 0) {
84 // request an offer from each party
85 for (NegotiationParty party : parties) {
86 round.addTurn(createTurn(party, OfferForVoting.class));
87 }
88 } else {
89 ArrayList<Class<? extends Action>> acceptOrReject = new ArrayList<Class<? extends Action>>(2);
90 acceptOrReject.add(Accept.class);
91 acceptOrReject.add(Reject.class);
92
93 // request a reaction on each offer from party
94 for (NegotiationParty votedOnParty : parties) {
95 for (NegotiationParty votingParty : parties) {
96 round.addTurn(createTurn(votingParty, acceptOrReject));
97 }
98 }
99 }
100 return round;
101 }
102
103 @Override
104 public boolean isFinished(Session session, List<NegotiationParty> parties) {
105 // if we are making new offers, we are never finished
106 if (session.getRoundNumber() < 2 || !isVotingRound(session)) {
107 return false;
108 }
109
110 // find an acceptable offer
111 Round thisRound = session.getMostRecentRound();
112 Round prevRound = session.getRounds().get(session.getRoundNumber() - 2);
113 Offer acceptedOffer = acceptedOffer(thisRound, prevRound);
114
115 // if null, we are not finished, otherwise we are
116 return acceptedOffer != null;
117 }
118
119 /**
120 * Gets the current agreement if any. This assumes that the session contains
121 * {@link Round}s containing offer, votes, offer, votes, etc in this order.
122 * An agreement consists an {@link Offer} that was {@link Accept}ed by all
123 * the votes. See also {@link #acceptedOffer(Round, Round)}.
124 *
125 * @param session
126 * The complete session history up to this point
127 * @return The agreement bid or null if none
128 */
129 @Override
130 public Bid getCurrentAgreement(Session session, List<NegotiationParty> parties) {
131 int round = session.getRoundNumber();
132 if (round % 2 == 1 || round < 2) {
133 return null;
134 }
135 Round thisRound = session.getMostRecentRound();
136 Round prevRound = session.getRounds().get(session.getRoundNumber() - 2);
137 Offer acceptedOffer = acceptedOffer(thisRound, prevRound);
138 return acceptedOffer == null ? null : acceptedOffer.getBid();
139 }
140
141 /**
142 * returns the first offer in the given {@link Round} that everyone
143 * accepted, or null if no such offer.
144 *
145 * @param votingRound
146 * the round with the voting ({@link Accept} or {@link Reject})
147 * actions. The turns in votingRound must contain the following:
148 * (N is the number of turns in the offer round)
149 * <p>
150 * vote(party1,offer1), vote(party2, offer1), ..., vote(partyN,
151 * offer1), vote(party1, offer2), ......, vote(party1, offerN),
152 * ... , vote(partyN, offerN)
153 * </p>
154 * We only consider offers that ALL N parties have voted on.
155 * @param offerRound
156 * the round with the offers (one for each party is expected).
157 * @return The first accepted offer (all parties accepted the offer) if such
158 * an offer exists, null otherwise.
159 * @throws IllegalArgumentException
160 * if the offerRound contains {@link Action}(s) not extending
161 * {@link Offer}
162 */
163 protected Offer acceptedOffer(Round votingRound, Round offerRound) {
164 allActionsAreOffers(offerRound);
165 int numOffers = offerRound.getActions().size();
166 if (numOffers == 0) {
167 return null;
168 }
169 List<Turn> turns = votingRound.getTurns();
170 List<Action> voteActions = offerRound.getActions();
171
172 int availableOfferRounds = Math.min(numOffers, turns.size() / numOffers);
173
174 for (int offerNumber = 0; offerNumber < availableOfferRounds; offerNumber++) {
175 // update the maxNumberOfVotes we got
176 maxNumberOfVotes = Math.max(maxNumberOfVotes, nrOfVotes(numOffers, turns, offerNumber));
177
178 // if enough votes, accept bid
179 if (maxNumberOfVotes == numOffers) {
180 return (Offer) voteActions.get(offerNumber);
181 }
182
183 }
184
185 return null;
186 }
187
188 /**
189 *
190 * @param numOffers
191 * the number of offers on the table (in each turn)
192 * @param turns
193 * all the voting turns
194 * @param offerNumber
195 * the offer number that is being checked.
196 * @return number of {@link Accept}s for given offer number
197 */
198 protected int nrOfVotes(int numOffers, List<Turn> turns, int offerNumber) {
199 int votes = 0;
200 // count number of votes
201 for (int voteNr = 0; voteNr < numOffers; voteNr++) {
202 // count the vote
203 if (turns.get(offerNumber * numOffers + voteNr).getAction() instanceof Accept) {
204 votes++;
205 }
206 }
207 return votes;
208 }
209
210 /**
211 * Checks if all actions are offers.
212 *
213 * @throws IllegalArgumentException
214 * if not.
215 * @param offerRound
216 */
217 protected void allActionsAreOffers(Round offerRound) {
218 for (Action action : offerRound.getActions()) {
219 if (!(action instanceof Offer)) {
220 throw new IllegalArgumentException(
221 "encountered an action " + action + " in the offer round, which is not an Offer");
222 }
223 }
224 }
225
226 /**
227 * Returns whether this is a voting round. First voting round is even round
228 * and >= 2.
229 *
230 * @param session
231 * the current state of this session
232 * @return true is this is an even round > 0.
233 */
234 protected boolean isVotingRound(Session session) {
235 return session.getRoundNumber() > 0 && session.getRoundNumber() % 2 == 0;
236 }
237
238 /**
239 * Gets the maximum number of vote this protocol found.
240 *
241 * @param session
242 * the current state of this session
243 * @param parties
244 * The parties currently participating
245 * @return the number of parties agreeing to the current agreement
246 */
247 @Override
248 public int getNumberOfAgreeingParties(Session session, List<NegotiationParty> parties) {
249 return maxNumberOfVotes;
250 }
251
252 @Override
253 public Map<NegotiationParty, List<NegotiationParty>> getActionListeners(List<NegotiationParty> parties) {
254 return listenToAll(parties);
255 }
256
257 /******************************************/
258
259 /**
260 * factory function. To support testing.
261 *
262 * @param votingParty
263 * @param allowedActions
264 * list of allowed action classes
265 * @return a new {@link Turn} with given actions as possible actions.
266 */
267 public Turn createTurn(NegotiationParty votingParty, Collection<Class<? extends Action>> allowedActions) {
268 return new Turn(votingParty, allowedActions);
269 }
270
271 /**
272 * create factory function. To support testing.
273 *
274 * @param party
275 * @param allowedAction
276 * the class of action that is possible.
277 * @return a new {@link Turn} with given action as possible actions.
278 */
279 public Turn createTurn(NegotiationParty party, Class<? extends Action> allowedAction) {
280 return new Turn(party, allowedAction);
281 }
282
283 /**
284 * factory function. To support testing.
285 *
286 * @return round
287 */
288 public Round createRound() {
289 return new Round();
290 }
291
292}
Note: See TracBrowser for help on using the repository browser.