Equilibrium in a two-row binary game

Write column $j$ of a two-row binary game as $((a_j,c_j),(b_j,d_j){)}^T$, with the row player's payoff first. If there is no pure Nash equilibrium, the column player's maximum payoff in each row must be one. Otherwise every column would be a best response in a zero-payoff row, and excluding an equilibrium there would force the opposite row to dominate in every column, giving an equilibrium in that opposite row.

A column maximizing the column player's top-row payoff must then have $(a_j,b_j)=(0,1)$, or its top cell would be an equilibrium. Its bottom column-player payoff must be zero, or its bottom cell would be one. Thus a column $((0,1),(1,0){)}^T$ occurs. The same argument for the bottom row produces $((1,0),(0,1){)}^T$. No column can give the column player payoffs $(1,1)$, since a row-player best response within that column would be a pure equilibrium.

Consequently, if neither pure equilibrium is found, mix equally over the two rows and equally over those two special columns. The row player's two expected payoffs are $1/2$; every column gives the column player at most $1/2$, and the supported columns achieve $1/2$. This is a Nash equilibrium. Computing the two row maxima, scanning for pure equilibria and locating the two special columns takes $O(n)$ running time for $n$ columns.