(9) — under the proximal BR map contracts with factor
ProvedLeiBR.Rand.eq9_contractionbest-responsecontractionp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let Assumptions 1 and 2 hold, , and . For all ,
Since , the proximal best-response map is a contraction of in the Euclidean norm of the vector of block norms; its unique fixed point is the Nash equilibrium.
Preamble
import Mathlib import Definitions.Def_LeiBR_Rand_Game import Definitions.Def_LeiBR_Rand_ProxBR import Definitions.Def_LeiBR_Rand_Assumption1 open MeasureTheory ProbabilityTheory
Formal statement
namespace LeiBR.Rand
/-- (9), §3.2, p. 7: under Assumption 2, with `a = ‖Γ‖`,
`‖(‖x̂_i(y') − x̂_i(y)‖)_i‖ ≤ a ‖(‖y'_i − y_i‖)_i‖` for all `y, y' ∈ X`. -/
theorem eq9_contraction {N : ℕ} {n : Fin N → ℕ} {d : ℕ} (G : Game N n)
(μξ : Measure (EuclideanSpace ℝ (Fin d)))
(ψ : Fin N → LeiBR.Sync.Profile n → EuclideanSpace ℝ (Fin d) → ℝ)
(gψ : ∀ i, LeiBR.Sync.Profile n → EuclideanSpace ℝ (Fin d) → LeiBR.Sync.Strat n i) (M : Fin N → ℝ)
(hA1 : Assumption1 G μξ ψ gψ M) (mu : ℝ) (hmu : 0 < mu)
(xhat : LeiBR.Sync.Profile n → LeiBR.Sync.Profile n) (hxhat : IsProxBR G mu xhat)
(hA2 : Assumption2 G mu) (y y' : LeiBR.Sync.Profile n) (hy : G.Feasible y) (hy' : G.Feasible y') :
blockNorm (xhat y' - xhat y) ≤ contrFactor G mu * blockNorm (y' - y) := by sorry
end LeiBR.Rand
Source
Lei, Shanbhag, Pang & Sen, On Synchronous, Asynchronous, and Randomized Best-Response Schemes for Stochastic Nash Games, arXiv:1704.04578v2, p. 7, §3.2, (9)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.