PaperlayerView exact revision on arXiv

Source-linked AI summary

Order-selection Prophet Inequality (Almost) Goes I.I.D

Bo Peng, Zhihao Gavin Tang

arXiv:2610.34892v1cs.DScs.GT

TL;DR

For order-selection prophet inequalities, the optimal i.i.d. ratio Γ⋆≈0.74544 is an upper bound, while prior order-selection algorithms achieved about 0.7258. The paper characterizes local arrival-time rules as allocation kernels and gives a kernel with ratio 0.74500001, less than 4.5 × 10^-4 below the upper bound.

  • Problem

    Prior order-selection algorithms achieved about 0.7258, below the i.i.d. upper bound Γ⋆≈0.74544.

    Source: §1 · p. 2

  • Method

    The paper characterizes local arrival-time constructions as allocation kernels and perturbs a baseline kernel to build K1, with analytic estimates and a finite interval-arithmetic certificate.

    Source: §1.1 · pp. 3–4

  • Results

    0.74500001 is the competitive ratio of the proposed algorithm, less than 4.5 × 10^-4 below the upper bound Γ⋆.

    Source: §1 · p. 2, §7 · p. 31

  • Takeaways & Limitations

    The K1 improvement over K0 gives up exact matching of the rarely winning items’ optimal i.i.d. threshold path.

    Source: §7 · p. 31

    Small-profile tests do not capture the opposing load effects that apply to positive-size profiles, and K0 fails at Γ⋆.

    Source: §5.3 · pp. 22–23

Abstract

from arXiv · show

We study the order-selection prophet inequality. A gambler knows the distributions of independent nonnegative random values, chooses the order in which to inspect them, and may irrevocably accept at most one value, at the time it is revealed. Since the order is irrelevant when the values are i.i.d., no algorithm can guarantee more than the optimal i.i.d.\ ratio $\Gamma_\star\approx0.74544$ of the expected maximum. We give an algorithm with competitive ratio $0.74500001$, less than $4.5\times10^{-4}$ below this bound. The algorithm samples independent arrival times and uses item-dependent thresholds. It is designed so that, conditional on its value, every item is selected with probability equal to a fixed fraction of its probability of being the maximum. We show that the constructions of this form that apply one local rule to every item are exactly those given by an allocation kernel, that is, by a coupling of two uniform random variables. Requiring every rarely winning item to follow the optimal i.i.d.\ threshold path singles out a baseline kernel, for which we prove analytically a ratio $\Gamma_0\approx0.7389$, defined through a one-dimensional control problem. Our final kernel perturbs this baseline, and its guarantee combines analytic estimates with a rigorous computer-assisted certificate.

1 Introduction

The paper studies how to choose an inspection order and stopping thresholds for independent values, achieving a competitive ratio of 0.74500001—less than 4.5 × 10^-4 below the i.i.d. upper bound. It characterizes local arrival-time rules using allocation kernels, analyzes a baseline kernel, and certifies a stronger perturbed kernel.

1 Introduction

  • The model lets a gambler choose the inspection order for independent, known distributions, while requiring each value to be accepted or rejected on revelation and allowing at most one acceptance.When values are i.i.d., order is irrelevant, making the optimal i.i.d. ratio Γ⋆ an upper bound for order selection.Source: §1 · pp. 1–2

1.2 Related Work

1.1 Our Approach and Results

  • 0.74500001 is the guaranteed competitive ratio, less than 4.5 × 10^-4 below the i.i.d. upper bound Γ⋆.The final kernel K1 is universally feasible at this ratio for arbitrary independent nonnegative values.Source: §1 · p. 2, §1.1 · p. 4
  • Local arrival-time rules correspond exactly to allocation kernels, which encode a coupling of two uniform random variables and automatically satisfy the total-allocation constraint.For each item, its allocation is the integral of its winning-probability profile against the kernel; feasibility then reduces to checking individual profile loads.Source: §1.1 · p. 3
  • The baseline kernel K0 is uniquely selected by requiring small-profile threshold paths to match the i.i.d. path, and it is universally feasible at Γ0 ≈ 0.7389.K0 nevertheless fails at Γ⋆ on a profile with substantial winning probability, so matching the i.i.d. path for small profiles is insufficient.Source: §1.1 · pp. 3–4

