Universal Online Contention Resolution with Preselected Order

Now we give an overview of our universal OCRSs. All of our universal OCRSs are generalizations of ordered OCRSs for product distributions [7, 15] with necessary randomization. Briefly, an ordered OCRS [15, Definition 3.2] preselects the arrival order of the elements, and then upon the arrival of each element, it greedily adds the element to the solution set, provided that the element is selectable (i.e., if it is active and can be added to the solution set without violating the matroid constraint).

Our first two universal OCRSs (Algorithm 1 and Algorithm 3) generalize ordered OCRSs by subsampling selectable elements. Specifically, these two OCRSs first preselect the arrival order (based on their respective criteria) and sample a subset of elements $T\subseteq [n]$. Then, upon the arrival of each element, they add the element to the solution set if it is selectable and belongs to $T$. Algorithm 1 and Algorithm 3 use different subsampling methods of independent interest – Algorithm 1 includes each element in $T$ independently with a certain probability, while Algorithm 3 employs a correlated subsampling method and achieves a slightly stronger universality guarantee.

Instead of subsampling selectable elements, our third universal OCRS (presented in Section 5) samples the arrival order of the elements. Specifically, given matroid $ℳ$ and prior distribution ${𝒟}_A$, this OCRS first computes a distribution over permutations by solving a linear program (LP), which is similar to the LP used by [7] to compute offline CRSs for product distributions. Then, it samples the arrival order from this distribution, and upon the arrival of each element, it includes the element in the solution set if the element is selectable. The universality guarantee of this OCRS is nearly optimal²²2We note that the $\epsilon$ loss is only due to computation – we will show that $(\alpha ,\alpha )$-universal OCRSs exist..

For comparison, our first two OCRSs have weaker universality guarantees, but they are easier to reason about for specific problem instances. In contrast, our third OCRS provides the strongest universality guarantee, though it is less intuitive because of the use of the LP.

In the course of deriving our third universal OCRS, we discovered an LP-based efficient reduction from universal online contention resolution to the matroid secretary problem for any arrival model (see Section 6 for the setup of the matroid secretary problem), thereby answering the aforementioned question from [8].

Briefly, Dughmi’s information-theoretic reduction [8, Theorem 4.1] was based on the separating hyperplane theorem. Our reduction replaces that with an LP duality argument, and then applies a technique from [19] to solve the corresponding LPs efficiently.

We start by introducing essential definitions and properties of matroids, and we refer interested readers to [22] for a comprehensive treatment of matroid theory. Essentially, a matroid is a set system with some independence structure, which is defined as follows.

Given a matroid, we can associate a (weighted) rank function with it.

Moreover, we can define notions of span and basis for a matroid.

Furthermore, we define the restriction of a matroid to a set of elements.

In the following lemma, we state several well-known properties of matroids.

Now we introduce contention resolution schemes (CRSs) for matroids. Given a matroid $ℳ\subseteq 2^{[n]}$ and a random set of active elements $A\subseteq [n]$ sampled from a prior distribution³³3Throughout the paper, we assume w.l.o.g. that ${𝒟}_A$ satisfies that $\forall i\in [n],{\mathrm{Pr}}_{A\sim {𝒟}_A}[i\in A]>0$. This assumption will simplify the presentation, as it ensures that the probabilities conditioned on the event $i\in A$ are well-defined. ${𝒟}_A\in \mathrm{\Delta }(2^{[n]})$, a CRS selects a subset of active elements $X\subseteq A$ such that $X\in ℳ$. Formally, we first let ${\mathrm{\Phi }}_{ℳ}$ denote the family of maps that take an active set $A\subseteq [n]$ as input and output a subset $X\subseteq A$ such that $X\in ℳ$, i.e.,

Then, a CRS for $(ℳ,{𝒟}_A)$ is a random map sampled from a distribution ${𝒟}_{\varphi }\in \mathrm{\Delta }({\mathrm{\Phi }}_{ℳ})$ (since the choice of ${𝒟}_{\varphi }$ fully determines the CRS, we also use the notation ${𝒟}_{\varphi }$ to refer to the CRS itself). Moreover, for $\alpha \in [0,1]$, we say that a CRS ${𝒟}_{\varphi }$ for $(ℳ,{𝒟}_A)$ is $\alpha$-balanced if it satisfies

