(9) — under the proximal BR map contracts the Euclidean norm of block distances by
ProvedLeiBR.Sync.eq_9best-responsecontractiongame-theoryp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Under Assumptions 1 and 2, with , let be the spectral norm of the matrix (3). Then for all ,
where the outer norms are Euclidean norms on .
Since by Assumption 2, the proximal BR map is a contraction of in this metric; this is the form of (5) used in the rate analysis.
Preamble
import Mathlib import Definitions.Def_LeiBR_Sync_NashGame import Definitions.Def_LeiBR_Sync_StochGame open MeasureTheory
Formal statement
namespace LeiBR.Sync
/-- (9), §3.2, p. 7: under Assumption 2, with `a = ‖Γ‖` (spectral norm), the proximal BR map
contracts the Euclidean norm of the vector of block distances:
`‖(‖x̂_i(y') - x̂_i(y)‖)_i‖ ≤ a ‖(‖y'_i - y_i‖)_i‖` for all `y, y' ∈ X`. -/
theorem eq_9
{N : ℕ} {n : Fin N → ℕ} {Ω : Type*} [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 < μ)
(xhat : Profile n → Profile n) (hxhat : IsProxBR X (payoff P ξ ψ) μ xhat)
(hA2 : Assumption2 X (payoff P ξ ψ) μ) :
∀ y ∈ stratSet X, ∀ y' ∈ stratSet X,
blockDist (xhat y') (xhat y) ≤ specNorm (Gamma X (payoff P ξ ψ) μ) * blockDist y' y := 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.2, (9), p. 7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.