Lemma 1: for any μ ≥ 0, J_k(x) ≤ J̄_k(x, μ)
ProvedBidPriceControl.Asymptotic.lemma1_upper_boundUnder the standing assumptions of §1 on the request laws , for every bid-price vector the optimal expected revenue of the Bellman equations (2)–(3) is bounded by the relaxed value (8):
Minimizing the right side over gives the upper bound of (9), the benchmark against which the heuristic is measured.
Formalization Note. The paper defines as the value (7) of a relaxed control problem and evaluates it as (8). This item takes (8) as the definition, so it is Lemma 1 combined with the evaluation (8).
import Mathlib import Definitions.Def_BidPriceControl_Asymptotic_Model
namespace BidPriceControl.Asymptotic
open MeasureTheory ProbabilityTheory
/-- Lemma 1 (p. 1583), with the relaxed value in its evaluated form (8): under the standing
assumptions of §1, for any `μ ≥ 0`, `J_k(x) ≤ J̄_k(x, μ)`, where `J` is the optimal expected revenue
of the Bellman equations (2)–(3). -/
theorem lemma1_upper_bound {m n : ℕ} (A : Fin m → Fin n → ℕ) (F : ℕ → Measure (Fin n → ℝ))
(k : ℕ) (x : Fin m → ℕ) (hF : ∀ t ∈ Finset.Icc 1 k, IsRequestLaw (F t))
(μ : Fin m → ℝ) (hμ : 0 ≤ μ) :
optValue A F k x ≤ relaxedValue A F k x μ := by sorry
end BidPriceControl.Asymptotic
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Data. The theorem takes a natural-number matrix and a sequence of measures on . It also takes , a capacity , and with for all .
Hypothesis. For every , is a request law:
- is a probability measure.
- -a.e. has all coordinates with at most one strictly positive.
- for every and every .
- Every coordinate is -integrable.
No bounded-support hypothesis is made, and nothing is assumed about or for .
The value . It is defined by the recursion
- ,
- .
In words: in each period you either reject, or accept one itinerary whose column fits the remaining capacity, earning and consuming . Any non-integrable integrand counts as .
Conclusion.
Degenerate cases.
- : the claim is .
- : every itinerary always fits and .
- : each is the point mass on the single point of and both sides are .
- All-zero columns: an itinerary with fits every capacity and has bid-price sum .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.