Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Expected dual value: E[∑tλt]=E[∑iri∑k=IiT+1ciΨ(k/ci)]\mathbb E[\sum_t\lambda^t]=\mathbb E[\sum_i r_i\sum_{k=I_i^T+1}^{c_i}\Psi(k/c_i)]E[∑t​λt]=E[∑i​ri​∑k=IiT​+1ci​​Ψ(k/ci​)]

Proved
PersonalizedAssortment.IB.expected_dual_value

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

dualityinventorymarkov-chainsp2o-batch-rm-cafterp2o-gran-per-chapterp2o-plan-paperp2o-v1probability

Let Ψ\PsiΨ be any function with Ψ(0)=0\Psi(0)=0Ψ(0)=0. Let St(⋅)S^t(\cdot)St(⋅) be any selection rule and let I0=c,I1,…,ITI^0=c,I^1,\dots,I^TI0=c,I1,…,IT be the inventory process it generates. Define λt=∑i∈StriΨ(Iit−1/ci)φizt(St)\lambda^t=\sum_{i\in S^t}r_i\Psi(I_i^{t-1}/c_i)\varphi_i^{z_t}(S^t)λt=∑i∈St​ri​Ψ(Iit−1​/ci​)φizt​​(St) with St=St(It−1)S^t=S^t(I^{t-1})St=St(It−1). Then

E[∑t=1Tλt]  =  E[∑i=1nri∑k=IiT+1ciΨ ⁣(kci)].\mathbb E\Big[\sum_{t=1}^T\lambda^t\Big]\;=\;\mathbb E\Big[\sum_{i=1}^n r_i\sum_{k=I_i^T+1}^{c_i}\Psi\!\left(\frac k{c_i}\right)\Big].E[t=1∑T​λt]=E[i=1∑n​ri​k=IiT​+1∑ci​​Ψ(ci​k​)].

The identity expresses the expected objective of the dual certificate through the final inventory alone. It is the computation that precedes the weak-duality bound in the proof of Theorem 1.

Formalization Note E[∑tλt]\mathbb E\big[\sum_t\lambda^t\big]E[∑t​λt] is written as ∑tE[λt(It−1)]\sum_t\mathbb E[\lambda^t(I^{t-1})]∑t​E[λt(It−1)]. The paper uses Lemma 2 to know that a product with zero inventory is never offered. Here the dynamics Iit=max⁡{Iit−1−1,0}I_i^t=\max\{I_i^{t-1}-1,0\}Iit​=max{Iit−1​−1,0} are used instead, together with Ψ(0)=0\Psi(0)=0Ψ(0)=0: a stocked-out product contributes 000 to both sides whether or not it is offered. So the identity holds for every selection rule, and neither Assumption 1 nor Lemma 2 is needed.

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

/-- The expected-dual display of §A.3 (pp. 1548–1549):
`𝔼[∑_{t=1}^T λ^t] = 𝔼[∑_{i=1}^n r_i ∑_{k=I_i^T+1}^{c_i} Ψ(k/c_i)]`, where `λ^t` is evaluated at the
inventories `I^{t-1}` at the start of the period and the right side at the final inventories
`I^T`. -/
theorem expected_dual_value {n : ℕ} {Z : Type*} (r : Fin n → ℝ) (c : Fin n → ℕ)
    (φ : Z → ChoiceModel n) (Ψ : ℝ → ℝ) (hΨ0 : Ψ 0 = 0) {T : ℕ} (z : Fin T → Z)
    (sel : Fin T → (Fin n → ℕ) → Finset (Fin n)) :
    ∑ t : Fin T, expectInv φ z sel c t.val t.isLt.le (lamIB Ψ r c φ z sel t) =
      expectInv φ z sel c T le_rfl
        (fun I => ∑ i : Fin n, r i * ∑ k ∈ Finset.Ioc (I i) (c i), Ψ ((k : ℝ) / (c 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, pp. 1548-1549, Section A.3, proof of Theorem 1, display beginning 'E[sum_t lambda^t] =' and the sentences after it
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}.
  • rir_iri​ are arbitrary reals and cic_ici​ are arbitrary naturals (possibly 000).
  • φ\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).
  • z0,…,zT−1∈Zz_0,\dots,z_{T-1}\in Zz0​,…,zT−1​∈Z.
  • σ\sigmaσ is an arbitrary selection mapping each ttt and each I∈NnI\in\mathbb N^nI∈Nn to a subset σt(I)⊆[n]\sigma_t(I)\subseteq[n]σt​(I)⊆[n], not required to satisfy any optimality or feasibility property.
  • Ψ:R→R\Psi : \mathbb R\to\mathbb RΨ:R→R is arbitrary except that Ψ(0)=0\Psi(0)=0Ψ(0)=0.

Expectation operator. Define Et[f]\mathbb E_t[f]Et​[f] for t≤Tt\le Tt≤T by the recursion

E0[f]=f(c),Et+1[f]=Et[I↦(1−∑i∈Sφizt(S))f(I)+∑i∈Sφizt(S) f(I−i)],\mathbb E_0[f] = f(c), \qquad \mathbb E_{t+1}[f] = \mathbb E_t\Big[I\mapsto \big(1-\textstyle\sum_{i\in S}\varphi^{z_t}_i(S)\big)f(I) + \sum_{i\in S}\varphi^{z_t}_i(S)\,f(I^{-i})\Big],E0​[f]=f(c),Et+1​[f]=Et​[I↦(1−∑i∈S​φizt​​(S))f(I)+∑i∈S​φizt​​(S)f(I−i)],

where S=σt(I)S=\sigma_t(I)S=σt​(I) and I−iI^{-i}I−i lowers coordinate iii by one, floored at 000. This is the expectation of f(It)f(I^t)f(It) for the chain that:

  • starts at ccc;
  • in step sss, from state III, lowers coordinate iii with probability φizs(σs(I))\varphi^{z_s}_i(\sigma_s(I))φizs​​(σs​(I)) for each i∈σs(I)i \in \sigma_s(I)i∈σs​(I);
  • otherwise stays.

Conclusion. Write λt(I)=∑i∈σt(I)Ψ(Ii/ci) ri φizt(σt(I))\lambda_t(I) = \sum_{i\in\sigma_t(I)}\Psi(I_i/c_i)\,r_i\,\varphi^{z_t}_i(\sigma_t(I))λt​(I)=∑i∈σt​(I)​Ψ(Ii​/ci​)ri​φizt​​(σt​(I)). The statement asserts

∑t=0T−1Et[λt]  =  ET[I↦∑i∈[n]ri∑k=Ii+1ciΨ ⁣(kci)],\sum_{t=0}^{T-1}\mathbb E_t\big[\lambda_t\big] \;=\; \mathbb E_T\Big[I\mapsto \sum_{i\in[n]} r_i \sum_{k=I_i+1}^{c_i}\Psi\!\left(\frac{k}{c_i}\right)\Big],t=0∑T−1​Et​[λt​]=ET​[I↦i∈[n]∑​ri​k=Ii​+1∑ci​​Ψ(ci​k​)],

where the inner sum runs over the integers in (Ii,ci](I_i, c_i](Ii​,ci​] and is empty when Ii≥ciI_i\ge c_iIi​≥ci​.

Degenerate cases.

  • If T=0T=0T=0, both sides are 000, since the right side is evaluated at I=cI=cI=c.
  • If ci=0c_i=0ci​=0, every ratio for product iii uses x/0=0x/0=0x/0=0, giving Ψ(0)=0\Psi(0)=0Ψ(0)=0, and the inner range is empty.
  • If n=0n=0n=0, both sides are 000.
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