Shapley Values For Transferable Utility Games

Johan Krouthen (1858-1932) was a Swedish painter.

The carrier of the cooperative game $(N,v)$ is a coalition $T$ satisfying $v(S)=v(S\cap T)$ for any coalition $S\subseteq N$. This definition states that the player $i\not\in T$ is a dummy player; that is to say, the player $i$ has nothing to contribute to any coalitions. Let $\pi$ be a permutation of $N$, i.e., a one-to-one function $\pi:N\rightarrow N$. Given a coalition $S\subseteq N$ with $|S|=s$, i.e., $S=\{i_{1},i_{2},\cdots ,i_{s}\}$, we have $\pi (S)=\{\pi (i_{1}),\pi (i_{2}),\cdots ,\pi (i_{s})\}$. We define a cooperative game $(N,v^{\pi})$ by $v^{\pi}(\pi (S))=v(S)$, i.e., $v^{\pi}(S)=v(\pi^{-1}(S))$.

Given a cooperative game $(N,v)$, we shall consider a corresponding vector $\boldsymbol{\phi}(v)=(\phi_{1}(v),\cdots ,\phi_{n}(v))$ in which the $i$th component $\phi_{i}(v)$ is interpreted as the payoffs received by player $i$ under an agreement. This correspondence is taken to satisfy the following Shapley axioms.

(S1). If $S$ is any carrier of the game $(N,v)$, then $\sum_{i\in S}\phi_{i}(v)=v(S)$.
(S2). For any permutation $\pi$ of $N$ and $i\in N$, we have $\phi_{\pi (i)}(v^{\pi})=\phi_{i}(v)$;
(S3). If $(N,v_{1})$ and $(N,v_{2})$ are any cooperative games, then we have $\phi_{i}(u+v)=\phi_{i}(u)+\phi_{i}(v)$ for all $i\in N$.

The function $\boldsymbol{\phi}:\mbox{TU}(N)\rightarrow\mathbb{R}^{N}$ by $(N,v)\mapsto\boldsymbol{\phi}(v)$ defines a vector $\boldsymbol{\phi}(v)$ which is called the Shapley value of the cooperative game $(N,v)\in \mbox{TU}(N)$
(Petrosjan and Zenkevich \cite[p.183]{pet}).

\begin{equation}{\label{perl3133}}\tag{1}\mbox{}\end{equation}

Lemma \ref{perl3133} (Petrosjan and Zenkevich \cite[p.183]{pet}). Let $u_{S}$ be a unanimity game on $S$. Then the vector $\boldsymbol{\phi}(u_{S})$ is uniquely defined by axioms {\em (S1)} and {\em (S2)} as follows:
\[\phi_{i}(u_{S})=\left\{\begin{array}{ll}
1/|S|, & \mbox{if $i\in S$}\\ 0, & \mbox{if $i\not\in S$}.
\end{array}\right .\]
Moreover, if $c\geq 0$, then we have
\[\phi_{i}(cu_{S})=\left\{\begin{array}{ll}
c/|S|, & \mbox{if $i\in S$}\\ 0, & \mbox{if $i\not\in S$}.
\end{array}\right .\]
In other words, we have $\phi_{i}(cu_{S})=c\phi_{i}(u_{S})$ for any $c\in\mathbb{R}$.

Proof. It is obvious that $S$ is a carrier of $u_{S}$. By axiom (S1), if $S\subseteq T$, then
\[\sum_{i\in T}\phi_{i}(u_{S})=u_{S}(T)=1=u_{S}(S)=\sum_{i\in S}\phi_{i}(u_{S}).\]
This means that $\phi_{i}(u_{S})=0$ for $i\not\in S$. If $\pi$ is a permutation which converts $S$ to itself, then $\pi (u_{S})=u_{S}$. Therefor, by axiom (S2), there is the equality $\phi_{i}(u_{S})=\phi_{j}(u_{S})$ for any $i,j\in S$. Since there is a total of $|S|$ and their sum is $1$, we have $\phi_{i}(u_{S})=1/|S|$ if $i\in S$. For $\phi_{i}(cu_{S})$, the proof is straightforward. Now we have $\phi_{i}(cu_{S})=c\phi_{i}(u_{S})$ for $c\geq 0$. By axiom (S3), if $u$, $v$ and $u-v$ are characteristic functions, then $\phi_{i}(u-v)=\phi_{i}(u)-\phi_{i}(v)$ for all $i\in N$. It shows that $\phi_{i}(cu_{S})=c\phi_{i}(u_{S})$ for $c<0$. $\blacksquare$

Theorem. (Petrosjan and Zenkevich \cite[p.183]{pet}). There exists a unique function $\boldsymbol{\phi}$ defined on $\mbox{TU}(N)$ and satisfies axioms (S1), (S2) and (S3). Moreover, we have
\begin{equation}{\label{peteq25}}\tag{2}
\phi_{i}(v)=\sum_{\{T:i\in T\subseteq N\}}\frac{(|T|-1)!(|N|-|T|)!}{|N|!}\cdot(v(T)-v(T\setminus\{i\}))
\end{equation}

Proof. From Lemmas \ref{perl3133} and \ref{perl3134}, we have
\[\phi_{i}(v)=\sum_{\{S:S\subseteq N\}}c_{S}\phi_{i}(u_{S})=\sum_{\{S:i\in S\subseteq N\}}c_{S}\frac{1}{|S|}.\]
Substituting (\ref{pereq3135}) into the above expression, we obtain
\[\phi_{i}(v)=\sum_{\{S:i\in S\subseteq N\}}\frac{1}{|S|}\left [\sum_{\{T:T\subseteq S\}} (-1)^{|S|-|T|}v(T)\right ]=
\sum_{\{T:T\subseteq N\}}\left [\sum_{\{S:T\cup\{i\}\subseteq S\subseteq N\}}(-1)^{|S|-|T|}\frac{1}{|S|}v(T)\right ].\]
Set
\[\gamma_{i}(T)\equiv\sum_{\{S:T\cup\{i\}\subseteq S\subseteq N\}}(-1)^{|S|-|T|}\frac{1}{|S|}.\]
If $i\not\in T’$ and $T=T’\cup\{i\}$, then $\gamma_{i}(T’)=-\gamma_{i}(T)$. Thus we have
\[\phi_{i}(v)=\sum_{\{T:i\in T\subseteq N\}}\gamma_{i}(T)\left [v(T)-v(T\setminus\{i\})\right ].\]
If $i\in T$, then there are exactly $\left (\begin{array}{c} s-|T|\\ |N|-|T|\end{array}\right )$ coalitions $S$ with $s$ elements such that $T\subseteq S$. We have
\begin{align*}
\gamma_{i}(T) & =\sum_{s=|T|}^{|N|}(-1)^{s-|T|}\left (\begin{array}{c} s-|T|\\ |N|-|T|\end{array}\right )\frac{1}{s}=
\sum_{s=|T|}^{|N|}(-1)^{s-|T|}\left (\begin{array}{c} s-|T|\\ |N|-|T|\end{array}\right )\int_{0}^{1}x^{s-1}dx\\
& =\int_{0}^{1}\sum_{s=|T|}^{|N|}(-1)^{s-|T|}\left (\begin{array}{c} s-|T|\\ |N|-|T|\end{array}\right )x^{s-1}dx\\
& =\int_{0}^{1}x^{|T|-1}\left [\sum_{s=|T|}^{|N|}\left (\begin{array}{c} s-|T|\\ |N|-|T|\end{array}\right )(-x)^{s-|T|}\right ]dx\\
& =\int_{0}^{1}x^{|T|-1}(1-x)^{|N|-|T|}dx=\frac{(|T|-1)!(|N|-|T|)!}{|N|!}
\end{align*}
It shows equation (\ref{peteq25}) which determines explicitly the components of Shapley value. The expression (\ref{peteq25}) satisfies axioms (S1), (S2) and (S3). This completes the proof. $\blacksquare$

Proposition. (Petrosjan and Zenkevich \cite[p.186]{pet}). Suppose that the cooperative game $(N,v)$ is super-additive. Then the Shapley value $\boldsymbol{\phi}(v)$ is an imputation.

Proof. By the superadditivity of the function $v$, we have $v(T)\geq v(T\setminus\{i\})+v(i)$. Equation (\ref{peteq25}) shows that
\[\phi_{i}(v)\geq v(i)\cdot\sum_{\{T:i\in T\subseteq N\}}\frac{(|T|-1)!(|N|-|T|)!}{|N|!}
=v(i)\cdot\sum_{t=1}^{|N|}\left (\begin{array}{c} t-1\\ |N|-1\end{array}\right )\frac{(t-1)!(|N|-t)!}{|N|!}=v(i).\]
This completes the proof. $\blacksquare$

\begin{equation}{\label{har89p1}}\tag{3}\mbox{}\end{equation}

Proposition \ref{har89p1}. {\em (Hart and Mas-Colell \cite[p.592]{har89}). Let $\boldsymbol{\phi}(v)$ be the Shapley value of the game $(N,v)$. Then
\[\phi_{i}(v)=\sum_{\{S:i\in S\}}\frac{c_{S}}{|S|}\]
for $i\in N$, where $c_{S}$ is given in $(\ref{pereq3135})$.

Proof. We can prove it by satisfying the axioms of the Shapley value. $\blacksquare$

The Shapley value expressed by (\ref{peteq25}) can be interpreted probabilistically as follows. Suppose the players (elements of the set $N$) have decided to meet in a specified place at a specified time. It would appear natural that, because of random deviations, they would arrive at various instants of time. However, it is assumed that the players’ arrival orders (i.e. their permutations) have the same probability, namely $1/|N|!$. Suppose that if, on arrival, player $i$ finds in place only the members of coalition $T\setminus\{i\}$, then he/she receives a payoff $v(T)-v(T\setminus\{i\})$. Then, the component of Shapley value $\phi_{i}(v)$ represents the payoff of player $i$, mathematical expectation in terms of this randomization (Petrosjan and Zenkevich \cite[p.186]{pet}).

Example. (Littlechild and Owen \cite[p.370-371]{lit})/ Let $N_{i}$ denote the set of type $i$ players for $i=1,\cdots ,m$ and $|N_{i}|=n_{i}$ be the number of type $i$ players. Let $N=\bigcup_{i=1}^{m}N_{i}$ and $n=\sum_{i=1}^{m}n_{i}$. Let $c_{i}$ be the “cost” associated with a type $i$ player. Without loss of generality, these types may be ordered so that $0=c_{0}<c_{1}<c_{2}<\cdots <c_{m}$. Define a game of $N$ by the subadditive characteristic function
\begin{equation}{\label{liteq1}}\tag{4}
v(\emptyset )=0\mbox{ and }v(S)=\max_{\{i:N_{i}\cap S\neq\emptyset\}}c_{i}.
\end{equation}
Finally, we define $R_{k}=\bigcup_{i=k}^{m}N_{i}$ and $r_{k}=\sum_{i=k}^{m}n_{i}$ for $k=1,\cdots ,m$. Note that $R_{1}=N$ and $r_{1}=n$. We can show that if the characteristic function is defined by (\ref{liteq1}), then the Shapley value may be simplified to
\[\phi_{j}(v)=\sum_{k=1}^{i}\frac{c_{k}-c_{k-1}}{r_{k}}\mbox{ for }j\in N_{i}.\]
If we set $\phi_{j}(v)=\Phi_{i}$ for $j\in N_{i}$, then
\[\Phi_{i}=\Phi_{i-1}+\frac{c_{i}-c_{i-1}}{r_{i}}.\]
If $n_{i}=1$ for all $i$, then
\[\Phi_{i}=\Phi_{i-1}+\frac{c_{i}-c_{i-1}}{n-i+1}. \sharp\]

The next theorem gives a new proof of Shapley value for the case of all cooperative games $\mbox{TU}(N)$ which are not necessarily superadditive (???).

\begin{equation}{\label{dub75t1}}\tag{5}\mbox{}\end{equation}

Theorem \ref{dub75t1}. (Dubey \cite[p.132]{dub75}). There is a unique function $\boldsymbol{\phi}$ defined on $\mbox{TU}(N)$ which satisfies the axioms {\em (S1)}, {\em (S2)} and {\em (S3)}.

Proof. For each coalition $S$ and $c\in\mathbb{R}$, we define a game $v_{S,c}$ by
\[v_{S,c}(T)=\left\{\begin{array}{ll}
c & \mbox{if $S\subseteq T$}\\ 0 & \mbox{if $S\not\subseteq T$}
\end{array}\right .\]
Then it is clear that $S$ and its supersets are all carriers for $v_{S,c}$. Therefore, axiom (i), we have $\sum_{i\in S}\phi_{i}(v_{S,c})=c$ and $\sum_{i\in S\cup\{j\}}\phi_{i}(v_{S,c})=c$ whenever $j\not\in S$. This implies that $\phi_{j}(v_{S,c})=0$ whenever $j\not\in S$. For $i,j\in S$, if $\pi$ is a permutation of $N$ which intercganges $i$ and $j$ and leaves the other players fixed, then it is clear that $\pi v_{S,c}=v_{S,c}$, i.e., $\pi(v_{S,c}(T))=v_{S,c}(T)$ for all $T\subseteq N$. Thus, by axiom (ii), we have $\phi_{i}(v_{S,c})=\phi_{j}(v_{S,c})$. Therefore $\boldsymbol{\phi}(v_{S,c})$ is unique if $\boldsymbol{\phi}$ exists, and is given by
\[\phi_{i}(v_{S,c})=\left\{\begin{array}{ll}
c/|S| & \mbox{if $i\in S$}\\ 0 & \mbox{if $i\notin S$}.\end{array}\right .\]
Then we can show that the family $\{v_{S,c}:\emptyset\neq S\subseteq N,c\in\mathbb{R}\}$ form a basis for the vector space $\mbox{TU}(N)$, and the proof is complete, which is the traditional approach. Alternatively, we give a new proof. We now consider the games $\{v’_{S,c}:\emptyset\neq S\subseteq N,c\in\mathbb{R}\}$ defined by
\[v’_{S,c}(T)=\left\{\begin{array}{ll}
c & \mbox{if $S=T$}\\ 0 & \mbox{if $S\neq T$}.
\end{array}\right .\]
Any game $v$ can be rewritten as a finite sum of games of the type $v’_{S,c}$. Using axiom (iii), if we can show that each $\boldsymbol{\phi}(v’_{S,c})$ is unique, then the uniqueness of $\boldsymbol{\phi}$ follows immediately. We are going to prove this by induction. Assume that $\boldsymbol{\phi}(v’_{S,c})$ is unique for $|S|=k+1,\cdots ,n$. We shall show that $\boldsymbol{\phi}(v’_{S,c})$ is unique for $|S|=k$. Let $S_{1},\cdots ,S_{l}$ be all proper supersets of $S$. Therefore $|S_{i}|>k$ for all $i=1,\cdots ,l$. Thus $\boldsymbol{\phi}(v’_{S_{i},c})$ is unique by the induction hypothesis. Since $v_{S,c}=v’_{S,c}+v’_{S_{1},c}+\cdots +v’_{S_{l},c}$, by axiom (iii), we have
\begin{equation}{\label{dub75eq1}}\tag{6}
\boldsymbol{\phi}(v_{S,c})=\boldsymbol{\phi}(v’_{S,c})+\boldsymbol{\phi}(v’_{S_{1},c})+\cdots +\boldsymbol{\phi}(v’_{S_{l},c}).
\end{equation}
Since all the terms except $\boldsymbol{\phi}(v’_{S,c})$ are unique, we see that $\boldsymbol{\phi}(v’_{S,c})$ is also unique. Since, for $|N|=|S|$, $v’_{N,c}=v_{N,c}$ is unique, By the induction argument, we see that each $\boldsymbol{\phi}(v’_{S,c})$ is unique. This concludes that $\boldsymbol{\phi}$ is unique if it exists. Next, we are going to present the existence. We also want to use the induction argument. For $s=|S|=k+1,\cdots ,n$, we suppose that
\[\phi_{i}(v’_{S,c})=\left\{\begin{array}{ll}
{\displaystyle \frac{(s-1)!(n-s)!}{n!}\cdot c}, & \mbox{if $i\in S$}\\
{\displaystyle -\frac{s}{n-s}\cdot\frac{(s-1)!(n-s)!}{n!}\cdot c},
& \mbox{if $i\not\in S$.}
\end{array}\right .\]
This is obviously true for $|S|=|N|=n$, since $v’_{N,c}=v_{N,c}$. Using (\ref{dub75eq1}), it follows
\[\phi_{i}(v’_{S,c})=\left\{\begin{array}{ll}
{\displaystyle \frac{(s-1)!(n-s)!}{n!}\cdot c}, & \mbox{if $i\in S$}\\
{\displaystyle -\frac{s}{n-s}\cdot\frac{(s-1)!(n-s)!}{n!}\cdot c},
& \mbox{if $i\not\in S$.}
\end{array}\right .\]
for $|S|=k$. It is now straightforward to obtain $\boldsymbol{\phi}(v)$. Since
\[v=\sum_{\emptyset\neq S\subseteq}v’_{S,v(S)},\]
by axiom (iii), we have
\[\boldsymbol{\phi}(v)=\sum_{\emptyset\neq S\subseteq}\boldsymbol{\phi}(v’_{S,v(S)}).\]
The righthand side, when simplified, gives
\[\phi_{i}(v)=\sum_{i\in T\subseteq N}\frac{(t-1)!(n-t)!}{n!}\left [v(T)-v(T\setminus\{i\})\right ].\]
It is easy to verify that $\boldsymbol{\phi}$ define above satisfies the axioms (i), (ii) and (iii). This completes the proof. $\blacksquare$

Given a cooperative game $(N,v)$, let $\pi$ be a permutation on $N$ and let
\[P(\pi ,i)=\left\{j\in N:\pi (j)<\pi (i)\right\}\]
be the set of predecessors of $i$ with respect to $\pi$. The marginal vector ${\bf m}(v,\pi )$ of $(N,v)$ is defined by
\begin{equation}{\label{ga33}}\tag{7}
m_{i}(v,\pi )=v\left (P(\pi ,i)\cup\{i\}\right )-v\left (P(\pi ,i)\right ).
\end{equation}
Then the Shapley value of the game $v$ is the average of the marginal vectors ${\bf m}(v,\pi )$ as shown below.

Proposition. (Curiel \cite[p.6]{cur} and Branzei et al. \cite[p.268]{bra}). Let $\boldsymbol{\phi}$ be the Shapley value of the cooperative game $(N,v)$ and let $\Pi (N)$ be the set of all permutations of $N$. Then, we have
\begin{equation}{\label{ga58}}\tag{8}
\boldsymbol{\phi}(v)=\frac{1}{|N|!}\sum_{\pi\in\Pi (N)}{\bf m}(v,\pi ). \sharp
\end{equation}

Shapley Value for Big Boss Games.

Let us recall the big boss games in Definition \ref{mut88d1} and recall that $m_{i}(v)=v(N)-v(N\setminus\{i\})$ is the player $i$’s marginal contribution to the grand coalition.

Proposition. (Muto et al. \cite[p.310]{mut88}). Let $(N,v)$ be a big boss game and $\boldsymbol{\phi}(v)$ be the Shapley value of $v$. Then $\phi_{1}(v)\leq v(N)-(\sum_{i\in N\setminus\{1\}}m_{i}(v))/2$. $\sharp$

From Propositions \ref{mut88t41} and \ref{mut88t42}, in the $\tau$-value and the nucleolus, each of the weak players $2,\cdots ,n$ gets exactly half of his/her marginal contribution to the grand coalition and the rest goes to the big boss $1$. However, in the Shaply value, the big boss generally gets less (Muto et al. \cite[p.310]{mut88}).

If the game is symmetric with respect to the weak players $2,\cdots ,n$, i.e., every two of these players are symmetric, then they get equal payoffs in each of the $\tau$-value, nucleolus, and the Shapley value. Thus each of the weak players generally gets more in the Shapley value. Here we note that the game $v\in BB\mbox{TU}(N)$ is symmetric with respect to the players $2,\cdots ,n$ if and only if, for every $S\subseteq N$ with $1\in S$, $v(S)$ depends only on the number of players in $S$, and thus all $m_{i}(v)$, $i\in N\setminus\{1\}$, have the same value (Muto et al. \cite[p.311]{mut88}).

Corollary. (Muto et al. \cite[p.311]{mut88}). Let $v\in BB\mbox{TU}(N)$. If $v$ is symmetric with respect to the players $2,\cdots ,n$, then $\phi_{i}(v)\geq m_{i}(v)/2$ for all $i\in N\setminus\{1\}$. $\sharp$

Theorem. (Muto et al. \cite[p.311]{mut88}). Let $v\in BB\mbox{TU}(N)$. Then, the following assertions are equivalent:

(a) $v$ is convex;

(b) $\phi_{1}(v)=\tau_{1}(v)=\nu_{1}(v)$;

From the above theorem, we see that if the big boss $1$ gets the same payoff in the Shapley value, in the $\tau$-value and in the nucleolus, then all other weak players also get the same payoffs in these solutions. Condition (\ref{mut88eq10}) ensures that $\phi_{i}(v)\geq\tau_{i}(v)$ for all $i\in N\setminus\{1\}$ (Muto et al. \cite[p.312]{mut88}).

Theorem. (Muto et al. \cite[p.312]{mut88}). Let $(N,v)$ be a strong big boss game in Definition \ref{mut88d2} and $\boldsymbol{\phi}(v)$ be the Shapley value of $v$. Then $\phi_{i}(v)\geq m_{i}(v)/2$ for all $i\in N\setminus\{1\}$. $\sharp$

The Uniqueness.

One can restrict the axioms (S1), (S2) and (S3) to subclasses $K$ of $\mbox{TU}(N)$. Axiom (S2) is required to hold only if $\pi v\in K$ whenever $v\in K$, and axiom (S3) only if $v_{1}+v_{2}\in K$ whenever $v_{1},v_{2}\in K$. The question arises whether the axioms, so restricted, specify a unique $\boldsymbol{\phi}$ on $K$ (Dubey \cite[p.134]{dub75}).

Proposition. (Dubey \cite[p.135]{dub75}). The following subclasses of $\mbox{TU}(N)$ preserve the uniqueness.

The subclass of all super-additive games (this is the original Shapley’s theorem).
The subclass of all simple games.
The subclass of all games for which $v(S)=0$ whenever $|S|\leq k$; as well as the subclass of all simple games with this restriction.
The subclass of all games in which certain players $i_{1},\cdots ,i_{k}$ are distinguished and $v(S)=0$ if $latex \{i_{1},\cdots ,i_{k}\}
\not\subseteq S$; as well as the subclass of all simple games with this restriction. $\sharp$

Proof. The proof of the uniqueness of $\boldsymbol{\phi}$ on the given subclasses is completely parallel to the proof of Theorem \ref{dub75t1}. $\blacksquare$

Let $C_{1}$ be the subclass of all monotonic simple games in $\mbox{TU}(N)$, i.e., simple games $v$ for which $v(S)=1$ implies that $v(T)=1$ whenever $S\subseteq T$, and let $C_{2}$ be the subclass of all super-additive simple games in $\mbox{TU}(N)$. The axioms (S1), (S2) and (S3) do not uniquely specify the Shapley value on $C_{1}$ or $C_{2}$ if $|N|>2$. However, if we replace axiom (S3) by a variant of it, which is called axiom (S3′) and will be stated below, then a unique $\boldsymbol{\phi}$ is specified on $C_{1}$ or $C_{2}$ and it is just the Shapley value. In what follows, we shall write out only for the case of $C_{2}$, because the case of $C_{1}$ can be obtained by replacing $C_{2}$ by $C_{1}$ throughout (Dubey \cite[p.136]{dub75}).

For $v_{1},v_{2}\in C_{2}$, we see that
\[(v_{1}\vee v_{2})(S)=\left\{\begin{array}{ll}
1, & \mbox{if either $v_{1}(S)=1$ or $v_{2}(S)=1$}\\
0, & \mbox{if $v_{1}(S)=0$ and $v_{2}(S)=0$}.
\end{array}\right .\]
and
\[(v_{1}\wedge v_{2})(S)=\left\{\begin{array}{ll}
1, & \mbox{if either $v_{1}(S)=1$ and $v_{2}(S)=1$}\\
0, & \mbox{if $v_{1}(S)=0$ or $v_{2}(S)=0$}.
\end{array}\right .\]

Note that $v_{1}\vee v_{2}$ may not always be in $C_{2}$ for $v_{1},v_{2}\in C_{2}$.
Let us make a simple check to see that $v_{1}\wedge c_{2}\in C_{2}$ whenever $v_{1},v_{2}\in C_{2}$. If $v_{1}\wedge v_{2}\not\in C_{2}$, then there are coalitions $S$ and $T$, $S\cap T=\emptyset$, such that $(v_{1}\wedge v_{2})(S\cup T)<(v_{1}\wedge v_{2})(S)+(v_{1}\wedge v_{2})(T)$ by considering super-additivity. But, by the definition of $(v_{1}\wedge v_{2})$, it means that either $v_{1}(S\cup T)<v_{1}(S)+v_{1}(T)$ or $v_{2}(S\cup T)<v_{2}(S)+v_{2}(T)$, which contradicts $v_{1},v_{2}\in C_{2}$ by considering the supper-additivity.

We are now in a position to state axiom (S3′).

(S3′). If $v_{1}\vee v_{2}\in C_{2}$ whenever $v_{1},v_{2}\in C_{2}$ then $\boldsymbol{\phi}(v_{1}\vee v_{2})+\boldsymbol{\phi}(v_{1}\wedge v_{2})=\boldsymbol{\phi}(v_{1})+\boldsymbol{\phi}(v_{2})$.

In stating axiom (S3′) for $C_{1}$, we may drop the “if” because $v_{1}\vee v_{2}\in C_{1}$ always (Dubey \cite[p.136-137]{dub75}).

Theorem. (Dubey \cite[p.137]{dub75}). There is a unique solution function $\boldsymbol{\phi}$ that is defined on $C_{2}$ and satisfies the axioms {\em (S1)}, {\em (S2)} and {\em (S3′)}. $\sharp$

Next we are going to consider the Shapley value for constant-sum games. A value $\boldsymbol{\phi}$ is marginalist if $\phi_{i}(v)$ depends only upon the $i$th marginal utility vector $(v(S\cup\{i\})-v(S))_{S\subseteq N\setminus\{i\}}$, i.e., $\phi_{i}(v)=\xi_{i}((v(S\cup\{i\})-v(S))_{S\subseteq N\setminus\{i\}})$, where $\xi_{i}:\mathbb{R}^{2^{|N|}-1}\rightarrow\mathbb{R}$. We restrict out consideration to the nonnegative constant-sum game of the class
\[\mbox{TU}(N)_{+c}=\left\{v\in \mbox{TU}(N):v(N)\neq 0, v(S)\geq 0, v(S)+v(N\setminus S)=v(N)\mbox{ for all }S\subseteq N\right\}\]
(Khmelnitskaya \cite[p.224-225]{khm03}).

Theorem. (Khmelnitskaya \cite[p.225]{khm03}). The only efficient, symmetric and marginalist value defined on $\mbox{TU}(N)_{c+}$ is the Shapley value. $\sharp$

The Potential.

Given a function $P:\mbox{TU}(N)\rightarrow\mathbb{R}$ which associates a real number $P(N,v)$ to every game $(N,v)\in \mbox{TU}(N)$, the {\bf marginal contribution} of player $i$ is defined as
\begin{equation}{\label{peteqa}}\tag{9}
P_{i}(N,v)=P(N,v)-P(N\setminus\{i\},v),
\end{equation}
where $i\in N$.

\begin{equation}{\label{har89da}}\tag{10}\mbox{}\end{equation}

Definition \ref{har89da}. (Hart and Mas-Colell \cite[p.591]{har89}). A function $P:\mbox{TU}(N)\rightarrow\mathbb{R}$ is called a potential function when the following conditions are satisfied:
\begin{equation}{\label{pereq3141}}\tag{11}
P(\emptyset ,v)=0\mbox{ and }\sum_{i\in N}P_{i}(N,v)=v(N)
\end{equation}
for all games $(N,v)\in \mbox{TU}(N)$. $\sharp$

From (\ref{peteqa}) and (\ref{pereq3141}), we see that
\[|N|\cdot P(N,v)=\sum_{i\in N}P(N,v)=\sum_{i\in N}P_{i}(N,v)+\sum_{i\in N}
P(N\setminus\{i\},v)=v(N)+\sum_{i\in N} P(N\setminus\{i\},v).\]
Therefore, we have
\begin{equation}{\label{pereq3142}}\tag{12}
P(N,v)=\frac{1}{|N|}\cdot\left [v(N)+\sum_{i\in N}P(N\setminus\{i\},v)\right ].
\end{equation}
In general, for $\emptyset\neq S\subseteq N$, we have
\begin{equation}{\label{bil98aeq4}}\tag{13}
P(\emptyset ,v)=0\mbox{ and }P(S,v)=\frac{1}{|S|}\cdot\left [v(S)+\sum_{i\in S}P(S\setminus\{i\},v)\right ].
\end{equation}
(Petrosjan and Zenkevich \cite[p.188]{pet} and Bilbao \cite[p.135]{bil98a})).

\begin{equation}{\label{petr1}}\tag{14}\mbox{}\end{equation}

Remark \ref{petr1}. (Petrosjan and Zenkevich \cite[p.188]{pet}). Starting with $P(\emptyset ,v)=0$, the expression (\ref{pereq3142}) determines $P(N,v)$ recursively. This proves the existence and uniqueness of the potential function and that $P(N,v)$ is uniquely determined by (\ref{pereq3141}) applied just to $(S,v)$ for all $S\subseteq N$. $\sharp$

\begin{equation}{\label{har89ta}}\tag{15}\mbox{}\end{equation}

Theorem \ref{har89ta}. (Petrosjan and Zenkevich \cite[p.188]{pet} and Hart and Mas-Colell \cite[p.591]{har89}). There exists a unique potential function $P$ defined on $\mbox{TU}(N)$. For every cooperative game $(N,v)$, the resulting payoff vector $(P_{1}(N,v),\cdots ,P_{i}(N,v),\cdots ,P_{N}(N,v))$ of marginal contributions coincides with the Shapley value of the game. Moreover, the potential of a game $(N,v)$ is uniquely determined by $(\ref{pereq3141})$ applied only to the game and its subgame (i.e. to $(S,v)$ for all $latex S\subseteq N).

Proof. From Remark \ref{petr1}, it remains to prove that $P_{i}(N,v)=\phi_{i}(v)$ for all cooperative games $(N,v)$ and all players $i\in N$, where $\boldsymbol{\phi}(N,v)$ is the Shapley value.

Method 1. We define
\begin{equation}{\label{har89eq23}}\tag{16}
P(N,v)=\sum_{S\subseteq N}\frac{c_{S}}{|S|},
\end{equation}
where $c_{S}$ is given in $(\ref{pereq3135})$. It is easily checked that (\ref{pereq3141}) is satisfied by this $P$. Hence (\ref{har89eq23}) defines the unique potential function. The result follows from Proposition \ref{har89p1}.

Method 2. We can show that $P_{i}(N,v)$ satisfy the standard axioms for the Shapley value by inductively using (\ref{pereq3142}). $\blacksquare$

We present another way of viewing the potential. Given a cooperative game $(N,v)$, the allocation of marginal contributions $v(N)-v(N\setminus\{i\})$ to player $i$ is, in general, not efficient. One way to resolve this difficulty is to add a new player, say player $0$, and extend the game to $N_{0}=N\cup\{0\}$ in such a way that the allocation of marginal contributions in the extended game becomes efficient. Formally, let $(N_{0},v_{0})$ be the extension of $(N,v)$, i.e., $v_{0}(S)=v(S)$ for all $S\subseteq N$. Then the requirement is
\begin{equation}{\label{pereq3143}}\tag{17}
v_{0}(N_{0})=\sum_{i\in N_{0}}\left (v_{0}(N_{0})-v_{0}(N_{0}\setminus\{i\})
\right )=\left (v_{0}(N_{0})-v(N)\right )+\sum_{i\in N}\left (v_{0}(N_{0})-v_{0}(N_{0}\setminus\{i\})\right ).
\end{equation}
This reduces to
\begin{equation}{\label{pereq3144}}\tag{18}
v(N)=\sum_{i\in N}\left (v_{0}(N_{0})-v_{0}(N_{0}\setminus\{i\})\right ),
\end{equation}
which yields the following restatement of the result of theorem.

Corollary. (Petrosjan and Zenkevich \cite[p.189]{pet}). There exists a unique extension $(N_{0},v_{0})$ of $(N,v)$ whose marginal contributions to the grand coalition are always efficient, more precisely, (\ref{pereq3143}) is satisfied for the game and all its subgames. It is given by $v_{0}(S\cup\{0\})=P(S,v)$ for all $S\subseteq N$, where $P$ is the potential function. $\sharp$

Note that the payoffs to the original players add up correctly to $v(N)$ in (\ref{pereq3144}). These are the Shapley values. Player $0$, whose payoff is the residual $P(N,v)-v(N)$, may be regarded as a “hidden player”.

\begin{equation}{\label{pert3147}}\tag{19}\mbox{}\end{equation}

Proposition \ref{pert3147}. (Petrosjan and Zenkevich \cite[p.190]{pet} and Hart and Mas-Colell \cite[p.592]{har89}). The potential function $P$ satisfies
\begin{equation}{\label{har89eq25}}\tag{20}
P(N,v)=\sum_{S\subseteq N}\frac{(|S|-1)!(|N|-|S|)!}{|N|!}\cdot v(S).
\end{equation}

Proof. The marginal contributions $P_{i}(N,v)$ of (\ref{har89eq25}) are easily seen to coincide with the Shapley value. Therefore (\ref{har89eq25}) is a potential function. $\blacksquare$

To interpret this last formula (\ref{har89eq25}), we consider the following probabilistic model of choosing random nonempty coalition $S\subseteq N$. First, we choose a size $s=1,2,\cdots ,n=|N|$ uniformly, i.e., with probability $1/n$ each. Second, choose a subset $S$ of size $s$, again uniformly, i.e., with probability $1/\tiny{\left (\begin{array}{c} n\\ s\end{array}\right )}$, where $s=|S|$. Equivalently, choose a random order of the $n$ elements of $N$ with probability $1/n!$ each, choose a cutting point $s$ with $1\leq s\leq n$, and let $S$ be the first $s$ elements in that order. The probability of choosing a set $S$ with $|S|=s$ is
\[p^{S}=\frac{1}{n}\cdot\frac{1}
{\left (\begin{array}{c} n\\ s\end{array}\right )}=
\frac{s!(n-s)!}{n\cdot n!}=\frac{s}{n}\cdot\frac{(s-1)!(n-s)!}{n!}=
\frac{|S|}{|N|}\cdot\frac{(|S|-1)!(|N|-|S|)!}{|N|!}.\]

Proposition. (Hart and Mas-Colell \cite[p.592]{har89}). Let $P$ be the potential function. Then
\begin{equation}{\label{pereq3146}}\tag{21}
P(N,v)=\mathbb{E}\left [\frac{|N|}{|S|}\cdot v(S)\right ],
\end{equation}
for every cooperative game $(N,v)$, where $\mathbb{E}$ denotes the expectation over $S$ with respect to the foregoing probability model.

Proof. We see that
\[\mathbb{E}\left [\frac{|N|}{|S|}\cdot v(S)\right ]=\sum_{S\subseteq N}
p^{S}\cdot\frac{|N|}{|S|}\cdot v(S)=\sum_{S\subseteq N}\frac{(|S|-1)!(|N|-|S|)!}{|N|!}\cdot v(S).\]
From Proposition \ref{pert3147}, the proof is complete. $\blacksquare$

We can rewrite (\ref{pereq3146}) as
\[\frac{P(N,v)}{|N|}=\mathbb{E}\left [\frac{v(S)}{|S|}\right ].\]
Thus the potential is the expected normalized worth, or, equivalently, the per-capita potential $P(N,v)/|N|$ equals the average per-capita worth $v(S)/|S|$. Hence the potential provides a most natural one-number summary of the game. One may regard $P$ as an operator that associates to each game $(N,v)$ another game $(N,Pv)$ given by $(Pv)(S)=P(S,v^{S})$ for all $S\subseteq N$. It is easily checked that this is a linear, positive, and symmetric operator; it is one-to-one and onto, and its fixed points are exactly the inessential games. If $(N,v)$ is a market game (i.e., totally balanced), then $Pv\leq v$ (Hart and Mas-Colell \cite[p.593]{har89}).

Next we are going to present another potential by considering the coalition structure. Let us recall the ${\cal F}$-restricted game in Definition \ref{bil98ad2}.

\begin{equation}{\label{bil98ad200}}\tag{22}\mbox{}\end{equation}

Definition \ref{bil98ad200}. (Bilbao \cite[p.135]{bil98a}). Let $(N,{\cal F})$ be a partition system. The ${\cal F}$-restricted potential of the game $(N,v)$ is defined by $P(N,v^{\cal F})$. $\sharp$

The recursive procedure defined by the formula (\ref{bil98aeq4}) implies an algorithm for computing $P(N,v^{\cal F})$. A new algorithm, in terms of $v$, is stated below.

\begin{equation}{\label{bil98at200}}\tag{23}\mbox{}\end{equation}

Theorem \ref{bil98at200}. (Bilbao \cite[p.135]{bil98a}). The restricted potential $P(N,v^{\cal F})$ satisfies:
\[P(S,v^{\cal F})=\left\{\begin{array}{ll}
{\displaystyle \frac{1}{|S|}\cdot\left [v(S)+\sum_{i\in S}P(S\setminus\{i\},
v^{\cal F})\right ]} & \mbox{for all }S\in {\cal F}.\\
\sum_{S_{k}\Pi_{S}}P(S_{k},v^{\cal F}) & \mbox{for all }S\not\in {\cal F}.
\end{array}\right .\]

Preservations of Differences.

Let $(N,v)$ be a cooperative game and $x_{i}(S)$ be the payoff of player $i$ in the subgame $(S,v)$ for $i\in S\subseteq N$. The constants $\{d_{ij}\}_{i,j\in N}$ are said to be compatible if and only if $d_{ii}=0$, $d_{ij}=-d_{ji}$ and $d_{ij}+d_{jk}=d_{ik}$ for all $i,j,k\in N$. We say that a payoff vector ${\bf x}=(x_{i})_{i\in N}$ preserves differences according to $\{d_{ij}\}$ if and only if $x_{i}-x_{j}=d_{ij}$ for all $i,j\in N$ (Hart and Mas-Colell \cite[p.594]{har89}).

It is trivial to verify that, given compatible constants $\{d_{ij}\}$, there exists a single efficient payoff vector ${\bf x}$ that preserves differences:
\begin{equation}{\label{har89eqb}}\tag{24}
x_{i}=\frac{1}{|N|}\left [v(N)+\sum_{j\in N}d_{ij}\right ]\mbox{ and }x_{j}=x_{i}-d_{ij}.
\end{equation}
Therefore, in order to have a well-defined solution, we need to specify the differences $\{d_{ij}\}$. We are going to construct the solution recursively. Let $(T,v)$ be a subgame. Suppose that payoffs of all the strict subgames $(S,v)$ of $(T,v)$, where $S\subseteq T$ and $S\neq T$, have been determined. Then we convene that the difference $d_{ij}$ to be preserved is given by
\[d_{ij}=x_{i}(T\setminus\{j\})-x_{j}(T\setminus\{i\}).\]
It will be seen below that these differences are indeed compatible. According to (\ref{har89eqb}), we can obtain a single efficient payoff vector of subgame $(T,v)$, which preserves differences. For any fixed $i\in N\setminus T$, by using the above procedure, we can obtain a single efficient payoff vector of subgame $(T\cup\{i\},v)$, which preserves differences. Inductively, we can obtain a single efficient payoff vector of game $(N,v)$. According to the constructive procedure, we see that
\begin{equation}{\label{har89eqe}}\tag{25}
x_{i}(T)-x_{j}(T)=d_{ij}=x_{i}(T\setminus\{j\})-x_{j}(T\setminus\{i\})
\end{equation}
(Hart and Mas-Colell \cite[p.594]{har89}).

Theorem. (Hart and Mas-Colell \cite[p.595]{har89}). The construction of the above solution is well-defined. Moreover, the solution is generated by a potential function. Therefore, the solution coincides with the Shapley value.

Proof. Consider the cooperative game $(N,v)$. Assume, by induction, that the solution has been already determined for all strict subgames of $(N,v)$. We set
\begin{equation}{\label{har89eq35}}\tag{26}
x_{i}(S)=P(S,v)-P(S\setminus\{i\},v),
\end{equation}
where $P$ is the unique potential function. The efficiency says that $\sum_{i\in N}x_{i}(N)=v(N)$. Therefore, $x_{i}(i)=v(i)$. By (\ref{pereq3142}), we also see that $P(\{i\},v)=v(i)$. This shows that (\ref{har89eq35}) is satisfied for singletions, i.e., $|S|=1$. In other words, the initial conditions is known. Applying (\ref{har89eq35}) to coalitions of size $|T|-1$ implies that the differences $d_{ij}$ are compatible, since
\begin{align*}
d_{ij} & =x_{i}(T\setminus\{j\})-x_{j}(T\setminus\{i\})\\
& =\left [P(T\setminus\{j\},v)-P(T\setminus\{i,j\},v)\right ]-\left [P(T\setminus\{i\},v)-P(T\setminus\{i,j\},v)\right ]\\
& =P(T\setminus\{j\},v)-P(T\setminus\{i\},v)=P_{j}(N,v)-P_{i}(N,v)
\end{align*}
satisfies the definition. Therefore, the efficient payoffs ${\bf x}(T)=(x_{i}(T))_{i\in T}$ of subgame $(T,v)$ is well-defined according to (\ref{har89eqb}), and we have
\begin{equation}{\label{har89eqd}}\tag{27}
x_{i}(T)-x_{j}(T)=d_{ij}=P(T\setminus\{j\},v)-P(T\setminus\{i\},v).
\end{equation}
Since ${\bf x}(T)$ is efficient, we have
\begin{equation}{\label{har89eqc}}\tag{28}
\sum_{j\in T}x_{j}(T)=v(T)
\end{equation}
From (\ref{har89eqd}), we fix $i$ and average over $j$ on $T$. Then, from (\ref{har89eqc}), we have
\[x_{i}(T)-\frac{1}{|T|}v(T)=\frac{1}{|T|}\cdot\sum_{j\in T}\left [P(T\setminus\{j\},v)-P(T\setminus\{i\},v)\right ].\]
Thus, by (\ref{pereq3142}),
\[x_{i}(T)+P(T\setminus\{i\},v)=\frac{1}{|T|}\left [v(T)+\sum_{j\in T}P(T\setminus\{j\},v)\right ]=P(T,v).\]
It shows that (\ref{har89eq35}) is satisfied for $S=T$. Inductively, we have $x_{i}(N)=P(N,v)-P(N\setminus\{i\},v)=P_{i}(N,v)$ by (\ref{har89eq35}). From Theorem \ref{har89ta}, ${\bf x}(N)=(x_{i}(N))_{i\in N}$ is the Shapley value. This completes the proof. $\blacksquare$

Consistency.

Let $\boldsymbol{\phi}:\mbox{TU}(N)\rightarrow\mathbb{R}^{|N|}$ be a function. Then $\boldsymbol{\phi}(N,v)$ be a vector in $\mathbb{R}^{|N|}$. We shall write $\phi_{i}(N,v)$ for its $i$th coordinate, i.e., $\boldsymbol{\phi}(N,v)=(\phi_{i}(N,v))_{i\in N}$. The function $\boldsymbol{\phi}$ is also called a solution function. For any coalition $T\subseteq N$, we define the reduced game $(T,v^{T}_{\boldsymbol{\phi}})$ as follows:
\begin{equation}{\label{har89eq41}}\tag{29}
v^{T}_{\scriptsize \boldsymbol{\phi}}(S)=v(S\cup T^{c})-\sum_{i\in T^{c}}\phi_{i}(S\cup T^{c},v)\mbox{ for all }S\subseteq T,
\end{equation}
where $T^{c}=N\setminus T$. A solution function $\boldsymbol{\phi}$ is consistent if and only if, for every cooperative game $(N,v)$ and every coalition $T\subseteq N$, we have
\begin{equation}{\label{har89eq42}}\tag{30}
\phi_{j}(T,v^{T}_{\scriptsize \boldsymbol{\phi}})=\phi_{j}(N,v)\mbox{ for all }j\in T.
\end{equation}
The interpretation is as follows. Given the solution function $\boldsymbol{\phi}$, a cooperative game $(N,v)$ and a coalition $T\subseteq N$, the members of $T$ (or, more precisely, every subcoalition of $T$) need to consider the total payoff remaining after paying the members of $T^{c}$ according to $\boldsymbol{\phi}$. To compute the worth of a coalition $S\subseteq T$ in the reduced game, we assume that the members of $T\setminus S$ are not present. In other words, one considers the game $(S\cup T^{c},v)$, in which payoffs are distributed according to $\boldsymbol{\phi}$. The appropriateness of this definition of reduced game depends on the particular situation being modeled; more specifically, on the concrete assumptions underlying the determination of the characteristic function (Hart and Mas-Colell \cite[p.597]{har89}).

Note that one usually delas with efficient solution functions, i.e.,
\[\sum_{i\in N}\phi_{i}(N,v)=v(N).\]
We then have
\[v(S\cup T^{c})=\sum_{i\in S\cup T^{c}}\phi_{i}(S\cup T^{c},v).\]
In this case, (\ref{har89eq41}) can be rewritten as
\[v^{T}_{\scriptsize \boldsymbol{\phi}}(S)=\sum_{i\in S}\phi_{i}(S\cup T^{c},v).\]

Lemma. (Hart and Mas-Colell \cite[p.597]{har89}). The solution function $\boldsymbol{\phi}$ is consistent if and ony if (\ref{har89eq42}) is satisfied for all games $(N,v)$ and all $T\subseteq N$ with $|T^{c}|=1$.

Proof. Use induction on the size of $T$. $\blacksquare$

The above lemma shows that whether $\boldsymbol{\phi}$ is consistent or not may be determined by considering only singleton coalitions $T^{c}$.

Proposition. (Hart and Mas-Colell \cite[p.597]{har89}). The Shapley value is a consistent solution function. $\sharp$

A solution function $\boldsymbol{\phi}$ is standard for two-person games if and only if
\[\phi_{i}(\{i,j\},v)=v(i)+\frac{1}{2}\left [v(\{i,j\})-v(i)-v(\{j\})\right ]\]
for all $i\neq j$ and all $v$. The “surplus” $v(\{i,j\})-v(i)-v(\{j\})$ is equally divided among the two players. The Shapley value and the nucleolus satisfy this requirement (Hart and Mas-Colell \cite[p.598]{har89}).

Theorem. (Hart and Mas-Colell \cite[p.598]{har89}). The solution function $\boldsymbol{\phi}$ is the Shapley value if and only if the following $\boldsymbol{\phi}$ is consistent and standard for two-person games. $\sharp$

A solution function $\boldsymbol{\phi}$ satisfies the equal treatment property if and only if, for any cooperative game $(N,v)$ and any two players $i,j\in N$,
\[\mbox{$v(S\cup\{i\})=v(S\cup\{j\})$ for all $S\subseteq N\setminus\{i,j\}$ implies $\phi_{i}(N,v)=\phi_{j}(N,v)$}.\]
Let $(N,v_{1})$ and $(N,v_{2})$ be two equivalent games, i.e., there are real constants $a>0$ and $\{b_{i}\}_{i\in N}$ satisfying
\[v_{1}(S)=a\cdot v_{2}(S)+\sum_{i\in S}b_{i}\mbox{ for all }S\subseteq N.\]
A solution function $\boldsymbol{\phi}$ is called transferable-utility invariant (TU-invariant) if and only if the following equality holds
\[\phi_{i}(N,v_{1})=a\cdot\phi_{i}(N,v_{2})+b_{i}\]
for all $i\in N$. Note that, for two-person games, the equal treatment property amounts to just
\[\phi_{i}(\{i,j\},v)=\phi_{j}(\{i,j\},v)=\frac{1}{2}v(\{i,j\})\]
whenever $v(i)=v(\{j\})$ (Hart and Mas-Colell \cite[p.600]{har89}).

Theorem. (Hart and Mas-Colell \cite[p.600]{har89}). The solution function $\boldsymbol{\phi}$ is the Shapley value if and only if the following conditions are satisfied:

$\boldsymbol{\phi}$ is consistent;
for two-person games, $\boldsymbol{\phi}$ is efficient and TU-invariant, and satisfies the equal treatment property.

Alternative Axiomatizations.

In the sequel, we are going to introduce the alternative axiomatizations of the Shapley value. Let us recall that the Shapley value is the unique value satisfying efficiency, symmetry, dummy, and additivity. Young \cite{you85} established an alternative aximatic characterization of the Shapley value by introducing the following axiom of marginality. Given a cooperative game $(N,v)$, we consider the marginal contribution of $i$ to $S$ as $\Delta_{i}v(S)$ defined in (\ref{ga35}). The value $\boldsymbol{\phi}$ is said to satisfy the marginality if and only if, for all $i\in N$, $\Delta_{i}v=\Delta_{i}w$ implies $\phi_{i}(v)=\phi_{i}(w)$. Then the Shapley value is the unique value satisfying efficiency, symmetry and marginality (Chun \cite[p.121-122]{chu89}).

Given $T\subseteq N$ such that $T\neq\emptyset$ and $\alpha\in\mathbb{R}$, the basis game with base $T$ and size $\alpha$ is defined by
\[v_{\alpha}^{T}(S)=\left\{\begin{array}{ll}
\alpha , & \mbox{if $T\subseteq S$}\\
0, & \mbox{otherwise}.
\end{array}\right .\]
Let $v_{\emptyset}$ be the trivial game $v_{\emptyset}(S)=0$ for all $S\subseteq N$. We consider the following axioms.

(C1:Triviality). $\boldsymbol{\phi}(v_{\emptyset})=0$. Triviality requires that if a game is such that the worths of all coalitions
are zero, then every agent receives nothing.
(C2:Coalitional Strategic Equivalence). Given two cooperative games $(N,v_{1})$ and $(N,v_{2})$, for all $\emptyset\neq T \subseteq N$ and all $\alpha\in\mathbb{R}$, if $v_{1}=v_{2}+v_{\alpha}^{T}$, then $\phi_{i}(v_{1})=\phi_{i}(v_{2})$ for all $i\in N\setminus T$. Coalitional strategic equivalence requires that adding a constant to the worth of all coalitions containing a given coalition $T$ does not affect the payoffs of players that do not belong to $T$.
(C3: Fair Ranking). Given two cooperative games $(N,v_{1})$ and $(N,v_{2})$, for all $T\subseteq N$, if $v_{1}(S)=v_{2}(S)$ for all $S\neq T$, then $\phi_{i}(v_{1})>\phi_{j}(v_{1})$ implies $\phi_{i}(v_{2})>\phi_{j}(v_{2})$ for all $i,j\in T$. Fair ranking requires that if two games are the same except for the worth of a given coalition $T$, then the relative payoffs of the players belonging to $T$ are not affected by the change in the worth of $T$ (Chun \cite[p.122-123]{chu89}).

For real numbers $a$ and $b$, we denote by $a\vee b=\max\{a,b\}$ and $a\wedge b=\min\{a,b\}$. For $v_{1},v_{2}\in \mbox{TU}(N)$, $v_{1}\vee v_{2}$ and $v_{1}\wedge v_{2}$ denotes the games defined by
\[(v_{1}\vee v_{2})(S)=v_{1}(S)\vee v_{2}(S)\mbox{ and }(v_{1}\wedge v_{2})(S)=v_{1}(S)\wedge v_{2}(S)\]
for all $S\subseteq N$. For each of the classes of simple games, control games and monotonic simple games, it holds that if $v_{1}$ and $v_{2}$ are in the class, so are $v_{1}\vee v_{2}$ and $v_{1}\wedge v_{2}$ (Feltkamp \cite[p.180]{fel95}).

Given a permutation $\pi$ on $N$, we recall that the game $(N,\pi v)$ is defined by $(\pi v)(S)=v(\pi (S))$ for all $S\subseteq N$. Let $G\subseteq \mbox{TU}(N)$ be a subclass. A {\bf solution} on $G$ is a vector-valued function $\boldsymbol{\phi}:G\rightarrow\mathbb{R}^{|N|}$, assigning the real number $\phi_{i}(v)$ to each player $i$ in the game $(N,v)\in G$. We introduce the following axioms:

(F1: Efficiency). $\sum_{i\in N}\phi_{i}(v)=v(N)$ for all games $(N,v)v\in G$;
(F2: Anonymity). For all games $(N,v)\in G$ and for all permutations $\pi$ of $N$ such that $(N,\pi v)\in G$, we have $\phi_{\pi (i)}(v)=\phi_{i}(\pi v)$ for all $i\in N$;
(F3: Null Player Property). $\phi_{i}(v)=0$ for all games $(N,v)\in G$ with null player $i$;
(F4: Transfer Property). For all games $(N,v_{1}),(N,v_{2})\in G$ such that $(N,v_{1}\vee v_{2}),(N,v_{1}\wedge v_{2})\in G$,
we have $latex \boldsymbol{\phi}(v_{1}\vee v_{2})+\boldsymbol{\phi}(v_{1}\wedge v_{2})=
\boldsymbol{\phi}(v_{1})+\boldsymbol{\phi}(v_{2})$;
(F5: Carrier Property). For all games $(N,v)\in G$ and each carrier $T$, we have $\sum_{i\in T}\phi_{i}(v)=v(T)$;
F6: Additivity). For all games $(N,v_{1}),(N,v_{2})\in G$ satisfying $(N,v_{1}+v_{2})\in G$, we have $\boldsymbol{\phi}(v_{1}+v_{2})=\boldsymbol{\phi}(v_{1})+\boldsymbol{\phi}(v_{2})$.

The name of axiom (F4) is motivated by the following observation. The game $v_{1}\wedge v_{2}$ arises from $v_{1}$ when all of the coalitions that win only in $v$ are made losing; $v_{1}\vee v_{2}$ arises from $v_{2}$ when these same coalitions are made winning. Hence, $v_{1}\wedge v_{2}$ and $v_{1}\vee v_{2}$ arise from $v_{1}$ and $v_{2}$ when winning coalitions are “transferred” from one game to the other (Feltkamp \cite[p.181-182]{fel95} and Weber \cite[p.109]{web88}).

We have the following observations.

If $G^{(1)}\subseteq G^{(2)}$ and a solution $\boldsymbol{\phi}$ satisfies any of the above axioms on $G^{(2)}$, it satisfies the axioms on the class $G^{(1)}$ as well.
A solution which is additive on $\mbox{TU}(N)$ satisfies the transfer property on $\mbox{TU}(N)$ and hence also on any subclass. To prove this, we take $v_{1},v_{2}\in \mbox{TU}(N)$. Then using additivity
\[\boldsymbol{\phi}(v_{1}\vee v_{2})+\boldsymbol{\phi}
(v_{1}\wedge v_{2})=\boldsymbol{\phi}(v_{1}\vee v_{2}+v_{1}\wedge v_{2})
=\boldsymbol{\phi}(v_{1}+v_{2})=\boldsymbol{\phi}(v_{1})+\boldsymbol{\phi}(v_{2}).\]

The carrier property is equivalent to the efficiency and null player properties together. It is well known that the Shapley value expressed by (\ref{peteq25}) satisfies the axioms (F1), (F2), (F3) and (F6) on $\mbox{TU}(N)$ and hence on any subclass of $\mbox{TU}(N)$.

Given a cooperative game $(N,v)$, for $i,j\in N$, the players $i,j$ are substitutes in $v$ if and only if, for every coalition $S\subseteq N\setminus\{i,j\}$,
\[v(S\cup\{i\})=v(S\cup\{j\}).\]
We also introduce the following axioms

(N1: Symmetry). The solution function $\boldsymbol{\phi}$ is symmetric if and only if, for every $(N,v)\in G$ and every two players $i,j$ that are substitutes in $v$, we have $\phi_{i}(v)=\phi_{j}(v)$.
(N2: Strong Positivity). The solution function $\boldsymbol{\phi}$ is strongly positive if and only if, for any player $i\in N$ and any two games $(N,v_{1}),(N,v_{2}\in G$ with $v_{1}(S\cup\{i\})-v_{1}(S)\geq v_{2}(S\cup\{i\})-v_{2}(S)$, we have $\phi_{i}(v_{1})\geq\phi_{i}(v_{2})$.

Proposition. (Chun \cite[p.123-124]{chu89}). We have the following properties.

(i) Dummy and additivity together imply coalitional strategic equivalence.

(ii) Marginality implies coalitional strategic equivalence.

(iii) Symmetry amd additivity together imply fair ranking. $\sharp$

\begin{equation}{\label{chu89t1}}\tag{31}\mbox{}\end{equation}

Theorem \ref{chu89t1}. (Chun \cite[p.124]{chu89}). The Shapley value is the unique value satisfying efficiency, triviality, coalitional strategic equivalence and fair ranking. $\sharp$

We can show that all the axioms in Theorem \ref{chu89t1} are independent and any three do not imply additivity (Chun \cite[p.128]{chu89}).

Theorem. (Feltkamp \cite[p.182]{fel95}). We have the following properties.

(i) The unique solution on the class of control games satisfying axioms (F1)–(F4) is the Shapley value.

(ii) The unique solution on the class of simple games satisfying axioms (F1)–(F4) is the Shapley value. $\sharp$

In order to characterize the Shapley value on $\mbox{TU}(N)$, we need some lemmas. The zero game in $\mbox{TU}(N)$ is denoted by $\underline{0}$. Given any coalition $S$ in $N$, the {\bf Dirac game} $\delta_{S}$ is defined by
\[\delta_{S}(T)=\left\{\begin{array}{ll}
1 & \mbox{if $T=S$}\\ 0 & \mbox{otherwise}\end{array}\right .\]

\begin{equation}{\label{fel95l3}}\tag{32}\mbox{}\end{equation}

Lemma \ref{fel95l3}. (Feltkamp \cite[p.183]{fel95}). The solution $\boldsymbol{\phi}$ on $\mbox{TU}(N)$ satisfies axiom (F4) with $\boldsymbol{\phi}(\underline{0})={\bf 0}$ if and only if, for all cooperative games $(N,v)\in \mbox{TU}(N)$, we have
\begin{equation}{\label{fel95eq1}}\tag{33}
\boldsymbol{\phi}(v)=\sum_{\{S:S\subseteq N\}}\boldsymbol{\phi}(v(S)\cdot\delta _{S}). \sharp
\end{equation}

While Lemma \ref{fel95l3} shows that a solution concept satisfying axiom (F4) is determined by its value on multiples of Dirac games, the next lemma shows it is also determined by its values on multiples on unanimity games.

Proposition. (Feltkamp \cite[p.184]{fel95}). For each $\emptyset\neq S\subseteq N$ and each real number $\alpha$, we assume that a vector $\boldsymbol{\phi}_{\alpha ,S}\in\mathbb{R}^{N}$ is given with $\boldsymbol{\phi}_{0,S}={\bf 0}$. Then, there exists a unique solution $\boldsymbol{\phi}$ on $\mbox{TU}(N)$ satisfying axiom (F4) satisfying $latex \boldsymbol{\phi}(\alpha\cdot u_{S})=
\boldsymbol{\phi}_{\alpha ,S}$ for all $\alpha\in\mathbb{R}$ and all $\emptyset\neq S\subseteq N$. $\sharp$

Theorem. (Feltkamp \cite[p.185]{fel95}). The Shapley value is the unique solution on $\mbox{TU}(N)$ satisfying axioms (F1)–(F4). $\sharp$

Another solution concept is the {\bf Banzhaf value} $\boldsymbol{\eta}$ defined on $\mbox{TU}(N)$ by
\[\eta_{i}(v)=\sum_{\{S:i\in S\}}(v(S)-v(S\setminus\{i\}))\]
for all $i\in N$. It is easily seen that the Banzhaf value satisfies axioms (F2), (F3), F(4) and (F6). Note that it does not satisfy axiom (F1). (Feltkamp \cite[p.185]{fel95}).

Theorem. (Feltkamp \cite[p.185-186]{fel95}). We define $\bar{\eta}(v)=\sum_{i\in N}\eta_{i}(v)$. Then, we have the following properties.

(i) The Banzhaf value is the unique value $\boldsymbol{\phi}$ defined on the set of all control games satisfying axioms (F2)–(F4) satisfying
\begin{equation}{\label{fel95eq6}}\tag{34}
\sum_{i\in N}\phi_{i}(v)=\bar{\eta}(v)
\end{equation}
for all $v$.

(ii) The Banzhaf value is the unique value $\boldsymbol{\phi}$ on the set of all simple games satisfying axioms (F2)–(F4) and (\ref{fel95eq6}).

(iii) The Banzhaf value is the unique value $\boldsymbol{\phi}$ on $\mbox{TU}(N)$ satisfying axioms (F2)–(F4) and (\ref{fel95eq6}). $\sharp$

Given a cooperative game $(N,v)$, we denote by $G(v)$ the additive group generated by the game $v$ and all of its subgames, i.e.,
\[G(v)=\left\{w\in \mbox{TU}(N):w=\sum k_{i}v^{S_{i}}\mbox{ where $k_{i}$ are
integers and $S_{i}$ coalitions}\right\}.\]
(Neyman \cite[p.117]{ney89}).

Theorem. (Neyman \cite[p.117]{ney89}). Given a cooperative game $(N,v)$, any solution function $\boldsymbol{\phi}$ from $G(v)$ into $\mathbb{R}^{|N|}$ that satisfies efficient axiom (F1), additive axiom (F6), null player axiom (F3) and symmetric axiom (N1) is the Shapley value. $\sharp$

Theorem. (Neyman \cite[p.117]{ney89}). Given a cooperative game $(N,v)$, any solution function $\boldsymbol{\phi}$ from $G(v)$ into $\mathbb{R}^{|N|}$ that satisfies efficient axiom (F1), symmetric axiom (N1) and strongly positive axiom (N2) is the Shapley value. $\sharp$

We denote by $G(N)$ the set of all superadditive games. Then A function $\boldsymbol{\phi}:G(N)\rightarrow (\mathbb{R}_{+}^{N})^{2^{N}}$ (i.e., for $v\in G(N)$, $\boldsymbol{\phi}(v)$ is a function $\boldsymbol{\phi}:2^{N}\rightarrow\mathbb{R}_{+}^{N}$) is said to be a Shapley function when the following axioms
are satisfied:

(TTI1: Efficiency). If $v\in G(N)$ and $S\subseteq N$ then
\[\sum_{i\in N}\phi_{i}(v)(S)=v(S)\mbox{ and }\phi_{i}(v)(S)=0\mbox{ for }i\not\in S,\]
where $\phi_{i}(v)(S)$ is the $i$th element of $\boldsymbol{\phi}(v)(S)$;
(TTI2: Carrier). If $v\in G(N)$, $S\subseteq N$ and $T$ a carrier in a coalition $S$, then $\phi_{i}(v)(S)=\phi_{i}(v)(T)$ for all $i\in N$;
(TTI3: ). If $v\in G(N)$, $S\subseteq N$ and $v(S\cup\{i\})=v(S\cup\{j\})$ for $i,j\in S$ and $S\subseteq S\setminus\{i,j\}$, then $\phi_{i}(v)(S)=\phi_{j}(v)(S)$;
(TTI4: Additivity). If $v_{1},v_{2}\in G(N)$, then $\phi_{i}(v_{1}+v_{2})(S)=\phi_{i}(v_{1})(S)+\phi_{i}(v_{2})(S)$ for all $i\in N$.

We see that $\boldsymbol{\phi}(v)(N)$ is the usual Shapley value. The unique explicit form of a Shapley function on $G(N)$ is obtained by extending the Shapley value (Tsurumi et al. \cite[p.600]{tsu01}).

\begin{equation}{\label{tsu01t1}}\tag{35}\mbox{}\end{equation}

Theorem \ref{tsu01t1}. (Tsurumi et al. \cite[p.600]{tsu01}). We define a function $\boldsymbol{\phi}:G(N)\rightarrow (\mathbb{R}_{+}^{N})^{2^{N}}$ by
\[\phi_{i}(v)(S)=\left\{\begin{array}{ll}
{\displaystyle \sum_{\{T:T\subseteq S,i\in T\}}
\frac{(|T|-1)!(|S|-|T|)!}{|S|!}\cdot\left [v(T)-v(T\setminus\{i\})\right ]}, &
\mbox{ if $i\in S$}\\
0, & \mbox{if $i\not\in S$}.
\end{array}\right .\]
Then the function $\boldsymbol{\phi}$ is the unique Shapley function on $G(N)$. $\sharp$

Proposition. (Tsurumi et al. \cite[p.600]{tsu01}). If the superadditive game $(N,v)$ is convex, then the vector $(\phi_{i}(v)(S))_{S\subseteq N,i\in S}$ is a PMAS. $\sharp$