Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 6 — under MNL, offering every product with w_j ≥ w_[k*] is optimal for (14) (repaired: some w_j ≥ 0)

Proved
ChoiceCDLP.MNL.top_ranked_optimal

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

assortment-optimizationdiscrete-choicemultinomial-logitp2o-batch-rm-cafterp2o-gran-per-chapterp2o-plan-paperp2o-v1revenue-management

Consider one customer segment with a finite consideration set ι\iotaι, MNL preference weights vj>0v_j > 0vj​>0 (j∈ιj \in \iotaj∈ι), a no-purchase weight v0≥0v_0 \ge 0v0​≥0 and scores wj∈Rw_j \in \mathbb{R}wj​∈R, at least one of which is nonnegative. For an offer set S⊆ιS \subseteq \iotaS⊆ι let

f(S)=∑j∈Swjvj∑j∈Svj+v0.f(S) = \frac{\sum_{j \in S} w_j v_j}{\sum_{j \in S} v_j + v_0}.f(S)=∑j∈S​vj​+v0​∑j∈S​wj​vj​​.

Then there is a product k∈ιk \in \iotak∈ι such that the threshold set S∗={j∈ι:wj≥wk}S^* = \{ j \in \iota : w_j \ge w_k \}S∗={j∈ι:wj​≥wk​} is an optimal solution of the offer-set problem (14):

f(S)≤f({j∈ι:wj≥wk})for every S⊆ι.f(S) \le f\bigl(\{ j \in \iota : w_j \ge w_k\}\bigr) \qquad \text{for every } S \subseteq \iota.f(S)≤f({j∈ι:wj​≥wk​})for every S⊆ι.

In the paper's words: rank the scores decreasingly, w[1]≥⋯≥w[s]w_{[1]} \ge \cdots \ge w_{[s]}w[1]​≥⋯≥w[s]​; there is a critical value k∗k^*k∗, 1≤k∗≤s1 \le k^* \le s1≤k∗≤s, such that offering exactly the products with wj≥w[k∗]w_j \ge w_{[k^*]}wj​≥w[k∗]​ is optimal. Here wkw_kwk​ plays the role of w[k∗]w_{[k^*]}w[k∗]​.

The result makes the column-generation subproblem of the choice-based deterministic linear program (CDLP), and the set-selection problems of the decomposition heuristic, solvable under MNL with disjoint segments by checking at most sss nested candidate sets, one per segment, instead of 2s2^s2s subsets. It was also shown by Gallego, Iyengar, Phillips and Dubey (2004).

Formalization Note. Offer vectors y∈{0,1}sy \in \{0,1\}^sy∈{0,1}s are subsets S : Finset ι; the consideration set is the whole finite type ι. The ranking is not formalized as a permutation: the k∗k^*k∗-th largest value w[k∗]w_{[k^*]}w[k∗]​ is the score wkw_kwk​ of some product kkk, and 1≤k∗≤s1 \le k^* \le s1≤k∗≤s becomes "k∈ιk \in \iotak∈ι". With ties the threshold set contains every product tied with w[k∗]w_{[k^*]}w[k∗]​, which is what the printed rule yj∗=1  ⟺  wj≥w[k∗]y^*_j = 1 \iff w_j \ge w_{[k^*]}yj∗​=1⟺wj​≥w[k∗]​ says. Repair: the hypothesis that some wj≥0w_j \ge 0wj​≥0 is added. As printed the proposition is false when every wj<0w_j < 0wj​<0: for s=1s = 1s=1, w1=−1w_1 = -1w1​=−1, v1=1v_1 = 1v1​=1, v0=1v_0 = 1v0​=1, the empty offer set has value 000 while the only set allowed by 1≤k∗1 \le k^*1≤k∗, namely {1}\{1\}{1}, has value −1/2-1/2−1/2. Negative scores do occur in the paper's application (wj=rj−π⊤Ajw_j = r_j - \pi^\top A_jwj​=rj​−π⊤Aj​, p. 300). The conclusion is that S∗S^*S∗ is an optimal solution; optimal solutions need not be unique. v0=0v_0 = 0v0​=0 is allowed (the paper uses it in §7), with f(∅)=0/0=0f(\emptyset) = 0/0 = 0f(∅)=0/0=0 in Lean, the paper's convention h(0):=0h(0) := 0h(0):=0.

Preamble
import Mathlib
import Definitions.Def_ChoiceCDLP_MNL_mnlObjective
Formal statement
namespace ChoiceCDLP.MNL

/-- Proposition 6 (Liu and van Ryzin 2008, p. 300). For one segment with consideration set `ι`
(finite), preference weights `v j > 0`, no-purchase weight `v₀ ≥ 0` and scores `w j`, there is
a product `k` (the `k*`-th ranked, `w k = w_[k*]`) such that offering every product with
`w j ≥ w k` is an optimal solution of
`max_{S ⊆ ι} (∑_{j ∈ S} w_j v_j) / (∑_{j ∈ S} v_j + v₀)` (problem (14)).
Repaired: the hypothesis that some `w j ≥ 0` is added (as printed, `1 ≤ k*` is false when
every `w j < 0`, where only the empty offer set is optimal). -/
theorem top_ranked_optimal {ι : Type*} [Fintype ι] (v w : ι → ℝ) (v₀ : ℝ)
    (hv : ∀ j, 0 < v j) (hv₀ : 0 ≤ v₀) (hw : ∃ j, 0 ≤ w j) :
    ∃ k : ι, ∀ S : Finset ι,
      mnlObjective v w v₀ S ≤ mnlObjective v w v₀ (Finset.univ.filter fun j => w k ≤ w j) := by sorry