and we say that ${𝒟}_A$ is $\alpha$-uncontentious for $ℳ$ if there exists an $\alpha$-balanced CRS for $(ℳ,{𝒟}_A)$.

Furthermore, we use the notation ${𝒟}_A^S$ to denote marginal distributions of ${𝒟}_A$. That is, for any $S\subseteq [n]$, ${𝒟}_A^S$ is defined as follows: $\forall Z\subseteq S,{\mathrm{Pr}}_{A^{\prime }\sim {𝒟}_A^S}[A^{\prime }=Z]:={\mathrm{Pr}}_{A\sim {𝒟}_A}[A\cap S=Z]$. We note that if ${𝒟}_A$ is $\alpha$-uncontentious for matroid $ℳ$, then ${𝒟}_A^S$ is $\alpha$-uncontentious for the restriction ${ℳ}_S$.

A self-contained proof of Lemma 10 is provided in the full paper.

Finally, we define a subsampling operator as follows.

Our universal OCRS is based on the following structural lemma, which says that given a matroid $ℳ$ and an uncontentious distribution ${𝒟}_A$ for $ℳ$, there exists an element $i$, such that if we sample a set of active elements $A$ from ${𝒟}_A$ and then independently remove each element in $A$ with some constant probability, there is a decent chance that the remaining elements do not span element $i$ conditioned on $i$ being active. This type of lemma was also central to the previous ordered/greedy OCRSs [7, 11] for product distributions.

We note that using subsampling is necessary for the above lemma, in the sense that even if $A$ is sampled from an $\alpha$-uncontentious distribution ${𝒟}_A$ for some strictly positive constant $\alpha$, it is still possible that every element $i$ is always spanned by $A\setminus \{i\}$ conditioned on $i\in A$.

Before proving Lemma 13, we state Lemma 15, which is implied by the characterization of uncontentious distributions [8, Theorem 2.1]. We provide the proof in the full paper.

Now we proceed to the proof of Lemma 13.

Our universal OCRS with independent subsampling (Algorithm 1) first samples a set $T={𝒯}_{\frac{\alpha }{2}}([n])$ and applies Lemma 13 iteratively to determine an order of the elements, and then following this order, it greedily selects each element that is selectable and belongs to $T$.

We state the universality guarantee of Algorithm 1 in Theorem 16 and defer the proof to the full paper, where we will also show that the universality guarantee in Theorem 16 is essentially tight for Algorithm 1.

Moreover, we note that Algorithm 1 does not specify how to find element $\pi (i)$ at Line 4. In the full paper, we implement this step by estimating probabilities ${\mathrm{Pr}}_{A^{\prime }\sim {𝒟}_A^{S_i}}[j\in {\text{span}}_{ℳ}({𝒯}_{\frac{\alpha }{2}}(A^{\prime }))\mid j\in A^{\prime }]$ for all $i\in [n]$ and $j\in S_i$ using Monte-Carlo sampling, which results in the following corollary.

Furthermore, as we mentioned in the introduction, Algorithm 1 (in fact, all of our universal OCRSs) generalizes ordered OCRSs for product distributions [7, 15]. For product distributions, it is known that ordered OCRSs can be strengthened to obtain greedy OCRSs, which work even for the worst-case arrival model [11, Theorem 2.1]. One might wonder whether we can also apply our techniques to make those greedy OCRSs universal. Unfortunately, the answer is no, because this would yield a universal OCRS for the worst-case arrival model, which does not exist even for 1-uniform matroids [8, Theorem 5.7]. However, this does not preclude the possibility that there might be meaningful relaxations of greedy OCRSs which can be made universal.

