Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.1, p. 16, first inequality — ΔJ_t(x + 1) ≤ ΔJ_t(x): the value function is concave in capacity

Proved
RobustMNL.Dynamic.marginalValue_antitone_capacity

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

dynamic-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1revenue-management

In the robust capacity-allocation model, for every period 1≤t≤T1 \le t \le T1≤t≤T and every capacity level x≥1x \ge 1x≥1,

ΔJt(x+1)≤ΔJt(x),\Delta J_t(x+1) \le \Delta J_t(x),ΔJt​(x+1)≤ΔJt​(x),

where ΔJt(x)=Jt(x)−Jt(x−1)\Delta J_t(x) = J_t(x) - J_t(x-1)ΔJt​(x)=Jt​(x)−Jt​(x−1) is the marginal value of capacity. Equivalently, x↦Jt(x)x \mapsto J_t(x)x↦Jt​(x) is concave on N\mathbb NN.

Concavity in capacity is the first half of Theorem 4.1, and gives the nonnegative increment ΔJt+1(x)−ΔJt+1(x+1)\Delta J_{t+1}(x) - \Delta J_{t+1}(x+1)ΔJt+1​(x)−ΔJt+1​(x+1) used in Theorem 4.3.

Formalization Note The paper states the theorem "for any x∈{0,1,…,C}x \in \{0, 1, \dots, C\}x∈{0,1,…,C}"; at x=0x = 0x=0 the term ΔJt(0)=Jt(0)−Jt(−1)\Delta J_t(0) = J_t(0) - J_t(-1)ΔJt​(0)=Jt​(0)−Jt​(−1) is undefined, so the statement is made for x≥1x \ge 1x≥1. JJJ is defined for all x∈Nx \in \mathbb Nx∈N (the recursion does not use CCC), so the statement for all x≥1x \ge 1x≥1 contains the paper's for every CCC. Revenues are arbitrary reals.

Preamble
import Mathlib
import Definitions.Def_RobustMNL_Dynamic_ValueFunction
Formal statement
namespace RobustMNL.Dynamic

theorem marginalValue_antitone_capacity {n : ℕ} (T : ℕ) (V : ℕ → Set (ℝ × (Fin n → ℝ)))
    (r : Fin n → ℝ) (hV : IsUncertaintySeq T V) (t x : ℕ) (ht : 1 ≤ t) (htT : t ≤ T) (hx : 1 ≤ x) :
    marginalValue T V r t (x + 1) ≤ marginalValue T V r t x := by sorry

end RobustMNL.Dynamic
Source
Rusmevichientong, Topaloglu, Robust Assortment Optimization in Revenue Management Under the Multinomial Logit Choice Model, Operations Research (2012), doi:10.1287/opre.1120.1063, authors' manuscript of 20 Sep 2011, Theorem 4.1 (first inequality), p. 16; proof in Appendix A, pp. 30–32
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

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