= Solution
The <equilibrium oddness theorem> gives a finite odd number of <Nash equilibria> in a finite nondegenerate <bimatrix game>. One way to see the parity is through the endpoint argument underlying the <Lemke-Howson algorithm>. Add sufficiently large constants to each payoff matrix so all entries are positive; this does not change <best responses>. Form the bounded <convex polytopes>
$$
X=\{s\geq0:Q^Ts\leq\mathbf1\},\qquad
Y=\{t\geq0:Pt\leq\mathbf1\}.
$$
Label an $s_i=0$ facet by row label $i$ and a tight $(Q^Ts)_j=1$ facet by column label $n+j$; in $Y$, label a tight $(Pt)_i=1$ facet by $i$ and $t_j=0$ by $n+j$. A completely labelled <vertex of a polytope> pair has either both vectors zero, or both nonzero and normalizes to a <Nash equilibrium>. In the latter case the labels express exactly the equilibrium best-response and zero-probability conditions. Nondegeneracy makes each <vertex of a polytope> have exactly $n$ distinct incident labels and each equilibrium correspond to one such pair.
Fix a label to drop and retain all pairs carrying every other label. Include the product-<convex polytope> edges that retain those labels. At a completely labelled pair there is one possible outgoing edge, obtained by dropping the fixed label. At any other retained <vertex of a polytope>, that label is missing and one other label is duplicated; dropping either copy gives the two incident edges. Thus this finite graph consists of paths and cycles, with its endpoints precisely the completely labelled pairs. A finite graph has an even number of degree-one vertices. Since one endpoint is the artificial zero pair, the number of genuine equilibrium endpoints is odd. This proves the required <equilibrium oddness theorem> and finiteness, without claiming that every equilibrium is reached from the zero pair on the same path.
For a <symmetric bimatrix game>, swapping players maps $(s,t)$ to $(t,s)$. Every nonsymmetric equilibrium lies in a distinct two-element pair; the fixed points of this involution are exactly the <symmetric equilibria>. Removing even-sized pairs from an odd total leaves an odd number of symmetric equilibria. In the present game, two equilibria form the swapped pair and the remaining one is $(x,x)$ with $x=(1/2,0,1/2)$. \b[There is exactly one symmetric equilibrium], as required.
Back to article page
