Theorem 2, p. 19 — nesting by fare order iff Q is increasing and a mixture of complete sets majorizes every incomplete set
ProvedChoiceRM.FareOrder.theorem_2Throughout, is the set of fare products, indexed in fare order . A choice model assigns to every offer set and product a purchase probability , with for and (the no-purchase probability is ). The complete sets are for , with ; every other set is incomplete.
The choice model has the nesting-by-fare-order property (Definition 4) if is increasing ( for ) and, for every , the problem has a complete optimal solution.
Theorem 2. The choice model has the nesting-by-fare-order property if and only if
-
the probability of purchase is increasing in , and
-
for every incomplete set there are convex weights , , such that the probabilities satisfy
In the language of majorization, the vector majorizes 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 is the element of Fin n; the order is Antitone x; is complete n k; the choice-model axioms are IsChoiceModel P (platform definition RevenueManagement_singleResource) together with SupportedOn P ( off , the model's own convention on p. 5). The page writes ; is the complete set (a printed slip, as the proof on p. 20 shows). Complete sets are indexed by , so counts as complete and the weights live on sets. The page indexes the weights by ; the paper notes on p. 21 that Theorem 2 holds for any specified family of sets, and with included the property is the one the paper's Propositions 5 and 6 need (for MNL and all , the unique optimum of (9) is ). The prefix condition is stated for ; is trivially true.
import Mathlib import Definitions.Def_RevenueManagement_singleResource import Definitions.Def_ChoiceRM_FareOrder_FareOrder
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.