Theorem 1 — Both instance-dependent and instance-independent signed bounds for OLD and OLT
DisprovedZhangJasinPricing.Cyclic.theorem_1There exist positive constants Ψ₁ and Ψ₂, independent of the horizon and every model parameter, such that for every customer model satisfying Assumption 1, and every prescribed initialization and measurable maximizing tie choice for OLD and OLT, the minimum positive gaps Δᴰᵉᶜ and Δᵀᴿ over the full respective cyclic policy classes exist. For every integer T≥2,
Here R is expected achieved revenue divided by T minus the corresponding full-class benchmark, as printed. Revenue includes initialization, clearing, and the actual final prefix. The independent bounds are separate conjuncts for every instance; they are not conditional on an assumed gap witness.
Differences from the source:
- encoding: finite ordered prices, nonnegative cohort amounts, and a general probability law → zero-based natural-number indices with explicit bounds, real cohort amounts, and a measurable probability space; reason: the same instances are represented; real amounts also include the uniform demands used on p. 28
- reading: Definition 1 mixes a strict maximum set with a non-strict empty-set test → the maximum and fallback use the displayed strict set; reason: the printed cases leave repeated thresholds undefined; this releases a threshold once reached and retains the larger class (I4)
- reading: the p. 9 transition display omits the last waiting cohort → transition experiments follow equation (1), including all previous still-patient cohorts through period ℓ; reason: this is the operational definition on p. 8 and resolves the explicit indexing typo (I3)
- reading: Assumption 1 overloads r as a mean and a realization → the ψ₂ bound one applies to revenue realizations and centered errors have finite ψ₂ norm; reason: the text says norm of all r; the informal tail display is not a separate MGF normalization
- reading: initialization tests every parameter, with a suggested reset/high/drop procedure → any finite covering list of prescribed test blocks, with incidental high-price samples, reset observations retained as revenue, and a final reset; reason: this specifies the underdetermined testing and first-episode clearing conventions without favorable estimates or idle delays
- reading: the constants are independent of T and all other problem parameters {rᵢ} and {rᵢⱼℓ} → the same two constants precede the model, M, K, initialization, and tie rules; reason: this is the non-narrowing reading of all other problem parameters required by the brief
- reading: Δ is called the minimum positive gap and occurs in denominators → existence of actual least positive gaps is an explicit conclusion, with independent bounds as separate conjuncts; reason: the minimum may not exist, including on ordinary instances (I5); assuming it or replacing it by an infimum would discard source instances
- generalization: OLT initialization tests each parameter once (p. 20); OLD says at least once (p. 13) → OLT also permits repeated targeted tests in the finite covering list; reason: choosing each parameter once recovers the printed OLT testing prescription under the declared block/reset reading; no source instance in that prescription is excluded
- reading: the drop maximum in (2) includes j=i although drop parameters are defined only for j<i → the j=i case is its separately displayed r_i branch; reason: the p. 10 explanation separates equality from the strict-drop case; no undefined diagonal drop parameter is introduced
import Definitions.Def_ZhangJasinPricing_Cyclic_Model import Definitions.Def_ZhangJasinPricing_Cyclic_Policies import Definitions.Def_ZhangJasinPricing_Cyclic_DynamicPrograms import Definitions.Def_ZhangJasinPricing_Cyclic_Learning import Definitions.Def_ZhangJasinPricing_Cyclic_Analysis open MeasureTheory open scoped BigOperators ENNReal noncomputable section
namespace ZhangJasinPricing.Cyclic
theorem theorem_1 :
∃ Ψ₁ Ψ₂ : ℝ, 0 < Ψ₁ ∧ 0 < Ψ₂ ∧
∀ (Ω : Type) [MeasurableSpace Ω] (D : Model Ω) (_hA : Assumption1 D),
∀ (initD initT : Initialization D.M D.K) (tieD tieT : TieRule),
(∃ ΔD ΔT : ℝ, IsLeast (positiveGaps D .decreasing) ΔD ∧
IsLeast (positiveGaps D .threshold) ΔT ∧
∀ T : ℕ, 2 ≤ T →
signedRegret D .decreasing initD tieD T ≤ Ψ₁ / ΔD * Real.log T / T ∧
signedRegret D .threshold initT tieT T ≤ Ψ₁ / ΔT * Real.log T / T) ∧
(∀ T : ℕ, 2 ≤ T →
signedRegret D .decreasing initD tieD T ≤ Ψ₂ * Real.sqrt (Real.log T / T) ∧
signedRegret D .threshold initT tieT T ≤ Ψ₂ * Real.sqrt (Real.log T / T)) := by sorry
end ZhangJasinPricing.Cyclic
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
There are universal real constants and such that the following holds. They are chosen before everything else, so they do not depend on the sample space, the numbers of prices or patience levels , the prices, the cohort distributions, the initialization schedules, the tie-breaking rules or the horizon . The claim is: for every type with a σ-algebra, every model on satisfying "Assumption 1", every two initializations and every two tie rules , both (I) and (II) below hold.
(I) Gap-dependent bound. There exist reals such that:
- is the least element of the set of positive gaps for the decreasing class;
- is the least element of the set of positive gaps for the threshold class;
- for every integer ,
(II) Gap-free bound. For every integer ,
Here is the natural logarithm. is the "signed regret" of the decreasing-mode algorithm run with , and is that of the threshold-mode algorithm run with . Both are defined below.
The existence of is part of the conclusion, not a hypothesis. The statement therefore asserts, for every admissible model, that both positive-gap sets are nonempty and attain their infimum.
Every bound is an upper bound on
None is an upper bound on benchmark minus revenue. The statement gives no lower bound on the algorithm's revenue.
The model . consists of the following data:
- Integers and .
- A price function with for , strictly decreasing on indices :
The values for are unconstrained.
- A probability measure on .
- Random variables ("cohort of arrival time , valuation bin , patience ").
- Reals .
For all , all and all :
- pointwise;
- is measurable and integrable;
- , the same for every ;
- is integrable.
Nothing is said about independence across , or .
Demand. Take a cohort array and a price-index sequence . Write for truncated natural-number subtraction. The demand at period is
- The comparison is between indices.
- Bin never enters the sum.
- Only cohorts arriving at times count.
Parameters. The parameter set is
The "experiment" for a parameter and start time is defined case by case:
- For :
- For with :
Let .
Assumption 1 requires, for every and every :
- the sub-Gaussian norm of the uncentred variable is at most ;
- the sub-Gaussian norm of is finite.
The norm is the imported subgaussianNorm with respect to , an extended-valued quantity whose definition is not shown here. The centring uses the start- mean for every .
Words and the two policy classes. A word is a finite list of natural numbers. It is valid if and every . Its periodic extension is . Two classes are used:
- Decreasing class. Valid words with . The indices are nondecreasing, so prices are nonincreasing.
- Threshold class. Valid words in which every entry is at most the last entry (an index comparison), and which satisfy a threshold condition defined next.
For the threshold condition, use one-based prices
Define as follows:
- if , then ;
- otherwise is the largest with and , or if there is no such .
The condition is for all .
Revenue of a word and the benchmark. The mean-cycle revenue of is
where the cohort array is for every . This is an "empty start": no cohorts exist before time . The average revenue is .
The benchmark of a class is
taken as a real supremum (Lean's convention gives if the set is empty or unbounded above). Both classes contain every one-letter word with , so they are nonempty.
The positive-gap set of a class is
The algorithm. The state holds:
- the observation list of triples (price index, sales, revenue);
- for each parameter, a list of revenue samples;
- the current word and an offset;
- flags "boundary" (initially true) and "after clearing" (initially false);
- an episode list;
- a cycle counter (initially ).
Write for the number of samples of parameter . The sample mean is
which is when . The optimistic index is
whose square-root term is when .
Observing price index with optional label at time (the number of observations so far) proceeds as follows:
- Sales are , where is the past observed indices followed by from time on.
- Revenue is sales.
- The triple is appended to the observation list.
- If a label is given, is appended to 's samples.
Initialization schedule. An initialization is a list of tests. Each test lies in , every element of occurs at least once, and repeats are allowed. Each test contributes one block:
- first ;
- then, if : one period ;
- otherwise, for : periods followed by .
The schedule is these blocks in order, followed by a final .
The plan options. The dynamic program returns all maximum-value pairs (word of length , total value), keeping every tie:
- For it is .
- For it maximizes over two kinds of candidate:
- "drops": a word from for some , extended by , with value increased by ;
- "same":
- in decreasing mode, a word from extended by , with value increased by ;
- in threshold mode, the concatenation of a word from and one from , for , with values added.
The option list collects, for lengths and end indices , all of with value divided by . The bound is in decreasing mode and in threshold mode.
Tie rule. A tie rule is any function choosing, from a candidate count , a numerical history vector and candidate values , an index in that maximizes . For each fixed it must be measurable in .
The history vector is:
- is the number of observations;
- for , is coordinate of observation ;
- beyond the recorded observations.
The selected plan is the option at the chosen index.
Label of a word position. For the current word at zero-based position , let and . The label is:
- if or ;
- otherwise , where in decreasing mode and in threshold mode.
Playing a position proceeds as follows:
- Observe with its label.
- If the cycle is not finished, advance the offset.
- If the cycle is finished:
- reset the offset to ;
- increase by ;
- set "boundary" to true iff some label used by has , where is the count recorded at the start of the last episode, or if there is none.
Starting an episode records the start time, the current counts, the current sample means and , sets the word, and clears both flags.
Each period does exactly one of the following:
- During initialization: observe the next schedule entry, with its label.
- Else, if "after clearing" is set: start an episode with the current word and play a position.
- Else, if "boundary" is set: select a new word .
- If there was a previous word and , run one clearing period. It observes with label , adopts and sets "after clearing".
- Otherwise, start an episode with and play a position.
- Otherwise: play a position.
Exactly one observation is added per period. The run lasts exactly periods, counting initialization and clearing periods.
Signed regret. Let be the sum of the revenue coordinates of the observations. Then
where is the benchmark of the class matching the mode.
Degenerate and default-value cases.
- Since is a probability measure, is nonempty.
- , and exclude zero counts and zero horizons, and .
- may be shorter than the initialization schedule, and the bounds are still asserted for such .
- If fails to be integrable (including failing to be measurable), its expectation is taken as . In that case .
- If a class's average revenues were unbounded above, would be by convention.
- If a positive-gap set is empty, for example when every word in the class attains , or if it has no least element because gaps accumulate at , then part (I) is false for that model. The theorem therefore includes the assertion that neither happens for any model satisfying Assumption 1. This holds for both classes simultaneously.
- With no samples, and the bonus is . With , and every bonus is .
- With no prior episode, the recorded counts are , so the "boundary" test is automatically true.
- All subtractions truncate at : in , , , , and .
- A missing maximum in is .
- Out-of-range word positions read index , hence price .
- Prices at indices are unconstrained.
- Assumption 1 bounds the sub-Gaussian norm of the uncentred experiments by , and requires only finiteness for the centred ones.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.