source: design/mopac/MOPaC.tex@ 46

Last change on this file since 46 was 46, checked in by bart, 3 years ago

refactor to help reusing partiesserver

File size: 13.4 KB
Line 
1\documentclass{article}
2\usepackage[utf8]{inputenc}
3
4\usepackage{relsize}
5\usepackage{xspace}
6\usepackage[inline]{enumitem}
7
8\usepackage{amsmath,amsfonts}
9
10\usepackage{url}
11\urlstyle{same}
12
13\usepackage{xcolor}
14\newcommand{\pkm}[1]{\textcolor{blue}{PKM: #1}}
15\newcommand{\ml}[1]{\textcolor{red}{Ming: #1}}
16
17\newtheorem{example}{Example}[section]
18
19%\newcommand\mopac{AMOP\nolinebreak[4]\hspace{-.05em}\raisebox{.4ex}{\relsize{-3}{\textbf{$--$}}}}
20%\newcommand\mopac{AMOP\texttt{--}\xspace}
21\newcommand\mopac{MOPaC\xspace}
22
23\title{MOPaC: The Multiple Offers Protocol for Multilateral Negotiations with Partial Consensus}
24
25
26
27\author{Pradeep K. Murukannaiah and Catholijn M. Jonker and W.Pasman}
28
29\begin{document}
30
31\maketitle
32
33\section{Introduction}
34
35Multilateral negotiations enable group decisions involving two or more parties. The SAOP and AMOP protocols \cite{Aydogan-2017-ACAN-NegoProtocols} facilitate multilateral negotiations, but require a (full) consensus among parties. However, negotiations requiring full consensus can be too restrictive, e.g., in the following scenarios.
36
37\begin{example}
38\label{ex:meeting}
39Consider a meeting scheduling negotiation among $n$ ($>2$) parties. Ideally, we would like all parties to agree on the meeting but the meeting can take place even if a few parties cannot make it. That is, if there are no offers that all parties agree on, but there are offers that a (large) subset of the parties agree on, the negotiation can still succeed with a partial consensus.
40\end{example}
41
42\begin{example}
43\label{ex:government}
44Consider the process of coalition building in a multi-party political system \cite{Dupont-2996-IntNego-NegotiationasCoalitionBuilding}. In an election, $n$ ($>2$) parties contested, and a certain number of candidates won from each party. However, none of the parties have a majority, on their own. Thus, the parties must negotiate and build a coalition to form the government. A partial consensus is sufficient to build a successful coalition.
45\end{example}
46
47\begin{example}
48\label{ex:flatmate}
49Consider that a group of $n$ ($>2$) friends would like to share (rent) flats with each other during their visit to a city. Each person in the group has preferences on the characteristics of the flat he or she wants to rent and the characteristics of their flatmates. The friends engage in a negotiation to find suitable flatmates. This negotiation can yield more than one successful deal each involving a partial consensus among a subset of the friends.
50\end{example}
51
52This report contains two parts:
53\begin{enumerate}
54 \item A formal description of the protocol (section 2+3).
55 \item A description of the implementation (section 4).
56\end{enumerate}
57
58
59\section{The {\mopac} Protocol}
60
61%\subsection{Setting}
62
63Let $A$ be a set of $n$ agents in a multilateral negotiation. $\forall i, A_i: 0 < i \leq n$, $A_i$, identifies one of the agents, where $\forall i, j: 0 < i,j \leq n$ and $i \neq j \implies A_i \neq A_j$.
64
65%\subsection{Power}
66Each agent $A_i$ has a power $p_i \in \mathbb{N}$ in the negotiation. Thus, the power, $p$, of a full consensus among agents is:
67\begin{equation}
68 p_{max} = \sum_{i=1}^{n} p_i
69\end{equation}
70
71Let $p_{min}$ be the minimum power required for any (partial) consensus to form in this negotiation, which is sent as a parameter to the protocol.
72
73\subsection{Protocol}
74A multilateral negotiation with the \mopac protocol runs for one or more rounds. Each round consists of the following phases.
75
76\begin{description}[leftmargin=1em]
77\item [Bidding phase:] Let $B$ be a bidding space of $m$ possible bids. Each agent puts a bid on the table. Let $b_{ij} \in B$ be agent $A_i$'s bid in round $j$.
78
79After the bidding phase, each agent is communicated the bid and power of each agent. That is, the following list is communicated to each agent:
80\begin{equation}
81 \Big[ [ A_1, b_{1j}, p_1],~\ldots [ A_n, b_{nj}, p_n] \Big]
82\end{equation}
83
84\item [Voting phase:] Each agent votes (\textsl{accept}/\textsl{reject}) on each bid on the table. With each \textsl{accept} vote, an agent must indicate:
85\begin{enumerate}[label=(\arabic*),noitemsep]
86 \item a \emph{minimum consensus threshold}, $C_{min}$: $p_{min} \le C_{min} \le p_{max} \in \mathbb{N}$, and
87 \item a \emph{maximum consensus threshold}, $C_{max}$, $C_{min} \le C_{max} \le p_{max} \in \mathbb{N}$.
88\end{enumerate}
89
90That is, the two possible votes an agent can provide on a bid $b_i$ (including the agent's own bid) are:
91\begin{equation}
92 v_i =
93 \begin{cases}
94 \langle b_i, \mathrm{accept}, C_{min}, C_{max} \rangle, \text{or} \\
95 \langle b_i, \mathrm{reject} \rangle.
96 \end{cases}
97\end{equation}
98
99By accepting a bid $b_i$ with $C_{min} = m$ and $C_{max} = n$, an agent indicates that it will accept the bid $b_i$ if a partial consensus group of \emph{power} at least $m$ and at most $n$ forms around bid $b_i$ (Section~\ref{sec:partial-consensus}).
100
101After the voting phase, each agent is communicated the votes of each agent. That is, the following list is communicated to each agent:
102\begin{equation}
103 \Big[ [ A_1, \langle b_1, v_1 \rangle,~\ldots \langle b_m, v_m \rangle],~\ldots [ A_n, \langle b_1, v_1 \rangle,~\ldots \langle b_m, v_m \rangle] \Big]
104\end{equation}
105
106\item [Opt-in phase:] Each agent votes again, as before, but with constraints that an agent cannot \textsl{reject} or reduce the $C_{min}$ value of a bid it had \textsl{accept}ed in the voting phase. That is, if an agent accepted $b_i$ with vote $v_i$ in the voting phase, its vote for $b_i$ in the opt-in phase $v'_i$ should be as follows.
107\begin{align}
108\forall v_i: v_i &= \langle b_i, \mathrm{accept}, C_{min}, C_{max} \rangle,\\ \nonumber
109v'_i &= \langle b_i, \mathrm{accept}, C_{min} \le C'_{min} \le p_{max}, C_{min} \le C'_{max} \le p_{max} \rangle.
110\end{align}
111%
112However, an agent can \textsl{accept} a bid it had \textsl{reject}ed in the voting phase.
113\begin{align}
114\forall v_i: v_i &= \langle b_i, \mathrm{reject} \rangle,\\ \nonumber
115v'_i &=
116\begin{cases}
117 \langle b_i, \mathrm{reject} \rangle, \text{or} \\
118 \langle b_i, \mathrm{accept}, p_{min} \le C'_{min} \le p_{max}, C'_{min} \le C'_{max} \le p_{max} \rangle.
119\end{cases}
120\end{align}
121
122%Also, an agent can increase the $C_{min}$ value, and increase or decrease the $C_{max}$ value for any bid in the second round.
123
124\item [Continuation or termination:] There is more than one way a \mopac negotiation can terminate. The following are two potential options. In both of these options, the continuation or termination decision is made after computing the viable consensus groups at the end of the second round of voting.
125
126\begin{enumerate}[label=(\arabic*)]
127 \item Determine a viable consensus group with the largest power (see Section~\ref{sec:partial-consensus}). If there is a tie for the group with largest power, break the ties randomly. For the agents in the chosen viable consensus group, the negotiation terminates with a deal. For the remaining agents, the negotiation terminates without a deal. This kind of termination is ideal, e.g., when negotiating to schedule a meeting (Example~\ref{ex:meeting}) or form a government (Example~\ref{ex:government}).
128 \item Determine a viable consensus group with the largest power (see Section~\ref{sec:partial-consensus}). If there is a tie for the group with largest power, break the ties randomly. Determine if there are more viable groups consisting of the remaining agents. If so, the negotiation terminates with a deal for such agents, too. The remaining agents go to the next round of negotiation. The negotiation continues until the deadline or until one or no agent remains in this round, whichever happens first. This type of termination is ideal, e.g., when negotiation for flatmates (Example~\ref{ex:flatmate}).
129\end{enumerate}
130
131\end{description}
132
133\section{Partial Consensus Formation}
134\label{sec:partial-consensus}
135
136Given a set of agents $C = \{ A_1^C, \ldots A_m^C \}$, who each voted \textsl{accept} for a bid $b_i$, $C$ is a partial consensus group on $b_i$. The \textbf{power} of the consensus $C$ is:
137
138\begin{equation}
139 p_C = \sum_{A_i \in C} p_i.
140\end{equation}
141
142\noindent A consensus $C$ for a bid $b_i$ is \textbf{viable} iff $\forall A_i \in C$, $C_{min} \le p_C \le C_{max}$. That is, a viable consensus group for a bid $b_i$ consists of a set of agents that accepted $b_i$ and the power of the group is within the minimum and maximum consensus thresholds indicated by each agent in the group.
143
144\subsection{Computing Viable Consensus Groups}
145The following is a naive approach for computing all viable consensus groups at the end of a MOPaC round. Although naive, this approach should be computationally feasible for a small number (e.g., $n \le 10$) of agents.
146
147\begin{enumerate}
148 \item Enumerate all bids $b_i$ in a round.
149 \item Compute the set of all possible agent groups $C_P^A$ such that a group of agents $c_i \in C^A$ iff $c_i \in P^A$, the power set of $A$ and $|c_i| > 1$.
150
151 $|C^A| = 2^n - n - 1$.
152
153 \item For each bid $b_i$ and agent group $c_i$, determine if $c_i$ is (1) a consensus group, and (2) viable. If so, add $\langle b_i, c_i \rangle$ to the list of viable groups, and proceed.
154\end{enumerate}
155
156\textbf{Optimization note}: The apriori algorithm used in association analysis \cite{Tan-2006-DataMining} can be used to prune the search space. That is, if a set $c_i$ is not a consensus group, none of its subsets will form a consensus group.
157
158%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
159
160\section{Implementation}
161
162An implementation of the formal protocol is available in GeniusWeb.
163The details differ from the formal definition, because it is more detailed, restricted and is object oriented rather than mathematical.
164
165This section gives an overview of the classes involved with MOPaC. For all the fine details, please refer to the GeniusWeb javadoc and wiki pages.
166
167\subsection{Protocol}
168At the top level, the MOPaC protocol is implemented by the \verb|MOPAC| class. The state of the protocol is defined in the \verb|MOPACState|, which can be seriailized, eg to a log file to log the final outcome details. The initial \verb|MOPACState| is defined through the \verb|MOPACSettings| object.
169
170The \verb|MOPACSettings| object contains a \verb|Deadline|, a List of \verb|TeamInfo| objects and a \verb|VotingEvaluator|.
171
172The \verb|Deadline| is a mechanism to ensure termination. It does this by placing an absolute time limit, plus possibly a number-of-rounds limit, on the protocol. If one of the limits is exceeded, the negotiation will just stop, and all parties that did not reach a deal leave the negotiation without a deal.
173
174The implementation is very specific about handling termination, both of parties doing an action not allowed by the protocol, when it ends a negotiation (walks away) and when the deadline is reached. If a party has placed a \verb|Vote| or opted in, that vote or opt-in remains valid even after it terminates.
175
176The \verb|TeamInfo| is in the MOPaC case just a single \verb|Party| plus its \verb|Profile| and its \verb|Parameters|. The Parameters is where the power of each party will be set, with key "power" and an integer as value. Parameters are optional, power=1 if not set. There may be other, party-specific parameters present.
177
178The protocol keeps track of the phase using the \verb|OfferPhase| (parties are expected to bid), \verb|VotingPhase| (parties are expected to vote) and \verb|OptInPhase| (parties are expected to opt in).
179
180The \verb|VotingEvaluator| is an implementation of the Partial Consensus Formation procedure of section 3. However it is much more detailed and has a few variants. \verb|VotingEvaluator| basically is a function that takes a set of \verb|CollectedVotes| and can determine the \verb|Agreements|. There are two \verb|VotingEvaluator| types:
181
182\begin{itemize}
183 \item \verb|LargestAgreement|: the negotiation ends as soon as a consensus group can be formed, with the consensus that has the largest total power as outcome.
184 \item \verb|LargestAgreementsLoop|: if a consensus group can be formed, create the consensus group with the largest total power. Remove the parties in the consensus group from the negotiation. If parties remain, repeat. If less than 2 parties remain, the negotiation ends. Otherwise, negotiation continues with the remaining parties.
185\end{itemize}
186
187
188\subsection{The Party's side objects}
189A negotiation party usually sees very little of all the protocol details: it just waits for a message from the protocol on what is expected next, and then acts accordingly. These messages are communicated through a number of objects:
190
191\verb|SessionSettings|: The usual information to start up a session, containing the party's \verb|Parameters|, \verb|Profile| etc.
192
193\verb|YourTurn|: the party receives this object to indicate the start of the Bidding phase of the protocol. Normally the party responds with an \verb|Offer|
194
195\verb|Voting|: the party receives this when it's time to vote on the bids on the table.Normally the party responds with a \verb|Votes| containing every \verb|~Vote| that it can accept.
196
197\verb|OptIn|. The party receives this when it's time to opt in. The party again normally responds with a \verb|Votes| object with a number of \verb|Vote| objects. If a \verb|Vote| was already voted for in the previous phase, the new Vote must extend the old Vote: iit must accept at least the same as the previous phase, to ensure that parties can not back off from a deal they already voted for.
198
199In all phases, a party can decide to \verb|EndNegotiation|. This basically means the party walks away. Remaining parties just continue negotiating.
200
201
202%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
203\bibliographystyle{unsrt}
204\bibliography{references}
205
206\end{document}
Note: See TracBrowser for help on using the repository browser.