= 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.
Back to article page
