How to Learn the Lemke–Howson Algorithm: Best-Response Polytopes, Labels, Complementary Pivoting and Bimatrix Nash Equilibria

How can a finite two-player game be turned into a path-following algorithm that is guaranteed to end at a Nash equilibrium? Lemke–Howson does exactly that. It converts best-response conditions into labels on two polytopes, deliberately removes one label, then follows a complementary-pivot path until the missing label returns at a nontrivial fully labelled point.

This Learning Hall article begins with mixed strategies and best responses, builds the polytope representation carefully, explains complete labelling and the dropped-label path, then moves into tableau pivots, normalization, degeneracy, starting-label sensitivity, exponential worst cases and professional software practice.

Quick Read

A bimatrix game has payoff matrices A and B for the row and column players.
A mixed Nash equilibrium is a pair of probability vectors where each player puts positive probability only on best responses.
After shifting payoffs to be positive, best-response inequalities define two polytopes P and Q.
Each vertex receives labels representing either a zero-probability pure strategy or a tight best-response inequality.
A nonzero pair of points that collectively carries every label corresponds to a Nash equilibrium after normalization.
The origin pair is an artificial completely labelled starting point.
Lemke–Howson drops one label, creating exactly one duplicate label elsewhere.
Complementary pivots alternate between P and Q, removing the duplicate and creating a new duplicate.
The path ends when the originally dropped label reappears; the resulting nonzero pair is fully labelled.
The method finds one equilibrium, not necessarily all equilibria, and it can take exponentially many pivots on specially constructed games.

1. Beginner Level: What Is a Bimatrix Game?

Player 1 chooses one of m rows and Player 2 chooses one of n columns. If row i and column j are chosen, Player 1 receives A[i,j] and Player 2 receives B[i,j].

A = row-player payoffs
B = column-player payoffs

A mixed strategy is a probability distribution over pure strategies. Let p be the row player’s probability vector and q the column player’s. Expected payoff to Player 1 is pᵀAq; to Player 2 it is pᵀBq.

2. What Makes a Nash Equilibrium?

At equilibrium, no player can improve by changing strategy alone. In a mixed equilibrium, every pure strategy receiving positive probability must be a best response to the opponent’s mixture. Strategies that are strictly worse may receive probability zero.

This creates a complementarity pattern:

positive probability  ⇒ best-response constraint is tight
constraint not tight  ⇒ corresponding probability = 0

Lemke–Howson turns that complementarity into labels.

3. Shift Payoffs to Positive Values

A standard polytope formulation assumes positive payoffs. Add a sufficiently large constant to every entry of A and B so all entries are positive. Adding the same constant to all outcomes of one player does not change that player’s best responses, so the Nash equilibria are strategically unchanged.

4. Build the Best-Response Polytopes

Use unnormalised nonnegative vectors x∈R^m and y∈R^n. One common convention defines:

P = { x ≥ 0 : Bᵀx ≤ 1 }
Q = { y ≥ 0 : Ay ≤ 1 }

P captures the row player’s mixture scaled so every column-player pure-strategy payoff is at most 1. Q does the analogous job for row-player best responses. At equilibrium, inequalities corresponding to strategies used with positive probability become tight.

5. Labels on P

There are m+n labels. For a point x in P:

row label i is present when x_i=0;
column label m+j is present when (Bᵀx)_j=1.

So each label says either “this row strategy is unused” or “this column strategy is a best response to x.”

6. Labels on Q

For y in Q, the complementary convention is:

row label i is present when (Ay)_i=1;
column label m+j is present when y_j=0.

Now a pair (x,y) is completely labelled when every label 1,…,m+n appears on at least one of the two points.

7. Why Complete Labelling Encodes Equilibrium

Take a row strategy i. If x_i>0, P cannot supply label i through x_i=0, so Q must supply it through (Ay)_i=1: row i is a best response. Conversely, if row i is not best, Q lacks that tight label, so complete labelling forces x_i=0.

The same reasoning applies to column strategies. Therefore a nonzero fully labelled pair satisfies the support/best-response complementarity conditions of a mixed Nash equilibrium.

8. Why the Origin Is a Special Starting Point

At x=0, every row label is present because every x_i=0. At y=0, every column label is present because every y_j=0. The pair (0,0) is therefore completely labelled—but it cannot be normalized into probability distributions.

Lemke–Howson uses this artificial equilibrium as a convenient starting vertex and then forces the path away from it.

9. Drop One Label

Choose an initial label k to remove. Leave the origin along the unique adjacent edge that makes label k disappear while preserving all other labels. The pair is now almost completely labelled: label k is missing, and as the path moves a different label becomes duplicated across P and Q.

The starting label matters. Different dropped labels can lead to different equilibria and very different path lengths.

10. Complementary Pivoting

Suppose label ℓ is duplicated: it appears on both current polytope vertices. Pivot on one side to remove ℓ there. Moving to the adjacent vertex introduces another label r. Now r is duplicated, so pivot on the opposite polytope to remove r. Continue alternating.

drop k
→ duplicate ℓ
→ pivot away ℓ
→ duplicate r
→ pivot away r
→ ...
→ dropped k reappears

This is why the algorithm is called complementary pivoting: each pivot restores complementarity for the duplicated label while shifting the defect to another label.

11. Why the Path Does Not Branch in the Nondegenerate Case

In a nondegenerate bimatrix game, each polytope vertex has exactly the expected number of tight independent constraints. An almost-completely-labelled vertex pair therefore has degree two in the path graph of complementary pivots: one edge is where we came from, the other is where we go next.

