Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The inventory-balancing dual certificate (λ,θ)(\lambda,\theta)(λ,θ) is feasible for Dual({zt})\mathrm{Dual}(\{z_t\})Dual({zt​})

Proved
PersonalizedAssortment.IB.dual_certificate_feasible

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

dualitylinear-programmingonline-algorithmsp2o-batch-rm-cafterp2o-gran-per-chapterp2o-plan-paperp2o-v1primal-dual

Let ri>0r_i>0ri​>0 and ci≥1c_i\ge1ci​≥1, let ∅∈S\emptyset\in\mathcal S∅∈S, and 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). Let St(⋅)S^t(\cdot)St(⋅) be an inventory-balancing selection rule. Consider any inventory path c=I0≥I1≥⋯≥ITc=I^0\ge I^1\ge\dots\ge I^Tc=I0≥I1≥⋯≥IT, compared coordinatewise. Define

θi=ri(1−Ψ(IiT/ci)),λt=∑i∈Stri Ψ(Iit−1/ci) φizt(St),St=St(It−1).\theta_i=r_i\big(1-\Psi(I_i^T/c_i)\big),\qquad \lambda^t=\sum_{i\in S^t}r_i\,\Psi(I_i^{t-1}/c_i)\,\varphi_i^{z_t}(S^t),\quad S^t=S^t(I^{t-1}).θi​=ri​(1−Ψ(IiT​/ci​)),λt=i∈St∑​ri​Ψ(Iit−1​/ci​)φizt​​(St),St=St(It−1).

Then (λ,θ)(\lambda,\theta)(λ,θ) is feasible for Dual({zt}t=1T)\mathrm{Dual}(\{z_t\}_{t=1}^T)Dual({zt​}t=1T​):

  1. λt≥∑i=1nφizt(S)(ri−θi)\lambda^t\ge\sum_{i=1}^n\varphi_i^{z_t}(S)(r_i-\theta_i)λt≥∑i=1n​φizt​​(S)(ri​−θi​) for every period ttt and every S∈SS\in\mathcal SS∈S;
  2. θi≥0\theta_i\ge0θi​≥0 for every product iii.

Every realized path of the inventory process is non-increasing and starts at ccc, so the certificate is dual feasible with probability one. The certificate is what links the algorithm to the benchmark LP.

Formalization Note The paper writes the chain of inequalities only at S=StS=S^tS=St. Feasibility means every constraint S∈SS\in\mathcal SS∈S holds, and that is what is stated.

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

/-- §A.3, p. 1548: along any inventory path `c = I 0 ≥ I 1 ≥ ⋯ ≥ I T` on which the
inventory-balancing rule is followed, `θ_i = r_i (1 - Ψ(I_i^T/c_i))` and
`λ^t = ∑_{i ∈ S^t} r_i Ψ(I_i^{t-1}/c_i) φ_i^{z_t}(S^t)` form a feasible solution of
`Dual({z_t})`: every constraint, for every period and every `S ∈ 𝒮`, holds. -/
theorem dual_certificate_feasible {n : ℕ} {Z : Type*} (r : Fin n → ℝ) (hr : ∀ i, 0 < r i)
    (c : Fin n → ℕ) (hc : ∀ i, 0 < c i) (𝒮 : Finset (Finset (Fin n))) (h𝒮 : ∅ ∈ 𝒮)
    (φ : Z → ChoiceModel n) (Ψ : ℝ → ℝ) (hΨ : IsPenaltyFunction Ψ) {T : ℕ} (z : Fin T → Z)
    (sel : Fin T → (Fin n → ℕ) → Finset (Fin n)) (hsel : IsIBRule Ψ r c 𝒮 φ z sel)
    (I : ℕ → Fin n → ℕ) (hI0 : I 0 = c) (hmono : ∀ t < T, ∀ i, I (t + 1) i ≤ I t i) :
    DualFeasible r 𝒮 φ z (fun t => lamIB Ψ r c φ z sel t (I t.val)) (thetaIB Ψ r c (I T)) := 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. 1548, Section A.3, proof of Theorem 1 (construction of theta_i, lambda^t and the display showing dual feasibility)
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 ci>0c_i > 0ci​>0 (natural) for every iii.
  • S\mathcal SS is a finite family of subsets of [n][n][n] containing ∅\emptyset∅.
  • φ\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)\le 1∑i∈S​φiz​(S)≤1).
  • z0,…,zT−1∈Zz_0,\dots,z_{T-1}\in Zz0​,…,zT−1​∈Z.

Penalty hypothesis. Ψ:R→R\Psi : \mathbb R\to\mathbb RΨ:R→R 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. σ\sigmaσ maps each period ttt and each vector I∈NnI\in\mathbb N^nI∈Nn to a set σt(I)\sigma_t(I)σt​(I). For every ttt and every III:

  • σt(I)∈S\sigma_t(I)\in\mathcal Sσt​(I)∈S;
  • σt(I)\sigma_t(I)σt​(I) maximizes S↦∑i∈SΨ(Ii/ci) ri φizt(S)S\mapsto \sum_{i\in S}\Psi(I_i/c_i)\,r_i\,\varphi^{z_t}_i(S)S↦∑i∈S​Ψ(Ii​/ci​)ri​φizt​​(S) over S\mathcal SS;
  • every maximizer in S\mathcal SS has at least as many elements as σt(I)\sigma_t(I)σt​(I).

Path hypothesis. I0,I1,I2,…I^0, I^1, I^2,\dotsI0,I1,I2,… is a sequence of vectors in Nn\mathbb N^nNn with I0=cI^0 = cI0=c and Iit+1≤IitI^{t+1}_i \le I^t_iIit+1​≤Iit​ for every t<Tt < Tt<T and every iii. The path is not required to be generated by σ\sigmaσ, nor to decrease by at most one per step.

Conclusion. Define

λt=∑i∈σt(It)Ψ ⁣(Iitci)ri φizt(σt(It)),θi=ri(1−Ψ ⁣(IiTci)).\lambda_t = \sum_{i\in\sigma_t(I^t)} \Psi\!\left(\frac{I^t_i}{c_i}\right) r_i\,\varphi^{z_t}_i\big(\sigma_t(I^t)\big), \qquad \theta_i = r_i\left(1 - \Psi\!\left(\frac{I^T_i}{c_i}\right)\right).λt​=i∈σt​(It)∑​Ψ(ci​Iit​​)ri​φizt​​(σt​(It)),θi​=ri​(1−Ψ(ci​IiT​​)).

The statement asserts:

  • for every period ttt and every S∈SS\in\mathcal SS∈S, ∑i∈[n]φizt(S) (ri−θi)≤λt\sum_{i\in[n]}\varphi^{z_t}_i(S)\,(r_i - \theta_i) \le \lambda_t∑i∈[n]​φizt​​(S)(ri​−θi​)≤λt​;
  • θi≥0\theta_i \ge 0θi​≥0 for every iii.

Degenerate cases.

  • If T=0T = 0T=0, only θi≥0\theta_i \ge 0θi​≥0 is asserted. Here θi=ri(1−Ψ(1))=0\theta_i = r_i(1 - \Psi(1)) = 0θi​=ri​(1−Ψ(1))=0.
  • If n=0n = 0n=0, the claim is 0≤00 \le 00≤0 for each ttt.
  • The hypothesis ∅∈S\emptyset\in\mathcal S∅∈S makes S\mathcal SS nonempty, so the selection hypothesis is satisfiable.
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