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

A simple cooperative game is a transferable utility game $(N,v)$ withA coalition of value $1$ is a winning coalition; a value-$0$ coalition loses. The displayed definition uses the usual monotone, nontrivial convention: the empty coalition loses and the grand coalition wins.

An induced subgraph game is a transferable utility game represented by a weighted undirected graph with one vertex per player; a coalition's value is the sum of the edge weights in its induced subgraph. With no self-loops,where each unordered pair is counted once and an absent edge has weight zero. Weights may have either sign. In an induced subgraph game with self-loops, write the loop weight at $i$ as ${\ell }_i$ and add ${\sum }_{i\in S}{\ell }_i$, counting each loop once. In particular, $v(\{i\})={\ell }_i$ when loops are allowed and is zero otherwise.^[ref]

No representation exists, even allowing arbitrary signed weights and self-loops. Every singleton coalition loses, so each loop weight must be ${\ell }_i=v(\{i\})=0$. Every two-player coalition wins, which then forcesThe represented grand-coalition value would consequently becontradicting 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.

Yes; without self-loops, such a nontrivial simple cooperative game has exactly one positive edge, of weight $1$. For each pair,because singleton and loop contributions are zero. Summing all edge weights gives $v(N)=1$, so precisely one unordered pair $\{a,b\}$ has weight $1$, and all other pairs have weight zero.

Thus the winning coalitions are exactly those containing both $a$ and $b$. For any $0\le \lambda \le 1$, setThis payoff vector is efficient, since ${\sum }_i{x}_i=v(N)=1$. Every winning coalition receives $1$ and every losing coalition receives a nonnegative total, so all inequalities $x(S)\ge v(S)$ hold. Hence it belongs to the core of a cooperative game.

In fact these are all core allocations. Singleton conditions require $x_i\ge 0$, and the winning pair requires $x_a+x_b\ge 1$; efficiency then forces equality and zero payoffs outside the pair. The endpoints are both veto players, consistent with the general characterization of the core of a simple cooperative game.

No. Two positive self-loops and one negative edge give a simple cooperative game with an empty core of a cooperative game. Give players $1,2$ loop weights ${\ell }_1={\ell }_2=1$, put $w_{12}=-1$, and give every other loop and edge weight zero. For a coalition $S$,Thus a coalition wins exactly when it contains player $1$ or player $2$. This is monotone, has values in $\{0,1\}$, and satisfies $v(\varnothing )=0,v(N)=1$. Extra players for any $n\ge 3$ do not alter any coalition value.

The core singleton inequalities would require $x_1\ge 1$, $x_2\ge 1$ and $x_i\ge 0$ for every other player, while efficiency requires ${\sum }_i{x}_i=1$. These requirements are inconsistent. Equivalently, the two disjoint winning singleton coalitions leave no veto player. Signed weights are essential to this particular representation and are permitted in the induced subgraph game model.

A loop-free induced subgraph game is a convex cooperative game if and only if every edge weight is nonnegative. Necessity follows by applying the supermodular inequality to $S=\{i\}$ and $T=\{j\}$. Since both singleton values and the empty value are zero,

Conversely, direct cancellation of common edge contributions gives, for any coalitions $S,T$,Every summand is nonnegative, proving that $v$ is a supermodular set function and hence convexity. Equivalently, a player's marginal contribution to $S$ is ${\Delta }_i(S)={\sum }_{j\in S}{w}_{ij}$, which cannot decrease as $S$ grows. This establishes the convexity criterion for an induced subgraph game directly.^[ref]

There is exactly one such nontrivial game for every $n\ge 1$: the unanimity game requiring every player. PutIt is a simple cooperative game, and permuting players preserves every coalition value. Thus it has the required symmetry of players in a cooperative game. It is also a convex cooperative game: if both $S,T$ are winning, all four terms in the supermodular inequality have value $1$; if exactly one is winning, their union is $N$ and their intersection loses, giving equality $1=1$; if neither wins, the right-hand side is zero and the inequality follows from nonnegativity. For $n=1$ the same definition gives the sole player value $1$.

To prove uniqueness, first establish that convex simple games are unanimity games. If $S,T$ are winning coalitions, the supermodular inequality givesso their intersection is also winning. The family of winning coalitions is finite and nonempty. Its intersection $K$ is therefore winning and nonempty, since the empty coalition loses. Every winning coalition contains $K$, and monotonicity makes every superset of $K$ winning. Hence $v=u_K$.

If $K$ were a proper nonempty subset of $N$, take $i\in K$ and $j\notin K$, and let $T=N\setminus \{i,j\}$. Then $T\cup \{i\}=N\setminus \{j\}$ contains $K$ and wins, whereas $T\cup \{j\}=N\setminus \{i\}$ loses. This violates symmetry of players in a cooperative game, which requires those two coalition values to agree. Thus $K=N$, proving the claimed count. The “nontrivial” convention excludes the identically zero game; if that degenerate game were also called simple, it would supply one additional symmetric convex example.