Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model
Authors: Billy Jin
Will Ma
Venue: NeurIPS 2022 Accept (2022)
Keywords: Online matching
online algorithms with advice
prediction augmented
learning augmented
two stage optimization

Abstract: We study the two-stage vertex-weighted online bipartite matching problem of Feng, Niazadeh, and Saberi (SODA ‘21) in a setting where the algorithm has access to a suggested matching that is recommended in the first stage. We evaluate an algorithm by its robustness $R$, which is its performance relative to that of the optimal offline matching, and its consistency $C$, which is its performance when the advice or the prediction given is correct.  We characterize for this problem the Pareto-efficient frontier between robustness and consistency, which is rare in the literature on advice-augmented algorithms, yet necessary for quantifying such an algorithm to be optimal. Specifically, we propose an algorithm that is $R$-robust and $C$-consistent for any $(R,C)$ with $0 \leq R \leq \frac{3}{4}$ and $\sqrt{1-R} + \sqrt{1-C} = 1$, and prove that no other algorithm can achieve a better tradeoff.

Online Bipartite Matching with Advice: Tight Robustness-Consistenny Tradeoffs for the Two-Stage Model
Billy Jin Cornell University bzj3@cornell..c edu
Will Ma
Columbia University wm24280gsb. columbia. edu
Abstract
We study the two-stage weriht-weighted online bipartite matching problem of Feng. Niazadeh, and Saberi (SODA '21) in setting where the algorithm has ac- cess to suggested matching that is recommended in the first stage. We evaluate an algorithm by its robustness R, which its performance relative to that of the optimal offline matching, and its consistency C, which is its performance when the advice or the prediction given is correct. We characterize for this problem the Pareto-efficient frontier between robustness and consistency, which is rare in the literature on auggentd algorithms, yet necessary for quantifying such an propose an algorithm that is R-robust
algorithm to be optimal. Specifically, and C-consistent for any (R. C) with 0 < R < and - vI-C and prove that no other algorithm can achieve better tradeoff.
Introduction
Online bipartite matching is fundamental model used assign incoming requests to servers, in- coming workers to jobs, incoming impressions to online advertisers, etc. Traditionally, it has been studied in either the adversarial setting, where nothing is assumed about the future; the stochastic setting, where future arrivals are assumed to follow a distributional model. However, algorithms for the former tend to be overly conservative in their decisions; whereas algorithms for the latter perform terribly when the assumed model is wrong. Therefore, recently budding literature has studied advice-augmented online algorithms, which use machine-learned prediction refine their decisions, but do not perform as terribly when the prediction is wrong.
In many problems including online matching, there is an inherent tradeoff between algorithm's 's performance when the prediction is correct, called its consistency, and the algorithm's performance under the worst-case future, called its robusmess. This is because high consistency can only be achieved by optimizing as if the predicted future was correct, resulting in a decision that can be terrible in the worst case. Conversely, high robustness requires hedging against all possible futures, which does not sufficiently prioritize the one predicted to come true.
In this paper characterize tight robustness-consistene by adding advice to the model of Feng et al. [1] where the online vertices arrive two stages (but many online vertices can arrive simultaneously). That is, derive a continuum of algorithms for two-stage online bipartite matching that define the Pareto-efficient frontier the tradeoff between performance when prediction is right performance when it is wrong. To our knowledge. Pareto- efficiency results are rare in the literature on advice-augmented online algorithms, especially when it comes to online matching (as review in Subsection I.3); yet, they are necessary for quantifying an verice-augmented online algorithm to be optimal. We now concretely explain the model, our algorithm, and the Pareto-efficient frontier it achieves between robustness and consistency.
tradeoff for online bipartite matching.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

1.1 Model and Results
We study the two-stage version of the maximum vertex- certe--weighte bipartite matching problem (see Subsection 1.2 for other variants). In this problem, there is an underlying bipartite graph G L. E), where D stands for "demand" and S stands for "supply". The vertices in S are weighted and offline (i.e. known in advance), while the vertices in D arrive online in two batches Dj and D2- After the vertices in each batch arrive, all their incident edges to S are revealed, and the algorithm chooses matching in the resulting subgraph. (In particular, note that the first time the algorithm needs to make decision after the entire batch Dj has arrived.) The algorithm's 's choices are irrevocable, and the goal of the problem is to maximize the total weight of the matched offline vertices after both batches have arrived, Observe that the optimal second-stage decision clearly to select the max-weight matching subject to the matching already chosen in the first stage; therefore the complexity of the problem boils down to finding a good first-stage matching.
In the advice- aurieee-uggeeeed model we introduce, the algorithm receives suggested matching A to make after the edges incident to the ftrst-stage vertices Dj have been revealed. Our model allows for an arbitrary advice A, although typically A would be the matching that, for a given (probabilistic) prediction of D2 and its incident edges, maximizes the (expected) total weight matched after both stages have arrived. (There is a different line of work (see (2) that assumes access to an oracle that gives perfect advice and studies the minimum number of queries needed to obtain a given guarantee.)
We define consistency based on this suggested matching, and explain later how it reduces to the standard notion of consistency based on prediction error (see Subsection I.2). That is, we define an algorithm's is consistency as how well it performs relative to the best matching that could have been obtained by exactly following the advice in the first stage. Meanwhile, we define an algorithm's robustness using the standard notion of competitive ratio, which is the algorithm's 's performance relative to the optimal maximum- mexigt matching in hindsight. We then say that an algorithm is C-consistent and R-robust, respectively, if its consistency is at least C' and robustness is at least R for all possible graphs G and suggested matchings A. Formally, this requires
inf ALG(G, A) G.A A)VICE(G.A)
2 C and inf ALG(G, A) G,A OPT(G) 2 R.
(1)
where following the earlier descriptions, ALG(G, A) is the algorithm's expected performance when given advice A and the graph ends up being G, ADVICE(G, A) is the performance from following advice A exactly on graph G, and OPT(G) is the meximum-weiggh matching in graph G. Note that since ADVICE(G, A) < (G) any algorithm that is R-robust is automatically at least R- consistent. However, C' can be higher than R. and having a consistency guarantce is desirable when the advice is good, because intuitively ADVICE A) will be large and close to OPT(
We now describe our algorithm. Here, it is convenient to consider the fractional relaxation of the problem, which allows vertices to be filled partially. In Section problem and show how to losslessly round any fractional solution to a randomized matching, so that we can focus on defining our algorithm for the fractional problem.
2 we formally define the fractional
First, in the absence of advice (i.e. when one only cares about robustness), traditional algorithms for online matching can be described as using a penalty function to "balance" how much to fill the offline vertices; the optimal competitive ratio usually achieved by carefully choosing the right penalty function. Using a linear penalty function, Feng et al. [ give an algorithm for two-stage bipartite matching that is _ --robust, which they prove optimal. However, since this algorithm makes no use of the advice, it only 3 3-consistent. On the other hand, note that the naive algorithm which always follows the advice exactly is I-consistent but O-robust. At this point, natural idea for obtaining a continuum of cooustness-consiseenn with probability p. and otherwise run the naive algorithm with probability 1 1- p. As the coin-flip probability p ranges from 0 to 1, the robustness/consistenyyy of this coin-flip -lip algorithm ranges along the line between (R, ()) (0, 1) and (R, C) = (2. }) (see the orange dashed line in Figure I
guarantees is to run the algorithm of Feng et al. M
To improve upon these naive guarantees, we revisit the penalty function approach. Our main insight is that for any given robustness level R E [0, 31, there is actually a family of penalty functions that guarantees R-robustness. While a traditional algorithm for online matching would choose the same penalty function for all the offline vertices, we observe that by choosing different penalty functions, we can incentivize the algorithm to prioritize matching to the vertices that are suggested by the advice, all while guarantecing R-robustness. We prove that such an algorithm ends up being
2

---

Robustness-Conssistenyy Tradeoff Curve
1.00
0.95
Consistency
0.90
0.80
0.75
Ours (lwo stage, tight)
Coin Flip (two stage)
0.70
Mahdian al. '12
0.65
Coin-Fiip (multi-stage)
Robustness R
Figure 1: Robustness--conssseenn tradeoff curves for various algorithms.
C-consistent, where C' is the unique value (decreasing in R) that satisfies the equation v1 R + vI- = 1. This curve is also plotted in Figure [ and is a significant improvement over the straight-line interpolation. This elementary, symmetric curve also happens to be tight.
Organization of paper. Notation and the reduction from integer to fractional matching is presented Our algorithm is formally defined in Section Proofs of robustness and consistency are sketched in Section and Section SistonnSrrespe respectively highlighting our new techniques. The hardness instance certifying our tradeoff curve of vI R + vI C 1 to be tight presented in Sec- For the full, most up-to-date version of the paper which includes all proofs, please refer to
in Section 2
tion [
https:/aariv.or//bb//00...
1.2 Discussion Other Variants and Definitions
Multi-stage variant. Classical models of online matching and budgeted allocation allow more than two stages online arrivals, and algorithms that hybridize between a fixed "advice" algorithm and traditional algorithms that "balance" against the adversary were introduced in Mahdian et al. [5]. However, under this framework it is difficult to define how the advice algorithm should react if the observed arrivals start to diverge from its predictions, making any tightness results between robustness and consistency elusive. Instead, we focus on the elegant two-stage model of Feng et al. [1 avoiding any complexities in how the advice should adapt the accuracy of past predictions.
We note that the guarantees in Mahdian et al. (5] do not apply our setting, since they do not handle the innovation in Feng et al. [1 of allowing multiple online vertices to arrive simultaneously. How- ever, even supposing they could be generalized with no loss, their guarantees would be significantly worse than ours (see Figure D which plots in green the tradeoff curve described in Theorem 4.1 in their paper). fact, as observed the upper-left part of Figure μ the guarantees of Mahdian et al. [5] can be worse than the simplistic coin-flip algorithm that either runs the "advice" algorithm, or runs the "balance" algorithm from the multi multi-stage setting This demonstrates the need for a simpler advice-augmented online matching framework
propose, in which the Pareto-efficient tradeoff between robustness and consistency can be exactly understood.
Unweighted variant. In the special case where all offline vertices have weight 1, better robustness- consistency tradeoff possible- in fact, the simplistic coin-flip algorithm is optimal. This is be- cause in the unweighted case, any maximal matching is at least as large as optimal, and there- fore naively following the advice is now -robbust (instead of 0-robust) and still 1-consistent. The vobustness-conssitene guarantees are now defined by the straight line between (Rt C) = 1)) and (R, C) (2, }). which optimal F However, in the vertex- weighted variant the straight-line guarantees are suboptimal, justiffn the need for our approach in Subsection
I.1
'n the stage setting, the analogue "balance" only (1 - robust hence the guarantees
soin-flip algorithm range along the line between (R, C) (0, 1) and (R, (1 !, !)) (see the red dashed line in Figure I).
"The instance which shows that this straight line tradeoff is tight for the unweighted setting is similar to the instance in Section 6 and can be found in the full version of the paper.
3

---

Edge-weighted variant. In this variant, the edges of the bipartite graph are weighted, and the aim to maximize the total weight of the edges in the matching. For 2-stage edge-weigs seigeweeghted bipartite matching, the naive coin-flip flip algorithm also turns out to be best-possible: The optimal tradeoff curve the line segment between (R, C) = (0, 1) and (2) 2). To see this, first note that the best possible robustness is 2' This is achieved by an algorithm that 1) with probability 1 finds the maximum 2.
matching M1 in the first stage and does nothing in the second stage, and 2) with probability 1 does nothing in the first stage and finds the maximum matching M2 in the second stage Thus, the coin-flip algorithm which naively interpolates between the 2 -robust algorithm and the I-consistent algorithm (that always follows the advice) attains the tradeoff.
To show the tradeoff is tight, consider first-stage graph consisting of single edge with weight 1, and suppose the advice suggests matching the edge. Let x be the probability the algorithm matches the edge. Any R-robust algorithm must have x - R. because if x 1 R then we cannot maintain Rt-robustness if in the second stage, a single edge to the offline vertex arrives with very high weight. Since I 1 R. this means the maximum consistency on this instance is 1 R (which is the case if the second-stage graph is empty). Thus, just as in the unweighted case, straight-line tradeoff is also optimal in the adge-weighted variant.
Consistency defined based on prediction error. Many papers on prediction-auggeented online al- gorithms (reviewed in Subsection 1.3) do not analyze two separate ratios ALG(G.A) and ALG(G.A) ADVICE(G,A)) OPT(G' parameterized by prediction error, and define consistency as the guarantee obtained when the error is O. The prediction error captures how much the prediction deviates from the truth, and its precise definition depends on the problem at hand.
OPT(G)
Instead, they provide a general guarantee ALG(G,A)
Our definition of robustness and consistency can be easily translated to a guarantee involving pre- diction error, because we can always define the error of advice A to be vi == ADVICE(G.A)
OPT(G.A) When
we do so, our robusmnes/consistency guarantee immediately implies the parameterized guarantee ALG(G.A) OPT(G) 2 max RR (1 - 1)) (2v1 R (1 R))}, for any value of R E [0, 2 that we can set. More generally, our definition can accommodate other notions of predictions and their associated error, as long as it is possible to quantify how they affect the value of ADVICE A)
1.3 Further Related Work
Despite the recent surge of interest in both online matching and online algorithms with advice (see the recent surveys Huang and Tröbst ? and Mitzenmacher and Vassilvitskii g respectively), lit- crature on online matching with advice has been relatively scant. We mention some papers this intersection below, as well as other related work.
Online matching with advice. Since Mahdian al. more recently Antoniadis al. p have introduced an online random-ordes edge-weighted bipartite matching problem with advice that pre- dicts the edge weights adjacent to each offline vertex in some optimal offline matching. Lavastida et al. [ introduced a framework that formalizes when predictions can be learned from past data, and their algorithmic performance degrades gracefully as function of prediction error. Broadly speaking, our work contrasts these three papers in that we are able to understand tight tradeoffs in whether to trust some advice, although in an arguably simpler setting.
Online matching models in-between adversarial and stochastic. Instead of abstracting all in- formation about the future into single piece of prediction/advice that could be wrong, another approach is to postulate an explicit model for how the future can deviate from past observations. Examples of this include the semi-online bipartite matching model of Kumar al. [10) and the partially predictable model of Hwang et al. [I]] We note that random-order arrivals can also be
viewed as a form of partial predictability which allows learning [2], and moreover it is possible
to derive simultaneous guarantees under adversarial and random-order arrivals [3] which have the
'This algorithm is } robutt because the value of the optimal matching is at most the sum of the values of Mi and M2. On the other hand, it is an easy exercise to find an example which shows that no algorithm can be more than } -robust.
'A an example, Lavastida et al. 6 measure prediction emrrr using a notion of total variation distance on the number of each "type" of online vertex to arrive. They propose algorithms that take advice in the form of a proportional allocation weight for each offline vertex.

