Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 1, p. 212 (formalized as: a fixed measurable dual selection) — (1/N) Σ μ(x, Yᵢ) converges a.s. to a supergradient of E v(x, Y)

Proved
RLPBidPrice.Directional.averaged_duals_supergradient

by mikedeng1 · Oct 3, 2026 · Mathlib 0df444a (Lean v4.33.1)

linear-programmingp2o-batch-rm-cafterp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityrevenue-managementstrong-law

Let AAA be a 0/1 incidence matrix with nonzero columns, r≥0r \ge 0r≥0, and xxx a capacity vector with every component xi>0x^i > 0xi>0. Let YYY be a measurable random demand vector on a probability space (Ω,P)(\Omega, P)(Ω,P) with Y≥0Y \ge 0Y≥0 almost surely, and let Y1,Y2,…Y_1, Y_2, \dotsY1​,Y2​,… be measurable random vectors, pairwise independent and each distributed as YYY. Model a linear programming algorithm that is "initialized with the same data on each run" as a measurable map f:Rn→Rmf : \mathbb{R}^n \to \mathbb{R}^mf:Rn→Rm returning, for every demand vector y≥0y \ge 0y≥0, an optimal vector of dual prices f(y)f(y)f(y) for (x,y)(x, y)(x,y) (a minimizer of L(x,⋅)L(x, \cdot)L(x,⋅) over μ≥0\mu \ge 0μ≥0); write μ(x,Yi)=f(Yi)\mu(x, Y_i) = f(Y_i)μ(x,Yi​)=f(Yi​). Then there is a vector g∈Rmg \in \mathbb{R}^mg∈Rm such that almost surely

lim⁡N→∞1N∑i=1Nμ(x,Yi)=g,\lim_{N \to \infty} \frac{1}{N} \sum_{i=1}^{N} \mu(x, Y_i) = g,N→∞lim​N1​i=1∑N​μ(x,Yi​)=g,

and ggg is a supergradient of JPI(x)=E v(x,Y)J^{PI}(x) = \mathbb{E}\, v(x, Y)JPI(x)=Ev(x,Y) at xxx:

JPI(z)≤JPI(x)+g⊤(z−x)for every capacity vector z≥0.J^{PI}(z) \le J^{PI}(x) + g^\top (z - x) \quad \text{for every capacity vector } z \ge 0.JPI(z)≤JPI(x)+g⊤(z−x)for every capacity vector z≥0.

The point of the proposition is the contrast with warm-started algorithms, whose returned duals depend on the history Y1,…,Yi−1Y_1, \dots, Y_{i-1}Y1​,…,Yi−1​ and whose averages need not converge.

Formalization Note. "Initialized with the same data on each run (e.g., it is not warm started with data from prior solutions)" is modelled by a fixed function fff of the current demand vector; its measurability is an added hypothesis (the paper does not discuss it; a measurable selection of optimal duals exists). "Always exists" is read as almost sure convergence, the strong-law sense in which it holds; the limit ggg is deterministic. The samples are the paper's "NNN independent samples of the demand vector" (p. 209); only pairwise independence is assumed. "Subgradient of Evk(x,Y)Ev_k(x, Y)Evk​(x,Y)" is the supergradient inequality on the feasible capacities z≥0z \ge 0z≥0 (JPIJ^{PI}JPI is concave). The time index kkk is dropped.

Preamble
import Mathlib
import Definitions.Def_RLPBidPrice_Directional_Model

open MeasureTheory Matrix
Formal statement
namespace RLPBidPrice.Directional

/-- Proposition 1, p. 212, formalized as: if the LP algorithm returns the same dual solution
`f y` whenever it is run on the demand `y` (a fixed measurable function of the data), then for
i.i.d. demand samples the running average of the returned dual prices converges almost surely
to a deterministic vector `g`, and `g` is a supergradient of `J^PI` at `x`. -/
theorem averaged_duals_supergradient {m n : ℕ} {Ω : Type*} [MeasurableSpace Ω]
    (P : Measure Ω) [IsProbabilityMeasure P]
    (A : Matrix (Fin m) (Fin n) ℝ) (r : Fin n → ℝ) (hA : IsIncidence A) (hr : 0 ≤ r)
    (x : Fin m → ℝ) (hx : ∀ i, 0 < x i)
    (Y : Ω → Fin n → ℝ) (hYm : Measurable Y) (hY : ∀ᵐ ω ∂P, 0 ≤ Y ω)
    (f : (Fin n → ℝ) → (Fin m → ℝ)) (hfm : Measurable f)
    (hf : ∀ y : Fin n → ℝ, 0 ≤ y → IsDualOpt A r x y (f y))
    (Ys : ℕ → Ω → Fin n → ℝ) (hYsm : ∀ k, Measurable (Ys k))
    (hind : Pairwise fun k l => ProbabilityTheory.IndepFun (Ys k) (Ys l) P)
    (hident : ∀ k, ProbabilityTheory.IdentDistrib (Ys k) Y P P) :
    ∃ g : Fin m → ℝ,
      (∀ᵐ ω ∂P, Filter.Tendsto
        (fun N : ℕ => (N : ℝ)⁻¹ • ∑ k ∈ Finset.range N, f (Ys k ω))
        Filter.atTop (nhds g)) ∧
      ∀ z : Fin m → ℝ, 0 ≤ z → JPI P A r Y z ≤ JPI P A r Y x + g ⬝ᵥ (z - x) := by sorry

