Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Online Supplement A, pp. 33–34 — the claim ŷ_i ≥ V_i(S*_i)^γ_i (R_i(S*_i) − ẑ)

Proved
ConstrNestedLogit.UpperBound.claim

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

assortment-optimizationlinear-programmingnested-logitp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider the nested logit model with no-purchase weight v0>0v_0 > 0v0​>0, preference weights vij>0v_{ij} > 0vij​>0, arbitrary revenues rijr_{ij}rij​, dissimilarity parameters γi∈(0,1]\gamma_i \in (0, 1]γi​∈(0,1] and no within-nest no-purchase weight. Let wij>0w_{ij} > 0wij​>0 be space requirements and cic_ici​ capacities with wij≤ciw_{ij} \le c_iwij​≤ci​ for every product (the paper's standing assumption, p. 8), and let {Xi:i∈M}\{X_i : i \in M\}{Xi​:i∈M} be finite sets of vectors such that every vector of XiX_iXi​ is feasible for the linear programming relaxation of the knapsack problem (10) of nest iii, and for every u≥0u \ge 0u≥0 some vector of XiX_iXi​ is optimal for that relaxation at uuu. Let (S1,…,Sm)(S_1, \dots, S_m)(S1​,…,Sm​) be an assortment with Si∈CiS_i \in \mathcal C_iSi​∈Ci​ for every nest. If (z,y)(z, y)(z,y) is a feasible solution of the linear program (13) built on the sets XiX_iXi​, then

yi  ≥  Vi(Si)γi(Ri(Si)−z)for all i∈M.y_i \;\ge\; V_i(S_i)^{\gamma_i}\big(R_i(S_i) - z\big) \qquad \text{for all } i \in M.yi​≥Vi​(Si​)γi​(Ri​(Si​)−z)for all i∈M.

This is the claim at the heart of the proof of Proposition 7; summing it over the nests and using the first constraint of (13) gives the upper bound.

Formalization Note The paper states the claim for an optimal solution (z^,y^)(\hat z, \hat y)(z^,y^​) of (13) and an optimal assortment (S1∗,…,Sm∗)(S_1^*, \dots, S_m^*)(S1∗​,…,Sm∗​) of problem (1); the statement here is for every feasible (z,y)(z, y)(z,y) and every feasible assortment, which is what the proof uses. Positivity of v0v_0v0​, vijv_{ij}vij​ and wijw_{ij}wij​ is added; wij≤ciw_{ij} \le c_iwij​≤ci​ is the paper's standing assumption (p. 8); vi0=0v_{i0} = 0vi0​=0 is the paper's model.

Preamble
import Mathlib
import Definitions.Def_NestedLogitVariants_General_Model
import Definitions.Def_NestedLogitVariants_General_Relaxation
import Definitions.Def_ConstrNestedLogit_UpperBound_Relaxation
import Definitions.Def_ConstrNestedLogit_UpperBound_LP13

open NestedLogitVariants.General
Formal statement
namespace ConstrNestedLogit.UpperBound

/-- Online Supplement A, the claim in the proof of Proposition 7 (pp. 33–34): if the vectors `X i`
are feasible for the linear programming relaxation of (10) and include an optimal solution of that
relaxation for every `u ≥ 0`, then every feasible solution `(z, y)` of the linear program (13)
satisfies `y_i ≥ V_i(S_i)^{γ_i} (R_i(S_i) − z)` for every nest `i` and every assortment
`(S_1, …, S_m)` that satisfies the space constraints. -/
theorem claim {ι : Type*} [Fintype ι] {n : ℕ} (I : Instance ι n)
    (hvnp : ∀ i, I.vnp i = 0) (hv0 : 0 < I.v0) (hv : ∀ i j, 0 < I.v i j)
    (hγ : ∀ i, 0 < I.γ i ∧ I.γ i ≤ 1)
    (w : ι → Fin n → ℝ) (c : ι → ℝ) (X : ι → Finset (Fin n → ℝ))
    (hw : ∀ i j, 0 < w i j) (hwc : ∀ i j, w i j ≤ c i)
    (hX : IsRelaxSolutionFamily I w c X)
    (S : ι → Finset (Fin n)) (hS : ∀ i, SpaceFeasible w c i (S i))
    (z : ℝ) (y : ι → ℝ) (hzy : LP13Feasible I X z y) :
    ∀ i, nestWeight I i (S i) * (R I i (S i) - z) ≤ y i := by sorry

end ConstrNestedLogit.UpperBound
Source
Gallego & Topaloglu, Constrained Assortment Optimization for the Nested Logit Model, Management Science (2014), DOI 10.1287/mnsc.2014.1931; authors' manuscript of Sept. 11, 2013, pp. 33–34, Online Supplement A, proof of Proposition 7 (the claim)
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me