Lemma 3.6, p. 12 — λμ + (1 − λ) ≥ 1/α(𝓛) for ℓ ∈ 𝓛, f > 0, ℓ*(λf) = ℓ(f)
ProvedPoAIndep.Topology.lemma_3_6anarchy-valuelatency-functionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a standard class of latency functions with anarchy value . Let and , let solve , and put , with if . Then
The lemma rephrases Definitions 3.2 and 3.3; it converts the edge-wise bound of Lemma 3.5 into a comparison with the cost of the Nash flow in Theorem 3.8.
Formalization Note. The inequality is stated in : the left side is , which is when , as on the page.
Preamble
import Mathlib import Definitions.Def_PoAIndep_Topology_Model
Formal statement
namespace PoAIndep.Topology
theorem lemma_3_6 (L : Set (ℝ → ℝ)) (hL : IsStandardClass L) (ℓ : ℝ → ℝ) (hℓ : ℓ ∈ L)
(x : ℝ) (hx : 0 < x) (lam : ℝ) (hlam : lam ∈ Set.Icc (0 : ℝ) 1)
(hsolve : marginalCost ℓ (lam * x) = ℓ x) :
(anarchyValue L)⁻¹ ≤
ENNReal.ofReal (lam * (if ℓ x = 0 then 1 else ℓ (lam * x) / ℓ x) + (1 - lam)) := by sorry
end PoAIndep.Topology
Source
Roughgarden, The price of anarchy is independent of the network topology (journal-version manuscript, Dec. 23, 2002), p. 12, Lemma 3.6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.