1.3 Organization

  • The paper moves from the model and kernel characterization through kernel design, baseline analysis, and the final guarantee, with deferred proofs and extensions in appendices.Appendices F and G prove the final theorem, and Appendix H extends the guarantee to distributions with atoms.Source: §1.3 · pp. 5–6

2 Model and Algorithmic Framework

The framework models order selection over independent, nonnegative values and uses independently sampled arrival times with item-dependent thresholds. It parameterizes threshold design through area allocations, reducing feasibility to keeping each item’s arrival load at most one.

2 Model and Algorithmic Framework

  • The gambler chooses an inspection order before observing independent, nonnegative values with known distributions and may accept at most one item.The exposition initially assumes atomless distributions; Appendix H extends the final guarantee to distributions with atoms.Source: §2 · p. 6

2.1 Independent Arrival Times with Item-Dependent Thresholds

  • Independent arrival times and item-dependent thresholds are chosen so each item’s acceptance probability, conditional on its value, is Γ times its probability of being the maximum.Integrating this exact item-wise guarantee gives E[ALG] = ΓE[OPT] when E[OPT] is finite.Source: §2.1 · p. 6

2.2 A Probability-Scale Parameterization

  • The probability-scale parameterization accepts item i when its loss score Ui is at most yi(Ti), with area-allocation functions specifying the threshold paths.Ui is the conditional probability that item i is not the maximum, given its value.Source: §2.2 · p. 7
  • When allocation functions satisfy the load constraints, the algorithm has no acceptance by time t with probability 1 − Γt and retains the exact item-wise guarantee.The probability of accepting by time t is Γt, so t measures the fraction of eventual acceptance probability accumulated, not the fraction of items inspected.Source: §2.2 · p. 8

2.3 Design of Area-Allocation Functions

  • The design problem is to maximize Γ while choosing allocations whose total is normalized and whose arrival load is at most one for every item.The paper restricts attention to local constructions; prior frameworks cited here report ratios of approximately 0.7251 and 0.7258, respectively.Source: §2.3 · p. 8

3 Local Constructions of Area Allocations

This section frames local area-allocation rules around the shared normalized-time constraint, then represents items by winning-probability profiles. It characterizes these local rules exactly through allocation kernels.

3 Local Constructions of Area Allocations

  • A local rule assigns each item a nondecreasing allocation from its own area curve, while allocations across items must sum to normalized time t.Source: §3 · p. 9

3.1 Winning-Probability Profiles

  • At maximum rank u, item i’s winning-probability profile is its conditional probability of attaining the maximum; profiles sum to one almost everywhere.Source: §3.1 · pp. 9–10

3.2 Characterization of Local Constructions

  • For fixed maximum rank u, K(t, u) gives the fraction of winning-probability mass allocated by normalized time t, using the same kernel for every item and input.Source: §3.2 · p. 11
  • A functional is a local construction exactly when an allocation kernel represents its allocations, and the kernel is unique up to null sets of maximum ranks.Source: §3.2 · p. 11

4 Kernel Design

Section 4 casts local arrival-law design as choosing an allocation kernel and minimizing its worst profile load at a target ratio. It uses the i.i.d. benchmark and two elementary kernels to show why nonconstant profiles matter.

4 Kernel Design

  • For a fixed target ratio, kernel design minimizes the largest arrival load over all profiles, seeking a single kernel whose loads are all at most one.The kernel may depend on the target ratio, but must work for every profile and input.Source: §4 · p. 12, §4.1 · p. 13

4.1 The Kernel Optimization Problem

  • For fixed (Γ,K), universal feasibility is equivalent to every profile’s load being at most one; this concerns prescribed arrival laws, not all Γ-competitive algorithms.When feasible, the construction gives the exact item-wise guarantee on atomless inputs, and that guarantee extends to arbitrary independent nonnegative distributions, including atoms.Source: §4.1 · p. 13

4.2 The I.I.D. Benchmark

  • Γ⋆≈0.7454403321 is attained by every allocation kernel on i.i.d. inputs, and the prescribed construction is feasible there exactly when Γ≤Γ⋆.On i.i.d. inputs, the kernels induce the same allocation.Source: §4.2 · pp. 14–15

