Theorem 3.3, p. 23 — games with regularly varying cost functions are asymptotically well designed: PoA(d⁽ⁿ⁾) → 1 for every unbounded demand sequence
ProvedLimitPoA.RegVar.theorem_3_3Let be a non-atomic congestion game with a finite non-empty set of groups and finitely many resources and strategies, satisfying (2.1), in which every group has a strategy. Suppose every resource cost function is non-negative, non-decreasing and continuous on and regularly varying: for every , exists in . Then is asymptotically well designed: for every demand sequence with and ,
This is the main result of the paper. It holds without any growth condition on the demands, and the class of regularly varying costs contains all polynomials with non-negative coefficients, logarithmic factors, and their products and sums; each resource may have a different regular variation index.
Formalization Note The paper assumes for every group; the statement admits zero entries, which the paper's own sequences use and which is equivalent to applying the positive-demand version to every subgame. is the worst NE cost (sSup) over the optimum cost (sInf); both sets are non-empty and bounded, so these are genuine values. The "scalable by decomposition" clause of the theorem is a separate milestone.
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop import Definitions.Def_LimitPoA_RegVar_Model
namespace LimitPoA.RegVar
/-- Theorem 3.3, p. 23: games with regularly varying cost functions are asymptotically well designed:
`PoA(d^(n)) → 1` along every unbounded demand sequence. -/
theorem theorem_3_3 (Γ : Game) (hΓ : Γ.Standing) (τ : Fin Γ.J → ℝ → ℝ)
(hτ : ∀ a, IsCostFn (τ a)) (hrv : ∀ a, IsRegularlyVarying (τ a)) :
IsAsymptoticallyWellDesigned Γ τ := by sorry
end LimitPoA.RegVar
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.