Introduction
Optimal stopping theory has long informed the design of online auctions. Hajiaghayi, Kleinberg, and Parkes [21 ] initiated the connection between secretary problems and online auction design, and Hajiaghayi, Kleinberg, and Sandholm [22 ] introduced prophet inequalities as a tool for designing and analyzing online auction mechanisms.1 These connections led to a broad study of how distributional information and random arrival can improve online allocation. In a prophet inequality problem, the values are drawn independently from known distributions, and an online algorithm makes irrevocable decisions as they are revealed. Its performance is compared with a prophet who sees all realizations before choosing an optimal feasible solution. The arrival order may be adversarial. In a secretary problem, the values are fixed and unknown, but the arrival order is uniformly random. The prophet-secretary model [16 ] combines the distributional information of prophet inequalities with the random arrival order of secretary problems. The distributions are known in advance, and the arrival order is uniform and independent of the realized values.
The central difficulty is to use this information while preserving feasibility for future arrivals. Accepting a valuable element may prevent the selection of later elements, and allocating an item to one buyer makes it unavailable to every later buyer. Distributional information allows an algorithm to estimate these opportunity costs; random arrival also limits how often an early decision can block a more valuable later one. We study how the interaction between these two sources of information depends on the feasibility structure. Our two settings are matroid selection and combinatorial auctions with XOS valuations, defined next.
Models and results
Matroid selection. The algorithm knows a matroid M = ( E , I ) M=(E,\mathcal{I}) M = ( E , I ) on N N N labeled elements and the distributions of their independent nonnegative weights X e X_e X e . On seeing a label and its weight, it irrevocably accepts or rejects the element. The accepted set must remain independent. In prophet secretary the arrival order is a uniform permutation independent of the weights. We will also consider an arbitrary order fixed independently of the weights and of the algorithm’s random bits. The benchmark in both models is
F 0 = E OPT ( M , X ) , OPT ( M , x ) = max I ∈ I ∑ e ∈ I x e . F_0=\mathbb{E}\operatorname{OPT}(M,X),\qquad\operatorname{OPT}(M,x)=\max_{I\in\mathcal{I}}\sum_{e\in I}x_e. F 0 = E OPT ( M , X ) , OPT ( M , x ) = I ∈ I max e ∈ I ∑ x e .
Write ALG for the realized online reward. A ratio c c c means E [ A L G ] ≥ c F 0 \mathbb{E}[\mathrm{ALG}]\ge cF_0 E [ ALG ] ≥ c F 0 . For our computational bounds the algorithm may query an independence oracle on any subset of the known ground set.
Theorem 1 (Independent weights in random order). For every finite matroid and independent nonnegative weights with F 0 < ∞ F_0<\infty F 0 < ∞ , there is a randomized prophet-secretary algorithm with
E [ A L G ] ≥ ( 1 − 1 / e + ε 0 ) F 0 , ε 0 = 1.14 ⋅ 10 − 6 . \mathbb{E}[\mathrm{ALG}]\ge(1-1/e+\varepsilon_0)F_0,\qquad\varepsilon_0=1.14\cdot10^{-6}. E [ ALG ] ≥ ( 1 − 1/ e + ε 0 ) F 0 , ε 0 = 1.14 ⋅ 1 0 − 6 . For explicitly given finite rational distributions, it uses O ( N 4 ) O(N^4) O ( N 4 ) independence queries in expectation and O ( N 4 log ( N + 2 ) ) O(N^4\log(N+2)) O ( N 4 log ( N + 2 )) in the worst case. Its arithmetic work and number of random bits are polynomial in the input length on every execution.
When the weights share a law, the next theorem gives a larger guarantee under a weaker assumption on the order.
Theorem 2 (I.i.d. weights in a fixed order). Let the weights of a known finite matroid be independent draws from a common known nonnegative distribution of finite mean. There is a randomized online algorithm that, in every fixed arrival order, obtains
E [ A L G ] ≥ c 0 F 0 , c 0 = 1 1 + η 0 = 0.6767410571 … , η 0 2 = e − 1 − η 0 , η 0 > 0. \mathbb{E}[\mathrm{ALG}]\ge c_0F_0,\qquad c_0=\frac{1}{1+\eta_0}=0.6767410571\ldots,\qquad\eta_0^2=e^{-1-\eta_0},\quad\eta_0>0. E [ ALG ] ≥ c 0 F 0 , c 0 = 1 + η 0 1 = 0.6767410571 … , η 0 2 = e − 1 − η 0 , η 0 > 0. The algorithm need not know the order in advance.
Averaging over a uniform permutation gives the same ratio for prophet secretary. The theorem also covers a matroid in which some labels have many substitutes and others have none. Its proof uses symmetry of the weights alone. The algorithm can be implemented by sampling and making O ( N 4 log ( 2 N ) ) O(N^4\log(2N)) O ( N 4 log ( 2 N )) independence queries. In a real-arithmetic model it only needs evaluations of the common distribution function and its left limits at the observed weights. For a finite rational law the same ratio holds with a worst-case polynomial bound on bit complexity (Appendix § 12 ).
Welfare with XOS buyers. There is a fixed set U U U of items. Each buyer i i i has a valuation drawn independently from a known distribution. When buyer i i i arrives, the algorithm observes her valuation v i v_i v i and assigns her a bundle S i S_i S i of unallocated items. Her valuation is XOS if it is the maximum of nonnegative additive clauses, that is, v i ( S ) = max ℓ ∑ j ∈ S w i ℓ j v_i(S) = \max_\ell\sum_{j\in S} w_{i\ell j} v i ( S ) = max ℓ ∑ j ∈ S w i ℓ j for w i ℓ j ≥ 0 w_{i\ell j} \ge0 w i ℓ j ≥ 0 . The benchmark OPT is the maximum welfare ∑ i v i ( S i ) \sum_i v_i(S_i) ∑ i v i ( S i ) over pairwise disjoint bundles for the realized valuations.
Theorem 3 (Sharpness for XOS welfare). For every ξ > 0 \xi> 0 ξ > 0 there is a finite instance with i.i.d. buyers for which every randomized online algorithm satisfies
E [ A L G ] < ( 1 − 1 / e + ξ ) E [ O P T ] . \mathbb{E}[\mathrm{ALG}] < (1 - 1/e + \xi)\mathbb{E}[\mathrm{OPT}]. E [ ALG ] < ( 1 − 1/ e + ξ ) E [ OPT ] .
All additive clauses have coefficients in { 0 , 1 } \{0,1\} { 0 , 1 } . The bound holds with public menus of clauses and unlimited computation, even if the order of buyer identities is announced in advance.
Together with the algorithm of Ehsani et al. [15 ] , this identifies the optimal guarantee for XOS welfare. The upper bound also follows from the i.i.d. coverage-welfare construction of Udwani and Wajc [33 ] by interchanging the roles of items and buyers. § 10 gives the reduction and a direct proof.
Relation to the earlier version. Theorem 1 of the first arXiv version provides a similar competitive ratio with ε 0 = 1.01 ⋅ 10 − 6 \varepsilon_0 = 1.01\cdot10^{-6} ε 0 = 1.01 ⋅ 1 0 − 6 for matroid prophet secretary with the same oracle complexity. The main addition here is Theorem 2 for i.i.d. distributions, with an improved competitive ratio. The previous version also established the XOS upper bound. In addition to that, here, we show that the XOS upper bound with additive tolerance ξ \xi ξ can be witnessed on O ( ξ − 4 log ( 1 / ξ ) ) O(\xi^{-4}\log(1/\xi)) O ( ξ − 4 log ( 1/ ξ )) items (Corollary 26).
Approach and techniques
The common accounting identity. For a nonnegative weight vector x x x , put S t = { e : x e > t } S_t = \{e : x_e > t\} S t = { e : x e > t } and let r ( S ) r(S) r ( S ) denote the rank of S S S . A maximum-weight basis found by greedy contains exactly r ( S t ) r(S_t) r ( S t ) elements of S t S_t S t at every height t t t . Consequently,
OPT ( M , x ) = ∫ 0 ∞ r ( S t ) d t . (1) \operatorname{OPT}(M,x) = \int_0^\infty r(S_t)\,\mathrm{d}t. \tag*{(1)} OPT ( M , x ) = ∫ 0 ∞ r ( S t ) d t . (1)
To see what one online decision costs at a given height, fix the arriving nonloop e e e , and let A A A consist of the unseen elements above that height. If A A A spans e e e , taking e e e consumes one unit of the rank available to A A A . If A A A does not span e e e , taking e e e costs A A A nothing, but passing over e e e can lose a unit of rank when its own weight exceeds t t t . Both matroid algorithms price these two possibilities. The common-law assumption changes what can be learned from a single sampling experiment.
One quantile cutoff for every height. Suppose the common upper-tail probability at height t t t is v v v . In the residual matroid, the unseen elements above t t t form a set obtained by retaining each unseen element independently with probability v v v . Write S e ( v ) S_e(v) S e ( v ) for the probability that this set fails to span e e e . An upper quantile q q q specifies a threshold. The rule takes e e e on the best q q q fraction of its draws, breaking ties at atoms by an independent random choice. At any height with tail probability v v v this rule earns min { q , v } \min\{q,v\} min { q , v } in expected count. Its expected cost to the remaining rank is
v S e ( v ) + q ( 1 − S e ( v ) ) . vS_e(v) + q(1-S_e(v)). v S e ( v ) + q ( 1 − S e ( v )) .
The first term is the expected cost of deletion. The second is the extra cost of contracting e e e when the rule accepts. In particular, the decision pays for itself exactly at v = q v=q v = q .
The same cutoff must also pay for the narrow bands v < q v<q v < q and the wide bands v > q v>q v > q . For v < q v<q v < q there is a loss only when the unseen sample spans e e e . For v > q v>q v > q there is a loss only when it fails to do so. This is where the shape of S e S_e S e matters. Calibrate q q q by S e ( q ) = e − a S_e(q)=e^{-a} S e ( q ) = e − a . A product-measure inequality bounds S e ( v ) S_e(v) S e ( v ) from below by e − a v / q e^{-av/q} e − a v / q for v < q v<q v < q and from above by the same curve for v > q v>q v > q . Thus the excess cost per unit of reward is at most a a a on narrow bands and at most max x ≥ 1 ( x − 1 ) e − a x = e − 1 − a / a \max_{x\ge1}(x-1)e^{-ax}=e^{-1-a}/a max x ≥ 1 ( x − 1 ) e − a x = e − 1 − a / a on wide bands. Equating the two gives exactly a = η 0 a=\eta_0 a = η 0 in Theorem 2 . The bound holds after fixing both the history and the next label, which explains why this proof needs no randomness in the arrival order. A sequence of parallel elements makes the one-step comparison sharp. The optimal rank-one policy can do better by compensating for a loss at one step with a gain at another.
Beyond the one-step comparison. For i.i.d. weights in random order, the distinction between a local guarantee and the optimal ratio can be made precise. Follow an arbitrary policy through its sequence of residual matroids. If it accepts a label with conditional probability q q q in a given minor, replacing that decision by a top-q q q cutoff sends the same probability mass to each child and earns at least as much in every upper band. Thus a policy can be described by a flow on labeled minors. In fact a single flow attains the worst-law ratio of the matroid simultaneously for all common laws. If some finite set of band targets were incompatible, a separating hyperplane would supply nonnegative weights for the bands. Those weights are the increments of a finite-support common law on which every policy misses its target. Appendix § 13 proves this characterization and a companion identity that compares the optimal online price with the prophet’s realized replacement cost on the same random restriction.
Pricing a decision when the laws differ. With arbitrary marginals, the unseen set at height t t t samples different labels at different rates. There is no common quantile at which to apply the preceding comparison. We work directly with the weighted optimum and use the randomness of the next label. For a nonloop e e e , fix the other weights and let τ e \tau_e τ e be the difference between their optima after deleting and contracting e e e . Deleting e e e from the original instance loses ( X e − τ e ) + (X_e-\tau_e)^+ ( X e − τ e ) + , where u + = max { u , 0 } u^+=\max\{u,0\} u + = max { u , 0 } . The sum of these losses in expectation, divided by the number of remaining labels, is the cost of rejecting the next arrival.
A large expected deletion loss can arise in two ways. An element might rarely draw a very large weight, or it might regularly beat its replacement by a substantial margin. To distinguish them, draw its weight a second time, keeping the other weights fixed. The quantity ( min { X e , X e ′ } − τ e ) + (\min\{X_e,X'_e\}-\tau_e)^+ ( min { X e , X e ′ } − τ e ) + counts the part of the surplus that survives the second draw. Summing its expectation over labels gives the stable surplus . Roughly speaking, rare high offers favor a posted price, whereas persistent membership in an optimum favors a basis-exchange rule. To make this distinction quantitative, we first choose the distribution against which to measure the two surpluses.
Starting from the actual upper tails, multiply every tail probability by a common scale factor q q q near one, capping the result at one. Let F q F_q F q be the expected optimum of this reference instance. The potential is ( 1 − θ q ) F q (1-\theta q)F_q ( 1 − θ q ) F q , with θ \theta θ slightly below 1 / e 1/e 1/ e . Increasing q q q makes the reference optimum larger and its coefficient smaller. The rate at which F q F_q F q grows is closely related to deletion surplus. At a given height, increasing one label’s probability changes expected rank precisely when the other active labels fail to span it. Integrating over heights relates the derivative of F q F_q F q to the sum of the deletion losses. The stable surplus bounds the contribution of tails that reach the cap. Concavity then allows the algorithm to choose q q q without sacrificing the potential inherited from earlier decisions.
Small stable surplus. The algorithm posts a price proportional to the expected difference between deleting and contracting the next label. Charging the price only to elements of the optimal basis loses too much. An element outside that basis can still clear its price, and a rule processing one arrival can collect its surplus. To quantify this contribution we cap the reference weights at scaled contraction prices and apply a tangent inequality for the expected rank under Poisson rounding [14 ] . After integrating over heights, the extra surplus covers the expected deletion loss. The rule processes one arrival and repeats in the resulting minor.
Large stable surplus. Two independent reference optima then have substantial overlap. To measure the relevant overlap, count a shared element at height t t t only when it belongs to both optima and both its weights exceed t t t . Integrating this expected count gives a weighted overlap Q Q Q . § 4.2 lower-bounds Q Q Q by comparing greedy and reverse-greedy bases of each level set. The algorithm can spend this overlap in the last part of the arrival sequence. It maintains virtual bases containing all previously accepted labels, updating each basis by an injective exchange whenever a new label is accepted. Early on it randomly thins acceptances to control the rate at which an exchange can displace any particular element. In a short final interval it removes this thinning. The corresponding loss in the baseline guarantee is quadratic in the length of that interval, whereas the gain from overlap is linear. Near the endpoints of the reference search, the baseline continuation has enough slack to pay for the final interval even at zero overlap. These comparisons cover all branches of the algorithm.
Why the XOS upper bound survives identical distributions. The auction construction has a public collection of partitions of the items, with one partition for every possible set of distinct buyer types. If the n n n realized types are distinct, the prophet can choose their common partition and give each buyer a different part, attaining full welfare. An online allocation fixes a supporting clause for each bundle as soon as it is assigned. Each such clause points to a partition indexed by just n n n types, so with a sufficiently large type space a later buyer is unlikely to be able to use the same partition. The construction makes one part from each of n n n distinct partitions cover exactly a 1 − ( 1 − 1 / n ) n 1-(1-1/n)^n 1 − ( 1 − 1/ n ) n fraction of the items. This counting identity limits the total welfare even when all valuation types and their probabilities are public.
Related work
Independent distributions and random arrival. The classical prophet inequality compares an online stopping rule with the expected maximum of independent nonnegative random variables [KS77]. Its connections to online auctions and pricing were developed in [21 , 22 ] .2 Esfandiari et al. [16 ] introduced the prophet-secretary model. In an arbitrary fixed order, the matroid inequality of Kleinberg and Weinberg [29 ] and the posted-price mechanism of Feldman, Gravin, and Lucier [18 ] give a factor of 1 / 2 1/2 1/2 for matroid selection and XOS welfare, respectively. Ehsani et al. [15 ] showed that random arrival raises both guarantees to 1 − 1 / e 1 - 1/e 1 − 1/ e . For a single choice, Azar, Chiplunkar, and Kaplan [3 ] broke this barrier, followed by Correa, Saona, and Ziliotto [13 ] . Chen et al. [12 ] obtained 0.688 for a single choice and 0.641 for prophet-secretary matching.
Identical distributions. In rank one the sharp constant over all horizons is 0.745440 . . .. Hill and Kertz [20 ] obtained the sharp finite-horizon constants, and Kertz [25 ] determined their limit. Abolhassani et al. [4 ] gave a threshold rule attaining 0.738 asymptotically. Correa et al. [CFH+21] matched the limiting upper bound with a guarantee for every horizon. For k k k choices, Brustle, Perez-Salazar, and Verdugo [8 ] characterized the finite-horizon i.i.d. ratio by a linear program. A cardinality constraint is invariant under relabeling. On a general matroid, exchanging two labels can change feasibility even when their weights have the same law. In the related random-assignment secretary problem [32 ] , an unknown list of weights is assigned uniformly to the labels. Conditioning i.i.d. weights on their unordered multiset gives this assignment. Our algorithm also uses the common law to compute weight quantiles.
Contention resolution and basis exchange. An online contention-resolution scheme selects a feasible subset from a random set of active elements [19 ] . Lee and Singla [30 ] obtained the tight factor 1 − 1 / e 1 - 1/e 1 − 1/ e for matroids under random arrival against the ex-ante relaxation. The distinction between benchmarks already matters in rank one. If each of n n n elements independently has value one with probability 1 / n 1/n 1/ n and zero otherwise, the ex-ante value is one, whereas the expected optimum is 1 − ( 1 − 1 / n ) n 1 - (1 - 1/n)^n 1 − ( 1 − 1/ n ) n . Our matroid guarantees use the latter benchmark. Adamczyk and Włodarczyk [6 ] used basis-exchange maps of the kind proved by Brualdi [9 ] to maintain feasible sets under random arrivals. Our heterogeneous algorithm applies exchanges to bases drawn from a reference distribution and uses the overlap of two such optima to bound the gain over 1 − 1 / e 1 - 1/e 1 − 1/ e . The rank inequality in its analysis uses the concavity of Poisson-rounded matroid rank [14 ] .
Information about weights. In the matroid secretary problem [7 ] , the weights are fixed and unknown. Recent algorithms give a constant guarantee in this model [31 , 24 ABH+26] . The single-sample prophet model gives one independent sample from each law. Azar, Kleinberg, and Weinberg studied its connection to secretary algorithms [5 ] . For a fixed arrival order independent of samples, realizations, and private randomness, Abdi et al. [2 ABH+26] obtained the sharp factor 1 / 2 1/2 1/2 on every matroid. Our algorithms use known distributions.
Online welfare. In the item-arrival model with coverage valuations, Kapralov, Post, and Vondrák [27 ] proved that greedy achieves 1 − 1 / e 1 - 1/e 1 − 1/ e on i.i.d. arrivals and that a polynomial-time algorithm improving this factor would imply NP = RP. Udwani and Wajc [33 ] proved the same upper bound for unrestricted computation even when the common distribution is known. Chawla and Dang [10 Appendix D] used a coverage-to-XOS transformation in the free-disposal model. § 10.3 explains how it carries the information-theoretic bound over to irrevocable buyer-arrival allocation.
Organization. After the common matroid preliminaries, § 3 gives the i.i.d. algorithm and proves the sharp bound on its one-step analysis. For general marginals, § 4 and § 6 prove the threshold and exchange bounds. § 7 –§ 9 use these bounds in the online algorithm. § 10 gives the auction construction. Appendices § 12 and § 13 treat implementation and optimal policies for i.i.d. weights. Appendices § 14 and § 15 give the bit complexity and the numerical certificate for general marginals.
Matroid preliminaries
Matroids and residual instances. We use the matroid and prophet-secretary models of § 1.1 . For M = ( E , I ) M=(E,\mathcal{I}) M = ( E , I ) , the rank of S ⊆ E S\subseteq E S ⊆ E is
r M ( S ) = max { ∣ I ∣ : I ⊆ S , I ∈ I } . r_M(S)=\max\{|I|:I\subseteq S,\ I\in\mathcal{I}\}. r M ( S ) = max { ∣ I ∣ : I ⊆ S , I ∈ I } .
A basis is a maximal independent set. Write B ( M ) \mathcal{B}(M) B ( M ) for the set of bases, all of size r M ( E ) r_M(E) r M ( E ) . The closure of S S S is cl M ( S ) = { e ∈ E : r M ( S ∪ { e } ) = r M ( S ) } \operatorname{cl}_M(S)=\{e\in E:r_M(S\cup\{e\})=r_M(S)\} cl M ( S ) = { e ∈ E : r M ( S ∪ { e }) = r M ( S )} . We say S S S spans e e e if e ∈ cl M ( S ) e\in\operatorname{cl}_M(S) e ∈ cl M ( S ) and spans T T T if T ⊆ cl M ( S ) T\subseteq\operatorname{cl}_M(S) T ⊆ cl M ( S ) . A flat is a set equal to its closure. An element is a loop if its singleton is dependent and a coloop if it belongs to every basis. Two distinct nonloops are parallel if their pair has rank one. Subscripts are omitted when the matroid is clear.
The restriction to R ⊆ E R\subseteq E R ⊆ E is M ∣ R = ( R , { I ∈ I : I ⊆ R } ) M|_R=(R,\{I\in\mathcal{I}:I\subseteq R\}) M ∣ R = ( R , { I ∈ I : I ⊆ R }) , and the deletion of R R R is M \ R = M ∣ E \ R M\backslash R=M|_{E\backslash R} M \ R = M ∣ E \ R . The contraction M / R M/R M / R has ground set E \ R E\backslash R E \ R and rank function
r M / R ( S ) = r M ( S ∪ R ) − r M ( R ) . r_{M/R}(S)=r_M(S\cup R)-r_M(R). r M / R ( S ) = r M ( S ∪ R ) − r M ( R ) .
This definition also applies when R R R is dependent. If R R R is independent, S S S is independent in M / R M/R M / R exactly when S ∪ R S\cup R S ∪ R is independent in M M M . For a single element, write M \ e M\backslash e M \ e and M / e M/e M / e . A matroid obtained by deletions and contractions is a minor . A set J J J disjoint from T T T is independent over T T T if r M ( T ∪ J ) = r M ( T ) + ∣ J ∣ r_M(T\cup J)=r_M(T)+|J| r M ( T ∪ J ) = r M ( T ) + ∣ J ∣ .
A circuit is an inclusionwise minimal dependent set. If B B B is a basis and e ∉ B e\notin B e ∈ / B , the unique circuit in B ∪ { e } B\cup\{e\} B ∪ { e } is the fundamental circuit of e e e with respect to B B B . We use the shorthand B − f + e = ( B \ { f } ) ∪ { e } B-f+e=(B\backslash\{f\})\cup\{e\} B − f + e = ( B \ { f }) ∪ { e } .
At a residual state, the accepted independent set is contracted and rejected elements are deleted. We discard loops. Independence of the weights allows us to use the original distribution on each surviving label. To implement a matroid independence query in the residual minor, adjoin the already contracted independent set and make one query to the original matroid independence oracle.
Weighted bases. We fix a total order of the labels throughout. The greedy algorithm scans elements in decreasing order of weight, using this label order to break ties, and adds an element whenever independence is preserved. It chooses a canonical maximum-weight basis, denoted B ( y ) B(y) B ( y ) . Zero-weight elements are used to complete the basis. A product distribution is a joint distribution with mutually independent coordinates. For a value vector Y Y Y with a product distribution, write F ( M , Y ) = E OPT ( M , Y ) F(M,Y)=\mathbb{E}\operatorname{OPT}(M,Y) F ( M , Y ) = E OPT ( M , Y ) , omitting the matroid and distribution when fixed. The distributions may have atoms, including an atom at zero. We write u + = max { u , 0 } u^+=\max\{u,0\} u + = max { u , 0 } , use 1 { A } \mathbf{1}\{A\} 1 { A } for the indicator of an event A A A , and put [ k ] = { 1 , … , k } [k]=\{1,\ldots,k\} [ k ] = { 1 , … , k } .
Identically distributed weights
Suppose that the weights are independent draws from a common distribution F F F on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) of finite mean. Fix an arrival order independently of the draws and the algorithm’s randomness. We now prove Theorem 2 . At each step N N N denotes the minor on the remaining labels, obtained by contracting accepted elements and deleting rejected elements. We write P N ( F ) P_N(F) P N ( F ) for its expected offline optimum.
Randomly break ties within each atom of F F F . More precisely, when e e e has weight x x x , draw its upper quantile U e U_e U e uniformly from [ 1 − F ( x ) , 1 − F ( x − ) ] [1-F(x),1-F(x-)] [ 1 − F ( x ) , 1 − F ( x − )] . These quantiles are independent and uniform on [ 0 , 1 ] [0,1] [ 0 , 1 ] , with the smallest quantiles corresponding to the largest weights. For 0 ≤ v ≤ 1 0\leq v\leq1 0 ≤ v ≤ 1 , let B v B_v B v be the elements with quantiles at most v v v . Equivalently, sample each label independently with probability v v v . Define
R N ( v ) = E r N ( B v ) , S e N ( v ) = Pr ( e ∉ cl N ( B v ∖ { e } ) ) . R_N(v)=\mathbb{E}r_N(B_v), \qquad S_e^N(v)=\Pr(e\notin\operatorname{cl}_N(B_v\setminus\{e\})). R N ( v ) = E r N ( B v ) , S e N ( v ) = Pr ( e ∈ / cl N ( B v ∖ { e })) .
Here B v B_v B v is sampled on E ( N ) E(N) E ( N ) , and r N r_N r N is the rank function of N N N . The function S e N S_e^N S e N measures how hard it is to replace e e e at a given weight level. In particular, it depends on the unseen labels, but has no dependence on their order.
The rule. Fix a parameter a > 0 a>0 a > 0 . Reject loops and accept coloops. For any other arrival e e e , accept if S e N ( U e ) ≥ e − a S_e^N(U_e)\ge e^{-a} S e N ( U e ) ≥ e − a . Equivalently, accept the best q q q fraction of the draws, where q q q is the solution to S e N ( q ) = e − a S_e^N(q)=e^{-a} S e N ( q ) = e − a . The solution is unique since S e N S_e^N S e N is a nonincreasing polynomial, with S e N ( 0 ) = 1 S_e^N(0)=1 S e N ( 0 ) = 1 and S e N ( 1 ) = 0 S_e^N(1)=0 S e N ( 1 ) = 0 . Its values lie strictly between 0 and 1 in the interior. The sampled implementation in Appendix A needs only independence queries.
Theorem 4 (One cutoff for all weight levels). For every v ∈ [ 0 , 1 ] v\in[0,1] v ∈ [ 0 , 1 ] , the expected number of accepted labels in B v B_v B v is at least c ( a ) R M ( v ) c(a)R_M(v) c ( a ) R M ( v ) , where
c ( a ) = 1 1 + max { a , e − 1 − a / a } . c(a)=\frac{1}{1+\max\{a,e^{-1-a}/a\}}. c ( a ) = 1 + max { a , e − 1 − a / a } 1 . Consequently the rule earns at least c ( a ) P M ( F ) c(a)P_M(F) c ( a ) P M ( F ) in every fixed order. The best choice of a a a is the unique positive solution η 0 \eta_0 η 0 to η 0 2 = e − 1 − η 0 \eta_0^2=e^{-1-\eta_0} η 0 2 = e − 1 − η 0 , giving c 0 = ( 1 + η 0 ) − 1 = 0.6767410571 … c_0=(1+\eta_0)^{-1}=0.6767410571\ldots c 0 = ( 1 + η 0 ) − 1 = 0.6767410571 … .
The proof uses one property of product measures. It controls the probability that e e e increases rank at all sampling rates from its value at the cutoff.
Lemma 5. If e e e is neither a loop nor a coloop, let S ( v ) = S e N ( v ) S(v)=S_e^N(v) S ( v ) = S e N ( v ) and τ ( v ) = − log ( 1 − v ) \tau(v)=-\log(1-v) τ ( v ) = − log ( 1 − v ) . Both − log S ( v ) / τ ( v ) -\log S(v)/\tau(v) − log S ( v ) / τ ( v ) and − log S ( v ) / v -\log S(v)/v − log S ( v ) / v are nondecreasing on ( 0 , 1 ) (0,1) ( 0 , 1 ) .
Proof. Record an absent label by a 1, so the bits have bias s = 1 − v s=1-v s = 1 − v . The event that e e e is unspanned is increasing in these bits and has probability h ( s ) = S ( 1 − s ) h(s)=S(1-s) h ( s ) = S ( 1 − s ) . The biased edge-isoperimetric inequality on the discrete cube [17 ] gives
− h ( s ) log h ( s ) ≤ − s log ( s ) h ′ ( s ) . -h(s)\log h(s)\le-s\log(s)h'(s). − h ( s ) log h ( s ) ≤ − s log ( s ) h ′ ( s ) .
Indeed, the entropy of the event indicator is − h log h -h\log h − h log h . By tensorization it is bounded by the sum of the expected conditional entropies obtained by resampling each bit in turn. The conditional entropy of the indicator in a given coordinate is − s log s -s\log s − s log s when it is pivotal and zero otherwise. Differentiating the product probability shows that the sum of the pivotal probabilities is h ′ ( s ) h'(s) h ′ ( s ) .
The displayed inequality is equivalent to ( log h ( s ) / log s ) ′ ≤ 0 (\log h(s)/\log s)'\le0 ( log h ( s ) / log s ) ′ ≤ 0 . Replacing s s s by 1 − v 1-v 1 − v gives the first claim. The second follows on multiplying by τ ( v ) / v \tau(v)/v τ ( v ) / v , the increasing average of 1 / ( 1 − t ) 1/(1-t) 1/ ( 1 − t ) over 0 ≤ t ≤ v 0\le t\le v 0 ≤ t ≤ v . □ \square □
Proof of Theorem 4. Fix v > 0 v>0 v > 0 . Condition on the history before the next weight is revealed, and let e e e be the next label. At a nonloop, write S = S e N S=S_e^N S = S e N and N − = N ∖ e N^-=N\setminus e N − = N ∖ e , N + = N / e N^+=N/e N + = N / e . The expected rank increases by v S ( v ) vS(v) v S ( v ) on adding e e e to a Bernoulli sample of the other labels. Also, r N / e ( A ) = r N ( A ∪ { e } ) − 1 r_{N/e}(A)=r_N(A\cup\{e\})-1 r N / e ( A ) = r N ( A ∪ { e }) − 1 , so contracting e e e costs the sample one unit of rank precisely when it spans e e e . Thus
R N ( v ) − R N − ( v ) = v S ( v ) , R N − ( v ) − R N + ( v ) = 1 − S ( v ) . R_N(v)-R_{N^-}(v)=vS(v), \qquad R_{N^-}(v)-R_{N^+}(v)=1-S(v). R N ( v ) − R N − ( v ) = v S ( v ) , R N − ( v ) − R N + ( v ) = 1 − S ( v ) .
Figure 1. In a three-element circuit both other labels must be sampled to span the current one, so S ( v ) = 1 − v 2 S(v)=1-v^2 S ( v ) = 1 − v 2 . The exponential through the cutoff bounds the probability from below for v < q v<q v < q and from above for v > q v>q v > q . Lemma 5 gives these same two bounds for every matroid.
With acceptance probability q q q , the expected drop in the potential R N ( v ) R_N(v) R N ( v ) is
D ( v ) = q + ( v − q ) S ( v ) . (2) D(v)=q+(v-q)S(v). \tag*{(2)} D ( v ) = q + ( v − q ) S ( v ) . (2)
An upper-quantile cutoff of size q q q earns min ( v , q ) \min(v,q) min ( v , q ) in the band. Thus the cost of using q q q instead of the best cutoff for this particular band is exactly
D ( v ) − min ( v , q ) = { ( q − v ) ( 1 − S ( v ) ) , v ≤ q , ( v − q ) S ( v ) , v ≥ q . D(v)-\min(v,q)=
\begin{cases}
(q-v)(1-S(v)), & v\le q,\\
(v-q)S(v), & v\ge q.
\end{cases} D ( v ) − min ( v , q ) = { ( q − v ) ( 1 − S ( v )) , ( v − q ) S ( v ) , v ≤ q , v ≥ q .
In the first case we sometimes accept below the band and block a future element in it. In the second we sometimes reject an element in the band that the other band elements cannot replace.
For an element that is neither a loop nor a coloop, set x = v / q x=v/q x = v / q . As illustrated in Figure 1, Lemma 5 and S ( q ) = e − a S(q)=e^{-a} S ( q ) = e − a give S ( v ) ≥ e − a x S(v)\ge e^{-ax} S ( v ) ≥ e − a x for x ≤ 1 x\le1 x ≤ 1 and S ( v ) ≤ e − a x S(v)\le e^{-ax} S ( v ) ≤ e − a x for x ≥ 1 x\ge1 x ≥ 1 , with the endpoint values obtained by continuity. In the first case
D ( v ) v − 1 ≤ ( x − 1 − 1 ) ( 1 − e − a x ) ≤ a . \frac{D(v)}{v}-1\le(x^{-1}-1)(1-e^{-ax})\le a. v D ( v ) − 1 ≤ ( x − 1 − 1 ) ( 1 − e − a x ) ≤ a .
In the second case
D ( v ) q − 1 ≤ ( x − 1 ) e − a x ≤ e − 1 − a / a . \frac{D(v)}{q}-1\le(x-1)e^{-ax}\le e^{-1-a}/a. q D ( v ) − 1 ≤ ( x − 1 ) e − a x ≤ e − 1 − a / a .
The last maximum is attained at x = 1 + 1 / a x=1+1/a x = 1 + 1/ a . In either case the expected reward in the band pays for c ( a ) D ( v ) c(a)D(v) c ( a ) D ( v ) . At a loop both quantities vanish, and at a coloop the reward and the rank drop are both v v v . Summing over arrivals telescopes the rank potential from R M ( v ) R_M(v) R M ( v ) to zero. The assertion for v = 0 v=0 v = 0 is immediate.
To recover weight, put p t = Pr ( X > t ) p_t=\Pr(X>t) p t = Pr ( X > t ) . Matroid greedy in descending weight order takes a basis of every upper level set. Hence P M ( F ) = ∫ 0 ∞ R M ( p t ) d t P_M(F)=\int_0^\infty R_M(p_t)\,dt P M ( F ) = ∫ 0 ∞ R M ( p t ) d t . The algorithm’s expected weight is the same integral of its expected band counts. Integrating proves the guarantee. Finally, a a a increases and e − 1 − a / a e^{-1-a}/a e − 1 − a / a decreases from infinity to zero, so their unique intersection maximizes c ( a ) c(a) c ( a ) .
Corollary 6 (A threshold in the original weights). Another c 0 c_0 c 0 -competitive rule accepts a nonloop e e e exactly when
X e ≥ c 0 ( P N ∖ e ( F ) − P N / e ( F ) ) . X_e\ge c_0\left(P_{N\setminus e}(F)-P_{N/e}(F)\right). X e ≥ c 0 ( P N ∖ e ( F ) − P N / e ( F ) ) . Proof. Integrating the one-step inequality in the proof of Theorem 4 shows that the expected current reward plus c 0 c_0 c 0 times the expected prophet value in the child minor is at least c 0 P N ( F ) c_0P_N(F) c 0 P N ( F ) . For each realized X e X_e X e , the rule in the corollary maximizes this sum over the two choices. Applying the inequality at each arrival proves the claim.
This price also connects the two matroid bounds. Let τ e \tau_e τ e be the difference of the realized optima in N ∖ e N \setminus e N ∖ e and N / e N/e N / e on the remaining weights. The prophet’s gain over deletion is E ( X e − τ e ) + \mathbb{E}(X_e-\tau_e)^+ E ( X e − τ e ) + ; the best decision credited with c 0 c_0 c 0 times the child’s prophet value gains E ( X e − c 0 E τ e ) + \mathbb{E}(X_e-c_0\mathbb{E}\tau_e)^+ E ( X e − c 0 E τ e ) + over its deletion credit. Corollary 6 and its proof show that, for a common law, the latter gain pays at least c 0 c_0 c 0 times the former for each next label. With different marginals we will obtain a surplus comparison by averaging over the next label under a suitably chosen reference law (§ 9 ).
How much can a one-step comparison prove?
The quantitative loss in Theorem 4 is sharp for the local comparison used in its proof. This statement already holds in rank one, where the optimal stopping rule attains the larger Hill–Kertz constant [CFH+21]. The example identifies where a stronger argument must use the continuation of the policy.
Proposition 7. Suppose a rule, possibly randomized, earns at every arrival and every quantile level v v v at least a fraction c c c of the expected one-step drop in R N ( v ) R_N(v) R N ( v ) , on every matroid with a common weight law. Then c ≤ c 0 c \le c_0 c ≤ c 0 . The same upper bound holds for a rule required only to cover the one-step drop in P N ( F ) P_N(F) P N ( F ) , even when the rule can depend on F F F .
Proof. For the band comparison, consider m + 1 m+1 m + 1 parallel elements. Write q m q_m q m for the marginal probability of taking the first element. At level v v v the first-step reward is at most min ( q m , v ) \min(q_m,v) min ( q m , v ) for any decision rule. By (2) , the expected drop is D m ( v ) = q m + ( v − q m ) ( 1 − v ) m D_m(v)=q_m+(v-q_m)(1-v)^m D m ( v ) = q m + ( v − q m ) ( 1 − v ) m . For 0 < c < 1 0<c<1 0 < c < 1 , put d = 1 / c − 1 d=1/c-1 d = 1/ c − 1 . A positive guarantee requires q m > 0 q_m>0 q m > 0 . Taking v ↓ 0 v\downarrow0 v ↓ 0 gives 1 + m q m = lim v ↓ 0 D m ( v ) / v ≤ 1 + d 1+mq_m=\lim_{v\downarrow0}D_m(v)/v\le1+d 1 + m q m = lim v ↓ 0 D m ( v ) / v ≤ 1 + d . Now set v = ( 1 + d ) / m v=(1+d)/m v = ( 1 + d ) / m for large m m m , so v > q m v>q_m v > q m . The local inequality would give
d ≥ D m ( v ) q m − 1 = ( v q m − 1 ) ( 1 − v ) m ≥ 1 d ( 1 − 1 + d m ) m . d \ge\frac{D_m(v)}{q_m}-1=\left(\frac{v}{q_m}-1\right)(1-v)^m \ge\frac{1}{d}\left(1-\frac{1+d}{m}\right)^m. d ≥ q m D m ( v ) − 1 = ( q m v − 1 ) ( 1 − v ) m ≥ d 1 ( 1 − m 1 + d ) m .
Passing to the limit yields d 2 ≥ e − 1 − d d^2\ge e^{-1-d} d 2 ≥ e − 1 − d , equivalently c ≤ c 0 c\le c_0 c ≤ c 0 . The case c = 1 c=1 c = 1 follows by monotonicity.
For the expected-weight comparison, suppose c 0 < c ≤ 1 c_0<c\le1 c 0 < c ≤ 1 . Let M k M_k M k denote the maximum of the k k k future draws on k + 1 k+1 k + 1 parallel elements and let X X X be the first draw. Crediting the child with c c c times its prophet value, the best decision compares X X X with c E M k c\mathbb{E}M_k c E M k . Subtracting the deletion credit c E M k c\mathbb{E}M_k c E M k from both sides, the required inequality becomes
E ( X − c E M k ) + ≥ c E ( X − M k ) + . (3) \mathbb{E}(X-c\mathbb{E}M_k)_+ \ge c\mathbb{E}(X-M_k)_+. \tag*{(3)} E ( X − c E M k ) + ≥ c E ( X − M k ) + . (3)
With d = 1 / c − 1 d=1/c-1 d = 1/ c − 1 and a = 1 + d a=1+d a = 1 + d , take the three-point law on { 0 , 1 , H k } \{0,1,H_k\} { 0 , 1 , H k } specified by
Pr ( X ≥ 1 ) = a / k , Pr ( X = H k ) = k − 2 , H k − 1 = d + ( 1 − a / k ) k 1 − ( 1 − k − 2 ) k . \Pr(X\ge1)=a/k,\qquad\Pr(X=H_k)=k^{-2},\qquad H_k-1=\frac{d+(1-a/k)^k}{1-(1-k^{-2})^k}. Pr ( X ≥ 1 ) = a / k , Pr ( X = H k ) = k − 2 , H k − 1 = 1 − ( 1 − k − 2 ) k d + ( 1 − a / k ) k .
For all large k k k these are valid probabilities and H k > 1 H_k>1 H k > 1 . The choice of H k H_k H k makes c E M k = 1 c\mathbb{E}M_k=1 c E M k = 1 and ( H k − 1 ) / k → b = d + e − a (H_k-1)/k\to b=d+e^{-a} ( H k − 1 ) / k → b = d + e − a . Multiply (3) by k k k . Its left side tends to b b b . On its right use E ( X − M k ) + = ∫ 0 ∞ ( 1 − F ( t ) ) F ( t ) k d t \mathbb{E}(X-M_k)_+=\int_0^\infty(1-F(t))F(t)^k\,dt E ( X − M k ) + = ∫ 0 ∞ ( 1 − F ( t )) F ( t ) k d t . The contributions from [ 0 , 1 ) [0,1) [ 0 , 1 ) and [ 1 , H k ) [1,H_k) [ 1 , H k ) after multiplying by k k k tend to a e − a ae^{-a} a e − a and b b b , respectively. Thus b ≥ c ( a e − a + b ) b\ge c(ae^{-a}+b) b ≥ c ( a e − a + b ) would be necessary, or d 2 ≥ e − 1 − d d^2\ge e^{-1-d} d 2 ≥ e − 1 − d . This contradicts c > c 0 c>c_0 c > c 0 . □ \square □
In rank one, a stopping rule attains the larger Hill–Kertz constant by balancing gains across arrivals. Whether the same 0.74544 … 0.74544\ldots 0.74544 … guarantee holds on every matroid in random order remains open. Appendix § 13 characterizes the optimum in that model by allowing precisely this kind of compensation.
Reference distributions and structural inequalities
The algorithm compares product distributions obtained by multiplying every upper tail by the same factor. This section establishes the two inequalities it needs. The first converts surplus that survives a second draw into overlap between two optimum bases (Lemma 10). The second lower-bounds the surplus available to an online threshold rule when little of the deletion surplus survives (Corollary 15).
Information and computation. The algorithm knows the ground set, the matroid through its independence oracle, and the labeled input distributions. At an arrival it observes the label and value and must decide immediately. The algorithm draws its reference samples using fresh randomness. When it constructs a candidate for the currently arriving label, it may fix that coordinate at the observed value and sample all other coordinates independently from their reference distributions. For the computational part of Theorem 1 , each distribution is an explicit finite list of rational values and probabilities; let L L L be their total binary encoding length. We first analyze exact random draws. Appendix § 14 replaces them by finite procedures and proves a worst-case polynomial bound on arithmetic operations and random bits.
Symbolic parameters. Fix positive rational constants δ \delta δ , θ \theta θ , ε \varepsilon ε , η \eta η , ρ \rho ρ , s s s , with δ \delta δ dyadic, meaning an integer divided by a power of two. Define
J = [ q − , q + ] = [ 1 − 4 δ , 1 + 4 δ ] , a ( q ) = 1 − θ q , d ∗ ( q ) = 1 − a ( q ) a ( q ) . (4) J = [q_-, q_+] = [1 - 4\delta, 1 + 4\delta], \qquad a(q) = 1 - \theta q, \qquad d_*(q) = \frac{1-a(q)}{a(q)}. \tag*{(4)} J = [ q − , q + ] = [ 1 − 4 δ , 1 + 4 δ ] , a ( q ) = 1 − θ q , d ∗ ( q ) = a ( q ) 1 − a ( q ) . (4)
The potential is a ( q ) F q a(q)F_q a ( q ) F q , where F q F_q F q is the expected reference optimum defined below. The algorithm uses η \eta η to decide whether to invoke the basis-exchange continuation. Its last δ \delta δ units of time will play a different role from the rest. The estimates have accuracy parameter ε \varepsilon ε and error budget ρ \rho ρ . The constant s s s enters only in the rank inequality of Lemma 13 . We use the following bounds:
0 < ε < δ ≤ 1 8 , ε ≤ 1 10 , 0 < θ < 1 , 0 < ρ < 1 , s > 0 , η > 10 ε , 1 2 ≤ a ( q ) ≤ 3 4 ( q ∈ J ) , ( max q ∈ J a ( q ) ) q + ≤ 1 , d ∗ ( q ) − 20 ε < 1 ( q ∈ J ) . (5) \begin{aligned}
&0 < \varepsilon< \delta\le\frac{1}{8}, \qquad\varepsilon\le\frac{1}{10}, \qquad0 < \theta< 1, \qquad0 < \rho< 1, \qquad s > 0, \qquad\eta> 10\varepsilon,\\
&\frac{1}{2} \le a(q) \le\frac{3}{4}\quad(q \in J), \qquad\left(\max_{q\in J} a(q)\right)q_+ \le1, \qquad d_*(q) - 20\varepsilon< 1\quad(q \in J). \tag*{(5)}
\end{aligned} 0 < ε < δ ≤ 8 1 , ε ≤ 10 1 , 0 < θ < 1 , 0 < ρ < 1 , s > 0 , η > 10 ε , 2 1 ≤ a ( q ) ≤ 4 3 ( q ∈ J ) , ( q ∈ J max a ( q ) ) q + ≤ 1 , d ∗ ( q ) − 20 ε < 1 ( q ∈ J ) . (5)
The proof of Theorem 1 will use three further scalar inequalities, stated in § 9 . Their meaning will be clear after the two possible continuations have been analyzed. Appendix § 15 gives a single choice satisfying all of them.
Deletion surplus and reference distributions
Let M M M be a loopless matroid, let Y = ( Y e ) e ∈ E Y = (Y_e)_{e\in E} Y = ( Y e ) e ∈ E have independent nonnegative coordinates, and assume F = E OPT ( M , Y ) < ∞ F = \mathbb{E}\operatorname{OPT}(M,Y) < \infty F = E OPT ( M , Y ) < ∞ . Fix a total order on the labels and use it to break all greedy ties. Let B ( Y ) B(Y) B ( Y ) be the resulting maximum-weight basis; zero-weight elements complete an optimum independent set to a basis.
For each label e e e , define its exclusion threshold by
τ e ( Y − e ) = OPT ( M ∖ e , Y ) − OPT ( M / e , Y ) . \tau_e(Y_{-e}) = \operatorname{OPT}(M\setminus e,Y) - \operatorname{OPT}(M/e,Y). τ e ( Y − e ) = OPT ( M ∖ e , Y ) − OPT ( M / e , Y ) .
This threshold depends only on the other values and is zero for a coloop. Separating an optimum according to whether it contains e e e gives
OPT ( M , Y ) − OPT ( M ∖ e , Y ) = ( Y e − τ e ) + , OPT ( M , Y ) − OPT ( M / e , Y ) = max { Y e , τ e } . (6) \begin{aligned}
\operatorname{OPT}(M,Y) - \operatorname{OPT}(M\setminus e,Y) &= (Y_e-\tau_e)^+,\\
\operatorname{OPT}(M,Y) - \operatorname{OPT}(M/e,Y) &= \max\{Y_e,\tau_e\}. \tag*{(6)}
\end{aligned} OPT ( M , Y ) − OPT ( M ∖ e , Y ) OPT ( M , Y ) − OPT ( M / e , Y ) = ( Y e − τ e ) + , = max { Y e , τ e } . (6)
Write
m e = E τ e , d e = E ( Y e − τ e ) + , D = ∑ e d e , m_e = \mathbb{E}\tau_e,\qquad d_e = \mathbb{E}(Y_e-\tau_e)^+,\qquad D=\sum_e d_e, m e = E τ e , d e = E ( Y e − τ e ) + , D = e ∑ d e ,
H = ∑ e E ( min { Y e , Y e ′ } − τ e ) + , C = D − H , H=\sum_e\mathbb{E}(\min\{Y_e,Y'_e\}-\tau_e)^+,\qquad C=D-H, H = e ∑ E ( min { Y e , Y e ′ } − τ e ) + , C = D − H ,
where Y e ′ Y'_e Y e ′ is an independent copy of Y e Y_e Y e , independent also of Y − e Y_{-e} Y − e . Thus D D D is the total deletion surplus, while H H H counts the part that survives a second independent draw of the element’s own value. We also define
x e ( z ) = P ( e ∈ B ( Y ) , Y e > z ) , Q = ∑ e ∫ 0 ∞ x e ( z ) 2 d z . x_e(z)=\mathbb{P}(e\in B(Y),\ Y_e>z),\qquad Q=\sum_e\int_0^\infty x_e(z)^2\,dz. x e ( z ) = P ( e ∈ B ( Y ) , Y e > z ) , Q = e ∑ ∫ 0 ∞ x e ( z ) 2 d z .
The quantity Q Q Q measures overlap between the value profiles of two independent optimum bases. For a height z > 0 z>0 z > 0 , put p e ( z ) = P ( Y e > z ) p_e(z)=\mathbb{P}(Y_e>z) p e ( z ) = P ( Y e > z ) and S z = { e : Y e > z } S_z=\{e:Y_e>z\} S z = { e : Y e > z } , and let
ρ e ( z ) = P ( e ∉ cl ( S z ∖ e ) ) . \rho_e(z)=\mathbb{P}(e\notin\operatorname{cl}(S_z\setminus e)). ρ e ( z ) = P ( e ∈ / cl ( S z ∖ e )) .
Greedy selects exactly r ( S z ) r(S_z) r ( S z ) elements above z z z . To identify the other two integrands, fix Y − e Y_{-e} Y − e . On A = S z ∖ e A=S_z\setminus e A = S z ∖ e the ranks in M ∖ e M\setminus e M ∖ e and M / e M/e M / e differ by 1 precisely when A A A spans e e e . Integrating this rank difference gives τ e \tau_e τ e . Since the sets S z ∖ e S_z\setminus e S z ∖ e are nested as z z z increases, τ e \tau_e τ e is the length of the initial interval of heights on which they span e e e . Thus, up to its endpoint, the event z > τ e z>\tau_e z > τ e is exactly the event that S z ∖ e S_z\setminus e S z ∖ e does not span e e e . Independence now gives
F = ∫ 0 ∞ E r ( S z ) d z , D = ∫ 0 ∞ ∑ e p e ( z ) ρ e ( z ) d z , H = ∫ 0 ∞ ∑ e p e ( z ) 2 ρ e ( z ) d z . (7) \begin{aligned}
F&=\int_0^\infty\mathbb{E}r(S_z)\,dz,\\
D&=\int_0^\infty\sum_e p_e(z)\rho_e(z)\,dz,\\
H&=\int_0^\infty\sum_e p_e(z)^2\rho_e(z)\,dz. \tag*{(7)}
\end{aligned} F D H = ∫ 0 ∞ E r ( S z ) d z , = ∫ 0 ∞ e ∑ p e ( z ) ρ e ( z ) d z , = ∫ 0 ∞ e ∑ p e ( z ) 2 ρ e ( z ) d z . (7)
The integrand defining D D D is the expected number of coloops in the active restriction. Consequently
0 ≤ H ≤ D ≤ F , 0 ≤ Q ≤ F . (8) 0\le H\le D\le F,\qquad0\le Q\le F. \tag*{(8)} 0 ≤ H ≤ D ≤ F , 0 ≤ Q ≤ F . (8)
For the second bound, use x e ( z ) 2 ≤ x e ( z ) x_e(z)^2\le x_e(z) x e ( z ) 2 ≤ x e ( z ) and ∑ e x e ( z ) = E r ( S z ) \sum_e x_e(z)=\mathbb{E}r(S_z) ∑ e x e ( z ) = E r ( S z ) .
Given the actual distributions X X X , the reference distribution with parameter q > 0 q>0 q > 0 is the product law Y q Y^q Y q defined by
P ( Y e q > z ) = min { 1 , q P ( X e > z ) } , z ≥ 0. (9) \mathbb{P}(Y^q_e>z)=\min\{1,q\mathbb{P}(X_e>z)\},\qquad z\ge0. \tag*{(9)} P ( Y e q > z ) = min { 1 , q P ( X e > z )} , z ≥ 0. (9)
For q ≤ 1 q\le1 q ≤ 1 , this means independently retaining each X e X_e X e with probability q q q and replacing it by zero otherwise. For q > 1 q>1 q > 1 it puts more mass on the upper quantiles. Use subscripts q q q for the quantities of this reference instance, such as F q F_q F q , D q D_q D q , H q H_q H q , and Q q Q_q Q q .
The next lemma relates a change in q q q to deletion surplus. The error term H q H_q H q accounts for coordinates whose reference tail has reached one.
Lemma 8 (Reference derivatives). The function q ↦ F q q\mapsto F_q q ↦ F q is nondecreasing, continuous, and concave. At every q > 0 q>0 q > 0 , its finite one-sided derivatives satisfy
D q − H q ≤ q ( F q ) + ≤ q ( F q ) − ≤ D q . D_q-H_q\le q(F_q)^+ \le q(F_q)^- \le D_q. D q − H q ≤ q ( F q ) + ≤ q ( F q ) − ≤ D q . Moreover,
min { 1 , q } F 1 ≤ F q ≤ max { 1 , q } F 1 . (10) \min\{1,q\}F_1\le F_q\le\max\{1,q\}F_1. \tag*{(10)} min { 1 , q } F 1 ≤ F q ≤ max { 1 , q } F 1 . (10)
Proof. At a fixed height z z z , expected rank is the multilinear extension of matroid rank evaluated at p e q ( z ) = min { 1 , q p e ( z ) } p_e^q(z)=\min\{1,qp_e(z)\} p e q ( z ) = min { 1 , q p e ( z )} , where here p e ( z ) = P ( X e > z ) p_e(z)=\mathbb{P}(X_e>z) p e ( z ) = P ( X e > z ) . Its derivative in coordinate e e e is the nonspanning probability ρ e q ( z ) \rho_e^q(z) ρ e q ( z ) . If q p e ( z ) < 1 qp_e(z)<1 q p e ( z ) < 1 , then q ∂ q p e q ( z ) = p e q ( z ) q\partial_qp_e^q(z)=p_e^q(z) q ∂ q p e q ( z ) = p e q ( z ) ; if q p e ( z ) > 1 qp_e(z)>1 q p e ( z ) > 1 , this derivative is zero. At equality, the left derivative includes the coordinate and the right derivative excludes it. Thus each one-sided derivative, multiplied by q q q , differs from D q D_q D q only by saturated-coordinate terms. Those terms are bounded by H q H_q H q , because p e q ( z ) 2 = p e q ( z ) = 1 p_e^q(z)^2=p_e^q(z)=1 p e q ( z ) 2 = p e q ( z ) = 1 on a saturated coordinate.
Both the slope of an unsaturated coordinate and its nonspanning probability are nonincreasing in q q q . The derivative of each layer’s expected rank is therefore nonincreasing, which proves concavity. Monotonicity follows by coupling the active sets. Differentiation and continuity under the height integral are justified locally by the integrable bound ∑ e p e ( z ) \sum_e p_e(z) ∑ e p e ( z ) ; every nonloop satisfies E X e ≤ F 1 \mathbb{E}X_e\le F_1 E X e ≤ F 1 .
For q ≤ 1 q\le1 q ≤ 1 , independently thin an X X X -optimal basis to obtain F q ≥ q F 1 F_q\ge qF_1 F q ≥ q F 1 , while monotonicity gives F q ≤ F 1 F_q\le F_1 F q ≤ F 1 . Also F q ≤ q ∑ e E X e → 0 F_q\le q\sum_e\mathbb{E}X_e\to0 F q ≤ q ∑ e E X e → 0 as q ↓ 0 q\downarrow0 q ↓ 0 . Concavity with this zero limit gives F q ≤ q F 1 F_q\le qF_1 F q ≤ q F 1 for q ≥ 1 q\ge1 q ≥ 1 ; the remaining inequality follows from monotonicity.
Lemma 9 (An affine potential). Let a a a be a positive nonincreasing affine function on an interval J ⊂ ( 0 , ∞ ) J\subset(0,\infty) J ⊂ ( 0 , ∞ ) . Then q ↦ a ( q ) F q q\mapsto a(q)F_q q ↦ a ( q ) F q is concave on J J J .
Proof. Let x < y x<y x < y belong to J J J and put q = t x + ( 1 − t ) y q=tx+(1-t)y q = t x + ( 1 − t ) y , with t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] . Using concavity of F F F and then affinity of a a a ,
a ( q ) F q ≥ a ( q ) ( t F x + ( 1 − t ) F y ) = t a ( x ) F x + ( 1 − t ) a ( y ) F y + t ( 1 − t ) ( a ( y ) − a ( x ) ) ( F x − F y ) ≥ t a ( x ) F x + ( 1 − t ) a ( y ) F y . \begin{aligned}
a(q)F_q &\ge a(q)\bigl(tF_x+(1-t)F_y\bigr)\\
&=ta(x)F_x+(1-t)a(y)F_y+t(1-t)(a(y)-a(x))(F_x-F_y)\\
&\ge ta(x)F_x+(1-t)a(y)F_y.
\end{aligned} a ( q ) F q ≥ a ( q ) ( t F x + ( 1 − t ) F y ) = t a ( x ) F x + ( 1 − t ) a ( y ) F y + t ( 1 − t ) ( a ( y ) − a ( x )) ( F x − F y ) ≥ t a ( x ) F x + ( 1 − t ) a ( y ) F y .
The last product is nonnegative because a a a decreases and F F F increases.
Stable surplus implies overlap
The derivative bounds involve H H H , but the continuation earns additional reward in proportion to Q Q Q . To relate them, run greedy twice on the same active set, once in decreasing priority order and once in reverse. An active coloop must survive both scans.
Lemma 10 (Stable surplus and overlap). For every independent nonnegative value vector,
H 2 ≤ Q ( F − D + H ) ≤ F Q . (11) H^2\le Q(F-D+H)\le FQ. \tag*{(11)} H 2 ≤ Q ( F − D + H ) ≤ F Q . (11)
Proof. Fix a height z z z and suppress it from the notation. Let S S S activate the labels independently with probabilities p e = P ( Y e > z ) p_e=\mathbb{P}(Y_e>z) p e = P ( Y e > z ) . Independently of these activity indicators, draw for each label a latent value from its conditional law given Y e > z Y_e>z Y e > z . Labels with p e = 0 p_e=0 p e = 0 can be omitted. Order the latent values decreasingly, breaking ties by the fixed label order.
For fixed latent priorities, let a e + a_e^+ a e + be the probability that the active labels preceding e e e do not span it, and let a e − a_e^- a e − be the corresponding probability for the labels following it. These events depend on disjoint sets of independent activity indicators. Nonspan by all other active labels implies both events, so
ρ e ≤ a e + a e − . \rho_e\le a_e^+a_e^-. ρ e ≤ a e + a e − .
The function a e + a_e^+ a e + is nondecreasing in e e e ’s latent value and nonincreasing in each other latent value; a e − a_e^- a e − has the opposite monotonicities. Product association, after reversing the order of the other coordinates, therefore gives
E [ a e + a e − ] ≤ ( E a e + ) ( E a e − ) . \mathbb{E}[a_e^+a_e^-]\le(\mathbb{E}a_e^+)(\mathbb{E}a_e^-). E [ a e + a e − ] ≤ ( E a e + ) ( E a e − ) .
For completeness, association in one coordinate follows from
2 Cov ( f ( Z ) , g ( Z ) ) = E [ ( f ( Z ) − f ( Z ′ ) ) ( g ( Z ) − g ( Z ′ ) ) ] 2\operatorname{Cov}(f(Z),g(Z))=\mathbb{E}[(f(Z)-f(Z'))(g(Z)-g(Z'))] 2 Cov ( f ( Z ) , g ( Z )) = E [( f ( Z ) − f ( Z ′ )) ( g ( Z ) − g ( Z ′ ))]
for an independent copy Z ′ Z' Z ′ . Conditional covariance and induction extend it to independent coordinates; replacing one function by its negative gives the displayed reversed inequality.
Let x e + x_e^+ x e + and x e − x_e^- x e − be the inclusion probabilities in the greedy and reverse-greedy bases of S S S . The reverse order reverses the entire value-and-label order. Then
p e 2 ρ e ≤ x e + x e − , ∑ e x e + = ∑ e x e − = Er ( S ) . p_e^2\rho_e\le x_e^+x_e^-,\qquad\sum_e x_e^+=\sum_e x_e^-=\operatorname{Er}(S). p e 2 ρ e ≤ x e + x e − , e ∑ x e + = e ∑ x e − = Er ( S ) .
Here x e + = x e ( z ) x_e^+=x_e(z) x e + = x e ( z ) because the greedy choices above height z z z depend only on the active elements. Every active coloop belongs to every basis of S S S . Hence p e ρ e ≤ x e − ≤ p e p_e\rho_e\le x_e^-\le p_e p e ρ e ≤ x e − ≤ p e , and consequently
x e − ( 1 − x e − ) ≥ p e ( 1 − p e ) ρ e . x_e^-(1-x_e^-)\ge p_e(1-p_e)\rho_e. x e − ( 1 − x e − ) ≥ p e ( 1 − p e ) ρ e .
Define Q − = ∫ 0 ∞ ∑ e x e − ( z ) 2 d z Q_-=\int_0^\infty\sum_e x_e^-(z)^2\,dz Q − = ∫ 0 ∞ ∑ e x e − ( z ) 2 d z . Integrating the preceding inequality and using (7) yields
F − Q − ≥ D − H . F-Q_-\ge D-H. F − Q − ≥ D − H .
All these integrals are finite, since the squared marginals are bounded by the marginals and their sum integrates to F F F . A final Cauchy–Schwarz inequality gives
H ≤ ∫ 0 ∞ ∑ e x e + ( z ) x e − ( z ) d z ≤ Q Q − ≤ Q ( F − D + H ) . H\le\int_0^\infty\sum_e x_e^+(z)x_e^-(z)\,dz\le\sqrt{QQ_-}\le\sqrt{Q(F-D+H)}. H ≤ ∫ 0 ∞ e ∑ x e + ( z ) x e − ( z ) d z ≤ Q Q − ≤ Q ( F − D + H ) .
The second inequality in (11) follows from H ≤ D H\le D H ≤ D .
Expected contraction prices
We next relate deletion surplus to the surplus above deterministic thresholds. The appropriate deterministic prices are expected contraction costs:
π e = E max { Y e , τ e } = m e + d e . \pi_e=\mathbb{E}\max\{Y_e,\tau_e\}=m_e+d_e. π e = E max { Y e , τ e } = m e + d e .
Let B B B be a maximum-π \pi π basis, and write
P = ∑ e ∈ B π e , G = F − P . P=\sum_{e\in B}\pi_e,\qquad G=F-P. P = e ∈ B ∑ π e , G = F − P .
The choice of a fixed basis will let us integrate a rank inequality over all heights. The gap G G G measures how much we lose by charging the contraction prices of this basis against the optimum.
Lemma 11 (Expected contraction prices). One has 0 ≤ P ≤ F 0\le P\le F 0 ≤ P ≤ F . Every strict superlevel set T T T of π \pi π is spanned by B ∩ T B\cap T B ∩ T , and B ∩ T B\cap T B ∩ T is a basis of T T T . Moreover,
G = ∫ 0 ∞ E [ r ( S z ) − ∣ B ∩ cl ( S z ) ∣ ] d z , S z = { e : Y e > z } , (12) G=\int_0^\infty\mathbb{E}\left[r(S_z)-\lvert B\cap\operatorname{cl}(S_z)\rvert\right]\,dz,\qquad S_z=\{e:Y_e>z\}, \tag*{(12)} G = ∫ 0 ∞ E [ r ( S z ) − ∣ B ∩ cl ( S z )∣ ] d z , S z = { e : Y e > z } , (12) and its integrand is nonnegative.
Proof. For deterministic nonnegative weights y y y , the weighted-rank formula and the rank formula for contraction give
OPT ( M , y ) = ∫ 0 ∞ r ( S z ( y ) ) d z , OPT ( M , y ) − OPT ( M / e , y ) = ∫ 0 ∞ 1 { e ∈ cl ( S z ( y ) ) } d z . \operatorname{OPT}(M,y)=\int_{0}^{\infty}r(S_z(y))\,\mathrm{d}z,\qquad\operatorname{OPT}(M,y)-\operatorname{OPT}(M/e,y)=\int_{0}^{\infty}\mathbf{1}\{e\in\operatorname{cl}(S_z(y))\}\,\mathrm{d}z. OPT ( M , y ) = ∫ 0 ∞ r ( S z ( y )) d z , OPT ( M , y ) − OPT ( M / e , y ) = ∫ 0 ∞ 1 { e ∈ cl ( S z ( y ))} d z .
If I I I is independent, then I ∩ cl ( S z ( y ) ) I\cap\operatorname{cl}(S_z(y)) I ∩ cl ( S z ( y )) is independent in a flat of rank r ( S z ( y ) ) r(S_z(y)) r ( S z ( y )) . Therefore the sum of the realized contraction costs over I I I is at most OPT ( M , y ) \operatorname{OPT}(M,y) OPT ( M , y ) . Take expectations and maximize over I I I to obtain P ≤ F P\le F P ≤ F . Apply the same identity to the fixed basis B B B and subtract its price sum from F F F to obtain (12) . Finally, the greedy characterization of a maximum-weight basis shows that B ∩ T B\cap T B ∩ T is a basis of every strict superlevel set T T T of π \pi π .
Fix b ∈ ( 0 , 1 ) b\in(0,1) b ∈ ( 0 , 1 ) and cap each reference value at b π e b\pi_e b π e :
Y ~ e = min { Y e , b π e } , Δ b = b P − E OPT ( M , Y ~ ) ≥ 0. \widetilde{Y}_e=\min\{Y_e,b\pi_e\},\qquad\Delta_b=bP-\mathbb{E}\operatorname{OPT}(M,\widetilde{Y})\ge0. Y e = min { Y e , b π e } , Δ b = b P − E OPT ( M , Y ) ≥ 0.
The cap deficit is nonnegative because OPT ( M , Y ~ ) ≤ OPT ( M , b π ) = b P \operatorname{OPT}(M,\widetilde{Y})\le\operatorname{OPT}(M,b\pi)=bP OPT ( M , Y ) ≤ OPT ( M , bπ ) = b P . Define the two threshold surpluses and the remaining capped surplus by
S b = ∑ e E ( Y e − b m e ) + , S π , b = ∑ e E ( Y e − b π e ) + , S_b=\sum_e\mathbb{E}(Y_e-bm_e)^+,\qquad S_{\pi,b}=\sum_e\mathbb{E}(Y_e-b\pi_e)^+, S b = e ∑ E ( Y e − b m e ) + , S π , b = e ∑ E ( Y e − b π e ) + ,
K b = ∑ e E ( min { Y e , b π e } − τ e ) + . K_b=\sum_e\mathbb{E}\bigl(\min\{Y_e,b\pi_e\}-\tau_e\bigr)^+. K b = e ∑ E ( min { Y e , b π e } − τ e ) + .
In K b K_b K b , compute τ e \tau_e τ e from the other coordinates of the original reference vector Y Y Y .
Lemma 12 (Surplus decomposition).
S b ≥ S π , b ≥ ( 1 − b ) F + b G + Δ b , D ≤ S π , b + K b . (13) S_b\ge S_{\pi,b}\ge(1-b)F+bG+\Delta_b,\qquad D\le S_{\pi,b}+K_b. \tag*{(13)} S b ≥ S π , b ≥ ( 1 − b ) F + b G + Δ b , D ≤ S π , b + K b . (13)
Proof. The first comparison follows from m e ≤ π e m_e\le\pi_e m e ≤ π e . Evaluating the capped weights on a y y y -optimal basis gives, for every realization,
OPT ( M , y ) ≤ OPT ( M , min { y , b π } ) + ∑ e ( y e − b π e ) + . \operatorname{OPT}(M,y)\le\operatorname{OPT}(M,\min\{y,b\pi\})+\sum_e(y_e-b\pi_e)^+. OPT ( M , y ) ≤ OPT ( M , min { y , bπ }) + e ∑ ( y e − b π e ) + .
Take expectations and use P = F − G P=F-G P = F − G for the second comparison. For the last inequality, apply ( y − t ) + ≤ ( y − w ) + + ( min { y , w } − t ) + (y-t)^+\le(y-w)^++(\min\{y,w\}-t)^+ ( y − t ) + ≤ ( y − w ) + + ( min { y , w } − t ) + with t = τ e t=\tau_e t = τ e and w = b π e w=b\pi_e w = b π e , and sum over e e e .
A rank inequality from Poisson concavity
To bound K b K_b K b , we use the concavity of Poisson-rounded matroid rank, which underlies the rounding method of Dughmi, Roughgarden, and Yan [14 ] . A tangent inequality evaluated at one scaled basis vector suffices here. The parameter s s s below will be chosen in Appendix D.
Lemma 13 (A fixed Poisson tangent). Let N 0 N_0 N 0 be a rank-r 0 r_0 r 0 matroid with a basis C 0 C_0 C 0 , and let R R R activate labels independently with probabilities p e p_e p e . Put
ρ e = P ( e ∉ cl N 0 ( R ∖ e ) ) , m = ∑ f ∈ C 0 P ( f ∉ cl N 0 ( R ) ) . \rho_e=\mathbb{P}(e\notin\operatorname{cl}_{N_0}(R\setminus e)),\qquad m=\sum_{f\in C_0}\mathbb{P}(f\notin\operatorname{cl}_{N_0}(R)). ρ e = P ( e ∈ / cl N 0 ( R ∖ e )) , m = f ∈ C 0 ∑ P ( f ∈ / cl N 0 ( R )) . For every s > 0 s>0 s > 0 ,
∑ e p e ρ e ≤ ∑ e p e 2 ρ e + r 0 e − s + s m . (14) \sum_e p_e\rho_e\le\sum_e p_e^2\rho_e+r_0e^{-s}+sm. \tag*{(14)} e ∑ p e ρ e ≤ e ∑ p e 2 ρ e + r 0 e − s + s m . (14)
Proof. First suppose p e < 1 p_e < 1 p e < 1 and set λ e = − log ( 1 − p e ) \lambda_e = -\log(1-p_e) λ e = − log ( 1 − p e ) . For x ∈ R ≥ 0 E ( N 0 ) x \in\mathbb{R}_{\geq0}^{E(N_0)} x ∈ R ≥ 0 E ( N 0 ) , let R x R_x R x activate each label independently with probability 1 − e − x e 1-e^{-x_e} 1 − e − x e , and define f ( x ) = E r N 0 ( R x ‾ ) f(x) = \mathbb{E}r_{N_0}(\overline{R_x}) f ( x ) = E r N 0 ( R x ) . Direct differentiation gives
∂ e f ( x ) = P ( e ∉ cl N 0 ( R x ) ) . \partial_e f(x) = \mathbb{P}(e \notin\operatorname{cl}_{N_0}(R_x)). ∂ e f ( x ) = P ( e ∈ / cl N 0 ( R x )) .
The diagonal second derivative is the negative of this probability. For distinct labels e , f e,f e , f , the mixed second derivative is minus the probability that e e e and f f f are parallel nonloops in N 0 / R x N_0/R_x N 0 / R x , with contracted labels treated as loops. To see this, condition on the other coordinates. The mixed discrete rank difference is − 1 -1 − 1 exactly for a parallel pair of nonloops; the factors e − x e − x f e^{-x_e-x_f} e − x e − x f enforce the absence of e , f e,f e , f from R x R_x R x .
Thus the negative Hessian is the expectation of a block matrix with one all-ones block for each nonloop parallel class of N 0 / R x N_0/R_x N 0 / R x and zeros elsewhere. Each block is positive semidefinite, so f f f is concave. At x = λ x=\lambda x = λ , write u e = ∂ e f ( λ ) = ( 1 − p e ) ρ e u_e=\partial_e f(\lambda)=(1-p_e)\rho_e u e = ∂ e f ( λ ) = ( 1 − p e ) ρ e . Since C 0 C_0 C 0 is a basis, f ( s 1 C 0 ) = r 0 ( 1 − e − s ) f(s\mathbf{1}_{C_0})=r_0(1-e^{-s}) f ( s 1 C 0 ) = r 0 ( 1 − e − s ) . The tangent inequality gives
∑ e λ e u e ≤ f ( λ ) − r 0 ( 1 − e − s ) + s ∑ f ∈ C 0 u f ≤ r 0 e − s + s m . \sum_e \lambda_e u_e \leq f(\lambda)-r_0(1-e^{-s})+s\sum_{f\in C_0}u_f \leq r_0e^{-s}+sm. e ∑ λ e u e ≤ f ( λ ) − r 0 ( 1 − e − s ) + s f ∈ C 0 ∑ u f ≤ r 0 e − s + s m .
Finally, p e = 1 − e − λ e ≤ λ e p_e=1-e^{-\lambda_e}\leq\lambda_e p e = 1 − e − λ e ≤ λ e , and hence
∑ e p e ρ e − ∑ e p e 2 ρ e = ∑ e p e u e ≤ ∑ e λ e u e . \sum_e p_e\rho_e-\sum_e p_e^2\rho_e=\sum_e p_eu_e\leq\sum_e\lambda_eu_e. e ∑ p e ρ e − e ∑ p e 2 ρ e = e ∑ p e u e ≤ e ∑ λ e u e .
This proves the claim. Coordinates with p e = 1 p_e=1 p e = 1 follow by continuity of the finite Bernoulli expectations. Rank zero is immediate. □
Bounding the capped surplus
We apply the rank inequality separately at every value layer. At height z z z the caps retain only those labels with b π e > z b\pi_e>z b π e > z , but an uncapped active label outside this set can still span a label inside. Conditioning on the outside active labels and contracting them keeps this dependence in the rank calculation.
Lemma 14 (Capped surplus). For every b ∈ ( 0 , 1 ) b\in(0,1) b ∈ ( 0 , 1 ) and s > 0 s>0 s > 0 ,
K b ≤ H + b P e − s + s ( G + Δ b ) . (15) K_b\leq H+bPe^{-s}+s(G+\Delta_b). \tag*{(15)} K b ≤ H + b P e − s + s ( G + Δ b ) . (15)
Proof. At height z > 0 z>0 z > 0 , let T z = { e : b π e > z } T_z=\{e:b\pi_e>z\} T z = { e : b π e > z } . Independence of Y e Y_e Y e from τ e \tau_e τ e gives
K b = ∫ 0 ∞ ∑ e ∈ T z p e ( z ) ρ e ( z ) d z . K_b=\int_0^\infty\sum_{e\in T_z}p_e(z)\rho_e(z)\,dz. K b = ∫ 0 ∞ e ∈ T z ∑ p e ( z ) ρ e ( z ) d z .
By Lemma 11 , B ∩ T z B\cap T_z B ∩ T z is a basis of T z T_z T z . Condition on the outside active set O = S z ∖ T z O=S_z\setminus T_z O = S z ∖ T z . The indicators inside T z T_z T z remain independent. The minor ( M / O ) ∣ T z (M/O)|_{T_z} ( M / O ) ∣ T z has rank at most r ( T z ) r(T_z) r ( T z ) . Since B ∩ T z B\cap T_z B ∩ T z spans T z T_z T z in M M M , it still spans T z T_z T z in this minor. Choose any basis of the minor contained in B ∩ T z B\cap T_z B ∩ T z . For this choice the quantity m m m in Lemma 13 is at most
m z ( O ) = ∑ f ∈ B ∩ T z P ( f ∉ cl ( S z ) ∣ O ) . m_z(O)=\sum_{f\in B\cap T_z}\mathbb{P}(f\notin\operatorname{cl}(S_z)\mid O). m z ( O ) = f ∈ B ∩ T z ∑ P ( f ∈ / cl ( S z ) ∣ O ) .
Apply Lemma 13 to this minor and average over O O O . The two error terms are linear, so
∑ e ∈ T z p e ( z ) ρ e ( z ) ≤ ∑ e ∈ T z p e ( z ) 2 ρ e ( z ) + e − s r ( T z ) + s m ( z ) , \sum_{e\in T_z}p_e(z)\rho_e(z)\leq\sum_{e\in T_z}p_e(z)^2\rho_e(z)+e^{-s}r(T_z)+sm(z), e ∈ T z ∑ p e ( z ) ρ e ( z ) ≤ e ∈ T z ∑ p e ( z ) 2 ρ e ( z ) + e − s r ( T z ) + s m ( z ) ,
::: where m ( z ) = ∑ f ∈ B ∩ T z P ( f ∉ cl ( S z ) ) m(z)=\sum_{f\in B\cap T_z}\mathbb{P}(f\notin\operatorname{cl}(S_z)) m ( z ) = ∑ f ∈ B ∩ T z P ( f ∈ / cl ( S z )) .
It remains to bound the integrated missing mass. For every deterministic set S S S , the set ( B ∖ T z ) ∩ cl ( S ) (B\setminus T_z)\cap\operatorname{cl}(S) ( B ∖ T z ) ∩ cl ( S ) is independent over T z T_z T z : B ∩ T z B\cap T_z B ∩ T z spans T z T_z T z , and B B B is independent. It is therefore also independent over S ∩ T z S\cap T_z S ∩ T z . As all its elements belong to cl ( S ) \operatorname{cl}(S) cl ( S ) ,
r ( S ) ≥ r ( S ∩ T z ) + ∣ ( B ∖ T z ) ∩ cl ( S ) ∣ . r(S)\ge r(S\cap T_z)+|(B\setminus T_z)\cap\operatorname{cl}(S)|. r ( S ) ≥ r ( S ∩ T z ) + ∣ ( B ∖ T z ) ∩ cl ( S ) ∣.
Equivalently,
r ( T z ) − ∣ B ∩ T z ∩ cl ( S ) ∣ ≤ r ( T z ) − r ( S ∩ T z ) + r ( S ) − ∣ B ∩ cl ( S ) ∣ . (16) r(T_z)-|B\cap T_z\cap\operatorname{cl}(S)|\le r(T_z)-r(S\cap T_z)+r(S)-|B\cap\operatorname{cl}(S)|. \tag*{(16)} r ( T z ) − ∣ B ∩ T z ∩ cl ( S ) ∣ ≤ r ( T z ) − r ( S ∩ T z ) + r ( S ) − ∣ B ∩ cl ( S ) ∣. (16)
Average and integrate. The left side integrates to ∫ 0 ∞ m ( z ) d z \int_0^\infty m(z)\,dz ∫ 0 ∞ m ( z ) d z . The first rank deficit integrates to Δ b \Delta_b Δ b , because the capped active set is S z ∩ T z S_z\cap T_z S z ∩ T z and ∫ 0 ∞ r ( T z ) d z = b P \int_0^\infty r(T_z)\,dz=bP ∫ 0 ∞ r ( T z ) d z = b P . The second integrates to G G G by (4.9). Therefore
∫ 0 ∞ m ( z ) d z ≤ G + Δ b . \int_0^\infty m(z)\,dz\le G+\Delta_b. ∫ 0 ∞ m ( z ) d z ≤ G + Δ b .
Now integrate the conditional rank inequality and enlarge its restricted squared-probability term to H H H .
□ \square □
The two deficits G G G and Δ b \Delta_b Δ b can now be eliminated. The resulting bound depends only on the quantities used to select the reference distribution and the thresholds used by the online policy.
Corollary 15 (Threshold surplus). If F > 0 F>0 F > 0 , then for every b ∈ ( 0 , 1 ) b\in(0,1) b ∈ ( 0 , 1 ) and s > 0 s>0 s > 0 ,
S b F ≥ 1 − b + b b + s ( D F − ( 1 − b ) − H F − b e − s ) . (17) \frac{S_b}{F}\ge1-b+\frac{b}{b+s}\left(\frac{D}{F}-(1-b)-\frac{H}{F}-be^{-s}\right). \tag*{(17)} F S b ≥ 1 − b + b + s b ( F D − ( 1 − b ) − F H − b e − s ) . (17)
Proof. Lemma 12 implies
G + Δ b ≤ S b − ( 1 − b ) F b . G+\Delta_b\le\frac{S_b-(1-b)F}{b}. G + Δ b ≤ b S b − ( 1 − b ) F .
Combining the same lemma with Lemma 14 and P ≤ F P\le F P ≤ F gives
D ≤ S b + H + b F e − s + s b ( S b − ( 1 − b ) F ) . D\le S_b+H+bFe^{-s}+\frac{s}{b}(S_b-(1-b)F). D ≤ S b + H + b F e − s + b s ( S b − ( 1 − b ) F ) .
Rearrange and divide by F F F .
□ \square □
All layer integrals above allow atoms. For each realization, changing a strict height cutoff to a weak one affects only a finite set of heights. Tonelli’s theorem therefore gives the same integrals after taking expectations. Integrability follows from F < ∞ F<\infty F < ∞ , since the mean of each nonloop is at most F F F .
A virtual basis-exchange continuation
Suppose two independent reference optima often contain the same valuable elements. We will use this overlap late in the arrival sequence. Each accepted label is inserted into every reference basis by an exchange. The algorithm stores only one record per acceptance. It can then recover any particular basis by replaying the exchanges starting from its original greedy basis.
As in the survival simulation of [ABH+26, Section 6], the algorithm tests a survival event on an auxiliary random sample. Here a test draws a reference basis and replays the accepted records. Lemma 18 gives the resulting acceptance rates.
Fix a loopless residual matroid M M M on n n n labels, a parameter q ∈ J q \in\mathcal{J} q ∈ J , and the product reference law μ \mu μ of Y = Y q Y = Y^q Y = Y q . We first describe the algorithm for finitely supported distributions, so that its screening probabilities are ratios of point masses. The approximation argument at the end of Appendix D extends the existence guarantee to general distributions. Write D e D_e D e and D e q D^q_e D e q for the original and reference distributions. Put
λ = 1 q , t 0 = 1 − δ , α = e − λ t 0 , ω = α − λ δ , (18) \lambda= \frac{1}{q}, \qquad t_0 = 1-\delta, \qquad\alpha= e^{-\lambda t_0}, \qquad\omega= \alpha-\lambda\delta, \tag*{(18)} λ = q 1 , t 0 = 1 − δ , α = e − λ t 0 , ω = α − λ δ , (18)
and assume ω > 0 \omega> 0 ω > 0 . Define
Φ δ ( q , z ) = 1 − α + α ω ( 1 − e − λ δ / ω ) ( 1 + ( 1 − α ) z ) . (19) \Phi_\delta(q,z)=1-\alpha+\alpha\omega\left(1-e^{-\lambda\delta/\omega}\right)\left(1+(1-\alpha)z\right). \tag*{(19)} Φ δ ( q , z ) = 1 − α + α ω ( 1 − e − λ δ / ω ) ( 1 + ( 1 − α ) z ) . (19)
For δ = 0 \delta= 0 δ = 0 , this is the familiar 1 − e − 1 / q 1-e^{-1/q} 1 − e − 1/ q guarantee. For a short positive final interval, its dependence on z z z will give the improvement.
Proposition 16 (Virtual continuation). If F = E OPT ( M , Y ) > 0 F=\mathbb{E}\operatorname{OPT}(M,Y)>0 F = E OPT ( M , Y ) > 0 , there is a feasible online continuation with
E [ ALG ] ≥ Φ δ ( q , Q / F ) F . \mathbb{E}[\operatorname{ALG}] \ge\Phi_\delta(q,Q/F)F. E [ ALG ] ≥ Φ δ ( q , Q / F ) F . In the exact-randomness model it uses O ( n 4 ) O(n^4) O ( n 4 ) matroid independence queries in expectation. Its decisions use only the current arrival and previously accepted records.
Updating virtual bases
Fix the label order from § 2 . For each pair of bases C C C , B B B , we need one injective exchange map from C C C to B B B . The same map must be used regardless of which source element is queried.
Lemma 17 (A canonical exchange map). For bases C C C , B B B , one can construct a bijection ϕ C , B : C → B \phi_{C,B}:C\to B ϕ C , B : C → B fixing C ∩ B C\cap B C ∩ B pointwise such that
B − ϕ C , B ( f ) + f ∈ B ( M ) ( f ∈ C ) . B-\phi_{C,B}(f)+f\in\mathcal{B}(M) \qquad(f\in C). B − ϕ C , B ( f ) + f ∈ B ( M ) ( f ∈ C ) . The map uses O ( n 2 ) O(n^2) O ( n 2 ) matroid independence queries.
Proof. Keep the target basis B B B fixed and initialize a working basis C ′ = C C'=C C ′ = C . Fix every element of C ∩ B C\cap B C ∩ B . Until C ′ = B C'=B C ′ = B , take the first f ∈ C ′ ∖ B f\in C'\setminus B f ∈ C ′ ∖ B in the label order and scan b ∈ B ∖ C ′ b\in B\setminus C' b ∈ B ∖ C ′ in that order. Choose the first b b b such that both B − b + f B-b+f B − b + f and C ′ − f + b C'-f+b C ′ − f + b are bases. Assign ϕ C , B ( f ) = b \phi_{C,B}(f)=b ϕ C , B ( f ) = b and replace C ′ C' C ′ by C ′ − f + b C'-f+b C ′ − f + b .
Such a b b b exists. Let Γ ⊆ B + f \Gamma\subseteq B+f Γ ⊆ B + f be the fundamental circuit of f f f , and let H = cl ( C ′ ∖ f ) H=\operatorname{cl}(C'\setminus f) H = cl ( C ′ ∖ f ) . Since f ∉ H f\notin H f ∈ / H and f ∈ cl ( Γ ∖ f ) f\in\operatorname{cl}(\Gamma\setminus f) f ∈ cl ( Γ ∖ f ) , some b ∈ Γ ∖ f b\in\Gamma\setminus f b ∈ Γ ∖ f lies outside H H H . This element belongs to B ∖ C ′ B\setminus C' B ∖ C ′ and permits both exchanges.
Each step removes one original source element outside B B B and adds one previously absent element of B B B . Thus the assigned images do not repeat, and the procedure ends at B B B . Every image satisfies the required exchange property with respect to the unchanged target. If d = ∣ C ∖ B ∣ d=|C\setminus B| d = ∣ C ∖ B ∣ , at most 2 ( d + ( d − 1 ) + ⋯ + 1 ) = d ( d + 1 ) 2(d+(d-1)+\cdots+1)=d(d+1) 2 ( d + ( d − 1 ) + ⋯ + 1 ) = d ( d + 1 ) queries are used.
To evaluate only ϕ C , B ( e ) \phi_{C,B}(e) ϕ C , B ( e ) , the algorithm stops this fixed scan when e e e ’s image is assigned. The scan order does not depend on e e e . This consistency is what allows us to charge all possible insertions to distinct target elements.
Reference realizations and accepted records. For a reference realization y y y , let B y 0 B_y^0 B y 0 be its canonical maximum-weight basis. The continuation algorithm stores records ( e i , t i , C i ) (e_i,t_i,C_i) ( e i , t i , C i ) , one for each acceptance, where C i C_i C i is the candidate basis that justified that acceptance. Let H \mathcal{H} H be the ordered list of accepted records. Define Replay ( y , H , t ) \operatorname{Replay}(y,\mathcal{H},t) Replay ( y , H , t ) by starting with B = B y 0 B=B_y^0 B = B y 0 and replaying the accepted records with t i ≤ t t_i\le t t i ≤ t in order:
B ← B − ϕ C i , B ( e i ) + e i . B \leftarrow B-\phi_{C_i,B}(e_i)+e_i. B ← B − ϕ C i , B ( e i ) + e i .
Write B y ( t ) = Replay ( y , H , t ) B_y(t)=\operatorname{Replay}(y,\mathcal{H},t) B y ( t ) = Replay ( y , H , t ) . At an arrival, evaluate this basis using the records of earlier acceptances. The continuation always samples from the same law on the same matroid M M M . In particular, a fresh reference basis may contain a previously rejected label.
Every current basis contains the accepted set A t A_t A t . Indeed, the source and target bases at an insertion both contain the previous accepted set, which the exchange map fixes pointwise. A pair ( e , y ) (e,y) ( e , y ) is live at t t t if y e > 0 y_e>0 y e > 0 and e ∈ B y ( t ) ∖ A t e\in B_y(t)\setminus A_t e ∈ B y ( t ) ∖ A t . Only accepted labels are inserted, so an unaccepted label present in B y ( t ) B_y(t) B y ( t ) also belongs to B y 0 B_y^0 B y 0 . Once a live pair disappears it cannot become live again.
For a fixed accepted history, define
K e , t ( d y ) = 1 { ( e , y ) is live at t } μ ( d y ) , k e ( t ) = ∫ K e , t ( d y ) , w e ( t ) = ∫ y e K e , t ( d y ) . (20) \begin{aligned}
\mathcal{K}_{e,t}(dy) &= \mathbf{1}\{(e,y)\text{ is live at }t\}\mu(dy),\\
k_e(t) &= \int\mathcal{K}_{e,t}(dy), \qquad
w_e(t) = \int y_e\mathcal{K}_{e,t}(dy). \tag*{(20)}
\end{aligned} K e , t ( d y ) k e ( t ) = 1 {( e , y ) is live at t } μ ( d y ) , = ∫ K e , t ( d y ) , w e ( t ) = ∫ y e K e , t ( d y ) . (20)
These are analysis quantities. The algorithm tests liveness in sampled reference realizations and never evaluates these integrals. For every reference realization, the live labels form a subset of B y 0 B_y^0 B y 0 and of B y ( t ) ∖ A t B_y(t)\setminus A_t B y ( t ) ∖ A t . Consequently they are feasible in M / A t M/A_t M / A t , and ∑ e w e ( t ) ≤ F \sum_e w_e(t)\le F ∑ e w e ( t ) ≤ F .
The arrival rule
Assign independent uniform times in [ 0 , 1 ] [0,1] [ 0 , 1 ] to the residual labels. In the random-permutation model, this means drawing and sorting n n n independent uniform numbers, then attaching them in order to the remaining arrivals. The rule uses the current time and accepted records; unused future clocks and rejected observations do not enter its decisions.
Candidate and probe draws are independent. A candidate uses the observed e e e -coordinate, whereas each probe samples that coordinate afresh. After t 0 t_0 t 0 , the algorithm accepts every screened live candidate.
The reference screen is a valid probability. The function u ↦ min { 1 , q u } u\mapsto\min\{1,qu\} u ↦ min { 1 , q u } is q q q -Lipschitz, so each positive reference atom has mass at most q q q times the corresponding original atom. Multiplying the original atom by the screen probability and sampling the other coordinates gives the candidate-realization submeasure λ K e , t \lambda\mathcal{K}_{e,t} λ K e , t before the Poisson test.
Every acceptance is feasible because its candidate basis contains all earlier accepted labels. Evaluating a fresh reference realization requires a greedy scan and at most n n n exchange replays, hence O ( n 3 ) O(n^3) O ( n 3 ) queries. There is at most one candidate realization and an expected two probe realizations per arrival, giving O ( n 4 ) O(n^4) O ( n 4 ) expected queries. It remains to prove the reward guarantee.
The law of the accepted process
A missing label may still be on its way, or it may already have been rejected. We keep both possibilities when conditioning on accepted records. To state the calculation, attach to each acceptance a mark , such as the value and the reference realization used in the decision. The history records the labels, times, and marks of acceptances. Given this history, the intensity of an acceptance with mark in a set is its conditional probability per unit time. Algorithm 1 Virtual continuation: processing an arrival ( e , v , t ) (e,v,t) ( e , v , t )
Figure 1.
Fixed input: residual matroid M M M , parameter q q q , distributions D f , D f q D_f,D_f^q D f , D f q , and switching time t 0 = 1 − δ t_0=1-\delta t 0 = 1 − δ .
State: accepted set A A A and ordered record list H \mathcal{H} H , both initially empty on entering the continuation.
Output: accept or reject e e e , with an updated state on acceptance.
Screen the value. If v = 0 v=0 v = 0 , return reject . Draw B s c r ∼ Bernoulli ( D e q ( { v } ) / ( q D e ( { v } ) ) ) B_{\mathrm{scr}}\sim\operatorname{Bernoulli}(D_e^q(\{v\})/(qD_e(\{v\}))) B scr ∼ Bernoulli ( D e q ({ v }) / ( q D e ({ v }))) . If B s c r = 0 B_{\mathrm{scr}}=0 B scr = 0 , return reject .
Sample a candidate basis. Set y e = v y_e=v y e = v and draw y f ∼ D f q y_f\sim D_f^q y f ∼ D f q independently for all f ≠ e f\ne e f = e . Set C ← Replay ( y , H , t ) C\leftarrow\operatorname{Replay}(y,\mathcal{H},t) C ← Replay ( y , H , t ) . If e ∉ C ∖ A e\notin C\setminus A e ∈ / C ∖ A , return reject .
Test early acceptance. If t ≤ t 0 t\le t_0 t ≤ t 0 : (a) Draw Z ∼ Poisson ( 2 ) Z\sim\operatorname{Poisson}(2) Z ∼ Poisson ( 2 ) .
(b) For j = 1 , … , Z j=1,\ldots,Z j = 1 , … , Z :
(i) Draw U j U_j U j uniformly from [ 0 , 1 ) [0,1) [ 0 , 1 ) and set u j ← 2 q U j u_j\leftarrow2qU_j u j ← 2 q U j .
(ii) If u j < t u_j<t u j < t , draw a fresh full reference vector z ∼ ∏ f D f q z\sim\prod_f D_f^q z ∼ ∏ f D f q , set C ′ ← Replay ( z , H , u j ) C'\leftarrow\operatorname{Replay}(z,\mathcal{H},u_j) C ′ ← Replay ( z , H , u j ) , and let A ( u j ) = { e i : ( e i , t i , C i ) ∈ H , t i ≤ u j } A(u_j)=\{e_i:(e_i,t_i,C_i)\in\mathcal{H},\ t_i\le u_j\} A ( u j ) = { e i : ( e i , t i , C i ) ∈ H , t i ≤ u j } . If z e > 0 z_e>0 z e > 0 and e ∈ C ′ ∖ A ( u j ) e\in C'\setminus A(u_j) e ∈ C ′ ∖ A ( u j ) , return reject .
Accept and update. Set A ← A ∪ { e } A\leftarrow A\cup\{e\} A ← A ∪ { e } , append ( e , t , C ) (e,t,C) ( e , t , C ) to H \mathcal{H} H , earn reward v v v , and return accept .
Lemma 18 (Acceptance intensity). For each label e e e , let T e T_e T e be a uniform arrival time, X e X_e X e its actual value, and R e R_e R e a private random tape. These triples are independent across labels, and their coordinates are independent. Suppose the decision at an arrival uses only the accepted marked history. For a frozen prefix h h h , let Ψ e ( h , t , X e , R e ) \Psi_e(h,t,X_e,R_e) Ψ e ( h , t , X e , R e ) be either rejection or an acceptance mark, and let ν e , h , t \nu_{e,h,t} ν e , h , t be its acceptance subprobability kernel under the unconditional law of ( X e , R e ) (X_e,R_e) ( X e , R e ) .
Along a prescribed accepted path, write h t h_t h t for the prefix before t t t and, for a label not yet accepted, put
S e ( t ) = 1 − ∫ 0 t ν e , h u , u ( M ) d u , S_e(t)=1-\int_0^t\nu_{e,h_u,u}(\mathcal{M})\,du, S e ( t ) = 1 − ∫ 0 t ν e , h u , u ( M ) d u , where M \mathcal{M} M is the acceptance-mark space. Wherever S e > 0 S_e>0 S e > 0 , the marked acceptance intensity, with respect to the history of accepted marks, is ν e , h t , t / S e ( t ) \nu_{e,h_t,t}/S_e(t) ν e , h t , t / S e ( t ) .
Proof. Fix a marked accepted path through time t t t . A label absent from this path satisfies precisely
{ T e > t } ∪ { T e ≤ t , Ψ e ( h T e , T e , X e , R e ) is rejection } . \{T_e>t\}\cup\{T_e\le t,\ \Psi_e(h_{T_e},T_e,X_e,R_e)\text{ is rejection}\}. { T e > t } ∪ { T e ≤ t , Ψ e ( h T e , T e , X e , R e ) is rejection } .
Its probability is S e ( t ) S_e(t) S e ( t ) . The sole arrival time is integrated once; no independence of decisions at counterfactual times is asserted. A label accepted at time t i t_i t i with mark m i m_i m i contributes the event density ν e i , h t i , t i ( d m i ) d t i \nu_{e_i,h_{t_i},t_i}(dm_i)\,dt_i ν e i , h t i , t i ( d m i ) d t i . Once the path is fixed, these are constraints on independent per-label triples. Scanning actual arrivals in order shows that the constraints are also sufficient to realize that path.
In the process with the claimed intensities, − d log S e ( u ) = ν e , h u , u ( M ) d u / S e ( u ) -d\log S_e(u)=\nu_{e,h_u,u}(\mathcal{M})\,du/S_e(u) − d log S e ( u ) = ν e , h u , u ( M ) d u / S e ( u ) before e e e is accepted. The survival factor is S e ( t ) S_e(t) S e ( t ) for an absent label. For an accepted label it is S e ( t i ) S_e(t_i) S e ( t i ) , which cancels the denominator in its event intensity. Thus the two processes have the same marked-path densities. There are at most n n n events, so these densities determine their laws. □ \square □
For analysis, include the credited value and the complete candidate realization in each acceptance mark. The other coordinates of that realization come from the accepting label’s private tape; they are not other labels’ actual values. Thus the preceding factorization still applies. Write F t \mathcal{F}_t F t for the filtration generated by the accepted marks, that is, the information they reveal through time t t t . The implemented state only needs the recorded bases. All kernels below use the prefix before a decision, or equivalently their left limits at an event time.
Set
Λ e ( t ) = λ ∫ 0 t k e ( u ) d u . \Lambda_e(t)=\lambda\int_0^t k_e(u)\,\mathrm{d}u. Λ e ( t ) = λ ∫ 0 t k e ( u ) d u .
Since 2 q ≥ 1 2q\ge1 2 q ≥ 1 , a raw early probe finds e e e live with probability Λ e ( t ) / 2 \Lambda_e(t)/2 Λ e ( t ) /2 . The Poisson test passes with probability e − Λ e ( t ) e^{-\Lambda_e(t)} e − Λ e ( t ) . Hence the actual acceptance kernel on candidate realizations is λ e − Λ e ( t ) K e , t \lambda e^{-\Lambda_e(t)}K_{e,t} λ e − Λ e ( t ) K e , t in the early phase, and λ K e , t \lambda K_{e,t} λ K e , t in the late phase. Mapping each candidate realization to its acceptance mark gives the kernel in Lemma 18. For labels not yet accepted, that lemma gives
S e ( t ) = { e − Λ e ( t ) , t ≤ t 0 , e − Λ e ( t 0 ) − λ ∫ t 0 t k e ( u ) d u , t > t 0 . S_e(t)=
\begin{cases}
e^{-\Lambda_e(t)}, & t\le t_0,\\
e^{-\Lambda_e(t_0)}-\lambda\int_{t_0}^t k_e(u)\,\mathrm{d}u, & t>t_0.
\end{cases} S e ( t ) = { e − Λ e ( t ) , e − Λ e ( t 0 ) − λ ∫ t 0 t k e ( u ) d u , t ≤ t 0 , t > t 0 .
Thus the early marked acceptance intensity is exactly λ K e , t \lambda K_{e,t} λ K e , t . In the late phase it is r e ( t ) K e , t r_e(t)K_{e,t} r e ( t ) K e , t , where
r e ( t ) = λ S e ( t ) , λ ( 1 + Λ e ( t 0 ) ) ≤ r e ( t ) ≤ λ ω . (21) r_e(t)=\frac{\lambda}{S_e(t)},\qquad
\lambda(1+\Lambda_e(t_0))\le r_e(t)\le\frac{\lambda}{\omega}. \tag*{(21)} r e ( t ) = S e ( t ) λ , λ ( 1 + Λ e ( t 0 )) ≤ r e ( t ) ≤ ω λ . (21)
The lower bound uses e x ≥ 1 + x e^x\ge1+x e x ≥ 1 + x . For the upper bound, use k e ≤ 1 k_e\le1 k e ≤ 1 and Λ e ( t 0 ) ≤ λ t 0 \Lambda_e(t_0)\le\lambda t_0 Λ e ( t 0 ) ≤ λ t 0 to obtain S e ( t ) ≥ α − λ δ = ω > 0 S_e(t)\ge\alpha-\lambda\delta=\omega>0 S e ( t ) ≥ α − λ δ = ω > 0 . After a label is accepted its kernels and rates are set to zero. These rates are only for the proof: the late rule is simply to accept every screened live candidate.
Persistence and the overlap gain
Lemma 19 (Persistence). If the marked acceptance intensities are r e ( t ) K e , t r_e(t)K_{e,t} r e ( t ) K e , t and r e ( t ) ≤ R r_e(t)\le R r e ( t ) ≤ R throughout an interval, every live pair has conditional death rate at most R R R , where the death rate is the instantaneous conditional rate at which the pair ceases to be live. In particular, for u ≤ v u\le v u ≤ v in that interval,
E [ w e ( v ) ∣ F u ] ≥ e − R ( v − u ) w e ( u ) . \mathbb{E}[w_e(v)\mid\mathcal{F}_u]\ge e^{-R(v-u)}w_e(u). E [ w e ( v ) ∣ F u ] ≥ e − R ( v − u ) w e ( u ) . The same inequality holds for the mass of live pairs with y e > z y_e>z y e > z .
Proof. Fix a live target pair and its current basis B B B . In any source realization with current basis C C C , injectivity of ϕ C , B \phi_{C,B} ϕ C , B allows at most one live source label to remove the target element. If the target label itself is live in the source, the map fixes it and no other source label can remove it. Its own acceptance is included in this bound. The killing intensity from that source realization is therefore at most R μ ( d y ) R\mu(\mathrm{d}y) R μ ( d y ) . Integration over source realizations gives the death-rate bound. Now fix a target realization live at u u u . Its conditional survival probability p ( v ) p(v) p ( v ) has p ( u ) = 1 p(u)=1 p ( u ) = 1 and p ′ ( v ) ≥ − R p ( v ) p'(v)\ge-Rp(v) p ′ ( v ) ≥ − R p ( v ) almost everywhere, since disappearance is irreversible. Thus p ( v ) ≥ e − R ( v − u ) p(v)\ge e^{-R(v-u)} p ( v ) ≥ e − R ( v − u ) . Integrate over live targets at u u u with weight y e y_e y e or 1 { y e > z } \mathbf{1}\{y_e>z\} 1 { y e > z } to obtain the claim.
This proof explains why the early random rejections act on whole source realizations. A bound on the total acceptance rate of each label alone would allow several labels to concentrate their mass on bases whose exchanges all evict the same target.
In the early phase the instantaneous reward rate is λ ∑ e w e ( t ) \lambda\sum_e w_e(t) λ ∑ e w e ( t ) . Persistence with R = λ R=\lambda R = λ and ∑ e w e ( 0 ) = F \sum_e w_e(0)=F ∑ e w e ( 0 ) = F bounds its expectation below by λ e − λ t F \lambda e^{-\lambda t}F λ e − λ t F . Integration gives expected early reward at least ( 1 − α ) F (1-\alpha)F ( 1 − α ) F , and at the switching time
E ∑ e w e ( t 0 ) ≥ α F . (22) \mathbb{E}\sum_e w_e(t_0)\ge\alpha F. \tag*{(22)} E e ∑ w e ( t 0 ) ≥ α F . (22)
We also claim
E ∑ e w e ( t 0 ) Λ e ( t 0 ) ≥ α ( 1 − α ) Q . (23) \mathbb{E}\sum_e w_e(t_0)\Lambda_e(t_0) \ge\alpha(1-\alpha)Q. \tag*{(23)} E e ∑ w e ( t 0 ) Λ e ( t 0 ) ≥ α ( 1 − α ) Q . (23)
To prove this, let u e ( t , z ) = ∫ 1 { y e > z } K e , t ( d y ) u_e(t,z)=\int\mathbf{1}\{y_e>z\}\mathcal{K}_{e,t}(\mathrm{d}y) u e ( t , z ) = ∫ 1 { y e > z } K e , t ( d y ) . Since u e ( t , z ) ≤ k e ( t ) u_e(t,z)\le k_e(t) u e ( t , z ) ≤ k e ( t ) ,
w e ( t ) k e ( t ) ≥ ∫ 0 ∞ u e ( t , z ) 2 d z . w_e(t)k_e(t)\ge\int_0^\infty u_e(t,z)^2\,\mathrm{d}z. w e ( t ) k e ( t ) ≥ ∫ 0 ∞ u e ( t , z ) 2 d z .
Persistence gives E u e ( t , z ) ≥ e − λ t x e ( z ) \mathbb{E}u_e(t,z)\ge e^{-\lambda t}x_e(z) E u e ( t , z ) ≥ e − λ t x e ( z ) . Conditional persistence followed by Jensen’s inequality therefore yields
E ∑ e w e ( t 0 ) Λ e ( t 0 ) ≥ λ ∫ 0 t 0 e − λ ( t 0 − t ) E ∑ e w e ( t ) k e ( t ) d t ≥ λ ∫ 0 t 0 e − λ ( t 0 − t ) e − 2 λ t Q d t = α ( 1 − α ) Q . \begin{aligned}
\mathbb{E}\sum_e w_e(t_0)\Lambda_e(t_0)\ge\lambda\int_0^{t_0}e^{-\lambda(t_0-t)}\mathbb{E}\sum_e w_e(t)k_e(t)\,\mathrm{d}t \\
&\ge\lambda\int_0^{t_0}e^{-\lambda(t_0-t)}e^{-2\lambda t}Q\,\mathrm{d}t=\alpha(1-\alpha)Q.
\end{aligned} E e ∑ w e ( t 0 ) Λ e ( t 0 ) ≥ λ ∫ 0 t 0 e − λ ( t 0 − t ) E e ∑ w e ( t ) k e ( t ) d t ≥ λ ∫ 0 t 0 e − λ ( t 0 − t ) e − 2 λ t Q d t = α ( 1 − α ) Q .
Proof of Proposition 16. By (21) , late persistence holds with R = λ / ω R=\lambda/\omega R = λ / ω , while the credit intensity is at least λ ∑ e ( 1 + Λ e ( t 0 ) ) w e ( t ) \lambda\sum_e(1+\Lambda_e(t_0))w_e(t) λ ∑ e ( 1 + Λ e ( t 0 )) w e ( t ) . Conditional on F t 0 \mathcal{F}_{t_0} F t 0 , the late reward is consequently at least
ω ( 1 − e − λ δ / ω ) ∑ e ( 1 + Λ e ( t 0 ) ) w e ( t 0 ) . \omega(1-e^{-\lambda\delta/\omega})\sum_e(1+\Lambda_e(t_0))w_e(t_0). ω ( 1 − e − λ δ / ω ) e ∑ ( 1 + Λ e ( t 0 )) w e ( t 0 ) .
Add the early reward and use (22) and (23) . The result is
E [ A L G ] ≥ ( 1 − α ) F + α ω ( 1 − e − λ δ / ω ) ( F + ( 1 − α ) Q ) , \mathbb{E}[\mathrm{ALG}]\ge(1-\alpha)F+\alpha\omega(1-e^{-\lambda\delta/\omega})(F+(1-\alpha)Q), E [ ALG ] ≥ ( 1 − α ) F + α ω ( 1 − e − λ δ / ω ) ( F + ( 1 − α ) Q ) ,
which is exactly (19) . Feasibility and the query bound were established above.
Estimating a reference instance
All quantities used by the search have a rank-layer representation. This permits a common estimator even when a large value occurs with very small probability. Sample the height of a layer in proportion to the probability that it contains an active element, then sample that layer conditioned on being nonempty. The observations are bounded in units of the expected maximum, regardless of the largest support value.
Throughout the implementation let N N N denote the original ground-set size. Fix a residual matroid on n ≤ N n\le N n ≤ N nonloops and a reference q ∈ J q\in J q ∈ J . Write
V q = E max e Y e q , C q = D q − H q . V_q=\mathbb{E}\max_e Y_e^q,\qquad C_q=D_q-H_q. V q = E e max Y e q , C q = D q − H q .
We stop at states with zero benchmark, so V q > 0 V_q>0 V q > 0 below.
Sampling a nonempty layer
Sort the distinct positive values appearing in the residual support lists as 0 = v 0 < v 1 < ⋯ < v s 0=v_0<v_1<\cdots<v_s 0 = v 0 < v 1 < ⋯ < v s . Write Δ j = v j − v j − 1 \Delta_j=v_j-v_{j-1} Δ j = v j − v j − 1 and let p e , j p_{e,j} p e , j be the reference tail probability on the interval ( v j − 1 , v j ) (v_{j-1},v_j) ( v j − 1 , v j ) . In a fixed label order, form the joint weights
w j , b = Δ j p b , j ∏ i < b ( 1 − p i , j ) . w_{j,b}=\Delta_jp_{b,j}\prod_{i<b}(1-p_{i,j}). w j , b = Δ j p b , j i < b ∏ ( 1 − p i , j ) .
Their sum is
∑ j , b w j , b = ∑ j Δ j ( 1 − ∏ e ( 1 − p e , j ) ) = V q . \sum_{j,b} w_{j,b}=\sum_j \Delta_j\left(1-\prod_e(1-p_{e,j})\right)=V_q. j , b ∑ w j , b = j ∑ Δ j ( 1 − e ∏ ( 1 − p e , j ) ) = V q .
Draw ( j , b ) (j,b) ( j , b ) with probability w j , b / V q w_{j,b}/V_q w j , b / V q . Set the indicators before b b b to zero and the indicator of b b b to one; draw each later indicator e e e independently with probability p e , j p_{e,j} p e , j . Denote the resulting nonempty active set by R R R . If R j R_j R j is an unconditioned product layer, then
Pr ( ( j , R ) ) = Δ j V q Pr ( R j = R ) , R ≠ ∅ . (24) \Pr((j,R))=\frac{\Delta_j}{V_q}\Pr(R_j=R),\qquad R\ne\varnothing. \tag*{(24)} Pr (( j , R )) = V q Δ j Pr ( R j = R ) , R = ∅ . (24)
Indeed, R R R has a unique first active label. Even when Pr ( R j ≠ ∅ ) \Pr(R_j\ne\varnothing) Pr ( R j = ∅ ) is small, this construction uses one categorical draw and at most n n n Bernoulli draws.
Let C ( R ) C(R) C ( R ) be the coloops of M ∣ R M|_R M ∣ R . From this one layer form
Z F = V q r ( R ) , Z D = V q ∣ C ( R ) ∣ , Z_F=V_q r(R),\qquad Z_D=V_q|C(R)|, Z F = V q r ( R ) , Z D = V q ∣ C ( R ) ∣ ,
Z C = V q ∑ e ∈ C ( R ) ( 1 − p e , j ) , Z e = V q 1 { e ∈ cl ( R ∖ e ) } . Z_C=V_q\sum_{e\in C(R)}(1-p_{e,j}),\qquad Z_e=V_q1\{e\in\operatorname{cl}(R\setminus e)\}. Z C = V q e ∈ C ( R ) ∑ ( 1 − p e , j ) , Z e = V q 1 { e ∈ cl ( R ∖ e )} .
Lemma 20 (Common layer estimates). The expectations of Z F , Z D , Z C , Z e Z_F,Z_D,Z_C,Z_e Z F , Z D , Z C , Z e are F q , D q , C q , m e g F_q,D_q,C_q,m_e^g F q , D q , C q , m e g , respectively. On every outcome,
V q ≤ Z F ≤ N V q , 0 ≤ Z C ≤ Z D ≤ Z F , 0 ≤ Z e ≤ V q . V_q\le Z_F\le NV_q,\qquad0\le Z_C\le Z_D\le Z_F,\qquad0\le Z_e\le V_q. V q ≤ Z F ≤ N V q , 0 ≤ Z C ≤ Z D ≤ Z F , 0 ≤ Z e ≤ V q . All observations can be computed with O ( n log ( n + 1 ) ) O(n\log(n+1)) O ( n log ( n + 1 )) independence queries.
Proof. The rank layer formula gives the first expectation. An active element is a coloop of the active restriction exactly when the other active elements do not span it. Thus the unconditioned expectations of the next two layer statistics are ∑ e p e ρ e \sum_e p_e\rho_e ∑ e p e ρ e and ∑ e p e ( 1 − p e ) ρ e \sum_e p_e(1-p_e)\rho_e ∑ e p e ( 1 − p e ) ρ e , where ρ e = Pr ( e ∉ cl ( R j ∖ e ) ) \rho_e=\Pr(e\notin\operatorname{cl}(R_j\setminus e)) ρ e = Pr ( e ∈ / cl ( R j ∖ e )) . Their height integrals are D q D_q D q and D q − H q D_q-H_q D q − H q . Similarly,
m e g = ∫ 0 ∞ Pr ( e ∈ cl ( R z ∖ e ) ) d z . m_e^g=\int_0^\infty\Pr(e\in\operatorname{cl}(R_z\setminus e))\,\mathrm{d}z. m e g = ∫ 0 ∞ Pr ( e ∈ cl ( R z ∖ e )) d z .
All integrands vanish on the empty layer because the residual matroid has no loops. Equation (24) therefore proves the asserted expectations. The bounds follow from 1 ≤ r ( R ) ≤ n 1\le r(R)\le n 1 ≤ r ( R ) ≤ n and ∣ C ( R ) ∣ ≤ r ( R ) |C(R)|\le r(R) ∣ C ( R ) ∣ ≤ r ( R ) .
For the query bound, greedily find a basis B B B of R R R and initialize U = B U=B U = B . For f ∈ R ∖ B f\in R\setminus B f ∈ R ∖ B , its fundamental circuit C f C_f C f satisfies
( B ∖ S ) + f is independent ⟺ C f ∩ S ≠ ∅ ( S ⊆ B ) . (B\setminus S)+f\text{ is independent}\quad\Longleftrightarrow\quad C_f\cap S\ne\varnothing\qquad(S\subseteq B). ( B ∖ S ) + f is independent ⟺ C f ∩ S = ∅ ( S ⊆ B ) .
Binary subdivision finds a member of C f ∩ U C_f\cap U C f ∩ U , when one exists, using O ( log ( n + 1 ) ) O(\log(n+1)) O ( log ( n + 1 )) queries. Remove each such member from U U U and continue until the intersection is empty. Every basis element is removed at most once, and each nonbasis element contributes one final unsuccessful test. At termination U = C ( R ) U=C(R) U = C ( R ) . For e ∈ R e\in R e ∈ R , the closure indicator is 1 { e ∉ U } 1\{e\notin U\} 1 { e ∈ / U } ; for e ∉ R e\notin R e ∈ / R , one query on B + e B+e B + e supplies it. This proves the bound. □ \square □
A single accuracy guarantee
Let K K K be the search budget in (28) . Set
H 0 = ⌈ log 2 2 N K ( N + 3 ) ρ ⌉ , m = ⌈ 2 N H 0 ε 2 ⌉ . H_0=\left\lceil\log_2\frac{2NK(N+3)}{\rho}\right\rceil,\qquad m=\left\lceil\frac{2NH_0}{\varepsilon^2}\right\rceil. H 0 = ⌈ log 2 ρ 2 N K ( N + 3 ) ⌉ , m = ⌈ ε 2 2 N H 0 ⌉ .
At each evaluated parameter draw exactly m m m fresh layers and average the observations. Denote the resulting estimates by F ^ , D ^ , C ^ , m ^ e \widehat F,\widehat D,\widehat C,\widehat m_e F , D , C , m e .
Lemma 21 (Simultaneous accuracy). Conditionally at any residual state, with probability at least 1 − ρ / N 1-\rho/N 1 − ρ / N , every one of its at most K K K adaptively requested batches satisfies
∣ F ^ − F q ∣ ≤ ε ( F q + V q ) , ∣ D ^ − D q ∣ ≤ ε ( D q + V q ) , ∣ C ^ − C q ∣ ≤ ε ( C q + V q ) , ∣ m ^ e − m e q ∣ ≤ ε m e q + ε V q / N ( e ∈ E ′ ) . \begin{aligned}
|\widehat{F}-F_q| &\le\varepsilon(F_q+V_q),\\
|\widehat{D}-D_q| &\le\varepsilon(D_q+V_q),\\
|\widehat{C}-C_q| &\le\varepsilon(C_q+V_q),\\
|\widehat{m}_e-m_e^q| &\le\varepsilon m_e^q+\varepsilon V_q/N \qquad(e\in E').
\end{aligned} ∣ F − F q ∣ ∣ D − D q ∣ ∣ C − C q ∣ ∣ m e − m e q ∣ ≤ ε ( F q + V q ) , ≤ ε ( D q + V q ) , ≤ ε ( C q + V q ) , ≤ ε m e q + ε V q / N ( e ∈ E ′ ) . The same bounds hold for the saved batch at an adaptively selected evaluated parameter.
Proof. For independent W i ∈ [ 0 , 1 ] W_i\in[0,1] W i ∈ [ 0 , 1 ] of mean μ \mu μ , Bernstein’s inequality and Var ( W i ) ≤ μ \operatorname{Var}(W_i)\le\mu Var ( W i ) ≤ μ imply
Pr ( ∣ W ‾ − μ ∣ > γ μ + t ) ≤ 2 exp ( − m ( γ μ + t ) 2 2 μ + ( 2 / 3 ) ( γ μ + t ) ) ≤ 2 e − m γ t / 2 , 0 < γ ≤ 1. \Pr\left(|\overline{W}-\mu|>\gamma\mu+t\right)\le2\exp\left(-\frac{m(\gamma\mu+t)^2}{2\mu+(2/3)(\gamma\mu+t)}\right)\le2e^{-m\gamma t/2},\qquad0<\gamma\le1. Pr ( ∣ W − μ ∣ > γ μ + t ) ≤ 2 exp ( − 2 μ + ( 2/3 ) ( γ μ + t ) m ( γ μ + t ) 2 ) ≤ 2 e − mγ t /2 , 0 < γ ≤ 1.
The last inequality follows by expanding the two sides of ( γ μ + t ) 2 ≥ ( γ t / 2 ) [ 2 μ + ( 2 / 3 ) ( γ μ + t ) ] (\gamma\mu+t)^2\ge(\gamma t/2)[2\mu+(2/3)(\gamma\mu+t)] ( γ μ + t ) 2 ≥ ( γ t /2 ) [ 2 μ + ( 2/3 ) ( γ μ + t )] . Normalize the first three observations by N V q NV_q N V q and each Z e Z_e Z e by V q V_q V q , and take γ = ε \gamma=\varepsilon γ = ε , t = ε / N t=\varepsilon/N t = ε / N . Each statistic fails with probability at most ρ / [ N K ( N + 3 ) ] \rho/[NK(N+3)] ρ / [ N K ( N + 3 )] . A conditional union bound over the at most N + 3 N+3 N + 3 statistics and K K K parameter evaluations proves the claim. Indeed, conditional on the previous evaluations, the next parameter is already fixed. Taking the intersection of the accuracy events also covers the batch eventually returned by the search. □ \square □
On the accurate event, the upper estimates
m ‾ e = m ^ e + ε V q / N 1 − ε (25) \overline{m}_e=\frac{\widehat{m}_e+\varepsilon V_q/N}{1-\varepsilon} \tag*{(25)} m e = 1 − ε m e + ε V q / N (25)
satisfy
m e q ≤ m ‾ e ≤ 1 + ε 1 − ε m e q + 2 ε V q N ( 1 − ε ) . m_e^q\le\overline{m}_e\le\frac{1+\varepsilon}{1-\varepsilon}m_e^q+\frac{2\varepsilon V_q}{N(1-\varepsilon)}. m e q ≤ m e ≤ 1 − ε 1 + ε m e q + N ( 1 − ε ) 2 ε V q .
For the threshold p e = a ( q ) m ‾ e p_e=a(q)\overline{m}_e p e = a ( q ) m e , put b = a ( q ) ( 1 + ε ) / ( 1 − ε ) b=a(q)(1+\varepsilon)/(1-\varepsilon) b = a ( q ) ( 1 + ε ) / ( 1 − ε ) . Our parameter ranges give b < 1 b<1 b < 1 , 0 ≤ b − a ( q ) < 2 ε 0\le b-a(q)<2\varepsilon 0 ≤ b − a ( q ) < 2 ε , and
p e ≥ a ( q ) m e q , ∑ e ( p e − b m e q ) + < 2 ε F q . (26) p_e\ge a(q)m_e^q,\qquad\sum_e(p_e-bm_e^q)^+<2\varepsilon F_q. \tag*{(26)} p e ≥ a ( q ) m e q , e ∑ ( p e − b m e q ) + < 2 ε F q . (26)
Thus the same batch supplies the search statistics, the stability test, and all possible next-arrival thresholds.
Choosing the reference parameter
A small additive error in the reference potential could accumulate over many arrivals. We avoid this loss by moving the reference only when the samples certify the sign of a one-sided derivative. At the returned point we need just two inequalities relating the deletion surplus to the stable surplus. Write
g ( q ) = a ( q ) F q , d ∗ ( q ) = θ q 1 − θ q . g(q)=a(q)F_q,\qquad d_*(q)=\frac{\theta q}{1-\theta q}. g ( q ) = a ( q ) F q , d ∗ ( q ) = 1 − θ q θ q .
Lemma 9 gives concavity of g g g . Since a ′ = − θ a'=-\theta a ′ = − θ , Lemma 8 gives
a F q q ( C q F q − d ∗ ( q ) ) ≤ g + ′ ( q ) ≤ g − ′ ( q ) ≤ a F q q ( D q F q − d ∗ ( q ) ) . (27) \frac{aF_q}{q}\left(\frac{C_q}{F_q}-d_*(q)\right)\le g'_+(q)\le g'_-(q)\le\frac{aF_q}{q}\left(\frac{D_q}{F_q}-d_*(q)\right). \tag*{(27)} q a F q ( F q C q − d ∗ ( q ) ) ≤ g + ′ ( q ) ≤ g − ′ ( q ) ≤ q a F q ( F q D q − d ∗ ( q ) ) . (27)
At an evaluated parameter call the batch positive if C ^ / F ^ > d ∗ + 10 ε \widehat{C}/\widehat{F} > d_{*}+10\varepsilon C / F > d ∗ + 10 ε , and negative if D ^ / F ^ < d ∗ − 10 ε \widehat{D}/\widehat{F} < d_{*}-10\varepsilon D / F < d ∗ − 10 ε . These tests are disjoint, since 0 ≤ C ^ ≤ D ^ ≤ F ^ 0 \le\widehat{C} \le\widehat{D} \le\widehat{F} 0 ≤ C ≤ D ≤ F on every outcome. The denominator is positive because F ^ ≥ V q \widehat{F} \ge V_q F ≥ V q .
Initialize the search at the inherited q i n q^{\mathrm{in}} q in , where ∣ q i n − 1 ∣ < 3 δ |q^{\mathrm{in}}-1| < 3\delta ∣ q in − 1∣ < 3 δ . Evaluate this parameter. If neither test holds, return it and its batch. If its batch is positive, bisect [ q i n , 1 + 4 δ ] [q^{\mathrm{in}},1+4\delta] [ q in , 1 + 4 δ ] : a positive midpoint replaces the left endpoint and its saved batch, and any other midpoint replaces the right endpoint. Return the saved left endpoint. If its batch is negative, use the symmetric procedure on [ 1 − 4 δ , q i n ] [1-4\delta,q^{\mathrm{in}}] [ 1 − 4 δ , q in ] and return the saved right endpoint. In either branch perform K − 1 K-1 K − 1 midpoint evaluations, where
K = 1 + ⌈ log 2 max { 1 , 32 δ N 2 ε } ⌉ . (28) K = 1 + \left\lceil\log_{2}\max\left\{1,\frac{32\delta N^{2}}{\varepsilon}\right\}\right\rceil. \tag*{(28)} K = 1 + ⌈ log 2 max { 1 , ε 32 δ N 2 } ⌉ . (28)
The terminal interval has length at most ε / ( 4 N 2 ) < δ \varepsilon/(4N^{2}) < \delta ε / ( 4 N 2 ) < δ .
Lemma 22 (Reference selection). On the simultaneous accurate event, the returned reference satisfies
a ( q ) F q ≥ a ( q i n ) F q i n . a(q)F_q \ge a(q^{\mathrm{in}})F_{q^{\mathrm{in}}}. a ( q ) F q ≥ a ( q in ) F q in . If ∣ q − 1 ∣ < 3 δ |q-1| < 3\delta ∣ q − 1∣ < 3 δ , then
d ∗ ( q ) − 20 ε ≤ D q / F q ≤ d ∗ ( q ) + H q / F q + 20 ε . (29) d_{*}(q)-20\varepsilon\le D_q/F_q \le d_{*}(q)+H_q/F_q+20\varepsilon. \tag*{(29)} d ∗ ( q ) − 20 ε ≤ D q / F q ≤ d ∗ ( q ) + H q / F q + 20 ε . (29) Its saved batch satisfies all bounds of Lemma 21 .
Proof. Accuracy and C q , D q ≤ F q C_q,D_q \le F_q C q , D q ≤ F q imply that both estimated ratios differ from their true ratios by at most 4 ε / ( 1 − 2 ε ) ≤ 5 ε 4\varepsilon/(1-2\varepsilon) \le5\varepsilon 4 ε / ( 1 − 2 ε ) ≤ 5 ε . Thus a positive batch certifies g + ′ > 0 g^{\prime}_{+} > 0 g + ′ > 0 , and a negative batch certifies g − ′ < 0 g^{\prime}_{-} < 0 g − ′ < 0 . By concavity, a parameter with a positive batch has larger potential than every point to its left, and a parameter with a negative batch has larger potential than every point to its right. Every update to the saved endpoint therefore increases the potential.
The two endpoints of the final interval may have different test outcomes. To transfer a failed test across that interval, we bound how fast its true ratio can change. Put q − = 1 − 4 δ ≥ 1 / 2 q_{-}=1-4\delta\ge1/2 q − = 1 − 4 δ ≥ 1/2 and a − = min J a ≥ 1 / 2 a_{-}=\min_{J}a \ge1/2 a − = min J a ≥ 1/2 . Coupling the product layers at two parameters gives
∣ D q − D s ∣ ≤ n 2 F 1 ∣ q − s ∣ , ∣ H q − H s ∣ ≤ 2 n 2 F 1 ∣ q − s ∣ , ∣ C q − C s ∣ ≤ 3 n 2 F 1 ∣ q − s ∣ . |D_q-D_s| \le n^{2}F_1|q-s|,\qquad|H_q-H_s| \le2n^{2}F_1|q-s|,\qquad|C_q-C_s| \le3n^{2}F_1|q-s|. ∣ D q − D s ∣ ≤ n 2 F 1 ∣ q − s ∣ , ∣ H q − H s ∣ ≤ 2 n 2 F 1 ∣ q − s ∣ , ∣ C q − C s ∣ ≤ 3 n 2 F 1 ∣ q − s ∣.
For the first bound, a changed layer has probability at most ∣ q − s ∣ ∑ e Pr ( X e > z ) |q-s|\sum_{e}\Pr(X_e>z) ∣ q − s ∣ ∑ e Pr ( X e > z ) and its number of coloops is at most n n n ; integrate and use ∑ e E X e ≤ n F 1 \sum_{e}\mathbb{E}X_e \le nF_1 ∑ e E X e ≤ n F 1 . For H H H , differences of the factors p e 2 p_e^2 p e 2 contribute at most twice the sum of probability changes, while the nonspanning factors contribute at most n − 1 n-1 n − 1 times that sum. This proves the other two bounds. Also F q ≥ q − F 1 F_q \ge q_{-}F_1 F q ≥ q − F 1 and, by concavity, ∣ F q − F s ∣ ≤ ( F 1 / q − ) ∣ q − s ∣ |F_q-F_s| \le(F_1/q_{-})|q-s| ∣ F q − F s ∣ ≤ ( F 1 / q − ) ∣ q − s ∣ . Since d ∗ ′ = θ / a 2 d_{*}^{\prime}=\theta/a^2 d ∗ ′ = θ / a 2 , both C q / F q − d ∗ ( q ) C_q/F_q-d_{*}(q) C q / F q − d ∗ ( q ) and D q / F q − d ∗ ( q ) D_q/F_q-d_{*}(q) D q / F q − d ∗ ( q ) are Lipschitz with constant at most
( 3 q − + 1 q − 2 + θ a − 2 ) n 2 ≤ 14 n 2 < 16 n 2 . \left(\frac{3}{q_{-}}+\frac{1}{q_{-}^{2}}+\frac{\theta}{a_{-}^{2}}\right)n^{2} \le14n^{2}<16n^{2}. ( q − 3 + q − 2 1 + a − 2 θ ) n 2 ≤ 14 n 2 < 16 n 2 .
At an initial stopping point, the failed tests give the desired two inequalities with 15 ε 15\varepsilon 15 ε in place of 20 ε 20\varepsilon 20 ε . In the positive branch the saved left endpoint is certified positive. If the final right endpoint is interior, it was assigned by a failed positive test, so its true normalized C C C ratio is at most 15 ε 15\varepsilon 15 ε above d ∗ d_{*} d ∗ . Transfer this estimate across the final interval, losing at most 4 ε 4\varepsilon 4 ε , to obtain the upper inequality at the returned point. The positive certificate gives the lower one. The negative branch is symmetric. If the opposite endpoint was never updated, the returned point is within ε / ( 4 N 2 ) < δ \varepsilon/(4N^{2})<\delta ε / ( 4 N 2 ) < δ of an endpoint of J J J , and hence lies in the boundary region ∣ q − 1 ∣ ≥ 3 δ |q-1|\ge3\delta ∣ q − 1∣ ≥ 3 δ . This proves the assertion in every case.
All ratio tests can be performed by cross multiplication. The estimates share the factor V q / m V_q/m V q / m , and every new parameter is a midpoint of two old endpoints. Appendix § 14 uses these facts to bound the bit complexity of the search.
The online algorithm and its guarantee
The selected reference serves two purposes. Its location and its stable surplus determine whether the virtual continuation can earn the entire remaining potential. If the algorithm instead takes a threshold step, the same reference supplies a price for each possible next arrival.
Conditions on the parameters
The three inequalities below correspond to the two ways of entering the continuation and the single threshold step. Put
h − = η − 10 ε , h + = η + 10 ε , b = b ( q ) = a ( q ) 1 + ε 1 − ε , z ∗ ( q ) = h − 2 1 − d ∗ ( q ) + 20 ε + h − , L ∗ ( q ) = 1 − b + b b + s ( d ∗ ( q ) + 20 ε − ( 1 − b ) − b e − s ) . (30) \begin{aligned}
h_- &= \eta- 10\varepsilon,\qquad h_+ = \eta+ 10\varepsilon,\qquad b = b(q) = a(q)\frac{1+\varepsilon}{1-\varepsilon},\\
z_*(q) &= \frac{h_-^2}{1-d_*(q)+20\varepsilon+h_-},\\
L_*(q) &= 1-b+\frac{b}{b+s}\left(d_*(q)+20\varepsilon-(1-b)-be^{-s}\right). \tag*{(30)}
\end{aligned} h − z ∗ ( q ) L ∗ ( q ) = η − 10 ε , h + = η + 10 ε , b = b ( q ) = a ( q ) 1 − ε 1 + ε , = 1 − d ∗ ( q ) + 20 ε + h − h − 2 , = 1 − b + b + s b ( d ∗ ( q ) + 20 ε − ( 1 − b ) − b e − s ) . (30)
The elementary restrictions (5) make the denominator of z ∗ z_* z ∗ positive and give 0 < b < 1 0 < b < 1 0 < b < 1 . In addition to ω > 0 \omega> 0 ω > 0 and q ( b + s ) > 1 q(b+s) > 1 q ( b + s ) > 1 throughout J J J , require
Φ δ ( q , 0 ) ≥ a ( q ) if q ∈ J , ∣ q − 1 ∣ ≥ 3 δ , (31) \Phi_\delta(q,0) \ge a(q)\qquad\text{if }q\in J,\ |q-1|\ge3\delta, \tag*{(31)} Φ δ ( q , 0 ) ≥ a ( q ) if q ∈ J , ∣ q − 1∣ ≥ 3 δ , (31)
Φ δ ( q , z ∗ ( q ) ) ≥ a ( q ) for q ∈ J , (32) \Phi_\delta(q,z_*(q)) \ge a(q)\qquad\text{for }q\in J, \tag*{(32)} Φ δ ( q , z ∗ ( q )) ≥ a ( q ) for q ∈ J , (32)
L ∗ ( q ) > b q d ∗ ( q ) + h + + 20 ε + 2 ε if ∣ q − 1 ∣ ≤ 3 δ . (33) L_*(q) > bq d_*(q)+h_+ + 20\varepsilon+ 2\varepsilon\qquad\text{if }|q-1|\le3\delta. \tag*{(33)} L ∗ ( q ) > b q d ∗ ( q ) + h + + 20 ε + 2 ε if ∣ q − 1∣ ≤ 3 δ . (33)
The first condition covers a reference close to the edge of the search interval. The second pays for a continuation with large stable surplus. The third pays for a threshold step when stable surplus is small. Appendix § 15 verifies these conditions simultaneously.
The policy
If A A A is the set of accepted elements and R R R the set of rejected or discarded elements, the residual matroid is ( M 0 / A ) ∖ R (M_0/A)\setminus R ( M 0 / A ) ∖ R . At each decision, the algorithm computes the reference and all prices before revealing the next remaining label. The value of N N N in the error allowances stays fixed throughout.
A loop is ignored when it arrives. Conditional on the history, the relative order of the remaining nonloops is uniform and their values retain their original product law. Reference samples are independent of these future arrivals. A threshold acceptance preserves feasibility by contraction.
At entry to a virtual continuation we use the current minor and the selected reference, initialize its local accepted set and record list to be empty, and attach fresh sorted clocks to the remaining arrivals as in § 6 .
Each threshold step removes one label. There are therefore at most N N N searches and at most one virtual continuation. A reference passed to another search always satisfies ∣ q − 1 ∣ < 3 δ |q-1| < 3\delta ∣ q − 1∣ < 3 δ . When N = 0 N=0 N = 0 , the algorithm returns the empty set before using N N N in a denominator.
Algorithm 2 The matroid prophet-secretary algorithm
Input: M 0 = ( E 0 , I 0 ) M_0=(E_0,\mathcal{I}_0) M 0 = ( E 0 , I 0 ) through a matroid independence oracle, the explicit input distributions, and the fixed parameters.
Output: an independent accepted set A A A .
Initialize N ← ∣ E 0 ∣ N \leftarrow|E_0| N ← ∣ E 0 ∣ , A ← ∅ A \leftarrow\varnothing A ← ∅ , M ← M 0 M \leftarrow M_0 M ← M 0 , and q i n ← 1 q^{\mathrm{in}} \leftarrow1 q in ← 1 .
Repeat: (a) Delete every loop from M M M and ignore its future arrival. If E ( M ) = ∅ E(M)=\varnothing E ( M ) = ∅ , or if X e = 0 X_e=0 X e = 0 almost surely for every e ∈ E ( M ) e\in E(M) e ∈ E ( M ) , reject all remaining arrivals and return A A A . (b) Run the reference search of § 8 on ( M , q i n ) (M,q^{\mathrm{in}}) ( M , q in ) . Retain its selected q q q , the exact V q V_q V q , and the saved estimates F ^ , D ^ , C ^ , ( m ^ e ) e ∈ E ( M ) \widehat{F},\widehat{D},\widehat{C},(\widehat{m}_e)_{e\in E(M)} F , D , C , ( m e ) e ∈ E ( M ) . (c) If ∣ q − 1 ∣ ≥ 3 δ |q-1|\ge3\delta ∣ q − 1∣ ≥ 3 δ or ( D ^ − C ^ ) / F ^ > η (\widehat{D}-\widehat{C})/\widehat{F}>\eta ( D − C ) / F > η , run the virtual continuation on M M M with parameter q q q and fresh randomness. Let A ′ A' A ′ be its accepted set. Return A ∪ A ′ A\cup A' A ∪ A ′ . (d) For every e ∈ E ( M ) e\in E(M) e ∈ E ( M ) , set
p e ← a ( q ) m ^ e + ε V q / N 1 − ε p_e \leftarrow a(q)\frac{\widehat{m}_e+\varepsilon V_q/N}{1-\varepsilon} p e ← a ( q ) 1 − ε m e + ε V q / N (e) Observe the next remaining element e e e and its value X e X_e X e . If X e > p e X_e>p_e X e > p e , accept e e e , set A ← A ∪ { e } A\leftarrow A\cup\{e\} A ← A ∪ { e } and M ← M / e M\leftarrow M/e M ← M / e . Otherwise reject e e e and set M ← M ∖ e M\leftarrow M\setminus e M ← M ∖ e . (f) Set q i n ← q q^{\mathrm{in}}\leftarrow q q in ← q and repeat.
One-step progress
Lemma 23 (Local potential bound). Assume (4.2) and (8.2)–(8.4), as well as ω > 0 \omega>0 ω > 0 and q ( b + s ) > 1 q(b+s)>1 q ( b + s ) > 1 throughout J J J . At a positive-value residual state, on the event that all queried batches are accurate, the next action has expected reward plus continuation potential at least
a ( q i n ) F q i n . a(q^{\mathrm{in}})F_{q^{\mathrm{in}}}. a ( q in ) F q in . After a threshold step, the potential is evaluated on the child minor at the inherited selected parameter q q q . A virtual continuation has zero terminal potential.
Proof. Fix all queried batches at the state and write q q q for the selected reference. Abbreviate a = a ( q ) a=a(q) a = a ( q ) , F = F q F=F_q F = F q , D = D q D=D_q D = D q , and H = H q H=H_q H = H q . Reference selection gives a F ≥ a ( q i n ) F q i n aF\ge a(q^{\mathrm{in}})F_{q^{\mathrm{in}}} a F ≥ a ( q in ) F q in , so it suffices to pay for a F aF a F .
If ∣ q − 1 ∣ ≥ 3 δ |q-1|\ge3\delta ∣ q − 1∣ ≥ 3 δ , the continuation earns at least a F aF a F by Proposition 16, Q ≥ 0 Q\ge0 Q ≥ 0 , and (8.2). It remains to consider ∣ q − 1 ∣ < 3 δ |q-1|<3\delta ∣ q − 1∣ < 3 δ . Reference selection then gives
d ∗ − 20 ε ≤ D F ≤ d ∗ + H F + 20 ε . (34) d_* - 20\varepsilon\le\frac{D}{F} \le d_*+\frac{H}{F}+20\varepsilon. \tag*{(34)} d ∗ − 20 ε ≤ F D ≤ d ∗ + F H + 20 ε . (34)
The two ratio estimates used by the search also imply
∣ D ^ − C ^ F ^ − H F ∣ ≤ 10 ε . \left|\frac{\widehat{D}-\widehat{C}}{\widehat{F}}-\frac{H}{F}\right|\le10\varepsilon. F D − C − F H ≤ 10 ε .
Large stable surplus. If ( D ^ − C ^ ) / F ^ > η (\widehat{D}-\widehat{C})/\widehat{F}>\eta ( D − C ) / F > η , then H / F > h − > 0 H/F>h_->0 H / F > h − > 0 . By Lemma 10 and (8.5),
Q F ≥ ( H / F ) 2 1 − D / F + H / F ≥ ( H / F ) 2 1 − d ∗ + 20 ε + H / F ≥ z ∗ ( q ) . \frac{Q}{F}\ge\frac{(H/F)^2}{1-D/F+H/F}\ge\frac{(H/F)^2}{1-d_*+20\varepsilon+H/F}\ge z_*(q). F Q ≥ 1 − D / F + H / F ( H / F ) 2 ≥ 1 − d ∗ + 20 ε + H / F ( H / F ) 2 ≥ z ∗ ( q ) .
The last inequality uses that x 2 / ( c + x ) x^{2}/(c+x) x 2 / ( c + x ) is increasing for x ≥ 0 x \ge0 x ≥ 0 when c > 0 c>0 c > 0 . Since Φ δ ( q , z ) \Phi_{\delta}(q,z) Φ δ ( q , z ) increases with z z z , condition (32) and Proposition 16 give reward at least a F aF a F .
Small stable surplus. Otherwise H / F ≤ h + H/F \le h_{+} H / F ≤ h + . Let b b b be as in (30) , and define S b = ∑ e E ( Y e q − b m e ) + S_b=\sum_e \mathbb{E}(Y_e^q-bm_e)^{+} S b = ∑ e E ( Y e q − b m e ) + . Write d = D / F d=D/F d = D / F , h = H / F h=H/F h = H / F , and c = b / ( b + s ) c=b/(b+s) c = b / ( b + s ) . We compare the surplus directly with the benchmark loss. Corollary 15 gives
S b F − b q d ≥ 1 − b − c ( ( 1 − b ) + h + b e − s ) + ( c − b q ) d . \frac{S_b}{F}-bqd \ge1-b-c\bigl((1-b)+h+be^{-s}\bigr)+(c-bq)d. F S b − b q d ≥ 1 − b − c ( ( 1 − b ) + h + b e − s ) + ( c − b q ) d .
Since q ( b + s ) > 1 q(b+s)>1 q ( b + s ) > 1 , the coefficient c − b q c-bq c − b q is negative. We may therefore substitute the upper stationarity bound d ≤ d ∗ + h + 20 ε d\le d_{*}+h+20\varepsilon d ≤ d ∗ + h + 20 ε . The terms c h ch c h cancel, giving
S b F − b q d ≥ 1 − b + c ( d ∗ + 20 ε − ( 1 − b ) − b e − s ) − b q ( d ∗ + h + 20 ε ) ≥ L ∗ ( q ) − b q ( d ∗ + h + + 20 ε ) > 2 ε . \begin{aligned}
\frac{S_b}{F}-bqd \ge1-b+c\bigl(d_{*}+20\varepsilon-(1-b)-be^{-s}\bigr)-bq(d_{*}+h+20\varepsilon) \\
&\ge L_{*}(q)-bq(d_{*}+h_{+}+20\varepsilon)>2\varepsilon.
\end{aligned} F S b − b q d ≥ 1 − b + c ( d ∗ + 20 ε − ( 1 − b ) − b e − s ) − b q ( d ∗ + h + 20 ε ) ≥ L ∗ ( q ) − b q ( d ∗ + h + + 20 ε ) > 2 ε .
The last two inequalities use h ≤ h + h\le h_{+} h ≤ h + and condition (33) . Thus
S b > b q D + 2 ε F . (35) S_b>bqD+2\varepsilon F. \tag*{(35)} S b > b q D + 2 εF . (35)
Fix the vector of thresholds p e p_e p e determined by the saved batch. Equations (25) and (26) give p e ≥ a m e p_e\ge am_e p e ≥ a m e and ∑ e ( p e − b m e ) + < 2 ε F \sum_e(p_e-bm_e)^{+}<2\varepsilon F ∑ e ( p e − b m e ) + < 2 εF . Let S X = ∑ e E ( X e − p e ) + S_X=\sum_e\mathbb{E}(X_e-p_e)^{+} S X = ∑ e E ( X e − p e ) + . Reference tails satisfy P ( Y e q > z ) ≤ q P ( X e > z ) \mathbb{P}(Y_e^q>z)\le q\mathbb{P}(X_e>z) P ( Y e q > z ) ≤ q P ( X e > z ) , and hence
S b ≤ ∑ e E ( Y e q − p e ) + + ∑ e ( p e − b m e ) + < q S X + 2 ε F . S_b\le\sum_e\mathbb{E}(Y_e^q-p_e)^{+}+\sum_e(p_e-bm_e)^{+}<qS_X+2\varepsilon F. S b ≤ e ∑ E ( Y e q − p e ) + + e ∑ ( p e − b m e ) + < q S X + 2 εF .
Together with (35) , this yields S X > b D ≥ a D S_X>bD\ge aD S X > b D ≥ a D .
For a fixed next label e e e , the difference between the deletion and contraction potentials is
a F q ( M ∖ e ) − a F q ( M / e ) = a m e . aF_q(M\setminus e)-aF_q(M/e)=am_e. a F q ( M ∖ e ) − a F q ( M / e ) = a m e .
Since p e ≥ a m e p_e\ge am_e p e ≥ a m e , accepting when X e > p e X_e>p_e X e > p e improves on deletion by at least ( X e − p e ) + (X_e-p_e)^{+} ( X e − p e ) + . Averaging over the next uniform label therefore gives expected reward plus child potential at least
a F + 1 n ( S X − a D ) ≥ a F . aF+\frac{1}{n}(S_X-aD)\ge aF. a F + n 1 ( S X − a D ) ≥ a F .
This child potential is exactly the incoming potential for the next reference search. All branches satisfy the claimed bound.
Charging statistical errors
Proposition 24 (Guarantee with exact random primitives). Under the stated parameter conditions, the ideal policy satisfies
E [ A L G ] ≥ ( 1 − θ − ρ ) F 0 . \mathbb{E}[\mathrm{ALG}]\ge(1-\theta-\rho)F_0. E [ ALG ] ≥ ( 1 − θ − ρ ) F 0 . Its expected number of matroid independence queries is O ( N 4 ) O(N^{4}) O ( N 4 ) .
Proof. If F 0 = 0 F_0=0 F 0 = 0 , the policy stops and the claim is immediate. Otherwise use the potential P ( M , q ) = a ( q ) F q ( M ) \mathcal{P}(M,q)=a(q)F_q(M) P ( M , q ) = a ( q ) F q ( M ) . Initially it is ( 1 − θ ) F 0 (1-\theta)F_0 ( 1 − θ ) F 0 . For every residual minor, F 1 ( M ) ≤ F 0 F_1(M)\le F_0 F 1 ( M ) ≤ F 0 , so Lemma 8 and (5) imply
0 ≤ P ( M , q ) ≤ ( max u ∈ J a ( u ) ) q + F 1 ( M ) ≤ F 0 . 0\le\mathcal{P}(M,q)\le\left(\max_{u\in J}a(u)\right)q_{+}F_1(M)\le F_0. 0 ≤ P ( M , q ) ≤ ( u ∈ J max a ( u ) ) q + F 1 ( M ) ≤ F 0 .
Conditionally at each computation state, all queried batches are accurate with probability at least 1 − ρ / N 1-\rho/N 1 − ρ / N , by Lemma 21 . On that event, Lemma 23 gives nonnegative expected drift of reward plus potential. On the complementary event, rewards and subsequent potentials remain nonnegative, so the expected decrease is at most F 0 F_0 F 0 .
Treat a virtual continuation as one final epoch and append empty epochs to obtain exactly N N N epochs. Summing conditional drift bounds loses at most N ( ρ / N ) F 0 = ρ F 0 N(\rho/N)F_0=\rho F_0 N ( ρ / N ) F 0 = ρ F 0 . No union bound over possible residual minors is needed.
There are at most N K m = O ( N 2 log 2 ( N + 2 ) ) NKm=O(N^2\log^2(N+2)) N K m = O ( N 2 log 2 ( N + 2 )) layer samples. Their total query cost is O ( N 3 log 3 ( N + 2 ) ) O(N^3\log^3(N+2)) O ( N 3 log 3 ( N + 2 )) . Loop detection and actual decisions use O ( N 2 ) O(N^2) O ( N 2 ) further queries. The one possible virtual continuation costs O ( N 4 ) O(N^4) O ( N 4 ) in expectation. Since log 3 ( N + 2 ) = O ( N ) \log^3(N+2)=O(N) log 3 ( N + 2 ) = O ( N ) , the total is O ( N 4 ) O(N^4) O ( N 4 ) .
Appendix C converts this policy to a bounded-bit algorithm at an additional loss of at most ρ F 0 \rho F_0 ρ F 0 . The resulting competitive ratio is 1 − θ − 2 ρ 1-\theta-2\rho 1 − θ − 2 ρ .
The sharp bound for XOS valuations
We now turn from selecting elements of a matroid to allocating disjoint bundles to buyers. For XOS valuations, Ehsani et al. [15 ] give a 1 − 1 / e 1-1/e 1 − 1/ e guarantee. We prove the matching upper bound even when every buyer draws her valuation from the same distribution. Our instance has a simple description. Each buyer values the items she receives in one part of a partition, and her type specifies which parts she may use. The prophet can usually choose a single partition that serves all buyers. An online algorithm must allocate each bundle before it knows which partition will serve the later buyers.
A family of partitions
Fix n ≥ 2 n\ge2 n ≥ 2 buyers and a finite index set T \mathcal{T} T . An item is a function from T \mathcal{T} T to [ n ] [n] [ n ] , so the item set is M = [ n ] T M=[n]^{\mathcal{T}} M = [ n ] T and m = ∣ M ∣ = n ∣ T ∣ m=|M|=n^{|\mathcal{T}|} m = ∣ M ∣ = n ∣ T ∣ . Each coordinate s ∈ T s\in\mathcal{T} s ∈ T partitions M M M into the n n n equal parts P s r = { x ∈ M : x ( s ) = r } P_s^r=\{x\in M:x(s)=r\} P s r = { x ∈ M : x ( s ) = r } , r ∈ [ n ] r\in[n] r ∈ [ n ] .
All these partitions are public. Within a partition the n n n parts are disjoint. Across partitions their overlaps are given by the product rule.
Lemma 25 (Counting partition parts). For distinct s 1 , … , s k ∈ T s_1,\ldots,s_k\in\mathcal{T} s 1 , … , s k ∈ T and arbitrary r 1 , … , r k ∈ [ n ] r_1,\ldots,r_k\in[n] r 1 , … , r k ∈ [ n ] ,
∣ ⋃ i = 1 k P s i r i ∣ = m ( 1 − ( 1 − 1 n ) k ) . \left|\bigcup_{i=1}^{k}P_{s_i}^{r_i}\right|=m\left(1-\left(1-\frac{1}{n}\right)^k\right). i = 1 ⋃ k P s i r i = m ( 1 − ( 1 − n 1 ) k ) . Proof. Outside the union each of the k k k specified coordinates has n − 1 n-1 n − 1 possible values. Each of the other coordinates has n n n possibilities.
An i.i.d. distribution of buyer types
Fix L ≥ n L\ge n L ≥ n and index the partitions by T = ( [ L ] n ) \mathcal{T}=\binom{[L]}{n} T = ( n [ L ] ) . Give each buyer an independent uniform label in [ L ] [L] [ L ] . For any partition index s s s containing her label a a a , she may use part r s ( a ) r_s(a) r s ( a ) , where r s ( a ) r_s(a) r s ( a ) is the position of a a a in the increasing order on s s s . Her valuation for a bundle S S S is
v a ( S ) = max s ∈ T : a ∈ s ∣ S ∩ P s r s ( a ) ∣ . (36) v^a(S)=\max_{s\in\mathcal{T}:a\in s}|S\cap P_s^{r_s(a)}|. \tag*{(36)} v a ( S ) = s ∈ T : a ∈ s max ∣ S ∩ P s r s ( a ) ∣. (36)
This is the maximum of additive clauses with coefficients in { 0 , 1 } \{0,1\} { 0 , 1 } . In particular,
v a ( S ) ≤ ∣ S ∣ , v a ( M ) = m / n . (37) v^a(S)\le|S|,\qquad v^a(M)=m/n. \tag*{(37)} v a ( S ) ≤ ∣ S ∣ , v a ( M ) = m / n . (37)
The prophet. If the n n n labels are distinct, their set is a partition index s s s . Allocating the part P s r s ( a ) P_s^{r_s(a)} P s r s ( a ) to each buyer with label a a a assigns every item exactly once, for welfare m m m . A pair of labels coincides with probability 1 / L 1/L 1/ L . Thus
E [ O P T ] ≥ m ( 1 − ( n 2 ) / L ) . (38) \mathbb{E}[\mathrm{OPT}] \ge m\left(1-\binom{n}{2}/L\right). \tag*{(38)} E [ OPT ] ≥ m ( 1 − ( 2 n ) / L ) . (38)
The online allocation. Reveal the entire permutation of buyer identities in advance and the label of each buyer at her arrival. Conditional on the permutation and the algorithm’s independent random tape, the labels A 1 , … , A n A_1,\ldots,A_n A 1 , … , A n in arrival order remain independent and uniform. When the algorithm gives S t S_t S t to the buyer at position t t t , fix the first maximizing index W t W_t W t in a public ordering of the clauses in (36) . Then
A t ∈ W t , v A t ( S t ) = ∣ S t ∩ P W t r W t ( A t ) ∣ . (39) A_t \in W_t,\qquad v^{A_t}(S_t)=\lvert S_t\cap P_{W_t}^{r_{W_t}(A_t)}\rvert. \tag*{(39)} A t ∈ W t , v A t ( S t ) = ∣ S t ∩ P W t r W t ( A t ) ∣ . (39)
We can fix this witness at the moment of allocation, even if several clauses attain the same value. For t < u t<u t < u , the witnesses can coincide only if the future label A u A_u A u lies in the already fixed n n n -set W t W_t W t . Conditional on the history through t t t , that event has probability n / L n/L n / L . A union bound gives
Pr [ ∃ t < u : W t = W u ] ≤ ( n 2 ) n L . (40) \Pr[\exists t<u: W_t=W_u]\le\binom{n}{2}\frac{n}{L}. \tag*{(40)} Pr [ ∃ t < u : W t = W u ] ≤ ( 2 n ) L n . (40)
When all witnesses are distinct, the n n n credited sets in (39) are disjoint subsets of their respective partition parts. Hence, by Lemma 25, their total size is at most m c n mc_n m c n , where c n = 1 − ( 1 − 1 / n ) n c_n=1-(1-1/n)^n c n = 1 − ( 1 − 1/ n ) n . This counting identity holds for every choice of distinct indices, including the ones selected by the algorithm’s past decisions. On a collision the welfare is at most m m m by (37) . Averaging over the permutation and the random tape gives
E [ A L G ] ≤ m ( c n + ( n 2 ) n / L ) . (41) \mathbb{E}[\mathrm{ALG}]\le m\left(c_n+\binom{n}{2}n/L\right). \tag*{(41)} E [ ALG ] ≤ m ( c n + ( 2 n ) n / L ) . (41)
Proof of Theorem 3 . For L > ( n 2 ) L>\binom{n}{2} L > ( 2 n ) , dividing (41) by the lower bound in (38) gives
E [ A L G ] E [ O P T ] ≤ c n + n ( n 2 ) / L 1 − ( n 2 ) / L . (42) \frac{\mathbb{E}[\mathrm{ALG}]}{\mathbb{E}[\mathrm{OPT}]}
\le
\frac{c_n+n\binom{n}{2}/L}{1-\binom{n}{2}/L}. \tag*{(42)} E [ OPT ] E [ ALG ] ≤ 1 − ( 2 n ) / L c n + n ( 2 n ) / L . (42)
Given ξ > 0 \xi>0 ξ > 0 , choose n n n so that c n < 1 − 1 / e + ξ / 2 c_n<1-1/e+\xi/2 c n < 1 − 1/ e + ξ /2 and then L L L so that the right-hand side is below 1 − 1 / e + ξ 1-1/e+\xi 1 − 1/ e + ξ . These choices work for every online algorithm. □
The bound allows unlimited computation and full knowledge of the input law. Indeed the list of clauses, over all L L L possible types, has L ( L − 1 n − 1 ) = n ∣ T ∣ L\binom{L-1}{n-1}=n|\mathcal{T}| L ( n − 1 L − 1 ) = n ∣ T ∣ clause occurrences. Listing the m m m binary coefficients of each takes n m log n m nm\log_n m nm log n m bits. The uncertainty is about which types will arrive.
Corollary 26. For 0 < ξ < 1 / 4 0<\xi<1/4 0 < ξ < 1/4 , the instance in Theorem 3 can have O ( ξ − 4 log ( 1 / ξ ) ) O(\xi^{-4}\log(1/\xi)) O ( ξ − 4 log ( 1/ ξ )) items.
Proof. Set c = 1 − 1 / e c=1-1/e c = 1 − 1/ e , n = 1 + ⌈ 8 / ξ ⌉ n=1+\lceil8/\xi\rceil n = 1 + ⌈ 8/ ξ ⌉ , and L = ⌈ 8 n 3 / ξ ⌉ L=\lceil8n^3/\xi\rceil L = ⌈ 8 n 3 / ξ ⌉ . Sample m ′ m' m ′ items independently from M M M , treating repeated samples as distinct items. Restrict each clause to these items. For any fixed choice of n n n distinct partition indices and one part from each, the fraction of sampled items in their union is the mean of m ′ m' m ′ independent Bernoulli variables of mean c n c_n c n . Let ζ = ξ / 8 \zeta=\xi/8 ζ = ξ /8 and take m ′ = ⌈ ( 1 + n log ( n ∣ T ∣ ) ) / ( 2 ζ 2 ) ⌉ m'=\lceil(1+n\log(n|\mathcal{T}|))/(2\zeta^2)\rceil m ′ = ⌈( 1 + n log ( n ∣ T ∣ )) / ( 2 ζ 2 )⌉ . Hoeffding’s inequality and a union bound over at most $(n|\mathcal{T}|)^n choices give a realization in which every such union covers at most a c n + ζ c_n+\zeta c n + ζ fraction. Fix this realization and make it public.
Every partition still covers all m ′ m' m ′ items, so the prophet earns m ′ m' m ′ whenever the labels are distinct. The collision bound (40) still holds because each witness is indexed by a set of n n n types. Consequently (42) holds with c n + ζ c_n+\zeta c n + ζ in place of c n c_n c n . The power series for log ( 1 − 1 / n ) \log(1-1/n) log ( 1 − 1/ n ) gives n log ( 1 − 1 / n ) ≥ − 1 − 1 / ( 2 ( n − 1 ) ) n\log(1-1/n)\geq-1-1/(2(n-1)) n log ( 1 − 1/ n ) ≥ − 1 − 1/ ( 2 ( n − 1 )) , whence c n − c ≤ 1 / ( 2 e ( n − 1 ) ) < ξ / 16 c_n-c\leq1/(2e(n-1))<\xi/16 c n − c ≤ 1/ ( 2 e ( n − 1 )) < ξ /16 . Also ( n 2 ) / L < ξ / 16 \binom{n}{2}/L<\xi/16 ( 2 n ) / L < ξ /16 . The ratio is therefore at most ( c + ξ / 4 ) / ( 1 − ξ / 16 ) < c + ξ (c+\xi/4)/(1-\xi/16)<c+\xi ( c + ξ /4 ) / ( 1 − ξ /16 ) < c + ξ . Finally, ∣ T ∣ ≤ L n |\mathcal{T}|\leq L^n ∣ T ∣ ≤ L n gives the stated bound on m ′ m' m ′ . The number of clauses per valuation can still be exponential in n n n .
Relation to coverage welfare
The upper bound also follows from Udwani and Wajc’s theorem for online coverage welfare under known i.i.d. item arrivals [33 Theorem 1.2] . We give the reduction to clarify the change of arrival model. It uses the coverage-to-XOS construction of Chawla and Dang [10 Appendix D] , who apply it to allocation with free disposal.
In the coverage problem there are k k k fixed buyers. Buyer a a a has a universe U a U_a U a with nonnegative weights w a , u w_{a,u} w a , u , and an arriving item of type e e e covers C a , e ⊆ U a C_{a,e}\subseteq U_a C a , e ⊆ U a if assigned to her. Her value is the total weight of the union of sets covered by her assigned items. Take disjoint copies of the universes. In the auction their elements become the items. Each arrival of type e e e becomes a buyer with valuation
v e ( S ) = max a ∈ [ k ] ∑ u ∈ S ∩ C a , e w a , u . (43) v_e(S)=\max_{a\in[k]}\sum_{u\in S\cap C_{a,e}}w_{a,u}. \tag*{(43)} v e ( S ) = a ∈ [ k ] max u ∈ S ∩ C a , e ∑ w a , u . (43)
To simulate an auction algorithm in the coverage problem, assign the arriving item to a maximizing clause a a a for the bundle S S S it allocates. All elements counted in that clause are then covered by buyer a a a . Because the auction bundles are disjoint, these elements are charged at most once across arrivals. The coverage welfare therefore dominates the auction welfare. Conversely, whenever a coverage algorithm assigns e e e to a a a , give the corresponding auction buyer the elements of C a , e C_{a,e} C a , e still unallocated. They are exactly the elements newly covered by this assignment, and the bundle earns their total weight. Both simulations run online. Applied offline they give equality of the optima. Finally, i.i.d. item types induce i.i.d. buyer valuations, whose joint law is preserved by an independent random permutation. Thus the information-theoretic coverage upper bound transfers to this auction model.
AI Use Statement
This work resulted from extensive interaction between the authors and OpenAI Astra, with the authors providing suggestions and critically checking Astra’s responses through iterative exchanges. OpenAI Astra was also used in writing and revising the manuscript through detailed prompts from the authors, with Gemini Argon assisting in some parts. The authors directed the process and evaluated the proposed ideas and arguments. A supplementary Lean archive is available on GitHub https://github.com/hajiaghayi/Matroid-Prophet-Secretary-XOS .
Implementing the common-law rule
Let n = ∣ E ( M ) ∣ ≥ 1 n = |E(\mathcal{M})| \ge1 n = ∣ E ( M ) ∣ ≥ 1 . An independence query to M \mathcal{M} M costs T I T_I T I , and a query returning F ( x − ) F(x^-) F ( x − ) and F ( x ) F(x) F ( x ) costs T F T_F T F . We first count arithmetic operations, comparisons, and uniform draws on [ 0 , 1 ] [0,1] [ 0 , 1 ] at unit cost. We give the finite-bit version below. Let I I I be the accepted set. To test whether A ⊆ E ( N ) ∖ { e } A \subseteq E(N) \setminus\{e\} A ⊆ E ( N ) ∖ { e } spans e e e , greedily extend I I I through A A A , then test whether the resulting independent set can be augmented by e e e . The test takes at most ∣ A ∣ + 1 |A|+1 ∣ A ∣ + 1 queries. Applying it to the empty set and the whole remaining set detects loops and coloops.
Algorithm 3 The sampled rule for identically distributed weights
Reject a loop and accept a coloop. For every other arrival ( e , x ) (e,x) ( e , x ) , draw its upper quantile u = 1 − F ( x ) + V ( F ( x ) − F ( x − ) ) u = 1 - F(x) + V(F(x) - F(x^-)) u = 1 − F ( x ) + V ( F ( x ) − F ( x − )) , using a fresh uniform V V V .
Draw m m m independent subsets of E ( N ) ∖ { e } E(N) \setminus\{e\} E ( N ) ∖ { e } by including each label with probability u u u . Let H H H be the number of subsets that fail to span e e e .
Accept if H / m ≥ e − η 0 H/m \ge e^{-\eta_0} H / m ≥ e − η 0 . Contract an accepted element and delete a rejected element.
Proposition 27. For an absolute constant C C C , using m = ⌈ C n 2 ⌈ log 2 ( 2 n ) ⌉ ⌉ m = \lceil Cn^2\lceil\log_2(2n)\rceil\rceil m = ⌈ C n 2 ⌈ log 2 ( 2 n )⌉⌉ trials per arrival in Algorithm 3 gives competitive ratio c 0 c_0 c 0 . The running time is O ( n 4 log ( 2 n ) ( 1 + T I ) + n T F ) O(n^4\log(2n)(1+T_I)+nT_F) O ( n 4 log ( 2 n ) ( 1 + T I ) + n T F ) .
The sampling error would cost a small additive term if we used only the guarantee in Theorem 4 . On a ground set of size n n n , however, the comparison has slack of order 1 / n 1/n 1/ n . We prove this first and then use the slack to pay for sampling.
Proof. Let g ( a ) = e − 1 − a / a g(a) = e^{-1-a}/a g ( a ) = e − 1 − a / a . Consider a deterministic cutoff q q q calibrated at S ( q ) = e − a S(q) = e^{-a} S ( q ) = e − a with η 0 / 2 ≤ a ≤ 3 η 0 / 2 \eta_0/2 \le a \le3\eta_0/2 η 0 /2 ≤ a ≤ 3 η 0 /2 , for a label that is neither a loop nor a coloop. There are absolute constants K , B > 0 K, B > 0 K , B > 0 with
D ( v ) min ( q , v ) ≤ 1 + η 0 + K ∣ a − η 0 ∣ − B / n ( 0 < v ≤ 1 ) . (44) \frac{D(v)}{\min(q,v)} \le1+\eta_0+K|a-\eta_0|-B/n \qquad(0<v\le1). \tag*{(44)} min ( q , v ) D ( v ) ≤ 1 + η 0 + K ∣ a − η 0 ∣ − B / n ( 0 < v ≤ 1 ) . (44)
Indeed, the event of sampling no other label gives S ( q ) ≥ ( 1 − q ) n − 1 S(q) \ge(1-q)^{n-1} S ( q ) ≥ ( 1 − q ) n − 1 . Thus q ≥ 1 − e − a / ( n − 1 ) ≥ b / n q \ge1-e^{-a/(n-1)} \ge b/n q ≥ 1 − e − a / ( n − 1 ) ≥ b / n for b = 1 − e − η 0 / 2 b = 1-e^{-\eta_0/2} b = 1 − e − η 0 /2 . Set d = 1 − q / τ ( q ) d = 1-q/\tau(q) d = 1 − q / τ ( q ) . Since τ ( q ) ≥ q + q 2 / 2 \tau(q) \ge q+q^2/2 τ ( q ) ≥ q + q 2 /2 , we have d ≥ q / 3 d \ge q/3 d ≥ q /3 . For v ≤ q v \le q v ≤ q , Lemma 5 gives 1 − S ( v ) ≤ a τ ( v ) / τ ( q ) 1-S(v) \le a\tau(v)/\tau(q) 1 − S ( v ) ≤ a τ ( v ) / τ ( q ) . By ( 1 − v / q ) τ ( v ) / v ≤ ( 1 − v ) τ ( v ) / v ≤ 1 (1-v/q)\tau(v)/v \le(1-v)\tau(v)/v \le1 ( 1 − v / q ) τ ( v ) / v ≤ ( 1 − v ) τ ( v ) / v ≤ 1 , it follows that
D ( v ) / v − 1 ≤ a ( 1 − d ) ≤ a − η 0 q / 6. D(v)/v-1 \le a(1-d) \le a-\eta_0q/6. D ( v ) / v − 1 ≤ a ( 1 − d ) ≤ a − η 0 q /6.
For v = q x ≥ q v=qx \ge q v = q x ≥ q , the power series of τ \tau τ yields τ ( q x ) / τ ( q ) ≥ ( 1 − d ) x + d x 2 \tau(qx)/\tau(q) \ge(1-d)x+dx^2 τ ( q x ) / τ ( q ) ≥ ( 1 − d ) x + d x 2 , first for v < 1 v<1 v < 1 and then by a limit. Applying Lemma 5 in the other direction gives
D ( v ) / q − 1 ≤ ( x − 1 ) e − a x − a d x ( x − 1 ) . D(v)/q-1 \le(x-1)e^{-ax-adx(x-1)}. D ( v ) / q − 1 ≤ ( x − 1 ) e − a x − a d x ( x − 1 ) .
For 1 ≤ x ≤ 1 + η 0 / 2 1 \le x \le1+\eta_0/2 1 ≤ x ≤ 1 + η 0 /2 this is at most η 0 / 2 \eta_0/2 η 0 /2 . For x > 1 + η 0 / 2 x>1+\eta_0/2 x > 1 + η 0 /2 it is at most g ( a ) e − η 0 2 q / 12 g(a)e^{-\eta_0^2q/12} g ( a ) e − η 0 2 q /12 . Concavity gives 1 − e − η 0 2 q / 12 ≥ q ( 1 − e − η 0 2 / 12 ) 1-e^{-\eta_0^2q/12} \ge q(1-e^{-\eta_0^2/12}) 1 − e − η 0 2 q /12 ≥ q ( 1 − e − η 0 2 /12 ) . Since g ( η 0 ) = η 0 g(\eta_0)=\eta_0 g ( η 0 ) = η 0 , these inequalities prove (A.1), for instance with
K = 1 + max a ∈ [ η 0 / 2 , 3 η 0 / 2 ] ∣ g ′ ( a ) ∣ , K = 1+\max_{a\in[\eta_0/2,3\eta_0/2]} |g'(a)|, K = 1 + a ∈ [ η 0 /2 , 3 η 0 /2 ] max ∣ g ′ ( a ) ∣ ,
B = min { η 0 / 2 , η 0 b / 6 , b g ( 3 η 0 / 2 ) ( 1 − e − η 0 2 / 12 ) } . B = \min\{\eta_0/2,\eta_0b/6,bg(3\eta_0/2)(1-e^{-\eta_0^2/12})\}. B = min { η 0 /2 , η 0 b /6 , b g ( 3 η 0 /2 ) ( 1 − e − η 0 2 /12 )} .
To analyze the sample, give each label an independent uniform priority in each trial and include it whenever its priority is at most u u u . As u u u grows, the number of nonspanning trials can only decrease. Thus, conditioned on these priorities, the sampled decision is a cutoff q ^ \widehat{q} q independent of the new weight and its tie breaker. Whether an interval endpoint belongs to the acceptance region is immaterial under continuous quantiles.
Put h = B / ( 2 K n ) h = B/(2Kn) h = B / ( 2 K n ) and define q − < q + q_{-} < q_{+} q − < q + by S ( q − ) = e − η 0 + h S(q_{-}) = e^{-\eta_0+h} S ( q − ) = e − η 0 + h and S ( q + ) = e − η 0 − h S(q_{+}) = e^{-\eta_0-h} S ( q + ) = e − η 0 − h . At both endpoints the population mean differs from β = e − η 0 \beta= e^{-\eta_0} β = e − η 0 by at least ρ = β ( 1 − e − h ) = Θ ( 1 / n ) \rho= \beta(1-e^{-h}) = \Theta(1/n) ρ = β ( 1 − e − h ) = Θ ( 1/ n ) . Hoeffding’s inequality [23 ] and monotonicity give
Pr ( q ^ ∉ [ q − , q + ] ) ≤ 2 e − 2 m ρ 2 . \Pr(\widehat{q} \notin[q_{-},q_{+}]) \leq2e^{-2m\rho^{2}}. Pr ( q ∈ / [ q − , q + ]) ≤ 2 e − 2 m ρ 2 .
This holds conditionally on the current minor. Choose λ = c 0 2 B / 4 \lambda= c_0^2B/4 λ = c 0 2 B /4 and take C C C large enough that the right-hand side is at most λ / n 2 \lambda/n^2 λ / n 2 . For every cutoff in the interval, (A.1) pays a fraction of each rank drop at least
( 1 + η 0 − B / ( 2 n ) ) − 1 ≥ c 0 + 2 λ / n . (1+\eta_0-B/(2n))^{-1} \geq c_0+2\lambda/n. ( 1 + η 0 − B / ( 2 n ) ) − 1 ≥ c 0 + 2 λ / n .
This fraction also works for loops and coloops since B ≤ η 0 / 2 B \leq\eta_0/2 B ≤ η 0 /2 and 1 − c 0 = c 0 η 0 1-c_0=c_0\eta_0 1 − c 0 = c 0 η 0 .
For the analysis only, replace a cutoff outside the interval by the exact one. The resulting policy earns at least ( c 0 + 2 λ / n ) P M ( F ) (c_0+2\lambda/n)P_M(F) ( c 0 + 2 λ / n ) P M ( F ) by the band argument. Couple it to Algorithm 3 up to the first replacement. Even conditionally on all weights, tie breakers, and the arrival order, the unused priorities at each step are fresh. The probability of a replacement is therefore at most n ( λ / n 2 ) = λ / n n(\lambda/n^2)=\lambda/n n ( λ / n 2 ) = λ / n . On this event the difference in payoffs is bounded by the realized offline optimum. Averaging gives at least ( c 0 + λ / n ) P M ( F ) (c_0+\lambda/n)P_M(F) ( c 0 + λ / n ) P M ( F ) for the sampled algorithm. Each trial uses O ( n ) O(n) O ( n ) elementary operations and O ( n ) O(n) O ( n ) independence queries using a mutable set representation, which gives the claimed running time.
Corollary 28 (Explicit rational distributions). If the common law is specified by rational weights and probabilities on a finite support, the ratio c 0 c_0 c 0 is achievable with polynomial worst-case bit complexity and O ( n 4 log ( 2 n ) ) O(n^4\log(2n)) O ( n 4 log ( 2 n )) independence queries.
Proof. Choose a dyadic β ~ \widetilde{\beta} β within ρ / 2 \rho/2 ρ /2 of e − η 0 e^{-\eta_0} e − η 0 . The preceding proof still gives c 0 + λ / n c_0+\lambda/n c 0 + λ / n for the real-arithmetic algorithm using β ~ \widetilde{\beta} β . Replace ρ \rho ρ by ρ / 2 \rho/2 ρ /2 in the Hoeffding bound and increase C C C . Computing this dyadic requires O ( log ( 2 n ) ) O(\log(2n)) O ( log ( 2 n )) bits of accuracy. For instance, bisect the strictly increasing function a 2 − e − 1 − a a^2-e^{-1-a} a 2 − e − 1 − a on [ 1 / 4 , 1 / 2 ] [1/4,1/2] [ 1/4 , 1/2 ] , using the Taylor series for the exponential with a remainder bound. Its derivative is at least 1 / 2 1/2 1/2 on this interval, so a function evaluation within ϵ \epsilon ϵ of zero locates the root within 2 ϵ 2\epsilon 2 ϵ . This gives a certified approximation in time polynomial in the requested precision.
Replace every uniform priority and tie breaker by its first L L L binary digits. Couple both versions by truncating the continuous draws. The quantile u u u changes by at most 2 − L 2^{-L} 2 − L even conditionally on the entire vector of weights and continuous tie breakers. A comparison between a priority and u u u can then change only if the original priority is within 2 1 − L 2^{1-L} 2 1 − L of u u u . Each fresh priority is uniform, independently of this conditioning, so the probability of such an event is at most 2 2 − L 2^{2-L} 2 2 − L . Up to the first disagreement there are at most n 2 m n^2m n 2 m comparisons. Choose L = O ( log ( 2 n ) ) L=O(\log(2n)) L = O ( log ( 2 n )) with 2 2 − L n 2 m ≤ λ / n 2^{2-L}n^2m\leq\lambda/n 2 2 − L n 2 m ≤ λ / n . The conditional probability of a disagreement is at most λ / n \lambda/n λ / n , and its cost is at most the realized offline optimum. This proves the ratio. The cumulative masses of the explicit law and all truncated comparisons can be computed exactly using rationals of polynomial bit length.
Optimal quantile cutoffs in uniform random order
The common-law algorithm in Section 3 works for every fixed arrival order independent of the draws. With a uniform permutation we can characterize the best guarantee for each individual matroid without imposing a local comparison. Fix a matroid M M M of positive rank on n n n labels, and let V M ( F ) V_M(F) V M ( F ) be the value of its optimal online policy in uniform random order. Write
γ ( M ) = inf F : P M ( F ) > 0 V M ( F ) P M ( F ) . \gamma(M)=\inf_{F:P_M(F)>0}\frac{V_M(F)}{P_M(F)}. γ ( M ) = F : P M ( F ) > 0 inf P M ( F ) V M ( F ) .
where F F F ranges over nonnegative common laws of finite mean. The policy inside the infimum may use the entire law. The next theorem shows that one table of quantile cutoffs, chosen knowing only the matroid, achieves γ ( M ) \gamma(M) γ ( M ) simultaneously for all common laws.
A flow on minors. Make a vertex for each residual labeled minor N N N . The root M M M has mass one. If a nonempty N N N receives mass y N y_N y N , the mass at which e e e arrives next is b N e = y N / ∣ E ( N ) ∣ b_{Ne}=y_N/|E(N)| b N e = y N /∣ E ( N ) ∣ . Send a N e a_{Ne} a N e units of this mass to N / e N/e N / e and b N e − a N e b_{Ne}-a_{Ne} b N e − a N e to N ∖ e N\setminus e N ∖ e , with 0 ≤ a N e ≤ b N e 0\le a_{Ne}\le b_{Ne} 0 ≤ a N e ≤ b N e and a N e = 0 a_{Ne}=0 a N e = 0 for loops. Sum the incoming masses at each vertex, including both arcs if they reach the same child. The graph is acyclic, and the feasible flows form a compact polytope D M \mathcal{D}_M D M . A flow D D D prescribes a cutoff q N e = a N e / b N e q_{Ne}=a_{Ne}/b_{Ne} q N e = a N e / b N e at every positive-mass arrival. Put
T D ( v ) = ∑ N , e min ( a N e , v b N e ) . T_D(v)=\sum_{N,e}\min(a_{Ne},vb_{Ne}). T D ( v ) = N , e ∑ min ( a N e , v b N e ) .
Theorem 29 (Simultaneous quantile cutoffs). In uniform random order,
γ ( M ) = max D ∈ D M inf 0 < v ≤ 1 T D ( v ) R M ( v ) . \gamma(M)=\max_{D\in\mathcal{D}_M}\inf_{0<v\le1}\frac{T_D(v)}{R_M(v)}. γ ( M ) = D ∈ D M max 0 < v ≤ 1 inf R M ( v ) T D ( v ) . The quantile cutoffs of a maximizing flow attain this ratio for every common law.
Proof. Any adaptive policy induces a feasible flow. Conditional on the past, the next label is uniform on the unseen labels, and the arriving quantile is fresh. Of the total mass b N e b_{Ne} b N e , at most a N e a_{Ne} a N e is accepted and at most v b N e vb_{Ne} v b N e belongs to the top v v v quantile band. Accepting its best q N e q_{Ne} q N e fraction attains the minimum of the two. This change preserves the masses of both children, so by induction it realizes the entire flow and earns exactly T D ( v ) T_D(v) T D ( v ) on every band. Zero-mass states can use arbitrary feasible decisions. It follows by integration over weight levels that any flow satisfying T D ( v ) ≥ c R M ( v ) T_D(v)\ge cR_M(v) T D ( v ) ≥ c R M ( v ) for all v v v is c c c -competitive on every law.
It remains to find such a flow for c = γ ( M ) c=\gamma(M) c = γ ( M ) . Fix finitely many positive endpoints v 1 , … , v k v_1,\ldots,v_k v 1 , … , v k . The set of vectors dominated coordinatewise by ( T D ( v i ) ) i (T_D(v_i))_i ( T D ( v i ) ) i for some D D D is closed by compactness and convex by concavity of each T D ( v i ) T_D(v_i) T D ( v i ) in D D D . If this set excluded ( c R M ( v i ) ) i (cR_M(v_i))_i ( c R M ( v i ) ) i , strict separation from that point by a hyperplane would give coefficients λ i ≥ 0 \lambda_i\ge0 λ i ≥ 0 , not all zero, with
max D ∈ D M ∑ i λ i T D ( v i ) < c ∑ i λ i R M ( v i ) . \max_{D\in\mathcal{D}_M}\sum_i\lambda_iT_D(v_i)<c\sum_i\lambda_iR_M(v_i). D ∈ D M max i ∑ λ i T D ( v i ) < c i ∑ λ i R M ( v i ) .
Nonnegativity follows since the set is closed under decreasing any coordinate. Give a label of upper quantile u u u the weight ∑ i λ i 1 { u ≤ v i } \sum_i\lambda_i1_{\{u\le v_i\}} ∑ i λ i 1 { u ≤ v i } . Its expected prophet value is the sum on the right without c c c , by the greedy algorithm. The sum on the left bounds the value of every policy, contradicting the definition of γ ( M ) \gamma(M) γ ( M ) . Thus every finite collection of the closed constraints T D ( v ) ≥ c R M ( v ) T_D(v)\ge cR_M(v) T D ( v ) ≥ c R M ( v ) admits a common flow. Compactness gives a flow satisfying all of them. □ \square □
For example, the deficit R M ( v ) − T D ( v ) R_M(v)-T_D(v) R M ( v ) − T D ( v ) is the sum over nonloop arrivals of positive mass of
b N e [ ( q N e − v ) + ( 1 − S e N ( v ) ) + ( v − q N e ) + S e N ( v ) ] . b_{Ne}\bigl[(q_{Ne}-v)_+(1-S_e^N(v))+(v-q_{Ne})_+S_e^N(v)\bigr]. b N e [ ( q N e − v ) + ( 1 − S e N ( v )) + ( v − q N e ) + S e N ( v ) ] .
This follows by telescoping (2) along the flow. The characterization therefore permits a loss at one arrival to be offset by a smaller loss at another.
Finite approximation. For 0 < δ ≤ 1 0 < \delta\le1 0 < δ ≤ 1 , start at v 1 = δ / n v_1 = \delta/n v 1 = δ / n , increase the endpoints by a factor 1 + δ 1 + \delta 1 + δ , and append 1 as the last endpoint. On this grid maximize c c c subject to the flow constraints and
∑ N , e t N e , i ≥ c R M ( v i ) , 0 ≤ t N e , i ≤ a N e , t N e , i ≤ v i b N e . \sum_{N,e} t_{Ne,i} \ge cR_M(v_i), \qquad0 \le t_{Ne,i} \le a_{Ne}, \qquad t_{Ne,i} \le v_i b_{Ne}. N , e ∑ t N e , i ≥ c R M ( v i ) , 0 ≤ t N e , i ≤ a N e , t N e , i ≤ v i b N e .
The resulting linear program has at most 3 n 3^n 3 n minor vertices and O ( 1 + δ − 1 log ( n / δ ) ) O(1+\delta^{-1}\log(n/\delta)) O ( 1 + δ − 1 log ( n / δ )) endpoints. Its cutoffs attain γ ( M ) / ( 1 + δ ) \gamma(M)/(1+\delta) γ ( M ) / ( 1 + δ ) on every law.
Indeed, let c c c be the grid optimum, so c ≥ γ ( M ) c \ge\gamma(M) c ≥ γ ( M ) . Both T D T_D T D and R M R_M R M are nondecreasing concave functions of v v v that vanish at zero. For the latter, differentiating the Bernoulli expectation gives
R M ′ ( v ) = ∑ e S e M ( v ) , R'_M(v) = \sum_e S^M_e(v), R M ′ ( v ) = e ∑ S e M ( v ) ,
which is nonincreasing. Between successive endpoints use monotonicity of T D T_D T D and R M ( v i + 1 ) ≤ ( 1 + δ ) R M ( v i ) R_M(v_{i+1}) \le(1+\delta)R_M(v_i) R M ( v i + 1 ) ≤ ( 1 + δ ) R M ( v i ) . Below v 1 v_1 v 1 , let n 0 n_0 n 0 be the number of nonloops. The first two inclusion–exclusion terms for sampling at least one nonloop give R M ( v 1 ) ≥ n 0 v 1 ( 1 − δ / 2 ) R_M(v_1) \ge n_0v_1(1-\delta/2) R M ( v 1 ) ≥ n 0 v 1 ( 1 − δ /2 ) . Now T D ( v ) ≥ v T D ( v 1 ) / v 1 T_D(v) \ge vT_D(v_1)/v_1 T D ( v ) ≥ v T D ( v 1 ) / v 1 , R M ( v ) ≤ n 0 v R_M(v) \le n_0v R M ( v ) ≤ n 0 v , and 1 − δ / 2 ≥ 1 / ( 1 + δ ) 1-\delta/2 \ge1/(1+\delta) 1 − δ /2 ≥ 1/ ( 1 + δ ) .
Decision prices on random restrictions
The flow follows minors under a particular policy. A different identity compares the optimal policy and the prophet on the same random restrictions. Let μ = E X \mu= \mathbb{E}X μ = E X and ϕ ( t ) = E ( X − t ) + \phi(t) = \mathbb{E}(X-t)_+ ϕ ( t ) = E ( X − t ) + . For a nonloop e e e of a minor N N N , define
w e = V N ∖ e ( F ) − V N / e ( F ) w_e = V_{N\setminus e}(F) - V_{N/e}(F) w e = V N ∖ e ( F ) − V N / e ( F )
and let Z e Z_e Z e be the difference between the realized offline optima in the same two minors, with identical draws on their common labels. The optimal online rule compares X e X_e X e with w e w_e w e . The prophet can compare X e X_e X e with Z e Z_e Z e after seeing the other weights. Put w e = Z e = 0 w_e = Z_e = 0 w e = Z e = 0 on loops.
For 0 ≤ s ≤ ℓ ≤ n 0 \le s \le\ell\le n 0 ≤ s ≤ ℓ ≤ n , take disjoint uniform sets of s s s contractions and ℓ − s \ell-s ℓ − s deletions. Write N ℓ s N_{\ell s} N ℓ s for the resulting minor and v ℓ s = E V N ℓ s ( F ) v_{\ell s} = \mathbb{E}V_{N_{\ell s}}(F) v ℓ s = E V N ℓ s ( F ) . When ℓ < n \ell< n ℓ < n , let e e e be a uniform remaining label and A e A_e A e the event that e e e is neither a loop nor a coloop in this minor.
Theorem 30 (Prices in random minors). For the uniform label in N ℓ s N_{\ell s} N ℓ s ,
E w e = v ℓ + 1 , s − v ℓ + 1 , s + 1 , \mathbb{E}w_e = v_{\ell+1,s} - v_{\ell+1,s+1}, E w e = v ℓ + 1 , s − v ℓ + 1 , s + 1 , v ℓ s − v ℓ + 1 , s = Pr ( e is a coloop ) μ + E [ 1 A e ϕ ( w e ) ] . v_{\ell s} - v_{\ell+1,s} = \Pr(e\text{ is a coloop})\mu+ \mathbb{E}[\mathbf{1}_{A_e}\phi(w_e)]. v ℓ s − v ℓ + 1 , s = Pr ( e is a coloop ) μ + E [ 1 A e ϕ ( w e )] . In particular, let N k N_k N k be the restriction to a uniform k k k -element set. With the expectations in the sums taken over N k N_k N k and its uniform label,
V M ( F ) = r ( M ) μ + ∑ k = 1 n E [ 1 A e ϕ ( w e ) ] , V_M(F) = r(M)\mu+ \sum_{k=1}^{n}\mathbb{E}[\mathbf{1}_{A_e}\phi(w_e)], V M ( F ) = r ( M ) μ + k = 1 ∑ n E [ 1 A e ϕ ( w e )] , P M ( F ) = r ( M ) μ + ∑ k = 1 n E [ 1 A e ϕ ( Z e ) ] . P_M(F) = r(M)\mu+ \sum_{k=1}^{n}\mathbb{E}[\mathbf{1}_{A_e}\phi(Z_e)]. P M ( F ) = r ( M ) μ + k = 1 ∑ n E [ 1 A e ϕ ( Z e )] .
Proof. Deleting the uniform label gives the law of N ℓ + 1 , s N_{\ell+1,s} N ℓ + 1 , s . Contracting it gives the law of N ℓ + 1 , s + 1 N_{\ell+1,s+1} N ℓ + 1 , s + 1 . The two minors coincide on a loop, so averaging the definition of w e w_e w e proves the first identity. By the Bellman equation, on a nonloop the optimal rule gains ϕ ( w e ) \phi(w_e) ϕ ( w e ) in expectation over the deletion continuation. A loop adds zero. A coloop adds μ \mu μ since its two continuation minors agree. Averaging proves the second identity. For the prophet, condition on the other weights. The gain from a nonloop is now ϕ ( Z e ) \phi(Z_e) ϕ ( Z e ) , again equal to μ \mu μ on a coloop.
Set s = 0 s=0 s = 0 and add these identities along successive uniform deletions. The continuation values telescope. The rank drops by one precisely when the deleted label is a coloop, so the sum of the coloop probabilities is r ( M ) r(M) r ( M ) . This gives both decompositions. □
Finite precision and polynomial running time
We now implement the ideal policy with a deterministic bound on all random-bit and arithmetic work. The distributions are explicit lists of nonnegative rational values and rational probabilities. Let L L L be their total binary encoding length and s i n s_{\mathrm{in}} s in the number of support entries. Zero-probability entries may be removed. The parameters are fixed rational constants; choose δ \delta δ dyadic, as in Appendix § 15 .
The statistical estimates cost at most ρ F 0 \rho F_0 ρ F 0 in expected reward. We give the implementation an additional budget of ρ F 0 \rho F_0 ρ F 0 . A uniform coupling conditional on the actual values will let us charge an implementation discrepancy to the realized offline optimum.
Rational encodings
Let D X D_X D X and D v D_v D v be the products of the input probability and value denominators, respectively. Their bit lengths are O ( L ) O(L) O ( L ) . At a queried reference q = u / w q = u/w q = u / w , every reference tail and atom probability has denominator dividing d p = w D X d_p = wD_X d p = w D X . Every joint layer weight can be placed over the common denominator D v d p n D_vd_p^n D v d p n , so
V q = v D v d p n V_q = \frac{v}{D_vd_p^n} V q = D v d p n v
for an integer v v v of polynomial bit length. Thus the joint sampling table has at most N s i n Ns_{\mathrm{in}} N s in entries, all of polynomial encoding length. Very small probabilities do not create a dependence on their reciprocals.
The averages can be accumulated using integer counters:
F ^ = V q m k F , D ^ = V q m k D , m ^ e = V q m k e , C ^ = V q m d p k C . \widehat{F} = \frac{V_q}{m}k_F,\qquad\widehat{D} = \frac{V_q}{m}k_D,\qquad\widehat{m}_e = \frac{V_q}{m}k_e,\qquad\widehat{C} = \frac{V_q}{md_p}k_C. F = m V q k F , D = m V q k D , m e = m V q k e , C = m d p V q k C .
Here k F , k D ≤ m N k_F,k_D \le mN k F , k D ≤ m N , k e ≤ m k_e \le m k e ≤ m , and k C ≤ m N d p k_C \le mNd_p k C ≤ m N d p . For the last counter, a sampled coloop contributes the integer d p ( 1 − p e , j ) d_p(1-p_{e,j}) d p ( 1 − p e , j ) . Thus averaging m m m samples adds only O ( log m ) O(\log m) O ( log m ) bits. The affine discount and thresholds have polynomial encoding length.
If the denominator of δ \delta δ is 2 d 2^d 2 d , every parameter formed by at most N K NK N K midpoint operations has denominator dividing 2 d + N K 2^{d+NK} 2 d + N K . Thus its encoding length is O ( d + N K ) O(d+NK) O ( d + N K ) , independently of the numerical estimates. The input distributions on surviving labels never change. Thus the encodings have polynomial length over the entire run.
A bounded categorical primitive
Let S = N K m S = NKm S = N K m , which bounds all layer samples on every execution. Set
T = ⌈ log 2 8 N ρ ⌉ , C c a t = S ( N + 2 ) + N 2 ( 1 + T ) + 2 N + N T , J 0 = N s i n + N + T + 3. T = \left\lceil\log_2\frac{8N}{\rho}\right\rceil,\qquad C_{\mathrm{cat}} = S(N+2) + N^2(1+T) + 2N + NT,\qquad J_0 = Ns_{\mathrm{in}} + N + T + 3. T = ⌈ log 2 ρ 8 N ⌉ , C cat = S ( N + 2 ) + N 2 ( 1 + T ) + 2 N + N T , J 0 = N s in + N + T + 3.
Choose G = 2 ℓ b i t G = 2^{\ell_{\mathrm{bit}}} G = 2 ℓ bit so that
G δ ∈ Z , G ≥ 2 ( 4 N 2 + C c a t J 0 ) ρ . (45) G\delta\in\mathbb{Z},\qquad G \ge\frac{2(4N^2+C_{\mathrm{cat}}J_0)}{\rho}. \tag*{(45)} G δ ∈ Z , G ≥ ρ 2 ( 4 N 2 + C cat J 0 ) . (45)
Every auxiliary draw uses exactly ℓ b i t \ell_{\mathrm{bit}} ℓ bit fair bits to obtain an integer J J J uniform on { 0 , … , G − 1 } \{0,\ldots,G-1\} { 0 , … , G − 1 } . For rational category probabilities p 1 , … , p k p_1,\ldots,p_k p 1 , … , p k , form their cumulative sums and return the first i i i for which ∑ j ≤ i p j > J / G \sum_{j\le i}p_j > J/G ∑ j ≤ i p j > J / G . This uses exact rational comparisons. Zero-probability categories are never returned. The primitive covers reference coordinates, layer choices, Bernoulli screens, and probe prefixes.
For an arrival in the early phase of the continuation, draw the probe count from { 0 , … , T } \{0,\ldots,T\} { 0 , … , T } with probabilities proportional to the rational weights 2 k / k ! 2^k/k! 2 k / k ! . These are the probabilities of a Poisson random variable of mean two conditioned to be at most T T T . They may be represented by the integer weights 2 k T ! / k ! 2^kT!/k! 2 k T ! / k ! . The implementation therefore requires neither exact exponential evaluations nor an unbounded count sampler.
Arrival clocks use the one-based grid ( J + 1 ) / G (J+1)/G ( J + 1 ) / G : draw one clock for each residual label, sort them, and assign them in order to the actual arrivals. For a raw probe use a fresh zero-based draw and set u = 2 q J / G u=2qJ/G u = 2 q J / G ; test the corresponding prefix only when u < s u<s u < s , where s s s is the current arrival clock. Keep repeated arrival clocks. Candidate realizations replay all preceding records in their append order. A probe replays the records whose clocks are at most u u u , also in append order. Every candidate basis therefore contains all preceding acceptances, even on executions with equal clocks, and feasibility is unconditional.
Lemma 31 (Categorical approximation). An exact categorical draw with k k k categories and the bounded-bit draw can be coupled to disagree with probability at most ( k − 1 ) / G (k-1)/G ( k − 1 ) / G . For ordered nonnegative integer categories the bounded-bit draw is no larger than the exact draw under this coupling.
Proof. Use the same uniform U ∈ [ 0 , 1 ) U\in[0,1) U ∈ [ 0 , 1 ) and let J = ⌊ G U ⌋ J=\lfloor GU\rfloor J = ⌊ G U ⌋ . A discrepancy requires an interior cumulative boundary between J / G J/G J / G and U U U . Each of the k − 1 k-1 k − 1 boundaries contributes probability at most 1 / G 1/G 1/ G . The ordering assertion follows because J / G ≤ U J/G\le U J / G ≤ U .
Lemma 32 (Uniform implementation error). For every fixed actual value vector in the positive-probability input supports and every fixed actual arrival permutation, the ideal and finite-bit algorithms can be coupled to make identical acceptance decisions with probability at least 1 − ρ 1-\rho 1 − ρ . Their expected reward difference is consequently at most ρ F 0 \rho F_0 ρ F 0 .
Proof. First round continuous arrival clocks upward to the grid, retaining exact categorical draws and Poisson counts. The probability of a clock collision is at most n ( n − 1 ) / ( 2 G ) n(n-1)/(2G) n ( n − 1 ) / ( 2 G ) ; declare a coupling failure on this event. Otherwise the clock order is preserved. Since the switching time 1 − δ 1-\delta 1 − δ is a grid point, rounding also preserves the early or late phase.
For a raw early probe, list the preceding accepted times as τ 1 ≤ ⋯ ≤ τ k ≤ s \tau_1\le\cdots\le\tau_k\le s τ 1 ≤ ⋯ ≤ τ k ≤ s . Its possible prefix categories have cumulative boundaries
τ 1 2 q , … , τ k 2 q , s 2 q , 1. \frac{\tau_1}{2q},\ldots,\frac{\tau_k}{2q},\frac{s}{2q},1. 2 q τ 1 , … , 2 q τ k , 2 q s , 1.
The strict inverse-CDF convention gives exactly the rule u < s u<s u < s and replay of records at times at most u u u . Rounding a time upward changes each boundary by at most 1 / ( 2 q G ) ≤ 1 / G 1/(2qG)\le1/G 1/ ( 2 q G ) ≤ 1/ G . There are at most n n n boundaries, so a probe changes category with conditional probability at most n / G n/G n / G . A Poisson count has mean two. Summing over at most n n n arrivals and including the collision event bounds this first coupling error by 4 N 2 / G 4N^2/G 4 N 2 / G . Before a discrepancy, candidate realizations and basis replays can be coupled identically. The bound holds at every possible history at which the continuation is entered and for every fixed actual vector and order.
Next replace each Poisson count Z Z Z by its law conditioned on Z ≤ T Z\le T Z ≤ T . The moment bound
Pr ( Z > T ) ≤ E 2 Z 2 T + 1 = e 2 2 T + 1 < 4 2 − T \Pr(Z>T)\le\frac{\mathbb{E}2^Z}{2^{T+1}}=\frac{e^2}{2^{T+1}}<4\,2^{-T} Pr ( Z > T ) ≤ 2 T + 1 E 2 Z = 2 T + 1 e 2 < 4 2 − T
gives error at most 4 N 2 − T ≤ ρ / 2 4N2^{-T}\le\rho/2 4 N 2 − T ≤ ρ /2 over the run. Couple counts identically when Z ≤ T Z\le T Z ≤ T ; otherwise generate a fresh conditional count and declare failure. This has the required conditional marginal. Finally replace all rational categorical draws by the bounded-bit primitive. There are at most C c a t C_{\mathrm{cat}} C cat draws: each layer uses at most N + 2 N+2 N + 2 ; the at most N ( 1 + T ) N(1+T) N ( 1 + T ) reference realizations used by the continuation use at most N N N coordinate draws each; and the remaining draws comprise at most N N N screens, N N N counts, and N T NT N T prefixes. Every category list has size at most J 0 J_0 J 0 . Until the first discrepancy, histories and the next categorical laws coincide. A conditional union bound and Lemma 31 give error at most C c a t J 0 / G C_{\mathrm{cat}}J_0/G C cat J 0 / G . Combining the three steps with (C.1) proves total error at most ρ \rho ρ .
On the failed coupling, the ideal algorithm’s possible advantage is at most the realized integral optimum: both algorithms are feasible and have nonnegative reward. The failure bound is uniform conditional on the actual values. Averaging therefore loses at most ρ F 0 \rho F_0 ρ F 0 , with no range restriction on those values.
Running time
Every arithmetic operand has polynomial bit length, every categorical draw uses a fixed number of bits, and each probe count is at most T T T . The Poisson integer weights have O ( T log ( T + 2 ) ) O(T\log(T+2)) O ( T log ( T + 2 )) bits. Thus all loops and all arithmetic work have polynomial worst-case bounds in N , L N,L N , L . For fixed parameters, K , T = O ( log ( N + 2 ) ) K,T=O(\log(N+2)) K , T = O ( log ( N + 2 )) , m = O ( N log ( N + 2 ) ) m=O(N\log(N+2)) m = O ( N log ( N + 2 )) , and ℓ b i t = O ( log ( N + 2 ) + log ( s i n + 1 ) ) \ell_{\mathrm{bit}}=O(\log(N+2)+\log(s_{\mathrm{in}}+1)) ℓ bit = O ( log ( N + 2 ) + log ( s in + 1 )) .
The outer policy uses O ( N 3 log 3 ( N + 2 ) ) O(N^3\log^3(N+2)) O ( N 3 log 3 ( N + 2 )) matroid independence queries. A fresh reference realization requires one greedy basis computation and at most n n n exchange replays. The canonical shrinking scan costs O ( n 2 ) O(n^2) O ( n 2 ) queries per replay, so a reference realization costs O ( n 3 ) O(n^3) O ( n 3 ) queries. There is at most one continuation. The bounded-bit count is no larger, in the categorical coupling, than a Poisson count conditioned on being at most T T T ; its mean is at most two. Thus the continuation algorithm evaluates O ( N ) O(N) O ( N ) reference realizations in expectation and at most N ( 1 + T ) = O ( N log ( N + 2 ) ) N(1+T)=O(N\log(N+2)) N ( 1 + T ) = O ( N log ( N + 2 )) reference realizations on every outcome. The resulting total query bounds are
O ( N 4 ) in expectation , O ( N 4 log ( N + 2 ) ) in the worst case . O(N^4) \quad\text{in expectation}, \qquad O\bigl(N^4\log(N+2)\bigr) \quad\text{in the worst case}. O ( N 4 ) in expectation , O ( N 4 log ( N + 2 ) ) in the worst case .
In particular, when matroid independence queries themselves take polynomial time, this is a polynomial-time algorithm in the complete rational input model.
Certifying the general matroid bound
The algorithm uses the rational parameters
δ = 7 4096 , θ = 367878301 10 9 , η = 247 5000 , s = 5 2 , ε = 10 − 6 , ρ = ε 3 , ε 0 = 1.14 ⋅ 10 − 6 . (46) \delta=\frac{7}{4096},\quad\theta=\frac{367878301}{10^9},\quad\eta=\frac{247}{5000},\quad s=\frac{5}{2},\quad\varepsilon=10^{-6},\quad\rho=\varepsilon^3,\quad\varepsilon_0=1.14\cdot10^{-6}. \tag*{(46)} δ = 4096 7 , θ = 1 0 9 367878301 , η = 5000 247 , s = 2 5 , ε = 1 0 − 6 , ρ = ε 3 , ε 0 = 1.14 ⋅ 1 0 − 6 . (46)
Two observations allow a slightly better choice of θ \theta θ . The threshold step is used only for ∣ q − 1 ∣ < 3 δ |q-1|<3\delta ∣ q − 1∣ < 3 δ . Also, although the curves a ( q ) a(q) a ( q ) and 1 − e − 1 / q 1-e^{-1/q} 1 − e − 1/ q are nearly tangent at q = 1 q=1 q = 1 , their gap decreases quadratically away from that point. We retain this quadratic term when checking the continuation near the middle of J J J .
Lemma 33 (Parameter choice). The parameters in (D.1) satisfy (5) and the three branch conditions (31) –(33) . Throughout J J J one has w > 0 w>0 w > 0 and q ( b + s ) > 1 q(b+s)>1 q ( b + s ) > 1 . Moreover, 1 − θ − 2 ρ > 1 − 1 / e + ε 0 1-\theta-2\rho>1-1/e+\varepsilon_0 1 − θ − 2 ρ > 1 − 1/ e + ε 0 .
Proof. Write u = e − 1 u=e^{-1} u = e − 1 . We use the rational enclosures
u − : = 36787944117 10 11 < u < 36787944118 10 11 = : u + , e − 5 / 2 < 821 10000 . u_-:=\frac{36787944117}{10^{11}}<u<\frac{36787944118}{10^{11}}=:u_+,\qquad e^{-5/2}<\frac{821}{10000}. u − := 1 0 11 36787944117 < u < 1 0 11 36787944118 =: u + , e − 5/2 < 10000 821 .
For the first, bound e e e between ∑ j = 0 16 1 / j ! \sum_{j=0}^{16}1/j! ∑ j = 0 16 1/ j ! and that sum plus 2 / 17 ! 2/17! 2/17 ! . For the second, use the first eleven terms of the positive series for e 5 / 2 e^{5/2} e 5/2 . The basic restrictions and q ( b + s ) > 1 q(b+s)>1 q ( b + s ) > 1 follow from 0.99 < q < 1.01 0.99<q<1.01 0.99 < q < 1.01 , 0.36 < θ < 0.37 0.36<\theta<0.37 0.36 < θ < 0.37 , and (D.1). The final ratio follows from u − − θ − 2 ρ > 1.14 ⋅ 10 − 6 u_{-}-\theta-2\rho>1.14\cdot10^{-6} u − − θ − 2 ρ > 1.14 ⋅ 1 0 − 6 .
Put a 0 ( q ) = 1 − e − 1 / q a_0(q)=1-e^{-1/q} a 0 ( q ) = 1 − e − 1/ q . Its curvature on J J J satisfies a 0 ′ ′ ( q ) = e − 1 / q ( 2 q − 1 ) / q 4 > 1 / 3 a_0''(q)=e^{-1/q}(2q-1)/q^4>1/3 a 0 ′′ ( q ) = e − 1/ q ( 2 q − 1 ) / q 4 > 1/3 : here e − 1 / q ≥ u ( 1 − 1 / 99 ) > 0.36 e^{-1/q}\ge u(1-1/99)>0.36 e − 1/ q ≥ u ( 1 − 1/99 ) > 0.36 . Since a − a 0 a-a_0 a − a 0 and its derivative both equal u − θ u-\theta u − θ at 1 1 1 ,
a ( q ) − a 0 ( q ) ≤ q ( u − θ ) − ( q − 1 ) 2 / 6. (47) a(q)-a_0(q)\le q(u-\theta)-(q-1)^2/6. \tag*{(47)} a ( q ) − a 0 ( q ) ≤ q ( u − θ ) − ( q − 1 ) 2 /6. (47)
Let x = λ δ x=\lambda\delta x = λ δ , so e − λ = α e − x e^{-\lambda}=\alpha e^{-x} e − λ = α e − x and α / ω = 1 + x / ω \alpha/\omega=1+x/\omega α / ω = 1 + x / ω . Applying 1 − e − t ≥ t − t 2 / 2 1-e^{-t}\ge t-t^2/2 1 − e − t ≥ t − t 2 /2 at t = x / ω t=x/\omega t = x / ω and e − x ≥ 1 − x + x 2 / 2 − x 3 / 6 e^{-x}\ge1-x+x^2/2-x^3/6 e − x ≥ 1 − x + x 2 /2 − x 3 /6 in (19) gives, for z ≥ 0 z\ge0 z ≥ 0 ,
Φ δ ( q , z ) − a 0 ( q ) ≥ − x 2 ( 1 − α 2 + x 2 ω + α x 6 ) + x α ( 1 − α ) ( 1 − x 2 ω ) z . (48) \Phi_\delta(q,z)-a_0(q)\ge-x^2\left(\frac{1-\alpha}{2}+\frac{x}{2\omega}+\frac{\alpha x}{6}\right)
+x\alpha(1-\alpha)\left(1-\frac{x}{2\omega}\right)z. \tag*{(48)} Φ δ ( q , z ) − a 0 ( q ) ≥ − x 2 ( 2 1 − α + 2 ω x + 6 α x ) + xα ( 1 − α ) ( 1 − 2 ω x ) z . (48)
It remains to bound rational expressions on intervals. Partition J J J at the points 1 + i δ / 32 1+i\delta/32 1 + i δ /32 , − 128 ≤ i ≤ 128 -128\le i\le128 − 128 ≤ i ≤ 128 . For consecutive endpoints l , r l,r l , r , put
A = u − ( 2 − 1 − δ l ) , H = u + r 1 − δ , X = δ l , W = A − X . A=u_{-}\left(2-\frac{1-\delta}{l}\right),\qquad H=\frac{u_{+}r}{1-\delta},\qquad X=\frac{\delta}{l},\qquad W=A-X. A = u − ( 2 − l 1 − δ ) , H = 1 − δ u + r , X = l δ , W = A − X .
The inequalities 1 + y ≤ e y ≤ 1 / ( 1 − y ) 1+y\le e^y\le1/(1-y) 1 + y ≤ e y ≤ 1/ ( 1 − y ) for y < 1 y<1 y < 1 , applied at y = 1 − ( 1 − δ ) / q y=1-(1-\delta)/q y = 1 − ( 1 − δ ) / q , give A ≤ α ≤ H A\le\alpha\le H A ≤ α ≤ H . Every interval has 0 < A < H < 1 / 2 0<A<H<1/2 0 < A < H < 1/2 and W > X > 0 W>X>0 W > X > 0 , so ω ≥ W > 0 \omega\ge W>0 ω ≥ W > 0 . Since t ( 1 − t ) t(1-t) t ( 1 − t ) increases on [ 0 , 1 / 2 ] [0,1/2] [ 0 , 1/2 ] , define
C = 1 l 2 ( 1 − A 2 + X 2 W + H X 6 ) , B = A ( 1 − A ) r ( 1 − X 2 W ) . C=\frac{1}{l^2}\left(\frac{1-A}{2}+\frac{X}{2W}+\frac{HX}{6}\right),\qquad B=\frac{A(1-A)}{r}\left(1-\frac{X}{2W}\right). C = l 2 1 ( 2 1 − A + 2 W X + 6 H X ) , B = r A ( 1 − A ) ( 1 − 2 W X ) .
Combining (D.2) and (D.3), we obtain Φ δ ( q , z ) − a ( q ) ≥ G + B δ z \Phi_\delta(q,z)-a(q)\ge G+B\delta z Φ δ ( q , z ) − a ( q ) ≥ G + B δ z throughout the interval, with
G = − C δ 2 − r ( u + − θ ) + 1 6 max { l − 1 , 1 − r , 0 } 2 . G=-C\delta^2-r(u_{+}-\theta)+\frac{1}{6}\max\{l-1,1-r,0\}^2. G = − C δ 2 − r ( u + − θ ) + 6 1 max { l − 1 , 1 − r , 0 } 2 .
Also z ∗ ( q ) ≥ z ∗ ( l ) z_*(q)\ge z_*(l) z ∗ ( q ) ≥ z ∗ ( l ) since d ∗ d_* d ∗ increases. For a threshold step, b b b decreases and d ∗ d_* d ∗ increases, so put
P = d ∗ ( l ) + 20 ϵ − 1 + b ( r ) ( 1 − 821 / 10000 ) . P=d_*(l)+20\epsilon-1+b(r)(1-821/10000). P = d ∗ ( l ) + 20 ϵ − 1 + b ( r ) ( 1 − 821/10000 ) .
Where P > 0 P>0 P > 0 , the left side of (33) minus its right side is at least
T = 1 − b ( l ) + b ( r ) P b ( r ) + s − b ( l ) r ( d ∗ ( r ) + η + 30 ϵ ) − 2 ϵ . T=1-b(l)+\frac{b(r)P}{b(r)+s}-b(l)r(d_*(r)+\eta+30\epsilon)-2\epsilon. T = 1 − b ( l ) + b ( r ) + s b ( r ) P − b ( l ) r ( d ∗ ( r ) + η + 30 ϵ ) − 2 ϵ .
Thus the finite checks in the table suffice. Intervals meeting at a branch boundary are closed, so their endpoints are covered.
Table 1.
Proof of Theorem 1 . First consider explicit finite distributions with rational values and probabilities. Use the parameters in Lemma 33 . Proposition 24 gives the ideal policy expected reward at least ( 1 − θ − ρ ) F 0 (1-\theta-\rho)F_0 ( 1 − θ − ρ ) F 0 . Lemma 32 loses at most another ρ F 0 \rho F_0 ρ F 0 , so the implemented policy obtains ( 1 − θ − 2 ρ ) F 0 > ( 1 − 1 / e + ε 0 ) F 0 (1-\theta-2\rho)F_0 > (1-1/e+\varepsilon_0)F_0 ( 1 − θ − 2 ρ ) F 0 > ( 1 − 1/ e + ε 0 ) F 0 when F 0 > 0 F_0>0 F 0 > 0 . For F 0 = 0 F_0=0 F 0 = 0 the asserted inequality holds trivially. The query bounds and worst-case polynomial arithmetic and random-bit bounds are those of Appendix § 14 .
For general distributions, discard loops and assume F 0 > 0 F_0>0 F 0 > 0 . Put β = 1 − θ − 2 ρ \beta=1-\theta-2\rho β = 1 − θ − 2 ρ and c = 1 − 1 / e + ε 0 c=1-1/e+\varepsilon_0 c = 1 − 1/ e + ε 0 , so β > c \beta>c β > c . For any τ > 0 \tau>0 τ > 0 , truncation and downward rounding to a finite rational grid produce independent Z e ≤ X e Z_e\le X_e Z e ≤ X e , bounded by a rational B B B , with E OPT ( M , Z ) ≥ F 0 − τ \mathbb{E}\operatorname{OPT}(M,Z)\ge F_0-\tau E OPT ( M , Z ) ≥ F 0 − τ . Indeed, the truncated optima increase to the original optimum, and rounding loses at most N N N times the grid width. Approximate each discretized marginal by a positive rational probability vector on the same support. This gives a product distribution Y Y Y whose joint total variation distance from Z Z Z is at most any prescribed γ > 0 \gamma>0 γ > 0 . Here the total variation distance between two distributions P P P and Q Q Q on a finite set is
1 2 ∑ x ∣ P ( x ) − Q ( x ) ∣ \frac{1}{2}\sum_x |P(x)-Q(x)| 2 1 x ∑ ∣ P ( x ) − Q ( x ) ∣
equivalently, it is the minimum probability that coupled draws from P P P and Q Q Q differ.
Run the finite algorithm designed for Y Y Y on the rounded values Z Z Z . Couple Y Y Y and Z Z Z and use the same arrival order and internal randomness. The two rewards coincide whenever their value vectors coincide, and both rewards and both offline optima lie in [ 0 , N B ] [0,NB] [ 0 , N B ] . Hence the expected reward on Z Z Z is at least
β E OPT ( M , Z ) − ( 1 + β ) N B γ ≥ β F 0 − β τ − ( 1 + β ) N B γ . \beta\mathbb{E}\operatorname{OPT}(M,Z)-(1+\beta)NB\gamma\ge\beta F_0-\beta\tau-(1+\beta)NB\gamma. β E OPT ( M , Z ) − ( 1 + β ) N B γ ≥ β F 0 − β τ − ( 1 + β ) N B γ .
At an actual arrival, form Z e Z_e Z e from X e X_e X e and feed it to this policy. The accepted set earns at least its rounded value. Choose τ \tau τ and then γ \gamma γ so that β τ + ( 1 + β ) N B γ < ( β − c ) F 0 \beta\tau+(1+\beta)NB\gamma<(\beta-c)F_0 β τ + ( 1 + β ) N B γ < ( β − c ) F 0 . This proves the same factor c c c for general distributions. Only the explicit finite rational model is used in the computational claim.