Solution

It suffices to take four players. Both two-player coalitions

{1, 2}

and

{3, 4}

win, because two is a prime number, while the empty coalition and the four-player coalition lose.

Suppose real weights and quota

q

represented this game. The empty coalition loses, so

0 < q

. The two winning coalitions require

w_{1} + w_{2} \geq q, w_{3} + w_{4} \geq q .

(1)

Adding gives

w_{1} + w_{2} + w_{3} + w_{4} \geq 2 q > q,

(2)

so the four-player coalition must win, a contradiction. Hence prime-cardinality games cannot in general be represented as weighted voting games. The same four-player obstruction appears inside every such game with at least four players.

This proof permits negative individual weights, as the printed definition does. An argument based solely on monotonicity would require a nonnegative-weight assumption and would not suffice for that definition.

 Ancestors (11)

 View article source

 Discussion (0)

New discussion

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

Past exam of the MSc in advanced computer science course of the University of Oxford / 2023 / Computational game theory / 4 / a / Solution

 Ancestors (11)

 Discussion (0)  Subscribe (1)

 Articles by others on the same topic (0)

 Discussion (0)