lemke#

lemke is a pure Python implementation of Lemke’s algorithm for linear complementarity problems (LCPs), including its application to computing a Nash equilibrium of a bimatrix game. It uses exact rational arithmetic and is built for teaching and research, where you want to see each pivot. It can be used as both a callable library and a CLI tool.

lemke is part of the Gambit project for computation in game theory, and it builds on the work of Bernhard von Stengel.

Features#

  • Lemke’s algorithm for linear complementarity problems, with a covering vector \(d\);

  • Lexicographic minimum ratio test to handle degenerate problems;

  • Arbitrary precision with integer pivoting;

  • Lemke–Howson and the tracing procedure for bimatrix games;

  • Verbose tableau output that shows every pivot;

  • Command-line tools: lemke, bimatrix and randomstart.

Usage examples#

Here are two quick examples of using lemke. You can view more detailed explanations in the tutorials/index.

1) Solve a 2×2 LCP in Python#

Consider LCP given in examples/lcp_2x2: find \(z \ge 0\) with \(w = q + Mz \ge 0\) and \(z^\top w = 0\), where

\[\begin{split}M = \begin{pmatrix} \frac{1}{2} & 1 \\ -1 & \frac{5}{2} \end{pmatrix}, \qquad q = \begin{pmatrix} -1 \\ -1 \end{pmatrix}.\end{split}\]
>>> from fractions import Fraction as F
>>> from lemke.lemke import lcp, runlemke
>>> problem = lcp(
...    M=[
...       [F(1, 2), F(1)],
...       [F(-1), F(5, 2)],
...    ],
...    q=[F(-1), F(-1)],
...    d=[F(1), F(1)],
... )
>>> result = runlemke(lcp=problem)
>>> result.success
True
>>> result.z
(Fraction(2, 3), Fraction(2, 3))

The solution is exact: \(z = (\frac{2}{3}, \frac{2}{3})\), with \(w = 0\).

2) Find a Nash equilibrium from the CLI#

Find Nash equilibria with the Lemke–Howson method for the bimatrix game in examples/game, where the payoff matrices are

\[\begin{split}A = \begin{pmatrix} 3 & 0 \\ 0 & 2 \end{pmatrix}, \qquad B = \begin{pmatrix} 2 & 0 \\ 0 & 7 \end{pmatrix}.\end{split}\]

Save the following as game_file:

# m,n=
2 2

# A=
3 0
0 2

# B=
2 0
0 7

Then run:

$ bimatrix lh game_file

The algorithm runs for all labels by default and finds 2 equilibria:

label 1 found eq (1,0),(1,0)
    supports: [0][0]
label 2 found eq (0,1),(0,1)
    supports: [1][1]
-------- equilibria found: --------
(1,0),(1,0)
    supports: [0][0] found by labels [1, 3]
(0,1),(0,1)
    supports: [1][1] found by labels [2, 4]

Installation#

lemke needs Python 3.10 or later.

It is not yet available on PyPI, but can be installed directly from GitHub:

pip install git+https://github.com/gambitproject/lemke.git

Citing lemke#

lemke is Free/Open Source software, released under the terms of the GNU General Public Licence, version 3 (GPL-3.0).

If you use lemke in a scientific publication, you can use the following citation:

Von Stengel, B. (2026). lemke: Lemke’s algorithm for linear complementarity problems and bimatrix games. https://github.com/gambitproject/lemke.