Lemma 3 —
ProvedCongestionApproxPNE.lemma_3algorithmic-game-theoryasymptoticsp2o-gran-per-chapterp2o-plan-paperp2o-v1real-analysis
For integers define
Then .
The sequence is the right-hand side of display (5); the lemma shows that the denominator of the first ratio of (3) at the parameter choice is eventually at most .
Differences from the source:
- encoding: the sequence defined for integers d ≥ 2 → a sequence over all d : ℕ, limit along atTop; reason: the values at d = 0, 1 do not affect a limit; k_d is Nat.ceil, equal to the printed ceiling for d ≥ 2 (both are 0 at d = 2)
Preamble
import Mathlib import Definitions.Def_CongestionApproxPNE_kd set_option autoImplicit false open Filter Topology
Formal statement
namespace CongestionApproxPNE
/-- **Lemma 3: `g(d) → 1`.**
Christodoulou, Gairing, Giannakopoulos, Poças, Waldmann, *Existence and Complexity of Approximate
Equilibria in Weighted Congestion Games*, arXiv:2002.07466v3, Appendix A, Lemma 3, p.23: "For any integer d ≥ 2 define the sequence
g(d) = (1 + d^{−1/(2(kd+1))})^{kd} + 2√d/(ln d (1 + ln d/(2d))^d) where kd = ⌈ln d/(2 ln ln d)⌉.
Then lim_{d→∞} g(d) = 1."
**Formalization Note** The sequence is indexed by `d : ℕ` and the limit is along `atTop`
(the values at `d = 0, 1`, outside the paper's range `d ≥ 2`, do not affect a limit).
`k_d` is `kd d` (`Nat.ceil`); `Real.log` is `ln`; non-integer powers of `d` are `Real.rpow`. -/
theorem lemma_3 :
Tendsto (fun d : ℕ => (1 + (d : ℝ) ^ (-(1 / (2 * ((kd d : ℝ) + 1))))) ^ kd d +
2 * Real.sqrt d / (Real.log d * (1 + Real.log d / (2 * d)) ^ d))
atTop (𝓝 1) := by sorry
end CongestionApproxPNE
Source
Christodoulou et al., Existence and Complexity of Approximate Equilibria in Weighted Congestion Games, arXiv:2002.07466v3, Appendix A, Lemma 3, p.23 (PDF p.24)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.