§2.4, p. 10 — the pure price of anarchy is at most every valid smoothness ratio
ProvedRobustPoA.Tight.weak_dualitycongestion-gamesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchysmooth-games
Let be a finite congestion game with a nonnegative social cost on every feasible profile. If is -smooth and , then its pure price of anarchy satisfies
This is the general upper-bound direction behind tightness: any smoothness certificate limits the cost of every pure Nash equilibrium relative to optimum.
Formalization Note The nonnegative objective is the standing assumption of §2.4. The extended-value convention covers an optimum of zero and games with no pure Nash equilibrium.
Preamble
import Definitions.Def_RobustPoA_Tight_Classes
Formal statement
namespace RobustPoA.Tight
open scoped ENNReal
open CongestionPoA.AsymSum
/-- §2.4, p. 10: the pure price of anarchy is bounded by any smoothness ratio. -/
theorem weak_duality {ι E : Type*} [Fintype ι] [DecidableEq ι]
[Fintype E] [DecidableEq E] (G : CongestionGame ι E)
(lam mu : ℝ) (hcost : ∀ A, IsProfile G A → 0 ≤ sumCost G A)
(hsmooth : IsSmoothCG G lam mu) (hmu : mu < 1) :
purePoA G ≤ ENNReal.ofReal (lam / (1 - mu)) := by sorry
end RobustPoA.Tight
Source
Roughgarden, Intrinsic Robustness of the Price of Anarchy, J. ACM 62(5) (2015), §2.4, p. 10, claim preceding Definition 2.8
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.