4
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

You should use lexicographic degeneracy resolution, and in particular the lexicographic minimum ratio test.

Actually the notes you cite mentions 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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .