(20) — the mean error recursion of Algorithm 1
ProvedLeiBR.Sync.eq_20best-responseconvergence-ratep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-approximation
Assume Assumptions 1 and 2, , and let be a Nash equilibrium. Let be generated by Algorithm 1 (abstract form) for a filtration , from a deterministic , with deterministic accuracies in (8). Put , and
Then
This one-step recursion is the core of the geometric rate (Proposition 4): the exact BR contracts by , and the inexactness enters only additively.
Preamble
import Mathlib import Definitions.Def_LeiBR_Sync_NashGame import Definitions.Def_LeiBR_Sync_StochGame import Definitions.Def_LeiBR_Sync_Algorithm1 open MeasureTheory
Formal statement
namespace LeiBR.Sync
/-- (20), proof of Proposition 4, p. 9: for Algorithm 1 with deterministic accuracies
`α_{i,k} ≥ 0`, `u_k = E‖(‖x_{i,k} - x*_i‖)_i‖` satisfies
`u_{k+1} ≤ a u_k + √N α_{max,k}` for all `k ≥ 0`, where `a = ‖Γ‖` and
`α_{max,k} = max_i α_{i,k}`. -/
theorem eq_20
{N : ℕ} {n : Fin N → ℕ} {Ω : Type*} [mΩ : MeasurableSpace Ω] (P : Measure Ω)
[IsProbabilityMeasure P] {d : ℕ} (ξ : Ω → EuclideanSpace ℝ (Fin d))
(X : ∀ i : Fin N, Set (Strat n i)) (ψ : Fin N → Profile n → EuclideanSpace ℝ (Fin d) → ℝ)
(gψ : ∀ i : Fin N, Profile n → EuclideanSpace ℝ (Fin d) → Strat n i) (M : Fin N → ℝ)
(hA1 : Assumption1 P ξ X ψ gψ M) (μ : ℝ) (hμ : 0 < μ)
(hA2 : Assumption2 X (payoff P ξ ψ) μ)
(xhat : Profile n → Profile n) (hxhat : IsProxBR X (payoff P ξ ψ) μ xhat)
(xs : Profile n) (hxs : IsNashEq X (payoff P ξ ψ) xs)
(F : Filtration ℕ mΩ) (α : Fin N → ℕ → ℝ) (hα : ∀ i k, 0 ≤ α i k)
(x0 : Profile n) (x : ℕ → Ω → Profile n) (hx : IsAlg1 P F X xhat α x0 x) :
∀ k : ℕ, ∫ ω, blockDist (x (k + 1) ω) xs ∂P ≤
specNorm (Gamma X (payoff P ξ ψ) μ) * ∫ ω, blockDist (x k ω) xs ∂P +
Real.sqrt N * ⨆ i : Fin N, α i k := by sorry
end LeiBR.Sync
Source
Lei, Shanbhag, Pang & Sen, On Synchronous, Asynchronous, and Randomized Best-Response Schemes for Stochastic Nash Games, arXiv:1704.04578v2, §3.3, proof of Proposition 4, (20), p. 9; α_max,k from p. 8
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.