Theorem 7.6 — global stability of the primal algorithm
ProvedKellyStochasticNetworks.primal_global_stabilityConsider a network with resources and routes, link-route incidence matrix , weights , gains , and congestion functions that are non-negative, continuous, increasing and not identically zero. The primal algorithm is the differential equation
and its Lyapunov function is
Let be a point of the positive orthant at which the drift vanishes, that is for every . Then two things hold.
- maximizes over the positive orthant.
- Every trajectory of the primal algorithm that starts in the positive orthant and stays there converges to as .
This is Theorem 7.6, and it is the chapter's central claim: a control rule in which no participant knows the network topology, and each source sees only its own rate and the congestion signals reaching it, drives the whole system to the unique maximizer of a global utility. Because the first term of is , that maximizer is the weighted proportionally fair allocation, so the protocol's limit is a fairness criterion rather than an accident of the dynamics.
The first conclusion is strict concavity plus stationarity. The second is the harder half: increases along trajectories by equation (7.7), but that alone leaves open whether the trajectory might stall short of , and ruling that out needs the compactness of the sublevel set together with a uniform lower bound on the derivative away from .
Formalization Note A trajectory is a differentiable function of real time whose derivative equals the primal drift at every non-negative time, with positivity along the trajectory assumed rather than derived; invariance of the positive orthant under the dynamics is a separate statement. The equilibrium is given by its stationarity condition rather than by an existence claim, and that it is the maximizer is part of the conclusion, so nothing is assumed about it that is not also proved.
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop import Definitions.Def_KellyStochasticNetworks_Congestion
namespace KellyStochasticNetworks
theorem primal_global_stability {J R : ℕ} (A : Fin J → Fin R → ℝ) (w κ : Fin R → ℝ)
(p : Fin J → ℝ → ℝ) (hA : ∀ j r, A j r = 0 ∨ A j r = 1)
(hw : ∀ r, 0 < w r) (hκ : ∀ r, 0 < κ r)
(hp : ∀ j, Continuous (p j)) (hpmono : ∀ j, Monotone (p j))
(hpnn : ∀ j y, 0 ≤ p j y) (hpne : ∀ j, ∃ y, p j y ≠ 0)
(xbar : Fin R → ℝ) (hbarpos : ∀ r, 0 < xbar r)
(hbar : ∀ r, w r = xbar r * ∑ j, A j r * p j (linkFlow A xbar j))
(x : ℝ → Fin R → ℝ) (hxpos : ∀ t, 0 ≤ t → ∀ r, 0 < x t r)
(hode : ∀ t, 0 ≤ t → ∀ r,
HasDerivAt (fun s => x s r) (primalDrift A w κ p (x t) r) t) :
IsMaxOn (primalUtility A w p) {y : Fin R → ℝ | ∀ r, 0 < y r} xbar
∧ Filter.Tendsto x Filter.atTop (nhds xbar) := by sorry
end KellyStochasticNetworksConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.