Improved Guarantees for Offline Stochastic Matching via new Ordered Contention Resolution Schemes
Authors: Brian Brubach
Nathaniel Grammel
Will Ma
Aravind Srinivasan
Venue: NeurIPS 2021 Poster (2021)
Keywords: Stochastic Optimization
Combinatorial Optimization
Discrete Optimization
Approximation Algorithms
Matching
Stochastic Matching
Prophet Inequality
Prophet Secretary
Contention Resolution

Abstract: Matching is one of the most fundamental and broadly applicable problems across many domains. In these diverse real-world applications, there is often a degree of uncertainty in the input which has led to the study of stochastic matching models. Here, each edge in the graph has a known, independent probability of existing derived from some prediction. Algorithms must probe edges to determine existence and match them irrevocably if they exist. Further, each vertex may have a patience constraint denoting how many of its neighboring edges can be probed. We present new ordered contention resolution schemes yielding improved approximation guarantees for some of the foundational problems studied in this area. For stochastic matching with patience constraints in general graphs, we provide a $0.382$-approximate algorithm, significantly improving over the previous best $0.31$-approximation of Baveja et al. (2018). When the vertices do not have patience constraints, we describe a $0.432$-approximate random order probing algorithm with several corollaries such as an improved guarantee for the Prophet Secretary problem under Edge Arrivals. Finally, for the special case of bipartite graphs with unit patience constraints on one of the partitions, we show a $0.632$-approximate algorithm that improves on the recent $1/3$-guarantee of Hikima et al. (2021).