---

same flavor as robustness-consiitengg consistency guarantees. Finally, we mention that the single sample model in Kaplan et al. [4] can be viewed a form of online matching with advice that is highly erroneous.
online algorithms. Tight robustness-come centssees--cosssteneey tradeoffss have become recently understood in prediction-augmentee ski rental 15 and single- commodity accept/reject problems [88 [9]. Our online matching problem contrasts these by having multi-dimensional state space, for which to our knowledge tightness results are rare. We should mention that in multi-dimensional problems such as prediction-augmente welfare maximization 21. "optimality" results in which consistency can be achieved with no loss of robustness (i.e. there is no "tradeoff") have been derived.
Optimality results in prediction-augment
caching (20] and online
Two-stage models. Two-stage models capture the essence of optimization under uncertainty, where the first-stage decision must anticipate the uncertainty, and the second-stage decision is usually a trivial recourse after the uncertainty (in case the second-stage graph) has been realized. We refer to Birge and Louveaux [22] and Bertsimas et al. [33 for broad overviews of two-stage stochastic and robust optimization. In this paper we focus on the two-stage online matching model of Feng et al. M. introducing advice to this model and fully characterizing the tradeoff between obeying vs. disobeying the advice. We note that multi-stage online matching model motivated by batching has also been recently considered in Feng and Niazadeh [24]. and two-stage matching has been formulated as a robust optimization problem in Housni et
2 Preliminaries and Notation
The problem input consists of a bipartite graph G = (D, S,,,,)), E), where the online vertices in D arrive in two batches D1, D2. We index the vertices in D (resp. 5) with (resp. j). When the vertices in D& (k 1) arrive, all their incident edges to S are revealed, and the algorithm irrevocably chooses a matching Mr between D2 and S. Each offline vertex j E S has a weight wj, and the goal is to maximize E(.j)EM,MM Wj. We evaluate algorithm by its robustness and consistency, which were defined in Subsection
AI
Worst-case instances. The following observation is crucial to our analysis. Note that when bound- ing robustness and consistency, one assume WLOG that the second-stage graph consists of matching. To see this, suppose we are bounding robustness, and consider the edges not matched by (PT(G) in the second stage. Deleting these edges does not change the value of OPT(G) and can only decrease the value of the matching found by the algorithm. Therefore we may assume that the second stage graph consists exactly of the matching selected by OPT(G) in the second stage. The same argument shows that when bounding consistency, we may assume that the second-stage graph consists exactly of the matching selected by ADVICE(G, A) in the second stage. Therefore from now on we assume the second-stage graph is a matching.
Reduction to fractional matching. The preceding observation about worst-case instances allows us to focus on the fractional version of the problem, which is easier to analyze and defined as follows. In each stage, the algorithm chooses a fractional matching instead of an integral one. Let x = (Iag : i E DI.5 E S, (i. E E) be the fractional matching chosen in the first stage, so that satisfies the constraints 2;
Σ En(t,))E Zij I and zj := EE(()) Taj I 1. Similarly, let y (Vi : D2.j E S, (i,j) (.()) E) be the fractional matching in the second stage, which satisfies V: = EE..EE Vij I 1 and yj == Ex..neE Vij < 1 - zj. The objective in the fractional problem maximize Ejes Wy + yj)- As mentioned earlier, the first stage decisions xj are the critical ones; therefore we will use the terminology that each offline vertex E S is filled to water level x; at the end of the first stage.
Although the fractional problem seems at first to be easier than the integral problem, it turns out to be straightforward to convert any fractional algorithm for two-stage bipartite matching into a (randomized) integral one with the same robustness/consiitency guarantees. To see why, consider any fractional algorithm and let x its first-stage output. To convert this to a randomized integral algorithm, sample integral matching Mj with marginals equal to x (i.e. P)(())) E M) = Zij
5

