Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§3, p. 15 — every product j ∈ S_i* of an optimal assortment has r_ij ≥ γ_i Z* + (1 − γ_i) R_i(S_i*)

Proved
NestedLogitVariants.Competitive.revenue_threshold_of_optimal

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 an optimal solution to the assortment problem (2), with optimal expected revenue Z∗Z^*Z∗. Then every product jjj offered in nest iii, j∈Si∗j \in S^*_ij∈Si∗​, satisfies

rij≥γi Z∗+(1−γi) Ri(Si∗).r_{ij} \ge \gamma_i\, Z^* + (1 - \gamma_i)\, R_i(S^*_i).rij​≥γi​Z∗+(1−γi​)Ri​(Si∗​).

This is the "useful implication of Proposition 2 and Lemma 3" observed after Lemma 3: if some offered product violated the threshold, it could be removed for a strictly larger revenue. It is the inequality the proof of Theorem 4 uses for the product jjj that is exchanged.

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

/-- The observation after Lemma 3, p. 15: if `(S*_1, …, S*_m)` is optimal for problem (2),
then `r_ij ≥ γ_i Z* + (1 − γ_i) R_i(S*_i)` for every `j ∈ S*_i`. -/
theorem revenue_threshold_of_optimal {ι : 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)
    (Sstar : ι → Finset (Fin n)) (hopt : IsOptimal I Sstar)
    (i : ι) (j : Fin n) (hj : j ∈ Sstar i) :
    I.γ i * revenue I Sstar + (1 - I.γ i) * R I i (Sstar i) ≤ I.r i 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. 15, paragraph after the proof of 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