The main idea of our improved universal OCRS is replacing the independent subsampling operator ${𝒯}_{\rho }$ with a correlated subsampling method⁵⁵5The author thanks an anonymous reviewer for suggesting this method and raising valuable questions. that is inspired by Lemma 18. Essentially, Lemma 18 says that given a matroid $ℳ$ and an uncontentious distribution ${𝒟}_A$ for $ℳ$, there exists an element $i$, such that if we sample a set of active elements $A$ from ${𝒟}_A$ and a uniformly random permutation $\sigma$, and then remove all elements in $A$ except those appearing before element $i$ in permutation $\sigma$, there is a decent chance that the remaining elements do not span $i$ conditioned on $i$ being active. We provide the proof of Lemma 18 in the full paper.

We can iteratively apply Lemma 18 to determine an order of elements, which will be the preselected order of our improved universal OCRS. We formally describe this procedure in Subroutine 2 and state its guarantee in Corollary 19. The proof of Corollary 19 is provided in the full paper.

In order to make use of Corollary 19, given a permutation $\pi$ generated by Subroutine 2, we need to sample a set $T\subseteq [n]$ such that for each $i\in [n]$, the subset ${\pi }^{i-1}\cap T$ follows the same distribution as the random set $\text{prefix}(\sigma ,\pi (i))$, where $\sigma \sim 𝒫({\pi }^i)$. In Lemma 20, we show that this can be achieved by first sampling a permutation ${\sigma }^{\prime }\sim 𝒫([n+1])$ and then setting $T$ as $\text{prefix}({\sigma }^{\prime },n+1)$.

We defer the proof of Lemma 20 to the full paper.

We are ready to present our improved universal OCRS with correlated subsampling (Algorithm 3). Algorithm 3 first runs Subroutine 2 to preselect an order $\pi$, and then, it samples a set $T$ according to Lemma 20. Finally, it iterates through all elements following order $\pi$, and for each $i\in [n]$, it selects element $\pi (i)$ if $\pi (i)$ is selectable and belongs to $T$. We state its universality guarantee in Theorem 21, which, as we will show in the full paper, is essentially tight for this algorithm.

We briefly note that unlike Algorithm 1, which is based on independent subsampling, Algorithm 3 employs a correlated subsampling method. Therefore, in Algorithm 3, the event that element $\pi (i)$ is subsampled (i.e., $\pi (i)\in T$) is correlated with the event that element $\pi (i)$ is spanned by the partial solution set $X_{i-1}$ (which is a subset of $T$). Analyzing this correlation will be the main technicality of the proof of Theorem 21, which is provided in the full paper.

Now we formulate an LP that computes an $\alpha$-balanced OCRS for any matroid $ℳ$ and any $\alpha$-uncontentious distribution ${𝒟}_A$ for $ℳ$. The resulting OCRS will be a random mixture of OCRSs ${\varphi }_{\pi }$ for various permutations $\pi \in {𝒮}_n$. Specifically, we let $x_i:={\mathrm{Pr}}_{A\sim {𝒟}_A}[i\in A]$ and $q_{i,\pi }:={\mathrm{Pr}}_{A\sim {𝒟}_A}[i\in {\varphi }_{\pi }(A)]$ for all $i\in [n]$ and $\pi \in {𝒮}_n$, and we consider the following LP (LP) and its dual (DP).

We note that every feasible solution $(\beta ,{\lambda }_{\pi })$ to (LP) corresponds to a $\beta$-balanced OCRS with preselected order for $(ℳ,{𝒟}_A)$. Indeed, because of the last two constraints in (LP), variables ${\lambda }_{\pi }$ for all $\pi \in {𝒮}_n$ together specify a distribution ${𝒟}_{\pi }$ over ${𝒮}_n$. We observe that ${\varphi }_{\pi }$ with $\pi \sim {𝒟}_{\pi }$ is a randomized OCRS with preselected order for $(ℳ,{𝒟}_A)$, and the first constraint in (LP) ensures that this OCRS is $\beta$-balanced.

The next lemma shows that if the prior distribution ${𝒟}_A$ is $\alpha$-uncontentious for matroid $ℳ$, then the optimal value of (DP) is at least $\alpha$. By LP duality, the optimal value of (LP) is also at least $\alpha$, and hence, the optimal solution to (LP) corresponds to an $\alpha$-balanced OCRS with preselected order for $(ℳ,{𝒟}_A)$.

