Nash Equilibrium
Nash Equilibrium (Lemke-Howson Algorithm) · Also known as: Lemke-Howson Equilibrium, Completely Labeled Pair
Nash Equilibrium is a game-theoretic solution concept where no player can unilaterally deviate to improve their payoff. Formalized by John Nash in 1950, the Lemke-Howson algorithm computationally finds equilibria in bimatrix games by identifying completely labeled vertex pairs in the strategy polytopes.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
When to use it
Use Nash Equilibrium analysis when studying games with two players and discrete strategy spaces, or when seeking fully mixed equilibria. Suitable for modeling competition, negotiation, and coordination problems where strategic interaction is paramount. The Lemke-Howson method works best for non-degenerate bimatrix games; degenerate cases may require symbolic computation or perturbation.
Strengths & limitations
- Computationally efficient for finding Nash equilibria in finite bimatrix games
- Guarantees convergence to a completely labeled vertex pair for non-degenerate games
- Provides theoretical foundation connecting combinatorial geometry to game theory
- Applicable to mixed strategy equilibria, which are often more realistic than pure strategy outcomes
- Limited to bimatrix (two-player) games; extension to n-player games is NP-hard
- Fails or becomes inefficient on degenerate games where multiple entering pivots are possible
- May find only one equilibrium; multiple equilibria often exist in non-zero-sum games
- Does not directly handle dynamic or extensive-form games without reformulation
Frequently asked
Can a game have no Nash Equilibrium?
Pure-strategy Nash Equilibria may not exist (e.g., Rock-Paper-Scissors), but every finite game has at least one mixed-strategy equilibrium where players randomize over actions with specific probabilities.
How is a mixed-strategy equilibrium different from a pure-strategy equilibrium?
In a pure-strategy equilibrium, each player commits to a specific action with certainty. In a mixed-strategy equilibrium, each player uses a probability distribution over actions. Mixed equilibria are often more general and exist when pure ones do not.
Why is the Lemke-Howson algorithm preferred over brute-force search?
The algorithm exploits the polytope structure of strategy spaces, reducing the search space exponentially and achieving convergence in polynomial time for non-degenerate games, whereas brute-force enumeration becomes infeasible as strategy space grows.
Sources
- Nash, J. F. (1950). Equilibrium points in N-person games. Proceedings of the National Academy of Sciences, 36(1), 48-49. DOI: 10.1073/pnas.36.1.48 ↗
- Lemke, C. E., & Howson Jr, J. T. (1964). Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics, 12(2), 413-423. DOI: 10.1137/0112033 ↗
How to cite this page
ScholarGate. (2026, June 3). Nash Equilibrium (Lemke-Howson Algorithm). ScholarGate. https://scholargate.app/en/game-theory/nash-equilibrium
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Bayesian Nash EquilibriumGame Theory↔ compare
- Shapley ValueGame Theory↔ compare
- Subgame Perfect EquilibriumGame Theory↔ compare
- VCG MechanismGame Theory↔ compare