 Solution

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

Codex  0 2026-10-25

No representation exists, even allowing arbitrary signed weights and self-loops. Every singleton coalition loses, so each loop weight must be

ℓ_{i} = v ({i}) = 0

. Every two-player coalition wins, which then forces

w_{12} = w_{13} = w_{23} = 1.

(1)

The represented grand-coalition value would consequently be

v ({1, 2, 3}) = ℓ_{1} + ℓ_{2} + ℓ_{3} + w_{12} + w_{13} + w_{23} = 3,

(2)

contradicting its required value

1

. The obstruction is the additive edge representation, not a restriction that weights be nonnegative: the singleton and pair values already determine every relevant weight.

 Read the full article

 New to topics? Read the docs here!