Proposition 2.2, p. 6 — f is a Nash flow iff every used path of a commodity is a shortest path
ProvedPoAIndep.Topology.proposition_2_2nash-flowp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1selfish-routingwardrop-equilibrium
Let be an instance (latency functions nonnegative, differentiable and nondecreasing on ) and let be a flow. Then is at Nash equilibrium in the sense of Definition 2.1 if and only if, for every commodity and all simple – paths with ,
In words: in a Nash flow all flow travels on minimum-latency paths. The page derives it from Definition 2.1 by letting the moved amount tend to , using continuity and monotonicity of the edge latencies. It is the working characterization of Nash flows used in Proposition 2.3 and Lemma 3.7.
Formalization Note. The hypothesis that is a flow (nonnegative, supported on simple – paths) is the paper's standing setting; feasibility is not needed.
Preamble
import Mathlib import Definitions.Def_PoAIndep_Topology_Model
Formal statement
namespace PoAIndep.Topology
theorem proposition_2_2 {V E : Type} [Fintype V] [DecidableEq V] [Fintype E]
[DecidableEq E] (I : Instance V E) (f : Flow I) (hf : IsFlow I f) :
IsNashFlow I f ↔
∀ (i : Fin I.k) (P₁ P₂ : List E),
IsSimplePath I.src I.tgt P₁ (I.s i) (I.t i) →
IsSimplePath I.src I.tgt P₂ (I.s i) (I.t i) →
0 < f i P₁ → pathLatency I f P₁ ≤ pathLatency I f P₂ := by sorry
end PoAIndep.Topology
Source
Roughgarden, The price of anarchy is independent of the network topology (journal-version manuscript, Dec. 23, 2002), p. 6, Proposition 2.2 (with the sentence preceding it on p. 5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.