Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 2: inventory balancing never offers a stocked-out product

Proved
PersonalizedAssortment.IB.lemma2_never_offers_stocked_out

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

assortment-optimizationinventoryonline-algorithmsp2o-batch-rm-cafterp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let ri>0r_i>0ri​>0 and ci≥1c_i\ge1ci​≥1, and let S\mathcal SS be a family of feasible assortments with ∅∈S\emptyset\in\mathcal S∅∈S that is closed under removing a product: S∈SS\in\mathcal SS∈S and j∈Sj\in Sj∈S imply S∖{j}∈SS\setminus\{j\}\in\mathcal SS∖{j}∈S. Suppose the choice models satisfy Assumption 1 (substitutability). Let Ψ\PsiΨ be a penalty function (Ψ:[0,1]→[0,1]\Psi:[0,1]\to[0,1]Ψ:[0,1]→[0,1] increasing, Ψ(0)=0\Psi(0)=0Ψ(0)=0, Ψ(1)=1\Psi(1)=1Ψ(1)=1) and let St(⋅)S^t(\cdot)St(⋅) be an inventory-balancing selection rule. That rule maximizes the index and, among the maximizers, has the fewest products. Then for every period ttt and every inventory vector 0≤I≤c0\le I\le c0≤I≤c,

i∈St(I)  ⟹  Ii>0.i\in S^t(I)\;\Longrightarrow\;I_i>0 .i∈St(I)⟹Ii​>0.

In words, the algorithm never offers an assortment that contains a product with zero remaining inventory.

Lemma 2 shows that inventory balancing respects the capacity constraints: it never tries to sell a unit it does not have.

Formalization Note The paper proves Lemma 2 in its online appendix and states it under Assumption 1 only. Closure of S\mathcal SS under removing a product is added, because without it the lemma is false. For example, take S={∅,{1,2}}\mathcal S=\{\emptyset,\{1,2\}\}S={∅,{1,2}} with product 111 stocked out and product 222 in stock with positive index: the rule must offer {1,2}\{1,2\}{1,2}. Every example family in the paper (cardinality, budget and shelf-space constraints) is closed under removal. The claim is made for every inventory vector between 000 and ccc, which covers every state the process can reach.

Preamble
import Mathlib
import Definitions.Def_PersonalizedAssortment_IB_ChoiceModel
import Definitions.Def_PersonalizedAssortment_IB_PenaltyFunction
import Definitions.Def_PersonalizedAssortment_IB_InventoryBalancing
Formal statement
namespace PersonalizedAssortment.IB

/-- Lemma 2 (p. 1538): under Assumption 1, the inventory-balancing algorithm never offers an
assortment containing a product with zero remaining inventory. Stated for every inventory vector
`I ≤ c` and every period. Added hypothesis `hdel`: the feasible family is closed under removing a
product (without it the lemma is false). -/
theorem lemma2_never_offers_stocked_out {n : ℕ} {Z : Type*} (r : Fin n → ℝ)
    (hr : ∀ i, 0 < r i) (c : Fin n → ℕ) (hc : ∀ i, 0 < c i) (𝒮 : Finset (Finset (Fin n)))
    (h𝒮 : ∅ ∈ 𝒮) (hdel : ∀ S ∈ 𝒮, ∀ j ∈ S, S.erase j ∈ 𝒮) (φ : Z → ChoiceModel n)
    (hsub : Substitutable 𝒮 φ) (Ψ : ℝ → ℝ) (hΨ : IsPenaltyFunction Ψ) {T : ℕ} (z : Fin T → Z)
    (sel : Fin T → (Fin n → ℕ) → Finset (Fin n)) (hsel : IsIBRule Ψ r c 𝒮 φ z sel)
    (t : Fin T) (I : Fin n → ℕ) (hI : ∀ i, I i ≤ c i) :
    ∀ i ∈ sel t I, 0 < I i := by sorry

end PersonalizedAssortment.IB
Source
Golrezaei, Nazerzadeh, Rusmevichientong, Real-Time Optimization of Personalized Assortments, Management Sci. 60(6), 2014, https://doi.org/10.1287/mnsc.2014.1939, p. 1538, Lemma 2
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Data.

  • Products are [n][n][n] and periods are {0,…,T−1}\{0,\dots,T-1\}{0,…,T−1}.
  • ri>0r_i>0ri​>0 and naturals ci>0c_i>0ci​>0 for all iii.
  • S\mathcal SS is a finite family of subsets of [n][n][n] such that ∅∈S\emptyset\in\mathcal S∅∈S, and for every S∈SS\in\mathcal SS∈S and every j∈Sj\in Sj∈S also S∖{j}∈SS\setminus\{j\}\in\mathcal SS∖{j}∈S.
  • φ\varphiφ assigns to each z∈Zz\in Zz∈Z a choice model (nonnegative φiz(S)\varphi^z_i(S)φiz​(S), zero for i∉Si\notin Si∈/S, with ∑i∈Sφiz(S)≤1\sum_{i\in S}\varphi^z_i(S)\le1∑i∈S​φiz​(S)≤1).

Substitutability hypothesis. For every z∈Zz\in Zz∈Z, every S∈SS\in\mathcal SS∈S and all i≠ji\ne ji=j,

φiz(S∪{j})≤φiz(S).\varphi^z_i(S\cup\{j\})\le\varphi^z_i(S).φiz​(S∪{j})≤φiz​(S).

Penalty hypothesis. Ψ\PsiΨ maps [0,1][0,1][0,1] into [0,1][0,1][0,1], is nondecreasing on [0,1][0,1][0,1], and has Ψ(0)=0\Psi(0)=0Ψ(0)=0 and Ψ(1)=1\Psi(1)=1Ψ(1)=1.

Selection hypothesis. For every period and every J∈NnJ\in\mathbb N^nJ∈Nn:

  • σt(J)∈S\sigma_t(J)\in\mathcal Sσt​(J)∈S;
  • σt(J)\sigma_t(J)σt​(J) maximizes S↦∑i∈SΨ(Ji/ci) ri φizt(S)S\mapsto\sum_{i\in S}\Psi(J_i/c_i)\,r_i\,\varphi^{z_t}_i(S)S↦∑i∈S​Ψ(Ji​/ci​)ri​φizt​​(S) over S\mathcal SS;
  • no maximizer in S\mathcal SS has fewer elements than σt(J)\sigma_t(J)σt​(J).

Conclusion. For any period ttt and any vector I∈NnI\in\mathbb N^nI∈Nn with Ii≤ciI_i\le c_iIi​≤ci​ for all iii, every product i∈σt(I)i\in\sigma_t(I)i∈σt​(I) has Ii>0I_i>0Ii​>0. The vector III is not required to be reachable by any process.

Degenerate cases. If T=0T=0T=0, there is no period, and the statement is vacuous. If n=0n=0n=0, σt(I)\sigma_t(I)σt​(I) is empty and the conclusion holds trivially.

Human review
  • Endorsed by Shuze Chen · Oct 21, 2026

    Confirmed by the moderator at approval.

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