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

Compute $C={\max }_j{c}_j$ and $D={\max }_j{d}_j$ in one pass. Scan the columns again: return the top cell of column $j$ if $c_j=C$ and $a_j\ge b_j$, or its bottom cell if $d_j=D$ and $b_j\ge a_j$. Each test is exactly mutual best response, so any returned cell is a pure Nash equilibrium.

If none is found, part (e) supplies columnsLocate one of each and mix with probability $1/2$ on each of those two columns, while the row player mixes $1/2$ on each row. The two row actions then both have expected payoff $1/2$.

To check all opposing deviations, observe that no column can have $(c_j,d_j)=(1,1)$. Such a column would maximize the column player's payoff in either row; choosing a row-player best response within it would give a pure equilibrium, contrary to the failed scan. Therefore every column has $c_j+d_j\le 1$, and against the equal row mixture its expected payoff is at most $1/2$. The two supported columns attain that bound.

Hence the returned half-half profile is a Nash equilibrium against every column, not only the two supported ones. A constant number of scans takes $O(n)$ running time, with constant auxiliary storage if the output mixture is represented by its two supported column indices and probabilities. This is the construction in equilibrium in a two-row binary game.