Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Expected revenue equals E[∑iri(ci−IiT)]\mathbb E[\sum_i r_i(c_i-I_i^T)]E[∑i​ri​(ci​−IiT​)]

Proved
PersonalizedAssortment.IB.revenue_eq_expected_sales

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

inventorymarkov-chainsp2o-batch-rm-cafterp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityrevenue-management

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. The expected revenue collected over the horizon is

Rev=∑t=1TE[∑i=1nri φizt(St(It−1)) 1[Iit−1>0]].\mathrm{Rev}=\sum_{t=1}^T\mathbb E\Big[\sum_{i=1}^n r_i\,\varphi_i^{z_t}\big(S^t(I^{t-1})\big)\,\mathbb 1[I_i^{t-1}>0]\Big].Rev=t=1∑T​E[i=1∑n​ri​φizt​​(St(It−1))1[Iit−1​>0]].

It equals the revenue of the units sold by the end of the horizon:

Rev  =  E[∑i=1nri (ci−IiT)].\mathrm{Rev}\;=\;\mathbb E\Big[\sum_{i=1}^n r_i\,(c_i-I_i^T)\Big].Rev=E[i=1∑n​ri​(ci​−IiT​)].

This is the identity the proof of Theorem 1 uses for the numerator of the competitive ratio.

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

/-- §A.3, p. 1549: the expected revenue of the algorithm equals `𝔼[∑_{i=1}^n r_i (c_i - I_i^T)]`,
the revenue of the units sold by the end of the horizon. -/
theorem revenue_eq_expected_sales {n : ℕ} {Z : Type*} (r : Fin n → ℝ) (c : Fin n → ℕ)
    (φ : Z → ChoiceModel n) {T : ℕ} (z : Fin T → Z)
    (sel : Fin T → (Fin n → ℕ) → Finset (Fin n)) :
    ibRevenue r c φ z sel =
      expectInv φ z sel c T le_rfl (fun I => ∑ i : Fin n, r i * ((c i : ℝ) - (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. 1549, Section A.3, proof of Theorem 1 ('On the other hand, the expected revenue of the inventory-balancing algorithm is equal to ...')
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.
  • φ\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.
  • σ\sigmaσ is an arbitrary map from periods and vectors I∈NnI\in\mathbb N^nI∈Nn to subsets of [n][n][n].

No further hypotheses are made.

Expectation operator. Et[f]\mathbb E_t[f]Et​[f] is defined 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 started at ccc that, in step sss from state III, lowers coordinate iii with probability φizs(σs(I))\varphi^{z_s}_i(\sigma_s(I))φizs​​(σs​(I)) and otherwise stays.

Conclusion. The statement asserts

∑t=0T−1Et[I↦∑i∈[n]ri φizt(σt(I)) 1[Ii>0]]  =  ET[I↦∑i∈[n]ri (ci−Ii)],\sum_{t=0}^{T-1}\mathbb E_t\Big[I\mapsto\sum_{i\in[n]} r_i\,\varphi^{z_t}_i(\sigma_t(I))\,\mathbf 1[I_i>0]\Big] \;=\; \mathbb E_T\Big[I\mapsto\sum_{i\in[n]} r_i\,(c_i - I_i)\Big],t=0∑T−1​Et​[I↦i∈[n]∑​ri​φizt​​(σt​(I))1[Ii​>0]]=ET​[I↦i∈[n]∑​ri​(ci​−Ii​)],

where ci−Iic_i - I_ici​−Ii​ is real subtraction.

Degenerate cases. If T=0T=0T=0, both sides are 000. 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