source: design/mopac/MOPaC.tex@ 53

\documentclass{article}
\usepackage[utf8]{inputenc}

\usepackage{relsize}
\usepackage{xspace}
\usepackage[inline]{enumitem}

\usepackage{amsmath,amsfonts}

\usepackage{url}
\urlstyle{same}

\usepackage{xcolor}
\newcommand{\pkm}[1]{\textcolor{blue}{PKM: #1}}
\newcommand{\ml}[1]{\textcolor{red}{Ming: #1}}

\newtheorem{example}{Example}[section]

%\newcommand\mopac{AMOP\nolinebreak[4]\hspace{-.05em}\raisebox{.4ex}{\relsize{-3}{\textbf{$--$}}}}
%\newcommand\mopac{AMOP\texttt{--}\xspace}
\newcommand\mopac{MOPaC\xspace}

\title{MOPaC: The Multiple Offers Protocol for Multilateral Negotiations with Partial Consensus}



\author{Pradeep K. Murukannaiah and Catholijn M. Jonker and W.Pasman}

\begin{document}

\maketitle

\section{Introduction}

Multilateral 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.

\begin{example}
\label{ex:meeting}
Consider 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.
\end{example}

\begin{example}
\label{ex:government}
Consider 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.
\end{example}

\begin{example}
\label{ex:flatmate}
Consider 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.
\end{example}

This report contains two parts:
\begin{enumerate}
        \item A formal description of the protocol (section 2+3).
        \item A description of the implementation (section 4).
\end{enumerate}


\section{The {\mopac} Protocol}

%\subsection{Setting}

Let $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$.

%\subsection{Power}
Each 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:
\begin{equation}
    p_{max} = \sum_{i=1}^{n} p_i
\end{equation}

Let $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.

\subsection{Protocol}
A multilateral negotiation with the \mopac protocol runs for one or more rounds. Each round consists of the following phases.

\begin{description}[leftmargin=1em]
\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$.

After the bidding phase, each agent is communicated the bid and power of each agent. That is, the following list is communicated to each agent:
\begin{equation}
 \Big[ [ A_1, b_{1j}, p_1],~\ldots [ A_n, b_{nj}, p_n] \Big]
\end{equation}

\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:
\begin{enumerate}[label=(\arabic*),noitemsep]
    \item a \emph{minimum consensus threshold}, $C_{min}$: $p_{min} \le C_{min} \le p_{max} \in \mathbb{N}$, and
    \item  a \emph{maximum consensus threshold}, $C_{max}$, $C_{min} \le C_{max} \le p_{max} \in \mathbb{N}$.
\end{enumerate}

That is, the two possible votes an agent can provide on a bid $b_i$ (including the agent's own bid) are:
\begin{equation}
    v_i =
    \begin{cases}
      \langle b_i, \mathrm{accept}, C_{min}, C_{max} \rangle, \text{or} \\
      \langle b_i, \mathrm{reject} \rangle.
    \end{cases}
\end{equation}

By 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}).

After the voting phase,  each agent is communicated the votes of each agent. That is, the following list is communicated to each agent:
\begin{equation}
 \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]
\end{equation}

\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.
\begin{align}
\forall v_i: v_i &= \langle b_i, \mathrm{accept}, C_{min}, C_{max} \rangle,\\ \nonumber
v'_i &= \langle b_i, \mathrm{accept}, C_{min} \le C'_{min} \le p_{max}, C_{min} \le C'_{max} \le p_{max} \rangle.
\end{align}
%
However, an agent can \textsl{accept} a bid it had \textsl{reject}ed in the voting phase.
\begin{align}
\forall v_i: v_i &= \langle b_i, \mathrm{reject} \rangle,\\ \nonumber
v'_i &= 
\begin{cases}
      \langle b_i, \mathrm{reject} \rangle, \text{or} \\
      \langle b_i, \mathrm{accept}, p_{min} \le C'_{min} \le p_{max}, C'_{min} \le C'_{max} \le p_{max} \rangle.
\end{cases}
\end{align}

%Also, an agent can increase the $C_{min}$ value, and increase or decrease the $C_{max}$ value for any bid in the second round.

\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.

\begin{enumerate}[label=(\arabic*)]
    \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}).
    \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}).
\end{enumerate}

\end{description}

\section{Partial Consensus Formation}
\label{sec:partial-consensus}

Given 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:

\begin{equation}
    p_C = \sum_{A_i \in C} p_i.
\end{equation}

\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.

\subsection{Computing Viable Consensus Groups}
The 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.

\begin{enumerate}
    \item Enumerate all bids $b_i$ in a round.
    \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$. 
    
    $|C^A| = 2^n - n - 1$.
    
    \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.
\end{enumerate}

\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.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Implementation}

An implementation of the formal protocol is available in GeniusWeb.
The details differ from the formal definition, because it is more detailed, restricted and is object oriented rather than mathematical.

This section gives an overview of the classes involved with MOPaC. For all the fine details, please refer to the GeniusWeb javadoc and wiki pages.

\subsection{Protocol}
At 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. 

The \verb|MOPACSettings| object contains  a \verb|Deadline|, a List of \verb|TeamInfo| objects and a \verb|VotingEvaluator|.

The \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.

The 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. 

The \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.

The 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). 

The \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:

\begin{itemize}
        \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. 
        \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.
\end{itemize}


\subsection{The Party's side objects}
A 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:

\verb|SessionSettings|: The usual information to start up a session, containing the party's \verb|Parameters|, \verb|Profile| etc. 

\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|

\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. 

\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. 

In all phases, a party can decide to \verb|EndNegotiation|. This basically means the party walks away. Remaining parties just continue negotiating.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliographystyle{unsrt}
\bibliography{references}

\end{document}