Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper considers the vertex-weighted online bipartite matching problem where the online vertices arrive in two batches. In the first batch, along with the neighborhoods of all vertices of the first batch, the algorithm is also provided with a predicted matching. The algorithm needs to commit to a matching, and then the second batch of online vertices are revealed and the algorithm can now match these new vertices to the set of unmatched offline vertices. The goal of the algorithm is to maximize the weight of the final matching. The paper defines the “robustness” of the algorithm as the ratio of the weight of the matching found by the algorithm to the weight of the optimal offline matching, and the “consistency” as the ratio of the weight of the matching found by the algorithm to the weight of the best matching obtained by following the predicted matching exactly. The primary contribution of the paper is to quantify the exact trade-off between these quantities.

strengths_and_weaknesses: It’s great that the authors can obtain a tight and non-trivial tradeoff between robustness and consistency for this model. The paper is well-written and is easy to read and follow.

The analysis and algorithm are based on Feng et al, and the primary observation is that any penalty function within a range of functions is sufficient to guarantee the desired robustness guarantee. By then adjusting the penalties for vertices in the predicted matching and for those not in the predicted matching, the bound on consistency follows.  

I appreciate the discussion in the introduction on alternate definitions of consistency and the notion of prediction error. 

questions: None
limitations: None
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies online matching with advice. In particular, the authors focus on a two-stage online bipartite matching problem, where vertices of part A are weighted and known in advance, while vertices of part B arrive in two batches. Each vertex arrives with all its incident edges, and we need to make irrevocable decision about matching each vertex in B.

Similar to the new literature on advice-augmented algorithms, a (supposedly good) matching for the first batch is given before the second stage begins. Two measures of robustness and consistency are important in this regime. Robustness compares with the optimal solution regardless of the advice, and consistency looks at optimality assuming the advice is correct. Compared to the usual prediction-error bounds, consistency is simpler to understand (one can translate between them).

The authors manage to characterize the Pareto frontier of robustness and consistency by presenting an essentially optimal algorithm. Note that without advice, a 3/4-competitive algorithm exists (due to [FNS21]), which trivially translates to a (3/4, 3/4) advice-augmented solution. A naive solution following only the advice obtains a (0, 1) guarantee (0 for robustness and 1 for consistency). While with a coin flip between the two methods, one can get a smooth linear tradeoff, the authors show how to use different set of penalties to obtain the optimal tradeoff of $\sqrt{1-R} + \sqrt{1-C} = 1$.
strengths_and_weaknesses: Strengths:
-First characterization of Pareto frontier for online bipartite matching.
-Tight guarantees.

Weaknesses:
- Lack of experiments on actual online bipartite matching datasets.
questions: none
limitations: n/a
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this paper, the authors consider the two-stage bipartite matching problem in a relatively new setting: there is an unreliable prediction in the first stage. The goal is to design the online algorithm which can balance the consistency (performance in the best case) and the robustness (performance in the worst case). Their algorithm can achieve the optimal Pareto-efficient frontier between consistency and robustness. The key idea is to choose different penalty functions for different offline vertices. They prove that their algorithm can achieve R-robust and C-consistent if the value R,C satisfy the inequality \sqrt{1-R}+\sqrt{1-C}<=1. They also give the tight example to show that such tradeoff is optimal. 
strengths_and_weaknesses: Strengths:

1.	The result shows the clean and optimal tradeoff relation between consistency and robustness. This is a very nice theoretical result.
2.	It is nice to model the consistency as ALG/ADVISE. In many other papers, we will model consistency as the performance of algorithm when the prediction is accurate. It is difficult to argue tradeoff between consistency and robustness. Thus, the model in this paper is in some sense more equal between consistency and robustness.

Weaknesses:

1.	The results hold only for a simple setting of online matching, that is, they consider only vertex-weighted version and two-stage model. However, although it is unclear how to generalize the results to edge-weighted or multi-stage, it is an interesting start.

