Theorem 1 (corrected: C1 on [A I], independent demands) — ∇ₓE v(x, Y) = E ∇ₓv(x, Y) = E μ(x, Y)
ProvedRLPBidPrice.Unbiased.theorem1_unbiased_gradientLet be an 0/1 leg–itinerary incidence matrix with nonzero columns, the fares, and a capacity vector satisfying Condition C1′ (whenever lies in the span of a set of columns of , that set spans ). Let be a random demand vector on a probability space : measurable, almost surely, with mutually independent components satisfying Condition 2 ( continuous for every ). Let and . Then:
- is differentiable at almost surely;
- is differentiable at and (the derivative of at is the expectation of the pathwise derivatives);
- for every random vector that is (almost everywhere strongly) measurable and almost surely an optimal dual price vector for the capacity constraints (a minimizer of over , Eq. (14)), has gradient at :
This is the paper's main result: the randomized linear programming estimate of the bid prices is an unbiased estimator of the gradient of the expected perfect-information revenue.
Formalization Note. The time index is dropped. Gradients are Fréchet derivatives on (with its sup norm; differentiability does not depend on the norm); in part 3 the derivative is the functional , i.e. the gradient is the vector of expected dual prices. Part 2 needs no dual selection; part 3 quantifies over measurable selections, because the expectation of a non-measurable selection is not defined. No integrability hypothesis on is made: .
Correction. The printed theorem assumes Condition 1 and Condition 2 only and is false. (i) Condition 1 is applied to the columns of (C1′): with having rows , , and i.i.d. uniform on , Conditions 1 and 2 hold but has one-sided slopes of about and in the second coordinate at . (ii) The components of are mutually independent: with one leg, , fares and , uniform on , the LP is degenerate almost surely and has a kink at .
import Mathlib import Definitions.Def_RLPBidPrice_Unbiased_Model open MeasureTheory Matrix
namespace RLPBidPrice.Unbiased
theorem theorem1_unbiased_gradient {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (r : Fin n → ℝ)
(hA : IsIncidence A) (hr : 0 ≤ r) (x : Fin m → ℝ) (hx : 0 ≤ x)
(hC1 : ConditionOnePrime A x)
{Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(Y : Ω → Fin n → ℝ) (hYm : Measurable Y) (hY0 : ∀ᵐ ω ∂P, 0 ≤ Y ω)
(hC2 : ConditionTwo P Y) (hind : ProbabilityTheory.iIndepFun (fun j ω => Y ω j) P) :
(∀ᵐ ω ∂P, DifferentiableAt ℝ (fun x' => piValue A r x' (Y ω)) x) ∧
HasFDerivAt (JPI P A r Y) (∫ ω, fderiv ℝ (fun x' => piValue A r x' (Y ω)) x ∂P) x ∧
(∀ μ : Ω → Fin m → ℝ, AEStronglyMeasurable μ P →
(∀ᵐ ω ∂P, IsDualOpt A r x (Y ω) (μ ω)) →
HasFDerivAt (JPI P A r Y) (gradCLM (fun i => ∫ ω, μ ω i ∂P)) x) := by sorry
end RLPBidPrice.Unbiased
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
The statement fixes natural numbers , a real matrix , a vector , and a point . It also fixes a measurable space with a probability measure , and a random vector with coordinates .
Several notions come from the imported module Def_RLPBidPrice_Unbiased_Model. Their definitions are not part of the code shown to me, so I cannot expand them. They are named here as opaque predicates and functions:
- , a property of the matrix;
- , a property of the matrix and the point;
- , a property of the measure and the random vector;
- , a quantity depending on , , a point and a vector ;
- , a function of ;
- , a relation between the data and a vector ;
- , which turns a vector in into a continuous linear map.
The auditor must check these definitions separately. In particular, whether they are satisfiable, and whether is really an expectation of , cannot be read off this statement.
Hypotheses. Inequalities between vectors are componentwise.
- holds.
- .
- .
- holds.
- is measurable for the product Borel structure on .
- for -almost every .
- holds.
- The coordinate random variables are mutually independent under .
Conclusion. Under these hypotheses, all three of the following hold.
(i) Almost-sure differentiability. For -almost every , the map
is Fréchet differentiable at the given point . This map is defined on all of , including points with negative coordinates.
(ii) Derivative as an integral. is Fréchet differentiable at , and its derivative there is the continuous linear map
This is a Bochner integral in the space of continuous linear maps. Pointwise, the integrand is taken to be the zero map at any where the map in (i) is not differentiable at . If the integrand is not Bochner-integrable, the integral is by convention the zero map. In that case the statement asserts that .
(iii) Derivative from dual solutions. Take any map with components . Suppose that:
- is almost-everywhere strongly measurable with respect to ; and
- for -almost every , holds.
Then is Fréchet differentiable at with derivative
Integrability of the is not assumed. Any that is not -integrable contributes the value in that coordinate. Part (iii) is a universally quantified implication. If no such exists, it holds vacuously. If several exist, it forces every one of them to give the same derivative.
Degenerate cases.
- : is a probability measure, so cannot be empty.
- : is a single point, and every continuous linear map out of it is zero. Parts (i)–(iii) then hold for any functions whatsoever, so the statement carries no content beyond the consistency of its hypotheses.
- : and are empty vectors. Hypotheses 2, 5, 6 and 8 hold trivially, and everything rests on the opaque definitions.
- Constant : a degenerate distribution, such as a constant almost surely, is permitted. Nothing excludes it besides whatever requires.
- Unsatisfiable hypotheses: since , and are not visible here, I cannot tell whether they can hold at all. If any of them is unsatisfiable, for example at or for particular , the whole theorem is vacuous in those cases.
- Zero conventions: as noted in (ii) and (iii), the zero conventions for non-integrable integrands and non-differentiable points mean the stated derivative formulas can silently evaluate to the zero map.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.