Simple and Optimal Greedy Online Contention Resolution Schemes
Authors: Vasilis Livanos
Venue: NeurIPS 2022 Accept (2022)
Keywords: contention resolution schemes
online algorithms
matroids
prophet inequalities

Abstract: Matching based markets, like ad auctions, ride-sharing, and eBay, are inherently online and combinatorial, and therefore have been extensively studied under the lens of online stochastic combinatorial optimization models. The general framework that has emerged uses Contention Resolution Schemes (CRSs) introduced by Chekuri, Vondrák, and Zenklusen for combinatorial problems, where one first obtains a fractional solution to a (continuous) relaxation of the objective, and then proceeds to round it. When the order of rounding is controlled by an adversary, it is called an Online Contention Resolution Scheme (OCRSs), which has been successfully applied in online settings such as posted-price mechanisms, prophet inequalities and stochastic probing.

The study of greedy OCRSs against an almighty adversary has emerged as one of the most interesting problems since it gives a simple-to-implement scheme against the worst possible scenario. Intuitively, a greedy OCRS has to make all its decisions before the online process starts. We present simple $1/e$ - selectable greedy OCRSs for the single-item setting, partition matroids, and transversal matroids. This improves upon the previous state-of-the-art greedy OCRSs of [FSZ16] that achieves $1/4$ for these constraints. Finally, we show that no better competitive ratio than $1/e$ is possible, making our greedy OCRSs the best possible.


