Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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. 
The 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.

The main results of the paper are

- An improve approximation guarantee of 0.383 for general graphs; improving upon the previous best 0.31.

- 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)

- 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.

The results are nice and are obtained by interesting insights.
main_review: The paper provides original and interesting results. 

The 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.

The result for bipartite graphs with unit patience on one side is obtained by a pretty natural negative correlation rounding.

All 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.

I 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.

Overall, 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?
limitations_and_societal_impact: See the last paragraph in the main review.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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. 
main_review: 
The 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! 

Several 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. 

One 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?

Overall 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. 
limitations_and_societal_impact: Do not think it applies here.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.

There is also a second result which generalizes ordered CRS from independent r.v. to negatively correlated.

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).

The 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. 



I think that this work will be quite interesting, but to a small crowd of specialized experts. 

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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. 

The 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? 

An 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. 

For 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.  
---
I'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.
limitations_and_societal_impact: yes
review_title: null

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