Theorem 7, p. 21 — scaling the nested-by-revenue LP optimum by the factor α of (6) gives a feasible solution of (3)
ProvedNestedLogitVariants.Synergistic.theorem_7Consider the nested logit assortment problem with fully-captured nests ( for every nest ), for some nest , positive revenues and products per nest. Let be an optimal solution of the linear program (4) in which the candidate assortments of every nest are the nested-by-revenue assortments , and let
with . Then is feasible for problem (3):
Combined with Theorem 1, this shows that the best combination of nested-by-revenue assortments, found by a linear program with variables and constraints, earns at least a fraction of the optimal expected revenue.
Formalization Note The standing assumptions are those of the model (see the Model definition) and of §4: every nest is fully captured, , and for some nest (p. 16). The positive revenues are the disclosed pin of this mission: they keep every denominator , , of (6) positive. The condition makes the range of (6) nonempty. The number is given together with the hypothesis that it is the greatest element of the set of terms of (6), not merely an upper bound. The collection is the set of nbr n j for , including . An optimal solution of (4) is a feasible pair whose is no larger than that of any feasible pair.
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_Synergistic_Factor
namespace NestedLogitVariants.Synergistic
/-- Theorem 7, p. 21: let `(x̂, ŷ)` be an optimal solution of problem (4) with the candidate
collections replaced by the nested-by-revenue assortments `{N_{ij} : j ∈ N_+}`. Then, with `α` the
expression in (6), `(α x̂, α ŷ)` is a feasible solution of problem (3). -/
theorem theorem_7 {ι : Type*} [Fintype ι] [DecidableEq ι] {n : ℕ} (I : Instance ι n)
(hI : I.Standing) (hfc : ∀ i, I.vnp i = 0) (hsyn : ∃ i, 1 < I.γ i)
(hr : ∀ i j, 0 < I.r i j) (hn : 2 ≤ n)
(α : ℝ) (hα : IsGreatest (alphaTerms I) α)
(xh : ℝ) (yh : ι → ℝ) (hopt : LP4Optimal I (fun _ => {S | ∃ j ≤ n, S = nbr n j}) xh yh) :
LP3Feasible I (α * xh) (α • yh) := by sorry
end NestedLogitVariants.Synergistic
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.