Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1, p. 15 — optimal nondominated offers and monotone largest index

Proved
ChoiceRM.Policy.theorem_1

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

discrete-choicedynamic-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1revenue-management

Consider a finite set of fare products with a proper choice model, nonnegative fares and a constant arrival probability λ∈[0,1]\lambda\in[0,1]λ∈[0,1]. List every nondominated offer set exactly once as S1,…,SmS_1,\ldots,S_mS1​,…,Sm​, in nondecreasing purchase-probability order. Let Vt(x)V_t(x)Vt​(x) be the optimal value with ttt periods and xxx units remaining, and ΔVt−1(x)\Delta V_{t-1}(x)ΔVt−1​(x) its marginal capacity value. At every t,x≥1t,x\ge1t,x≥1, a greatest index k∗k^*k∗ maximizing Rk−QkΔVt−1(x)R_k-Q_k\Delta V_{t-1}(x)Rk​−Qk​ΔVt−1​(x) exists. Every maximizing index gives an optimal offer set, and

Vt(x)=λ(Rk∗−Qk∗ΔVt−1(x))+Vt−1(x).V_t(x)=\lambda\bigl(R_{k^*}-Q_{k^*}\Delta V_{t-1}(x)\bigr)+V_{t-1}(x).Vt​(x)=λ(Rk∗​−Qk∗​ΔVt−1​(x))+Vt−1​(x).

For fixed ttt, the greatest optimal index is nondecreasing with remaining capacity xxx. For fixed xxx, it is nonincreasing with the number ttt of periods remaining. This gives the paper's ordered optimal policy, including the specified rule for ties.

Formalization Note Fin n indexes products, including the empty offer set among subsets. The ordered family is exhaustive and has no repeats. Time counts backward as periods remaining. The assumptions 0≤λ≤10\le\lambda\le10≤λ≤1 state that arrival is a probability; t,x≥1t,x\ge1t,x≥1 avoid undefined decisions and marginal values at zero. The fare-order convention r1≥⋯≥rnr_1\ge\cdots\ge r_nr1​≥⋯≥rn​ is omitted because no result in Section 2 uses it.

Preamble
import Mathlib
import Definitions.Def_RevenueManagement_singleResource
import Definitions.Def_ChoiceRM_Policy_Dominance
import Definitions.Def_ChoiceRM_Policy_Value
Formal statement
namespace ChoiceRM.Policy

open RevenueManagement

/-- Theorem 1 (p. 15): choose a nondominated set attaining the stage maximum;
the greatest optimal index rises with capacity and falls with time remaining. -/
theorem theorem_1 {n m : ℕ} (lam : ℝ) (hlam0 : 0 ≤ lam) (hlam1 : lam ≤ 1)
    (P : Finset (Fin n) → Fin n → ℝ) (hP : IsChoiceModel P)
    (r : Fin n → ℝ) (hr : ∀ j, 0 ≤ r j)
    (Sq : Fin m → Finset (Fin n)) (hSq : IsOrderedNondominated P r Sq) :
    (∀ t x, 1 ≤ t → 1 ≤ x →
      ∃ k : Fin m,
        IsLargestMaximizer P r Sq (deltaV lam P r (t - 1) x) k ∧
        (∀ l : Fin m,
          (∀ i : Fin m,
            expRevenue P r (Sq i) - purchaseProb P (Sq i) * deltaV lam P r (t - 1) x ≤
              expRevenue P r (Sq l) - purchaseProb P (Sq l) * deltaV lam P r (t - 1) x) →
          IsOptimalOffer lam P r t x (Sq l)) ∧
        V lam P r t x =
          lam * (expRevenue P r (Sq k) - purchaseProb P (Sq k) *
            deltaV lam P r (t - 1) x) + V lam P r (t - 1) x) ∧
    (∀ t x x' (hx : 1 ≤ x) (hxx' : x ≤ x') (ht : 1 ≤ t)
      (k k' : Fin m),
      IsLargestMaximizer P r Sq (deltaV lam P r (t - 1) x) k →
      IsLargestMaximizer P r Sq (deltaV lam P r (t - 1) x') k' →
      k ≤ k') ∧
    (∀ x t t' (hx : 1 ≤ x) (ht : 1 ≤ t) (htt' : t ≤ t')
      (k k' : Fin m),
      IsLargestMaximizer P r Sq (deltaV lam P r (t - 1) x) k →
      IsLargestMaximizer P r Sq (deltaV lam P r (t' - 1) x) k' →
      k' ≤ k) := by sorry

end ChoiceRM.Policy
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. 15, Theorem 1; p. 12, equation (7)
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