§3.1, remark after Definition 3.2, p. 9 — ℓ*(0) = ℓ(0) ≤ ℓ(r) ≤ ℓ*(r), so some λ ∈ [0,1] solves ℓ*(λr) = ℓ(r)
ProvedPoAIndep.Topology.exists_lambdaanarchy-valuelatency-functionmarginal-costp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a standard latency function with marginal cost , and let . Then
and consequently there is with
This is the justification given after Definition 3.2 that the anarchy value is well defined: the scalar exists because is continuous. The same scalars define the scaled-down pseudoflow in Lemma 3.5 and Theorem 3.8.
Formalization Note. is the one-sided derivative of at .
Preamble
import Mathlib import Definitions.Def_PoAIndep_Topology_Model
Formal statement
namespace PoAIndep.Topology
theorem exists_lambda (ℓ : ℝ → ℝ) (hℓ : IsStandard ℓ) (r : ℝ) (hr : 0 < r) :
(marginalCost ℓ 0 = ℓ 0 ∧ ℓ 0 ≤ ℓ r ∧ ℓ r ≤ marginalCost ℓ r) ∧
∃ lam ∈ Set.Icc (0 : ℝ) 1, marginalCost ℓ (lam * r) = ℓ r := by sorry
end PoAIndep.Topology
Source
Roughgarden, The price of anarchy is independent of the network topology (journal-version manuscript, Dec. 23, 2002), p. 9, §3.1, paragraph after Definition 3.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.