Epsilon-equilibrium

Epsilon-equilibrium
A solution concept in game theory
Relationships
Superset of	Nash Equilibrium
Significance
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. 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.^[1]

Definition

There is more than one alternative definition.

The standard definition

Given a game and a real non-negative parameter $\varepsilon$ , a strategy profile is said to be an $\varepsilon$ -equilibrium if it is not possible for any player to gain more than $\varepsilon$ in expected payoff by unilaterally deviating from his strategy.^[2]^:45 Every Nash Equilibrium is equivalent to an $\varepsilon$ -equilibrium where $\varepsilon = 0$ .

Formally, let $G = (N, A=A_1 \times \dotsb \times A_N, u\colon A \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 $\Delta_i$ be the space of probability distributions over $A_i$ . A vector of strategies $\sigma \in \Delta = \Delta_1 \times \dotsb \times \Delta_N$ is an $\varepsilon$ -Nash Equilibrium for $G$ if

u_i(\sigma)\geq u_i(\sigma_i^',\sigma_{-i})-\varepsilon

for all

\sigma_i^' \in \Delta_i, i \in N.

Well-supported approximate equilibrium

The following definition^[3] 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 $\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\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

\sum_{s\in S_{-p}}u_p(js)x_s > \varepsilon+\sum_{s\in S_{-p}}u_p(j's)x_s \Longrightarrow x^p_{j'} = 0.

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,^[4] 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^[5] For games with payoffs in the range [0,1] and ε=2/3, ε-well-supported equilibria can be computed in polynomial time^[6]

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

References

↑ V. Bubelis (1979). "On equilibria in finite games". International Journal on Game Theory 8 (2): 65–79. doi:10.1007/bf01768703.
↑ Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.
↑ P.W. Goldberg and C.H. Papadimitriou (2006). "Reducibility Among Equilibrium Problems". 38th Symposium on Theory of Computing. pp. 61–70. doi:10.1145/1132516.1132526.
↑ C. Daskalakis, P.W. Goldberg and C.H. Papadimitriou (2009). "The Complexity of Computing a Nash Equilibrium". SIAM Journal on Computing 39 (3): 195–259. doi:10.1137/070699652.
↑ H. Tsaknakis and Paul G. Spirakis (2008). "An optimisation approach for approximate Nash equilibria". Internet Mathematics 5 (4): 365–382. doi:10.1080/15427951.2008.10129172.
↑ Spyros C. Kontogiannis and Paul G. Spirakis (2010). "Well Supported Approximate Equilibria in Bimatrix Games". Algorithmica 57 (4): 653–667. doi:10.1007/s00453-008-9227-6.

H Dixon 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.
Leyton-Brown, Kevin; Shoham, Yoav (2008), Essentials of Game Theory: A Concise, Multidisciplinary Introduction, San Rafael, CA: Morgan & Claypool Publishers, ISBN 978-1-59829-593-1 . An 88-page mathematical introduction; see Section 3.7. Free online 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.
Shoham, Yoav; Leyton-Brown, Kevin (2009), Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, New York: Cambridge University Press, ISBN 978-0-521-89943-7 . 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.

Topics in game theory

Definitions	Normal-form game Extensive-form game Escalation of commitment Graphical game Cooperative game Succinct game Information set Hierarchy of beliefs Preference

Equilibrium concepts	Nash equilibrium Subgame perfection Mertens-stable equilibrium Bayesian-Nash Perfect Bayesian Trembling hand Proper equilibrium Epsilon-equilibrium Correlated equilibrium Sequential equilibrium Quasi-perfect equilibrium Evolutionarily stable strategy Risk dominance Core Shapley value Pareto efficiency Quantal response equilibrium Self-confirming equilibrium Strong Nash equilibrium Markov perfect equilibrium

Strategies	Dominant strategies Pure strategy Mixed strategy Tit for tat Grim trigger Collusion Backward induction Forward induction Markov strategy

Classes of games	Symmetric game Perfect information Simultaneous game Sequential game Repeated game Signaling game Cheap talk Zero-sum game Mechanism design Bargaining problem Stochastic game n-player game Large Poisson game Nontransitive game Global games Strictly determined game

Games	Prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Rock-paper-scissors Pirate game Dictator game Public goods game Blotto games War of attrition El Farol Bar problem Fair division Fair cake-cutting Cournot game Deadlock Diner's dilemma Guess 2/3 of the average Kuhn poker Nash bargaining game Screening game Prisoners and hats puzzle Trust game Princess and monster game Monty Hall problem Rendezvous problem

Theorems	Minimax theorem Nash's theorem Purification theorem Folk theorem Revelation principle Arrow's impossibility theorem

Key figures	Albert W. Tucker Amos Tversky Ariel Rubinstein Daniel Kahneman David K. Levine David M. Kreps Donald B. Gillies Drew Fudenberg Eric Maskin Harold W. Kuhn Herbert Simon Hervé Moulin Jean Tirole Jean-François Mertens John Harsanyi John Maynard Smith John Nash John von Neumann Kenneth Arrow Kenneth Binmore Leonid Hurwicz Lloyd Shapley Melvin Dresher Merrill M. Flood Oskar Morgenstern Paul Milgrom Peyton Young Reinhard Selten Robert Aumann Robert B. Wilson Roger Myerson Samuel Bowles Thomas Schelling William Vickrey

See also	All-pay auction Alpha–beta pruning Bertrand paradox Bounded rationality Combinatorial game theory Confrontation analysis Coopetition List of game theorists List of games in game theory No-win situation Tragedy of the commons Tyranny of small decisions

This article is issued from Wikipedia - version of the Tuesday, February 16, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.