Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 7.4 — the network problem and weighted proportional fairness agree

Proved
KellyStochasticNetworks.proportional_fair_iff

by naimengye · Sep 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

operations-researchoptimizationstochastic-networks

The network problem network(A,C;w)\mathrm{network}(A,C;w)network(A,C;w) is to maximize ∑rwrlog⁡xr\sum_r w_r\log x_r∑r​wr​logxr​ over the feasible flows x≥0x\ge0x≥0 with ∑s:j∈sxs≤Cj\sum_{s:j\in s}x_s\le C_j∑s:j∈s​xs​≤Cj​ for every resource jjj. A feasible vector xxx with every xr>0x_r>0xr​>0 is weighted proportionally fair when the aggregate of proportional changes to any other feasible allocation is non-positive:

∑rwr yr−xrxr  ≤  0for every feasible y.\sum_r w_r\,\frac{y_r-x_r}{x_r}\;\le\;0 \qquad\text{for every feasible } y .r∑​wr​xr​yr​−xr​​≤0for every feasible y.

Proposition 7.4: these are the same condition. A feasible xxx with positive components maximizes ∑rwrlog⁡xr\sum_r w_r\log x_r∑r​wr​logxr​ over the positive feasible flows if and only if it is weighted proportionally fair.

One direction is concavity of the logarithm: log⁡yr−log⁡xr≤(yr−xr)/xr\log y_r-\log x_r\le (y_r-x_r)/x_rlogyr​−logxr​≤(yr​−xr​)/xr​, so a non-positive aggregate of proportional changes forces ∑rwrlog⁡yr≤∑rwrlog⁡xr\sum_r w_r\log y_r\le\sum_r w_r\log x_r∑r​wr​logyr​≤∑r​wr​logxr​. The other is the first-order condition: the objective changes by ∑rwr δxr/xr+o(δx)\sum_r w_r\,\delta x_r/x_r+o(\delta x)∑r​wr​δxr​/xr​+o(δx) 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 ∑rwrlog⁡xr\sum_r w_r\log x_r∑r​wr​logxr​, 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 log⁡0\log 0log0 is not a real number and the book's optimum is interior. The fairness condition is quantified over all feasible yyy, including boundary points, exactly as the book states it; the quotient (yr−xr)/xr(y_r-x_r)/x_r(yr​−xr​)/xr​ is meaningful there because xr>0x_r>0xr​>0.

Preamble
import Mathlib
import Definitions.Def_KellyStochasticNetworks_Wardrop
import Definitions.Def_KellyStochasticNetworks_Congestion
Formal statement
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 KellyStochasticNetworks
Source
Kelly & Yudovina, Stochastic Networks, CUP 2014, pp. 159-160 (PDF pp. 167-168), the definition of weighted proportional fairness and Proposition 7.4: 'We say an allocation x = (x_r, r in R) is proportionally fair if it is feasible, and if for any other feasible allocation y the aggregate of proportional changes is non-positive: sum_r (y_r - x_r)/x_r <= 0.' 'Proposition 7.4 A vector x solves network(A, C; w) if and only if it is weighted proportionally fair.' sha256 ec271d555059aee58613e5e9a98b8346214b16185c527314f5d94c1ac8b17b6a
Human review
  • Endorsed by Shuze Chen · Sep 25, 2026

    Confirmed by the moderator at approval.

  • Endorsed by naimengye · Sep 25, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me