Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 2 (corrected: Eq. (22) includes the duals of y ≤ Y) — D(x; d) = E u(x, Y; d)

Proved
RLPBidPrice.Directional.directional_derivative_eq_expected_u

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

convex-analysislinear-programmingp2o-batch-rm-cafterp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityrevenue-management

Let AAA be a 0/1 leg–itinerary incidence matrix with nonzero columns, r≥0r \ge 0r≥0 the fares, 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 JPI(x)=E v(x,Y)J^{PI}(x) = \mathbb{E}\, v(x, Y)JPI(x)=Ev(x,Y), where v(x,Y)=max⁡{r⊤y:Ay≤x, 0≤y≤Y}v(x, Y) = \max\{r^\top y : Ay \le x,\ 0 \le y \le Y\}v(x,Y)=max{r⊤y:Ay≤x, 0≤y≤Y}. For every direction d∈Rmd \in \mathbb{R}^md∈Rm the one-sided directional derivative of JPIJ^{PI}JPI at xxx exists and

D(x;d)=lim⁡h↓01h[JPI(x+hd)−JPI(x)]=E u(x,Y;d),D(x; d) = \lim_{h \downarrow 0} \frac{1}{h}\big[J^{PI}(x + hd) - J^{PI}(x)\big] = \mathbb{E}\, u(x, Y; d),D(x;d)=h↓0lim​h1​[JPI(x+hd)−JPI(x)]=Eu(x,Y;d),

where

u(x,Y;d)=min⁡{d⊤μ:μ≥0, L(x,μ)=min⁡μ′≥0L(x,μ′)},L(x,μ)=∑j=1nYj(rj−μ⊤Aj)++μ⊤x,u(x, Y; d) = \min\{d^\top \mu : \mu \ge 0,\ L(x, \mu) = \min_{\mu' \ge 0} L(x, \mu')\}, \qquad L(x, \mu) = \sum_{j=1}^n Y^j (r^j - \mu^\top A^j)^+ + \mu^\top x,u(x,Y;d)=min{d⊤μ:μ≥0, L(x,μ)=μ′≥0min​L(x,μ′)},L(x,μ)=j=1∑n​Yj(rj−μ⊤Aj)++μ⊤x,

is the least value of d⊤μd^\top\mud⊤μ over the optimal vectors of dual prices of the capacity constraints.

No condition on the demand distribution is assumed: the result covers the nondifferentiable case, where the dual prices are not unique with positive probability and the averaged dual prices only estimate a supergradient. Averaging u(x,Yi;d)u(x, Y_i; d)u(x,Yi​;d) over simulated demands gives an unbiased estimator of the directional derivative.

Formalization Note. The limit is one-sided, h→0+h \to 0^+h→0+ (nhdsWithin 0 (Set.Ioi 0)); the paper's Eq. (12) writes lim⁡h→0\lim_{h \to 0}limh→0​, whose two-sided version fails in the nondifferentiable case. x>0x > 0x>0 is implicit in the paper (it differentiates at a capacity vector; at a zero capacity a direction leaving {x≥0}\{x \ge 0\}{x≥0} makes the LP infeasible). uuu is a real sInf; for x>0x > 0x>0 and Y≥0Y \ge 0Y≥0 the optimal dual price set is nonempty and bounded, so uuu is an attained minimum and bounded uniformly in YYY. No integrability of YYY is needed: v(x,Y)v(x, Y)v(x,Y) is bounded by ∑jrjmax⁡ixi\sum_j r^j \max_i x^i∑j​rjmaxi​xi because every itinerary uses a leg. The time index kkk is dropped.

Correction. The paper defines uuu by Eq. (22), min⁡d⊤μ\min d^\top\mumind⊤μ subject to μ⊤x=vk(x,Y)\mu^\top x = v_k(x, Y)μ⊤x=vk​(x,Y), μ⊤A≤r\mu^\top A \le rμ⊤A≤r, μ≥0\mu \ge 0μ≥0, which omits the dual variables of y≤Yy \le Yy≤Y; with that uuu the proposition is false (one leg, one itinerary, r=1r = 1r=1, x=1x = 1x=1, YYY uniform on [0,2][0, 2][0,2], d=1d = 1d=1: D(x;d)=P(Y>1)=1/2D(x; d) = P(Y > 1) = 1/2D(x;d)=P(Y>1)=1/2 but the printed (22) gives Emin⁡(Y,1)=3/4\mathbb{E}\min(Y, 1) = 3/4Emin(Y,1)=3/4). Here uuu is taken over the optimal dual prices of the Lagrangian problem (14).

Preamble
import Mathlib
import Definitions.Def_RLPBidPrice_Directional_Model

open MeasureTheory Matrix
Formal statement
namespace RLPBidPrice.Directional

/-- Proposition 2, p. 212, with Eq. (22) corrected: at a capacity vector `x > 0` the one-sided
directional derivative `D(x; d)` of `J^PI` exists for every direction `d` and equals
`E u(x, Y; d)`. -/
theorem directional_derivative_eq_expected_u {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 ω)
    (d : Fin m → ℝ) :
    Filter.Tendsto (fun h : ℝ => h⁻¹ * (JPI P A r Y (x + h • d) - JPI P A r Y x))
      (nhdsWithin 0 (Set.Ioi 0)) (nhds (∫ ω, u A r x (Y ω) d ∂P)) := 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 2 (with Eq. (12), p. 210, and Eq. (22), p. 212)