questions: I have a question about the claim “we can assume the second-stage graph is a matching” in section 2, page 5. If we only consider the measurement robustness (or consistency), we can assume the second stage graph is a matching, which is exactly the matching chosen by OPT (or ADVICE). However, if we consider both the robustness and the consistency, I am not convinced that we can assume the second stage graph is a matching. In the worst-case instance, it is possible that OPT and ADVICE chooses different matchings in the second stage graph. If this is the case, suppose we delete all edges which are not selected by OPT in the second stage graph, OPT(G) keeps the same while ALG(G,A) may decrease. However, in this case, we do not know the change of ADVISE(G,A), thus consistency C might be increase. I still think the claim should be correct, but the argument is not clean. 
limitations: Yes. The authors clearly address the limitations. I don’t think there are potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper studies the problem of augmenting the recently introduced two stage vertex-weighted online bipartite matching problem with predictions. In this problem one "sees" one side U of the bipartition. The vertices on the other side W are associated with a weight each and arrive in two batches. The algorithm has to decide on which edges to add to the matching after the first batch arrives and then do the same again after the second batch arrives (while still being consistent with previously selected edges). Goal is to maximise the total weight of vertices from W that are matched.

The authors argue that it is without loss of generality to assume that the vertices of the second batch only come with the edges that the optimal solution uses for these vertices, so the problem essentially reduces to handling the first batch. It is assumed that the algorithm has access to a prediction on how to match the first batch of vertices. This prediction may or may not be accurate, so the algorithm needs to keep a sort of tradeoff, between safe-guarding itself for all possible second batches that could still arrive (robustness) and following the predicted matching (in order to attain consistency, i.e., good performance when the prediction is accurate). 

There is already a recent result by Feng et al. (SODA 2021) that looks at the problem without predictions. The proposed algorithm here identifies, for each desired robustness how to fine tune the parameters in Feng et al.'s  algorithm so as to obtain the best possible consistency that the desired robustness allows. A very simple example shows that the obtained robustness and consistency are Pareto optimal.
strengths_and_weaknesses: Strengths:

- The matching problem considered is quite interesting.
- Although the algorithm is a slight modification of the one by Feng et al., there is still a non-negligible amount of technical work required to "set the parameters" correctly and prove the obtained results

Weaknesses:

- I found it quite hard to follow the paper. The main reasons I could identify for this are the following:
* The problem is not clear at all. The first time the paper mentions that they actually look into the *maximization* version is on page 5. I was until this point under the impression that a minimisation problem is considered which made many statements confusing (I assume if I were familiar with Feng's result it may have been clear, but in my opinion the authors should not assume familiarity with that result). 
* The performance of the algorithm (also the one without predictions) must surely depend on the sizes of the respective batches D_1 and D_2, but this is not touched upon at all. It seems to me that this is handled by the way that consistency is defined (i.e., comparing to an algorithm that uses the same batches). The authors suggest a way to define an error measure to get a result as a function to the prediction quality, similar to other results in the area. This definition seems to me quite adhoc, and not very reasonable. The only justification seems to be that "this works" to give the desired formula. 

- I find that predicting the whole matching for D_1 at once can be a bit unnatural. 

- I am not sure if I would call the problem online. It resembles some similarity to online algorithms in that there must be an irrevocable decision after the first batch without knowledge of the second batch, but thats all. Also it should be made more explicit that the whole batch arrives before the algorithm needs to decide anything.

- The paper refers to the prediction as advice. This can be confusing, since in the online algorithms literature the term "advice" has historically been used for predictions that are guaranteed to be optimal (and usually one studies the relationship between the amount of that advice required to obtain a specific performance guarantee). When the predictions are of unknown quality as is the case here, the term "predictions" seems to be much more established and I would suggest to change the paper accordingly.

- No experimental evaluation is contained.
questions: Can you obtain similar results when the number of batches increases to 3? What about the "purely online" setting with "n batches"? I would find this a much more interesting problem/result. If not, where is the challenge?
limitations: No potential negative social impact. With respect to limitations, see above.
review_title: null

Meta-review: metareview: The paper studies two stage matching with advice and completely characterizes the tradeoff between the robustness and consistency. The online matching problem is a central problem in online algorithms with numerous applications such as assigning jobs to machines, impressions to advertisers, etc. The model studied here is a very simplified online model where there are only two stages. On the other hand, the paper is a rare case in advice augmented algorithms where the tradeoff between robustness and consistency is fully understood. The reviewers all appreciate the tight characterization. There is a minor concern that the paper does not include experimental evaluation. The authors are encouraged to include the simple result for the edge weighted case (in the author response) to provide more context to the main result.
confidence: Certain
Decision: Accept