4.3 The Perfectly Correlated Kernel

  • 1−1/e is the largest universally feasible ratio for the perfectly correlated kernel, which allocates winning probability mass at rank u at time t=u.Its worst-case loads arise from nonconstant profiles.Source: §4.3 · p. 15, §4.4 · p. 17

4.4 The Independent Kernel

  • 1−1/e is also the largest universally feasible ratio for the independent kernel, which allocates each item’s winning probability mass at a constant rate across maximum ranks.The worst-case loads for the two elementary kernels arise from nonconstant profiles.Source: §4.4 · pp. 16–17

5 From the I.I.D. Benchmark to the Kernel K0

This section uses small-profile threshold paths to select the baseline kernel K0 that matches the i.i.d. path for every shape. It then analyzes K0’s load through a relaxed hazard-control problem and identifies a positive-profile obstruction to feasibility near the i.i.d. benchmark.

5.1 Small Profiles and the Linearized Area Curve

  • As profiles scale toward zero, their area curves linearize; for the constant shape, the limiting path is q and the load is J(Γ⋆) = 1.For any kernel, the constant shape gives the i.i.d. path and load, so the worst-case zero-scale load is at least J(Γ).Source: §5 · p. 17, §5.1 · pp. 19–20

5.2 A First-Order Condition and the Design Principle

  • K0 is the unique allocation kernel whose limiting threshold path equals q for every small-profile shape.It allocates each profile’s linearized area at the i.i.d. threshold q(t).Source: §5.2 · p. 21

5.3 The Kernel K0

  • K0 is an allocation kernel with allocation aλ(q(t)); probabilistically, it spreads winning probability at rank u uniformly over levels [u, 1].Each part is released when the i.i.d. threshold reaches its level.Source: §5.3 · p. 22
  • For positive-size profiles, self-competition can raise K0’s load while self-survival lowers it; the net effect is bounded uniformly over profiles.The paper also exhibits a profile where self-competition dominates at Γ⋆.Source: §5.3 · pp. 22–23

5.4.1 Exponential coordinates

  • On the i.i.d. threshold path, exponential time and rank align, and the rescaled threshold complement R equals one.Table 3 summarizes these coordinates for the analysis of K0’s guarantee.Source: Table 3 · p. 24, §5.4.1 · p. 24

5.4 A Universal Guarantee for K0

  • For every profile, K0 is universally feasible at ratios Γ ≤ Γ0 ≈0.7389 and satisfies the exact item-wise guarantee.The guarantee is derived by bounding the load through a scalar differential equation and a deterministic control problem.Source: §5 · p. 17, §5.4 · pp. 23–24

5.4.1 Exponential coordinates

  • In exponential coordinates, t_r = 1 − (1 + r)e^-r and h(r) is the cumulative hazard of the item's rank, with 0 ≤ h(r) ≤ r.The i.i.d. threshold path satisfies 1 − q(t_r) = e^-r.Source: §5.4.1 · p. 24, §5.4.2 · p. 25

5.4.2 The threshold lag

  • The rescaled threshold complement R(r) is at most 1 + h(r), while the load integrand also reflects self-survival and the item's allocation rate.For rarely winning items, h is close to zero, so the threshold lag factor is close to one.Source: §5.4.2 · pp. 25–26

5.4.3 The control problem

  • Relaxing the profile hazard to any measurable control k(r) in [0, r] yields the control value VΓ(0) and bounds every K0 load by Γ + VΓ(0).The relaxation ignores that a true cumulative hazard must be nondecreasing and 1-Lipschitz.Source: §5.4.3 · pp. 26–27

5.4.4 The constant Γ0

  • The unique Γ0 satisfying Ψ(Γ0) = 1 guarantees universal feasibility of K0 for every Γ ≤ Γ0.The bound follows from ℓΓ(K0, λ) ≤ Γ + VΓ(0) for every profile λ.Source: §5.4.4 · p. 27, §5.4.3 · p. 27
  • A profile shows K0 is not universally feasible for any Γ ≥ 149/200, including Γ⋆, so reaching Γ⋆ requires changing how the kernel treats positive-size profiles.The paper's numerical observations suggest the feasibility threshold lies below 0.74 and within about 10^-3 of Γ0.Source: §5.4.4 · pp. 27–29
  • Numerical two-phase profiles suggest K0's feasibility threshold lies in [Γ0, 0.74), within about 10^-3 of Γ0, with remaining theorem slack arising from the threshold-lag step.At Γ = 0.74, one tested profile has load approximately 1.00018.Source: §5.4.4 · pp. 28–29

