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

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 requireAdding givesso 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.

Let $W(C)={\sum }_{i\in C}{w}_i$. If the two disjoint winning coalitions exchange players, the aggregate weight is conserved:If both resulting coalitions lost, each weight would be strictly below $q$, making their sum strictly below $2q$. This is impossible. Thus every weighted voting game has swap robustness for disjoint winning coalitions, even when the weights or quota are negative.

The converse is false. The four-player prime-cardinality game from part (a) has swap robustness for disjoint winning coalitions: swapping one player each way preserves each coalition's cardinality, so in fact both winning coalitions remain winning. Part (a) proves it is not a weighted voting game.

Even imposing monotonicity would not repair the converse under the printed disjointness restriction. As a stronger counterexample, use five players and declare a coalition winning exactly when it contains player $1$ and contains either both $2,3$ or both $4,5$. This is a simple cooperative game, and all its winning coalitions contain player $1$, so no two are disjoint; the stated swap condition holds vacuously.

Nevertheless $\{1,2,3\}$ and $\{1,4,5\}$ win, while $\{1,2,4\}$ and $\{1,3,5\}$ lose. Both pairs contain every player the same total number of times. A weighted representation would therefore givea contradiction. This is a trade obstruction to weighted voting and pinpoints how weak the disjoint-only swap requirement is.

Use the usual empty-coalition normalization $v(\varnothing )=0$ for a transferable utility game. Write $P_i=\{1,\dots ,i-1\}$, so the proposed payoff is the marginal contributionThe vector is the marginal contribution vector for the natural player order.

First, convex cooperative games have increasing marginal contributions. If $A\subseteq B$ and $i\notin B$, apply the defining supermodular set function inequality to $A\cup \{i\}$ and $B$:Rearranging gives

The vector is efficient by a telescoping sum:Now fix any coalition $T$. For each $i\in T$, its earlier members are $T\cap P_i\subseteq P_i$. Increasing marginal contributions therefore giveSum over the members of $T$ in increasing order. The right-hand side is another telescoping sum, now along the growing coalition $T$:Efficiency and these inequalities for every coalition are exactly the defining requirements of the core of a cooperative game. Thus $x$ belongs to the core. The same proof works for any player ordering, not only the natural order.

The normalization is essential to the literal statement: the printed part does not explicitly state it. Without $v(\varnothing )=0$, take the constant characteristic function of a coalitional game $v(T)=1$. It satisfies the displayed convex cooperative game inequality with equality, but every proposed $x_i$ is zero, so efficiency fails when $N$ is nonempty. Under the standard normalized definition, the proof above establishes the intended result.