3
$\begingroup$

Computing a Shapley value, we are mapping the set of coalition games on $N$ to a vector of $N$ elements:

$$ \phi: \; \mathbb{R^{2^N}} \to \mathbb{R}^N $$

In a sense, this is compression, or more precisely hashing (since compression is often thought of as being a lossless injection).

What does the inverse direction look like? What do two games $v$ and $w$ that have Shapley values ($\phi(v)=\phi(w)$) have in common?

If we parametrized games with $N$ parameters, what would the relationship between these $N$ parameters and the $N$ Shapley values be? That is, if we have a function

$$ \rho: \; \mathbb{R}^N \to \mathbb{R^{2^N}} $$

whereby, for any $x \in \mathbb{R}^N$ we get a coalition game $\rho(x)$, then what would the Shapley values $\phi(\rho(x))$ of the latter be? More specifically, what would the relationship between $\phi(\rho(x))$ and $x$ be?

Examples of parametrized coalition games $\rho$: The "sum game" or the "product game", where the value of a coalition is the sum (resp. product) of the values (parameters) of the members of the coalition.

$\endgroup$
-1
$\begingroup$

First of all I think that there is a fundamental misunderstanding of the meaning or reflection of the Shapley value. The Shapley value does not reflect a hash or compression of a TU-game. It reflects inter alia the bargaining power of the players involved in a fictitious bargaining process in accordance with a set of objective principles. Subjects involved can form different coalitions which have some bargaining power to assure to its members a certain payoff. This is reflected by the coalition value $v(S)$. The distributive rule of the overall profit in accordance with the Shapley value captures the intrinsic bargaining power of the players represented by the coalition values. This means, the Shapley value is a solution concept of a TU-game, i.e., an outcome of a coalitional bargaining game.

Moreover, the Shapley value refers to nondiscriminatory and upright standards that even apply in situation with unequal partners. These standards define objective principles on which subjects can agree or disagree. This set of objective principles determines a fair division of the profits among subjects. This means, the Shapley value relies on an axiomatic foundation on which subjects can obey. The axiomatic characterization of the Shapley value as given by Shapley (1953) is as follows: Efficiency, Symmetry, Dummy Player and Additivity (see a textbook for the exact definitions). Thus, if a set of subjects agree to obey the distributive rule given by this axiomatization, then the total profit must be distributed in accordance with the Shapley value. However, in case that a subject proposes a different distribution of the profit, then this proposal is vulnerable in the sense that it does not reflect the agreed upon rule of arbitration. From this consideration it should be obvious that it is not necessarily required that an agreement on a rule of distributive justice needs to be binding (cf. Chapter 3-4 of my book http://www.springer.com/us/book/9783642395482).

From the preceding discussion, it should also be obvious that $\phi$ is not a bijective mapping, and that $\rho$ is not the inverse of $\phi$. Thus, we do not have a particular inverse direction for $\phi$. As a consequence, we can only observe a tight relationship between $\phi(\rho(x))$ and $x$, if the game is, for instance, additive. Then we have $\phi(\rho(x)) = x$. As an example let us consider the vector $x=\{3,7,2,5\}$, the corresponding additive game is (lexi-order)

$$ v=[3,7,2,5,10,5,8,9,12,7,12,15,10,14,17], $$

and the Shapley value of this game is again the vector $x=\{3,7,2,5\}$.

In addition, if we have a game $v$, then we can decompose it by a linear basis approach into a flat game $z$ and an additive game $w$, s.t. $v=z+w$. The Shapley value of game $v$ can be decomposed by $\phi(v)=\phi(z+w)=\phi(w)$, thus $\phi(z)=\mathbf{0}$. Let us consider as an example the following convex game (lexi-order)

$$ v=[0,0,0,0,0,0,0,0,0,0,0,3,0,2,5],$$

the Shapley value of this game is given by $\phi(v)=\{1,5/3,2/3,5/3\}$.

The linear decomposition of $v$ produces a flat game given by

$$ z=[-1,-5/3,-2/3,-5/3,-8/3,-5/3,-8/3,-7/3,-10/3,-7/3,-10/3,-4/3, -10/3,-2,0], $$

where the Shapley value is given by $\phi(z)=\mathbf{0}$, and an additive game

$$ w=[1,5/3,2/3,5/3,8/3,5/3,8/3,7/3,10/3,7/3,10/3,13/3,10/3,4,5], $$

with a Shapley value of $\phi(w)=\{1,5/3,2/3,5/3\}$, hence $\phi(v)=\phi(w)$. Therefore, in both games the bargaining power of the players is similar in accordance with the rule of arbitration represented by Shapley value, and distributes the profit for both games in the same way. However, note that this is not the case for the pre-nucleolus. There we obtain $\nu(v)=\{4/3,4/3,1,4/3\}, \nu(z)=\{1/3,1/3,1/3,-1/3 \}$, and $\nu(w)=\{1,5/3,2/3,5/3\}$ respectively.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.