end ChoiceCDLP.MNL
Source
Liu, van Ryzin, On the Choice-Based Linear Programming Model for Network Revenue Management, Manuf. Serv. Oper. Manag. 10(2), 2008, p. 300, Proposition 6
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Here ι\iotaι is an arbitrary type with finitely many elements. It indexes a family of items j∈ιj \in \iotaj∈ι. The statement takes as data:

  • two real-valued functions on ι\iotaι, a weight vjv_jvj​ and a score wjw_jwj​ for each jjj;
  • a single real number v0v_0v0​.

It assumes three hypotheses:

  • (i) every weight is strictly positive: vj>0v_j > 0vj​>0 for all j∈ιj \in \iotaj∈ι;
  • (ii) v0≥0v_0 \ge 0v0​≥0;
  • (iii) at least one score is nonnegative: there is some j∈ιj \in \iotaj∈ι with wj≥0w_j \ge 0wj​≥0.

The conclusion uses a function Fv,w,v0(S)F_{v,w,v_0}(S)Fv,w,v0​​(S) that assigns a real number to every finite subset S⊆ιS \subseteq \iotaS⊆ι. It is mnlObjective, defined in the imported module Definitions.Def_ChoiceCDLP_MNL_mnlObjective. Its definition is not part of the code given here, so this read-back cannot say what it computes. In particular, it cannot confirm the ratio (∑j∈Swjvj)/(∑j∈Svj+v0)\left(\sum_{j\in S} w_j v_j\right)/\left(\sum_{j\in S} v_j + v_0\right)(∑j∈S​wj​vj​)/(∑j∈S​vj​+v0​) that the docstring gives, or how that ratio is handled when its denominator is 000. Hypotheses (i) and (ii) appear nowhere else in the statement, so they matter only through that definition.

The statement asserts that there is an element k∈ιk \in \iotak∈ι such that the following holds. Let

Tk  =  { j∈ι  :  wk≤wj }.T_k \;=\; \{\, j \in \iota \;:\; w_k \le w_j \,\}.Tk​={j∈ι:wk​≤wj​}.

TkT_kTk​ is the set of all items whose score is at least wkw_kwk​. It includes kkk itself and every item tied with kkk. Then for every finite subset S⊆ιS \subseteq \iotaS⊆ι, including S=∅S = \varnothingS=∅ and S=ιS = \iotaS=ι:

Fv,w,v0(S)  ≤  Fv,w,v0(Tk).F_{v,w,v_0}(S) \;\le\; F_{v,w,v_0}(T_k).Fv,w,v0​​(S)≤Fv,w,v0​​(Tk​).

So some upper set of scores, {j:wj≥wk}\{j : w_j \ge w_k\}{j:wj​≥wk​}, maximizes Fv,w,v0F_{v,w,v_0}Fv,w,v0​​ over all finite subsets of ι\iotaι. The statement says nothing about which kkk this is. It does not say that kkk is unique, that kkk has any particular rank, or that wk≥0w_k \ge 0wk​≥0. Because TkT_kTk​ always contains kkk, the maximizing set it names is never empty. The statement therefore does not allow the empty set to be the named maximizer, although the empty set may still attain the same value.

On degenerate cases:

  • Empty ι\iotaι: hypothesis (iii) requires some j∈ιj \in \iotaj∈ι, so ι\iotaι cannot be empty. The hypotheses rule this case out.
  • One-element ι={a}\iota = \{a\}ι={a}: kkk must be aaa and Tk={a}T_k = \{a\}Tk​={a}. The claim becomes Fv,w,v0(∅)≤Fv,w,v0({a})F_{v,w,v_0}(\varnothing) \le F_{v,w,v_0}(\{a\})Fv,w,v0​​(∅)≤Fv,w,v0​​({a}), where wa≥0w_a \ge 0wa​≥0 by (iii).
  • v0=0v_0 = 0v0​=0: this is allowed. If FFF divides by ∑j∈Svj+v0\sum_{j\in S} v_j + v_0∑j∈S​vj​+v0​, then for S=∅S = \varnothingS=∅ that denominator is 000. Real division by zero returns 000 by convention, so Fv,w,v0(∅)F_{v,w,v_0}(\varnothing)Fv,w,v0​​(∅) would be 000 rather than undefined. Whether this applies depends on the unseen definition.
  • All scores equal: Tk=ιT_k = \iotaTk​=ι whatever kkk is chosen. The claim is then that offering everything is at least as good as every subset.
  • Hypothesis (iii): it asks only that one score be nonnegative. Other scores may be negative.
Human review
  • Endorsed by Shuze Chen · Oct 21, 2026

    Confirmed by the moderator at approval.

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