Epsilon-equilibrium
In game theory, an epsilon-equilibrium, or near-Nash equilibrium, is a strategy profile that approximately satisfies the condition of Nash equilibrium. In a Nash equilibrium, no player has an incentive to change his behavior. In an approximate Nash equilibrium, this requirement is weakened to allow the possibility that a player may have a small incentive to do something different. This may still be considered an adequate solution concept, assuming for example status quo bias. This solution concept may be preferred to Nash equilibrium due to being easier to compute, or alternatively due to the possibility that in  games of more than 2 players, the probabilities involved in an exact Nash equilibrium need not be rational numbers. Definition. There is more than one alternative definition. The standard definition. Given a game and a real non-negative parameter formula_1, a strategy profile is said to be an formula_1-equilibrium if it is not possible for any player to gain more than formula_1 in expected payoff by unilaterally deviating from his strategy. Every Nash Equilibrium is equivalent to an formula_1-equilibrium where formula_5. Formally, let formula_6 be an formula_7-player game with action sets formula_8 for each player formula_9 and  utility function formula_10. Let formula_11 denote the payoff to player formula_9 when strategy profile formula_13 is played. Let formula_14 be the space of probability distributions over formula_8. A vector of strategies formula_16 is an formula_1-Nash Equilibrium for formula_18 if Well-supported approximate equilibrium. The following definition imposes the stronger requirement that a player may only assign positive probability to a pure strategy formula_21 if the payoff of formula_21 has expected payoff at most formula_1 less than the best response payoff. Let formula_24 be the probability that strategy profile formula_13 is played. For player formula_26 let formula_27 be strategy profiles  of players other than formula_26; for formula_29 and a pure strategy formula_30 of formula_26 let formula_32 be the strategy profile where formula_26 plays formula_30 and other players play formula_13. Let formula_36 be the payoff to formula_26 when strategy profile formula_13 is used. The requirement can be expressed by the formula Results. The existence of a polynomial-time approximation scheme (PTAS) for ε-Nash equilibria is equivalent to the question of whether there exists one for ε-well-supported approximate Nash equilibria, but the existence of a PTAS remains an open problem. For constant values of ε, polynomial-time algorithms for  approximate equilibria are known for lower values of ε than are known for well-supported approximate equilibria. For games with payoffs in the range [0,1] and ε=0.3393, ε-Nash equilibria can be computed in polynomial time For games with payoffs in the range [0,1] and ε=2/3, ε-well-supported equilibria can be computed in polynomial time 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 tit-for-tat and grim trigger. Although neither tit-for-tat nor grim trigger are Nash equilibria for the game, both of them are formula_40-equilibria for some positive formula_40. The acceptable values of formula_40 depend on the payoffs of the constituent game and on the number T of periods. In economics, the concept of a pure strategy epsilon-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 the Bertrand–Edgeworth model, where no pure-strategy equilibrium exists, a pure-strategy epsilon equilibrium may exist.