---

ALGORITTM 1: Algorithm for Two-Stage Fractional Vertex Weighted Bipartite Matching with Advice
Input: Suggested matching A in the first-stage graph and desired robustness level R.
1: (Define penalty functions) Let (x) = max (0. 1- } and fu(æ)) min [1, 1-2).
2: (First stage) When the first-stage vertices Dj arrive, let Si C S be the set of offline vertices that are in the suggested matching A. Set fj = ft for all j E Si and f, = fu for all j E S St.
Solve the following optimization problem for the first-stage fractional matching x:
(Pt)
max
(t)dtt
JES
s.1. Iy
Σ
Fij 1
ViED,
Ij
Σ
Túj -1
VjES
(EDE-LLEE
Fij 20
Vie Di, (1.5) E
3: (Second stage) When the second-stage vertices D2 arrive, solve for the optimal fractional matching y subject the capacities already taken by x:
(P2)
max
JES
s.t. yk =
Σ
Vis 1
ViE D2 AjES
Σ
V6 S 1 B)
ie DED
Vij 2
ViE D2. (
4: Return x + y.
for all edges (1 in the first-stage graph) We then take M2 to be the maximum-weige weight matching in the second-stage graph, subject to Mj already being chosen.
To analyze the (expected) weight of the integral matching M1 M2, note that in the first stage the expected weight of M1 is equal to that of x by construction. Now consider the second stage. As we have argued, we may assume the second-stage graph consists of a matching; let (i,j) be one of these edges. The contribution of (i, to the value of the fractional algorithm is wy 2z), because the remaining amount that offline vertex j can be filled is (1 - xz)). On the other hand, the integral algorithm will match ji in M2 if and only if is unmatched in M1. which happens with probability (1 x. So the contribution of (i.j) to the expected increase of the integral algorithm is also wy(1 ..y). Since the integral version of the problem can be reduced to the fractional version,
we focus on the latter in the remainder of the paper.
Algorithm
As argued in Section 2 losslessly round fractional matching integral one. Therefore we focus on the fractional two-stage bipartite matching problem from now on. Our algorithm is described in Algorithm 0 The main challenge is commit to a matching when the first-stage graph is revealed, that incorporates some advice but maintains a worst-case competitive ratio.
Intuitively, the amount æy that each vertex j E S is filled to after the first stage is governed by three factors. First, it should depend on the weight wy; the larger wj is, the larger æ, should be. Second, it should depend not. Third, it should depend on how much the other offline vertices are filled; the larger I, is compared to the other vertices competing to be filled, the more hesitant should be of filling it even further, because this can be exploited by a second-stage graph whose edges are incident to the
the advice; 2; should be larger if j is recommended by the advice, and smaller
'Since the bipartite matching polytope is integral, x can be written as convex combination of inte- gral matchings. Such convex combination can be found in polynomial time using algorithmic versions of Carathéodory's theorem.

---

1.0
1.0
1.0
fudi 6000
0.8
0.8
0.8
0.6
fulx)
0.6
0.6
0.0
0.2
0.0
0.2
Figure 2: Plots of fL and fu for three values of R. Left: R = 0. Middle: R Right: R 4'
The consistencies achieved are C C, C 1. respectively. In the right plot, the green dashed line indicates the penalty function used by Feng et al. MI
vertices which have already been filled the most. Typically, the third point is achieved by defining penalty f(zz) [0, 1] the marginal benefit of filling j. with f(z,) increasing in Zj, which encourages the balancing of the water levels across j E S. This is combined with the first point by associating a potential (1 f(z)) with each j S. The algorithm then decreases these potentials while filling water levels, with the aim of equalizing them as much as possible.
Our main idea to address the second point, now that there is some advice, is to use lower penalty rate (I,) to incentivize the filling of offline vertices j S, that are matched by the advice, and higher penalty rate fu(r)) for & S1. More specifically, for any desired "robustness" R, our analysis characterizes the envelope of penalty functions f [0, 1] - [0, 1] (see Theorem D that guarantees worst-case competitive ratio of R, and defines fL, fu according the lower, upper boundaries of this envelope respectively.
Figure 2 plots the penalty functions ft and fu for three values of R. The parameter R E [0, 4 affects the separation between fL and fu- If respectively, from which it can be seen that Algorithm will fully match all the vertices suggested by the advice. Intuitively, setting A = 0 is desirable when we trust that the advice will perform well. On the other extreme, setting R 3 guarantees the maximum possible robustness, which is not reliant on the advice. Surprisingly, even this case there is bit of separation between fL and fu (see Figure 2 and hence the algorithm still discriminates between offline vertices E S1 j & S1, despite its distrust in the advice. We plot one intermediate value where R g-
O, then fL, fu are the constant functions 0,
Finally, having decided penalty functions for the offline vertices, there is still the question of how to balance their potential levels when multiple online vertices D1 can arrive in the first stage. For- tunately, this question was answered by Feng et al. [1]. who show that problem Pi is the right one solve, and establish neat structural decomposition on its solution. Our Lemma μ is simpli- fied version of the structural decomposition from their paper, which suffices for our purposes, and importantly, allowing for heterogeneous penalty functions across offline vertices j S.
Definition 1. Let be the first-stage fractional matching found by Algorithm 7 For all E S, we say j is filled if ã; = or (ī,) 1. Let F denote the set of filled offline vertices, and let U = S denote the set of unfilled offtine vertices.
Lemma 1. After the first-stage fractional matching, the following statements hold for all E Di:
1. If has any unfilled neighbor (i.e. j U for some j with (i.j) E E), then F; = 1.
2. For any unfilled neighbor j and any neighbor with L.k > 0, it must be that
wy (z(;,)) S wp fx())))
(2)
We explain the intuition behind Lemmal Property holds because if T. instead, then variable Taj where j is any unfilled neighbor of could have been increased to strictly improve the objective of (P:). Meanwhile, Property 2 holds because Z. > 0, i.e. is being used to fill in the current solution, then the potential of & must be no less than the potential of any unfilled neighbor j that could have been filled instead. We note that the structural decomposition in Feng et al. M richer, but our simplified properties suffice for our purposes and are easier to establish when our penalty functions fj (due to heterogeneity) do not necessarily satisfy their boundary conditions such as (0) 0 or (1) 1. For space reasons, the proof of Lemma D is in the full version of the paper.
7

