Proof of Proposition 6, p. 24, (15) — the index k* and the weight λ for an incomplete set
ProvedChoiceRM.MNL.exists_kstar_thetadiscrete-choicemultinomial-logitp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1revenue-management
Let , write , and let be incomplete (not of the form , ). Then there is an index with such that
- ;
- contains a product with index larger than , i.e. ;
- there is with
The two complete sets and , mixed with weights and , are the convex combination that the proof of Proposition 6 compares with .
Formalization Note The paper's is written (λ is reserved in Lean). Products are Fin n, so "" in the paper's 1-based indexing is "some with k ≤ j.val" in 0-based indexing, and is complete n k. The page says "define by (15)"; that a solution exists and lies in , so that the weights are convex, is implicit there and is what this item asserts.
Preamble
import Mathlib import Definitions.Def_RevenueManagement_singleResource import Definitions.Def_ChoiceRM_MNL_FareOrder import Definitions.Def_ChoiceRM_MNL_Models
Formal statement
namespace ChoiceRM.MNL
/-- Proof of Proposition 6, p. 24, (15): for an incomplete set `T` there is an index `k*` with
`W(A_{k*}) ≤ W(T) < W(A_{k*+1})` (where `W(S) = Σ_{i∈S} w_i`), `T` contains a fare beyond
`A_{k*}`, and a weight `θ ∈ [0, 1]` (the paper's `λ`) solving (15). -/
theorem exists_kstar_theta {n : ℕ} (w : Fin n → ℝ) (hw : ∀ j, 0 < w j)
(T : Finset (Fin n)) (hT : ¬ IsComplete T) :
∃ k < n,
∑ i ∈ complete n k, w i ≤ ∑ i ∈ T, w i ∧
∑ i ∈ T, w i < ∑ i ∈ complete n (k + 1), w i ∧
(∃ j ∈ T, k ≤ j.val) ∧
∃ θ : ℝ, 0 ≤ θ ∧ θ ≤ 1 ∧
θ * ((∑ i ∈ complete n k, w i) / (∑ i ∈ complete n k, w i + 1)) +
(1 - θ) * ((∑ i ∈ complete n (k + 1), w i) /
(∑ i ∈ complete n (k + 1), w i + 1)) =
(∑ i ∈ T, w i) / (∑ i ∈ T, w i + 1) := by sorry
end ChoiceRM.MNL
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. 24, proof of Proposition 6, definition of k* and eq. (15)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.