Proof of Theorem 4.2, pp. 16–17 — S*_t(x) solves the static robust problem with revenues r_i − ΔJ_{t+1}(x)
ProvedRobustMNL.Dynamic.optAssort_iff_staticdynamic-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimization
Let and , and write . Then:
- An assortment is an optimal assortment of smallest cardinality of the period- Bellman problem with capacity (that is, ) if and only if is an optimal assortment of smallest cardinality of the static Robust Logit problem over with revenues (that is, for revenues ).
- The optimal values agree:
This is the reduction by which every structural result of Section 3 transfers to the dynamic problem.
Formalization Note The static objects are the restated IsSmallestOptimal and Zstar at the revenues fun i => r i - marginalValue T V r (t + 1) x. The paper's remark that products with are never used is not needed, since the static results are stated for arbitrary real revenues.
Preamble
import Mathlib import Definitions.Def_RobustMNL_Dynamic_ValueFunction
Formal statement
namespace RobustMNL.Dynamic
theorem optAssort_iff_static {n : ℕ} (T : ℕ) (V : ℕ → Set (ℝ × (Fin n → ℝ)))
(r : Fin n → ℝ) (hV : IsUncertaintySeq T V) (t x : ℕ) (ht : 1 ≤ t) (htT : t ≤ T) (hx : 1 ≤ x) :
(∀ S : Finset (Fin n), IsOptAssort T V r t x S ↔
RobustMNL.Static.IsSmallestOptimal (V t) (fun i => r i - marginalValue T V r (t + 1) x) S) ∧
J T V r t x - J T V r (t + 1) x =
RobustMNL.Static.Zstar (V t) (fun i => r i - marginalValue T V r (t + 1) x) := by sorry
end RobustMNL.Dynamic
Source
Rusmevichientong, Topaloglu, Robust Assortment Optimization in Revenue Management Under the Multinomial Logit Choice Model, Operations Research (2012), doi:10.1287/opre.1120.1063, authors' manuscript of 20 Sep 2011, Proof of Theorem 4.2, p. 16 (last display) – p. 17 (first paragraph)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.