Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3, p. 14 — removing a product with r_ij < γ_i Z + (1 − γ_i) R_i(S_i) strictly increases revenue

Proved
NestedLogitVariants.Competitive.lemma_3

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

assortment-optimizationnested-logitp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1revenue-management

Assume γi≤1\gamma_i \le 1γi​≤1 and vi0=0v_{i0} = 0vi0​=0 for every nest i∈Mi \in Mi∈M, and v0>0v_0 > 0v0​>0. Let (S1,…,Sm)(S_1, \dots, S_m)(S1​,…,Sm​) be any assortment, with expected revenue Z=Π(S1,…,Sm)Z = \Pi(S_1, \dots, S_m)Z=Π(S1​,…,Sm​). Suppose that in some nest iii the conditional revenue satisfies Ri(Si)≥ZR_i(S_i) \ge ZRi​(Si​)≥Z, and that some product j∈Sij \in S_ij∈Si​ has a small revenue:

rij<γi Z+(1−γi) Ri(Si).r_{ij} < \gamma_i\, Z + (1 - \gamma_i)\, R_i(S_i).rij​<γi​Z+(1−γi​)Ri​(Si​).

Then removing product jjj from SiS_iSi​ yields an assortment (S1,…,Si−1,Si∖{j},Si+1,…,Sm)(S_1, \dots, S_{i-1}, S_i \setminus \{j\}, S_{i+1}, \dots, S_m)(S1​,…,Si−1​,Si​∖{j},Si+1​,…,Sm​) whose expected revenue is strictly larger than ZZZ.

The lemma provides the mechanism by which products with small revenues are removed from an assortment without loss; combined with Proposition 2 it gives the revenue threshold satisfied by every product of an optimal assortment.

Formalization Note The standing assumptions of §3 (p. 13), γi≤1\gamma_i \le 1γi​≤1 and vi0=0v_{i0} = 0vi0​=0 for every nest, are hypotheses, together with those of §1 and the disclosed pins of the model definition (vij>0v_{ij} > 0vij​>0, rij≥0r_{ij} \ge 0rij​≥0, γi>0\gamma_i > 0γi​>0, revenues ordered within each nest). The positivity v0>0v_0 > 0v0​>0 is the section's own "without loss of generality" assumption (p. 14), stated as a hypothesis here because the argument uses it.

Preamble
import Mathlib
import Definitions.Def_NestedLogitVariants_Competitive_Model
Formal statement
namespace NestedLogitVariants.Competitive

/-- Lemma 3, p. 14: if `Z = Π(S_1, …, S_m)` and a product `j ∈ S_i` satisfies
`r_ij < γ_i Z + (1 − γ_i) R_i(S_i)` and `R_i(S_i) ≥ Z`, then removing `j` from `S_i` yields a
strictly larger expected revenue than `Z`. -/
theorem lemma_3 {ι : Type*} [Fintype ι] [DecidableEq ι] {n : ℕ} (I : Instance ι n) (hI : I.Standing)
    (hγ : ∀ i, I.γ i ≤ 1) (hfc : ∀ i, I.vnp i = 0) (hv0 : 0 < I.v0)
    (S : ι → Finset (Fin n)) (i : ι) (j : Fin n) (hj : j ∈ S i)
    (hr : I.r i j < I.γ i * revenue I S + (1 - I.γ i) * R I i (S i))
    (hR : revenue I S ≤ R I i (S i)) :
    revenue I S < revenue I (Function.update S i ((S i).erase j)) := by sorry

end NestedLogitVariants.Competitive
Source
Davis, Gallego, Topaloglu, Assortment optimization under variants of the nested logit model, revised manuscript of June 18, 2013 (published Oper. Res. 62(2), 2014, DOI 10.1287/opre.2014.1256), p. 14, Lemma 3
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 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