Lemma 24 follows from Lemma 15 and Lemma 23. We provide the proof in the full paper.

We have shown that for any matroid $ℳ$ and any $\alpha$-uncontentious distribution ${𝒟}_A$ for $ℳ$, we can find an $\alpha$-balanced OCRS for $(ℳ,{𝒟}_A)$ by solving (LP) in Eq. (5.1). Solving (LP) directly is not computationally efficient because there are super-exponentially many variables ${\lambda }_{\pi }$. However, we can use the ellipsoid method [13] to solve (DP) in Eq. (5.1).

To apply the ellipsoid method to solve (DP), we need to construct a separation oracle, which given any $\gamma \in ℝ$ and $\mu \in {ℝ}_{\ge 0}^n$ such that ${\sum }_{i\in [n]}{x}_i{\mu }_i=1$, checks whether there is a permutation $\pi \in {𝒮}_n$ such that ${\sum }_{i\in [n]}{q}_{i,\pi }{\mu }_i>\gamma$, and if so, outputs the constraint ${\sum }_{i\in [n]}{q}_{i,\pi }{\mu }_i\le \gamma$. We notice that by Lemma 23, ${𝔼}_{A\sim {𝒟}_A}[{\sum }_{i\in {\varphi }_{\pi }(A)}{\mu }_i]\le {𝔼}_{A\sim {𝒟}_A}[{\sum }_{i\in {\varphi }_{{\pi }_{\mu }}(A)}{\mu }_i]$ for all permutations $\pi \in {𝒮}_n$, which is equivalent to ${\sum }_{i\in [n]}{q}_{i,\pi }{\mu }_i\le {\sum }_{i\in [n]}{q}_{i,{\pi }_{\mu }}{\mu }_i$ for all $\pi \in {𝒮}_n$. Therefore, we can implement the separation oracle efficiently as follows: Given $\gamma \in ℝ$ and $\mu \in {ℝ}_{\ge 0}^n$ such that ${\sum }_{i\in [n]}{x}_i{\mu }_i=1$, the oracle checks whether ${\sum }_{i\in [n]}{q}_{i,{\pi }_{\mu }}{\mu }_i>\gamma$, and if so, outputs the constraint ${\sum }_{i\in [n]}{q}_{i,{\pi }_{\mu }}{\mu }_i\le \gamma$.

Given this separation oracle, we can solve (DP) in Eq. (5.1) efficiently using the ellipsoid method, which identifies a polynomial number of dual constraints that certify the optimal value of (DP). Then, we can solve (LP) efficiently by restricting it to the variables that correspond to the dual constraints identified by the ellipsoid method. The only issue is that the coefficients $x_i$ and $q_{i,\pi }$ in the LP constraints are not necessarily known. However, this can be addressed by estimating the coefficients on demand using Monte-Carlo sampling (i.e., we estimate coefficients $x_i$ for all $i\in [n]$ at the beginning, and we estimate coefficients $q_{i,{\pi }_{\mu }}$ for all $i\in [n]$ only when the ellipsoid method queries the separation oracle with input $\mu \in {ℝ}_{\ge 0}^n$ and certain $\gamma \in ℝ$) and solving the approximate versions of the LPs. We defer the details to the full paper and state the guarantee of the resulting OCRS in Theorem 25.

