Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 2 — Preservation of shifted thresholds

Proved
ChenCheckout.Protection.proposition_2

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, M≥1 and an iteration reached by Procedure 2. If all current counters satisfy d_j^curr≤b_j/2−δ, then every eligible item’s updated counter satisfies the same inequality, in either update branch.

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: 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 proposition_2 {n : ℕ} (inst : Instance n) (δ : ℝ) (hδ : 0 ≤ δ) (hδsmall : δ < 1/2)
    (M : ℕ) (hM : 0 < M) (xs : List (Fin n)) (hT : 0 < xs.length) (e : Iteration n)
    (he : Reachable inst δ M xs e)
    (hd : ∀ j, e.counts j ≤ threshold inst δ j) :
    ∀ j ∈ eligible e, updatedCounts inst δ e j ≤ threshold inst δ j := 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, Proposition 2, printed p. 309 / PDF 13
Read-back

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

Setting. The instance is as follows:

  • 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);
  • qiq^iqi (nonnegative, zero off AAA, total at most 111, substitutable);
  • an exact oracle for w≥0w\ge0w≥0.

The hypotheses are:

  • 0≤δ<120\le\delta<\tfrac120≤δ<21​;
  • M≥1M\ge1M≥1;
  • ∣x∣≥1|x|\ge1∣x∣≥1;
  • e=(u,i,Π,L,D,H)e=(u,i,\Pi,L,D,H)e=(u,i,Π,L,D,H) appears in the trace of some outcome, possibly of probability zero, of the list-construction computation on (δ,M,x)(\delta,M,x)(δ,M,x).

That computation, for each customer:

  • estimates HHH from MMM simulated fixed-list runs;
  • appends eligible minimal-ratio items with their ratio, updating counts;
  • stops when the threshold test passes, or after n+1n+1n+1 rounds.

Iteration quantities. With βj=bj/2−δ\beta_j=b_j/2-\deltaβj​=bj​/2−δ:

  • eligible =[n]∖({i}∪{items in Π or L})=[n]\setminus(\{i\}\cup\{\text{items in }\Pi\text{ or }L\})=[n]∖({i}∪{items in Π or L});
  • passes means Dj+Hj≤βjD_j+H_j\le\beta_jDj​+Hj​≤βj​ for all eligible jjj;
  • ρ\rhoρ is the minimum of (βj−Dj)/Hj(\beta_j-D_j)/H_j(βj​−Dj​)/Hj​ over eligible jjj with Hj>0H_j>0Hj​>0 (the smallest index attaining it), or 000 if there are none;
  • Dj+=Dj+(passes?1:ρ)HjD^+_j=D_j+(\text{passes}?1:\rho)H_jDj+​=Dj​+(passes?1:ρ)Hj​ for eligible jjj.

Statement. If Dj≤βjD_j\le\beta_jDj​≤βj​ for all jjj, then Dj+≤βjD^+_j\le\beta_jDj+​≤βj​ for every eligible jjj.

Degenerate cases.

  • If no item is eligible, the conclusion is vacuous.
  • Nothing is assumed about the accuracy or sign of HHH.
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