recursive_one_player_extension_barrier
Let r be a natural number and let α : ℕ → ℝ be a sequence satisfying 0 ≤ α r and α r < 1. Under the one-player extension recurrence α (k + 1) = 1 / (2 - α k) for all k ≥ r, the approximation guarantee for any m ≥ r satisfies α m = 1 - 1 / ((m : ℝ) - c), where c = (r : ℝ) - 1 / (1 - α r).
Statement
theorem recursive_one_player_extension_barrier (r : ℕ) (α : ℕ → ℝ) (hαr : 0 ≤ α r ∧ α r < 1) (hrec : ∀ k, r ≤ k → α (k + 1) = 1 / (2 - α k)) (m : ℕ) (hm : r ≤ m) : let c : ℝ := (r : ℝ) - 1 / (1 - α r) α m = 1 - 1 / ((m : ℝ) - c)
- Formalizes
- arXiv:2611.06076 Proposition 2.3
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- recursive_one_player_extension_reciprocalLet r be a natural number, and let α : ℕ → ℝ be a sequence satisfying α (k + 1) = 1 / (2 - α k) for all k ≥ r. If α r < 1, then for all m…
Read back from the Lean
Let $r$ be a natural number and $\alpha : \mathbb{N} \to \mathbb{R}$ be a sequence of real numbers such that $0 \le \alpha(r) < 1$. Suppose that for every natural number $k \ge r$, the recurrence $\alpha(k + 1) = \frac{1}{2 - \alpha(k)}$ holds. Then for any natural number $m \ge r$, setting $c = r - \frac{1}{1 - \alpha(r)}$, we have $\alpha(m) = 1 - \frac{1}{m - c}$.
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
Under the recurrence α (k + 1) = 1 / (2 - α k), the quantity 1 / (1 - α m) grows linearly with m, as established by recursive_one_player_extension_reciprocal. Rearranging this relation shows that the denominator (m : ℝ) - c is equal to 1 / (1 - α m). Substituting this into the desired formula reduces the claim to simplifying the double reciprocal 1 / (1 / (1 - α m)) to 1 - α m, from which the result follows by elementary ring arithmetic.
(m : ℝ) - c = 1 / (1 - α m), where c = (r : ℝ) - 1 / (1 - α r)
Applying recursive_one_player_extension_reciprocal gives the linear relation 1 / (1 - α m) = 1 / (1 - α r) + ((m : ℝ) - (r : ℝ)). Rearranging this equality algebraically by ring arithmetic establishes that (m : ℝ) - ((r : ℝ) - 1 / (1 - α r)) equals 1 / (1 - α m).
uses
recursive_one_player_extension_reciprocalhave h := recursive_one_player_extension_reciprocal r α hαr.2 hrec m hm have hc : (m : ℝ) - ((r : ℝ) - 1 / (1 - α r)) = 1 / (1 - α m) := by rw [h]; ring
It suffices to show α m = 1 - 1 / (1 / (1 - α m))
Unfolding the definition of c = (r : ℝ) - 1 / (1 - α r) in the target equality and substituting the expression for (m : ℝ) - c replaces the denominator with 1 / (1 - α m).
show α m = 1 - 1 / ((m : ℝ) - ((r : ℝ) - 1 / (1 - α r))) rw [hc]
1 / (1 / (1 - α m)) = 1 - α m
Applying one_div_div rewrites the double division 1 / (1 / (1 - α m)) as (1 - α m) / 1, which simp evaluates to 1 - α m.
uses
one_div_divhave hinv : 1 / (1 / (1 - α m)) = 1 - α m := by rw [one_div_div]; simp
α m = 1 - (1 - α m), concluding the proof
Rewriting with the simplified double reciprocal transforms the goal into α m = 1 - (1 - α m), which is an identity verified by ring arithmetic.
rw [hinv]; ring
recursive_one_player_extension_reciprocal- Under the recurrence α (k + 1) = 1 / (2 - α k) with initial condition α r < 1, the reciprocal sequence satisfies 1 / (1 - α m) = 1 / (1 - α r) + (m - r) for all m ≥ r.
one_div_div- For elements a, b of a division monoid, the reciprocal of a / b is b / a: 1 / (a / b) = b / a.
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.
/-- Proposition 2.3: Limitation of recursive one-player extension for multiplayer approximate Nash equilibria. -/theorem recursive_one_player_extension_barrier (r : ℕ) (α : ℕ → ℝ) (hαr : 0 ≤ α r ∧ α r < 1) (hrec : ∀ k, r ≤ k → α (k + 1) = 1 / (2 - α k)) (m : ℕ) (hm : r ≤ m) : let c : ℝ := (r : ℝ) - 1 / (1 - α r) α m = 1 - 1 / ((m : ℝ) - c) := by have h := recursive_one_player_extension_reciprocal r α hαr.2 hrec m hm have hc : (m : ℝ) - ((r : ℝ) - 1 / (1 - α r)) = 1 / (1 - α m) := by rw [h]; ring show α m = 1 - 1 / ((m : ℝ) - ((r : ℝ) - 1 / (1 - α r))) rw [hc] have hinv : 1 / (1 / (1 - α m)) = 1 - α m := by rw [one_div_div]; simp rw [hinv]; ring