The Shapley Value As A Von Neumann-Morgenstern Utility

James Edwin Meadows (1828-1888) was a British painter.

The Shapley value is shown to be a von Neumann-Morgenstern utility function. The concept of strategic risk is introduced, and it is shown that the Shapley value of a game equals its utility if and only if the underlying preferences are neutral to both ordinary and strategic risk (Roth \cite[p.657]{rot}).

Utility Theory.

We summarize an axiomatization of utility. A set $M$ is a mixture set if, for any elements $a,b\in M$ and for any number $p\in [0,1]$, we can associate another element of $M$ denoted by $[pa;(1-p)b]$ called a lottery between $a$ and $b$. For $p,q\in [0,1]$, we assume that lotteries have the following properties for all $a,b\in M$:

$[1a;ob]=a$;
$[pa;(1-p)b]=[(1-p)b;pa]$;
$[q[pa;(1-p)b];(1-q)b]=[pqa;(1-pq)b]$.

A preference on $M$ is defined to be a binary relation $\succeq$ such that, for any $a,b\in M$, either $a\succeq b$ or $b\succeq a$ must hold, and if $a\succeq b$ abd $b\succeq c$ then $a\succeq c$. We write $a\succ b$ if $a\succeq b$ and $b\not\succeq a$ and $a\sim b$ if $a\succeq b$ and $b\succeq a$ (Roth \cite[p.658]{rot}).

A real-valued function $u$ defined on a mixture set $M$ is a utility function for the preference $\succeq$ if it is order preserving, i.e., for $a,b\in M$, $u(a)>u(b)$ if and only if $a\succ b$, and if
\[u([pa;(1-p)b])=pu(a)+(1-p)u(b).\]

If $\succeq$ is a preference ordering on a mixture set $M$, then the following conditions insure that a utility function exists:

(a) For any $a,b,c\in M$, the set $\{p:[pa;(1-p)b]\succeq c\}$ and $\{p:c\succeq [pa;(1-p)b]\}$ are closed;
(b) If $a_{1},a_{2}\in M$ and $a_{1}\sim a_{2}$, then, for any $b\in M$, we have $[\frac{1}{2}a_{1},\frac{1}{2}b]=[\frac{1}{2}a_{2}, \frac{1}{2}b]$.

The utility function is unique up to an affine transformation. For any element $x\in M$, the utility of $x$ can be given by
\[u(x)=\frac{p_{ab}(x)-p_{ab}(r_{0})}{p_{ab}(r_{1})-p_{ab}(r_{0})},\]
where $a,b,r_{1},r_{1}$ are elements of $M$ such that $a\succeq x\succeq b$ and $a\succeq r_{1}\succeq r_{0}\succeq b$ and, for any $y\in M$, such that $a\succeq y\succeq b$, $p_{ab}(y)$ is defined by
\begin{equation}{\label{roteq23}}\tag{1}
y\sim [p_{ab}(y)a;(1-p_{ab}(y))b].
\end{equation}
It can be shown that the numbers $p_{ab}(\cdot)$ are well-defined, and the functuion $u(\cdot)$ is independent of the choice of $a$ and $b$. The fixed elements $r_{0}$ and $r_{1}$ determine the origin and scale of the utility function. Note that $u(r_{0})=0$ and $u(r_{1})=1$ (Roth \cite[p.658]{rot}).

A Utility Function for Games.

