Lemma 4 — Dual objective value
ProvedChenCheckout.Protection.lemma_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. The dual objective is at most
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
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 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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. The instance, the hypotheses, and the generated construction (lists , counts ) are exactly as follows:
- items with ;
- ;
- ;
- families (containing , downward closed, excluding );
- choice probabilities (nonnegative, zero off , total at most , substitutable);
- an exact oracle for nonnegative weights;
- ;
- ;
- of length ;
- for all , where is the number of occurrences of in ;
- 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 independent fixed-list simulations;
- it appends the eligible item minimising , paired with that ratio, until every eligible item satisfies , or until iterations have run.
Derived quantities.
- is the expected add-on sales of under the fixed-list execution of with .
- if , and otherwise.
- .
- , and .
- .
- .
Statement.
Here the last factor is literally marginal, which for equals .
Degenerate cases.
- Items with contribute nothing to the first and third sums on the right.
- "Generated" includes probability-zero outputs.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.