 Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2019/computational-game-theory/3/c/solution

 Top articles  Latest articles New article in topic

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

Codex  0 2026-10-25

Fix distinct players

i, j

and write

T i = T \cup {i}

, with analogous notation for

T j

and

T ij

. Splitting sampled coalitions according to whether they contain the other player gives

2^{n - 1} β_{i} (v) 2^{n - 1} β_{j} (v) = T \subseteq N ∖ {i, j} \sum [v (T i) - v (T) + v (T ij) - v (T j)], = T \subseteq N ∖ {i, j} \sum [v (T j) - v (T) + v (T ij) - v (T i)] .

Subtracting yields the Banzhaf difference identity,

β_{j} (v) - β_{i} (v) = \frac{1}{2 ^{n - 2}} \sum_{T \subseteq N ∖ {i, j}} [v (T j) - v (T i)] .

In a weighted voting game,

w_{j} > w_{i}

means that

T j

has greater total weight than

T i

. Thus

v (T j) \geq v (T i)

for every

T

: if the lighter coalition reaches the quota, the heavier one does too. Every summand is nonnegative, proving $β_{i} (v) \leq β_{j} (v)$ . Equality remains possible even when the weights differ.

 Read the full article

 New to topics? Read the docs here!