Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The weighted α\alphaα-fair objective

Definition
KellyStochasticNetworks_FlowLevel

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

operations-researchoptimizationstochastic-networks

The objective of the weighted α\alphaα-fair rate allocation of Chapter 8 of Kelly and Yudovina, Stochastic Networks, written in the aggregate variables of problem (8.4).

Let nrn_rnr​ be the number of flows active on route rrr, each allocated rate xrx_rxr​, so that route rrr consumes Xr=nrxrX_r = n_r x_rXr​=nr​xr​ at every resource it uses. Given weights wr>0w_r > 0wr​>0 and a parameter α∈(0,∞)\alpha \in (0, \infty)α∈(0,∞), the weighted α\alphaα-fair allocation maximizes

G(X)=∑rwrnrα Xr1−α1−α(α≠1),G(X)=∑rwrnrlog⁡Xr(α=1),G(X) = \sum_r w_r n_r^{\alpha}\,\frac{X_r^{1-\alpha}}{1-\alpha} \qquad (\alpha \ne 1), \qquad\qquad G(X) = \sum_r w_r n_r \log X_r \qquad (\alpha = 1),G(X)=r∑​wr​nrα​1−αXr1−α​​(α=1),G(X)=r∑​wr​nr​logXr​(α=1),

subject to ∑r:j∈rXr≤Cj\sum_{r : j \in r} X_r \le C_j∑r:j∈r​Xr​≤Cj​ for every resource jjj, over X≥0X \ge 0X≥0.

The two cases are the same function in disguise: the derivative is wrnrαXr−αw_r n_r^{\alpha}X_r^{-\alpha}wr​nrα​Xr−α​ for every α∈(0,∞)\alpha \in (0,\infty)α∈(0,∞), which is the point of Exercise 8.3, and the α=1\alpha = 1α=1 branch is the natural continuation of the family through the removable singularity at α=1\alpha = 1α=1.

The family interpolates between the fairness notions of Chapter 7. As α→0\alpha \to 0α→0 with w≡1w \equiv 1w≡1 the total throughput approaches its maximum; at α=1\alpha = 1α=1 the rates are weighted proportionally fair; at α=2\alpha = 2α=2 with wr=1/Tr2w_r = 1/T_r^2wr​=1/Tr2​ they are TCP fair; and as α→∞\alpha \to \inftyα→∞ with w≡1w \equiv 1w≡1 they approach max-min fairness.

Formalization Note The objective is written in the aggregate rates Xr=nrxrX_r = n_r x_rXr​=nr​xr​ of problem (8.4) rather than the per-flow rates of (8.1). The two problems are equivalent, but in (8.4) the feasible set does not depend on nnn, which is the form the stability argument uses; that feasible set is the networkFeasible published in mission VII of this series. Powers are real exponents, so the objective is meaningful where the flow counts and rates are positive. The case split at α=1\alpha = 1α=1 is explicit, exactly as the book defines it.

Definition code
import Mathlib
import Definitions.Def_KellyStochasticNetworks_Wardrop
import Definitions.Def_KellyStochasticNetworks_Congestion

namespace KellyStochasticNetworks

/-- The objective of the **weighted α-fair** allocation problem, written in the variables
`X_r = n_r x_r` of problem (8.4):
`G(X) = ∑_r w_r n_r^α X_r^{1-α}/(1-α)` for `α ≠ 1`, and `∑_r w_r n_r log X_r` for `α = 1`.
Kelly–Yudovina, *Stochastic Networks*, pp. 188 and 190. -/
noncomputable def alphaFairObjective {R : ℕ} (w n : Fin R → ℝ) (α : ℝ) (X : Fin R → ℝ) : ℝ :=
  if α = 1 then ∑ r, w r * n r * Real.log (X r)
  else ∑ r, w r * n r ^ α * (X r ^ (1 - α) / (1 - α))

end KellyStochasticNetworks
Source
Kelly & Yudovina, Stochastic Networks, CUP 2014, ch. 8, pp. 188 and 190 (PDF pp. 196 and 198): the weighted alpha-fair allocation problem (8.1) p. 188, and its rewriting (8.4) in the variables X_r = n_r x_r p. 190. sha256 ec271d555059aee58613e5e9a98b8346214b16185c527314f5d94c1ac8b17b6a

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