 Epsilonequilibrium

Epsilonequilibrium A solution concept in game theory Relationships Superset of Nash Equilibrium Significance Used for stochastic games In game theory, an epsilonequilibrium, or nearNash equilibrium, is a strategy profile that approximately satisfies the condition of Nash equilibrium.
Definition
Given a game and a real nonnegative parameter ε, a strategy profile is said to be an εequilibrium if it is not possible for any player to gain more than ε in expected payoff by unilaterally deviating from his strategy. Every Nash Equilibrium is equivalent to a εequilibrium where ε = 0.
Formally, let be a Nplayer game with action sets A_{i} for each player and utility function u. A vector of strategies is an Nash Equilibrium for G if
 for all
Example
The notion of εequilibria is important in the theory of stochastic games of potentially infinite duration. There are simple examples of stochastic games with no Nash equilibrium but with an εequilibrium for any ε strictly bigger than 0.
Perhaps the simplest such example is the following variant of Matching Pennies, suggested by Everett. Player 1 hides a penny and Player 2 must guess if it is heads up or tails up. If Player 2 guesses correctly, he wins the penny from Player 1 and the game ends. If Player 2 incorrectly guesses that the penny is heads up, the game ends with payoff zero to both players. If he incorrectly guesses that it is tails up, the game repeats. If the play continues forever, the payoff to both players is zero.
Given a parameter ε > 0, any strategy profile where Player 2 guesses heads up with probability ε and tails up with probability 1ε (at every stage of the game, and independently from previous stages) is an εequilibrium for the game. The expected payoff of Player 2 in such a strategy profile is at least 1ε. However, it is easy to see that there is no strategy for Player 2 that can guarantee an expected payoff of exactly 1. Therefore, the game has no Nash equilibrium.
Another simple example is the finitely repeated prisoner's dilemma for T periods, where the payoff is averaged over the T periods. The only Nash equilibrium of this game is to choose Defect in each period. Now consider the two strategies titfortat and grim trigger. Although neither titfortat nor grim trigger are Nash equilibria for the game, both of them are equilibria for some positive . The acceptable values of depend on the payoffs of the consituent game and on the number T of periods.
References
 H. Everett. "Recursive Games". In H.W. Kuhn and A.W. Tucker, editors. Contributions to the theory of games, vol. III, volume 39 of Annals of Mathematical Studies. Princeton University Press, 1957.
 LeytonBrown, Kevin; Shoham, Yoav (2008), Essentials of Game Theory: A Concise, Multidisciplinary Introduction, San Rafael, CA: Morgan & Claypool Publishers, ISBN 9781598295931, http://www.gtessentials.org. An 88page mathematical introduction; see Section 3.7. Free online at many universities.
 R. Radner. Collusive behavior in noncooperative epsilon equilibria of oligopolies with long but finite lives, Journal of Economic Theory, 22, 121157, 1980.
 Shoham, Yoav; LeytonBrown, Kevin (2009), Multiagent Systems: Algorithmic, GameTheoretic, and Logical Foundations, New York: Cambridge University Press, ISBN 9780521899437, http://www.masfoundations.org. A comprehensive reference from a computational perspective; see Section 3.4.7. Downloadable free online.
 S.H. Tijs. Nash equilibria for noncooperative nperson games in normal form, Siam Review, 23, 225237, 1981.
Categories:
Wikimedia Foundation. 2010.