Proposition 4 — Pathwise primary sales
ProvedChenCheckout.Protection.proposition_4Let 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
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
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. The instance and hypotheses are as follows:
- items;
- ;
- ;
- families (containing , downward closed, excluding );
- choice probabilities (nonnegative, zero off , total at most , substitutable on );
- an exact oracle for , and an oracle computation that returns on every outcome;
- ;
- ;
- ;
- for all , where counts occurrences of in ;
- is an output of the list-construction computation on some branch, possibly of probability zero, with lists .
Fixed-list execution of with . Stock starts at . For customer of type :
- No stock. If stock, the offer is and the sale is recorded with no purchase and no stock change.
- Offer. Otherwise:
- a stop index is drawn along list using coins , or list is taken as empty if missing;
- is the set of zero-stock items, items on lists , and the first entries of list ;
- the offer is with on and off .
- Purchase.
- The customer buys , whose stock decreases by 1 (truncated).
- At most one add-on is drawn categorically with masses ; the stock of decreases by 1 (truncated).
Counts.
- primaryCount is the number of sales with primary where was in the offer.
- addonCount is the number of sales with add-on .
Statement. On every outcome of this execution, including probability-zero branches, every item satisfies, in real arithmetic:
Degenerate cases.
- The equation is required on every branch, not only almost surely.
- is a real difference and could be negative.
- is allowed.
- and enter only through which are generated.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.