6 A Kernel with Competitive Ratio Above 0.745

The perturbed kernel K1 is universally feasible at Γ1 and yields an order-selection algorithm for arbitrary independent nonnegative values. Its construction perturbs K0 while preserving both coupling marginals, and its guarantee is established with a finite computer-assisted certificate.

6.1 Motivation

  • A uniform mixture of K0 and the independent kernel numerically appeared feasible at ratio 0.74, motivating the finer grid-based search.The mixture was 0.972K0 + 0.028Kind.Source: §6.1 · p. 29
  • A grid search led to K1, which transfers mass between selected rank-time cells while preserving both marginals and differs from K0 on nonconstant profiles.Unlike K0, K1 does not make every small-profile threshold path coincide with q.Source: §6.1 · p. 29

6.2 The Kernel K1

  • K1 perturbs K0’s coupling on a coarse grid using 69 integers, with each transfer preserving every row and column sum.The perturbation is supported on a bounded region and K1 equals K0 outside the stated rank or time ranges.Source: §6.2 · p. 30

6.3 The Guarantee

  • Γ1 = 0.74500001 is a universal guarantee for K1, yielding an order-selection algorithm for arbitrary independent nonnegative values.The construction also satisfies the exact item-wise guarantee on every atomless input.Source: §6.3 · p. 30
  • The K1 proof refines K0’s load analysis by using regional estimates, a backward comparison over admissible paths, and finitely certified bounds for block-mass vectors.Figure 4 pairs corresponding proof steps for Theorems 5.5 and 6.1.Source: §6.3 · p. 31, Figure 4 · p. 31

7 Concluding Remarks

The conclusion characterizes local arrival-time constructions as allocation kernels and reports K1’s guarantee, while leaving optimal feasibility open. The accompanying disclosure says K1’s rigorous guarantee is not yet conceptually understood, and the appendix derives and verifies arrival laws from an item-wise guarantee.

7 Concluding Remarks

  • Local arrival-time constructions reduce to choosing one coupling of two uniform random variables; K1 exceeds 0.745, but whether any kernel is feasible at Γ⋆ remains open.The guarantee for K1 rests on a computer-assisted certificate.Source: §7 · p. 31

AI Disclosure

  • The authors report that AI systems developed K1, its analysis, and its certificate, and describe the rigorous result as evidence rather than a definitive explanation of attainability.They say they lack a conceptual understanding of K1 beyond its motivation.Source: AI Disclosure · p. 32

A.1 Threshold Paths

  • For a continuous nondecreasing allocation B matching the area curve’s endpoints, the threshold path y = A← ◦ B is continuous and nondecreasing.The lemma also gives y(0) as the greatest x with A(x)=0 and y(1)=1.Source: §A.1 · p. 36

A.2 Deriving the Arrival Laws from the Item-Wise Guarantee

  • The arrival-law derivation makes the effective inspection measure equal Γ times the increase in the item’s threshold path, enforcing the item-wise guarantee.The derivation is presented as heuristic before the next subsection verifies the construction.Source: §A.2 · p. 37

A The Arrival Construction

  • The resulting arrival construction uses independent arrivals and survival functions chosen so that the probability no item has qualified by time τ is 1 − Γτ.Here normalized time measures accepted probability divided by Γ.Source: §A.2 · p. 37

A.3 Proof of Theorem 2.1

The appendix verifies the arrival construction and develops the profile-to-area representation used in the paper. It relates each item’s loss score and area curve to its winning-probability profile, recovers profiles from area curves, and shows that admissible profile families can be realized by independent inputs.

A.3 Proof of Theorem 2.1

  • Under the stated allocation and load conditions, the arrival construction yields the exact item-wise guarantee for atomless inputs.The arrival distributions are completed with a no-arrival outcome when an item’s arrival mass is below one.Source: §A.3 · pp. 37–38

B Profiles and Area Curves

  • An item’s area curve is determined by its winning-probability profile and is continuous, convex, nondecreasing, and 1-Lipschitz.Its right derivative is the distribution function of the associated random variable Xλ.Source: §B.1 · p. 39, B Profiles and Area Curves · p. 39

