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