Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4 — Dual objective value

Proved
ChenCheckout.Protection.lemma_4

by Shuze Chen · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

assortment-optimizationonline-algorithmsp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let n,T be positive integers. The instance has positive integer inventories b_j, real prices r_j ≥ r_j^{disc} ≥ 0, nonempty downward-closed feasible add-on families excluding the primary, and substitutable single-purchase choice probabilities with residual no-purchase mass. An exact nonnegative-weight assortment oracle is supplied. The arrival list is arbitrary and fixed independently of all draws. Fix 0 ≤ δ < 1/2 and a positive sample count M. Fix any output of the concrete list constructor, with no good-estimation assumption. Physical expectations below keep these lists fixed. Assume a_j ≤ b_j, where a_j counts primary requests. Write d̄_j=E[D_j] for actual expected add-on sales, d̂_j for recorded counters, and d_j=max(d̄_j,d̂_j+δ) if d̂_j≥1/2−δ, otherwise d_j=d̄_j. The ideal assortment S_i* is the maximizer in Definition 7, excluding add-ons with a_j+2d_j≥b_j. The dual objective is at most

∑i2riai+∑j2rjdiscdj+∑iai∑j≠irjdisc(1−aj+2djbj)pij(Si∗).\sum_i2r_i a_i+\sum_j2r_j^{disc}d_j+\sum_i a_i\sum_{j\ne i}r_j^{disc}\left(1-\frac{a_j+2d_j}{b_j}\right)p_{ij}(S_i^*).i∑​2ri​ai​+j∑​2rjdisc​dj​+i∑​ai​j=i∑​rjdisc​(1−bj​aj​+2dj​​)pij​(Si∗​).

Differences from the source:

  • encoding: items and times numbered from 1 → items are Fin n and times are zero-based positions of a nonempty arrival list; reason: bijection of finite index sets; all inventories remain positive integers and all prices/probabilities remain real
  • encoding: expectations over independent simulation and purchase draws → finite operational Bernoulli trees with fresh draws, exact real leaf probabilities and finite weighted expectations; reason: for each fixed finite input these procedures have finitely many outcomes; no restriction to rational parameters or to independent product purchases is imposed
  • reading: step 9 minimizes a ratio also at zero estimates without a convention → zero-rate candidates have infinite selection ratio and are skipped when a positive-rate violating candidate exists; reason: I1; preserves zero purchase probabilities and never uses Lean real division by zero to select an item
  • reading: a small error parameter → 0 ≤ δ < 1/2 for procedure invariants, and 0 < δ < 1/2 in Theorem 3; reason: positive integer inventories make every shifted threshold nonnegative; δ=0 is also explicitly discussed in the source
  • encoding: analysis of the algorithm with generated lists fixed → a constructor output is selected through Generated, with physical expectations under its fixed-list run; reason: Generated means an actual operational branch, not a successful-sampling hypothesis; every branch is included
  • encoding: consistent oracle tie-breaking and an arbitrary minimizing item in Procedure 2 → the supplied deterministic maximizing oracle followed by deletion of excluded add-ons, and increasing-index ties for positive-rate ratio selection; reason: fixes choices left unspecified by the source; Procedure 1 removes the primary from its exclusion set before forming the exact source weight vector
Preamble
import Definitions.Def_ChenCheckout_Protection_Computation
import Definitions.Def_ChenCheckout_Protection_Choice
import Definitions.Def_ChenCheckout_Protection_Model
import Definitions.Def_ChenCheckout_Protection_Execution
import Definitions.Def_ChenCheckout_Protection_Construction
import Definitions.Def_ChenCheckout_Protection_Analysis
Formal statement
namespace ChenCheckout.Protection

theorem lemma_4 {n : ℕ} (inst : Instance n) (δ : ℝ) (hδ : 0 ≤ δ) (hδsmall : δ < 1/2)
    (M : ℕ) (hM : 0 < M) (xs : List (Fin n)) (hT : 0 < xs.length)
    (ha : ∀ j, arrivalCount xs j ≤ inst.b j) (c : Construction n)
    (hc : Generated inst δ M xs c) :
    DualValue inst xs (dualVector inst δ xs c) ≤ dualUpper inst δ xs c := by sorry

end ChenCheckout.Protection
Source
Chen, Ma, Simchi-Levi and Xin (2024), Mathematics of Operations Research 49(1), 297–325, https://doi.org/10.1287/moor.2023.1357, Lemma 4, printed p. 312 / PDF 16
Read-back

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

