(27), p.37 —
ProvedContAssortLogit.eq_27assortment-optimizationmultinomial-logitp2o-gran-per-chapterp2o-plan-paperp2o-v1regretrevenue-managementstochastic-approximation
Let be a revenue function, , and let be an upper bound of on . Then for every the second derivative exists and
With and this is the paper's constant (p.38), so
The constant does not depend on ; this uniformity is what makes the regret bound of Theorem 1 worst-case.
Differences from the source:
- encoding: and are functions on → with every hypothesis stated on (or ); reason: values outside never enter any quantity; same instances
- reading: the class of Assumption 1, with → the class with a fixed derivative bound , for every ; reason: the supremum over all functions satisfying (i) and differentiability is , so the class must carry a bound ; every is allowed
- encoding: with → for every , exists and for every upper bound of on ; reason: the supremum of over is , and a bound for every upper bound is the bound for ; existence of is presupposed by the display
Preamble
import Mathlib import Definitions.Def_ContAssortLogit_Model open MeasureTheory Set
Formal statement
namespace ContAssortLogit
/-- **Inequality (27)** (Peeters, den Boer & Mandjes, arXiv:1807.06497v4, proof of Lemma 4,
pp.37–38): `sup_{y ∈ (0,1)} {−g″(y)} ≤ C₀`, with the constant of p.38
`C₀ = sup_{y ∈ (0,1), v ∈ 𝒱} {|v′(y)| + 2v̄²} + sup_{y ∈ [0,1]} w′(y) v̄`.
In Lean: for every `y ∈ (0, 1)` the second derivative `g″(y)` exists (as the derivative of `g′` at
`y`) and `−g″(y) ≤ D + 2v̄² + M_w v̄`, for every upper bound `M_w` of `w′` on `[0, 1]`.
**Formalization Note.** The supremum of `|v′|` over `(0,1) × 𝒱(v̲, v̄, D)` is `D` (small
oscillations of slope up to `D` stay inside `[v̲, v̄]`), and stating the bound for every upper
bound `M_w` of `w′` is equivalent to stating it with `M_w = sup_{[0,1]} w′`. -/
theorem eq_27 (w v : ℝ → ℝ) (vlo vhi D : ℝ) (hw : IsRevenueFn w)
(hpar : ClassParams w vlo vhi) (hv : InClass vlo vhi D v) (Mw : ℝ)
(hMw : ∀ x ∈ Icc (0 : ℝ) 1, derivWithin w (Icc 0 1) x ≤ Mw) :
∀ y ∈ Ioo (0 : ℝ) 1, ∃ g2 : ℝ, HasDerivAt (deriv (gfun w v)) g2 y ∧
-g2 ≤ D + 2 * vhi ^ 2 + Mw * vhi := by sorry
end ContAssortLogit
Source
Peeters, den Boer, Mandjes, Continuous Assortment Optimization with Logit Choice Probabilities under Incomplete Information, arXiv:1807.06497v4, proof of Lemma 4, (27), p.37, and the definition of C₀, p.38
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.