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?
Best Answer
You should use lexicographic degeneracy resolution, and in particular the lexicographic minimum ratio test.
Actually the notes you cite mention this correctly:
[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.