Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2, p. 19 — nesting by fare order iff Q is increasing and a mixture of complete sets majorizes every incomplete set

Proved
ChoiceRM.FareOrder.theorem_2

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.

The choice model has the nesting-by-fare-order property (Definition 4) if QQQ is increasing (Q(S)≤Q(T)Q(S) \le Q(T)Q(S)≤Q(T) for S⊆TS \subseteq TS⊆T) and, for every x1≥x2≥⋯≥xnx_1 \ge x_2 \ge \dots \ge x_nx1​≥x2​≥⋯≥xn​, the problem max⁡S⊆N∑j=1nxjPj(S)\max_{S \subseteq N} \sum_{j=1}^n x_j P_j(S)maxS⊆N​∑j=1n​xj​Pj​(S) has a complete optimal solution.

Theorem 2. The choice model has the nesting-by-fare-order property if and only if

  1. the probability of purchase Q(S)Q(S)Q(S) is increasing in SSS, and

  2. for every incomplete set TTT there are convex weights α0,…,αn≥0\alpha_0, \dots, \alpha_n \ge 0α0​,…,αn​≥0, ∑kαk=1\sum_k \alpha_k = 1∑k​αk​=1, such that the probabilities 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​) satisfy

∑j=1iPˉj(α)≥∑j=1iPj(T)(i=1,…,n−1)and∑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\text{and}\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)andj=1∑n​Pˉj​(α)=j=1∑n​Pj​(T).

In the language of majorization, the vector (Pˉ1(α),…,Pˉn(α))(\bar P_1(\alpha), \dots, \bar P_n(\alpha))(Pˉ1​(α),…,Pˉn​(α)) majorizes (P1(T),…,Pn(T))(P_1(T), \dots, P_n(T))(P1​(T),…,Pn​(T)) in fare order. The theorem reduces the question whether an optimal revenue-management policy is nested by fare order to a finite family of linear feasibility problems, one per incomplete set, and is the tool the paper uses for the independent-demand and multinomial-logit models.

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). The page writes Pˉj(α)=∑k=1nαkPj(Sk)\bar P_j(\alpha) = \sum_{k=1}^n \alpha_k P_j(S_k)Pˉj​(α)=∑k=1n​αk​Pj​(Sk​); SkS_kSk​ is the complete set AkA_kAk​ (a printed slip, as the proof on p. 20 shows). 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∅). The prefix condition is stated for i=0,…,n−1i = 0, \dots, n-1i=0,…,n−1; i=0i = 0i=0 is trivially true.

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

open RevenueManagement

/-- Theorem 2, p. 19: a choice model has the nested-by-fare-order property iff (i) the purchase
probability `Q` is increasing and (ii) for every incomplete set `T` some convex combination
`P̄(α)` of the complete sets majorizes `(P_1(T), …, P_n(T))`. -/
theorem theorem_2 {n : ℕ} (P : Finset (Fin n) → Fin n → ℝ)
    (hP : IsChoiceModel P) (hsupp : SupportedOn P) :
    HasFareOrderNesting P ↔
      ((∀ S T : Finset (Fin n), S ⊆ T → purchaseProb P S ≤ purchaseProb P T) ∧
        ∀ T : Finset (Fin n), ¬ IsComplete T →
          ∃ α : Fin (n + 1) → ℝ, (∀ k, 0 ≤ α k) ∧ ∑ k, α k = 1 ∧
            (∀ i, i < n → ∑ j ∈ complete n i, P T j ≤ ∑ j ∈ complete n i, mixProb P α j) ∧
            ∑ j, mixProb P α j = ∑ j, P T j) := 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), p. 19, Theorem 2 (with Definition 4, p. 18)
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