Lemke–Howson algorithm

From Algorithm Wiki
Jump to navigation Jump to search

Algorithm Details

Year : 1964

Family : Nash Equilibria

Authors : C. E. Lemke and J. T. Howson, Jr.

Read More: https://epubs.siam.org/doi/abs/10.1137/0112033?journalCode=smjmap.1&

Paper Link : https://epubs.siam.org/doi/abs/10.1137/0112033?journalCode=smjmap.1

Time Complexity :

Problem Statement

Nash equilibrium is a concept within game theory where the optimal outcome of a game is where there is no incentive to deviate from the initial strategy. More specifically, the Nash equilibrium is a concept of game theory where the optimal outcome of a game is one where no player has an incentive to deviate from their chosen strategy after considering an opponent's choice.

Overall, an individual can receive no incremental benefit from changing actions, assuming other players remain constant in their strategies. A game may have multiple Nash equilibria or none at all.



Nash equilibrium is important because it helps a player determine the best payoff in a situation based not only on their decisions but also on the decisions of other parties involved. Nash equilibrium can be utilized in many facets of life, from business strategies to selling a house to war, and social sciences.


Python : https://github.com/s3rvac/lemke-howson