Past exam of the computer science course of the University of Oxford / 2019 / Computational game theory / 3

For a fixed finite player set $N$ and characteristic function $v$ with $v(\varnothing )=0$, let $\psi (v)$ be the allocated payoff vector. A standard four-axiom characterization is:

Cooperative-game efficiency: ${\sum }_{i\in N}{\psi }_i(v)=v(N)$.

Cooperative-game symmetry: if $v(S\cup \{i\})=v(S\cup \{j\})$ for every $S\subseteq N\setminus \{i,j\}$, then ${\psi }_i(v)={\psi }_j(v)$.

The null player axiom: if $v(S\cup \{i\})=v(S)$ for every $S\subseteq N\setminus \{i\}$, then ${\psi }_i(v)=0$.

Cooperative-game additivity: for games $v,w$ on the same $N$, ${\psi }_i(v+w)={\psi }_i(v)+{\psi }_i(w)$, where $(v+w)(S)=v(S)+w(S)$.

These axioms uniquely specify the Shapley value. This is the zero-marginal null-player convention. The original work combines some requirements into an equivalent formulation.^[ref]

Use the inclusive quota: a coalition wins at weight at least $25$. For each player, count losing predecessor coalitions that become winning when that player joins. Group these swing counts by predecessor cardinality $t=0,1,2,3$:

For example, player one is pivotal for predecessor coalitions $\{2\}$, $\{2,3\}$, $\{2,4\}$, $\{3,4\}$ and $\{2,3,4\}$. Player three is pivotal only for $\{1,4\}$; player four has the symmetric counterpart.

Each swing contributes $1/8$ to the probabilistic Banzhaf index. For the Shapley value, a swing with $t$ predecessors contributes $t!(3-t)!/4!$, which is $1/4,1/12,1/12,1/4$ for the four possible sizes. Applying these weights to the table givesThe Shapley values sum to one. The unnormalized Banzhaf indices sum to $5/4$; they must not be replaced by normalized shares in this part.

Fix distinct players $i,j$ and write $Ti=T\cup \{i\}$, with analogous notation for $Tj$ and $Tij$. Splitting sampled coalitions according to whether they contain the other player givesSubtracting yields the Banzhaf difference identity,In a weighted voting game, $w_j>w_i$ means that $Tj$ has greater total weight than $Ti$. Thus $v(Tj)\ge v(Ti)$ for every $T$: if the lighter coalition reaches the quota, the heavier one does too. Every summand is nonnegative, proving ${\beta }_i(v)\le {\beta }_j(v)$. Equality remains possible even when the weights differ.

The probabilistic Banzhaf index satisfies cooperative-game symmetry, the null player axiom and cooperative-game additivity, but not cooperative-game efficiency.

For cooperative-game symmetry, interchangeable players have $v(Ti)=v(Tj)$ for every $T$ omitting them. The Banzhaf difference identity therefore gives equal indices. For a null player, every marginal contribution in the defining average is zero, so its index is zero.

For cooperative-game additivity, each marginal contribution is additive:Averaging both sides over the same $2^{n-1}$ coalitions gives ${\beta }_i(v+w)={\beta }_i(v)+{\beta }_i(w)$.

For failure of cooperative-game efficiency, the indices computed in part (b) sum to $5/4$, whereas the grand-coalition value is one. This is already a counterexample. Independently, a three-player majority game gives each player index $1/2$, also exceeding the total value when summed. Pivotality averaged over independently chosen coalitions does not telescope in the way the ordering-average Shapley value does.

Where its denominator is nonzero, normalization enforces cooperative-game efficiency and preserves cooperative-game symmetry and the null player axiom. The violated axiom is cooperative-game additivity.

For an exact counterexample on three players, let $v$ be the majority game, and let $w$ be the dictatorship in which a coalition wins precisely when it contains player one. Their probabilistic Banzhaf indices arewith $v(N)=w(N)=1$. HenceUnnormalized indices add, so $\beta (v+w)=(3/2,1/2,1/2)$. Their sum is $5/2$, while $(v+w)(N)=2$. ThereforeThe sum game is a valid transferable utility game, although it is not binary; that is the natural domain of the additivity axiom. The failure comes from a game-dependent scaling factor. A zero denominator, as for the zero game, makes the displayed normalization undefined unless a separate convention is supplied; none of the counterexample's denominators vanish.