We denote by $Z^{N}$ the class of games which are positive-valued, i.e., games for which $v(S)\geq 0$ for all $S\subseteq N$. A player $i\in N$ is called a dummy for a game $v$ if it is not contained in every carrier. (Note that this differs slightly the usual definition of a dummy.) Denote by $D_{i}^{N}\subseteq Z^{N}$ the class of games for which $i$ is a dummy. It will be convenient to define the games $v_{0}$ and $v_{i}$ by
\[v_{0}(S)=0\mbox{ and }v_{i}(S)=\left\{\begin{array}{ll}
1 & \mbox{if $i\in S$}\\ 0 & \mbox{if $i\not\in S$}
\end{array}\right .\]
for all $S\subseteq N$. In the game $v_{0}$, all players are dummies, and in $v_{i}$, all players but $i$ are dummies (Roth \cite[p.660]{rot}).

We will be interested in the mixture set $M$ generated by $Z^{N}\times N$ of strategic players. Thus, $M$ consists of all lotteries of the form $[p(v,i);(1-p)(w,j)]$, where $(v,i)$ and $(w,j)$ are elements of $Z^{N}\times N$. We assume that a preference $\succeq$ is defined on $M$ which satisfies Conditions (a) and (b). We read $(v,i)\succeq (w,j)$ as it is preferred to play player $i$ in game $v$ than to play player $j$ in game $w$. We impose the following conditions on the preferences.

(c) For all $i\in N$, $v\in Z^{N}$ and for any permutation $\pi$, we have $(v,i)\sim (\pi v,\pi (i))$;
(d) If $v\in D_{i}^{N}$, then $(v,i)\sim (v_{0},i)$, and, for every $v\in Z^{N}$ and $i\in N$, we have $(v,i)\succeq (v_{0},i)$ and $(v_{i},i)\succ (v_{0},i)$;
(e) For any number $c>1$, and for every $v\in Z^{N}$, $i\in N$, we have $(v,i)\sim [(1/c)(cv,i);(1-1/c)(v_{0},i)]$.

Condition (c) merely says that the names of the players do not determine their desirability in a game. Condition (d) says that playing any player in $Z^{N}$ is at least as desirable as being a dummy in any game, and there is some strategic player, namely $(v_{i},i)$, which is strictly preferable to being a dummy. Condition (e) takes note of the fact that games are defined in terms of a utility function. It says that if two strategic players are identical except for the fact that the utility obtainable in one is a positive multiple of the utility obtainable in the other, then the first is indifferent to the appropriate gamble between the second, and the prospect of receiving zero (Roth \cite[p.660-661]{rot}).

We are noe in a position to define a utility function for strategic players, which shall call strategic utility. Such a function exists, since the preference $\succeq$ satisfies Conditions (i) and (ii). The strategic utility of a game $v$ is the vector $latex \boldsymbol{\theta}=
(\theta_{1}(v),\cdots ,\theta_{n}(v))$, where
\[\theta_{i}(v)\equiv\theta (v,i)=\frac{p_{ab}((v,i))-p_{ab}(r_{0})}{p_{ab}(r_{1})-p_{ab}(r_{0})}\]
for $p_{ab}(\cdot)$ as in (\ref{roteq23}) and for $a,b,r_{0},r_{1}\in M$ such that $a\succeq (v,i)\succeq b$, and $a\succeq r_{1}\succeq r_{0}\succeq b$. Fixing $r_{1}=(v_{i},i)$ and $r_{0}=(v_{0},i)$, we get $\theta_{i}(v_{i})=1$ and $\theta_{i}(v_{0})=0$. Condition (d) insures that we can always take $b=r_{0}$ so that $p_{ab}(r_{0})=0$ for all $a\in M$ (Roth \cite[p.661]{rot}).

\begin{equation}{\label{rotl1}}\tag{2}\mbox{}\end{equation}

Proposition \ref{rotl1}. (Roth \cite[p.661]{rot}). For any permutation $\pi$ and for every $i\in N$, we have $\theta_{\pi (i)}(\pi v)=\theta_{i}(v)$. $\sharp$

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

Proposition \ref{rotl2}. (Roth \cite[p.661]{rot}). For any number $c\geq 0$ and for any $i\in N$, we have $\theta_{i}(cv)=c\theta_{i}(v)$. $\sharp$

From Proposition \ref{rotl2} and the fact that $\theta_{i}(v_{i})=1$ and $\theta_{i}(v_{0})=0$, we have
\begin{equation}{\label{roteq41}}\tag{4}
\theta_{i}(cv_{i})=c.
\end{equation}
By Proposition \ref{rotl1}, any player $i$ yields the same result. The utility function $\boldsymbol{\theta}$ is unique, since (\ref{roteq41}) sets the origin and scale (Roth \cite[p.662]{rot}).

In order to evaluate $\boldsymbol{\theta}$ for other elements of the set $M$, i.e., the games not of the form $cv_{i}$, we must investigate
the risk posture of the preference relation $\succeq$. We shall distinguish between two kinds of risk. {\bf Ordinary risk} involves the uncertainty which arises from the chance mechanism involved in lotteries, while strategic risk involves the uncertainty which arises from the interaction in a game of the strategic players, i.e., those who are not dummies (Roth \cite[p.662]{rot}).

The preference $\succeq$ is {\bf averse to strategic risk} if, for every $S\subseteq N$ and all $i\in S$, $(v_{i},i)\succ (|S|\cdot u_{S},i)$,
where $u_{S}$ is the unanimity game. This means that it is preferable to receive a utility of one for certain (in a game with no other strategic players) than to negotiate how to distribute a utility of $|S|$ among $S$ players. If the preference is reversed, we say that it is {\bf risk preferring to strategic risk}. The preference relation $\succeq$ is neutral to strategic risk if, for all $S\subseteq N$ and every $i\in S$, we have $(v_{i},i)\sim (|S|\cdot u_{S},i)$. The preference $\succeq$ is averse to ordinary risk if, for all $i\in N$ and $v,w\in Z^{N}$, $(pw+(1-p)v,i)\succ [p(w,i);(1-p)(v,i)]$, i.e., if it is preferable to play the game $pw+(1-p)v$ than to have a lottery which results in the game $w$ with probability $p$ and the game $v$ with probability $(1-p)$. Similarly, the preference is {\bf neutral to ordinary risk} if, for all games $v,w\in Z^{N}$ and for every $i\in N$, we have $(pw+(1-p)v,i)\sim [p(w,i);(1-p)(v,i)]$ (Roth \cite[p.662]{rot}).

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

Proposition \ref{rotl3}. (Roth \cite[p.663]{rot}). If the preference relation $\succeq$ is neutral to strategic risk, then
\[\theta_{i}(u_{S})=\left\{\begin{array}{ll}
1/|S| & \mbox{if $i\in S$}\\ 0 & \mbox{if $i\not\in S$}.
\end{array}\right .\]

\begin{equation}{\label{rotl4}}\tag{6}\mbox{}\end{equation}

Proposition \ref{rotl4}. {(Roth \cite[p.663]{rot}). If the preference relation $\succeq$ is neutral to ordinary risk, then $\boldsymbol{\theta}(v+w)=\boldsymbol{\theta}(v)+\boldsymbol{\theta}(w)$. $\sharp$

Thus, for a preference relation $\succeq$, which obeys Conditions (i)-(v), we can prove that following result.

Theorem. (Roth \cite[p.663]{rot}). The strategic utility $\boldsymbol{\theta}$ is equal to the Shapley value $\boldsymbol{\phi}$ if and only if the preference relation $\succeq$ is neutral with respect to both ordinary and strategic risk. $\sharp$

We have shown that the Shapley value is a risk neutral utility function. Propositions \ref{rotl3} and \ref{rotl4} make it clear that the Shapley axioms (i) and (iii) are intimately related to the two kinds of risk neutrality. The normalization of the preferences given by Conditions (iii)=(v) seems to be completely natural, regardless of the risk posture which the preference reflects. But, when we are dealing with preference neutral to ordinary risk, it is not necessary to independently assume Condition (v), because of the following result (Roth \cite[p.664]{rot}).

Proposition. (Roth \cite[p.664]{rot}). Ordinary risk neutrality implies Condition (v). $\sharp$

Utility Functions for Simple Games.

A simple game on a set $N$ of players is one in which the characteristic function $v$ takes on only the values $0$ and $1$, and in which $v(S)=1$ implies $v(T)=1$ for all $S\subseteq T\subseteq N$. Such games arise naturally as models of political or economic situations in which every coalition of players is either “winning” or “losing”. We shall show that both the Shapley-Shubik index and the Banzhaf index for simple games correspond to von Neumann-Morgenstern utility functions, which differ only in their postures toward risk (Roth \cite[p.481]{rot77}).

Observe that if $v$ is a simple game, then the quantity $v(S)-v(S\setminus\{i\})$ equals $0$ unless $S$ is a winning coalition and $S\setminus\{i\}$ is a losing coalition, in which case it equals $1$. Consequently, if we suppose that players in a simple game $v$ “vote” in random order, then the Shapley value $\phi_{i}(v)$ is precisely the probability that player $i$ will cast a “pivotal” vote. As such, it can be viewed as an apriori index of power in simple games, and is referred to as the Shapley-Shubik index. However, if only simple games are to be considered, the Shapley axioms (i)-(iii) no longer specify a unique functional form. This is because axiom (iii) becomes nonbinding since the class of simple games is not closed under addition; that is to say, if $v$ and $w$ are nontrivial simple games with $v(N)=w(N)=1$, and the game $v+w$ is not simple, since $v(N)+w(N)=2$ (Roth \cite[p.482]{rot77}).

Another value for simple games which has received attention is the Banzhaf index, which takes as a measure of power of the relative ability of players to transform winning coalitions into losing coalitions, and vice versa. We define a swing for player $i\in N$ as a pair $(S,S\setminus\{i\})$ such that the coalition $S$ is winning, and $S\setminus\{i\}$ is losing, i.e., $v(S)=1$ and $v(S\setminus\{i\})=0$. Let $\eta_{i}(v)$ denote the number of swings for player $i$ in game $v$, and let $T(v)=\sum_{i\in N}\eta_{i}(v)$. Then, the Banzhaf index of relative power for each player is
\[\beta_{i}(v)=\frac{\eta_{i}(v)}{T(v)}\mbox{ for }i=1,\cdots ,n.\]
We refer to $\eta_{i}(v)$ as the nonnormalized Banzhaf index (Roth \cite[p.482]{rot77}).

For any simple games $v$ and $w$, the games $v\vee w$ and $v\wedge w$ are defined by
\[(v\vee w)(S)=\left\{\begin{array}{ll}
1 & \mbox{if $v(S)=1$ or $w(S)=1$}\\ 0 & \mbox{otherwise}
\end{array}\right .\mbox{ and }
(v\wedge w)(S)=\left\{\begin{array}{ll}
1 & \mbox{if $v(S)=1$ and $w(S)=1$}\\ 0 & \mbox{otherwise}.
\end{array}\right .\]
The Shapley-Shubik and the (normalized or nonnormalized) Banzhaf indices yield different rankings of the players in a given simple game. Consequently, it is desirable to find a common interpretation of the indices which will permit us to investigate their differences and similarities. This task is facilitated by the following two propositions (Roth \cite[p.482]{rot77}).

Proposition. (Roth \cite[p.482]{rot77}). The Shapley-Shubik index is the unique function $\boldsymbol{\phi}$ defined on simple games which satisfies the Shapley axioms (i) and (ii) and which has the property that:
\begin{equation}{\label{rot77eq14}}\tag{7}
\mbox{For any simple games $v$ and $w$, we have $latex \boldsymbol{\phi}(v\vee w)+\boldsymbol{\phi}(v\wedge w)=
\boldsymbol{\phi}(v)+\boldsymbol{\phi}(w)$.}
\end{equation}

A dummy in a game $v$ is an $i\in N$ for which there are no swings.

Proposition. (Roth \cite[p.483]{rot77}). The normalized Banzhaf index is the unique function defined on simple games which satisfies the following four properties.

If $i\in N$ is a dummy in $v$, then $\eta_{i}(v)=0$.
We have $\sum_{i\in N}\eta_{i}(v)=T(v)$.
For each permutation $\pi$, we have $\eta_{\pi (i)}(\pi v)=\eta_{i}(v)$;
For any simple games $v$ and $w$, we have $\boldsymbol{\phi}(v\vee w)+\boldsymbol{\phi}(v\wedge w)=\boldsymbol{\phi}(v)+\boldsymbol{\phi}(w)$. $\sharp$

The introduction of (\ref{rot77eq14}) permits these indices to be studied in the context of simple games alone. Let $C^{N}$ be the class of simple games defined of $N$, and let $M$ be the mixture space generated by $C^{N}\times N$. Then the elements of $M$ are elements $(v,i)$ of $C^{N}\times N$, and lotteries of the form $[p(w,i);(1-p)(v,j)]$, where $(w,i)$ and $(v,j)$ are in $C^{N}\times N$, and $p$ is a probability. An individual involved in such a lottery will, with probability $p$, play player $i$ in game $w$, and with probability $1-p$ play player $j$ in game $v$ (Roth \cite[p.483]{rot77}).

Let $P$ be a preference relation defined on $M$. We read $(w,i)P(v,j)$ as it is preferable to play player $i$ in game $w$ than to play player $j$ in game $v$. For $a,b\in M$, we write $aIb$ (which means that $a$ is indifferent $b$) is neither $aPb$ or $bPa$. We write $aRb$ if either $aPb$ or $aIb$, and assume that $R$ is a transitive, complete order on $M$. Furthermore, we assume that if $aIb$, then for every $c\in M$ and $p\in [0,1]$, we have $[pa;(1-p)c]I[pb;(10p)c]$. We take $P$ to be {\bf continuous}, i.e., if $a,b,c\in M$ such that $aPbPc$, then there exists a unique $q\in (0,1)$ such that $bI[qa;(1-q)c]$ (Roth \cite[p.484]{rot77}).

We denote by $u_{T}$ and $u_{0}$ the games defined by
\[u_{0}(S)=0\mbox{ for all }S\subseteq N\mbox{ and }
u_{T}(S)=\left\{\begin{array}{ll}
1 & \mbox{if $T\subseteq S$}\\ 0 & \mbox{otherwise}.
\end{array}\right .\]
For each $i\in N$, we denote by $D_{i}^{N}\subseteq C^{N}$ the set of simple games for which player $i$ is a dummy. We take $P$ to satisfy the following conditions:

(a): For all $v\in C^{N}$, $i\in N$ and every permutation $\pi$, we have $(v,i)I(\pi v,\pi (i))$;
(b): For every $i\in N$ and $v\in D_{i}^{N}$, we have $(v,i)I(v_{0},i)$ and $(v_{\{i\}},i)P(v_{0},i)$. For every $v\in C^{N}$, we have $(v_{\{i\}},i)R(v,i)R(v_{0},i)$.

It is well-known that such a preference can be represented by a utility function $\theta$ such that, for all $a,b\in M$,
\[\theta (a)>\theta (b)\mbox{ if and only if }aPb\]
and
\[\theta ([pa;(1-p)b])=p\theta (a)+(1-p)\theta (b).\]
Furthermore, $\theta$ is unique up to an affine transformation, so we can set $\theta (v_{\{i\}},i)=1$ and $\theta (v_{0},i)=0$. For an arbitrary element $(v,i)$ of $C^{N}\times N$, we have $\theta_{i}(v)\stackrel{def}{=}\theta (v,i)=q$, where $q$ is a number such that
$(v,i)I[q(v_{\{i\}},i);(1-q)(v_{0},i)]$. By the continuity of $P$ and condition (ib), $\theta_{i}(v)$ is well-defined (Roth \cite[p.484]{rot77}).

We have yet to completely specify the preference $P$. We do so by expressing the references involving two kinds of risk.

(c): Ordinary risk neutrality. For all simple games $v$ and $w$, we have
\[\left [\frac{1}{2}(v,i);\frac{1}{2}(w,i)\right ]I\left [\frac{1}{2}(v\vee w,i);\frac{1}{2}(v\wedge w,i)\right ];\]
(d): Strategic risk neutrality. For all $S\subseteq N$ and $i\in S$, we have
\[(v^{S},i)I\left [\frac{1}{|S|}(v_{\{i\}},i); \left (1-\frac{1}{|S|}\right )(v_{0},i)\right ].\]

Condition (c) specifies indifference between two lotteries. One lottery results in either the game $v$ or the game $w$, while the other results in either the game $v\vee w$ or the game $v\wedge w$. Note that the condition is plausible, since $(v\vee w)\geq v$ and $(v\wedge w)\leq w$. Thus, it is to be expected that it is more desirable to play in the game $v\vee w$ than to play the same player in game $v$, and less desirable to play in the game $v\wedge w$ than in the game $w$. Condition (c) expresses the intensity of these desirability comparisons. Note also that a given coalition $S$ has the same probability of being a winning coalition in either lottery. Condition (d) specifies indifference between playing the game $v^{S}$ as one of $|S|$ players in the unique minimal winning coalition, or participating in a lottery which gives probability $1/|S|$ of being a dictator and probability $1-1/|S|$ of being a dummy. Note that the risk involved in playing the game $v^{S}$ is trategic rather than probabilistic — no gamble is involved (Roth \cite[p.485]{rot77}).

\begin{equation}{\label{rot77t1}}\tag{8}\mbox{}\end{equation}

Theorem \ref{rot77t1}. (Roth \cite[p.485]{rot77}). If $P$ is a preference obeying conditions {\em (i)}-{\em (iv)}, then the unique utility $\theta$ such that $\theta_{i}(v_{\{i\}})=1$ and $\theta_{i}(v_{0})=0$ is equal to the Shapley-Shubik index. $\sharp$

The above theorem says that the Shapley-Shubik index is the utility function representing preferences described by conditions (i)-(iv). Naturally, different preferences will give rise to different functions. Suppose that the posture toward strategic risk is represented not by condition (d) but by the following condition:

(e): For every $S\subseteq N$ and $i\in S$, we have
\[\left [\frac{1}{T(v^{S})}(v^{S},i);\left (1-\frac{1}{T(v^{S})}\right )
(v_{0},i)\right ]I\left [\frac{1}{|S|\cdot2^{n-1}}(v_{\{i\}},i);\left (1-\frac{1}{|S|\cdot2^{n-1}}\right )(v_{0},i)\right ].\]

Then the following result says that the nonnormalized Banzhaf index is a utility functuon for the preference relation $P$
(Roth \cite[p.487]{rot77}).

Theorem. (Roth \cite[p.487]{rot77}). If $P$ is a preference obeying conditions (a)–(c) and condition (e), then the unique utility $\theta$ such that $\theta_{i}(v_{\{i\}})=2^{n-1}$ and $\theta_{i}(v_{0})=0$ is equal to the non-normalized Banzhaf index.

Proof. The proof is precisely like the proof of Theorem~\ref{rot77t1}, once it has been observed that condition (e) implies that
\[\theta_{i}(v^{S})=\eta_{i}(v^{S})=\left\{\begin{array}{ll}
\frac{T(v^{S})}{|S|} & \mbox{if $i\in S$}\\ 0 & \mbox{otherwise}.
\end{array}\right .\]

Therefore, the nonnormalized Banzhaf index and the Shapley-Shubik index reflect preferences which differ only in their postures toward strategic risk. Similarly, it is not difficult to show that the ordinary (normalized) Banzhaf index corresponds to preferences which obey condition (d) but not condition (c). That is, the Banzhaf index reflects preferences which are neutral to strategic risk, but not to ordinary risk. The normalization has the effect of changing the risk posture, since each game is normalized independently, i.e., each game $v$ is normalized by $T(v)$ (Roth \cite[p.488]{rot77}).

We have seen that the difference between the Shapley-Shubik index and the nonnormalized Banzhaf index results from different postures toward strategic risk. That is, the two indices reflect different attitudes toward the relative benefits of engaging in strategic interaction with other players in games of the form $v^{S}$. The difference between the Shapley-Shubik and the ordinary Banzhaf index, on the other hand, reflects different postures towards ordinary risk — the kind which results from lotteries, rather than from strategic interactions. Thus, the difference between these two indices seems to be essentiaaly non-game-theoretic (Roth \cite[p.488]{rot77})