1
$\begingroup$

Suppose we have $n$ players in a cooperative game; let the set of all players be denoted $U = \{1, 2, \dots, n\}$. The characteristic function $v: 2^{U} \rightarrow \mathbb{R}$ (where $2^U$ is the powerset of $U$) maps subsets of $U$ to a value in the reals which denotes the value generated by some subset of the players $S$ ($S \subset U$) if they cooperate.

Given some characteristic function $v$, the allocation vector $\psi(v) \in \mathbb{R}^n$ gives us the amount of the total value generated allocated to each player in $U$. In particular, for $i \in U$, $\psi_i(v)$ is the portion of the value allocated to the $i$th player under the the characteristic function $v$.

One way of determining/constraining $\psi$ is by listing some axioms $v$ and $\psi$ must follow. For example, the Shapley axioms:

  • (symmetry) for any $S \subset U$ and $i,j \not\in S$, if $v(S \cup \{i\}) = v(S \cup \{j\})$ then $v(\{i\}) = v(\{j\})$

  • (dummy) given some $i \in U$, if for all $S \subset U$, $v(S \cup \{i\}) = v(S)$, then $v(\{i\}) = 0$

  • (efficiency) $\sum_{i \in U} \psi_i(v) = v(U)$

  • (additivity) given two characteristic functions $v$ and $v'$, and some $i \in U$, then $\psi_i(v + v') = \psi_i(v) + \psi_i(v')$

Consider the $S$-veto game: let $S \subset U$ be a special "veto block", and let $w_S$ be the characteristic function for the game such that if $S \subseteq A$, then $w_S(A) = 1$, otherwise $w_S(A) = 0$. In other words, the block of players $S$ generates all the possible value game. Suppose that $w_S$ and $\psi(w_S)$ follow the Shapley axioms. How do the axioms then constrain $w_S$ and $\psi(w_S)$?

  • (symmetry) for any $i, j \not\in S$, where $S$ is the veto-block, $w_S(S \cup \{i\}) = w(S \cup \{j\}) = w_S(S)$, where the final equality follows from the definition of the $S$-veto game

  • (dummy) as a consequence of symmetry, we know that if $i \not\in S$, then $w_S(S \cup \{i\}) = w_S(S)$, so the dummy axiom tells us that $w_S(\{i\}) = 0$

  • (efficiency) $\sum_{i \in U} \psi_i(w_S) = w_S(U) = 1$

The text I am reading says that we can also determine, using the symmetry axiom, that: $$ i \in S \implies \psi_i(w_S) = \frac{1}{\left| S \right|}$$

I am a bit unsure how to determine this using the symmetry axiom. Suppose we have $i, j \in S$, and then consider $R = S \setminus \{i, j\}$. Note that $R \cup \{i\}$ and $R \cup \{j\}$ both only contain $S$ if $i = j$. If $i = j$, then symmetry only tells us the trivial truth $w_S(\{i\}) = w_S(\{i\})$. If $i \neq j$, then $w_S(R \cup \{i\}) = w_S(R \cup \{j\}) = 0$, because $S \not\subset R \cup \{i\}$, and similarly $S \not\subset R \cup \{j\}$.

The problem is that the symmetry axiom requires that both $i$ and $j$ are not in the set we want to apply the symmetry axiom around. Put differently, if the symmetry axiom was stated like so:

  • (modified symmetry) for any $A, A'$ and $i, j \in U$ such that $i \not\in A$ and $j \not\in A'$, $v(A \cup \{i\}) = v(A' \cup \{j\})$, then $v(\{i\}) = v(\{j\})$

then we could set $R_i = S \setminus \{i\}$ and $R_j = S \setminus \{j\}$, for which we have that $w_S(R_i \cup \{i\}) = w_S(R_j \cup \{j\}) = w_S(S) = 1$, and so $w_S(\{i\}) = w_S(\{j\})$ for all $i, j \in S$, which would give us the required by the efficiency axiom.

The issue with the modified symmetry axiom is that we could prove that dummy players generate the same value as non-dummy players. For instance, suppose $d$ is a dummy player, so that for any set $S$, $v(S \cup \{d\}) = v(S)$. Let $i \in S$ such that $v(S \setminus \{i\}) < v(S)$ (i.e. $i$ is not a dummy player) then:

$$ v(S) = v((S \setminus \{i\}) \cup \{i\}) = v(S \cup \{d\}) \implies v(\{i\}) = v(\{d\}) = 0 $$

which violates our assumption that $i$ is not a dummy player. Thus, I am fairly sure that the modified symmetry axiom is not how the symmetry axiom is meant to be interpreted.

So how can the symmetry axiom be used to prove that in the $S$-veto game:

$$ i \in S \implies \psi_i(w_S) = \frac{1}{\left| S \right|}$$

$\endgroup$
5
  • $\begingroup$ Something seems to be mixed up in the sentence following "Consider the $S$-veto game:". $\endgroup$
    – joriki
    Nov 23, 2019 at 20:39
  • $\begingroup$ @joriki thanks for catching that! is it better now? $\endgroup$
    – bzm3r
    Nov 23, 2019 at 20:42
  • $\begingroup$ Yes, it's fine now. $\endgroup$
    – joriki
    Nov 23, 2019 at 20:43
  • $\begingroup$ Something's still wrong, though, somewhere. Where you introduce $w_S$, it seems that it takes only the values $0$ and $1$. But then you want to show that it takes a value in between? $\endgroup$
    – joriki
    Nov 23, 2019 at 20:45
  • 1
    $\begingroup$ @joriki Ah yes, notation error. We want to show that $\psi_i(w_S)$, for any $i \in S$, is $1/\left|S\right|$. I fixed it in the main text. $\endgroup$
    – bzm3r
    Nov 23, 2019 at 20:56

1 Answer 1

1
$\begingroup$

I think you've misstated the symmetry axiom. It differs from the one in Wikipedia in two respects: There's a universal quantifier over $S$ in the premise, and the conclusion concerns $\psi$, not $v$. I believe in your notation the symmetry axiom should be:

For $i\ne j$, if $v(S\cup\{i\})=v(S\cup\{j\})$ for all $S$ with $i,j\notin S$ then $\psi_i(v)=\psi_j(v)$.

This readily yields the desired result, since the premise holds for any pair of players in the veto block, so they all have the same allocation, and since efficiency implies that they add to $1$, they must each be $\frac1{|S|}$.

$\endgroup$
1
  • 1
    $\begingroup$ You're right I misstated. I checked my text, and see that it talks about $\psi$ there too. Furthermore, I misunderstood and was trying to apply the symmetry axiom to $S$ in the veto block game; I should be applying it to all subsets of $U$ which do not contain $S$. Thanks! $\endgroup$
    – bzm3r
    Nov 23, 2019 at 22:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .