Proposition 6 — under MNL, offering every product with w_j ≥ w_[k*] is optimal for (14) (repaired: some w_j ≥ 0)
ProvedChoiceCDLP.MNL.top_ranked_optimalConsider one customer segment with a finite consideration set , MNL preference weights (), a no-purchase weight and scores , at least one of which is nonnegative. For an offer set let
Then there is a product such that the threshold set is an optimal solution of the offer-set problem (14):
In the paper's words: rank the scores decreasingly, ; there is a critical value , , such that offering exactly the products with is optimal. Here plays the role of .
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 nested candidate sets, one per segment, instead of subsets. It was also shown by Gallego, Iyengar, Phillips and Dubey (2004).
Formalization Note. Offer vectors are subsets S : Finset ι; the consideration set is the whole finite type ι. The ranking is not formalized as a permutation: the -th largest value is the score of some product , and becomes "". With ties the threshold set contains every product tied with , which is what the printed rule says. Repair: the hypothesis that some is added. As printed the proposition is false when every : for , , , , the empty offer set has value while the only set allowed by , namely , has value . Negative scores do occur in the paper's application (, p. 300). The conclusion is that is an optimal solution; optimal solutions need not be unique. is allowed (the paper uses it in §7), with in Lean, the paper's convention .
import Mathlib import Definitions.Def_ChoiceCDLP_MNL_mnlObjective
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Here is an arbitrary type with finitely many elements. It indexes a family of items . The statement takes as data:
- two real-valued functions on , a weight and a score for each ;
- a single real number .
It assumes three hypotheses:
- (i) every weight is strictly positive: for all ;
- (ii) ;
- (iii) at least one score is nonnegative: there is some with .
The conclusion uses a function that assigns a real number to every finite subset . 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 that the docstring gives, or how that ratio is handled when its denominator is . 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 such that the following holds. Let
is the set of all items whose score is at least . It includes itself and every item tied with . Then for every finite subset , including and :
So some upper set of scores, , maximizes over all finite subsets of . The statement says nothing about which this is. It does not say that is unique, that has any particular rank, or that . Because always contains , 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 : hypothesis (iii) requires some , so cannot be empty. The hypotheses rule this case out.
- One-element : must be and . The claim becomes , where by (iii).
- : this is allowed. If divides by , then for that denominator is . Real division by zero returns by convention, so would be rather than undefined. Whether this applies depends on the unseen definition.
- All scores equal: whatever 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.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.