Simple and Optimal Greedy Online Contention Resolution Schemes
Vasilis Livanos
Department of Computer Science University of Illinois Jrbana-Champaige
Urbana, II 61801 1ivanos3@111imoiss
Abstract
Real-world problems such ad allocation and matching have been extensively studied under the lens of combinatorial optimization. In several applications, uncertainty in the input appears naturally and this has led to the study of online stochastic optimization models for such problems. For the offline case, these constrained combinatorial optimization problems have been extensively studied, and Contention Resolution Schemes (CRSs), introduced by Chekuri, Vondrák, and Zenklusen, have emerged in recent years as general framework obtaining solution. The idea behind CRS is first obtain fractional solution to (continuous) relaxation of the objective and then round the fractional solution to integral one. When the order of rounding is controlled by an adversary, Online Contention Resolution Schemes (OCRSs) can used instead, and have been successfully applied in settings such as prophet incqualities and stochastic probing. In this work, focus on greedy OCRSs, which provide guarantees against the strongest possible adversary, an almighty adversary. Intuitively, a greedy OCRS has make all its decisions before the online process starts. We present simple l/e - selectable greedy OCRSs for the single-item setting, partition matroids and transversal matroids, which improve upon the previous state-of-the-arr greedy OCRSs of [FSZ16] for these constraints. We also show that our greedy OCRSs are optimal, even for the simple single-item case.
1 Introduction
In recent years, problems Bayesian and stochastic online optimization have attracted significant interest, especially in the field of machine learning. In this setting, decisions in an online manner, based on the information available to us so far, and our objective is to minimize our "regret", which is captured by a loss function and describes how much better could have done we had all the information available a priori.
usually asked to make
In several applications, in which our decision relies also on hidden information, such as deciding whether user will click an they are presented with [AD 20, XSC BSSX20 [GMS21] or whether a kidney donor is good match for another patient [BTT3] DS15. our online decision problem naturally becomes stochastic. The inherent uncertainty such applications makes the study of stochastic optimization all the more significant, and demonstrating algorithms with reasonable competitive ratios when one has knowledge of the underlying distributions illustrates the importance of learning distributions in AL.
One can consider a simpler setting which our decision at each time step is a binary choice. In one such formulation, elements arrive in an online manner and we have to select subset of them, subject to certain combinatorial constraints. The simplest example of such constraint is when we
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

only want to select a single element. Under this formulation, the elements reveal one after the other in an online manner whether they are "active" or not, and our binary decision is whether to select an active element, with the constraint of being able to select at most one active element. In this paper, we study this problem and its generalizations. Famous examples of such settings are prophet inequality problems [KS77 KW12 [FG and secretary problems [Dyn63]. which have found application in the design of posted-price mechanisms and auctions, among others.
One approach that has seen plenty of success for these problems is to use the known distributional information to obtain a continuous relaxation of the objective. One can then solve this relaxation and get an optimal fractional solution z²,, which corresponds to the marginals of the elements under the optimal distribution. Thus, the optimal value of the relaxation constitutes an upper bound the performance of any online (or even offline) algorithm. Afterwards, x² is used to devise an online algorithm in order to maximize the value of the subset of elements selected. It is easy to see that this algorithm essentially corresponds to an online rounding procedure for x².
In this paper, we contribute provably optimal algorithms for the problem of rounding an optimal solution to a linear program in an online manner, for a range of fundamental constraints. The online nature of our rounding well-motivated in the field of AI due the fact that we are not able to control the arrival order of the agents. Our algorithms apply for the single-item setting, for partition matroids. as well as transversal matroids which have been used extensively to model matching markets [DRS09 CFMP BIK07).
1.1 Online Contention Resolution Schemes
Such rounding algorithms have recently been used to obtain several optimal and interesting results
SVZITFSZID AW18 EFGT20 BZ20 RS17 CL2I. and have more applications in online mech- anism design and posted pricing mechanisms [CMMSI HKS07]. General rounding algorithms for offline problems are called Contention Resolution Schemes (CRSs) and were introduced by Chekuri, Vondrák and Zenklusen [CVZII] with the purpose of maximizing a submodular function. A CRS is defined with respect to a constraint family. Examples of such combinatorial constraints include selecting an independent set in a given matroid, selecting feasible matching in a given a graph in which the elements correspond to edges, or selecting a feasible set of elements subject a knapsack constraint, where each element is associated with a size. Chekuri, Vondrák and Zenklusen (CVZII) gave the first CRSs for all aforementioned constraint families as well as other constraints. For a given fractional point x², the main idea behind CRSs is to first obtain random set R, drawn from the product distribution with marginals x." hence called the active elements. Since R may be infeasible with respect to the constraints, the CRS proceeds to "drop" specific elements from R and obtain a new, feasible, set R' C R.
While the general applicability of the CRS approach is remarkable, they are unfortunately not useful for Bayesian and stochastic online optimization problems. In particular, one can utilize CRSs when they have the ability to choose the order in which they obtain information about the underlying ground set of elements, as CRSs round fractional point xx in a particular order obtain a feasible solution.
To overcome the inherently offline nature of CRSs, Feldman, Svensson and Zenklusen [FSZ16] introduced the notion of Online Contention Resolution Schemes (OCRSs), applicable in variety of online settings in Bayesian and stochastic online optimization, such as prophet inequalities
[S188 RS17 CL21). stochastic probing 166 GNB GNSI6, GNSI7), and posted pricing mechanisms [KS07]. Surprisingly, OCRSs yield constant-facto competitive ratios for several interesting feasibility constraints.
All of the results presented in [FSZ16] are based on a special subclass of OCRSs called greedy OCRSs. Intuitively, greedy OCRS fixes downward-closed subfamily of feasible sets F before the online process starts. During the online process, the greedy OCRS maintains a subset S of the elements which is feasible in F. and then greedily accepts any active element if S U {i} is also feasible in F. L.. if does not violate feasibility, with respect to F, of the set maintained by the greedy OCRS. One can easily see that the final set at the end of the online process is feasible by construction.
Even though greedy OCRSs offer suboptimal performance guarantees with respect to (non-greedy) OCRSs, as we will see, their study remains interesting for two important reasons. First, greedy OCRSs are inherently simpler than their non-greedy counterparts. Usually, to obtain an optimal
2

---

non-greedy OCRS for non-trivial constraint, one has to use linear programming duality, as in the approach of [SS88. This leads to non non-intuitive algorithm which, in many situations, can be difficult to implement I In short, greedy OCRSs are simpler to implement and more intuitive.
Furthermore, greedy OCRSs provide guarantees against an almighty adversary who has knowledge of the future as well as any random coins used by the algorithm. This property is crucial for applications that require the algorithm compare against an almighty adversary. One such example is [B2222 in which the authors study the "delegation gap" of the generalized Pandora's 's box problem and in fact reduce the problem to the design of an OCRS which is necessarily greedy. To the best of our knowledge, this result is the first example of an application in which non non-greedy OCRSs cannot be applied and a greedy OCRS is needed.
1.2 Our contributions
In this paper, we analyze the performance of greedy OCRSs and provide the first provably optimal greedy OCRS for the single-item setting, partition matroids and transversal matroids.
We have four main contributions:
We design a 1/e-selectable greedy OCRS for the single-item setting (Theorem
We show that our greedy OCRS extends naturally to partition matroid (Corollary 1.2
We proceed show that greedy OCRS can be (4/+ -)-slectt,,,,, for any e even for the single item setting. This, combined with our first contribution, shows that our \/e-selectable greedy OCRS is the best possible (Theorem I.3
We extend our greedy OCRS to transversal matroid as well, and show that the selectability can be increased - 1/c for special cases of transversal matroids (Theorem 1.4).
Our results improve upon the 1/4 //-sellcctbble OCRSs of [FSZI6] for all the constraints discussed here.
As corollary, our work presents the first instance of a dichotomy between the best possible guarantees by greedy OCRSs and (non-greedy) OCRSs, since a 1/2 (non-greedy) OCRS is known for the single- item setting [Ala14].
We proceed with our four main results. The proof of the following theorem is found Section 3 Theorem 1.1. There exists a //e-selectable (randomized) greedy OCRS for the single-item setting.
Next, we extend the single-item greedy OCRS to a partition matroid constraint, by decomposing the partition matroid into single-item instances, running the greedy OCRS above and accepting an active element and only if independent in the corresponding single-item instance of the decomposition.
Corollary 1.2. There exists a //esselectbble (randomized) greedy OCRS for partition matroids.
We complement the results above by also showing that it is tight. The proof of the following theorem can be found in Section
Theorem 1.3. For every & > O, there exists no greedy OCRS for the single-item setting that selects an active element with probability at least a/e + for all E N.
Finally, we extend Theorem 1.1 to a more general class of matroids, transversal matroids, and strengthen it for the special case in which every element's neighborhood has size at least 3. The proof of the following theorem is found in Section 5
Theorem 1.4. Let M = (U, I) be a transversal matroid represented by a bipartite gruph G (U U,, Then, there exists 3/e-selectable (randomized) greedy OCRS π for M. Furthermore, if for every element u E U we have [w)) 2 3, where N (u)) is the set of neighbours of u in G, then π is (1 (1)) selectable (randomized) greedy OCRS for M.
1/e)
'For example if the OCRS used for an application which one has to account for the strategic behaviour of the agents.
A partition matroid consists of partition of the elements into disjoint sets A AI,..., such that subset of the elements $ independent if and only |S r A₁| < 1 for every < j S
A transversal matroid consists of a bipartite graph G = (AU B, E)), in which the set of elements is A and a set S C A is independent if and only if there exists matching in G that covers S.
3

---

1.3
Related work
Contention Resolution Schemes (CRSs) have found several applications. Applications of CRSs in Bayesian mechanism design and posted price mechanisms (CHMST0) can be found in CVZIT. Later, Yan [ connected mechanism design with the notion of correlation gap [ADSYI 12). OCRSs were developed [FSZ16] with applications to Bayesian mechanism design as one of the main motivations as they directly translate competitive ratios for the prophet inequality problem [FSZ16] Rub 16 RS17 CL21]. In fact, Alaci's work on uniform matroids [Ala]4 precedes [FSZ16] and can be seen as an OCRS, even though it is formulated differently. Random order CRSs (ROCRSs) were introduced in (AWI8) and yield improved bounds when the arrival order random.
Since their introduction CVZI1
As stated previously, Feldman, Svensson and Zenklusen [FSZ16] gave the first greedy OCRS for matroids, which is 1/4-selectable. Lee and Singla (LSI8] showed reverse connection between OCRSs and prophet inequalitiess obtaining a 1/2-selectable (non-greedy) OCRS for matroids and a (1 - 1/e)-selectable ROCRS for the single item setting. Adamezyk and Wlodarezyk [AW18] obtained several results, including a 1/8=t1-sclectable ROCRS for the intersection of k matroids. For matchings, Ezra et (EFGT20) designed 0.337-selectable OCRS for bipartite graphs, while Bruggmann and
Zenklusen [B20]] developed optimal monotone CRSs via a novel polyhedral approach.
This work is connected to stochastic optimization, online algorithms, mechanism design and sub- modular optimization, all of which have extensive literature. There have been several surveys on the topic [ Lucl7] CFH 19 Din 3 HK92]. well as survey on random-orde order models in general [GS20. Singla's thesis [Sin18] has connections to several of the topics discussed here. On the application side, prophet inequality and secretary problems have received significant atten- tion in the last years, due to their connections with Bayesian mechanism design and posted price
mechanisms [GM66 HK82
Ker86
Dyn63 KS77 KW12, ACK17 CFH 17 CSZ20 AFE 17
EHLMI5 HKS07
EHKS18
FZ18), while ROCRSs have found several applications to stochastic BSZI9
probing ASWI6
GN13
GNST6
GNSL7
ANT6.. Recently, Dughmi (Dug20) Dug21
showed the equivalence between the existence of constant-factor universal OCRSs and constant- factor approximation to the famous matroid secretary problem [BIKKI8]. Apart from OCRSs, the other main technique that has emerged for proving prophet inequalities and guarantees for posted- price mechanisms is the "balanced prices" framework KW12 FGL15 DFKL DKL.20 We refer the reader to a survey by Lucier [uc for more information on this separate technique.
Independently, (FLT+21) study the problem of designing an oblivious OCRS for the same setting and obtain a similar result, showing that there exists a 3/e-selectable oblivious OCRS and no oblivious OCRS can be (t/e + 8) sellecttabe for any E >> O. We note that the two results (and schemes) are very different. In fact, their OCRS is not greedy, while ours is not oblivious. Whether one can achieve similar guarantees with greedy and oblivious OCRSs for more general settings is an interesting open problem.
1.4 Roadmap
We begin in Section with some background. Then, in Section 3, we present our first main result, the 1/e-selectable greedy OCRS for the single-item setting and partition matroids. Then, in Section 4 show that our greedy OCRS is optimal. We proceed with our greedy OCRS for transversal matroids in Section 5 which also achieves the optimal 1/e selectability and show it performs even better under mild assumptions on the structure of the transversal matroid. Finally, we present our experimental results in Section 6 demonstrating how our schemes outperform the best previously known schemes for randomly generated as well as specific worst-case instances. All omitted proofs can be found in the Appendix which, along the code used for the experiments, is provided in the supplementary material.
4 'An CRS (or OCRS) is called oblivious if and only if it does not make use of the fractional point x, i.c. if for every S C .N the distribution of n.. (S) and the distribution of J.. (S) are identical for any two fractional points 2.y. E Ps.

---

2
Preliminaries
Before we proceed, we present the formal definitions of CRSs, OCRSs and greedy OCRSs and briefly describe 1 1/4-selectable single item OCRS by [FSZ16).
N be a finite ground set, A constraint family over N a subset I C 2N; a set S E I called feasible, while set S & I is called infeasible. We say Pz S [0, 1j is polyhedral relaxation of (N, I) if Pz a polyhedron and s E Pr for all S E I (here 1 is the characteristic vector of S).
Given a polyhedral relaxation Pz of constraint (W,Z) I) and point a E Pz, natural question whether we can round x in order to obtain a feasible set S I. One way to achieve this is via Contention Resolution Schemes, which we define below.
Definition 2.1 (Contention Resolution Scheme [CVZII]. Let b E [0.1]. A (b,c)-balanced Contention Resolution Scheme x for Pı is a procedure that for every E b- Pz and C N, returns random set Tx (A) C A support(z)) (r) and satisfies the following properties:
1. n. (A) E Z with probability 1, VAC x E Pr, and
2. for all i support(z), Pr E (R(x)) R(x)) 2 Ve b Pr.
where R(x) S C denotes a random set in which every element i E N appears independently with probability 24.
The scheme is said to be monotone Pr [i E nu (At) 2 Pr E (A2)) whenever i E A1 S A2-
For the remainder of this paper, we drop the subscript in Pr and simply write P whenever the constraint is clear from context.
CRSs offline rounding schemes. In the case where the arrival order of the elements is selected by an adversary, we can use the following notion of Online Contention Resolution Schemes (OCRS) to round x.
Definition 2.2 (Online Contention Resolution Scheme (OCRS) FSZ16)). ). For an online selection setting where a point æ E P is given, we draw a random subset of the elements R(z), in which each element i appears independently with probability zę. We call R(xr the set of active elements. Afterwards, we observe whether the element E N are active (e R(x)), one by one, and have to immediately and irrevocably decide whether to select an element or not before the next element is revealed. An Online Contention Resolution Scheme for P is an online algorithm which selects a subset C R(x) such that 11 E P.
A scheme is called Random Order Contention Resolution Schemes (ROCRS) if, instead of being chosen by an adversary, the arrival order of the elements is chosen uniformly at random. Adamczyk and Wlodarezyk present several interesting results on ROCRSs in [AW88]. In the case of adversarial arrival order, however, one can distinguish between three different adversaries in terms of the information they have at their disposal. An offline adversary, which is the weakest of the three, has to fix an ordering of the elements before any of the elements are revealed. An almighty adversary, the most powerful one, has access to the realizations of all random events; both the set of active elements and any potential random bits the algorithm may use. Therefore, an almighty adversary can predict the algorithm's 's behaviour and choose a truly worst-case ordering of the elements for the particular algorithm. In between the two extremes is the online adversary. An online adversary's 's choices can only depend on the realizations of the elements that have appeared so far. In other words, the adversary has, at any step, exactly the same information the algorithm, and their decision to which element to reveal at step can only depend on the realizations of the elements revealed in steps 1 through i 1.
We also define the notion of a greedy OCRS, which provide guarantees with respect to an almighty adversary.
Definition 2.3 (Greedy OCRS FSZI6)). Let P S [0, 1]" be relaxation of the feasible sets F C 2N' An OCRS ग for P is called a greedy OCRS if, for any x E P. π defines down-closed subfamily of feasible sets Fr.. F, and it selects an active element when it arrives if, together with the set of elements already selected, the resulting set is in Fz.z. We say that N is randomized greedy OCRS if, given the choice of Fa. is randomized. Otherwise, we say that π is deterministic greedy OCRS.
5

---

For the remainder of this paper, we drop the subscript in Fr.. and simply write Fg or F, whenever and z are clear from context.
Intuitively, we say a greedy OCRS c-selectable if and only an active element E R(x) can be included in the currently selected elements I C R(x)) and maintain feasibility with probability at least c.
Definition 2.4 (c-selectability), Let E [0, 1]. A greedy OCRS for P is e-selectable and only if for any P we have
Pr[ (e) E EF I(t.
Ve VeEW.
Notice that a c-selectable greedy OCRS guarantees that each active element selected with probability at least c, even against the almighty adversary. We should note that the randomness in the above definition is with respect to both the randomness of R(x) and also any potential randomness the greedy OCRS might
decide upon Fu.
Next, we briefty describe the 1/4-selectable single item greedy OCRS by FSZ16). Given a fractional point such that Σ < 1, the greedy OCRS will, at step observe whether element is active or not. If it is active, the greedy OCRS will choose to select with probability 1/2 or discard it and move on to the next element. Since each element is active with probability x; and is selected with probability =1/2, the expected number of selected elements is at most half, and thus, by Markov's inequality, the probability the greedy OCRS selects elements is at least 1/2. Therefore, for every element i, we reach without having selected an element with probability at least 1/2 and we select i, given that it is active, with probability 1/2, for overall selectability of 1/4.
We should note that for the single item setting there exists a 1/2-selectable OCRS Ala14 but, crucially, it is not greedy. In fact, we show in the Section 4 that there is no 1/2-selectable greedy OCRS for the single item setting.
An \/-seleccabll greedy OCRS for the single-item setting
This section is dedicated to proving Theorem 1.1 Before begin, we need the following lemma. Lemma 3.1. Let , ak E [0, 1]. Then
k-1
a3 2
In 1 ak
Σ j=1
in
0j +
2 Ok
aj
Next, consider a ground set N' = {e,, "ee,,,........ en), and let M = (W I) be the uniform matroid of rank with respect to N, i.e. [[ei) e E N.. Let P be the following polyhedral relaxation of M:
p x 0. 11th
Σ
For a given x E P, let π = Tu denote the OCRS we will create. will draw random set R(q) where each element 6 appears R(q) independently with some probability qa- The family of feasible subsets is
Fr.. = [(+) le E R(g)).
We set di =1 #1/2 f for all e; e N. Afterwards, æ selects the first element e; that is active and that {er) E F.
Lemma 3.2. π is a randomized greedy OCRS.
Next, we quantify the probability that each element selected by æ, given that is active. Lemma 3.3. selects every element e, N, given that it is active, with probability at least 1/c.
Proof. We relabel the elements of N so that each e; arrives in the i-th step. Consider element e, N. Given that e; is active, since æ a greedy OCRS, x will select e, if and only if it has not selected any elements before e; and also {ei} E Fx.x. Recall that we have {e:} E F with

---

probability exactly 9; = 1 - 2/2.. Furthermore, for every element e, where j < i, it needs to be the case that we avoid having both {e,} E FT... and also e, coming up active. This happens with I + #3/2 for every ej where the probability that e, is selected by given that it is active, we have
probability 1-x, =j- (1 - -=/22)
Overall, we denote by ra
Inr; in (1-
i-1
1 xy + - 1)) In (1
i-1
+j 1 2j +
Z4
+ (1
Iz
In
2
2
j=1
j=1
i-1
2 22
1,
j=1
where the first inequality follows from Lemma 3.1 and the second inequality follows from Σ, 24 1. Therefore r; 2 l/e, for all i N.
From Lemmas 3.2 and 3.3 it follows that is a //e-selectbble (randomized) greedy OCRS for P.
Remark 3.4. In personal communication, Jan Vondrák devised an alternate scheme for the problem, after we notified him of our scheme. With his consent [Von], we have included this alternate scheme in the Appendix, which can be found in the supplementary material.
4
1/c is tight
In this section, we present the proof of Theorem 1.3 Consider the instance where x; = 1/n for all e, N., where n [W) and let A denote the set of active elements. Any greedy OCRS will select a subset S of F = {e, | e; E W/ with some probability as, and then accept the first element in S that comes up active. What is the worst-case probability that element from S will be selected? This is minimized for the element
which is last in the arrival order, which has a probability of being selected exactly equal to (1 1111/2 1/x))51- because the OCRS is greedy, and it would select an element from S which arrived earlier, it came up active. Therefore, no greedy OCRS can guarantee, for any S C F, that an element E W will be selected, when E A, with probability greater than
(1 1/m)( Thus, for any E N and any greedy OCRS n, we have
|S|-1
1 n2
Prfe (())
Σ as 1
SCN eES
k-1
Σ
ag.
(1)
n
SCN cES
Next, for greedy OCRS æ to be c-selectable, it needs to guarantee that mineeN Pr/e E (A) e A] 2 Therefore, if we show that
min
S C,
eEV
k=
SCN: =k eES
by (I) it follows that π cannot be (c + =)- selectaale for any & > Lemma 4.1.
1 n
n-1
min NEA
0S
1
SCN: e6g
By Lemma 4.1 since lim (1 - 1/1m))"- = 1/e, follows that there exists no greedy OCRS for
P that selects an element e, when active, with probability at least 1/e for all e E N.
7

---

Extension to Transversal Matroids
In this section, we prove Theorem 1.4 Let MM (U, be a transversal matroid and G (U,VEE) denote the underlying bipartite graph, where [0] n. We know that subset S S U is independent and only if there exists a matching in G that covers Let be the natural polyhedral relaxation be the greedy OCRS we will create. For each E V, will
of M. For a given E P. let π draw a random set R. S (w),, which each element u U appears with probability Qu- For every E U, let (u) denote the set of neighbors of in G. Then, we set
1 1
TWOW
au 1
Ia
It is easy to see that Qu [0, 1] for every [AV 2 L, and thus qu well-defined.
Next, we create a down-closed subfamily feasible sets by taking all possible combinations sets created by taking most one element from each Rh and then taking the union of all such elements. Specifically,
FrZZ = (u. 3 C C (u......, 3. S V s.t. U E Re,, Vj E [I....,k}}
Any set S in F is clearly independent set of M, the constraints guarantee that there always exists a matching in G that covers S. During the online process, æ starts with set of selected elements S 0, and greedily selects an active element S + E F.
The proof of the following lemma identical to the proof of Lemma 3.2 and follows from the discussion above.
Lemma 5.1. π is randomized greedy OCRS.
Next, we again lower bound the selection probability of an active element.
Lemma 5.2. π selects every element u E U, given that it is active, with probability at least afe. Furthermore, if N (u) | 2 3 for all u E U, π selects every element u E U, given that it is active, with a/e.
probability least
We conclude that ı is a s/eseelee greedy OCRS for M and that if [N(u]] 2 3 for every U, a a (1 s/eessele greedy OCRS for... M.
Experimental Results
In this section, present experimental results which give quantitative view into how greedy OCRSs outperform the former state-of-the-art greedy OCRSs by (FSZ16]. For the constraint system, we consider both the single-item setting well constraints. The code used to run these experiments can be found in the supplementary material.
transversal matroid
For our experiments, we have the following parameters:
N: The number of elements. For the single item setting, this varies from 10 to 100. For the transversal matroid constraint, this is set to 50.
ITERATIONS: For a fixed the number of times we simulate the realization of the elements. This used approximate the selectability each element within reasonable estimate and is set to 200, 0000.
REPETITIONS: The number of times we run the entire experiment from scratch. This has no effect on the uniform instance of the single-item setting or the transversal matroid constraint, but affects the random vector x in the randomly-generace instance of the single-item setting, and set to 10.
We focus on two metrics: the minimum selectability and the average selectability of each element. For fixed v, the minimum (resp. average) selectability records the minimum (resp. average) over all elements of the fraction of the times an element was selected by our greedy OCRS over the number of times it was active. While the average gives an idea of what selectability to expect for most elements, the minimum selectability provides worst-case estimate.

---

For both types of constraints, we can see that our greedy OCRSs ouiperform the 1/t-selectable single-item greedy OCRS by [FZZ66] the minimum selectability metric and performs substantially better in the average selectability metric.
6.1 Single-Item Setting
We consider two different types of instances for the single-item setting: the uniform instance, where I; 1/n for every element i & N, as well as a rundomly-generated generated instance, in which æ is a random vector of length with the constraint that Σ 24
Ninimum Selectab lity Unitom instance
Minimum Selectability Random Instance
34
0.0
02-
51
(F5215)
Cur Alponitm
01
Our Aigonthen
(152361
Average Selectabiity Uniform Instance
Average Selectability Random Instance
0.
38
0.6
Agorntmm [15c16]
(Hacte)
0.4
53
03
Figure 1: 100, ITERATIONS 200, 000, REPETITIONS 10
6.2
Transversal Matroid
For the transversal matroid constraint, consider three different types of instances: transversal matroid with |V| = 2, [N(x))
and Tu = 2/n. for all vertices u E U, a transversal matroid with V 3, [N) 3 and T. 3/n for all vertices u E U, as well transversal matroid with [V = 4, [w)) = and Fy = 4/n. for all vertices u E U.
While there many options for the choice of what transversal matroid to pick, selected these "uniform" instances of transversal matroids to illustrate how the selectability changes as [N()) increases. Since transversal matroid with [V] 1, [Nx)] equivalent to a uniform instance of the single-item setting, we do not consider it explicitly, but we
and I., 1/n for all vertices u E U
plot it together with the previous three instances. The x-axis in the figures below corresponds to the size of [.))
Minimum Selectability
Transversal Matroid
0.6
Algorithm [PSZ16)
0.4
0.0
Average Selectability Transversal Matroid
0.8
Algorithm
[F5216]
0.0
Figure 2: N 50, ITERATIONS 200, 000

---

Acknowledgments and Disclosure of Funding
The author would like to thank Chandra Chekuri, Ruta Mehta and Jan Vondrák for guidance and helpful discussions.
Work on this paper partially supported by NSF grant CCF-1910149.
References
[AAD*20] 20] Saba Ahmadi, Faez Ahmed, John P. Dickerson, Mark Fuge, and Samir Khuller. An algorithm for multi-attribute diverse matching. In Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pages 3-9. International Joint Conferences on Artificial Intelligence Organization, 2020. Main track.
[ACK17] Yossi Azar, Ashish Chiplunkar, and Haim Kaplan. Prophet secretary: Surpassing the 1-1/e barrier. CoRR, abs/1711.01855 2017.
[ADSY12] Shipra Agrawal, Yichuan Ding. Amin Saberi, and Yinyu Ye. Price of correlations in stochastic optimization. Operations Research, 60(1):150-162, 2012. Preliminary version in Proc. of ACM-SIAM SODA 2010.
[ABE 17] Melika Abolhassani, Soheil Ehsani, Hossein Esfandiari, MohammadTaghe Hajiaghayi, Robert Kleinberg, and Brendan Lucier. Beating 1-1/è for ordered prophets. CoRR, abs/1704.05836, 2017.
[Ala14] Saeed Alaci. Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM Journal on Computing, 43(2):930-972, 2014.
[AN16] Arash Asadpour and Hamid Nazerzadeh. Maximizing stochastic monotone submodular functions. Management Science, 62(6):2374-2391, 2016.
[ASW16] Marek Adamczyk, Maxim Sviridenko, and Justin Ward. Submodular stochastic probing on matroids. Mathematics of Operations Research, 41(3):1022-100 1038, 2016.
[AW18] Marek Adamezyk and Michal Wlodarczyk. Random order contention resolution schemes. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018 pages 790-801, 2018.
[BDP22] Curtis Bechtel, Shaddin Dughmi, and Neel Patel. Delegated pandora's box. In David M. Pennock, Ilya Segal, and Sven Seuken, editors, EC '22: The 23nd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11 15, 2022, pages 666-693. ACM, 2022.
[BFT13] Dimitris Bertsimas, Vivek F. Farias, and Nikolaos Trichakis. Fairness, efficiency, and flexibility in organ allocation for kidney transplantation. Operations Research, 61(1):73- 87, 2013.
[BGMS21] Brian Brubach, Nathaniel Grammel, Will Ma, and Aravind Srinivasan. Improved guarantees for offline stochastic matching via ordered contention resolution schemes. In A. Beygelzimer, Y. Dauphin, Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[BIK07] Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. Matroids, secretary problems, and online mechanisms. In Proceedings of the Eighteenth ACM-SlACMMSIAA Symposium Discrete Algorithms, SODA '07, page 434 443, USA, 2007. Society for Industrial and Applied Mathematics.
[BIKKI8] Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. Matroid secretary problems. J. ACM, 65(6), nov 2018.
[BSSX20] Brian Brubach, Karthik A. Sankararaman, Aravind Srinivasan, and Pan Xu. Attenuate locally, win globally: Attenuation-based frameworks for online stochastic matching with timeouts. Algorithmica, 82(1):64-87, Jan 2020.
10

---

[BSZ19] Domagoj Bradac, Sahil Singla, and Goran Zuzic. (Near) Optimal Adaptivity Gaps for Stochastic Multi-Valuu Probing. In Dimitris Achlioptas and László A. Végh, edi- tors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019), volume 145 of Leibniz International Proceed- ings in Informatics (LJPIcs), pages 49:1-49:21, Dagstuhl, Germany, 2019. Schloss Ressuul-Leibnniz-Zentru fuer Informatik.
[BZ20] Simon Bruggmann and Rico Zenklusen. An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint. Mathematical Programming, Oct 2020.
[CFH*17] 17] José Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld. Posted price mechanisms for random stream of customers. Proceedings of the 2017 ACM Conference on Economics and Computation, EC 17, pages 169-186, New York, NY, USA, 2017. ACM.
[CFH* 19] José Correa, Patricio Foncea, Ruben Hocksma, Tim Oosterwijk, and Tjark Vredeveld. Recent developments in prophet inequalities. ACM SIGecom Exchanges, 17(1):61-70, 2019.
[CFMP] Florin Constantin, Jon Feldman, S. Muthhkrishhan, and Martin Pál. An Online Mecha- nism for Ad Slot Reservations with Cancellations, pages 2265-1274.
[CHMS10] Shuchi Chawla, Jason D) Hartline, David I. Malec, and Balasubramanian Sivan. Multi- parameter mechanism design and sequential posted pricing. In Proceedings of the forty-second ACM symposium Theory of computing, pages 3 311-320, 2010.
[CL21] Chandra Chekuri and Vasilis Livanos. On submodular prophet inequalities and correla- tion gap. In Ioannis Caragiannis and Kristoffer Arnsfelt Hansen, editors, Algorithmic Game Theory- 14th International Symposium, SAGT 2021, Aarhus, Denmark, September 21-24, 2021, Proceedings. volume 12885 of Lecture Notes in Computer Science, page 410. Springer, 2021.
[CSZ20] Jose Correa, Raimundo Saona, and Bruno Ziliotto. Prophet secretary through blind strategies. Mathematical Programming, 08 2020.
[CVZ11] Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC '11, pages 783-792, New York, NY, USA, 2011. ACM.
[DFKL20] Paul Dütting, Michal Feldman, Thomas Kesselheim, and Brendan Lucier. Prophet inequalities made easy: Stochastic optimization by pricing nonstochastic inputs. SIAM Journal on Computing. (9(3):540-582 2020.
[Din13] Michael Dinitz. Recent advances on the matroid secretary problem. ACM SIGACT News, 44(2):126611) 142, 2013.
[DKL20] Paul Dütting, Thomas Kesselheim, and Brendan Lucier. An o(log log m) prophet inequality for subadditive combinatorial auctions. ACM SIGecom Exchanges, 18(2):32- 37, 2020.
[DRS09] Shaddin Dughmi, Tim Roughgarden, and Mukund Sundararajan. Revenue submodularity. In Proceedings of the 10th ACM Conference on Electronic Commerce, EC '09 page 243-252, New York, NY, USA, 2009. Association for Computing Machinery.
[DS15) John Dickerson and Tuomas Sandholm. Futurematch: Combining human value judg- ments and machine learning to match in dynamic environments. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). Feb. 2015.
[Dug20] Shaddin Dughmi. The outer limits of contention resolution on matroids and connections to the secretary problem. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference). volume 168 of LIPIcs, pages 42:1-42:18 42:18. Schloss Dagstuhl- Lcibniz-Zentrum für Informatik, 2020.
11