B.1 The Rank Representation

  • The rank representation expresses the item’s loss score as xλ(Ri), so its area curve depends on the input only through its profile λi.On the exponential scale, the profile gives the hazard rate of the item’s rank.Source: §B.1 · pp. 39–40

B.2 From a Profile to Its Area Curve

  • The area formulas give Aλ(1)=µλ and express the curve through the profile’s rank-dependent loss-score function.The appendix also gives a probabilistic reading of the area curve using a random rank R.Source: B Profiles and Area Curves · p. 39, §B.2 · p. 40

B.3 Recovering the Profile from the Area Curve

  • An area curve Aλ determines its profile λ up to a null set.The recovery proceeds through the loss-score function xλ(u).Source: §B.3 · p. 41

B.4 Realizing Families of Profiles

  • Every finite measurable family of profiles summing to one almost everywhere is realized by independent atomless nonnegative values.In particular, any one profile λ is realized in a two-item input with profiles (λ, 1 − λ).Source: §B.4 · p. 41

B.5 Proof of Lemma 3.2

The appendix establishes a bijection between winning-probability profiles and area curves. The curve depends only on the profile’s equivalence class, and the profile can be recovered from it up to null sets.

B.5 Proof of Lemma 3.2

  • The map from profiles to area curves is onto and one-to-one, with the profile recovered up to its equivalence class.The area curve is defined from the profile, and the recovery lemma identifies the profile from that curve.Source: §B.5 · p. 42

C Proof of the Characterization of Local Constructions

The proof characterizes local constructions through a kernel representation, building a jointly measurable allocation kernel from the construction’s action on profiles and establishing uniqueness.

C Proof of the Characterization of Local Constructions

  • The proof proceeds from additivity and positivity to densities, then a consistent kernel, and finally uniqueness.For each fixed time, the construction acts by integration against a density.Source: C Proof of the Characterization of… · p. 42
  • The total-allocation identity makes the fixed-time map additive, monotone, positively homogeneous, and Lipschitz in L1.The proof obtains additivity by comparing profile families (f, g, 1 − f − g) and (f + g, 0, 1 − f − g).Source: C Proof of the Characterization of… · pp. 42–43
  • Each fixed-time map is integration against a density kt, obtained by applying Radon–Nikodym to the measure induced on Borel sets.The density satisfies 0 ≤ kt ≤ 1 almost everywhere.Source: C Proof of the Characterization of… · p. 43
  • Choosing the densities consistently yields a jointly measurable kernel that is nondecreasing and right-continuous in time.Taking f ≡ 1 gives the normalization integral of K(t, u) over u equal to t.Source: C Proof of the Characterization of… · p. 43
  • Any two kernels representing the same construction agree almost everywhere at every time.The proof first establishes agreement at rational times, then uses right-continuity.Source: C Proof of the Characterization of… · p. 43

D.1 Constant Profiles and the I.I.D. Benchmark

For constant profiles, the load is bounded by J(Γ), whose limiting form connects the analysis to the optimal i.i.d. ratio; for any fixed kernel and profile, load is nondecreasing in Γ.

D.1 Constant Profiles and the I.I.D. Benchmark

  • As c ↓ 0, the constant-profile load converges to J(Γ), which yields the classical characterization of the optimal i.i.d. ratio.The characterization is attributed to Kertz (1986) and Correa et al. (2021a).Source: §D.1 · pp. 44–45
  • ℓΓ(K, c) ≤ J(Γ) for constant profiles.The bound follows by substituting the profile estimate into the integral formula for the load.Source: §D.1 · p. 44

D.2 Monotonicity in the Target Ratio

  • For fixed K and λ, ℓΓ(K, λ) is nondecreasing in the target ratio Γ.The allocation and threshold path do not depend on Γ.Source: §D.2 · p. 45

E Deferred Proofs from Section 5.4

The deferred proofs establish the control problem’s value through finite-horizon optimization and an infinite-horizon limit, and justify the numerical procedure with a truncation bound.

E Deferred Proofs from Section 5.4

F Proof of the Guarantee for K1

The proof verifies the final kernel’s feasibility at Γ1 and obtains the algorithmic guarantee; its computer-assisted bounds cover every admissible profile, not just profiles constant on grid blocks.

