= Solution
Compute $C=\max_jc_j$ and $D=\max_jd_j$ in one pass. Scan the columns again: return the top cell of column $j$ if $c_j=C$ and $a_j\geq b_j$, or its bottom cell if $d_j=D$ and $b_j\geq 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 columns
$$
\begin{pmatrix}(1,0)\\(0,1)\end{pmatrix},\qquad\begin{pmatrix}(0,1)\\(1,0)\end{pmatrix}.
$$
Locate 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\leq1$, and against the equal row mixture its <expected payoff> is at most $1/2$. The two supported columns attain that bound.
Hence \b[the returned half-half profile is a <Nash equilibrium> against every column, not only the two supported ones]. A constant number of scans takes \b[$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>.
Back to article page
