Theorem 9 — for every α > 1, O(⌈α/(α−1)⌉ n^{⌈α/(α−1)⌉+2}) candidates include an α-approximate solution of (7)
ProvedConstrNestedLogit.Scheme.theorem_9Consider a nest of the nested logit model with preference weights , revenues (of any sign), no within-nest no-purchase weight, and space constraints with and . Write and (with ). For every , with , there is a collection with
such that for every some member of the collection is an -approximate solution of problem (7):
Combined with Theorem 4 and Theorem 2 of the paper, this yields an -approximation for the space-constrained assortment problem through a linear program with variables and constraints.
Formalization Note The paper's is pinned to the explicit bound , uniform in like the paper's: for , at most sets of size at most , times at most pieces of (the open intervals between the at most intersection points of the lines and , and the points themselves); the covers . The collection is fixed before . , and are added; is the paper's assumption. Products are Fin n, nests a finite type, and the within-nest no-purchase weight of the published model is set to zero.
import Mathlib import Definitions.Def_NestedLogitVariants_LP_Model import Definitions.Def_ConstrNestedLogit_Scheme_Model
namespace ConstrNestedLogit.Scheme
open NestedLogitVariants.LP in
/-- Theorem 9, p. 40: under space constraints, for every `α > 1`, with `q = ⌈α/(α − 1)⌉`, there is
a collection `A` of space-feasible assortments of nest `i` with at most
`5 (q + 1) n^(q + 2) + 1` members (the paper's `|T_i| = O(⌈α/(α − 1)⌉ n^{⌈α/(α−1)⌉+2})`)
that contains an `α`-approximate solution of problem (7) for every `u ≥ 0`. -/
theorem theorem_9 {ι : Type*} {n : ℕ}
(I : NestedLogitVariants.LP.Instance ι n) (hvnp : ∀ i, I.vnp i = 0)
(hv : ∀ i j, 0 < I.v i j) (w : ι → Fin n → ℝ) (c : ι → ℝ)
(hwc : ∀ i j, w i j ≤ c i) (hw : ∀ i j, 0 < w i j) (hc : ∀ i, 0 ≤ c i) (i : ι)
(α : ℝ) (hα : 1 < α) :
∃ A : Finset (Finset (Fin n)), (∀ S ∈ A, ConstrNestedLogit.Space.spaceFeasible w c i S) ∧
A.card ≤ 5 * (⌈α / (α - 1)⌉₊ + 1) * n ^ (⌈α / (α - 1)⌉₊ + 2) + 1 ∧
∀ u : ℝ, 0 ≤ u → ∃ S ∈ A, ∀ S', ConstrNestedLogit.Space.spaceFeasible w c i S' →
V I i S' * (R I i S' - u) ≤ α * (V I i S * (R I i S - u)) := by sorry
end ConstrNestedLogit.Scheme
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.