Nash equilibrium
In plain wordsA stable standoff in a game: each player's choice is already their best answer to what the others are doing, so nobody gains by changing course alone — though the result need not be good for anyone.
A profile of strategies, one per player, in which each player's strategy is a best response to the others', so that no one gains by deviating alone. Every finite game has at least one Nash equilibrium if players may randomize (mixed strategies), but a game may have many, and equilibria can be collectively bad: in the prisoner's dilemma, mutual defection is the unique equilibrium although both players would prefer mutual cooperation. Computing a Nash equilibrium is hard in general (PPAD-complete), whereas two-player zero-sum games are solvable by linear programming. In AI, equilibrium concepts guide multi-agent reinforcement learningmulti-agent reinforcement learning, n.: Reinforcement learning with several AI agents learning at once in a shared world, where each must adapt to the others — as teammates, rivals or both. and self-playself-play, n.: Training an AI by having it play against copies of itself, so it always has an opponent at its own level and can keep improving without human examples.; the poker program Libratus approximated a Nash equilibrium of two-player no-limit poker with counterfactual regretregret, n.: How much worse a learner did than it could have done had it known the best choice from the start — the price of having to learn by trying. minimization, and Pluribus extended such methods to six players, where equilibrium guarantees no longer hold; GANgenerative adversarial network, n.: Two neural networks trained as rivals: one forges fake images, the other tries to spot the fakes. As both improve, the forger's output becomes realistic enough to fool people. training seeks an equilibrium between generator and discriminator; and governance analyses use equilibrium reasoning about racing and cooperation among AI developers.
Both labs racing is a Nash equilibrium even though both would prefer a coordinated slowdown.
Origin
Defined by John Nash in 'Equilibrium Points in n-Person Games' (Proceedings of the National Academy of Sciences, 1950) and 'Non-Cooperative Games' (Annals of Mathematics, 1951), generalizing Antoine Augustin Cournot's 1838 duopoly equilibrium and von Neumann's minimax solution. Nash shared the 1994 Nobel Memorial Prize in Economic Sciences for this work.
Related
- game theorygame theory, n.: The mathematics of strategic decisions, where each player's best move depends on what the others do. It is used to study competition and cooperation among people, firms, nations and AI agents.
- self-playself-play, n.: Training an AI by having it play against copies of itself, so it always has an opponent at its own level and can keep improving without human examples.
- multi-agent reinforcement learningmulti-agent reinforcement learning, n.: Reinforcement learning with several AI agents learning at once in a shared world, where each must adapt to the others — as teammates, rivals or both.
- generative adversarial networkgenerative adversarial network, n.: Two neural networks trained as rivals: one forges fake images, the other tries to spot the fakes. As both improve, the forger's output becomes realistic enough to fool people.
- minimaxminimax, n.: A way for a game-playing program to choose moves by assuming the opponent will always make their best reply, and picking the move whose worst-case outcome is best.
- regretregret, n.: How much worse a learner did than it could have done had it known the best choice from the start — the price of having to learn by trying.
Sources
- Nash, J. F. (1950). Equilibrium Points in n-Person Games. Proceedings of the National Academy of Sciences, 36(1).
Mentioned in
game theorygame theory, n.: The mathematics of strategic decisions, where each player's best move depends on what the others do. It is used to study competition and cooperation among people, firms, nations and AI agents., LibratusLibratus, prop. n.: A poker-playing AI from Carnegie Mellon University that in 2017 decisively beat four top professionals at two-player no-limit Texas hold'em. Its successor, Pluribus, beat professionals at six-player poker in 2019.