Lemma 14 — the algebraic inequality behind Lemma 10
ProvedWeightedCongestionBR.lemma_14algorithmic-game-theoryapproximate-equilibriacongestion-gamesp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix a positive integer . For any polynomial and any ,
for any . It is applied resource by resource in the proof of Lemma 10.
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_WeightedCongestionBR_IsPd set_option autoImplicit false open scoped NNReal
Formal statement
namespace WeightedCongestionBR
/-- **Lemma 14** (Giannakopoulos, Noarov, Schulz, *Computing Approximate Equilibria in Weighted Congestion Games via Best-Responses*, arXiv:1810.12806v6, p.27). Fix a positive integer `d`. For any polynomial `f ∈ 𝔓_d` and any
`ε > 0`,
`y f(z + x + y) ≤ (1 + ε) y f(z + x' + y) + (1 + 1/ε)^d d^d x f(z + x + y')`
for any `x, x', y, y', z ≥ 0`. -/
theorem lemma_14 (d : ℕ) (hd : 1 ≤ d) (f : Polynomial ℝ) (hf : IsPd d f) (ε : ℝ) (hε : 0 < ε)
(x x' y y' z : ℝ) (hx : 0 ≤ x) (hx' : 0 ≤ x') (hy : 0 ≤ y) (hy' : 0 ≤ y') (hz : 0 ≤ z) :
y * f.eval (z + x + y) ≤
(1 + ε) * y * f.eval (z + x' + y) + (1 + 1 / ε) ^ d * (d : ℝ) ^ d * x * f.eval (z + x + y') := by sorry
end WeightedCongestionBR
Source
Giannakopoulos, Noarov, Schulz, Computing Approximate Equilibria in Weighted Congestion Games via Best-Responses, arXiv:1810.12806v6, Lemma 14, p.27
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.