数理解析研究所講究録
第 1857 巻 2013 年 30-40

30Marginal worth vectors for $TU$ games
Kensaku KIKUTASchool of Business Administration
University of Hyogo

1. Introduction

The Shapley value ([Shapley $1953|)$ is a solution for cooperative $TU$ games. Marginal
worth in cooperative games is a kind of difference of the characteristic function. The Shapley

value could be expressed as a convex combination of marginal worth vectors. In this article
taking marginal worths of several players into consideration we give relations between the
Shapley values for subgames. We characterize the Shapley value as a sum of differencesof several players, which satisfies the efficiency. See [Grabisch/Marichal/Roubens 2000]
with respect to extensions of this kind of discussions under Boolean function etc. See, forexample, [Lange/Grabisch 2011] with respect to topics around the Shapley value.

A TU game is a pair $(N, v)$ , where $N=\{1, \ldots, n\}$ is a fimite set of players and is areal-valued function defined on the subsets of $N$ with $v(\emptyset)=0.$ is called the characteristic
function of the $TU$ game. subset of $N$ is called a coalition. For a $TU$ game $(N, v)$ anda coalition $S\subseteq N$ , a subgame $(S, v)$ is a $TU$ game where is the player set and isa restriction to the subsets of . For any set $Z,$
denotes the cardinality of . Fora coalition $S,$with coordinates indexed byis the-dimensional product spaceplayers in . An element of
is a payoff vector. The i-th component of $x\in R^{S}$ isand $=0$ (ifdenoted by . For
and $x\in R^{N}$ , we define $x(S)= \sum_{i\in S}x_{i}$
$v$

$v$

$A$

$S$

$S$

$R^{s}$$x_{i}$$S=\emptyset)$

$x$

$Z$

$|Z|$

$R^{|S|}$

$|S|$

$S$

$v$

$R^{N}$$S\subseteq N$$(if S\neq\emptyset)$. For a $TU$ game $(N, v)$ let(1)$X(N, v)\equiv\{x\in R^{N}:x(N)=v(N)\}$ .

An element of $X(N, v)$ is called a pre-imputation. The Shapley value ([Shapley 1953]) for a$TU$ game $(N, v)$ is a payoff vector $\varphi(N, v)\in R^{N}$ where$\varphi_{i}(N, v)=\sum_{S:i\in S}\frac{(|S|-1)!(n-|S|)!}{n!}[v(S)-v(S\backslash \{i\})]$

.

(2)

31
It is well-known that the Shapley value is a pre-imputation, that is, $\varphi(N, v)\in X(N, v)$ .
2. Marginal worth vector and the Shapley value

Let $a:2^{N}arrow R$ be a function. For each$R\subseteq N$, let$c_{R}(a)= \sum_{T\subseteq R}(-1)^{|R\backslash T|}a(T)$and for$R\subseteq N$, define a characteristic function$v_{R}$

,

(3)

by

(4)

$v_{R}(S)=\{\begin{array}{l}1, if R\subseteq S\subseteq N;0, otherwise.\end{array}$

The next lemma was used in [Shapley 1953] to define and characterize the Shapley value.

Lemma 2.1. ([Shapley 1953]) For any $TU$ game $(N, v)$ and all$v(S)= \sum_{\emptyset\neq R\subseteq N}c_{R}(v)v_{R}(S)$Let $a:2^{N}arrow R$ be a function. For $i\in N$ and$S\subseteq N$$S\subseteq N,$.

(5), define$\triangle_{i}a(S)\equiv a(S)-a(S\backslash \{i\})$(6).

When $a=v$ for some $TU$ game $(N, v),$is called the marginal worth of $i\in N$ at. The next lemmas are obtained straightforwardly from Lemma 2.1, and given (at least
implicitly) in [Shapley 1953].
$\Delta_{i}v(S)$$S$

Lemma 2.2. For a $TU$ game $(N, v)$ and$S\subseteq N,$$\triangle_{i}v(S)=\sum_{i\in R\subseteq S}c_{R}(v)$.

(7)

Proof:$\triangle_{i}v(S)=\sum_{\emptyset\neq R\subseteq N}c_{R}(v)[v_{R}(S)-v_{R}(S\backslash \{i\})]$$= \sum_{i\in R\subseteq S}c_{R}(v)$.

$\square$Lemma 2.3. For a $TU$ game $(N, v)$ and for each $i\in N$ and$S\subseteq N$such that $i\in S,$$\varphi_{i}(N, v)=\Delta_{i}v(S)+\sum_{i\in R,R\not\in S}\frac{c_{R}(v)}{|R|}+\sum_{i\in R\subseteq S}(\frac{1}{|R|}-1)c_{R}(v)$

.

(8)

32
Proof: By Lemma 2.2 and from [Shapley 1953]$\varphi_{i}(N, v)=\sum_{i\in R\subseteq N}\frac{1}{|R|}c_{R}(v)$.

$\square$

Let $a:2^{N}arrow R$ be a function. For $|S|\geq 2$ , let $S=\{i_{1}, \ldots, i_{|S|}\}$ . Define inductively with
(6), the marginal worth of several players, by$\triangle_{i_{1)}\ldots,i_{|S|}}a(S)=\triangle_{i_{1},\ldots,i_{|S|-1}}a(S)-\triangle_{i_{1},\ldots,i_{|S|-1}}a(S\backslash \{i_{|S|}\})$

Lemma 2.4. ([Grabisch/Marichal/Roubens 2000]) Let.

: $2^{N}arrow R$ be a function. For$a$$S\subseteq T\subseteq N,$$\triangle_{i_{1},\ldots,i_{|S|}}a(T)=\sum_{s\subseteq R\subseteq T}c_{R}(a)$,(9)

where $S=\{i_{1}, \ldots, i_{|S|}\}.$

Let $s=|S|$ . By induction on . When $s=1$ , that is, $S=\{i\}$ . We define$b:2^{N}arrow R$ by $b(R)=a(R)-a(\emptyset)$ for all $R\in 2^{N}$ . Since$(N, b)$ could be regarded
as a $TU$ game. It is easy to see $c_{R}(a)=c_{R}(b)$ for all $R\in 2^{N}$ . Applying Lemma 2.2, we
have
Proof;$s$$b(\emptyset)=0,$$\sum_{i\in R\subseteq T}c_{R}(a)=\sum_{i\in R\subseteq T}c_{R}(b)=\triangle_{i}b(T)=\triangle_{i}a(T)$.

So it holds for $s=1$ . Suppose $s\geq 2.$$\triangle_{i_{1},i_{2},\ldots,i_{s}}a(T)=\triangle_{i_{1},\ldots,i_{s-1}}a(T)-\triangle_{i_{1},\ldots,i_{s-1}}a(T\backslash \{i_{s}\})$$= \sum_{\{i_{1},\ldots,i_{s-1}\}\subseteq R\subseteq T}c_{R}(a)-\sum_{\{i_{1},\ldots,i_{s-1}\}\subseteq R\subseteq T\backslash \{i_{s}\}}c_{R}(a)$$= \sum_{\{i_{1},\ldots,i_{s-1},i_{s}\}\subseteq R\subseteq T}c_{R}(a)$.

$\square$without confusion. When $a=v$
From Lemma 2.4 we could expressasat . The next
for some $TU$ game $(N, v),$is called the marginal worth oflemma is from [Grabisch/Marichal/Roubens 2000].
$\triangle_{i_{1},\ldots,i_{|S|}}a(T)$$\triangle_{S}v(T)$$\triangle_{S}a(T)$$S\subseteq N$

$T$

33
Lemma 2.5. For a $TU$ game $(N, v)$ and $i\in N,$$\varphi_{i}(N, v)=v(\{i\})+\sum_{R:i\in R\subseteq N|R|\geq 2},\frac{\triangle_{R}v(R)}{|R|}$

Proof: This is by Lemmas 2.3 and 2.4 and by $v(\emptyset)=0.$

.

(10)

$\square$Example 1. Let $n=3$ . By Lemmas 2.4 and 2.5,$\varphi(N, v)=x^{123}+(\frac{\triangle_{1,2}v(12)}{2}+\frac{\triangle_{1,3}v(13)}{2}+\frac{\triangle_{1,2,3}v(123)}{3})(1,0,0)$$+( \frac{\triangle_{1,2}v(12)}{2}+\frac{\triangle_{2,3}v(23)}{2}+\frac{\triangle_{1,2,3}v(123)}{3})(0,1,0)$$+( \frac{\Delta_{1,3}v(13)}{2}+\frac{\triangle_{2,3}v(23)}{2}+2\frac{\triangle_{1,2,3}v(123)}{3})(0,0,1)$(11)$=x^{123}+ \frac{1}{2}\triangle_{1,2}v(12)(1,1,0)+\frac{1}{2}\triangle_{1,3}v(13)(1,0,1)+\frac{1}{2}\triangle_{2,3}v(23)(0,1,1)$$+ \frac{1}{3}\triangle_{1,2,3}v(123)(1,1,1)$

where $x^{123}=(v(1), v(2), v(3))$ .

For

, let

be the Shapley value for the subgame $(S, v)$ . The next theorem
gives a relation between the Shapley values for subgames.
$S\subseteq N$$\varphi(S, v)$

Theorem 2.6. For every $i\in N,$$\varphi_{i}(N, v)=\sum_{i\in S\subset N}(-1)^{n+1-|S|}\varphi_{i}(S, v)+\frac{\triangle_{N}v(N)}{n}$

or

(12)
$\sum_{i\in S\subseteq N}(-1)^{n+1-|S|}\varphi_{i}(S, v)+\frac{\triangle_{N}v(N)}{n}=0.$

Proof: By induction on . Assume that it holds for all $(R, v)$ such that $|R|\leq n-1$ . Then$n$$\sum_{i\in S\subseteq R}(-1)^{|R|+1-|S|}\varphi_{i}(S, v)+\frac{\triangle_{R}v(R)}{|R|}=0.$

From this and Lemma 2.5,$\varphi_{i}(N, v)=\varphi_{i}(\{i\}, v)-\sum_{i\in R\subset N,|R|\geq 2}\sum_{i\in S\subseteq R}(-1)^{|R|+1-|S|}\varphi_{i}(S, v)+\frac{\triangle_{N}v(N)}{n}.$Here$\sum_{i\in R\subset N,|R|\geq 2}\sum_{i\in S\subseteq R}(-1)^{|R|+1-|S|}\varphi_{i}(S, v)=\sum_{i\in S\subset N}(-1)^{1-|S|}\varphi_{i}(S, v)\sum_{S\subseteq R\subset N,|R|\geq 2}(-1)^{|R|}.$

34
Furthermore we see$\sum_{S\subseteq R\subset N,|R|\geq 2}(-1)^{|R|}=\{\begin{array}{ll}(-1)^{n+1}, if |S|\geq 2;1-(-1)^{n}, if S=\{i\}.\end{array}$So,$\varphi_{i}(N, v)=\varphi_{i}(\{i\}, v)-[1-(-1)^{n}]\varphi_{i}(\{i\}, v)$$\sum_{i\in S\subset N,|S\}\geq 2}(-1)^{1-|S|}\varphi_{i}(S, v)(-1)^{n+1}+\frac{\triangle_{N}v(N)}{n}$$= \sum_{i\in S\subset N}(-1)^{n+1-|S|}\varphi_{i}(S, v)+\frac{\triangle_{N}v(N)}{n}.

\square$3. Marginal worth vector and the potential function
In this section we see a relation between the potential functions for subgames. Proposition 3.1 and Theorem 2.6 could be compared.
Define the potential function (See [Hart/Mas-Cole111989]) for a $TU$ game $(N, v)$ by$P(N, v)= \sum_{\emptyset\neq R\subseteq N}\frac{c_{R}(v)}{|R|}$

.

(13)

In the same way the potential function $P(S, v)$ for each subgame $(S, v),$$\emptyset\neq S\subset N$, isdefined.
Proposition 3.1. For a $TU$ game $(N, v)$ ,$\sum_{\emptyset\neq S\subseteq N}(-1)^{n+1-|S|}P(S, v)+\frac{\triangle_{N}v(N)}{n}=0$

.

(14)

Proof: By induction on . Assume that it holds for all $(R, v)$ such that $|R|\leq n-1$ . Then$n$$\sum_{\emptyset\neq s\subseteq R}(-1)^{|R|+1-|S|}P(S, v)+\frac{\triangle_{R}v(R)}{|R|}=0.$

From this and (13),$P(N, v)=- \sum_{\emptyset\neq R\subset N}\sum_{\emptyset\neq s\subseteq R}(-1)^{|R|+1-|S|}P(S, v)+\frac{\triangle_{N}v(N)}{n}$$=- \sum_{\emptyset\neq S\subset N}P(S, v)\sum_{s\subseteq R\subset N}(-1)^{|R|+1-|S|}+\frac{\triangle_{N}v(N)}{n}.$35Here, letting $s=|S|,$$\sum_{s\subseteq R\subset N}(-1)^{|R|+1-|S|}=\sum_{r=s}^{n-1}(-1)^{r+1-s}(\begin{array}{l}n-sr-s\end{array})$$=-(\begin{array}{l}n-s0\end{array})+(\begin{array}{l}n-s1\end{array})-\cdots+(-1)^{n-s}(\begin{array}{l}n-sn-s\end{array})$$=-(-1)^{n-s+1}$

So,$P(N, v)= \sum_{\emptyset\neq S\subset N}P(S, v)(-1)^{n+1-|S|}+\frac{\Delta_{N}v(N)}{n}.

\square$4. Multilinear extension and the Shapley value
In this section we state a relation between the marginal worth and derivative of multi-

linear extension ([Owen 1972]).
For $(N, v),1et$,(15)$f(x_{1}, \ldots, x_{n})=\sum_{s\subseteq N}\{\Pi_{k\in S}x_{k}\Pi_{k\not\in S}(1-x_{k})\}v(S)$

where$0\leq x_{i}\leq 1, \forall i=1, \ldots, n.$

Proposition 4.1 Let $R=\{i_{1}, \ldots, i_{r}\}$ where $r=|R|.$.

$\frac{\partial^{r}f}{\partial x_{i_{1}}\cdots\partial x_{i_{r}}}=\sum_{R\subseteq s}\{\Pi_{k\in S\backslash R^{X}k}\Pi_{k\not\in S}(1-x_{k})\}(\triangle_{R}v)(S)$

Proof: By induction on $r\geq 1$ . Let $r=1$ and $R=\{i\}$ . Then$\frac{\partial f}{\partial x_{i}}=\sum_{i\in S}\{\Pi_{k\in S\backslash \{i\}}x_{k}\Pi_{k\not\in S}(1-x_{k})\}v(S)-\sum_{i\not\in S}\{\Pi_{k\in S}x_{k}\Pi_{k\not\in S,k\neq i}(1-x_{k})\}v(S)$$= \sum_{i\in S}\{\Pi_{k\in S\backslash \{i\}}x_{k}\Pi_{k\not\in S}(1-x_{k})\}v(S)-\sum_{i\in S}\{\Pi_{k\in S\backslash \{i\}}x_{k}\Pi_{k\not\in S}(1-x_{k})\}v(S\backslash \{i\})$$= \sum_{i\in S}\{\Pi_{k\in S\backslash \{i\}^{X}k}\Pi_{k\not\in S}(1-x_{k})\}(\triangle_{i}v)(S)$

.

(16)

36
Next assume it holds for $r-1$ . Then$\frac{\partial^{r}f}{\partial x_{i_{1}}\cdots\partial x_{i_{r}}}=\frac{\partial f}{\partial x_{i_{r}}}(\sum_{R\backslash \{i_{r}\}\subseteq S}\{\Pi_{k\in S\backslash (R\backslash \{i_{r}\})}x_{k}\Pi_{k\not\in S}(1-x_{k})\}(\triangle_{i_{1},\ldots,i_{r-1}}v)(S))$$= \frac{\partial f}{\partial x_{i_{r}}}(\sum_{R\subseteq S}\{\Pi_{k\in S\backslash (R\backslash \{i_{r}\})^{X}k}\Pi_{k\not\in S}(1-x_{k})\}(\triangle_{i_{1},\ldots,i_{r-1}}v)(S)$$+ \sum_{R\backslash \{i_{f}\}\subseteq Si_{r}\not\in s},\{\Pi_{k\in S\backslashR}x_{k}\Pi_{k\not\in S}(1-x_{k})\}(\triangle_{i_{1},\ldots,i_{r-1}}v)(S))$$= \sum_{R\subseteq S}\{\Pi\Pi(1-x_{k})\}(\triangle_{i_{1},\ldots,i_{r-1}}v)(S)$$\sum_{R\backslash \{i_{r}\}\subseteq Si_{r}\not\in s},\{\Pi_{k\in S\backslash R}x_{k}\Pi_{k\not\in S,k\neq i_{r}}(1-x_{k})\}(\triangle_{i_{1},\ldots,i_{r-1}}v)(S)$$= \sum_{R\subseteq s}\{\Pi_{k\in S\backslash R}x_{k}\Pi_{k\not\in S}(1-x_{k})\}(\triangle_{i_{1},\ldots,i_{r-1}}v)(S)$$- \sum_{R\subseteq s}\{\Pi_{k\in S\backslash R^{X}k}\Pi_{k\not\in S}(1-x_{k})\}(\triangle_{i_{1},\ldots,i_{r-1}}v)(S\backslash \{i_{r}\})$$= \sum_{R\subseteq s}\{\Pi_{k\in S\backslash R^{X}k}\Pi_{k\not\in S}(1-x_{k})\}(\triangle_{i_{1},\ldots,i_{r}}v)(S)$.

$\square$

5. Another expression of the Shapley value
In this section we characterize the Shapley value as a sum of marginal worths of $co$ alitions
at $N$ which is a pre-imputation, that is, it satisfies the efficiency.
Theorem 5.1. For any $TU$ game $(N, v)$ , define a payoff vector $y(N, v)$ by $y_{i}(N, v)=$
for all $i\in N$ . Then $y(N, v)$ is a pre-imputation for all $TU$ games$\sum_{i\in S\subseteq N}\alpha_{|S|}(\triangle sv)(N)$$(N, v)$

if and only if it is the Shapley value.

Before proving this theorem, we need lemmas.

37
Lemma 5.2. For$\emptyset\neq S\subseteq N,$$( \triangle_{S}v)(N)=\sum_{R\subseteq S}(-1)^{|R|}v(N\backslash R)$

.

(17)

Proof: Let $S=\{i_{1}, \ldots, i_{S}\}.$$(\triangle_{i_{1},\ldots,i_{s}}v)(N)=(\triangle_{i_{1},\ldots,i,-1}v)(N)-(\triangle_{i_{1},\ldots,i_{s-1}}v)(N\backslash \{i_{S}\})$$= \sum_{R\subseteq S\backslash \{i_{s}\}}(-1)^{|R|}v(N\backslash R)-\sum_{R\subseteq S\backslash \{i_{\epsilon}\}}(-1)^{|R|}v(N\backslash \{i_{s}\}\backslash R)$$= \sum_{R\subseteq S\backslash \{i_{\theta}\}}(-1)^{|R|}v(N\backslash R)-\sum_{R\subseteq S,i_{s}\in R}(-1)^{|R|-1}v(N\backslash R)$$= \sum_{R\subseteq S,i_{s}\not\in R}(-1)^{|R|}v(N\backslash R)+\sum_{R\subseteqS,i_{s}\in R}(-1)^{|R|}v(N\backslash R)$$= \sum_{R\subseteq S}(-1)^{|R|}v(N\backslash R)$.

$\square$Lemma 5.3. For a $TU$ game $(N, v)$ and $i\in N,$$\varphi_{i}(N, v)=\sum_{i\in S\subseteq N}(-1)^{|S|+1}\triangle_{S}v(N)|S|$

Proof: From Lemma 5.2,$\sum_{i\in S\subseteq N}(-1)^{|S|+1}\triangle_{S}v(N)|S|$$= \sum_{i\in S\subseteq N}\frac{(-1)^{|S|+1}}{|S|}\sum_{R\subseteq S}(-1)^{|R|}v(N\backslash R)$$= \sum_{i\in S\subseteq N}\frac{(-1)^{|S|+1}}{|S|}[\sum_{i\in R\subseteq S}(-1)^{|R|}v(N\backslash R)+\sum_{i\not\in R\subseteq S}(-1)^{|R|}v(N\backslash R)]$$= \sum_{i\in S\subseteq N}\sum_{i\in R\subseteq S}\frac{(-1)^{|R|+|S|+1}}{|S|}v(N\backslash R)+\sum_{i\in S\subseteq N}\sum_{i\not\in R\subseteq S}\frac{(-1)^{|R|+|S|+1}}{|S|}v(N\backslash R)$

the lst term$= \sum_{i\in R\subseteq N}(-1)^{|R|}v(N\backslash R)\sum_{S:R\subseteq S}\frac{(-1)^{|S|+1}}{|S|}$$= \sum_{i\in R\subseteq N}(-1)^{|R|}v(N\backslash R)\sum_{s=|R|}^{n}\frac{(-1)^{s+1}}{s}(\begin{array}{l}n-|R|s-|R|\end{array})$$= \sum_{i\in R\subseteq N}(-1)^{|R|}v(N\backslash R)\frac{(-1)^{|R|+1}}{n(_{|R|-1}^{n-1})}=\sum_{i\in R\subseteq N}\frac{v(N\backslash R)}{n(_{|R|-1}^{n-1})}.$

(18)

38
the 2nd term$= \sum_{i\not\in R\subseteq N}(-1)^{|R|}v(N\backslash R)\sum_{S:i\in S,R\subseteq S}\frac{(-1)^{|S|+1}}{|S|}$$= \sum_{i\not\in R\subseteq N}(-1)^{|R|}v(N\backslash R)\sum_{S:R\cup\{i\}\subseteq S}\frac{(-1)^{|S|+1}}{|S|}$$= \sum_{i\not\in R\subseteq N}(-1)^{|R|}v(N\backslash R)\sum_{s=|R|+1}^{n}\frac{(-1)^{s+1}}{s}(\begin{array}{l}n-|R|-1s-|R|-1\end{array})$$= \sum_{i\not\in R\subseteq N}(-1)^{|R|}v(N\backslash R)\frac{(-1)^{|R|}}{n(_{|R|}^{n-1})}=\sum_{i\not\in R\subseteq N}\frac{v(N\backslash R)}{n(_{|R|}^{n-1})}.$

Hence$\sum_{i\in S\subseteq N}(-1)^{|S|+1}\frac{\triangle_{S}v(N)}{|S|}=-\sum_{i\in R\subseteq N}\frac{v(N\backslash R)}{n(_{|R|-1}^{n-1})}+\sum_{i\not\in R\subseteq N}\frac{v(N\backslash R)}{n(_{|R|}^{n-1})}$$=- \sum_{i\not\in S}\frac{v(S)}{n(_{n-|S|-1}n1)}+\sum_{i\in S\subseteq N}\frac{v(S)}{n(_{n-|S|}^{n-1})}$$=- \sum_{i\in S\subseteq N}\frac{v(S\backslash \{i\})}{n(_{n-|S|}^{n-1})}+\sum_{i\in S\subseteq N}\frac{v(S)}{n(_{n-|S|}^{n-1})},$

which is the Shapley value,
Lemma 5.4. Let$\varphi_{i}(N, v)$.

$\square$$y_{i}^{N}= \sum_{i\in S\subseteq N}\alpha_{|S|}(\triangle_{S}v)(N)$. If for all $TU$ games $(N, v)$ ,(19)$\sum_{i\in N}y_{i}^{N}=v(N)$then$\alpha_{s}=\frac{(-1)^{s+1}}{s}$, for all $s=1,$$\ldots,$$n$.

Proof:$v(N)= \sum_{i\in N}y_{i}^{N}=\sum_{i\in N}\sum_{i\in S\subseteq N}\alpha_{|S|}(\triangle_{S}v)(N)$$= \sum_{S\neq\emptyset}\sum_{i\in S}\alpha_{|S|}(\triangle_{S}v)(N)$$= \sum_{s\neq\emptyset}|S|\alpha_{|S|}(\triangle_{S}v)(N)$$= \sum_{s\neq\emptyset}|S|\alpha_{|S|}\sum_{R\subseteq S}(-1)^{|R|}v(N\backslash R)$$= \sum_{R\subseteq N}(-1)^{|R|}v(N\backslash R)\sum_{S\neq\emptyset,R\subseteq S}|S|\alpha_{|S|}.$

(20)

39
Since this is an identity, we compare coefficients $v(N)$ of both sides.
$1= \sum_{s\neq\emptyset}|S|\alpha_{|S|}=\sum_{s=1}^{n}(\begin{array}{l}ns\end{array})s\alpha_{s}$For$R\neq\emptyset,$

$N$

.

(21)

we compare coefficients of both sides.
$0= \sum_{R\subseteq S}|S|\alpha_{|S|}=\sum_{s=|R|}^{n}(\begin{array}{l}n-|R|s-|R|\end{array})s\alpha_{s}$.

For $R=N$ , by comparing coefficients of both sides, we havesince $v(\emptyset)=0$ . In the equation (22) on
Then$\{\alpha_{s}\}$

, let

$R$

(22)
$n\alpha_{n}v(\emptyset)=0$, which holds

be such that $|R|=n-k$ for $k=1,2,3.$$(n-1)\alpha_{n-1}+n\alpha_{n}=0$, for $k=1,$$(n-2)\alpha_{n-2}+2(n-1)\alpha_{n-1}+n\alpha_{n}=0$ ,for $k=2,$$(n-3)\alpha_{n-3}+3(n-2)\alpha_{n-2}+3(n-1)\alpha_{n-1}+n\alpha_{n}=0$ ,for $k=3.$

From these,$n\alpha_{n}=-(n-1)\alpha_{n-1}=(n-2)\alpha_{n-2}=-(n-3)\alpha_{n-3}.$

Assume for $\ell\leq k-1,$$(n-\ell)\alpha_{n-\ell}=n\alpha_{n}$, if$\ell$

is even, and $=-n\alpha_{n}$ , if$\ell$

is odd.

The equation (22) for $|R|=n-k$ becomes to$0=(\begin{array}{l}k0\end{array})(n-k)\alpha_{n-k}+\{\begin{array}{ll}n\alpha_{n}(-[Matrix]+[Matrix]-\cdots+[Matrix]) , if k is even;n\alpha_{n}(+[Matrix]-[Matrix]+\cdots-[Matrix]) , if k is odd;\end{array}$$=(\begin{array}{l}k0\end{array})(n-k)\alpha_{n-k}+\{\begin{array}{ll}n\alpha_{n}(-[Matrix]) , if k is even;n\alpha_{n}(+[Matrix]) , if k is odd.\end{array}$

Inductive consideration implies$(n-k)\alpha_{n-k}=\{\begin{array}{ll}n\alpha_{n}, if k is even;-n\alpha_{n}, if k is odd;\end{array}$

From this, the equation (21) becomes to$n\alpha_{n}(-(\begin{array}{l}n1\end{array})+(\begin{array}{l}n2\end{array})-\cdots+(\begin{array}{l}nn\end{array}))=1,$

(23)

40
if

$n$

is even. If$n$is odd, the equation (21) becomes to$n\alpha_{n}((\begin{array}{l}nl\end{array})-(\begin{array}{l}n2\end{array})+\cdots+(\begin{array}{l}nn\end{array}))=1.$

So $n\alpha_{n}=(-1)^{n+1}$ . From this and (23}, we have the lemma.
From Lemmas 5.2-5.4, we have the theorem.

$\square$$\square$

References[1] Grabisch, M., J. Marichal, M. Roubens (2000). Equivalent representation of set functions. Math. of Oper. Res. 25157-178.
[2] Hart, S., JA.Mas-Colell (1989).. Potential, value, and consistency. Econometnca 57

589-614.
[3] Lange, F., M. Grabisch (2011). New axiomatizations of the Shapley interaction index
for bi-capacities. Fuzzy Sets and Systems 17664-75.
[4] Owen, G. (1972). Multilinear extensions of games. Management Science 1864-79.

[5] Shapley, L.S. (1953). A value for -person games. H.W.Kuhn, A.W.Tucker,eds., Contributions$n$to the Theory of Games, Vol.II, Annals of Mathematics Studies, 28. Princeton University
Press, Princeton, NJ,307-317.