A solution concept in game theory
Superset of Nash Equilibrium
Used for stochastic games

In game theory, an epsilon-equilibrium, or near-Nash equilibrium, is a strategy profile that approximately satisfies the condition of Nash equilibrium.


Given a game and a real non-negative 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 G=(N,A=A_1\times\cdots\times A_N, u: A \rightarrow \reals^N) be a N-player game with action sets Ai for each player and utility function u. A vector of strategies \sigma \in \Delta = \Delta_1 \times \cdots \times \Delta_N is an \epsilon-Nash Equilibrium for G if

u_i(\sigma)\geq u_i(\sigma_i^',\sigma_{-i})-\epsilon for all \ \sigma_i^' \in \Delta_i, i \in N


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 \epsilon-equilibria for some positive \epsilon. The acceptable values of \epsilon depend on the payoffs of the consituent game and on the number T of periods.


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Nash equilibrium — A solution concept in game theory Relationships Subset of Rationalizability, Epsilon equilibrium, Correlated equilibrium Superset of Evolutionarily stable strategy …   Wikipedia

  • Correlated equilibrium — A solution concept in game theory Relationships Superset of Nash equilibrium Significance Proposed by …   Wikipedia

  • Manipulated Nash equilibrium — MAPNASH A solution concept in game theory Relationships Subset of Nash equilibrium, Subgame perfect equilibrium Significance …   Wikipedia

  • Markov perfect equilibrium — A solution concept in game theory Relationships Subset of Subgame perfect equilibrium Significance Proposed by …   Wikipedia

  • Coalition-proof Nash equilibrium — The concept of coalition proof Nash equilibrium applies to certain noncooperative environments in which players can freely discuss their strategies but cannot make binding commitments [1]. It emphasizes the immunization to deviations that are… …   Wikipedia

  • Determination of equilibrium constants — Equilibrium constants are determined in order to quantify chemical equilibria. When an equilibrium constant is expressed as a concentration quotient, it is implied that the activity quotient is constant. In order for this assumption to be valid… …   Wikipedia

  • Trembling hand perfect equilibrium — Infobox equilibrium name=(Normal form) trembling hand perfect equilibrium subsetof=Nash Equilibrium supersetof=Proper equilibrium discoverer=Reinhard Selten: This article is about games. For the cocktail, see Perfect Equilibrium (Cocktail)… …   Wikipedia

  • Proper equilibrium — Infobox equilibrium name=Proper equilibrium subsetof=Trembling hand perfect equilibrium discoverer=Roger B. MyersonProper equilibrium is a refinement of Nash Equilibrium due to Roger B. Myerson. Proper equilibrium further refines Reinhard Selten… …   Wikipedia

  • Cooperative game — This article is about a part of game theory. For video gaming, see Cooperative gameplay. For the similar feature in some board games, see cooperative board game In game theory, a cooperative game is a game where groups of players ( coalitions )… …   Wikipedia

  • Stackelberg competition — The Stackelberg leadership model is a strategic game in economics in which the leader firm moves first and then the follower firms move sequentially. It is named after the German economist Heinrich Freiherr von Stackelberg who published Market… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”