Proof of Theorem 1, "if" half: , give for every
ProvedRandAssort.theorem_1_if_boundassortment-optimizationoperations-researchoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1randomizationrobust-optimization
Let be a robust assortment instance satisfying the standing assumptions of §3, with a compact subset of a finite-dimensional real normed space. Let be its set of expected revenue vectors, a real number, and with componentwise. Then every randomized assortment satisfies
With and the maximum over , this gives , which is the "if" half of Theorem 1.
Formalization Note is the real infimum of over , and . No continuity of is assumed.
Differences from the source:
- generalization: threshold R⋆_det(𝒰) → an arbitrary real c; reason: the statement at c = R⋆_det(𝒰) is the source's
- reading: chain R⋆(p) = min_{R∈conv ℛ} p⊤R ≤ p⊤R′, whose identity is quoted from (5) → R⋆(p) ≤ p⊤R′; reason: the identity is e-companion eq. (5), a separate milestone that states the attainment; this step uses only the inequality it gives for R′ ∈ conv ℛ, which holds for the infimum without lower semicontinuity
- encoding: products {1,…,n}, alternatives 𝒩₀ = 𝒩 ∪ {0} with r₀ = 0, a compact subset of a finite-dimensional space; 𝒮, 𝒰 implicitly nonempty; min over 𝒰 → Fin n, Option (Fin n) with none the no-purchase option, revenue summed over offered products, 𝒰 a subset of a finite-dimensional real normed space; 𝒮, 𝒰 nonempty in the validity predicate; R⋆(p) the real infimum ⨅; reason: Lean convention; same instances
Preamble
import Mathlib import Definitions.Def_RandAssort_Model import Definitions.Def_RandAssort_RevenueVectors
Formal statement
namespace RandAssort
/-- **Proof of Theorem 1**, first display, e-companion p.ec9 of Z. Wang, H. Peura, W. Wiesemann,
*Randomized Assortment Optimization*, Operations Research (2024), doi:10.1287/opre.2022.0129:
`R⋆(p) = min_{R ∈ conv ℛ} p⊤R ≤ p⊤R′ ≤ R⋆_det(𝒰)`.
For a valid instance, a real `c`, and a point `R′ ∈ conv ℛ` with `R′ ≤ c · e`, every randomized
assortment `p ∈ Δ(𝒮)` satisfies `R⋆(p) ≤ p⊤R′ ≤ c`; in particular its worst-case revenue is at
most `c`. The paper uses `c = R⋆_det(𝒰)`.
**Formalization Note** `R⋆(p)` is the real infimum `⨅ u ∈ 𝒰, R(p, u)` (`Instance.RstarP`) and
`p⊤R′ = ∑_{S ∈ 𝒮} p_S R′_S`. The identity `R⋆(p) = min_{R ∈ conv ℛ} p⊤R` of the display is
e-companion eq. (5), a separate statement; here only the inequality `R⋆(p) ≤ p⊤R′` it yields for
`R′ ∈ conv ℛ` is asserted, which holds without continuity of `u ↦ R(S, u)`. -/
theorem theorem_1_if_bound {n : ℕ} {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
[FiniteDimensional ℝ E] (I : Instance n E) (hI : I.IsValid) (c : ℝ)
(R' : I.S → ℝ) (hR' : R' ∈ convexHull ℝ I.revSet) (hle : ∀ S : I.S, R' S ≤ c)
(p : I.S → ℝ) (hp : p ∈ stdSimplex ℝ I.S) :
I.RstarP p ≤ ∑ S : I.S, p S * R' S ∧ ∑ S : I.S, p S * R' S ≤ c := by sorry
end RandAssort
Source
Wang–Peura–Wiesemann, Randomized Assortment Optimization, Oper. Res. (2024), doi:10.1287/opre.2022.0129, proof of Theorem 1, first display, e-companion p.ec9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.