One rounded family with both space guarantees
ProvedConstrNestedLogit.Space.space_guaranteeassortment-optimizationknapsacknested-logitp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
For each nest with positive product preference and space weights, and individually feasible products, one collection of rounded LP assortments and singletons works for every . It has at most feasible members and always includes a two-approximate solution of problem (7). For every satisfying for all products, the same collection also includes a -approximate solution at every :
Here . The two guarantees imply the factor claimed in §5.2, while keeping the candidate family fixed before and .
Formalization Note Products form a nonempty finite set, and the within-nest no-purchase weight is zero. Positive preference and space weights are explicit.
Preamble
import Mathlib import Definitions.Def_ConstrNestedLogit_Space_Model
Formal statement
namespace ConstrNestedLogit.Space
/-- The one quadratic-size family from §5.1 has both guarantees of §5.2. -/
theorem space_guarantee {ι : Type*} [Fintype ι] [DecidableEq ι] {n : ℕ}
(I : NestedLogitVariants.LP.Instance ι n)
(w : ι → Fin n → ℝ) (c : ι → ℝ) (i : ι)
(hn : 0 < n)
(hvnp : ∀ i, I.vnp i = 0) (hv : ∀ j, 0 < I.v i j)
(hw : ∀ j, 0 < w i j) (hwc : ∀ j, w i j ≤ c i) :
∃ A : Finset (Finset (Fin n)),
isRoundedCandidateFamily I w c i A ∧
(∀ S ∈ A, spaceFeasible w c i S) ∧
A.card ≤ (n + 1) ^ 2 ∧
(∀ u : ℝ, 0 ≤ u → ∃ S ∈ A, isApproximateAt I w c i u 2 S) ∧
(∀ ε : ℝ, 0 ≤ ε → ε < 1 → (∀ j, w i j ≤ ε * c i) →
∀ u : ℝ, 0 ≤ u → ∃ S ∈ A,
isApproximateAt I w c i u (1 / (1 - ε)) S) := 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. 22, concluding paragraph of §5.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.