Eq. (16): Σ_{t≤θk} Σ_j P(R_t^j(θ) > μ*A^j) μ*A^j = θ μ*x
ProvedBidPriceControl.Asymptotic.bid_price_revenue_identityoptimizationp2o-batch-rm-cafterp2o-gran-per-chapterp2o-plan-paperp2o-v1revenue-management
Assume the standing assumptions of §1 and let be an optimal solution of (9) for . For every integer ,
Complementary slackness in (10) says that legs with a positive bid price are exactly filled in expectation. So the expected bid-price value of the requests the alternate system accepts equals the bid-price value of the scaled capacity.
Formalization Note. is exceedProb under the scaled laws scaledLaw F θ; .
Preamble
import Mathlib import Definitions.Def_BidPriceControl_Asymptotic_Model
Formal statement
namespace BidPriceControl.Asymptotic
open MeasureTheory ProbabilityTheory
/-- Display (16) of the proof of Theorem 1 (p. 1586): by the Kuhn–Tucker conditions (10), for an
optimal solution `μ*` of (9) for `(x, k)` and every integer `θ ≥ 1`,
`μ*(∑_{t=1}^{θk} ∑_j P(R_t^j(θ) > μ*A^j) A^j − θx) = 0`, so that
`∑_{t=1}^{θk} ∑_j P(R_t^j(θ) > μ*A^j) μ*A^j = θ μ*x`. -/
theorem bid_price_revenue_identity {m n : ℕ} (A : Fin m → Fin n → ℕ)
(F : ℕ → Measure (Fin n → ℝ)) (k : ℕ) (x : Fin m → ℕ)
(hF : ∀ t ∈ Finset.Icc 1 k, IsRequestLaw (F t))
(μstar : Fin m → ℝ) (hmin : IsRelaxedMinimizer A F k x μstar) (θ : ℕ) (hθ : 1 ≤ θ) :
∑ t ∈ Finset.Icc 1 (θ * k), ∑ j, exceedProb A (scaledLaw F θ) μstar t j * bidSum A μstar j
= (θ : ℝ) * ∑ i, μstar i * (x i : ℝ) := by sorry
end BidPriceControl.Asymptotic
Source
Talluri, van Ryzin, An Analysis of Bid-Price Controls for Network Revenue Management, Management Sci. 44(11), 1998, p. 1586, eq. (16)
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Data. The theorem takes , measures on , , , and with .
Hypotheses.
- For , is a request law: a probability measure, a.s. nonnegative with at most one positive coordinate, no positive-value atoms, and integrable coordinates.
- minimizes over , where .
Conclusion.
Degenerate cases.
- No minimizer: if none exists, the statement is vacuous.
- or : the left side is , so the claim is .
- : both sides are .
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.