Setting. The instance, the hypotheses, and the generated construction ccc (lists Λ\LambdaΛ, counts DDD) are exactly as follows:

  • items [n][n][n] with n≥1n\ge1n≥1;
  • bj≥1b_j\ge1bj​≥1;
  • 0≤dj≤rj0\le d_j\le r_j0≤dj​≤rj​;
  • families Fi\mathcal F_iFi​ (containing ∅\emptyset∅, downward closed, excluding iii);
  • choice probabilities qAiq^i_AqAi​ (nonnegative, zero off AAA, total at most 111, substitutable);
  • an exact oracle OiO_iOi​ for nonnegative weights;
  • 0≤δ<120\le\delta<\tfrac120≤δ<21​;
  • M≥1M\ge1M≥1;
  • xxx of length T≥1T\ge1T≥1;
  • aj≤bja_j\le b_jaj​≤bj​ for all jjj, where aja_jaj​ is the number of occurrences of jjj in xxx;
  • ccc is an output, on some possibly probability-zero branch, of the threshold-based list construction.

That construction does the following for each customer:

  • it repeatedly estimates last-step add-on frequencies from MMM independent fixed-list simulations;
  • it appends the eligible item minimising (bj/2−δ−Dj)/Hj(b_j/2-\delta-D_j)/H_j(bj​/2−δ−Dj​)/Hj​, paired with that ratio, until every eligible item satisfies Dj+Hj≤bj/2−δD_j+H_j\le b_j/2-\deltaDj​+Hj​≤bj​/2−δ, or until n+1n+1n+1 iterations have run.

Derived quantities.

  • aˉj\bar a_jaˉj​ is the expected add-on sales of jjj under the fixed-list execution of xxx with Λ\LambdaΛ.
  • a^j=max⁡(aˉj,Dj+δ)\hat a_j=\max(\bar a_j,D_j+\delta)a^j​=max(aˉj​,Dj​+δ) if Dj≥12−δD_j\ge\tfrac12-\deltaDj​≥21​−δ, and a^j=aˉj\hat a_j=\bar a_ja^j​=aˉj​ otherwise.
  • ωj=dj(1−(aj+2a^j)/bj)\omega_j=d_j(1-(a_j+2\hat a_j)/b_j)ωj​=dj​(1−(aj​+2a^j​)/bj​).
  • ideal(i)={i}∪{j∈Oi(max⁡(0,ω)):aj+2a^j<bj}\mathrm{ideal}(i)=\{i\}\cup\{j\in O_i(\max(0,\omega)):a_j+2\hat a_j<b_j\}ideal(i)={i}∪{j∈Oi​(max(0,ω)):aj​+2a^j​<bj​}, and Ii=ideal(i)∖{i}I_i=\mathrm{ideal}(i)\setminus\{i\}Ii​=ideal(i)∖{i}.
  • θj=(rjaj+2dja^j)/bj\theta_j=(r_ja_j+2d_j\hat a_j)/b_jθj​=(rj​aj​+2dj​a^j​)/bj​.
  • λt=rxt(1−axt/bxt)+∑j≠xtωjqIxtxt(j)\lambda_t=r_{x_t}(1-a_{x_t}/b_{x_t})+\sum_{j\ne x_t}\omega_jq^{x_t}_{I_{x_t}}(j)λt​=rxt​​(1−axt​​/bxt​​)+∑j=xt​​ωj​qIxt​​xt​​(j).

Statement.

∑jbjθj+∑t=0T−1λt  ≤  ∑i2riai+∑j2dja^j+∑iai∑j≠iωj qIii(j).\sum_{j}b_j\theta_j+\sum_{t=0}^{T-1}\lambda_t\;\le\;\sum_i2r_ia_i+\sum_j2d_j\hat a_j+\sum_ia_i\sum_{j\neq i}\omega_j\,q^i_{I_i}(j).j∑​bj​θj​+t=0∑T−1​λt​≤i∑​2ri​ai​+j∑​2dj​a^j​+i∑​ai​j=i∑​ωj​qIi​i​(j).

Here the last factor is literally marginal(i,j,ideal(i))(i,j,\mathrm{ideal}(i))(i,j,ideal(i)), which for j≠ij\ne ij=i equals qIii(j)q^i_{I_i}(j)qIi​i​(j).

Degenerate cases.

  • Items with ai=0a_i=0ai​=0 contribute nothing to the first and third sums on the right.
  • "Generated" includes probability-zero outputs.
Human review
  • Endorsed by Community (Bot) · Oct 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 29, 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