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 [14 ] 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.
Problem definitions
Matroid prophet secretary. A matroid M = ( E , I ) M = (E,\mathcal{I}) M = ( E , I ) consists of a finite ground set E E E and a nonempty family I ⊆ 2 E \mathcal{I} \subseteq2^E I ⊆ 2 E of independent sets. The family is hereditary: every subset of a set in I \mathcal{I} I also belongs to I \mathcal{I} I . It satisfies the augmentation axiom: if I , J ∈ I I,J \in\mathcal{I} I , J ∈ I and ∣ I ∣ < ∣ J ∣ |I| < |J| ∣ I ∣ < ∣ J ∣ , there is an element e ∈ J ∖ I e \in J \setminus I e ∈ J ∖ I with I ∪ { e } ∈ I I \cup\{e\} \in\mathcal{I} I ∪ { e } ∈ I . A basis is an inclusionwise maximal independent set; all bases have the same size, called the rank of the matroid. For nonnegative weights, the greedy algorithm scans elements in decreasing weight order and adds an element whenever independence is preserved. A fixed label order breaks ties and specifies a canonical maximum-weight basis.
The matroid and its N = ∣ E ∣ N = |E| N = ∣ E ∣ labeled elements are known in advance. Each element e e e has a nonnegative value X e X_e X e drawn independently from a known distribution. The elements arrive in a uniformly random order, independent of the values. At an arrival the algorithm observes the element’s label and value and must accept or reject it immediately and irrevocably. The accepted set must remain independent. Its reward is the sum of the accepted values, and the expected offline benchmark is
F 0 = E [ max I ∈ I ∑ e ∈ I X e ] . F_0 = \mathbb{E}\left[\max_{I \in\mathcal{I}} \sum_{e \in I} X_e\right]. F 0 = E [ I ∈ I max e ∈ I ∑ X e ] .
A matroid independence oracle answers whether a queried subset S ⊆ E S \subseteq E S ⊆ E belongs to I \mathcal{I} I ; queries may involve elements that have not arrived. For the computational result, each distribution is given explicitly as a finite list of rational values and rational probabilities. Oracle calls are counted separately from arithmetic operations and random bits. Prophet secretary for combinatorial auctions. There is a fixed item set U U U and a known set of buyers. Each buyer i i i has a valuation v i : 2 U → R ≥ 0 v_i:2^U \to\mathbb{R}_{\ge0} v i : 2 U → R ≥ 0 drawn independently from a known distribution. Buyers arrive in uniformly random order, independently of their valuations. When buyer i i i arrives, the algorithm observes v i v_i v i and irrevocably assigns her a bundle S i S_i S i of previously unallocated items. The objective is social welfare , ∑ i v i ( S i ) \sum_i v_i(S_i) ∑ i v i ( S i ) . The offline optimum OPT maximizes this sum over all pairwise disjoint bundles after seeing every valuation.
A valuation is XOS if it is the maximum of finitely many nonnegative additive functions:
v ( S ) = max ℓ ∈ L ∑ j ∈ S w ℓ , j , w ℓ , j ≥ 0. v(S)=\max_{\ell\in\mathcal{L}}\sum_{j\in S}w_{\ell,j},\qquad w_{\ell,j}\ge0. v ( S ) = ℓ ∈ L max j ∈ S ∑ w ℓ , j , w ℓ , j ≥ 0.
The functions indexed by ℓ ∈ L \ell\in\mathcal{L} ℓ ∈ L are its additive clauses . A clause attaining the maximum on S S S is a supporting clause for S S S . Such valuations are normalized, meaning v ( ∅ ) = 0 v(\varnothing)=0 v ( ∅ ) = 0 , and monotone, meaning v ( S ) ≤ v ( T ) v(S)\le v(T) v ( S ) ≤ v ( T ) whenever S ⊆ T S\subseteq T S ⊆ T . Independence is required across buyers’ valuation functions, not across the values that one function assigns to different bundles.
Competitive ratio. In either model, write ALG for the realized reward or welfare. We call an algorithm α \alpha α -competitive, for α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] , if E [ A L G ] ≥ α E [ O P T ] \mathbb{E}[\mathrm{ALG}]\ge\alpha\mathbb{E}[\mathrm{OPT}] E [ ALG ] ≥ α E [ OPT ] on every instance with finite expected optimum. In the matroid model, E [ O P T ] = F 0 \mathbb{E}[\mathrm{OPT}]=F_0 E [ OPT ] = F 0 . The expectation is over the input values or valuations, the arrival order, and the algorithm’s randomness. Thus larger competitive ratios are better.
Our results
Ehsani, Hajiaghayi, Kesselheim, and Singla [12 ] established the same competitive ratio, 1 − 1 / e 1-1/e 1 − 1/ e , for both models. Their analysis explains this guarantee through time-dependent thresholds and an exponential bound on the loss of available value. It leaves a natural question: does the common guarantee reflect the inherent difficulty of both problems?
The single-choice case already admits a better competitive ratio. Azar, Chiplunkar, and Kaplan [3 ] surpassed 1 − 1 / e 1-1/e 1 − 1/ e , and subsequent work obtained further improvements [8 , 7 ] . For a general matroid, however, the algorithm must account for the interactions among many accepted elements. Our main result uses the matroid exchange structure to obtain a strict improvement for every matroid.
Theorem 1 (Matroid prophet secretary). For ε 0 = 1.01 ⋅ 10 − 6 \varepsilon_0=1.01\cdot10^{-6} ε 0 = 1.01 ⋅ 1 0 − 6 , every matroid on N N N elements with independent nonnegative values and finite F 0 F_0 F 0 admits a randomized online algorithm satisfying
E [ A L G ] ≥ ( 1 − 1 e + ε 0 ) F 0 . \mathbb{E}[\mathrm{ALG}]\ge\left(1-\frac{1}{e}+\varepsilon_0\right)F_0. E [ ALG ] ≥ ( 1 − e 1 + ε 0 ) F 0 . For explicitly given finite distributions with rational values and probabilities and access to a matroid independence oracle, the expected number of matroid independence queries is O ( N 4 ) O(N^4) O ( N 4 ) and the worst-case number is O ( N 4 log ( N + 2 ) ) O(N^4\log(N+2)) O ( N 4 log ( N + 2 )) . Its arithmetic work and number of random bits are polynomial in N N N and the total binary encoding length of the distributions on every execution.
The theorem applies to arbitrary matroids. Its guarantee has no dependence on rank, on the number of possible values, or on their numerical range. The computational statement uses the full explicit input length; it is not a claim about access only to a sampling oracle. The existence guarantee for general distributions follows by approximation. We keep all algorithmic parameters symbolic until § 15 , where an explicit rational choice is verified with positive slack in every required inequality.
For combinatorial auctions with XOS valuations, the same improvement is impossible. Our second result gives a matching upper bound on the competitive ratio, even when the buyers’ valuation functions are drawn independently from one common finite distribution.
Theorem 2 (Sharpness for combinatorial auctions with XOS valuations). For every ξ > 0 \xi> 0 ξ > 0 , there is a finite prophet-secretary instance with XOS valuations on which every randomized online algorithm satisfies
E [ A L G ] < ( 1 − 1 e + ξ ) E [ O P T ] . \mathbb{E}[\mathrm{ALG}] < \left(1-\frac{1}{e}+\xi\right)\mathbb{E}[\mathrm{OPT}]. E [ ALG ] < ( 1 − e 1 + ξ ) E [ OPT ] . The buyers’ valuations may be drawn independently from the same finitely supported distribution, and every additive clause may have coefficients in { 0 , 1 } \{0,1\} { 0 , 1 } . The conclusion holds even if all clauses and the entire arrival permutation are given in advance and computation is unrestricted.
Together with [12 ] , this identifies 1 − 1 / e 1 - 1/e 1 − 1/ e as the optimal competitive ratio for prophet secretary with XOS valuations. The same upper bound follows from Udwani and Wajc’s result for online welfare maximization with coverage valuations under independent and identically distributed (i.i.d.) item arrivals from a known distribution [29 ] . In that problem, each arriving item is assigned to one of a fixed set of buyers, whose value is the total weight of the objects covered by her assigned items, with each object counted once. A transformation that exchanges the roles of arriving items and buyers yields our model; it is related to the coverage-to-XOS construction of Chawla and Dang [6 ] . We state this implication explicitly and give a direct proof. The obstruction is informational: an online allocation commits to a supporting additive clause before the later types determine which clauses fit together. Offline approximation hardness alone would not imply this statement.
Our Approach and Techniques
To see why matroid prophet secretary and prophet secretary with XOS valuations separate at 1 − 1 / e 1 - 1/e 1 − 1/ e , recall the unified ( 1 − 1 / e ) (1 - 1/e) ( 1 − 1/ e ) analysis of Ehsani, Hajiaghayi, Kesselheim, and Singla [12 ] . The ( 1 − 1 / e ) (1 - 1/e) ( 1 − 1/ e ) guarantee in random-order prophet models suggests two complementary paradigms: posted thresholds , which extract enough surplus above each element’s replacement cost to offset the offline value lost by accepting it, and online contention-resolution schemes , which select a feasible subset of random candidates as they arrive. Our continuation uses additional random rejections of early candidates to maintain a uniform bound on the rate at which any reference-optimum element is blocked. This gives exponential survival until a short final interval, where the algorithm removes these rejections to exploit stable overlap.
Pushing either paradigm past 1 − 1 / e 1 - 1/e 1 − 1/ e on a matroid runs into two opposite regimes. In a volatile regime , rare, high-value realizations make the surplus lost by deleting an element unstable across independent draws. The baseline survival analysis gives only 1 − 1 / e 1 - 1/e 1 − 1/ e . A threshold rule can nevertheless gain surplus from elements that clear their deterministic prices even when they do not belong to the offline optimal basis. These additional contributions matter because the rule processes only the next arrival: its expected surplus is the average of the individual elements’ expected surpluses, so these elements need not be simultaneously feasible. We choose the reference distribution so that this surplus covers the expected decrease in the residual benchmark, with the slack needed for a strict improvement.
In a persistent regime , a core of reliable elements repeatedly enters the offline optimal basis B ( X ) B(X) B ( X ) across independent draws (here X = ( X e ) e ∈ E X = (X_e)_{e \in E} X = ( X e ) e ∈ E , a basis is a maximal independent set, and B ( y ) B(y) B ( y ) denotes the maximum-weight basis for weights y y y , with a fixed label order breaking ties); here collisions between persistent winners make it useful to exploit the substantial overlap between independent optimal bases through an adaptive contention-resolution scheme near the end of the horizon. Our matroid algorithm (Theorem 1 ) turns this tension into a step-by-step win-win dichotomy, whereas our XOS lower bound (Theorem 2 ) shows that general combinatorial auctions with XOS valuations can force an early commitment to incompatible global completions.
Part I: Beating 1 − 1 / e 1 - 1/e 1 − 1/ e for Matroid Prophet Secretary (Theorem 1 )
Deletion surplus, tail-rescaled reference distributions, and potential-driven search.
As elements of an N N N -element matroid arrive in random order, each outer threshold step contracts the matroid when accepting an element e e e (M / e M/e M / e ) and deletes it when rejecting it (M ∖ e M \setminus e M ∖ e ). Deletion forbids using e e e ; contraction declares I ⊆ E ∖ { e } I \subseteq E \setminus\{e\} I ⊆ E ∖ { e } independent exactly when I ∪ { e } I \cup\{e\} I ∪ { e } was independent before the contraction. Loops, elements belonging to no independent set, are discarded.
The matroid obtained by these contractions and deletions is the residual minor . In a residual minor M = ( E , I ) M = (E,\mathcal{I}) M = ( E , I ) of size n = ∣ E ∣ ≤ N n = \lvert E\rvert\leq N n = ∣ E ∣ ≤ N with a reference product distribution Y = ( Y e ) e ∈ E Y = (Y_e)_{e\in E} Y = ( Y e ) e ∈ E , meaning that its coordinates are independent, write OPT ( M , y ) = max I ∈ I ∑ f ∈ I y f \operatorname{OPT}(M,y) = \max_{I\in\mathcal{I}} \sum_{f\in I} y_f OPT ( M , y ) = max I ∈ I ∑ f ∈ I y f and let Y − e Y_{-e} Y − e omit coordinate e e e .
Each element e e e has an exclusion threshold τ 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 ) —the critical weight for e e e to enter the greedy basis B ( Y ) B(Y) B ( Y ) , with equality resolved by the fixed tie order—so deleting e e e reduces the offline optimum by OPT ( M , Y ) − OPT ( M ∖ e , Y ) = ( Y e − τ e ) + \operatorname{OPT}(M,Y) - \operatorname{OPT}(M \setminus e,Y) = (Y_e - \tau_e)^+ OPT ( M , Y ) − OPT ( M ∖ e , Y ) = ( Y e − τ e ) + , where u + = max { u , 0 } u^+ = \max\{u,0\} u + = max { u , 0 } .
Summing d e = E [ ( Y e − τ e ) + ] d_e = \mathbb{E}[(Y_e - \tau_e)^+] d e = E [( Y e − τ e ) + ] over e ∈ E e \in E e ∈ E gives the deletion surplus D = ∑ e d e D = \sum_e d_e D = ∑ e d e , which plays a dual role: rejecting a uniformly random next arrival drops the offline benchmark E [ OPT ( M , Y ) ] \mathbb{E}[\operatorname{OPT}(M,Y)] E [ OPT ( M , Y )] by D / n D/n D / n , while D D D also measures the total surplus above replacement costs.
To test whether this surplus comes from rare spikes or persistent winners, we track its stable part H = ∑ e E [ ( min { Y e , Y e ′ } − τ e ) + ] H = \sum_e \mathbb{E}[(\min\{Y_e,Y'_e\} - \tau_e)^+] H = ∑ e E [( min { Y e , Y e ′ } − τ e ) + ] for a copy Y e ′ Y'_e Y e ′ independent of all coordinates of Y Y Y , keeping the same other-coordinate threshold τ e \tau_e τ e , which measures how much of D D D survives when each element’s weight is drawn twice independently. Even when H H H is tiny under the true distribution X X X , however, this alone does not guarantee that the surplus of a one-step threshold rule covers the benchmark loss D / n D/n D / n .
At each residual minor M M M with positive expected optimum, we choose a nearby reference distribution under which the threshold rule can be compared with the loss in the offline benchmark. Zero-value states terminate. The reference distributions are Y q Y^q Y q , for q ∈ J = [ 1 − 4 δ , 1 + 4 δ ] q \in\mathcal{J} = [1 - 4\delta, 1 + 4\delta] q ∈ J = [ 1 − 4 δ , 1 + 4 δ ] , where δ \delta δ also specifies the length of the final window of the continuation. Their coordinates are independent and satisfy
p e q ( z ) = Pr [ Y e q > z ] = min { 1 , q Pr [ X e > z ] } , z ≥ 0. p_e^q(z) = \Pr[Y_e^q > z] = \min\{1, q\Pr[X_e > z]\}, \qquad z \geq0. p e q ( z ) = Pr [ Y e q > z ] = min { 1 , q Pr [ X e > z ]} , z ≥ 0.
Thus Y 1 Y^1 Y 1 is the original distribution. For q < 1 q < 1 q < 1 , the same distribution is obtained by independently replacing each value by zero with probability 1 − q 1 - q 1 − q . For q > 1 q > 1 q > 1 , every upper-tail probability is increased by the factor q q q until it reaches one. In particular, the occurrence probability of an unsaturated high-value event changes proportionally with q q q .
Write F q = F q ( M ) F_q = F_q(M) F q = F q ( M ) , where F q ( M ′ ) = E [ OPT ( M ′ , Y q ) ] F_q(M') = \mathbb{E}[\operatorname{OPT}(M',Y^q)] F q ( M ′ ) = E [ OPT ( M ′ , Y q )] for a minor M ′ M' M ′ , using the reference values on its remaining labels. As q q q increases, the expected optimum is nondecreasing, while competition between elements for inclusion in an optimal basis can increase. The useful feature of this rescaling is that the marginal change in F q F_q F q is closely related to the expected value lost when an element is deleted. We make this relation precise below. It allows us to choose a reference parameter for which the threshold surplus and the decrease in the benchmark can be compared quantitatively.
For a fixed reference parameter q q q , we write
d e q = E [ ( Y e q − τ e ( Y − e q ) ) + ] , D q = ∑ e ∈ E d e q , H q = ∑ e ∈ E E [ ( min { Y e q , Y e q ′ } − τ e ( Y − e q ) ) + ] . \begin{aligned}
d_e^q &= \mathbb{E}\left[\left(Y_e^q-\tau_e(Y_{-e}^q)\right)^+\right], & D_q &= \sum_{e\in E} d_e^q,\\
H_q &= \sum_{e\in E}\mathbb{E}\left[\left(\min\{Y_e^q,Y_e^{q'}\}-\tau_e(Y_{-e}^q)\right)^+\right].
\end{aligned} d e q H q = E [ ( Y e q − τ e ( Y − e q ) ) + ] , = e ∈ E ∑ E [ ( min { Y e q , Y e q ′ } − τ e ( Y − e q ) ) + ] . D q = e ∈ E ∑ d e q ,
where Y e q ′ Y_e^{q'} Y e q ′ is an independent copy of Y e q Y_e^q Y e q , independent also of Y − e q Y_{-e}^q Y − e q . Thus d e q d_e^q d e q is the expected loss from deleting e e e under the reference distribution, and D q D_q D q is the sum of these losses. The quantity H q H_q H q measures the part of this surplus that remains when the same element must exceed the same exclusion threshold in two independent draws. These are the reference-distribution versions of the quantities defined above.
The reference search must preserve the benchmark promised by the preceding step of the algorithm. For this purpose, we use the potential
g ( q ) = a ( q ) F q , a ( q ) = 1 − θ q , g(q)=a(q)F_q,\qquad a(q)=1-\theta q, g ( q ) = a ( q ) F q , a ( q ) = 1 − θ q ,
where θ \theta θ is a fixed constant slightly below 1 / e 1/e 1/ e . At q = 1 q=1 q = 1 , the reference distribution is the original one, and g ( 1 ) = ( 1 − θ ) F 1 g(1)=(1-\theta)F_1 g ( 1 ) = ( 1 − θ ) F 1 . We choose θ \theta θ so that this exceeds the target ( 1 − 1 / e + ϵ 0 ) F 1 (1-1/e+\epsilon_0)F_1 ( 1 − 1/ e + ϵ 0 ) F 1 by enough to pay for estimation and implementation errors. At a later residual state, the search starts from the inherited reference parameter and uses its estimates to certify nondecreasing potential. These certificates are valid whenever the estimates are accurate.
As q q q increases, F q F_q F q is nondecreasing and the coefficient a ( q ) a(q) a ( q ) is decreasing. The search uses this tradeoff to find a reference distribution suitable for one of our two algorithmic steps. To explain the resulting condition, suppose first that q q q is a differentiable interior stationary point. Then
0 = g ′ ( q ) = − θ F q + ( 1 − θ q ) F q ′ , 0=g'(q)=-\theta F_q+(1-\theta q)F'_q, 0 = g ′ ( q ) = − θ F q + ( 1 − θ q ) F q ′ ,
and hence
q F q ′ F q = θ q 1 − θ q = : d ∗ ( q ) . \frac{qF'_q}{F_q}=\frac{\theta q}{1-\theta q}=:d_*(q). F q q F q ′ = 1 − θ q θ q =: d ∗ ( q ) .
For q q q close to one and θ \theta θ close to 1 / e 1/e 1/ e , this target ratio is close to ( 1 / e ) / ( 1 − 1 / e ) (1/e)/(1-1/e) ( 1/ e ) / ( 1 − 1/ e ) .
The remaining step is to relate q F q ′ qF'_q q F q ′ to the deletion surplus D q D_q D q . Once this relation is established, the stationarity condition controls the ratio D q / F q D_q/F_q D q / F q that appears in the threshold analysis. The actual search uses estimates and one-sided derivatives, so it only needs the approximate version of this condition stated below.
We use the rank-layer representation F q = ∫ 0 ∞ E [ r ( S z q ) ] d z F_q=\int_0^\infty\mathbb{E}[r(S_z^q)]\,\mathrm{d}z F q = ∫ 0 ∞ E [ r ( S z q )] d z , which integrates the expected rank at each height z z z . Here S z q = { e : Y e q > z } S_z^q=\{e:Y_e^q>z\} S z q = { e : Y e q > z } is the active upper-level set and r ( A ) = max { ∣ I ∣ : I ⊆ A , I ∈ I } r(A)=\max\{|I|:I\subseteq A,\ I\in\mathcal{I}\} r ( A ) = max { ∣ I ∣ : I ⊆ A , I ∈ I } is matroid rank. Differentiating the multilinear extension of matroid rank (the expected rank under independent inclusion probabilities) shows that each coordinate’s derivative is its nonspanning probability ρ e q ( z ) = Pr [ e ∉ cl ( S z q ∖ e ) ] \rho_e^q(z)=\Pr[e\notin\operatorname{cl}(S_z^q\setminus e)] ρ e q ( z ) = Pr [ e ∈ / cl ( S z q ∖ e )] , where cl ( A ) = { f ∈ E : r ( A ∪ { f } ) = r ( A ) } \operatorname{cl}(A)=\{f\in E:r(A\cup\{f\})=r(A)\} cl ( A ) = { f ∈ E : r ( A ∪ { f }) = r ( A )} is the closure of A A A . A set A A A spans an element e e e if e ∈ cl ( A ) e\in\operatorname{cl}(A) e ∈ cl ( A ) , and spans a set C C C if C ⊆ cl ( A ) C\subseteq\operatorname{cl}(A) C ⊆ cl ( A ) .
Since these probabilities and the coordinate slopes are nonincreasing in q q q , integrating over z z z shows that F q F_q F q is nondecreasing and concave (Lemma 3 ), so g ( q ) = a ( q ) F q g(q)=a(q)F_q g ( q ) = a ( q ) F q is concave on J \mathcal{J} J (Lemma 4 ) and q F q ′ qF'_q q F q ′ equals D q D_q D q up to the slack H q = ∫ 0 ∞ ∑ e ∈ E ρ e q ( z ) 2 ρ ˉ e q ( z ) d z H_q=\int_0^\infty\sum_{e\in E}\rho_e^q(z)^2\bar{\rho}_e^q(z)\,\mathrm{d}z H q = ∫ 0 ∞ ∑ e ∈ E ρ e q ( z ) 2 ρ ˉ e q ( z ) d z from saturated tails where q Pr [ X e > z ] ≥ 1 q\Pr[X_e>z]\ge1 q Pr [ X e > z ] ≥ 1 . Writing ( F q ′ ) + (F'_q)_+ ( F q ′ ) + and ( F q ′ ) − (F'_q)_- ( F q ′ ) − for the right and left derivatives, and ϵ = 10 − 6 \epsilon=10^{-6} ϵ = 1 0 − 6 for the estimation tolerance, we have:
D q − H q ≤ q ( F q ′ ) + ≤ q ( F q ′ ) − ≤ D q , D q F q ∈ [ d ∗ ( q ) − 20 ϵ , d ∗ ( q ) + H q F q + 20 ϵ ] . (1) \begin{aligned}
D_q-H_q &\le q(F'_q)_+ \le q(F'_q)_- \le D_q,\\
\frac{D_q}{F_q} &\in\left[d_*(q)-20\epsilon,\ d_*(q)+\frac{H_q}{F_q}+20\epsilon\right]. \tag*{(1)}
\end{aligned} D q − H q F q D q ≤ q ( F q ′ ) + ≤ q ( F q ′ ) − ≤ D q , ∈ [ d ∗ ( q ) − 20 ϵ , d ∗ ( q ) + F q H q + 20 ϵ ] . (1)
Here the second line is the approximate stationarity condition certified by the search for ∣ q − 1 ∣ < 3 δ |q - 1| < 3\delta ∣ q − 1∣ < 3 δ on the simultaneous accurate-estimation event of Lemma 16. It need not mean that g ′ g' g ′ itself is small when H q / F q H_q/F_q H q / F q is large. On this event, starting from the parent minor’s parameter q i n q^{\mathrm{in}} q in (q i n = 1 q^{\mathrm{in}} = 1 q in = 1 initially), binary search moves q q q only along certified ascent directions of g ( q ) g(q) g ( q ) . We therefore need to preserve g ( q ) ≥ g ( q i n ) g(q) \geq g(q^{\mathrm{in}}) g ( q ) ≥ g ( q in ) , without estimating max q ∈ J g ( q ) \max_{q \in J} g(q) max q ∈ J g ( q ) to additive accuracy ϵ 0 F 1 \epsilon_0 F_1 ϵ 0 F 1 . The tolerance ϵ \epsilon ϵ instead enters the local surplus inequalities. Taking ϵ = 10 − 6 \epsilon= 10^{-6} ϵ = 1 0 − 6 leaves enough slack for the improved parameter choice below; it changes the constants in the sample count but preserves polynomial running time.
The affine coefficient a ( q ) = 1 − θ q a(q) = 1 - \theta q a ( q ) = 1 − θ q is chosen close to the tangent at q = 1 q = 1 q = 1 of the baseline continuation curve a 0 ( q ) = 1 − e − 1 / q a_0(q) = 1 - e^{-1/q} a 0 ( q ) = 1 − e − 1/ q . If the selected parameter lies in the boundary region ∣ q − 1 ∣ ≥ 3 δ |q - 1| \geq3\delta ∣ q − 1∣ ≥ 3 δ , the strict convexity of a 0 a_0 a 0 on J J J places the baseline value a 0 ( q ) F q a_0(q)F_q a 0 ( q ) F q above a ( q ) F q a(q)F_q a ( q ) F q by order δ 2 F q \delta^2 F_q δ 2 F q . Our parameter choice leaves enough margin to cover the continuation’s loss of the same order, so the algorithm can finish with that continuation.
Otherwise, the search returns an interior parameter satisfying (1) , and the algorithm branches on whether its estimate of H q / F q H_q/F_q H q / F q exceeds η = 49 / 1000 \eta= 49/1000 η = 49/1000 . We use the final-window length δ = 3 / 2048 \delta= 3/2048 δ = 3/2048 . Together with the sharper threshold comparison below, these choices yield ϵ 0 = 1.01 ⋅ 10 − 6 \epsilon_0 = 1.01 \cdot10^{-6} ϵ 0 = 1.01 ⋅ 1 0 − 6 . § 15 verifies all scalar inequalities uniformly over the reference interval.
Small stable surplus (H q / F q ≲ η H_q/F_q \lesssim\eta H q / F q ≲ η ): One-step threshold progress via Poisson rank concavity
On the accurate-estimation event, when H q / F q H_q/F_q H q / F q is small, (1) pins D q / F q ≈ d ∗ ( q ) D_q/F_q \approx d_*(q) D q / F q ≈ d ∗ ( q ) . In this volatile regime, the algorithm processes only the single next arrival e e e : it sets a deterministic price p e = a ( q ) m ‾ e q p_e = a(q)\overline{m}_e^q p e = a ( q ) m e q , using a conservative estimate m ‾ e q ≥ m e q \overline{m}_e^q \geq m_e^q m e q ≥ m e q , where m e q = E [ τ e ( Y q ) ] = F q ( M ∖ e ) − F q ( M / e ) m_e^q = \mathbb{E}[\tau_e(Y^q)] = F_q(M \setminus e) - F_q(M/e) m e q = E [ τ e ( Y q )] = F q ( M ∖ e ) − F q ( M / e ) is e e e ’s expected exclusion threshold, contracting e e e if X e > p e X_e > p_e X e > p e and deleting e e e otherwise, and passes q i n = q q^{\mathrm{in}} = q q in = q to the child minor.
Rejecting a uniform next arrival drops the potential a ( q ) F q a(q)F_q a ( q ) F q by 1 n a ( q ) D q \frac{1}{n}a(q)D_q n 1 a ( q ) D q in expectation, whereas contracting e e e reduces the potential by a ( q ) m e q ≤ p e a(q)m_e^q \leq p_e a ( q ) m e q ≤ p e more than deletion does, so accepting when X e > p e X_e > p_e X e > p e gains at least ( X e − p e ) + (X_e - p_e)^+ ( X e − p e ) + over deletion. Using Pr [ Y e q > z ] ≤ q Pr [ X e > z ] \Pr[Y_e^q > z] \leq q\Pr[X_e > z] Pr [ Y e q > z ] ≤ q Pr [ X e > z ] to transfer from X X X to Y q Y^q Y q , positive expected drift reduces to showing that the posted-price surplus S b = ∑ e E [ ( Y e q − b m e q ) + ] S_b = \sum_e \mathbb{E}[(Y_e^q - b m_e^q)^+] S b = ∑ e E [( Y e q − b m e q ) + ] (b = a ( q ) ( 1 + ϵ ) / ( 1 − ϵ ) b = a(q)(1+\epsilon)/(1-\epsilon) b = a ( q ) ( 1 + ϵ ) / ( 1 − ϵ ) ) strictly exceeds b q D q + 2 ϵ F q bqD_q + 2\epsilon F_q b q D q + 2 ϵ F q .
Why does S b S_b S b beat b q D q bqD_q b q D q when H q H_q H q is small? Crediting ( Y e q − b m e q ) + (Y_e^q - b m_e^q)^+ ( Y e q − b m e q ) + only on elements that enter the offline basis B ( Y q ) B(Y^q) B ( Y q ) would ignore arrivals that clear their static price b m e q b m_e^q b m e q without winning in B ( Y q ) B(Y^q) B ( Y q ) . To capture this extra surplus (Section 3), we split each element’s integral at the cap b π e b\pi_e b π e , where π e = E [ max { Y e q , τ e ( Y − e q ) } ] = m e q + d e q \pi_e = \mathbb{E}[\max\{Y_e^q,\tau_e(Y^q_{-e})\}] = m_e^q + d_e^q π e = E [ max { Y e q , τ e ( Y − e q )}] = m e q + d e q is expected contraction price , and fix a maximum-π \pi π basis B B B .
Above the caps (z > b π e z > b\pi_e z > b π e ), lower-bounding Y e q − b m e q ≥ Y e q − b π e Y_e^q - b m_e^q \geq Y_e^q - b\pi_e Y e q − b m e q ≥ Y e q − b π e already recovers ( 1 − b ) F q (1-b)F_q ( 1 − b ) F q up to the gap between F q F_q F q , ∑ e ∈ B π e \sum_{e \in B}\pi_e ∑ e ∈ B π e , and the capped values (Lemma 7).
Below the caps (z ≤ b π e z \leq b\pi_e z ≤ b π e ), the greedy choice of B B B ensures that B ∩ { e : b π e > z } B \cap\{e : b\pi_e > z\} B ∩ { e : b π e > z } spans the entire cap-active set { e : b π e > z } \{e : b\pi_e > z\} { e : b π e > z } at every height z z z (Lemma 6). Conditioning on and contracting active elements outside this set, then restricting to the cap-active set, yields a minor with a basis C 0 ⊆ B ∩ { e : b π e > z } C_0 \subseteq B \cap\{e : b\pi_e > z\} C 0 ⊆ B ∩ { e : b π e > z } , where we invoke the concavity of Poisson-rounded matroid rank [10 ] , the expected rank when labels f f f are included independently with probabilities 1 − e − u f 1 - e^{-u_f} 1 − e − u f for a nonnegative intensity vector u u u .
We compare the tangent at the current intensity vector matching the layer’s inclusion probabilities (with saturated probabilities handled by continuity) with the rank at s 1 C 0 s\mathbf{1}_{C_0} s 1 C 0 , the vector equal to s s s on C 0 C_0 C 0 and zero elsewhere (s = 5 / 2 s = 5/2 s = 5/2 , Lemma 8). This controls the capped deletion surplus by stable surplus and the expected number of basis elements not spanned by the active set in this minor, bounding the capped part of D q D_q D q in terms of S b S_b S b , the stable surplus H q H_q H q , and a small Poisson tail b e − s F q be^{-s}F_q b e − s F q (Lemma 9 ).
Combining the bounds above and below the caps eliminates all intermediate terms in π e \pi_e π e and B B B , leaving a closed-form bound in D q D_q D q , H q H_q H q , and F q F_q F q (Corollary 10 ), whose strict inequality below uses the selected reference and our parameter choice:
S b F q ≥ 1 − b + b b + s ( D q F q − ( 1 − b ) − H q F q − b e − s ) > b q D q F q + 2 ε when H q / F q ≤ η + 10 ε . (2) \begin{aligned}
\frac{S_b}{F_q} &\ge1-b+\frac{b}{b+s}\left(\frac{D_q}{F_q}-(1-b)-\frac{H_q}{F_q}-be^{-s}\right) \\
&> bq\frac{D_q}{F_q}+2\varepsilon\qquad\text{when } H_q/F_q\le\eta+10\varepsilon. \tag*{(2)}
\end{aligned} F q S b ≥ 1 − b + b + s b ( F q D q − ( 1 − b ) − F q H q − b e − s ) > b q F q D q + 2 ε when H q / F q ≤ η + 10 ε . (2)
For the strict comparison, we first subtract b q D q / F q bqD_q/F_q b q D q / F q from the structural lower bound. The resulting coefficient of D q / F q D_q/F_q D q / F q is negative, so we substitute the upper stationarity bound in (1) . The positive and negative terms b b + s H q / F q \frac{b}{b+s}H_q/F_q b + s b H q / F q cancel, leaving the dependence on H q / F q H_q/F_q H q / F q only in the benchmark term − b q H q / F q -bqH_q/F_q − b q H q / F q . This retains more of the available surplus than bounding the two sides separately; the detailed calculation appears in Lemma 18 .
Large stable surplus
3. Large stable surplus (H q / F q ≳ η H_q/F_q\gtrsim\eta H q / F q ≳ η ): Basis overlap and virtual basis-exchange continuation. When its estimate exceeds η \eta η (so H q / F q > η − 10 ε H_q/F_q>\eta-10\varepsilon H q / F q > η − 10 ε on the accurate event), we first show (Lemma 5 ) that two independent reference optima must share a substantial weighted overlap Q q = ∑ e ∫ 0 ∞ x e ( z ) 2 d z Q_q=\sum_e\int_0^\infty x_e(z)^2\,dz Q q = ∑ e ∫ 0 ∞ x e ( z ) 2 d z , where x e ( z ) = Pr [ e ∈ B ( Y q ) , Y e q > z ] x_e(z)=\Pr[e\in B(Y^q),Y_e^q>z] x e ( z ) = Pr [ e ∈ B ( Y q ) , Y e q > z ] . We bound the integrand p e q ( z ) ρ e q ( z ) p_e^q(z)\rho_e^q(z) p e q ( z ) ρ e q ( z ) of H q H_q H q by comparing the greedy and reverse-greedy bases of the active set S z q S_z^q S z q at each height z z z , using the decreasing value-and-label order and its full reverse. An active element e ∈ S z q e\in S_z^q e ∈ S z q is a coloop of S q S^q S q (its removal lowers the rank by one) only if it is spanned neither by earlier active elements (which puts e e e in the greedy basis) nor by later active elements (which puts e e e in the reverse-greedy basis).
Draw independent latent priorities from Y e q ∣ Y e q > z Y_e^q\mid Y_e^q>z Y e q ∣ Y e q > z , omitting zero-tail labels, independently of the active indicators, and let a e + a_e^+ a e + and a e − a_e^- a e − be the conditional probabilities of these two nonspanning events.
For fixed priorities the events depend on disjoint sets of independent active indicators (hence factor), while their probabilities have opposite monotonicities in the latent priorities, so the product-association inequality gives ρ e q ( z ) ≤ E [ a e + ] E [ a e − ] \rho_e^q(z)\le\mathbb{E}[a_e^+]\mathbb{E}[a_e^-] ρ e q ( z ) ≤ E [ a e + ] E [ a e − ] and p e q ( z ) ρ e q ( z ) ≤ x e + ( z ) x e − ( z ) p_e^q(z)\rho_e^q(z)\le x_e^+(z)x_e^-(z) p e q ( z ) ρ e q ( z ) ≤ x e + ( z ) x e − ( z ) , where x e + x_e^+ x e + and x e − x_e^- x e − are the corresponding basis-inclusion probabilities.
The product-association inequality states that coordinatewise increasing and decreasing functions of independent coordinates have nonpositive covariance; the proof of Lemma 5 includes the needed argument.
Bounding the reverse-greedy second moment by F q − D q + H q F_q-D_q+H_q F q − D q + H q and applying Cauchy–Schwarz over ( e , z ) (e,z) ( e , z ) yields H q 2 ≤ Q q ( F q − D q + H q ) ≤ F q Q q H_q^2\le Q_q(F_q-D_q+H_q)\le F_qQ_q H q 2 ≤ Q q ( F q − D q + H q ) ≤ F q Q q .
Once Q q / F q Q_q/F_q Q q / F q is bounded away from zero, a single virtual basis-exchange continuation finishes the entire residual instance (Section 4, Proposition 11 ). Throughout this continuation, the entry minor and reference distribution remain fixed, and rejected labels remain in reference realizations. Represent the random order by independent uniform arrival times in [ 0 , 1 ] [0,1] [ 0 , 1 ] for the residual labels. Following [23 , 1 ] , the algorithm maintains a distribution over feasible completions by recording each accepted arrival as a triple ( e i , t i , C i ) (e_i,t_i,C_i) ( e i , t i , C i ) , where t i ∈ [ 0 , 1 ] t_i\in[0,1] t i ∈ [ 0 , 1 ] is its arrival time and C i C_i C i is the candidate basis that witnessed its acceptance.
Any fresh reference draw y ∼ Y q y\sim Y^q y ∼ Y q starts at its offline greedy basis B = B 0 y B=B_0^y B = B 0 y and replays all acceptances up to time t t t via canonical basis-exchange bijections ϕ C i , B : C i → B \phi_{C_i,B}:C_i\to B ϕ C i , B : C i → B from the source basis C i C_i C i to the current target basis B B B , updating 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 (Lemma 12 ). Here B − f + e = ( B ∖ { f } ) ∪ { e } B-f+e=(B\setminus\{f\})\cup\{e\} B − f + e = ( B ∖ { f }) ∪ { e } ; each such exchange preserves a basis, and the bijection fixes C i ∩ B C_i\cap B C i ∩ B pointwise.
Inductively, the evolved basis B y ( t ) B_y(t) B y ( t ) always contains the set A t A_t A t of labels accepted before the decision at time t t t , so every remaining “live” element e ∈ B y ( t ) ∖ A t e \in B_y(t) \setminus A_t e ∈ B y ( t ) ∖ A t (y e > 0 y_e > 0 y e > 0 ) is feasible to add to A t A_t A t , and injectivity of the exchange map ensures that, in each source realization, at most one live source label can evict a fixed target element from B B B .
During the early phase t ∈ [ 0 , 1 − δ ] t \in[0,1-\delta] t ∈ [ 0 , 1 − δ ] , whenever an arrival e e e passes a Bernoulli screen matching λ \lambda λ times the positive-value reference measure (λ = 1 / q \lambda= 1/q λ = 1/ q ; for finite distributions, an observed v > 0 v > 0 v > 0 passes with probability Pr [ Y e q = v ] / ( q Pr [ X e = v ] ) \Pr[Y_e^q = v]/(q\Pr[X_e = v]) Pr [ Y e q = v ] / ( q Pr [ X e = v ]) ) and is live in a freshly sampled reference realization with y e = X e y_e = X_e y e = X e and y − e ∼ Y − e q y_{-e} \sim Y_{-e}^q y − e ∼ Y − e q , we must correct for conditioning on the accepted history. Let k e ( u ) k_e(u) k e ( u ) be the probability, over a fresh reference realization, that e e e is live at time u u u along a fixed accepted history, and let Λ e ( t ) = λ ∫ 0 t k e ( u ) d u \Lambda_e(t) = \lambda\int_0^t k_e(u)\,du Λ e ( t ) = λ ∫ 0 t k e ( u ) d u .
We draw a Poisson(2) number of probes (mean two) at uniform times u ∈ [ 0 , 2 q ) u \in[0,2q) u ∈ [ 0 , 2 q ) and reject e e e if any probe with u < t u < t u < t finds e e e live in a fresh reference realization.
Since each probe lands in [ 0 , t ) [0,t) [ 0 , t ) and finds e e e live with probability 1 2 Λ e ( t ) \frac{1}{2}\Lambda_e(t) 2 1 Λ e ( t ) , this test passes with exact probability e − Λ e ( t ) e^{-\Lambda_e(t)} e − Λ e ( t ) , and our identity for the acceptance intensity—the conditional acceptance probability per unit time—(Lemma 13 ) gives the no-acceptance factor S e ( t ) = e − Λ e ( t ) S_e(t) = e^{-\Lambda_e(t)} S e ( t ) = e − Λ e ( t ) for an unaccepted label along that history, accounting for either nonarrival or an earlier rejection.
The factors cancel, so the acceptance intensity on live reference realizations has uniform density λ e − Λ e ( t ) / S e ( t ) = λ \lambda e^{-\Lambda_e(t)}/S_e(t) = \lambda λ e − Λ e ( t ) / S e ( t ) = λ , and expected live weight is at least e − λ t e^{-\lambda t} e − λ t times its initial value (Lemma 14 ).
In the final window t ∈ ( 1 − δ , 1 ] t \in(1-\delta,1] t ∈ ( 1 − δ , 1 ] , we drop the Poisson attenuation and accept every screened live candidate. Now S e ( t ) ≤ e − Λ e ( 1 − δ ) S_e(t) \le e^{-\Lambda_e(1-\delta)} S e ( t ) ≤ e − Λ e ( 1 − δ ) is no longer canceled: persistent elements with large early live mass k e ( u ) k_e(u) k e ( u ) —those contributing to Q q Q_q Q q —see their conditional acceptance rate jump to λ / S e ( t ) ≥ λ ( 1 + Λ e ( 1 − δ ) ) \lambda/S_e(t) \ge\lambda(1+\Lambda_e(1-\delta)) λ / S e ( t ) ≥ λ ( 1 + Λ e ( 1 − δ )) , yielding a first-order bonus + Ω ( δ Q q ) +\Omega(\delta Q_q) + Ω ( δ Q q ) at a second-order cost − O ( δ 2 F q ) -O(\delta^2 F_q) − O ( δ 2 F q ) .
Range-independent layer sampling and polynomial complexity
Naive Monte Carlo estimation of F q F_q F q , D q D_q D q , H q H_q H q , and m e q m_e^q m e q would depend on the numerical spread of the distributions. § 11 eliminates this dependence by observing that all required layer statistics vanish on the empty active set: normalizing by the closed-form expected maximum V q = E [ max e Y e q ] V_q = \mathbb{E}[\max_e Y_e^q] V q = E [ max e Y e q ] , we sample a nonempty active layer R = S z q R = S_z^q R = S z q from the sorted support intervals, with probabilities proportional to their contributions to V q V_q V q . This gives the needed importance-sampling distribution without rejection sampling.
Here M ∣ R = ( R , { I ∈ I : I ⊆ R } ) M|_R = (R,\{I \in\mathcal{I}: I \subseteq R\}) M ∣ R = ( R , { I ∈ I : I ⊆ R }) denotes the restriction of M M M to R R R : it retains only the labels in R R R and the independent sets contained in R R R . Finding a basis and all coloops of M ∣ R M|_R M ∣ R via binary search on fundamental circuits (the unique minimal dependent subsets of a basis plus one nonbasis element) takes O ( n ( log ( n + 1 ) ) ) O(n(\log(n+1))) O ( n ( log ( n + 1 ))) matroid independence queries (tests of whether a specified set is independent; Lemma 15 ) and gives unbiased estimators in [ 0 , N V q ] [0,NV_q] [ 0 , N V q ] , supporting all reference searches in O ( N 3 log 3 ( N + 2 ) ) O(N^3\log^3(N+2)) O ( N 3 log 3 ( N + 2 )) queries (Lemma 16 ) while the continuation uses O ( N 4 ) O(N^4) O ( N 4 ) expected queries.
Finally, § 14 discretizes arrival clocks and caps Poisson counts, using bounded-bit draws and coupling finite-precision execution with the ideal policy conditionally on X X X at negligible loss.
Part II: The 1 − 1 / e 1-1/e 1 − 1/ e Barrier for XOS Valuations (Theorem 2 )
Basis exchange versus early witness commitment
Why can an online algorithm beat 1 − 1 / e 1-1/e 1 − 1/ e for every matroid, yet not uniformly over combinatorial auctions with XOS valuations? In a matroid, the basis-exchange property lets our virtual continuation maintain a distribution over candidate bases and update all of them simultaneously as elements arrive (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 ), without committing upfront to a single global completion.
In a combinatorial auction with n n n buyers having XOS valuations, indexed by arrival position t t t , each buyer’s valuation v ( S ) = max ℓ ∈ L ∑ j ∈ S w ℓ , j v(S) = \max_{\ell\in\mathcal{L}}\sum_{j \in S} w_{\ell,j} v ( S ) = max ℓ ∈ L ∑ j ∈ S w ℓ , j is a maximum over additive clauses, where $\mathcal is the clause index set and w ℓ , j ≥ 0 w_{\ell,j} \ge0 w ℓ , j ≥ 0 is clause ℓ \ell ℓ ’s weight for item j j j . Write L t \mathcal{L}_t L t for buyer t t t ’s realized clause index set. Items must be allocated online into disjoint bundles S 1 , … , S n S_1,\ldots,S_n S 1 , … , S n .
Buyer t t t evaluates S t S_t S t through a supporting clause W t ∈ L t W_t \in\mathcal{L}_t W t ∈ L t , called its witness clause . In our construction, each clause specifies one slice of a global n n n -way partition indexed by a set of n n n possible buyer types. Thus irrevocably allocating S t S_t S t fixes buyer t t t ’s canonical witness partition W t W_t W t before seeing the types of future buyers u > t u>t u > t . The witness uses a fixed tie order and is only an analysis variable; the algorithm need not compute it.
Theorem 2 shows that this early-commitment bottleneck caps every algorithm’s expected welfare at ( 1 − 1 / e + o ( 1 ) ) E [ O P T ] (1-1/e+o(1))\mathbb{E}[\mathrm{OPT}] ( 1 − 1/ e + o ( 1 )) E [ OPT ] along the instance family below, even for i.i.d. buyers, { 0 , 1 } \{0,1\} { 0 , 1 } clauses, known arrival order, and unrestricted computation.
Public partitions from a product space
§ 16 realizes this obstruction via a product-space geometry. Write [ k ] = { 1 , … , k } [k]=\{1,\ldots,k\} [ k ] = { 1 , … , k } . Each of the n ≥ 2 n\ge2 n ≥ 2 buyers draws an i.i.d. uniform type A t ∈ [ L ] A_t\in[L] A t ∈ [ L ] from a type space of integer size L ≥ n L\ge n L ≥ n . We work in the regime L / n 3 → ∞ L/n^3\to\infty L / n 3 → ∞ as n → ∞ n\to\infty n → ∞ , which governs all o ( 1 ) o(1) o ( 1 ) and o ( m ) o(m) o ( m ) terms below. We index n n n -buyer type sets by the family T = ( [ L ] n ) \mathcal{T}=\binom{[L]}{n} T = ( n [ L ] ) of all n n n -element subsets of [ L ] [L] [ L ] .
Taking the item universe to be the product cube M = [ n ] T M=[n]^{\mathcal{T}} M = [ n ] T , consisting of all functions x : T → [ n ] x:\mathcal{T}\to[n] x : T → [ n ] , of size m = ∣ M ∣ = n ∣ T ∣ m=|M|=n^{|\mathcal{T}|} m = ∣ M ∣ = n ∣ T ∣ , each type set s ∈ T s\in\mathcal{T} s ∈ T partitions M M M along coordinate s s s into n n n equal slices 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 ] ) of size m / n m/n m / n .
A buyer of type a ∈ [ L ] a\in[L] a ∈ [ L ] has one binary clause for each type set s ∈ T s\in\mathcal{T} s ∈ T containing a a a —the indicator of the slice P s r s ( a ) P_s^{r_s(a)} P s r s ( a ) , where r s ( a ) ∈ [ n ] r_s(a)\in[n] r s ( a ) ∈ [ n ] is the position of a a a in the increasing ordering of s s s —giving the binary XOS valuation v a ( S ) = max s ∈ T : a ∈ s ∣ S ∩ P s r s ( a ) ∣ v^a(S)=\max_{s\in\mathcal{T}:a\in s}|S\cap P_s^{r_s(a)}| v a ( S ) = max s ∈ T : a ∈ s ∣ S ∩ P s r s ( a ) ∣ . Thus L t = { s ∈ T : A t ∈ s } \mathcal{L}_t=\{s\in\mathcal{T}:A_t\in s\} L t = { s ∈ T : A t ∈ s } , identifying each witness clause with its type set.
Since coordinates x ( s 1 ) , … , x ( s k ) x(s_1),\ldots,x(s_k) x ( s 1 ) , … , x ( s k ) of a uniform item x ∈ M x\in M x ∈ M at distinct type sets s 1 , … , s k ∈ T s_1,\ldots,s_k\in\mathcal{T} s 1 , … , s k ∈ T are independent and uniform on [ n ] [n] [ n ] , any k k k slices from distinct type sets come from distinct coordinates of the cube and cover a fixed fraction of M M M (Lemma 23), even adaptively:
∣ ⋃ i = 1 k P s i r i ∣ = m ( 1 − ( 1 − 1 n ) k ) (3) \left|\bigcup_{i=1}^{k}P_{s_i}^{r_i}\right|=m\left(1-\left(1-\frac{1}{n}\right)^k\right) \tag*{(3)} i = 1 ⋃ k P s i r i = m ( 1 − ( 1 − n 1 ) k ) (3)
for any distinct s 1 , … , s k ∈ T s_1,\ldots,s_k\in\mathcal{T} s 1 , … , s k ∈ T and any r 1 , … , r k ∈ [ n ] r_1,\ldots,r_k\in[n] r 1 , … , r k ∈ [ n ] .
Prophet coordination versus online witness divergence
With probability at least 1 − ( n 2 ) / L = 1 − o ( 1 ) 1-\binom{n}{2}/L=1-o(1) 1 − ( 2 n ) / L = 1 − o ( 1 ) , the realized types A 1 , … , A n ∈ [ L ] A_1,\ldots,A_n\in[L] A 1 , … , A n ∈ [ L ] are distinct and form a shared type set s ∗ = { A 1 , … , A n } ∈ T s^*=\{A_1,\ldots,A_n\}\in\mathcal{T} s ∗ = { A 1 , … , A n } ∈ T . Knowing s ∗ s^* s ∗ upfront, the prophet coordinates all n n n buyers onto the disjoint slices S t ∗ = P s ∗ r s ∗ ( A t ) S_t^*=P_{s^*}^{r_{s^*}(A_t)} S t ∗ = P s ∗ r s ∗ ( A t ) of the partition indexed by s ∗ s^* s ∗ , obtaining welfare m m m on this event. Consequently, E [ O P T ] ≥ ( 1 − ( n 2 ) / L ) m = ( 1 − o ( 1 ) ) m \mathbb{E}[\mathrm{OPT}]\ge(1-\binom{n}{2}/L)m=(1-o(1))m E [ OPT ] ≥ ( 1 − ( 2 n ) / L ) m = ( 1 − o ( 1 )) m .
By contrast, when an online algorithm allocates S t ⊆ M S_t\subseteq M S t ⊆ M at step t t t , buyer t t t ’s maximizing witness type set W t ∈ T W_t\in\mathcal{T} W t ∈ T (A t ∈ W t A_t\in W_t A t ∈ W t ), for which v A t ( S t ) = ∣ S t ∩ P W t r W t ( A t ) ∣ v^{A_t}(S_t)=|S_t\cap P_{W_t}^{r_{W_t}(A_t)}| v A t ( S t ) = ∣ S t ∩ P W t r W t ( A t ) ∣ , is fixed before future buyers u > t u>t u > t reveal their types A u ∈ [ L ] A_u\in[L] A u ∈ [ L ] .
Since any valid witness W u W_u W u for buyer u > t u>t u > t must contain A u A_u A u , buyer u u u can reuse W t W_t W t (W u = W t W_u=W_t W u = W t ) only if her unrevealed uniform type A u ∈ [ L ] A_u\in[L] A u ∈ [ L ] lands in the n n n -element set W t W_t W t (conditional probability n / L n/L n / L given the earlier history). By a union bound, all n n n online witnesses W 1 , … , W n ∈ T W_1,\ldots,W_n\in\mathcal{T} W 1 , … , W n ∈ T are distinct with probability at least 1 − ( n 2 ) n / L = 1 − o ( 1 ) 1-\binom{n}{2}n/L=1-o(1) 1 − ( 2 n ) n / L = 1 − o ( 1 ) .
Writing A L G \mathrm{ALG} ALG for realized online welfare, whenever the witnesses are distinct, the credited subsets S t ∩ P W t r W t ( A t ) S_t\cap P_{W_t}^{r_{W_t}(A_t)} S t ∩ P W t r W t ( A t ) are pairwise disjoint (as S 1 , … , S n S_1,\ldots,S_n S 1 , … , S n are disjoint) and pack inside the union of n n n slices ⋃ t = 1 n P W t r W t ( A t ) \bigcup_{t=1}^nP_{W_t}^{r_{W_t}(A_t)} ⋃ t = 1 n P W t r W t ( A t ) —where items in overlaps of multiple slices go to at most one buyer, while a ( 1 − 1 / n ) n ≈ 1 / e (1 - 1/n)^n \approx1/e ( 1 − 1/ n ) n ≈ 1/ e fraction of the cube is missed by (3) :
A L G = ∑ t = 1 n ∣ S t ∩ P W t W t ( A t ) ∣ ≤ ∣ ⋃ t = 1 n P W t W t ( A t ) ∣ = m ( 1 − ( 1 − 1 / n ) n ) = ( 1 − 1 / e + o ( 1 ) ) m . (4) \begin{aligned}
\mathrm{ALG} &= \sum_{t=1}^{n} \left|S_t \cap P_{W_t}^{\mathrm{Wt}}(A_t)\right| \leq\left|\bigcup_{t=1}^{n} P_{W_t}^{\mathrm{Wt}}(A_t)\right| \\
&= m\left(1-(1-1/n)^n\right) = (1-1/e+o(1))m. \tag*{(4)}
\end{aligned} ALG = t = 1 ∑ n S t ∩ P W t Wt ( A t ) ≤ t = 1 ⋃ n P W t Wt ( A t ) = m ( 1 − ( 1 − 1/ n ) n ) = ( 1 − 1/ e + o ( 1 )) m . (4)
The exceptional witness-collision event contributes at most n ( n 2 ) m / L = o ( m ) n\binom{n}{2}m/L = o(m) n ( 2 n ) m / L = o ( m ) to expected welfare. Section 10.3 also derives Theorem 2 via an online coverage-to-XOS transposition [6 ] of the ( 1 − 1 / e ) (1-1/e) ( 1 − 1/ e ) i.i.d. online coverage barrier of Udwani and Wajc [29 ] . Unlike offline approximation questions [9 , 15 ] that concern computational restrictions, our bound is purely informational: all n ∣ T ∣ n|\mathcal{T}| n ∣ T ∣ clause occurrences and the arrival order are known upfront, and the 1 − 1 / e 1-1/e 1 − 1/ e loss stems solely from committing to disjoint bundles before future buyer types arrive.
Related work
Secretary problems and matroids. The matroid secretary problem was introduced by Babaioff, Immorlica, and Kleinberg [5 ] . Its values are fixed and unknown, and its arrival order is uniformly random. Before the recent constant-factor algorithms, the best general approximation factor was O ( log log r ) O(\log\log r) O ( log log r ) , where r r r is the rank, by work of Lachish [26 ] and Feldman, Svensson, and Zenklusen [18 ] . Singla [28 ] gives an algorithm that accepts every element of the canonical optimum with probability at least 1 / 4 1/4 1/4 , and Huang [23 ] obtains the optimal universal probability guarantee 1 / e 1/e 1/ e with expected polynomial matroid independence query complexity. The merged manuscript of Abdi et al. [1 ] gives a unified treatment and obtains independent acceptance events, each with probability 1 / e 1/e 1/ e , for the elements of the canonical optimum. These results require no prior information about values. Theorem 1 concerns the additional power of values drawn independently from known distributions under the same feasibility constraint.
Prophet inequalities and random arrival. Esfandiari, Hajiaghayi, Liaghat, and Monemizadeh [14 ] introduced prophet secretary. In the adversarial-order model, Kleinberg and Weinberg [25 ] proved the optimal 1 / 2 1/2 1/2 matroid prophet inequality. Feldman, Gravin, and Lucier [16 ] obtained the corresponding 1 / 2 1/2 1/2 welfare guarantee for buyers with XOS valuations through posted prices. Ehsani et al. [12 , 13 ] improved both guarantees to 1 − 1 / e 1-1/e 1 − 1/ e under uniformly random arrival. Our matroid theorem improves their guarantee for arbitrary matroids.
The single-choice prophet-secretary problem admits ratios above 1 − 1 / e 1-1/e 1 − 1/ e . Azar, Chiplunkar, and Kaplan [3 ] obtained a strict improvement, followed by further improvements of Correa, Saona, and Ziliotto [8 ] . Chen, Huang, Li, and Tang [7 ] developed further single-choice techniques and improved the ratio for prophet-secretary matching. Those results do not supply the general-matroid guarantee proved here.
Limited information and single-sample guarantees. Azar, Kleinberg, and Weinberg [4 ] showed that an order-oblivious secretary algorithm yields a single-sample prophet algorithm with the same competitive guarantee. Such a secretary algorithm first observes a random sample and then uses a selection rule whose guarantee holds for any order of the remaining elements. For general matroids, Fu et al. [17 ] obtained a constant guarantee using only polylogarithmically many samples from each distribution; Feldman, Svensson, and Zenklusen [20 ] subsequently sharpened the sample complexity. These guarantees allow an almighty adversary to choose the arrival order after seeing the samples, values, and algorithmic randomness. Abdi, Banihashem, Hajiaghayi, and Mittal [2 ] , and the merged treatment [1 ] , obtain the optimal 1 / 2 1/2 1/2 guarantee using one sample from each distribution when the arrival order is fixed independently of the samples, values, and algorithmic randomness. Their guarantee specifies the joint law of the accepted labels and values: it is obtained by drawing a fresh independent value for each element, computing the optimum, and retaining each element of that optimum independently with probability 1 / 2 1/2 1/2 . Our polynomial-time theorem assumes explicitly given distributions and combines this information with random arrival to exceed 1 − 1 / e 1 - 1/e 1 − 1/ e .
Contention resolution and distributional methods. An online contention-resolution scheme receives a random set of active elements and selects a feasible subset as they arrive. Its guarantee lower-bounds each active element’s conditional probability of selection. Such schemes provide a route from fractional benchmarks to online decisions [19 ] . Lee and Singla [27 ] obtained optimal random-order contention-resolution guarantees for matroids, with constant 1 − 1 / e 1 - 1/e 1 − 1/ e . Their benchmark is an ex-ante relaxation: it requires the vector of marginal selection probabilities to lie in the matroid polytope, the convex hull of the incidence vectors of independent sets, without imposing feasibility separately on every realization. This benchmark can exceed the expected integral prophet optimum. Its tight bound therefore does not preclude Theorem 1 . Dughmi [11 ] relates the matroid secretary conjecture to contention resolution for correlated distributions in the online random-order model. This connection and the distributional invariants in [2 , 1 ] place the joint distribution of feasible choices at the center of the analysis. Our continuation maintains virtual optimum bases and characterizes the distribution of its accepted process directly using greedy optimization and basis exchange. The reference search uses the actual expected optimum and the relation between deletion surplus and overlap. For the structural surplus inequality, we use the concavity of Poisson-rounded matroid rank proved by Dughmi, Roughgarden, and Yan [10 ] .
Combinatorial auctions. Offline welfare approximation for XOS valuations has been studied extensively [9 , 15 ] . The upper bound considered here permits exact knowledge of the distributions, explicit clause descriptions, and unrestricted computation. Udwani and Wajc [29 ] establish the corresponding information-theoretic obstruction for online coverage welfare. § 16 gives both a direct XOS construction and the precise transposition from their model.
Organization. Section 2 fixes the model and symbolic parameters. Section 3 proves the structural inequalities, and Section 4 analyzes the virtual continuation. § 11 and § 12 give the common sampler and reference search. § 13 combines them into the online algorithm. § 14 supplies the bounded-bit implementation, and § 15 verifies all parameter conditions and completes Theorem 1 . Finally, § 16 proves the sharp auction upper bound.
Preliminaries and parameters
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 } .
Every basis has size r M ( E ) r_M(E) r M ( E ) ; write B ( M ) \mathcal{B}(M) B ( M ) for the set of bases. 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. Loops can be discarded; the distributions on surviving labels remain unchanged. 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.
Weights and probability notation. For deterministic nonnegative weights y y y , let
OPT ( M , y ) = max I ∈ I ∑ e ∈ I y e . \operatorname{OPT}(M,y)=\max_{I\in\mathcal{I}}\sum_{e\in I}y_e. OPT ( M , y ) = I ∈ I max e ∈ I ∑ y e .
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. An atom is a value with positive probability; our arguments allow atoms and zero values. 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 } .
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. Conditional on the current history, every fresh reference sample uses independent randomness and its specified distribution; no unarrived actual value is used. A candidate reference realization may fix the current coordinate to its observed value, while drawing all other coordinates independently.
For the computational theorem, 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. § 14 replaces them by finite procedures and proves a worst-case polynomial bound on arithmetic operations and random bits. An independence-oracle call counts as one oracle operation. For the auction problem, the buyers’ valuation functions are independent; values of different bundles under one function need not be independent.
Symbolic parameters. Fix positive rational constants δ , θ , ε , η , ρ , σ \delta,\theta,\varepsilon,\eta,\rho,\sigma δ , θ , ε , η , ρ , σ , 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 ) . (5) 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*{(5)} J = [ q − , q + ] = [ 1 − 4 δ , 1 + 4 δ ] , a ( q ) = 1 − θ q , d ∗ ( q ) = a ( q ) 1 − a ( q ) . (5)
The roles of these constants are distinct: δ \delta δ is the length of the final unattenuated interval, θ \theta θ determines the potential, ε \varepsilon ε is the estimation accuracy, η \eta η is the stability cutoff, ρ \rho ρ is an error budget, and s s s specifies the scaled basis vector used in the Poisson-rank tangent comparison.
We impose the following elementary conditions throughout:
0 < ε < δ ≤ 1 8 , ε ≤ 1 10 , 0 < θ < 1 , 0 < ρ < 1 , s > 0 , η > 10 ε , 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, 0 < ε < δ ≤ 8 1 , ε ≤ 10 1 , 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 ) . (6) \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*{(6)} 2 1 ≤ a ( q ) ≤ 4 3 ( q ∈ J ) , ( q ∈ J max a ( q ) ) q + ≤ 1 , d ∗ ( q ) − 20 ε < 1 ( q ∈ J ) . (6)
The welfare proof will use three further scalar inequalities, stated in § 13 . Their meaning will be clear after the two possible continuations have been analyzed. § 15 gives a single choice satisfying all of them.
Reference distributions and structural inequalities
The algorithm will compare several product distributions obtained by rescaling the upper tails of the input distributions. We first record the quantities that govern this comparison. The main structural conclusion is a lower bound on the surplus above expected exclusion thresholds. Combined with approximate stationarity, it will show that a selected reference instance with little stable deletion surplus has enough threshold surplus to support the next online decision.
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 ) + , \operatorname{OPT}(M,Y) - \operatorname{OPT}(M \setminus e,Y) = (Y_e - \tau_e)^{+}, OPT ( M , Y ) − OPT ( M ∖ e , Y ) = ( Y e − τ e ) + ,
OPT ( M , Y ) − OPT ( M / e , Y ) = max { Y e , τ e } . (7) \operatorname{OPT}(M,Y) - \operatorname{OPT}(M/e,Y) = \max\{Y_e,\tau_e\}. \tag*{(7)} OPT ( M , Y ) − OPT ( M / e , Y ) = max { Y e , τ e } . (7)
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}\bigl(\min\{Y_e,Y'_e\} - \tau_e\bigr)^{+}, \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\,\mathrm{d}z. 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 )) .
The weighted-rank formula and independence give
F = ∫ 0 ∞ E r ( S z ) d z , F=\int_0^\infty\mathbb{E}r(S_z)\,dz, F = ∫ 0 ∞ E r ( S z ) d z ,
D = ∫ 0 ∞ ∑ e p e ( z ) ρ e ( z ) d z , (8) D=\int_0^\infty\sum_e p_e(z)\rho_e(z)\,dz, \tag*{(8)} D = ∫ 0 ∞ e ∑ p e ( z ) ρ e ( z ) d z , (8)
H = ∫ 0 ∞ ∑ e p e ( z ) 2 ρ e ( z ) d z . H=\int_0^\infty\sum_e p_e(z)^2\rho_e(z)\,dz. H = ∫ 0 ∞ e ∑ p e ( z ) 2 ρ e ( z ) d z .
The integrand defining D D D is the expected number of coloops in the active restriction. Consequently
0 ≤ H ≤ D ≤ F , 0 ≤ Q ≤ F . (9) 0\le H\le D\le F,\qquad0\le Q\le F. \tag*{(9)} 0 ≤ H ≤ D ≤ F , 0 ≤ Q ≤ F . (9)
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. (10) \mathbb{P}(Y_e^q>z)=\min\{1,q\mathbb{P}(X_e>z)\},\qquad z\ge0. \tag*{(10)} P ( Y e q > z ) = min { 1 , q P ( X e > z )} , z ≥ 0. (10)
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 3 (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 . (11) \min\{1,q\}F_1\le F_q\le\max\{1,q\}F_1. \tag*{(11)} min { 1 , q } F 1 ≤ F q ≤ max { 1 , q } F 1 . (11)
Proof. At a fixed height z z z , expected rank is the multilinear extension of matroid rank evaluated at p e ( z ) = min { 1 , q p e ( z ) } p_e(z)=\min\{1,qp_e(z)\} p e ( 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 4 (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 . a(q)F_q \ge a(q)\left(tF_x+(1-t)F_y\right)
=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. 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 continuation algorithm’s improvement is expressed in terms of Q Q Q , whereas the reference derivatives involve H H H . The following inequality connects them. Its proof compares greedy order with the reverse greedy order. It uses association of independent coordinates, rather than any additional dependence assumption on the random optimum bases.
Lemma 5 (Stable surplus and overlap). For every independent nonnegative value vector,
H 2 ≤ Q ( F − D + H ) ≤ F Q . (12) H^2 \le Q(F-D+H) \le FQ. \tag*{(12)} H 2 ≤ Q ( F − D + H ) ≤ F Q . (12)
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 ) : elements below height z z z cannot affect the greedy selection of an element above that height.
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 (8) 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{Q Q_-}\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 (12) 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 quantity G G G measures the loss in replacing the realized optimum by one fixed basis of expected contraction prices.
Lemma 6 (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 } , (13) G=\int_0^\infty\mathbb{E}\bigl[r(S_z)-|B\cap\operatorname{cl}(S_z)|\bigr]\,dz,\qquad S_z=\{e:Y_e>z\}, \tag*{(13)} G = ∫ 0 ∞ E [ r ( S z ) − ∣ B ∩ cl ( S z ) ∣ ] d z , S z = { e : Y e > z } , (13) 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))\,dz,\qquad\operatorname{OPT}(M,y)-\operatorname{OPT}(M/e,y)=\int_0^\infty\mathbf{1}\{e\in\operatorname{cl}(S_z(y))\}\,dz. 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 (13) . 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 ) + .
The exclusion thresholds in K b K_b K b belong to the original reference instance Y Y Y , not to the capped instance Y ~ \widetilde{Y} Y .
Lemma 7 (Surplus decomposition).
S b ≥ S π , b ≥ ( 1 − b ) F + b G + Δ b , D ≤ S π , b + K b . (14) S_b\ge S_{\pi,b}\ge(1-b)F+bG+\Delta_b,\qquad D\le S_{\pi,b}+K_b. \tag*{(14)} S b ≥ S π , b ≥ ( 1 − b ) F + b G + Δ b , D ≤ S π , b + K b . (14)
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 [10 ] . A tangent inequality evaluated at one scaled basis vector suffices here. The parameter s s s below will be chosen in § 15 .
Lemma 8 (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 . (15) \sum_e p_e\rho_e\le\sum_e p_e^2\rho_e+r_0e^{-s}+sm. \tag*{(15)} e ∑ p e ρ e ≤ e ∑ p e 2 ρ e + r 0 e − s + s m . (15)
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 E ( N 0 ) x\in\mathbb{R}^{E(N_0)} x ∈ R 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}(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 e e , f f 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 the matrix having an all-ones block on each nonloop parallel class of N 0 / R x N_0/R_x N 0 / R x and zeros elsewhere. Every such matrix 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(s1_{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_eu_e\le f(\lambda)-r_0(1-e^{-s})+s\sum_{f\in C_0}u_f\le 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}\le\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\le\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 a fixed layer, the labels outside the cap set must be contracted before the inequality is applied. This preserves the original exclusion thresholds and is the reason for conditioning on the outside active set.
Lemma 9 (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 ) . (16) K_b\le H+bPe^{-s}+s(G+\Delta_b). \tag*{(16)} K b ≤ H + b P e − s + s ( G + Δ b ) . (16) 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 6 , 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 ) and has a basis chosen from B ∩ T z B\cap T_z B ∩ T z . Its basis missing mass 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 8 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)\le\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 ) ∣ . (17) 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*{(17)} r ( T z ) − ∣ B ∩ T z ∩ cl ( S ) ∣ ≤ r ( T z ) − r ( S ∩ T z ) + r ( S ) − ∣ B ∩ cl ( S ) ∣. (17)
Average and integrate. The left side integrates to ∫ 0 ∞ m ( z ) d z \int_{0}^{\infty} m(z)\,\mathrm{d}z ∫ 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)\,\mathrm{d}z=bP ∫ 0 ∞ r ( T z ) d z = b P . The second integrates to G G G by (13) . Therefore
∫ 0 ∞ m ( z ) d z ≤ G + Δ b . \int_{0}^{\infty} m(z)\,\mathrm{d}z \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 .
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 10 (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 ) . (18) \frac{S_b}{F}\ge1-b+\frac{b}{b+s}\left(\frac{D}{F}-(1-b)-\frac{H}{F}-be^{-s}\right). \tag*{(18)} F S b ≥ 1 − b + b + s b ( F D − ( 1 − b ) − F H − b e − s ) . (18) Proof. Lemma 7 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 9 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}\left(S_b-(1-b)F\right). D ≤ S b + H + b F e − s + b s ( S b − ( 1 − b ) F ) . Rearrange and divide by F F F .
All statements in this section allow atoms and zero values. Strict and weak inequalities differ only at a measure-zero set of height boundaries. The layer integrals are finite under F < ∞ F<\infty F < ∞ ; in particular, each nonloop has finite mean. The same arguments extend from bounded values to arbitrary integrable distributions by truncation.
A virtual basis-exchange continuation
We now give the continuation used when the reference optima have sufficient overlap. Its state is a short list of accepted records. Those records describe how to update any reference optimum, so the algorithm can work with a distribution of bases without listing that distribution.
In the efficient survival simulation of [1 Section 6] , auxiliary coordinates represent survivor sets without evaluating their probabilities. We use the same implementation principle, with fresh reference draws and deterministic basis-exchange replay. Lemma 13 establishes the distribution of the accepted process.
Fix a loopless residual matroid M M M on n n n labels, a parameter q ∈ J q\in 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 Section 9 extends the existence guarantee to general distributions. Write D e D_e D e and D e q D_e^q D e q for the original and reference distributions. Put
λ = 1 q , t 0 = 1 − δ , α = e − λ t 0 , ω = α − λ δ , (19) \lambda=\frac{1}{q},\qquad t_0=1-\delta,\qquad\alpha=e^{-\lambda t_0},\qquad\omega=\alpha-\lambda\delta, \tag*{(19)} λ = q 1 , t 0 = 1 − δ , α = e − λ t 0 , ω = α − λ δ , (19)
and assume ω > 0 \omega>0 ω > 0 . Define
Φ δ ( q , z ) = 1 − α + α ω ( 1 − e − λ δ / ω ) ( 1 + ( 1 − α ) z ) . (20) \Phi_\delta(q,z)=1-\alpha+\alpha\omega\left(1-e^{-\lambda\delta/\omega}\right)\left(1+(1-\alpha)z\right). \tag*{(20)} Φ δ ( q , z ) = 1 − α + α ω ( 1 − e − λ δ / ω ) ( 1 + ( 1 − α ) z ) . (20)
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 11 (Virtual continuation). If F = EOPT ( M , Y ) > 0 F=\operatorname{EOPT}(M,Y)>0 F = EOPT ( M , Y ) > 0 , there is a feasible online continuation with
E [ A L G ] ≥ Φ δ ( q , Q / F ) F . \mathbb{E}[\mathrm{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 Section 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 12 (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 .
Denote the resulting basis by B y ( t ) = Replay ( y , H , t ) B_y(t)=\operatorname{Replay}(y,\mathcal{H},t) B y ( t ) = Replay ( y , H , t ) . At the current decision the current label’s record has not yet been appended. The residual matroid M M M , its ground set, and the reference law remain fixed for the whole continuation. In particular, rejected labels remain in reference realizations.
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
Algorithm 1 Virtual continuation: processing an arrival ( e , v , t ) (e,v,t) ( e , v , t )
Fixed input: residual matroid M M M , parameter q q q , distributions D f , D f q D_f,D^q_f 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^q_e(\{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^q_f 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^q_f 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 .
( 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 ) , \mathcal{K}_{e,t}(dy)=\mathbf{1}\{(e,y)\text{ is live at }t\}\mu(dy), 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 ) . (21) k_e(t)=\int\mathcal{K}_{e,t}(dy),\qquad w_e(t)=\int y_e\mathcal{K}_{e,t}(dy). \tag*{(21)} k e ( t ) = ∫ K e , t ( d y ) , w e ( t ) = ∫ y e K e , t ( d y ) . (21)
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.
A Bernoulli draw with parameter p p p equals one with probability p p p . Here Z ∼ Poisson ( 2 ) Z\sim\operatorname{Poisson}(2) Z ∼ Poisson ( 2 ) means P ( Z = k ) = e − 2 2 k / k ! \mathbb{P}(Z=k)=e^{-2}2^k/k! P ( Z = k ) = e − 2 2 k / k ! for k = 0 , 1 , … k=0,1,\ldots k = 0 , 1 , … . Every rejection instruction terminates the current decision and leaves the accepted set and record list unchanged. All candidate and probe samples are fresh and independent. Probe realizations include a fresh draw for their own e e e -coordinate; they do not reuse the actual value. After t 0 t_0 t 0 , every screened live candidate is accepted.
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
An element missing from the accepted history may not yet have arrived, or may already have been rejected. The analysis must include both possibilities. The following identity does so without conditioning the reference samples on whether a label has arrived.
An acceptance mark is auxiliary data attached to an accepted element, such as its value and candidate reference realization. The accepted marked history consists of the earlier accepted labels, their acceptance times, and these marks; rejected arrivals are omitted. A subprobability kernel assigns to each possible history a measure of total mass at most one on the mark space. Here its mass on a set of marks is the probability of accepting with a mark in that set, and the missing mass is the rejection probability. The corresponding acceptance intensity is the conditional probability per unit time of such an acceptance, given the accepted history.
Lemma 13 (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 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.
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)}\mathcal{K}_{e,t} λ e − Λ e ( t ) K e , t in the early phase, and λ K e , t \lambda\mathcal{K}_{e,t} λ K e , t in the late phase. Mapping each candidate realization to its acceptance mark gives the kernel in Lemma 13 . 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\mathcal{K}_{e,t} λ K e , t . In the late phase it is r e ( t ) K e , t r_e(t)\mathcal{K}_{e,t} r e ( t ) K e , t , where
r e ( t ) = λ S e ( t ) , λ ( 1 + Λ e ( t 0 ) ) ≤ r e ( t ) ≤ λ ω . (22) r_e(t) = \frac{\lambda}{S_e(t)}, \qquad\lambda(1+\Lambda_e(t_0)) \le r_e(t) \le\frac{\lambda}{\omega}. \tag*{(22)} r e ( t ) = S e ( t ) λ , λ ( 1 + Λ e ( t 0 )) ≤ r e ( t ) ≤ ω λ . (22)
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 14 (Persistence). If the marked acceptance intensities are r e ( t ) K e , t r_e(t)\mathcal{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 ) . Integrate over source realizations to obtain the death-rate bound, and then integrate the conditional survival inequality over target realizations with weight y e y_e y e or 1 { y e > z } \mathbb{1}\{y_e > z\} 1 { y e > z } .
The proof uses a bound on the intensity of each source realization, which explains the early random rejections. Preserving only a label’s overall acceptance probability would not give the same conclusion: a value-based cutoff could concentrate acceptance on source bases whose exchanges remove the same target element.
In the early phase R = λ R=\lambda R = λ . Since E ∑ e w e ( 0 ) = F \mathbb{E}\sum_e w_e(0)=F E ∑ e w e ( 0 ) = F , its expected reward is at least ( 1 − α ) F (1-\alpha)F ( 1 − α ) F , and
E ∑ e w e ( t 0 ) ≥ α F . (23) \mathbb{E}\sum_e w_e(t_0) \ge\alpha F. \tag*{(23)} E e ∑ w e ( t 0 ) ≥ α F . (23)
We also claim
E ∑ e w e ( t 0 ) Λ e ( t 0 ) ≥ α ( 1 − α ) Q . (24) \mathbb{E}\sum_e w_e(t_0)\Lambda_e(t_0) \ge\alpha(1-\alpha)Q. \tag*{(24)} E e ∑ w e ( t 0 ) Λ e ( t 0 ) ≥ α ( 1 − α ) Q . (24)
To prove this, let u e ( t , z ) = ∫ 1 { y e > z } K e , t ( d y ) u_e(t,z)=\int1\{y_e>z\}K_{e,t}(dy) 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\,dz. 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)\,dt \\
&\ge\lambda\int_0^{t_0}e^{-\lambda(t_0-t)}e^{-2\lambda t}Q\,dt=\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 11. By (22) , 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 (23) and (24) . 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 (20) . Feasibility and the query bound were established above.
Estimating a reference instance
The algorithm needs estimates of the reference optimum, deletion surplus, stable surplus, and contraction thresholds. Estimating these quantities by sampling full values would introduce a dependence on the range of the values. Instead we sample a nonempty value layer. The normalization is the expected maximum of the reference values, which can be computed exactly from the input distributions.
Let N N N be the original ground-set size. Consider a residual matroid on n ≤ N n\le N n ≤ N nonloops and a reference parameter q ∈ J q\in J q ∈ J . Put
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 omit zero-value states, so V q > 0 V_q>0 V q > 0 . We use the symbolic parameters from Section 2.
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 all later indicators independently with probabilities 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 ≠ ∅ . (25) \Pr((j,R)) = \frac{\Delta_j}{V_q}\Pr(R_j=R), \qquad R \ne\varnothing. \tag*{(25)} Pr (( j , R )) = V q Δ j Pr ( R j = R ) , R = ∅ . (25)
Indeed, R R R has a unique first active label. This construction uses one categorical draw and at most n n n Bernoulli draws; it does not condition on nonemptiness by rejection sampling.
Let C ( R ) \mathcal{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|\mathcal{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\mathcal{C}(R)}(1-p_{e,j}), \qquad Z_e = V_q 1\{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 15 (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 q F_q,D_q,C_q,m_e^q F q , D q , C q , m e q , 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 q = ∫ 0 ∞ Pr ( e ∈ cl ( R z ∖ e ) ) d z . m_e^q=\int_0^\infty\Pr(e\in\operatorname{cl}(R_z\setminus e))\,\mathrm{d}z. m e q = ∫ 0 ∞ Pr ( e ∈ cl ( R z ∖ e )) d z .
All integrands vanish on the empty layer because the residual matroid has no loops. Equation (25) 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 ) |\mathcal{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} \Longleftrightarrow 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=\mathcal{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.
A single accuracy guarantee
Let K K K be the bound on the number of reference-parameter evaluations specified below. 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 $\widehat{F},\widehat{D},\widehat{C},\widehat{m}_e.
Lemma 16 (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 ) , \lvert\widehat{F}-F_q\rvert\le\varepsilon(F_q+V_q), ∣ F − F q ∣ ≤ ε ( F q + V q ) , ∣ D ^ − D q ∣ ≤ ε ( D q + V q ) , \lvert\widehat{D}-D_q\rvert\le\varepsilon(D_q+V_q), ∣ D − D q ∣ ≤ ε ( D q + V q ) , ∣ C ^ − C q ∣ ≤ ε ( C q + V q ) , \lvert\widehat{C}-C_q\rvert\le\varepsilon(C_q+V_q), ∣ C − C q ∣ ≤ ε ( C q + V q ) , ∣ m ^ e − m e q ∣ ≤ ε m e q + ε V q / N ( e ∈ E ) . \lvert\widehat{m}_e-m_e^q\rvert\le\varepsilon m_e^q+\varepsilon V_q/N \qquad(e\in E). ∣ m e − m e 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(\lvert\overline{W}-\mu\rvert>\gamma\mu+t)\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. At each evaluation the parameter is fixed before its fresh batch is drawn, which permits adaptive evaluations and reuse of the selected batch. □
On the accurate event, the upper estimates
m ‾ e = m ^ e + ε V q / N 1 − ε (26) \overline{m}_e=\frac{\widehat{m}_e+\varepsilon V_q/N}{1-\varepsilon} \tag*{(26)} m e = 1 − ε m e + ε V q / N (26)
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 . (27) p_e\ge a(q)m_e^q,\qquad\sum_e(p_e-bm_e^q)^+<2\varepsilon F_q. \tag*{(27)} p e ≥ a ( q ) m e q , e ∑ ( p e − b m e q ) + < 2 ε F q . (27)
Thus the same batch supplies the search statistics, the stability test, and all possible next-arrival thresholds.
Choosing the reference parameter
The search preserves the inherited potential by certifying the signs of one-sided derivatives. It does not estimate the maximum of that potential to an additive accuracy. The estimation tolerance is therefore accounted for in the local surplus conditions, without incurring an additive optimization error at each search.
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 .
The function g g g is concave: F q F_q F q is nonnegative, nondecreasing and concave, while a ( q ) a(q) a ( q ) is positive, decreasing and affine. The reference derivative bounds give
a F q q ( C q F q − d ∗ ( q ) ) ≤ g + ′ ( q ) ≤ g − ′ ( q ) ≤ a F q q ( D q F q − d ∗ ( q ) ) . (28) \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*{(28)} q a F q ( F q C q − d ∗ ( q ) ) ≤ g + ′ ( q ) ≤ g − ′ ( q ) ≤ q a F q ( F q D q − d ∗ ( q ) ) . (28)
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\leq\widehat{C}\leq\widehat{D}\leq\widehat{F} 0 ≤ C ≤ D ≤ F on every outcome. The denominator is positive because F ^ ≥ V q \widehat{F}\geq 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 δ \lvert q^{\mathrm{in}}-1\rvert<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. Perform at most K − 1 K-1 K − 1 midpoint evaluations, where
K = 1 + ⌊ log 2 max { 1 , 32 δ N 2 ε } ⌋ . (29) K=1+\left\lfloor\log_2\max\left\{1,\frac{32\delta N^2}{\varepsilon}\right\}\right\rfloor. \tag*{(29)} K = 1 + ⌊ log 2 max { 1 , ε 32 δ N 2 } ⌋ . (29)
The terminal interval has length at most ε / ( 4 N 2 ) < δ \varepsilon/(4N^2)<\delta ε / ( 4 N 2 ) < δ .
Lemma 17 (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\geq a(q^{\mathrm{in}})F_{q^{\mathrm{in}}}. a ( q ) F q ≥ a ( q in ) F q in . If ∣ q − 1 ∣ < 3 δ \lvert q-1\rvert<3\delta ∣ q − 1 ∣ < 3 δ , then
d ∗ ( q ) − 20 ε ≤ D q / F q ≤ d ∗ ( q ) + H q / F q + 20 ε . (30) d_*(q)-20\varepsilon\leq D_q/F_q\leq d_*(q)+H_q/F_q+20\varepsilon. \tag*{(30)} d ∗ ( q ) − 20 ε ≤ D q / F q ≤ d ∗ ( q ) + H q / F q + 20 ε . (30) Its saved batch satisfies all bounds of Lemma 16.
Proof. Accuracy and C q , D q ≤ F q C_q,D_q\leq 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)\leq5\varepsilon 4 ε / ( 1 − 2 ε ) ≤ 5 ε . Thus a positive batch certifies g + ′ > 0 g'_+>0 g + ′ > 0 , and a negative batch certifies g − ′ < 0 g'_-<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.
We need only a coarse continuity estimate to certify the returned point. Put q − = 1 − 4 δ ≥ 1 / 2 q_-=1-4\delta\geq1/2 q − = 1 − 4 δ ≥ 1/2 and a − = min J a ≥ 1 / 2 a_-=\min_J a\geq1/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 ∣ . \lvert D_q-D_s\rvert\leq n^2F_1\lvert q-s\rvert,\qquad\lvert H_q-H_s\rvert\leq2n^2F_1\lvert q-s\rvert,\qquad\lvert C_q-C_s\rvert\leq3n^2F_1\lvert q-s\rvert. ∣ 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 ) \lvert q-s\rvert\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\leq 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\geq q_-F_1 F q ≥ q − F 1 and, by concavity, ∣ F q − F s ∣ ≤ ( F 1 / q − ) ∣ q − s ∣ \lvert F_q-F_s\rvert\leq(F_1/q_-)\lvert q-s\rvert ∣ F q − F s ∣ ≤ ( F 1 / q − ) ∣ q − s ∣ . Since d ∗ = θ / a 2 d_*=\theta/a^2 d ∗ = θ / a 2 , each normalized function in {(xref)}(6.1) is 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\leq14n^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 δ \lvert q-1\rvert\geq3\delta ∣ q − 1 ∣ ≥ 3 δ . This proves the assertion in every case. ∎
The algorithm may compare ratios by cross multiplication. For a fixed evaluation, all estimates share the factor V q / m V_q/m V q / m , so the comparisons use the stored integer counters and known rational probabilities. No estimated ratio is used to generate a new reference parameter: parameters are obtained only by midpoint operations. With fixed algorithmic constants, there are O ( N 2 log 2 ( N + 2 ) ) O(N^2\log^2(N+2)) O ( N 2 log 2 ( N + 2 )) layer draws and O ( N 3 log 3 ( N + 2 ) ) O(N^3\log^3(N+2)) O ( N 3 log 3 ( N + 2 )) matroid independence queries over the entire outer policy.
The online algorithm and its guarantee
The algorithm has two possible actions at a residual state. A threshold step processes one actual arrival and then recomputes the reference. A virtual continuation finishes the remaining instance using Proposition 11 . The reference search decides which action can pay for the current potential.
Conditions on the parameters
We can now state the remaining scalar conditions. They are sufficient for the proof and involve no property of the input instance. 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 ) . (31) \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*{(31)}
\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 ) . (31)
The elementary restrictions (6) 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 δ , (32) \Phi_\delta(q,0)\ge a(q) \qquad\text{if }q\in J,\ |q-1|\ge3\delta, \tag*{(32)} Φ δ ( q , 0 ) ≥ a ( q ) if q ∈ J , ∣ q − 1∣ ≥ 3 δ , (32)
Φ δ ( q , z ∗ ( q ) ) ≥ a ( q ) for q ∈ J , (33) \Phi_\delta(q,z_*(q))\ge a(q) \qquad\text{for }q\in J, \tag*{(33)} Φ δ ( q , z ∗ ( q )) ≥ a ( q ) for q ∈ J , (33)
L ∗ ( q ) > b q ( d ∗ ( q ) + h + + 20 ε ) + 2 ε for q ∈ J . (34) L_*(q)>bq\bigl(d_*(q)+h_++20\varepsilon\bigr)+2\varepsilon\qquad\text{for }q\in J. \tag*{(34)} L ∗ ( q ) > b q ( d ∗ ( q ) + h + + 20 ε ) + 2 ε for q ∈ J . (34)
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. § 15 verifies these conditions simultaneously.
The policy
We now specify the state and the interface between the threshold rule and the virtual continuation. Let M 0 = ( E 0 , I 0 ) M_0=(E_0,\mathcal{I}_0) M 0 = ( E 0 , I 0 ) be the input matroid and let N = ∣ E 0 ∣ N=|E_0| N = ∣ E 0 ∣ . The original value of N N N is used in all estimation and error budgets, including after the ground set has shrunk. The state consists of an accepted independent set A A A , a residual minor M M M , and an inherited reference parameter q i n q^{\mathrm{in}} q in . If R R R denotes the set of rejected or discarded elements, the state satisfies the invariant
M = ( M 0 / A ) ∖ R . M=(M_0/A)\setminus R. M = ( M 0 / A ) ∖ R .
Initially A = R = ∅ A=R=\varnothing A = R = ∅ , M = M 0 M=M_0 M = M 0 , and q i n = 1 q^{\mathrm{in}}=1 q in = 1 . An element discarded because it is a loop is rejected when it arrives and is otherwise ignored.
At each residual state, the algorithm first removes loops and checks whether every remaining value is zero almost surely. This is an exact test on the finite input distributions. If the state has
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 § 12 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.
positive expected optimum, the algorithm performs the reference search of § 12 and retains its final sample batch. The search, the branch choice, and all thresholds are computed before the next remaining element is revealed. No actual future value is used in these computations.
There are two possible branches. A threshold step processes exactly one remaining arrival, updates the residual minor, and starts a new reference search with the selected parameter. A virtual continuation processes all remaining arrivals using Algorithm 1 with the entry minor and reference distribution fixed. On entering that continuation, its local accepted set and record list are empty: the previously accepted elements are already contracted in the entry minor. Fresh uniform clocks are sorted and attached to the remaining arrivals as in Section 4.
The maintained set A A A is feasible in the original matroid: an acceptance in the residual minor extends the already contracted independent set. There are at most N N N residual computation states, because each threshold step removes one element, and at most one virtual continuation. Whenever another threshold state is reached, the inherited reference satisfies ∣ q i n − 1 ∣ < 3 δ |q^{\mathrm{in}}-1|<3\delta ∣ q in − 1∣ < 3 δ , as required by the search. The case N = 0 N=0 N = 0 terminates before any expression containing 1 / N 1/N 1/ N is evaluated.
Conditionally on a residual state, the unseen actual values still have their independent original distributions, and their relative arrival order is uniform. Discarding loops preserves that relative order. The computation before the next arrival uses only the known distributions and fresh independent samples, so it does not change these conditional laws.
One-step progress
Lemma 18 (Local potential bound). Assume (6) and (32) –(34) , 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 δ , Proposition 11 , Q ≥ 0 Q \ge0 Q ≥ 0 , and (32) give a continuation reward of at least a F aF a F . Suppose henceforth that q q q is outside this boundary region. Reference selection then gives
d ∗ − 20 ε ≤ D / F ≤ d ∗ + H / F + 20 ε . (35) d_{\ast}-20\varepsilon\le D/F \le d_{\ast}+H/F+20\varepsilon. \tag*{(35)} d ∗ − 20 ε ≤ D / F ≤ d ∗ + H / F + 20 ε . (35)
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 the stability test fires, then H / F > h − > 0 H/F>h_{-}>0 H / F > h − > 0 . By Lemma 5 and (35) ,
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_{\ast}+20\varepsilon+H/F}\ge z_{\ast}(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 (33) and Proposition 11 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 (31) , 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 10 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_{\ast}+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_{\ast}+20\varepsilon-(1-b)-be^{-s}\bigr)-bq(d_{\ast}+h+20\varepsilon) \\
&\ge L_{\ast}(q)-bq(d_{\ast}+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 (34) . Thus
S b > b q D + 2 ε F . (36) S_b>bqD+2\varepsilon F. \tag*{(36)} S b > b q D + 2 εF . (36)
For the proof, define the threshold p e p_e p e for every remaining label, using the saved batch; the implementation only needs that of the next arrival. Equations (26) and (27) 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 (36) , 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) = a m_e. a F q ( M ∖ e ) − a F q ( M / e ) = a m e .
Since p e ≥ a m e p_e \ge a m_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 19 (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 ) 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 3 and (6) imply
0 ≤ P ( M , q ) ≤ ( max u ∈ J a ( u ) ) q + F 1 ( M ) ≤ F 0 . 0 \le 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 16 . On that event, Lemma 18 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 ) .
Section 8 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 ρ .
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 Section 9.
There are two separate sources of error. Inaccurate statistical estimates have already been assigned total expected loss at most ρ F 0 \rho F_0 ρ F 0 . This section assigns a further ρ F 0 \rho F_0 ρ F 0 to all finite-precision random draws. The latter estimate is uniform for each fixed actual value vector and arrival order, so it requires no bound on the magnitudes of the realized rewards.
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 N_{\mathrm{sin}} N sin 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 ) . More samples add only O ( log m ) O(\log m) O ( log m ) bits and one factor m m m to the denominators. The affine discount and thresholds therefore also 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. These facts rule out repeated multiplication of unrelated denominators across successive states.
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 = N_{\mathrm{sin}} + N + T + 3. T = ⌈ log 2 ρ 8 N ⌉ , C cat = S ( N + 2 ) + N 2 ( 1 + T ) + 2 N + N T , J 0 = N sin + 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 ) ρ . (37) G\delta\in\mathbb{Z},\qquad G \ge\frac{2(4N^2+C_{\mathrm{cat}}J_0)}{\rho}. \tag*{(37)} G δ ∈ Z , G ≥ ρ 2 ( 4 N 2 + C cat J 0 ) . (37)
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 20 (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 21 (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 20 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 (37) 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(N^4\log(N+2)) \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.
A choice of parameters
We complete the matroid analysis with a rational choice that yields a gain of 1.01 × 10 − 6 1.01\times10^{-6} 1.01 × 1 0 − 6 . All inequalities are verified uniformly on J J J using rational arithmetic and elementary Taylor bounds. Set
δ = 3 2048 , θ = 36787843 10 8 , ε = 1 10 6 , η = 49 1000 , \delta=\frac{3}{2048},\qquad\theta=\frac{36787843}{10^8},\qquad\varepsilon=\frac{1}{10^6},\qquad\eta=\frac{49}{1000}, δ = 2048 3 , θ = 1 0 8 36787843 , ε = 1 0 6 1 , η = 1000 49 ,
s = 5 2 , ρ = ε 3 = 1 10 18 , ε 0 = 101 10 8 . (38) s=\frac{5}{2},\qquad\rho=\varepsilon^3=\frac{1}{10^{18}},\qquad\varepsilon_0=\frac{101}{10^8}. \tag*{(38)} s = 2 5 , ρ = ε 3 = 1 0 18 1 , ε 0 = 1 0 8 101 . (38)
Thus J = [ 509 / 512 , 515 / 512 ] J=[509/512,515/512] J = [ 509/512 , 515/512 ] and a ( q ) = 1 − θ q a(q)=1-\theta q a ( q ) = 1 − θ q . We use the definitions of d ∗ , h − , h + , b , Φ δ d_*,h_-,h_+,b,\Phi_\delta d ∗ , h − , h + , b , Φ δ , and z ∗ z_* z ∗ from the preceding sections.
Lemma 22 (Parameter choice). The parameters in (38) satisfy the basic parameter restrictions. For every q ∈ J q\in J q ∈ J , one has ω > 0 \omega>0 ω > 0 , q ( b + s ) > 1 q(b+s)>1 q ( b + s ) > 1 , and
Φ δ ( q , z ∗ ) > a ( q ) , \Phi_\delta(q,z_*)>a(q), Φ δ ( q , z ∗ ) > a ( q ) , 1 − b + b b + s ( d ∗ + 20 ε − ( 1 − b ) − b e − s ) > b q ( d ∗ + h + + 20 ε ) + 2 ε . 1-b+\frac{b}{b+s}\left(d_*+20\varepsilon-(1-b)-be^{-s}\right)>bq\left(d_*+h_++20\varepsilon\right)+2\varepsilon. 1 − b + b + s b ( d ∗ + 20 ε − ( 1 − b ) − b e − s ) > b q ( d ∗ + h + + 20 ε ) + 2 ε . For q ∈ J q\in J q ∈ J with ∣ q − 1 ∣ ≥ 3 δ |q-1|\ge3\delta ∣ q − 1∣ ≥ 3 δ , one also has Φ δ ( q , 0 ) > a ( q ) \Phi_\delta(q,0)>a(q) Φ δ ( q , 0 ) > a ( q ) . Finally,*
1 − θ − 2 ρ > 1 − 1 e + ε 0 . 1-\theta-2\rho>1-\frac{1}{e}+\varepsilon_0. 1 − θ − 2 ρ > 1 − e 1 + ε 0 .
Proof. Put u = e − 1 u=e^{-1} u = e − 1 and S 16 = ∑ j = 0 16 1 / j ! S_{16}=\sum_{j=0}^{16}1/j! S 16 = ∑ j = 0 16 1/ j ! . The exponential series and direct rational comparison give
S 16 < e < S 16 + 2 17 ! , u − : = 36787944117 10 11 < u < 36787944118 10 11 = : u + . S_{16}<e<S_{16}+\frac{2}{17!},\qquad
u_-:=\frac{36787944117}{10^{11}}<u<\frac{36787944118}{10^{11}}=:u_+. S 16 < e < S 16 + 17 ! 2 , u − := 1 0 11 36787944117 < u < 1 0 11 36787944118 =: u + .
We will also use e − 5 / 2 < 821 / 10000 e^{-5/2}<821/10000 e − 5/2 < 821/10000 , which follows from
e 5 / 2 > ∑ j = 0 10 ( 5 / 2 ) j j ! = 1810641293 148635648 > 10000 821 . e^{5/2}>\sum_{j=0}^{10}\frac{(5/2)^j}{j!}=\frac{1810641293}{148635648}>\frac{10000}{821}. e 5/2 > j = 0 ∑ 10 j ! ( 5/2 ) j = 148635648 1810641293 > 821 10000 .
Elementary bounds. Write k = ( 1 + ε ) / ( 1 − ε ) = 1000001 / 999999 k=(1+\varepsilon)/(1-\varepsilon)=1000001/999999 k = ( 1 + ε ) / ( 1 − ε ) = 1000001/999999 , so b = k a b=ka b = k a . Direct rational comparisons give, uniformly on J J J ,
99 100 < q < 101 100 , 5 8 < a < b < 16 25 , 1 < k < 1001 1000 , k θ < 369 1000 . (39) \frac{99}{100}<q<\frac{101}{100},\qquad\frac{5}{8}<a<b<\frac{16}{25},\qquad1<k<\frac{1001}{1000},\qquad k\theta<\frac{369}{1000}. \tag*{(39)} 100 99 < q < 100 101 , 8 5 < a < b < 25 16 , 1 < k < 1000 1001 , k θ < 1000 369 . (39)
The restrictions 0 < ε ≤ δ ≤ 1 / 8 0<\varepsilon\leq\delta\leq1/8 0 < ε ≤ δ ≤ 1/8 , ε ≤ 1 / 10 \varepsilon\leq1/10 ε ≤ 1/10 , 0 < θ , ρ < 1 0<\theta,\rho<1 0 < θ , ρ < 1 , s > 0 s>0 s > 0 , and η > 10 ε \eta>10\varepsilon η > 10 ε follow immediately from the parameter values. The bounds on a a a imply 1 / 2 < a < 3 / 4 1/2<a<3/4 1/2 < a < 3/4 ,
( max q ∈ J a ( q ) ) q + < 16 25 101 100 < 1 , d ∗ − 20 ε < d ∗ < 3 5 < 1. \left(\max_{q\in J}a(q)\right)q_+<\frac{16}{25}\frac{101}{100}<1,\qquad d_*-20\varepsilon<d_*<\frac{3}{5}<1. ( q ∈ J max a ( q ) ) q + < 25 16 100 101 < 1 , d ∗ − 20 ε < d ∗ < 5 3 < 1.
Also b + s > 3 b+s>3 b + s > 3 , so q ( b + s ) > ( 99 / 100 ) 3 > 1 q(b+s)>(99/100)3>1 q ( b + s ) > ( 99/100 ) 3 > 1 .
A uniform bound for the continuation. Write a 0 ( q ) = 1 − e − 1 / q a_0(q)=1-e^{-1/q} a 0 ( q ) = 1 − e − 1/ q , x = λ δ x=\lambda\delta x = λ δ , and α = e − λ ( 1 − δ ) \alpha=e^{-\lambda(1-\delta)} α = e − λ ( 1 − δ ) . On J J J ,
512 515 ≤ λ ≤ 512 509 , 409 412 ≤ λ ( 1 − δ ) ≤ 2045 2036 , x ≤ X : = 3 2036 . \frac{512}{515}\leq\lambda\leq\frac{512}{509},\qquad\frac{409}{412}\leq\lambda(1-\delta)\leq\frac{2045}{2036},\qquad x\leq X:=\frac{3}{2036}. 515 512 ≤ λ ≤ 509 512 , 412 409 ≤ λ ( 1 − δ ) ≤ 2036 2045 , x ≤ X := 2036 3 .
The inequalities e − t ≥ 1 − t e^{-t}\geq1-t e − t ≥ 1 − t and e t ≤ 1 / ( 1 − t ) e^t\leq1/(1-t) e t ≤ 1/ ( 1 − t ) for 0 ≤ t < 1 0\leq t<1 0 ≤ t < 1 yield
A − : = u − − 2027 2036 < α < u + − 412 409 = : A + . A_-:=u_--\frac{2027}{2036}<\alpha<u_+-\frac{412}{409}=:A_+. A − := u − − 2036 2027 < α < u + − 409 412 =: A + .
In particular, 0 < A − < A + < 1 / 2 0<A_-<A_+<1/2 0 < A − < A + < 1/2 and ω = α − x > W : = A − − X > 9 / 25 > 0 \omega=\alpha-x>W:=A_--X>9/25>0 ω = α − x > W := A − − X > 9/25 > 0 .
Apply 1 − e − t ≥ t − t 2 / 2 1-e^{-t}\geq t-t^2/2 1 − e − t ≥ t − t 2 /2 to the definition of Φ δ \Phi_\delta Φ δ , and use e − x ≥ 1 − x + x 2 / 2 − x 3 / 6 e^{-x}\geq1-x+x^2/2-x^3/6 e − x ≥ 1 − x + x 2 /2 − x 3 /6 . Since e − λ = α e − x e^{-\lambda}=\alpha e^{-x} e − λ = α e − x and α / ω = 1 + x / ω \alpha/\omega=1+x/\omega α / ω = 1 + x / ω , for every z ≥ 0 z\geq0 z ≥ 0 we obtain
Φ δ ( q , z ) − a 0 ( q ) ≥ − δ 2 λ 2 ( 1 − α 2 + x 2 ω + α x 6 ) + δ λ α ( 1 − α ) ( 1 − x 2 ω ) z . (40) \Phi_\delta(q,z)-a_0(q)\geq-\delta^2\lambda^2\left(\frac{1-\alpha}{2}+\frac{x}{2\omega}+\frac{\alpha x}{6}\right)+\delta\lambda\alpha(1-\alpha)\left(1-\frac{x}{2\omega}\right)z. \tag*{(40)} Φ δ ( q , z ) − a 0 ( q ) ≥ − δ 2 λ 2 ( 2 1 − α + 2 ω x + 6 α x ) + δ λ α ( 1 − α ) ( 1 − 2 ω x ) z . (40)
For example, its constant term follows from
α ( e − x − 1 + x − x 2 2 ω ) ≥ − x 2 ( 1 − α 2 + x 2 ω + α x 6 ) . \alpha\left(e^{-x}-1+x-\frac{x^2}{2\omega}\right)\geq-x^2\left(\frac{1-\alpha}{2}+\frac{x}{2\omega}+\frac{\alpha x}{6}\right). α ( e − x − 1 + x − 2 ω x 2 ) ≥ − x 2 ( 2 1 − α + 2 ω x + 6 α x ) .
The preceding rational bounds give
λ 2 ( 1 − α 2 + x 2 ω + α x 6 ) < ( 512 509 ) 2 ( 1 − A − 2 + X 2 W + A + X 6 ) < 323 1000 , \lambda^2\left(\frac{1-\alpha}{2}+\frac{x}{2\omega}+\frac{\alpha x}{6}\right)<\left(\frac{512}{509}\right)^2\left(\frac{1-A_-}{2}+\frac{X}{2W}+\frac{A_+X}{6}\right)<\frac{323}{1000}, λ 2 ( 2 1 − α + 2 ω x + 6 α x ) < ( 509 512 ) 2 ( 2 1 − A − + 2 W X + 6 A + X ) < 1000 323 ,
λ α ( 1 − α ) ( 1 − x 2 ω ) > 512 515 A − ( 1 − A − ) ( 1 − X 2 W ) > 23 100 . \lambda\alpha(1-\alpha)\left(1-\frac{x}{2\omega}\right)>\frac{512}{515}A_-(1-A_-)\left(1-\frac{X}{2W}\right)>\frac{23}{100}. λ α ( 1 − α ) ( 1 − 2 ω x ) > 515 512 A − ( 1 − A − ) ( 1 − 2 W X ) > 100 23 .
In the second line, α ( 1 − α ) \alpha(1-\alpha) α ( 1 − α ) is increasing on the relevant interval, which lies below 1 / 2 1/2 1/2 . Thus
Φ δ ( q , z ) ≥ a 0 ( q ) + 23 100 δ z − 323 1000 δ 2 ( q ∈ J , z ≥ 0 ) . (41) \Phi_\delta(q,z)\geq a_0(q)+\frac{23}{100}\delta z-\frac{323}{1000}\delta^2\qquad(q\in J,\ z\geq0). \tag*{(41)} Φ δ ( q , z ) ≥ a 0 ( q ) + 100 23 δ z − 1000 323 δ 2 ( q ∈ J , z ≥ 0 ) . (41)
The affine discount and the boundary region. Put Δ θ = u + − θ = 101118 / 10 11 \Delta_\theta=u_+-\theta=101118/10^{11} Δ θ = u + − θ = 101118/1 0 11 . The inequality t e − t ≤ e − 1 te^{-t}\le e^{-1} t e − t ≤ e − 1 for t > 0 t>0 t > 0 yields
a ( q ) − a 0 ( q ) = e − 1 / q − θ q ≤ q ( u − θ ) < q + Δ θ . (42) a(q)-a_0(q)=e^{-1/q}-\theta q\le q(u-\theta)<q+\Delta_\theta. \tag*{(42)} a ( q ) − a 0 ( q ) = e − 1/ q − θ q ≤ q ( u − θ ) < q + Δ θ . (42)
For the boundary region, put w = a − a 0 w=a-a_0 w = a − a 0 . On J J J ,
a 0 ′ ′ ( q ) = e − 1 / q 2 q − 1 q 4 > u − ( 1 − 3 509 ) 2 ( 509 / 512 ) − 1 ( 515 / 512 ) 4 > 1 3 . a_0''(q)=e^{-1/q}\frac{2q-1}{q^4}>u_-\left(1-\frac{3}{509}\right)\frac{2(509/512)-1}{(515/512)^4}>\frac{1}{3}. a 0 ′′ ( q ) = e − 1/ q q 4 2 q − 1 > u − ( 1 − 509 3 ) ( 515/512 ) 4 2 ( 509/512 ) − 1 > 3 1 .
Here e − 1 / q ≥ u e − 3 / 509 ≥ u ( 1 − 3 / 509 ) e^{-1/q}\ge ue^{-3/509}\ge u(1-3/509) e − 1/ q ≥ u e − 3/509 ≥ u ( 1 − 3/509 ) . Since w ( 1 ) = w ′ ( 1 ) = u − θ w(1)=w'(1)=u-\theta w ( 1 ) = w ′ ( 1 ) = u − θ , Taylor’s theorem gives
w ( q ) ≤ q ( u − θ ) − 1 6 ( q − 1 ) 2 < q + Δ θ − 1 6 ( q − 1 ) 2 . w(q)\le q(u-\theta)-\frac{1}{6}(q-1)^2<q+\Delta_\theta-\frac{1}{6}(q-1)^2. w ( q ) ≤ q ( u − θ ) − 6 1 ( q − 1 ) 2 < q + Δ θ − 6 1 ( q − 1 ) 2 .
The rational comparison
( 3 2 − 323 1000 ) δ 2 − q + Δ θ = 494293197 327680000000000 > 0 \left(\frac{3}{2}-\frac{323}{1000}\right)\delta^2-q+\Delta_\theta=\frac{494293197}{327680000000000}>0 ( 2 3 − 1000 323 ) δ 2 − q + Δ θ = 327680000000000 494293197 > 0
shows that w ( q ) < − ( 323 / 1000 ) δ 2 w(q)<-(323/1000)\delta^2 w ( q ) < − ( 323/1000 ) δ 2 when ∣ q − 1 ∣ ≥ 3 δ |q-1|\ge3\delta ∣ q − 1∣ ≥ 3 δ . Equation (41) with z = 0 z=0 z = 0 now proves the boundary condition.
The stability branch. The function d ∗ ( q ) = θ q / ( 1 − θ q ) d_*(q)=\theta q/(1-\theta q) d ∗ ( q ) = θ q / ( 1 − θ q ) is increasing. Since h − = 4899 / 100000 h_-=4899/100000 h − = 4899/100000 , direct rational substitution gives
z ∗ ( q ) ≥ ( 4899 / 100000 ) 2 1 − d ∗ ( 509 / 512 ) + 1 / 50000 + 4899 / 100000 > 127 25000 . z_*(q)\ge\frac{(4899/100000)^2}{1-d_*(509/512)+1/50000+4899/100000}>\frac{127}{25000}. z ∗ ( q ) ≥ 1 − d ∗ ( 509/512 ) + 1/50000 + 4899/100000 ( 4899/100000 ) 2 > 25000 127 .
The denominators are positive by the basic restrictions. Combining this bound with (41) and (42) , we obtain
Φ δ ( q , z ∗ ) − a ( q ) > 23 100 3 2048 127 25000 − 323 1000 ( 3 2048 ) 2 − 515 512 101118 10 11 = 437697 327680000000000 > 1 10 9 . \begin{aligned}
\Phi_\delta(q,z_*)-a(q)&>\frac{23}{100}\frac{3}{2048}\frac{127}{25000}-\frac{323}{1000}\left(\frac{3}{2048}\right)^2-\frac{515}{512}\frac{101118}{10^{11}}\\
&=\frac{437697}{327680000000000}>\frac{1}{10^9}.
\end{aligned} Φ δ ( q , z ∗ ) − a ( q ) > 100 23 2048 3 25000 127 − 1000 323 ( 2048 3 ) 2 − 512 515 1 0 11 101118 = 327680000000000 437697 > 1 0 9 1 .
This proves the stability condition uniformly on J J J .
The threshold branch. Define the difference between the two sides of the required inequality by
T ( q ) = 1 − b + b b + s ( d ∗ + 20 ε − ( 1 − b ) − b e − s ) − b q ( d ∗ + h + + 20 ε ) − 2 ε . T(q)=1-b+\frac{b}{b+s}\left(d_*+20\varepsilon-(1-b)-be^{-s}\right)-bq(d_*+h_++20\varepsilon)-2\varepsilon. T ( q ) = 1 − b + b + s b ( d ∗ + 20 ε − ( 1 − b ) − b e − s ) − b q ( d ∗ + h + + 20 ε ) − 2 ε .
We first show that T T T is decreasing on J J J . Using b = k a b=ka b = k a , a d ∗ = θ q ad_*=\theta q a d ∗ = θ q , and a = 1 − θ q a=1-\theta q a = 1 − θ q , write
T ( q ) = 1 − k a − k θ q 2 − k a q ( h + + 20 ε ) − 2 ε + R ( q ) k a + s , T(q)=1-ka-k\theta q^2-kaq(h_++20\varepsilon)-2\varepsilon+\frac{R(q)}{ka+s}, T ( q ) = 1 − k a − k θ q 2 − k a q ( h + + 20 ε ) − 2 ε + k a + s R ( q ) ,
R ( q ) = k ( θ q − a + k a 2 ( 1 − e − s ) + 20 ε a ) . R(q)=k\left(\theta q-a+ka^2(1-e^{-s})+20\varepsilon a\right). R ( q ) = k ( θ q − a + k a 2 ( 1 − e − s ) + 20 ε a ) .
Here θ q = 1 − a < 3 / 8 \theta q=1-a<3/8 θ q = 1 − a < 3/8 , so 1 − 2 θ q > 0 1-2\theta q>0 1 − 2 θ q > 0 . By (39) ,
R ( q ) < 1001 1000 ( 3 8 + 1001 1000 ( 16 25 ) 2 + 1 50000 16 25 ) < 1 , R ′ ( q ) = k θ ( 2 − 2 k a ( 1 − e − s ) − 20 ε ) < 2 k θ . R(q)<\frac{1001}{1000}\left(\frac{3}{8}+\frac{1001}{1000}\left(\frac{16}{25}\right)^2+\frac{1}{50000}\frac{16}{25}\right)<1,\qquad R'(q)=k\theta(2-2ka(1-e^{-s})-20\varepsilon)<2k\theta. R ( q ) < 1000 1001 ( 8 3 + 1000 1001 ( 25 16 ) 2 + 50000 1 25 16 ) < 1 , R ′ ( q ) = k θ ( 2 − 2 k a ( 1 − e − s ) − 20 ε ) < 2 k θ .
Differentiating and using k a + s > 3 ka+s>3 k a + s > 3 therefore gives
T ′ ( q ) = k θ ( 1 − 2 q ) − k ( h + + 20 ε ) ( 1 − 2 θ q ) + R ′ ( q ) k a + s + k θ R ( q ) ( k a + s ) 2 < − 98 100 θ + 2 ( 369 / 1000 ) 3 + 369 / 1000 9 < 0. \begin{aligned}
T'(q)=k\theta(1-2q)-k(h_{+}+20\varepsilon)(1-2\theta q)+\frac{R'(q)}{ka+s}+\frac{k\theta R(q)}{(ka+s)^2} \\
&<-\frac{98}{100}\theta+\frac{2(369/1000)}{3}+\frac{369/1000}{9}<0.
\end{aligned} T ′ ( q ) = k θ ( 1 − 2 q ) − k ( h + + 20 ε ) ( 1 − 2 θ q ) + k a + s R ′ ( q ) + ( k a + s ) 2 k θ R ( q ) < − 100 98 θ + 3 2 ( 369/1000 ) + 9 369/1000 < 0.
It remains to check q = q + q=q_{+} q = q + . Write b + = b ( 515 / 512 ) b_{+}=b(515/512) b + = b ( 515/512 ) and d + = d ∗ ( 515 / 512 ) d_{+}=d_{*}(515/512) d + = d ∗ ( 515/512 ) . The bound e − 5 / 2 < 821 / 10000 e^{-5/2}<821/10000 e − 5/2 < 821/10000 and direct rational substitution give
T ( q + ) > 1 − b + + b + b + + 5 / 2 ( d + + 1 50000 − ( 1 − b + ) − 821 b + 10000 ) T(q_{+})>1-b_{+}+\frac{b_{+}}{b_{+}+5/2}\left(d_{+}+\frac{1}{50000}-(1-b_{+})-\frac{821b_{+}}{10000}\right) T ( q + ) > 1 − b + + b + + 5/2 b + ( d + + 50000 1 − ( 1 − b + ) − 10000 821 b + )
− b + 515 512 ( d + + 4903 100000 ) − 1 500000 > 1 10000 . -b_{+}\frac{515}{512}\left(d_{+}+\frac{4903}{100000}\right)-\frac{1}{500000}>\frac{1}{10000}. − b + 512 515 ( d + + 100000 4903 ) − 500000 1 > 10000 1 .
Hence T ( q ) > 0 T(q)>0 T ( q ) > 0 throughout J J J , as required.
Final gain. The Taylor certificate at the start of the proof gives
e − 1 − θ − 2 ρ > 36787944117 10 11 − 36787843 10 8 − 2 10 18 = 1011169999998 10 18 > 101 10 8 = ε 0 . e^{-1}-\theta-2\rho>\frac{36787944117}{10^{11}}-\frac{36787843}{10^{8}}-\frac{2}{10^{18}}=\frac{1011169999998}{10^{18}}>\frac{101}{10^{8}}=\varepsilon_{0}. e − 1 − θ − 2 ρ > 1 0 11 36787944117 − 1 0 8 36787843 − 1 0 18 2 = 1 0 18 1011169999998 > 1 0 8 101 = ε 0 .
This is the claimed competitive-ratio improvement after both error budgets have been charged. □
Proof of Theorem 1 . First consider explicit finite distributions with rational values and probabilities. Use the parameters in Lemma 22 . Proposition 19 gives the ideal policy expected reward at least ( 1 − θ − ρ ) F 0 (1-\theta-\rho)F_{0} ( 1 − θ − ρ ) F 0 . Lemma 21 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 . The zero-benchmark case is immediate. The query bounds and worst-case polynomial arithmetic and random-bit bounds are those of § 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. □
The sharp bound for XOS valuations
The matroid theorem improves the random-order guarantee of Ehsani et al. [12 ] . Such an improvement cannot hold for the full class of combinatorial auctions with XOS valuations. We prove Theorem 2 by an explicit construction with independent and identically distributed buyer valuations.
Recall that an XOS valuation on an item set M M M has the form
v ( S ) = max ℓ ∈ L ∑ j ∈ S w ℓ j , w ℓ j ≥ 0. v(S)=\max_{\ell\in\mathcal{L}}\sum_{j\in S}w_{\ell j},\qquad w_{\ell j}\ge0. v ( S ) = ℓ ∈ L max j ∈ S ∑ w ℓ j , w ℓ j ≥ 0.
Each buyer’s valuation is drawn independently from a known distribution. Buyers arrive in uniformly random order, and a buyer must receive her bundle at her arrival. Allocations are disjoint and irrevocable. The benchmark is the expected welfare of an optimal integral allocation after all valuations have been revealed.
Together with the 1 − 1 / e 1-1/e 1 − 1/ e guarantee of Ehsani, Hajiaghayi, Kesselheim, and Singla [12 ] , the theorem determines the optimal universal competitive ratio for this model. The universal upper bound also follows from the known-i.i.d. coverage lower bound of Udwani and Wajc [29 ] by the transposition described in § 16.3 . We include a direct construction because it exposes the precise distinction from the matroid problem and requires only an elementary counting argument.
Proof idea. The items admit many public partitions into n n n equal parts. Parts from different partitions overlap exactly as independent sets of density 1 / n 1/n 1/ n would overlap. A buyer’s type specifies one allowable part in each of several partitions, and her value is the maximum number of allocated items in an allowable part. The realized types jointly identify a partition whose parts the prophet can allocate without loss. An online allocation, however, fixes a supporting clause before later types are known. Two buyers can use the same partition only if an earlier choice correctly predicts a feature of a later type. With high probability all online supporting clauses therefore use different partitions. Their union covers only a 1 − 1 / e + o ( 1 ) 1-1/e+o(1) 1 − 1/ e + o ( 1 ) fraction of the items, which bounds the total online welfare.
A public family of independent partitions
Fix n ≥ 2 n\ge2 n ≥ 2 and a finite index set T \mathcal{T} T . The items are the functions from T \mathcal{T} T to [ n ] [n] [ n ] :
M = [ n ] T , m = ∣ M ∣ = n ∣ T ∣ . M=[n]^{\mathcal{T}},\qquad m=|M|=n^{|\mathcal{T}|}. M = [ n ] T , m = ∣ M ∣ = n ∣ T ∣ .
For every s ∈ T s\in\mathcal{T} s ∈ T , define a partition of M M M by
P s r = { x ∈ M : x ( s ) = r } , r ∈ [ n ] . P_s^r=\{x\in M:x(s)=r\},\qquad r\in[n]. P s r = { x ∈ M : x ( s ) = r } , r ∈ [ n ] .
These are deterministic, publicly known sets. A uniformly random item is useful only for counting: its coordinates at different indices are independent and uniform on [ n ] [n] [ n ] .
Lemma 23 (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. An item lies outside the union precisely when its s i s_i s i -coordinate differs from r i r_i r i for every i i i . There are ( n − 1 ) k n ∣ T ∣ − k (n-1)^k n^{|\mathcal{T}|-k} ( n − 1 ) k n ∣ T ∣ − k such items.
The lemma holds for every choice of distinct indices. In particular, it remains valid when the indices are chosen adaptively; we will not need any independence assumption on the algorithm’s choices.
Independent and identically distributed valuations
Let L ≥ n L \ge n L ≥ n be an integer and take
T = ( [ L ] n ) . \mathcal{T} = \binom{[L]}{n}. T = ( n [ L ] ) .
For a ∈ s a \in s a ∈ s , write r s ( a ) r_s(a) r s ( a ) for the position of a a a in the increasing ordering of s s s . For every label a ∈ [ L ] a \in[L] a ∈ [ L ] , define the valuation
v a ( S ) = max s ∈ T a ∈ s ∣ S ∩ P s r s ( a ) ∣ . (43) v^a(S) = \max_{\substack{s \in\mathcal{T} \\ a \in s}} \left|S \cap P_s^{r_s(a)}\right|. \tag*{(43)} v a ( S ) = s ∈ T a ∈ s max S ∩ P s r s ( a ) . (43)
Each of the n n n buyers independently draws a uniform label from [ L ] [L] [ L ] and has the corresponding valuation. Thus all buyers have the same distribution. Each clause in (43) is additive with binary coefficients, so the valuations are normalized, monotone, and XOS. Moreover,
v a ( S ) ≤ ∣ S ∣ , v a ( M ) = m / n . (44) v^a(S) \le|S|,\qquad v^a(M) = m/n. \tag*{(44)} v a ( S ) ≤ ∣ S ∣ , v a ( M ) = m / n . (44)
We give the algorithm the label itself at each arrival. Revealing this additional information only strengthens the upper bound.
The prophet’s allocation. If the realized labels a 1 , … , a n a_1,\ldots,a_n a 1 , … , a n are distinct, they form an index s = { a 1 , … , a n } ∈ T s = \{a_1,\ldots,a_n\} \in\mathcal{T} s = { a 1 , … , a n } ∈ T . Assigning P s r s ( a i ) P_s^{r_s(a_i)} P s r s ( a i ) to buyer i i i partitions all of M M M and gives welfare m m m . No feasible allocation has welfare greater than m m m , by (44) . A union bound on repeated labels gives
E [ O P T ] ≥ m ( 1 − ( n 2 ) L ) . (45) \mathbb{E}[\mathrm{OPT}] \ge m\left(1-\frac{\binom{n}{2}}{L}\right). \tag*{(45)} E [ OPT ] ≥ m ( 1 − L ( 2 n ) ) . (45)
A witness fixed at each arrival. Fix an arbitrary randomized online algorithm. Condition on the entire arrival permutation and on its independent random tape, and index buyers by arrival position. Let A t A_t A t be the label seen at position t t t and let S t S_t S t be the bundle allocated there. The labels A 1 , … , A n A_1,\ldots,A_n A 1 , … , A n remain independent and uniform on [ L ] [L] [ L ] .
After S t S_t S t is chosen, select a maximizing index in (43) , breaking ties by a fixed public ordering:
W t ∈ T , A t ∈ W t , v A t ( S t ) = ∣ S t ∩ P W t r W t ( A t ) ∣ . (46) W_t \in\mathcal{T},\qquad A_t \in W_t,\qquad v^{A_t}(S_t) = \left|S_t \cap P_{W_t}^{r_{W_t}(A_t)}\right|. \tag*{(46)} W t ∈ T , A t ∈ W t , v A t ( S t ) = S t ∩ P W t r W t ( A t ) . (46)
The index W t W_t W t is an analysis variable; the algorithm need not compute it. What matters is that it is determined when S t S_t S t becomes irrevocable. A canonical witness exists for an empty bundle as well.
For t < u t < u t < u , equality of witnesses forces
W t = W u ⟹ A u ∈ W t . W_t = W_u \Longrightarrow A_u \in W_t. W t = W u ⟹ A u ∈ W t .
Conditional on the history at position t t t , the set W t W_t W t has n n n labels whereas A u A_u A u is still uniform on [ L ] [L] [ L ] . Consequently,
Pr [ W t = W u ] ≤ n L , Pr [ some two witnesses coincide ] ≤ n ( n 2 ) L . (47) \Pr[W_t = W_u] \le\frac{n}{L},\qquad
\Pr[\text{some two witnesses coincide}] \le\frac{n\binom{n}{2}}{L}. \tag*{(47)} Pr [ W t = W u ] ≤ L n , Pr [ some two witnesses coincide ] ≤ L n ( 2 n ) . (47)
The first inequality does not condition on the future witness W u W_u W u . It uses only the necessary event A u ∈ W t A_u \in W_t A u ∈ W t , whose probability is already fixed when W t W_t W t is chosen. Averaging over the random tape and arrival permutation preserves both inequalities.
The online welfare. The credited sets
S t ∩ P W t r W t ( A t ) , t ∈ [ n ] , S_t \cap P_{W_t}^{rW_t(A_t)}, \qquad t \in[n], S t ∩ P W t r W t ( A t ) , t ∈ [ n ] ,
are pairwise disjoint because the allocated bundles are disjoint. Their total cardinality equals the algorithm’s welfare. Therefore, on the event that the witnesses are all distinct, Lemma 23 implies
ALG ≤ ∣ ⋃ t = 1 n P W t r W t ( A t ) ∣ = m ( 1 − ( 1 − 1 n ) n ) . \operatorname{ALG} \le\left|\bigcup_{t=1}^{n} P_{W_t}^{rW_t(A_t)}\right| = m\left(1-\left(1-\frac{1}{n}\right)^n\right). ALG ≤ t = 1 ⋃ n P W t r W t ( A t ) = m ( 1 − ( 1 − n 1 ) n ) .
On the remaining event, the elementary bound ALG ≤ m \operatorname{ALG} \le m ALG ≤ m suffices. Put c n = 1 − ( 1 − 1 / n ) n c_n = 1-(1-1/n)^n c n = 1 − ( 1 − 1/ n ) n . It follows that
E [ ALG ] ≤ m ( c n + n ( n 2 ) L ) . (48) \mathbb{E}[\operatorname{ALG}] \le m\left(c_n+\frac{n\binom{n}{2}}{L}\right). \tag*{(48)} E [ ALG ] ≤ m ( c n + L n ( 2 n ) ) . (48)
Proof of Theorem 2. Combining (45) and (48) , for L ≥ ( n 2 ) L \ge\binom{n}{2} L ≥ ( 2 n ) we obtain
E [ ALG ] E [ OPT ] ≤ c n + n ( n 2 ) / L 1 − ( n 2 ) / L . (49) \frac{\mathbb{E}[\operatorname{ALG}]}{\mathbb{E}[\operatorname{OPT}]} \le\frac{c_n+n\binom{n}{2}/L}{1-\binom{n}{2}/L}. \tag*{(49)} E [ OPT ] E [ ALG ] ≤ 1 − ( 2 n ) / L c n + n ( 2 n ) / L . (49)
Since c n → 1 − 1 / e c_n \to1-1/e c n → 1 − 1/ e , first 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 choose L L L sufficiently large that the right-hand side of (49) is less than 1 − 1 / e + ξ 1-1/e+\xi 1 − 1/ e + ξ . The resulting instance depends only on ξ \xi ξ , and the estimate holds simultaneously for every online algorithm.
Input representation. The proof does not hide the partitions or impose a query limit. Across the common distribution there are 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 each clause’s m m m binary coefficients takes n m ∣ T ∣ = n m log n m nm|\mathcal{T}|=nm\log_n m nm ∣ T ∣ = nm log n m entries, polynomial in n n n and m m m . The item universe is large, as is permissible in a worst-case information-theoretic construction. The algorithm may inspect the entire explicit input and perform arbitrary independent simulations from the known distributions; none reveals an unarrived actual label.
Relation to coverage welfare and prior work
Udwani and Wajc [29 Theorem 1.2] prove a 1 − 1 / e 1-1/e 1 − 1/ e information-theoretic upper bound for item-arrival coverage welfare under known i.i.d. arrivals. The following transposition transfers that bound to buyer-arrival combinatorial auctions with XOS valuations. The underlying coverage-to-XOS construction also appears in Chawla and Dang [6 Appendix D] ; we spell out why the transfer respects irrevocable disjoint allocation.
Write the source coverage functions using disjoint coverage universes U 1 , … , U k U_1,\ldots,U_k U 1 , … , U k , nonnegative weights w a , u w_{a,u} w a , u , and sets C a , e ⊆ U a C_{a,e}\subseteq U_a C a , e ⊆ U a for each arriving type e e e . Assigning a set of arriving item occurrences S S S to buyer a a a gives coverage value
f a ( S ) = ∑ u ∈ ⋃ e ∈ S C a , e w a , u . f_a(S)=\sum_{u\in\bigcup_{e\in S}C_{a,e}}w_{a,u}. f a ( S ) = u ∈ ⋃ e ∈ S C a , e ∑ w a , u .
The source problem assigns each arriving item to at most one buyer and maximizes ∑ a f a ( S a ) \sum_a f_a(S_a) ∑ a f a ( S a ) . In the transposed instance the items are U = ⨆ a U a U=\bigsqcup_a U_a U = ⨆ a U a , and an arrival of type e e e is a buyer with XOS valuation
v e ( S ) = max a ∈ [ k ] ∑ u ∈ S ∩ C a , e w a , u . (50) v_e(S)=\max_{a\in[k]}\sum_{u\in S\cap C_{a,e}}w_{a,u}. \tag*{(50)} v e ( S ) = a ∈ [ k ] max u ∈ S ∩ C a , e ∑ w a , u . (50)
Any allocation for the XOS instance gives a coverage allocation of at least the same value: at each arrival, assign the source item to a maximizing clause a a a ; disjoint credited subsets cannot count a coverage element twice. Conversely, a coverage algorithm gives the corresponding buyer the still unallocated elements of C a , e C_{a,e} C a , e when it assigns type e e e to a a a . These are exactly the newly covered elements. Both transformations are online, and applying them offline shows equality of the optima. An i.i.d. source sequence induces buyers whose valuations are drawn independently from the same distribution. Permuting these buyers uniformly and independently of their valuations preserves the i.i.d. sequence of arriving valuation types.
Offline approximation results for XOS welfare [9 , 15 ] concern what can be computed from a given representation. The upper bound above is independent of computational limitations: all clauses are public, and the algorithm may use arbitrary computation and independent simulations. The loss arises because an allocation fixes a supporting clause before the remaining actual types are known.
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/blob/main/MatroidProphetSecretary_XOS_Proofs.zip]. The strengthened numerical guarantee in this version is proved by the rational certificate in § 15 .