Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 4, p. 15 — adding a missing higher-revenue product k < j to S_i* keeps the assortment optimal

Proved
NestedLogitVariants.Competitive.insert_higher_revenue_optimal

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

assortment-optimizationnested-by-revenuenested-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), and suppose that in some nest iii the assortment Si∗S^*_iSi∗​ contains product jjj but not product kkk, where k<jk < jk<j (so rik≥rijr_{ik} \ge r_{ij}rik​≥rij​). Let S^i=Si∗∪{k}\hat S_i = S^*_i \cup \{k\}S^i​=Si∗​∪{k}. Then

(S1∗,…,Si−1∗,S^i,Si+1∗,…,Sm∗)(S^*_1, \dots, S^*_{i-1}, \hat S_i, S^*_{i+1}, \dots, S^*_m)(S1∗​,…,Si−1∗​,S^i​,Si+1∗​,…,Sm∗​)

is also an optimal solution to problem (2).

This exchange step is the core of the proof of Theorem 4: repeating it fills every gap in every nest until each nest offers a set of the form {1,2,…,j}\{1, 2, \dots, j\}{1,2,…,j}.

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. Products are indexed 0,…,n−10, \dots, n-10,…,n−1; k<jk < jk<j compares indices, which by the ordering of revenues means rik≥rijr_{ik} \ge r_{ij}rik​≥rij​.

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

/-- Proof of Theorem 4, p. 15 (exchange step): if `(S*_1, …, S*_m)` is optimal and `S*_i`
contains product `j` but not product `k` with `k < j`, then adding `k` to `S*_i` gives an
assortment that is also optimal. -/
theorem insert_higher_revenue_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 k : Fin n) (hj : j ∈ Sstar i) (hk : k ∉ Sstar i) (hkj : k < j) :
    IsOptimal I (Function.update Sstar i (insert k (Sstar i))) := 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, proof of Theorem 4 (first paragraph)
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