Now we formulate an LP that given a $c$-competitive matroid secretary algorithm ALG, computes a nearly $(c\cdot \alpha )$-balanced OCRS for any matroid $ℳ$ and any $\alpha$-uncontentious distribution ${𝒟}_A$ for $ℳ$. The resulting OCRS will be a random mixture of OCRSs ${𝒟}_{\varphi }^{(\text{ALG},w)}$ for various weight vectors $w\in {ℝ}_{\ge 0}^n$. Specifically, we let $x_i:={\mathrm{Pr}}_{A\sim {𝒟}_A}[i\in A]$ and $q_{i,w}:={\mathrm{Pr}}_{A\sim {𝒟}_A,\varphi \sim {𝒟}_{\varphi }^{(\text{ALG},w)}}[i\in \varphi (A)]$ for all $i\in [n]$ and $w\in {ℝ}_{\ge 0}^n$, and we define $W_{\epsilon }:=\left\{\frac{\epsilon \cdot i}{n}\right|i\in \{0,\mathrm{\dots },\lceil \frac{n}{\epsilon \cdot p_{\min }}\rceil \}\}$, where $\epsilon >0$ is a parameter which we can choose arbitrarily, and $p_{\min }:={\min }_{i\in [n]}{\mathrm{Pr}}_{A\sim {𝒟}_A}[i\in A]$ (we assume that $p_{\min }>0$ as in the preliminary). We consider the following LP (LP1) and its dual (DP1).

We note that every feasible solution $(\beta ,{\lambda }_w)$ to (LP1) corresponds to a $\beta$-balanced OCRS for $(ℳ,{𝒟}_A)$ in the same arrival model as algorithm ALG. Indeed, because of the last two constraints in (LP1), variables ${\lambda }_w$ for all $w\in W_{\epsilon }^n$ together specify a distribution ${𝒟}_w$ over $W_{\epsilon }^n$. We observe that ${𝒟}_{\varphi }^{(\text{ALG},w)}$ with $w\sim {𝒟}_w$ is an OCRS for $(ℳ,{𝒟}_A)$ in the same arrival model as algorithm ALG, and the first constraint in (LP1) ensures that this OCRS is $\beta$-balanced.

The next lemma shows that if the matroid secretary algorithm ALG is $c$-competitive, and the prior distribution ${𝒟}_A$ is $\alpha$-uncontentious for matroid $ℳ$, then the optimal value of (DP1) is at least $(1-\epsilon )c\cdot \alpha$. By LP duality, the optimal value of (LP1) is also at least $(1-\epsilon )c\cdot \alpha$, and hence, the optimal solution to (LP1) corresponds to an $((1-\epsilon )c\cdot \alpha )$-balanced OCRS for $(ℳ,{𝒟}_A)$ in the same arrival model as algorithm ALG.

Lemma 27 follows from Lemma 26. We provide the proof in the full paper.

We will not directly solve (DP1) in Eq. (6.1) using the ellipsoid method (because here we do not have a straightforward implementation of the separation oracle). Instead, we will use the ellipsoid method to reduce the number of constraints in (DP1) such that its optimal value remains at least $(1-2\epsilon )c\cdot \alpha$ (this technique was also used by [19] to compute optimal OCRSs for product distributions). Specifically, we consider the following polytope $Q_{\epsilon }$:

If $\alpha ,c,\epsilon \in (0,1]$, then by Lemma 27, any vector $\mu \in {ℝ}_{\ge 0}^n$ such that ${\sum }_{i\in [n]}{x}_i{\mu }_i=1$ must satisfy that ${\sum }_{i\in [n]}{q}_{i,{\mu }^{\prime }}{\mu }_i\ge (1-\epsilon )c\cdot \alpha$, where ${\mu }^{\prime }\in W_{\epsilon }^n$ is defined in Eq. (8). Therefore, polytope $Q_{\epsilon }$ is empty, and moreover, we can construct an efficient separation oracle for $Q_{\epsilon }$ as follows: Given any $\mu \in {ℝ}_{\ge 0}^n$ such that ${\sum }_{i\in [n]}{x}_i{\mu }_i=1$, the oracle outputs the violated constraint ${\sum }_{i\in [n]}{q}_{i,{\mu }^{\prime }}{\mu }_i\le (1-2\epsilon )c\cdot \alpha$ for ${\mu }^{\prime }\in W_{\epsilon }^n$ given by Eq. (8). Using this separation oracle, we can apply the ellipsoid method to identify a polynomial-size subset $W^{\prime }\subseteq W_{\epsilon }^n$ such that the following polytope $Q_{\epsilon }^{\prime }$ is empty: