Introduction
Online bipartite matching asks how much of an optimal allocation can be recovered when one side of the graph is revealed over time. For unweighted matching, the Ranking algorithm of Karp, Vazirani, and Vazirani [13 ] achieves the optimal competitive ratio 1 − 1 / e 1 - 1/e 1 − 1/ e . The same ratio is attainable when weights belong to the offline vertices [1 ] . With arbitrary edge weights and no free disposal, an early assignment can prevent an arbitrarily more valuable later assignment. Free disposal allows each offline vertex to retain its most valuable assigned edge. This is a natural model for display advertising, where an advertiser may receive several impressions but pays only for its most valuable assignment [7 ] .
Even with free disposal, the greedy 1 / 2 1/2 1/2 guarantee resisted improvement for more than a decade. Fahrbach, Huang, Tao, and Zadimoghaddam [6 ] broke this barrier with a 0.5086-competitive algorithm and introduced online correlated selection (OCS). Gao et al. [GHH+22] obtained a 0.519 guarantee, and Blanc and Charikar [2 ] introduced multiway OCS and obtained 0.5368. The OCS viewpoint separates two tasks. A sampling rule chooses the candidates for the current arrival, and a selection procedure chooses one integral assignment from those candidates. Correlating the selections across arrivals can make repeated requests to a vertex more effective than independent rounding.
For weighted matching, however, a vertex is not simply covered or uncovered. An edge of weight w w w can help at every level below w w w and at none of the levels above it. A useful selection process must therefore work for many overlapping subsequences of arrivals. Moreover, arrivals outside one such subsequence still advance the process. A competitive analysis must account for these changes of state without charging them to matching gain at that threshold.
We address this issue by keeping the state distribution in the dual analysis. This removes a restriction in the earlier reduction that limits the benefit of sampling many candidates.
Our results
The offline side L L L of a bipartite graph is known in advance. Online vertices arrive in an arbitrary fixed order and reveal their incident nonnegative edge weights. Each arrival is assigned to at most one offline vertex. An offline vertex may receive several assignments; only its heaviest assigned edge contributes to the objective. The benchmark OPT is the weight of a maximum matching in the entire input graph. The input is fixed independently of the algorithm’s random choices. Missing edges may be treated as zero-weight edges; an assignment to one is implemented by discarding the arrival.
Theorem 1. There is a randomized 0.556195-competitive algorithm for edge-weighted online bipartite matching with free disposal. For every finite input graph and every fixed arrival order,
E [ A L G ] ≥ 0.556195 O P T . \mathbb{E}[\mathrm{ALG}] \ge0.556195\ \mathrm{OPT}. E [ ALG ] ≥ 0.556195 OPT . For rational input weights, the algorithm has a finite implementation with expected polynomial running time, with fixed preprocessing depending only on the constant in the guarantee.
The graph-independent preprocessing is large. § 7 gives the constants and their certificates. § 4 gives the finite algorithm, its stored state, and pseudocode for both sampling and assignment. The verification programs and Lean sources are available in the artifact repository.3 Appendix § 12 gives reproduction instructions.
The proof has two components. First, we give a state-dependent primal–dual theorem for a family of geometric-age selection processes. The process records an age: the number of steps since its most recent reset. A win map W W W assigns a desired win probability to each output of this process. Let T W T_W T W be the substochastic matrix that retains only transitions on which an auxiliary selection trial fails, and let π \pi π be the stationary age distribution. When W W W satisfies the tournament inequalities, the competitive guarantee is
γ ( W ) = 1 − 1 m + 1 ∑ n ≥ 0 ( m m + 1 ) n π T W n 1. (1) \gamma(W)=1-\frac{1}{m+1}\sum_{n\geq0}\binom{m}{m+1}^{n}\pi T_W^{n}\mathbf{1}. \tag*{(1)} γ ( W ) = 1 − m + 1 1 n ≥ 0 ∑ ( m + 1 m ) n π T W n 1 . (1)
Here m m m is the number of candidates sampled on an arrival. This expression already appears in Blanc–Charikar’s reduction [2 Theorem 7] , under additional shape and gap conditions. To see the restriction imposed by the gap condition, write F ( n ) = π T W n 1 F(n)=\pi T_W^n\mathbf{1} F ( n ) = π T W n 1 . For a map with stationary mean 1 / m 1/m 1/ m , we have F ( 1 ) − F ( 0 ) = − 1 / m F(1)-F(0)=-1/m F ( 1 ) − F ( 0 ) = − 1/ m . When γ > 1 / 2 \gamma>1/2 γ > 1/2 , the gap condition in [2 Equation (23)] requires
m ≤ 1 − γ 2 γ − 1 , or equivalently γ ≤ m + 1 2 m + 1 . m\leq\frac{1-\gamma}{2\gamma-1},
\qquad\text{or equivalently}\qquad
\gamma\leq\frac{m+1}{2m+1}. m ≤ 2 γ − 1 1 − γ , or equivalently γ ≤ 2 m + 1 m + 1 .
This upper bound tends to 1 / 2 1/2 1/2 as the number of candidates grows. Theorem 4 establishes the same guarantee for the geometric-age family without this restriction or the scalar shape assumptions. Its invariant accounts for intervening arrivals through their effect on the state distribution. Theorem 15 shows that, for maps of stationary mean 1 / m 1/m 1/ m with positive baseline, γ ( W ) \gamma(W) γ ( W ) is the exact worst-case ratio of the specified ideal algorithm. A deterministic family of triangular unit-weight graphs attains it asymptotically.
Second, we choose the win map. For fixed m m m and reset probability, Theorem 6 characterizes an optimal nondecreasing map under the necessary calibration constraint for a vertex sampled once. It assigns the same baseline score to an initial segment of ages, modifies at most one boundary age, and preserves the remaining quantile-bin scores. The map is explicit once the baseline is fixed. Proposition 9 extends this optimization to a broader class of processes with independent resets by averaging over their internal state conditional on the time since the last reset.
A vertex sampled more than once imposes further selection constraints; the optimization theorem alone does not establish these. We verify them for the map used in Theorem 1 . § 7 fixes the constants, Appendix § 9 proves the finite certificate’s sufficiency, and Appendix § 12 identifies the repository verifiers.
Related work
Online matching and free disposal. The OCS literature has developed several ways to correlate online choices while preserving feasible assignments. Gao, He, Huang, Nie, Yuan, and Zhong [GHH+22] strengthened two-way OCS and obtained a 0.519 guarantee. Shin and An [SA21] constructed a three-way OCS, obtaining 0.5093 directly and 0.5132 when combined with the improved two-way OCS. Blanc and Charikar [2 ] developed multiway OCS and obtained a 0.5368-competitive algorithm. Their reduction also showed that the original two-way formulation cannot give a ratio above 0.5239. For complete bipartite graphs with product-form weights w i j = a i b j w_{ij}=a_i b_j w ij = a i b j , Charikar, Henzinger, and Nguyen [3 ] obtained a 0.5664-competitive algorithm. That result exploits the decomposable weight structure; the theorem here permits arbitrary edge weights on arbitrary bipartite graphs. The surveys of Mehta [14 ] and Huang, Tang, and Wajc [9 ] give broader background on the models and techniques of online matching and ad allocation.
Primal–dual analysis and submodular allocation. Devanur, Jain, and Kleinberg [5 ] gave a randomized primal–dual analysis of Ranking and its vertex-weighted extension, with dual feasibility in expectation. For free disposal, Devanur, Huang, Korula, Mirrokni, and Yan [4 ] developed an analysis using a level function. The threshold decomposition in the present paper belongs to this line of work and to the complementary cumulative-distribution viewpoint used by Fahrbach et al. [6 ] . Our dual credit additionally records the joint distribution of the selection state and the event of auxiliary failure. Fractional free-disposal algorithms admit the stronger 1 − 1 / e 1-1/e 1 − 1/ e guarantee. Recent treatments include the primal–dual frameworks surveyed by Niazadeh and Udwani [NU26] and the minimax framework of Kesselheim, Molinaro, Patton, and Singla [11 ] . These fractional guarantees do not supply the integral rounding required here.
Free-disposal matching is a special case of online submodular welfare maximization: the valuation of an offline vertex for its assigned set is the maximum incident edge weight in that set. The special form of these valuations matters. Kapralov, Post, and Vondrák [12 ] rule out polynomial-time competitive ratios strictly above 1 / 2 1/2 1/2 for general coverage valuations, unless NP = RP. Udwani and Wajc [UW26] recently proved an unconditional 1 / 2 1/2 1/2 upper bound for general online submodular welfare in the standard model, where value queries involve already arrived items. Our improvement uses the maximum-weight valuation of matching; it does not extend to arbitrary monotone submodular valuations.
Overview of the Proof
A state-dependent analysis for general edge weights
From weights to coverage. For an offline vertex i i i , let M i M_i M i be the largest weight assigned to it. Its expected contribution is
E [ M i ] = ∫ 0 ∞ Pr ( M i ≥ w ) d w . \mathbb{E}[M_i] = \int_{0}^{\infty} \Pr(M_i \ge w)\,\mathrm{d}w. E [ M i ] = ∫ 0 ∞ Pr ( M i ≥ w ) d w .
Thus we can study, simultaneously for every w w w , whether an arrival of weight at least w w w has selected i i i . This complementary cumulative distribution function viewpoint is standard in weighted online matching [4 , 6 ] . It explains why negative correlation is useful: repeated opportunities above a threshold should be less likely to fail together. It also identifies the main obstacle. An arrival below the threshold does not cover it, but it can change the distribution of the next selection opportunity.
The selection process. Give each offline vertex an independent process whose state is its age since the last reset. Each occurrence of the vertex among the sampled candidates advances the process by one step, called an exposure. The age increments with probability q = 1 − p q = 1 - p q = 1 − p and resets to zero with probability p p p . A reset at age z z z produces a score W ( z ) W(z) W ( z ) , representing a desired win probability; a nonreset produces the baseline b = W ( − 1 ) b = W(-1) b = W ( − 1 ) . Write X k X_k X k for the desired win probability at step k k k . We take W W W to be nondecreasing: a longer wait before a reset gives a larger score, while a reset returns the process to age zero. This dependence between successive scores is what we use to improve on independent selection.
On each arrival, the algorithm samples m m m candidates independently from a probability vector v v v . If vertex i i i appears r r r times, its process takes r r r consecutive steps. Its combined desired win probability is 1 − ∏ k = 1 r ( 1 − X k ) 1 - \prod_{k=1}^{r}(1 - X_k) 1 − ∏ k = 1 r ( 1 − X k ) . A monotone tournament of Blanc and Charikar [2 ] converts the combined probabilities into one actual winner. The vector v v v is a deterministic function of the input prefix and the averaged states. It is independent of all realized candidate multisets, seed states, and tournament outcomes. Consequently, after conditioning on the candidate multisets, the selection processes retain the dependence properties needed in the analysis.
The tournament bounds the probability that a vertex remains unselected on any fixed set of arrivals by the expected product of its auxiliary failure probabilities. In particular, the bound applies to the arrivals whose edge to that vertex has weight at least a chosen threshold.
The residual potential. Fix a vertex i i i and a threshold w w w . Let ν ( z ) \nu(z) ν ( z ) be the probability that all auxiliary trials for edges of weight at least w w w have failed and the current age is z z z . This is a subprobability distribution: its total mass is the current auxiliary failure probability. Write P P P for the age transition matrix and T T T for the substochastic matrix that also requires the auxiliary trial to fail. On an arrival with edge weight w i w_i w i , each step sends ν \nu ν to ν T \nu T ν T if w ≤ w i w \le w_i w ≤ w i , and to ν P \nu P ν P if w > w i w > w_i w > w i .
The state ν \nu ν records more than its total mass. Two thresholds can have the same failure probability but different age distributions. To account for this difference, continue the auxiliary trials for an independent geometric number of steps with mean m m m . Let h ( z ) h(z) h ( z ) be the probability of at least one success, starting at age z z z . Starting at a larger age gives at least as large a success probability at the first reset; after that reset, the processes can be coupled to agree. Thus h h h is nondecreasing.
Let π \pi π be the stationary age distribution and put γ = π h \gamma= \pi h γ = π h . The residual potential of the threshold is ν h \nu h ν h : the expected success probability that remains on its uncovered mass. We assign the complementary quantity γ − ν h \gamma- \nu h γ − ν h as offline dual credit. It starts at zero because initially ν = π \nu= \pi ν = π .
Solving the one-step recurrence for the independent stopping experiment gives
h = 1 − ( I − m ( T − I ) ) − 1 1. h = 1 - (I - m(T-I))^{-1}\mathbf{1}. h = 1 − ( I − m ( T − I ) ) − 1 1 .
Proposition 5 shows that this choice maximizes π h \pi h π h among bounded linear potentials satisfying the local update inequality for w ≤ w i w \le w_i w ≤ w i on states satisfying the invariant below.
Credit monotonicity. The proof uses the complementary vector θ = π − ν \theta= \pi- \nu θ = π − ν . We show that every reachable θ \theta θ is a nonnegative linear combination of π \pi π and the distributions δ 0 P n \delta_0P^n δ 0 P n , n ≥ 0 n \ge0 n ≥ 0 . The latter is the distribution of a geometric age truncated at n n n ; it becomes stochastically older when another ordinary exposure is taken. This representation is preserved by both updates. A P P P -update advances each component by one age transition. A T T T -update also contributes a stationary component from the baseline success probability and a fresh reset component from the additional success probability at a reset. The existing components are rescaled and advanced; all coefficients remain nonnegative. Since each component becomes stochastically older under an age transition, the representation gives θ P h ≥ θ h \theta Ph \ge\theta h θ P h ≥ θ h , equivalently ν P h ≤ ν h \nu Ph \le\nu h ν P h ≤ ν h . Since 0 ≤ T ≤ P 0 \le T \le P 0 ≤ T ≤ P and h ≥ 0 h \ge0 h ≥ 0 , a T T T -update also satisfies ν T h ≤ ν P h ≤ ν h \nu Th \le\nu Ph \le\nu h ν T h ≤ ν P h ≤ ν h . Thus both updates increase the credit γ − ν h \gamma- \nu h γ − ν h . This invariant handles arbitrary interleavings of arrivals above and below the threshold.
The two update inequalities. Suppose the current vertex is sampled with probability x x x . Its number of exposures is Bin ( m , x ) \operatorname{Bin}(m,x) Bin ( m , x ) . If w ≤ w i w \le w_i w ≤ w i , the updated state is ν ( I + x ( T − I ) ) m \nu(I + x(T-I))^m ν ( I + x ( T − I ) ) m . Write y ( x ) y(x) y ( x ) for its mass and a ( x ) a(x) a ( x ) for its residual potential. The recurrence defining h h h gives
m ( T − I ) ( h − 1 ) = h . m(T-I)(h-1)=h. m ( T − I ) ( h − 1 ) = h .
After differentiating the binomial update and using the invariant, this identity yields
− y ′ ( x ) + a ′ ( x ) ≥ a ( x ) . -y'(x)+a'(x)\ge a(x). − y ′ ( x ) + a ′ ( x ) ≥ a ( x ) .
The decrease in auxiliary failure probability thus pays for the increase in offline credit and leaves a contribution toward the online vertex’s dual variable.
If w > w i w > w_i w > w i , set a ( x ) = ν ( I + x ( P − I ) ) m h a(x)=\nu(I+x(P-I))^m h a ( x ) = ν ( I + x ( P − I ) ) m h . There is no coverage gain, although the age distribution still changes. The same recurrence shows that k = ( I − m ( P − I ) ) h k=(I-m(P-I))h k = ( I − m ( P − I )) h is nonnegative and has stationary expectation γ \gamma γ . Every state ν \nu ν reached by the algorithm satisfies 0 ≤ ν ≤ π 0 \le\nu\le\pi 0 ≤ ν ≤ π . Since k ≥ 0 k \ge0 k ≥ 0 , we have ν k ≤ π k = γ \nu k \le\pi k = \gamma ν k ≤ π k = γ . Together with credit monotonicity, this gives
− a ′ ( x ) ≤ γ − a ( x ) . -a'(x)\le\gamma-a(x). − a ′ ( x ) ≤ γ − a ( x ) .
After integration, the credit created when w > w i w > w_i w > w i is at most the sampling probability times its post-arrival credit. This term is subtracted in the sampling deficit below. The accounting therefore includes state changes above the current edge weight, where no matching gain is available.
Water filling. Integrate the threshold credits to obtain one offline dual variable α i \alpha_i α i per vertex, and integrate one minus the auxiliary miss probability to obtain its contribution P i \mathcal{P}_i P i to the surrogate primal objective. This objective lower-bounds the expected matching value. For an edge of weight w i w_i w i and sampling probability x x x , the two update inequalities combine into
Δ P i − Δ α i ≥ x ( γ w i − α i [ x ] ) . \Delta\mathcal{P}_i-\Delta\alpha_i \ge x(\gamma w_i-\alpha_i[x]). Δ P i − Δ α i ≥ x ( γ w i − α i [ x ]) .
where α i [ x ] \alpha_i[x] α i [ x ] is the credit after the hypothetical update. This suggests the terminal deficit d i ( x ) = γ w i − α i [ x ] d_i(x)=\gamma w_i-\alpha_i[x] d i ( x ) = γ w i − α i [ x ] . These deficits are continuous and nonincreasing. A large deficit means that the edge’s dual constraint still requires a large contribution from the arriving vertex. The algorithm increases the coordinates with the largest deficit until their total is one; a zero-weight dummy absorbs any remaining probability. Every used coordinate has the same terminal deficit β \beta β . This gives dual feasibility, while integrating the two update inequalities pays for ∑ i Δ α i + β \sum_i \Delta\alpha_i+\beta ∑ i Δ α i + β . Summing over arrivals proves the competitive guarantee γ \gamma γ .
Tournament feasibility. The remaining condition belongs to the selection process. For each 1 ≤ r < m 1 \le r < m 1 ≤ r < m , let V r = ∏ k = 1 r ( 1 − X k ) V_r=\prod_{k=1}^{r}(1-X_k) V r = ∏ k = 1 r ( 1 − X k ) . The tournament exists when
E [ ( s − V r ) + ] ≤ H r ( s ) : = s − m − r m + m − r m ( 1 − s ) m / ( m − r ) ( 0 ≤ s ≤ 1 ) . \mathbb{E}[(s-V_r)+] \le H_r(s) := s-\frac{m-r}{m}+\frac{m-r}{m}(1-s)^{m/(m-r)} \qquad(0 \le s \le1). E [( s − V r ) + ] ≤ H r ( s ) := s − m m − r + m m − r ( 1 − s ) m / ( m − r ) ( 0 ≤ s ≤ 1 ) .
The singleton condition follows from the quantile construction. For repeated candidates, condition on the first reset. The remainder starts at age zero and has bounded age. Its minimum and mean failure products satisfy short recurrences. Replacing this fresh product by a two-point distribution with the same mean, supported at its lower and upper bounds, increases every convex positive-part expectation. This avoids enumerating the reset patterns.
The initial age is unbounded. Conditional Jensen combines its older quantile bins into an explicit integral, while the pooled ages remain one point mass. Conditioning on the first reset thus gives a convex upper bound with at most 2 r 2r 2 r age-averaged terms and a point mass for the no-reset case. A quadratic estimate handles thresholds near zero. Elsewhere, chords between certified endpoint values bound the curve. Minimizing the gap between each chord and H r H_r H r reduces its validity to an exact integer-power inequality. A finite rational partition therefore covers every real threshold; Appendix § 9 gives the construction.
Choosing the win map
For fixed m m m and p p p , the necessary singleton constraint is W ( Y ) ⪯ i c x U m − 1 W(Y) \preceq_{\mathrm{icx}} U^{m-1} W ( Y ) ⪯ icx U m − 1 , where Y Y Y is an output of the stationary reset process, U U U is uniform on [ 0 , 1 ] [0,1] [ 0 , 1 ] , and ⪯ i c x \preceq_{\mathrm{icx}} ⪯ icx denotes increasing convex order. To see why pooling arises, fix a baseline b ∈ [ q m − 1 / m , 1 / m ] b \in[q^{m-1}/m,1/m] b ∈ [ q m − 1 / m , 1/ m ] and consider maps of mean 1 / m 1/m 1/ m . Their integrated lower-quantile curve S ( u ) S(u) S ( u ) must satisfy S ( u ) ≥ b u S(u) \ge bu S ( u ) ≥ b u and S ( u ) ≥ u m / m S(u) \ge u^m/m S ( u ) ≥ u m / m . The smallest permitted values at the seed’s quantile-bin endpoints are therefore given by
ϕ b ( u ) = max { b u , u m / m } . \phi_b(u)=\max\{bu,u^m/m\}. ϕ b ( u ) = max { b u , u m / m } .
The successive secant slopes define a nondecreasing win map. The linear part assigns a common score to the youngest ages, and the remaining slopes preserve the older quantile-bin scores. A renewal formula shows that, at fixed baseline, γ ( W ) \gamma(W) γ ( W ) is nondecreasing in the stationary upper-tail score sums. The pooled map maximizes these sums at fixed baseline. Theorem 6 proves this comparison, including maps whose mean is less than 1 / m 1/m 1/ m , and reduces the optimization to the choice of b b b .
Age also suffices for a broader class of processes with independent resets. Conditional on the reset times, each cycle contributes at most one nonconstant factor to a failure product. Replacing its terminal score by its conditional mean preserves avoidance probabilities and, by Jensen’s inequality, preserves the tournament constraints. Proposition 9 proves this reduction by averaging over the internal randomness between resets. The subsequent pooled replacement optimizes only the singleton relaxation; its higher-multiplicity constraints still require the certificate described above.
Correlated Selection and Weight Thresholds
The stationary geometric-age seed
Fix m ≥ 2 m \ge2 m ≥ 2 , a reset probability p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) , and q = 1 − p q = 1-p q = 1 − p . Start Z 1 Z_1 Z 1 with distribution π ( z ) = p q z \pi(z) = pq^z π ( z ) = p q z , z ≥ 0 z \ge0 z ≥ 0 . At exposure k k k , independently draw a reset bit B k B_k B k with probability p p p of being one. If B k = 1 B_k = 1 B k = 1 , output Y k = Z k Y_k = Z_k Y k = Z k and set Z k + 1 = 0 Z_{k+1} = 0 Z k + 1 = 0 . Otherwise output Y k = − 1 Y_k = -1 Y k = − 1 and set Z k + 1 = Z k + 1 Z_{k+1} = Z_k + 1 Z k + 1 = Z k + 1 . Every offline vertex gets an independent seed.
Let W ( − 1 ) = b ∈ [ 0 , 1 ) W(-1) = b \in[0,1) W ( − 1 ) = b ∈ [ 0 , 1 ) and let W ( z ) W(z) W ( z ) be nondecreasing in z ≥ 0 z \ge0 z ≥ 0 , with b ≤ W ( z ) ≤ 1 b \le W(z) \le1 b ≤ W ( z ) ≤ 1 . The desired win probability at exposure k k k is X k = W ( Y k ) X_k = W(Y_k) X k = W ( Y k ) . The raw sequence ( Y k ) (Y_k) ( Y k ) is stationary and negatively associated [2 Section 10.1] ; Lemma 14 gives a short independent proof. Coordinatewise increasing maps preserve negative association, so the same holds for ( X k ) (X_k) ( X k ) .
Definition 2 (Negative association). A finite family ( X k ) k ∈ I (X_k)_{k\in I} ( X k ) k ∈ I is negatively associated if, for disjoint index sets A A A , B ⊆ I B \subseteq I B ⊆ I and increasing functions g g g , h h h for which the expectations exist,
Cov ( g ( ( X k ) k ∈ A ) , h ( ( X k ) k ∈ B ) ) ≤ 0. \operatorname{Cov}\left(g((X_k)_{k\in A}),h((X_k)_{k\in B})\right) \le0. Cov ( g (( X k ) k ∈ A ) , h (( X k ) k ∈ B ) ) ≤ 0. An infinite sequence is negatively associated if all its finite subfamilies are.
Negative association is a property of the stationary win process, not an assertion that the algorithm’s choices remain negatively associated after conditioning on their past outcomes. The analysis never requires such a conditional assertion.
The monotone tournament
For random variables A A A , B B B in [ 0 , 1 ] [0,1] [ 0 , 1 ] , we write A ⪯ i c x B A \preceq_{\mathrm{icx}} B A ⪯ icx B when E [ φ ( A ) ] ≤ E [ φ ( B ) ] \mathbb{E}[\varphi(A)] \le\mathbb{E}[\varphi(B)] E [ φ ( A )] ≤ E [ φ ( B )] for every increasing convex function φ \varphi φ . Equivalently, E [ ( A − t ) + ] ≤ E [ ( B − t ) + ] \mathbb{E}[(A-t)_+] \le\mathbb{E}[(B-t)_+] E [( A − t ) + ] ≤ E [( B − t ) + ] for every t ∈ [ 0 , 1 ] t \in[0,1] t ∈ [ 0 , 1 ] . The positive-part function measures the expected excess above a given level.
For r = 1 , … , m − 1 r = 1,\ldots,m-1 r = 1 , … , m − 1 , put
V r = ∏ k = 1 r ( 1 − X k ) , U r = 1 − V r . V_r = \prod_{k=1}^{r}(1-X_k), \qquad U_r = 1-V_r. V r = k = 1 ∏ r ( 1 − X k ) , U r = 1 − V r .
The following sufficient condition is exactly the one used in Blanc–Charikar’s tournament construction.
Lemma 3 (Tournament criterion [2 ] ). Suppose that, for every r = 1 , … , m − 1 r = 1,\ldots,m-1 r = 1 , … , m − 1 and every t ∈ [ 0 , 1 ] t \in[0,1] t ∈ [ 0 , 1 ] ,
E [ ( U r − t ) + ] ≤ 1 − t − m − r m ( 1 − t m / ( m − r ) ) . (2) \mathbb{E}[(U_r-t)_+] \le1-t-\frac{m-r}{m}\left(1-t^{m/(m-r)}\right). \tag*{(2)} E [( U r − t ) + ] ≤ 1 − t − m m − r ( 1 − t m / ( m − r ) ) . (2) Then an m m m -candidate multiset admits a randomized tournament with the following properties. If vertex i i i has multiplicity r i r_i r i and its next r i r_i r i scores are X i , 1 , … , X i , r i X_{i,1},\ldots,X_{i,r_i} X i , 1 , … , X i , r i , its combined desired win probability is Q i = 1 − ∏ k = 1 r i ( 1 − X i , k ) Q_i = 1-\prod_{k=1}^{r_i}(1-X_{i,k}) Q i = 1 − ∏ k = 1 r i ( 1 − X i , k ) . Conditional only on Q i = u Q_i = u Q i = u , its probability of winning is at least u u u , where the probability averages over independent stationary opponent blocks and fresh tournament randomness. For a fixed tuple of desired win probabilities, the tournament kernel gives each vertex a winning probability that is nondecreasing in its own desired win probability and nonincreasing in every opponent’s desired win probability. A vertex of multiplicity m m m wins deterministically.
The reference distribution for multiplicity r r r has cumulative distribution function t r / ( m − r ) t^{r/(m-r)} t r / ( m − r ) . Raising a reference draw to the power 1 / ( m − r ) 1/(m-r) 1/ ( m − r ) produces the maximum of r r r independent uniform draws. Comparing these strengths across a partition of m m m gives the desired conditional winning probability exactly. Inequality (2) says that the proposed desired win probability is below the reference draw in increasing convex order. The monotone submartingale-coupling theorem of Müller and Rüschendorf [15 Theorem 4.5(a)] , used in [2 Theorem 8 and Lemma 9.13] , then transfers the reference strengths to the proposed distribution. We use this coupling theorem in its published form.
A nonselection bound for arbitrary subsets of rounds
Given a deterministic probability vector v = ( v i ) \boldsymbol{v} = (v_i) v = ( v i ) , sample m m m candidates independently from the categorical distribution v \boldsymbol{v} v , using fresh randomness independent of all seeds and earlier draws. The multiplicity of i i i is K i ∼ Bin ( m , v i ) K_i \sim\operatorname{Bin}(m,v_i) K i ∼ Bin ( m , v i ) . Consume that many consecutive exposures from i i i ’s seed and run the tournament. The chosen vertex receives the arriving online vertex.
The algorithm below chooses every probability vector from deterministic states that average over all earlier multiplicities. For a fixed input, the entire vector sequence is therefore independent of the realized multisets and seed outcomes. Fix this sequence and condition on all the sampled multisets. For any fixed vertex i i i and any deterministic set S S S of rounds, condition additionally on i i i ’s desired win probabilities in those rounds. The opponents’ seed sequences remain independent of i i i ’s sequence. They are jointly negatively associated, and losing to them in disjoint rounds is increasing in disjoint sets of their seed coordinates. With independent tournament randomization on different rounds, the conditional probability of losing every round in S S S is at most the product of the individual loss probabilities. Tournament consistency gives
Pr [ i never selected in S ] ≤ E [ ∏ k ∈ E ( S ) ( 1 − X k ) ] , (3) \Pr[i\text{ never selected in }S] \le\mathbb{E}\left[\prod_{k\in E(S)}(1-X_k)\right], \tag*{(3)} Pr [ i never selected in S ] ≤ E k ∈ E ( S ) ∏ ( 1 − X k ) , (3)
where E ( S ) E(S) E ( S ) is the union of the seed exposures consumed in those rounds. This is the arbitrary-subset assertion of [2 Lemma 9.11] , followed by averaging over the candidate multisets. Repeated occurrences consume distinct exposure indices.
For a weight threshold w w w , take S = { j : w i j ≥ w } S = \{j : w_{ij} \ge w\} S = { j : w ij ≥ w } . Auxiliary independent success coins with probabilities X k X_k X k , used only for the analysis, turn the right side of (3) into a miss probability. The reduction below tracks that probability jointly with the age. The auxiliary failure probability upper-bounds the actual nonselection probability; equality is not required.
The Algorithm
On each arrival, deterministic accounting vectors define a sampling distribution and are updated by averaging over its candidate counts. The algorithm then samples m m m candidates, advances their sampled seeds, and selects one winner. The sampled outcomes do not feed back into the accounting vectors. This separation preserves the arbitrary-subset guarantee from § 3 .
The description is parameterized by m m m , p p p , W W W , an age cap C C C , a score scaling factor n n n , and a water-filling accuracy ϵ \epsilon ϵ . § 7 sets these constants. We use the finite capped and scaled process directly; the subsequent analysis first establishes the ideal guarantee and then bounds the implementation loss in Appendix § 10 .
What is precomputed
Write q = 1 − p q=1-p q = 1 − p , b f = η W ( − 1 ) b_f=\eta W(-1) b f = η W ( − 1 ) , and W f ( z ) = η W ( z ) W_f(z)=\eta W(z) W f ( z ) = η W ( z ) for 0 ≤ z ≤ C 0\le z\le C 0 ≤ z ≤ C , and put z + = min { z + 1 , C } z^+=\min\{z+1,C\} z + = min { z + 1 , C } . On { 0 , … , C } \{0,\ldots,C\} { 0 , … , C } , the transition matrix P f P_f P f and substochastic failure matrix T f T_f T f satisfy
P f ( z , z + ) = q , P f ( z , 0 ) = p , T f ( z , z + ) = q ( 1 − b f ) , T f ( z , 0 ) = p ( 1 − W f ( z ) ) . \begin{aligned}
P_f(z,z^+) &= q, & P_f(z,0) &= p,\\
T_f(z,z^+) &= q(1-b_f), & T_f(z,0) &= p(1-W_f(z)).
\end{aligned} P f ( z , z + ) T f ( z , z + ) = q , = q ( 1 − b f ) , P f ( z , 0 ) T f ( z , 0 ) = p , = p ( 1 − W f ( z )) .
The stationary distribution is π f ( z ) = p q z \pi_f(z)=pq^z π f ( z ) = p q z for z < C z<C z < C and π f ( C ) = q C \pi_f(C)=q^C π f ( C ) = q C . Preprocessing computes the exact rational quantities
h f = 1 − ( ( m + 1 ) Id − m T f ) − 1 1 , Γ = π f h f . (4) h_f=1-\bigl((m+1)\operatorname{Id}-mT_f\bigr)^{-1}\mathbf{1},\qquad\Gamma=\pi_f h_f. \tag*{(4)} h f = 1 − ( ( m + 1 ) Id − m T f ) − 1 1 , Γ = π f h f . (4)
Here Id \operatorname{Id} Id is the identity matrix on the finite age space. These are the finite versions of the potential and guarantee in § 2 . The sampling rule uses this exact Γ \Gamma Γ ; the decimal constant in Theorem 1 is a lower bound on the final guarantee, not a replacement for it. A backward recurrence in Appendix § 10 .§ 2 computes h f h_f h f in O ( C ) O(C) O ( C ) rational arithmetic operations.
The remaining preprocessed objects are finite tournament tables. For each multiplicity r < m r<m r < m and possible combined desired win probability u u u , a table specifies a distribution K r ( u , ⋅ ) K_r(u,\cdot) K r ( u , ⋅ ) over ordered strength bins. A second table gives the winner probabilities when several candidates occupy the highest sampled bin. Thus the online tournament requires only table lookups and draws from rational distributions. Appendix § 10 .§ 3 gives the stationary-block dynamic program, the rational coupling LP, and the polynomial integrals that construct these tables. Their sizes can be large; all depend only on the fixed seed parameters, not on the graph or its edge weights.
The state stored at an offline vertex
For each real offline vertex i i i , maintain the following objects. The dummy vertex ⊥ \perp ⊥ has only the sampled age.
A sampled age Z i ∈ { 0 , … , C } Z_i\in\{0,\ldots,C\} Z i ∈ { 0 , … , C } , initialized independently from π f \pi_f π f . It advances only when i i i occurs among the sampled candidates.
A retained edge e i e_i e i and its weight M i M_i M i , initially empty and zero. This record implements free disposal.
A collection of accounting vectors ν i , I \nu_{i,I} ν i , I , one for each interval I I I between consecutive positive weights revealed at i i i , with zero included as the first endpoint. The vector records the auxiliary miss event jointly with the age, averaged over all candidate samples and seed outcomes.
The accounting vectors are deterministic functions of the input prefix. They are subprobability vectors, so their entries need not sum to one and are never normalized. They determine the sampling distribution. The sampled ages and retained edges are used only to execute the random assignment and record its value.
Initially no finite intervals are stored. The implicit tail above the largest weight revealed at i i i always has vector π f \pi_f π f and contributes zero credit. When an edge of weight w i w_i w i arrives, insert w i w_i w i as an endpoint if it is positive and new. An interior insertion splits one interval into two copies of its old vector. An insertion above all previous weights creates a new finite interval with vector π f \pi_f π f . Denote this operation by Refine ( i , w i ) \operatorname{Refine}(i,w_i) Refine ( i , w i ) and the resulting set of finite intervals by I i \mathcal{I}_i I i . At arrival j j j there are at most j j j such intervals per vertex.
Every interval now lies entirely on one side of w i w_i w i . Define
K i , I = { T f , sup I ≤ w i , P f , inf I ≥ w i , R i , I ( x ) = ( 1 − x ) Id + x K i , I . (5) K_{i,I}=
\begin{cases}
T_f, & \sup I\le w_i,\\
P_f, & \inf I\ge w_i,
\end{cases}
\qquad
R_{i,I}(x)=(1-x)\operatorname{Id}+xK_{i,I}. \tag*{(5)} K i , I = { T f , P f , sup I ≤ w i , inf I ≥ w i , R i , I ( x ) = ( 1 − x ) Id + x K i , I . (5)
Below the current weight, an exposure must be an auxiliary miss to remain in the accounting vector. Above that weight, an exposure simply advances the age. In particular, the intervals above w i w_i w i also receive an update.
Choosing the candidate probabilities
Suppose the sampling probability of i i i were x x x . Its multiplicity would be Bin ( m , x ) \operatorname{Bin}(m,x) Bin ( m , x ) , so the averaged vector on interval I I I would be ν i , I R i , I ( x ) m \nu_{i,I}R_{i,I}(x)^m ν i , I R i , I ( x ) m . The resulting total credit is
A i ( x ) = ∑ I ∈ I i ∣ I ∣ [ Γ − ν i , I R i , I ( x ) m h f ] , d i ( x ) = Γ w i − A i ( x ) . (6) A_i(x) = \sum_{I \in\mathcal{I}_i} |I| \left[\Gamma- \nu_{i,I}R_{i,I}(x)^m h_f\right], \qquad d_i(x) = \Gamma w_i - A_i(x). \tag*{(6)} A i ( x ) = I ∈ I i ∑ ∣ I ∣ [ Γ − ν i , I R i , I ( x ) m h f ] , d i ( x ) = Γ w i − A i ( x ) . (6)
Here ∣ I ∣ |I| ∣ I ∣ is the interval length. All hypothetical evaluations use the same vectors present just after Refine. Trying a sampling probability does not modify those vectors.
The deficit d i ( x ) d_i(x) d i ( x ) measures how much of the current edge’s dual constraint remains after giving i i i probability x x x . It is nonincreasing in x x x , as proved in § 5 . Water filling repeatedly gives more probability to a vertex with the largest deficit. We use the finite rational rule in Algorithm 1: at arrival j j j , allocate probability in increments of 1 / N j 1/N_j 1/ N j , where N j = ⌈ m j ( j + 1 ) / ϵ ⌉ N_j = \lceil m_j(j+1)/\epsilon\rceil N j = ⌈ m j ( j + 1 ) / ϵ ⌉ . A dummy coordinate has deficit identically zero. Fix a deterministic tie order once, with the dummy first. After N j N_j N j increments the probabilities sum to one. The grid approximately equalizes the terminal deficits. Its total loss in competitive ratio is at most ϵ \epsilon ϵ , independently of the number of arrivals.
Each deficit is an explicit polynomial. To evaluate it without taking a matrix power for every trial value of x x x , first compute
c i , k = ∑ I ∈ I i ∣ I ∣ [ Γ − ν i , I K i , I k h f ] ( 0 ≤ k ≤ m ) , c_{i,k} = \sum_{I \in\mathcal{I}_i} |I| \left[\Gamma- \nu_{i,I}K_{i,I}^{k}h_f\right] \qquad(0 \le k \le m), c i , k = I ∈ I i ∑ ∣ I ∣ [ Γ − ν i , I K i , I k h f ] ( 0 ≤ k ≤ m ) ,
A i ( x ) = ∑ k = 0 m ( m k ) x k ( 1 − x ) m − k c i , k . (7) A_i(x) = \sum_{k=0}^{m} \binom{m}{k}x^k(1-x)^{m-k}c_{i,k}. \tag*{(7)} A i ( x ) = k = 0 ∑ m ( k m ) x k ( 1 − x ) m − k c i , k . (7)
The first line conditions on exactly k k k exposures; the second averages over their binomial count. Sparse row-vector products compute all coefficients. Precomputing the powers of x x x and 1 − x 1-x 1 − x up to degree m m m makes each subsequent evaluation use O ( m ) O(m) O ( m ) rational arithmetic operations. A max heap stores the current deficits. An increment changes only the chosen coordinate’s key.
Once v v v is chosen, commit ν i , I ← ν i , I R i , I ( v i ) m \nu_{i,I} \leftarrow\nu_{i,I}R_{i,I}(v_i)^m ν i , I ← ν i , I R i , I ( v i ) m for every stored interval. This can be evaluated by m m m successive sparse mixture updates. The grid increments themselves are only hypothetical; they are not committed as separate exposures. The committed update averages over Bin ( m , v i ) \operatorname{Bin}(m,v_i) Bin ( m , v i ) and does not use the candidate count that will actually be sampled.
From candidates to one retained edge
Draw m m m independent candidates from v v v , using fresh randomness independent of every seed. Let r i r_i r i be the number of occurrences of i i i . Each distinct candidate consumes r i r_i r i consecutive exposures of its own sampled seed. On a reset, the score is W f ( Z i ) W_f(Z_i) W f ( Z i ) at the age before the reset, and the new age is zero. On a nonreset, the score is b f b_f b f and the age increments, capped at C C C . If these scores are X i , 1 , … , X i , r i X_{i,1},\ldots,X_{i,r_i} X i , 1 , … , X i , r i , their combined desired win probability is
Q i = 1 − ∏ k = 1 r i ( 1 − X i , k ) . Q_i = 1 - \prod_{k=1}^{r_i}(1-X_{i,k}). Q i = 1 − k = 1 ∏ r i ( 1 − X i , k ) .
The scores have already been scaled individually. No auxiliary success coins are generated: the algorithm only computes this product.
Algorithm 1. Choosing the sampling probabilities
Input: arrival j j j , weights ( w i ) (w_i) ( w i ) , and frozen interval vectors.
for each real vertex i i i do
Set c i , k ← 0 c_{i,k} \gets0 c i , k ← 0 for k = 0 , … , m k = 0,\ldots,m k = 0 , … , m .
for each I ∈ I i I \in\mathcal{I}_i I ∈ I i do
Set u ← ν i , I u \gets\nu_{i,I} u ← ν i , I and K ← K i , I K \gets K_{i,I} K ← K i , I from (5) .
for k = 0 , … , m k = 0,\ldots,m k = 0 , … , m do
Set c i , k ← c i , k + ∣ I ∣ ( Γ − u h f ) c_{i,k} \gets c_{i,k} + |I|(\Gamma- uh_f) c i , k ← c i , k + ∣ I ∣ ( Γ − u h f ) .
if k < m k < m k < m then u ← u K u \gets uK u ← u K .
end for
end for
Define d i ( x ) = Γ w i − A i ( x ) d_i(x) = \Gamma w_i - A_i(x) d i ( x ) = Γ w i − A i ( x ) using (7) .
end for
Set d ⊥ ( x ) ← 0 d_{\perp}(x) \gets0 d ⊥ ( x ) ← 0 and N ← ⌈ m j ( j + 1 ) ϵ ⌉ N \gets\left\lceil\frac{mj(j+1)}{\epsilon} \right\rceil N ← ⌈ ϵ mj ( j + 1 ) ⌉ .
Set t i ← 0 t_i \gets0 t i ← 0 for every i ∈ L ∪ { ⊥ } i \in L \cup\{\perp\} i ∈ L ∪ { ⊥ } .
repeat N N N times
Choose i i i maximizing d i ( t i / N ) d_i(t_i/N) d i ( t i / N ) , using the fixed tie order.
Set t i ← t i + 1 t_i \gets t_i + 1 t i ← t i + 1 .
end repeat
return v i = t i / N v_i = t_i/N v i = t i / N for every i ∈ L ∪ { ⊥ } i \in L \cup\{\perp\} i ∈ L ∪ { ⊥ } .
If only one distinct candidate was sampled, it wins. Otherwise, each candidate independently draws a bin from K r i ( Q i , ⋅ ) K_{r_i}(Q_i,\cdot) K r i ( Q i , ⋅ ) . Only candidates in the highest drawn bin can win. The precomputed within-bin probabilities determine which one does. Equal bin indices need not give equal winner probabilities when the multiplicities differ; Appendix § 10 .§ 3 gives their exact formula. Algorithm 3 gives the procedure Tournament used by Algorithm 2. The numbers Q i Q_i Q i are inputs to this calibrated procedure, rather than probabilities to be normalized across candidates.
The dummy participates with its own persistent seed and the same tournament rule; a dummy win discards the arrival. A real winner receives the arrival, and free disposal keeps the heavier of its new edge and its previously retained edge. All sampled exposures are consumed, including those of losing candidates and those on rounds whose winner is certain or whose edge cannot improve the retained weight. They affect later selection opportunities.
Information used by the algorithm. The sampling routine reads only revealed weights and deterministic accounting vectors. Neither the sampled ages nor the retained edges are fed back into it. Likewise, its accounting vectors are not conditioned on the realized multiplicities or the winner. For every fixed input, the entire sequence of probability vectors is therefore deterministic, exactly as required in § 3 . The auxiliary success trials and the independent geometric horizon used to interpret h f h_f h f belong only to the analysis.
Arithmetic and running time. All operations shown above can use exact rational arithmetic. With n = ∣ L ∣ n = |L| n = ∣ L ∣ and d = C + 1 d = C + 1 d = C + 1 , the credit coefficients and committed updates at arrival j j j require O ( n j m d ) O(n_jmd) O ( n j m d ) arithmetic operations because the kernels are sparse. Heap-based water filling requires O ( N j ( m + log ( n + 1 ) ) ) O(N_j(m+\log(n+1))) O ( N j ( m + log ( n + 1 ))) further operations. The interval vectors and credit coefficients use O ( n j d + n m ) O(n_jd+nm) O ( n j d + nm ) space, in addition to the fixed tournament tables. Appendix § 10 gives the polynomial bit-complexity bound and exact rational sampling procedure. The algorithm has competitive guarantee Γ − ϵ \Gamma-\epsilon Γ − ϵ ; § 7 accounts for the cap, scaling, and grid losses and obtains Theorem 1 .
Algorithm 2. Finite online matching with free disposal
Input: offline vertices L L L and the preprocessed finite model.
Draw Z ‾ i ∼ π f \overline{Z}_i \sim\pi_f Z i ∼ π f independently for all i ∈ L ∪ { ⊥ } i \in L \cup\{\perp\} i ∈ L ∪ { ⊥ } .
For each real i i i , set I i ← ∅ \mathcal{I}_i \leftarrow\varnothing I i ← ∅ , M i ← 0 M_i \leftarrow0 M i ← 0 , and e i ← ∅ e_i \leftarrow\varnothing e i ← ∅ .
for each arrival j = 1 , 2 , … j = 1,2,\ldots j = 1 , 2 , … do
Read weights w i w_i w i ; set w i = 0 w_i = 0 w i = 0 for an absent edge.
For each real i i i , apply Refine ( i , w i ) \operatorname{Refine}(i,w_i) Refine ( i , w i ) .
Compute v v v by Algorithm 1 from these interval vectors.
For every i , I i,I i , I , set ν i , I ← ν i , I R i , I ( v i ) m \nu_{i,I} \leftarrow\nu_{i,I}R_{i,I}(v_i)^m ν i , I ← ν i , I R i , I ( v i ) m .
Draw m m m independent candidates from v v v ; record their counts r i r_i r i .
for each distinct candidate i i i with r i > 0 r_i > 0 r i > 0 do
Set F i ← 1 F_i \leftarrow1 F i ← 1 .
repeat r i r_i r i times
Draw a fresh reset bit B ∼ Bernoulli ( p ) B \sim\operatorname{Bernoulli}(p) B ∼ Bernoulli ( p ) .
if B = 1 B = 1 B = 1 then
Set X ← W f ( Z i ) X \leftarrow W_f(Z_i) X ← W f ( Z i ) , then Z i ← 0 Z_i \leftarrow0 Z i ← 0 .
else
Set X ← b f X \leftarrow b_f X ← b f , then Z i ← min { Z i + 1 , C } Z_i \leftarrow\min\{Z_i + 1,C\} Z i ← min { Z i + 1 , C } .
end if
Set F i ← F i ( 1 − X ) F_i \leftarrow F_i(1-X) F i ← F i ( 1 − X ) .
end repeat
Set Q i ← 1 − F i Q_i \leftarrow1-F_i Q i ← 1 − F i .
end for
Set u ← Tournament ( ( i , r i , Q i ) r i > 0 ) u \leftarrow\operatorname{Tournament}((i,r_i,Q_i)_{r_i>0}) u ← Tournament (( i , r i , Q i ) r i > 0 ) .
if u ≠ ⊥ u \ne\perp u = ⊥ and w u > M u w_u > M_u w u > M u then
Set M u ← w u M_u \leftarrow w_u M u ← w u and e u ← ( u , j ) e_u \leftarrow(u,j) e u ← ( u , j ) , discarding its previous edge.
end if
end for
Output: the nonempty retained edges ( e i ) i ∈ L (e_i)_{i\in L} ( e i ) i ∈ L .
A State-Dependent Primal–Dual Analysis
We now prove the matching reduction. Throughout this section, W W W is any nondecreasing map from { − 1 , 0 , 1 , … } \{-1,0,1,\ldots\} { − 1 , 0 , 1 , … } to [ 0 , 1 ] [0,1] [ 0 , 1 ] satisfying Lemma 3 . We write the formulas for the uncapped process; Appendix § 10 gives the corresponding capped process and shows that the same invariant and proof apply.
Fix an integer m ≥ 2 m \ge2 m ≥ 2 and p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) , and put q = 1 − p q = 1-p q = 1 − p and b = W ( − 1 ) b = W(-1) b = W ( − 1 ) . The age transition matrix and the substochastic failure matrix are
P ( z , z + 1 ) = q , P ( z , 0 ) = p , T ( z , z + 1 ) = q ( 1 − b ) , T ( z , 0 ) = p ( 1 − W ( z ) ) . P(z,z+1)=q,\qquad P(z,0)=p,\qquad T(z,z+1)=q(1-b),\qquad T(z,0)=p(1-W(z)). P ( z , z + 1 ) = q , P ( z , 0 ) = p , T ( z , z + 1 ) = q ( 1 − b ) , T ( z , 0 ) = p ( 1 − W ( z )) .
Thus
T = ( 1 − b ) P − p ( W − b ) δ 0 . T=(1-b)P-p(W-b)\delta_0. T = ( 1 − b ) P − p ( W − b ) δ 0 .
The stationary distribution of P P P is π ( z ) = p q z \pi(z)=pq^z π ( z ) = p q z . Each offline vertex has an independent stationary seed; a reset outputs the age z z z and a nonreset outputs − 1 -1 − 1 . Its desired win probability is W ( z ) W(z) W ( z ) at a reset and b b b at a nonreset.
The assumptions of Lemma 3 give the arbitrary-subset bound (3) . We use the corresponding auxiliary miss process to lower-bound the expected matching value. Define the column vector
h = 1 − ( I − m ( T − I ) ) − 1 1 , γ = π h . (8) h = \mathbf{1} - \left(I - m(T-I)\right)^{-1}\mathbf{1}, \qquad\gamma= \pi h. \tag*{(8)} h = 1 − ( I − m ( T − I ) ) − 1 1 , γ = π h . (8)
The inverse is well defined by
( I − m ( T − I ) ) − 1 = 1 m + 1 ∑ n = 0 ∞ ( m m + 1 ) n T n . \left(I-m(T-I)\right)^{-1}=\frac{1}{m+1}\sum_{n=0}^{\infty}\left(\frac{m}{m+1}\right)^nT^n. ( I − m ( T − I ) ) − 1 = m + 1 1 n = 0 ∑ ∞ ( m + 1 m ) n T n .
Equivalently, take an independent geometric number N N N of exposures, with Pr ( N = n ) = m n ( m + 1 ) n + 1 \Pr(N=n)=\frac{m^n}{(m+1)^{n+1}} Pr ( N = n ) = ( m + 1 ) n + 1 m n for n ≥ 0 n\ge0 n ≥ 0 . Then h ( z ) h(z) h ( z ) is the probability of an auxiliary success within those N N N exposures, starting at age z z z . It follows that 0 ≤ h ≤ 1 0\le h\le1 0 ≤ h ≤ 1 and that h h h is nondecreasing in age. For the latter assertion, couple two initial ages until the first reset, using identical baseline-success coins at nonresets. The older process has a larger success probability at the first reset; if both survive, their ages agree thereafter.
Theorem 4 (State-dependent matching reduction). Under the assumptions above, there is a randomized online algorithm for edge-weighted bipartite matching with free disposal whose competitive ratio is at least
γ = 1 − ∑ n = 0 ∞ m n ( m + 1 ) n + 1 π T n 1. \gamma=1-\sum_{n=0}^{\infty}\frac{m^n}{(m+1)^{n+1}}\pi T^n\mathbf{1}. γ = 1 − n = 0 ∑ ∞ ( m + 1 ) n + 1 m n π T n 1 .
The standard matching LP gives the following sufficient condition. If nonnegative variables satisfy α i + β j ≥ γ w i j \alpha_i+\beta_j\ge\gamma w_{ij} α i + β j ≥ γ w ij for every edge and E [ A L G ] ≥ ∑ i α i + ∑ j β j \mathbb{E}[\mathrm{ALG}]\ge\sum_i\alpha_i+\sum_j\beta_j E [ ALG ] ≥ ∑ i α i + ∑ j β j , then weak duality implies E [ A L G ] ≥ γ O P T \mathbb{E}[\mathrm{ALG}]\ge\gamma\mathrm{OPT} E [ ALG ] ≥ γ OPT . We construct these variables online. Offline variables only increase; the variable for an arrival is fixed when that arrival is processed.
The state invariant
At a fixed offline vertex and weight threshold w w w , let ν \nu ν be the subprobability row vector of the current age jointly with the event that all auxiliary trials for edges of weight at least w w w have failed. Initially ν = π \nu=\pi ν = π . Set θ = π − ν \theta=\pi-\nu θ = π − ν .
The invariant requires ν \nu ν to be nonnegative and θ \theta θ to be a nonnegative linear combination of the distributions
π , δ 0 P n ( n = 0 , 1 , 2 , … ) . \pi,\qquad\delta_0P^n\quad(n=0,1,2,\ldots). π , δ 0 P n ( n = 0 , 1 , 2 , … ) .
In particular, every state satisfying the invariant has 0 ≤ ν ≤ π 0\le\nu\le\pi 0 ≤ ν ≤ π coordinatewise. The coefficients need not sum to one; their sum is the subprobability mass of θ \theta θ . When b = 0 b=0 b = 0 , a probabilistic interpretation decomposes successful histories by their first auxiliary success on an edge of weight at least w w w , which resets the age to zero. For b > 0 b>0 b > 0 , the following algebraic invariant also includes a stationary component.
The following identities prove preservation of the invariant. For an arrival whose edge to the fixed vertex has weight w i w_i w i , each exposure with w > w i w>w_i w > w i uses P P P and maps
ν ⟼ ν P , θ ⟼ θ P . \nu\longmapsto\nu P,\qquad\theta\longmapsto\theta P. ν ⟼ ν P , θ ⟼ θ P .
An exposure with w ≤ w i w\le w_i w ≤ w i uses T T T and maps
ν ⟼ ν T , θ ⟼ b π + ( 1 − b ) θ P + p ( ∑ z ν ( z ) ( W ( z ) − b ) ) δ 0 . \nu\longmapsto\nu T,\qquad
\theta\longmapsto b\pi+(1-b)\theta P+p\left(\sum_z\nu(z)(W(z)-b)\right)\delta_0. ν ⟼ ν T , θ ⟼ bπ + ( 1 − b ) θ P + p ( z ∑ ν ( z ) ( W ( z ) − b ) ) δ 0 .
Every coefficient is nonnegative because W ( z ) ≥ b W(z) \ge b W ( z ) ≥ b . Both operations preserve the invariant, as do their convex combinations with the identity operation. This includes Bernoulli exposure trials and arbitrary compositions of them.
θ 0 P n \theta_0P^n θ 0 P n is the distribution of min ( G , n ) \min(G,n) min ( G , n ) for a geometric random variable G G G of parameter p p p . These distributions increase stochastically with n n n , while π P = π \pi P = \pi π P = π . Since h h h is increasing and nonnegative, θ P h ≥ θ h \theta Ph \ge\theta h θ P h ≥ θ h . Define the credit
A ( ν ) : = ( π − ν ) h A(\nu) := (\pi-\nu)h A ( ν ) := ( π − ν ) h
and note that A ( ν ) ≤ π h = γ A(\nu) \le\pi h = \gamma A ( ν ) ≤ π h = γ . A P P P -update increases this credit because θ P h ≥ θ h \theta Ph \ge\theta h θ P h ≥ θ h , or equivalently ν P h ≤ ν h \nu Ph \le\nu h ν P h ≤ ν h . A T T T -update satisfies the same comparison: since 0 ≤ T ≤ P 0 \le T \le P 0 ≤ T ≤ P and h ≥ 0 h \ge0 h ≥ 0 ,
ν T h ≤ ν P h ≤ ν h . \nu Th \le\nu Ph \le\nu h. ν T h ≤ ν P h ≤ ν h .
Thus credit is nondecreasing under both types of exposure. Consequently the residual
a ( ν ) : = ν h = γ − A ( ν ) a(\nu) := \nu h = \gamma- A(\nu) a ( ν ) := ν h = γ − A ( ν )
is nonincreasing under either operation. This is an assertion about aggregate states satisfying the invariant; the pointwise inequality T h ≤ h Th \le h T h ≤ h is neither needed nor generally true.
Updates for one online arrival
Given a probability vector v = ( v i ) v = (v_i) v = ( v i ) , sample m m m independent candidates and pass their multiset to the tournament. The multiplicity of a fixed vertex i i i is distributed as Bin ( m , v i ) \operatorname{Bin}(m,v_i) Bin ( m , v i ) .
For a current edge of weight w i w_i w i and a threshold w w w , each exposure uses T T T if w ≤ w i w \le w_i w ≤ w i and P P P if w > w i w > w_i w > w i . Writing x = v i x = v_i x = v i , the corresponding deterministic updates of the joint state vector are
ν ⟼ ν R x m , R x = I + x ( T − I ) , w ≤ w i , \nu\longmapsto\nu R_x^m,\qquad R_x = I + x(T-I),\qquad w \le w_i, ν ⟼ ν R x m , R x = I + x ( T − I ) , w ≤ w i ,
and
ν ⟼ ν S x m , S x = I + x ( P − I ) , w > w i . \nu\longmapsto\nu S_x^m,\qquad S_x = I + x(P-I),\qquad w > w_i. ν ⟼ ν S x m , S x = I + x ( P − I ) , w > w i .
These formulas already average over the binomial multiplicity. Every intermediate state satisfies the invariant. The resulting credit is continuous and nondecreasing as a function of x ∈ [ 0 , 1 ] x \in[0,1] x ∈ [ 0 , 1 ] . One way to see monotonicity in x x x is to condition on the number of exposures: credit increases with that number, and the binomial count increases stochastically with x x x .
Define the auxiliary failure probability and offline dual contribution by
y i ( w ) = ν i ( w ) 1 , α i ( w ) = γ − ν i ( w ) h , α i = ∫ 0 ∞ α i ( w ) d w . y_i(w) = \nu_i(w)\mathbf{1},\qquad\alpha_i(w) = \gamma- \nu_i(w)h,\qquad\alpha_i = \int_0^\infty\alpha_i(w)\,dw. y i ( w ) = ν i ( w ) 1 , α i ( w ) = γ − ν i ( w ) h , α i = ∫ 0 ∞ α i ( w ) d w .
The surrogate primal objective is P = ∑ i ∫ 0 ∞ ( 1 − y i ( w ) ) d w \mathcal{P} = \sum_i \int_0^\infty(1-y_i(w))\,dw P = ∑ i ∫ 0 ∞ ( 1 − y i ( w )) d w . The nonselection bound in (3) implies that the expected actual matching value is at least P \mathcal{P} P . Above all previously revealed weights, ν i ( w ) = π \nu_i(w) = \pi ν i ( w ) = π , so the integrals have finite support.
Here is an explicit water-filling rule. For each real vertex i i i , let α i [ x ] \alpha_i[x] α i [ x ] be its total offline credit after a hypothetical update with probability x x x , and put
d i ( x ) = γ w i − α i [ x ] , 0 ≤ x ≤ 1. d_i(x) = \gamma w_i - \alpha_i[x],\qquad0 \le x \le1. d i ( x ) = γ w i − α i [ x ] , 0 ≤ x ≤ 1.
Introduce a dummy vertex ⊥ \perp ⊥ with d ⊥ ( x ) = 0 d_\perp(x) = 0 d ⊥ ( x ) = 0 . Choose a maximizer, with a fixed deterministic tie rule, of the concave optimization problem
max { ∑ i ∈ L ∪ { ⊥ } ∫ 0 v i d i ( x ) d x : v i ≥ 0 , ∑ i v i = 1 } . (9) \max\left\{\sum_{i\in L\cup\{\perp\}}\int_0^{v_i} d_i(x)\,dx : v_i \ge0,\ \sum_i v_i = 1\right\}. \tag*{(9)} max ⎩ ⎨ ⎧ i ∈ L ∪ { ⊥ } ∑ ∫ 0 v i d i ( x ) d x : v i ≥ 0 , i ∑ v i = 1 ⎭ ⎬ ⎫ . (9)
Each d i d_i d i is continuous and nonincreasing, so a maximizer exists. The first-order optimality conditions say that all positive coordinates have a common terminal deficit β \beta β , while unused coordinates have deficit at most β \beta β . The dummy coordinate ensures β ≥ 0 \beta\ge0 β ≥ 0 . Hence, after the updates,
β = max ( 0 , max i ( γ w i − α i ) ) = ∑ i v i ( γ w i − α i ) . \beta= \max\left(0,\max_i(\gamma w_i-\alpha_i)\right)=\sum_i v_i(\gamma w_i-\alpha_i). β = max ( 0 , i max ( γ w i − α i ) ) = i ∑ v i ( γ w i − α i ) .
The maximization can equivalently be implemented by increasing the coordinates with the largest current deficit until the total mass is one, using the dummy coordinate whenever every real deficit is nonpositive. This establishes dual feasibility for the γ \gamma γ -scaled weights, which persists because every α i \alpha_i α i is nondecreasing.
Relation to the finite algorithm. The ideal algorithm uses this water-filling vector in the sampling-and-tournament procedure of § 4 . The pseudocode there uses the capped, scaled seed and a rational grid; Appendix § 10 accounts for those three implementation losses. We first prove the budget for the ideal water-filling rule above.
Thresholds at or below the current edge weight
For w ≤ w i w \le w_i w ≤ w i , fix a pre-arrival state ν \nu ν satisfying the invariant and write
y ( x ) = ν R x m 1 , a ( x ) = ν R x m h . y(x)=\nu R_x^m\mathbf{1},\qquad a(x)=\nu R_x^m h. y ( x ) = ν R x m 1 , a ( x ) = ν R x m h .
The resolvent identity in (8) is
m ( T − I ) ( h − 1 ) = h . (10) m(T-I)(h-\mathbf{1})=h. \tag*{(10)} m ( T − I ) ( h − 1 ) = h . (10)
Differentiating the finite polynomial R x m R_x^m R x m gives
− y ′ ( x ) + a ′ ( x ) = m ν R x m − 1 ( T − I ) ( h − 1 ) = ν R x m − 1 h ≥ ν R x m h = a ( x ) . -y'(x)+a'(x)=m\nu R_x^{m-1}(T-I)(h-\mathbf{1})=\nu R_x^{m-1}h\ge\nu R_x^m h=a(x). − y ′ ( x ) + a ′ ( x ) = m ν R x m − 1 ( T − I ) ( h − 1 ) = ν R x m − 1 h ≥ ν R x m h = a ( x ) .
The inequality uses monotonicity on states satisfying the invariant for the final Bernoulli exposure trial. Integrating from zero to the chosen probability v i v_i v i , and using that a a a decreases, gives
y ( 0 ) − y ( v i ) + a ( v i ) − a ( 0 ) ≥ v i a ( v i ) . (11) y(0)-y(v_i)+a(v_i)-a(0)\ge v_i a(v_i). \tag*{(11)} y ( 0 ) − y ( v i ) + a ( v i ) − a ( 0 ) ≥ v i a ( v i ) . (11)
Thus the increase in the surrogate primal objective pays the offline-credit increase and the appropriate share of the new online dual variable.
Thresholds above the current edge weight
For w > w i w>w_i w > w i , write a ( x ) = ν S x m h a(x)=\nu S_x^m h a ( x ) = ν S x m h . Define
k = ( I − m ( P − I ) ) h . k=(I-m(P-I))h. k = ( I − m ( P − I )) h .
By (10) ,
k = m ( P − T ) ( 1 − h ) = m [ q b ( 1 − h ( z + 1 ) ) + p W ( z ) ( 1 − h ( 0 ) ) ] at age z . (12) k=m(P-T)(1-h)=m\left[q b(1-h(z+1))+pW(z)(1-h(0))\right]\quad\text{at age }z. \tag*{(12)} k = m ( P − T ) ( 1 − h ) = m [ q b ( 1 − h ( z + 1 )) + p W ( z ) ( 1 − h ( 0 )) ] at age z . (12)
Hence k ≥ 0 k\ge0 k ≥ 0 pointwise. Stationarity also gives π k = π h = γ \pi k=\pi h=\gamma π k = π h = γ . Let ρ = ν S x m − 1 \rho=\nu S_x^{m-1} ρ = ν S x m − 1 . Since 0 ≤ ρ ≤ π 0\le\rho\le\pi 0 ≤ ρ ≤ π ,
− a ′ ( x ) = − m ρ ( P − I ) h = ρ k − ρ h ≤ γ − ρ h ≤ γ − a ( x ) . -a'(x)=-m\rho(P-I)h=\rho k-\rho h\le\gamma-\rho h\le\gamma-a(x). − a ′ ( x ) = − m ρ ( P − I ) h = ρ k − ρ h ≤ γ − ρ h ≤ γ − a ( x ) .
The final comparison again follows from monotonicity on states satisfying the invariant. Integrating and using that a a a decreases gives
a ( 0 ) − a ( v i ) ≤ v i ( γ − a ( v i ) ) . (13) a(0)-a(v_i) \le v_i(\gamma-a(v_i)). \tag*{(13)} a ( 0 ) − a ( v i ) ≤ v i ( γ − a ( v i )) . (13)
There is no primal gain when w > w i w>w_i w > w i . The offline dual-credit increase is bounded by v i v_i v i times its post-arrival credit, the right side of (13) . This exact inequality replaces the scalar gap-rate condition.
Completion of the competitive analysis
For each vertex, integrate (11) below the current edge weight and (13) above it. Summing over vertices yields the following bound, where α i ( w ) \alpha_i(w) α i ( w ) and α i \alpha_i α i denote their post-arrival values:
Δ P − ∑ i Δ α i ≥ ∑ i v i [ ∫ 0 w i ( γ − α i ( w ) ) d w − ∫ w i ∞ α i ( w ) d w ] = ∑ i v i ( γ w i − α i ) = β . \begin{aligned}
\Delta P-\sum_i\Delta\alpha_i &\ge\sum_i v_i\left[\int_0^{w_i}(\gamma-\alpha_i(w))\,\mathrm{d}w-\int_{w_i}^{\infty}\alpha_i(w)\,\mathrm{d}w\right]\\
&=\sum_i v_i(\gamma w_i-\alpha_i)=\beta.
\end{aligned} Δ P − i ∑ Δ α i ≥ i ∑ v i [ ∫ 0 w i ( γ − α i ( w )) d w − ∫ w i ∞ α i ( w ) d w ] = i ∑ v i ( γ w i − α i ) = β .
All dual variables start at zero. Therefore P ≥ ∑ i α i + ∑ j β j \mathcal{P}\ge\sum_i\alpha_i+\sum_j\beta_j P ≥ ∑ i α i + ∑ j β j , while the dual constraints give ∑ i α i + ∑ j β j ≥ γ OPT \sum_i\alpha_i+\sum_j\beta_j\ge\gamma\operatorname{OPT} ∑ i α i + ∑ j β j ≥ γ OPT . Since the expected actual value is at least P \mathcal{P} P , the theorem follows.
The choice of residual potential
The resolvent also explains which part of the construction remains to be optimized. For a fixed miss kernel, it gives the largest stationary credit permitted by the local update inequality for w ≤ w i w\le w_i w ≤ w i among bounded linear residual potentials.
Proposition 5 (Optimality for the local linear-credit criterion). Let g g g be a bounded column vector satisfying
m ν ( T − I ) ( g − 1 ) ≥ ν g for every state ν satisfying the invariant. (14) m\nu(T-I)(g-1)\ge\nu g\quad\text{for every state }\nu\text{ satisfying the invariant.} \tag*{(14)} m ν ( T − I ) ( g − 1 ) ≥ ν g for every state ν satisfying the invariant. (14) Then π g ≤ π h = γ \pi g\le\pi h=\gamma π g ≤ π h = γ . The vector h h h attains equality in (14) for every state.
Proof. Put R = ( I − m ( T − I ) ) − 1 R=(I-m(T-I))^{-1} R = ( I − m ( T − I ) ) − 1 and d = m ( T − I ) ( g − 1 ) − g d=m(T-I)(g-1)-g d = m ( T − I ) ( g − 1 ) − g . Every row π T n \pi T^n π T n satisfies the invariant: it is the state after n n n successive T T T -updates. Thus π T n d ≥ 0 \pi T^n d\ge0 π T n d ≥ 0 for every n ≥ 0 n\ge0 n ≥ 0 . The positive resolvent series gives
0 ≤ 1 m + 1 ∑ n ≥ 0 ( m m + 1 ) n π T n d = π R d = π ( h − g ) . 0\le\frac{1}{m+1}\sum_{n\ge0}\left(\frac{m}{m+1}\right)^n\pi T^n d=\pi Rd=\pi(h-g). 0 ≤ m + 1 1 n ≥ 0 ∑ ( m + 1 m ) n π T n d = π R d = π ( h − g ) .
All series converge absolutely because the vectors are bounded. The last identity and the equality assertion follow from (10) .
The proposition concerns the local criterion (14) . It places no upper bound on matching algorithms or on other dual analyses. Within this criterion, improving γ \gamma γ requires changing the failure matrix. We next optimize the win map that determines this kernel.
Optimal Win Maps at a Fixed Reset Probability
Fix m ≥ 2 m \ge2 m ≥ 2 , p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) , and q = 1 − p q=1-p q = 1 − p . The output Y Y Y of the stationary reset process has probabilities Pr ( Y = − 1 ) = q \Pr(Y=-1)=q Pr ( Y = − 1 ) = q and Pr ( Y = z ) = p q z \Pr(Y=z)=p q^z Pr ( Y = z ) = p q z for z ≥ 0 z \ge0 z ≥ 0 . For a nondecreasing map W : { − 1 , 0 , 1 , … } → [ 0 , 1 ] W:\{-1,0,1,\ldots\}\to[0,1] W : { − 1 , 0 , 1 , … } → [ 0 , 1 ] , let T W T_W T W be its miss kernel and define
γ ( W ) = 1 − ( 1 − a ) ∑ n ≥ 0 a n π T W n 1 , a = m m + 1 , π ( z ) = p q z . \gamma(W)=1-(1-a)\sum_{n\ge0}a^n\pi T_W^n\mathbf{1},\qquad a=\frac{m}{m+1},\qquad\pi(z)=p q^z. γ ( W ) = 1 − ( 1 − a ) n ≥ 0 ∑ a n π T W n 1 , a = m + 1 m , π ( z ) = p q z .
This section optimizes γ ( W ) \gamma(W) γ ( W ) under the multiplicity-one tournament constraint. Feasibility for larger multiplicities is a separate condition. Let W \mathcal{W} W be the class of nondecreasing maps W : { − 1 , 0 , 1 , … } → [ 0 , 1 ] W:\{-1,0,1,\ldots\}\to[0,1] W : { − 1 , 0 , 1 , … } → [ 0 , 1 ] satisfying W ( Y ) ⪯ i c x U m − 1 W(Y)\preceq_{\mathrm{icx}} U^{m-1} W ( Y ) ⪯ icx U m − 1 for a uniform U ∈ [ 0 , 1 ] U\in[0,1] U ∈ [ 0 , 1 ] .
Theorem 6 (Optimality of pooling). Put u z = 1 − p q z u_z=1-pq^z u z = 1 − p q z and b 0 = q m − 1 / m b_0=q^{m-1}/m b 0 = q m − 1 / m . For b ∈ [ b 0 , 1 / m ] b\in[b_0,1/m] b ∈ [ b 0 , 1/ m ] , define
ϕ b ( u ) = max { b u , u m / m } , W b ( − 1 ) = b , W b ( z ) = ϕ b ( u z + 1 ) − ϕ b ( u z ) u z + 1 − u z . \phi_b(u)=\max\{bu,u^m/m\},\qquad W^b(-1)=b,\qquad W^b(z)=\frac{\phi_b(u_{z+1})-\phi_b(u_z)}{u_{z+1}-u_z}. ϕ b ( u ) = max { b u , u m / m } , W b ( − 1 ) = b , W b ( z ) = u z + 1 − u z ϕ b ( u z + 1 ) − ϕ b ( u z ) . Every W b W^b W b is nondecreasing, has stationary mean 1 / m 1/m 1/ m , and satisfies W b ( Y ) ⪯ i c x U m − 1 W^b(Y)\preceq_{\mathrm{icx}} U^{m-1} W b ( Y ) ⪯ icx U m − 1 for a uniform U ∈ [ 0 , 1 ] U\in[0,1] U ∈ [ 0 , 1 ] . Moreover,
sup W ∈ W γ ( W ) = max b 0 ≤ b ≤ 1 / m γ ( W b ) . \sup_{W\in\mathcal{W}}\gamma(W)=\max_{b_0\le b\le1/m}\gamma(W^b). W ∈ W sup γ ( W ) = b 0 ≤ b ≤ 1/ m max γ ( W b ) . Thus an optimal map exists and pools the youngest ages, possibly modifying one boundary age, while preserving all older quantile-bin scores. The statement concerns γ ( W ) \gamma(W) γ ( W ) and this geometric seed; it does not assert that pooling preserves the tournament constraints for larger multiplicities.
We first establish the comparison principle that connects quantiles to the online objective.
Lemma 7 (Upper-tail comparison). Let W 0 , W 1 W^0,W^1 W 0 , W 1 be nondecreasing maps with the same baseline W 0 ( − 1 ) = W 1 ( − 1 ) = b < 1 W^0(-1)=W^1(-1)=b<1 W 0 ( − 1 ) = W 1 ( − 1 ) = b < 1 . If
∑ z ≥ k p q z W 1 ( z ) ≥ ∑ z ≥ k p q z W 0 ( z ) ( k ≥ 0 ) , \sum_{z\ge k}p q^z W^1(z)\ge\sum_{z\ge k}p q^z W^0(z)\qquad(k\ge0), z ≥ k ∑ p q z W 1 ( z ) ≥ z ≥ k ∑ p q z W 0 ( z ) ( k ≥ 0 ) , then γ ( W 1 ) ≥ γ ( W 0 ) \gamma(W^1)\ge\gamma(W^0) γ ( W 1 ) ≥ γ ( W 0 ) .
Proof. We use a short renewal formula. For a map W W W with mean μ = E [ W ( Y ) ] \mu=\mathbb{E}[W(Y)] μ = E [ W ( Y )] , write
r = a q ( 1 − b ) , t = r / q = a ( 1 − b ) , F W ( x ) = ∑ z ≥ 0 x z ( 1 − W ( z ) ) , R = 1 − a p F W ( r ) . r=aq(1-b),\qquad t=r/q=a(1-b),\qquad F_W(x)=\sum_{z\ge0}x^z(1-W(z)),\qquad R=1-apF_W(r). r = a q ( 1 − b ) , t = r / q = a ( 1 − b ) , F W ( x ) = z ≥ 0 ∑ x z ( 1 − W ( z )) , R = 1 − a p F W ( r ) .
Let h = 1 − ( I − m ( T W − I ) ) − 1 1 h=1-(I-m(T_W-I))^{-1}\mathbf{1} h = 1 − ( I − m ( T W − I ) ) − 1 1 and ℓ 0 = 1 − h ( 0 ) \ell_0=1-h(0) ℓ 0 = 1 − h ( 0 ) . Conditioning on the first reset, or summing the miss recurrence from age zero, gives
ℓ 0 = 1 − a ( 1 − r ) R , γ ( W ) = m 1 + m b [ b + ( μ − b ) ℓ 0 ] . (15) \ell_0=\frac{1-a}{(1-r)R},\qquad\gamma(W)=\frac{m}{1+mb}\left[b+(\mu-b)\ell_0\right]. \tag*{(15)} ℓ 0 = ( 1 − r ) R 1 − a , γ ( W ) = 1 + mb m [ b + ( μ − b ) ℓ 0 ] . (15)
For the second identity, stationarity implies π ( P − T W ) = b π + ( μ − b ) δ 0 \pi(P-T_W)=b\pi+(\mu-b)\delta_0 π ( P − T W ) = bπ + ( μ − b ) δ 0 ; apply this equality to h h h and use m ( I − T W ) ( 1 − h ) = h m(I-T_W)(1-h)=h m ( I − T W ) ( 1 − h ) = h . All denominators are positive because
R ≥ 1 − r − a p 1 − r > 0 , r + a p = a ( q ( 1 − b ) + p ) < 1. R\ge\frac{1-r-ap}{1-r}>0,\qquad r+ap=a\bigl(q(1-b)+p\bigr)<1. R ≥ 1 − r 1 − r − a p > 0 , r + a p = a ( q ( 1 − b ) + p ) < 1.
Interpolate linearly between the two maps. Regarding c z = p 2 q z W ( z ) c_z=p^2q^zW(z) c z = p 2 q z W ( z ) as the stationary score mass at age z z z , differentiation of (15) gives
g z : = ∂ γ ∂ c z = m ℓ 0 1 + m b ( 1 − a ( μ − b ) p R t z ) . (16) g_z:=\frac{\partial\gamma}{\partial c_z}=\frac{m\ell_0}{1+mb}\left(1-\frac{a(\mu-b)}{pR}t^z\right). \tag*{(16)} g z := ∂ c z ∂ γ = 1 + mb m ℓ 0 ( 1 − pR a ( μ − b ) t z ) . (16)
Since μ ≥ b \mu\ge b μ ≥ b and 0 < t < 1 0<t<1 0 < t < 1 , these marginal values are nondecreasing in age. They are positive as well. Indeed, μ = p + q b − p 2 F W ( q ) \mu=p+qb-p^2F_W(q) μ = p + q b − p 2 F W ( q ) , so the numerator of the smallest bracket is
R − a ( μ − b ) p = 1 − a ( 1 − b ) + a p ( F W ( q ) − F W ( r ) ) > 0. R-\frac{a(\mu-b)}{p}=1-a(1-b)+ap\bigl(F_W(q)-F_W(r)\bigr)>0. R − p a ( μ − b ) = 1 − a ( 1 − b ) + a p ( F W ( q ) − F W ( r ) ) > 0.
Put δ z = p 2 q z ( W 1 ( z ) − W 0 ( z ) ) \delta_z=p^2q^z\bigl(W^1(z)-W^0(z)\bigr) δ z = p 2 q z ( W 1 ( z ) − W 0 ( z ) ) and D k = ∑ z ≥ k δ z ≥ 0 D_k=\sum_{z\ge k}\delta_z\ge0 D k = ∑ z ≥ k δ z ≥ 0 . Along the interpolation, summation by parts yields
d d τ γ ( ( 1 − τ ) W 0 + τ W 1 ) = g 0 D 0 + ∑ k ≥ 1 ( g k − g k − 1 ) D k ≥ 0. \frac{d}{d\tau}\gamma\bigl((1-\tau)W^0+\tau W^1\bigr)=g_0D_0+\sum_{k\ge1}(g_k-g_{k-1})D_k\ge0. d τ d γ ( ( 1 − τ ) W 0 + τ W 1 ) = g 0 D 0 + k ≥ 1 ∑ ( g k − g k − 1 ) D k ≥ 0.
The series and differentiation are justified by the geometric bound on the masses, the uniform positive lower bound on R R R , and the uniform bound on the gradients. Integrating in τ \tau τ proves the lemma. □
Proof of Theorem 6 . For a bounded random variable X X X with quantile function Q X Q_X Q X , let J X ( u ) = ∫ u 1 Q X ( v ) d v J_X(u)=\int_u^1Q_X(v)\,dv J X ( u ) = ∫ u 1 Q X ( v ) d v . The elementary dual identities
J X ( u ) = inf s { ( 1 − u ) s + E [ ( X − s ) + ] } , J_X(u)=\inf_s\{(1-u)s+\mathbb{E}[(X-s)_+]\}, J X ( u ) = s inf {( 1 − u ) s + E [( X − s ) + ]} ,
E [ ( X − s ) + ] = sup 0 ≤ u ≤ 1 { J X ( u ) − ( 1 − u ) s } \mathbb{E}[(X-s)_+]=\sup_{0\le u\le1}\{J_X(u)-(1-u)s\} E [( X − s ) + ] = 0 ≤ u ≤ 1 sup { J X ( u ) − ( 1 − u ) s }
show that increasing-convex order is equivalent to comparison of these integrated upper quantiles. In particular, the reference variable V = U m − 1 V=U^{m-1} V = U m − 1 has mean 1 / m 1/m 1/ m and J V ( u ) = ( 1 − u m ) / m J_V(u)=(1-u^m)/m J V ( u ) = ( 1 − u m ) / m .
The convex function ϕ b \phi_b ϕ b has ϕ b ( 0 ) = 0 \phi_b(0)=0 ϕ b ( 0 ) = 0 , ϕ b ( q ) = b q \phi_b(q)=bq ϕ b ( q ) = b q , and ϕ b ( 1 ) = 1 / m \phi_b(1)=1/m ϕ b ( 1 ) = 1/ m , with all slopes in [ 0 , 1 ] [0,1] [ 0 , 1 ] . Its successive secants therefore define a nondecreasing W b W^b W b on [ 0 , 1 ] [0,1] [ 0 , 1 ] . The integrated lower-quantile curve of W b ( Y ) W^b(Y) W b ( Y ) is the chordal interpolant of ϕ b \phi_b ϕ b at 0 , q , u 1 , u 2 , … , 1 0,q,u_1,u_2,\ldots,1 0 , q , u 1 , u 2 , … , 1 . Each chord lies above ϕ b \phi_b ϕ b , which lies above u m / m u^m/m u m / m . The endpoint at one gives the full mean 1 / m 1/m 1/ m , so its upper-quantile curve lies below J V J_V J V . This proves singleton feasibility. The crossing of the line b u bu b u with u m / m u^m/m u m / m also gives the stated pooling form; at most one age bin contains the crossing.
Now let W W W be any map in the supremum, and set b = W ( − 1 ) b=W(-1) b = W ( − 1 ) and μ = E [ W ( Y ) ] \mu=\mathbb{E}[W(Y)] μ = E [ W ( Y )] . Monotonicity and singleton feasibility imply b ≤ μ ≤ 1 / m b\le\mu\le1/m b ≤ μ ≤ 1/ m . At the atom cut u k u_k u k , the integrated upper tail is
U k = ∑ z ≥ k p 2 q z W ( z ) . U_k=\sum_{z\ge k}p^2q^zW(z). U k = z ≥ k ∑ p 2 q z W ( z ) .
The quantile constraint gives U k ≤ ( 1 − u k m ) / m U_k\le(1-u_k^m)/m U k ≤ ( 1 − u k m ) / m . All lower atoms have score at least b b b and total mass u k u_k u k , so U k ≤ μ − b u k ≤ 1 / m − b u k U_k\le\mu-bu_k\le1/m-bu_k U k ≤ μ − b u k ≤ 1/ m − b u k as well. If b ≥ b 0 b\ge b_0 b ≥ b 0 , these bounds combine to give
U k ≤ 1 m − max { b u k , u k m / m } = ∑ z ≥ k p 2 q z W b ( z ) . U_k\le\frac{1}{m}-\max\{bu_k,u_k^m/m\}=\sum_{z\ge k}p^2q^zW^b(z). U k ≤ m 1 − max { b u k , u k m / m } = z ≥ k ∑ p 2 q z W b ( z ) .
Lemma 7 proves γ ( W ) ≤ γ ( W b ) \gamma(W)\le\gamma(W^b) γ ( W ) ≤ γ ( W b ) , including competitors with mean below 1 / m 1/m 1/ m .
If b < b 0 b<b_0 b < b 0 , keep this baseline and replace the reset scores by the unpooled quantile-bin means. Their upper tails are exactly ( 1 − u k m ) / m (1-u_k^m)/m ( 1 − u k m ) / m , so the same lemma shows that this replacement cannot lower γ \gamma γ . Raising its baseline to b 0 b_0 b 0 then increases every desired win probability on every seed path and cannot lower the discounted success probability. The resulting map is W b 0 W^{b_0} W b 0 .
Finally, the maximum on the right is attained. For each fixed age, W b ( z ) W^b(z) W b ( z ) is continuous in b b b , including at pooling boundaries and at b = 1 / m b = 1/m b = 1/ m . Bounded convergence makes π T n W b 1 \pi T^nW_b1 π T n W b 1 continuous for every fixed n n n , and the resolvent tail is bounded uniformly in b b b by a N + 1 a^{N+1} a N + 1 after index N N N . Hence γ ( W b ) \gamma(W^b) γ ( W b ) is continuous on the compact interval [ b 0 , 1 / m ] [b_0,1/m] [ b 0 , 1/ m ] . Every map in this interval is singleton-feasible, which also proves the reverse inequality in the theorem. □
Remark 8. The competitors include every bounded monotone map on the infinite age space, including capped and other finite-valued maps. If one restricts the optimization to finite-valued maps, the same value is a supremum: pooling a sufficiently far upper tail of W b W^b W b into its conditional mean preserves singleton feasibility, and the resulting values of γ \gamma γ converge to γ ( W b ) \gamma(W^b) γ ( W b ) . Attainment by a finite-valued map is not required or asserted.
Why the age state suffices
The preceding optimization also covers seeds with a richer internal state. The relevant property is that a reset cycle produces at most one output above the fixed baseline. Averaging that output over the internal randomness leaves the avoidance objective unchanged.
Let S S S be a finite or countable partially ordered state space with a least element 0 0 0 . A Markov kernel R R R on S S S is stochastically monotone if R f Rf R f is increasing whenever f f f is bounded and increasing. Write μ ⪯ s t ν \mu\preceq_{\mathrm{st}} \nu μ ⪯ st ν if μ f ≤ ν f \mu f \le\nu f μ f ≤ ν f for every such f f f . Fix such a kernel, a reset probability p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) , a baseline b ∈ [ 0 , 1 ) b \in[0,1) b ∈ [ 0 , 1 ) , and an increasing function W : S → [ b , 1 ] W:S \to[b,1] W : S → [ b , 1 ] .
On each exposure, independently of the past, the seed resets with probability p p p . A reset from state Z Z Z outputs W ( Z ) W(Z) W ( Z ) and sends the state to 0 0 0 . Otherwise, the output is b b b and the next state is sampled from R ( Z , ⋅ ) R(Z,\cdot) R ( Z , ⋅ ) , using fresh randomness. Put q = 1 − p q = 1-p q = 1 − p . The transition kernel and stationary distribution are
P = p 1 δ 0 + q R , T = p ( 1 − W ) δ 0 + q ( 1 − b ) R , P = p\mathbf{1}\delta_0 + qR,\qquad T = p(1-W)\delta_0 + q(1-b)R, P = p 1 δ 0 + q R , T = p ( 1 − W ) δ 0 + q ( 1 − b ) R ,
π = p ∑ k ≥ 0 q k δ 0 R k . \pi= p\sum_{k\ge0}q^k\delta_0R^k. π = p k ≥ 0 ∑ q k δ 0 R k .
The stationary process can be constructed from independent reset bits indexed by all integer times: start from 0 0 0 at the last reset and apply the intervening R R R transitions.
Proposition 9 (Reduction to age-dependent scores). For the stationary seed above, define
W ‾ ( − 1 ) = b , W ‾ ( k ) = δ 0 R k W ( k ≥ 0 ) . \overline{W}(-1)=b,\qquad\overline{W}(k)=\delta_0R^kW\quad(k\ge0). W ( − 1 ) = b , W ( k ) = δ 0 R k W ( k ≥ 0 ) . This is a nondecreasing geometric-age map with reset probability p p p . Write X t X_t X t and X ‾ t \overline{X}_t X t for the original and age-dependent outputs. For every finite deterministic set of exposure indices S S S ,
E [ ∏ t ∈ S ( 1 − X t ) ] = E [ ∏ t ∈ S ( 1 − X ‾ t ) ] . (17) \mathbb{E}\left[\prod_{t\in S}(1-X_t)\right]
=
\mathbb{E}\left[\prod_{t\in S}(1-\overline{X}_t)\right]. \tag*{(17)} E [ t ∈ S ∏ ( 1 − X t ) ] = E [ t ∈ S ∏ ( 1 − X t ) ] . (17) Moreover, the combined desired win probabilities U S = 1 − ∏ t ∈ S ( 1 − X t ) U_S=1-\prod_{t\in S}(1-X_t) U S = 1 − ∏ t ∈ S ( 1 − X t ) and U ‾ S = 1 − ∏ t ∈ S ( 1 − X ‾ t ) \overline{U}_S=1-\prod_{t\in S}(1-\overline{X}_t) U S = 1 − ∏ t ∈ S ( 1 − X t ) admit a coupling such that
U ‾ S = E [ U S ∣ B ] , (18) \overline{U}_S=\mathbb{E}[U_S\mid\mathcal{B}], \tag*{(18)} U S = E [ U S ∣ B ] , (18) where B \mathcal{B} B is the sigma-field generated by the two-sided reset sequence. Thus averaging over the internal randomness preserves every discounted sum of these failure probabilities, and all the tournament inequalities of Lemma 3 .
Proof. Condition on the complete reset sequence. Each cycle contains independent internal R R R randomness and has just one possibly nonbaseline output, at its terminating reset. If that reset follows k k k ordinary transitions, the conditional mean of its output is δ 0 R k W \delta_0R^kW δ 0 R k W . All other outputs equal b b b . Consequently,
E [ ∏ t ∈ S ( 1 − X t ) ∣ B ] = ∏ t ∈ S ( 1 − E [ X t ∣ B ] ) . \mathbb{E}\left[\left.\prod_{t\in S}(1-X_t)\right| \mathcal{B}\right]=\prod_{t\in S}(1-\mathbb{E}[X_t\mid\mathcal{B}]). E [ t ∈ S ∏ ( 1 − X t ) B ] = t ∈ S ∏ ( 1 − E [ X t ∣ B ]) .
Using the same reset bits in the geometric-age process gives X ‾ t = E [ X t ∣ B ] \overline{X}_t=\mathbb{E}[X_t\mid\mathcal{B}] X t = E [ X t ∣ B ] and proves both displayed identities. This reasoning also applies to the cycle crossing the start of S S S : its preceding reset is fixed by the two-sided sequence.
Since 0 0 0 is the least state, δ 0 ⪯ s t δ 0 R \delta_0\preceq_{\mathrm{st}}\delta_0R δ 0 ⪯ st δ 0 R . Stochastic monotonicity then gives δ 0 R k ⪯ s t δ 0 R k + 1 \delta_0R^k\preceq_{\mathrm{st}}\delta_0R^{k+1} δ 0 R k ⪯ st δ 0 R k + 1 for every k k k . Applying W W W proves that W ‾ \overline{W} W is nondecreasing; its range lies in [ b , 1 ] [b,1] [ b , 1 ] .
Equation (17) preserves every term of the absolutely convergent discounted avoidance sum. Conditional Jensen applied to (18) gives E [ φ ( U ‾ S ) ] ≤ E [ φ ( U S ) ] \mathbb{E}[\varphi(\overline{U}_S)]\leq\mathbb{E}[\varphi(U_S)] E [ φ ( U S )] ≤ E [ φ ( U S )] for every convex φ : [ 0 , 1 ] → R \varphi:[0,1]\to\mathbb{R} φ : [ 0 , 1 ] → R . Taking S S S to be a consecutive block and φ ( u ) = ( u − t ) + \varphi(u)=(u-t)_+ φ ( u ) = ( u − t ) + proves all the tournament comparisons.
Corollary 10. Fix m m m and p p p . Among the monotone regenerative seeds above satisfying the singleton constraint X 0 ⪯ i c x U m − 1 X_0\preceq_{\mathrm{icx}}U^{m-1} X 0 ⪯ icx U m − 1 , the maximum value of γ \gamma γ in (1) is
max q m − 1 / m ≤ b ≤ 1 / m γ ( W b ) . \max_{q^{m-1}/m\leq b\leq1/m}\gamma(W^b). q m − 1 / m ≤ b ≤ 1/ m max γ ( W b ) . In particular, a pooled geometric-age map attains the optimum.
Proof. The reduction to age-dependent scores preserves γ \gamma γ and the singleton constraint, so Theorem 6 gives the upper bound. The geometric-age process itself belongs to this class: take S = Z ≥ 0 S=\mathbb{Z}_{\geq0} S = Z ≥ 0 and R ( k , k + 1 ) = 1 R(k,k+1)=1 R ( k , k + 1 ) = 1 . The maximum is therefore attained by the pooled map from that theorem.
The reduction requires no negative association of the original output; the resulting nondecreasing age map has that property. The corollary optimizes under the singleton constraint. Averaging preserves any constraints for repeated candidates that already hold, whereas replacing the resulting map by its pooled optimizer still requires checking those additional constraints. Scores above the baseline on intermediate transitions are outside the regenerative class considered here.
Setting the Parameters
We use two instantiations of the following family:
m ∈ { 500 , 1000 } , p = 9 2 m , q = 1 − p , A = m 50 , b = ( 1 − p q A ) m − 1 m . (19) m\in\{500,1000\},\qquad p=\frac{9}{2m},\qquad q=1-p,\qquad A=\frac{m}{50},\qquad b=\frac{(1-pq^A)^{m-1}}{m}. \tag*{(19)} m ∈ { 500 , 1000 } , p = 2 m 9 , q = 1 − p , A = 50 m , b = m ( 1 − p q A ) m − 1 . (19)
The choice m = 1000 m=1000 m = 1000 proves Theorem 1 ; the choice m = 500 m=500 m = 500 gives a 0.556-competitive construction with a shorter certificate. Put u z = 1 − p q z u_z=1-pq^z u z = 1 − p q z . The win map is
W ( − 1 ) = b , W ( z ) = { b , 0 ≤ z < A , u z + 1 m − u z m m p 2 q z , z ≥ A . (20) W(-1)=b,\qquad W(z)=
\begin{cases}
b, & 0\leq z<A,\\
\frac{u_{z+1}^m-u_z^m}{mp^2q^z}, & z\geq A.
\end{cases} \tag*{(20)} W ( − 1 ) = b , W ( z ) = { b , m p 2 q z u z + 1 m − u z m , 0 ≤ z < A , z ≥ A . (20)
It is the pooled map W b W^b W b of Theorem 6 at an integer pooling boundary, illustrated in Figure 1 . Thus it is nondecreasing, has mean 1 / m 1/m 1/ m , and satisfies the singleton tournament constraint.
Figure 1. The pooled map for the simpler instantiation, with m = 500 m=500 m = 500 , p = 9 / 1000 p=9/1000 p = 9/1000 , and A = 10 A=10 A = 10 . The horizontal coordinate reverses and magnifies the upper quantiles; the vertical coordinate scales their integral by 500. The blue curve is linear for u ≤ u 10 u \le u_{10} u ≤ u 10 (right of the dotted line) and joins the unchanged quantile-bin endpoints on the left. Dots show selected bin endpoints; the tail chords lie slightly above the gray reference curve.
The proof uses the conditions summarized below. The selection conditions concern the constant-size random process and are independent of the input graph.
Table 1. Two certified instantiations. Here s 0 s_0 s 0 separates the small-threshold estimate from the chord verification. Every displayed lower bound is strict. The ideal bounds use the same 20-term rational Bonferroni expression; the finite bounds subtract 10 − 8 + 1 / ( m ⋅ 10 6 ) + 10 − 6 10^{-8} + 1/(m \cdot10^6) + 10^{-6} 1 0 − 8 + 1/ ( m ⋅ 1 0 6 ) + 1 0 − 6 for capping, scaling, and water filling, respectively.
Table 2.
The tournament inequalities
Lemma 11 (Computer-assisted tournament certificate). For the parameters in (19) and the map (20) ,
E [ ( s − ∏ k = 1 r ( 1 − W ( Y k ) ) ) + ] ≤ H r ( s ) ( 1 ≤ r < m , 0 ≤ s ≤ 1 ) . \mathbb{E}\left[\left(s-\prod_{k=1}^{r}(1-W(Y_k))\right)_{+}\right] \le H_r(s) \qquad(1 \le r < m,\ 0 \le s \le1). E [ ( s − k = 1 ∏ r ( 1 − W ( Y k )) ) + ] ≤ H r ( s ) ( 1 ≤ r < m , 0 ≤ s ≤ 1 ) .
Proof. The singleton case follows analytically from the quantile construction. Appendix § 9 reduces each remaining case to a finite collection of explicit inequalities. Condition on the first reset; two positive renewal recurrences give the minimum and mean failure of the fresh remainder. Replacing that remainder by its endpoint chord and integrating out the initial age by conditional Jensen gives a convex upper bound with at most 2 r 2r 2 r terms and a no-reset atom. We take the values of s 0 s_0 s 0 in Table 1 and compare this bound with the reference by a quadratic estimate on [ 0 , s 0 ] [0,s_0] [ 0 , s 0 ] and rational chords on [ s 0 , 1 ] [s_0,1] [ s 0 , 1 ] . Support and mean bounds use 128-bit dyadic rationals. Failure scales are rounded downward to 64 bits, mixture weights upward to 128 bits, and chord endpoint values upward to 96 bits. All interval evaluations use 256 bits of precision.
The repository verifier described in Appendix § 12 passes for every required multiplicity in both instantiations. Its certified statistics are summarized below.
Table 1 (PDF p. 22).
The ratio is the largest upper-to-lower coefficient ratio in the small-threshold comparison. Each chord is certified on the entire unit interval by a strict interval enclosure of the equivalent integer-power comparison in (32) . Neither run required an exact-power fallback. The analytic bounds and the checked partitions cover every real threshold in [ 0 , 1 ] [0,1] [ 0 , 1 ] .
A short rational lower bound on the guarantee
γ \gamma γ can be evaluated without truncating the age space. We specialize the renewal formula to mean 1 / m 1/m 1/ m .
Lemma 12 (Renewal formula for γ \gamma γ ). Let W W W be a geometric-age win map with baseline b b b and mean 1 / m 1/m 1/ m . Set a = m / ( m + 1 ) a=m/(m+1) a = m / ( m + 1 ) , ρ = a q ( 1 − b ) \rho=aq(1-b) ρ = a q ( 1 − b ) , and F ( v ) = ∑ z ≥ 0 v z ( 1 − W ( z ) ) F(v)=\sum_{z\geq0}v^z(1-W(z)) F ( v ) = ∑ z ≥ 0 v z ( 1 − W ( z )) . Then
γ = m b + ( 1 − m b ) ℓ 0 1 + m b , ℓ 0 = 1 − a ( 1 − ρ ) ( 1 − a p F ( ρ ) ) (21) \gamma=\frac{mb+(1-mb)\ell_0}{1+mb},\qquad\ell_0=\frac{1-a}{(1-\rho)(1-apF(\rho))} \tag*{(21)} γ = 1 + mb mb + ( 1 − mb ) ℓ 0 , ℓ 0 = ( 1 − ρ ) ( 1 − a pF ( ρ )) 1 − a (21)
Proof. This is (15) with μ = 1 / m \mu=1/m μ = 1/ m and r = ρ r=\rho r = ρ .
For an integer-pooled map, put B = 1 − b B=1-b B = 1 − b and
c j = ( − 1 ) j + 1 ( m − 1 j ) p j − 1 ( 1 − q j + 1 ) j + 1 . c_j=(-1)^{j+1}\binom{m-1}{j}\frac{p^{j-1}(1-q^{j+1})}{j+1}. c j = ( − 1 ) j + 1 ( j m − 1 ) j + 1 p j − 1 ( 1 − q j + 1 ) .
The identity
1 − W ( z ) = 1 p ∫ q 1 [ 1 − ( 1 − p q z v ) m − 1 ] d v ( z ≥ A ) 1-W(z)=\frac{1}{p}\int_q^1\left[1-(1-pq^zv)^{m-1}\right]\,dv\qquad(z\geq A) 1 − W ( z ) = p 1 ∫ q 1 [ 1 − ( 1 − p q z v ) m − 1 ] d v ( z ≥ A )
shows that the even Bonferroni truncation ∑ j = 1 2 k c j q j z \sum_{j=1}^{2k}c_jq^jz ∑ j = 1 2 k c j q j z is a lower bound on 1 − W ( z ) 1-W(z) 1 − W ( z ) . In particular,
S 20 : = B 1 − ρ A 1 − ρ + ρ A ∑ j = 1 20 c j q A j 1 − ρ q j ≤ F ( ρ ) . (22) S_{20}:=B\frac{1-\rho^A}{1-\rho}+\rho^A\sum_{j=1}^{20}\frac{c_jq^{Aj}}{1-\rho q^j}\leq F(\rho). \tag*{(22)} S 20 := B 1 − ρ 1 − ρ A + ρ A j = 1 ∑ 20 1 − ρ q j c j q A j ≤ F ( ρ ) . (22)
These bounds do not require successive expansion terms to decrease in magnitude. They follow from the usual Bonferroni inequalities for 1 − ( 1 − x ) m − 1 1-(1-x)^{m-1} 1 − ( 1 − x ) m − 1 , followed by integration.
Lemma 13. The parameters in (19) satisfy
0 < m b < 1 , 1 − a p S 20 > 0 , 0 < mb < 1,\qquad1-apS_{20} > 0, 0 < mb < 1 , 1 − a p S 20 > 0 , and
m b + ( 1 − m b ) 1 − a ( 1 − ρ ) ( 1 − a p S 20 ) 1 + m b > g m . (23) \frac{mb + (1-mb)\dfrac{1-a}{(1-\rho)(1-apS_{20})}}{1+mb} > g_m. \tag*{(23)} 1 + mb mb + ( 1 − mb ) ( 1 − ρ ) ( 1 − a p S 20 ) 1 − a > g m . (23) Here g 500 = 55607 / 100000 g_{500}=55607/100000 g 500 = 55607/100000 and g 1000 = 347623 / 625000 g_{1000}=347623/625000 g 1000 = 347623/625000 . Consequently γ > g m \gamma> g_m γ > g m for both rows of Table 1.
Proof. All quantities in the displayed inequalities are rational expressions in (19) . Exact rational evaluation verifies them. The score verifier identified in Appendix § 12 evaluates the displayed expression using rational arithmetic and compares it with the corresponding exact rational g m g_m g m . Finally, the right side of (21) is increasing in F ( ρ ) F(\rho) F ( ρ ) when m b < 1 mb < 1 mb < 1 . Substituting (22) proves the score bound.
Completing the competitive guarantee
Theorem 4 and Lemmas 11–13 give an ideal algorithm with competitive guarantee greater than g m g_m g m for each row of Table 1. For a finite implementation, use the common choices
C = 5 m / 2 , η = 1 − 1 m ⋅ 10 6 , ϵ = 10 − 6 . C = 5m/2,\qquad\eta= 1-\frac{1}{m\cdot10^6},\qquad\epsilon= 10^{-6}. C = 5 m /2 , η = 1 − m ⋅ 1 0 6 1 , ϵ = 1 0 − 6 .
Use the seed map W f ( z ) = η W ( min { z , C } ) W_f(z)=\eta W(\min\{z,C\}) W f ( z ) = η W ( min { z , C }) for z ≥ 0 z\geq0 z ≥ 0 , with baseline W f ( − 1 ) = η b W_f(-1)=\eta b W f ( − 1 ) = η b , and water-filling accuracy ϵ \epsilon ϵ . Appendix § 10 proves that these operations lose less than 10 − 8 10^{-8} 1 0 − 8 from capping, at most 1 / ( m ⋅ 10 6 ) 1/(m\cdot10^6) 1/ ( m ⋅ 1 0 6 ) from scaling, and at most 10 − 6 10^{-6} 1 0 − 6 from water filling, while preserving tournament feasibility. The resulting guarantees are therefore strictly greater than
m = 500 : 0.55607 − 10 − 8 − 2 ⋅ 10 − 9 − 10 − 6 = 0.556068988 > 0.556 , m = 1000 : 0.55619680 − 10 − 8 − 10 − 9 − 10 − 6 = 0.556195789 > 0.556195. \begin{aligned}
m=500 &: \quad0.55607-10^{-8}-2\cdot10^{-9}-10^{-6}=0.556068988>0.556,\\
m=1000 &: \quad0.55619680-10^{-8}-10^{-9}-10^{-6}=0.556195789>0.556195.
\end{aligned} m = 500 m = 1000 : 0.55607 − 1 0 − 8 − 2 ⋅ 1 0 − 9 − 1 0 − 6 = 0.556068988 > 0.556 , : 0.55619680 − 1 0 − 8 − 1 0 − 9 − 1 0 − 6 = 0.556195789 > 0.556195.
The second instantiation proves Theorem 1 .
Scope of the Lean development. The accompanying Lean development formalizes the 0.556195 guarantee for an explicit finite dyadic seed, relative to two explicitly registered literature assumptions: a calibrated seed-to-selector construction and an independent categorical sampler. These assumptions are not proved in the development. The formal theorem does not cover the expected polynomial running time, the ideal-algorithm tightness theorem, or the optimization characterizations proved here. The formal statements, assumption registry, and verification instructions are included with the Lean sources in the artifact repository (Appendix § 12 ).
AI Use Statement. This work resulted from extensive interaction between the authors and OpenAI Astra. The authors provided suggestions, critically checked the responses, and directed the writing and revision process, evaluating the proposed ideas and arguments.
Negative Association of the Geometric-Age Process
We give an independent proof of the seed property used in § 3 . It uses Reimer’s inequality [Rei00]: for arbitrary events E , F E,F E , F in a finite Bernoulli product space, with arbitrary coordinate biases,
Pr ( E □ F ) ≤ Pr ( E ) Pr ( F ) . \Pr(E \mathbin{\Box} F) \le\Pr(E)\Pr(F). Pr ( E □ F ) ≤ Pr ( E ) Pr ( F ) .
Here E □ F E \mathbin{\Box} F E □ F means that disjoint sets of product coordinates certify the two events. No monotonicity in the product coordinates is required.
Lemma 14. The outputs of the stationary geometric-age process are negatively associated. The same holds after any finite age cap.
Proof. Realize the seed using iid Bernoulli reset bits ( B t ) t ∈ Z (B_t)_{t\in\mathbb{Z}} ( B t ) t ∈ Z . Fix a cap L L L . If B t = 0 B_t=0 B t = 0 , let Y t [ L ] = − 1 Y_t^{[L]}=-1 Y t [ L ] = − 1 ; otherwise let Y t [ L ] Y_t^{[L]} Y t [ L ] be the smaller of L L L and the number of consecutive zeros immediately preceding t t t . Any finite set of capped outputs depends on finitely many bits.
At a realized nonnegative output Y t [ L ] = z Y_t^{[L]}=z Y t [ L ] = z , the bits in K t = [ t − z , t ] ∩ Z K_t=[t-z,t]\cap\mathbb{Z} K t = [ t − z , t ] ∩ Z consist of z z z zeros followed by one. Fixing them certifies Y t [ L ] ≥ z Y_t^{[L]}\ge z Y t [ L ] ≥ z under every completion. An output equal to − 1 -1 − 1 needs no certificate. All the sets K t K_t K t of nonnegative outputs in a realized sample are disjoint: if s < t s<t s < t and their intervals intersected, the terminal one at s s s would lie among the zeros required by the later interval.
Let E , F E,F E , F be increasing events in disjoint sets of output coordinates. At any sample in E ∩ F E\cap F E ∩ F , the certificates of its nonnegative outputs in the first set jointly certify E E E , since every completion preserves or increases those outputs. The analogous certificates certify F F F , and the two collections are disjoint. Thus E ∩ F = E □ F E\cap F=E\mathbin{\Box}F E ∩ F = E □ F in the Bernoulli product space. Reimer’s inequality proves negative correlation of these events. Integrating upper-level events proves the covariance inequality for bounded increasing functions, which is negative association.
For any finite set of times, capped outputs eventually equal the uncapped outputs almost surely as L → ∞ L\to\infty L → ∞ . Bounded convergence passes negative association to the uncapped sequence; truncation extends it to the usual integrable functions.
A Finite Certificate for the Tournament Inequalities
We prove the reduction used in Lemma 11. Fix the integer-pooled map (20) , and write D ( z ) = 1 − W ( z ) D(z)=1-W(z) D ( z ) = 1 − W ( z ) and B = 1 − b B=1-b B = 1 − b . For each 2 ≤ r < m 2\le r<m 2 ≤ r < m , we prove
E [ ( s − V r ) + ] ≤ H r ( s ) , V r = ∏ j = 1 r ( 1 − X j ) , 0 ≤ s ≤ 1. (24) \mathbb{E}[(s-V_r)_+] \le H_r(s),\qquad V_r=\prod_{j=1}^{r}(1-X_j),\qquad0\le s\le1. \tag*{(24)} E [( s − V r ) + ] ≤ H r ( s ) , V r = j = 1 ∏ r ( 1 − X j ) , 0 ≤ s ≤ 1. (24)
The proof conditions on the first reset. Its bounded remainder is replaced by a two-point distribution with the same mean; the unbounded initial age is integrated out. The resulting convex envelope has at most 2 r 2r 2 r terms for the initial age and a no-reset atom.
The support and mean of a fresh block
Let V n 0 V_n^0 V n 0 be the failure product in n n n exposures started at age zero, and put d n = min V n 0 d_n=\min V_n^0 d n = min V n 0 and f n = E [ V n 0 ] f_n=\mathbb{E}[V_n^0] f n = E [ V n 0 ] . Then d 0 = f 0 = 1 d_0=f_0=1 d 0 = f 0 = 1 , and conditioning on the first reset gives
d n = min { B n , min 0 ≤ k < n B k D ( k ) d n − k − 1 } , f n = ( q B ) n + p ∑ k = 0 n − 1 ( q B ) k D ( k ) f n − k − 1 . (25) \begin{aligned}
d_n&=\min\left\{B^n,\min_{0\le k<n}B^kD(k)d_{n-k-1}\right\},\\
f_n&=(qB)^n+p\sum_{k=0}^{n-1}(qB)^kD(k)f_{n-k-1}. \tag*{(25)}
\end{aligned} d n f n = min { B n , 0 ≤ k < n min B k D ( k ) d n − k − 1 } , = ( q B ) n + p k = 0 ∑ n − 1 ( q B ) k D ( k ) f n − k − 1 . (25)
Indeed, the no-reset event has probability q n q^n q n and product B n B^n B n . A first reset after k k k nonresets has probability p q k pq^k p q k and leaves an independent fresh block of length n − k − 1 n-k-1 n − k − 1 . Every failure factor is at most B B B , so the maximum product is B n B^n B n . In particular d n ≤ V n 0 ≤ B n d_n\le V_n^0\le B^n d n ≤ V n 0 ≤ B n . For n ≤ A n\le A n ≤ A , every score is the baseline and d n = f n = B n d_n=f_n=B^n d n = f n = B n .
For d n < B n d_n<B^n d n < B n , set θ n = ( B n − f n ) / ( B n − d n ) \theta_n=(B^n-f_n)/(B^n-d_n) θ n = ( B n − f n ) / ( B n − d n ) ; otherwise set θ n = 0 \theta_n=0 θ n = 0 . The endpoint chord of a convex function gives
E [ ( s − V n 0 ) + ] ≤ ( 1 − θ n ) ( s − B n ) + + θ n ( s − d n ) + . (26) \mathbb{E}[(s-V_n^0)_+]\le(1-\theta_n)(s-B^n)_++\theta_n(s-d_n)_+. \tag*{(26)} E [( s − V n 0 ) + ] ≤ ( 1 − θ n ) ( s − B n ) + + θ n ( s − d n ) + . (26)
The two-point distribution has the same mean as V n 0 V_n^0 V n 0 . These recurrences and this comparison account for every reset pattern.
Integrating out the initial age
Put u k = 1 − p q k u_k=1-pq^k u k = 1 − p q k . For C > 0 C>0 C > 0 and 0 ≤ u < 1 0\le u<1 0 ≤ u < 1 , define I ( s , C , u ) = ∫ u 1 ( s − C ( 1 − v m − 1 ) + ) d v I(s,C,u)=\int_u^1(s-C(1-v^{m-1})_+)\,dv I ( s , C , u ) = ∫ u 1 ( s − C ( 1 − v m − 1 ) + ) d v . Direct integration gives
I ( s , C , u ) = { C H 1 ( s / C ) , 0 ≤ s ≤ C ( 1 − u m − 1 ) , ( 1 − u ) ( s − C ) + C ( 1 − u m ) / m , s ≥ C ( 1 − u m − 1 ) . (27) I(s,C,u)=
\begin{cases}
CH_1(s/C), & 0\le s\le C(1-u^{m-1}),\\
(1-u)(s-C)+C(1-u^m)/m, & s\ge C(1-u^{m-1}).
\end{cases} \tag*{(27)} I ( s , C , u ) = { C H 1 ( s / C ) , ( 1 − u ) ( s − C ) + C ( 1 − u m ) / m , 0 ≤ s ≤ C ( 1 − u m − 1 ) , s ≥ C ( 1 − u m − 1 ) . (27)
The branches agree in value and derivative. For the stationary age Z Z Z , conditional Jensen gives
E Z [ ( s − C D ( Z + k ) ) + ] ≤ ψ k ( s , C ) : = { ( 1 − q A − k ) ( s − C B ) + + I ( s , C , u A ) p q k , k < A , I ( s , C , u k ) p q k , k ≥ A . (28) \mathbb{E}_Z[(s-CD(Z+k))_+]\le\psi_k(s,C):=
\begin{cases}
(1-q^{A-k})(s-CB)_++\dfrac{I(s,C,u_A)}{pq^k}, & k<A,\\
\dfrac{I(s,C,u_k)}{pq^k}, & k\ge A.
\end{cases} \tag*{(28)} E Z [( s − C D ( Z + k ) ) + ] ≤ ψ k ( s , C ) := ⎩ ⎨ ⎧ ( 1 − q A − k ) ( s − C B ) + + p q k I ( s , C , u A ) , p q k I ( s , C , u k ) , k < A , k ≥ A . (28)
For each pre-reset age z ≥ max { A , k } z\ge\max\{A,k\} z ≥ max { A , k } , W ( z ) W(z) W ( z ) is the mean of v m − 1 v^{m-1} v m − 1 on [ u z , u z + 1 ] [u_z,u_{z+1}] [ u z , u z + 1 ] . Its probability p q z − k pq^{z-k} p q z − k , divided by the bin width p 2 q z p^2q^z p 2 q z , is 1 / ( p q k ) 1/(pq^k) 1/ ( p q k ) . Jensen therefore integrates the entire old-age tail. The younger ages, when present, retain their common failure B B B . No initial-age cutoff is needed.
Conditional on the first reset position k k k , the block failure is B k D ( Z + k ) V r − k − 1 0 B^{k}D(Z+k)V^{0}_{r-k-1} B k D ( Z + k ) V r − k − 1 0 , with independent initial age and fresh remainder. Applying (26) and then (28) gives the following bound, where n = r − k − 1 n=r-k-1 n = r − k − 1 in the sum:
E [ ( s − V r ) + ] ≤ Φ r ( s ) : = q r ( s − B r ) + + ∑ k = 0 r − 1 p q k [ ( 1 − θ n ) ψ k ( s , B r − 1 ) + θ n ψ k ( s , B k d n ) ] . (29) \mathbb{E}[(s-V_r)_+] \le\Phi_r(s) := q^r(s-B^r)_+ + \sum_{k=0}^{r-1}pq^k\left[(1-\theta_n)\psi_k(s,B^{r-1})+\theta_n\psi_k(s,B^kd_n)\right]. \tag*{(29)} E [( s − V r ) + ] ≤ Φ r ( s ) := q r ( s − B r ) + + k = 0 ∑ r − 1 p q k [ ( 1 − θ n ) ψ k ( s , B r − 1 ) + θ n ψ k ( s , B k d n ) ] . (29)
Both comparisons preserve means, so Φ r ( 1 ) = E [ 1 − V r ] ≤ r / m \Phi_r(1)=\mathbb{E}[1-V_r]\le r/m Φ r ( 1 ) = E [ 1 − V r ] ≤ r / m . The positive-part representation makes Φ r \Phi_r Φ r convex.
Directed bounds on the fresh comparison
The verifier uses fixed rational bounds 0 < a n ≤ d n 0<a_n\le d_n 0 < a n ≤ d n , f n ≤ f n f_n\le f_n f n ≤ f n , and B n ≤ e n ≤ 1 B^n\le e_n\le1 B n ≤ e n ≤ 1 . For a n < e n a_n<e_n a n < e n , put
θ ^ n = min { 1 , max { 0 , e n − f n e n − a n } } . \widehat{\theta}_n=\min\left\{1,\max\left\{0,\frac{e_n-f_n}{e_n-a_n}\right\}\right\}. θ n = min { 1 , max { 0 , e n − a n e n − f n } } .
The chord on [ a n , e n ] [a_n,e_n] [ a n , e n ] using the true mean has lower-endpoint weight ( e n − f n ) / ( e n − a n ) (e_n-f_n)/(e_n-a_n) ( e n − f n ) / ( e n − a n ) . The displayed weight is at least this large. Therefore (26) remains an upper bound after replacing its endpoints and weight by a n , e n , θ ^ n a_n,e_n,\widehat{\theta}_n a n , e n , θ n . A deterministic interval is handled as one atom; for n ≤ A n\le A n ≤ A the verifier retains the deterministic product B n B^n B n before the final scale rounding.
The recurrence for d n d_n d n uses lower bounds and downward products. The positive recurrence for f n f_n f n is evaluated with outward interval arithmetic and a lower endpoint is taken. The mixture weight is rounded upward, with its other weight defined as exactly the complement. Finally the two scales B k a n , B k e n B^ka_n,B^ke_n B k a n , B k e n are rounded downward, preserving their order, and their weights are rounded upward. Each change is safe because ψ k ( s , C ) \psi_k(s,C) ψ k ( s , C ) is nonincreasing in C C C . The baseline in young atoms and the no-reset failure may also be rounded downward; the no-reset probability is rounded upward. Thus the fixed envelope being checked has the form
Φ ^ r ( s ) = ρ 0 ( s − c 0 ) + + ∑ ( k , C , w ) ∈ T r w ψ ^ k ( s , C ) . \widehat{\Phi}_r(s)=\rho_0(s-c_0)_+ + \sum_{(k,C,w)\in\mathcal{T}_r}w\widehat{\psi}_k(s,C). Φ r ( s ) = ρ 0 ( s − c 0 ) + + ( k , C , w ) ∈ T r ∑ w ψ k ( s , C ) .
with nonnegative rational weights, at most 2 r 2r 2 r triples, and a baseline B ≤ B B\le B B ≤ B in the young atoms. Here ψ ^ k \widehat{\psi}_k ψ k is (28) with B B B replaced by B B B , while ρ 0 ≥ q r \rho_0\ge q^r ρ 0 ≥ q r and 0 < c 0 ≤ B r 0<c_0\le B^r 0 < c 0 ≤ B r . It is convex and dominates (29) . Outward rounding need not preserve the endpoint mean identity.
Covering all real thresholds
Choose s 0 > 0 s_0>0 s 0 > 0 such that, for every triple ( k , C , w ) (k,C,w) ( k , C , w ) ,
s 0 < c 0 , s 0 < C B , s 0 < C ( 1 − u max { A , k } m − 1 ) , (30) s_0<c_0,\qquad s_0<CB,\qquad s_0<C(1-u_{\max\{A,k\}}^{m-1}), \tag*{(30)} s 0 < c 0 , s 0 < C B , s 0 < C ( 1 − u m a x { A , k } m − 1 ) , (30)
where B ≤ B B\le B B ≤ B is the baseline failure used in young atoms. The atoms vanish on [ 0 , s 0 ] [0,s_0] [ 0 , s 0 ] , and each integral uses the first branch of (27) . Writing C min = min T r C C_{\min}=\min_{\mathcal{T}_r}C C m i n = min T r C and using H ′ ′ ( t ) = ( m − 1 ) − 1 ( 1 − t ) − ( m − 2 ) / ( m − 1 ) H''(t)=(m-1)^{-1}(1-t)^{-(m-2)/(m-1)} H ′′ ( t ) = ( m − 1 ) − 1 ( 1 − t ) − ( m − 2 ) / ( m − 1 ) gives
Φ ^ r ( s ) ≤ 1 2 p ( m − 1 ) ( ∑ ( k , C , w ) ∈ T r w q − k C ) ( 1 − s 0 / C min ) − ( m − 2 ) / ( m − 1 ) s 2 . (31) \widehat{\Phi}_r(s)\le\frac{1}{2p(m-1)}
\left(\sum_{(k,C,w)\in\mathcal{T}_r}\frac{wq^{-k}}{C}\right)
(1-s_0/C_{\min})^{-(m-2)/(m-1)}s^2. \tag*{(31)} Φ r ( s ) ≤ 2 p ( m − 1 ) 1 ( k , C , w ) ∈ T r ∑ C w q − k ( 1 − s 0 / C m i n ) − ( m − 2 ) / ( m − 1 ) s 2 . (31)
Since H r ′ ′ ( s ) = r ( m − r ) − 1 ( 1 − s ) ( 2 r − m ) / ( m − r ) H_r''(s)=r(m-r)^{-1}(1-s)^{(2r-m)/(m-r)} H r ′′ ( s ) = r ( m − r ) − 1 ( 1 − s ) ( 2 r − m ) / ( m − r ) and its exponent is at most m − 2 m-2 m − 2 ,
H r ( s ) ≥ r 2 ( m − r ) ( 1 − s 0 ) m − 2 s 2 ( 0 ≤ s ≤ s 0 ) . H_r(s) \ge\frac{r}{2(m-r)}(1-s_0)^{m-2}s^2 \qquad(0 \le s \le s_0). H r ( s ) ≥ 2 ( m − r ) r ( 1 − s 0 ) m − 2 s 2 ( 0 ≤ s ≤ s 0 ) .
Comparing coefficients proves the whole initial interval.
On [ s 0 , 1 ] [s_0,1] [ s 0 , 1 ] , take a rational partition and rational upper bounds on Φ ^ r \widehat{\Phi}_r Φ r at its endpoints. Convexity bounds the function by each joining chord, written S s − M Ss-M S s − M . We check that this line lies below H r H_r H r on the entire unit interval. If S ≤ 0 S \le0 S ≤ 0 , it suffices that M ≥ 0 M \ge0 M ≥ 0 ; if S ≥ 1 S \ge1 S ≥ 1 , the condition is M − S + r / m ≥ 0 M-S+r/m \ge0 M − S + r / m ≥ 0 . For 0 < S < 1 0<S<1 0 < S < 1 , define u = 1 − S u=1-S u = 1 − S and a ∗ = ( m / r ) ( M − S + r / m ) a_*=(m/r)(M-S+r/m) a ∗ = ( m / r ) ( M − S + r / m ) . Minimizing H r ( s ) − S s + M H_r(s)-Ss+M H r ( s ) − S s + M at s = 1 − u ( m − r ) / r s=1-u^{(m-r)/r} s = 1 − u ( m − r ) / r gives the exact test
a ∗ ≥ 0 , a ∗ r ≥ u m . (32) a_* \ge0,\qquad a_*^r \ge u^m. \tag*{(32)} a ∗ ≥ 0 , a ∗ r ≥ u m . (32)
These are rational inequalities. Every accepted chord certifies its full interval, and explicit coverage of the partition completes the proof of (24) .
The implementation uses 128-bit dyadic bounds for the fresh recurrences, mixture weights, and outer probabilities; 64-bit downward scales; and 96-bit endpoint upper bounds. Arb enclosures [10 ] use 256 bits. The cutoff bounds in (30) are rounded downward. For endpoint evaluation, an affine integral branch is used only when its validity is certified. Otherwise, when s < C s<C s < C , the full integral C H 1 ( s / C ) CH_1(s/C) C H 1 ( s / C ) is a safe upper bound. If s ≥ C s\ge C s ≥ C , the affine branch applies. Inconclusive chord signs are resolved by exact rational powers in (32) . Endpoint computations need not define a convex function: the chord argument uses their certified upper bounds on the fixed convex envelope.
A Finite Rational Implementation
We give a finite rational implementation of Theorem 1 with the error allowances in § 7 . We cap and scale the seed, replace the continuous coupling by a finite tournament, and discretize water filling.
Capping and scaling the seed
Cap the age at an integer L ≥ A L\ge A L ≥ A , replacing W ( z ) W(z) W ( z ) by W ( min { z , L } ) W(\min\{z,L\}) W ( min { z , L }) . The capped stationary probabilities are p q z pq^z p q z for z < L z<L z < L and q L q^L q L at the final state. The ordinary transition sends the final state to itself on a nonreset and to zero on a reset. The invariant used in Theorem 4 remains valid: δ 0 P n \delta_0P^n δ 0 P n now has the distribution of min ( G , n , L ) \min(G,n,L) min ( G , n , L ) . All desired win probabilities decrease pointwise, so tournament feasibility persists.
The first Bonferroni bound in the reset-failure integral gives
D ( z ) ≤ c 1 q z ( z ≥ A ) , c 1 = ( m − 1 ) p ( 1 + q ) 2 . D(z) \le c_1q^z \quad(z\ge A),\qquad c_1=\frac{(m-1)p(1+q)}{2}. D ( z ) ≤ c 1 q z ( z ≥ A ) , c 1 = 2 ( m − 1 ) p ( 1 + q ) .
To bound the change in γ \gamma γ , couple the uncapped stationary age Z Z Z and the capped age min { Z , L } \min\{Z,L\} min { Z , L } using the same reset bits. This coupling is preserved by every transition and has the correct stationary marginals. For any coupled stationary score processes X k ≥ X k ′ X_k\ge X'_k X k ≥ X k ′ in [ 0 , 1 ] [0,1] [ 0 , 1 ] , product telescoping gives
0 ≤ E [ ∏ k = 1 n ( 1 − X k ′ ) ] − E [ ∏ k = 1 n ( 1 − X k ) ] ≤ n E [ X 1 − X 1 ′ ] . 0 \le\mathbb{E}\left[\prod_{k=1}^{n}(1-X'_k)\right]-\mathbb{E}\left[\prod_{k=1}^{n}(1-X_k)\right]\le n\mathbb{E}[X_1-X'_1]. 0 ≤ E [ k = 1 ∏ n ( 1 − X k ′ ) ] − E [ k = 1 ∏ n ( 1 − X k ) ] ≤ n E [ X 1 − X 1 ′ ] .
The discounted number of exposures in (1) has mean m m m . Hence the difference between their values of γ \gamma γ is at most m E [ X 1 − X 1 ′ ] m\mathbb{E}[X_1-X'_1] m E [ X 1 − X 1 ′ ] . This uses the stationary, unconditional score distribution; it does not condition that distribution on previous failures.
Capping changes a score only at a reset from an age z > L z > L z > L , and the change is at most D ( L ) D(L) D ( L ) . The stationary probability of such a reset is p q L + 1 p q^{L+1} p q L + 1 . The cap loss is therefore at most
m p q L + 1 D ( L ) ≤ m p c 1 q 2 L + 1 . m p q^{L+1} D(L) \le m p c_1 q^{2L+1}. m p q L + 1 D ( L ) ≤ m p c 1 q 2 L + 1 .
Scaling the capped scores by η \eta η loses at most m ( 1 − η ) E [ X 1 ( L ) ] ≤ 1 − η m(1-\eta)\mathbb{E}[X_1^{(L)}] \le1-\eta m ( 1 − η ) E [ X 1 ( L ) ] ≤ 1 − η , since capping decreases the stationary mean from 1 / m 1/m 1/ m .
For both parameter choices in (19) , take L = 5 m / 2 L=5m/2 L = 5 m /2 . The rational checks in Appendix § 12 give
m p c 1 q 5 m + 1 < 10 − 8 . (33) m p c_1 q^{5m+1} < 10^{-8}. \tag*{(33)} m p c 1 q 5 m + 1 < 1 0 − 8 . (33)
The bounds are less than 3.047 ⋅ 10 − 9 3.047 \cdot10^{-9} 3.047 ⋅ 1 0 − 9 for m = 500 m=500 m = 500 and 3.232 ⋅ 10 − 9 3.232 \cdot10^{-9} 3.232 ⋅ 1 0 − 9 for m = 1000 m=1000 m = 1000 . Thus the implemented seed uses 1251 or 2501 age states, respectively. For η = 1 − 1 / ( m ⋅ 10 6 ) \eta=1-1/(m\cdot10^6) η = 1 − 1/ ( m ⋅ 1 0 6 ) , the scaling loss is at most 1 / ( m ⋅ 10 6 ) 1/(m\cdot10^6) 1/ ( m ⋅ 1 0 6 ) . The finite matrices are rational, so their resolvent and the resulting value of Γ \Gamma Γ are rational as well.
Computing the finite potential
The inverse in (4) can be computed by a short backward recurrence. Use the cap C C C and scaled scores of § 4.1 , and put
a = m m + 1 , ρ = a q ( 1 − b f ) , R = 1 − a 1 − ρ . a=\frac{m}{m+1},\qquad\rho=aq(1-b_f),\qquad R=\frac{1-a}{1-\rho}. a = m + 1 m , ρ = a q ( 1 − b f ) , R = 1 − ρ 1 − a .
Starting at the capped state, compute
σ C = a p ( 1 − W f ( C ) ) 1 − ρ , σ z = a p ( 1 − W f ( z ) ) + ρ σ z + 1 ( z = C − 1 , … , 0 ) . \sigma_C=\frac{ap(1-W_f(C))}{1-\rho},\qquad\sigma_z=ap(1-W_f(z))+\rho\sigma_{z+1}\quad(z=C-1,\ldots,0). σ C = 1 − ρ a p ( 1 − W f ( C )) , σ z = a p ( 1 − W f ( z )) + ρ σ z + 1 ( z = C − 1 , … , 0 ) .
Then
ℓ 0 = R 1 − σ 0 , ℓ z = R + σ z ℓ 0 , h f ( z ) = 1 − ℓ z , Γ = ∑ z = 0 C π f ( z ) h f ( z ) . \ell_0=\frac{R}{1-\sigma_0},\qquad\ell_z=R+\sigma_z\ell_0,\qquad h_f(z)=1-\ell_z,\qquad\Gamma=\sum_{z=0}^{C}\pi_f(z)h_f(z). ℓ 0 = 1 − σ 0 R , ℓ z = R + σ z ℓ 0 , h f ( z ) = 1 − ℓ z , Γ = z = 0 ∑ C π f ( z ) h f ( z ) .
Indeed, the defining equation for the miss probability is ℓ z = 1 − a + ρ ℓ min { z + 1 , C } + a p ( 1 − W f ( z ) ) ℓ 0 \ell_z=1-a+\rho\ell_{\min\{z+1,C\}}+ap(1-W_f(z))\ell_0 ℓ z = 1 − a + ρ ℓ m i n { z + 1 , C } + a p ( 1 − W f ( z )) ℓ 0 . Solving its cap self-loop and substituting backwards gives the displayed recurrence. Its denominators are positive: ρ < 1 \rho<1 ρ < 1 and σ 0 ≤ a p ( 1 − b f ) / ( 1 − ρ ) < 1 \sigma_0\le ap(1-b_f)/(1-\rho)<1 σ 0 ≤ a p ( 1 − b f ) / ( 1 − ρ ) < 1 . Thus preprocessing uses O ( C ) O(C) O ( C ) exact rational arithmetic operations for this step.
Constructing the finite tournament tables
We give the full preprocessing used by Tournament. The input consists of m , p , C m,p,C m , p , C , the unscaled capped scores W ( z ) W(z) W ( z ) , their baseline b b b , and 0 < η < 1 0<\eta<1 0 < η < 1 . All quantities below are rational. For our parameter choices, b > 0 b>0 b > 0 and D ( C ) = 1 − W ( C ) > 0 D(C)=1-W(C)>0 D ( C ) = 1 − W ( C ) > 0 .
Stationary block distributions. For each 1 ≤ r < m 1\le r<m 1 ≤ r < m , enumerate the distribution of the scaled combined desired win probability Q r ′ = 1 − ∏ k = 1 r ( 1 − X k f ) Q'_r=1-\prod_{k=1}^{r}(1-X_k^f) Q r ′ = 1 − ∏ k = 1 r ( 1 − X k f ) . Here X k f X_k^f X k f is a single-exposure score from W f W_f W f , starting in the stationary distribution π f \pi_f π f . An exact dynamic program uses a dictionary A t ( z , f ) A_t(z,f) A t ( z , f ) for the probability of age z z z and accumulated failure product f f f after t t t exposures. Initialize A 0 ( z , 1 ) = π f ( z ) A_0(z,1)=\pi_f(z) A 0 ( z , 1 ) = π f ( z ) . An entry of mass a a a at ( z , f ) (z,f) ( z , f ) sends
q a to ( min { z + 1 , C } , f ( 1 − b f ) ) , p a to ( 0 , f ( 1 − W f ( z ) ) ) . \begin{aligned}
qa &\text{ to }(\min\{z+1,C\},f(1-b_f)),\\
pa &\text{ to }(0,f(1-W_f(z))).
\end{aligned} q a p a to ( min { z + 1 , C } , f ( 1 − b f )) , to ( 0 , f ( 1 − W f ( z ))) .
Merge equal rational keys. The failure product is a recorded value; it does not further multiply the transition mass. After step r r r , sum over ages with the same value 1 − f 1-f 1 − f , obtaining distinct sorted scores ξ r , 1 < ⋯ < ξ r , n r \xi_{r,1}<\cdots<\xi_{r,n_r} ξ r , 1 < ⋯ < ξ r , n r and positive probabilities ρ r , j \rho_{r,j} ρ r , j . One run to length m − 1 m-1 m − 1 gives all these distributions.
Strength bins and their means. Set
δ = ( 1 − η ) b D ( C ) m − 2 , H = ⌈ m − 1 δ ⌉ , t ℓ = ℓ H ( 0 ≤ ℓ ≤ H ) . \delta=(1-\eta)bD(C)^{m-2},\qquad H=\left\lceil\frac{m-1}{\delta}\right\rceil,\qquad t_\ell=\frac{\ell}{H}\quad(0\le\ell\le H). δ = ( 1 − η ) b D ( C ) m − 2 , H = ⌈ δ m − 1 ⌉ , t ℓ = H ℓ ( 0 ≤ ℓ ≤ H ) .
For the reference strength S r S_r S r with cumulative distribution s r s^r s r , bin ℓ \ell ℓ has probability and conditional mean
ω r , ℓ = t ℓ r − t ℓ − 1 r , μ r , ℓ = E [ S r m − r ∣ S r in bin ℓ ] = r ( t ℓ m − t ℓ − 1 m ) m ω r , ℓ . (34) \omega_{r,\ell}=t_\ell^r-t_{\ell-1}^r,\qquad\mu_{r,\ell}=\mathbb{E}[S_r^{m-r}\mid S_r\text{ in bin }\ell]=\frac{r(t_\ell^m-t_{\ell-1}^m)}{m\omega_{r,\ell}}. \tag*{(34)} ω r , ℓ = t ℓ r − t ℓ − 1 r , μ r , ℓ = E [ S r m − r ∣ S r in bin ℓ ] = m ω r , ℓ r ( t ℓ m − t ℓ − 1 m ) . (34)
All probabilities are positive and the means increase strictly with ℓ \ell ℓ . Write M r M_r M r for the random bin mean and Z r = S r m − r Z_r=S_r^{m-r} Z r = S r m − r . Every power s m − r s^{m-r} s m − r varies by at most δ \delta δ on one bin, so ( Z r − δ ) + ≤ M r (Z_r-\delta)_+\le M_r ( Z r − δ ) + ≤ M r in this coupling.
Let Q r Q_r Q r be the same capped block win before scaling. Product telescoping gives Q r − Q r ′ ≥ ( 1 − η ) b D ( C ) r − 1 ≥ δ Q_r-Q'_r\ge(1-\eta)bD(C)^{r-1}\ge\delta Q r − Q r ′ ≥ ( 1 − η ) b D ( C ) r − 1 ≥ δ . Capping preserves the tournament inequalities, so Q r ⪯ i c x Z r Q_r\preceq_{\mathrm{icx}}Z_r Q r ⪯ icx Z r . Since x ↦ ( x − δ ) + x\mapsto(x-\delta)_+ x ↦ ( x − δ ) + is increasing and convex,
Q r ′ ⪯ i c x ( Q r − δ ) + ⪯ i c x ( Z r − δ ) + ⪯ i c x M r . Q'_r\preceq_{\mathrm{icx}}(Q_r-\delta)_+\preceq_{\mathrm{icx}}(Z_r-\delta)_+\preceq_{\mathrm{icx}}M_r. Q r ′ ⪯ icx ( Q r − δ ) + ⪯ icx ( Z r − δ ) + ⪯ icx M r .
This supplies the finite convex-order comparison needed below.
The coupling linear program. For each r r r , the variable K j ℓ ( r ) K^{(r)}_{j\ell} K j ℓ ( r ) is the probability of choosing bin ℓ \ell ℓ when the desired win probability is ξ r , j \xi_{r,j} ξ r , j . Solve
K j ℓ ( r ) ≥ 0 , ∑ ℓ = 1 H K j ℓ ( r ) = 1 , ∑ j = 1 n r ρ r , j K j ℓ ( r ) = ω r , ℓ , ∑ ℓ = 1 H μ r , ℓ K j ℓ ( r ) ≥ ξ r , j , ∑ ℓ = h H K j ℓ ( r ) ≤ ∑ ℓ = h H K j + 1 , ℓ ( r ) ( j < n r , 2 ≤ h ≤ H ) . (35) \begin{aligned}
K^{(r)}_{j\ell}&\ge0,\qquad&&\sum_{\ell=1}^{H}K^{(r)}_{j\ell}=1,\\
\sum_{j=1}^{n_r}\rho_{r,j}K^{(r)}_{j\ell}&=\omega_{r,\ell},\qquad&&\sum_{\ell=1}^{H}\mu_{r,\ell}K^{(r)}_{j\ell}\ge\xi_{r,j},\\
\sum_{\ell=h}^{H}K^{(r)}_{j\ell}&\le\sum_{\ell=h}^{H}K^{(r)}_{j+1,\ell}&& (j<n_r,\ 2\le h\le H). \tag*{(35)}
\end{aligned} K j ℓ ( r ) j = 1 ∑ n r ρ r , j K j ℓ ( r ) ℓ = h ∑ H K j ℓ ( r ) ≥ 0 , = ω r , ℓ , ≤ ℓ = h ∑ H K j + 1 , ℓ ( r ) ℓ = 1 ∑ H K j ℓ ( r ) = 1 , ℓ = 1 ∑ H μ r , ℓ K j ℓ ( r ) ≥ ξ r , j , ( j < n r , 2 ≤ h ≤ H ) . (35)
The first two lines of (35) impose nonnegativity, the two marginals, and the conditional-mean requirement. The last line orders the conditional bin distributions stochastically as the desired win probability increases. The coupling theorem in Lemma 3 guarantees feasibility. This bounded rational polytope has a rational feasible point, which an exact LP algorithm can find. Store its rows as K r ( ξ r , j , ⋅ ) K_r(\xi_{r,j},\cdot) K r ( ξ r , j , ⋅ ) and check the constraints exactly. Any coarser common rational partition with feasible versions of these LPs also suffices; the displayed choice of H H H guarantees feasibility.
The within-bin winner table. Conceptually, after sampling its bin, each candidate independently draws a reference strength conditioned on that bin, and the largest strength wins. We integrate out this continuous draw. Let J J J be the candidates in the highest sampled bin [ a , b ] [a,b] [ a , b ] . No other candidate can win. For i ∈ J i\in J i ∈ J , its conditional winning probability is
c i ( r J , [ a , b ] ) = r i ∏ k ∈ J ( b r k − a r k ) ∫ a b s r i − 1 ∏ k ∈ J ∖ { i } ( s r k − a r k ) d s . (36) c_i(r_J,[a,b])=\frac{r_i}{\prod_{k\in J}(b^{r_k}-a^{r_k})}\int_a^b s^{r_i-1}\prod_{k\in J\setminus\{i\}}(s^{r_k}-a^{r_k})\,ds. \tag*{(36)} c i ( r J , [ a , b ]) = ∏ k ∈ J ( b r k − a r k ) r i ∫ a b s r i − 1 k ∈ J ∖ { i } ∏ ( s r k − a r k ) d s . (36)
Algorithm 3. The finite calibrated tournament
Input: distinct candidates ( i , r i , Q i ) (i,r_i,Q_i) ( i , r i , Q i ) after all seed exposures.
if there is one distinct candidate then return it.
for each candidate i i i do
Independently draw ℓ i \ell_i ℓ i from the table row K r i ( Q i , ⋅ ) K_{r_i}(Q_i,\cdot) K r i ( Q i , ⋅ ) .
end for
Set ℓ ∗ ← max i ℓ i \ell_* \leftarrow\max_i \ell_i ℓ ∗ ← max i ℓ i and J ← { i : ℓ i = ℓ ∗ } J \leftarrow\{i:\ell_i=\ell_*\} J ← { i : ℓ i = ℓ ∗ } .
List J J J in the fixed vertex order and read c ( r J , [ t ℓ ∗ − 1 , t ℓ ∗ ] ) c(r_J,[t_{\ell_*-1},t_{\ell_*}]) c ( r J , [ t ℓ ∗ − 1 , t ℓ ∗ ]) .
Draw and return a member of J J J with these probabilities.
This is the integral of i i i ’s conditional density against its opponents’ conditional cumulative distributions. The integrand is a polynomial of degree at most m − 1 m-1 m − 1 . Multiply the polynomials and integrate each monomial exactly over the rational endpoints. The resulting rational probabilities are nonnegative and sum to one. Precompute them for each bin and each ordered positive multiplicity list whose sum is at most m m m . Candidates are represented by their positions in this list, so the tables are independent of graph labels. List the candidates in the fixed vertex order, and map the returned probability vector back to their labels in that same order.
Algorithm 3 now specifies the tournament entirely with rational distributions. In particular, it does not break equal-bin events uniformly: the multiplicities determine the appropriate probabilities in (36) .
Calibration and monotonicity. For a stationary input block, the column constraints in (35) give the reference bin probabilities. Lifting the bin to its original conditional strength distribution therefore recovers the marginal Pr ( S r ≤ s ) = s r \Pr(S_r \le s)=s^r Pr ( S r ≤ s ) = s r . Opponent blocks and fresh bin draws are independent across vertices. A candidate of strength s s s and multiplicity r r r consequently wins with probability s m − r s^{m-r} s m − r . Conditional only on its own desired win probability ξ r , j \xi_{r,j} ξ r , j , its winning probability is at least that desired win probability by the conditional-mean constraint. The tail constraints make its strength stochastically increase with its desired win probability, giving the required monotonicity in its own and its opponents’ scores. The rational table integrates out only fresh randomness, so it reproduces this kernel exactly.
The dummy uses the same seed and tables as a real vertex. A sole candidate of multiplicity m m m wins deterministically after consuming all its exposures. No coupling LP is needed for that multiplicity. The preprocessing introduces no loss beyond the single-exposure scaling already accounted for. Its dictionary, grid, and LPs can be very large: their sizes are not asserted to be polynomial in m m m or C C C , which are fixed constants in the theorem.
Rational water filling without a known horizon
At arrival j j j , let W j W_j W j be the largest weight revealed so far and fix an accuracy ϵ > 0 \epsilon>0 ϵ > 0 . Every terminal deficit d i ( x ) d_i(x) d i ( x ) is nonincreasing and m W j mW_j m W j -Lipschitz. To see the latter, condition on the number of exposures: each threshold credit is a Bernstein polynomial with nondecreasing coefficients in [ 0 , 1 ] [0,1] [ 0 , 1 ] . Its derivative is at most m Γ m\Gamma m Γ , and the interval of relevant thresholds has length at most W j W_j W j .
Set N j = ⌈ m ( j + 1 ) / ϵ ⌉ N_j=\lceil m(j+1)/\epsilon\rceil N j = ⌈ m ( j + 1 ) / ϵ ⌉ . Starting from the zero vector, repeatedly increase by 1 / N j 1/N_j 1/ N j a coordinate of largest current deficit, including the dummy, until the total probability is one. Let β j \beta_j β j be the final maximum deficit. At the last increment of any used coordinate, its deficit is at least the then maximum and hence at least β j \beta_j β j ; the increment lowers it by at most m W j / N j mW_j/N_j m W j / N j . It follows that
∑ i v i d i ( v i ) ≥ β j − ϵ W j j ( j + 1 ) . \sum_i v_i d_i(v_i) \ge\beta_j-\frac{\epsilon W_j}{j(j+1)}. i ∑ v i d i ( v i ) ≥ β j − j ( j + 1 ) ϵ W j .
Dual feasibility still holds with β j \beta_j β j , and the primal–dual budget loses only this error. Since W j ≤ O P T W_j \le\mathrm{OPT} W j ≤ OPT and ∑ j ≥ 1 1 / [ j ( j + 1 ) ] = 1 \sum_{j\ge1} 1/[j(j+1)] = 1 ∑ j ≥ 1 1/ [ j ( j + 1 )] = 1 , the total competitive loss is at most ϵ \epsilon ϵ . We take ϵ = 10 − 6 \epsilon= 10^{-6} ϵ = 1 0 − 6 .
After j j j arrivals, each vertex has at most j j j threshold breakpoints. All capped states, matrices, credits, and grid probabilities are rational. With fixed preprocessing, the arithmetic operation count and bit lengths are polynomial in the input size and 1 / ϵ 1/\epsilon 1/ ϵ .
For the bit-length claim, let D 0 D_0 D 0 be a common denominator of π f \pi_f π f and D 1 D_1 D 1 a common denominator of P f , T f P_f,T_f P f , T f . Every accounting entry after j j j arrivals has a denominator dividing
D 0 D 1 m j ∏ s = 1 j N s m . D_0D_1^{mj}\prod_{s=1}^{j}N_s^m. D 0 D 1 mj s = 1 ∏ j N s m .
Splitting an interval copies its vector, and each committed mixture update introduces at most a factor D 1 m N j m D_1^mN_j^m D 1 m N j m . The entries lie in [ 0 , 1 ] [0,1] [ 0 , 1 ] , so their bit lengths are polynomial. Credit computations add the rational input weights and fixed potential; their bit lengths remain polynomial in the total input length.
To sample a rational probability vector, put its entries over a common denominator D D D , draw a uniform integer in { 0 , … , D − 1 } \{0,\ldots,D-1\} { 0 , … , D − 1 } , and use the cumulative integer masses. Draw ⌈ log 2 D ⌉ \lceil\log_2 D\rceil ⌈ log 2 D ⌉ unbiased bits and reject values at least D D D ; the expected number of trials is less than two. The case D = 1 D=1 D = 1 is deterministic. This implements the categorical draws, reset coins, bin draws, and winner draws using only finite bit strings.
Tightness of the Main Analysis
This appendix concerns the ideal full-mean algorithm underlying the competitive guarantee. Its conclusion does not assert optimality among all online algorithms or tightness of the finite scaled implementation.
Theorem 15 (Tightness of the ideal matching reduction). Fix m ≥ 2 m \ge2 m ≥ 2 , p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) , and an admissible nondecreasing geometric-age map W W W with baseline b = W ( − 1 ) > 0 b = W(-1) > 0 b = W ( − 1 ) > 0 and stationary mean E [ X 1 ] = 1 / m \mathbb{E}[X_1] = 1/m E [ X 1 ] = 1/ m . Use exact water filling and the tournament of Section 3, with a kernel depending only on the current multiset and score tuple and independent fresh randomization on each round. Put
A k = E [ ∏ ℓ = 1 k ( 1 − X ℓ ) ] , A 0 = 1 , γ = 1 − ∑ k ≥ 0 m k ( m + 1 ) k + 1 A k . A_k=\mathbb{E}\left[\prod_{\ell=1}^{k}(1-X_\ell)\right],\qquad A_0=1,\qquad\gamma=1-\sum_{k\ge0}\frac{m^k}{(m+1)^{k+1}}A_k. A k = E [ ℓ = 1 ∏ k ( 1 − X ℓ ) ] , A 0 = 1 , γ = 1 − k ≥ 0 ∑ ( m + 1 ) k + 1 m k A k . For each n n n , let G n G_n G n have offline vertices 1 , … , n 1,\ldots,n 1 , … , n and online arrivals 1 , … , n 1,\ldots,n 1 , … , n , where arrival j j j has unit-weight edges precisely to vertices j , j + 1 , … , n j,j+1,\ldots,n j , j + 1 , … , n . Then
OPT ( G n ) = n , lim n → ∞ E [ ALG ( G n ) ] n = γ . \operatorname{OPT}(G_n)=n,\qquad\lim_{n\to\infty}\frac{\mathbb{E}[\operatorname{ALG}(G_n)]}{n}=\gamma. OPT ( G n ) = n , n → ∞ lim n E [ ALG ( G n )] = γ . Consequently the worst-case competitive ratio of this ideal algorithm is exactly γ \gamma γ .
Proof. The diagonal edges form a perfect matching, so OPT ( G n ) = n \operatorname{OPT}(G_n)=n OPT ( G n ) = n . We first show that at arrival j j j the candidate vector is uniform on its k j = n − j + 1 k_j=n-j+1 k j = n − j + 1 neighbors. All active vertices have identical accounting histories and, inductively, a common row ν \nu ν satisfying the invariant. Their only relevant weight interval is ( 0 , 1 ] (0,1] ( 0 , 1 ] , so their deficit after hypothetical probability x x x is
d ( x ) = ν ( I + x ( T − I ) ) m h . d(x)=\nu(I+x(T-I))^m h. d ( x ) = ν ( I + x ( T − I ) ) m h .
This is positive: every desired win probability is at least b b b , so the geometric stopping-time interpretation gives h ≥ m b / ( 1 + m b ) > 0 h\ge mb/(1+mb)>0 h ≥ mb / ( 1 + mb ) > 0 , while a run of nonreset misses has positive probability because q ( 1 − b ) > 0 q(1-b)>0 q ( 1 − b ) > 0 . For every row μ \mu μ satisfying the invariant,
μ T h ≤ ( 1 − b ) μ P h ≤ ( 1 − b ) μ h . \mu T h\le(1-b)\mu P h\le(1-b)\mu h. μ T h ≤ ( 1 − b ) μ P h ≤ ( 1 − b ) μ h .
Thus d ′ ( x ) = m μ ( T − I ) h ≤ − m b μ h < 0 d'(x)=m\mu(T-I)h\le-mb\mu h<0 d ′ ( x ) = m μ ( T − I ) h ≤ − mb μ h < 0 , with μ = ν ( I + x ( T − I ) ) m − 1 \mu=\nu(I+x(T-I))^{m-1} μ = ν ( I + x ( T − I ) ) m − 1 . Inactive vertices have nonpositive deficits, as does the dummy. The unique maximizer of the strictly concave active water-filling objective therefore assigns probability 1 / k j 1/k_j 1/ k j to each active vertex and zero elsewhere. This also proves the induction hypothesis for the next active set.
Next, singleton calibration is exact. Fix any multiset consisting of m m m distinct vertices, and let g i ( x ) g_i(x) g i ( x ) be vertex i i i ’s winning probability given its singleton score x x x , averaging over independent stationary opponent scores and fresh tournament randomness. Calibration gives g i ( X i ) ≥ X i g_i(X_i)\ge X_i g i ( X i ) ≥ X i almost surely. Since exactly one vertex wins and every stationary singleton score has mean 1 / m 1/m 1/ m ,
∑ i = 1 m E [ g i ( X i ) − X i ] = 1 − m / m = 0. \sum_{i=1}^{m}\mathbb{E}[g_i(X_i)-X_i]=1-m/m=0. i = 1 ∑ m E [ g i ( X i ) − X i ] = 1 − m / m = 0.
Every summand is nonnegative, so g i ( X i ) = X i g_i(X_i)=X_i g i ( X i ) = X i almost surely for each vertex. This conclusion holds for every fixed distinct-vertex multiset; symmetry of the tournament is not required.
Fix δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) and consider a vertex i ≤ ( 1 − δ ) n i\le(1-\delta)n i ≤ ( 1 − δ ) n . Its total number of sampled exposures is
K i , n = ∑ j = 1 i Bin ( m , 1 / k j ) , λ i , n = E [ K i , n ] = m ∑ k = n − i + 1 n 1 k , K_{i,n}=\sum_{j=1}^{i}\operatorname{Bin}(m,1/k_j),\qquad
\lambda_{i,n}=\mathbb{E}[K_{i,n}]=m\sum_{k=n-i+1}^{n}\frac{1}{k}, K i , n = j = 1 ∑ i Bin ( m , 1/ k j ) , λ i , n = E [ K i , n ] = m k = n − i + 1 ∑ n k 1 ,
where the binomials are independent. Uniformly over these vertices, λ i , n \lambda_{i,n} λ i , n is bounded by a constant depending only on m , δ m,\delta m , δ , and E [ K i , n 2 ] ≤ λ i , n + λ i , n 2 \mathbb{E}[K_{i,n}^{2}]\le\lambda_{i,n}+\lambda_{i,n}^{2} E [ K i , n 2 ] ≤ λ i , n + λ i , n 2 .
Call the candidate tape bad for vertex i i i if it occurs more than once on any round, or if some opponent vertex occurs more than once among all the rounds containing i i i . The first event has probability at most
( m 2 ) ∑ j = 1 i k j − 2 . \binom{m}{2}\sum_{j=1}^{i}k_j^{-2}. ( 2 m ) j = 1 ∑ i k j − 2 .
For the second, condition on all indicators specifying which draws equal i i i , and exclude the first event. There are L = ( m − 1 ) K i , n L=(m-1)K_{i,n} L = ( m − 1 ) K i , n opponent draws. Each is independent and uniform on its round’s active set with i i i removed, of size at least δ n − 1 \delta n-1 δ n − 1 . Any pair coincides with probability at most 1 / ( δ n − 1 ) 1/(\delta n-1) 1/ ( δ n − 1 ) . Hence, for δ n > 1 \delta n>1 δ n > 1 ,
Pr ( bad for i ) ≤ ( m 2 ) ∑ j = 1 i k j − 2 + ( m − 1 ) 2 E [ K i , n 2 ] 2 ( δ n − 1 ) = O m , δ ( n − 1 ) . \Pr(\text{bad for }i)\le\binom{m}{2}\sum_{j=1}^{i}k_j^{-2}+\frac{(m-1)^2\mathbb{E}[K_{i,n}^{2}]}{2(\delta n-1)}
=O_{m,\delta}(n^{-1}). Pr ( bad for i ) ≤ ( 2 m ) j = 1 ∑ i k j − 2 + 2 ( δ n − 1 ) ( m − 1 ) 2 E [ K i , n 2 ] = O m , δ ( n − 1 ) .
Condition on a candidate tape that is not bad for i i i . Its exposures are singletons on distinct rounds, and all opponents on those rounds are distinct vertices. The tape fixes every seed exposure index. Each opponent contributes one stationary singleton score, and those scores are independent because their vertex seeds are independent. Intervening rounds do not change this statement: seed evolution depends on sampled exposures, not on tournament winners. These scores are also independent of the entire seed sequence of i i i . Consequently, conditional on that sequence, exact singleton calibration and fresh independent tournament randomness give loss probability
∏ ℓ = 1 K i , n ( 1 − X ℓ ) . \prod_{\ell=1}^{K_{i,n}}(1-X_\ell). ℓ = 1 ∏ K i , n ( 1 − X ℓ ) .
Averaging over the target seed and then the candidate tape yields
∣ Pr ( i is never chosen ) − E [ A K i , n ] ∣ ≤ O m , δ ( n − 1 ) . \left|\Pr(i\text{ is never chosen})-\mathbb{E}[A_{K_{i,n}}]\right|\le O_{m,\delta}(n^{-1}). Pr ( i is never chosen ) − E [ A K i , n ] ≤ O m , δ ( n − 1 ) .
The independent Bernoulli sum K i , n K_{i,n} K i , n is within total variation m ∑ j ≤ i k j − 2 = O m , δ ( n − 1 ) m\sum_{j\le i}k_j^{-2}=O_{m,\delta}(n^{-1}) m ∑ j ≤ i k j − 2 = O m , δ ( n − 1 ) of a Poisson variable of mean λ i , n \lambda_{i,n} λ i , n . One elementary coupling proves this bound by coupling each Bernoulli( u ) (u) ( u ) to Poisson( u ) (u) ( u ) with error at most u 2 u^2 u 2 , then adding independent pairs. Uniformly for i / n ≤ 1 − δ i/n\le1-\delta i / n ≤ 1 − δ ,
λ i , n = − m log ( 1 − i / n ) + O m , δ ( n − 1 ) . \lambda_{i,n}=-m\log(1-i/n)+O_{m,\delta}(n^{-1}). λ i , n = − m log ( 1 − i / n ) + O m , δ ( n − 1 ) .
Since 0 ≤ A k ≤ 1 0\le A_k\le1 0 ≤ A k ≤ 1 , bounded Poisson expectations are continuous in their means. Riemann summation therefore gives the limiting contribution of these vertices as
∫ 0 1 − δ [ 1 − E [ A Pois ( − m log ( 1 − t ) ) ] ] d t . \int_0^{1-\delta}\left[1-\mathbb{E}\left[A_{\operatorname{Pois}(-m\log(1-t))}\right]\right]\,dt. ∫ 0 1 − δ [ 1 − E [ A Pois ( − m l o g ( 1 − t )) ] ] d t .
The remaining vertices contribute between zero and δ n + 1 \delta n+1 δ n + 1 , and the omitted integral is between zero and δ \delta δ . Letting δ ↓ 0 \delta\downarrow0 δ ↓ 0 identifies the full limit. Finally, putting x = − log ( 1 − t ) x=-\log(1-t) x = − log ( 1 − t ) and interchanging nonnegative terms gives
∫ 0 1 E [ A Pois ( − m log ( 1 − t ) ) ] d t = ∑ k ≥ 0 A k ∫ 0 ∞ e − ( m + 1 ) x ( m x ) k k ! d x = ∑ k ≥ 0 m k ( m + 1 ) k + 1 A k . \int_0^1\mathbb{E}\left[A_{\operatorname{Pois}(-m\log(1-t))}\right]\,dt
=\sum_{k\ge0}A_k\int_0^\infty e^{-(m+1)x}\frac{(mx)^k}{k!}\,dx
=\sum_{k\ge0}\frac{m^k}{(m+1)^{k+1}}A_k. ∫ 0 1 E [ A Pois ( − m l o g ( 1 − t )) ] d t = k ≥ 0 ∑ A k ∫ 0 ∞ e − ( m + 1 ) x k ! ( m x ) k d x = k ≥ 0 ∑ ( m + 1 ) k + 1 m k A k .
This proves the limit. The matching reduction supplies the reverse worst-case guarantee, so the ratio is exactly γ \gamma γ .
Reproducibility and Verification Artifacts
The repository linked in § 1 contains the numerical verifiers, generated certificates, and Lean sources. Build instructions are in README.md; source hashes are in paper/verifiers/manifest.json. Appendix § 9 proves the reductions used by the tournament verifier.
The directory paper/verifiers/ contains verify_score_two.py and verify_tournament_two.py. Run make score for the exact score and implementation margins, and make tournament for the all-multiplicity certificate. The latter requires Python 3.12 and the pinned dependency in requirements.txt. Both tournament runs must report PASS for every 2 ≤ r < m 2\le r<m 2 ≤ r < m , with 12,915 chords for m = 500 m=500 m = 500 and 30,105 for m = 1000 m=1000 m = 1000 . Run the programs with Python assertions enabled.
The formal main theorem is in research/lean/tournament1000/Main1000.lean. With Lean 4.19.0 and the pinned dependencies installed, run make lean-main to compile its dependency closure and audit its assumptions. The formalization has the scope and two literature assumptions stated in § 7 ; research/lean/README.md documents the build and its checks.