Proposition 7.4 — the network problem and weighted proportional fairness agree
ProvedKellyStochasticNetworks.proportional_fair_iffThe network problem is to maximize over the feasible flows with for every resource . A feasible vector with every is weighted proportionally fair when the aggregate of proportional changes to any other feasible allocation is non-positive:
Proposition 7.4: these are the same condition. A feasible with positive components maximizes over the positive feasible flows if and only if it is weighted proportionally fair.
One direction is concavity of the logarithm: , so a non-positive aggregate of proportional changes forces . The other is the first-order condition: the objective changes by under a perturbation, so optimality gives the inequality infinitesimally, and concavity extends it to non-infinitesimal variations.
The equivalence is what lets Theorem 7.6 be read as a fairness statement: the primal algorithm converges to the maximizer of an objective whose first term is , and therefore to the proportionally fair allocation. By Remark 7.5 that allocation is also the Nash bargaining solution and a market-clearing equilibrium.
Formalization Note The maximum is taken over the feasible set intersected with the positive orthant, since is not a real number and the book's optimum is interior. The fairness condition is quantified over all feasible , including boundary points, exactly as the book states it; the quotient is meaningful there because .
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop import Definitions.Def_KellyStochasticNetworks_Congestion
namespace KellyStochasticNetworks
theorem proportional_fair_iff {J R : ℕ} (A : Fin J → Fin R → ℝ) (C : Fin J → ℝ)
(w : Fin R → ℝ) (hA : ∀ j r, 0 ≤ A j r) (hw : ∀ r, 0 < w r)
(x : Fin R → ℝ) (hxpos : ∀ r, 0 < x r) (hxfeas : x ∈ networkFeasible A C) :
IsMaxOn (networkObjective w) (networkFeasible A C ∩ {y | ∀ r, 0 < y r}) x
↔ ∀ y ∈ networkFeasible A C, (∑ r, w r * ((y r - x r) / x r)) ≤ 0 := by sorry
end KellyStochasticNetworksConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.