Epsilon-equilibrium

There is more than one alternative definition.

Given a game and a real non-negative parameter $\backslash varepsilon$, a strategy profile is said to be an

$\backslash varepsilon$-equilibrium if it is not possible for any player to gain more than $\backslash varepsilon$ in expected payoff by unilaterally deviating from his strategy.{{Cite Algorithmic Game Theory 2007}}{{rp|45}}

Every Nash Equilibrium is equivalent to an $\backslash varepsilon$-equilibrium where $\backslash varepsilon\; =\; 0$.

Formally, let $G\; =\; (N,\; A=A\_1\; \backslash times\; \backslash dotsb\; \backslash times\; A\_N,\; u\backslash colon\; A\; \backslash to\; R^N)$

be an $N$-player game with action sets $A\_i$ for each player $i$ and utility function $u$.

Let $u\_i\; (s)$ denote the payoff to player $i$ when strategy profile $s$ is played.

Let $\backslash Delta\_i$ be the space of probability distributions over $A\_i$.

A vector of strategies $\backslash sigma\; \backslash in\; \backslash Delta\; =\; \backslash Delta\_1\; \backslash times\; \backslash dotsb\; \backslash times\; \backslash Delta\_N$ is an $\backslash varepsilon$-Nash Equilibrium for $G$ if

:$u\_i(\backslash sigma)\backslash geq\; u\_i(\backslash sigma\_i^\text{'},\backslash sigma\_\{-i\})-\backslash varepsilon$ for all $\backslash sigma\_i^\text{'}\; \backslash in\; \backslash Delta\_i,\; i\; \backslash in\; N.$

The following definition{{cite conference

| doi = 10.1145/1132516.1132526

| author = P.W. Goldberg and C.H. Papadimitriou

| year = 2006

| title = Reducibility Among Equilibrium Problems

| book-title = 38th Symposium on Theory of Computing

| pages = 61–70

}}

imposes the stronger requirement that a player may only assign positive probability to a pure strategy $a$ if the payoff of $a$ has expected payoff at most $\backslash varepsilon$ less than the best response payoff.

Let $x\_s$ be the probability that strategy profile $s$ is played. For player $p$ let $S\_\{-p\}$ be strategy profiles of players other than $p$; for $s\backslash in\; S\_\{-p\}$ and a pure strategy $j$ of $p$ let $js$ be the strategy profile where $p$ plays $j$ and other players play $s$.

Let $u\_p(s)$ be the payoff to $p$ when strategy profile $s$ is used.

The requirement can be expressed by the formula

:$\backslash sum\_\{s\backslash in\; S\_\{-p\}\}u\_p(js)x\_s\; >\; \backslash varepsilon+\backslash sum\_\{s\backslash in\; S\_\{-p\}\}u\_p(j\text{'}s)x\_s\; \backslash Longrightarrow\; x^p\_\{j\text{'}\}\; =\; 0.$

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,{{cite journal

| doi = 10.1137/070699652

| author = C. Daskalakis, P.W. Goldberg and C.H. Papadimitriou

| year = 2009

| title = The Complexity of Computing a Nash Equilibrium

| journal = SIAM Journal on Computing

| volume = 39

| issue = 3

| pages = 195–259

| citeseerx = 10.1.1.68.6111

}} 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.{{cite journal

| author = H. Tsaknakis and Paul G. Spirakis

| year = 2008

| title = An optimisation approach for approximate Nash equilibria

| journal = Internet Mathematics

| volume = 5

| issue = 4

| pages = 365–382

| doi=10.1080/15427951.2008.10129172

| doi-access = free

}}

For games with payoffs in the range [0,1] and ε=2/3, ε-well-supported equilibria can

be computed in polynomial time.{{cite journal

| doi = 10.1007/s00453-008-9227-6

| author = Spyros C. Kontogiannis and Paul G. Spirakis

| year = 2010

| title = Well Supported Approximate Equilibria in Bimatrix Games

| journal = Algorithmica

| volume = 57

| issue = 4

| pages = 653–667

| s2cid = 15968419

}}

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 $\backslash epsilon$-equilibria for some positive $\backslash epsilon$. The acceptable values of $\backslash epsilon$ 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.

;Inline citations

{{Reflist}}

;Sources

• H Dixon [https://ideas.repec.org/a/bla/restud/v54y1987i1p47-62.html 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.
• {{Citation | last2=Shoham | first2=Yoav | last1=Leyton-Brown | first1=Kevin | authorlink1 = Kevin Leyton-Brown | title=Essentials of Game Theory: A Concise, Multidisciplinary Introduction | publisher=Morgan & Claypool Publishers | isbn=978-1-59829-593-1 | url=http://www.gtessentials.org | year=2008 | location=San Rafael, CA}}. An 88-page mathematical introduction; see Section 3.7. [http://www.morganclaypool.com/doi/abs/10.2200/S00108ED1V01Y200802AIM003 Free online] {{Webarchive|url=https://web.archive.org/web/20000815223335/http://www.economics.harvard.edu/~aroth/alroth.html |date=2000-08-15 }} 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.
• {{Citation | last1=Shoham | first1=Yoav | last2=Leyton-Brown | first2=Kevin | title=Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations | publisher=Cambridge University Press | isbn=978-0-521-89943-7 | url=http://www.masfoundations.org | year=2009 | location=New York}}. A comprehensive reference from a computational perspective; see Section 3.4.7. [http://www.masfoundations.org/download.html Downloadable free online].
• S.H. Tijs. Nash equilibria for noncooperative n-person games in normal form, SIAM Review, 23, 225–237, 1981.

{{Game theory}}

{{DEFAULTSORT:Epsilon-Equilibrium}}

Category:Game theory equilibrium concepts