Kuhn–Tucker conditions (10) for μ*: expected leg demand above the bid prices ≤ capacity, with complementary slackness
ProvedBidPriceControl.Asymptotic.kuhn_tucker_conditionsAssume the standing assumptions of §1; in particular the marginals of are continuous on . Let be an optimal solution of (9). Then for every leg ,
In words, the expected number of seats of leg requested at revenues above the bid prices does not exceed its capacity, and equals it when the leg's bid price is positive.
Formalization Note. The paper prints (10) as , , . With that sign and , expected demand would exceed capacity, which contradicts the paper's own reading of (10) on p. 1584 and its use on p. 1585. The statement uses the corrected sign, slack , with eliminated. Only the necessity direction is stated.
import Mathlib import Definitions.Def_BidPriceControl_Asymptotic_Model
namespace BidPriceControl.Asymptotic
open MeasureTheory ProbabilityTheory
/-- The Kuhn–Tucker conditions (10) (pp. 1583–1584), with the sign of the slack corrected: if the
marginals of the `R_t^j` are continuous on `(0, +∞)` (standing assumptions of §1), an optimal
solution `μ*` of (9) satisfies, for every leg `i`,
`∑_{t=1}^k ∑_j P(R_t^j > μ*A^j) a_ij ≤ x^i` and `μ*^i (x^i − ∑_{t=1}^k ∑_j P(R_t^j > μ*A^j) a_ij) = 0`
(the slack `λ^i = x^i − ∑_t ∑_j P(R_t^j > μ*A^j) a_ij ≥ 0` and `λ^i μ*^i = 0`). -/
theorem kuhn_tucker_conditions {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) (i : Fin m) :
∑ t ∈ Finset.Icc 1 k, ∑ j, exceedProb A F μstar t j * (A i j : ℝ) ≤ (x i : ℝ) ∧
μstar i * ((x i : ℝ) - ∑ t ∈ Finset.Icc 1 k, ∑ j, exceedProb A F μstar t j * (A i j : ℝ))
= 0 := by sorry
end BidPriceControl.Asymptotic
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Data. The theorem takes , measures on , , , a vector and a leg .
Hypotheses.
- For each , is a request law: a probability measure, a.s. nonnegative with at most one positive coordinate, no atom of any at a positive value, and integrable coordinates.
- minimizes the relaxed value: , and for all , where
Conclusion. Write , with strict inequality. Then both
hold.
Degenerate cases.
- No minimizer: if no minimizer exists for the given data, the statement asserts nothing.
- : it asserts and .
- : the sums are , with the same conclusions as .
- Zero capacity: if , it asserts for every and every with .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.