Theorem 4.2, p. 14 β for a standard class containing the constants, two-link instances attain the worst Nash/optimal cost ratio over all networks, and it equals Ξ±(π)
ProvedPoAIndep.Topology.theorem_4_2Let be the network with one source vertex, one sink vertex and two edges directed from source to sink. Let be a standard class of latency functions containing the constant functions. If denotes the set of all instances with latency functions in and the single-commodity instances with underlying network , then
The statement consists of two parts.
- (Attained on two links.) For every there is a single-commodity instance on with latency functions in , a feasible Nash flow and a feasible flow with and .
- (Upper bound everywhere.) For every instance on any finite directed network with any number of commodities and latency functions in , every feasible Nash flow and every feasible flow with satisfy .
Part 1 gives and part 2 gives ; since instances on are instances of the general model, , and the chain of equalities follows. The price of anarchy for such a class is thus independent of the network topology: the simplest two-link networks are already worst possible.
Formalization Note. The anarchy value and the ratios are compared in , so is allowed. The paper's presupposes existence of Nash and optimal flows and the uniqueness of the Nash cost (Proposition 2.4, cited); the formal statement uses ratios over all feasible Nash flows and all feasible flows of positive cost instead, which expresses the same suprema without that dependence. is constructed inside the general instance model.
import Mathlib import Definitions.Def_PoAIndep_Topology_Model
namespace PoAIndep.Topology
theorem theorem_4_2 (L : Set (β β β)) (hL : IsStandardClass L) (hc : ContainsConstants L) :
(β b : ENNReal, b < anarchyValue L β
β (r : β) (hr : 0 < r) (β : Fin 2 β β β β) (hβ : β e, IsLatency (β e)),
InClass (twoLink r hr β hβ) L β§
β f g : Flow (twoLink r hr β hβ),
IsFlow _ f β§ IsFeasible _ f β§ IsNashFlow _ f β§
IsFlow _ g β§ IsFeasible _ g β§ 0 < cost _ g β§
b < ENNReal.ofReal (cost _ f / cost _ g)) β§
(β (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.