Online Interval Selection with Binary Predictions: Optimal Consistency and a Continuous Robustness Tradeoff

Online Interval Selection with Binary Predictions: Optimal Consistency and a Continuous Robustness Tradeoff Zhong Han 1 tees is d = φ2 , below the limit 3 for every 1-increasing policy with finite robustness (Karavasilis, 2025, Definition 4.8 and Lemma 4.9). Such a policy never accepts an interval shorter than its longest conflicting holder. Shaped-BANK attains d with robustness φ5 , whereas every budget below 4φ + 3 forces consistency strictly above d.

arXiv:2610.37361v1 [cs.DS] 27 Oct 2026

Abstract We study online interval selection with binary predictions of membership in a final optimal solution. Requests arrive in arbitrary order; accepted requests may be revoked, but rejected or revoked requests cannot be recovered. With rewards proportional to interval length, the best consistency √ under finite strict robustness is d = (3 + 5)/2 when both guarantees hold almost surely on each fixed input, including for randomized algorithms. A continuous lower bound forces consistency strictly above d at every robustness budget below 4φ + 3 ≈ 9.472, whereas our deterministic algorithm attains d with√exact robustness φ5 ≈ 11.090, where φ = (1 + 5)/2. Each held interval inherits a ledger recording positive prediction mass lost through irrevocable decisions. A tunable replacement cost gives a continuous family with exact consistency throughout and exact robustness on two parameter intervals, including (C, R) = (25/9, 10) and (4, 7). Randomization permits expected consistency approaching one with finite expected robustness, whereas almost-sure robustness forces expected consistency strictly above two at every finite budget.

Why per-execution protection? Consider provisional reservations for one resource: offers specify future slots, decisions precede service, and declined offers expire. When accepted reservations can still be cancelled and hourly values are equal, duration is the selection objective. A guarantee for each completed batch protects against a poor random outcome as well as incorrect advice. Appendix E treats proportional cancellation costs. Our lower bounds cover randomized algorithms with both ratios almost surely on each fixed input; deterministic Shaped-BANK attains optimal consistency. Mixing a prediction follower with a robust algorithm improves expected ratios but can return zero reward with positive probability. Almost-sure robustness with expected consistency has different necessary bounds and an open optimum (Section 7). Remembering missed predictions. When a positive request is rejected, BANK distributes its length among the ledgers of conflicting holders. A replacement inherits those ledgers, so the same held interval can require different future decisions depending on what has already been missed. Bounding this inherited mass permits shorter replacements while protecting both guarantees. Varying the replacement cost and both special thresholds gives a continuous tradeoff; Section 6 identifies its exact segments.

1. Introduction An online selection algorithm can revoke accepted requests but cannot recover rejected alternatives. Even perfect predictions leave a dilemma: a short request may belong to the final optimum because compatible requests arrive later, yet accepting it can be disastrous if the input stops. How much can perfect predictions help while preserving finite robustness?

1.1. Related work Consistency–robustness tradeoffs quantify the benefit of accurate advice together with worst-case protection when it is wrong (Mitzenmacher & Vassilvitskii, 2020; Lykouris & Vassilvitskii, 2018; Purohit et al., 2018; Angelopoulos et al., 2020; Wei & Zhang, 2020). Here even exact optimum-membership advice cannot recover rejected or revoked alternatives. Optimal consistency with a matching lower bound, an attainable budget curve and bud-

In the binary optimum-membership model of Karavasilis (2025), optimal consistency under two almost-sure guaran1

Department of Biomedical Engineering, College of Design and Engineering, National University of Singapore. Correspondence to: Zhong Han <zhong.han.hz@u.nus.edu>. Preprint. October 27, 2026.

1

Optimal Consistency for Interval Selection

get lower bounds quantify this irreversible decision constraint. In our model, Karavasilis (2025, Observation 4.6) excludes consistency one by early stopping; Definition 4.8 and Lemma 4.9 give C ≥ 3 for every finitely robust 1increasing policy, including Revoke-Proportional (RP), and Theorem 4.10 certifies C(RPλ ) ≤ 3λ/(λ − 1). RevokeProp-Half permits shorter positive replacements without a matching guarantee. BANK makes such replacements finitely robust below three and matches a full-class consistency lower bound.

The essential supremum is over the coins. A zero denominator gives +∞; there is no additive term. For deterministic algorithms write R, C instead of Ras , Cas . Thus a finite budget B gives, on every fixed labelled prefix τ, Pr{OPT(τ ) ≤ BALGA (τ )} = 1. (2) The null set may depend on τ . Predictions may be infeasible. Write α = 1/φ, d = φ2 , and M = φ3 . Define

Replacement charging appears in any-order interval selection (Borodin & Karavasilis, 2023). Karavasilis identified dependence between direct and transferred charges as possible slack. Our joint geometric bound determines exact robustness for two BANK parameter intervals and unchanged RP; source measures control mass lost through rejections.

C ∗ (B) =

inf

Bmin (d) =

inf

R(A),

A deterministic:C(A)=d

∗ as (d) analowith inf ∅ = +∞. Define Cas (B) and Bmin gously using possibly randomized algorithms and Cas , Ras . The class defining C ∗ (B) is empty below M : all-zero labels transfer the classical prediction-free lower bound (Tomkins, 1995). The LR rule of Garay et al. (1997), in the interval formulation of Karavasilis (2025, Lemma 4.5), has C = R = M because it ignores predictions.

Antoniadis et al. (2026) also use binary optimum advice and length rewards, but require release-time order and irrevocable acceptance. TrustGreedy (Boyar et al., 2026) maximizes cardinality, receives a predicted full input set before arrivals, and cannot revoke accepted intervals; its replacements update the unaccepted part of a plan. Other models permit fractional allocation, resumption, recall or unit profits; Appendix R.1 distinguishes these scopes.

Theorem 1 (Optimal consistency under almost-sure guarantees). Allowing randomized algorithms, min A:Ras (A)<∞

2. Model and Main Guarantees

Cas (A) = d.

(3)

The deterministic Shaped-BANK T∗ (Section 4) attains the minimum, also under the stronger requirement that both guarantees hold on every execution.

A request I = [s(I), f (I)) has a unique identity, length w(I) = f (I) − s(I) > 0, and a fixed prediction p(I) ∈ {0, 1} revealed on arrival. Positive-length overlap means conflict; endpoint contact is compatible. A feasible set Pcontains pairwise compatible requests, with w(X) = I∈X w(I). Distinct identities may have coincident intervals.

Corollary 1 (Bounds on its robustness cost). The universal budget and the Shaped-BANK budget satisfy as 4φ + 3 ≤ Bmin (d) ≤ Bmin (d) ≤ R(T∗ ) = B∗ := φ5 . (4) The remaining factor is φ5 /(4φ + 3) ≈ 1.171 for either class.

Requests arrive in arbitrary order. Each arrival is immediately accepted or permanently rejected, maintaining a feasible held set St . Held requests may be revoked; rejected and revoked identities cannot be recalled, but their information may be retained. Future arrivals, their total number and termination time are unknown; any finite prefix may be complete.

Table 1 and Figure 1 distinguish universal bounds from attainments. Theorems 2, 5, and 6 prove Theorem 1; Theorem 4 gives the corollary’s lower endpoint. Naive accepts a positive request exactly when it conflicts with no previously accepted positive, and never revokes; it rejects all negative requests.

Definition 1 (Strict consistency and robustness). For a nonempty finite labelled input σ, let P be its positive requests, OPT = maxX feasible w(X) and ALG = w(Sfinal ). Predictions are perfect when P equals one final optimum, allowing ties. For a possibly randomized algorithm and inputs fixed independently of its coins, define OPT(σ) , ALGA (σ) σ OPT(σ) Cas (A) = sup ess sup . ALGA (σ) σ:P optimal

C(A),

A deterministic:R(A)≤B

3. Universal Lower Bounds Theorem 2. Every deterministic algorithm with finite robustness has C(A) ≥ d. For each such algorithm and every ϵ > 0, a finite perfectly labelled input with a unique optimum gives ratio greater than d − ϵ.

Ras (A) = sup ess sup

(1)

Proof. Perfect labels concern the final input; a stopping prefix may have incorrect labels. Fix a finite robustness 2

Optimal Consistency for Interval Selection

a

b Ta : exact R Ta : certified R LR/RP/Shaped-BANK

LR

Bounds on C * (B)

M

φ5

4φ + 3

(7, 4)

4

Unknown optimal budget

Shaped-BANK 11.090

Gap between known bounds

3.5

Scalar Credit

(10, 25/9)

11.472

3 (φ 5 , d)

Universal lower bound

SUM-BANK

d

15.326

5

7

9

11

Robustness budget B

9

11

13

15

Budget at C = d

Figure 1. Known performance bounds. (a) The universal lower envelope is max{d, G(B), H(B)}; the attainable envelope combines LR with Ta . Solid Ta segments have exact robustness, dotted segments only a certificate; the shaded gap is unresolved. Near B = 6.65, where G meets d + 1/20, the lower envelope switches to H, which is proved only for γ ≤ 1/20. The dashed LR/RP/Shaped-BANK envelope excludes interior Ta parameters; its jump at B = φ5 is Shaped-BANK attaining d. (b) At C = d, the three algorithm budgets are exact, while the universal minimum remains in the marked interval. Both panels concern almost-sure guarantees. Table 1. Principal guarantees. First block: also valid for randomized algorithms with both guarantees almost surely, using Cas , Ras . Second: deterministic attainments. LR is due to Garay et al. (1997); RP’s consistency bound to Karavasilis (2025). The last row instead uses expected reward on fixed inputs. Scope

optimal. Offer the positive interval L = [δ − t, δ). If it is accepted, stop. The positives are compatible and have weight s + t > 1; every positive conflicts with the sole negative J. They therefore form the unique optimum. The algorithm holds at most L, giving ratio at least

Guarantee

Finite almost-sure robustness Cas ≥ d Budget Ras ≤ B Cas ≥ max{d, G(B), H(B)} Optimal Cas = d Ras ≥ 4φ + 3 LR (prediction-free) SUM-BANK at λ = M Shaped-BANK Parametric Ta , α ≤ a ≤ 1 RP, λ ≥ 2 Initial Naive/LR 1<c≤M

(s + t)/t = d − 2δ/t > d − ϵ.

C=R=M C = d, R = 7φ + 4 C = d, R = φ5 C = (1 + a)2 , R ≤ Ka ; equality outside (a− , a+ ) (Theorem 7) C ≤ 3λ/(λ − 1); R = 2λ + 2

If L is rejected, offer the positive unit interval U = [1 − δ, 2 − δ) and stop. The full positives again form the unique optimum, now of weight s+t+1. The algorithm can retain only J or U , so its value is at most one and its ratio is at least d − 2δ > d − ϵ. Emptying the held set only worsens either bound.

mixture, Cexp = c, Rexp = 2φc/(c−1)

Determinism fixes the decision on L from the shared prefix, so the appropriate finite input can be chosen for A without changing any label. Taking the supremum proves the result.

bound R. Let t = α and choose 0 < δ < min{t/2, tϵ/2}. Set s = 1 − 2δ, take an integer m > Rs, and partition [δ, 1 − δ) into m positive tiles of length ℓ = s/m < 1/R.

The same argument applies to two almost-sure guarantees: fix the finite tree of stopping and perfect terminal inputs, and intersect their probability-one guarantee events. A tape in that intersection would survive every branch, contradicting the deterministic argument. All lower bounds below have such finite trees and therefore also hold with ∗ Cas , Ras , Cas in place of C, R, C ∗ (Appendix L.4). Tile rejection relies on unknown termination, strict ratios, and no recall. Figure 2 illustrates the two terminal branches. Ap-

First offer the negative unit interval J = [0, 1), then the tiles. Robustness forces acceptance of J. At the first abandonment of J, only the arriving tile can remain: earlier tiles have been rejected and cannot be recalled. Stopping there gives OPT ≥ 1 and ALG ≤ ℓ < 1/R, a contradiction. Thus every tile is rejected and J remains. This argument uses robustness, since the positive tiles alone are not yet 3

Optimal Consistency for Interval Selection

4. The BANK Mechanism

pendix A gives bounded-size rational witnesses for fixed R.

Each held request has a nonnegative ledger b(J). A positive arrival adds its length once: acceptance inherits revoked ledgers, while rejection distributes the length among conflicts. Negative rejection adds nothing. Ledgers preserve prediction mass lost through irrevocable decisions. P For conflicts D, write W = w(D) and bD = J∈D b̄J , where b̄J is the snapshot before this arrival. The ordinary gate Q(D) is a sum of replacement costs. SUM-BANK uses cost λw(J) (λ = M unless stated) for every conflict. Scalar Credit-BANK uses min{M v, dv+cb} for a negative conflict, with a fixed coefficient c ≥ 0. Shaped-BANK retains cost M v for a positive conflict of length v, but uses

Theorem 3 (A budget-dependent lower curve). For every deterministic algorithm with R(A) ≤ B < ∞ and B ≥ M, C(A) ≥ max{d, G(B)},

B G(B) = √ . (5) ( B − 1)2

A finite binary-reserve tree amplifies missed positive mass under either response to a negative reserve, until a perfect terminal violates consistency (Appendix B). For example, C ∗ (5) > 3.27 and C ∗ (6) > 2.85. The robustness cost remains separated from d even when consistency only approaches its optimum.

q∗ (v, b) = min{2φv, max{dv, φv + αb}} (7) P for a negative conflict. Thus Q(D) = J∈D τ (J), with τ (J) = M w(J) or q∗ (w(J), b(J)) according to its label. The negative cost stays at dv up to b = φv, increases linearly up to b = dv, and then remains at 2φv.

Theorem 4 (A continuous cost barrier). Put β = 4φ + 3. Every deterministic algorithm with finite robustness and C(A) ≤ d has R(A) ≥ β. More generally,   1 β−B , > d (B < β). C ∗ (B) ≥ d + min 100 83φ + 53 (6)

After ordinary acceptance fails, a positive request can still replace all its conflicts if they are negative and w ≥ αW,

Proof sketch: missed sources and a longer reserve. Figure 3 shows four forced decisions: retain the negative anchor K, reject the right reserve R0 , switch to a positive unit J+ (called J in the figure), then reject I, L. Tiny positive tiles force retention of K, of length near φ. Accepting R0 , of length near φ2 , permits a perfect completion violating consistency. To force J+ , a remote anchor and boundary requests repair full-history optimality after either response; analogous completions exclude I, L. The realized history contains a compatible packing of limiting weight φ3 + 1 + φ + φ2 = β while only J+ survives. Hypothetical completion requests are not counted.

w ≥ bD /φ.

The first test permits replacing longer conflicts, unlike 1increasing policies. More generally, an a-increasing rule requires w ≥ a maxJ∈D w(J) when accepting with D 6= ∅; Shaped-BANK satisfies this for a = α. The second prevents the same missed positive mass from being discarded repeatedly. Ordinary acceptance has priority; all thresholds accept equality. For a rejected positive, put Z = [∀J ∈ D : p(J) = 0]. The simultaneous fees are   w w(J)/W, Z, w < αW, (8) gJ = w b̄J /bD , Z, w ≥ αW, w < bD /φ,   w w(J)/W, ¬Z.

For C ≤ d + γ, suppose R(A) < Dl (γ) and choose r strictly between them. A finite remote anchor of length h consumes consistency slack γh. Choosing h = (r − 1)a + ε after a hypothetical switch to held value at most a, and reducing the initial anchor, preserves the four forcing steps. Appendix C supplies finite parameters and strict full-history optimality certificates. Its implicit bound Dl (γ) satisfies Dl (0) = β and Dl (γ) ≥ β − (83φ + 53)γ on [0, 1/100]; approaching equality budgets from below proves (6).

These cases are exhaustive on rejection; ¬Z means that a positive conflict exists. The compatible-positive filter keeps a positive label only if its request is compatible with all earlier kept positives (Appendix K). For fixed parameters, this implementation uses O(n2 ) exact arithmetic operations/comparisons and O(n) stored scalars or interval records, including filtering (Appendix O.4). LemmaP1 (Conservation). For arbitrary labels and each time t, J∈St b(J) = w(Pt ), where Pt is the positive set revealed by time t. All ledgers are finite and nonnegative.

The stronger implicit bound gives Dl (.005) ≈ 8.680 and Dl (.01) ≈ 8.088. A shorter reserve gives Ds on 0 ≤ γ ≤ 1/20, useful farther from d: Ds (.02) > 7.41. Figure 1 combines them as H(B) = max{Hs (B), Hl (B)}, where
Hj (B) = d + sup {0} ∪ {γ ∈ [0, γj ] : B < Dj (γ)} ,

Proof. Acceptance removes the sum bD and adds bD + pw. A rejected negative adds zero; a rejected positive adds fees summing to w. On rejection W > 0, and a ledger-test failure has bD > 0. Induction proves both assertions.

with γs = 1/20 and γl = 1/100. 4

Optimal Consistency for Interval Selection Prefix: J (p = 0) → H1 , …, Hm (p = 1) → L (p = 1) J = [0, 1) δ>0 shaded overlaps

J retained through all tiles

tiles Hk : all rejected

m > Rs, so tile length < 1/R

L

U (p = 1), if L rejected

0

δ

1−δ

1

Accept L: stop

Reject L: append U

ALG ≤ t, OPT = s + t

ALG ≤ 1, OPT = s + t + 1

OPT/ALG ≥ (s + t)/t → d

OPT/ALG ≥ s + t + 1 → d t = α = 1/φ, s = 1 − 2δ, δ ↓ 0 (schematic)

Figure 2. Universal lower-bound construction. Filled left and open right endpoints indicate half-open intervals. The common prefix forces retention of J and permanent rejection of every Hi ; the decision on L selects one of two complete inputs. Both have perfect predictions and a unique optimum. The geometry uses s = 1 − 2δ, t = φ−1 , and δ > 0; six central pieces are drawn schematically.

Algorithm 1 Shared ledger policy with ordinary gate Q

approaching φ + 2 > d. The complete five-request calculation is in Appendix M.

1: Initialize S ← ∅. 2: On arrival of (I, p), with w = w(I): 3: D ← {J ∈ S : J conflicts with I}; W ← w(D). 4: Snapshot P b̄J ← b(J) for every J ∈ D. 5: bD ← J∈D b̄J ; Z ← [∀J ∈ D : p(J) = 0]. 6: Test ordinary w ≥ Q(D) first (true if D = ∅). 7: If it fails, test special p = 1, Z, w ≥ αW , w ≥ bD /φ. 8: if either test accepts then 9: Accept I; permanently revoke all of D. 10: S ← (S \ D) ∪ {I}; b(I) ← bD + pw. 11: else 12: Permanently reject I. 13: if p = 1 then 14: Compute every gJ by (8) from snapshots. 15: Simultaneously set b(J) ← b̄J + gJ for J ∈ D. 16: end if 17: end if 18: All other existing ledgers are unchanged; output S at

The price of a special replacement. A negative lengthφ anchor has zero-ledger cost M . A unit positive replaces it at the special threshold and acquires cost M . Rejections around these successive holders yield a compatible packing approaching φ5 while only the unit survives (Proposition D.5).

5. Why the Ledger Gives Optimal Consistency Theorem 5 (A sufficient consistency interface). Use positive cost M v, the summed ordinary gate, and the shared BANK rules. Suppose the negative cost is finite and satisfies q(v, b) ≥ dv for all b ≥ 0, and v + max{αv, α2 b} ≤ αq(v, b) (0 ≤ b ≤ dv).

termination.

(9)

If the complete positive set P is feasible, every held request satisfies b(J) ≤ dw(J). Consequently w(P ) ≤ d ALG. Shaped-BANK and SUM-BANK with cost M v satisfy this interface; their finite robustness and Theorem 2 imply C = d.

Why length alone does not determine a replacement. For 0 < ε < 1/8, start with negative [0, 1) and reveal the compatible positives [ε, 1/2), [1/2, 1 − ε) and [−α + 2ε, ε). All three are shorter than α and fail both acceptance routes. The holder remains [0, 1), but its ledger grows from zero to φ−3ε > 1. Now positive [1−ε, 1−ε+α) passes the length test at equality. Its ledger test fails: bD > 1 = φw. Removing that test would leave reward α and a perfect-label ratio

Proof sketch: full source shares and directional cuts. Fix a finite execution with feasible complete positive set P . At snapshot n, conserved fractions aX,n (I) assign every arrived positive source I among held identities X. The 5

Optimal Consistency for Interval Selection

measure µX,n (A) =

X

aX,n (I)|I ∩ A|

With no occupied birth side, the first crossing has bpre ≤ v and fee at most αv, reducing to the preceding case. A source crossing both endpoints pays one fee and excludes every later crossing. Thus event-time bounds close capacity.

(10)

I∈P

has mass bn (X) and density at most one; unarrived sources have zero coefficients. Its support is not clipped to X: replacing positive [0, 1) by negative [.9, 6) inherits mass one, not .1. Let E L , ER denote left and right exterior mass and P Ln,X (s) = I∈P :f (I)≤s aX,n (I)w(I) the full left shares. Lemma 2 (Side and directional-cut invariant). Under the cost and BANK-rule hypotheses of Theorem 5, fix a finite execution with feasible complete positive set P . Use the conserved source measure and full shares defined above. Write νX for birth and δX for revocation, or one beyond the final arrival if X survives. For every negative V = [x, x + v) and live snapshot νV ≤ n < δV , each side S ∈ {L, R} satisfies ES,νV (V ) ≤ αv,

At a positive birth, let BQ , WQ be its negative children’s total ledger and length. Ordinary acceptance gives BQ ≤ u, WQ ≤ u/d; special acceptance gives BQ , WQ ≤ φu. Adding Q gives capacity, and compatibility excludes later positive fees. For the cut, set e = z − s, G = s(Q) − s ≥ e. Trace a left source share backward to the first support starting below s. There are three cases. (i) An intermediate positive H occurs before that crossing. Shrinking paths give w(H) ≤ u/d and e < dw(H) ≤ u; the cut is at most BQ + u ≤ du. (ii) Otherwise the negative path starts with child V , of length v. For ordinary Q, G < φv ≤ αu. For special Q, a nonleftmost V gives G < αv ≤ u; if another child K carries left shares, protrusion gives φG < v + w(K) ≤ φu. Again BQ + u pays the cut.

bn (V ) ≤ dv,

ES,n (V ) ≤ max{αv, α2 bn (V )}. For each actual positive T = [s, t) ∈ P arriving after νV , if s < z ≤ t, z ≤ x and LνV ,V (s) > 0, then

(iii) Only the leftmost child V carries shares and Q is special. If s(V ) ≥ s, its inherited birth cut plus the remaining distance gives a bound below φv. Otherwise density gives

LνV ,V (s) + z − s ≤ αv. At each live snapshot n, a positive Q of length u has bn (Q) ≤ du and, for every actual positive T = [s, t) arriving after its live snapshot n, Ln,Q (s)+z−s ≤ du

Ln,Q (s)+e < v +EL (V ) ≤ max{φv, v +α2 b(V )} ≤ du.

(s < z ≤ t ≤ s(Q), Ln,Q (s) > 0).

Here the length gate pays for v ≤ φu and the ledger gate for b(V ) ≤ φu; neither budget alone suffices for this bound. Reflection and source conservation finish w(P ) = P X b(X) ≤ d ALG. Appendix D proves the geometric and boundary-case details.

Both cuts include their reflections under y 7→ −y. The complete proof is in Appendix D.1. Why the negative capacity follows. Induct on accepted birth order, establishing every live snapshot of each earlier identity before using it at a parent’s birth. Earlier children’s cuts and the cost interface pay the new negative birth bounds. The positive cut uses the three cases below. Independently, replacement-tree geometry bounds subtree length by 2v at a negative root and M v at a positive root (Appendix D). Density bounds the mass inside V by v. A side with nonzero exterior mass at birth stays bounded by αv: an existing crossing source excludes another, while wholly exterior birth sources and a later crossing source share the birth-cut budget. Each initially empty side has at most one later crossing source. Its fee obeys g < αv after length failure, or g ≤ αbpre after ledger failure, which implies g ≤ α2 (bpre + g). These are event-time bounds.

At the golden endpoint, q∗ is the smallest cost nondecreasing in b that satisfies this sufficient interface (Proposition D.2). The interface itself is not necessary: setting q(v, 0) = φv and keeping q∗ for b > 0 also preserves d-consistency, by pruning source-free children (Appendix E.1). The relaxed policy still satisfies the nonshrinking hypothesis below, so its robustness is at least φ5 .

6. Exact Robustness and the Remaining Gap Theorem 6 (Exact Shaped-BANK robustness). For arbitrary finite labelled inputs, R(T∗ ) = φ5 .

With two occupied birth sides, b ≤ (1 + 2α)v < dv. With one, the other side’s first crossing has bpre ≤ (1 + α)v, so its fee is at most α(1 + α)v = v. Without that crossing, density already suffices. Thus b ≤ |{z} v +

αv |{z}

inside

protected side

Proof sketch: joint endpoint charges. In the replacement forest, revoked requests are children of their replacements. Give each accepted identity its ordinary cost just before revocation or final termination. Costs do not decrease during a lifetime. An ordinary parent of length h pays at most h in child costs. At a special parent, its negative children have

+ |{z} v = dv. other side

6

Optimal Consistency for Interval Selection

total length and ledger W, bD ≤ φh, and q∗ (v, b) ≤ dv + α3 b, X qi ≤ dW + α3 bD ≤ Ah,

proves the upper bound. The five-request construction in Proposition D.5 approaches φ5 , proving equality. The endpoint cannot be improved merely by reshaping nonshrinking negative costs (q− (v, b) ≥ v) within the same special tests: d-consistency then forces R ≥ φ5 , even without cost continuity or monotonicity (Appendix E.1). To trade consistency for a smaller budget, we change both special thresholds below.

A = φ + 3.

i

For analysis, split each rejected optimal request among its current conflicts in proportion to their costs. These receivers form an ancestry antichain: no receiver is an ancestor of another. The comparator is a fixed offline optimum. Passing the charges to final roots preserves their sum. At most two disjoint optimal requests cross the boundary of a root’s connected accepted hull; the others fit between their cuts. Bounding the two exterior charges jointly with the space remaining between them avoids counting the same interval twice.

6.1. A continuous attainable tradeoff The optimal-consistency endpoint is part of a tunable family. Fix a ∈ [α, 1] and put ma = max{(1 + a)/a2 , 1 + a + a−1 }.

Let HJ be the connected accepted hull of a root J. For a cut x, define LJ (x) as the largest sum of terminal costs over an ancestry antichain in this subtree whose intervals start strictly left of x; define UJ (y) by ends strictly right of y. The cuts x, y are the inward endpoints of the crossing comparator intervals, using the hull endpoints when a crossing is absent. Unless one comparator covers the entire hull, feasibility gives x ≤ y and the root charge is bounded by

Policy Ta uses positive cost ma v, negative cost  qa (v, b) = min (1 + a + a−1 )v, max{(1 + a−1 )v, v/a + b/(1 + a)} , (12) and special tests w ≥ aW , w ≥ abD . In all fee-case guards, replace αW by aW and bD /φ by abD ; the proportional fees, priority and inheritance are unchanged. Theorem 7 (Continuous attainable guarantees). For every a ∈ [α, 1], C(Ta ) = (1 + a)2 and R(Ta ) ≤ Ka = max{Oa , Na }, where the outward and no-bridge coefficients are defined in (D.23): Oa comes from a special root with one outward child; Na from child charges with no child bridging both cuts. The bound is exact on [α, a− ] ∪ [a+ , 1], where a− ≈ 0.677821 and a+ ≈ 0.813824 are the unique roots specified by (D.29) in Proposition D.4. In particular, a α 2/3 1 C(Ta ) d 25/9 4 R(Ta ) φ5 10 7

FJ (x, y) = |HJ ∩ [x, y]| + LJ (x) + UJ (y). The two maxima need not use the same antichain. A comparator covering the entire hull is treated separately: it is the only contributor there and is charged at most Ah. At an ordinary node, its own cost dominates every descendant antichain’s total terminal cost, so the node itself maximizes an endpoint whenever eligible. At a special node J = [a, b), each endpoint maximum is either the root’s singleton cost or the sum of child maxima. Orient a single singleton to the left. If y < b, the gap lies inside J; if y ≥ b, at most one compatible child extends beyond y. With both maxima supplied by children, at most one child bridges both cuts. These alternatives exhaust the geometry, including coincident cuts and equality at an interval endpoint. The coefficients are in Table 2 (Appendix D.3).

All three pairs are exact, and the guarantees hold after the compatible-positive filter. Proof sketch: mechanism of the tradeoff. The source induction separates negative capacity (1 + a)2 v from positive capacity ama v. The exterior-mass bounds become av at birth and max{av, ab/(1+a)} during a negative lifetime. Their weighted cut is paid by qa . In the positive cut’s multichild case, the accepted-history bounds change branch at a3 + a2 = 1; both branches pay the same directional gap. The joint-cut analysis reduces to the two continuous coefficients Oa , Na . Five-request families match the consistency throughout the range and the robustness on the two stated intervals. Appendix D gives the induction, coefficient comparison and matching constructions. At budget 7, T1 improves LR’s M ≈ 4.236 and RP’s certificate 5; continuity extends this improvement to an interval. At budget 10, T2/3

The largest case is a special root with one endpoint charged at the root and the other at an outward child. Write ρ = A/M . Monotonicity and the fixed-ledger slope inequality q∗ (W, bD )−q∗ (v, bD ) ≥ φ(W −v) absorb that child’s cost and excess length. Since ρ − 1 < φ, the total charge is at most (M + 1)h + W + q∗ (W, bD ) ≤ (M + 1 + φ)h + q∗ (φh, φh) = φ5 h.

(11)

The other endpoint choices give smaller coefficients; Appendix D lists and proves them. Summing over final roots 7

Optimal Consistency for Interval Selection

has exact consistency 25/9 < 3. For a− < a < a+ , only Oa ≤ R(Ta ) ≤ Na is known.

false positive’s nonnegative excess of conflicting optimal weight over its own length (Appendix K). Zero conflict error need not make positives feasible, so raw SG lacks this guarantee.

The envelope combines LR’s C = R = M , RP’s C ≤ 3(B − 2)/(B − 4) for B ≥ 6, and Ta . RP has exact robustness 2λ + 2 for λ ≥ 2 (Appendix J); its consistency certificate beats LR above 4 + 3φ ≈ 8.854. Appendix G compares SUM and scalar Credit. For M ≤ B < 7, LR remains the best guarantee among these policies.