F Proof of the Guarantee for K1

  • Verifying K1 as an allocation kernel and checking its load condition establishes the guarantee for the fixed pair (K1, Γ1).Proposition 4.1 then gives the algorithmic guarantee.Source: F Proof of the Guarantee for K1 · p. 47
  • The perturbation changes a profile’s allocation only through four block masses, while the profile determines a nondecreasing, 1-Lipschitz path.Regional bounds control the threshold complement and then the load along every admissible path.Source: F Proof of the Guarantee for K1 · p. 47
  • A finite cover turns regional bounds into the required inequality without restricting profiles to a finite family or requiring block-constant profiles.Figure 5 depicts the mass-vector cover and the steps for bounding one region.Source: F Proof of the Guarantee for K1 · p. 47, Figure 5 · p. 47

F.1 Validity of the Kernel

This appendix establishes that the perturbed density defines a valid allocation kernel and develops a finite certificate to bound its load uniformly across mass profiles. The validity argument covers all profiles, including arbitrarily small positive scales, using analytic cases or certified pieces of the master cover, with closed enclosures handling ties and shared boundaries.

F.1 Validity of the Kernel

  • The density p1 is nonnegative with the required marginals, so K1 is an allocation kernel; its correction vanishes beyond r = 10 and has zero integral over each input row.Finite rational inequalities certify the nonnegativity conditions.Source: §F.1 · pp. 48–49

F.2 Load Representation

  • The load identity isolates allocation and survival-rate dependence in k and σ, leaving the threshold term R, which depends on the inverse of the profile’s area curve.For the baseline kernel, k = h; the perturbation changes this rate.Source: §F.2 · p. 50

F.3 Block Parameters and Admissible States

  • Four block masses determine allocation and rate corrections, while the threshold term still depends on the profile within each block and is bounded uniformly over measurable profiles.The block-mass bounds and current state provide the basis for uniform bounds across profiles.Source: §F.3 · pp. 50–51

F.4 Bounding the Threshold Complement

  • The proof bounds the inverse of the profile’s area curve and uses a nonnegative correction term to tighten the regional upper bound on the load integral.The correction is subtracted from the upper bound; when no positive correction is certified, it is set to zero.Source: §F.4 · pp. 52–53

F.5.1 Continuation integrals and backward comparison

  • The load splits at the last input-block endpoint b4 = 32/5, and a backward comparison propagates a uniform continuation bound across finite intervals.The comparison starts from a terminal bound and updates it backward over the intervals.Source: §F.5.1 · pp. 53–54

F.5.2 The integral beyond the last block

  • Beyond r = 10, the perturbation vanishes and R(r) ≤ 1 + h(r); a finite backward comparison then carries the tail bound from 10 to b4.The tail estimate is analytic on [10, ∞), while the interval [b4, 10] is handled by finite partitioning.Source: §F.5.2 · p. 54

F.5.3 The prefix and a state-dependent comparison

  • On [0, b4], a state-dependent Bellman comparison uses a potential and the integrated correction to bound the prefix load for every profile in the region.The Bellman residual is verified over parameter–state cells.Source: §F.5.3 · p. 55

F.6 Finite Verification and Completion of the Proof

  • Finite verification selects sufficient bounds for parameter regions and checks that accepted regions cover every possible block-mass vector, including small-scale and boundary cases.Coverage uses an exact dyadic-grid check; the small-scale cube is verified directly.Source: §F.6 · p. 56, §F.6.1 · p. 56

F.6.1 Covering all profiles

  • Chart boxes are affinely rescaled to a unit four-dimensional box, and Equation (106) maps them to rigorous bounds on the original masses Mg.The full image is enclosed outwardly.Source: §F.6.1 · p. 57
  • For xmax > 2^-10, boxes in Q handle the original coordinates x, and the two covers may share the boundary xmax = 2^-10.Both covers use closed enclosures; ties between pivots and common scale endpoints cause no ambiguity because one valid chart suffices.Source: §F.6.1 · p. 57
  • Every mass vector, including positive scales arbitrarily close to zero, is either treated analytically or belongs to a certified piece of the master cover.Closed chart images include ties and shared boundaries.Source: §F.6.1 · p. 57

F.6.2 The numerical certificate

The section develops a finite, computer-assisted certificate for the kernel’s guarantees, establishing regional comparisons for continuation and Bellman bounds. It uses interval arithmetic to verify inequalities across parameter regions and state cells, including the generated potential and its derivatives despite floating-point rounding.