end RLPBidPrice.Directional
Source
Talluri, van Ryzin, A Randomized Linear Programming Method for Computing Network Bid Prices, Transp. Sci. 33(2), 1999, p. 212, Proposition 1
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Setting. Let m,n∈Nm, n \in \mathbb{N}m,n∈N, let Ω\OmegaΩ be a measurable space, and let PPP be a probability measure on Ω\OmegaΩ. Let AAA be a real m×nm \times nm×n matrix and r∈Rnr \in \mathbb{R}^nr∈Rn. All vector inequalities are componentwise.

Hypotheses.

  • AAA is an incidence matrix: every entry is 000 or 111, and every column has at least one nonzero entry.
  • r≥0r \ge 0r≥0.
  • x∈Rmx \in \mathbb{R}^mx∈Rm with xi>0x_i > 0xi​>0 for every iii.
  • Y:Ω→RnY : \Omega \to \mathbb{R}^nY:Ω→Rn is measurable, and Y(ω)≥0Y(\omega) \ge 0Y(ω)≥0 for PPP-almost every ω\omegaω.
  • f:Rn→Rmf : \mathbb{R}^n \to \mathbb{R}^mf:Rn→Rm is a single measurable function such that, for every y≥0y \ge 0y≥0, f(y)f(y)f(y) is an optimal dual price at (x,y)(x, y)(x,y). That is, f(y)≥0f(y) \ge 0f(y)≥0 and f(y)f(y)f(y) minimises
μ′↦∑jyjmax⁡(0, rj−∑iμi′Aij)+μ′⋅x\mu' \mapsto \sum_j y_j \max\Big(0,\ r_j - \sum_i \mu'_i A_{ij}\Big) + \mu'\cdot xμ′↦j∑​yj​max(0, rj​−i∑​μi′​Aij​)+μ′⋅x

over μ′≥0\mu' \ge 0μ′≥0. Nothing is required of f(y)f(y)f(y) when y≱0y \not\ge 0y≥0.

  • Y0,Y1,Y2,⋯:Ω→RnY_0, Y_1, Y_2, \dots : \Omega \to \mathbb{R}^nY0​,Y1​,Y2​,⋯:Ω→Rn are measurable and pairwise independent under PPP. Mutual independence is not required.
  • Each YkY_kYk​ has the same distribution under PPP as YYY.

Definitions used.

  • v(z,y0)=sup⁡{ r⋅y:Ay≤z, 0≤y≤y0 }v(z,y_0) = \sup\{\, r\cdot y : Ay \le z,\ 0 \le y \le y_0 \,\}v(z,y0​)=sup{r⋅y:Ay≤z, 0≤y≤y0​}, which is 000 if the set is empty.
  • J(z)=∫Ωv(z,Y(ω)) dP(ω)J(z) = \int_\Omega v(z, Y(\omega))\, dP(\omega)J(z)=∫Ω​v(z,Y(ω))dP(ω), the Bochner integral, which is 000 if the integrand is not integrable.

Conclusion. There exists a vector g∈Rmg \in \mathbb{R}^mg∈Rm such that both of the following hold:

  1. For PPP-almost every ω\omegaω,
1N∑k=0N−1f(Yk(ω))  ⟶  gas N→∞.\frac{1}{N} \sum_{k=0}^{N-1} f\big(Y_k(\omega)\big) \;\longrightarrow\; g \quad \text{as } N \to \infty .N1​k=0∑N−1​f(Yk​(ω))⟶gas N→∞.

At N=0N = 0N=0 the prefactor 1/01/01/0 is taken as 000. This term does not affect the limit. 2. For every z∈Rmz \in \mathbb{R}^mz∈Rm with z≥0z \ge 0z≥0,

J(z)≤J(x)+g⋅(z−x).J(z) \le J(x) + g\cdot(z-x).J(z)≤J(x)+g⋅(z−x).

The statement does not say how ggg relates to fff or YYY beyond these two properties. In particular, it does not identify ggg with any expectation. No integrability of YYY is assumed, so J(x)J(x)J(x) and J(z)J(z)J(z) are the true integrals only when those integrands are integrable, and 000 otherwise.

Degenerate cases.

  • If m=0m = 0m=0: the incidence hypothesis forces n=0n = 0n=0. Then ggg is the unique element of R0\mathbb{R}^0R0 and both claims are trivial.
  • If n=0n = 0n=0 and m≥1m \ge 1m≥1: optimality forces f(y)=0f(y) = 0f(y)=0, so the averages are 000. Then g=0g = 0g=0 works, since J≡0J \equiv 0J≡0 on z≥0z \ge 0z≥0.
  • The hypothesis on fff may be unsatisfiable for some data (for example, if some y≥0y \ge 0y≥0 has no minimiser, or no measurable choice exists). In that case the statement is vacuous.
Human review
  • Endorsed by Shuze Chen · Oct 21, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 21, 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