Table 5 (Appendix N) reports means, intervals and individual-run fifth percentiles q.05 . Intervals use 10,000 shared whole-input bootstrap resamples (Appendix N.1). LR leads FP .1 and 1 in mean and q.05 . In the two low-FP rows of Table 5, SGF gains .245 and .532 points over LR (paired intervals [.076, .401] and [.365, .693]), and raw SG gains a further .527 and .916 (Appendix N), so filtering is not the source. Both rows use the smallest rate of the prespecified low-FP grid (Appendix O). Perfect-label Naive gets 100% but lacks finite robustness. Filtered SG exceeds filtered RP in all 20 cell means; its differences from best scalar Credit range from about −.001 to .04 points (Appendix N).

7. Guarantees and Learning Interfaces 7.1. Randomization and the guarantee being protected For fixed inputs, measure OPT/E[ALG]. An initial coin selects NAIVE with probability π, otherwise LR. Its exact tradeoff is 2φc R= , 1 < c ≤ M. (13) c−1 Here π = (M/c − 1)/(M − 1). At c = d, R = 2d; at R = φ5 , c ≈ 1.412. On all-negative inputs the Naive branch gains zero. The finite-expected-robustness consistency infimum is one, unattained; the full frontier remains open (Appendix L.2).

Chronological logistic advice on 7 NASA and 31 CTC instances gives SGF 94.58/89.66%, below LR’s 96.86/91.25%. Reward selection on reused blocks mainly chooses all-negative advice; the nonconstant CTC cost score remains below LR (Appendices P.1–P.2).

With only robustness almost surely and consistency in expectation, every finite budget B > 1 instead requires (Proposition L.4)

7.3. What should a learned advice bit predict? The same rejection can leave the same held interval but different ledgers, changing a later replacement; thus the useful prediction can concern continuation reward rather than immediate reward. Appendix Q lets the bit estimate its rollout effect on final reward. Its transfer bound uses the reference policy’s membership error and deployment-state rollout error; the latter is not estimated here. An independent cohort favors lookahead but does not confirm additional learning gains.

1 Cexp ≥ 2 + > 2. B−1 Robustness on a fixed shorter input forces rejection on the shared prefix; a fixed longer perfect input then gives the bound. A half-length special gate with ordinary factor four allows pathwise robustness at most 18, a sharp uniform bound over this action family, but every fixed independent acceptance probability has Cexp ≥ d (Appendix L.5).

8. Discussion

For 0 < π < 1, adapting inputs to observed actions makes the mixture’s expected robustness infinite (Appendix L.3; Ben-David et al., 1994). This further motivates protection of individual executions rather than relying solely on a mixture’s fixed-input expected reward.

The universal budget for attaining d remains in [4φ+3, φ5 ]. The optimal universal frontier and the tradeoff with almostsure robustness but expected consistency are open; within Ta , only (a− , a+ ) lacks exact robustness. Improving the budget upper bound φ5 requires leaving policies that always reject negative arrivals shorter than d times a sole negative holder, even with arbitrary historydependent ledgers and positive rules (Appendix F).

7.2. Workload and learned-label diagnostics NASA-iPSC and CTC-SP2 give 18,066 and 77,205 intervals. Twenty shared reveal/label repetitions flip members (FN) or nonmembers (FP) of one optimum; FP 1 is allpositive, FN 1 all-negative.

A filter-free policy with C = d, finite robustness and a smooth conflict-error guarantee remains open; weighted precision and recall need not control this error (Appendix K.5).

Filtering preserves both exact guarantees and adds OPT ≤ d ALG + ηK . Here ηK is missed optimal weight plus each

8

Optimal Consistency for Interval Selection

Impact Statement

Frontiers of Algorithmics: IJTCS-FAW 2025, volume 15828 of Lecture Notes in Computer Science, pp. 33–48. Springer, 2025. doi: 10.1007/978-981-96-8312-3_3.

The results concern retained length under unrestricted revocation. Proportional fees account for one cancellation cost, but not reliability obligations or unequal consequences across users. Training labels inherit their offline objective’s biases; neither optimal membership nor these competitive ratios ensure fair allocation. The public job traces are used only to construct selection instances, without inferring individual behavior.

Borodin, A. and Karavasilis, C. Any-order online interval selection. In Byrka, J. and Wiese, A. (eds.), Approximation and Online Algorithms: 21st International Workshop, WAOA 2023, volume 14297 of Lecture Notes in Computer Science, pp. 175–189. Springer, 2023. doi: 10.1007/978-3-031-49815-2_13. Boyar, J., Favrholdt, L. M., Kamali, S., and Larsen, K. S. Online interval scheduling with predictions. Journal of Computer and System Sciences, 160:103795, 2026. doi: 10.1016/j.jcss.2026.103795.

References Ameli, A. J., Sanità, L., and Venzin, M. Learningaugmented online covering problems. In Proceedings of the 43rd International Conference on Machine Learning, volume 306 of Proceedings of Machine Learning Research, pp. 2307–2331. PMLR, 2026.

Chen, P., Zhao, H., Tang, X., Wang, Y., and Deng, S. Towards optimal robustness in learning-augmented paging. In Proceedings of the 43rd International Conference on Machine Learning, volume 306 of Proceedings of Machine Learning Research, pp. 18492–18516. PMLR, 2026.

Angelopoulos, S., Dürr, C., Jin, S., Kamali, S., and Renault, M. Online computation with untrusted advice. In 11th Innovations in Theoretical Computer Science Conference, volume 151 of Leibniz International Proceedings in Informatics, pp. 52:1–52:15, 2020. doi: 10.4230/LIPIcs.ITCS.2020.52.

Dallot, J., Emek, Y., Gil, Y., Pacut, M., and Schmid, S. Online algorithms with unreliable guidance. arXiv:2602.20706v2, 2026. Daneshvaramoli, M., Karisani, H., Lechowicz, A., Sun, B., Musco, C. N., and Hajiesmaili, M. Nearoptimal consistency-robustness trade-offs for learningaugmented online knapsack problems. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pp. 12459–12489. PMLR, 2025.

Antoniadis, A., Coester, C., Elias, M., Polak, A., and Simon, B. Online metric algorithms with untrusted predictions. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 345–355, 2020. Antoniadis, A., Shahheidar, A., Shahkarami, G., and Soltani, A. A switching framework for online interval scheduling with predictions. Proceedings of the AAAI Conference on Artificial Intelligence, 40(43): 36129–36136, 2026. doi: 10.1609/aaai.v40i43.40930.

Elmachtoub, A. N. and Grigas, P. Smart “predict, then optimize”. arXiv preprint arXiv:1710.08005v5, 2020. Author preprint version 5, revised 19 November 2020. Feitelson, D. G., Tsafrir, D., and Krakov, D. Experience with using the parallel workloads archive. Journal of Parallel and Distributed Computing, 74(10):2967–2982, 2014. doi: 10.1016/j.jpdc.2014.06.013.

Babaioff, M., Hartline, J. D., and Kleinberg, R. D. Selling ad campaigns: Online algorithms with cancellations. In Proceedings of the Tenth ACM Conference on Electronic Commerce, 2009. URL https://www.eecs.northwestern. edu/~hartline/papers/buyback-EC-09.pdf.

Fung, S. P. Y., Poon, C. K., and Zheng, F. Improved randomized online scheduling of intervals and jobs. arXiv preprint arXiv:1204.2933, 2012.

Ben-David, S., Borodin, A., Karp, R., Tardos, G., and Wigderson, A. On the power of randomization in online algorithms. Algorithmica, 11(1):2–14, 1994. doi: 10.1007/BF01294260.

Garay, J. A., Gopal, I. S., Kutten, S., Mansour, Y., and Yung, M. Efficient on-line call control algorithms. Journal of Algorithms, 23(1):180–194, 1997. doi: 10.1006/ jagm.1996.0821.

Benomar, Z. and Perchet, V. Non-clairvoyant scheduling with partial predictions. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 3506–3538. PMLR, 2024.

Grigorescu, E., Lin, Y.-S., and Song, M. Learningaugmented algorithms for online concave packing and convex covering problems. In Proceedings of the 28th International Conference on Artificial Intelligence and Statistics, volume 258 of Proceedings of Machine Learning Research, pp. 1072–1080. PMLR, 2025.

Berg, M. Comparing the hardness of online minimization and maximization problems with predictions. In 9

Optimal Consistency for Interval Selection

Jin, B. and Ma, W. Online bipartite matching with advice: Tight robustness-consistency tradeoffs for the two-stage model. In Advances in Neural Information Processing Systems, volume 35, 2022. URL https://proceedings.ne urips.cc/paper_files/paper/2022/file/5d68a3f05ee2aae6 a0fb2d94959082a0-Paper-Conference.pdf.

Purohit, M., Svitkina, Z., and Kumar, R. Improving online algorithms via ML predictions. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https://papers.neurips.cc/pape r_files/paper/2018/hash/73a427badebe0e32caa2e1fc753 0b7f3-Abstract.html.

Karavasilis, C. Interval selection with binary predictions. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, pp. 8527–8535. International Joint Conferences on Artificial Intelligence Organization, 2025. doi: 10.24963/ijcai.2025/948.

Ross, S. and Bagnell, J. A. Reinforcement and imitation learning via interactive no-regret learning. arXiv preprint arXiv:1406.5979v1, 2014.

Khodak, M., Balcan, M.-F., Talwalkar, A., and Vassilvitskii, S. Learning predictions for algorithms with predictions. In Advances in Neural Information Processing Systems, volume 35, pp. 3542–3555, 2022.

Ryabchenko, A., Attias, I., and Roy, D. M. Capacityconstrained online learning with delays: Scheduling frameworks and regret trade-offs. In Proceedings of Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pp. 4973–5014, 2025.

Li, Y., Lavasani, A. M., and Pankratov, D. Online interval selection on a simple chain. Theoretical Computer Science, 1085:116195, 2026. doi: 10.1016/j.tcs.2026.116 195.

SchedMD. Slurm workload manager: Advanced resource reservation guide, n.d. URL https://slurm.schedmd.co m/reservations.html. Accessed 18 October 2026; live documentation.

Lipton, R. J. and Tomkins, A. Online interval scheduling. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 302–311, 1994.

Seiden, S. S. Randomized online interval scheduling. Operations Research Letters, 22(4–5):171–177, 1998. doi: 10.1016/S0167-6377(98)00019-4.

Lykouris, T. and Vassilvitskii, S. Competitive caching with machine learned advice. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 3296– 3305. PMLR, 2018.

Tesauro, G. and Galperin, G. R. On-line policy improvement using monte-carlo search. In Advances in Neural Information Processing Systems, volume 9, 1996. URL https://proceedings.neurips.cc/paper_files/paper/1996/ hash/996009f2374006606f4c0b0fda878af1-Abstract.ht ml.

Mitzenmacher, M. and Vassilvitskii, S. Algorithms with predictions. arXiv:2006.09123, 2020.

Tomkins, A. Lower bounds for two call control problems. Information Processing Letters, 56(3):173–178, 1995. doi: 10.1016/0020-0190(95)00147-5.

Nair, V., Bartunov, S., Gimeno, F., von Glehn, I., Lichocki, P., Lobov, I., O’Donoghue, B., Sonnerat, N., Tjandraatmadja, C., Wang, P., Addanki, R., Hapuarachchi, T., Keck, T., Keeling, J., Kohli, P., Ktena, I., Li, Y., Vinyals, O., and Zwols, Y. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13349v3, 2021.

Wang, Z., Zhang, Y., Wei, Z., and Li, S. Bandit learning for online scheduling with immediate decision. In Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, volume 337 of Proceedings of Machine Learning Research, pp. 7168–7199. PMLR, 2026.

Parallel Workloads Archive. The Cornell Theory Center (CTC) IBM SP2 log. Dataset documentation, n.d.a. URL https://www.cs.huji.ac.il/labs/parallel/workload/l_ctc_s p2/index.html.

Wei, A. and Zhang, F. Optimal robustness-consistency trade-offs for learning-augmented online algorithms. In Advances in Neural Information Processing Systems, volume 33, 2020. URL https://proceedings.neurips.cc/pap er/2020/file/5bd844f11fa520d54fa5edec06ea2507-Pap er.pdf.

Parallel Workloads Archive. The NASA Ames iPSC/860 log. Dataset documentation, n.d.b. URL https://www.cs .huji.ac.il/labs/parallel/workload/l_nasa_ipsc/index.htm l.

Woeginger, G. J. On-line scheduling of jobs with fixed start and end times. Theoretical Computer Science, 130(1):5– 16, 1994. doi: 10.1016/0304-3975(94)90150-3.

Parallel Workloads Archive. Standard Workload Format, version 2.2. Format documentation, n.d.c. URL https: //www.cs.huji.ac.il/labs/parallel/workload/swf.html. 10

Optimal Consistency for Interval Selection

Technical Appendix Guide to the appendix Question

Reading route

Universal consistency and budget lower bounds Parametric guarantees, exact intervals and cost limits

Appendices A–C Appendix D, especially Proposition D.4; penalties in Appendix E and history-dependent restriction in Appendix F Overview in Appendix G; proofs in Appendices H–J Appendix K; randomized guarantees in Appendix L, including the sharp safe action family in Proposition L.5 Results in Appendices M–N and P; shared protocol in Appendix O Appendix P.2; rollout and its expected reference certificate in Appendix Q Appendix R

Credit, SUM and RP guarantees Filtering and randomized guarantees Mechanism experiments and protocol Learned labels and rollout advice Model and literature comparisons

Notation guide The algorithm stores only requests, labels and ledgers. Source measures, cuts, capacities and replacement histories are proof quantities. Notation Core policies and error φ, α, d, M T∗ , q∗ (v, b) Ta , q a , C a , K a Oa , N a , a − , a + τ (J), qJ W, bD , b(J) ηK (P, O)

Meaning Golden ratio, α = 1/φ, optimal consistency d = φ2 , and positive cost coefficient M = φ3 . Shaped-BANK and its negative cost for length v and ledger b, defined in (D.18). Parametric policy, negative cost, exact consistency (1 + a)2 , and robustness certificate for a ∈ [α, 1]. Outward and no-bridge coefficients, with Ka = max{Oa , Na }; exact robustness holds on [α, a− ] ∪ [a+ , 1]. A held request’s current ordinary cost and its terminal cost at revocation or final termination; subscripts specify the policy. Total conflicting length, total conflicting ledger, and the ledger of a current request; some appendix proofs denote the total ledger by B. Conflict-sensitive error of original labels relative to a fixed optimum; subscript K names the metric.

Lower bounds and attained budgets B∗ , BC∗ , BS Exact Shaped-BANK, best scalar Credit and SUM endpoints φ5 , 4φ + 5 and 7φ + 4. G(B), Ds , Dl , H Binary-reserve lower curve, short/long-reserve necessary budgets, and H = max{Hs , Hl } from their inverse consistency bounds. β Local notation: 4φ + 3 in Appendix C; φ in Appendix I; a free transfer parameter in Appendix J. π, rLR Initial-mixture probability of Naive and the LR ratio rLR = M . Appendix variants and proof quantities βa , q0,a , Qa , ma , ka Appendix D’s parameter-dependent cost and capacity coefficients; Qa is distinct from a request Q. h0,a , h1,a , θa , ca , Aa , ρa Parameter-dependent history, source-share and terminal-cost coefficients in (D.1) and (D.19); a3c + a2c = 1 marks the history branch change. Aλ Descriptive MAX-BANK comparator with α = 1/φ, β = φ and ordinary maximum threshold λ. Sλ SUM-BANK with the same special tests and ledgers, and ordinary total-conflict threshold λ. Tc , c ∗ = α 3 Scalar Credit-BANK and its best consistent coefficient; T = Tφ/2 denotes the fixed c = φ/2 comparison. aX,n (I), µX,n , EL , ER Conserved share of positive source I in X, its source measure, and the mass exterior to X on each side. P, P ′ Original positive set and permanent feasible positive history produced by the filter.

11

Optimal Consistency for Interval Selection

A. Finite universal witnesses Theorem 2 gives the complete stopping-prefix proof. For its bounded-size refinement, fix a finite robustness bound R ≥ 1 with OPT(τ ) ≤ RALGA (τ ) on every nonempty labelled prefix τ. (A.1) Write J = [0, 1), s = 1 − 2δ and ℓ = s/m < 1/R. The positive requests are Hk = [δ + (k − 1)ℓ, δ + kℓ),

k = 1, . . . , m,

(A.2)

L = [δ − t, δ),

(A.3)

U = [1 − δ, 2 − δ).

(A.4)

The negative anchor J is followed by the Hk and L; U arrives only if L is rejected. Thus σ − = (J, H1 , . . . , Hm , L) and σ + = (J, H1 , . . . , Hm , L, U ). Figure 2 shows both branches. Corollary A.1 (Bounded-size witnesses with a prescribed ratio). Fix a deterministic algorithm A in the model in the main text and any valid finite robustness bound R ≥ 1 satisfying (A.1). For every real number κ ∈ (2, d), there is a finite input σκ with at most dRe + 3 requests such that its positive requests form its unique optimal solution and OPT(σκ ) = κ. ALGA (σκ ) If κ is rational, all interval endpoints can be chosen rational. In particular, for this same A and R, every ε > 0 admits a rational-endpoint input with at most dRe + 3 requests, unique optimum, perfect predictions, and ratio greater than d − ε. Proof. Fix κ ∈ (2, d), and set t=

κ−1 , κ

s=

(κ − 1)2 , κ

δ=

1−s 3 − κ − κ−1 = , 2 2

m = dRe,

ℓ=

s . m

(A.5)

Since 2 < κ < d, we have κ2 − 3κ + 1 < 0, and hence 0 < s < 1 and δ > 0. Moreover, 0 < t < 1,

t − 2δ = κ − 2 > 0,

s + t = κ − 1 > 1.

(A.6)

In particular, 0 < δ < t/2 < 1/2. Also, m ≥ R > Rs,

0<ℓ=

s s 1 ≤ < . m R R

(A.7)

Thus the same m, chosen solely from R, works for every κ in the stated range. Use the requests J, H1 , . . . , Hm , L, U defined in (A.2)–(A.4) and the preceding definition of J, now with the parameters (A.5). The prefix argument of Theorem 2 applies because ℓ < 1/R: the algorithm must retain J and permanently reject every Hk . Explicitly, a first abandonment at Hk would leave value at most ℓ, while stopping at that prefix leaves the offline request J of weight one, contradicting (A.1). The geometry is unchanged: the positive requests are mutually compatible, each conflicts with the sole negative request J, and the positive total weights in the two complete inputs are OPT(σ − ) = s + t = κ − 1 > 1,

OPT(σ + ) = s + t + 1 = κ > 1.

They are therefore the unique optima, so both inputs have perfect predictions. If A accepts L, choose σ − . Its only possible nonempty final set is {L}, and (A.1) excludes an empty final set. Hence its value is exactly t, giving κ−1 OPT(σ − ) = = κ. ALGA (σ − ) (κ − 1)/κ If A rejects L, choose σ + . Its only possible nonempty final sets are {J} and {U }, each of weight one. Again (A.1) excludes the empty set, so the ratio is exactly κ. As in Theorem 2, determinism and unknown termination allow the appropriate complete input to be fixed for A, with no change to its labels. 12

Optimal Consistency for Interval Selection

The two branches use m + 2 and m + 3 requests, respectively. If κ is rational, then t, s, δ, and ℓ = s/m are rational, so every endpoint in the construction is rational. Finally, for any ε > 0, choose a rational
κ ∈ max{2, d − ε}, d . The construction gives the asserted rational witness with the same request bound.

Request count and the limiting boundary. The request bound dRe + 3 is uniform in κ and ε for fixed R, but not over all algorithms. Rational endpoints give finite descriptions without a uniform encoding-length bound as κ → d. The gap δ > 0 is essential: at δ = 0, L = [−t, 0) and U = [1, 2) are compatible with J = [0, 1). The two branch bounds ALG ≤ t and ALG ≤ 1 no longer follow, and replacing the Hk by J gives a second optimum of equal weight. The witnesses therefore keep δ > 0 and only approach this limit.

B. An all-algorithm tradeoff by binary reserve amplification Put φ = (1 +

√

5)/2, d = φ2 , and t G(t) = √ , ( t − 1)2

t > 1.

(B.1)

The following bound applies to every deterministic algorithm in the original model. Theorem B.1 (Universal consistency–robustness tradeoff). For every finite B ≥ φ3 , an algorithm with R(A) ≤ B satisfies C(A) ≥ max{d, G(B)}. In particular, R(A) ≤ 5 =⇒ √ and R(A) ≤ 6 implies C(A) ≥ (42 + 12 6)/25.

√ 15 + 5 5 > 3, C(A) ≥ 8

(B.2)

(B.3)

Corollary B.1 (Endpoint of the binary-reserve bound). An algorithm with C(A) = d has R(A) ≥ φ4 = 3φ + 2.

(B.4)

Theorem 4 strengthens this endpoint to 4φ + 3; the continuous bound above remains useful away from C = d. Proof of Theorem B.1 and its corollary. We prove the theorem by constructing a finite adaptive input for every strict pair φ3 ≤ r < φ 4 ,

d ≤ c < G(r).

(B.5)

All requests have positive length and all stated conflicts have positive overlap. Labels are fixed at arrival. At every prefix at which consistency is invoked, the complete positive set is a feasible unique optimum. Exchange certificates. For a feasible positive set P and a set S of negative requests, let P (S) be the positive requests intersecting at least one member of S. If w(P (S)) > w(S)

for every nonempty feasible negative set S,

(B.6)

then P is the unique optimum. Indeed, any feasible solution using exactly the negatives S has weight at most w(S)+w(P \ P (S)) < w(P ). A proper subset of P also has smaller weight. In the induction below, the certificate for old negatives uses old positives and that for newly added negatives uses a disjoint group of new positives. Thus their weights can be added even when a single new positive intersects several new negatives.

13

Optimal Consistency for Interval Selection

The two ideal transitions. Write k = c − 2, and define F (q) =

A = (r − 1)(c − 1) − 1,

c , A − rq

T (q) =

1+q . k+1−q

(B.7)

Since r ≥ φ3 > 4 and G decreases with G(4) = 4, we have 0 < k < 2. Also G(r) < r for r > 4, so r − c > 0. On [0, k], A − rq ≥ A − rk = r − c > 0,

k + 1 − q ≥ 1.

The sign of F (q) − q is the sign of rq 2 − Aq + c. Its discriminant, ∆ = A2 − 4rc = (r − 1)c − r

2

− 4rc,

√

has, as a quadratic in c, roots r/( r + 1)2 < 1 and G(r). Hence (B.5) gives ∆ < 0 and F (q) > q. Furthermore, T (q) − q = Consequently

q 2 − kq + 1 > 0, k+1−q

q 2 − kq + 1 = (q − k/2)2 + 1 − k 2 /4 > 0.

µ = min min{F (q), T (q)} − q > 0. 0≤q≤k

(B.8)

Starting at q = 0, every ideal sequence of the two transitions exceeds k within bk/µc + 1 steps. This gives a uniformly finite binary response tree. A strict initial state. Choose a sufficiently small δ0 > 0. Present negative J = [0, 1), which robustness forces the algorithm to accept. Present positive pieces partitioning [δ0 , 1 + 2δ0 ): prescribe the final piece [1 − δ0 , 1 + 2δ0 ) and partition [δ0 , 1 − δ0 ) into pieces shorter than 1/r. Take δ0 < 1/2 and 3δ0 < 1/r. Every piece strictly intersects J. At the first departure from J, only the incoming piece could be held, contradicting robustness because historical OPT ≥ 1. Thus all pieces are missed. Their total weight is 1 + δ0 > 1, and each conflicts with the sole negative J, so they form a unique optimum. The algorithm holds J alone. The inductive state and terminal tail. At a live state the algorithm holds a sole negative anchor Q = [b, b + x). Every positive has been missed; their feasible set P is the unique optimum and has weight p = x + w,

q = w/x > 0.

The leftmost positive endpoint is b + δ, where 0 < δ < x, and every positive starts at or to the right of that point. Initially (x, w, δ) = (1, δ0 , δ0 ). If q > k, append a positive tail of length x ending at b + δ. It is compatible with P and overlaps Q by δ. The old exchange certificates persist after adding a compatible positive, so the full positive set remains uniquely optimal. Either nonempty response has gain x, but its optimum has weight p + x = 2x + w > cx. The empty response violates robustness. This terminates the branch. A reserve and the accepting branch. Suppose q ≤ k. Set z = (c − 1)x − w,

ℓ = z + δ,

Z = [b + δ/4 − z, b + δ/4).

(B.9)

Then z ≥ x > 0. Present Z as a negative request. It overlaps Q by δ/4 and is separated from P by a gap of 3δ/4. If Z is accepted, put ζ = δ/16 and present a positive partition of [left(Z) + ζ, right(Z) + 2ζ). Prescribe the final crossing piece [right(Z) − ζ, right(Z) + 2ζ) and partition the preceding interval into pieces shorter than x/r. We choose the initial perturbation so that 3ζ < x/r and z > 2ζ at every such state. Every piece strictly intersects Z. 14

Optimal Consistency for Interval Selection

Historical Q has length x, so robustness forces every piece to be missed. All new positives end at or before b+3δ/8 < b+δ, hence are compatible with P . The new positive group has weight z + ζ > z and every member intersects Z. For any feasible subset of historical negatives, use its old conflict certificate inside P ; if it also contains Z, add this new group. The groups contain distinct positive requests, so (B.6) holds for every subset and the augmented positive set is uniquely optimal. The new state has x′ = z,

w′ = x + w + δ/16,

δ ′ = δ/16.

(B.10)

Its density tends to T (q) as δ/x → 0. The small right-crossing piece repairs the reserve while leaving a positive free margin at its left endpoint. The rejecting branch and a forced reset. If Z is rejected, present positive L = [b − z, b + δ),

w(L) = ℓ.

It contains Z with margins δ/4 and 3δ/4, is compatible with P , and overlaps Q by δ. Old P certifies every old negative subset, while L alone strictly dominates Z. Thus P + L is uniquely optimal. Its weight is p + ℓ = cx + δ, so retaining Q violates consistency. A surviving algorithm accepts L. Present negative X, ending at left(Z), of length x′ = rℓ − p − z + δ = (A − rq)x + (r + 1)δ ≥ (r − c)x + (r + 1)δ > 0.

(B.11)

It overlaps L by δ/4 and is compatible with Z and every member of P . The historical feasible set P + Z + X has weight rℓ + δ, forcing replacement of L by X through robustness. Fill [left(X) + δ/4, left(L)) with positive pieces shorter than x′ /r. Its length is x′ − δ/2 > 0 by (B.11). Each piece intersects X, and historical X forces every piece to be missed. The new positive group, consisting of L and this fill, has weight ℓ + x′ − δ/2 = x′ + z + δ/2. For the newly added negatives, the full certificates are negative subset {Z} {X} {Z, X}

positive conflict group L L + fill L + fill

strict surplus δ z + δ/2 δ/2.

In the joint row the positive group is counted once. Combining a row with the old certificate inside P establishes (B.6) for every feasible historical negative subset. Hence the full positive set is uniquely optimal. All positives have been missed, X is the sole held request, and the new state is x′ = Ax − rw + (r + 1)δ,

w ′ = cx + δ/2,

δ ′ = δ/4.

(B.12)

Its limiting density is F (q). One finite perturbation for the complete tree. The ideal binary tree from (B.8) has finitely many nodes. All its nonterminal anchor lengths are positive, since the transition denominators are bounded below by r − c and 1; every terminal density strictly exceeds k. For each branch, the initial state and the exact updates (B.10), (B.12) depend continuously on δ0 near zero and converge to the corresponding ideal states. Choose one sufficiently small δ0 > 0 simultaneously for all nodes. Then all ideal terminal excesses remain positive, all anchor lengths remain positive, and every required ratio δ/x is small enough to ensure δ < x, z > 2ζ, and 3ζ < x/r, as well as the initial seed inequalities. The margin is divided by 16 on acceptance and by 4 on rejection. Anchor lengths need not increase: continuity at the finitely many positive ideal lengths controls every ratio separately. If a perturbed state 15

Optimal Consistency for Interval Selection

crosses k earlier, terminate there. Otherwise it reaches a terminal level of the finite ideal tree with its strict terminal excess preserved. All overlaps and forcing margins that vanish in the ideal limit have explicit positive finite identities. These are the overlaps δ/4, δ, δ/4 at the reserve, positive repair, and reset; the accepting repair surplus δ/16; the two forcing surpluses δ; and the joint reset certificate surplus δ/2. The seed has positive surplus δ0 and a crossing piece of length 3δ0 . Causality, all responses, and termination. Each partition has finitely many pieces. Along a surviving history the held set is a singleton and the incoming request intersects it. The legal responses are therefore to retain that singleton, replace it by the incoming request, or hold nothing. Empty responses violate robustness. Both nonempty reserve responses are continued explicitly. At all other steps the alternative response has a strict violation at the current prefix, where the adversary may stop. Voluntary revocation creates no additional available request, and rejected or revoked requests cannot be recalled. Thus the construction covers every deterministic decision and uses no assumption about the termination time. All consistency invocations have the complete positive optimum certified above. The finite response tree proves the contradiction for every strict pair (B.5). For φ3 ≤ B < φ4 and every d ≤ c < G(B), the construction gives C(A) > c. Therefore C(A) ≥ G(B) by taking the supremum over those c. Since G is decreasing and G(φ4 ) = d, the established universal lower bound C(A) ≥ d proves Theorem B.1 for all stated budgets. The corollary follows at the crossing. More generally, G(G(t)) = t, so for d ≤ c < G(φ3 ) the theorem equivalently requires R(A) ≥ G(c) whenever C(A) ≤ c. Scope of the lower bound. The proof provides no matching algorithm. At c = d and r = φ4 , the reset map F has a double fixed point at q = k; its ideal orbit from zero approaches k from below. For larger r its smaller fixed point is below k. Always rejecting the reserve therefore prevents this ideal construction from crossing k. This explains the limit of the present mechanism. Corollary B.2 (An explicit finite request bound). For a strict pair (r, c) in (B.5), put  k = c − 2,

A = (r − 1)(c − 1) − 1,

∆ = A − 4rc, 2

m0 = min

−∆ 1 − k 2 /4 , 4rA k + 1

 > 0.

