Proposition 2 — Preservation of shifted thresholds
ProvedChenCheckout.Protection.proposition_2Let 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
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_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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. The instance is as follows:
- ;
- ;
- ;
- families (containing , downward closed, excluding );
- (nonnegative, zero off , total at most , substitutable);
- an exact oracle for .
The hypotheses are:
- ;
- ;
- ;
- appears in the trace of some outcome, possibly of probability zero, of the list-construction computation on .
That computation, for each customer:
- estimates from simulated fixed-list runs;
- appends eligible minimal-ratio items with their ratio, updating counts;
- stops when the threshold test passes, or after rounds.
Iteration quantities. With :
- eligible ;
- passes means for all eligible ;
- is the minimum of over eligible with (the smallest index attaining it), or if there are none;
- for eligible .
Statement. If for all , then for every eligible .
Degenerate cases.
- If no item is eligible, the conclusion is vacuous.
- Nothing is assumed about the accuracy or sign of .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.