---

[Dug21] Shaddin Dughmi. Matroid secretary is equivalent to contention resolution. CoRR, 005/2103.04205, 2021.
[Dyn63] E. B. Dynkin. The optimum choice of the instant for stopping a Markov process. Sovier Math. Dokl, 4, 1963.
[FGTT00] Tomer Ezra, Michal Feldman, Nick Gravin, and Zhihao Gavin Tang. Online stochastic max-weight matching: Prophet inequality for vertex and edge arrival models. In Pro- ceedings of the s ACM Conference on Economics and Computation, EC '20, page 769-787, New York, NY, USA, 2020. Association for Computing Machinery.
[EHKS18] Soheil Ehsani, MohammadTaghh Hajiaghayi, Thomas Kesselheim, and Sahil Singla. Prophet secretary for combinatorial auctions and matroids. In Proceedings of the Twenty- Ninth Annual ACM- Symposium on Discrete Algorithms, SODA '18, page 700-714, USA, 2018. Society for Industrial and Applied Mathematics.
[EHLM15] Hossein Esfandiari, MohammadTaghh Hajiaghayi, Vahid Liaghat, and Morteza Monem- izadeh. Prophet secretary. CoRR, abs/ tass/150..01 0000000100 155, 2015.
[FGL15] Michal Feldman, Nick Gravin, and Brendan Lucier. Combinatorial auctions via posted prices. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 135. SIAM, 2015.
[FL Hu Fu, Pinyan Lu, Zhihao Gavin Tang, Abner Turkieltaub, Hongxun Wu, Jinzhao Wu, and Qianfan Zhang. Oblivious online contention resolution schemes, 2021.
[FSZ16] Moran Feldman, Ola Svensson, and Rico Zenklusen. Online contention resolution schemes. In Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium Discrete Algorithms, SODA '16, pages 1033, Philadelphia, PA, USA, 2016. Society for Industrial and Applied Mathematics.
[Z188] Moran Feldman and Rico Zenklusen. The submodular secretary problem goes linear. SIAM Journal on Computing, 47(2):330-366, 2018
[GM66] John P. Gilbert and Frederick Mosteller. Recognizing the maximum of sequence. Journal of the American Statistical Association, 61(313)335-33, 1966.
[GNI3] Anupam Gupta and Viswanath Nagarajan. A stochastic probing problem with ap- plications. In Michel Goemans and José Correa, editors, Integer Programming and Combinatorial Optimization, pages 205-216, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
[GNS16] Anupam Gupta, Viswanath Nagarajan, and Sahil Singla. Algorithms and adaptivity gaps for stochastic probing. In Robert Krauthgamer, editor, Proceedings of the awenty-Seventh Annual ACM-SIAM Symposium Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1731-1747. SIAM, 2016.
[GNS17] Anupam Gupta, Viswanath Nagarajan, and Sahil Singla. Adaptivity gaps for stochastic probing: Submodular and XOS functions. In Philip N. Klein, editor, Proceedings of the Tienty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1688-188 1702. SIAM, 2017.
[GS20] Anupam Gupta and Sahil Singla. Random-orde models, 2020. htttps//aaxiii org/
abs/ Abs/2000 2002. 12159
[Gup17] Anupam Gupta. Prophets and secretaries, June 2017.
[HK82] T. P. Hill and Robert P. Kertz. Comparisons of stop rule and supremum expectations of i.i.d. random variables. Ann. Probab., 10(2):336-345, 05 1982.
[HK92] Theodore Hill and Robert P Kertz. A survey prophet inequalities in optimal stopping theory. Contemp. Math, 125:191-207, 1992.
12

---

[HKS07] Mohammad Taghi Hajiaghayi, Robert Kleinberg, and Tuomas Sandholm. Automated online mechanism design and prophet inequalities. In Proceedings of the 22Nd National Conference on Artificial Intelligence- Volume I, AAAI077, pages 58 65. AAAI Press, 2007.
[Ker86] Robert Kertz. Stop rule and supremum expectations of i.idd random variables: A complete comparison by conjugate duality. Journal of Multivariate Analysis, 19(1):88 1 112, 1986.
[KS77] Ulrich Krengel and Louis Sucheston. Semiamarts and finite values. Bull. Amer. Math. Soc., 83(4):745-747, 07 1977.
[KW12] Robert Kleinberg and Seth Matthew Weinberg, Matroid prophet inequalities. In Pro- ceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 123 136, 2012.
[L.118] Euiwoong Lee and Sahil Singla. Optimal online contention resolution schemes via ex-ante prophet inequalities. In Hannah Bast, Grzegorz Herman, and Yossi Azar, editors, 26th European Symposium on Algorithms, ESA 2018, Leibniz International Proceedings in Informatics, LIPIcs, Germany, August 2018. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.
[Luc17] Brendan Lucier. An economic view of prophet inequalities. SIGecom Exch., 16(1):24 September 2017.
[RS17] Aviad Rubinstein and Sahil Singla. Combinatorial prophet incqualities. Proceedings of the Eventy-Eighthe Annual ACM-SIAM Symposium on Discrete Algorithms, pages 167 1- 1687. SIAM, 2017, Longer ArXiv version is at attttp://axxiii org/ frrg/abs/166111 00665
[Rub16] Aviad Rubinstein. Beyond Matroids: Secretary Problem and Prophet Inequality with General Constraints, page 222-332, Association for Computing Machinery, New York, NY, USA, 2016.
[Sin18] Sahil Singla. Combinatorial Optimization Under Uncertainty: Probing and Stopping- Time Algorithms. PhD thesis, CMU, 2018. http://reports-archh archive. adm edu/ anon Maton/2018/CHU-OOO CS 18- 111. 111.pdf pdf
[Von] Jan Vondrák. personal communication.
[XSC 19] Pan Xu, Yexuan Shi, Hao Cheng, John Dickerson, Karthik Abinav Sankararaman, Aravind Srinivasan, Yongxin Tong, and Leonidas Tsepenekas. A unified approach to online matching with conflict-aware constraints. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01):2221-222) Jul. 2019.
[Yanl1] Qiqi Yan. Mechanism design via correlation gap. In Dana Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium Discrete Algorithms, SODA 201 San Francisco, California, USA, January 23-25, 2011, pages 710-719. SIAM, 2011.
13


