Lemma 3.7, p. 12 — a Nash flow is a min-cost flow for the costs ℓₑ(fₑ): Σₑ ℓₑ(fₑ)fₑ ≤ Σₑ ℓₑ(fₑ)f*ₑ
ProvedPoAIndep.Topology.lemma_3_7min-cost-flownash-flowp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1selfish-routing
Let be an instance, let be a feasible flow at Nash equilibrium and let be any feasible flow. Then
That is, a Nash flow is a minimum-cost flow, in the classical sense, for the fixed edge costs . In Theorem 3.8 it shows that the error term is nonnegative.
Formalization Note. The page says " be at Nash equilibrium and feasible for instance "; the formal statement reads "feasible" as applying to as well, since the proof invokes Proposition 2.3, which requires it, and the inequality fails for a Nash flow routing larger rates.
Preamble
import Mathlib import Definitions.Def_PoAIndep_Topology_Model
Formal statement
namespace PoAIndep.Topology
theorem lemma_3_7 {V E : Type} [Fintype V] [DecidableEq V] [Fintype E]
[DecidableEq E] (I : Instance V E) (f g : Flow I) (hf : IsFlow I f) (hfeas : IsFeasible I f)
(hnash : IsNashFlow I f) (hg : IsFlow I g) (hgfeas : IsFeasible I g) :
∑ e, I.ℓ e (edgeFlow I f e) * edgeFlow I f e ≤
∑ e, I.ℓ e (edgeFlow I f e) * edgeFlow I g e := by sorry
end PoAIndep.Topology
Source
Roughgarden, The price of anarchy is independent of the network topology (journal-version manuscript, Dec. 23, 2002), p. 12, Lemma 3.7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.