Improved Guarantees for Offline Stochastic Matching via New Ordered Contention Resolution Schemes
Brian Brubach
Nathaniel Grammel
Computer Science Department Wellesley College Wellesley, MA 02481 bb100@wellesley.com edu
Department of Computer Science
University of Maryland
College Park, MD 20742
ngrammel 1@udd edu
Will Ma
Aravind Srinivasan
Graduate School of Business Columbia University
Department of Computer Science
University of Maryland College Park, MD 20742
New York, NY 10027
wm24288gab. columbia. edu
asriniv @umd edu
Abstract
Matching is one of the most fundamental and broadly applicable problems across many domains. In these diverse real-world applications, there is often degree uncertainty in the input which has led to the study of stochastic matching models. Here, each edge in the graph has known, independent probability of existing derived from some prediction. Algorithms must prohe edges to determine existence and match them irrevocably if they exist. Further, each vertex may have a patience constraint denoting how many of its neighboring edges can be probed. We present new ordered contention resolution schemes yielding improved approximation guarantees for some of the foundational problems studied in this area. For stochastic matching with patience constraints in general graphs, we provide a 0.382-approxingg algorithm, significantly improving over the previous best .pp1-approximaation Baveja al. (2018). When the vertices not have patience constraints, we describe a 432-approxi random order probing algorithm with several corollaries such as an improved guarantee for the Prophet Secretary problem under Edge Arrivals. Finally, for the special case of bipartite graphs with unit patience constraints on one of the partitions, we show 0.632-apee algorithm that improves on the recent 1 1/3-guarane guarantee of Hikima et al. (2021).
Introduction
The offline stochastic matching problem is about finding maximum matching on a weighted graph. However, each edge e is active independently according to a known probability pe, and only active edges can be matched. The set of active edges is initially unknown. An edge whose endpoints are unmatched can be probed to determine whether it is active, and if so, it is irrevocably inserted into the matching. The objective is sequentially probe the edges in a way to maximize the expected weighted matching at the end.
Matching problems arise in numerous deployed Al systems, especially those dealing with allocation and scheduling. See, for example, the works of Ahmadi et al.] (2020); Ahmed et al. (2017): Brubach al. (2020) (022bb; [Baeeja al. (2018) for applications advertising, e-commerce, organ exchange. online dating, peer review, school matching, and hiring; and Hikima et al.] (2021); Nanda et al. (2020): Xu (019) for applications ride sharing, crowdsourcing (worker-task assignment), and
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

recommendation systems. The work Esfandiari et al. (2016); Antoniadis et al. (2020) gives further discussion on applications to e-commerce and internet advertising, and illustrates the importance of designing algorithms with good theoretical guarantees in deployed AI systems.
Stochastic edges play a major role in properly capturing many of these applications when we account for hidden information about whether a proposed match will be accepted. Is a kidney donor a good match? Will a worker accept an offered task? Does a user want to click on this ad? The uncertainty inherent in the presence or absence of various edges naturally leads to the need for stochastic optimization. Achieving good results when the edge probabilities are known demonstrates the value of learning distributions in AL.
We contribute improved algorithms for range of fundamental problems, well useful-speciate case problems, in the realm of stochastic matching. Although our results are phrased for the offline setting, some of our algorithms also translate the random-order online setting in which the edges arrive in random order. This online arrival model is well-motivated in these Al settings due to the inability to control the order in which the agents arrive.
Below, we further describe three typical features that may be present in stochastic matching problems.
Patience constraints. The offline stochastic matching problem is typically considered with the input including an integral patience parameter t. for each vertex v known as patience constraint or timeout. This adds the constraint that at most t, of the edges incident to v can be probed, which is motivated by applications which the vertices represent users who are only willing to view a finite number of potential matches. A vertex which has been probed l. times is said to have timed out. To capture the absence of patience constraints some models, we allow patience parameters to be co.
Probing orders allowed. Most generally, we allow algorithms to probe the edges in any order based on the realizations of past probes. Sometimes we impose that the algorithm must make a single pass through the edges, according to a uniform random permutation. This can also represent an "online" setting in which the edges arrive in a uniformly random order, and upon arrival, an edge must either be probed (only possible if both endpoints are unmatched and have remaining patience) or irrevocably discarded. We say that such algorithms are random-order
Special case of graphs considered. We introduce a new class of graphs, bipartite graphs with a unit-patience side, for which we derive further improved guarantees. Such graph can be divided into two sides such that: (1) all edges are between vertices on different sides; and (2) for one of the sides, all patiences are 1, This subclass of graphs captures problem of interest in AI with applications such as crowdsourcing and ride-hailing, described in Hikima et al. (2021).
1.1 Summary of Results
To derive computationallly-fficiii probing algorithms, address the standard approach of first solving a fractional relaxation, which prescribes a probability ye E [0, 1] with which each edge e should be probed. These relaxed values Ye only have satisfy the matching and patience constraints in expectation, while a probing algorithm must satisfy these constraints with probability (w.p.) 1. However, we can still hope to probe every edge e with probability at least e ye. for some S 1. It is well-known that such an algorithm would then be c-approximate, i.e. its expected weight matched would be at least times that of optimal probing algorithm.
Result 1. A 0.382-approximate random-order probing algorithm for general graphs.
This makes a significant improvement to the line work on patience-constrained offline stochastic matching for general graphs, which includes the 0.25-approximate algorithm of Bansal et al. (2012) 0.269- approximate algorithm of Addmncyk et al. (2015). and 0.31-approximate algorithm of Baveja et al. (2018). We emphasize that although our algorithm considers the edges in random order, no better guarantee is known even without imposing this property. Our general guarantee can be parametrized by the patiences in the graph and improves in certain special cases.
Corollary 1. A (1 e 2 ~ ap2-aapprox random-order probing algorithm for general graphs without patience constraints.
In the special case where every patience is oo, the guarantee of our random-order probing algorithm improves to 0.432. We note that without patience constraints, the Greedy algorithm which probes edges in decreasing order of weights (ignoring the probabilities p.) guarantees at least 1/2 the offline

---

maximum weighted matching knowing the set of active edges in advance. However, our algorithm has the benefit of providing a guarantee relative to the relaxed values ye, and moreover only needs to consider the edges in a uniformly random order (instead of needing to choose the order). This means that the special case of our algorithm where patiences are oo implies new results for Random-onder Contention Resolution Schemes and Prophet Secretary under Edge Arrivals, as we discuss below.
Corollary 2. A (1 - e 3)2 12//-selectabll Kandom-order Contention Resolution Scheme for the match- ing polytope of general graphs.
For S L, the definition of o-selectable Contention Resolution Scheme can be reduced to our goal of probing every edge e with probability at least c Ve. as we explain in Section [2] Previous work in this area has derived (1 e 2 ///esellectbble "offline" Contention Resolution Scheme, which needs to know the set of active edges in advance, for the matching polytope of general graphs (Guruganesh and Lee 2017). The selectability has been recently improved be strictly greater than (1 1)/2 while also satisfying a monotonicity property (Bruggmann and Zenkluser 2020). However, both of these results require knowing the of active edges in advance, while our algorithm observes the activeness of edges in an ordered fashion and must immediately decide whether to insert any active edges into the matching. In fact, our algorithm satisfies the definition of Random-order Contention Resolution Scheme introduced in the papers by Adamczyk and Włodarczyk (2018); 8); Lee and Singla (0018). To this end, our specific setting of the matching polytope is not captured" by these papers.
Corollary 3. A 0.432-guaranter for the Prophet Secretary problem under Edge Arrivals, in general graphs.
Contention Resolution Schemes for the matching polytope also imply Prophet Inequalities under the Edge Arrival model introduced in Gravin and Wang (2019). The best-known result here is a 0.337-selectable adversarial-ores
Contention Resolution Scheme for the matching polytope of general graphs due to Ezra et al. (2020), which implies a 0.337 under Edge Arrivals in any order. When the edges arrive in uniformly random order, this can be called the Prophet Secretary problem (Esfandiari et al. 2017) under Edge Arrivals, for which our Random-order Contention Resolution Scheme implies an improved 0.432-gum 442--gurree
for Prophet Inequalities
Corollary 4. A new class of non-adaptive (1 - 1/e)- Random-order Contention Resolution Schemes for rank-l matroids.
In the further special case of a star graph with infinite patiences, the selectability of our probing algorithm improves to 1/e. The constraint that at most one edge in star graph be matched corresponds to a rank-1 matroid, for which a (1 - 1/e)-selectable Random-order Contention Resolu- tion Scheme is already known (e.g. Lee and Singla 2018 However, our analysis yields a wide range of new such schemes, which are simpler than existing ones in that they satisfy a non-adaptiveness property, which we we elaborate on in Subsection 1.2
Result 2. A (1 - 1/e) se 0.632-approximate probing algorithm for bipartite graphs with a unit- patience side.
This result improves and generalizes the guaaanttee of Hikima et al. 2021) which holds for a special case of bipartite graphs with a unit-patience side. Despite the ubiquity of (1 -uuaranus
in online matching, to the best of our understanding, our guarantee requires the novel technical ingredient of a (1 1eeesccle Ordered Contention Resolution Scheme for rank-1 matroids under negative correlation. The aforementioned (1 //))-selectabilityy results for rank-1 matroids assume elements to be active independently and do not establish this guarantee,
discuss in Subsection 1.2 We note that our probing algorithm here must be able to choose the order, though. We note that concurrent and independent work of Borodin et al. (2021) study online problem which implics the same (1 - appoxxiiponnnnation for the offline problem in the particular case where one side has unit patience and the other side has unlimited patience.
1.2 Description of Techniques
Random-order probing: finding an attenuation function which improves the worst case, As described before, our probing algorithm for general graphs considers the edges in a uniformly random
II' the graph is bipartite, then its matching polytope can be captured by the intersection of two matroids; however, in this case the selectability guaranteed by /Adamcyyk and Wlodarezyk (0018) is 1/3, which is worse than our selectability of 0.432.
3

---

order. This can be implemented by each edge drawing an "arrival time" ze independently and uniformly from [O.1]. Baveja et all (2018) have previously analyzed a similar algorithm, which probes each incoming edge according to the fractionally-feasite
probability ye as long as is safe. They show that every edge e ends up being probed with probability at least 0.31 yes yielding a 0.31 0.31-approximate algorithm. The worst case occurs for an edge e' whose values of Ve' are close to O, with both endpoints of e' being incident to other edges e" whose values of ye" Pe" are 1.
To improve this worst case, we attach an "attenuation factor" a(e) E [0, 1] to each edge e such that the probability of an incoming safe edge e being probed is scaled down by factor of a(e). We make a(e) decreasing in Ve and Pe, to dissuade the aforementioned edges e" with large values of ye", from being probed and blocking edge e'. However, given an arbitrary function a defining the attenuation factors, computing the new worst case could be difficult. Therefore, our approach is instead to derive properties on a which cause the worst case to only involve edges e with a(e) 1. More specifically, we show that for functions a defined by a(e) @(UcPe) for some univariate function ā with a(0) = 1, it is possible to design the derivatives of so that the worst case, edge e' is only incident to edges e" with Ve"Pe" R 0 (which implies that a(e") x ā(0) 1). Our final bound is then derived from the same expression as in Baveja et al. 2018 except the worst case ratio has improved to 0,382. The specific attenuation function we compute is inconsequential to this improved ratio-the key is showing the existence of an attenuation function which eliminates the previous worst case. However, by deriving such necessary properties, we are able to see not only which attenuation functions work, but also which don't 't work (suggesting alternative attenuation functions can't t do better than ours). Further, having a family of valid attenuation functions allows for a choice of different attenuation functions for different application domains while keeping the same approximation guarantee.
Using our attenuation for Random-order Contention Resolution Schemes. As stated in Corol- laries 2] and 3 our attenuation analysis in the special case of infinite patiences implies a previously-
unknown (1 --)) 2)/2-sclectable Random-order Contention Resolution Scheme for the matching polytope of general graphs. We now discuss the further special case in Corollary of star graphs, for which we can contrast our technique with that used in the known Random-order Contention Resolu- tion Schemes for rank-1 matroids. Here, Lee and Singla (2018) show that (1- - seleectbbbyyy can be achieved using what we would call the attenuation function a(e) exp(=ZePee which depends on the arrival time ze of cach edge e. This function is designed (see Ehsani et al., 2018) to yield closed-form form expression for the probability of availability at any particular time allows them to elegantly compute that the selectability is 1 1/e..
[0, 1]. which
In this special case, our analysis also yields (1 1/e)-selectable Random-order Contention Resolution Scheme. However, instead of designing specific function, our analysis implies a class of functions which sufficiently atttenue large values of pe to prevent them from blocking smaller values of Pe- To elaborate, we show that either of the functions a(e) = exp(- -axp.) or a(e) = ope, with [1/2, 1]. ensures that in the worst case, all edges have P. = 0. And in this worst case, a(e) ze 1 for all e, from which we can conclude that any edge has an Rs 1 - 1/e chance of being selected. We note that our functions do not depend on the arrival time x. and can be seen non-adaptive (1- /eeeeetceee Random-order Contention Resolution Schemes for a rank-1 matroid, which we believe could be applied elsewhere
attenuate
Bipartite graphs with a mnit-patience side. For offline stochastic matching on bipartite graphs, a standard technique (Bansal et al. (012)) is to randomly round the fractionally-feasibl values ye to binary values Y, using the dependent rounding procedure of Gandhi et al. (2006), which ensures the patience constraints on both sides to be satisfied w.p. 1. Under our additional assumption that one of the sides V11 has umit-patience, the vertices in V12 must have rounded degree at most 1, resulting in the rounded graph being a disjoint collection of stars. One could then separately handle the edges in each star using a Random-order Contention Resolution Scheme for rank-l matroids, since its edges e will be disjoint from other stars and active independently w.p. Pe-
"This intuition can be illustrated as follows. If there is no attenuation, then the worst case involves two edges e', with probabilities par = O. Pe. = 1. which when shown in a random order implies that e" will block e' w.p. 1/2, whereas e' will not block e". The goal of "attenuation" is to scale down the probability of selecting e". to increase the probability of selecting e'.
4

---

However, this does not lead to (1 1/ee-selectabiiity To elaborate, for any vertex & V1, let 8(v) denote the of edges incident to u. Fractional feasibility the ye values ensures
Σ (Ed(v)
PeVe 11,
(1)
but the rounded star graph formed by edges {e E 8(v) Y. 1} could have Eeeb(o) PeYe 1 whenever some particular edge e' has Y = 1, making difficult to ensure that edge e' gets selected with sufficient probability when Yor is rounded up.
Reinterpretation as contention resolution under negative correlation. To resolve this issue, we instead imagine each edge d(v) as being active with probability Fe == Pelle, which satisfies Eee((v) Re S 1, due to ① The active edges in ((v) are correlated in a way such that they cannot conflict with active edges in other stars; however, due to this correlation, any of the affrrmentioned Random-order Contention Resolution Schemes which agnostic to the correlation will only be 1 1/2-selectable, as we will show in Section 4
Despite this apparent lack of a correlation-agnostic (1 seeessele Contention Resolution Scheme, what we do show is that the optimal online algorithm, which trivially sorts the edges E 8(v) in decreasing order of weights w., obtains in expectation least 1 - 1/ee times the fractional value E.e((w) Ze This is only possible due to the following negative correlation property enjoyed by the rounding procedure of Gandhi et al. (006)). with Ze E {0, 1} denoting the activeness of an edge
Pr
N (2. 6) LEES
< II EES
PriZe = 6]
vS S 8(0), 10,
(2)
Our analysis applies this negative correlation property with = 0 to show that the expected overall weight obtained by the online algorithm is minimized when the Ze are independent. despite the fact that for a particular edge e', negative correlation among other edges in 8(v) could make it more likely that e' is blocked than in the independent case. Through the equivalence derived in Lee and Singla 2018), our analysis also implies the existence of a (1 1/e)-selectable Ordered Contention Resolution Scheme for rank-1 matroids under negative correlation, assuming the order be chosen. We leave as an open question whether a - 1/e)- Random-order Contention Resolution Scheme possible under property (2).
1.3
Roadmap
We begin Section with some background. Then, in Section 3 we present random-order algorithm for general graphs. achieving a.382-aprroximation for stochastic matching. We then analyze the same algorithm in the case of infinite patience, where the algorithm yields a (1 11-6 e 2)2
approximation (and thus a (1 1-- 2 //2e-sclectable Random-order Contention Resolution Scheme for the matching polytope); and the case of a star graph, where the algorithm achieves an approximation guarantee of 1 1/e (and thus gives (1 seeessele Random-order Contention Resolution scheme for rank-1 1 matroids). Finally, in Section[4 we present an algorithm for stochastic matching on bipartite graphs with unit patience side, which achieves approximation guarantee of 1/e. All omitted proofs can be found in the full version of this paper (Brubach et al. 2021a).
2 Notation and Preliminaries
The weighted stochastic graph is denoted by G = E), with the weight and probability of being active being denoted by w. and pe, respectively, for each edge E E. The patience parameter is
As concrete example, let e have patience f., = 2, and be incident to three edges with = 1, y1 = P2 - 3, 1; and Ps 0, ys = - E, which are fractionally feasible in that Eeg((v) PeBe and Σ ErEA(N) < 2. The rounding must be such that whenever Y1 = 1, we also have Yz = 1, which results in Eegg(e) Ye = -
'A 1/2-selectable Random-ordes order Contention Resolution Scheme for star graphs under negative correlation implied by the "uniform black box" in Brubach et al. 2020 This black box has also been extended in some cases by Fata al. 2019).
5

---

denoted by bu for each vertex v E V. Given any problem instance defined by these values, finding the optimal probing algorithm is computationally challenging (Bansal al. 2012). For c S 1, a probing algorithm is said to be c-approximate if its expected weight matched is at least times that of the optimal probing algorithm, for any problem instance. The following IPP relaxation commonly used to derive computationally efficient probing algorithms.
LP == max
Σ EE
subject to
Σ Ze
AE V
(3a)
rEa(v)
Σ Ve S h
VVEV
(3b)
REd(w)
0 S ye S
YeE E Ve E E
(3c)
2e YePe
(3d)
Note that we have let 8(v) denote the set of edges incident to a vertex v. The variable ye E [0. 1] corresponds to the probability of probing edge e. The variable 2, is then the probability that edge is included in the matching (that is, is both active and probed). Constraint (3a) for vertex E V is the matching constraint: it is satisfied when is matched to at most one of its neighbors in expectation. Constraint (3b) for a vertex v E V is the patience constraint: it satisfied when at most t, edges incident to are probed in expectation.
Lemma Bansal et al. (012)). For any problem instance, the optimal objective value LP is an upper bound on the expected weight matched by any optimal probing algorithm.
Due to Lemma for an algorithm to be c-approximate, suffices to show that its expected weight matched is at least c LP. All of our algorithms will be based on taking an optimal LP solution given by (ye)aEE, and randomizing in a way to probe every edge e with probability at least c ye. which suffices for matching expected weight at least c LP. We note that the gap between the LP and the optimal probing algorithm can be large: |rubach et al. (202Tb) showed that for some graphs, the ratio between the maximum-weige matching and the LP objective value can be as large as 0.544.
Definition (Ordered Contention Resolution Scheme Problem). A graph G = (V, E) and a vector (Ee)cEF lying in its matching polytope (i.e. satisfying Exes(v) Ee S 1 for all v) is given. Each edge E has an "activeness" in {0, 1} whose state initially unknown other than that it equals I w.p. ž.. The activeness of edges is observed sequentially, and if an edge is both active and eligible to be matched (i.e. not incident to any edges already matched), then can be either immediately matched or irrevocably discarded. A (randomized) algorithm that guarantees every edge E E of being matched with ex ante probability least e oØ said be a c-selectable Ordered Contention Resolution Scheme for the matching polytope.
A probing algorithm which guarantees every edge e probability least c Ve of being probed implies a e-selectable Ordered Contention Resolution Scheme. To see this, given an instance to the problem in Definition [ we can construct an instance of offline stochastic matching with p.- = ã. for all and 4, = oo for all v. which means that setting ye = 1 for all e is a feasible solution to LP (3. The probing algorithm will indicate whether to probe each edge in way that guarantees the overall probability of any edge e being probed to be at least c ye c. Therefore, if in Definition D we "accept an edge when active" whenever the probing algorithm would have probed that edge, this translates to an ex ante guarantee of c = c 2. on the probability of any edge e being matched, as desired.
Definition 2 (Random-order), A probing algorithm is said to be random-ordes order if it can be applied in the online setting where the edges arrive in a uniformly random order, and upon arrival, each edge needs to be either immediately probed (if safe) or irrevocably discarded. Analogously, Random- order Contention Resolution Scheme must observe the activeness of edges in a uniformly random order.

---

3 Algorithm and Analysis for Result
3.1 Description of Algorithm and Attenuation Functions
Our algorithm is based on the algorithm of [aveeaa et al. (018)). ) but with an added attenuation factor. This algorithm first solves LP (3 get fractional solution (Ye)aEg. Then, the algorithm independently rounds the LP solution by setting, for each edge Y, = 1 with probability Ve and Y, = 0 with probability Ye- Then, the algorithm generates a uniformly random permutation on F; the algorithm then proceeds to probe each edge E E, in the order of the permutation, if Y. and both endpoints are still safe (i.e., the endpoints are both umatched with remaining patience).
Our algorithm adds an additional attenuation as follows. Let a: E + [0, 1] be our attenuation function; then, when we get to edge {u, v), we generate new Berouulli random variable A. such that [[A.] = a(e). Then, we probe e if
1. e is safe
2. Y, 1, and
3. A. =
Pseudocode is given in Algorithm Recall that we can generate the permutation by first generating.
for each E E, a uniformly random "arrival time" Te E [0, 1]. and ordering the edges in increasing order of arrival time. Slightly abusively, we use (e) == Te refer to the arrival time of an edge
Algorithm I: Attenuation-based algorithm for Stochastic Matching
Function AttemuateeMatchh(+ E. p):
Generate random permutation æ E for each edge in the order of π do
Generate random bit Y. 1 with probability ye Generate random bit Ag = with probability a(e)
e "safe" AYe = 1 A then
Probe
Our analysis allows for 0.p22-aprroi be achieved for many choices of attenuation function. Specifically, our analysis will require a few key properties of our attenuation function, outlined in Definition
Definition 3. We call an attenuation function a(e) effective if all of the following conditions hold:
1. a(e) can be expressed function ā(2,) of ze
2. ā(0) = 1
3. In(1 xzā(2)) is convex function of [0, 1] for any (0,
There many functions which satisfy the conditions of Definition 3 Notice, for instance, that the first two conditions are straightforward: we require only that the attenuation function be a function of z, and result in attenuation when ze 0. The final condition satisfied by many nice classes of functions, with some examples given in Definition 4
Definition 4. Define the following attenuation functions:
The exponential attenuation function, defined by ēexp (2)
for any 2 1/2
The linear attenuation function, defined by شهn (2) := 1 az for any a 2 1/2
can be easily verified, by taking second derivatives, that these two functions indeed satisfy the third
property of Definition 3 and hence effective.
7

---

3.2 Analysis of the Attenuation Algorithm
The expected weight of the matching produced by our algorithm is E[ALG] = EEED WePe Pr(Y, Pr(A, 1] Pr(e gets probed Y: = n A, 1] ΣEEE WePeyaa(e)) Pr(e gets probed Ye 1nA,- 1]. We wish to lower bound Pr(e gets probed YYe In., 1J. We will then establish
that for an effective attenuation function, a(e) Prfe gets probed | Y = 1n A₂ 1] 2 0.382. This then implies our 1.382-selectabilit result for the matching polytope, and establishes the 0.382- approximation for stochastic matching on general graphs.
{u, f and consider the endpoint (the endpoint can be treated symmetrically L.tt a E [0, 1J; we will condition on π (e)) = x. Let E(u) == d(u) {e} be the set of u's neighbors excluding e. If probing an edge f E E(u) results in either a successful match or u timing out, then we say that edge/ f blocks e. We denote by B,, the event that e is not blocked by any edge f E E(u).
Fix an edge
We wish to analyze the local structure (around edge e) that produces the worst bound on Pr[B.]] We now present sequence of lemmas that lead the identification of the worst case e for any effective attenuation function.
Lemma 2. For effective attenuation functions, all edges f E E(u) in the worst case have Py {0, 1}.
As brief intuition for Lemma 2 we note that any edge with p, E (0, 1) can be replaced with two edges fo and fi with probabilities of being active of ( and respectively. We can assign Ur and Vn in such way that all LP constraints are still satisfied, and can show that the probability of an edge blocking is only increased by doing so.
Equipped with Lemma 2, let (u) If E(u) py 0} and Ei(u) {f E E(u) |ps = 1}. Using the fact that all edges have integer probabilities (either O or 1), we can lower bound the probability of u not being blocked by the following quantity:
S. = Pr[Te S tu -]
1]
II (1- (1-xyya(f)) fEE
(4)
where Tú E)) Ty, and T is Bernoulli random variable with Pr[TT 1] zyya(f). It
easy to see that Pr BB.) 2 Su, because: (1) Pr(T,, S fu 1] represents the probability of u not timing out before considering edge e; (2) the product represents the probability of a not being matched.
The third property of effective attenuation functions (the convexity of In(1 xzā(²))) allows us to analyze the worst case behavior of edges in Ei (u) and further simplify our bound. This stated as Lemma 3
Lemma 3. If a(f) is an effective attenuation function, then
S, 2 Pr[Tu S tu 1le 1]e-=(1-zx) =(1-2.)
We can then state and prove our final results by further analyzing the worst-case behavior of edges in Eo(u).
Theorem (corresponds to Result from Subsection I.1]. For any graph and any feasible solution
(NE)EE to the LP (3. Algorithm (ssing an effective attenuation function considers the edges in random order and probes every edge e = {u, v} E E with probability at least
a(ze)
2x(1- gt. (2) (x)
ye
(6)
where (z) == Pr[T t - 1] for T ~ Pois((((t - 1)). For the effective attenuation functions of Definition 4 the value in parentheses in (6) is minimized when 2, 0. This is then further lower
bounded by Ro 0.382 when L,, = to = 2, so the algorithm is a 0.382-approximation.
Corollary 5 (corresponds Corollaries D to 3 from Subsection 1.1.. In the case where all patiences
are oo, since 9 (x) = 1 for all x E (0, IJ. for any feasible solution (ye Jee to LP (3): Algorithm] I using one of the attenuation functions from Definition 4 considers the edges in random order and
probes every edge e = {u, f} with probability at least
dx
(1-e-2)
which R 0.432y In this case, the algorithm is 1..3--approiiiattoon and a seletalele Random-order Contention Resolution Scheme for the matching polytope
8

---

Proposition 1 (corresponds to Corollary from Section 1.. For any star graph with infinite patiences and any feasible solution (ye)egE to the LP (3). Algorithm | in Definition 4 considers the edges in random order and probes every edge = {u, 4) E E with probability least
using one of the attenuation functions
( dx
(fedd)) V/
ye
This yields a (1 - (1/e)---eleeeeel selecttle Random-order Contention Resolution Scheme for rank-1 matroids which does not adapt to the time of arrival of each element.
4 Algorithm and Analysis for Result 2
Let G = EV be a bipartite graph with bipartition = V1 U V2. Assume tu = 1 for all E V1. Description of algorithm. We first solve the standard LP (3 to obtain an optimal solution (Ye)eEr satisfying Eeedte) MePe I and EeEδ(e) Ye S t for all E V. Then, we run the rounding procedure Gandhi et al. (2006) on Yr to get an integral solution Y, E {0, 1}. This guarantees that for each vertex Vi that Eees(u) Y. S 1. Thus, most one vertex E ō(u) will be rounded to
Y. 1 for every u E V1. Thus, in the rounded graph G (V, E), where É == {e E E Y. 1}. each vertex E 122 is the center of a star graph. For each vertex v E V2, we probe the edges e E 6(v) in decreasing order of weight, for each with Y. 1.
Analysis of algorithm. The expected value achieved by this strategy is
B[ALG| = E
Σ W(u) LUEV
Σ [[)())] VEV
where Ww)) denotes the weight of the edge matched by the algorithm (if any) for a vertex v. In our analysis, we consider each vertex u E V/2 separately, since in the rounded graph, it is the center of star graph that disconnected from any other vertices of V2. We first utilize the negative correlation property of our dependent rounding technique (Gandhi et al. 2006) to establish the following lemma.
Lemma 4. Consider a fixed vertex E V2. Label the edges of 8(v) from to k == |6(x) such that
w1 2 W2 2 2..2 Wk. Then:
EW(
Σ W II
(
(1-
For V2, let (P Eecs(r) me Using Lemma from which our main result immediately follows.
:
4 then able derive the following,
Lemma 5, For any vertex E V2, we have
[[W()) 2 11 (1- OPT(e)
Theorem (corresponds to Result 2 from Subsection patience side, let (ye) denote an optimal solution to the LP 3b. Then our algorithm above matches expected weight least (1 1/e) Evev, Exeg(r) WePeyes yielding a (1 ( approxxxiiiiiii..n....
For any bipartite graph with a unit-
We note that the problem of stochastic matching on bipartite graphs with a unit patience side is a special case of particular interest, it captures "Problem A" in Hikima al. (022)) As shown in Lemma A Hikima et al. (202T), an a-approximation for Problem A implics an a-approximation for the Integrated Stochastic Problem for Control Variables and Bipartite Matching (ISPCB), This is discussed further at the end of this section.
Why we cannot use an existing Contention Resolution Scheme. Lemmas 4 and 5 show that the total expected weight collected from edges 5(v) is at least (1 - 1/e) OP Tv)).. We now explain why it is not possible use correlation-agnostr Contention Resolution Scheme to match every edge e E ((v) with probability at least (1 1 1/e). We consider the following example, in which every edge has the same value of
Peye- Therefore, a correlation-agnosti Contention Resolution

---

Scheme would treat the edges symmetrically, doing no better than a strategy which considers the edges in a random order until an edge e matched (which requires both Y, be rounded to I and for edge to exist). However, due to the first-stage dependent rounding for Ye, the probabilities of edges being matched end up being negatively correlated (as defined in (2) in the introduction). This negative correlation among the neighbors of particular edge "0" can increase the probability of edge 0 being blocked to 1/2 (something not possible under independence), as we now demonstrate.
Example 1. Consider a star graph with + edges, whose central vertex has patience 2. Take the fractionally-fessible solution yo = 1, Po 1/(T + +)), and y1
yr 1/T,, P1 ... Pr T/(T + 1). Any rounding procedure which satisfies the patience w.p. and preserves the marginal probabilities will set Yo = YY; = Yr O for all other i', with i drawn uniformly from {I,..., T). This implies that w.p. 11 + 1), one of the edges I,... T will match upon being uncountered. Any correlation-agnostic procedure would treat all edges symmetrically, since they all have the same value of 2; = P:tk = 1/(T + 1). Consequently, edge will have a (1 1/(T + 1))/2 probability of being blocked, whenever it is considered later than the aforementioned edge which matches upon being encountered. Therefore, the correlation-aee -agnostic procedure cannot be better than 1/2-sclectable
as T oc.
4.1 Improvement Approximation Ratio of Hikima et al. (2021)
The work Hikima et al. (202T) introduces and studies a problem they call Integrated Stochastic Problem for Control variables and Bipartite Matching (ISPCB). This problem is two-stage bipartite matching problem where the algorithm is given a bipartite graph G = (V1 U V2, E)) and must set a control variable zu for each u Ví. Then, each vertex V1 leaves the graph with probability (T() (where (Tt) is some known probability which depends on I,,,, and then the algorithm computes maximum-wedt weight matching on the resulting graph.
Hikima et al. (202I) prove an approximation guarantee for ISPCB by first studying a problem they denote Problem A. Problem A can be seen as the problem of stochastic bipartite matching with unit-patience side which we study here: For each edge (u, v) E E, Pu. Pr, (Tr ). bn = for each V1, and 4. Do for each V2. The proof of Theorem in Hikima et al. (202T) shows that an a-approximation of Problem A implies an a-approximation for ISPCB. The 1 1/3-approximation then follows from the 1 1/3-approximation for stochastic bipartite matching in Bansal al. (2012). Our Result 2 captures Problem A, which thus implies a (1 11-1/ 1/ee-approximmattoo for ISPCB, improving
on the previous //-aapproiiittion of Hikima et al. 2001
Acknowledgments and Disclosure of Funding
Nathaniel Grammel and Aravind Srinivasan were supported in part by NSF award CCF-1749864, and by research awards from Amazon and Google.
References
M. Adamezyk and M. Włodarczyk. Random order contention resolution schemes. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 790-801. IEEE, 2018
M. Adamczyk, F. Grandoni, and J. Mukherjee. Improved approximation algorithms for stochastic matching. In Algorithms-ESS ESA 2015, pages 1-12. Springer, 2015.
S. Ahmadi, F. Ahmed, J. P. Dickerson, M. Fuge, and S. Khuller. An algorithm for multi-attribute diverse matching. In C. Bessiere, editor, Proceedings of the Twemy-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pages 3-9. ijcai.org, 2020.
F. Ahmed, Dickerson, and M. Fuge. Diverse weighted bipartite b-matching. C. Sierra, editor, Proceedings of the Twenty-Sixth International Joini Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, 17 pages 35-41, ijeai.org, 2017.
A. Antoniadis, T. Gouleakis, P. Kleer, and P. Kolev. Secretary and online matching problems with machine learned advice. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 7933-7944.
10

---

Curran Associates, Inc., 2020. URL http::///ooooooooooooooooooo///p co.p:
N. Bansal, A. Gupta, J. Li, J. Mestre, V. Nagarajan, and A. Rudra. When lp is the cure for your matching woes: Improved bounds for stochastic matchings. Algorithmica, 63(4):733-762, 2012.
A. Baveja, A. Chavan, A. Nikiforov, A. Srinivasan, and P. Xu. Improved bounds in stochastic matching and optimization. Algorithmica, 80(1 1):3255-3252, 2018.
A. Borodin, C. MacRury, and A. Rakheja. Prophet inequality matching meets probing with commit- ment. CoRR, abs/2102.04325,, 2021. htttttts////xiii/
04325
B. Brubach, K. A. Sankararaman, A. Srinivasan, and P. Xu. Attenuate locally, win globally: Attenuation-base frameworks for online stochastic matching with timeouts. Algorithmica, 82(1): 64 87, 2020.
B. Brubach, N. Grammel, Ma, and A. Srinivasan. Improved guarantees for offline stochastic matching via new ordered contention resolution schemes. arXiv preprint arXiv:2106.06892 2021a la.
B. Brubach, N. Grammel, W. Ma, and A. Srinivasan, Follow your star: New frameworks for online stochastic matching with known and unknown patience. In A. Banerjee and K. Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 2872-2880. PMLR, 13-15 Apr 202 URL httt::/pproceediiie
mlr press/v preess/v130/bruuachllaa htth//brubaaaaaaaaaaaaaaaaaaaaae html
S. Bruggmann and R. Zenklusen. An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint. Mathematical Programming, pages 1-51, 2020.
S. Ehsani, M. Hajiaghayi, T. Kesselheim, and S. Singla. Prophet secretary for combinatorial auctions and matroids. Proceedings of the twenty-ninth annual acm-siam symposium on discrete algorithms, pages 700-714. SIAM, 2018
H. Esfandiari, N. Korula, and V. Mirrokni. Bi-objective online matching and submod- ular allocations. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Gar- nett, editors, Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016. URL https://proceediiie newris.euippp http:/g......re.../a//////////// cc/paperr2016/file) 066729007/d$4466655e22222211
.pff
H. Esfandiari, M. Hajiaghayi, V. Liaghat, and M. Monemizadeh. Prophet secretary. SIAM Journal on Discrete Mathematics,
31(3):1685-170) 31(a))maaiiii3333:1)633: 2017.
T. Ezra, M. Feldman, N. Gravin, and Z. G. Tang. Online stochastic max-weight matching: prophet inequality for vertex and edge arrival models. In Proceedings of the 2 ACM Conference on Economies and Computation, pages 769-787, 2020.
E. Fata, W. Ma, and D. Simchi-Levi. Multi-stage and multi-customer assortment optimization with inventory constraints. Available at SSRN 3443109, 2019.
R. Gandhi, S. Khuller, S. Parthasarathy, and A. Srinivasan. Dependent rounding and its applications to approximation algorithms. Journal of the ACM (JACM), 53(3):324-30 2603 2006.
N. Gravin and H. Wang. Prophet inequality for bipartite matching: merits of being simple and non adaptive. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 93-109, 2019.
G. Guruganesh and E. Lee. Understanding the correlation gap for matchings. arXiv preprint arXiv:1710.063399 2017.
Y. Hikima, Y. Akagi, H. Kim, M. Kohjima, Kurashima, and Toda. Integrated optimization of bipartite matching and its stochastic behavior: New formulation and approximation algorithm via min-cost flow optimization. The Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, 2021.

---

E. Lee and S. Singla. Optimal online contention resolution schemes via ex-ante prophet inequalities, In 26th Anmual European Symposium on Algorithms (ESA 2018). Schloss Dagstuhl Leibniz- fuer Informatik, 2018.
V. Nanda, P. Xu, K. A. Sankararaman, J. P. Dickerson, and A. Srinivasan. Balancing the tradeoff between profit and fairness in rideshare platforms during high high-demand hours. In The Thirty- Fourth AAAI Conference Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelliennce Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 2210 2217-221. AAAI Press, 2020.
P. Xu, Y. Shi, H. Cheng, J. P. Dickerson, K. A. Sankararaman, A. Srinivasan, Y. Tong, and L. Tsepenekas. A unified approach online matching with conflict-aware constraints. In The Thirty-Thee Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-Firss Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 February 2019, pages 2221 -2288 AAAI Press, 2019.
12


Reviews:
[{"review_id": "tdfKLSetoD6", "reviewer": "Reviewer_1hJb", "summary": "The paper considers a version of the stochastic matching problem. We have a graph with known weights on the edges but where each edge is present with probability p_e (also known). Sequentially, a decision-maker has to probe edges. When DM probes an edge, she can see whether the edge was present or not, and in the former case, she must include it in the matching. The main result in the paper is 0.382 approximation-algorithm for this problem. ", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "\nThe main result is quite interesting. It improves on a sequence of earlier work in the area and, quite notably, the 0.382 algorithm is obtained by probing edges in random order! \n\nSeveral variants and improved factors are discussed. A nice one (obtained as a corollary of the main result) is a best-known-to-date guarantee (of 0.432) for what the authors call prophet secretary under edge arrivals. Here the weights of the edges of a graph are random variables with known distribution and come in random order. A DM has to select edges online to form a matching. The goal is to maximize the weight of the matching, and the benchmark is the expected weight of a max weight matching. There are also many other results. These are a nice complement but somewhat less interesting to me. \n\nOne issue that is very interesting (and probably would be nice to have some more discussion in the paper) refers to the differences in the order of arrival of the edges. For the 0.382 algorithm, the authors use random order, but it turns out that nothing better is known even if the algorithm could pick the probing order. On the contrary, for the 0.432 algorithm, again the authors propose to use random order. But this does improve upon the best know algorithm with adversarial order. Is there some sort of general statement connecting these three possible orderings (chosen by ALG, random, adversarial). What happens in the first problem if the order is adversarial? What happens in the second if the order can be chosen by ALG?\n\nOverall I think this is a strong paper. It is, however, purely theoretical. The authors discuss some applications in AI but very en passant and unconvincingly. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Do not think it applies here.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "gdjo2BBiCUl", "reviewer": "Reviewer_Eoae", "summary": "They give an improved 0.38 approximation algorithm for a basic stochastic matching problem. They also get improvements for a few other variants. One notable result is improving a recent 0.33 approximation in [Hikima et al] to 0.63.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper obtains improved approximation algorithms for a number of stochastic matching problems. These problems are motivated from many applications in AI, such as ride hailing, online ads and crowdsourcing. \n\nThe most basic problem is the following. There is a weighted graph where each edge e is active with independent probability p_e. The set of active edges is initially unknown. An algorithm can “probe” edges sequentially: if an edge is probed and active then it must be included in the matching. There is also a “patience” constraint that at most t_v edges at node v can be probed. The goal is to maximize the expected weight of the matching. The paper gives a 0.38 approximation for this problem, improving on a 0.31 result (and many previous ones). The main idea is in identifying the correct “attenuation probabilities” in the previous algorithm [Baveja et al.]. Both the algorithm and analysis rely heavily on [Baveja et al.]. They also use the idea from [Adamczyk et al.] for damping the LP probabilities. However, they view this process more abstractly, by searching for an “attenuation function” with certain properties. This seems like a cleaner approach than ad-hoc choices of the damping factor. For a particular attenuation function, they show (numerically) that the approximation is 0.38. Is this the “best” attenuation function, or can one get a better bound with a different function? \n\nAn advantage of their approach (and some previous papers) is that the probing order is just random and not chosen in a careful manner. So the results also hold in the “random order” online setting. They also obtain some improvements for problems in this setting. \n\nFor bipartite graphs with unit-patience on one side, they get a much better 0.63 approximation. This special case was recently studied in [Hikima et al.] where a 0.33 approximation was obtained. The authors mention that their improved result also implies an improvement in the final result of [Hikima et al.]. This seems like a significant improvement for that problem- but, there are no details given.  \n---\nI'm satisfied that the authors' result improves on the main result in [Hikima et al.]. It will be good to add full details in a later version.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "GMcr76anMWX", "reviewer": "Reviewer_PbEY", "summary": "The paper considers the offline stochastic matching problem: Each edge e of the graph is equipped by a probability p_e (that it exists) and a weight w_e. \nThe goal is to find a good probing strategy: an edge can be probed if we can add it to the current matching, if probed and it exists it has to be added to the matching. One difficulty is that vertices have patience constraints stipulating how many adjacent edges the strategy can probe.\n\nThe main results of the paper are\n\n- An improve approximation guarantee of 0.383 for general graphs; improving upon the previous best 0.31.\n\n- An improved guarantee of 0.432 if vertices have unbounded patience (it is trivial to get 1/2 by querying the edges in decreasing order; however their result applies in the random edge-arrival online model)\n\n- In the special case of bipartite graphs and one side has unit patience, they get an 1-1/e guarantee improving upon a recent 1/3-guarantee.\n\nThe results are nice and are obtained by interesting insights.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper provides original and interesting results. \n\nThe improved approximation guarantee for general graphs heavily builds upon a prior work and adds the idea of \"decreasing the probability of very likely edges\". This is a quite well-known trick but still leads to the improved guarantees in this setting.  I am not certain why a family of attenuation functions is better than having one that works.\n\nThe result for bipartite graphs with unit patience on one side is obtained by a pretty natural negative correlation rounding.\n\nAll their results also apply to the random order online setting  except for the last mentioned bipartite case. This leads to interesting contention resolution schemes for general graphs and results for the prophet secretary problem in that setting.\n\nI find the result for rank-1 matroids less interesting. The Lee and Singla result apply to all matroids with the same guarantee and I am not convinced that the presented schemes are much better.\n\nOverall, I find it quite a nice collection of results. A concern is why NeurIPS would be the right venue. The authors should do a better job explaining why this is related to learning (now they simply cite a couple of papers but they don't spend much effort in explaining the relationship). Also a more detailed comment is if there is any known integrality gaps of the studied LP?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See the last paragraph in the main review. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "CJim9spdoFu", "reviewer": "Reviewer_2oiH", "summary": "The submission focuses on the following “stochastic matching” 1-player game: Nature samples a (hidden) graph, where each edge appears independently with probability p_e. The Algorithm can sequentially probe candidate edges. If an edge belongs to the graph, its vertices are matched and can not participate in later matches. The goal is to maximize the total weight of matched edges. In one of the variants, each vertex also has a (known-to-the-algorithm) patience which upper bounds the number of allowed attempted matches.\n\nThere is also a second result which generalizes ordered CRS from independent r.v. to negatively correlated.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Previous work proposed the natural approach of solving a fractional + in-expectation LP relaxation, and then sequentially probing the edges (in random order) with probabilities obtained from the LP solution. The goal of the analysis is to bound the minimum probability that any edge is probed, compared to its probability in the LP solution (which is an upper bound on the integral but offline optimum).\n\nThe authors of the new submission notice that this solution unfairly discriminates low-probability edges: out of k edges w.p. 1/k, we only have probability 1-1/e of picking one of them. In contrast a single edge with probability 1 (which appears identical to the LP) will be picked w.p. 1. This creates a bottleneck in the analysis when low and high probability edges are competing for matching the same vertex. To overcome this issue, the authors propose to weigh down high-probability edges, yielding improved constant factors in the competitive analysis. \n\n\n\nI think that this work will be quite interesting, but to a small crowd of specialized experts. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All of the reviewers liked this paper and felt that it should be accepted. 
Decision: Accept (Poster)