In
game theory
Game theory is the study of mathematical models of strategic interactions among rational agents. Myerson, Roger B. (1991). ''Game Theory: Analysis of Conflict,'' Harvard University Press, p.&nbs1 Chapter-preview links, ppvii–xi It has appli ...
, an epsilon-equilibrium, or near-Nash equilibrium, is a
strategy profile
In game theory, a player (game), player's strategy is any of the options which they choose in a setting where the outcome depends ''not only'' on their own actions ''but'' on the actions of others. The discipline mainly concerns the action of a pl ...
that approximately
satisfies the condition of
Nash equilibrium
In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equili ...
. 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
Status quo bias is an emotional bias; a preference for the maintenance of one's current or previous state of affairs, or a preference to not undertake any action to change this current or previous state. The current baseline (or status quo) is take ...
. 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
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all rationa ...
.
Definition
There is more than one alternative definition.
The standard definition
Given a game and a real non-negative parameter
, a
strategy profile
In game theory, a player (game), player's strategy is any of the options which they choose in a setting where the outcome depends ''not only'' on their own actions ''but'' on the actions of others. The discipline mainly concerns the action of a pl ...
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
Strategy (from Greek στρατηγία ''stratēgia'', "art of troop leader; office of general, command, generalship") is a general plan to achieve one or more long-term or overall goals under conditions of uncertainty. In the sense of the "art ...
.
Every
Nash Equilibrium
In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equili ...
is equivalent to an
-equilibrium where
.
Formally, let
be an
-player game with action sets
for each player
and utility function
.
Let
denote the payoff to player
when
strategy profile
In game theory, a player (game), player's strategy is any of the options which they choose in a setting where the outcome depends ''not only'' on their own actions ''but'' on the actions of others. The discipline mainly concerns the action of a pl ...
is played.
Let
be the space of probability distributions over
.
A vector of strategies
is an
-Nash Equilibrium for
if
:
for all
Well-supported approximate equilibrium
The following definition
imposes the stronger requirement that a player may only assign positive probability to a pure strategy
if the payoff of
has expected payoff at most
less than the best response payoff.
Let
be the probability that strategy profile
is played. For player
let
be strategy profiles of players other than
; for
and a pure strategy
of
let
be the strategy profile where
plays
and other players play
.
Let
be the payoff to
when strategy profile
is used.
The requirement can be expressed by the formula
:
Results
The existence of a
polynomial-time approximation scheme
In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems).
A PTAS is an algorithm which takes an insta ...
(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
,1and ε=0.3393, ε-Nash equilibria can
be computed in polynomial time
For games with payoffs in the range
,1and ε=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
In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equili ...
but with an ε-equilibrium for any ε strictly bigger than 0.
Perhaps the simplest such example is the following variant of
Matching Pennies
Matching pennies is the name for a simple game used in game theory. It is played between two players, Even and Odd. Each player has a penny and must secretly turn the penny to heads or tails. The players then reveal their choices simultaneously ...
, 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
In game theory, a player (game), player's strategy is any of the options which they choose in a setting where the outcome depends ''not only'' on their own actions ''but'' on the actions of others. The discipline mainly concerns the action of a pl ...
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
In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equili ...
.
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
In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equili ...
of this game is to choose Defect in each period. Now consider the two strategies
tit-for-tat
Tit for tat is an English saying meaning "equivalent retaliation". It developed from "tip for tap", first recorded in 1558.
It is also a highly effective strategy in game theory. An agent using this strategy will first cooperate, then subseque ...
and
grim trigger
In game theory, grim trigger (also called the grim strategy or just grim) is a trigger strategy for a repeated game.
Initially, a player using grim trigger will cooperate, but as soon as the opponent defects (thus satisfying the trigger condition) ...
. Although neither
tit-for-tat
Tit for tat is an English saying meaning "equivalent retaliation". It developed from "tip for tap", first recorded in 1558.
It is also a highly effective strategy in game theory. An agent using this strategy will first cooperate, then subseque ...
nor
grim trigger
In game theory, grim trigger (also called the grim strategy or just grim) is a trigger strategy for a repeated game.
Initially, a player using grim trigger will cooperate, but as soon as the opponent defects (thus satisfying the trigger condition) ...
are Nash equilibria for the game, both of them are
-equilibria for some positive
. The acceptable values of
depend on the payoffs of the constituent game and on the number T of periods.
In economics, the concept of a
pure strategy
In game theory, a player's strategy is any of the options which they choose in a setting where the outcome depends ''not only'' on their own actions ''but'' on the actions of others. The discipline mainly concerns the action of a player in a game ...
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
In microeconomics, the Bertrand–Edgeworth model of price-setting oligopoly looks at what happens when there is a homogeneous product (i.e. consumers want to buy from the cheapest seller) where there is a limit to the output of firms which are wi ...
, where no pure-strategy equilibrium exists, a pure-strategy epsilon equilibrium may exist.
References
;Inline citations
;Sources
*
H Dixonbr>
Approximate 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 of ''Annals of Mathematical Studies''. Princeton University Press, 1957.
* . An 88-page mathematical introduction; see Section 3.7
Free onlineat 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.
* . A comprehensive reference from a computational perspective; see Section 3.4.7
Downloadable free online
*S.H. Tijs. ''Nash equilibria for noncooperative ''n''-person games in normal form'', SIAM Review, 23, 225–237, 1981.
{{DEFAULTSORT:Epsilon-Equilibrium
Game theory equilibrium concepts