Set N = bk/m0 c + 1 and Q = max{br(c − 1)c + 3, brc + 4}. The binary-reserve adversary can use at most brc + 4 + N Q requests on every branch. The bound depends on the strict target ratios, not on the algorithm or the choice of sufficiently small perturbation and allowed subdivisions. Proof. On [0, k], completing the square gives rq 2 − Aq + c ≥ −∆/(4r), while 0 < A − rq ≤ A. Thus F (q) − q ≥ −∆/(4rA). Likewise q 2 − kq + 1 ≥ 1 − k 2 /4 and 0 < k + 1 − q ≤ k + 1, so T (q) − q ≥ (1 − k 2 /4)/(k + 1). Every ideal branch therefore terminates in at most N transitions. The common finite-tree perturbation in the proof preserves this depth; a perturbed branch reaching q > k sooner terminates sooner. Partition a segment of length L into bL/uc + 1 equal pieces whenever every piece must be strictly shorter than u. The seed uses the anchor, at most brc + 1 interior pieces, and one prescribed crossing piece. On an accepting-reserve transition, z/x = c−1−q ≤ c−1: the reserve, at most br(c−1)c+1 interior pieces, and the crossing piece use at most br(c−1)c+3 requests. On a rejecting-reserve transition, the reserve, positive repair and negative reset are three requests. The fill has length less than x′ , with pieces shorter than x′ /r, so at most brc + 1 pieces suffice. Finally one terminal tail is enough. Adding these counts gives the displayed bound. Early violations or voluntary deletion only shorten a branch.

16

Optimal Consistency for Interval Selection

C. Source-first budget bounds with two reserve lengths Put c = d + γ, k = d + γr, and β = 4φ + 3. We use two constructions, distinguished by the length of a rejected right reserve. Their limiting packing values are   1 1 1 Fs (γ, r) = 2Vs + (1 + Vs ) + , Vs = , k k−2 c−2     1 1 1 1 + (1 + Vl ) + , Vl = . (C.1) Fl (γ, r) = Vl 1 + c−2 k k−2 k−2 The short-reserve construction allows 0 ≤ γ ≤ 1/20; the long-reserve construction allows 0 ≤ γ ≤ 1/100. Let Ds (γ) and Dl (γ) solve Dj (γ) = Fj (γ, Dj (γ)), j ∈ {s, l}. (C.2) Theorem C.1 (Necessary robustness budgets). The roots above are unique in [6, 2φ3 ] and [8, β], respectively. Each is continuous and strictly decreasing on its stated domain, with Ds (0) = 2φ3 and Dl (0) = β. In the model of Section 2, every deterministic algorithm with finite robustness satisfies C(A) ≤ d + γ

=⇒

R(A) ≥ Dj (γ)

on the corresponding domain. Every perfect terminal used below has a unique full-history optimum equal to the complete positive family. For fixed γ, each Fj is nonincreasing in r, so Fj −r is strictly decreasing. Each Fj strictly decreases with γ at fixed positive r. At the upper root endpoints its value is at most that endpoint, with equality when γ = 0. For the short construction, 13/5 < d < 21/8 gives   80 67 40 40 Fs (γ, 6) > + + > 6. 27 27 117 37 For the long construction, d < 131/50 gives k < 27/10, c < 263/100 at r = 8, and hence     10 100 17 10 10 10670 Fl (γ, 8) > 1+ + + = > 8. 7 63 7 27 7 1323 Continuity proves existence and uniqueness. The strict parameter decrease and uniqueness on a compact interval prove the root properties. C.1. A finite completion For a feasible positive family P, let ΓP (S) be the positive identities conflicting with a negative family S. The condition w(ΓP (S)) > w(S)

for every nonempty feasible negative family S

(C.3)

makes P the unique full-history optimum: a packing using S has weight at most w(P) − w(ΓP (S)) + w(S), and a proper subset of P also has smaller weight. Lemma C.1 (Completion with finite consistency slack). Let c = d + γ, γ ≥ 0, and r > 1. Suppose the complete positive family P is feasible, ends at or before p, and has weight P0 . The negatives are N and an unavailable R0 = [p, p + z), z > 0. Suppose (C.3) holds for every nonempty feasible subset of N . The held weight is at most a > 0, and a historical feasible family has weight at least a. If finite h, ζ > 0 satisfy h > (r − 1)a,

h > 2ζ,

p + αh − ζ > every old right endpoint,

αh > z + 2ζ, P0 − ca − γh − 2ζ > 0,

(C.4)

there is a finite continuation causing an r-robustness violation or a c-consistency violation at a unique-perfect terminal. Proof. Set b = p + αh − ζ and offer negative H = [b, b + h), disjoint from all old requests. Omitting it leaves gain at most a < (a + h)/r, so it must be retained. Offer a finite positive partition F of [b + ζ, b + h − ζ), each tile shorter than (a + h)/r − a. A first departure from H leaves at most a plus the incoming tile, so robustness forces every tile to be missed. 17

Optimal Consistency for Interval Selection

Offer positive U = [p, p + αh). If retained, stop. The gain is at most a + αh, while the complete positives weigh P0 + φh − 2ζ. Their consistency excess is P0 − ca − αγh − 2ζ > 0. If U is rejected and H discarded, stop for a robustness violation. Otherwise offer positive V1 = [b + h − ζ, b + 2h − ζ) and stop. Every response has gain at most a + h, whereas the positives weigh P0 + dh − 2ζ, with excess P0 − ca − γh − 2ζ > 0. The old positive group strictly pays every feasible subset of N . The disjoint new group {U } ∪ F strictly pays R0 , since αh > z; it pays H or {R0 , H}, since its weight φh − 2ζ exceeds h + z. This covers every mixed negative family without double counting. Adding V1 preserves the certificate. All partitions are finite, no old request is recalled, and voluntary deletion only reduces the gain bounds. C.2. One construction with short or long reserves Figure 3 shows the surviving long-reserve branch and the compatible packing used at its terminal state. Proof of Theorem C.1. Choose a construction j in its stated domain and suppose C(A) ≤ c and R(A) < Dj (γ). Choose r > R(A) strictly below the root, with r ≥ 6 for j = s or r ≥ 8 for j = l. Then Fj (γ, r) > r. Write V = Vj , P = 1 + V , and set 10 6 + + 12, k−2 k   1 Fj (γ, r) − r 0 < ε < min , . 10000 Ξj Ξs =

Ξl =

10 6 4 + + + 17, k−2 k c−2 (C.5)

Use common parameters v = V − 4ε,

p = 1 + v − 2ε = P − 6ε,

t = p/k − ε,

ℓ = (p − 4ε)/(k − 2),

and reserve length