Reviews:
[{"review_id": "nKY9iOkjsL2", "reviewer": "Reviewer_KzEE", "summary": "The paper studies the problem of designing greedy online content resolution schemes (OCRSs). The author provide an OCRS that provides a $\\frac{1}{e}$-selectable greedy strategy for single-item settings and partition matroids. Then, they provide a similar result for transversal matroids. In this case, they also provide a better result for specific settings.\nMoreover, they show that these results are tight for greedy OCRC. Finally, they provides a experimental analysis with a comparison with previous works.\n\n", "questions": "Why is it an important property for OCRSs being greedy? Is it simply because they work against an almighty adversary?", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "strengths: The paper provides better results than previous work. Moreover, the authors show that this bound is tight. The paper is easy to follow and provides a detailed analysis of previous works.\n\nWeakness: The derivation of the technical results do not seem too involved.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "eXXJEhGAd3r", "reviewer": "Reviewer_LXMv", "summary": "The paper presents some results regarding online contention resolution schemes. The main result, to my taste, is the result for selecting a single item. One can rephrase this result as follows. We are given a point x in the simplex (\\sum x_i \\le 1) and then draw a random set of “elements” by taking each one with probability x_i independently. The elements will then be presented to us in arbitrary order and we have to select one upon seeing it. The question is: What is the best number c such that the probability of selecting any element is at least cx_i? The paper proves that the best such c is 1/e. Nice! The way to do it is as follows. You draw this random set, then clean it up by dropping each element on it with probability 1-x_i/2, and finally take the first element that was not dropped. This can be implemented as a greedy OCRS and therefore it improves upon the factor 1/4 of FSZ16. Also, it is not too hard to show this is best possible. One should note that this clean-up step is needed as otherwise we may have a “large” probability element that may come first and then would block the remaining “small” probability elements from ever appearing. Say x_1=1-eps and x_2=eps, if we do not clean-up we will only get element 2 w.p. eps^2.\n\nThe paper also extends this idea to some classes of transversal matroids. ", "questions": "No further questions", "limitations": "none", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main result is nice and simple. I appreciate that. The authors also show it can be useful in related more complex settings though that part did not feel like very exciting to me. \n\nI do not like the write-up very much. It is written for specialists and not for a wide audience. Even the problem definition is not clearly stated and there are missing definitions (e.g. that of R(x)). \n\nI think the authors should try to rephrase their main result in simple terms (in particular without using the OCRS terminology) in the first few pages of the paper. This is relatively easy. And then, once they really need matroids and more general CRS they can give more notation and technicalities.  \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "Qsrm0SzetvR", "reviewer": "Reviewer_CZba", "summary": "An Online Contention Resolution Scheme (OCRS) is a rounding technique designed for online optimization problems especially in Bayesian optimization (example prophet inequalities). The paper focuses on Greedy online contention resolution schemes and provides an optimal greedy OCRS for the single-item setting as well as for more general constraint sets such as partition matroids and transversal matroids. The paper also demonstrates a matching lower bound.", "questions": "1. In Definition 2.1, property 2,  what is R(x)? Did you mean A there?\n2. In Definition 2.1, could you clarify the order of quantifiers? Are properties 1 and 2 simultaneously satisfied for all sets A and all points x?\n3. In Definition 2.1, property 2, should the RHS be c*x_i?\n4. In Definition 2.2, clarify that the random subset R(x) is drawn so that the marginal probability of i \\in R(x) = x_i.\n5. In line 246, typo - 1 - x_j(1-x_j / 2)\n6. In line 261, “no greedy OCRS cannot” -> “no greedy OCRS can”\n", "limitations": "None", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper provides an elegant greedy OCRS for the single-item setting. The scheme itself is very simple and simply selects in F each element i with probability q_i := 1 - x_i/2. The algorithm then selects the first item (in adversarial order) that is active and selected in F. \nSince the work of Feldman etal (that introduced OCRS) also introduced the notion of greedy OCRSs back in 2015, it is rather satisfying to see such a simple scheme that is provably optimal (among greedy schemes).\n\nI believe that while interesting, the paper is of limited interest to the Neurips community and would be better suited at a TCS venue.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "K4GTHPnuEWM", "reviewer": "Reviewer_Wsp9", "summary": "The paper considers greedy online contention resolution schemes. A contention resolution scheme (CRS) is, roughly, a method to round a fractional solution for a (packing) problem to a random integral one. More precisely, given a vector $x\\in[0,1]^n$ that is feasible for a fractional relaxation of a problem, let $y\\in\\{0,1\\}^n$ be an integral vector obtained by selecting each $y_i$ to be $1$ independently with probability $x_i$. But $y$ may be infeasible for the problem, so now the task of the CRS is to switch some of the $y_i$ from 1 to 0 in order to obtain a feasible solution (in other words, the CRS selects an integral $z\\le y$ that is feasible). A CRS is *online* (abbrev. OCRS) if the $y_i$ are revealed one by one, and the OCRS has to pick $z_i$ immediately after $y_i$ is revealed. OCRSs have applications to various online problems such as prophet inequalities, stochastic probing etc. An OCRS is said to be $c$-selectable if, roughly, $P(z_i=1)\\ge c\\cdot x_i$ for each $i$ (the precise definition given in the paper is somewhat more complicated, which I believe has to do with the type of ``almighty adversary’’ considered, which can choose the order in which the entries of $y_i$ are revealed with full knowledge of all random number generators). Intuitively, a $c$-selectable OCRS corresponds to losing a factor $c$ in the rounding procedure.\n\nThe paper considers a subtype of OCRSs that are called *greedy*, which means that it first chooses (randomly) a downwards-closed family of coordinates, corresponding to a subset of feasible solutions, and then greedily tries to set each $z_i$ to 1 if possible while maintaining a solution corresponding to this downwards-closed family.\n\nResults:\n- They give a 1/e-selectable greedy OCRS for the single-item setting (i.e, the feasibility constraint is $\\sum_i x_i\\le 1$). This improves over the previous 1/4-selectable greedy OCRS, but is worse than the known 1/2-selectability achieved by a non-greedy OCRS. It also implies immediately the same result for partition matroids.\n- They show that 1/e is tight for greedy OCRSs for the single-item setting.\n- They extend their result to so-called transversal matroids.\n\nIn an experimental evaluation, their 1/e-selectable greedy OCRS indeed improves upon the previous 1/4-selectable greedy OCRS.", "questions": "A discussion about benefits of greedy over non-greedy OCRSs would be useful. Are they significantly simpler? Does the 1/2-selectability of the known non-greedy OCRS also hold against almighty adversaries?\n\nSpecific (minor) comments:\n- Line 172: Is $\\mathcal P_{\\mathcal I}$ the same thing that you denoted as $\\mathcal P$ before?\n- Line 175: What is $R(x)$? I later found kind of a definition of $R$ in the introduction, but it would have been good to define it in preliminaries.\n- Line 211, 237 and elsewhere: You omit some of the subscripts of $\\mathcal F$. It would have been good to state explicitly that you may drop them from the notation.\n- Line 234: Here you seemingly use $R$ with a different meaning than before.\n- Line 246: One of the $x_i$ should be $x_j$.\n- Line 274: Presumably $R_v$ only contains neighbors of $v$? Otherwise, how would you conclude that each $S\\in\\mathcal F$ is covered by a matching?\n- Line 302 you say that number of iterations is set to 200,000, but in the caption of Figure 1 it states 10,000 instead of 200,000.\n- Figure 2: What is the number on the x-axis? I thought it’s the size of $N(u)$, but it goes up to 4 whereas in the description of the setup you say it goes only up to 3.", "limitations": "This is a theoretical work and negative societal impact is not expected. Limitations are clear from the mathematical formulations.", "rating": 4, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main result — improving from 1/4 to 1/e and showing tightness — is the final answer for single-item greedy OCRSs. This is a nice and clean result. I’m not entirely sure about the significance though, given that a (better) 1/2-selectable non-greedy OCRS is known. Why would one choose this greedy OCRS when the known non-greedy one performs better? The experimental evaluation only contains comparison with the previous (suboptimal) greedy one, but not with the better non-greedy one.\n\nThe writing is mostly good, but some things were unclear to me for some time because of insufficient definitions (see below; but I could eventually guess the likely intended meaning).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept