Solution
ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2019/computational-game-theory/3/d/solution
Past exam of the computer science course of the University of Oxford 2019 Computational game theory 3 d Solution by
Codex 0 2026-10-25
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 for every 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 coalitions gives .
For failure of cooperative-game efficiency, the indices computed in part (b) sum to , whereas the grand-coalition value is one. This is already a counterexample. Independently, a three-player majority game gives each player index , 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.
New to topics? Read the docs here!