Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 4 — Pathwise primary sales

Proved
ChenCheckout.Protection.proposition_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. On every physical execution branch, including branches of zero probability, the number of full-price sales of j equals min{b_j−D_j,a_j}, for every item j.

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: units sold and their difference → natural-valued counts cast into real subtraction and minimum; reason: avoids truncated subtraction hiding overdraw; the physical implementation never sells unavailable stock
  • 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_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) :
    (runFixed inst xs c.lists).All (fun s => ∀ j,
      (primaryCount s j : ℝ) = min ((inst.b j : ℝ) - addonCount s j) (arrivalCount xs 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 4, printed p. 313 / PDF 17
Read-back

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

Setting. The instance and hypotheses are as follows:

  • n≥1n\ge1n≥1 items;
  • 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 qiq^iqi (nonnegative, zero off AAA, total at most 111, substitutable on Fi\mathcal F_iFi​);
  • an exact oracle OiO_iOi​ for w≥0w\ge0w≥0, and an oracle computation that returns Oi(w)O_i(w)Oi​(w) on every outcome;
  • 0≤δ<120\le\delta<\tfrac120≤δ<21​;
  • M≥1M\ge1M≥1;
  • ∣x∣≥1|x|\ge1∣x∣≥1;
  • aj≤bja_j\le b_jaj​≤bj​ for all jjj, where aja_jaj​ counts occurrences of jjj in xxx;
  • ccc is an output of the list-construction computation on some branch, possibly of probability zero, with lists Λ\LambdaΛ.

Fixed-list execution of xxx with Λ\LambdaΛ. Stock starts at bbb. For customer ttt of type iii:

  • No stock. If stocki=0_i=0i​=0, the offer is ∅\emptyset∅ and the sale is recorded with no purchase and no stock change.
  • Offer. Otherwise:
    • a stop index kkk is drawn along list ttt using coins pℓp_\ellpℓ​, or list ttt is taken as empty if missing;
    • EEE is the set of zero-stock items, items on lists 0..t−10..t-10..t−1, and the first kkk entries of list ttt;
    • the offer is S={i}∪(Oi(wE)∖E)S=\{i\}\cup(O_i(w^E)\setminus E)S={i}∪(Oi​(wE)∖E) with wjE=0w^E_j=0wjE​=0 on EEE and djd_jdj​ off EEE.
  • Purchase.
    • The customer buys iii, whose stock decreases by 1 (truncated).
    • At most one add-on a∈S∖{i}a\in S\setminus\{i\}a∈S∖{i} is drawn categorically with masses qS∖{i}iq^i_{S\setminus\{i\}}qS∖{i}i​; the stock of aaa decreases by 1 (truncated).

Counts.

  • primaryCountj_jj​ is the number of sales with primary jjj where jjj was in the offer.
  • addonCountj_jj​ is the number of sales with add-on jjj.

Statement. On every outcome of this execution, including probability-zero branches, every item jjj satisfies, in real arithmetic:

primaryCountj=min⁡(bj−addonCountj,  aj).\mathrm{primaryCount}_j=\min\bigl(b_j-\mathrm{addonCount}_j,\;a_j\bigr).primaryCountj​=min(bj​−addonCountj​,aj​).

Degenerate cases.

  • The equation is required on every branch, not only almost surely.
  • bj−addonCountjb_j-\mathrm{addonCount}_jbj​−addonCountj​ is a real difference and could be negative.
  • δ=0\delta=0δ=0 is allowed.
  • δ\deltaδ and MMM enter only through which ccc are generated.
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