Theorem 12, p. 28 — the powers-of-δ optimum of (4), scaled to (δ^(2γ̄+1) x̂, δ^(γ̄+1) ŷ), is feasible for (3)
ProvedNestedLogitVariants.PowersDelta.theorem_12Throughout, the instance satisfies the standing assumptions of §1, there is at least one product (), satisfies (the standing assumption of §6, p. 25), and . Let be an optimal solution of problem (4) when the candidate collection of nest is , and the assortments have the two properties of p. 28: whenever problem (15) at level is feasible, is feasible for it and . Then
that is, , and for every nest and every assortment .
Combined with Theorem 1, this shows that restricting nest to the at most candidates loses at most a factor of the optimal expected revenue, for the general nested logit model with nest dissimilarity parameters above one and arbitrary nonnegative no-purchase weights in the nests.
Formalization Note The assortments enter as an arbitrary family with the two properties of p. 28 (IsPowersFamily): the statement holds for every such family, which includes the one Proposition 15 constructs. A level with no feasible assortment imposes nothing on . Optimality of for (4) is feasibility plus minimality of among feasible points. is passed as the greatest element of , so there is at least one nest. The pins of the shared model (, , ) are disclosed in the definition item.
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_PowersDelta_Levels
namespace NestedLogitVariants.PowersDelta
/-- Theorem 12, p. 28. Let `(x̂, ŷ)` be an optimal solution of problem (4) with the candidate
collections `{Ŝ_il : l = l^L_i, …, l^U_i} ∪ {∅}`. Then `(δ^{2γ̄+1} x̂, δ^{γ̄+1} ŷ)` is feasible for
problem (3), where `γ̄ = max_i γ_i > 1` and `δ > 1`. Stated for every family `Ŝ_il` with the two
properties of p. 28 (`IsPowersFamily`). -/
theorem theorem_12 {ι : Type*} [Fintype ι] [DecidableEq ι] {n : ℕ} [NeZero n] (I : Instance ι n)
(hI : I.Standing) (γbar : ℝ) (hγbar : IsGreatest (Set.range I.γ) γbar) (hγbar1 : 1 < γbar)
(δ : ℝ) (hδ : 1 < δ)
(Sh : ι → ℤ → Finset (Fin n)) (hSh : IsPowersFamily I δ Sh)
(xh : ℝ) (yh : ι → ℝ) (hopt : LP4Optimal I (powersCandidates I δ Sh) xh yh) :
LP3Feasible I (δ ^ (2 * γbar + 1) * xh) (δ ^ (γbar + 1) • yh) := by sorry
end NestedLogitVariants.PowersDelta
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.