F.6.2 The numerical certificate

  • The certificate covers [0, 1]^4 \ {0} and establishes universal feasibility, exact item-wise guarantees for atomless inputs, and a competitive guarantee for arbitrary independent nonnegative distributions.The proof bounds the arrival load below Ucert in both cases for the mass vector.Source: §F.6.2 · p. 57

G Estimates and Finite Updates for the Certificate

  • Uniform estimates target ℓλ, an upper bound on arrival load, using bounds on threshold complement R and correction term G, finite comparison updates, and arithmetic for whole-cell certification.The estimates hold uniformly over their stated parameter and state ranges.Source: G Estimates and Finite Updates for the… · p. 57

G.1.1 A comparison with the baseline

  • A baseline comparison bounds R(r) by υ(1 + h(r)) and gives ρ*(r) ≥ (r − log υ)+ under its stated shift condition.The comparison uses the perturbed cumulative density relative to the baseline.Source: §G.1.1 · p. 58

G.1.2 Finite-scale capacity bound

  • Finite-scale capacity bounds use chart-scale masses and cumulative-mass enclosures to control R, while future-endpoint bounds apply given a nonnegative gap lower bound and positive past-mass bound.The capacity argument also handles a positive actual scale when a chart’s lower scale endpoint is zero.Source: §G.1.2 · p. 59, §G.1.3 · p. 60

G.1.4 The negative-gap branch

  • For negative-gap states, derivative monotonicity and certified shift factors yield quotient or constant upper bounds, with a candidate omitted when its denominator cannot be certified positive.The shift estimate also applies without division when hρ = 0.Source: §G.1.4 · p. 60, §G.1.5 · p. 61

G.1.6 Convexity on an output cell

  • Convexity on each output cell lets endpoint checks certify bounds throughout the cell, including shift bounds and the least sufficient shift from the prefix budget.The prefix-budget condition is checked throughout the cell; if it fails, the global shift bound remains available.Source: §G.1.6 · pp. 61–62

G.2.1 Changing the order of integration

  • The correction term is bounded by changing integration order and using a past window when its conditions hold; cellwise instantiation uses the exact binary64 value represented by 0.2545 as a verified starting value.When the window conditions are not certified, the correction term is set to zero.Source: §G.2.1 · p. 62, §G.2.2 · pp. 62–63, §G.2.3 · p. 63

G.3.1 One-dimensional integration

  • One-dimensional integration uses convex chords, while the state-band chord bound combines endpoint bounds over each retained state band to bound the integral uniformly over admissible profiles.Different bounds may be integrated separately, with their upper endpoints minimized.Source: §G.3.1 · p. 64, §G.3.2 · p. 64, Then any vj satisfying · p. 65

G.3.3 A finite-scale forward comparison

  • A partition-based forward comparison bounds the survival factor and the local ratio using lower bounds for k on each interval.The construction propagates a finite-scale bound across intervals using the recurrence for σ_j.Source: §G.3.3 · p. 66

G.3.4 Finite Bellman update

  • The finite Bellman update makes affine interpolation satisfy the Bellman inequality throughout each interval when the update uses a uniform residual bound.The argument handles both endpoint orderings of W_j and W_j+1; repeated updates yield the stated load bound for every admissible terminal state.Source: §G.3.4 · pp. 66–67

G.3.5 Finite-tail construction of V

  • The finite-tail construction propagates a continuation bound backward from r = 10 to b4 using interval-specific bounds and the finite Bellman update.It starts from V_λ(10) ≤ 265e−20 and processes finitely many intervals in the exponential coordinate.Source: §G.3.5 · p. 67

G.4.1 State-band comparison

  • The state-band comparison selects the applicable certified inverse bound with the smallest chord integral, then propagates the continuation bound backward across coordinate and state cells.Refined candidates are used only when their branch and denominator conditions are certified throughout the cell.Source: §G.4.1 · p. 68

G.4.2 Bellman comparison

  • Regional Bellman comparisons bound the residual over whole cells, taking the minimum of valid candidates and refining bounds when cell conditions permit.Refinements retain common dependence on block masses or variation in r; adaptive subdivision includes a stored tolerance of 2 · 10−7 in the residual bound.Source: §G.4 · p. 67, §G.4.2 · pp. 69–70

