Lemke-Howson pivoting in degenerate bimatrix games I'm working on an implementation of the Lemke-Howson algorithm for finding Mixed Nash Equilibria of bimatrix games, and I'm running into a roadblock when the algorithm is fed a degenerate game. For example, consider the following payoff matrix:
\begin{align*}
\begin{array}{c|c|c|c}
   & L   &    M  &     R \\
\hline
A & (1,3) & (3,3) &  (3,1) \\
B & (3,1)  & (1,1) & (3,3) \\
C & (1,3)  & (3,1)  & (3,3) \\
\hline
\end{array}
\end{align*}
The corresponding tableaus for this game are:
$$
\begin{array}{c}
r_1 = 1 - y_4 - 3y_5 - 3y_6 \\
r_2 = 1 - 3y_4 - y_5 - 3y_6 \\
r_3 = 1 - y_4 - 3y_5 - 3y_6
\end{array}
$$
$$
\begin{array}{c}
s_4 = 1 - 3x_1 - x_2 - 3x_3 \\
s_5 = 1 - 3x_1 - x_2 - x_3 \\
s_6 = 1 - x_1 - 3x_2 - 3x_3
\end{array}
$$
Following the description of pivoting steps found here, if I start by bringing $x_1$ into the basis, I immediately run into a tie in when applying the min-ratio rule between $s_4$ and $s_5$. This is expected because the game is degenerate. If I arbitrarily choose to bring $s_5$ out of the basis, I end up with
$$
\begin{array}{rcl}
s_4 &=& -2x_3 + s_5 \\
x_1 &=& \frac{1}{3} - \frac{1}{3}x_2 - \frac{1}{3}x_3 - \frac{1}{3}s_5 \\
s_6 &=& \frac{2}{3} - \frac{8}{3}x_2 - \frac{8}{3}x_3 + \frac{1}{3}s_5
\end{array}
$$
Since $s_5$ was removed from the basis, I bring $y_5$ into the basis next. Again, the min-ratio rule ties, this time between $r_1$ and $r_3$. If I choose to bring $r_1$ out of the basis, the algorithm terminates, and leaves me with
\begin{array}{rcl}
\vec{x} &=& (1, 0, 0) \\
\vec{y} &=& (0, 1, 0)
\end{array}
$$
However, the expected MNE for this game is
$$
\begin{array}{rcl}
\vec{x} &=& (0.5, 0.5, 0) \\
\vec{y} &=& (0, 0, 1)
\end{array}
$$
If in the first pivoting step, I choose to break the tie by bringing $s_4$ out of the basis, I bring in $y_4$ for $s_2$ after that with a unique application of the min-ratio rule, therefore bringing in $x_2$ for $s_6$ with another unique application of the min-ratio rule after that. The algorithm terminates with the correct answer if I break the following tie between $r_1$ and $r_3$ by choosing $r_1$.
How can I break ties in the min-ratio rule when pivoting so that I can get the correct MNE for the game?
 A: You should use lexicographic degeneracy resolution, and in particular the lexicographic minimum ratio test.
Actually the notes you cite mention this correctly:

By using infinitesimal perturbations, we can obtain a “good” tie-breaking rule that can be performed in polynomial time; see the section of [2] on the lexicographic method. However, this rule is impractical to perform by hand, so we will not describe it here, and no simpler one appears to be known in the literature.

[2] is the original paper of Lemke and Howson. Here are newer alternative descriptions of the lexicographic minimum ratio test and implementations to guide you:


*

*For the Lemke-Howson algorithm, it is described in Section 3.6 of: 
B. von Stengel (2007), Equilibrium computation for two-player games in strategic and extensive form. Chapter 3, Algorithmic Game Theory, eds. N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, Cambridge Univ. Press, Cambridge, 53-78. http://www.maths.lse.ac.uk/personal/stengel/TEXTE/agt-stengel.pdf

*It is used in von Stengel's implementation of Lemke's algorithm, which is very similar to the Lemke-Howson algorithm, here:   https://github.com/stengel/ecta2002

*It is also described for Lemke's algorithm in Section 3 of: 
Efficient computation of equilibria for extensive two-person games.  Daphne Koller, Nimrod Megiddo, and Bernhard von Stengel. Games and Economic Behavior 14 (1996), 247-259. http://www.maths.lse.ac.uk/personal/stengel/TEXTE/lemke.html

*It is also used in lrs, which has an open source implementation you can look at. Start with e.g.: 
lrs: A Revised Implementation of the Reverse Search Vertex Enumeration Algorithm.  David Avis. http://cgm.cs.mcgill.ca/~avis/doc/avis/Av98a.pdf

*It is described for the simplex method for linear programming on page 36 of: 
Chvatal, Vasek (1983). Linear Programming. New York: Freeman.
