Theorem 4, p. 15 — with γ_i ≤ 1 and v_i0 = 0, some optimal assortment has S_i* = N_ij in every nest
ProvedNestedLogitVariants.Competitive.theorem_4Consider the nested logit assortment problem (2) in which every nest is fully captured, for all , and every dissimilarity parameter satisfies . Products in each nest are ordered by revenue, , and denotes the nested-by-revenue assortment of the highest-revenue products of nest , with and . Then there exists an optimal solution to problem (2) such that
This is the main structural result of the paper for competitive products and fully-captured nests: the search for an optimal assortment can be restricted to the combinations of nested-by-revenue assortments, and the paper then finds the best combination with a linear program with variables.
Formalization Note The standing assumptions of §3 (p. 13), and , are hypotheses, together with those of §1 and the pins of the model definition (, , , revenues ordered). The no-nest weight is only assumed nonnegative, : the section assumes "without loss of generality", and the case is covered by the paper's remark that offering the single highest-revenue product is then optimal. Products are indexed and is nbr n j with ; gives the empty assortment. The statement asserts that some optimal assortment is nested by revenue, not that every optimal assortment is (which fails under ties).
Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.
import Mathlib import Definitions.Def_NestedLogitVariants_Competitive_Model
namespace NestedLogitVariants.Competitive
/-- Theorem 4, p. 15: with `γ_i ≤ 1` and `v_{i0} = 0` for all nests, there exists an optimal
solution `(S*_1, …, S*_m)` to problem (2) such that, for all `i ∈ M`, `S*_i = N_ij` for some
`j ∈ N_+ = {0, 1, …, n}`. -/
theorem theorem_4 {ι : Type*} [Fintype ι] [DecidableEq ι] {n : ℕ} (I : Instance ι n) (hI : I.Standing)
(hγ : ∀ i, I.γ i ≤ 1) (hfc : ∀ i, I.vnp i = 0) :
∃ S : ι → Finset (Fin n), IsOptimal I S ∧ ∀ i, ∃ j ≤ n, S i = nbr n j := by sorry
end NestedLogitVariants.Competitive
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.