1
$\begingroup$

In the Wikipedia article on the Shapley value (here), a formula is given that generalises the notion of the Shapley value from an individual player to a group of players. It is stated as follows:

$$ \phi_{C} (v) = \sum_{T \subseteq N \setminus C} \frac{(n - |T| -|C|)! |T|!}{(n - |C| + 1)!} \sum_{S \subseteq C} (-1)^{|C| - |S|}v(S \cup T) \qquad (1) . $$

I found this formula intriguing, so I checked out the reference wherein I'd be able to find out more about this formula. The reference is an article called "Multilinear Extensions of Games" and it was written by Guillermo Owen in 1972. You can find it over here.

In the Appendix of this article (p. 78 at the bottom of the page), it is stated that if $f(x_{1} , \dots , x_{n})$ is a multilinear function if it can be expressed in the form $$f(x_{1} , \dots , x_{n}) = \sum_{S \subset N} C_{S} \prod_{j \in S} x_{j}, $$ where $N = \{ 1, \dots , n \}$, $ 0 \leq x_{i} \leq 1 $ ($i = 1, \dots , n$), and the $C_{S}$ are constants. Furthermore, Owen defines $$\alpha_{i}^{S} = \left\{ \begin{array}{ll} 1 & \mbox{if } i \in S \\ 0 & \mbox{if } i \notin S \end{array} \right.$$ as the $S$-corner of the cube. They also define the unit cube as $I^{N}$. Then the theorem in the appendix is as follows: Let $v$ be a function defined on the subsets of $N$. Then there exists a unique multilinear function, $f$, defined on $I^{N}$, which has the property that $f(\alpha^{S}) = v(S)$ for all $S \subset N$.

In the proof of this theorem, Owen demonstrates (though I don't understand the proof) that this unique multilinear function $f$ can be written in two ways: $$ f(x) = \sum_{S \subset N} \{ \sum_{T \subset S} (-1)^{s-t} v(T) \} \prod_{j \in S} x_{j} \qquad (2) $$ and: $$f(x) = \sum_{S \subset N} \{ \prod_{j \in S} x_{j} \prod_{j \notin S} (1 - x_{j} ) \} v(S) \qquad (3) $$

Questions:

  1. How does one reconcile formula (1) with formulas (2) and (3) ? How does the difference in notation work?

  2. Could you shed light on the proof of the theorem given by Owen in the appendix?

  3. Is there a way to express the Shapley value of a coalition in terms of the Shapley values of the individual players?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.