Lemma 4.4 — a flow feasible for costs at least
ProvedSelfishRouting.Linear.lemma_4_4Let every edge have a linear latency with , let the rates be positive and the route incidences , and let be an optimal flow for the rates . Let be the minimum marginal cost of increasing flow on an - path with respect to . Then for every , every flow feasible for the rates satisfies
The per-unit cost of pushing additional traffic through the network is at least the current minimum marginal path cost; this is what bounds the cost of augmenting the optimal flow for to a flow for in Theorem 4.5.
Formalization Note The rates are . is the minimum of the marginal path costs over the routes serving (see the definition item; the routes form a nonempty finite set because and is feasible). The hypothesis is kept as printed. Routes are incidence columns (a disclosed generalization).
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop import Definitions.Def_SelfishRouting_Linear_Model import Definitions.Def_SelfishRouting_Linear_LinearLatency
namespace SelfishRouting.Linear
open KellyStochasticNetworks
/-- Lemma 4.4 (p. 16): with linear latencies, if `f*` is optimal for the rates `r` and
`δ > 0`, then every flow feasible for the rates `(1 + δ) r` has cost at least
`C(f*) + δ ∑ᵢ L*ᵢ(f*) rᵢ`. -/
theorem lemma_4_4 {J R Sd : ℕ} (A : Fin J → Fin R → ℝ) (hA : ∀ j r, A j r = 0 ∨ A j r = 1)
(s : Fin R → Fin Sd) (rate : Fin Sd → ℝ) (hrate : ∀ i, 0 < rate i)
(a b : Fin J → ℝ) (ha : ∀ j, 0 ≤ a j) (hb : ∀ j, 0 ≤ b j)
(xstar : Fin R → ℝ) (hxstar : IsOptimalFlow A s (linLatency a b) rate xstar)
(δ : ℝ) (hδ : 0 < δ)
(y : Fin R → ℝ) (hy : y ∈ wardropFeasible s (fun i => (1 + δ) * rate i)) :
SelfishRouting.Bicriteria.cost A (linLatency a b) xstar +
δ * ∑ i, minMarginalPathCost A s a b xstar i * rate i ≤
SelfishRouting.Bicriteria.cost A (linLatency a b) y := by sorry
end SelfishRouting.Linear
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.