Epsilon-equilibrium

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

Formally, let ${\displaystyle G=(N,A=A_{1}\times \dotsb \times A_{N},u\colon A\to R^{N})}$ be an ${\displaystyle N}$-player game with action sets ${\displaystyle A_{i}}$ for each player ${\displaystyle i}$ and utility function ${\displaystyle u}$. Let ${\displaystyle u_{i}(s)}$ denote the payoff to player ${\displaystyle i}$ when strategy profile ${\displaystyle s}$ is played. Let ${\displaystyle \Delta _{i}}$ be the space of probability distributions over ${\displaystyle A_{i}}$. A vector of strategies ${\displaystyle \sigma \in \Delta =\Delta _{1}\times \dotsb \times \Delta _{N}}$ is an ${\displaystyle \varepsilon }$-Nash Equilibrium for ${\displaystyle G}$ if

${\displaystyle u_{i}(\sigma )\geq u_{i}(\sigma _{i}^{'},\sigma _{-i})-\varepsilon }$ for all ${\displaystyle \sigma _{i}^{'}\in \Delta _{i},i\in N.}$

The following definition[3] imposes the stronger requirement that a player may only assign positive probability to a pure strategy ${\displaystyle a}$ if the payoff of ${\displaystyle a}$ has expected payoff at most ${\displaystyle \varepsilon }$ less than the best response payoff. Let ${\displaystyle x_{s}}$ be the probability that strategy profile ${\displaystyle s}$ is played. For player ${\displaystyle p}$ let ${\displaystyle S_{-p}}$ be strategy profiles of players other than ${\displaystyle p}$; for ${\displaystyle s\in S_{-p}}$ and a pure strategy ${\displaystyle j}$ of ${\displaystyle p}$ let ${\displaystyle js}$ be the strategy profile where ${\displaystyle p}$ plays ${\displaystyle j}$ and other players play ${\displaystyle s}$. Let ${\displaystyle u_{p}(s)}$ be the payoff to ${\displaystyle p}$ when strategy profile ${\displaystyle s}$ is used. The requirement can be expressed by the formula

${\displaystyle \sum _{s\in S_{-p}}u_{p}(js)x_{s}>\varepsilon +\sum _{s\in S_{-p}}u_{p}(j's)x_{s}\Longrightarrow x_{j'}^{p}=0.}$