\documentclass{coopgames}
\usepackage{amsmath,amssymb,amsthm,amsfonts,mathrsfs,pifont}
\newtheorem{theo}{Theorem}
\newtheorem{definition}{Definition}[section]

\newcommand{\real}{{\mathbb R}}
\newcommand{\scr}[1]{\mathscr #1}
\newcommand{\C}[0]{{\cal C}}
\newcommand{\argmax}{\mbox{arg}\hspace{-2.5pt}\max}
\newcommand{\CS}{{\cal S}}
\newcommand{\ok}{\ding{52}}
\newcommand{\imp}{{\cal I}mp}



\title{Some Notes on Cooperative Games} 


\author{St\'ephane Airiau \\ 
{ \tt{s.airiau@uva.nl}}\\ \ \\
{  Institute for Logic, Language \& Computation} \\
{  Universiteit van Amsterdam, The Netherlands} 
}
\date{}

\begin{document}
%\maketitle



\section{TU games}
\label{sec:TU}

The game theory community has extensively studied the coalition
formation problem~\cite{Kahan84:Theories,Osborne94:Course}.  The
literature is divided into two main models, depending on whether
utility can be transferred between individuals.  In a transferable
utility game (or TU game), it is assumed that agents can compare their
utility and that a common scale of utility exists. In this case, it is
possible to define a value for a coalition as the worth the coalition
can achieve through cooperation. The agents have to share the value of
the coalition, hence utility needs to be transferable.  In a so-called
non-transferable utility game (or NTU game), inter-personal comparison
of utility is not possible, and agents have a preference over the
different coalitions of which it is a member. In this section, we
introduce the TU games.


\subsection{Definitions}

In the following, we use a utility-based approach and we assume that
``everything has a price'': each agent has a utility function that is
expressed in currency units.  The use of a common currency enables the
agents to directly compare alternative outcomes, and it also enables
side payments.  The definition of a TU game is simple: it involves a
set of players and a characteristic function (a map from sets of
agents to real numbers) which represents the value that a coalition
can achieve. The characteristic function is common knowledge and the
value of a coalition depends only on the other players present in its
coalition.

\subsubsection{Notations and types of TU games}

We consider a set $N$ of $n$ agents. A \emph{coalition} is a non-empty
subset of $N$.  The set $N$ is also known as the \emph{ grand
  coalition}.  The set of all coalitions is $2^N$ and its
cardinality is $2^n$.  A \emph{coalition structure (CS)} ${\cal S}=\{
{\cal C}_1, \cdots, {\cal C}_m \}$ is a partition of $N$: each set
${\cal C}_i$ is a coalition with $\cup_{i=1}^m {\cal C}_i = N$ and $ i
\neq j \Rightarrow {\cal C}_i \cap {\cal C}_j = \emptyset$.  We will
denote $\scr{S}_\C$ the set of all partitions of a set of agnets $\C
\subseteq N$. The set of all CSs is then denoted as $\scr{S}_N$, its
size is of the order $O(n^n)$ and
$\omega(n^\frac{n}{2})$~\cite{Sandholm99:Coalition}.  The \emph{
  characteristic function} (or \emph{ valuation function}) $v: 2^N \to
{\mathbb R}$ provides the worth or utility of a coalition.  Note that
this definition assumes that the valuation of a coalition $\cal C$
does not depend on the other coalitions present in the population.

\begin{definition}[TU game] A transferable utility game (TU game) is
  defined as a pair $(N,v)$ where $N$ is the set of agents, and $v: 2^N
  \to {\mathbb R}$ is a characteristic function.
\end{definition}

A first example of a TU game is the \emph{majority game}.  Assume that
the number of agents $n$ is odd and that the agents decide between two
alternatives using a majority vote. Also assume that no agent is
indifferent, i.e., an agent always strictly prefers one alternative
over the other. We model this by assigning to a ``winning coalition''
the value 1 and to the other ones the value 0, i.e.,
$$v({\cal C}) =\left\{\begin{tabular}{l} 1 when $|{\cal C}| >  \frac{n}{2}$ \\ $0$
    otherwise \end{tabular} \right.$$ 

We now describes some types of valuation functions.
\begin{description}
\item[Additive (or inessential):] $\forall {\cal C}_1, {\cal C}_2 \subseteq N \; |
  \; {\cal C}_1 \cap {\cal C}_2= \emptyset$ , $v({\cal C}_1 \cup {\cal
    C}_2) = v({\cal C}_1) + v({\cal C}_2)$.  When a TU game is additive, $v({\cal C}) = \sum_{i \in
    {\cal C}} v(i)$, i.e., the worth of each coalition is the same
  whether its members cooperate or not: there is no gain in
  cooperation or any synergies between coalitions, which explains the
  alternative name (inessential) used for such games.

\item[Superadditive:] $\forall {\cal C}_1, {\cal C}_2 \subseteq N \; |
  \; {\cal C}_1 \cap {\cal C}_2= \emptyset$ , $v({\cal C}_1 \cup {\cal
    C}_2) \geq v({\cal C}_1) + v({\cal C}_2)$, in other words, any
  pair of coalitions is best off by merging into one.  In such
  environments, social welfare is maximised by forming the grand
  coalition.
\item[Subadditive:] $\forall {\cal C}_1, {\cal C}_2 \subseteq N \; |
  \; {\cal C}_1 \cap {\cal C}_2= \emptyset$ , $v({\cal C}_1 \cup {\cal
    C}_2) \leq v({\cal C}_1) + v({\cal C}_2)$: the agents are best off
  when they are on their own, i.e., cooperation not desirable.
\item[Convex games:] First let us call $v({\cal C} \cup \{i\}) - v({\cal C})$ the
  marginal contribution of a player $i$ to coalition~${\cal C}$, i.e., it is
  the increase of value of coalition ${\cal C}$ due to the presence of agent
  $i$.  We call then a valuation convex if for all ${\cal C} \subseteq T$ and
  $i \notin T$ $v({\cal C} \cup \{i\}) - v({\cal C}) \leq v(T \cup \{i\}) - v(T)$. So a
  valuation function is convex when the marginal contribution of each
  player increases with the size of the coalition he joins. Convex
  valuation functions are superadditive.
\item[Monotonic] A function is monotonic when $\forall \C_1 \subseteq
  \C_2 \subseteq N$, $v(C_1) \leq v(C_2)$. In other words, when more
  agents join a coalition, the value of the larger coalition is at
  least the value of the smaller one. For example, the valuation
  function of the majority game is monotonic: when more agents join a
  coalition, they cannot turn the coalition from a winning to a losing
  one.
\item[Unconstrained.] The valuation function can be superadditive for
  some coalitions, and subadditive for others: some coalitions should
  merge when others should remain separated.  This is the most
  difficult and interesting environment.
%why
\end{description}



The valuation function provides a value to a set of agents, not to
individual agents. The \emph{payoff distribution} $x=\{x_1,\cdots, x_n
\}$ describes how the worth of the coalition is shared between the
agents, where $x_i$ is the payoff of agent $i$.  We also use the
notation $x({\cal C}) = \sum_{i \in {\cal C}} x(i)$. A \emph{payoff
  configuration (PC)} is a pair $({\cal S}, x)$ where ${\cal S} \in
\scr{S}_N$ is a CS and $x$ is a payoff distribution. Given a TU game
$(N,v)$ as an input, the \emph{fundamental question} is what PC will
form: what are the coalitions that will form and how to distribute the
worth of the coalition (see Figure~\ref{fig:fundamental}).

\begin{table}[h]
\begin{center}
$N=\{1,2,3\}$ \\
$v(\{1\})=0$, $v(\{2\})=0$, $v(\{3\})=0$\\
$v(\{1,2\}) = 90$ \\
$v(\{1,3\}) = 80$ \\
$v(\{2,3\}) = 70$ \\
$v(\{1,2,3\}) =105$ \\
\end{center}
\caption{An example of a TU game}
\label{ex:TUgame}
\end{table}

Let us go over the TU game in Table~\ref{ex:TUgame}. In this example,
there are three agents named $1$, $2$ and $3$. There are 7 possible
coalitions and the value of each coalition is given in the table.
There are 5 CSs which are the following: $\{\{1\}, \{2\}, \{3\}\}$,
$\{\{1, 2\}, \{3\}\}$, $\{\{1\},\{2, 3\}\}$, $\{\{2\}, \{1, 3\}\}$,
$\{\{1,2,3\}\}$. What PC should be chosen? Should the agents form the
grand coalition and share equally the value? The choice of the
coalition can be justified by arguing that it is the coalition that
generates the most utility for the society. However, is an equal share
justified?  Agent~$3$ could propose to agent~$1$ to form $\{1,3\}$ and
to share equally the value of this coalition (hence, 40 for each
agent).  Actually, agent~$2$ can make a better offer to agent~$1$ by
proposing an equal share of 45 if they form $\{1,2\}$.  Agent~$3$
could then propose to agent~$1$ to form $\{1,3\}$ and to let it get 46
(agent~$3$ would then have 34). Is there a PC that would be preferred
by all agents at the same time? 





\subsection{The core}

Let us assume that we have a TU game $(N,v)$ and that we want to form
the grand coalition. What would be a good payoff distribution $x$.
Following the discussion about the game in Table~\ref{ex:TUgame}, it
seems desirable that no agent has an incentive to form a different
coalition such that all members benefit.  This is the idea about the
core, which was first introduced by Gillies~\cite{Gillies53:Theorems}.
A payoff distribution is in the \emph{core} when no agent has any
incentive to be in a different coalition.  This is at first akin to
the Nash equilibrium concept of non-cooperative games.  The core
actually presents a stronger condition: no set of agents can benefit
by forming a new coalition, which corresponds to the group rationality
assumption. More formally:

\begin{definition}[Core] A payoff distribution $x \in {\mathbb R}^n$ is in
  the \emph{core} of a game $(N,v)$ iff $x$ is an imputation that is
  group rational, i.e., $core(N,v) = \{x \in {\mathbb R}^n \,|\,
  \sum_{i \in N} x_i = v(N) \; \land \;  \forall \C \subseteq N \; x(\C) \geq
  v(\C) \}$
\end{definition}

A payoff distribution is in the core when no group of agents has any
interest in rejecting it, i.e., no group of agents can gain by forming
a different coalition.  Note that this condition has to be true for
all subsets of $N$, in particular, this ensures individual
rationality.  The core can thus be defined as a payoff structure that
satisfies weak linear inequalities.  The core is therefore closed and
convex.  Another way to define the core is in terms of excess:

\begin{definition}[Core] The core is the set of payoff distribution $x \in
  {\mathbb R}^n$, such that $\forall R \subset N$, $e(R,x) \le 0$
\end{definition}

\noindent In other words, a PC is in the core when
there exists no coalition that has a positive excess.  This definition
is attractive as it shows that no coalition has any complaint: each
coalition's demand can be granted.

 Let us consider the following two-player game $(\{1,2\},v)$
where $v(\{1\})=5$, $v(\{2\})=5$, and $v(\{1,2\})=20$.  The core of
the game is a segment defined as follows: $core(N,v)= \{ (x_1,x_2)\in
\real^2 \;|\; x_1 \geq 5,\, x_2 \geq 5,\, x_1+x_2=20 \}$ and is
represented in Figure~\ref{ex:core}. This example shows that,
although the game is symmetric, most of the payoffs in the core are
not fair. Core allocations focus on stability only and they may not be
fair.





There are, however, multiple concerns associated with using the notion
of the core.  First, the core can be empty: the conflicts captured by
the characteristic function cannot satisfy all the players
simultaneously.  When the core is empty, at least one coalition is
dissatisfied by the utility allocation and therefore is a blocking
coalition.  Let us consider the following example from
\cite{Kahan84:Theories}: $v(\{A,B\}) = 90$, $v(\{A,C\}) = 80$,
$v(\{B,C\}) = 70$, and $v(N)=120$.  In this case, the core is the PC
where the grand coalition forms and the associated payoff distribution
is $\left(50,40,30 \right)$.  If $v(N)$ is increased, the size of the
core also increases.  But if $v(N)$ decreases, the core becomes empty
(this was the case of the example in Table~\ref{ex:TUgame}).



Some classes of games, however, are guaranteed to have a non-empty
core. The following theorem covers the class of \emph{convex games}.\begin{theo}
A convex game has a non-empty core.
\end{theo}

\begin{proof}
  Let us assume a convex game $(N,v)$.  Let us define a payoff vector
  $x$ in the following way: $x_1 = v(\{1\})$ and for all $i \in
  \{2,\dots,n\}$, $x_i = v(\{1,2,\dots,i\}) - v(\{1,2,\dots,i-1\})$.
  In other words, the payoff of the $i^{th}$ agent is its marginal
  contribution to the coalition consisting of all previous agents in
  the order $\{1,2,\dots,i-1\}$.

  Let us prove that the payoff vector is \emph{efficient} by writing up and
  summing the payoff of all agents:\\
\centerline{\begin{tabular}{rcl}
\rule{0pt}{12pt} $x_1$ &=&  $v(\{1\})$ \\
 $x_2$ &=& $v(\{1,2\}-v(\{1\})$\\
&$\dots$&\\
$x_i$ &=& $v(\{1,2,\dots,i\}) - v(\{1,2,\dots,i-1\})$ \\
&\dots&\\
$x_n$ &=& $v(\{1,2,\dots,n\}) - v(\{1,2,\dots,n-1\})$ \\
\hline \rule{0pt}{12pt}$\sum_{i\in N} x_n$ &=& $v(\{1,2,\dots,n\})=v(N)$\\
\end{tabular}}

By summing these $n$ equalities, we obtain the efficiency condition: $\sum_{i\in N} x_n = v(\{1,2,\dots,n\})=v(N)$.\ok

Let us prove that the payoff vector is \emph{individually rational}.
By convexity, we have $v(\{i\}) - v(\emptyset) \leq v(\{1,2,\dots,i\})
- v(\{1,2,\dots, i-1\})$, hence $v(\{i\}) \leq x_i$. \ok

Finally, let us prove that the payoff vector is \emph{group rational}.
Let $C \subseteq N$, $C=\{a_1, a_2, \dots, a_k\}$ and let us consider
that $a_1 < a_2 < \dots < a_k$. It is obvious that $\{a_1, a_2, \dots,
a_k\} \subseteq \{1,2,\dots,a_k\}$. Using the convexity
assumption, we obtain the following:\\

\centerline{\begin{tabular}{rcl}
    $v(\{a_1\}) - v(\emptyset)$ &$\leq$& $v(\{1,2,\dots,a_1\}) -v(\{1,2,\dots,a_1-1\}) = x_{a_1}$\\
    $v(\{a_1,a_2\}) - v(\{a_1\})$ &$\leq$& $v(\{1,2,\dots,a_2\}) -v(\{1,2,\dots,a_2-1\}) = x_{a_2}$\\ 
    &$\dots$&\\
    $v(\{a_1,a_2,\dots,a_l\}) - v(\{a_1,a_2,\dots,a_{l-1}\})$ &$\leq$& $v(\{1,2,\dots,a_l\}) - v(\{1,2,\dots,a_l-1\}) = x_{a_l}$\\ 
 &$\dots$&\\
   $v(\{a_1,a_2,\dots,a_k\}) - v(\{a_1,a_2,\dots,a_{k-1}\})$ &$\leq$&
   $v(\{1,2,\dots,a_k\}) - v(\{1,2,\dots,a_k-1\}) = x_{a_k}$\\ \hline
\rule{0pt}{12pt}$v(C) = v(\{a_1,a_2,\dots,a_k\})$  &$\leq$& $\sum_{i=1}^k x_{a_k} = x(C)$
\end{tabular}}

By summing these $k$ inequalities, we obtain $v(C) =
v(\{a_1,a_2,\dots,a_k\}) \leq \sum_{i=1}^k x_{a_k} = x(C)$, which
is the group rationality condition. \ok
\end{proof}

Another example are minimum cost spanning tree game.  Let $N$ be the
set of customers, and let $0$ be the supplier.  Let us define $N_* = N
\cup \{0\}$. For $(i,j) \in N_*^2$, $i\neq j$, let $c_{i,j}$ be the
cost of connecting $i$ and $j$ by the edge $e_{ij}$. Let $(N,c)$ be
the corresponding cost game, which is called a minimum cost spanning
tree game ((MCST) game).

\begin{theo}
Every minimum cost spanning tree game has a non-empty core.
\end{theo}

\begin{proof}
  Let us define a cost distribution $x$ and then we will show that $x$
  is in the core.

  Let $T=(N,E_N)$ a minimum cost spanning tree for the graph $\left(N_*,
    c_{\{ij\} \subseteq N_*^2}\right)$.  Let $i$ be a customer. Since
  $T$ is a tree, there is a unique path $(0,a_1,\dots,a_k,i)$ from $0$
  to $i$.  The cost paid by agent $i$ is defined by $x_i = c_{a_k,i}$.

  This cost allocation is efficient by construction of $x$.

  We need to show the cost allocation is group rational, i.e. for all
  coalition $S$, we have $x(S) \leq v(S)$ (it is a cost, which
  explains the inequality).  Let $S \subset N$ and $T_S = (S \cup
  \{0\}, E_s)$ be a minimum cost spanning tree of the graph $\left(S
    \cup \{0\}, c_{\{ij\} \in S \cup \{0\} }\right)$. Let extand the
  tree $T_S$ to a graph $T^+_S=(N_*,E^+_N)$ by adding the remaining
  customers $N \setminus S$, and for each customer $i \in N \setminus
  S$, we add the edge of $E_N$ ending in $i$, i.e., we add the edge
  $(a_k,i)$. The graph $T^+_S$ has $|S|+|N\setminus S|$ edges an is
  connected. Hence, $T^+_S$ is a spanning tree.  Now, we note that $c(S) +
  x(N\setminus S) = \sum_{e_{ij} \subseteq E^+_N} c_{ij} \geq
  \sum_{e_{ij} \subseteq E_N} =c(N) = x(N)$. The inequality is due to
  the fact that $T^+_S$ is a spanning tree, and $T$ is a minimum
  spanning tree. It follows that $x(S) \leq v(S)$. \ok
\end{proof}

The set of games with non-empty core has been characterized
independently by Bondareva (1963) and Shapley (1967), and the result
is known as the Bondareva Shapley theorem. This result connects
results from linear programming with the concept of the core.  

Let $\C \subseteq N$. The \emph{characteristic vector} $\chi_\C$ of
$\C$ is the member of $\real^N$ defined by $\chi_\C^i =\left\{
  \begin{tabular}{l} 1 if $i \in \C$ \\ 0 if $i \in N \setminus
    \C$\end{tabular}\right.$

\begin{definition}[Map]
  A \emph{map} is a function $2^N \setminus \emptyset \rightarrow
  \real_+$ that gives a positive weight to each coalition.
\end{definition}

\begin{definition}[Balanced map]
A function $\lambda: 2^N \setminus \emptyset \rightarrow \real_+$ is a
\emph{balanced map} iff $\sum_{\C \subseteq N} \lambda(\C) \chi_\C = \chi_N$
\end{definition}

A map is balanced when the amount received over all the coalitions
containing an agent $i$ sums up to 1. We provide an example in
Table~\ref{tab:ex-bal-map} for a three-player game.

\begin{table}[h]
\begin{center}
\begin{tabular}{cc}

\begin{tabular}{|c|ccc|}
\hline 
\rule{0pt}{12pt}          & 1 & 2 & 3 \\ \hline
\rule{0pt}{12pt} $\{1,2\}$ & $\frac{1}{2}$  & $\frac{1}{2}$  &  0 \\
\rule{0pt}{12pt} $\{1,3\}$ & $\frac{1}{2}$  & 0  &  $\frac{1}{2}$ \\
\rule{0pt}{12pt} $\{2,3\}$ & 0  & $\frac{1}{2}$  & $\frac{1}{2}$  \\
\hline
\end{tabular}

&

\begin{tabular}{l}
$\;\lambda(\C) = \left\{ \begin{tabular}{l} $\frac{1}{2}$ if $|\C| =2$
    \\ $0$ otherwise \\ \end{tabular} \right.$ \\

Each of the column sums up to 1. \\

$\frac{1}{2} \chi_{\{1,2\}} +  \frac{1}{2} \chi_{\{1,3\}} +
\frac{1}{2} \chi_{\{2,3\}} = \chi_{\{1,2,3\}}$ \\
\end{tabular}
\end{tabular}
\end{center}
\caption{Example of a balanced map for $n=3$}
\label{tab:ex-bal-map} 
\end{table}

\begin{definition}[Balanced game]
  A game is \emph{balanced} iff for each balanced map $\lambda$ we
  have $\sum_{\C \subseteq N, \C \neq \emptyset} \lambda(\C) v(\C)
  \leq v(N)$.
\end{definition}

\begin{theo}[Bondareva-Shapley theorem]
A TU game has a non-empty core iff it is balanced.
\end{theo}

This theorem completely characterize the set of games with a non-empty
core. However, it is not always easy or feasible to check that it is a
balanced game.

There are few extensions to the concept of the core.  As discussed
above, one main issue of the core is that it can be empty.  In
particular, a member of a coalition may block the formation so as to
gain a very small payoff.  When the cost of building a coalition is
considered, it can be argued that it is not worth blocking a coalition
for a small utility gain.  The strong and weak $\epsilon$-core
concepts model this possibility.  The constraints defining the strong
(respectively the weak) $\epsilon$-core become $\forall T \subseteq N,
x(T) \ge v(T) - \epsilon$, (respectively $\forall T \subseteq N, x(T)
\ge v(T) - |T|\cdot \epsilon$).  In the weak core, the minimum amount
of utility required to block a coalition is per player, whereas for
the strong core, it is a fixed amount.

\subsection{Games with Coalition Structure}

In most traditional work in game theory, the superadditivity of the
valuation function is not explicitly stated, but it is implicitly
assumed. In the definition of the core that we presented, we stated
that the grand coalition is formed. With this definition, checking
whether the core is empty amounts to checking whether the grand
coalition is stable.

Aumann and Dr\`eze discuss why the coalition formation process may
generate a CS that is not the grand
coalition~\cite{Aumann74:Cooperative}.  One reason they mention is
that the valuation may not be superadditive (and they provide some
discussion about why it may be the case).  Another reason is that a CS
may ``reflect considerations that are excluded from the formal
description of the game by necessity (impossibility to measure or
communicate) or by choice''~\cite{Aumann74:Cooperative}.  For example,
the affinities can be based on location (each agent may come from the
same country or university), or trust relations, etc.

\begin{definition}[Game with coalition structure] A \emph{ game with
  coalition structure} is a triplet $(N, v, S)$, where $(N,v)$ is a TU
game, and $S$ is a particular CS. In addition, transfer of utility is
only permitted within (not between) the coalitions of $S$,
i.e., $\forall {\cal C} \in S$, $x({\cal C}) = v({\cal C})$.
\end{definition}

Another way to understand this definition is to consider that the
problems of deciding which coalition forms and how to share the
coalition's payoff are decoupled: the choice of the coalition is made
first and results in the CS. Only the payoff distribution choice is
left open. The agents are allowed to refer to the value of coalition
with agents oustide of their coalition (i.e., opportunities they would
get outside of their coalition) to negotiate a better payoff. Note
that the agents' goal is not to change the CS, but only to negotiate a
better payoff for themselves.

Aumann and Dr\`eze extend the definition of many solution concepts and
we now present the definition of the core, which is borrowed
from~\cite{Chalkiadakis08:Overlapping}. The definition is similar
to~\cite{Dieckmann02:Dynamic,Sandholm97:Coalitions}. First, we need to
define the set of possible payoffs: the payoff distributions such that
the sum of the payoff of the members of a coalition in the CS does not
exceed the value of that coalition. More formally:

\begin{definition}{Feasible payoff}
  Let $(N,v,\CS)$ be a TU game with CS. The set of \emph{feasible
    payoff distributions} is $X_{(N,v,\CS)} = \{x \in \real^n \;|\;
  \forall \C \in \CS x(\C) \leq v(\C) \}$.
\end{definition}


A payoff distribution $x$ is \emph{efficient} with respect to a CS
$\CS$ when $\forall \C \in \CS$, $\sum_{i \in \C} x_j = v(\C)$. A
payoff distribution is an \emph{imputation} when it is efficient (with
respect to the current CS) and individually rational (i.e., $\forall i
\in N$, $x_i \geq v(\{i\})$). The set of all imputations for a CS $\CS$
is denoted by $\imp(\CS)$. We can now state the definition of the core:

\begin{definition}[Core]
  The core of a game $(N, v, \CS)$ is the set of all PCs
  $(\CS, x)$ such that $x \in \imp(\CS)$ and $\forall \C \subseteq N$,
  $\sum_{i \in \C} x_j \geq v(\C)$, i.e., $core(N,v,\CS) = \{ x \in
  \real^n \; | \; (\forall \C \in \CS, x(\C) \leq v(\C)) \land
  (\forall \C \subseteq N, x(\C) \geq v(\C)) \}$.
\end{definition}

We now provide a theorem by Aumann and Dr\`eze which shows that the
core satisfies a desirable properties: if two agents can be
substituted, then a core allocation must provide them identical
payoffs.

\begin{definition}[Substitutes]
  Let $(N,v)$ be a game and $(i,j) \in N^2$.  Agents $i$ and $j$ are
  \emph{substitutes} iff $\forall \C \subseteq N \setminus \{i,j\}$,
  $v(\C \cup \{i\}) = v(\C \cup \{j\})$.
\end{definition}

\begin{theo}
  Let $(N,v,\CS)$ be a game with coalition structure, let $i$ and $j$
  be substitutes, and let $x \in core(N,v,\CS)$.

    If $i$ and $j$ belong to different members of $\CS$, then
    $x_i=x_j$.
\end{theo}

\begin{proof}
  Let $(i,j) \in N^2$ be substitutes, $\C \in \CS$ such that $i \in
  \C$ and $j \notin \C$. Let $x \in core(N,v,\CS)$.  Since $i$ and $j$
  are substitutes, we have $v((\C \setminus \{i\}) \cup \{j\}) = v((\C
  \setminus \{i\}) \cup \{i\}) = v(\C)$.  Since $x\in core(N,v,\CS)$,
  we have $\forall \C \subseteq N$, $x(\C) \geq v(\C)$, we apply this
  to $(\C \setminus \{i\}) \cup \{j\}$:\\ $0 \geq v((\C \setminus
  \{i\}) \cup \{j\}) - x((\C \setminus \{i\}) \cup \{j\})$ $= v(\C) -
  x(\C) +x_i-x_j$, since $\C \in \CS$ and $x \in core(N,v,\CS)$,
  $x(\C) = v(\C)$ we have $x_j \geq x_i$.  Since $i$ and $j$ play
  symmetric roles, we have $x_i=x_j$. \ok
\end{proof}

\subsection{The nucleolus}
\newcommand{\ord}{^\blacktriangleright}
\newcommand{\glex}{\geq_{lex}}
\newcommand{\llex}{\leq_{lex}}

The nucleolus is based on the notion of excess and has been introduced
by Schmeidler~\cite{Schmeidler69:Nucleolus}.  The excess measures the
amount of ``complaints'' of a coalition for a payoff distribution. We
already mentionned the excess and gave a definition of the core using
the excess. We now recall the definition.

\begin{definition}[Excess]
  Let $(N,v)$ be a TU game, $\C \subseteq N$ be a coalition, and $x$
  be a payoff distribution over $N$. The \emph{excess $e(\C,x)$} of
  coalition $\C$ at $x$ is the quantity $e(\C,x) = v(\C) - x(\C)$.
\end{definition}

The following example in Table~\ref{ex:nucleolus} is a motivating
example for the nucleolus.

\begin{table}[h]

\begin{center}
  $N=\{1,2,3\}$,\\
  $v(\{i\}) = 0$ for $i \in \{1,2,3\}$ \\
  $v(\{1,2\}) = 5$,  $v(\{1,3\}) = 6$,  $v(\{2,3\}) = 6$\\
  $v(N)=8$
\end{center}

Let us consider two payoff vectors $x= \langle 3, 3, 2 \rangle$ and $y=\langle 2, 3, 3 \rangle$.

\centerline{\begin{tabular}{cc}
$x=\langle 3, 3, 2 \rangle$ & $y=\langle 2, 3, 3 \rangle$ \\
\begin{tabular}{|c|c|}
\hline
\rule{0pt}{12pt}coalition $\C$ &  $e(\C,x)$\\ \hline
\rule{0pt}{12pt}$\{1\}  $     &  -3 \\
$\{2\} $      &  -3 \\
$\{3\} $      &  -2 \\
$\{1,2\} $   &  -1 \\
$\{1,3\} $   &  1 \\
$\{2,3\} $   &  1 \\
$\{1,2,3\}$ &  0 \\ \hline
\multicolumn{2}{c}{\rule{0pt}{0pt}}
\end{tabular}
&
\begin{tabular}{|c|c|}
\hline
\rule{0pt}{12pt}coalition $\C$ &  $e(\C,y)$ \\ \hline
\rule{0pt}{12pt}$\{1\}  $     &  -2 \\
$\{2\} $      &  -3 \\
$\{3\} $      &  -3 \\
$\{1,2\} $   &  0 \\
$\{1,3\} $   &  1 \\
$\{2,3\} $   &  0 \\
$\{1,2,3\}$ &  0 \\ \hline
\multicolumn{2}{c}{\rule{0pt}{0pt}}
\end{tabular} 
\end{tabular}}



Which payoff should we prefer? $x$ or $y$? To compare two vectors of
complaints, we can use the lexicographical order.
Let \emph{$\glex$} denote the \emph{lexicographical} ordering of
$\real^m$, i.e., $\forall (x,y) \in \real^m$, $x \glex y$ iff
$\left\{\begin{tabular}{l}
    x=y or \\
    $\exists t$ s. t. $1 \leq t \leq m$ s. t. $\forall i$ s. t. $1 \leq i \leq
    t$ $x_i=y_i$ and $x_t > y_t$ \\ \end{tabular} \right.$

For example, using the lexicographical ordering, we have $\langle
1,1,0,-1,-2,-3,-3 \rangle \glex \langle 1,0,0,0,-2,-3,-3 \rangle$.

  Let $l$ be a sequence of $m$ reals. We denote by \emph{$l\ord$} the
  \emph{reordering} of $l$ in \emph{decreasing} order. 

  In the example, $e(x) = \langle -3,-3,-2,-1,1,1,0 \rangle$ and then $e(x)\ord = \langle 1,1,0,-1,-2,-3,-3 \rangle$.

  Using the lexicographical ordering, we are now ready to compare the
  payoff distributions $x$ and $y$ and we note that $y$ is better than
  $x$ since  $e(x)\ord  \llex  e(y)\ord $: there is a smaller amount
  of complaints in $y$ than in $x$ given the lexicographical ordering.

\caption{A motivating example for the nucleolus} 
\label{ex:nucleolus}
\end{table}

A payoff distribution is in the nucleolus when it yields the ``least
problematic'' sequence of complaints according to the lexicographical
ordering, i.e., when no other payoff distribution is better.  The
first entry of $e(x)\ord$ is the maximum excess: the agents involved
in the corresponding coalition have the largest incentive to leave
their current coalition and form a new one.  Put another way, the
agents involved in that coalition have the most valid complaint.  The
nucleolus of the game is a set of payoff distributions such that the
corresponding vector of excess $e(x)\ord$ is minimal.  The nucleolus
tries to minimise the possible complaints (or minimise the incentives
to create a new coalition) over all possible payoff distributions.

\begin{definition}   Let $\imp$ be the set of all imputations.
  The \emph{nucleolus $Nu(N,v)$} is the set \\ \centerline{$\displaystyle Nu(N,v)
  = \left\{ x \in \imp\; | \; \forall y \in \imp \;\; e(y)\ord \glex
    e(x)\ord \right\} $.}
\end{definition}

We now provide some properties of the nucleolus.

\begin{theo}
  Let $(N,v)$ be a TU game and $\imp$ is the set of imputations. If $\imp \neq \emptyset$, \\
  then the nucleolus $Nu(N,v)$ is \emph{non-empty}.
\end{theo}

\begin{theo}
  The nucleolus has \emph{at most one} element.
\end{theo}

\begin{theo}Let $(N,v)$ be a TU game with a non-empty core. Then
  $Nu(N,v) \subseteq core(N,v)$
  \end{theo}

The nucleolus is guaranteed to be non-empty and it is unique. These
are two important property in favour of the nucleolus.  Moreover, when
the core is non-empty, the nucleolus is in the core.  

One drawback, however, is that the nucleolus is difficult to compute.
It can be computed using a sequence of linear programs of decreasing
dimensions.  The size of each of these groups is, however,
exponential.  In some special cases, the nucleolus can be computed in
polynomial time~\cite{Faigle01:Computation,Deng06:finding}, but in
the general case, computing the nucleolus is not guaranteed to be
polynomial.  Only a few papers in the multiagent systems community
have used the nucleolus, e.g., \cite{Yokoo06:Compact}.


\subsection{The kernel}

The kernel was first introduced by Davis and Maschler
in~\cite{Davis65:Kernel}: in the kernel, the strength of the players
is measured by the maximum excess the agent can obtain by forming a
new coalition with different agents.  An agent can consider a payoff
distribution to be acceptable by comparing its own `strength' with the
`strength' of other members of its coalition.  When both agents have
equal strength, they do not have any incentive to leave the coalition.
Although its definition is not as intuitive as the core, the kernel
exists and is always
non-empty. % and hence, its use as a solution concept has been popular
%in multiagent research, for example
%in~\cite{Blankenburg05:Trusted,Blankenburg04:Safe,Dang04:Generating,Klusch96:Polynomial,Kraus04:Advantages,Larson99:Anytime,Shehory99:Feasible}.


\subsubsection{Definition of the kernel}

We recall that the \emph{excess} related to coalition $\cal C$ for a payoff distribution x is defined as $e({\cal C},x)= v({\cal C}) - x({\cal C})$.  For two agents $k$ and $l$, the \emph{ maximum surplus} $s_{k,l}$ of agent $k$ over agent $l$ with respect to $x$ is $\max_{c
  \subseteq N \;|\; k\in c,\, l\notin c}e(c,x)$.  This maximum surplus can be used by agent $k$ to show its strength over agent $l$: assuming it is positive and that the agent can claim all of it, agent $k$ can argue that it will be better off without agent $l$; hence it should be compensated with more utility for staying in the current coalition. When any two agents in a coalition have the same maximum surplus (except for a special case), the agents are said to be in equilibrium. A payoff distribution is in the kernel when all agents are in equilibrium. The formal definitions follow:

% \begin{definition}[Equilibrium] Two agents that are in the same coalition are \emph{in
% equilibrium} when any one of the following conditions holds:
%  $$\left\{
% \begin{tabular}{p{0.9\columnwidth}}
%   $\bullet$  $s_{k,l} = s_{l,k}$: agents have equal power \\
%   $\bullet$  $s_{k,l} > s_{l,k}$ and $x_l = v(l)$: $k$ dominates $l$, but $l$ has the minimum utility it can get (individual rationality), hence $k$ cannot claim more utility from player $l$\\
%   $\bullet$  $s_{k,l} < s_{l,k}$ and $x_k = v(k)$: $l$ dominates $k$ and $k$ has the minimum utility.\\
% \end{tabular}
% \right.$$
% \end{definition}

\begin{definition}[kernel]Let $(N,v,\CS)$ be a TU game with coalition
    structure. The \emph{kernel} is the set of imputations $x \in \imp(\CS)$ such
    that for every coalition $\C \in \CS$, if $(k,l) \in \C^2$, $k \neq
    l$, then we have either $s_{kl}(x) \geq s_{lk}(x)$ or
    $x_k=v(\{k\})$. 
\end{definition}

One property of the kernel is that the nucleolus is included in the
kernel. Hence, it follows that when the set of imputations is
non-empty, the kernel is also non empty.

\begin{theo}
The nucleolus is included in the kernel
\end{theo}

\begin{theo} When $\imp \neq \emptyset$, then the kernel is non-empty.
\end{theo}


An approximation of the kernel is the $\epsilon$-kernel, where the equality $s_{k,l} = s_{l,k}$ above is replaced by $|s_{k,l} - s_{l,k}| \leq \epsilon$.  Notice that this definition requires considering all pairs of agents in the coalition.  Unlike the case of the core, the kernel is always non-empty~\cite{Osborne94:Course}.  One property of the kernel is that agents with the same maximum surplus, i.e., symmetric agents, will receive equal payoff.  For ensuring fairness, this property is important.



\subsection{Shapley Value}

The Shapley value is designed to provide a fair payoff distribution in
a coalition~\cite{Shapley53:Value}.  % The Shapley value and its
% variants have been used in multiagent
% system~\cite{Ketchpel94:Formation,Klusch96:Coalition,Zlotkin94:Coalition}.
First we present a set of axioms that defines the Shapley value.  We
then present a different interpretation of the Shapley value which is
based on marginal surplus.  Finally, we present computational issues
and a value that is cheaper to compute which derived from the Shapley
value.

\subsubsection{An Axiomatic Characterisation}

Another approach to define a stability concept is the axiomatic
method. We consider a \emph{value function $\phi$} which assigns an
efficient allocation $x$ to a TU game $(N,v)$ (i.e., an allocation
that satisfies $\phi(N)=v(N)$).  Let us consider some axioms that may
be desirable for such a value function.  The first axiom uses the
definition of a dummy agent: an agent $i$ is a \emph{dummy} when
$v({\cal C} \cup i) - v({\cal C}) = v({i})$ for all ${\cal C}
\subseteq N$ such that $i \notin {\cal C}$.

\begin{description}
\item[DUM (``Dummy actions'')]: if agent $i$ is a dummy then $x_i
  = v(\{ i \})$.  In other words, if the presence of agent $i$ does
  not improve the worth of a coalition by more than $v(\{ i \})$, the
  agent does not bring anything to the coalition, and then, should
  obtain only $v(\{i\})$.
\item[SYM (``Symmetry'')]: When two agents generate the same
  marginal contributions, they should be rewarded equally: for $i \neq
  j$ and $\forall \C \subseteq N$ such that $i \notin \C$ and $j
  \notin S$, if $v(\C \cup \{i\}) = v(\C \cup \{j\}) $, then
  $x_i=x_j$.
\item[ADD (``Additivity'')]: For any two TU games $(N,v)$ and
  $(N,w)$ and corresponding payoff profiles $x \in \real^{n}$ and $y
  \in \real^{n}$, the payoff profile should be $x+y$ for the TU game
  $(N,v+w)$. 
\end{description}

\begin{theo}
  The Shapley value is the unique value that is budget-balanced and
  that satisfies axioms 1, 2, and 3.
\end{theo}

The theorem states that these three axioms uniquely define a value
function, that is called the \emph{Shapley value}.  A proof of this
theorem can be found in~\cite{Osborne94:Course}. To prove this
results, one needs to show the existence of a value function that
satisfies the three axioms, and then prove the unicity of the value
function. In addition, note that the axioms are independent. Finally,
one can also show that if one of the three axioms is dropped, it is
possible to find multiple value functions satisfying the other two
axioms.

The axioms SYM and DUM are clearly desirable. The last axion, ADD, is
harder to motivate in some cases. If the valuation function of a TU
game is interpreted as an expected payoff, then ADD is desirable.
Also, if we consider cost-sharing games and one TU game corresponds to
sharing the cost of one service, then ADD is desirable as the cost for
a joint-service should be the sum of the cost of the separate
services. However, if we do not make any assumptions about the games
$(N,v)$ and $(N,w)$, the axiom implies that there is no interaction
between the two games. In addition, the game $(N,v+w)$ may induce a
behavior that may be unrelated to the behavior induced by either
$(N,v)$ or $(N,w)$. Other axiomatisations that do not use the ADD
axiom have been proposed by \cite{Young85:Monotonic} and
\cite{Myerson77:Graphs}.

\subsubsection{Ordinal Marginal Contribution}

Another interpretation of the Shapley value is based on the notion of
ordered marginal contribution.  The marginal contribution of an agent
$i$ to a coalition $\C \subseteq N$ is $mc_i(\C) = v(\C \cup \{i\}) - v(\C)$.
% Consider a coalition $\cal C$ and few agents that want to join this
% coalition.  One way to compare the contribution of different agents
% is to compare the marginal contribution of each agent $i$ to this
% coalition: $\Delta_i({\cal C}) = v({\cal C} \cup i) - v({\cal C})$:
% the greater the surplus, the more wealth will be distributed to the
% agents.  In the formation of a coalition, there may be incentives to
% join the coalition early or late. Hence, using the surplus may be
% unfair to some agents. To ensure fairness, the Shapley value is the
% average marginal contribution over all possible joint orders of the
% agents.
Let us consider that a coalition $\cal C$ is built incrementally with
one agent at a time entering the coalition.  Also consider that the
payoff of each agent $i$ is its marginal contribution.  For example,
$\langle mc_1(\emptyset), mc_2(\{1\}), mc_3(\{1,2\}) \rangle$ is an
efficient payoff distribution for a game $\{1,2,3\},v)$\footnote{the
  proof of Theorem~1 shows that such a payoff distribution is in the
  core of a convex game}. In this case, the value of each agent
depends on the order in which the agents enter the coalition, which
may not be fair.  For example, consider agents that form a coalition
to take advantages of price reduction when buying large quantities of
a product. Agents that start the coalition may have to spend large
setup cost, and agents that come later benefits from the already large
number of agents in the coalition.  To alleviate this issue, the Shapley
value averages each agents' payoff over all possible orderings: the
value of agent $i$ in coalition $\cal C$ is the average marginal value
over all possible orders in which the agents may join the coalition.

Let $\sigma$ represent a joining order of the grand coalition $N$:
$\sigma$ can also be viewed as a permutation of $\langle 1, \dots, n
\rangle$. We write $mc(\sigma)$ the payoff vector where agent $i$
obtains $mc_i(\{ \sigma(j) \;|\; j < i \})$. The payoff vector
$mc(\sigma)$ is called the \emph{marginal vector}.  Let us denote the
set of all permutations of the sequence $\langle 1, \dots, n \rangle$
as $\Sigma(N)$. The Shapley values can then be defined as

$$Sh(N,v) = \frac{\sum_{\sigma \in \Sigma(N)} mc(\sigma)}{n!}.$$


\begin{table}[h] 
\begin{center}
$N=\{1,2,3\}$
\begin{tabular}{ccc}
$v(\{1\})=0$ & $v(\{2\})=0$ &  $v(\{3\})=0$ \\
 $v(\{1,2\}) = 90$ & $v(\{1,3\}) = 80$ & $v(\{2,3\}) = 70$\\
 & $v(\{1,2,3\}) =120$ &\\
\end{tabular}

\vspace{5pt}

\begin{tabular}{lr}
\begin{tabular}{lrrr}
\hline                                &   1  &   2  &   3   \\ \hline
$1 \leftarrow 2 \leftarrow 3$ &   0   &  90  &   30  \\
$1 \leftarrow 3 \leftarrow 2$ &   0   &  40  &   80  \\
$2 \leftarrow 1 \leftarrow 3$ &  90  &   0   &   30  \\
$2 \leftarrow 3 \leftarrow 1$ &  50  &   0   &   70  \\
$3 \leftarrow 1 \leftarrow 2$ &  80  &  40  &    0  \\
$3 \leftarrow 2 \leftarrow 1$ &  50  &  70  &    0  \\ \hline
 total                                &  270 & 240 & 210  \\ \hline
Shapley value  $\phi$         & 45   &  40  &   35 \\
\hline
\end{tabular}

&

\begin{tabular}{l}
Let $y = \langle 50, 40,30 \rangle$  \\

\begin{tabular}{ccc}
\hline
$\C$ &  $e(\C,\phi)$  & $e(\C,y)$ \\ \hline
$\{1\}  $     &  -45  & 0 \\
$\{2\} $      &  -40  & 0 \\
$\{3\} $      &  -35  & 0 \\
$\{1,2\} $   &  5     & 0 \\
$\{1,3\} $   &  0     & 0 \\
$\{2,3\} $   &  -5    & 0 \\
$\{1,2,3\}$ &  0  & 0 \\ \hline
\end{tabular}
\end{tabular}
\end{tabular}
\end{center}
This example shows that the Shapley value may not be in the core, and may not be the nucleolus.
\caption{Example of a computation of Shapley value}
\label{ex:Shapley}
\end{table}

We provide an example in Table~\ref{ex:Shapley} in which we list all
the orders in which the agents can enter the grand coalition. The sum
is over all joining orders, which may contains a very large number of
terms. However, when computing the Shapley value for one agent, one
can avoid some redundancy by summing over all coalitions and noticing
that:
\begin{itemize}
\item There are $|\C|!$ permutations in which all members of $\C$ precede $i$.
\item There are $|N \setminus (\C \cup \{i\})|!$ permutations in which
  the remaining members succede $i$, i.e. $(n - |\C|-1)!$.
\end{itemize}
These observations allow us to rewrite the Shapley value as:
$$Sh_i(N,v) = \sum_{\C \subseteq N \setminus \{i\}
}\frac{|\C|!(n-|\C|-1)!}{n!}\left( v(\C \cup \{i\}) - v(\C)
\right).$$

Note that the example from Table~\ref{ex:Shapley} also demonstrates
that in general the Shapley value is not in the core or in the
nucleolus. At noted before, the Shapley value always exists and is
unique.  When the valuation function is superadditive, the Shapley
value is individually rational, i.e., it is an imputation.  When the
core is non-empty, the Shapley value may not be in the core.  However,
when the valuation function is convex, the Shapley value is also group
rational, hence, it is in the core.




\bibliographystyle{plain}
\bibliography{coalition}
\end{document}
