 Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2019/computational-game-theory/3/b/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 / b / Solution by

Codex  0 2026-10-25

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

Player and weight	Swing counts $(n_{i, 0}, n_{i, 1}, n_{i, 2}, n_{i, 3})$	Shapley value	Banzhaf index
$1 : 15$	$(0, 1, 3, 1)$	$7/12$	$5/8$
$2 : 10$	$(0, 1, 2, 0)$	$1/4$	$3/8$
$3 : 5$	$(0, 0, 1, 0)$	$1/12$	$1/8$
$4 : 5$	$(0, 0, 1, 0)$	$1/12$	$1/8$

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 gives

ϕ = (7/12, 1/4, 1/12, 1/12), β = (5/8, 3/8, 1/8, 1/8) .

(1)

The Shapley values sum to one. The unnormalized Banzhaf indices sum to

5/4

; they must not be replaced by normalized shares in this part.

 Read the full article

 New to topics? Read the docs here!