1 | package genius.core.protocol;
|
---|
2 |
|
---|
3 | import java.util.ArrayList;
|
---|
4 | import java.util.Collection;
|
---|
5 | import java.util.List;
|
---|
6 | import java.util.Map;
|
---|
7 |
|
---|
8 | import genius.core.Bid;
|
---|
9 | import genius.core.actions.Accept;
|
---|
10 | import genius.core.actions.Action;
|
---|
11 | import genius.core.actions.Offer;
|
---|
12 | import genius.core.actions.OfferForVoting;
|
---|
13 | import genius.core.actions.Reject;
|
---|
14 | import genius.core.parties.NegotiationParty;
|
---|
15 | import genius.core.session.Round;
|
---|
16 | import genius.core.session.Session;
|
---|
17 | import 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 | */
|
---|
55 | public 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 | }
|
---|