Epsilon-equilibrium

From Wikipedia, the free encyclopedia

Epsilon-equilibrium
A solution concept in game theory
Relationships
Superset of:	Nash Equilibrium
Significance
Used for:	stochastic games
This box: view • talk • edit

In game theory, an Epsilon-equilibrium is a strategy profile that approximately satisfies the condition of Nash Equilibrium.

[edit] Definition

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 be a N-player 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

[edit] 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 ε-equilibria for . The reason is that a player can gain extra payoff (averaged over the T periods) by defecting in the last round.

[edit] 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.

v • d • e Topics in game theory Definitions Normal form game · Extensive form game · Cooperative game · Information set · Preference Equilibrium concepts Nash equilibrium · Subgame perfection · Bayesian-Nash · Perfect Bayesian · Trembling hand · Proper equilibrium · Epsilon-equilibrium · Correlated equilibrium · Sequential equilibrium · Quasi-perfect equilibrium · Evolutionarily stable strategy · Risk dominance · Pareto efficiency Strategies Dominant strategies · Pure strategy · Mixed strategy · Tit for tat · Grim trigger · Collusion Classes of games Symmetric game · Perfect information · Dynamic game · Repeated game · Signaling game · Cheap talk · Zero-sum game · Mechanism design · Stochastic game · Nontransitive game Games Prisoner's dilemma · Traveler's dilemma · Coordination game · Chicken · Volunteer's dilemma · Dollar auction · Battle of the sexes · Stag hunt · Matching pennies · Ultimatum game · Minority game · Rock-paper-scissors · Pirate game · Dictator game · Public goods game · Bargaining problem · Blotto games  · War of attrition Theorems Minimax theorem · Purification theorems · Folk theorem · Revelation principle · Arrow's theorem