Nash Equilibrium
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.
Key highlights
- 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
Intuition
This section is available to Pro members. Upgrade to Pro
How it works
This section is available to Pro members. Upgrade to Pro
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
Common pitfalls
This section is available to Pro members. Upgrade to Pro
Applications
This section is available to Pro members. Upgrade to Pro
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
- 1.Nash, J. F. (1950). Equilibrium points in N-person games. Proceedings of the National Academy of Sciences, 36(1), 48-49.
- 2.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.
You have read it. What now?
Cite this page
ScholarGate. (2026, June 3). Nash Equilibrium. ScholarGate. https://scholargate.app/game-theory/nash-equilibrium