Epsilon-equilibrium
a situation where players have only a small incentive to change strategies
≈ 2 min read
Names in other languages
- EnglishEpsilon-equilibrium
- עבריתשיווי משקל אפסילון
- РусскийЭпсилон-равновесие
- 中文ε-均衡
- 简体中文ε-均衡
- 繁體中文ε-均衡
- 中文ε-均衡
- 中文ε-均衡
- 中文ε-均衡
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.
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. Note that the utilities of all players are normalized to [0,1], so this is actually a multiplicative approximation: the gain cannot be more than \varepsilon times the highest utility. \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. For games with payoffs in the range [0,1] and ε=0.3393, ε-Nash equilibria can be computed in polynomial time.
For games with payoffs in the range [0,1] and ε=2/3, ε-well-supported equilibria can be computed in polynomial time.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1356441337 under CC BY-SA 4.0; modifications have been made.