G.4.3 Joint residual bounds

  • Joint residual bounds strengthen separate bounds on d, ν, and −ν by preserving their shared mass constraints and solving the resulting linear minimization as a fractional knapsack problem.Enlarging feasible mass ranges preserves a lower bound.Source: §G.4.3 · p. 70

G.4.4 Common-mass quadratic expansion; G.4.5 Variation of the center term in the exponential coordinate

  • The common-mass quadratic expansion yields a whole-cell residual bound, while a derivative enclosure propagates the center term across the coordinate interval.The expansion is used only when the nonnegative-gap condition holds throughout the cell; the derivative enclosure follows from the mean value theorem.Source: §G.4.4 · p. 70, §G.4.5 · p. 71

G.5 Construction of the State Potential; G.5.1 Choosing the state derivative; G.5.2 From the derivative to the potential

  • The state potential is chosen from a midpoint-based candidate derivative and then built by trapezoidal integration, monotonicity enforcement, and bilinear interpolation.The interpolated vertices define the actual potential checked in the residual, without assuming the candidate derivative is accurate.Source: §G.5 · p. 71, §G.5.1 · p. 72, §G.5.2 · p. 73

G.5.2 From the derivative to the potential

  • The generator’s binary64 vertex values are verified as exact dyadic rationals, and outward interval bounds certify the Bellman inequality for the actual generated potential on every admissible cell.Verification regenerates vertices from the package’s regional inputs and resolutions, checking the actual interpolant and its derivatives rather than relying on separate potential tables.Source: §G.5.2 · p. 73

G.6 Certified Arithmetic

  • Interval bounds, including quadrature errors and the finite-tail estimate, certify the regional inequalities over real parameters in every cell; grids use step 1/Nr with Nr divisible by five.These grids include every output-cell and source-block boundary.Source: §G.6 · p. 74

G.6.1 Outward interval evaluation

The certificate uses outward interval evaluation to enclose exact results and reject failed checks. Separate bounds for elementary functions support the verified calculations.

G.6.1 Outward interval evaluation

  • Outward rounding encloses each exact arithmetic result, including subnormals, while finite ordered endpoints and certified positive divisors are required.Products use all four endpoint products; any failed check rejects the computation.Source: §G.6.1 · p. 74
  • Kernel intervals are checked against the exact integer specification, and target-ratio intervals must enclose the exact rational Γ1.The wrapper checks the rounding environment and verifies that numerical engines load the certified coefficient endpoints unchanged.Source: §G.6.1 · p. 74

G.6.2 Elementary functions

  • Exponential bounds use a truncated series with a controlled remainder and monotonicity; negative arguments use e^-x = 1/e^x.The certified bounds do not rely on a library approximation to e^x.Source: §G.6.2 · p. 74
  • A lower bound on log(1 + x) is built from downward-rounded log y and log 2 bounds after decomposing the rounded input.The log-series bounds are applied to z and 1/3, and positive remaining terms are dropped.Source: §G.6.2 · p. 74
  • For an upper bound on √x, a library value only seeds a search that increases until its square's lower interval endpoint reaches x.Zero is handled exactly, and failed checks reject the computation; candidate potentials are checked independently as exact vertices.Source: §G.6.2 · pp. 74–75

H Extension to Distributions with Atoms

The guarantee extends to arbitrary independent nonnegative distributions, including those with atoms, by randomized tie-breaking. The construction applies the arrival algorithm to atomless scores while preserving the original maximum value.

H Extension to Distributions with Atoms

  • Randomized tie-breaking extends the kernel guarantee to arbitrary independent nonnegative distributions, including those with atoms.The proof integrates over v to establish E[ALG] = ΓE[OPT] when the latter expectation is finite.Source: H Extension to Distributions with Atoms · p. 75
  • Independent uniform tie-breakers transform values into independent atomless scores, enabling the arrival construction to use the kernel on atomless distributions.The score laws are absolutely continuous, with density at most n.Source: H Extension to Distributions with Atoms · p. 75
  • The score transformation is nondecreasing in value and orders ties by the independent tie-breaker, while the largest-score item retains the original maximum value.Thus the inspection order agrees almost surely with the tie-broken ordering of original values.Source: H Extension to Distributions with Atoms · p. 75
Loading 2610.34892v1…