Past exam of the computer science course of the University of Oxford / 2019 / Computational game theory / 2 / e / Solution

Write column $j$ as $((a_j,c_j),(b_j,d_j){)}^T$, where the row player's binary payoff is first. Suppose, for a contradiction, there is no pure Nash equilibrium.

The column player's maximum payoff in the top row must be one. Otherwise every column would be its best response there. To avoid a top-row equilibrium, every column would then need $a_j=0,b_j=1$. But a column maximizing $d_j$ would immediately give a bottom-row equilibrium. The same reasoning with rows exchanged shows that the maximum bottom-row column payoff is also one.

Choose a column with $c_j=1$. To avoid a top-row equilibrium, it must have $a_j=0,b_j=1$. It cannot also have $d_j=1$, because its bottom cell would then be an equilibrium. Hence this column is $((0,1),(1,0){)}^T$, the specified second column type. Exchanging rows forces a column $((1,0),(0,1){)}^T$, the specified first type.

Thus absence of a pure equilibrium forces both forbidden column types to occur. If the given game omits them, this is a contradiction, proving existence of a pure Nash equilibrium. The argument actually proves the stronger statement that omitting either one of the two types suffices.