---

3 II
11
2 11
0
2
2
(a) The fully robust solution.
(b) The algorithm's first-stage
(c) The algorithm's first-stage matching if the advice suggests (1,2). (2,3).
matching if the advice suggests (1,3), (2,4)
Figure 3: Example to illustrate the features of the algorithm. is on the left and D1 is on the right. The vertices in S are 1, 2,3, 3, 4 and the vertices in Dj are j 1,2 (labelling goes from top to bottom). The number next to j E S is its weight wy. The green edges are suggested by the advice.
3.1 Illustration of how our Algorithm uses Advice
As example, suppose R and C G. where we note that vI- VI-C = 1. Let D₁ consist of vertices = 1, and S consist of vertices j = 2, 3, 4 with weights wy = 1,1,2,4 respectively. The edges in the graph are 11, (1, 2). (1,3) and (2, (2,
We first demonstrate the case where the advice suggests edges (1.3) and (2,4), which would match weight Wys + w4 = 6 in the first stage. Intuitively, this advice is not so "extreme" in that it is greedily matching the highest-weight vertices in while it can, without assuming can later match them in the second stage. In this case our algorithm would follow the advice exactly (see Figure BD and have a consistency of Its robustness would at least G. with the worst case being when the second stage consists of single edge (3,4), which cannot be matched by our algorithm but increases the optimal offline matching from 6 to 7. Nonetheless, this suffices because @ is well above the targeted 7
robustness of R 5
We now demonstrate the case where the advice suggests edges (1,2) and (2,3) instead, perhaps predicting that an edge (3,4) will allow us to match offline vertex 4 later. This advice quite "extreme" in that it is skipping the highest- vertex in S in the first stage, based second- stage prediction which may not come to fruition. Following it exactly would give a weight of W2 + W3 3 in the first stage. which cannot be more than - 3-robus significantly lower than the target of g. Meanwhile, the maximally robust fractional matching based linear penalty functions (Feng et al. M: shown in Figure Say, which judiciously balances between all the offline vertices, is not -consisten Our algorithm returns the solution in Figure Bc. which follows the advice in that it completely proritizes vertex 2 over vertex 1, but deviates by significantly filling offline vertex 4 (which has the highest weight) as a failsafe (although not as much as the fully robust solution). This makes it both $ rrbbst and g --consistent, and our algorithm can be adjusted accordingly to be both R-robust and C-consistent for any values R, C satisfying -I- R
C
Based on these examples, we highlight two desirable features of our algorithm. First, it naturally responds to the "extremity" of the advice, by deviating more from the more extreme advice (in the 2nd case) order to maintain R-robustness. Second, from the definition of fu and fL in Algorithm together with Lemmal it can be seen that if R and the graph is unweighted, then our algorithm will always follow the advice exactly. This is because (1) = R < R = fu), which implies the algorithm will prioritize filling vertex suggested by the advice over one that is not, even if the former is completely filled and the latter is empty. Put another way, the algorithm automatically recognizes that any maximal matching will be at least rooust in an unweighted graph.
'The worst is if the second-stage graph consists of single edge (3, 2), in which case ALG(G, A) and OGT 7.
'If the second- stage graph consists of edges (3, 1) and (4,4), 4), then the fully robust solution gets value of
1 3 2 2 +
72 whereas ADVICE(G, A) = 8. Their ratio is G. which is less than -.-
Ii
8

---

4 Analysis of Robustness
We begin by analyzing the robustness of Algorithm which is its competitive ratio with respect to the optimal matching in hindsight. The theorem below gives characterization of the penalty functions fj that are sufficient to guarantee R-robustness, which is what led to our plots in Figure D
Theorem 1. Let R [0, } Suppose we run Algorithm where the functions I3 satisfy the following properties:
[ [0. [0, 1] increasing,
2. 1 1-R < [5(x) 1-
Then Algorithm 7 is R-robust.
The proof of Theorem D employs the online primal-dual technique. Based on the algorithm's deci- sions, we construct dual variables that are approximately feasible and lower bound the algorithm's objective value. (This is also the proof approach used by [1) but note that the way our dual variables are set is necessarily different in order to derive our results. ) The simplified structural property (Lemma allows in the primal-dual analysis. Roughly speaking. the upper bound on fy guarantees approximate dual feasibility for the first stage edges, while the lower bound on fy guarantces for the second stage edges. For space reasons, we have deferred the proof to the Full version of the paper.
characterize the envelope of functions that guarantee R-robustness
5 Analysis of Consistency
We now turn to analyzing the consistency of the algorithm. In the previous section, described an envelope of functions (see Figure 2 that were sufficient to guarantee Rrrobustness. For a desired robustness level we now maximize consistency by setting the penalty functions f, to their lower bound for vertices suggested by the advice, and to their upper bound for vertices not suggested by the advice. The theorem below shows that this choice of the penalty functions achieves the desired pobustness-consiitenn tradeoff. Later in Section g we show this tradeoff to be tight.
Let R E [0, 3). and let S1 be the set of offline vertices that are matched by the suggested matching the first-stage graph. Suppose we run Algorithm 7 with
Theorem 2.
f((x) min 1- for all SS St, and
f)()) max{1 [1- 1-8 03 for all j S1.
Then Algorithm
is (2v1 R - -consisttt.
Our high-level strategy for bounding consistency (which recall is ADVICE(G.A) is to carefully split the value of ALG(G, A), attributing separate contribution to each first-stage vertex E Dr. We then split the value of ADVICE(G, AA) in a similar way. This decomposes the numerator and denominator as sums over i E D,, which means it suffices to lower-bound the ratio of the terms corresponding to each individual E D1. For concreteness, consider some fixed E D1 and let a E be the offline vertex that the advice suggests matching to. The bad case for consistency is if T. is low, because this means the algorithm deviated from the advice. However, because the potential functions are chosen to incentivize matching to a, the only way Ha can be low is if i is substantially matched to other vertices with higher weight than Wa- implying the algorithm must have collected lot of value from the vertices that intuition precise, is deferred to the full version of the paper for space reasons.
ALG(G.A)
recommended by the advice. The full proof, which makes this
6 Tightness of the Hobustness-Consiiteen Tradeoff
Theorems and together show that Algorithm I is able to be both R-robust and C-consistent, for any (R, C*) with R [0, 인 and vI R + VI- 1. We now show this tradeoff to be tight.

---

0/2
2
2
Figure 4: Illustration of the hardness instance. on the left and D is on the right. The first arrival neighbors both vertices of S. The second arrival neighbors exactly vertex of S, but could be either vertex. The advice to match the green edge (1, 1).
The hardness instance. The hardness instance illustrated Figure it a graph where D has two vertices = 1,2 that arrive one in each stage. S has two vertices j = 1,2 with weights (for some w E [0, 1] that we will set later) and ut2 = The first-stage graph consists of both edges 1) and 2), and the advice suggests matching along the edge (1, 1). which is "extreme" advice in that offline vertex has the lower weight one edge (which can be either (2, 1) or (2, 2)). Since the algorithm does not know which edge will arrive in the second stage, it must hedge against both possibilities when making its first-stage decision.
Theorem 3. Let w -ー in the instance described above Then any algorithm that R-robust is at most C-consistent where C' = =2v1
R).
Proof of Theorem Let x == and 1 - x' = T12, that the algorithm's 's first-stage decision is entirely characteried by the value of There are two cases.
Edge (2 arrives in the second stage. Then ALG = w + 1 - and ADVICE W.
Edge (2, 2) arrives in the second stage. Then ALG = wxr + and ADVICE + w.
(Note that regardless of which edge arrives the second stage, OPT is always equal to 1 + w.) For the algorithm be R-robust in Case must have
W + 1
- x (1- + w))
On the other hand, for the algorithm to be C-consistent in Case 2, must have
WI +
C - c((+w)-
1
Since the algorithm does not know which of the two will happen in the second stage, it must choose an x that satisfies both of the inequalities above. For a desired robustness R and consistency C, this is only possible if
C(1 + w) - < (1 1 RR
which when rearranged becomes
C R) + w
Substituting w VI-R above gives C 2/1 R (1 R), desired.
'This choice of w obtained by minimizing (1 Ryw
10

---

References
[1] Yiding Feng, Rad Niazadeh, and Amin Saberi. Two-stage stochastic matching with application to ride hailing. In Proceedings of the 2021 ACM-SIAM Symposium Discrete Algorithms (SODA), pages 2862-2877. SIAM, 2021.
[2] Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Kim S. Larsen, and Jesper W. Mikkelsen. Online algorithms with advice: A survey. ACM Comput. Surv., 50(2), apr 2017. ISSN 0360- 1144/30564/36
0300. doi: 10.1 145/3056461.
[3] Richard M Karp. Umesh Vazirani, and Vijay V Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pages 352-358, 1990.
[4] Aranyak Mchta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized online matching. Journal of the ACM (JACM), 54(5):22-es 2007.
[5] Mohammad Mahdian, Hamid Nazerzadeh, and Amin Saberi. Online optimization with uncer- tain information. ACM Transactions on Algorithms (TALG), 8(1):1-29, 2012.
[6] Thomas Lavastida, Benjamin Moseley, Ravi, and Chenyang Xu. Learnable and instance- robust predictions for online matching, flows and load balancing. In 29th Annual European Symposium on Algorithms (ESA 2021). Schloss Dagstubl-Lecibniz-Zeiinn 2021.
für Informatik,
[7] Zhiyi Huang and Thorben Tröbst. Online matching. Online and Baaching-Based Market Design, Federico Echenique, Nicole Immorlica and Vijay V. Vazirani, editors, appear in 2022.
[8] Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. arXiv preprint arXiv:2006.091 2020.
[9] Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online matching problems with machine learned advice. Advances in Neural Information Processing Systems, 33:7933-79444 2020.
[10] Ravi Kumar, Manish Purohit, Aaron Schild, Zoya Svitkina, and Erik Vee. Semi-online bipartite matching. 10th Innovations in Theoretical Computer Science, 2019.
[11] Dawsen Hwang, Patrick Jaillet, and Vahideh Manshadi. Online resource allocation under par- tially predictable demand. Operations Research, 69(3):895 915, 2021.
[12] Nikhil R Devanur and Thomas P Hayes. The adwords problem: online keyword matching with budgeted bidders under random permutations. In Proceedings of the 10th ACM conference on Electronic commerce, pages 71-78, 2009.
[13] Vahab S Mirrokni, Shayan Oveis Gharan, and Morteza Zadimoghaddam. Simultaneous ap- proximations for adversarial and stochastic online budgeted allocation. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 1690-1701. SIAM, 2012.
[14] Haim Kaplan, David Naori, and Danny Raz. Online weighted matching with a sample. In Pro- ceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1247-1272. SIAM, 2022.
[15] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predic- tions. Advances in Neural Information Processing Systems, 31, 2018.
[16] Étienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning augmented algorithms. Advances in Neural Information Processing Systems, 33:20083-20094, 2020.
[17] Alexander Wei and Fred Zhang. Optimal robustness-consiisenng trade-offs for learning- augmented online algorithms. Advances Neural Information Processing Systems, 33:8042- 8053, 2020.

---

[18] Bo Sun, Russell Lee, Mohammad Hajiesmaili, Adam Wierman, and Danny Tsang, Pareto- optimal Saaming--uggeett algorithms for online conversion problems. Advances Neural Information Processing Systems, 34, 2021.
[19] Santiago Balseiro, Christian Kroer, and Rachitesh Kumar. Single-leg revenue management with advice. arXiv preprint arXiv:2202. 10939, 2022.
[20] Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM (JACM), 68(4):1-25, 2021.
[21] Siddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh, and Billy Jin. Online nash social welfare maximization with predictions. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022. SIAM, 2022.
[22] John R Birge and Francois Louveaux. Introduction to stochastic programming. Science & Business Media, 2011.
Springer
[23] Dimitris Bertsimas, David Brown, and Constantine Caramanis. Theory and applications of robust optimization. SIAM review, 53(3):464-501, 2011.
[24] Yiding Feng and Rad Niazadeh. Batching and optimal multi-stage bipartite allocations. Chicago Booth Research Paper, (20-29), 2020.
[25] Omar El Housni, Vineet Goyal, Oussama Hanguir, and Clifford Stein. Matching drivers to riders: A two-stage robust approach. arXiv preprint arXiv:2011.03662 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yss]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs, if not in the main body, are in the supplementary materials.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report enror bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (c.g., code, data, models) curating/relcasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'te re using/curating? [N/A]
12

---

(c) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "aenEvMeRxid", "reviewer": "Reviewer_CvJo", "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.\n\nSimilar 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).\n\nThe 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$.", "questions": "none", "limitations": "n/a", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n-First characterization of Pareto frontier for online bipartite matching.\n-Tight guarantees.\n\nWeaknesses:\n- Lack of experiments on actual online bipartite matching datasets.", "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": "GLCHmG30mVD", "reviewer": "Reviewer_Lbyq", "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.\n", "questions": "None", "limitations": "None", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nThe 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.  \n\nI appreciate the discussion in the introduction on alternate definitions of consistency and the notion of prediction error. \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": "7kKkoyxTYC3", "reviewer": "Reviewer_iKQU", "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.\n\nThe 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). \n\nThere 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.", "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.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The matching problem considered is quite interesting.\n- 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\n\nWeaknesses:\n\n- I found it quite hard to follow the paper. The main reasons I could identify for this are the following:\n* 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). \n* 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. \n\n- I find that predicting the whole matching for D_1 at once can be a bit unnatural. \n\n- 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.\n\n- 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.\n\n- No experimental evaluation is contained.", "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": "2MczSQdymyM", "reviewer": "Reviewer_d2AC", "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. ", "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. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1.\tThe result shows the clean and optimal tradeoff relation between consistency and robustness. This is a very nice theoretical result.\n2.\tIt 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.\n\nWeaknesses:\n\n1.\tThe 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.\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": {}}]

Author rebuttal:

Decision: Accept