one_player_extension_approx_nash
In 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] (satisfying ∀ i a, 0 ≤ u i a ∧ u i a ≤ 1), let α be a real number satisfying 0 ≤ α and α ≤ 1. If x is an α-approximate Nash equilibrium of the r-player subgame fixing player Fin.last r to pure action s : A (Fin.last r), and b : A (Fin.last r) is a pure best response of player Fin.last r to x in the full game, then setting θ = 1/(2-α), the product profile Fin.snoc x (stdSimplex.mix θ _ _ (stdSimplex.pure s) (stdSimplex.pure b)) is a θ-approximate Nash equilibrium of the (r+1)-player game.
Statement
theorem one_player_extension_approx_nash {r : ℕ} {A : Fin (r + 1) → Type} [∀ i, Fintype (A i)] [∀ i, DecidableEq (A i)] (u : Fin (r + 1) → ((i : Fin (r + 1)) → A i) → ℝ) (hu : ∀ i a, 0 ≤ u i a ∧ u i a ≤ 1) (s : A (Fin.last r)) (α : ℝ) (hα0 : 0 ≤ α) (hα1 : α ≤ 1) (x : (j : Fin r) → stdSimplex ℝ (A j.castSucc)) (hx : is_approx_nash_equilibrium (normal_form_subgame_last u s) α x) (b : A (Fin.last r)) (hb : is_pure_best_response_last u x b) : let θ : ℝ := 1 / (2 - α) let y : stdSimplex ℝ (A (Fin.last r)) := stdSimplex.mix θ (div_nonneg zero_le_one (by linarith)) ((div_le_iff₀ (by linarith : 0 < 2 - α)).mpr (by linarith)) (stdSimplex.pure s) (stdSimplex.pure b) is_approx_nash_equilibrium u θ (Fin.snoc x y)
- Formalizes
- arXiv:2611.06076 Lemma 2.1 -- Breaking the One-Player Extension Barrier: History-Aware Repair for Multiplayer Approximate Nash Equilibria
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- 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…
- is_approx_nash_equilibriumA 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…
- normal_form_subgame_lastGiven action types A : Fin (r + 1) → Type and payoff function u : Fin (r + 1) → ((j : Fin (r + 1)) → A j) → ℝ for an (r+1)-player game,…
- is_pure_best_response_lastIn an (r+1)-player game with payoff function u : Fin (r + 1) → ((j : Fin (r + 1)) → A j) → ℝ and action types A, pure action b : A…
- one_player_extension_theta_identityFor any real α with 2 - α ≠ 0, setting θ = 1/(2-α) satisfies θα + 1 - θ = θ.
- stdSimplex.purePoint-mass simplex element at
i₀. - stdSimplex.mixConvex combination of two simplex points:
mix α hα₀ hα₁ x y = α·x + (1-α)·y. This is the basic vocabulary for compound lotteries and for… - stdSimplex.mix_applystdSimplex.mix_apply
- stdSimplex.pure_applystdSimplex.pure_apply
Read back from the Lean
Given:
- a natural number $r$,
- an action type family $A : \mathrm{Fin}(r + 1) \to \mathrm{Type}$ such that each $A(i)$ is a finite type with decidable equality,
- a payoff function $u : \mathrm{Fin}(r + 1) \to ((i : \mathrm{Fin}(r + 1)) \to A(i)) \to \mathbb{R}$,
- a hypothesis $hu$ that every player's payoff for every pure action profile lies in $[0, 1]$ (i.e., $\forall i\ a, 0 \le u(i, a) \le 1$),
- an action $s \in A(\mathrm{Fin.last}\ r)$ for the last player,
- a real number $\alpha$ satisfying $0 \le \alpha \le 1$,
- a mixed strategy profile $x : (j : \mathrm{Fin}\ r) \to \mathrm{stdSimplex}\ \mathbb{R}\ (A(j.\mathrm{castSucc}))$ for the first $r$ players,
- a hypothesis $hx$ that $x$ is an $\alpha$-approximate Nash equilibrium in the subgame obtained by fixing the last player's action to $s$ (normal_form_subgame_last u s),
- an action $b \in A(\mathrm{Fin.last}\ r)$ for the last player,
- a hypothesis $hb$ that $b$ is a pure best response for the last player against the strategy profile $x$ (is_pure_best_response_last u x b),
the theorem asserts that:
letting $\theta = \frac{1}{2 - \alpha} \in [0, 1]$ and letting $y \in \mathrm{stdSimplex}\ \mathbb{R}\ (A(\mathrm{Fin.last}\ r))$ be the mixture of pure strategies $s$ and $b$ with weight $\theta$ on $s$ and $1 - \theta$ on $b$ (via stdSimplex.mix),
the extended strategy profile $\mathrm{Fin.snoc}\ x\ y$ (where the first $r$ players play according to $x$ and the last player plays $y$) is a $\theta$-approximate Nash equilibrium for the full game $u$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To extend an α-approximate Nash equilibrium x of an r-player game (with a fixed action s for the (r+1)-th player) to the full game, the last player mixes s with their best response b using weight θ = 1/(2-α). For the last player, the gain from deviating is at most θ since b is already optimal against x and payoffs lie in [0, 1]. For any other player, the deviation gain decomposes by linearity into θ times the subgame deviation gain (at most α) plus (1-θ) times the worst-case payoff difference (at most 1), yielding θ * α + (1-θ) = θ.
The probabilities over all pure action profiles sum to 1.
By distributing products over sums, the sum of products of probabilities across players factorises into the product of each player's probability sum, each of which is 1.
uses
Finset.prod_univ_sum,Fintype.piFinset_univ,Finset.prod_const_one(∑ a : (j : Fin n) → A j, ∏ j : Fin n, (x j).val (a j)) = 1 := by have h := @Finset.prod_univ_sum (Fin n) ℝ _ _ A _ (fun _ => Finset.univ) (fun j a => (x j).val a) classical rw [Fintype.piFinset_univ] at h rw [← h] have h1 (j : Fin n) : (∑ a : A j, (x j).val a) = 1 := (x j).2.2 simp_rw [h1, Finset.prod_const_one]
Expected payoffs are bounded by 1.
Since payoffs are at most 1 and probabilities are non-negative, the expected payoff is bounded by the sum of probabilities, which equals 1.
uses
normal_form_expected_payoff,Finset.sum_le_sum,mul_le_mul_of_nonneg_left,one_player_extension_approx_nash_prod_nonneg,mul_one,one_player_extension_approx_nash_sum_prod_eq_onelemma one_player_extension_approx_nash_expected_payoff_le_one {n : ℕ} {A : Fin n → Type} [∀ i, Fintype (A i)] (u : Fin n → ((i : Fin n) → A i) → ℝ) (hu : ∀ i a, 0 ≤ u i a ∧ u i a ≤ 1) (i : Fin n) (x : (j : Fin n) → stdSimplex ℝ (A j)) : normal_form_expected_payoff u i x ≤ 1 := by unfold normal_form_expected_payoff have h_le : (∑ a, (∏ j, (x j).val (a j)) * u i a) ≤ ∑ a : (j : Fin n) → A j, (∏ j, (x j).val (a j)) * 1 := by apply Finset.sum_le_sum intro a _ apply mul_le_mul_of_nonneg_left (hu i a).2 (one_player_extension_approx_nash_prod_nonneg x a) simp_rw [mul_one] at h_le rw [one_player_extension_approx_nash_sum_prod_eq_one] at h_le exact h_le
Expected payoffs are non-negative.
Each term in the expected payoff sum is a product of non-negative probabilities and non-negative payoffs.
uses
normal_form_expected_payoff,Finset.sum_nonneg,mul_nonneg,one_player_extension_approx_nash_prod_nonneglemma one_player_extension_approx_nash_expected_payoff_nonneg {n : ℕ} {A : Fin n → Type} [∀ i, Fintype (A i)] (u : Fin n → ((i : Fin n) → A i) → ℝ) (hu : ∀ i a, 0 ≤ u i a ∧ u i a ≤ 1) (i : Fin n) (x : (j : Fin n) → stdSimplex ℝ (A j)) : 0 ≤ normal_form_expected_payoff u i x := by unfold normal_form_expected_payoff apply Finset.sum_nonneg intro a _ exact mul_nonneg (one_player_extension_approx_nash_prod_nonneg x a) (hu i a).1
The probability of a joint profile factorises when appending the last player's action.
Splitting the product over Fin (r + 1) into the product over the first r coordinates and the last coordinate gives the product of the first r players' probabilities with the last player's probability.
uses
Fin.prod_univ_castSucc,Fin.snoc_castSucc,Fin.snoc_lastlemma one_player_extension_approx_nash_prod_snoc_apply {r : ℕ} {A : Fin (r + 1) → Type} [∀ i, Fintype (A i)] (x : (j : Fin r) → stdSimplex ℝ (A j.castSucc)) (y : stdSimplex ℝ (A (Fin.last r))) (a : (j : Fin (r + 1)) → A j) : (∏ j : Fin (r + 1), ((Fin.snoc (α := fun i => stdSimplex ℝ (A i)) x y j : stdSimplex ℝ (A j)).val (a j))) = (∏ j : Fin r, (x j).val (a j.castSucc)) * y.val (a (Fin.last r)) := by rw [Fin.prod_univ_castSucc] simp only [Fin.snoc_castSucc, Fin.snoc_last]
Expected payoffs are affine in the last player's mixed strategy.
Substituting a convex combination of two strategies for the last player and using linearity of summation decomposes the expected payoff into the convex combination of the expected payoffs under each strategy.
uses
normal_form_expected_payoff,one_player_extension_approx_nash_prod_snoc_apply,stdSimplex.mix_apply,Finset.sum_add_distrib,Finset.mul_sumlemma one_player_extension_approx_nash_expected_payoff_mix_last {r : ℕ} {A : Fin (r + 1) → Type} [∀ i, Fintype (A i)] (u : Fin (r + 1) → ((i : Fin (r + 1)) → A i) → ℝ) (x : (j : Fin r) → stdSimplex ℝ (A j.castSucc)) (y1 y2 : stdSimplex ℝ (A (Fin.last r))) (θ : ℝ) (hθ0 : 0 ≤ θ) (hθ1 : θ ≤ 1) (i : Fin (r + 1)) : normal_form_expected_payoff u i (Fin.snoc x (stdSimplex.mix θ hθ0 hθ1 y1 y2)) = θ * normal_form_expected_payoff u i (Fin.snoc x y1) + (1 - θ) * normal_form_expected_payoff u i (Fin.snoc x y2) := by unfold normal_form_expected_payoff simp_rw [one_player_extension_approx_nash_prod_snoc_apply] simp only [stdSimplex.mix_apply] have h (a : (j : Fin (r + 1)) → A j) : ((∏ j : Fin r, (x j).val (a j.castSucc)) * (θ * y1.val (a (Fin.last r)) + (1 - θ) * y2.val (a (Fin.last r)))) * u i a = θ * (((∏ j : Fin r, (x j).val (a j.castSucc)) * y1.val (a (Fin.last r))) * u i a) + (1 - θ) * (((∏ j : Fin r, (x j).val (a j.castSucc)) * y2.val (a (Fin.last r))) * u i a) := by ring simp_rw [h] rw [Finset.sum_add_distrib, ← Finset.mul_sum, ← Finset.mul_sum]
Fixing the last player to a pure strategy matches the subgame expected payoff.
Using the equivalence between joint profiles and pairs of actions, the sum over the last player's actions collapses to the single pure action s, matching the subgame definition.
uses
normal_form_expected_payoff,normal_form_subgame_last,Equiv.sum_comp,Fin.snocEquiv,Fintype.sum_prod_type,Fin.prod_univ_castSucc,Fin.snoc_castSucc,Fin.snoc_last,stdSimplex.pure_apply,Finset.sum_commlemma one_player_extension_approx_nash_expected_payoff_snoc_pure_last {r : ℕ} {A : Fin (r + 1) → Type} [∀ i, Fintype (A i)] [∀ i, DecidableEq (A i)] (u : Fin (r + 1) → ((i : Fin (r + 1)) → A i) → ℝ) (x : (j : Fin r) → stdSimplex ℝ (A j.castSucc)) (s : A (Fin.last r)) (k : Fin r) : normal_form_expected_payoff u k.castSucc (Fin.snoc x (stdSimplex.pure s)) = normal_form_expected_payoff (normal_form_subgame_last u s) k x := by unfold normal_form_expected_payoff normal_form_subgame_last have h_equiv := (Equiv.sum_comp (Fin.snocEquiv A) (fun a => (∏ j : Fin (r + 1), ((Fin.snoc (α := fun i => stdSimplex ℝ (A i)) x (stdSimplex.pure s) j : stdSimplex ℝ (A j)).val (a j))) * u k.castSucc a)).symm rw [h_equiv] simp_rw [Fintype.sum_prod_type] have h_eq (a_last : A (Fin.last r)) (a_init : (j : Fin r) → A j.castSucc) : Fin.snocEquiv A (a_last, a_init) = Fin.snoc a_init a_last := rfl simp_rw [h_eq] have h_prod (a_last : A (Fin.last r)) (a_init : (j : Fin r) → A j.castSucc) : (∏ j : Fin (r + 1), ((Fin.snoc (α := fun i => stdSimplex ℝ (A i)) x (stdSimplex.pure s) j : stdSimplex ℝ (A j)).val (Fin.snoc a_init a_last j))) = (∏ j : Fin r, (x j).val (a_init j)) * (stdSimplex.pure s : stdSimplex ℝ (A (Fin.last r))).val a_last := by rw [Fin.prod_univ_castSucc] simp only [Fin.snoc_castSucc, Fin.snoc_last] simp_rw [h_prod, stdSimplex.pure_apply] rw [Finset.sum_comm] have h_inner (a_init : (j : Fin r) → A j.castSucc) : (∑ a_last : A (Fin.last r), ((∏ j : Fin r, (x j).val (a_init j)) * (if a_last = s then (1 : ℝ) else 0)) * u k.castSucc (Fin.snoc a_init a_last)) = (∏ j : Fin r, (x j).val (a_init j)) * u k.castSucc (Fin.snoc a_init s) := by have h_split (a_last : A (Fin.last r)) : ((∏ j : Fin r, (x j).val (a_init j)) * (if a_last = s then (1 : ℝ) else 0)) * u k.castSucc (Fin.snoc a_init a_last) = if a_last = s then (∏ j : Fin r, (x j).val (a_init j)) * u k.castSucc (Fin.snoc a_init s) else 0 := by split_ifs with h · subst h; ring · ring simp_rw [h_split] simp simp_rw [h_inner]
Setup and parameters for the extension profile.
We define the mixture parameter θ = 1 / (2 - α) and the last player's strategy y mixing s and b. We show 0 ≤ θ ≤ 1 and θ * α + (1 - θ) = θ, then case split on whether a player is the last player or one of the first r players.
uses
div_nonneg,zero_le_one,div_le_iff₀,one_player_extension_theta_identity,Fin.lastCasestheorem one_player_extension_approx_nash {r : ℕ} {A : Fin (r + 1) → Type} [∀ i, Fintype (A i)] [∀ i, DecidableEq (A i)] (u : Fin (r + 1) → ((i : Fin (r + 1)) → A i) → ℝ) (hu : ∀ i a, 0 ≤ u i a ∧ u i a ≤ 1) (s : A (Fin.last r)) (α : ℝ) (hα0 : 0 ≤ α) (hα1 : α ≤ 1) (x : (j : Fin r) → stdSimplex ℝ (A j.castSucc)) (hx : is_approx_nash_equilibrium (normal_form_subgame_last u s) α x) (b : A (Fin.last r)) (hb : is_pure_best_response_last u x b) : let θ : ℝ := 1 / (2 - α) let y : stdSimplex ℝ (A (Fin.last r)) := stdSimplex.mix θ (div_nonneg zero_le_one (by linarith)) ((div_le_iff₀ (by linarith : 0 < 2 - α)).mpr (by linarith)) (stdSimplex.pure s) (stdSimplex.pure b) is_approx_nash_equilibrium u θ (Fin.snoc x y) := by intro θ y have hθ0 : 0 ≤ θ := div_nonneg zero_le_one (by linarith) have hθ1 : θ ≤ 1 := (div_le_iff₀ (by linarith : 0 < 2 - α)).mpr (by linarith) have h2α : 2 - α ≠ 0 := by linarith have h_theta_id : θ * α + (1 - θ) = θ := one_player_extension_theta_identity α h2α intro i refine Fin.lastCases ?_ ?_ i
The last player has no profitable deviation beyond θ.
Any deviation of the last player yields at most the payoff of the best response b. Decomposing the equilibrium payoff into the mix of s and b, the gain is bounded by θ times the difference between b and s payoffs, which is at most θ * 1 = θ.
uses
Function.update,Fin.snoc,stdSimplex.pure,Fin.update_snoc_last,one_player_extension_approx_nash_expected_payoff_mix_last,normal_form_expected_payoff,one_player_extension_approx_nash_expected_payoff_le_one,one_player_extension_approx_nash_expected_payoff_nonneg,mul_one· intro a have hup : Function.update (Fin.snoc (α := fun i => stdSimplex ℝ (A i)) x y) (Fin.last r) (stdSimplex.pure a) = Fin.snoc (α := fun i => stdSimplex ℝ (A i)) x (stdSimplex.pure a) := Fin.update_snoc_last (α := fun i => stdSimplex ℝ (A i)) y x (stdSimplex.pure a) rw [hup] have hmix := one_player_extension_approx_nash_expected_payoff_mix_last u x (stdSimplex.pure s) (stdSimplex.pure b) θ hθ0 hθ1 (Fin.last r) change normal_form_expected_payoff u (Fin.last r) (Fin.snoc x (stdSimplex.pure a)) - normal_form_expected_payoff u (Fin.last r) (Fin.snoc x y) ≤ θ rw [hmix] have _hba := hb a have _hub := one_player_extension_approx_nash_expected_payoff_le_one u hu (Fin.last r) (Fin.snoc x (stdSimplex.pure b)) have _hus := one_player_extension_approx_nash_expected_payoff_nonneg u hu (Fin.last r) (Fin.snoc x (stdSimplex.pure s)) calc normal_form_expected_payoff u (Fin.last r) (Fin.snoc x (stdSimplex.pure a)) - (θ * normal_form_expected_payoff u (Fin.last r) (Fin.snoc x (stdSimplex.pure s)) + (1 - θ) * normal_form_expected_payoff u (Fin.last r) (Fin.snoc x (stdSimplex.pure b))) _ ≤ normal_form_expected_payoff u (Fin.last r) (Fin.snoc x (stdSimplex.pure b)) - (θ * normal_form_expected_payoff u (Fin.last r) (Fin.snoc x (stdSimplex.pure s)) + (1 - θ) * normal_form_expected_payoff u (Fin.last r) (Fin.snoc x (stdSimplex.pure b))) := by linarith _ = θ * (normal_form_expected_payoff u (Fin.last r) (Fin.snoc x (stdSimplex.pure b)) - normal_form_expected_payoff u (Fin.last r) (Fin.snoc x (stdSimplex.pure s))) := by ring _ ≤ θ * 1 := by nlinarith _ = θ := mul_one θ
Any of the first r players has no profitable deviation beyond θ.
For player k, the payoff decomposes into a θ-weight on the subgame payoff and a (1 - θ)-weight on the profile with b. The subgame gain is at most α because x is an α-Nash equilibrium, and the b-profile gain is at most 1 - 0 = 1. Thus the deviation gain is at most θ * α + (1 - θ) * 1 = θ.
uses
Function.update,Fin.snoc,stdSimplex.pure,Fin.snoc_update,one_player_extension_approx_nash_expected_payoff_mix_last,normal_form_expected_payoff,one_player_extension_approx_nash_expected_payoff_snoc_pure_last,normal_form_subgame_last,one_player_extension_approx_nash_expected_payoff_le_one,one_player_extension_approx_nash_expected_payoff_nonneg· intro k a have hup : Function.update (Fin.snoc (α := fun i => stdSimplex ℝ (A i)) x y) k.castSucc (stdSimplex.pure a) = Fin.snoc (α := fun i => stdSimplex ℝ (A i)) (Function.update x k (stdSimplex.pure a)) y := (Fin.snoc_update (α := fun i => stdSimplex ℝ (A i)) y x k (stdSimplex.pure a)).symm rw [hup] let x' := Function.update x k (stdSimplex.pure a) have hmix' := one_player_extension_approx_nash_expected_payoff_mix_last u x' (stdSimplex.pure s) (stdSimplex.pure b) θ hθ0 hθ1 k.castSucc have hmix := one_player_extension_approx_nash_expected_payoff_mix_last u x (stdSimplex.pure s) (stdSimplex.pure b) θ hθ0 hθ1 k.castSucc change normal_form_expected_payoff u k.castSucc (Fin.snoc x' y) - normal_form_expected_payoff u k.castSucc (Fin.snoc x y) ≤ θ rw [hmix', hmix] have hxs' := one_player_extension_approx_nash_expected_payoff_snoc_pure_last u x' s k have hxs := one_player_extension_approx_nash_expected_payoff_snoc_pure_last u x s k have _hnash := hx k a have _hub' := one_player_extension_approx_nash_expected_payoff_le_one u hu k.castSucc (Fin.snoc x' (stdSimplex.pure b)) have _hub := one_player_extension_approx_nash_expected_payoff_nonneg u hu k.castSucc (Fin.snoc x (stdSimplex.pure b)) calc (θ * normal_form_expected_payoff u k.castSucc (Fin.snoc x' (stdSimplex.pure s)) + (1 - θ) * normal_form_expected_payoff u k.castSucc (Fin.snoc x' (stdSimplex.pure b))) - (θ * normal_form_expected_payoff u k.castSucc (Fin.snoc x (stdSimplex.pure s)) + (1 - θ) * normal_form_expected_payoff u k.castSucc (Fin.snoc x (stdSimplex.pure b))) _ = θ * (normal_form_expected_payoff u k.castSucc (Fin.snoc x' (stdSimplex.pure s)) - normal_form_expected_payoff u k.castSucc (Fin.snoc x (stdSimplex.pure s))) + (1 - θ) * (normal_form_expected_payoff u k.castSucc (Fin.snoc x' (stdSimplex.pure b)) - normal_form_expected_payoff u k.castSucc (Fin.snoc x (stdSimplex.pure b))) := by ring _ = θ * (normal_form_expected_payoff (normal_form_subgame_last u s) k x' - normal_form_expected_payoff (normal_form_subgame_last u s) k x) + (1 - θ) * (normal_form_expected_payoff u k.castSucc (Fin.snoc x' (stdSimplex.pure b)) - normal_form_expected_payoff u k.castSucc (Fin.snoc x (stdSimplex.pure b))) := by rw [hxs', hxs] _ ≤ θ * α + (1 - θ) * 1 := by nlinarith _ = θ := by linarith [h_theta_id]
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open BigOperatorslemma one_player_extension_approx_nash_prod_nonneg {n : ℕ} {A : Fin n → Type} [∀ i, Fintype (A i)] (x : (j : Fin n) → stdSimplex ℝ (A j)) (a : (j : Fin n) → A j) : 0 ≤ ∏ j : Fin n, (x j).val (a j) := Finset.prod_nonneg (fun j _ => (x j).2.1 (a j))lemma one_player_extension_approx_nash_sum_prod_eq_one {n : ℕ} {A : Fin n → Type} [∀ i, Fintype (A i)] (x : (j : Fin n) → stdSimplex ℝ (A j)) : (∑ a : (j : Fin n) → A j, ∏ j : Fin n, (x j).val (a j)) = 1 := by have h := @Finset.prod_univ_sum (Fin n) ℝ _ _ A _ (fun _ => Finset.univ) (fun j a => (x j).val a) classical rw [Fintype.piFinset_univ] at h rw [← h] have h1 (j : Fin n) : (∑ a : A j, (x j).val a) = 1 := (x j).2.2 simp_rw [h1, Finset.prod_const_one]lemma one_player_extension_approx_nash_expected_payoff_le_one {n : ℕ} {A : Fin n → Type} [∀ i, Fintype (A i)] (u : Fin n → ((i : Fin n) → A i) → ℝ) (hu : ∀ i a, 0 ≤ u i a ∧ u i a ≤ 1) (i : Fin n) (x : (j : Fin n) → stdSimplex ℝ (A j)) : normal_form_expected_payoff u i x ≤ 1 := by unfold normal_form_expected_payoff have h_le : (∑ a, (∏ j, (x j).val (a j)) * u i a) ≤ ∑ a : (j : Fin n) → A j, (∏ j, (x j).val (a j)) * 1 := by apply Finset.sum_le_sum intro a _ apply mul_le_mul_of_nonneg_left (hu i a).2 (one_player_extension_approx_nash_prod_nonneg x a) simp_rw [mul_one] at h_le rw [one_player_extension_approx_nash_sum_prod_eq_one] at h_le exact h_lelemma one_player_extension_approx_nash_expected_payoff_nonneg {n : ℕ} {A : Fin n → Type} [∀ i, Fintype (A i)] (u : Fin n → ((i : Fin n) → A i) → ℝ) (hu : ∀ i a, 0 ≤ u i a ∧ u i a ≤ 1) (i : Fin n) (x : (j : Fin n) → stdSimplex ℝ (A j)) : 0 ≤ normal_form_expected_payoff u i x := by unfold normal_form_expected_payoff apply Finset.sum_nonneg intro a _ exact mul_nonneg (one_player_extension_approx_nash_prod_nonneg x a) (hu i a).1lemma one_player_extension_approx_nash_prod_snoc_apply {r : ℕ} {A : Fin (r + 1) → Type} [∀ i, Fintype (A i)] (x : (j : Fin r) → stdSimplex ℝ (A j.castSucc)) (y : stdSimplex ℝ (A (Fin.last r))) (a : (j : Fin (r + 1)) → A j) : (∏ j : Fin (r + 1), ((Fin.snoc (α := fun i => stdSimplex ℝ (A i)) x y j : stdSimplex ℝ (A j)).val (a j))) = (∏ j : Fin r, (x j).val (a j.castSucc)) * y.val (a (Fin.last r)) := by rw [Fin.prod_univ_castSucc] simp only [Fin.snoc_castSucc, Fin.snoc_last]lemma one_player_extension_approx_nash_expected_payoff_mix_last {r : ℕ} {A : Fin (r + 1) → Type} [∀ i, Fintype (A i)] (u : Fin (r + 1) → ((i : Fin (r + 1)) → A i) → ℝ) (x : (j : Fin r) → stdSimplex ℝ (A j.castSucc)) (y1 y2 : stdSimplex ℝ (A (Fin.last r))) (θ : ℝ) (hθ0 : 0 ≤ θ) (hθ1 : θ ≤ 1) (i : Fin (r + 1)) : normal_form_expected_payoff u i (Fin.snoc x (stdSimplex.mix θ hθ0 hθ1 y1 y2)) = θ * normal_form_expected_payoff u i (Fin.snoc x y1) + (1 - θ) * normal_form_expected_payoff u i (Fin.snoc x y2) := by unfold normal_form_expected_payoff simp_rw [one_player_extension_approx_nash_prod_snoc_apply] simp only [stdSimplex.mix_apply] have h (a : (j : Fin (r + 1)) → A j) : ((∏ j : Fin r, (x j).val (a j.castSucc)) * (θ * y1.val (a (Fin.last r)) + (1 - θ) * y2.val (a (Fin.last r)))) * u i a = θ * (((∏ j : Fin r, (x j).val (a j.castSucc)) * y1.val (a (Fin.last r))) * u i a) + (1 - θ) * (((∏ j : Fin r, (x j).val (a j.castSucc)) * y2.val (a (Fin.last r))) * u i a) := by ring simp_rw [h] rw [Finset.sum_add_distrib, ← Finset.mul_sum, ← Finset.mul_sum]lemma one_player_extension_approx_nash_expected_payoff_snoc_pure_last {r : ℕ} {A : Fin (r + 1) → Type} [∀ i, Fintype (A i)] [∀ i, DecidableEq (A i)] (u : Fin (r + 1) → ((i : Fin (r + 1)) → A i) → ℝ) (x : (j : Fin r) → stdSimplex ℝ (A j.castSucc)) (s : A (Fin.last r)) (k : Fin r) : normal_form_expected_payoff u k.castSucc (Fin.snoc x (stdSimplex.pure s)) = normal_form_expected_payoff (normal_form_subgame_last u s) k x := by unfold normal_form_expected_payoff normal_form_subgame_last have h_equiv := (Equiv.sum_comp (Fin.snocEquiv A) (fun a => (∏ j : Fin (r + 1), ((Fin.snoc (α := fun i => stdSimplex ℝ (A i)) x (stdSimplex.pure s) j : stdSimplex ℝ (A j)).val (a j))) * u k.castSucc a)).symm rw [h_equiv] simp_rw [Fintype.sum_prod_type] have h_eq (a_last : A (Fin.last r)) (a_init : (j : Fin r) → A j.castSucc) : Fin.snocEquiv A (a_last, a_init) = Fin.snoc a_init a_last := rfl simp_rw [h_eq] have h_prod (a_last : A (Fin.last r)) (a_init : (j : Fin r) → A j.castSucc) : (∏ j : Fin (r + 1), ((Fin.snoc (α := fun i => stdSimplex ℝ (A i)) x (stdSimplex.pure s) j : stdSimplex ℝ (A j)).val (Fin.snoc a_init a_last j))) = (∏ j : Fin r, (x j).val (a_init j)) * (stdSimplex.pure s : stdSimplex ℝ (A (Fin.last r))).val a_last := by rw [Fin.prod_univ_castSucc] simp only [Fin.snoc_castSucc, Fin.snoc_last] simp_rw [h_prod, stdSimplex.pure_apply] rw [Finset.sum_comm] have h_inner (a_init : (j : Fin r) → A j.castSucc) : (∑ a_last : A (Fin.last r), ((∏ j : Fin r, (x j).val (a_init j)) * (if a_last = s then (1 : ℝ) else 0)) * u k.castSucc (Fin.snoc a_init a_last)) = (∏ j : Fin r, (x j).val (a_init j)) * u k.castSucc (Fin.snoc a_init s) := by have h_split (a_last : A (Fin.last r)) : ((∏ j : Fin r, (x j).val (a_init j)) * (if a_last = s then (1 : ℝ) else 0)) * u k.castSucc (Fin.snoc a_init a_last) = if a_last = s then (∏ j : Fin r, (x j).val (a_init j)) * u k.castSucc (Fin.snoc a_init s) else 0 := by split_ifs with h · subst h; ring · ring simp_rw [h_split] simp simp_rw [h_inner]/-- One-player extension: extending an α-approximate equilibrium of a restricted subgame yields a 1/(2-α)-approximate equilibrium. -/theorem one_player_extension_approx_nash {r : ℕ} {A : Fin (r + 1) → Type} [∀ i, Fintype (A i)] [∀ i, DecidableEq (A i)] (u : Fin (r + 1) → ((i : Fin (r + 1)) → A i) → ℝ) (hu : ∀ i a, 0 ≤ u i a ∧ u i a ≤ 1) (s : A (Fin.last r)) (α : ℝ) (hα0 : 0 ≤ α) (hα1 : α ≤ 1) (x : (j : Fin r) → stdSimplex ℝ (A j.castSucc)) (hx : is_approx_nash_equilibrium (normal_form_subgame_last u s) α x) (b : A (Fin.last r)) (hb : is_pure_best_response_last u x b) : let θ : ℝ := 1 / (2 - α) let y : stdSimplex ℝ (A (Fin.last r)) := stdSimplex.mix θ (div_nonneg zero_le_one (by linarith)) ((div_le_iff₀ (by linarith : 0 < 2 - α)).mpr (by linarith)) (stdSimplex.pure s) (stdSimplex.pure b) is_approx_nash_equilibrium u θ (Fin.snoc x y) := by intro θ y have hθ0 : 0 ≤ θ := div_nonneg zero_le_one (by linarith) have hθ1 : θ ≤ 1 := (div_le_iff₀ (by linarith : 0 < 2 - α)).mpr (by linarith) have h2α : 2 - α ≠ 0 := by linarith have h_theta_id : θ * α + (1 - θ) = θ := one_player_extension_theta_identity α h2α intro i refine Fin.lastCases ?_ ?_ i · intro a have hup : Function.update (Fin.snoc (α := fun i => stdSimplex ℝ (A i)) x y) (Fin.last r) (stdSimplex.pure a) = Fin.snoc (α := fun i => stdSimplex ℝ (A i)) x (stdSimplex.pure a) := Fin.update_snoc_last (α := fun i => stdSimplex ℝ (A i)) y x (stdSimplex.pure a) rw [hup] have hmix := one_player_extension_approx_nash_expected_payoff_mix_last u x (stdSimplex.pure s) (stdSimplex.pure b) θ hθ0 hθ1 (Fin.last r) change normal_form_expected_payoff u (Fin.last r) (Fin.snoc x (stdSimplex.pure a)) - normal_form_expected_payoff u (Fin.last r) (Fin.snoc x y) ≤ θ rw [hmix] have _hba := hb a have _hub := one_player_extension_approx_nash_expected_payoff_le_one u hu (Fin.last r) (Fin.snoc x (stdSimplex.pure b)) have _hus := one_player_extension_approx_nash_expected_payoff_nonneg u hu (Fin.last r) (Fin.snoc x (stdSimplex.pure s)) calc normal_form_expected_payoff u (Fin.last r) (Fin.snoc x (stdSimplex.pure a)) - (θ * normal_form_expected_payoff u (Fin.last r) (Fin.snoc x (stdSimplex.pure s)) + (1 - θ) * normal_form_expected_payoff u (Fin.last r) (Fin.snoc x (stdSimplex.pure b))) _ ≤ normal_form_expected_payoff u (Fin.last r) (Fin.snoc x (stdSimplex.pure b)) - (θ * normal_form_expected_payoff u (Fin.last r) (Fin.snoc x (stdSimplex.pure s)) + (1 - θ) * normal_form_expected_payoff u (Fin.last r) (Fin.snoc x (stdSimplex.pure b))) := by linarith _ = θ * (normal_form_expected_payoff u (Fin.last r) (Fin.snoc x (stdSimplex.pure b)) - normal_form_expected_payoff u (Fin.last r) (Fin.snoc x (stdSimplex.pure s))) := by ring _ ≤ θ * 1 := by nlinarith _ = θ := mul_one θ · intro k a have hup : Function.update (Fin.snoc (α := fun i => stdSimplex ℝ (A i)) x y) k.castSucc (stdSimplex.pure a) = Fin.snoc (α := fun i => stdSimplex ℝ (A i)) (Function.update x k (stdSimplex.pure a)) y := (Fin.snoc_update (α := fun i => stdSimplex ℝ (A i)) y x k (stdSimplex.pure a)).symm rw [hup] let x' := Function.update x k (stdSimplex.pure a) have hmix' := one_player_extension_approx_nash_expected_payoff_mix_last u x' (stdSimplex.pure s) (stdSimplex.pure b) θ hθ0 hθ1 k.castSucc have hmix := one_player_extension_approx_nash_expected_payoff_mix_last u x (stdSimplex.pure s) (stdSimplex.pure b) θ hθ0 hθ1 k.castSucc change normal_form_expected_payoff u k.castSucc (Fin.snoc x' y) - normal_form_expected_payoff u k.castSucc (Fin.snoc x y) ≤ θ rw [hmix', hmix] have hxs' := one_player_extension_approx_nash_expected_payoff_snoc_pure_last u x' s k have hxs := one_player_extension_approx_nash_expected_payoff_snoc_pure_last u x s k have _hnash := hx k a have _hub' := one_player_extension_approx_nash_expected_payoff_le_one u hu k.castSucc (Fin.snoc x' (stdSimplex.pure b)) have _hub := one_player_extension_approx_nash_expected_payoff_nonneg u hu k.castSucc (Fin.snoc x (stdSimplex.pure b)) calc (θ * normal_form_expected_payoff u k.castSucc (Fin.snoc x' (stdSimplex.pure s)) + (1 - θ) * normal_form_expected_payoff u k.castSucc (Fin.snoc x' (stdSimplex.pure b))) - (θ * normal_form_expected_payoff u k.castSucc (Fin.snoc x (stdSimplex.pure s)) + (1 - θ) * normal_form_expected_payoff u k.castSucc (Fin.snoc x (stdSimplex.pure b))) _ = θ * (normal_form_expected_payoff u k.castSucc (Fin.snoc x' (stdSimplex.pure s)) - normal_form_expected_payoff u k.castSucc (Fin.snoc x (stdSimplex.pure s))) + (1 - θ) * (normal_form_expected_payoff u k.castSucc (Fin.snoc x' (stdSimplex.pure b)) - normal_form_expected_payoff u k.castSucc (Fin.snoc x (stdSimplex.pure b))) := by ring _ = θ * (normal_form_expected_payoff (normal_form_subgame_last u s) k x' - normal_form_expected_payoff (normal_form_subgame_last u s) k x) + (1 - θ) * (normal_form_expected_payoff u k.castSucc (Fin.snoc x' (stdSimplex.pure b)) - normal_form_expected_payoff u k.castSucc (Fin.snoc x (stdSimplex.pure b))) := by rw [hxs', hxs] _ ≤ θ * α + (1 - θ) * 1 := by nlinarith _ = θ := by linarith [h_theta_id]