Theorem 3.8, p. 12 β for any instance with latencies in a standard class π, Ο(G, r, β) β€ Ξ±(π)
ProvedPoAIndep.Topology.theorem_3_8Let be a standard class of latency functions with anarchy value . Let be any instance β an arbitrary finite directed network with any number of commodities β whose edge latency functions all belong to . If is a feasible flow at Nash equilibrium and is any feasible flow with , then
Equivalently, , where is the ratio between the cost of a Nash flow and of an optimal flow.
This is the central technical result of the paper: the anarchy value, defined through two-link Pigou-type examples alone, bounds the inefficiency of selfish routing in every network.
Formalization Note. The paper's ratio presupposes that Nash and optimal flows exist and that all Nash flows have the same cost (Proposition 2.4, cited by the paper). The formal statement avoids that dependence: it bounds for every feasible Nash flow and every feasible of positive cost, which, since an optimal flow has the least cost, is the bound on . The ratio is compared in .
import Mathlib import Definitions.Def_PoAIndep_Topology_Model
namespace PoAIndep.Topology
theorem theorem_3_8 (L : Set (β β β)) (hL : IsStandardClass L) :
β (V E : Type) [Fintype V] [DecidableEq V] [Fintype E] [DecidableEq E] (I : Instance V E),
InClass I L β β f g : Flow I, IsFlow I f β IsFeasible I f β IsNashFlow I f β
IsFlow I g β IsFeasible I g β 0 < cost I g β
ENNReal.ofReal (cost I f / cost I g) β€ anarchyValue L := by sorry
end PoAIndep.Topology
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.