Read-back

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

Fix natural numbers mmm and nnn. Let (Ω,F)(\Omega, \mathcal F)(Ω,F) be a measurable space with a probability measure PPP on it. The statement also takes:

  • a real m×nm \times nm×n matrix A=(Aij)i≤m, j≤nA = (A_{ij})_{i \le m,\, j \le n}A=(Aij​)i≤m,j≤n​ that satisfies the predicate IsIncidence(A)\mathrm{IsIncidence}(A)IsIncidence(A);
  • a vector r∈Rnr \in \mathbb R^nr∈Rn with rj≥0r_j \ge 0rj​≥0 for every jjj;
  • a vector x∈Rmx \in \mathbb R^mx∈Rm with xi>0x_i > 0xi​>0 for every iii (strictly positive in every coordinate);
  • a measurable map Y:Ω→RnY : \Omega \to \mathbb R^nY:Ω→Rn such that, for PPP-almost every ω\omegaω, every coordinate of Y(ω)Y(\omega)Y(ω) is ≥0\ge 0≥0;
  • an arbitrary direction d∈Rmd \in \mathbb R^md∈Rm, with no sign or size restriction.

IsIncidence\mathrm{IsIncidence}IsIncidence and two other objects come from the imported module Def_RLPBidPrice_Directional_Model, and their definitions are not part of the code shown here:

  • JP,A,r,YPI:Rm→RJ^{PI}_{P,A,r,Y} : \mathbb R^m \to \mathbb RJP,A,r,YPI​:Rm→R, a real-valued function of a capacity vector. It depends on PPP, AAA, rrr and YYY.
  • uA,r(x,y;d)∈Ru_{A,r}(x, y; d) \in \mathbb RuA,r​(x,y;d)∈R, a real number for a vector x∈Rmx \in \mathbb R^mx∈Rm, a vector y∈Rny \in \mathbb R^ny∈Rn and a direction d∈Rmd \in \mathbb R^md∈Rm.

This read-back cannot unfold these three definitions. Whatever they contain carries over into the statement's meaning unchanged. The same holds for any conventions they use, such as integrals, suprema, or the meaning of "incidence".

Conclusion. The difference quotient of JPIJ^{PI}JPI at xxx in direction ddd converges as hhh tends to 000 from the right (h>0h > 0h>0 only):

lim⁡h→0+JP,A,r,YPI(x+hd)−JP,A,r,YPI(x)h  =  ∫ΩuA,r(x, Y(ω); d) dP(ω).\lim_{h \to 0^+} \frac{J^{PI}_{P,A,r,Y}(x + h d) - J^{PI}_{P,A,r,Y}(x)}{h} \;=\; \int_\Omega u_{A,r}\big(x,\, Y(\omega);\, d\big)\, dP(\omega).h→0+lim​hJP,A,r,YPI​(x+hd)−JP,A,r,YPI​(x)​=∫Ω​uA,r​(x,Y(ω);d)dP(ω).

This claims two things: the one-sided limit exists, and it equals the stated value. The statement makes no claim about the two-sided limit or about h<0h < 0h<0. The right-hand side is a Bochner integral. No hypothesis says that ω↦uA,r(x,Y(ω);d)\omega \mapsto u_{A,r}(x, Y(\omega); d)ω↦uA,r​(x,Y(ω);d) is integrable, and no hypothesis says that YYY is integrable. If that function is not integrable (including when it is not measurable), the right-hand side is by convention 000, and the claim becomes that the quotient tends to 000.

Degenerate cases.

  • h=0h = 0h=0. It is excluded by the right-sided limit, so the convention 0−1=00^{-1} = 00−1=0 plays no role.
  • m=0m = 0m=0. The only vector xxx is the empty one, and the positivity hypothesis on xxx holds vacuously. The only direction is ddd = the empty vector, so x+hd=xx + hd = xx+hd=x and the quotient is identically 000. The statement then asserts exactly that ∫ΩuA,r(x,Y(ω);d) dP=0\int_\Omega u_{A,r}(x, Y(\omega); d)\, dP = 0∫Ω​uA,r​(x,Y(ω);d)dP=0.
  • d=0d = 0d=0 (any mmm). The quotient is identically 000, so the statement asserts ∫ΩuA,r(x,Y(ω);0) dP=0\int_\Omega u_{A,r}(x, Y(\omega); 0)\, dP = 0∫Ω​uA,r​(x,Y(ω);0)dP=0.
  • n=0n = 0n=0. rrr and YYY are the empty vector, and their hypotheses hold vacuously. The content then depends entirely on the imported definitions.
  • Ω\OmegaΩ. It is necessarily nonempty, because PPP is a probability measure. It may have a single point, in which case YYY is a single deterministic vector with nonnegative entries.
  • Hypotheses on AAA. Whether IsIncidence(A)\mathrm{IsIncidence}(A)IsIncidence(A) holds for any particular AAA, including when mmm or nnn is 000, is decided by the imported definition. This read-back cannot say whether it is ever satisfiable.
  • Imported definitions. If JPIJ^{PI}JPI is itself defined through integrals or suprema, their default-value conventions apply inside it: 000 for a non-integrable integrand, and junk values for empty or unbounded suprema. None of the hypotheses above rule those situations out.
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