This path-following structure is the constructive heart of the 1964 existence proof.

12. Termination at a Real Equilibrium

The path cannot return to the starting origin through the same missing-label orientation without retracing. In the nondegenerate finite graph, following the complementary path eventually reaches the other endpoint, where the originally dropped label k reappears. There is no duplicate label left, so the pair is fully labelled and nonzero.

Normalize:

p = x / sum(x)
q = y / sum(y)

The resulting probability vectors form a Nash equilibrium.

13. A Tiny 2×2 Mental Model

In a 2×2 game, P and Q are polygons in two dimensions. Their vertices correspond to combinations of zero-probability and tight-best-response constraints. A Lemke–Howson run can literally be drawn as a path walking along polygon edges while one label is missing and another is duplicated.

Do this graphically before using tableaux. The geometry makes “drop one label, chase the duplicate” far easier to understand than raw pivot arithmetic.

14. Tableau Implementation

Software usually represents the two polytopes with tableaux. A pivot chooses an entering variable corresponding to the duplicated label and uses a ratio test to determine which basic variable leaves. The leaving variable’s label becomes the next duplicate.

enter duplicate label
→ ratio test
→ pivot
→ leaving label becomes next duplicate
→ switch tableau

Modern Nashpy exposes Lemke–Howson directly and its current implementation includes a lexicographic option for pivoting.

15. Degeneracy

A game is degenerate when a mixed strategy has more pure best responses than the size of its support, or equivalently when polytope vertices have extra labels/tight constraints. Then the simple path may branch, ratio tests can tie, and naïve pivoting may cycle or return malformed supports.

Professional implementations use lexicographic pivoting, symbolic perturbation or other anti-cycling conventions. Always distinguish the clean nondegenerate theory from production handling of degenerate inputs.

16. Lemke–Howson Finds One Equilibrium, Not All

Running the algorithm with one dropped label follows one path to one equilibrium. Trying every initial label may find several equilibria, but there is no guarantee that all equilibria are discovered exactly once. Support enumeration, vertex enumeration and other algorithms serve different jobs.

17. Worst-Case Complexity Is Not Polynomially Bounded

The original construction is elegant and often practical, but it does not imply a polynomial-time algorithm for all bimatrix games. Savani and von Stengel constructed families where every Lemke–Howson path is exponentially long in the game dimension.

This fits the broader complexity picture: computing a Nash equilibrium of a two-player game is PPAD-complete. A pivot method can be excellent software without being a general polynomial-time solution to the equilibrium problem.

18. Starting-Label Sensitivity

A game with m+n labels gives multiple possible runs. One starting label may reach an equilibrium quickly while another may take far longer. Practical solvers sometimes try several dropped labels or use heuristics.

Benchmark path length by starting label, not just by game size.

19. Failure Modes

Not shifting payoffs positive under the chosen polytope formulation. Inequality geometry can fail.
Mixing the label convention for P and Q. Row/column zero labels and tight-response labels are complementary.
Normalizing the artificial origin. Its coordinate sums are zero.
Pivoting on the wrong tableau. The duplicated label dictates the complementary side.
Ignoring ratio-test ties. Degenerate games require deterministic anti-cycling logic.
Assuming one run returns all equilibria.
Comparing floating tableau entries with exact equality without tolerance/exact arithmetic policy.

20. Professional Testing Strategy

Verify returned strategies are nonnegative and sum to 1.
Compute each player’s pure-strategy expected payoffs and verify support strategies are best responses.
Test matching pennies, coordination games and games with pure equilibria.
Run every possible initial dropped label and compare endpoints/path lengths.
Test degenerate games against a trusted solver and exercise lexicographic pivoting.
Compare with Nashpy’s current implementation.
For small games, enumerate supports and confirm the Lemke–Howson result belongs to the equilibrium set.

21. How to Learn It Efficiently

Start with one 2×2 game and draw both best-response polytopes. Write the label set beside every vertex. Identify the artificial origin, remove one label with a pencil, and trace duplicate labels manually. Only after the path is visually obvious should tableau pivots be introduced.

A strong PRIMM sequence is: predict the next duplicate label, run one pivot, investigate why complementarity is preserved, modify the dropped label, then make a small solver. Parsons problems can scaffold the pivot loop without hiding the geometry.

22. Professional Applications and Limits

Computational game theory.
Teaching constructive fixed-point/equilibrium arguments.
Benchmarking equilibrium algorithms for bimatrix games.
Research on PPAD and path-following complexity.
Small and medium two-player games where one equilibrium is sufficient.

Do not treat a computed Nash equilibrium as a prediction without domain interpretation. Equilibrium says no unilateral deviation is profitable under the model; it does not guarantee fairness, uniqueness, social desirability or empirical behavioural accuracy.

23. Practice Problems

Shift a bimatrix game to positive payoffs and show best responses are unchanged.
Construct P and Q for a 2×2 game.
Assign every label to every polytope vertex.
Trace a complete Lemke–Howson path for each possible dropped label.
Normalize the final x,y pair and verify best-response conditions.
Create a degenerate game and observe a tied pivot.
Compare Lemke–Howson with support enumeration in Nashpy.
Measure pivot counts across random games and different initial labels.

24. Sources and Further Reading

Final idea: Lemke–Howson makes equilibrium computable by turning “everyone is best-responding” into a labelling invariant. The algorithm deliberately breaks one piece of complementarity and then follows the only path that keeps every other piece intact until the missing label returns. That transformation—from strategic conditions to a geometric pivot path—is the idea worth learning.

Small Group Tutorials