Ingame theory, anepsilon-equilibrium, or near-Nash equilibrium, is astrategy profile that approximatelysatisfies the condition ofNash equilibrium. In a Nash equilibrium, no player has an incentive to change hisbehavior. In an approximate Nash equilibrium, this requirement is weakened to allow the possibility that aplayer may have a small incentive to do something different. This may still be considered an adequatesolution concept, assuming for examplestatus quo bias. This solution concept may be preferred to Nashequilibrium due to being easier to compute, or alternatively due to the possibility that in games of morethan 2 players, the probabilities involved in an exact Nash equilibrium need not berational numbers.^[1]

There is more than one alternative definition.

Given a game and a real non-negative parameter${\displaystyle \epsilon }$, astrategy profile is said to be an${\displaystyle \epsilon }$-equilibrium if it is not possible for any player to gain more than${\displaystyle \epsilon }$ inexpected payoff by unilaterally deviating from hisstrategy.^[2]: 45 EveryNash Equilibrium is equivalent to an${\displaystyle \epsilon }$-equilibrium where${\displaystyle \epsilon =0}$.

Formally, let${\displaystyle G=(N,A=A_1\times \cdots \times A_N,u:A\to R^N)}$be an${\displaystyle N}$-player game with action sets${\displaystyle A_i}$ for each player${\displaystyle i}$ and utility function${\displaystyle u}$.Let${\displaystyle u_i(s)}$ denote the payoff to player${\displaystyle i}$ whenstrategy profile${\displaystyle s}$ is played.Let${\displaystyle {\mathrm{\Delta }}_i}$ be the space of probability distributions over${\displaystyle A_i}$.A vector of strategies${\displaystyle \sigma \in \mathrm{\Delta }={\mathrm{\Delta }}_1\times \cdots \times {\mathrm{\Delta }}_N}$ is an${\displaystyle \epsilon }$-Nash Equilibrium for${\displaystyle G}$ if

${\displaystyle u_i(\sigma )\ge u_i({\sigma }_i^{{}^{\prime }},{\sigma }_{-i})-\epsilon }$ for all${\displaystyle {\sigma }_i^{{}^{\prime }}\in {\mathrm{\Delta }}_i,i\in N.}$

Note that the utilities of all players are normalized to [0,1],^[3] so this is actually amultiplicative approximation: the gain cannot be more than${\displaystyle \epsilon }$ times the highest utility.

The following definition^[4]imposes the stronger requirement that a player may only assign positive probability to a pure strategy${\displaystyle a}$ if the payoff of${\displaystyle a}$ has expected payoff at most${\displaystyle \epsilon }$ less than the best response payoff.Let${\displaystyle x_s}$ be the probability that strategy profile${\displaystyle s}$ is played. For player${\displaystyle p}$ let${\displaystyle S_{-p}}$ be strategy profiles of players other than${\displaystyle p}$; for${\displaystyle s\in S_{-p}}$ and a pure strategy${\displaystyle j}$ of${\displaystyle p}$ let${\displaystyle js}$ be the strategy profile where${\displaystyle p}$ plays${\displaystyle j}$ and other players play${\displaystyle s}$.Let${\displaystyle u_p(s)}$ be the payoff to${\displaystyle p}$ when strategy profile${\displaystyle s}$ is used.The requirement can be expressed by the formula

${\displaystyle \sum _{s\in S_{-p}}{u}_p(js)x_s>\epsilon +\sum _{s\in S_{-p}}{u}_p(j^{\prime }s)x_s⟹x_{j^{\prime }}^p=0.}$

The existence of apolynomial-time approximation scheme (PTAS) for ε-Nash equilibria isequivalent to the question of whether there exists one for ε-well-supportedapproximate Nash equilibria,^[5] but the existence of a PTAS remains an open problem.For constant values of ε, polynomial-time algorithms for approximate equilibriaare known for lower values of ε than are known for well-supportedapproximate equilibria.For games with payoffs in the range [0,1] and ε=0.3393, ε-Nash equilibria canbe computed in polynomial time.^[6]For games with payoffs in the range [0,1] and ε=2/3, ε-well-supported equilibria canbe computed in polynomial time.^[7]

The notion of ε-equilibria is important in the theory ofstochastic games of potentially infinite duration. There are simple examples of stochastic games with noNash equilibrium but with an ε-equilibrium for any ε strictly bigger than 0.

Perhaps the simplest such example is the following variant ofMatching Pennies, suggested by Everett. Player 1 hides a penny andPlayer 2 must guess if it is heads up or tails up. If Player 2 guesses correctly, hewins 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 gamerepeats. If the play continues forever, the payoff to both players is zero.

Given a parameterε > 0, anystrategy profile where Player 2 guesses heads up withprobability ε and tails up with probability 1 − ε (at every stage of the game, and independentlyfrom previous stages) is anε-equilibrium for the game. The expected payoff of Player 2 insuch a strategy profile is at least 1 − ε. However, it is easy to see that there is nostrategy for Player 2 that can guarantee an expected payoff of exactly 1. Therefore, the gamehas noNash equilibrium.

Another simple example is the finitelyrepeated prisoner's dilemma for T periods, where the payoff is averaged over the T periods. The onlyNash equilibrium of this game is to choose Defect in each period. Now consider the two strategiestit-for-tat andgrim trigger. Although neithertit-for-tat norgrim trigger are Nash equilibria for the game, both of them are${\displaystyle ϵ}$-equilibria for some positive${\displaystyle ϵ}$. The acceptable values of${\displaystyle ϵ}$ depend on the payoffs of the constituent game and on the number T of periods.

In economics, the concept of apure strategyepsilon-equilibrium is used when the mixed-strategy approach is seen as unrealistic. In a pure-strategy epsilon-equilibrium, each player chooses a pure-strategy that is within epsilon of its best pure-strategy. For example, in theBertrand–Edgeworth model, where no pure-strategy equilibrium exists, a pure-strategy epsilon equilibrium may exist.

• Nash equilibrium computation - discusses the general problem of computing an exact or approximate Nash equilibrium.

Inline citations

Sources

• H DixonApproximate Bertrand Equilibrium in a Replicated Industry, Review of Economic Studies, 54 (1987), pages 47–62.
• H. Everett. "Recursive Games". In H.W. Kuhn and A.W. Tucker, editors.Contributions to the theory of games, vol. III, volume 39 ofAnnals of Mathematical Studies. Princeton University Press, 1957.
• Leyton-Brown, Kevin; Shoham, Yoav (2008),Essentials of Game Theory: A Concise, Multidisciplinary Introduction, San Rafael, CA: Morgan & Claypool Publishers,ISBN 978-1-59829-593-1. An 88-page mathematical introduction; see Section 3.7.Free onlineArchived 2000-08-15 at theWayback Machine at many universities.
• R. Radner.Collusive behavior in non-cooperative epsilon equilibria of oligopolies with long but finite lives, Journal of Economic Theory,22, 121–157, 1980.
• Shoham, Yoav; Leyton-Brown, Kevin (2009),Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, New York:Cambridge University Press,ISBN 978-0-521-89943-7. A comprehensive reference from a computational perspective; see Section 3.4.7.Downloadable free online.
• S.H. Tijs.Nash equilibria for noncooperativen-person games in normal form, SIAM Review,23, 225–237, 1981.

• Game theory equilibrium concepts

• Articles with short description
• Short description is different from Wikidata
• Webarchive template wayback links