Lemma 2 — the smoothness infimum equals
ProvedWeightedCongestionBR.lemma_2algorithmic-game-theoryapproximate-equilibriacongestion-gamesp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let and let be a positive integer. Then
and the infimum is attained by a feasible pair .
This is the key step of the smoothness argument behind Lemma 1 and Theorem 1; the extra variable is what allows groups of deviating players.
Differences from the source:
- generalization: B = Φ_{d,ρ}^{d+1} (an infimum) → IsGLB at Φ_{d,ρ}^{d+1} and Φ_{d,ρ}^{d+1} belongs to the set; reason: the proof (p.26) exhibits a feasible pair with value Φ_{d,ρ}^{d+1} (μ = μ̂/ρ); attainment is what Lemma 1 needs in multiplicative form, and the statement specializes to the source's equality
Preamble
import Mathlib import Definitions.Def_WeightedCongestionBR_genGolden import Definitions.Def_WeightedCongestionBR_smoothSet set_option autoImplicit false open scoped NNReal
Formal statement
namespace WeightedCongestionBR
/-- **Lemma 2** (Giannakopoulos, Noarov, Schulz, *Computing Approximate Equilibria in Weighted Congestion Games via Best-Responses*, arXiv:1810.12806v6, p.7; proof in Appendix A, pp.24–26). For any `ρ ≥ 1` and positive integer `d`,
`B := inf { λρ/(1 − μρ) | λ ∈ ℝ, μ ∈ (0, 1/ρ), ∀ x, y, z ≥ 0, f ∈ 𝔓_d :
y f(z + x + y) ≤ λ y f(z + y) + μ x f(z + x) } = Φ_{d,ρ}^{d+1}`.
**Formalization Note** The infimum is `IsGLB`. The statement adds that it is attained (the pair
`μ = μ̂/ρ` of the proof, p.26), which Lemma 1 uses in multiplicative form. -/
theorem lemma_2 (d : ℕ) (ρ : ℝ) (hd : 1 ≤ d) (hρ : 1 ≤ ρ) :
IsGLB (smoothSet d ρ) (genGolden d ρ ^ (d + 1)) ∧
genGolden d ρ ^ (d + 1) ∈ smoothSet d ρ := by sorry
end WeightedCongestionBR
Source
Giannakopoulos, Noarov, Schulz, Computing Approximate Equilibria in Weighted Congestion Games via Best-Responses, arXiv:1810.12806v6, Lemma 2, p.7 (proof in Appendix A, pp.24–26)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.