Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

pp. 19–20, after Theorem 2 — a majorizing mixture of complete sets earns at least as much as T

Proved
ChoiceRM.FareOrder.mixture_dominates

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

assortment-optimizationdiscrete-choicep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1revenue-management

Throughout, N={1,…,n}N = \{1, \dots, n\}N={1,…,n} is the set of fare products, indexed in fare order r1≥r2≥⋯≥rn≥0r_1 \ge r_2 \ge \dots \ge r_n \ge 0r1​≥r2​≥⋯≥rn​≥0. A choice model assigns to every offer set S⊆NS \subseteq NS⊆N and product jjj a purchase probability Pj(S)≥0P_j(S) \ge 0Pj​(S)≥0, with Pj(S)=0P_j(S) = 0Pj​(S)=0 for j∉Sj \notin Sj∈/S and Q(S)=∑j∈SPj(S)≤1Q(S) = \sum_{j \in S} P_j(S) \le 1Q(S)=∑j∈S​Pj​(S)≤1 (the no-purchase probability is P0(S)=1−Q(S)P_0(S) = 1 - Q(S)P0​(S)=1−Q(S)). The complete sets are Ak={1,…,k}A_k = \{1, \dots, k\}Ak​={1,…,k} for k=0,1,…,nk = 0, 1, \dots, nk=0,1,…,n, with A0=∅A_0 = \emptysetA0​=∅; every other set is incomplete.

Let T⊆NT \subseteq NT⊆N and let α0,…,αn≥0\alpha_0, \dots, \alpha_n \ge 0α0​,…,αn​≥0 with ∑kαk=1\sum_k \alpha_k = 1∑k​αk​=1 be weights such that Pˉj(α)=∑k=0nαkPj(Ak)\bar P_j(\alpha) = \sum_{k=0}^n \alpha_k P_j(A_k)Pˉj​(α)=∑k=0n​αk​Pj​(Ak​) satisfies

∑j=1iPˉj(α)≥∑j=1iPj(T)(i=1,…,n−1),∑j=1nPˉj(α)=∑j=1nPj(T).\sum_{j=1}^i \bar P_j(\alpha) \ge \sum_{j=1}^i P_j(T) \quad (i = 1, \dots, n-1), \qquad \sum_{j=1}^n \bar P_j(\alpha) = \sum_{j=1}^n P_j(T).j=1∑i​Pˉj​(α)≥j=1∑i​Pj​(T)(i=1,…,n−1),j=1∑n​Pˉj​(α)=j=1∑n​Pj​(T).

Then for every x1≥x2≥⋯≥xnx_1 \ge x_2 \ge \dots \ge x_nx1​≥x2​≥⋯≥xn​,

∑j∈TxjPj(T)  ≤  ∑k=0nαk∑j∈AkxjPj(Ak).\sum_{j \in T} x_j P_j(T) \;\le\; \sum_{k=0}^n \alpha_k \sum_{j \in A_k} x_j P_j(A_k).j∈T∑​xj​Pj​(T)≤k=0∑n​αk​j∈Ak​∑​xj​Pj​(Ak​).

This is the paper's direct explanation of why the majorization condition suffices: the convex combination of complete sets produces at least as much value in (9) as TTT, for the same probability of purchase.

Formalization Note Fare j∈{1,…,n}j \in \{1, \dots, n\}j∈{1,…,n} is the element j−1j - 1j−1 of Fin n; the order x1≥⋯≥xnx_1 \ge \dots \ge x_nx1​≥⋯≥xn​ is Antitone x; AkA_kAk​ is complete n k; the choice-model axioms are IsChoiceModel P (platform definition RevenueManagement_singleResource) together with SupportedOn P (Pj(S)=0P_j(S) = 0Pj​(S)=0 off SSS, the model's own convention on p. 5). Complete sets are indexed by k∈{0,…,n}k \in \{0, \dots, n\}k∈{0,…,n}, so A0=∅A_0 = \emptysetA0​=∅ counts as complete and the weights α\alphaα live on n+1n + 1n+1 sets. The page indexes the weights by k=1,…,nk = 1, \dots, nk=1,…,n; the paper notes on p. 21 that Theorem 2 holds for any specified family of sets, and with A0A_0A0​ included the property is the one the paper's Propositions 5 and 6 need (for MNL and all xj<0x_j < 0xj​<0, the unique optimum of (9) is ∅\emptyset∅).

Preamble
import Mathlib
import Definitions.Def_RevenueManagement_singleResource
import Definitions.Def_ChoiceRM_FareOrder_FareOrder
Formal statement
namespace ChoiceRM.FareOrder

open RevenueManagement

/-- pp. 19–20, after Theorem 2: if the mixture `P̄(α)` of complete sets has prefix sums at least
those of `P(T)` and the same total, then for every `x_1 ≥ … ≥ x_n` the mixture earns at least
as much as `T` in (9). -/
theorem mixture_dominates {n : ℕ} (P : Finset (Fin n) → Fin n → ℝ)
    (hP : IsChoiceModel P) (hsupp : SupportedOn P) (T : Finset (Fin n))
    (α : Fin (n + 1) → ℝ) (hα0 : ∀ k, 0 ≤ α k) (hα1 : ∑ k, α k = 1)
    (hpre : ∀ i, i < n → ∑ j ∈ complete n i, P T j ≤ ∑ j ∈ complete n i, mixProb P α j)
    (htot : ∑ j, mixProb P α j = ∑ j, P T j)
    (x : Fin n → ℝ) (hx : Antitone x) :
    fareValue P x T ≤ ∑ k : Fin (n + 1), α k * fareValue P x (complete n k.val) := by sorry

end ChoiceRM.FareOrder
Source
Talluri, van Ryzin, Revenue management under a general discrete choice model of consumer behavior, working paper of October 21, 2001 (UPF Economics Working Paper 533; published Management Science 50(1), 2004, DOI 10.1287/mnsc.1030.0147), pp. 19–20, discussion after Theorem 2 ("This later property is sufficient to ensure that the expected revenue is at least as large")
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

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