Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2020/computational-game-theory/3/g/solution

There is exactly one such nontrivial game for every : the unanimity game requiring every player. Put
It 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 are winning, all four terms in the supermodular inequality have value ; if exactly one is winning, their union is and their intersection loses, giving equality ; if neither wins, the right-hand side is zero and the inequality follows from nonnegativity. For the same definition gives the sole player value .
To prove uniqueness, first establish that convex simple games are unanimity games. If are winning coalitions, the supermodular inequality gives
so their intersection is also winning. The family of winning coalitions is finite and nonempty. Its intersection is therefore winning and nonempty, since the empty coalition loses. Every winning coalition contains , and monotonicity makes every superset of winning. Hence .
If were a proper nonempty subset of , take and , and let . Then contains and wins, whereas loses. This violates symmetry of players in a cooperative game, which requires those two coalition values to agree. Thus , 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.

New to topics? Read the docs here!