Lemke–Howson algorithm
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.
PseudoCode
Applications
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.