Theorem 10, p. 24 — with γ_i ≤ 1, the optimum (x̂, ŷ) of (4) over {Ŝ_i(ϵ_i)} ∪ {{j}} gives (2x̂, 2ŷ) feasible for (3)
ProvedNestedLogitVariants.PartialCompetitive.theorem_10Consider a nested logit instance in which every dissimilarity parameter satisfies , while the within-nest no-purchase weights are arbitrary. For each nest take as candidate assortments the greedy assortments of the continuous knapsack problem together with the singletons,
and let be an optimal solution of the linear program (4) restricted to these candidates. Then is feasible for the full linear program (3):
Combined with Theorem 1 of the paper, this yields a factor-two approximation for assortment optimization under the nested logit model with partially-captured nests, where the exact problem is NP-hard, using a linear program with polynomially many constraints.
Formalization Note An optimal solution of (4) is a feasible pair whose is no larger than that of any feasible pair. is the componentwise double of . The value of the candidate collection is represented by real capacities, since every capacity at least already gives .
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_PartialCompetitive_Model import Definitions.Def_NestedLogitVariants_PartialCompetitive_Knapsack
namespace NestedLogitVariants.PartialCompetitive
/-- Theorem 10, p. 24: with dissimilarity parameters at most one, if `(x̂, ŷ)` is an optimal
solution of (4) with the candidate collections `{Ŝ_i(ε) : ε ∈ [0, ∞]} ∪ {{j} : j ∈ N}`, then
`(2 x̂, 2 ŷ)` is feasible for (3). -/
theorem theorem_10 {ι : Type*} [Fintype ι] [DecidableEq ι] {n : ℕ} (I : Instance ι n)
(hI : I.Standing)
(hγ : ∀ i, I.γ i ≤ 1)
(xh : ℝ) (yh : ι → ℝ) (hopt : LP4Optimal I (candidates I) xh yh) :
LP3Feasible I (2 * xh) (2 • yh) := by sorry
end NestedLogitVariants.PartialCompetitive
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.