Ratio inequality for full and fractional products
ProvedConstrNestedLogit.Space.ratio_inequalityassortment-optimizationknapsacknested-logitp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Suppose an optimal LP solution of (10) has exactly one fractional product , and write . Its full products have utility-to-space ratios at least that of , hence
This comparison supports the refined space approximation when individual products are small relative to capacity.
Formalization Note Positive space weights make the displayed quotient meaningful.
Preamble
import Mathlib import Definitions.Def_ConstrNestedLogit_Space_Model
Formal statement
namespace ConstrNestedLogit.Space
/-- Full products have utility-to-space ratios at least that of the fractional product. -/
theorem ratio_inequality {ι : Type*} [Fintype ι] [DecidableEq ι] {n : ℕ}
(I : NestedLogitVariants.LP.Instance ι n)
(w : ι → Fin n → ℝ) (c : ι → ℝ) (i : ι)
(hvnp : ∀ i, I.vnp i = 0) (hv : ∀ k, 0 < I.v i k)
(hw : ∀ k, 0 < w i k) (hwc : ∀ k, w i k ≤ c i)
(u : ℝ) (hu : 0 ≤ u) (x : Fin n → ℝ)
(hx : spaceLPOptimal I w c i u x) (j : Fin n)
(hj : oneFractional x j) :
utilityRatio I w i u j * (∑ k ∈ rounded x, w i k) ≤
assortmentUtility I i u (rounded x) := by sorry
end ConstrNestedLogit.Space
Source
Gallego & Topaloglu, Constrained Assortment Optimization for the Nested Logit Model, Management Science (2014), DOI 10.1287/mnsc.2014.1931; authors' manuscript of Sept. 11, 2013, p. 21, §5.2 displayed ratio inequality
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.