( z=

v − ε, v/(c − 2) − 10ε,

s = ε − ℓ,

(C.6)

j = s, j = l.

Both cases satisfy v > 1, p > 2, 4/5 < t < 1 − 2ε, ℓ > 2, and ε < v/(4r). In the short case z < v < φ; in the long case v < z < d. To check the uniform bounds, in the short case V > 40/27, p > 67/27 − 6/10000 and k < 61/20 imply t > 4/5; in the long case V > 25/18, p > 2.38 and k < 68/25 do so. In both cases p ≤ d − 6ε, so t ≤ 1 − (6/k + 1)ε and p − v − t ≥ (6/k − 1)ε > 0. Missed sources and a rejected right reserve. Offer negative K = [1 − ε, 1 − ε + v) and a positive partition A0 of [1, p), each tile shorter than v/r. Finite robustness first forces K to be retained; at a first departure from it, only the incoming tile could remain. Historical K would then give a ratio exceeding r. Thus every tile is missed and K remains alone. Offer negative R0 = [p, p + z), overlapping K by ε. If retained, offer positive S = [1 − ε, 1), then a positive partition F of [p, p + z − ε) whose first tile is [p, p + 2ε) and all tiles are shorter than v/(2r). Discarding R0 on S leaves at most ε < v/r; a first departure on a tile leaves at most ε plus that tile, also below v/r. Hence R0 is retained throughout. Offer positive TR = [p + z − ε, p + 2z − ε) and stop. Every response has gain at most z + ε, and the complete positive weight is v + 2z − 2ε. Its excess over c times the gain bound is ( (3 − c)v − 4ε > 0, j = s, (9c − 22)ε > 0, j = l. The positives are compatible. The group S, A0 and the first new tile conflicts with K and weighs v + ε > v. The group F, TR conflicts with R0 and weighs 2z − ε > z. Since K, R0 conflict, these checks cover every feasible negative family. The terminal is unique-perfect, contradicting consistency. Consequently R0 is rejected and K retained. The hypothetical positive continuation is absent from this rejection history.

18

Optimal Consistency for Interval Selection

Forcing a positive switch. Offer positive J = [0, 1) and write A = {J} ∪ A0 , of weight p. Suppose J is rejected. Offer positive T = [p, p + v) and put E = p + v. The only possible local holders are K and T , which conflict and each weigh v. For the short reserve, stop: T strictly pays R0 because v > z, and A pays K. The positive set tiles [0, E), is uniquely optimal, and has consistency excess
E − cv = 4(c − 2) − 2 ε > 0. For the long reserve, T alone does not pay R0 . Put χ = 2α − 1 > 0, ζ = χε/4 and h = (r − 1)v + ε. With b = E + αh − ζ, offer negative H = [b, b + h), a positive partition FH of [b + ζ, b + h − ζ) with tiles shorter than (v + h)/r − v, and then positive U = [E, E + αh). Here αh > 7α > d + 2ζ > z + 2ζ, so H is beyond all old requests. Historical {K, H} forces H to be retained while its tiles are missed. If U is retained, stop; otherwise H must remain, and we offer V1 = [b + h − ζ, b + 2h − ζ) and stop. Gains are at most v + αh and v + h, respectively. The second consistency excess, which is no larger than the first, is
E − cv − γh − 2ζ = 4(k − 2) − 2 − γ − χ/2 ε > 0, since its coefficient is at least 3χ/2 − 1/100 > 0. For full-history optimality, the negative families are subsets of {K, H} or {R0 , H}. The following payment groups have positive surplus: Negative family

Conflicting positive group

Surplus

K R0 H R0 , H

A T, U U, FH T, U, FH

p−v v + αh − z αh − 2ζ v + αh − z − 2ζ

The groups for K and H are disjoint, covering the remaining joint family. The shared U is counted only once for R0 , H. Adding V1 preserves all certificates. Thus both terminals are unique-perfect. In either reserve construction, J must be accepted and retained alone. Forcing rejection of the interior and left negatives. Offer negative I = [ε, ε + t), disjoint from K, R0 and conflicting with J. If accepted, apply Lemma C.1 with positives A, held bound a = t, local negatives {K, I}, boundary reserve R0 and historical witness I. The positive J strictly pays I because t < 1, and A pays K and {K, I} because p − v − t > 0. Take h = (r − 1)t + ε and ζ = ε/4. In the short case αh > (3/5)5(4/5) = 12/5 > z + 2ζ; in the long case αh > (3/5)7(4/5) = 84/25 > z + 2ζ. The anchor therefore lies beyond all old endpoints, and the deficit is p − ct − γh − 2ζ = (k − γ − 1/2)ε > 0. The lemma rules out acceptance of I. Now offer negative L = [s, ε), touching I, disjoint from K, R0 , and conflicting with J. If accepted, set η = ε/4, offer a positive partition of [s + η, 0) with tiles shorter than ℓ/r, and then positive B = [s + η − ℓ, s + η). Historical L forces the tiles to be missed. Their union with B is a feasible positive family Z of weight 2ℓ − ε − η > ℓ, all conflicting with L. Every response to B leaves gain at most ℓ. Apply the lemma with positives A ∪ Z, a = ℓ, local negatives {K, I, L}, boundary reserve R0 and witness L. For {I}, the conflicting group is Γ(I) = {J} and w(J) = 1 > t. For {K} and {K, I}, A pays with surplus at least p − v − t > 0. The disjoint group Z pays L. Combining these certificates covers {I, L} and every other nonempty subset of the three compatible local negatives without double counting. Take h = (r − 1)ℓ + ε,

ζ = ε/4.

Since ℓ > 2, the geometric requirements are stronger than those just checked for I. The deficit is p + 2ℓ − ε − η − cℓ − γh − 2ζ = (9/4 − γ)ε > 0. The lemma rules out acceptance of L, including the joint R0 , H payment without reusing a boundary positive. 19

(C.7)

Optimal Consistency for Interval Selection

a

b ε

ε

ε

K (p = 0)

Retain K; miss tiles Strict robustness

0 (p = 1) R0 (p = 0)

Reject right reserve Otherwise: perfect completion

J (p = 1) I (p = 0)

Accept positive J Otherwise: remote reserve repair

L (p = 0) L → φ3

I→1

0 → φ

R0 → φ 2

Compatible packing: lengths as ε ↓ 0 Total → 4φ + 3; finite witness has weight > 9.4

Reject interior I and left L Otherwise: bounded remote completion

Algorithm retains only J: ALG = 1

Figure 3. Surviving branch with a long right reserve, at γ = 0, r = 9.4 and ε = 1/20000. Endpoint gaps are exaggerated: the schematic is not to scale, and hatching marks positive-length overlaps. Positive tiles arrive before the reserve. The forced responses retain K, reject R0 , switch to J, and reject I, L. The actual packing L, I, A0 , R0 approaches 4φ + 3, while the algorithm retains value one. If J is rejected, the additional positive T and remote completion pay the entire longer reserve; this branch is separate from the displayed history. Packing labels give the limiting lengths as ε ↓ 0, not the finite instance’s exact lengths.

The actual robustness terminal. Stop after L is rejected. The algorithm holds only J, of value one. The actual requests L, I, A0 , R0 form a compatible packing of weight ℓ + t + (p − 1) + z = Fj (γ, r) − Ξj ε > r. This packing is uniquely optimal. Without K, choosing L, I beats J and permits every member of A0 and R0 ; a packing containing K has weight at most ℓ + t + v, which is smaller because (p − 1) + z > v. This violates robustness. All partitions are finite; each branch retains its original labels and complete negative history. Voluntary deletion either reduces the displayed gain or violates robustness at an earlier prefix. Determinism fixes which finite branch is taken. C.3. Consequences for the consistency infimum For j ∈ {s, l} put γs = 1/20, γl = 1/100, and define   B ≤ Dj (γj ), d + γj , Hj (B) = d + Dj−1 (B), Dj (γj ) < B < Dj (0),   d, B ≥ Dj (0). Taking parameters approaching equality from below in the theorem gives C ∗ (B) ≥ max{d, G(B), H(B)},

H(B) = max{Hs (B), Hl (B)}.

The G term is used on its domain B ≥ M . Since Dl is continuous at zero, every B < β has C ∗ (B) > d. An explicit weaker version follows by fixing r = β and writing Fl (γ, β) = 2V + V 2 + V /q + 1/k + V /k,

20

V = (d + γβ − 2)−1 ,

q = d + γ − 2.

(C.8)

Optimal Consistency for Interval Selection

Every term is a positive product of reciprocals of increasing affine functions. Its negative derivative is nonincreasing, and at zero their sum is −∂γ Fl (0, β) = β(7φ + 8) + φ3 = 83φ + 53. As Dl (γ) ≤ β, Dl (γ) ≥ Fl (γ, β) ≥ β − (83φ + 53)γ. Thus, by taking smaller parameters and then their supremum,   1 β−B ∗ C (B) ≥ d + min , >d (B < β). 100 83φ + 53 The short-reserve curve remains useful farther from d (Section 3). Its corresponding explicit bound Ds (γ) ≥ 2φ3 − (32φ + 20)γ follows by the same derivative argument, and is retained by (C.8). At γ = 0 the long construction permits v → φ, z → φ2 , t → 1 and ℓ → φ3 . The larger reserve is possible because a separate completion pays it when J is rejected. These four parameter inequalities give the limiting value β. Further improvement requires additional compatible missed mass on the continuing history or different forcing decisions. A larger counterfactual completion cannot itself supply that mass.

D. Source measures and shaped replacement costs Write α = 1/φ, d = φ2 , and M = φ3 . We prove a common capacity theorem for a ∈ [α, 1]; a = α recovers the interface used by Shaped-BANK, SUM-BANK, and Credit-BANK. Set βa = a−1 ,

Ca = (1 + a)2 ,

q0,a = 1 + βa ,

Q a = 1 + a + βa ,

ma = max{(1 + a)/a , Qa }, ka = ama = max{1 + βa , 1 + a + a2 }, a ma + 1 θa = , h0,a = , h1,a = 1 + βa h0,a . 1+a ma − β a 2

(D.1)

These constants are fixed for an entire execution. The ordinary gate adds the actual costs of all current conflicts and has priority. The special gate accepts a positive arrival only if every conflict is negative and w ≥ aW , w ≥ abD . The simultaneous fees are those in (8), with α replaced by a and the ledger-test condition replaced by w < abD . Full inheritance and equality acceptance are unchanged. D.1. A common consistency interface Theorem D.1 (Parametric feasible-positive capacity). Let the fixed finite nonnegative ordinary costs satisfy q+ (v, b) ≥ ma v

(v > 0, b ≥ 0),

q− (v, b) ≥ q0,a v

(v > 0, b ≥ 0),

(D.2)

q− (v, b) ≥ max{q0,a v, v/a + b/(1 + a)}

(v > 0, 0 ≤ b ≤ Ca v).

(D.3)

For every finite execution whose complete positive set P is feasible, each negative held identity satisfies b(J) ≤ Ca w(J) and each positive one satisfies b(J) ≤ ka w(J) throughout its lifetime. Consequently w(P ) ≤ Ca ALG. The complete set includes future positive requests and previously rejected or revoked identities. The theorem assumes no monotonicity or upper bound on the costs; the robustness proof imposes these on the capped cost. Event times and conserved sources. Fix one finite execution with arrivals numbered 1, . . . , N and feasible complete positive set P . Write Sn for the held identities immediately after arrival n. An accepted identity X has birth index νX and first revocation index δX ; set δX = N + 1 if it survives. Its live snapshots are precisely νX ≤ n < δX . A rejection fee at arrival n uses the old state Sn−1 ; an accepted parent’s inherited ledger uses this same state, before adding its own positive source. For an arrived positive source T , let aX,n (T ) be its conserved coefficient in the ledger of held identity X. Acceptance merges coefficients and adds a unit coefficient for a positive arrival; rejection distributes a unit coefficient by its fees. Thus X X aX,n (T ) = 1, bn (X) = aX,n (T )w(T ). aX,n (T ) ≥ 0, T ∈P

X∈Sn

21

Optimal Consistency for Interval Selection

The unit-sum identity is for sources arriving by n; coefficients of future sources are zero. Define X µX,n (E) = aX,n (T )|T ∩ E|.

(D.4)

T ∈P

Compatibility of the sources and coefficients at most one imply that this measure has density at most one. For X = [x, x+v) put EL,n (X) = µX,n ((−∞, x)) and ER,n (X) = µX,n ([x + v, ∞)). For a cut s, the whole-source mass is X aX,n (T )w(T ). Ln,X (s) = T ∈P : f (T )≤s

It counts complete shares of sources ending by s, whereas the measure of (−∞, s) may include a partial share of a source crossing s. In particular, the former is at most the latter. A subscript 0 below denotes the birth snapshot νX ; omitted time subscripts refer to the single live snapshot being considered. Every left-side assertion also has its reflected right-side form. Exterior mass and one-event fees. Internal mass is at most the holder’s length. A fixed endpoint is crossed by at most one positive source; only a post-birth source crossing that endpoint can increase exterior mass on that side. Feasibility excludes positive held conflicts of a positive arrival. A negative receiver of length v receives g < av when the special length test fails, or g ≤ abpre when the ledger test fails. The latter gives g ≤ θa (bpre + g).

(D.5)

The exterior contribution is bounded both by its fee and by the length of the source’s exterior segment. Geometry independent of capacity. Let ac ∈ (α, 1) solve a3c + a2c = 1. Directly from (D.1), ma ka h0,a h1,a

a ≤ ac (1 + a)/a2 1 + βa 1 + a + a2 2 + a + βa

a ≥ ac Qa 1 + a + a2 1 + βa 1 + βa + βa2

The branches agree at ac . Throughout the range, 1 + βa ≤ ka ≤ Ca , ma ≥ Qa > q0,a ≥ 2, h0,a ≥ 1 + a, h1,a h0,a βa 1+a = h0,a − 1, ≤ h0,a − 1, < 1, ≤ 1. ma q0,a ma a2 ma

(D.6)

For ka ≤ Ca , the first branch is equivalent to a3 + 2a2 − 1 ≥ 0, which vanishes at α and increases thereafter; the other branch has slack a. Let H(X) be the sum of lengths of all accepted identities in the replacement subtree rooted at X. For arbitrary labels, H(X) ≤ h0,a w(X)

H(X) ≤ h1,a w(X)

at an ordinary birth,

at a special birth.

(D.7)

Indeed each child’s history divided by its actual cost is at most max{h0,a /q0,a , h1,a /ma } = h0,a − 1. An ordinary parent pays the sum of child costs, at most its own length; a special parent has only negative children, of total length at most βa times its own. These recurrences prove (D.7) from empty births, without a ledger-capacity assumption. Negative nodes are always ordinary; an ordinary positive also satisfies the larger h1,a bound. The accepted union is connected, and a negative subtree protrudes beyond either root endpoint by at most (h0,a − 1) times the root length. Negative-to-negative downward edges shrink length by at least q0,a ; a positive child of a negative node costs at least ma times its length. An edge from a positive parent to a negative child expands by at most βa . Thus successive positive nodes on a downward path have length ratio at most βa /ma < 1. Before the first node starting below a fixed cut, a negative tail from length v displaces by less than v/(q0,a − 1) = av. A tail from a positive root of length u, with only negative intermediate nodes, displaces by less than βa q0,a u/(q0,a − 1) = (1 + a)u/a. Each nonzero source has an accepted entry support overlapping it. At the golden endpoint these estimates also give the original accepted-history bounds H(X) ≤ 2w(X) (p(X) = 0),

H(X) ≤ M w(X) (p(X) = 1),

H(X) ≤ τ (X) (a = α),

where τ (X) is the actual ordinary cost; 2 ≤ d and the positive cost lower bound is M . 22

(D.8)

Optimal Consistency for Interval Selection

The birth-order induction. The induction order is the arrival index of accepted identities. Each identity’s claim covers all its live snapshots, including the last snapshot before a later parent’s birth. For a negative V of length v, prove capacity bn (V ) ≤ Ca v and EL,νV (V ), ER,νV (V ) ≤ av,

(D.9)

EL,n (V ), ER,n (V ) ≤ max{av, θa bn (V )},

(D.10)

LνV ,V (s) + z − s ≤ av

(D.11)

if s < z ≤ t, z ≤ s(V ), LνV ,V (s) > 0.

In the last assertion T0 = [s, t) ranges over actual positive requests arriving after νV . It need not overlap V . For a positive Q of length u, prove capacity bn (Q) ≤ ka u and Ln,Q (s) + z − s ≤ ka u

if s < z ≤ t ≤ s(Q), Ln,Q (s) > 0,

(D.12)

where T0 = [s, t) is an actual positive request arriving after the live snapshot n. Positive ledgers are constant during a lifetime. All cut assertions include their reflections, counting full shares of sources starting beyond the right cut. Earlier capacities and cuts first establish a new negative node’s birth bounds. Its birth bounds and subsequent one-event fees then establish its entire-lifetime bounds. A positive node uses earlier negative assertions and the independent geometry. In particular, a new node’s capacity is never used to establish its own birth cuts. Lemma D.1 (Weighted directional cut at a live snapshot). Let a negative X = [x, x + v) be live at snapshot n and satisfy its capacity, birth exterior, lifetime exterior, and birth-cut assertions. For an actual positive T0 = [s, t) arriving after n, if s < z ≤ t, z < f (X), and Ln,X (s) > 0, then Ln,X (s) + z − s ≤ aq− (v, bn (X)).

(D.13)

The reflected assertion holds. No later parent’s capacity or cut is an assumption. Proof. At this snapshot the cost hypothesis gives v + max{av, θa b} ≤ aq− (v, b).

(D.14)

If x < s, density gives LX (s) ≤ EL (X) + s − x; adding z − s leaves a quantity smaller than EL (X) + v, paid by the lifetime bound and (D.14). If x ≥ s, a source ending by s cannot newly overlap X during its lifetime, so LX (s) = L0,X (s). Set z0 = min{z, x}. For z0 > s use the birth cut; for z0 = s necessarily x = s, and use the birth exterior bound. Thus LX (s) + z0 − s ≤ av. The remaining distance is zero or less than v, giving (1 + a)v = aq0,a v ≤ aq− (v, b). Lemma D.2 (Negative birth bounds). Assume the full induction assertions for every earlier accepted identity at all its live snapshots. A new negative identity satisfies the birth exterior bounds and birth cuts above. Proof. Let the ordinary parent be V of length ℓ. Its children have old-state costs summing to at most ℓ. A negative child X = [x, x + v) contributes mass to the left of s(V ) at most EL (X) + max{s(V ) − x, 0} ≤ EL (X) + v ≤ aq− (v, b(X)). A positive child’s entire ledger is at most ka v = ama v ≤ aq+ (v, b). Sum to obtain the left birth exterior bound, and reflect for the right. For the left birth cut, every child with a nonzero left share overlaps V and ends strictly beyond z. A negative child obeys Lemma D.1. A positive child is compatible with T0 and overlaps V to its right, forcing its start at least t; its earlier positive cut pays its share and the gap with ka w(X) ≤ aτ (X).PSum over all children with nonzero shares. There is at least one, so the gap is paid at least once and L0,V (s) + z − s ≤ a X τ (X) ≤ aℓ. Zero-share children need no whole-ledger estimate. Reflection and empty births finish the proof. Lemma D.3 (Negative lifetime and capacity). The negative birth assertions and the subsequent rejection fees imply the lifetime exterior bounds and bn (V ) ≤ Ca w(V ) at every live snapshot, without assuming this capacity in advance. Proof. Write V = [x, x + ℓ). A side with positive exterior mass at birth stays bounded by aℓ. A birth source crossing that endpoint excludes any later positive crosser. Otherwise all birth sources contributing to that side lie wholly beyond the endpoint. If a later source T = [s, t) crosses the left endpoint, those sources end by s, so EL,0 (V ) = L0,V (s). The birth 23

Optimal Consistency for Interval Selection

cut bounds EL,0 (V ) + x − s ≤ aℓ, and the new exterior contribution is at most x − s. No second boundary source can cross that side. Reflect for the right. A side with zero birth exterior receives exterior mass only from its unique later boundary source. Its fee is bounded by aℓ after length failure, or by θa b(V ) after ledger failure, using (D.5). Ledger monotonicity preserves this bound thereafter. This proves the lifetime exterior assertion. For capacity, two birth-nonzero sides give b ≤ (1 + 2a)ℓ ≤ Ca ℓ by density. With exactly one such side, before a first boundary on the other side bpre ≤ (1 + a)ℓ, hence its fee is at most a(1 + a)ℓ. Subsequently b ≤ ℓ + aℓ + a(1 + a)ℓ = Ca ℓ. With neither side nonzero at birth, the first boundary has bpre ≤ ℓ and fee at most aℓ. One side is then protected from any later crosser, and the preceding argument applies to the other side. If that first source crosses both endpoints, no later boundary source is possible; with no boundary, density suffices. These are event-time fee bounds. Lemma D.4 (Positive birth and cut). Assume the full induction assertions for every earlier identity. A positive accepted Q satisfies capacity bn (Q) ≤ ka w(Q) and the positive cuts throughout its live snapshots. Proof. Let u = w(Q) and evaluate all child quantities immediately before its birth. All children are negative. Ordinary acceptance gives WQ ≤ u/q0,a and BQ ≤ Ca WQ ≤ a(1 + a)u; special acceptance gives BQ , WQ ≤ βa u. Thus b(Q) = u + BQ ≤ ka u. No later positive request overlaps Q, so its ledger and shares remain constant. Fix a live snapshot and an actual later positive T0 = [s, t) with s < z ≤ t ≤ s(Q) and LP Q (s) > 0. Set e = z − s and G = s(Q) − s, so e ≤ G. The source Q is not counted in LQ (s), which therefore equals X LX (s) ≤ BQ . Trace one nonzero share of a source ending by s down the replacement tree to its accepted entry support. Whether the source was accepted or rejected there, that support overlaps it and starts strictly below s. Stop at the first such start. Every positive node before this crossing starts at least at t, by compatibility with T0 . Case 1: a positive node occurs strictly below Q before the crossing. Let H be the last one. The independent path estimates give w(H) ≤ βa u/ma . Its subsequent tail has only negative intermediate nodes, hence e ≤ s(H) − s <

1+a 1+a w(H) ≤ 2 u ≤ u. a a ma

This also permits a positive crossing node, whose cost is at least q0,a times its length. Thus LQ (s) + e ≤ BQ + u ≤ ka u. Case 2: no such positive node occurs, and either Q is ordinary or more than one child is relevant. Let V be the first child on the selected path and v = w(V ). The negative-tail displacement gives s(V ) − s < av if s(V ) ≥ s; if s(V ) < s the inequality is immediate. Since V overlaps Q, G < (1 + a)v. For ordinary Q, v ≤ u/q0,a yields e < au, and BQ + e < (a2 + 2a)u ≤ (1 + a + a2 )u ≤ ka u, where a ≤ 1. For special Q, if V is not leftmost, a compatible child to its left ends after s(Q); then s(V ) > s(Q) and G < av ≤ u. If V is leftmost but another child K has LK (s) > 0, that child starts to the right of s(Q). Its entry support lies below s, so the independent protrusion bound gives G < (h0,a − 1)w(K). Now ( βa , a ≤ ac , 1 1 + = −1 1 + a h0,a − 1 (1 + a) + a ≥ βa , a ≥ ac , with the last inequality equivalent to a3 + a2 ≥ 1. Consequently βa G < v + w(K) ≤ WQ ≤ βa u. In either special subcase, e ≤ G < u and BQ + e < (1 + βa )u ≤ ka u. Case 3: Q is special and only its leftmost child V carries a left share. Then LQ (s) = LV (s) and z ≤ t ≤ s(Q) < f (V ). If s(V ) ≥ s, no source ending by s can charge V after birth, so LV (s) = L0,V (s). Put z0 = min{z, s(V )}. For z0 > s, use the earlier birth cut. For z0 = s, necessarily s(V ) = s, and use L0,V (s) ≤ EL,0 (V ) ≤ av instead. Thus LV (s) + z0 − s ≤ av, while 0 ≤ z − z0 < v, giving LQ (s) + e < (1 + a)v ≤ (1 + βa )u ≤ ka u. If s(V ) < s, density and the earlier lifetime exterior bound give LQ (s) + e < v + EL (V ) ≤ max{(1 + a)v, v + θa b(V )} ≤ max{1 + βa , βa + (1 + a)−1 }u = (1 + βa )u ≤ ka u. 24

Optimal Consistency for Interval Selection

The last inequality uses the two separate special budgets v ≤ WQ ≤ βa u and b(V ) ≤ BQ ≤ βa u. These three cases exhaust the path and child-share alternatives. Reflection proves the right cut. Completion of Theorem D.1. A new negative identity obtains its birth assertions from earlier children, then its lifetime assertions from its own actual fees. Its weighted cut is used only for later births. A new positive identity uses earlier negative P assertions and independent geometry. This closes the birth induction. Source conservation and ka ≤ Ca give P w(P ) = X b(X) ≤ Ca X w(X). Theorem D.2 (Golden endpoint interface). For the special tests and fees at a = α, suppose q+ (v, b) ≥ M v and q− (v, b) ≥ dv

(v > 0, b ≥ 0),

(D.15)

q− (v, b) ≥ max{dv, φv + αb}

(v > 0, 0 ≤ b ≤ dv).

(D.16)

For every feasible complete positive set, each held identity satisfies b(J) ≤ dw(J) throughout its lifetime and w(P ) ≤ d ALG. Proof. This is the a = α specialization of Theorem D.1: Ca = ka = q0,a = d, ma = M , and v/a + b/(1 + a) = φv + αb. D.2. The capped family and exact consistency Define Ta by the preceding a-special tests and fees, positive cost ma v, and negative cost qa (v, b) = min{Qa v, max{q0,a v, v/a + b/(1 + a)}}.

(D.17)

Its filtered form is TaF . The cost is q0,a v up to b = (1 + a)v, then linear up to b = Ca v, and then equal to Qa v. The cap is inactive on the capacity range, so Theorem D.1 gives consistency at most Ca . Proposition D.1 (Exact consistency of the family). For every a ∈ [α, 1], both Ta and TaF have C(Ta ) = C(TaF ) = (1 + a)2 . Proof. Choose 0 < ϵ < min{1/100, a2 /[4(3a + 1)]} and offer J H1 H2 L R

0 1 1 1 1

[0, 1), [ϵ, 1/2), [1/2, 1 − ϵ), [2ϵ − a, ϵ), [1 − ϵ, 1 − ϵ + z),

z = a(1 + a − 3ϵ) − ϵ.

The two seeds and L are shorter than a and fail ordinary acceptance, since the negative cost is at least q0,a ≥ 2. They fail the special length test and leave ledger bJ = 1 + a − 3ϵ. This is below the first breakpoint, so qa (1, bJ ) = q0,a . The final request has z > a but z = abJ − ϵ, hence passes the length test and fails the ledger test. It also fails ordinary acceptance because z < a + a2 ≤ 1 + 1/a = q0,a , where the last inequality is (a − 1)(a + 1)2 ≤ 0 after multiplication by a. Thus ALG = 1. The positives are consecutive in spatial order L, H1 , H2 , R. Their union contains the anchor and every offered request; they therefore form an optimum of weight (1 + a)2 − (3a + 4)ϵ. Any feasible set containing the anchor contains none of these positives, so this optimum is unique. Letting ϵ decrease to zero proves the lower bound. The capacity theorem proves the upper bound. Filtering leaves these perfect labels unchanged and inherits the upper bound. At a = α, the family recovers Shaped-BANK T∗ with   dv, q∗ (v, b) = min{2φv, max{dv, φv + αb}} = φv + αb,   2φv, 25

b ≤ φv, φv ≤ b ≤ dv, b ≥ dv.

(D.18)

Optimal Consistency for Interval Selection

Proposition D.2 (Smallest monotone sufficient cost). Among costs satisfying the interface of Theorem 5 and nondecreasing in b for fixed v, q∗ is pointwise smallest. Proof. For b ≤ dv, the two interface inequalities require q(v, b) ≥ max{dv, φv + αb}, exactly q∗ on this range. At b = dv this value is 2φv, so monotonicity requires at least 2φv for larger b. The cost q∗ meets all requirements. The branches of (D.18) agree at both boundaries. Minimality is relative to this sufficient interface, which is not necessary (Appendix E.1). D.3. Joint-cut robustness of the family The following common transfer lemma is also used in Appendices H and J. Lemma D.5 (Comparator-to-root transfer). Consider a finite execution on positive-length intervals, starting from an empty held set. Acceptance revokes precisely the current conflicts and retains all nonconflicts; rejection leaves the held set unchanged, and there are no other revocations. Give each accepted identity V a weight ωV ≥ w(V ). Suppose every rejected I has a nonempty current conflict set D(I) and pieces zI,V satisfying X 0 ≤ zI,V ≤ ωV (V ∈ D(I)), zI,V = w(I). V ∈D(I)

Link each revoked identity to its replacement. In this forest, let HJ be the closure of the union in J’s subtree, including J. An ancestry antichain contains no node and its strict ancestor; let ΩJ be its maximum weight in this subtree. Let LJ (x) and UJ (y) be the same maximum restricted respectively to starts below x and finishes above y, both strictly; empty antichains are allowed. Set FJ (x, y) = |HJ ∩ [x, y]| + LJ (x) + UJ (y). If each final root satisfies ΩJ ≤ Kw(J),

FJ (x, y) ≤ Kw(J)

for all real x ≤ y,

then every feasible subset O of the input requests satisfies w(O) ≤ KALG. Proof. An accepted member of O charges its length to its own identity; a rejected member uses the stipulated pieces. Pass each piece to its receiver’s final root. Its charge there is at most its own length and is positive only if it intersects that root’s hull in positive length. Each hull is connected along replacement edges. Fix HJ = [A, B]. If one comparator covers its whole interior, allowing endpoint equality, it is the sole positive-charge contributor. Its receivers form an ancestry antichain: they were simultaneously held, or consist of its own accepted identity. Thus its charge is at most ΩJ . Otherwise feasibility permits at most one comparator strictly crossing each hull endpoint. Let x be the left crosser’s finish (or A if absent), and y the right crosser’s start (or B). Then A ≤ x ≤ y ≤ B. The left crosser’s receivers form an ancestry antichain with starts below x, giving charge at most LJ (x); the right side gives UJ (y). An absent side has zero maximum at its hull endpoint. All remaining contributors are contained in [x, y], and their disjoint lengths bound their total charge by |HJ ∩ [x, y]|. The root charge is therefore at most FJ (x, y). Summing over roots preserves every initial piece, even when their hulls overlap, and proves the claim. Cost shape and terminal budgets. Let ca =

a , (1 + a)2

Aa = βa + βa2 + (1 + a)−2 ,

ρa = max{1, Aa /ma }.

(D.19)

The three branches of (D.17) give q0,a v ≤ qa (v, b) ≤ Qa v ≤ ma v, qa (v, b) ≤ q0,a v + ca b, qa (W, B) − qa (v, B) ≥ βa (W − v)

(D.20) (0 ≤ v ≤ W ).

(D.21)

For the affine majorant the middle-branch slack is v − b/Ca ≥ 0; the cap branch uses b ≥ Ca v and ca Ca = a = Qa − q0,a . For fixed B, the successive slopes in v are Qa , βa , q0,a ; the branches are continuous and qa (0, B) = 0. The cost is nondecreasing in both variables. 26

Optimal Consistency for Interval Selection

Give each accepted identity X its ordinary cost qX at the last live snapshot, immediately before P revocation or at termination. These costs are nondecreasing during each lifetime. An ordinary parent of length h has i qi ≤ h. A special parent has only negative children and X W, B ≤ βa h, qi ≤ q0,a W + ca B ≤ Aa h. (D.22) i

Since ma ≥ q0,a βa , ca ≤ 1/4, and q0,a ≥ 2, ρa ≤ 1 + ca /q0,a ≤ 9/8 < q0,a ,

ρa − 1 < β a .

An ancestry antichain has total weight at most qJ in an ordinary-root subtree and P at most max{ma , Aa }w(J) = ρa ma w(J) in a special-root subtree. Indeed, omitting an ordinary root gives at most ρa i qi ≤ ρa h < qJ . A special root’s negative children are ordinary and their weights sum to at most Aa h; the singleton costs ma h. This simultaneous induction uses no feasible-positive capacity. It also shows that an eligible ordinary root attains its endpoint maximum, while an ineligible side has weight at most ρa h. Theorem D.3 (Parametric robustness certificate). Let Ka be the maximum of the general coefficients in Table 2. For every finite arbitrarily labelled input, both Ta and TaF satisfy OPT ≤ Ka ALG. In fact, Oa = ma + 1 + 2βa + βa2 ,

Na = h1,a + Aa + ρa βa ,

Ka = max{Oa , Na }.

(D.23)

The map a 7→ Ka is continuous on [α, 1]. Proof. Use Lemma D.5 with terminal cost weights ωX = qX . The independent history bounds give hull length at most h0,a h at an ordinary root and h1,a h at a special root. For x ≤ y, write FJ (x, y) = |HJ ∩ [x, y]| + LJ (x) + UJ (y) as in that lemma. The two endpoint maxima need not coexist. An antichain either contains the root singleton or omits it and decomposes over child subtrees. Thus ( ) X LJ (x) = max qJ 1{s(J)<x} , LCi (x) , i

with the analogous right recurrence. A zero or ineligible root term is assigned to the child choice. Ties of positive eligible values can use either attaining choice. There is no mixed root and descendant choice, since they are comparable in ancestry. The descendants of an antichain need not be spatially compatible; only immediate children are known to have been held together. At an ordinary root, two eligible endpoints put the gap in the root and give 1 + 2ma . One eligible endpoint gives h0,a + ma + ρa , and none gives h0,a + 2ρa , using the full hull. At a special root J = [l, r), the two endpoints choose exactly two, one, or zero singletons. Two singletons give 1 + 2ma . For exactly one singleton, reflect to put it on the left, so l < x. If y < r, the gap lies in J and the coefficient is 1 + ma + Aa . Otherwise r ≤ y. Every child starts strictly before r; compatibility permits at most one child V ending beyond y. If this outward child exists, the gap is contained in J ∪ V , of length at most h + v. Its right maximum is qV , while all other child roots are right-ineligible. Hence FJ ≤ (ma + 1)h + (1 − ρa )v + qa (v, bV ) + ρa W ≤ (ma + 1)h + (1 − ρa )v + qa (v, B) + ρa W ≤ (ma + 1)h + W + qa (W, B) ≤ (ma + 1 + βa + q0,a βa )h.

(D.24)

The third line follows from the fixed-ledger slope βa > ρa − 1; the last uses monotonicity, both special budgets, and qa (βa h, βa h) = q0,a βa h. If there is no outward child, all child roots are right-ineligible. The full hull then gives h1,a + m a + ρa β a . If both endpoint choices use children, call a child V a bridge when s(V ) < x ≤ y < f (V ). There is at most one compatible bridge, including at x = y. Its gap and endpoint weights contribute at most v + 2qV . Every other child has 27

Optimal Consistency for Interval Selection Table 2. Complete joint-cut case list. The special root is [l, r) and mixed choices are oriented with the singleton on the left. Ka is the maximum of the general coefficients, with the repeated 1 + 2ma counted once. The endpoint column preserves the specialized Shaped-BANK calculation; the largest entry there is 5φ + 3. Root and endpoint choices

General coefficient

At a = α

Ordinary: two eligible Ordinary: one eligible Ordinary: none eligible

1 + 2ma h0,a + ma + ρa h0,a + 2ρa

4φ + 3 7φ − 4 10φ − 12

Special: two singletons 1 + 2ma 4φ + 3 Special: one, y < r 1 + ma + A a 3φ + 5 Special: one, outward child ma + 1 + βa + q0,a βa 5φ + 3 Special: one, no outward child h1,a + ma + ρa βa 2φ + 7 Special: children, bridge βa + 2Aa 3φ + 6 Special: children, no bridge h1,a + Aa + ρa βa φ+9

at most one eligible endpoint, so its endpoint sum is at most qi + ρa vi ; this also covers two ineligible endpoints since qi ≥ q0,a vi ≥ ρa vi . Consequently X X FJ ≤ v + 2qV + (qi + ρa vi ) ≤ W + 2 qi ≤ (βa + 2Aa )h, i

i̸=V

where the middle inequality uses (ρa − 1)vi ≤ qi . With no bridge, use the full hull and all endpoint sums to obtain h1,a + Aa + ρa βa . These cases exhaust the table: root versus children at each endpoint, the unique outward child in the mixed case, and the presence or absence of a bridge in the child-only case. Strict eligibility assigns endpoint equality to ineligibility. The full antichain bound max{ma , Aa }h is at most (1 + ma + Aa )h ≤ KP a h. A rejected request I has a nonempty conflict set and fails ordinary acceptance, so assign analytical pieces w(I)τ (X)/ D τ to its current conflicts. They sum to w(I) and are each below its receiver’s current cost, hence below qX . All weights exceed the corresponding interval lengths. These analytical pieces are not ledger fees. Every hypothesis of Lemma D.5 is now verified, giving the robustness bound. The filter produces another causal labelled execution and is covered by the same bound. It remains to reduce the table to (D.23). Put ea = (1 + a)−2 and m0,a = βa + βa2 , so Aa = m0,a + ea and ma ≥ m0,a . The branch formulas give h0,a ≤ 1 + βa ; also ea ≤ α2 < 1/2 and 1 ≤ ρa ≤ 9/8 < ma . The gap Oa − (1 + 2ma ) is βa for a ≤ ac and βa + βa2 − 1 − a ≥ 0 for a ≥ ac . Further, Oa − (h0,a + ma + ρa ) ≥ βa + βa2 − ρa ≥ 7/8, Oa − (1 + ma + Aa ) = βa − ea > 0, Oa − (βa + 2Aa ) = ma − m0,a + 1 − 2ea > 0. The ordinary no-endpoint row is smaller than its one-endpoint row. The no-outward row h1,a + ma + ρa βa is at most Na when Aa ≥ ma . Otherwise a > ac , since Aa = ma + ea on the first branch; then h1,a = 1 + βa + βa2 and ρa = 1, making this row equal to Oa . Since both Oa , Na occur in the table, the reduction follows. Continuity follows from the defining functions and maxima. The golden robustness endpoint. At a = α, ca = α3 , h0,a = 2, h1,a = ma = M , Aa = φ + 3, and ρa = Aa /M . The cost identities specialize to dv ≤ q∗ (v, b) ≤ 2φv < M v, q∗ (v, b) ≤ dv + α3 b, (D.25) q∗ (W, B) − q∗ (v, B) ≥ φ(W − v), and the special terminal budgets become W, B ≤ φh,

X

qi ≤ dW + α3 B ≤ (φ + 3)h.

(D.26)

(D.27)

i

In particular, the critical outward case is FJ ≤ (M + 1)h + W + q∗ (W, B) ≤ (M + 1 + φ)h + q∗ (φh, φh) = (5φ + 3)h. 28

(D.28)

Optimal Consistency for Interval Selection

All other endpoint coefficients in the table are smaller: their positive slacks follow directly from 3/2 < φ < 2. This gives K α = φ5 . Theorem D.4 (Exact shaped-cost guarantees). Both T∗ and T∗F have consistency d and exact strict robustness φ5 = 5φ+3. Proof. The capacity theorem and Proposition D.1 give exact consistency. The specialized joint-cut calculation gives the robustness upper bound; Proposition D.5 below supplies the matching family. Proposition D.3 (A matching outward family). For every a ∈ [α, 1], raw and filtered Ta satisfy R ≥ Oa . At a = 1 the exact pair is (C, R) = (4, 7). Proof. For 0 < ϵ < 1/10 offer K I R J L

0 [1 − ϵ, 1 + βa − ϵ), 0 [ϵ, 1 + βa − 2ϵ), 0 [1 + βa − 2ϵ, 1 + βa − 2ϵ + q0,a βa − ϵ), 1 [0, 1), 0 [2ϵ − ma , ϵ).

The anchor K has length βa , zero ledger, and cost q0,a βa . Both I and R reject; their lengths are q0,a − 3ϵ < q0,a βa and q0,a βa − ϵ. The unit positive J fails ordinary acceptance and passes the special length test at equality with zero ledger. After it replaces K, the final negative L rejects at length ma − ϵ < ma . Thus ALG = 1, while the compatible L, I, R tile the entire offered hull and give OPT = ma + 1 + βa + q0,a βa − 5ϵ. There is only one positive, so filtering changes nothing. Let ϵ decrease to zero. At a = 1 the constants are q0,a = 2, ma = Qa = 3, Aa = 9/4, ρa = 1, h0,a = 2, h1,a = 3; the table’s maximum is 7, matching this lower bound, and the exact consistency proposition gives 4. Proposition D.4 (Exact robustness on two parameter intervals). Let a− ∈ (α, ac ) and a+ ∈ (ac , 1) be the unique zeros in these respective intervals of p− (x) = 1 + 3x + x2 − 5x3 − 6x4 − 4x5 − x6 ,

(D.29)

p+ (x) = 1 + 2x + x − 3x − 3x − x . 2

For both Ta and TaF , the exact robustness is R=

(

3

4

5

1 + 3/a + 2/a2 , α ≤ a ≤ a− , a + 2 + 3/a + 1/a2 , a+ ≤ a ≤ 1.

On (a− , a+ ), the bounds are Oa ≤ R ≤ Na with Oa < Na . In particular, a = 2/3 gives the exact pair (C, R) = (25/9, 10). Proof. On [α, ac ], substitution gives ∆a := Oa − Na =

1 1 + 2a −1−a− , 2 a (1 + a)3

a2 (1 + a)3 ∆a = p− (a).

√ Here d∆a /da = −2/a3 − 1 + (1 + 4a)/(1 + a)4 < 0, since the last fraction is below one. The signs ∆α = 2 5 − 4 > 0 and ∆ac = −(1 + 2ac )/(1 + ac )3 < 0 give the unique crossing a− . On [ac , 1], put ga := Aa − ma =

1 1 + − 1 − a, a2 (1 + a)2

a2 (1 + a)2 ga = p+ (a). Now dga /da = −2/a3 − 2/(1 + a)3 − 1 < 0, gac = (1 + ac )−2 > 0, and g1 = −3/4. Thus its unique zero is a+ , where ρa reaches one, and ( (ma − Aa )(1 + βa /ma ), ac ≤ a ≤ a+ , O a − Na = m a − Aa , a+ ≤ a ≤ 1. 29

Optimal Consistency for Interval Selection

The signs and Proposition D.3 prove the two exact intervals and the strict middle certificate gap; substituting the two branches of ma gives the displayed R. Finally, ∆2/3 = 119/1500 > 0 and 2/3 < ac , with O2/3 = 10. Proposition D.1 gives C = 25/9. Numerically, a− ≈ 0.677821, ac ≈ 0.754878, and a+ ≈ 0.813824. D.4. A matching family and the architectural limitation Proposition D.5 (A floor for fixed special rules). Fix a = α. Keep positive ordinary cost M v, the shared special tests, ordinary priority, fees, and ledger inheritance. If the negative cost is finite and satisfies q(v, 0) ≥ dv, the resulting raw and filtered policies have strict robustness at least φ5 . Proof. For 0 < ϵ < 1/100 offer the following five requests in order: K I R J L

0 0 0 1 0

[1 − ϵ, d − ϵ), [ϵ, d − 2ϵ), [d − 2ϵ, d − 2ϵ + M − ϵ), [0, 1), [2ϵ − M, ϵ).

K is accepted empty, has length φ, and carries zero ledger. Both I and R overlap it and have length below q(φ, 0) ≥ M , so they are rejected. The positive J fails ordinary acceptance, passes the special length test at equality and the zero-ledger test, and replaces K. Finally L overlaps J and has length M − ϵ < M , so it is rejected. Thus ALG = 1. The compatible intervals L, I, R tile the entire offered hull; all five requests lie in that hull. Therefore OPT = 2(M − ϵ) + (d − 3ϵ) = 5φ + 3 − 5ϵ. There is only one positive, so filtering changes nothing. Taking ϵ ↓ 0 proves the floor and the matching lower bound in Theorem D.4. With positive cost M v, these results make Shaped-BANK robustness-optimal within the sufficient-cost class of Theorem D.2. The zero-ledger relaxation and the nonshrinking-cost floor are analyzed next.

E. Cancellation penalties and replacement-cost limits The buyback objective subtracts a proportional payment for each revoked request from the value finally retained (Babaioff et al., 2009). For the unchanged Shaped-BANK policy, its accepted-history bound also controls this payment. The following result applies with or without the permanent-history filter and for arbitrary raw predictions. Proposition E.1 (Sharp cumulative revocation factor). Let T be the total length of accepted identities subsequently revoked, each counted once, and let N, P be the final lengths held with effective labels zero and one. Then T ≤ N + 2φP ≤ 2φ ALG. The supremum of T /ALG over finite nonempty inputs is 2φ, also for the filtered policy. Proof. The replacement forest partitions all accepted identities among the final held roots. Equation (D.8) bounds the accepted history of a negative root by twice its length and that of a positive root by M times its length. Subtracting the final roots gives T ≤ N + (M − 1)P = N + 2φP . For sharpness, put nk = dk and ak = α2 (dk − 1). For k = 0, . . . , K, present in order Nk = [0, nk ), p(Nk ) = 0,

Pk = [ak , ak+1 ), p(Pk ) = 1.

2 The positives are mutually compatible, have lengths αnk , and lie inside their respective PNk , since ak+1 = nk − α . Thus the permanent filter preserves their labels. Before Pk , the negative holder has ledger j<k αnj = ak ≤ nk . The special

30

Optimal Consistency for Interval Selection

length test accepts Pk at equality, and its ledger test passes. Then Nk+1 passes the positive holder’s ordinary test at equality, since nk+1 = M αnk . The final reward is αdK , and T =

K X

dk + α

k=0

K−1 X

dk = 2φ ALG − 1.

k=0

Taking K → ∞ proves the supremum. Charge c w(I) for revoking I, in the same units as retained length, and define ALGc = ALG − cT . Finite net robustness means a positive constant Rc satisfying OPT ≤ Rc ALGc on every input. An offline algorithm can select its final optimum without cancellations, so its net optimum is still OPT. For 0 ≤ c < 1/(2φ), Proposition E.1 gives ALGc ≥ (1 − 2φc)ALG,

Rc ≤

φ5 . 1 − 2φc

(E.1)

Under perfect membership predictions the corresponding sufficient consistency bound is d/(1 − 2φc). For arbitrary predictions with the permanent filter, Corollary K.1 instead gives   OPT OPT − ηK ALGc ≥ (1 − 2φc) max , . φ5 d These ratio bounds are sufficient. The fee range for finite robustness is exact for this unchanged algorithm. In the sharpness family all intervals lie in NK , itself an offered interval, so OPT = dK and ALGc = αdK (1 − 2φc) + c. At c = 1/(2φ) the net reward is constant while the optimum diverges; above that threshold it is eventually negative. This threshold concerns the unmodified policy; a monetary refund rate must first be converted to retained-duration units to give c. E.1. Which replacement-cost assumptions are necessary? The zero-ledger condition in the sufficient interface of Theorem D.2 is not necessary. What matters in that proof is the cost paid along paths that actually carry positive source mass. Theorem E.1 (Consistency after relaxing the zero-ledger cost). In the shared ledger policy, suppose positive costs are at least M v. For negative costs require q(v, b) ≥ dv

(b > 0),

q(v, b) ≥ φv + αb

(0 < b ≤ dv).

The value q(v, 0) may be any finite nonnegative number. For every finite execution with feasible complete positive set P , every held interval satisfies b(X) ≤ dw(X) and w(P ) ≤ d ALG. Proof. Use the source coefficients and birth-order induction of Theorem D.2. A zero-ledger child has zero coefficient for every positive source, so it contributes nothing to an inherited measure, exterior mass, or whole-source cut. It can be omitted from every such sum; the omitted ordinary costs are nonnegative. We justify the geometric estimates separately, since they need not hold for source-free accepted history. Follow any nonzero source share from its accepted entry support to its current holder. At each replacement edge on this path, the child has positive ledger immediately before revocation. A negative child therefore costs at least dv, and a positive child at least M v. The original edge contractions apply: an ordinary parent has a negative child of length at most 1/d times its own, or a positive child of length at most 1/M times its own; a special positive parent has negative children of total length at most φ times its own. Consecutive positive nodes on a source path contract by at least d. The negative-tail displacement bounds remain αv from a negative root and du from a positive root. Equivalently, retain the root and only replacement edges whose child had positive ledger at revocation. Every nonzero source has its entry support in this retained tree. Its interval union is connected. Induction gives retained history at most 31

Optimal Consistency for Interval Selection

2v at a negative root and M v at a positive root: an ordinary parent pays all retained child costs, and a special parent has only negative children of total length at most φ times its own. Thus the negative-subtree protrusion bound also holds for all source-bearing paths used by the proof. The weighted cut has a nonzero left share, hence positive ledger, so its cost inequalities are unchanged. At a negative birth, omit the zero-ledger children and apply the original weighted or positive cuts to the others. Their costs sum to at most the actual ordinary gate. Birth exterior and cut bounds follow, with the zero-birth-ledger case immediate. The lifetime argument and its three capacity cases use no cost restriction at zero ledger. At an ordinary positive birth of length u, every child satisfies bi ≤ q(vi , bi ), also when bi = 0, so the inherited ledger is at most u. One must not infer that the total child length is at most u/d: zero-ledger children can violate that inequality. The positive cut proof only needs this length bound for the selected child carrying a nonzero share, for which its individual cost gives vi ≤ u/d. At a special birth the actual tests still give both child length and inherited ledger at most φu. All remaining path and sibling arguments carrying nonzero shares use the geometry established above. The positive cuts and the birth induction therefore close as before. Finally source conservation gives the claimed bound for w(P ). For example, define

( q0 (v, b) =

φv, b = 0, q∗ (v, b), b > 0.

With positive cost M v, this policy is d-consistent and has finite robustness, although q0 (v, 0) < dv. It is homogeneous and nondecreasing in ledger, with an explicit jump at zero. A finite robustness certificate follows. Total accepted subtree length is at most dv at a negative root and (M + 1)v = 2dv at a positive root. At an ordinary parent, child history divided by child cost is at most φ; at a special parent all children are negative and their total length is at most φv. This proves both bounds simultaneously. Thus total accepted history H is at most 2d ALG. Distribute each rejected offline-comparator interval’s length among its then-held conflicts proportionally to their lengths. Ordinary rejection and costs at most M v bound a receiver’s charge by M v. For a fixed accepted identity, at most two compatible comparator intervals extend past its endpoints; those contained inside it have total length at most its own. Its total rejected-comparator charge is therefore at most (2M + 1)v. Accepted comparator identities contribute at most H. Consequently OPT ≤ (2M + 2)H ≤ 8d2 ALG. The universal lower bound then makes its consistency exactly d. Theorem E.2 (A floor under nonshrinking negative costs). Keep the ordinary-first sum gate, both special tests, fees, and full ledger inheritance. Allow arbitrary fixed finite nonnegative cost functions q− (v, b) and q+ (v, b), but assume q− (v, b) ≥ v

(v > 0, b ≥ 0).

(E.2)

If the raw or permanently filtered policy is d-consistent, then q− (v, v) ≥ dv,

q+ (v, dv) ≥ M v

(v > 0),

and its strict robustness is at least φ5 . No monotonicity, continuity, or homogeneity of either cost is assumed. Proof. First fix v > 0 and suppose c = q− (v, v)/v < d; by (E.2), c ≥ 1. All following coordinates are multiplied by this fixed v, without rescaling the cost function. Put t = α − ϵ and x = 1 − t, with sufficiently small ϵ > 0. Offer negative V = [0, 1), three positive tiles partitioning [1 − ϵ − x, 1 − ϵ), then positive T0 = [1 − ϵ, 1 − ϵ + t). All four positives fail the special length test and are shorter than the ordinary cost, which is at least one. Their rejections give ledger x + t = 1 exactly. Negative W = [ϵ − c, ϵ) now replaces V at ordinary equality. Offer four positive tiles partitioning [2ϵ − c, 0), and then T1 = [0, t − ϵ). Their lengths are below both αc and c, so all reject, leaving ledger B = c + 1 + t − 3ϵ. Finally offer a positive L ending at 2ϵ − c with length ℓ = αB − ϵ. It fails the special ledger test. If it is accepted ordinarily, its ratio is 1 + B/ℓ > d. If it is rejected, the ratio is (φB − ϵ)/c, and φB − ϵ − dc = d − c − (4φ + 1)ϵ > 0. The positives are consecutive and tile the full offered hull; both negatives lie inside it. Hence their labels are perfect in either branch. This contradiction proves q− (v, v) ≥ dv and uses no positive cost. 32

Optimal Consistency for Interval Selection

Next fix u > 0 and suppose q+ (u, du) < M u. Choose 0 < c < M with cu ≥ q+ (u, du), and multiply all following coordinates by u. Offer negative K = [1 − ϵ, d − ϵ) and three positive tiles partitioning [1, d). They reject, giving length and ledger both φ. The first part makes its ordinary cost at least M . Positive Q = [0, 1) is special at equality in both tests and has ledger d. Negative W = [ϵ − c, ϵ) replaces it ordinarily. Four positive tiles partitioning [2ϵ − c, 0) reject, leaving ledger B = d + c − 2ϵ. A final positive L ending at 2ϵ − c, of length ℓ = αB − ϵ, again gives ratio 1 + B/ℓ > d if accepted, whereas rejection gives φB − ϵ − dc = M − c − (2φ + 1)ϵ > 0. The positives again partition the complete hull containing both negatives. Thus q+ (u, du) ≥ M u. For the robustness witness, use unit scale and negative K = [1 − ϵ, d − ϵ) followed by three positive tiles partitioning [1, d). These rejections give ledger exactly φ, so q− (φ, φ) ≥ M . Offer I R J L

0 0 1 0

[ϵ, d − 2ϵ), [d − 2ϵ, d − 2ϵ + M − ϵ), [0, 1), [2ϵ − M, ϵ).

The first two requests reject. Request J is special at equality in both tests, with ledger d, and its positive cost is at least M . Thus L also rejects and the final gain is one. The compatible L, I, R tile the entire hull and give OPT = φ5 − 5ϵ. The four positive predictions are mutually compatible, so the filter changes no label in this witness or in either perfect-label construction above. Letting ϵ ↓ 0 proves the bound. Unlike Proposition D.5, which fixes positive cost M v and assumes q(v, 0) ≥ dv but not C = d, this floor permits arbitrary fixed positive costs and assumes the global condition (E.2) together with C = d. In particular, changing the fixed positive coefficient to κ < M , including κ = d, cannot preserve d-consistency under these hypotheses. The unrestricted claim for arbitrary negative costs remains open. Discounting positive-ledger states can fail. The lower-cost rule qlow (v, b) = min{2φv, max{min{φ(v + b), dv}, φv + αb}} is not d-consistent, even with the original positive cost M v. Here is a 14-request family with 0 < ϵ ≤ 10−3 . Put v = φ5 , u = φ4 , w = φ7 and offer V0 0 [0, 1), S0 , S1 1 [0, 1/2), [1/2, 1), V1 0 [1 − ϵ, φ + 2 − ϵ), V2 0 [φ + 2 − 2ϵ, 4φ + 3 − 2ϵ), V3 0 [4φ + 3 − 3ϵ, 9φ + 6 − 3ϵ), Q 1 [9φ + 6 − 4ϵ, 12φ + 8 − 4ϵ), W 0 [9φ + 6 − 5ϵ, 22φ + 14 − 5ϵ). Next offer four positive tiles partitioning [12φ + 8 − 4ϵ, 22φ + 14 − 6ϵ), followed by positive L = [d − 3ϵ, 9φ + 6 − 4ϵ) and positive R starting at 22φ + 14 − 6ϵ with length α(1 + w + φ6 − 3ϵ) − ϵ. The first two positives reject. At ledger one, the successive negative costs are d, 3φ + 1, 5φ + 3, so V1 , V2 , V3 are ordinary replacements at equality. Request Q is special at length equality and W is ordinary at equality w = M u. All remaining requests reject: the four tiles and L fail the length test, and R fails the ledger test. They also fail ordinary acceptance. Thus ALG = w,

w(P ) = dw + φ − (3φ + 1)ϵ > dw.

To check optimality, the first two positives pay for V0 at equality. Request L is longer than every compatible subset of {V1 , V2 , V3 }, whose largest weight is w(V1 ) + w(V3 ) = 6φ + 4 < φ6 − ϵ. The positive Q, the four tiles, and R all conflict with W and have total weight w − 2ϵ + w(R) > w. These three assigned positive groups are disjoint and compatible, and each belongs to the positive conflict set of its assigned negative group. Replacing any feasible negative subset by its conflicting positives therefore never loses weight. Hence P is an optimum; it need not be unique because V0 ties S0 , S1 . The ratio tends to d + φ−6 ≈ 2.674 > d. Unlike the zero-ledger relaxation, this policy transports nonzero source mass through several discounted negative replacements. 33

Optimal Consistency for Interval Selection

F. A barrier for singleton-negative replacement The five-request floor in Proposition D.5 fixes the positive cost and special predicates. The following result permits arbitrary ledgers, positive costs, and history-dependent rules. It requires only one restriction on negative arrivals, evaluated before their decisions. Theorem F.1 (Singleton-negative barrier). Consider a deterministic policy A in the model of Section 2 that satisfies the following condition at every reachable prearrival state: (N) If the sole held request is a negative K of length v, an incoming negative that conflicts with K and has length less than dv is rejected. If C(A) ≤ d and R(A) < ∞, then R(A) ≥ φ5 . The result allows voluntary revocation and arbitrary dependence on the entire rejected history. It also holds after the permanent feasibility filter. Proof. Fix a finite robustness bound r > max{1, R(A)} and 0 < ϵ < 1/1000. Put v = φ(1 − 4ϵ),

p = 1 + v − 2ϵ,

z = dv − ϵ.

Offer the negative requests K = [1 − ϵ, 1 − ϵ + v),

I = [ϵ, p),

R = [p, p + z)

in this order. Finite robustness forces K to be retained. Both subsequent requests conflict with it and lie strictly below the threshold dv, with margins φv − 1 + 3ϵ > 0 and ϵ, respectively. Condition (N) rejects both; discarding K would leave zero reward. Offer a finite positive partition of [1, p), each tile shorter than v/r. At the first departure from K, only the incoming tile could remain, whereas historical K gives OPT ≥ v. Robustness therefore forces every tile to be missed and K retained. Now offer positive J = [0, 1). Let A consist of J and these tiles; it tiles [0, p) and has weight p. This positive family is feasible but is not an optimum of the current history, since R is compatible with all of it. A perfect completion forces retention of J. Suppose J is rejected. Then K remains, since deleting it gives zero reward. Offer positive T = [p, p + v) and put E = p + v. After any response, the local held weight is at most v, whereas w(A ∪ {T }) = E,

E − dv = 2ϵ.

Set η = ϵ/2, choose finite h > max{dv, (r − 1)v, 1}, and put u = αh,

b = E + u − η,

H = [b, b + h),

U = [E, b + η).

Offer negative H. It is disjoint from all earlier requests; in particular, b − (p + z) = αh − φv + ϵ − η > 0. The historical packing {K, H} has weight v + h > rv, so H must be retained. Offer a finite positive partition F of [b + η, b + h − η), with each tile shorter than (v + h)/r − v > 0. At the first departure from H, the held weight is at most v plus the incoming tile. The same historical packing forces every tile to be missed and H retained, even if the local holder is voluntarily revoked. Offer positive U . If retained, stop, with held weight at most v + αh. If U is not retained, robustness forces H to remain. In that case offer positive V = [b + h − η, b + 2h − η) and stop; every response has held weight at most v + h. All positives are compatible. Their totals in the two branches are E + φh − 2η and E + dh − 2η, so E + φh − 2η − d(v + αh) = ϵ, E + dh − 2η − d(v + h) = ϵ. To apply consistency, we check the entire history. At the first terminal the negatives are K, I, R, H. Every feasible negative family is a subset of {K, H} or {I, R, H}. The following positive groups conflict with the indicated negative families and have the stated strict surpluses: 34

Optimal Consistency for Interval Selection

Negative family

Positive group

Surplus

{K} {I} {R} {H} {R, H}

A ∪ {T } A {T, U } {U } ∪ F {T, U } ∪ F

E−v ϵ αh − φv + ϵ αh − 2η αh − φv + ϵ − 2η

All margins are positive because αh > φv and 2η = ϵ. The groups for K and H are disjoint. The group A for I is disjoint from each group for R, H, or {R, H}. Adding the corresponding margins therefore covers all nine nonempty feasible negative subsets, counting the shared U only once. Adding V preserves these certificates. The strict exchange argument in (C.3) proves that the complete positives are the unique optimum at both terminals. Either terminal contradicts C(A) ≤ d. Thus J must be accepted and retained on the common prefix; accepting and then discarding it would leave zero reward. A second perfect completion forces rejection of L. Define ℓ = φp − 2ϵ,

s = ϵ − ℓ,

L = [s, ϵ),

and offer negative L. It overlaps the sole holder J by ϵ. Suppose it is accepted; finite robustness forces its retention. Put χ = 2α − 1 = α3 > 0 and η = χϵ/4. Offer a positive partition of [s + η, 0) with each tile shorter than ℓ/r. Historical L forces every tile to be missed by the same first-departure argument. Next offer positive B = [s + η − ℓ, s + η), of length ℓ. It overlaps L by η and is compatible with every earlier positive. After either response the local held weight is at most ℓ. Let Z consist of B and this left partition. The full local positive family P = Z ∪ A tiles [s + η − ℓ, p), with weight P0 = p + 2ℓ − ϵ − η,

P0 − dℓ = χϵ − η = 3χϵ/4.

(F.1)

The negatives are N = {K, I, L} and the unavailable R = [p, p + z). Among K, I, L, only K and I conflict. All five nonempty feasible negative subsets have strict exchange certificates: Negative family

Positive group

Surplus

{K} {I} {L} {K, L} {I, L}

A A Z ∪ {J} Z ∪A Z ∪A

p − v = 1 − 2ϵ ϵ ℓ+1−ϵ−η p+ℓ−v−ϵ−η ℓ−η

Every margin is positive for the stated ϵ range. Apply Lemma C.1 with c = d, γ = 0, a = ℓ, and ζ = χϵ/8. Historical L has weight a. Choose finite h > max{(r − 1)ℓ, 1} with αh > z + 2ζ. Then h > 2ζ and p + αh − ζ > p + z, the largest old right endpoint, while P0 − dℓ − 2ζ = χϵ/2 > 0. Thus every hypothesis of the lemma holds. Its satellite construction repairs R as well as the new negative H; for their joint subset the new conflict group has surplus αh − z − 2ζ > 0 and counts its shared boundary positive once. This group is disjoint from every local group above, so mixed negative subsets also satisfy strict exchange. The resulting robustness or actual-perfect consistency violation rules out acceptance of L. The finite robustness witness. Stop on the common prefix immediately after L, which must be rejected. J remains the sole holder, so ALG = 1. The compatible negatives L, I, R tile the entire offered hull, containing every request on this short input. Length reward therefore gives the exact optimum OPT = ℓ + (p − ϵ) + (dv − ϵ) = d + 2dv − (2φ + 6)ϵ = φ5 − (18φ + 14)ϵ. 35

Optimal Consistency for Interval Selection Table 3. Deterministic guarantees. d = φ2 , c∗ = α3 , B∗ = φ5 , BC∗ = 4φ + 5, BS = 7φ + 4. In paired rows the error guarantee applies only to the filtered policy (superscript F ); ηK uses original labels. LR is due to Garay et al. (1997); its interval formulation, Naive and the RP consistency bound are given by Karavasilis (2025). Algorithm LR RPλ , λ ≥ 2 Naive Shaped T∗ , T∗F Credit Tc∗ , TcF∗ F SUM Sφ3 , Sφ 3

Consistency M 3λ ≤ λ−1 1 d d d

Robustness

Error guarantee

M (exact) — 2λ + 2 (exact) — ∞ OPT ≤ ALG + ηK B∗ (exact) OPT ≤ dALG + ηK BC∗ (exact) OPT ≤ dALG + ηK BS (exact) OPT ≤ dALG + ηK

Every partition above is finite: a positive mass can be split into finitely many tiles below any positive threshold. The two longer completions are causal witnesses that force decisions on their shared prefixes; neither changes an earlier label or assumes prefix optimality. Taking the supremum over positive ϵ proves R(A) ≥ φ5 . All constructed positive families are compatible, so permanent filtering changes no bit and the same witnesses apply. In particular, a source-cost policy whose sole negative holder of length v costs at least dv, and whose negatives have no acceptance route outside that cost gate, satisfies (N). Its positive costs, source fees, inheritance, and history-dependent special rules do not enter the proof. Any deterministic policy with C ≤ d and finite R < φ5 must instead accept some conflicting negative shorter than dv at a reachable state whose sole holder is a negative of length v. The zero-ledger policy q0 in Appendix E.1 gives a concrete escape from this early negative prefix. With the same v = φ(1 − 4ϵ) and p = 1 + v − 2ϵ, offer K followed immediately by I = [ϵ, p), before any positive source arrives. The ledger is zero and w(I) − q0 (v, 0) = 1 + v − 3ϵ − φv = ϵ > 0. Thus q0 replaces K by I, breaking the intended singleton-anchor branch. This policy is nevertheless d-consistent and finitely robust. It shows why an early-negative branch cannot simply be presumed to reject. However, q0 (v, b) ≥ v at every negative state, so Theorem E.2 still gives R(q0 ) ≥ φ5 .

G. Additional ledger policies and guarantees Credit varies the negative ledger coefficient; SUM uses total conflicting length. MAX uses maximum conflicting length and is retained as a descriptive experimental comparator. Credit-BANK Tc has negative cost min{M v, dv + cb}, c ≥ 0. The constant-cost gates are ( P λ J∈D w(J), SUM, Gλ (D) = (G.1) λ maxJ∈D w(J), MAX. Definition G.1 (Ledger policies). Shaped-BANK T∗ uses (7) and positive cost M v; Credit-BANK Tc uses (H.1). SUMBANK Sλ , for λ > d, and MAX-BANK Aλ , for λ ≥ d, use Algorithm 1 with the respective gate in (G.1). All other rules are shared: ordinary acceptance has priority, all thresholds accept equality, and special acceptance requires a positive prediction, only negative conflicts, and both length and ledger tests. The guarantees below concern Shaped, Credit, SUM and RP. Table 3 collects the endpoint comparisons. The full scalar envelope, its exact consistency threshold c∗ = α3 , and its global minimum 4φ+5 are in Theorem H.1. The fixed comparison T = Tφ/2 has exact robustness 6φ+3. For SUM, Corollary I.1 proves the policy-specific threshold λ ≥ φ3 , and Proposition J.1 gives exact robustness φ(2λ + 1) on that range, with the upper bound K(φ, λ) from (J.2) for λ > d. For c ∈ [c∗ , 1] and λ ≥ φ3 , respectively, both families satisfy w(P ) ≤ d ALG for feasible complete positives. For RP, Corollary J.1 proves exact robustness 2λ + 2 when λ ≥ 2, and λ + 2λ/(λ − 1) when 1 < λ < 2. Its published consistency bound 3λ/(λ − 1) need not be exact. Theorem F.1 treats the shared singleton-negative obstruction. Tables 4 and 6 compare the policies empirically; Appendices M–O specify the matched repeats and differing robustness budgets.

36

Optimal Consistency for Interval Selection

H. Credit-dependent replacement costs Put α = 1/φ, d = φ2 , and M = φ3 . ForP any fixed real c ≥ 0, Credit-BANK Tc uses the shared ledger updates and special tests of Algorithm 1, with ordinary gate J∈D τc (J), where ( M w(J), p(J) = 1, (H.1) τc (J) = min{M w(J), dw(J) + cb(J)}, p(J) = 0. Write qc (v, b) = min{M v, dv + cb} for the negative cost. The coefficient changes only this ordinary cost and is fixed for an entire execution. Ordinary acceptance has priority, thresholds accept equality, and rejection fees use simultaneous old-state snapshots with length-failure priority. Special acceptance still requires a positive arrival, only negative conflicts, W, B ≤ φw(I), and full ledger inheritance. The permanent-filter composition is denoted TcF . Theorem H.1 (Exact scalar envelope and consistency threshold). For 0 ≤ c ≤ 1, both raw and filtered policies have exact robustness R(Tc ) = R(TcF ) = K(c) := max{Kout (c), Kbr (c)}, Kout (c) = 5φ + 3 + φc, Kbr (c) = 5φ + 2 + 2φc.

(H.2)

Within this range, their consistency equals d if and only if c ≥ c∗ := α3 = 2φ − 3. For c ∈ [c∗ , 1], every execution with feasible complete positive set P satisfies b(J) ≤ dw(J) throughout every held lifetime,

w(P ) ≤ d ALG.

(H.3)

Among all c ≥ 0 whose raw policy has consistency d, the minimum robustness is 4φ + 5, attained only at c = c∗ . The same statement holds for the filtered policies. The branches in (H.2) agree at c = α; the outward branch dominates below it and the bridge branch above it. In particular, the comparison policy T = Tφ/2 retains C(T ) = d and R(T ) = 6φ + 3. H.1. Consistency from the common source-measure interface Theorem D.2 applies precisely when the scalar cost satisfies its two negative-cost inequalities. Globally qc (v, b) ≥ dv. For 0 ≤ b ≤ dv, the cap branch obeys φv + αb ≤ (φ + αd)v = 2φv < M v. The affine branch dominates the same expression exactly when v + (c − α)b ≥ 0

(0 ≤ b ≤ dv).

(H.4)

For c ≥ α this is immediate. For 0 ≤ c < α, its minimum over this interval is [1 + d(c − α)]v, so the necessary and sufficient condition for the interface is c ≥ α − 1/d = α − α2 = α3 = c∗ . At c = c∗ , equality occurs at b = dv, where the cost is 2φv < M v. Thus equality is included without invoking the cap. The source-measure induction proves (H.3), in fact for every c ≥ c∗ . On [c∗ , 1] the finite robustness proved below and Theorem 2 give exact consistency d. The following finite construction proves necessity. H.2. Eleven requests proving the consistency threshold Fix 0 ≤ c < c∗ and put k = 3φ + 1,

∆ = 2φ − d(1 + c) > 0,

D = (φ − c)k + 1 > 0.

Choose 0 < ϵ < min{1/100, ∆/(2D)}. 37

(H.5)

Optimal Consistency for Interval Selection

First offer the negative unit interval X = [0, 1) and then the positive seed intervals [ϵ, 1/2) and [1/2, 1 − ϵ). Their lengths 1/2 − ϵ < α fail the special length test and are below the ordinary cost, which is at least d. Both reject and deposit their complete lengths into the sole held conflict X, giving ledger 1 − 2ϵ. The positive interval A = [2ϵ − α, ϵ) has length α − ϵ and rejects for the same reasons. The ledger is now b1 = φ − 3ϵ. Next offer positive B starting at 1 − ϵ with length ℓB = αb1 − ϵ = 1 − (3α + 1)ϵ. Since ϵ < 1/100 and α < 31/50, we have ℓB > 0.96 > α. Thus B passes the special length test but fails the ledger test: φℓB = b1 − φϵ < b1 . It also fails the ordinary test because ℓB < 1 < d. Its complete length enters X’s ledger, which becomes bX = d − kϵ. Let g = d + cbX and offer negative J = [ϵ − g, ϵ). The cap on X is inactive, since g ≤ d(1 + c) < d(1 + c∗ ) = 2φ < M. Therefore J has exactly the old ordinary cost of X as its length. It overlaps X in [0, ϵ), accepts at equality, and inherits all of bX . We have d ≤ g < 2φ. Partition [2ϵ − g, 2ϵ − α) into four equal positive tiles. Each has positive length (g − α)/4 < αg because 4α > 1, and its length is below dg, a lower bound on J’s ordinary cost. Each tile overlaps J, fails both the ordinary test and the special length test, and deposits its full length. After the four tiles, the ledger of J is Bpre = bX + g − α = g + 2 − kϵ. Finally offer positive C ending at 2ϵ − g with length z = αBpre − ϵ. It passes the special length test because φz − g = 2 − (k + φ)ϵ > 0, using k + φ = 4φ + 1 < 8. It fails the ledger test strictly, as φz = Bpre − φϵ < Bpre . It also fails ordinary acceptance, since z < α(g + 2) < dg; the last inequality follows from d − α = 2 and g > α. Its overlap with J is positive: z > αg > ϵ. Thus every fee in the construction is the full arriving positive length, and the final held set is {J} with reward g. In spatial order the positive requests are C, the four new tiles, A, the two seed tiles, and B. They are consecutive and tile one interval. Its left end lies left of J because z > ϵ, and its right end lies right of X because ℓB > ϵ; hence it contains both historical negatives. The positive tiling attains the length of the entire offered hull and is optimal. Moreover it is the unique optimum. Covering the two extreme segments requires C and B, respectively. They exclude J and X, leaving only the positive tiles, all of which are needed to cover their positive-length segments. The labels are therefore perfect and the filter changes none of them. The exact optimum is OPT = Bpre + z = φ(g + 2 − kϵ) − ϵ, so OPT − d ALG = 2φ − g − (φk + 1)ϵ = ∆ − [(φ − c)k + 1]ϵ = ∆ − Dϵ > ∆/2 > 0.

(H.6)

This is a strict finite violation for every c < c∗ , for both raw and filtered policies. At c = c∗ , all gates and the uniqueness argument still hold for 0 < ϵ < 1/100; only the strict violation disappears. Its limit is lim

OPT

ϵ↓0 ALG

=φ+

2α = d. 1 + c∗

For positive ϵ at this endpoint, OPT − dg = −Dϵ < 0, consistent with the upper bound. 38

Optimal Consistency for Interval Selection

H.3. Terminal costs and the scalar robustness envelope We use the replacement-forest and connected-hull framework of Lemma D.5 and the proof of Theorem D.3. The scalarspecific estimates below verify its hypotheses without any feasible-label assumption. Throughout this subsection 0 ≤ c ≤ 1. For each accepted identity X, let qX be its ordinary cost immediately before revocation, or at termination if retained. Ledgers grow by nonnegative fees during a held lifetime, so costs are nondecreasing and dw(X) ≤ qX ≤ M w(X). An P ordinary parent of length h satisfies i qi ≤ h. A special parent is positive and has negative, ordinarily accepted children. Its special tests imply X W, B ≤ φh, qi ≤ dW + cB ≤ Ah, A = M + φc, ρ = A/M = 1 + c/d. (H.7) i

In this range 1 ≤ ρ ≤ 1 + 1/d < d. The P terminal-cost induction from the shaped proof applies with these A, ρ: an ordinary root’s omitted-root bound is ρ i qi ≤ ρh < qJ ; a special root’s ordinary children sum to at most Ah, as does its singleton M h. Thus the full same positive antichain bound is qJ or Aw(J) respectively. The history bound (D.8) also applies, since it uses only theP cost M h, negative lower bound dh, and special length gate. An ordinary birth gives history at most h + i qi ≤ 2h; a special birth gives h + 2W ≤ M h. The connected hulls obey these same bounds. Use Lemma D.5 with ωX = qX :

FJ (x, y) = |HJ ∩ [x, y]| + LJ (x) + UJ (y).

(H.8)

At an ordinary root, an eligible root singleton attains the side maximum qJ ; an ineligible side has weight at most ρh. With two eligible endpoints the gap lies inside the root and has length at most h; otherwise use its full history bound 2h. Thus the coefficients for two, one or no eligible endpoints are 1 + 2M,

2 + M + ρ,

2 + 2ρ.

(H.9)

At a special root J = [a, b), each side chooses the eligible root singleton of cost M h or the sum of the children’s side maxima. A zero maximum may choose children. Two singleton choices give (1 + 2M )h. With exactly one singleton, reflect so it is the left. If b > y, the gap is inside J, giving (1 + M + A)h. If b ≤ y, every child starts below b, so at most one compatible child k ends above y. If such a child exists, the gap has length at most h + hk and FJ ≤ (M + 1)h + (1 − ρ)hk + qk + ρW ≤ (M + 1)h + (1 + d − ρ)hk + cbk + ρW ≤ (M + 1)h + (1 + d)W + cB ≤ [M + 1 + φ(1 + d + c)]h = Kout (c)h.

(H.10)

Here qk ≤ dhk + cbk , 1 + d − ρ > 0, hk ≤ W , and bk ≤ B. Without an outward child, all right-side maxima are ineligible, and the full-hull bound gives (2M + ρφ)h. If both endpoint choices use children, at most one child bridges both cuts, meaning s(Ck ) < x ≤ y < f (Ck ). This child contains the gap and contributes at most hk + 2qk . Every other child has at most one eligible endpoint and contributes at most qi + ρhi . This also bounds a child with two ineligible endpoints because qi ≥ dhi > ρhi . Consequently X FJ ≤ hk + 2qk + (qi + ρhi ) ≤W +2

X

i̸=k

qi ≤ (1 + 2d)W + 2cB ≤ Kbr (c)h.

(H.11)

i

The second line uses (ρ − 1)hi ≤ qi . If no child bridges, each contributes at most qi + ρhi ; together with the full-hull bound, this gives (M + A + ρφ)h. All remaining coefficients lie below the two-term envelope. For the special-root cases, Kout − (1 + 2M ) = φ + φc, Kout − (1 + M + A) = φ, Kout − (2M + ρφ) = 1 + c, Kbr − (M + A + ρφ) = c. 39

Optimal Consistency for Interval Selection

For the remaining ordinary cases, Kout − (2 + M + ρ) = 3φ − 1 + 2αc > 0, Kout − (2 + 2ρ) = 5φ − 1 + (3φ − 4)c > 0. At c = 0 one non-bridge comparison is equality, which is sufficient. Strict endpoint eligibility assigns contact to the ineligible case; bridge uniqueness holds also when x = y. We have proved FJ (x, y) ≤ K(c)w(J) in every case. P For the charge hypothesis, assign each rejected I pieces w(I)τc (X)/ Y ∈D τc (Y ) to its current conflicts. Strict ordinary rejection and lifetime monotonicity bound each piece by qX ≥ w(X). These charges are used only in the analysis. The full antichain bound is at most Ah, and Kout − A = 3φ + 2 > 0. Lemma D.5 therefore yields OPT ≤ K(c)ALG. The same upper bound holds on effective labels after filtering. H.4. Two finite families matching the envelope Eight requests for the outward coefficient. Fix 0 < ϵ < 1/100. Offer negative K = [1 − ϵ, d − ϵ), of length φ, then three positive tiles partitioning [1 + ϵ, d − ϵ) equally. Each tile has length (φ − 2ϵ)/3 < 1 = αw(K), so it fails the special length test. Its length is also below dw(K) = M , so it rejects ordinarily. Each pays its full length to K, giving ledger bK = φ − 2ϵ. For 0 ≤ c ≤ 1, put g = M + cbK . The cost is exactly g, since g ≤ M + φ < M φ. Next offer, in this order, I R J L

0 0 1 0

[ϵ, d − 2ϵ), [d − 2ϵ, d − 2ϵ + g − ϵ), [0, 1), [2ϵ − M, ϵ).

Both I and R overlap the held K and have lengths d − 3ϵ < g and g − ϵ < g, respectively; being negative, they reject without changing the ledger. The positive J fails ordinary acceptance and passes both special tests: φw(J) = w(K) and bK < φ. It replaces K. Finally L overlaps J in positive length and has length M − ϵ < M , so it rejects against the positive ordinary cost. The algorithm ends with reward one. The four positive intervals are compatible, so filtering leaves all labels unchanged. The intervals L, I, R are consecutive, compatible, and tile the entire offered hull; all other requests are contained in that hull. Therefore their total is exactly OPT = (M − ϵ) + (d − 3ϵ) + (g − ϵ) = Kout (c) − (5 + 2c)ϵ.

(H.12)

Taking positive ϵ ↓ 0 gives the outward lower supremum for both raw and filtered policies. Seven requests for the bridge coefficient. Fix 0 < ϵ < 1/100, put p = (1 − 2ϵ)/3, b0 = 1 − 2ϵ, g = d + cb0 , and a = g − ϵ. Offer negative J = [0, 1), then three positive tiles partitioning [ϵ, 1 − ϵ) into lengths p, then negative L = [ϵ − a, ϵ),

R = [1 − ϵ, 1 − ϵ + a),

and finally positive Q = [1 − ϵ, 1 − ϵ + α). Every tile fails ordinary acceptance and the special length test because p < α, pays exactly p to the sole conflict J, and leaves it held. The ledger becomes b0 . Its ordinary cost is exactly g < M , since d + cb0 < d + 1 < M . Both exterior negatives overlap J in length ϵ and have length a < g, so they reject. The final Q fails the ordinary gate but satisfies both special tests: φw(Q) = 1 and b0 < 1. Thus ALG = α. The two exterior negatives and the three tiles form a feasible tiling of the entire input hull. All offered requests lie in it, including Q ⊂ R because a > α. Thus 2a + b0 OPT = = Kbr (c) − 4φ(c + 1)ϵ. ALG α

(H.13)

All positives are compatible, so the same execution occurs after filtering. Their feasible positive mass has ratio d−2φϵ < d; the robustness witness has imperfect labels. Taking positive ϵ ↓ 0 gives the bridge lower supremum. Since Kout − Kbr = 1 − φc, the two constructions match the upper envelope, including the switch at c = α and both endpoints c = 0, 1. 40

Optimal Consistency for Interval Selection

H.5. The global scalar minimum It remains to exclude larger coefficients. For any fixed c ≥ 1, use the eight-request outward construction with the actual capped cost g = min{M φ, M + c(φ − 2ϵ)}. The tile rejections still follow from the lower cost M on K. The negative requests I, R have lengths d − 3ϵ < g and g − ϵ < g, so reject. The same unit positive J fails the ordinary gate and passes both special tests; the held negative’s ledger is still φ − 2ϵ. The final L rejects against M . The compatible L, I, R still tile the entire input hull; hence ALG = 1 and OPT = M + d + g − 5ϵ. Continuity of the minimum as ϵ ↓ 0 gives R(Tc ), R(TcF ) ≥ M + d + min{M φ, M + cφ} = φ5 + φ min{c, φ} ≥ φ5 + φ > 4φ + 5.

(H.14)

This remains valid at c = φ, even if the cap is only reached in the limit. The filter changes no positive label. On [0, 1] both affine robustness branches have strictly positive slope, so K(c) is strictly increasing. Since c∗ < α, K(c∗ ) = φ5 + φα3 = φ5 + α2 = 4φ + 5. Every c < c∗ fails consistency d by the eleven-request construction. Every c ∈ (c∗ , 1] has strictly larger exact robustness, and (H.14) excludes every c ≥ 1 regardless of its consistency. This proves the global minimum and uniqueness in Theorem H.1. Shaped-BANK’s exact robustness φ5 improves this scalar minimum by α2 .

I. The exact consistency threshold of SUM-BANK SUM-BANK uses the constant cost λv for either prediction. Its optimal-consistency range follows from the source-measure theorem, while a separate finite construction proves necessity. Theorem I.1 (SUM feasible-positive capacity). For every λ ≥ M = φ3 and feasible complete positive set P , each held interval satisfies b(J) ≤ dw(J), w(P ) ≤ d ALG. (I.1) Consequently C(Sλ ) = d. Proof. Apply Theorem D.2 with q+ (v, b) = q(v, b) = λv. Globally q ≥ dv and q+ ≥ M v. For 0 ≤ b ≤ dv, φv + αb ≤ 2φv < M v ≤ λv. Thus every hypothesis holds with the exact shared fees and inheritance. Conservation gives the feasible-positive bound. The finite robustness in Proposition J.1 and Theorem 2 give equality for consistency. Corollary I.1 (Exact threshold). For λ > d, C(Sλ ) = d if and only if λ ≥ φ3 . Proof. The preceding theorem proves sufficiency. For d < λ < φ3 , Proposition I.1 gives   φ φ3 C(Sλ ) ≥ φ 1 + + 2 > d. λ λ The expression decreases strictly in λ and equals d at φ3 . I.1. A two-source lower bound with eleven requests The next construction gives the converse for the sharp golden-line threshold. It concerns SUM-BANK on that parameter line.

41

Optimal Consistency for Interval Selection

Proposition I.1. For every real λ > d = φ2 , 

φ φ3 C(Sλ ) ≥ φ 1 + + 2 λ λ

 .

(I.2)

Eleven-request inputs with a unique optimum and perfect predictions approach this bound. In particular it exceeds d for d < λ < φ3 and equals d at the endpoint in the limit. Proof. Write β = φ, so d = β + 1 and β 3 = 2β + 1. Fix λ > d and choose 0 < q, η, ζ < 14 ,

β 1 0 < ε < min{ 100 , 4λ }.

Set x = q − β + ε,

y = x + ε − β/λ,

m = (q + 1 + λ − η)/2,

B = λ + β + β /λ − q − η − 3ε, 3

u = (1 − ζ)B/β.

Reveal the following distinct requests in the displayed order. Request

Interval

Prediction

Z E1 E2 Y X Q J T H1 H2 U

[y − d/λ + ε, y + ε) [y − d/λ, y − d/(2λ)) [y − d/(2λ), y) [y, y + β/λ) [x, x + β) [q, q + 1) [0, λ) [x + 2ε, q) [q + 1, m) [m, λ − η) [λ − η, λ − η + u)

0 1 1 1 0 1 0 1 1 1 1

All lengths are positive. In particular, w(T ) = β − 3ε > 0 and w(Hi ) = (λ − 1 − q − η)/2 > 0. Also B > λ − 53/100 > 147/100 and u > (3/4)(147/100)/2 = 441/800 > η, so U crosses the right endpoint of J. The positive requests in spatial order are E1 , E2 , Y, T, Q, H1 , H2 , U . They are compatible: Y ends at x + ε, before T starts at x + 2ε, and all other consecutive contacts are at endpoints. Among negative requests, Z is compatible with X and J, whereas X overlaps J. Indeed, Z ends at x + 2ε − β/λ < x < 0, while X ends at q + ε > 0. We now follow the actual acceptance rules, with ordinary acceptance taking priority and equality accepted. Initially Z is accepted. Each Ei has length d/(2λ) < β/λ = w(Z)/β. Both tests fail, and each assigns its full length to its sole conflict Z. Hence b(Z) = d/λ. Request Y overlaps Z by ε and fails the ordinary test. Both special thresholds hold at equality: w(Y ) = β/λ = w(Z)/β = b(Z)/β. Thus Y replaces Z and has ledger (d + β)/λ = β 3 /λ. Request X overlaps Y by ε and replaces it ordinarily at equality, w(X) = λw(Y ) = β, inheriting that ledger. Next Q fails the ordinary test, meets the special length test at equality, and satisfies its ledger test since b(X)/β = d/λ < 1 = w(Q). Therefore b(Q) = 1 + β 3 /λ. Request J replaces Q ordinarily at equality, with birth ledger b0 (J) = 1 + β 3 /λ. Each of T, H1 , H2 has only J as a current conflict and length less than λ/β: for T , use λ > d = β 2 ; for Hi , use w(Hi ) < λ/2 < λ/β. Each fails both ordinary acceptance and the special length test. Their full lengths are assigned to J, leaving ledger B just before U . The special ledger test for U strictly fails because u = (1 − ζ)B/β < B/β. The ordinary test also fails: B < λ + 2β implies u < λ/β + 2 < λ2 . For the last inequality, λ2 − λ/β − 2 is increasing for λ > d and equals 2β > 0 at λ = d. Whether or not the special length test fails, the sole-conflict allocation assigns all of u to J. The terminal solution is {J} and ALG = λ, while ledger conservation gives w(P ) = B + u.

42

Optimal Consistency for Interval Selection

To check perfect predictions, fix a feasible subset of negative requests and extend it by all compatible positives. This is the best extension since all weights are positive. Besides the empty subset, the only feasible choices and their deficits relative to P are {Z} β/λ 1 + β/λ − 3ε {X} {J} β − q − η − 3ε + u {Z, X} 1 + β/λ − 3ε {Z, J} β/λ + β − q − η − 3ε + u. All are strictly positive under the parameter restrictions. A proper subset of P also loses positive weight. Thus P is the unique optimum. Consequently the exact finite ratio is    OPT 1−ζ β β3 q + η + 3ε = 1+ 1+ + 2 − . ALG β λ λ λ Let all four positive perturbations tend to zero through their permitted ranges, keeping eleven requests. Since 1 + 1/β = β, this proves the supremum lower bound (I.2). Subtracting β(1 + d/λ) gives β(β 3 − λ)/λ2 . The lower bound exceeds d exactly when λ2 − dλ − d2 < 0, whose positive root is β 3 . For an explicit finite witness, take λ = 3, q = 1/100, and ε = η = ζ = 1/1000. The ratio is 2502479 + 7474021φ ≈ 3.243488669 > d. 4500000

J. Joint geometric cuts for aggregate replacement Proportional charging of rejected requests is used in Karavasilis (2025, Theorems 4.10–4.11). Here we bound the charge arriving at a final replacement tree. Its two exterior charges and the space left between them must be bounded together. The proof distinguishes an ancestry antichain from a feasible set of intervals: only the former is required for the intermediate maxima. Theorem J.1 (Aggregate-gate transfer). Let β ≥ 1 and λ > β. A causal policy accepts a request by revoking precisely its current conflicts, retains all nonconflicts, leaves its held set unchanged on rejection, and makes no other revocations. Label each acceptance M or S, with empty-conflict acceptances labelled M. Assume that: 1. An M node’s children have total length at most its length divided by λ. 2. An S node has only M children, with total length at most β times its length. 3. Every rejected request I has a nonempty conflict set D and satisfies w(I) < λw(D). Put qM =

λ+1 , λ−β

qS =

λ(β + 1) . λ−β

K(β, λ) = max{β(2λ + 1), (β + 1)λ + qS , βλ + β 2 + qS }.

(J.1) (J.2)

Every feasible request set O then satisfies w(O) ≤ K(β, λ)ALG. No correctness or feasibility of the predictions is assumed. Proof. We first bound each replacement tree and then distribute the optimal requests over the final trees. Replacement trees and restricted antichains. Each accepted identity is a node, made a child of its unique replacement if revoked. The roots are the final held requests. Child roots are compatible, and each overlaps its parent in positive length. An ancestry antichain contains no node and its strict ancestor. Subtree induction bounds its mass by h at an M root of length h, and by βh at an S root. If the root is included, the antichain is its singleton. Otherwise an M root gives mass at most βh/λ < h, while an S root sums the M child bounds to at most βh.

43

Optimal Consistency for Interval Selection

Let HJ be the closure of the union of the accepted intervals in J’s subtree. This union is connected along replacement edges. The identities qM = 1 + qS /λ and qS = 1 + βqM bound the sum of all node lengths, and hence |HJ |, by qM w(J) or qS w(J) according to the root’s type. Also qS ≥ qM . Different final hulls need not be disjoint. For arbitrary real x ≤ y, let LJ (x) be the maximum mass of an ancestry antichain restricted to nodes V with s(V ) < x. Define UJ (y) using f (V ) > y. Empty antichains are allowed. Set FJ (x, y) = |HJ ∩ [x, y]| + λ{LJ (x) + UJ (y)}.

(J.3)

We prove FJ (x, y) ≤ K(β, λ)w(J) for every subtree. These maxima may come from different times. An ordinary root. Write J = [a, b) and h = b−a. Root-omitting antichains have mass at most βh/λ < h. Consequently LJ (x) = h

LJ (x) ≤ βh/λ

(a < x),

(a ≥ x),

and the analogous right statements hold with b > y and b ≤ y. If both root endpoint tests hold, the gap lies inside J, and FJ ≤ (2λ + 1)h. If exactly one holds, the coefficient is at most qM + λ + β. It does not exceed (β + 1)λ + qS , since the difference is β(λ − 1) + (qS − qM ) ≥ 0. If neither holds, the coefficient qM + 2β is smaller still because λ > β. A special root. Its ordinary children Ci have lengths hi and total H = LJ (x) = max{h1a<x ,

X

LCi (x)},

P

i hi ≤ βh. The exact recursions are

UJ (y) = max{h1b>y ,

i

X

UCi (y)}.

i

Select maximizing branches, using children when the maximum is zero. If both selections are the singleton root, the gap lies in J, giving (2λ + 1)h. If one selects the root and the other selects children, the coefficient is at most qS + (β + 1)λ. Suppose both select children. Call Ck a bridge when s(Ck ) < x ≤ y < f (Ck ). At most one bridge exists, including when x = y, because two would overlap in positive length. If it exists, the entire gap lies in Ck and both its maxima equal hk . Every other child has at most one eligible root endpoint, so its two maxima sum to at most (1 + β/λ)hi . This also covers two ineligible endpoints, since 2β/λ < 1 + β/λ. Therefore FJ ≤ (2λ + 1)hk + (λ + β)(H − hk ) ≤ (2λ + 1)H ≤ β(2λ + 1)h. If there is no bridge, the hull bound instead gives FJ ≤ qS h + (λ + β)H ≤ (qS + βλ + β 2 )h. These cases prove the asserted joint-cut bound. Equality at an endpoint is consistently assigned to the ineligible case. From cuts to actual optimal requests. Apply Lemma D.5 with ωV = λw(V ) ≥ w(V ). Its endpoint maxima are λ times the length maxima used here, so its FJ is exactly (J.3). A rejected I sends w(I)w(V )/w(D) < λw(V ) to each current conflict V . The full weighted antichain bound is at most λβh, below K(β, λ)h since K ≥ β(2λ + 1). The established joint-cut bound therefore proves the theorem. The empty input and empty O are immediate. Lemma J.1 (A single-conflict witness for SUM). For every λ > d, the following family gives SUM-BANK ratio approaching (2λ + 1)φ. The family has one positive prediction, so permanent filtering leaves it unchanged. Proof. Put α = 1/φ and choose 0 < τ < min{(1 − α)/2, (λ − 1)/2}. Reveal [0, 1)0 ,

[−λ + 2τ, τ )0 ,

[τ, 1 − τ )0 ,

[1 − τ, 1 + λ − 2τ )0 ,

[τ, τ + α)1 ,

where subscripts are prediction labels. The first request is accepted. Each later request has exactly one maintained conflict. The three subsequent negative requests have length below λ, are rejected, and add no ledger. The last request passes the special length test at equality with zero conflicting ledger, leaving ALG = α. The middle three requests are pairwise compatible and form the unique optimum: the central one strictly contains and outweighs the last positive request, while the initial unit interval conflicts with every other request and has smaller weight than their packing. Their total is 2λ+1−4τ . Letting τ ↓ 0 proves the ratio through finite inputs with positive overlaps.

44

Optimal Consistency for Interval Selection

Proposition J.1 (SUM robustness). For every λ > d, φ(2λ + 1) ≤ R(Sλ ) ≤ RS (λ) := K(φ, λ).

(J.4)

R(Sλ ) = φ(2λ + 1),

(J.5)

For λ ≥ φ3 , these bounds match: R(Sφ3 ) = 7φ + 4.

For 3 ≤ λ ≤ φ3 , the upper coefficient is dλ + λd/(λ − φ). Proof. Ordinary acceptance gives the aggregate child bound. Special acceptance has only negative children, each of type M, and its length gate gives total child length at most φw(I). Every rejection fails the ordinary gate. Thus all transfer hypotheses hold with β = φ, independently of the ledgers and labels. The first term of K dominates when qS ≤ (φ − 1)λ + φ and qS ≤ φλ − 1. At λ = φ3 the first is an equality and the second has positive slack; qS decreases while both right sides increase. Below that threshold, down to 3, the mixed term dominates the first; it exceeds the third by λ − d > 0. This proves the stated upper coefficients. The lower bound is supplied by Lemma J.1. Corollary J.1 (Exact robustness of Revoke-Proportional). For every λ > 1, the unchanged Revoke-Proportional algorithm of Karavasilis (2025, Algorithm 4) satisfies  (  λ + 2λ/(λ − 1), 1 < λ ≤ 2, 2λ = (J.6) R(RPλ ) = max 2λ + 2, λ + λ−1 2λ + 2, λ ≥ 2. The same formula holds with the permanent prediction filter of Section K. Thus 2 is the exact cutoff for the formula 2λ + 2. The published consistency bound 3λ/(λ − 1) is unchanged. Proof. RP has the ordinary aggregate gate. Its special branch requires a positive label, only negative conflicts, and new length at least their total. Thus the replacement-tree and charge-conversion definitions of Theorem J.1 apply with β = 1. Every subtree ancestry antichain has mass at most its root length. In particular, an eligible singleton root attains the corresponding restricted maximum LJ or UJ . Coupled one-sided tails. For J = [a, b) of length h and y ≥ a, set TJ (y) = |HJ ∩ [a, y]| + λUJ (y),

  λ+1 tM = max λ + 1, , λ−1

tS = tM + 1.

We claim TJ (y) ≤ tM h at an ordinary root and TJ (y) ≤ tS h at a special root. The reflected statement also Pholds. If a ≤ y < b, the root attains UJ (y) = h, and the bound is (λ + 1)h. If y ≥ b, the root is ineligible and UJ (y) = i UCi (y). The closed hull HJ is the union of [a, b] and its child hulls. Each child starts at ai < b ≤ y, so X X |HJ ∩ [b, y]| ≤ |HCi ∩ [b, y]| ≤ |HCi ∩ [ai , y]|. i

i

P

Consequently TJ (y) ≤ h+ i TCi (y). At an ordinary root the child lengths sum to at most h/λ, giving (1+tS /λ)h ≤ tM h because (λ − 1)tM ≥ λ + 1. At a special root all children are ordinary and their lengths sum to at most h, giving (1 + tM )h = tS h. This proves the tail bounds by induction, including endpoint equality. Joint cuts. Set cM = λ + tM and cS = cM + 1. We show that the functional FJ (x, y) from (J.3) is at most cM h or cS h according to the root type. If both root endpoints are eligible, the gap is within J and FJ ≤ (2λ + 1)h ≤ cM h. If exactly one is eligible, say a < x and b ≤ y, then LJ (x) = h and FJ (x, y) ≤ λh + |HJ ∩ [a, y]| + λUJ (y) = λh + TJ (y). The tail bound gives the desired coefficient for either type. Reflection handles the other orientation. 45

Optimal Consistency for Interval Selection

If neither P endpoint is eligible, both restricted maxima decompose over children, and the hull union yields FJ (x, y) ≤ h + i FCi (x, y). At a special root this is at most (1 + cM )h = cS h. At an ordinary root it is at most (1 + cS /λ)h ≤ cM h, since (λ − 1)cM ≥ λ + 1. Equalities in endpoint tests are ineligible cases; an eligible root may always be selected in an antichain tie. These cases cover all real x ≤ y. The charge conversion in Theorem J.1 now gives R ≤ cS ; its whole-hull covering case has charge at most λh ≤ cS h. Algebraically, cS = max{2λ + 2, λ + 2λ/(λ − 1)}. Lower bound for λ ≥ 2. For 0 < ε < 1/8, reveal K G U J L

[1 − ε, 2 − ε) [ε, 2 − 2ε) [2 − 2ε, 2 − 2ε + λ − ε) [0, 1) [−λ + 2ε, ε)

0 0 0 1 0.

The trace is ordinary acceptance, two rejections, special acceptance, and rejection. In particular w(G) = 2 − 3ε < λ, also at λ = 2. The final value is one, and the compatible comparison set {L, G, U } has value 2λ + 2 − 5ε. Let ε ↓ 0. Alternating-chain lower bound. For any λ > 1, integer n ≥ 0, and 0 < ε < 1/2, define candidate lengths ℓ2k = ℓ2k+1 = λk−n

(0 ≤ k ≤ n),

a0 = 0,

ai+1 = ai + (1 − ε)ℓi .

Reveal Ai = [ai , ai + ℓi ) in increasing i, labelling even indices negative and odd indices positive. Immediately after Ai , reveal the negative filler Fi = [ai + εℓi , ai + (1 − ε)ℓi ). Each even candidate after the first ordinarily replaces its sole predecessor at growth equality. Each odd candidate specially replaces its negative predecessor at length equality. Consecutive candidates overlap in positive length, every filler is rejected, and the final held set is the singleton A2n+1 of length one. Writing b = f (A2n+1 ), finally reveal the negative request U = [b − ε, b − ε + λ − ε). It overlaps the held interval and is rejected. The fillers are compatible: Fi ends at ai+1 and the next filler starts strictly to its right. The final filler ends where U starts. They therefore give the feasible comparison value (1 − 2ε)2

n X

λk−n + λ − ε.

k=0

Letting first ε ↓ 0 and then n → ∞ gives R ≥ λ+2λ/(λ−1). All executions in the family are finite and use positive-length overlaps. For 1 < λ < 2 this limit exceeds 2λ + 2 by (2 − λ)(λ + 1)/(λ − 1) > 0; for λ ≥ 2 the preceding five-request family gives the larger branch. Finally, consecutive positive carriers in the chain, of lengths a and λa, have gap [λ − ε(1 + λ)]a > 0. Thus all positive predictions are feasible and the permanent filter changes no label. The five-request family has just one positive. The upper bound allows arbitrary effective labels, proving the filtered formula as well.

K. Prediction filtering and zero-error inputs Fix an optimum O, the original positive set P , and the set NO (F ) of optimum requests conflicting with F . The error of Karavasilis (2025) is X ηK (P, O) = w(O \ P ) + [w(NO (F )) − w(F )]. (K.1) F ∈P \O

Optimality makes each summand nonnegative; a false positive of equal weight to its optimal conflicts contributes zero. Proposition K.1 (Zero-error limitation). No finite k ≥ 0 makes OPT ≤ a ALG + kηK (P, O) valid for all inputs of raw Shaped-BANK when a < 4φ + 1, or raw scalar Credit with fixed c > 0 when a < 4φ + 3. For SUM-BANK at λ > d, the obstruction holds for a < 2λ + 1. Finite witnesses with pairwise distinct interval geometries have ALG = 1, OPT > a and zero error for every optimum. 46

Optimal Consistency for Interval Selection

Distinct overlapping equal-length alternatives inflate the ledger while contributing zero error; their complete positive set is infeasible. The filter maintains a permanent feasible history P ′ . An originally positive request receives effective label 1 precisely when it is compatible with all of P ′ ; insert it immediately, before running the selected policy. Every other effective label is 0. Every request reaches the algorithm, and the effective label is fixed for all decisions and ledger updates. Requests remain in P ′ after rejection or revocation. This is the Naive selection rule of Karavasilis (2025), used as a filter. Denote the compositions by T∗F , TcF , and SλF . Corollary K.1 (Simultaneous guarantees). For original labels and fixed optimum O, Shaped-BANK satisfies   OPT OPT − ηK (P, O) ALG(T∗F ) ≥ max , , φ5 d

(K.2)

with C = d and exact R = φ5 . The same simultaneous formula holds for scalar Credit TcF , c ∈ [α3 , 1], with robustness K(c) from Theorem H.1; its minimum is 4φ + 5. For SUM at λ ≥ φ3 , replace the robustness denominator by (2λ + 1)φ. These policies also have C = d and exact stated robustness. K.1. The permanent-history filter and its quality We analyze the permanent history P ′ defined above, produced by the NAIVE rule (Karavasilis, 2025, Algorithm 1). Original labels determine ηK (P, O); effective labels determine every policy decision and ledger increment. Lemma K.1 (Quality of the known NAIVE filter). For every finite request stream and every fixed optimum O, the permanent history produced by the filter in Section K is feasible, is a subset of P , and satisfies w(P ′ ) ≥ OPT − ηK (P, O).

(K.3)

The inequality is the NAIVE guarantee of Karavasilis (2025, Theorem 3.5). Proof. Each insertion preserves compatibility with every earlier insertion, so the entire set P ′ is feasible. Only originally positive requests are inserted, giving P ′ ⊆ P . For F ∈ P \ O, set eF = w(NO (F )) − w(F ). The set (O \ NO (F )) ∪ {F } is feasible. Optimality of O therefore gives w(O) ≥ w(O) − w(NO (F )) + w(F ), and hence eF ≥ 0 for every such F . Partition the positive predictions and their filtered subset as A = P ∩ O,

A′ = P ′ ∩ O,

B = P \ O,

B ′ = P ′ \ O.

If I ∈ A \ A′ , it was blocked at its arrival by some earlier request F ∈ P ′ . Since I ∈ O and O is feasible, that blocker cannot belong to O; thus F ∈ B ′ . Consequently, [ X A \ A′ ⊆ NO (F ), w(A \ A′ ) ≤ w(NO (F )). (K.4) F ∈B ′

F ∈B ′

Overlapping neighborhoods may count a request more than once, which only enlarges the right-hand side. Using B ′ ⊆ B

47

Optimal Consistency for Interval Selection

and the nonnegativity of every eF , we obtain w(P ′ ) = w(A) − w(A \ A′ ) + w(B ′ ) X X ≥ w(A) − w(NO (F )) + w(F ) F ∈B ′

X

= w(A) −

F ∈B ′

eF

F ∈B ′

X

≥ w(A) −

eF

F ∈B

X

= w(O) − w(O \ P ) −

eF

F ∈P \O

= OPT − ηK (P, O). This also accounts for false positives that the filter never inserts. K.2. Composition with the feasible-set guarantee Proof of Corollary K.1. Let A be a policy with a feasible-positive guarantee w(P ′ ) ≤ d ALGA and an arbitrary-label robustness bound OPT ≤ RA ALGA . The filter passes every request to A with an effective label fixed on arrival. Its complete effective positive set is the feasible set P ′ , while the offline optimum is unchanged. Lemma K.1 therefore gives   OPT OPT − ηK (P, O) ALGAF ≥ max , . RA d This remains valid when the second term is negative. The required policy-specific bounds are as follows. Policy and range

RA

Shaped-BANK Credit, c ∈ [α3 , 1] SUM, λ ≥ φ3

5

φ K(c) (2λ + 1)φ

Feasible-positive bound

Robustness bound

Theorem D.2 Theorem H.1 Theorem I.1

Theorem D.4 Theorem H.1 Proposition J.1

In particular, the Credit specialization is  ALG(TcF ) ≥ max

OPT OPT − ηK (P, O) , K(c) d

 .

(K.5)

For perfect original predictions, every positive belongs to a feasible optimum, so filtering changes no label. Thus the filtered and raw consistency suprema agree and equal d. To retain exact robustness, one must also check the matching witnesses. Shaped-BANK’s family in Proposition D.5 has one positive request. Both Credit families in Theorem H.1 have compatible positive sets. The SUM family in Lemma J.1 has one positive request. All therefore pass unchanged, proving equality with the listed RA . For Credit this includes 4φ + 5 at c = α3 and 6φ + 3 at c = φ/2. Standalone Naive returns P ′ and has the stronger coefficient-one error bound but unbounded robustness: a single negativelabelled request gives it zero reward. At the optimal-consistency configurations, the compositions add finite robustness while attaining the smallest deterministic consistency compatible with it. K.3. A zero-error obstruction with distinct intervals Proposition K.2 (Uniform zero-error obstruction). For SUM-BANK at every λ > d, with α = 1/φ and β = φ, and every c < 2λ + 1, there is a finite input with pairwise distinct interval geometries, ALG = 1, OPT > c, and ηK (P, O) = 0 for every optimum O. Therefore no finite k ≥ 0 makes OPT ≤ c ALG + kηK (P, O) valid for all inputs of that unfiltered configuration.

48

Optimal Consistency for Interval Selection

Proof. Every arrival below has at most one maintained conflict. Choose δ > 0 with δ < 1/4, λ − δ > max{α, δ}, and 2λ + 1 − 5δ > max{c, 1}. Choose an integer n > 1/α, set h = (1 − 3δ)/n, and choose an integer m large enough that B = mnh = m(1 − 3δ) > β(λ − δ). For j = 1, . . . , n let aj = δ + (j − 1)(h + δ/n) and define m positive requests in group j by   kδ kδ Ij,k = aj + , aj + +h , k = 0, . . . , m − 1. mn mn Within a group, all starts are different and their total span is less than δ/n < h, so all intervals overlap in positive length. Consecutive groups are separated by a gap δ/(mn) > 0. The first group starts at δ and the last endpoint is 1 − δ − δ/(mn) < 1 − δ. Thus all central intervals have distinct geometries and lie in [δ, 1 − δ). Offer the negative anchor J = [0, 1), then all the Ij,k in lexicographic (j, k) order, and finally the positive requests L = [2δ − λ, δ),

U = [1 − δ, 1 + λ − 2δ).

Each central request has length h < α < λ, so it fails both ordinary acceptance and the special length test. Its sole conflict is J, which receives its full length. After all central requests the ledger is B. Each boundary request has length λ − δ < λ and fails the special ledger test because the current ledger is at least B > β(λ − δ). Both reject and the final reward is one. The strict overlaps with J have length δ, and no requests in this construction are geometrically identical. Every other request conflicts with J. A feasible set avoiding J contains at most one interval of each central group, and can contain L, U together with any such selection. All weights are positive, and OPT = 2(λ − δ) + nh = 2λ + 1 − 5δ > max{c, 1}. Consequently the optima are exactly L, U and one representative per group. Every optimum is contained in P . An unselected positive conflicts with exactly one of its members, the chosen representative of its own group, which has the same length h. Every term of (K.1) is therefore zero, for every optimum. Substitution proves the assertion for all finite k. The construction has multiple optima but no coincident intervals. The complete positive set contains overlapping alternatives, so the predictions are not perfect. At λ = φ3 it excludes every error-bound coefficient below 4φ + 3. Corollary K.2 (Credit-BANK has the same zero-error limitation). For every fixed c > 0, every a < 4φ + 3, and every finite k ≥ 0, raw Tc fails OPT ≤ a ALG + kηK on some finite input with distinct interval geometries. Proof. Use the construction above with λ = M = φ3 and choose δ so that 2M + 1 − 5δ > a. Increase m until B = m(1 − 3δ) > max{φ(M − δ), φ/c}. Initially the unit negative anchor costs d, and every central length satisfies h < α < d, so all central requests reject. The inequality cB > φ = M − d brings the anchor cost to its cap M before L, U arrive. Each boundary request then fails the ordinary and ledger tests, and subsequent deposits preserve the cap. The reward is one and the same optimum calculation gives OPT = 2M + 1 − 5δ > a and zero error for every optimum. Corollary K.3 (Shaped-BANK’s raw zero-error limitation). For every a < 4φ + 1 and every finite k ≥ 0, raw ShapedBANK fails OPT ≤ a ALG + kηK (P, O) on a finite input with pairwise distinct interval geometries, ALG = 1, OPT > a, and ηK (P, O) = 0 for every optimum O. Proof. Use Proposition K.2’s overlapping-group construction with λ = 2φ. Choose δ > 0 small enough that 4φ+1−5δ > a. The initial negative unit anchor costs d, and all central requests have length h < α < d. They therefore reject ordinarily and by the special length test, each depositing its whole length. The finite multiplicity m gives B = m(1 − 3δ) > φ(2φ − δ) > d.

49

Optimal Consistency for Interval Selection

The shaped cost has reached its cap 2φ before the two boundary arrivals. Each boundary length is 2φ − δ, below both its ordinary threshold and the ledger threshold. Both reject, their deposits preserve the cap, and the reward is one. The optimal sets are the two boundary requests and one equal-length representative of each central group. They have weight 4φ + 1 − 5δ > a, and every unchosen positive has exactly one equal-weight conflict in each optimum. Thus ηK (P, O) = 0 for every optimum, as required. The two policies’ different caps give different zero-error coefficients. For raw Shaped-BANK, 4φ+1 > d already excludes the optimal-consistency coefficient in such a bound. K.4. Exact implementation of the special tests For rational w > 0 and X ≥ 0,

w ≥ X/φ

⇐⇒

w2 + wX − X 2 ≥ 0.

For X > 0, divide by X 2 and use that t2 + t − 1 is strictly increasing for t ≥ 0 with root 1/φ; for X = 0, both conditions hold. Taking X = W or X = B implements the two special tests without rounding the golden ratio. K.5. Precision, recall, and confidence scores Classification summaries and conflict-weighted error answer different questions. Fix an optimum O of positive weight and write T = P ∩ O, F = P \ O. The length-weighted recall is rw = w(T )/w(O); when w(P ) > 0, length-weighted precision is pw = w(T )/w(P ). For each false-positive request F ∈ F define κF = w(NO (F ))/w(F ) ≥ 1. The error definition gives exactly X w(F ) ηK (P, O) = 1 − rw + (κF − 1). OPT OPT F ∈P \O

If pw > 0 and every false positive has κF ≤ κ, this implies the conditional bound ηK 1 − pw ≤ 1 − rw + (κ − 1)rw . OPT pw There is no universal bound on κ in our model: a short false-positive interval can conflict with a much longer optimal interval. Indeed, fix 0 < ϵ < 1/10 and an integer m ≥ 2. Let O contain [0, 1) and m2 − 1 mutually compatible intervals to its right with total length ϵ. Add m distinct intervals of length ϵ/m2 inside [0, 1), and label every request positive. These added intervals have combined length at most ϵ/m < 1, so O is the unique optimum. Recall is one, count precision is m2 /(m2 + m) → 1, and weighted precision is (1 + ϵ)/(1 + ϵ + ϵ/m) → 1. Nevertheless m − ϵ/m ηK = −→ ∞. OPT 1+ϵ Thus even simultaneously high count and weighted precision and perfect recall do not alone make this error guarantee informative. The observed conflict costs, not only the confusion matrix, must be reported. A predictor may output a score s(I) ∈ [0, 1] and fix its bit at arrival using p(I) = 1{s(I) ≥ τ }. For every threshold fixed without future test outcomes, the deterministic robustness theorem still applies to the resulting bits, and the filtered error theorem applies to their actual ηK . Calibration or threshold selection alone does not bound the conflict multipliers above.

L. Randomized guarantees and pathwise protection For the expected-gain comparison, allow randomized algorithms with the same online information and feasible, irrevocable rejection and revocation rules as in Section 2. Fix each complete nonempty finite labelled input σ independently of the algorithm’s random coins. The input includes the reveal order, all intervals, all labels, and its termination point; its length and future requests are not disclosed to the algorithm. Define Rexp (A) = sup σ

OPT(σ) , E[ALGA (σ)]

Cexp (A) =

sup

OPT(σ)

σ:P is optimal E[ALGA (σ)]

.

A zero denominator gives ratio +∞, and no additive term is allowed. For deterministic algorithms, Rexp and Cexp coincide with the ratios in Definition 1. 50

Optimal Consistency for Interval Selection

L.1. The exact initial-mixture curve Proposition L.1 (An initial mixture of two existing algorithms). Let rLR = 2φ + 1 and 0 ≤ π < 1. At initialization, Mπ selects NAIVE with probability π and LR with probability 1 − π, and then follows the selected algorithm for the whole input. Put 1 rLR Cπ = , Rπ = . π + (1 − π)/rLR 1−π Then Cexp (Mπ ) = C π ,

Rexp (Mπ ) = Rπ < ∞.

Eliminating π gives R = 2φC/(C − 1) for 1 < C ≤ φ3 . This is the exact curve of this mixture family. For arbitrary original labels and any one fixed optimum O, 1−π OPT E[ALGMπ ] ≥ π max{0, OPT − ηK (P, O)} + rLR   OPT OPT = max , − πηK (P, O) . Rπ Cπ

(L.1)

Here P is the original positive set and ηK (P, O) is the error in (K.1). Proof. The known guarantees used here are ALGNaive ≥ max{0, OPT − ηK (P, O)} and ALGLR ≥ OPT/rLR (Karavasilis, 2025, Theorem 3.5 and Section 4). The first also follows from Lemma K.1, since standalone NAIVE returns its permanent feasible history. For each fixed input, linearity of expectation gives E[ALGMπ ] = π ALGNaive + (1 − π) ALGLR . Substituting the two guarantees proves the first line of (L.1). Its second line is the identity a + π max{0, x} = max{a, a + πx} for π ≥ 0, with a = (1 − π)OPT/rLR and x = OPT − ηK (P, O). In particular, it remains valid for π = 0 and for ηK (P, O) > OPT. Under perfect predictions, P = O for some optimum, and NAIVE accepts every member of P and no other request. It therefore gains OPT. This yields the stated uniform consistency bound; the LR term yields the uniform robustness bound. For matching lower bounds, take finite unlabelled inputs whose LR ratios tend to its exact worst-case ratio rLR . Labelling one optimum positive gives Naive reward OPT without changing LR, and hence mixture ratios tending to C π . Labelling every request negative instead gives Naive reward zero and ratios tending to Rπ . L.2. A fixed-input lower bound for randomized algorithms A different, elementary bound shows a uniform separation from consistency one at every fixed robustness budget. Define 1 Lexp (B) = √ , 2 1 − B −1 − (1 − B −1 )

B ≥ 4/3.

Proposition L.2 (A two-input randomized lower bound). Every randomized algorithm in the fixed-input expected-gain model has Rexp ≥ 4/3. If Rexp ≤ B < ∞, then Cexp ≥ Lexp (B) > 1. Both inequalities use inputs with only three requests. In particular this lower bound is valid for an oblivious adversary. Proof. Fix v ≥ 1. The following two inputs have the same labelled prefix: A = [0, 1), p(A) = 1;

N = [1/2, 1/2 + v), p(N ) = 0.

The first input ends with D = [1, 1 + v) labelled positive. The second ends with L = [−1/2, 1/2) labelled negative. All conflicts have positive overlap. Both optima have weight v + 1: the first is uniquely {A, D} and has perfect predictions; the second is uniquely {N, L} and does not. These inputs and their stopping points are fixed before the algorithm draws its coins.

51

Optimal Consistency for Interval Selection

Let p be the probability that A is still held after the common prefix. Coupling the two executions on the same random tape gives the same value of p. If A is held, the respective final rewards are at most v + 1 and 1. If it is not held, no recall permits it to return, and the rewards are at most v and v + 1. These bounds also cover an empty held set and voluntary revocation. Consequently E[ALG+ ] ≤ v + p, E[ALG− ] ≤ v + 1 − vp. For v = 1, their sum is at most 3, whereas both optima are 2; therefore robustness is at least 4/3. Write c = Cexp and assume Rexp ≤ B. The consistency guarantee on the first input and robustness guarantee on the second imply v+1 (v + 1)(1 − B −1 ) −v ≤p≤ . c v Thus, for every v ≥ 1, v 1 − B −1 1 ≤ + . (L.2) c v+1 v √ Set t = 1 − B −1 ∈ [1/2, 1) and v = t/(1 − t) ≥ 1. The right side becomes 2t − t2 , proving the claimed bound. Since t < 1, this number is strictly less than one. The bound is tight for this two-input family, including its stopping prefixes. At the displayed v = t/(1 − t), accept A, retain it at N with probability t, and otherwise replace it by N . At D, take A + D when A survived and obtain v otherwise. At L, retain A when it survived and take N + L otherwise. The two final expected rewards are v + t and v + 1 − vt, giving F F exactly (Cexp , Rexp ) = (Lexp (B), B) for the restricted family F of these two inputs and their two distinct nonempty proper prefixes. The prefix after N has expected reward 2t and ratio v/(2t) = 1/(2(1 − t)) ≤ B; the first prefix has ratio one. Corollary L.1 (An unattained randomized consistency infimum). Among randomized algorithms with finite Rexp , the infimum of Cexp is one and is not attained. Proof. Every feasible reward is at most OPT. The initial mixtures have finite robustness and consistency tending to one as π ↑ 1, while Proposition L.2 excludes equality at every finite budget. L.3. What changes under adaptive or runwise guarantees An adaptive-offline adversary chooses each next labelled request and the stopping point from the observed past requests and retained sets, without seeing future random bits, and compares the result with the offline optimum of the realized history. Its expected robustness criterion is E[OPT(σ)] ≤ B E[ALG(σ)] for every such finite adversary. Here σ is random. Proposition L.3 (The initial mixture is not adaptively robust). For every 0 < π < 1, the initial mixture Mπ has infinite expected robustness against adaptive-offline adversaries. Proof. Offer one negative interval [0, 1). Naive rejects it and LR accepts it, so the observed retained set reveals the chosen algorithm. If it was accepted, stop. Otherwise offer one more negative interval [2, 2 + H) and stop. Naive rejects that request as well. Thus E[ALG] = 1 − π, E[OPT] = 1 + πH. The ratio is unbounded as finite H increases. Each adversary uses at most two requests and no future coin information. Even on a fixed one-request negative input, the mixture has zero reward with probability π. Hence its expected-gain bound cannot be interpreted as a finite per-run ratio with failure probability less than π.

52

Optimal Consistency for Interval Selection

L.4. Finite-tree transfer of the lower bounds The deterministic lower bounds do extend to randomized algorithms required to satisfy both stated ratios almost surely on every fixed input. To see this, take a finite deterministic adversary tree proving that a pair (c, B) is impossible. It has finitely many terminal input sequences. If both ratios held almost surely on each fixed sequence, the intersection of those finitely many probability-one events would still have probability one. A tape in that intersection defines a deterministic causal rule that survives the entire tree, a contradiction. This argument does not extend to ratios of expected gains: distinct leaves can offset one another in expectation. Ben-David et al.’s adaptive-offline derandomization theorem addresses a single comparison criterion. With two criteria, perfect and imperfect terminal histories carry different target factors. Adaptive robustness covers every adversary, whereas adaptive consistency covers adversaries whose every terminal history has perfect predictions. These separate requirements do not supply the mixed-terminal comparison needed to transfer the deterministic frontier to expected adaptive guarantees. L.5. Almost-sure robustness with expected consistency Fix the complete input, including termination, independently of the coins. The hybrid requirements are Pr{OPT(σ) ≤ BALG(σ)} = 1

for every fixed finite labelled σ,

and OPT ≤ Cexp E[ALG] on perfectly labelled inputs, without an additive term. The finite-tree transfer in Appendix L.4 requires both guarantees almost surely. Proposition L.4 (A necessary hybrid budget bound). Every almost-surely B-robust algorithm, for finite B > 1, satisfies Cexp ≥ 2 +

1 . B−1

Proof. Put s = 1 − 2δ. Present a negative unit interval J = [0, 1), then positive tiles partitioning [δ, 1 − δ), each of length less than 1/B, then a positive interval L = [δ − t, δ). Choose t > δ, s + t > 1, and t < s/(B − 1). The input either ends there or continues with the positive unit interval U = [1 − δ, 2 − δ). Both complete positive sets are optimal, of weights s + t and s + t + 1 respectively. At the first tile on which the algorithm abandons J, its available reward is at most that tile’s length, whereas the prefix optimum is at least one. Almost-sure robustness on each of these finitely many prefixes therefore forces it to keep J and reject all tiles. On the fixed input ending at L, accepting L would give (s + t)/t > B, so this action has probability zero. By causality the same holds on the fixed longer input. There its final reward is at most one, since all tiles and L are irrecoverable and J conflicts with U . Hence Cexp ≥ s + t + 1. Let δ ↓ 0 and t ↑ s/(B − 1), retaining the strict inequalities. The bound is exact for the original single-anchor/two-terminal family when B ≥ 3. For 0 < t ≤ 1, accepting L with probability p gives maximal expected rewards 1 − p + pt and 1 + pt. When both actions are legal, p = 1/(1 + s) equalizes the two ratios at 1 + s. Below t = s/(B − 1) only rejection is legal, giving 1 + s + t; for t ≥ 1, accepting always gives a ratio at most 1 + s. These responses protect every prefix of this family for B ≥ 3. Taking suprema gives 2 + 1/(B − 1). At the original t = α, the balanced ratios tend to two. Limits of mixing the stated deterministic policies. Let α = 1/φ and d = φ2 . There is a common perfect-input obstruction to initially mixing SG, LR, and the stated SUM/Credit policies. Take 0 < t < α and 0 < δ < min{t, 1/4}. Start with a negative unit anchor [0, 1), then positive tiles partitioning [δ, 1−δ), each shorter than α. Next issue L = [δ−t, δ) and U = [1 − δ, 2 − δ). All these policies retain the anchor until U ; after U their gain is at most one. The positives tile the whole request hull, of length 2 − 2δ + t → d as t ↑ α and δ ↓ 0. The same input therefore precludes consistency below d for every initial mixture of these policies. The strict inequality t < α removes the complementarity present at t = α. Proposition L.5 (Sharp guarantee for a safe action family). Consider a policy that accepts empty-conflict arrivals, accepts whenever w(I) ≥ 4w(D), and otherwise may accept only when I is positive, all conflicts are negative, and w(I) ≥ w(D)/2. An acceptance replaces exactly D; a rejection changes nothing. Its choice within this last action set may be randomized and depend on the history. Every execution satisfies OPT ≤ 18 ALG. The coefficient 18 is sharp uniformly over this action family, also after permanent feasibility filtering. 53

Optimal Consistency for Interval Selection

Proof. Label ordinary and empty-conflict acceptances M, and other acceptances S. Every M node has child mass at most one fourth of its length. Every S node has only negative, hence M, children, with mass at most twice its length. Every rejection has nonempty D and w(I) < 4w(D). Theorem J.1 applies with (β, λ) = (2, 4): qS = 6 and all three terms defining K equal 18. For sharpness, fix 0 < ϵ < 1/8 and offer J X Y Z P

0 0 0 0 1

[0, 1), [2ϵ − 4, ϵ), [1 − ϵ, 5 − 2ϵ), [ϵ, 1/2 − ϵ), [1/2 − ϵ, 1 − ϵ).

The rules force retention of J through Z: each subsequent negative request overlaps J and has length below four. The final request P has length 1/2 and is eligible for special acceptance at equality. On the accepting execution, ALG = 1/2. The compatible requests X, Z, P, Y tile the entire request hull, so OPT = 9 − 4ϵ and the ratio is 18 − 8ϵ. The policy that accepts every special-eligible arrival realizes this execution for every ϵ, proving sharpness as ϵ ↓ 0. There is only one positive request, so the filter leaves the construction unchanged. Let Hp use an independent Bernoulli(p) coin at each eligible nonordinary positive arrival in this family. For every fixed p > 0, the preceding construction accepts P with probability p, so Hp and its filtered form have exact almost-sure robustness 18. This uniform sharpness does not impose robustness 18 on every policy in the action family or determine its best hybrid budget. On this input, OPT/E[ALG] tends to 9/(1 − p/2), which is below 18 when p < 1. Proposition L.6 (Fixed acceptance probabilities do not beat d). For every constant p ∈ [0, 1], the expected consistency of Hp is at least d, despite its pathwise robustness bound of 18. Proof. Write q = 1 − p. For n ≥ 2, 1 ≤ r < 4, and small ε > 0, first issue disjoint negative unit anchors Ji = [ai , ai + 1),

ai = i(1 + r − 2ε),

0 ≤ i < n.

Then issue positive tiles of length below 1/2 partitioning each [ai + ε, ai + 1 − ε), and positive intervals of length t < 1/2 crossing the two exterior anchor endpoints by ε, where t > ε. All are rejected. Finally issue, from left to right, the positive bridges Ii = [ai + 1 − ε, ai+1 + ε), 0 ≤ i < n − 1. Each has length r. The positives tile the entire request hull, so their optimal value is n + (n − 1)r − 2nε + 2t. At Ii , the untouched right anchor is still held, and the left anchor may also be held. Thus w(D) ∈ {1, 2}, and every bridge passes the special gate and strictly fails the ordinary gate. Its acceptance is exactly its independent coin outcome. Consequently E[ALG] = (n − 1)pr + 2q + (n − 2)q 2 . Taking ε ↓ 0, t ↑ 1/2, and then n → ∞ gives the consistency lower bound Hr (p) =

1+r . (1 − p)2 + pr

√ Set p∗ = 1/d = (3 − 5)/2. If p < p∗ , let r ↑ 4; then Hr (p) → 5/(1 + p)2 > d, since (1 + p∗ )2 = 5/d. If p∗ ≤ p ≤ 1/2, use r = 1: 1 − p + p2 ≤ 1 − p∗ + p2∗ = 2/d, hence H1 (p) ≥ d. At p = p∗ this is a supremum statement, sufficient to exclude every uniform consistency constant below d. For p ≥ 1/2, use a different perfect input with 0 < ε < 1/4. Start with [0, 1) negative, and finish with K = [1/4, 3/4) positive. Before K, issue positive tiles partitioning [ε, 1/4) and [3/4, 1 − ε), and the positive intervals [ε − t, ε) and [1 − ε, 1 − ε + t), where ε < t < 1/2 and all tiles are shorter than 1/2. These early positives are rejected. The positives together tile a hull of length 1 − 2ε + 2t → 2. Only K invokes a coin, yielding expected gain 1 − p/2. The limiting ratio is 2/(1 − p/2) ≥ 8/3 > d. State-dependent probabilities and correlated decisions, which remain pathwise protected within Proposition L.5’s action set, are outside this obstruction. 54

Optimal Consistency for Interval Selection

M. Same-threshold ledger ablation The ablation removes only SUM-BANK’s special ledger acceptance test, retaining ordinary priority, length thresholds, all-negative conflicts, ledger updates and irrecoverability. It measures the gate’s total effect on the resulting trajectory. M.1. A five-request explanation of the ledger test Fix λ ≥ φ3 and 0 < ε < 1/8. Reveal the following intervals in order; the subscript is the prediction: [0, 1)0 ,

[ε, 1/2)1 ,

[1/2, 1 − ε)1 ,

[−1/φ + 2ε, ε)1 ,

[1 − ε, 1 − ε + 1/φ)1 .

The four positives tile the full input hull, giving the unique optimum 1 + 2/φ − 3ε. The initial negative conflicts with each of them. Both policies reject the next three requests because their lengths are below 1/φ; none passes the ordinary gate. Immediately before the last arrival, the held length is one and the ledger is B = φ − 3ε > 1. The last positive passes the special length test at equality. Without the ledger test it replaces the negative, leaving reward 1/φ and ratio φ + 2 − 3φε −→ φ + 2 > d. With the test, it is rejected because B > 1 = φw(I), and SUM retains reward one. Permanent filtering changes no label because the positives are compatible. Thus the ablation loses the proved consistency guarantee even though its mean effect on the workloads below is small. This construction also applies to Shaped-BANK and every Credit-BANK Tc in the stated family when only its special ledger test is disabled and ledger updates are retained: throughout the prefix the sole held negative has ordinary cost at least d, whereas every positive length is at most 1/φ. Hence all ordinary tests still fail, and the same length and ledger decisions follow. The conclusion concerns only these policies with the test removed. M.2. Paired workload intervention Each of the eight conditions has 100 repetitions; within a repetition, enabled and disabled SUM gates share inputs, optima, permutations and labels. Differences are percentage points of ALG/OPT, using the separate eight-comparison bootstrap family in Appendix O. This intervention does not cover Shaped-BANK or the low-FP rates in Table 5. Table 4. Ledger ablation, 100 repetitions per condition. Win/tie/loss counts compare exact paired rewards; positive favors the enabled gate. Log

Condition

NASA NASA NASA NASA CTC CTC CTC CTC

Perfect FN .1 FP .1 FP 1 Perfect FN .1 FP .1 FP 1

Mean difference

Adjusted 99.375% CI

Win/tie/loss

0.00006 0.00000 0.01227 0.00000 0.00776 0.00406 0.54094 0.00000

[0.00000, 0.00019] [0.00000, 0.00000] [0.00238, 0.02129] [0.00000, 0.00000] [0.00297, 0.01375] [0.00064, 0.00847] [0.48731, 0.59718] [0.00000, 0.00000]

2/98/0 0/100/0 72/0/28 0/100/0 17/81/2 10/89/1 99/0/1 0/100/0

All-positive inputs make the special branch inactive, producing identical complete trajectories. On NASA FN .1, no disabled-gate veto occurs in these streams, also giving equality. The remaining comparisons include losses in individual repetitions despite nonnegative means.

N. Reward and error-bound activation Table 5 gives the reward, uncertainty and tail summaries discussed in Section 7.2. Figure 4 compares eight policies on twenty shared joint repetitions. Appendix O defines the policies, inputs and conditional uncertainty estimates. Reward comparisons. Filtered SG loses to filtered SUM on both perfect-label cells, and to raw SG on all six nonzero low-FP cells. MAX(φ3 ) beats SG at FP .1, .5 and 1 on both logs; LR is strongest among the displayed methods at those rates and at FN 1. Table 8 contains a low-FP exception to this ranking. The filtered-RP means favor SG in all 20 cells, but at CTC FP .1 the raw-RP paired interval includes zero. 55

Optimal Consistency for Interval Selection Table 5. Random-order reward, percent of optimum (20 inputs per condition). Each cell is mean+u −ℓ / q.05 : the pointwise 95% bootstrap interval is [mean − ℓ, mean + u]; q.05 is the empirical individual-run fifth percentile: the sample minimum for each deterministic method, and the weighted quantile of 40 branch outcomes for each mixture. MixC , MixB use π = α2 /2, 1/φ in Section 7 (expected consistency d, resp. robustness φ5 ); means integrate the coin. Act. counts inputs with ηK < (4 − 2φ)OPT (Appendix O). SG denotes ShapedBANK; SGF is filtered SG. These are exploratory fixed-log summaries. Log

Labels

Act.

LR

MixC

MixB

SGF

NASA NASA NASA NASA CTC CTC CTC CTC

Perfect FP 0.01923 FP 0.1 FP 1 Perfect FP 0.0034 FP 0.1 FP 1

20/20 20/20 0/20 0/20 20/20 20/20 0/20 0/20

96.83+.14 −.13 / 96.25 96.83+.14 −.13 / 96.25 96.83+.14 −.13 / 96.25 96.83+.14 −.13 / 96.25 93.27+.10 −.11 / 92.77 93.27+.10 −.11 / 92.77 93.27+.10 −.11 / 92.77 93.27+.10 −.11 / 92.77

97.43+.12 −.10 / 96.47 94.95+.14 −.15 / 85.85 91.66+.20 −.18 / 69.28 90.21+.12 −.11 / 61.36 94.55+.08 −.08 / 92.86 91.74+.15 −.15 / 84.26 84.81+.12 −.12 / 48.49 87.72+.11 −.10 / 63.87

98.79+.05 −.05 / 96.51 90.75+.36 −.37 / 85.41 80.11+.44 −.44 / 67.55 +.24 75.42−.24 / 61.00 +.04 97.43−.04 / 92.99 +.42 88.33−.39 / 83.22 +.28 65.89−.28 / 47.58 +.22 75.32−.22 / 63.43

+.09 99.10−.09 / 98.76 97.07+.11 −.10 / 96.61 94.36+.20 −.20 / 93.60 89.12+.27 −.28 / 87.84 95.58+.14 −.14 / 94.83 93.80+.16 −.17 / 92.95 89.25+.14 −.14 / 88.72 86.39+.16 −.16 / 85.68

Table 6. Mean retained reward (% of OPT; twenty shared repetitions per cell). Shaped-BANK (SG) and RP at λ = (5φ + 1)/2 share exact robustness 5φ + 3. Superscript F denotes permanent filtering. The best scalar Credit uses c∗ = 2φ − 3 and budget 4φ + 5; SUM has budget 7φ + 4; MAX(φ3 ) is a descriptive comparator. Credit at c = φ/2 is included in the full comparison tables. Log

Labels

SGF

NASA NASA NASA CTC CTC CTC

Perfect FP .1 FP 1 Perfect FP .1 FP 1

99.10 94.36 89.12 95.58 89.25 86.39

SG ScalarF 99.10 94.92 88.63 95.58 89.68 85.72

99.10 94.35 89.08 95.58 89.24 86.37

SUMF

MAX(φ3 )

99.17 92.26 88.56 95.91 87.34 85.73

98.93 96.20 93.07 95.51 90.63 89.15

LR Half(4) 96.83 96.83 96.83 93.27 93.27 93.27

99.26 93.15 89.01 97.22 86.84 86.12

RPF 98.67 91.76 88.17 92.80 87.24 85.37

Figure 5 shows activation counts 20,7,0 on NASA and 20,5,0 on CTC at the three nonzero low-FP rates; both perfect cells activate 20/20. In contrast, the main FP grid has nonpositive error branches. Scalar Credit at c = φ/2 has a different low-FP threshold and middle-rate counts 9/20 and 11/20. SG’s larger guaranteed robust floor can reduce the error-branch activation count while strengthening the worst-case guarantee. Best scalar control. Filtered SG minus filtered best scalar Credit (c∗ ; Appendix O.5) has fifteen positive means, four exact zero means and one negative mean; the range is [−0.00085, 0.03927] percentage points. At NASA FP.05769, SG minus scalar is −0.00085 with pointwise interval [−0.00946, 0.00592] and 2/17/1 wins/ties/losses. Raw differences have fourteen positive and six zero means, with maximum 0.16959 points at CTC FP.5 (interval [0.13983, 0.20048]). The workload-reward differences are small despite the strict improvement in the worst-case guarantee. N.1. Uncertainty and individual-run rewards Table 5 uses the twenty matched inputs and pointwise bootstrap protocol of Appendix O. Each input fixes the requests, order, labels and termination; mixture coins introduce no additional input replications. The mixture mean integrates the initial policy coin. Its empirical fifth percentile instead uses the forty branch outcomes with masses π/20 and (1−π)/20. For a fixed input, both branch probabilities exceed .05, so the conditional fifth percentile is min{Nr , Lr }. Averaging these conditional quantities is not the pooled quantile in Table 5. The latter can differ between MixC and MixB even though their conditional minima coincide. Explicitly, with rewards Nr , Lr as percentages of optimum, 20 1 X [π1Nr ≤t + (1 − π)1Lr ≤t ], Fbπ (t) = 20 r=1

56

q.05 = inf{t : Fbπ (t) ≥ .05}.

Optimal Consistency for Interval Selection

a

NASA / FN

b

NASA / FP

c

CTC / FN

d

CTC / FP

100

Retained reward (% of OPT)

95 90 85

100 95 90 85 0.0

0.1

0.5

1.0

0.0

0.1

0.5

1.0

Class-conditional flip probability SG filtered SG raw

MAX(φ 3 )

Credit filtered SUM filtered

Half(4) RP filtered

LR

Figure 4. Main-regime rewards: NASA/CTC rows and FN/FP columns. The eight methods are raw/filtered SG, filtered best scalar Credit, filtered SUM, MAX(φ3 ), LR, Half(4), and filtered RP at the SG robustness budget. Points are twenty-repetition means with pointwise 95% bootstrap intervals (10,000 shared resamples). Perfect labels appear in both columns; FN and FP flip different classes. The FP perfect-to-0.1 segment is omitted because the low-FP regime lies between them. Methods have different guarantee budgets; MAX is descriptive. Raw/filtered SG coincide in the FN panels, while filtered SG and scalar Credit nearly overlap at this scale.

NASA

a Mean ηK /OPT

SG threshold: 4 − 2φ

SG threshold: 4 − 2φ

1.0

0.5 Mean crossing: 0.03700

0.0

Error branch active (fraction)

CTC

b

c

Mean crossing: 0.00655

d

20/20

20/20

1.0 20/20

20/20

0.5

7/20

5/20 0/20

0/20

0.0 0

0.01923

0.03846

0.05769

0

0.0034

0.0068

0.0102

False-positive probability

Figure 5. Bounded low-FP study. Top: mean original-label ηK /OPT with pointwise bootstrap intervals; dashed line: SG’s exact activation threshold 4 − 2φ. Bottom: actual activation counts out of twenty with pointwise Wilson intervals. Dotted vertical references mark the analytic expected-error crossings, .03700 and .00655; the measured grid was fixed around the Credit crossings. Rates share nested labels and reveal orders. Mean-error crossing and realization-level activation are distinct quantities.

57

Optimal Consistency for Interval Selection

O. Shared experimental protocol and provenance O.1. Instances, policies and comparison budgets Raw/filtered SG and raw/filtered RP at λ = (5φ+1)/2 share exact robustness 5φ+3. Each uses two fixed logs, seven main conditions (perfect labels; FN or FP at .1, .5, 1), and three additional low-FP rates per log, with twenty joint repetitions, giving 400 cases. The low-FP rates are .01923, .03846, .05769 on NASA and .0034, .0068, .0102 on CTC. 3 Thirteen main-regime controls share those repetitions: raw/filtered Credit (c = φ/2), raw/filtered SUM p (λ = φ ), MAX at 3 3 φ and Λ, LR, Half(4), and five RP settings. These RP settings are φ , (7φ + 2)/2, λ0 = (B0 + B0 (B0 − 8))/4 with B0 = 8φ + 5, and raw/filtered (6φ + 1)/2. The last pair matches Credit’s budget √ 6φ + 3; (7φ + 2)/2 matches SUM’s 7φ + 4. RP at λ0 has exact robustness 2λ0 + 2, not B0 . Here Λ = (5φ + 2 + 33φ + 21)/2 ≃ 9.357715; MAX is a descriptive comparator with no claimed guarantee.

The separate SUM ledger ablation (Appendix M) uses 100 repetitions; its paired differences are computed within that study. The logs are NASA-iPSC-1993-3.1-cln (Parallel Workloads Archive, n.d.b) and CTC-SP2-1996-3.1-cln (Parallel Workloads Archive, n.d.a) from the Parallel Workloads Archive (Feitelson et al., 2014). Mirrored inputs match later official downloads; earlier download logs and original cleaning source are unavailable. Raw SWF files are not redistributed because unrestricted redistribution is not established. Mapping follows SWF (Parallel Workloads Archive, n.d.c). Each retained record gives [s, s + t) with weight t > 0 seconds. NASA uses SWF column 2 as a start-time surrogate, without adding its unknown wait −1; CTC uses s = submit + wait with known nonnegative wait. Cleaning requires eighteen columns, valid required integer fields, nonnegative start surrogate/submission and positive runtime; neither status nor processor count is a filter. All exclusions are zero-runtime records. Stable IDs are physical SWF line numbers; coincident intervals remain distinct. Table 7. Fixed workload-derived instances. Exact objectives are seconds. Quantity Data records Excluded zero-runtime records Retained intervals Exact optimum V Fixed optimal-set size (FN eligible) Complement size (FP eligible)

NASA

CTC

18,239 173 18,066 5,816,181 3,635 14,431

77,222 17 77,205 28,353,920 1,464 75,741

Integer weighted-interval dynamic programming sorts by (finish, start, id) and computes Vj = max{Vj−1 , wj + Vk(j) }, where k(j) counts earlier requests finishing no later than request j starts. A tie excludes the current request, fixing an optimum O independently of reveal order and labels. Endpoint contact is compatible. Only offline optimization and label construction use the full instance. Online methods see immutable labels one request at a time, without termination knowledge, recall or geometric expiration. This single-resource, random-reveal reduction does not reproduce queues or processor allocation. O.2. Randomization and uncertainty For each log and repetition r = 0, . . . , 19, PCG64 streams supply one reveal permutation and one uniform per stable ID. FN flips members of O to zero; FP flips its complement to one. An eligible ID flips when its uniform is below the binary64 conversion of the stored rational rate q. Rates therefore share nested labels; methods and error types share streams, so cells are not independent samples. Perfect FN/FP labels coincide. FN positives are feasible; FP positives need not be. Rewards are 100 ALG/V . The bootstrap draws 10,000 resamples of the twenty whole repetitions per log, shared across methods and conditions. Pointwise 95% percentile intervals use linear interpolation at .025 and .975; paired intervals resample within-repetition differences in percentage points. The 60 primary contrasts compare filtered SG with raw SG and raw/filtered matched RP in twenty cells. The 34 secondary contrasts compare filtered SG with filtered c = φ/2 Credit in twenty cells and filtered SUM in fourteen main cells. Forty further contrasts compare raw/filtered SG with their best scalar counterparts. The ancillary tables (see anc/README.md) give full summaries for all twenty cells and all 134 contrasts, including adverse and zero results. These bootstrap intervals and the Wilson activation intervals are pointwise 58

Optimal Consistency for Interval Selection

and conditional on the two fixed logs. The SUM ablation uses 10,000 × 100 whole-repetition resamples and quantiles .003125/.996875 for its eight-comparison family, separately from the pointwise SG comparisons. Without public preregistration, the ablation conditions, low-FP rates and c∗ were fixed before their outcomes; the eight-policy display before scalar outcomes; and the models, thresholds and independent-cohort comparisons in Appendix Q before test rewards. O.3. Original-label error and activation For original positives P and fixed optimum O, compute exactly X   ηK = w(O \ P ) + w(NO (F )) − w(F ) . F ∈P \O

Original labels define this statistic; immutable effective labels govern filtered decisions and fees. SG’s error branch exceeds its robust floor precisely when ηK /V < 1 − d/(5φ + 3) = 4 − 2φ ≃ .763932. For marginal FP probability q, E[ηK /V ] = qS, with S = 120075280/5816181 ≃ 20.6450 on NASA and S = 3309283172/28353920 ≃ 116.7134 on CTC. Credit’s threshold (4 − φ)/3 ≃ .793989 gives mean crossings .038459/.006803; SG gives .0370031776/.0065453654. The added grid surrounds both crossings below the original minimum nonzero rate .1. O.4. Policy definitions and implementation With d = φ + 1, α = φ − 1, M = 2φ + 1, SG uses negative cost min{2φv, max{dv, φv + αb}} and positive cost M v, capped per holder before summation. Breakpoints b = φv, dv and rational/golden-field comparisons are exact. Ordinary acceptance has priority; non-strict boundaries accept equality. Rejection fees use old values, and replacement inherits whole ledgers. Permanent positive history records a compatible effective positive even if subsequently rejected or revoked. Credit at c = φ/2 uses v+(v+min{v, b/2})φ for a negative holder. SUM’s ordinary test uses total conflicting length; MAX changes only this ordinary quantity to maximum conflicting length, retaining SUM’s special gates and ledger updates. LR follows Algorithm 3 of Karavasilis (2025): empty acceptance or strict x > φy, where y is maximum conflicting length. RP follows Algorithm 4: after ordinary acceptance fails, a positive arrival with all-negative conflicts must satisfy w(I) ≥ W . Half(4) changes this last test to 2w(I) ≥ W and uses ordinary parameter 4. It is an author-chosen empirical control; no RP certificate or optimal-parameter claim transfers to it. These controls use the definitions above, rather than reproducing published workload curves. An independent full-scan implementation agrees on all SG decisions and rewards; labels, errors and bootstrap summaries were separately reconstructed. Arithmetic resources. For fixed parameters of the displayed SUM, Shaped and Ta costs, a full-scan implementation uses O(n2 ) exact arithmetic operations and comparisons, and O(n) stored scalars and interval records over n arrivals. At time t, scan at most t − 1 holders to form conflicts, sum lengths, costs and ledgers, then update fees or replace records. Each displayed cost takes constant arithmetic work; fee denominators are positive on their branches. The permanent positive filter adds one scan and at most t records. Source measures and replacement forests are proof objects, not stored policy state. Parameters are exact arithmetic constants; rational inputs and rational a use rational operations, and the golden endpoint uses a fixed quadratic field. This bounds scalar counts, not their bit sizes or floating-point error; OPT computation and retained diagnostic traces are excluded. O.5. Strongest-scalar control The scalar c∗ = α3 = 2φ − 3 is the best consistent scalar endpoint, with exact robustness 4φ + 5 and cost min{M v, dv + c∗ b}. Raw/filtered scalar Credit uses the same 400 cases and bootstrap resamples as SG. Appendix N summarizes its forty contrasts; c = φ/2 remains in the full tables.

59

Optimal Consistency for Interval Selection

P. Experimental diagnostics: randomization, learned labels, and application limits A randomized control with its coin integrated exactly. Naive accepts a positively predicted request only when it is compatible with every previously accepted request, and never revokes one. The initial mixture selects Naive with probability π and LR otherwise, once before the input is processed. For each fixed input and prediction vector we report 100{π Naive + (1 − π) LR}/OPT. We use πC = α2 /2 and πB = 1/φ, with expected guarantees (C̄, R̄) ≤ (d, 2d) and (φ5 /(3φ+3), φ5 ), respectively. Inputs are fixed independently of the coin; these are expected-reward guarantees, not finite per-execution robustness bounds. In the perfect/FP .1/FP 1 rows of Table 5, the underlying Naive means are 100.00/69.78/62.18% on NASA and 100.00/48.97/64.23% on CTC. The budget-matched mixture beats filtered SG on perfect CTC labels, but loses at FP .1 on both logs; the consistency-matched mixture beats filtered SG at FP 1 on both logs. Finite binary64 decision check. With integer geometry/rewards and binary64 thresholds/ledgers, literal min/max evaluation agrees with exact breakpoint evaluation on branches, labels, final IDs and rewards for 800 SG streams (400 cases; 38,108,400 arrivals). This finite check gives no guarantee for adversarial near-boundary inputs or accumulated ledger error. A CTC submission-order diagnostic. We keep CTC’s interval geometry [submit + wait, submit + wait + runtime), fixed optimum and uniform arrays, but reveal requests in ascending submission time, breaking ties by physical-line ID. Perfect labels give one deterministic case; FP probabilities .0068 and .1 each use the twenty label streams. Both SG variants use exact arithmetic. This changes reveal order alone; the application interpretation is examined in Appendix P.2. Table 8. CTC submission-order sensitivity. Mean percentages of the fixed optimum; n = 1 for perfect labels and n = 20 for each nonzero FP rate. The initial coin is integrated for both mixture columns. Condition

Naive

LR

MixC

MixB

SG

SGF

Perfect FP .0068 FP .1

100.00 95.05 78.11

94.98 94.98 94.98

95.94 94.99 91.76

98.08 95.02 84.55

95.61 95.30 94.10

95.61 95.28 93.57

At FP .1, submission order raises filtered SG’s mean from 89.25% to 93.57%, and the budget-matched mixture’s from 65.89% to 84.55%. LR remains better than filtered SG. At FP .0068, filtering costs only 0.020 percentage points, compared with 1.276 under the random-reveal protocol. The perfect-label mixture still exceeds SG. The magnitude of these comparisons thus depends strongly on reveal order. P.1. Learned labels, structured errors, and a planted obstruction To test errors beyond independent flips, we construct separate instances from the logs. Requests are ordered by (ti , IDi ), where ti is SWF column 2 and IDi is the physical-line identifier. The 60/20/20 split starts at b.6nc, b.8nc and advances each cut past equal timestamps. Training/validation/test counts are 10,839/3,613/3,614 for NASA and 46,323/15,441/15,441 for CTC. Consecutive blocks of 512 requests form separate instances; a final block shorter than 32 is appended to its predecessor. Each block has its own canonical offline optimum, so conflicts across blocks are omitted. Its optimum uses the tie-breaking DP of Appendix O. Block boundaries, unlike split boundaries, may separate equal timestamps. There are 7 NASA and 31 CTC test blocks. These blocks are not assumed to be independent samples from a workload population. A concrete prediction pipeline. For each log, an ℓ2 -regularized logistic model learns membership in the training blocks’ canonical optima. Its seven causal features are log-duration, log-lead-time, log-gap since the preceding reveal, log-count and log-total-length of previously revealed conflicts, and two time-of-day coordinates. Logarithms use log(1 + x); lead time is si − ti . History starts empty in every block, including at split boundaries; the first gap is zero. Earlier equal-time requests enter in ID order. Conflict features include all earlier overlapping reveals in the block, regardless of labels or acceptance, and their full lengths are summed. The periodic features are sine and cosine of 2π(ti mod 86400)/86400, with no calendar offset. Training-only unweighted means and population standard deviations scale all splits, with zero deviations replaced by one. The constructed interval inputs reveal runtime at arrival; NASA’s column 2 is a start-time surrogate. See Appendix P.2 for the application boundary. 60

Optimal Consistency for Interval Selection Table 9. Held-out learned-label checks. Precision/recall pool request counts; weighted recall and ηK /OPT pool lengths. Reward rows are means of block percentages. The selected threshold maximizes validation F1, not the online objective. Quantity Precision / recall Weighted recall ηK /OPT Active error branch Shaped / filtered SUM / MAX at φ3 LR / Naive Consistency-matched mixture Budget-matched mixture Filtered Shaped, all-negative Naive, all-positive

NASA

CTC

.851/.660 .610 .577 6/7

.428/.426 .364 1.574 0/31

94.58/94.58 95.17/95.17 96.86/61.43 90.09 74.96 96.96 90.45

89.81/89.66 89.43/89.95 91.25/62.68 85.79 73.59 90.30 83.51

P Writing hi = β0 +β ⊤ zi for standardized features, training minimizes the sum of logistic losses i [log(1+exp hi )−yi hi ]+ kβk22 /2; the intercept is unpenalized. A deterministic Newton solver fits the model. Labels are 1{pi ≥ τ }. Validation pooled F1 chooses τ ∈ {.05, .10, . . . , .95}, breaking ties toward the largest threshold and giving .35 and .20; neither test data nor online reward is used for tuning. Fixed .5, explicit all-negative/all-positive and perfect-label controls are also reported. Both constant controls outperform their corresponding learned-label policies in Table 9. Fixed threshold .5 gives 94.88/89.90% for filtered Shaped, and perfect labels give 97.61/96.58%. Validation F1 need not select useful advice for the online objective or determine conflict-weighted error. Matched counts with different error structure. On each test block we create FP errors at target .01 or FN errors at target .1, rounding the eligible count to the nearest integer. Uniform placement, length-proportional sampling without replacement, and a cyclic consecutive burst in eligible reveal order have exactly the same error count within a block. They do not match error weight or per-request marginals. Each block and placement uses one fixed seed; the comparisons are descriptive. With 85 total NASA false negatives, uniform versus length-weighted placement changes mean ηK /OPT from .081 to .526, Naive’s reward from 91.85 to 47.41%, and Shaped’s from 97.92 to 96.71%. For CTC the corresponding numbers are .108 versus .272, 89.24 versus 72.80%, and 94.96 versus 92.86%. Bursts and FP placements give different rankings; the ancillary tables (see anc/README.md) list all 228 cases, including unfavorable comparisons. Embedding the zero-error construction. We instantiate the distinct-geometry family with δ = 1/100, three central groups, eight alternatives per group, and rational boundary parameter 16/5 < 2φ. Its 27 requests have OPT = 147/20, raw Shaped reward 1, and ηK = 0. A spatially disjoint scaled copy is embedded into the first test block of each log, whose background labels are perfect. The witness supplies a fraction a ∈ {0, 1/4, 1/2, 9/10, 1} of total optimum; its requests retain their adversarial order. At a = 1/2, raw/filtered Shaped give 56.46/93.05% on NASA and 55.12/91.72% on CTC. At a = 1, raw Shaped, SUM and MAX give 20/147, filtered Shaped and LR give 638/735, and Naive is optimal. The error remains zero, although the positive set is infeasible. This explains the filter’s role on this proved construction. Decisions and ledgers use exact rational/golden arithmetic; mixture coins are integrated analytically. P.2. Decision-aligned labels and the application boundary We keep the split, seven features and linear-logistic capacity of Appendix P.1, but align training and threshold selection with decision costs. This secondary design was chosen after test-block inspection. It uses weighted logistic training, motivated by prediction versus decision loss (Elmachtoub & Grigas, 2020), rather than SPO+ or its guarantee. A cost target tied to the error. For a training block with optimum O of value V , assign cost ( wi /V, i ∈ O,
ci = w(NO (i)) − wi /V, i ∈ / O.

61

Optimal Consistency for Interval Selection Table 10. Secondary objective-alignment diagnostic. Entries are mean block percentages for filtered SG on the same 7 NASA and 31 CTC test blocks. Reward selection uses only validation blocks. Threshold 1 gives all-negative labels on these scores. Condition

NASA

CTC

Ordinary score, F1-selected Ordinary score, error-selected Ordinary score, reward-selected Cost score, F1-selected Cost score, error-selected Cost score, reward-selected

94.58 93.71 96.96 93.13 94.91 96.96

89.66 90.30 90.30 90.21 90.30 90.48

All-negative Perfect labels LR (ignores labels)

96.96 97.61 96.86

90.30 96.58 91.25

P Then i ci 1{bi 6= 1i∈O } = ηK (b, O)/V . In addition to the ordinary-logistic score, we fit a score using ci -weighted binary log loss, globally rescaling Ptraining costs to mean one and retaining the same L2 coefficient 1 on the summed loss. Thus the loss weights are mci / j cj for m training requests. Zero-cost negatives have zero loss weight but remain in the unweighted training standardization. Only the cost model is fitted anew, using the same solver and an additional final gradient infinity-norm check below 10−5 . Such a cost score is not an ordinary calibrated membership probability. Neither does minimizing ηK maximize retained reward. Each score uses the 21 validation thresholds 0, .05, . . . , 1; the endpoints give all-positive and all-negative labels on the evaluated inputs. Explicit constant controls are retained. Selection maximizes pooled F1, minimizes mean block ηK /V , or maximizes mean block filtered-SG reward; ties choose the largest threshold. Together with fixed .5 thresholds and negative/positive/ perfect controls, this gives 11 conditions for each of the eight policies. Reward selection chooses all-negative advice for both ordinary scores and the NASA cost score. Their improvement over F1 therefore cannot be credited to learning. The CTC cost score selects .30 and gains .1802 percentage points over the constant: 3 blocks improve, 27 tie and 1 worsens. The leave-one-block-out mean range is [.1018, .1991] points, a sensitivity range, not a confidence interval. Its mean remains .7690 points below LR. The ancillary tables (see anc/README.md) list all twelve paired contrasts, including adverse results. The error-oriented NASA score reduces pooled ηK /V from .5767 to .4838 and makes the error branch active in all seven blocks rather than six, yet gives lower reward than the all-negative control, whose error branch is inactive. Error informativeness and empirical utility are thus distinct diagnostics. The CTC reward-selected cost score reduces pooled error from 1.5735 to .9501, activates the error branch in only 4 of 31 blocks and produces four special admissions. These results support objective sensitivity, not a claim that objective mismatch is the sole reason for the ordinary predictor’s failure. Feasibility and boundary context. Permanently projecting each positive through the existing causal Naive filter gives feasible immutable labels. Raw SG on those labels exactly equals filtered SG on the original labels in every evaluated case, verifying the wrapper identity. Feasibility does not resolve future membership ambiguity: the first offer [0, 1) has identical observed features whether the input stops or later reveals [0, 2), although its optimal membership differs. An immutable feasible positive history cannot retain both overlapping offers. We also concatenate each test tail, recomputing its optimum and causal features without internal resets while keeping all learned coefficients, standardization and validation thresholds fixed. History still starts empty, with first gap zero, at the test boundary. NASA’s sum of block optima is 1,054,070, compared with continuous optimum 1,032,493; CTC’s corresponding values are 16,376,035 and 6,390,734. There are 357/152,107 cross-block overlap pairs and 64/1,041 canonical label changes. Hence the blocks are substantively different constructed problems, particularly for CTC. Continuous-tail reward-selected cost SG gives 97.16/94.03%, versus 97.26/94.95% for LR; the CTC margin over constant-negative SG is only .0182 points. This jointly changes feature context, labels, geometry and normalization, so it does not isolate a boundary effect. What these inputs mean for an application. Prefix-invariant features are causal only given known interval endpoints. SWF distinguishes realized runtime from requested time (Parallel Workloads Archive, n.d.c). NASA substitutes start times for unavailable submissions (Parallel Workloads Archive, n.d.b); CTC’s actual waits and runtimes are retrospective 62

Optimal Consistency for Interval Selection

observations (Parallel Workloads Archive, n.d.a). Under the chronological interpretation, ordinary-F1 filtered SG revokes 58/58 previously started NASA intervals and 20/263 previously started CTC intervals. These are simulated revocations in historical traces. A real reservation interface can specify start and duration while disallowing deletion during running jobs (SchedMD, n.d.). Thus a sufficient model interpretation is a provisional planning batch completed before any service starts; interleaved execution needs additional constraints and analysis. The current data do not validate that application. A valid application test needs complete offers, original reveal times, then-available features and permission for the algorithm’s actions. Completed-service records and these adjacent-block comparisons establish neither that match nor improvement over LR.

Q. Forecasting the effect of an advice bit An alternative to optimal-membership prediction is to estimate how the current advice bit affects final retained length. This interface specializes fixed-reference rollout (Tesauro & Galperin, 1996) to BANK. It preserves arbitrary-bit robustness, with accuracy measured by conditional reward contrasts. The conditional target. Consider a finite horizon with possibly earlier random termination and integrable terminal rewards. The exogenous offer process is independent of the algorithm’s choices. A state s contains the observed history, time, held set, ledgers, permanent filter history, and any reference memory. Fix a deterministic pure causal bit rule A, defined at every reachable counterfactual state. Let QA (s, b) be expected final length after using bit b now and following A thereafter, under the true conditional future-offer and stopping law. Define ∆A (s) = QA (s, 1) − QA (s, 0). A paired estimate replays the same hypothetical suffix under both current bits, with each branch continuing A from its own state. The deployed controller ν recomputes this estimate at each arrival and chooses its sign; ties may use A(s). Hypothetical suffixes must not be the test episode’s realized future. Historical samples alone also do not certify that their conditional law matches deployment. Why immediate retained value is insufficient. An advice bit can change a ledger even when both current actions reject the request. One reachable example begins with a negative [0, 1), followed by positive intervals [−.6, .01), [.01, .5) and [.5, .99). All three are rejected, leaving the unit holder with ledger 1.59. At I = [.99, 1.6) both bits again reject; bit one raises its ledger to 2.20. Now offer the negative [0, 2.8). The smaller ledger permits replacement, while the larger one prevents it. A final negative [1, 4) gives branch rewards 2.8 and 4; replacing that final offer by [3, 6) gives 5.8 and 4. The bit contrast is therefore 6/5 or −9/5 despite identical immediate reward and identical suffix lengths. The positive intervals are compatible, so filtering does not erase the example. It diagnoses information that the interface can use; it is not a performance comparison of policies started from empty state. Proposition Q.1 (Expected transfer of a reference certificate). Let YA , Yν be final rewards of the reference and deployed b A , suppose the quantities controllers, both using filtered Shaped-BANK from empty state. For an estimated contrast ∆ below are integrable and put X b A (st ) − ∆A (st )|. εroll = Eν |∆ t

Let ηA be the error in (K.1) of the raw labels produced by A on its own trajectory. Then   EOPT EOPT − EηA , EYν ≥ max − ε . roll φ5 d

(Q.1)

Proof. The finite-horizon performance-difference identity (Ross & Bagnell, 2014, Lemma 4.3) gives X EYν − EYA = Eν (ν(st ) − A(st ))∆A (st ). t

b A ≥ 0 and |ν − A| ≤ 1, so each summand is at least −|∆ b A − ∆A |. Apply Corollary K.1 The sign rule satisfies (ν − A)∆ to A’s own trajectory. Independently, arbitrary-bit robustness applies pathwise to ν, giving the other branch of (Q.1).

63

Optimal Consistency for Interval Selection Table 11. Fixed all-negative-reference attribution cohort: six Context trials and 384 test episodes. No-MC columns use certified finite expectations on the same models and episodes as the 128-suffix column. Retained and revoked lengths are in the original interval units; the primary paired outcome is retained length.

Method Conditional Pooled Uniform Known law Myopic All negative

128 suffixes % OPT

No MC % OPT

No MC Retained

No MC Revoked

94.334 94.474 94.143 94.660 — —

94.817 94.458 94.423 94.665 90.652 87.297

13.76302 13.68750 13.68229 13.74740 12.91667 12.45573

4.86719 4.91406 4.66406 4.89063 2.45313 .83333

The error is measured on ν’s visited states, not on a fixed archive of reference states; it includes scenario-model and sampling error. The member-label error ηA belongs to A, not to ν. Exact conditional contrasts remove εroll , but do not turn rollout bits into perfect membership predictions or supply a per-execution consistency-d guarantee. With an all-negative reference, ηA = OPT and the second branch is vacuous. Thus a good causal reference is a substantive part of this interface. Q.1. Complete-policy diagnostics We use two fixed synthetic offer laws, with all policies starting empty. The 16 interval types combine starts {0, 3, 6, 9} and lengths {1, 3, 6, 12}. Initial types are uniform; episodes stop with probability .1 after each offer and are capped at 24 offers. IID transitions are uniform. In the Context law, an observed binary context is fixed for each episode. Given current type i, next-type weights are 1 + 41{j compatible with i} + 21{wj ≤ 3} in context zero and 1 + 41{j contains i} + 21{wj ≥ 6} in context one. Both laws have full support. Laplace-smoothed counts fit conditional or pooled transitions; fitted stopping accounts for censoring at the cap. Learning versus lookahead. The original attribution study used six independent Context training trials and two IID controls, each with 2,048 training and 64 fresh test episodes. Every method continues with the all-negative reference after the current advice bit. Conditional, pooled and uniform models differ only in their future laws; uniform learns no transitions and knows the specified stopping rate. A known-law control knows the generator but never the realized future. The original Monte Carlo comparison used 16/128 common-random-number suffixes; the finite-expectation analysis below reuses its fitted models and test episodes. Finite-state recursion evaluates the 512 test episodes (384 Context, 128 IID) through the remaining horizon. Outward bounds certify nonzero contrast signs under the sampler’s 53-bit law, and exact rational recursion certifies the remaining 26 zeros. On the 384 Context episodes, conditional minus uniform gains .08073 in mean retained length and .3943 percentage points in mean ALG/OPT (13 wins, 365 ties, 6 losses). Four of six trial length differences are positive and two negative. Uniform minus myopic gains .76563 length and 3.7711 points. Conditional minus pooled gains .07552 length and .3596 points, compared with −.1409 points using 128 suffixes. Sampling precision therefore affects this cohort’s comparison. In all 128 IID episodes, the four no-Monte-Carlo laws have identical terminal values, averaging 95.4432% of OPT. These reused-test results are descriptive; Table 12 reports an independent cohort. Independent cohort. The independent cohort used 24 Context and eight IID training trials, each with 2,048 training and 64 test episodes under the same generator, fitting rules, all-negative reference and finite-expectation evaluation. All seven policies started empty; a swapped control exchanged the fitted context rows. The primary contrast was conditional minus uniform length, averaged within training trial (Table 12). Secondary intervals are descriptive and unadjusted for multiplicity. The primary trial means split 11 positive, three zero and ten negative (22 episode wins, 1,496 ties, 18 losses). Its interval confirms neither a positive mean gain nor a zero effect; the earlier six-trial positive cohort remains separate. Uniform minus myopic gains 2.0836 percentage points in mean ALG/OPT (descriptive 95% interval [1.5439, 2.6234]). Conditional/pooled/uniform mean test negative log-likelihoods per opportunity, averaging trials equally, are 2.630468/2.772968/2.818286: better future-law fit does not establish added terminal reward. In the eight IID trials, 64

Optimal Consistency for Interval Selection Table 12. Independent Context cohort: 24 training trials and 1,536 test episodes. Differences are in retained-length units; Student-t intervals use 23 degrees of freedom. Episodes sharing a fitted model are not independent training replications. Predeclared comparison

Mean difference

Trial-level 95% interval

+.003255 −.010417 +.024740 +.462891 +.019531

[−.041704, +.048214] [−.053072, +.032239] [−.033268, +.082747] [+.375407, +.550374] [−.019780, +.058843]

Conditional − uniform (primary) Conditional − pooled Conditional − swapped Uniform − myopic Known law − uniform

conditional minus uniform is −.007813 length, with 95% interval [−.049707, .034082]. Earlier cohorts and interpretation. Earlier exploratory cohorts used four fitted training trials per law and separate test episodes. They do not provide uniform learning gains: with an all-negative reference, fitted Context rollout averaged 92.83% versus uniform’s 94.36%, and increasing suffixes from 16 to 128 lowered another fitted Context mean from 95.44% to 94.98%. A learned-reference diagnostic instead fit A from context, type and index bin with Laplace smoothing and threshold 1/2. Its error branch was active in 134/256 episodes; rollout improved every trial mean over A, but fitted-minusuniform averaged −.25/ + .13 points in IID/Context. The earlier cohorts’ shared fitted models and different references preclude pooling with the cohorts above. The known-law controller is not optimal continuation: it follows its fixed reference in hypothetical suffixes and replans at the next actual arrival. All tables average episode ratios, not EALG/EOPT in the certificate. Cancellation is material: in the attribution cohort, mean revoked length is 2.4531 for myopic, 4.6641 for uniform and 4.8672 for conditional rollout; in the learned-reference cohort it rises from 1.70/1.85 for A to 4.39/4.16 with fitted-law rollout. On the original attribution cohort’s fixed Context trajectories, subtracting a proportional fee c per revoked length gives conditional minus uniform mean net reward (31 − 78c)/384. It stays positive throughout the unchanged algorithm’s fee domain 0 ≤ c < 1/(2φ); the six trial differences remain four positive and two negative. This does not hold across all environments: the IID rolloutminus-myopic mean is (63 − 245c)/128, which turns negative above c = 9/35 within that domain. This is retrospective accounting in original length units, with no new samples or fee-aware reoptimization. On the new fixed Context trajectories, charging c per revoked length gives conditional minus uniform mean net reward (5 − 190c)/1536 and uniform minus myopic (711 − 2887c)/1536. Their sign changes at 1/38 and 711/2887 both lie inside 0 ≤ c < 1/(2φ). Thus the original cohort’s positive conditional-minus-uniform net difference throughout that domain does not extend to this cohort. These studies do not estimate deployment-state error in (Q.1), and matched suffix counts do not equalize inference costs.

R. Further model comparisons R.1. Further related models and source scope Guarantees in the same model. The extended version of Karavasilis (2025), Theorem 3.5, proves proportional-weight Naive; Appendix K.1 gives our self-contained proof. The proceedings, Section 4, Algorithm 3 and Lemma 4.5, give LR’s maximum-conflict rule at parameter φ with competitive ratio at most 2φ + 1, attributed there to Garay et al. (1997). Section 1 cites the stopping-prefix antecedent and finitely robust 1-increasing barrier. The latter uses α = 1: for α < 1, its construction need not force rejection, since the internal request has length v − 2ϵ > αv when ϵ < (1 − α)v/2. The matching prediction-free lower bound is Theorem 1 in Section 2 of the October 28, 1995 author manuscript of Tomkins (1995). It allows preemption of infinite-duration calls on a line, with length rewards paid only to calls retained at termination. Represent a route from i to j by [i, j): shared-edge conflict, endpoint compatibility, length reward, and permanent rejection or preemption agree with our model. Fix every prediction to zero. Any deterministic algorithm here then induces a prediction-free algorithm on this subclass, so R ≥ 2φ+1. No request expires, and arbitrary stopping prefixes are allowed. This is a supremum lower bound, not a claim that a finite witness attains equality. Relation to earlier charging arguments. For the unweighted 2k guarantee, Borodin & Karavasilis (2023, Section 3, Propositions 1–2) charge optimal intervals to holders and transfer charges through replacements, separately bounding two

65

Optimal Consistency for Interval Selection

direct and at most 2k − 2 transferred charges. We retain this device, adding cost-weighted ancestry antichains and the twocut functional FJ (x, y) to bound the remaining geometric gap and both exterior charges jointly under special, potentially length-decreasing replacements and nonconstant ledger costs. Prediction and decision interfaces. Our bits refer to one fixed final optimum, with deterministic robustness for every fixed label sequence. In contrast, Dallot et al. (2026, Section 2) use answer-dependent guidance whose replacement by adversarial guidance is selected independently at each step. TrustGreedy of Boyar et al. (2026) maximizes cardinality using an upfront prediction of the full input set; it revises a planned solution while preserving irrevocably accepted requests. Li et al. (2026) study unit-length, unit-profit simple chains under random and adversarial orders, including complexity with a trustworthy advice tape. Several adjacent guarantees allow different decisions. Daneshvaramoli et al. (2025, Theorems 4.1 and 5.2) mix fractional knapsack decisions from critical-value predictions; their integral conversion assumes bounded unit values and sufficiently small item weights. It addresses a capacity constraint, not interval conflicts. Grigorescu et al. (2025) use real packing decisions, advice interpolation and a quantified feasibility relaxation. Scheduling with partial size predictions permits rate sharing and resumption (Benomar & Perchet, 2024); paging permits reloads and a consumable, resettable relative prediction budget (Chen et al., 2026). These mechanisms differ from BANK’s inherited positive mass and permanent rejection. The request-prediction framework of Ameli et al. (2026, Section 1, Theorems 1.1–1.2) uses irrevocable covering decisions, feasibility under unions, and subadditive costs. Feasible interval selections need not remain feasible under unions, so that covering guarantee does not directly transfer. Weights, order, and source versions. The technical version of Berg (2025), Corollary 36, treats unit profits, irrevocable decisions and bounded overlap t, with 1 ≤ α ≤ t and decision bit 0 denoting acceptance. Splitting length-weighted intervals into unit requests can change feasibility, prediction identities and available online decisions, so it does not transfer that guarantee. Antoniadis et al. (2026) use membership bits and length weights, but require release-time order and irrevocable selection; their guarantees involve additive terms, length ratios or randomization. Our results instead use arbitrary order and strict ratios. Berg and Boyar are compared through their public technical versions; the simple-chain source is arXiv:2608.10376v1, and the paging and concave-packing sources are arXiv:2606.01342v3 and arXiv:2411.08332v1. Advice, learning, and randomization. The Pareto viewpoint for trusted and untrusted advice precedes this work (Angelopoulos et al., 2020); Mitzenmacher & Vassilvitskii (2020) survey prediction-based algorithms. Khodak et al. (2022) learn predictors through algorithm-dependent quality measures, without directly supplying a guarantee for our membership interface. Theorem 2.1 of Ben-David et al. (1994) derandomizes against adaptive offline adversaries in a request-answer model. Our mixture instead fixes the complete labelled input before randomization, with consistency and robustness suprema over different input classes; that theorem alone does not yield an adaptive two-criterion extension. Immediate service and learning. Capacity-constrained online learning loses delayed feedback when a tracked round is abandoned (Ryabchenko et al., 2025); its regret objective depends on which observations survive. Our duration guarantee does not imply a learning-regret bound. Wang et al. (2026) study no-buffer scheduling with abandonment and censored reward feedback. Their general objective uses task rewards, not occupied duration. With one machine, arrival times bi , known lengths ℓi , rewards equal to ℓi , and time to finish the final accepted jobs, the intervals [bi , bi +ℓi ) form a start-ordered subclass of our model. Completed jobs can remain in the held-set record because later arrivals cannot conflict with them. Our upper guarantees therefore apply to this restricted case; our full-class lower bounds and their bandit regret bounds do not transfer between the two models. Earlier scheduling and nearby tradeoffs. Early interval scheduling includes Lipton & Tomkins (1994) and Woeginger (1994); the latter rewards completion of fixed-start/end jobs started at arrival and lost if aborted, rather than terminal heldset rewards. Seiden (1998) improves the randomized guarantee in this start-ordered setting, distinguished from any-order selection by Borodin & Karavasilis (2023, Section 1); its guarantees do not replace LR for arbitrary order. Fung et al. (2012) randomize initially between two deterministic schedulers; arrival order and completion rewards prevent transferring their constants. Jin & Ma (2022) prove a tight two-stage matching tradeoff where naive coin interpolation can be suboptimal for vertex weights. Its advice/hindsight ratios and irrevocable batches do not give an interval lower bound. Antoniadis et al. (2020) robustify metrical-task and line-matching predictions through different states and interfaces. Nair et al. (2021) learn MIP partial assignments and branching decisions. 66

Related documents

• Online Interval Selection with Binary Predictions: Optimal Consistency and a Continuous Robustness Tradeoff#1468965
• Generalizing Beyond Suboptimality: Offline Reinforcement Learning Learns Effective Scheduling through Random Solutions#1035314
• AUGUSTE: Online-Learning dApp for Predictive URLLC Scheduling#259409
• Web Services ReliableMessaging v1.2 (2009-02-01)#600962
• DaCe-DT: Data-Centric Offline Multi-Task Reinforcement Learning via Adaptive Prompts and Trajectory Correction for Heterogeneous Tasks#1248012