Exercise 8.4 — the characterization
ProvedKellyStochasticNetworks.alpha_fair_kktThe -fair allocation is characterized by Karush–Kuhn–Tucker conditions. Let be a Lagrange multiplier for the capacity constraint at resource , and write for the total price along route . Suppose a positive rate vector and multipliers satisfy
- the stationarity condition for every route ;
- primal feasibility: for every resource ;
- dual feasibility: for every resource ;
- complementary slackness: for every — a resource with a positive price is saturated.
Then the aggregate rates maximize the -fair objective over the feasible set.
The stationarity condition is the informative one. A route's rate depends on the network only through the sum of the prices of the resources it uses, and the exponent controls how sharply a route reacts to that price: small makes rates very sensitive, so capacity concentrates on cheap routes and throughput is maximized, while large flattens the response towards max-min fairness.
Formalization Note The route price is introduced as a named quantity with its defining identity as a hypothesis, which keeps the statement readable and matches the book's notation. The conclusion is maximality of the aggregate rates over the feasible set intersected with the positive orthant, since the objective involves real powers and a logarithm.
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop import Definitions.Def_KellyStochasticNetworks_Congestion import Definitions.Def_KellyStochasticNetworks_FlowLevel
namespace KellyStochasticNetworks
theorem alpha_fair_kkt {J R : ℕ} (A : Fin J → Fin R → ℝ) (C : Fin J → ℝ)
(w n : Fin R → ℝ) (α : ℝ) (hα : 0 < α)
(hA : ∀ j r, A j r = 0 ∨ A j r = 1) (hw : ∀ r, 0 < w r) (hn : ∀ r, 0 < n r)
(x p : Fin R → ℝ) (q : Fin J → ℝ) (hxpos : ∀ r, 0 < x r)
(hp : ∀ r, p r = ∑ j, A j r * q j) (hppos : ∀ r, 0 < p r)
(hprimal : ∀ j, (∑ r, A j r * (n r * x r)) ≤ C j)
(hdual : ∀ j, 0 ≤ q j)
(hslack : ∀ j, q j * (C j - ∑ r, A j r * (n r * x r)) = 0)
(hstat : ∀ r, x r = (w r / p r) ^ (1 / α)) :
IsMaxOn (alphaFairObjective w n α)
({X | ∀ j, (∑ r, A j r * X r) ≤ C j} ∩ {X | ∀ r, 0 < X r})
(fun r => n r * x r) := by sorry
end KellyStochasticNetworksConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.