is_approx_nash_equilibrium
A strategy profile x : (j : Fin n) → stdSimplex ℝ (A j) in an n-player normal-form game with payoff function u : Fin n → ((j : Fin n) → A j) → ℝ is an ε-approximate Nash equilibrium if for every player i : Fin n and every pure action a : A i, the expected payoff under Function.update x i (stdSimplex.pure a) minus the expected payoff under x is at most ε.
Statement
def is_approx_nash_equilibrium {n : ℕ} {A : Fin n → Type} [∀ i, Fintype (A i)] [∀ i, DecidableEq (A i)] (u : Fin n → ((i : Fin n) → A i) → ℝ) (ε : ℝ) (x : (j : Fin n) → stdSimplex ℝ (A j)) : Prop
- Defined in
- arXiv:2611.06076 Section 2
- Verified
- 05 Nov 2026
- Axioms
- none listed
- Built on 2
- normal_form_expected_payoffIn an n-player normal-form game with action types A : Fin n → Type, finite action spaces, and payoff function u : Fin n → ((j : Fin n) → A…
- stdSimplex.purePoint-mass simplex element at
i₀.
- Used by 1
- one_player_extension_approx_nashIn an (r+1)-player normal-form game with payoff functions u : Fin (r + 1) → ((j : Fin (r + 1)) → A j) → ℝ taking values in [0, 1]…
Read back from the Lean
Given a natural number $n$, a family of action types $A : \mathrm{Fin}\ n \to \mathrm{Type}$ with Fintype and DecidableEq instances for each $A(i)$, a payoff function $u : \mathrm{Fin}\ n \to ((i : \mathrm{Fin}\ n) \to A\ i) \to \mathbb{R}$, a real number $\varepsilon : \mathbb{R}$, and a mixed strategy profile $x : (j : \mathrm{Fin}\ n) \to \mathrm{stdSimplex}\ \mathbb{R}\ (A\ j)$, the predicate is_approx_nash_equilibrium u ε x asserts that:
for every player $i : \mathrm{Fin}\ n$ and every pure action $a : A\ i$, the expected payoff to player $i$ under the strategy profile where player $i$'s mixed strategy in $x$ is replaced by the pure strategy stdSimplex.pure a (with all other players playing according to $x$) minus player $i$'s expected payoff under $x$ is less than or equal to $\varepsilon$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- An ε-approximate Nash equilibrium has regret at most ε for every player. -/ def is_approx_nash_equilibrium {n : ℕ} {A : Fin n → Type} [∀ i, Fintype (A i)] [∀ i, DecidableEq (A i)] (u : Fin n → ((i : Fin n) → A i) → ℝ) (ε : ℝ) (x : (j : Fin n) → stdSimplex ℝ (A j)) : Prop := ∀ (i : Fin n) (a : A i), normal_form_expected_payoff u i (Function.update x i (stdSimplex.pure a)) - normal_form_expected_payoff u i x ≤ ε