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

Table of contents
- Solution c

Solution

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.

 Ancestors (10)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version