Online Matching in Sparse Random Graphs: Non-Asymptotic Performances of Greedy Algorithm
Authors: Nathan Noiry
Vianney Perchet
Flore Sentenac
Venue: NeurIPS 2021 Poster (2021)
Keywords: Online Matching
Random Graphs
Stochastic Approximation
Differential Equation Method

Abstract: Motivated by sequential budgeted allocation problems, we investigate  online matching problems where connections between vertices are not i.i.d., but they have fixed degree distributions -- the so-called configuration model. We estimate the competitive ratio of the simplest algorithm, GREEDY, by approximating some relevant stochastic discrete processes by their continuous counterparts, that are solutions of an explicit system of partial differential equations. This technique gives precise bounds on the estimation  errors,  with arbitrarily high probability as the problem size increases. In particular, it allows the formal comparison between different configuration models. We also prove that, quite surprisingly,  GREEDY can have  better performance guarantees than RANKING, another celebrated algorithm for online matching that usually outperforms the former.

Online Matching in Sparse Random Graphs: Non-Asymptotic Performances of Greedy Algorithm
Nathan Noiry
Flore Sentenac
Télécom Paris, Palaiseau, France noirynathan@gmai.ccm com
CREST, ENSAE Paris, Palaiseau, France flore. wwrrosssnttnnccensse...m
Vianney Perchet
CREST, ENSAE Paris, Palaiscau, France
CRITEO AI Lab, Paris, France vianney www.peeeetoooooaleppeeeee
Abstract
Motivated by sequential budgeted allocation problems, we investigate online match- ing problems where connections between vertices are not i..dd,, but they have fixed degree distributions the so-called configuration model. We estimate the compet- itive ratio of the simplest algorithm, GREEDY, by approximating some relevant stochastic discrete processes by their continuous counterparts, which solutions an explicit system of partial differential equations. This technique gives precise bounds the estimation errors, with arbitrarily high probability the problem size increases. In particular, it allows the formal comparison between different configuration models. We also prove that, quite surprisingly, GREEDYcan have better performance guarantees than RANKING, another celebrated algorithm for online matching that usually outperforms the former.
Introduction
Finding matchings in bipartite graphs (2/VV,)) where & C U x V is set of edges, is long-standing problem with different motivations and approaches Godsil 1981 Zdeborová and Mézard 2006 Lovász and Plummer 2009 Bordenave et al.] 2013]] If uf is seen as set of resources and > as demands, the objective is to allocate as many resources to demands (an allocation or matching between u and is admissible if (u, v) E) with the constraint that resource is allocated only one demand and vice-versa.
Motivated particularly by practical applications to Internet advertising, the online variant of this problem is receiving increasing attention (we refer the excellent survey [Mehta] 2012] for more applications, specific settings, results and techniques). In this case, the set of vertices 27 is present at the beginning and the graph unveils sequentially: vertices the other, along with the edges they belong to. An online algorithm must decide, right after observing os and its associated set edges & := {(u, v&)) E {) to match it to some other vertex u E Ut, at the conditions that (u, v&) E ε and u E l/ has not been matched yet. The performance of an online algorithm is evaluated by its competitive ratio, which is the ratio between the size of the matching has created and the highest possible matching in hindsight [eldmann al. 2009
are observed sequentially, one after
This theoretical setting is particularly well suited for online advertising: the set of campaigns/ads
that an advertiser can run and users U1, ......, By arrive sequentially [Mehta 2012 Manshadi et al. 2012 Some of them are eligible for a large subset of campaigns, others are not (usually based
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

on their attributes/featurrs, such as the geographic localization, the browsing history. or any other relevant information). The objective of an advertiser (in this over-simplified model) is maximize the number of displayed ads. In practice, campaigns/ads are not displayed only once but have a maximal budget of impressions (say, specific ad can be displayed only 10.000 times each day). A possible trick consists of duplicating the vertices of U as many times as the budget. However, this results in strong and undesirable correlations between vertices. It is, therefore, more appropriate to consider a bipartite graph with capacities and admissible matchings as subsets of edges such that each vertex belongs to several different edges, but not more than their associated capacities w E N (a vertex 8 E V is matched once while E L1 can be matched Wa times).
This online matching problem with capacities has been quite extensively studied. is known that GREEDY, which matches all incoming vertices to any available neighbor has a competitive ratio of 1/2 in the worst case, albeit it achieves 1/e as soon as the incoming vertices arrive in Random Order (Goel and Mehta 2008b). The worst-case optimal algorithm is the celebrated RANKING, which achieves - 1/e on any instance [Karp et al., 1990 Devanur al. 2013 Birnbaum and Mathieu
2008 and also has better guarantees in the Random Order setting Mahdian and Yan 2011
Beyond the adversarial setting, the following stochastic setting has been considered: there exist
finite set of L "base" vertices e(1), ................................ (()) associated base edge-sets g(1) g()....," g(1), When a vertex vig arrives, its type 02 E (1,...,A, I.} is drawn iid from some distribution (either known beforehand or not) and then its edge set is set as & = E(+,). In the context where the distribution is known, algorithms with much better competitive ratios than GREEDY RANKING were designed [Manshadi et al. 2012 Jaillet and Lu 2014 Brubach et al. 2019, specifically with competitive ratio of 2/e- when the expected number of arrival of each type are integral and 0.706 without
this assumption. Notably, those competitive ratios still hold with Poisson arrival rates rather than a fixed number of arrivals.
On a side note, a vast line of work considers online matching in weighted graphs Devanur et al. 2012, Goel and Mehtal 2008a Mehta 2012). which is outside the scope of this paper. However, it is still worth noting that the unweighted graph is a weighted graph with all weights equal.
This model of the stochastic setting is quite interesting but rather strong: it lacks flexibility and cannot be used to represent some challenging instances ( ffor example when the degrees of each vertex U increase linearly with the number of vertices in V, or when the set 2/ of campaigns must be fixed so that the model is well specified, etc...). Another tentative is to consider Erdös- Rényi graphs assuming that each possible edge is present in 21 x V with some fixed probability and independently of the other edges (see [Mastin and Jaillet 2013). ). The most interesting and challenging setting corresponds to the so-called sparse regime where each vertex of t/ has an expected degree independent of the size of V. which amounts to take a probability of connection equal to c/n. Interestingly enough, even the analysis of the simplest GREEDY algorithm is quite challenging and already insightful in those models [Brodiin et al. 2018 Arnosti 2019 Dyer et al., 1993 Mastin and Jaillet 2013). Unfortunately. although this Erdōs- Rényi model is compatible with growing sets 21 and V. also turns out to be quite restrictive. The main reason is that the approximate Poisson degree distribution of the vertices has light-tail and does not allow for the appearance of the so-called scale-free property satisfied by many real-world networks [Barabási et al. 2000 Van Der Hofstad 2016).
We, therefore, consider more appropriate random graphs generation process called configuration model, introduced by [Bender and Canficld| 1978) and [Bollobas 1980]. The optimal matching of this model has been computed in [Bordenave et al. 2013 The configuration model is particularly well suited to handle different situations such as the following one. Assume that campaigns can either be "intensive" (with many eligible users) "selective/light" (few eligible users), with an empirical proportion of, say, 20%/80%. Then whether an advertiser handles 100 campaigns at the same time or 10.000, it will always have roughly this proportion of intensive vs. light campaigns. Similarly, some users are more valuable than others, and are thus eligible for more campaigns than the others; the proportion of each type being independent of the total population size. The configuration model accommodates these observations by basically drawing iid degrees for vertices lf and V (accordingly to some different unknown distributions for U/ and V) and then by finding a graph such that those degrees distribution are satisfied (up to negligible errors); as a consequence, the graphs generated are sparse, in the sense that the number of edges grows linearly with the number of vertices.
Additionally, the configuration model is a well-suited random graph model which mimics a number of properties of real- world complex networks, while being analytically tractable. For instance, choosing
2

---

power-law distributions for the degrees allows to obtain the so-called scale-free property (often
observed in practice, as highlighted for the web by Faloutsos al. [1999]]. ) The configuration
model also displays the so called "small-world phenomenon" (observed for instance in the graph of Facebook by Backstrom al. 2012 as its diameter of logarithmic order.
Main contribution
We investigate the performances (in terms of expected competitive ratio) of the GREEDY matching algorithm in configuration models and we provide explicit quantitative results using stochastic approximation techniques [Wormald] [995]; prove that the increasing size of the random matching created arbitrarily close to the solution of some explicit ODE, Solving the latter then gives in turn the solution to the original problem.
The remaining of the paper is organized as follows. Section describes precisely the problem and Theorem iis our first main result: it describes the performances of GREEDY in the capacity-less problem. The proof of Theorem is delayed to Appendix [ but the main ideas and intuitions are provided in Section
S
The online matching with capacities problem is treated in Appendix A
2 Online Matching Problems; Models and main result
Consider a bipartite graph with capacities G = (4, V.E.w) where u = (I...., and V are two finite set of vertices, & C {[u, v), u E U, u E V] is the set of edges and w: 1 N, is capacity function. A matching M G is a subset of edges
7} (1....,7h
& such that any vertex v E V is the endpoint of at most one edge E M and any vertex u E U is the endpoint of most wh, edges M. We will denote by M the of matchings on G: the optimal matching M E M is the one (or any one) with the highest cardinality, denoted by [M*
The batched matching problem consists in finding any optimal matching M given graph with capacities G; the online variant might be a bit more challenging, as the matching is constructed sequentially. Formally, the set of vertices U and their capacities w are known from the start, and vertices v E V arrive sequentially (with the edges they helong to) and Mo = 0. At stage &. E IN assuming matching M,- has been constructed
decision maker observes new vertex 14 and its associated set of edges {w, v)); u E E). If possible, one of these edges (u,, v4) is added to M₁-1, with the constraint that M,,- M,-1 U {we, 3 is still matching. The objective is maximize the size of the constructed matching Mr. The classical way to evaluate the performances of an algorithm the competitive ratio, defined as MMl//|**| [0, 1] (the higher the better).
2.1 Structured online matching via Configuration Model
As mentioned before, the online matching problem can be quite difficult without additional structure. We will therefore assume that the vertex degrees in 21 and V have (at least asymptotically in N and T) some given subGaussiar distributions Tu and Ty, of respective expectation Jeu and foy and respective proxy-variance o and o.. Those numbers are related in the sense that we assume that T = Hi N N. Given those degree distributions, the graphs we consider are random draws by
from bipartite configuration model described below; for the sake of clarity, we first consider the capacity-less case (when Wa = 1 for all u E U).
Given Tu and my and N,T > 1, let d'. ...., d E lid. Tu and d' .....,, df E IN Lid. my be independent random variables; intuitively, those numbers are respectively the number of half-edges attached to vertex in 21 and V. Consider also two extra random variables
N
T
T
Ny+1 max
M
00 and db+1 = max
Σ j=1
d
d/ 0}
1=1
1=1
Although the order of arrival is irrelevant to the models studied, it could have an impact on other models.
2 X is subGaussian with proxy-variance o² if for any s R, [[exp(sxX)] S exp (d2.2) Actually, we only need that my and my have some finite moment of order 7y > In the general case, consider 1 [N pu /vv.. The proof is identical, up negligible 1/N error term
3

---

so that equality between total degrees holds, i.c., N+ d' = -+ dz. Finally, random (capacity-
less) bipartite graph denoted by CM(d d ) is constructed with uniform pairing of half-edges of u U (N + 1} with half-edges of V {T 1] and removing vertices T + and N + +1 and their associated edges. These two artificially added vertices are just here to define pairing between half-edges. Notice that, by the law of large numbers and since T = (Pu/vv)N, di r+1 o(N) and d N++1 = o(N) almost surely
The bipartite configuration model CM(d4, d is then the random graph obtained by uniform matching between the half-edges of and the half-edges of V, where the random sequences d' ) and d (d]); ) are defined above.
2.2 Competitive ratio of GREEDY algorithm. Main result
The first question to investigate in this structured setting is the computation of the (expected) competitive ratio of the simple algorithm GREEDY. It constructs a matching by sequentially adding any admissible edge uniformly at random. Describing it and stating our results require the following additional notations: for any (resp. V): the generating series of TH and mTy are denoted by du and Φy and are defined
(u, v) E E, u(e) (resp. v(e) = v) is the extremity of e in U
(u(s)
Σ (k)s
and
Σ (k)ss*
220
Our first main theorem, stated below, identifies the asymptotic size of the matching generated by GREEDY the bipartite configuration model we have just defined. As the batched problem (i.e., computing the size of the optimal matching M²) well understood [Bordenave et al. 2013), this quantity is sufficient derive competitive ratios. Again, for the sake of presentation, first assume that all capacities are fixed, equal to one; the general case is presented Appendix
Theorem 1. (Performances of GREEDY in the capacity-less case)
Given N 2 1 and T th N. let Mr be the matching built by GREEDY on CM(d" dd) then the by following convergence probability holds:
[Mr] P 1-
N
N N
where G is the unique solution of the following ordinary differential equation:
G'(s) 1- dv (I
Mu 2u (1- G()(
1 2h
G(()
HV 6u(11 - G(s)) 1u
Moreover, for any E [0, 1), if Ms)) is the matching obtained by GREEDY after seeing a proportion of vertices of V. then
Mr(())
P,
dru -
(2)
N
Convergence rates are explicit; with probability exponentially large, at least 1 ÇN exp(-ENe/2)
Mr(()]
N (1-ou(1- SkN KN
sup sE[O.1]
where f. k. depend only on the (first two) moments of both πV and mu, and c is some universal constant (set arbitrarily as 1/20 in the proof).
Theorem generalizes to the case with capacities, see Sections and A.2 of Theorem are postponed to Appendix D but the main ideas given Section
The details of the proof
2.3 Examples, Instantiations and Corollaries
We provide in this section some interesting examples and corollaries that illustrate the powerfulness of Theorem and how it can be used to compare different situations.
And even ((VN) with probability exponentially large in N as both distributions are sub aab-Gassiian. So the effects of those additional vertices can be neglected.

---

2.3.1 d-regular graphs
The first typical example of random graphs are d-regular" ", for some d E N, i.e., graphs such that each vertex has an exact degree of d (to avoid trivial examples, we obviously assume d 2 2).
It is non-trivial to sample a d-regular graph at random, yet it is easy to generate random graphs Gy with the configuration model described above, with the specific choices of my = = ōd, the Dirac mass at d. The downside is that G2 is not exactly a d-regular bipartite random graph (as some vertices might be connected more than once, i... there might exist parallel edges). However, conditioned to be simple, i.c, without multiple edges and loops, it has the law of a uniform d-regular bipartite random graph. Moreover, the probability of being simple is bounded away from Van Der Hofstad 2016); as a consequence, any property holding with probability tending to 1 for GN. holds with probability tending to for uniform d-regular bipartite random graphs. Finally, we also mention that Hall's Theorem [Frizze and Karonski 2016 implies that Gy admits a perfect matching. so that |M* = -N.
Instantiating Equation ① to d-regular graphs yields that the competitive ratio of GREEDY converges, with probability 1, to (1 G(1)) where G is the solution of the following ODE (1 G(s))
1 (1 ((5))--1) G' (s) d'
(3)
hence the competitive ratio of GREEDY is 1 (but again, d = 1-regular graphs are trivial). More interestingly, if d = 2, the ODE has a closed form solution: G(s) exp($) 1, that the competitive ratio of GREEDY converges to 4ve- (e + 3) = 0.877 > 1 - : = 0.632, where the latter a standard bound of the competitive ratio of GREEDY (for general, non-regular graphs) MMetta 2012
As expected, had we taken d 1, then G(s)
Solving Equation
In the general case d 2 3, even if Equation 3 does not have a closed form solution, it is still possible to provide some insights. Notice first that the polynomial P(X)
1- (1 - (1 - x)d-1jd admits n == d(d - 1) roots, among which there is with multiplicity d 1. If X is another root, then
(1 (1-(1-) -1-11
+ 1 1 (1 -1- (1-x)==11 = tkr k 1....,d-- 1.
=e-
Therefore,
- = - e spx
which admits d 1 distinct solutions for each 1o = 1..... d 1. The resulting == (d - 1)2 distinct complex, denoted ....... Ln, are the roots of P(X)/(1 x)d-1, so the ODE reduces to:
y((
Sisisn v(1 2i d'
Since the following trivially holds:
Σ
Σ
a
Insisn (X
xz))
1Sisn I 1 - rzy) X 3j
X - Zi
15 in
it is possible to integrate Equation in Σ Eisisn a; log(y(t) - xz) = a + c to finally get
II (u(t) 1z) = Cexpl" 8 () Isisn
and since y(0) must hold that C IIisisn (-r;;)a, As consequence, v1) solves:
II (v(1) 2z) ee//d 1Siin
II Isisa
(
Unfortunately, even for d = 3, the solution somehow simplifies but has no closed form; on the other hand, numerical computations indicate that the competitive ratio of GREEDY converges to 0.89 when and N tends to infinity. We provide in Figure 3 the numerical solutions of the ODE for d-regular graphs (actually, we draw the functions 1 dv various values of d; the end-point obtained at s = indicates the relative performance of GREEDY. As expected, those functions are point-wise increasing with d (as the problem becomes simpler and simpler for GREEDY when d 2 2).
G(s)) that are more relevant) for
5

---

E34
0.0
Figure I: Numerical computations (on Scilab, results are almost instantancous) of GREEDY perfor- mances for d (blue), d (red), d (green), d = 6 (black) and d = 10 (magenta), On the left, global solution, on the right, zoom-in on the end points with final values.
2.3.2 The Erdös-Rényí case.
In Bardós-Rényi graph, there is an edge between two vertices E U and e E V with some probability p N independently from each others. As N goes to infinity, the number of edges vertex follows (approximately) a Poisson law of parameter >> 1.
As consequence, consider the configuration model where my and my Poisson laws of parameter c, which yields μ (s) c(-1)) In this case, Equation becomes:
cG' (3) cG(s)
cGGJ 1.
The solutions are given by:
G(s) log log(ck-cs +1)))
yielding
Φx (1 - (x()) = log (6 -co (c==ce+1)
The initial condition ou - G(0)) = (1) = 1 gives e = cº - 1, from which we deduce that the
number of matches of GREEDY is asymptotically proportional to
@u = log c-
which recovers, sanity check, some existing results Mastin and Jaillet 2013
2.3.3 The comparison of different configuration models
Using Gronwall's Lemma, possible to show Theorem can be used to compare different configuration models, as in the following Corollary.
Corollary 1. Consider two configuration models CM, (dl' dy) and CM, a' s.s. af and di are both drawn i..dd. from TV, dy drawn i.i.d. from bo and d is drawn i.idd. from TV. with En ZT)(() = En x (z). If (s)(s) 2 (s) for any s E (0, 1), then by denoting respectively " and 722 the asymptotic proportion of vertices matched by GREEDY in CM, aV) and CMz(dl dy), holds that necessarily 72 2/
For instance, let us assume that the degree distribution the offline side is fixed. Then the matching size obtained by GREEDY is asymptotically larger if vertices on the online side all have exactly the same degree d rather than if those degrees are drawn from Poisson distribution with expectation d.
similar result (with a different criterion) holds with fixed degree distribution on the online side and differing one the offline side.

---

2.4 GREEDY can outperform RANKING! !
We recall that the RANKING algorithm, which is the worse case optimal, chooses at random ranking over U and uses it to break ties (i.e., if two vertices and u' can be matched to vk. then it is the one with the smallest rank that is matched by RANKING). Quite surprisingly, we get that in the configuration model RANKING can have worse competitive ratio than GREEDY, which advocates again for its thorough study.
Proposition 1. Let "/ and " be the assymptotic performances of RANKING and GREEDY on the 2-regular graph. The following holds:
G YRR.
In other words. GREEDY outperforms RANKING in the 2-regular graph.
We conjecture that the above result actually holds for any d 2 2. and more generally for wide class of distributions my and my (finding a general criterion would be very interesting). The proof of Proposition is provided in Appendix G The main idea is that in the 2-regular graph, RANKING is biased towards selecting as matches vertices with two remaining half- rather than just one. Indeed, vertices with only one remaining half-edge were not selected previously and thus have higher rank. The vertices with only one remaining half-edge will not get matched in the subsequent iterations, so not picking them matches is suboptimal. On the other hand, GREEDY picks any match uniformly at random and does not exhibit such bias.
4-regular graph
10-regular graph
20-regular graph
2.00
2 reqular graph
100
20000
30000
aumber OF (nstcPied Vertices
RANKING GREEDY
1530
60:0
800
1981
030
550
3600 itoration
30008
8500
9000
20:00
30002
8030
8000
5000
2230
1000
8000
5000
9030
1002
Rterttio
Reretion
(teretion
Figure Experimental performances of GREEDY vs. RANKING on d-regular graphs
3 Ideas of proof of Theorem 1
The main idea behind the proof of Theorem T (postponed to Section D is to show that the random deterministic evolution of the matching size generated by GREEDY is closely related to the solution of some ODE (this is sometimes called "the differential equation method" [Wormald 1995) or "stochastic approximations" [Robbins and Monro 1951)). Computing the solution of the ODE is easier- - if not explicitly, at least numerically in intricate cases than estimating the performances of GREEDY by Monte-Carlo simulations and it provides qualitative, as well quantitative, properties.
Tracking the matching size is non-trivial because the vertices (in 24 and V) have different degrees, hence some of them more likely to be matched than others. However, in the configuration model, each vertex has the same distribution of degrees before the sequences d and d are fixed. As a consequence, the proof relies the three following techniques
1. The graph is built sequentially, along with the matching and not beforehand (fixing the "randomness" at the beginning would be very difficult to handle in the analysis). Thankfully, this does not change the law of the graph generated (this obviously crucial).
2. We are not only going track the size of the matching built as we need to handle different probabilities of matching (and pairing the graph) for each vertex. As consequence, we are going to track the numbers of non-matched vertices which have still half-edges be paired and the number of already matched vertices that have j half-edges remaining. This will give one different ODE per value of jf
Since सy and my are sub-Gaussian, we will prove that with arbitrarily high probability exponential in N -, there are only polynomial number of such equations
7

---

3. All those differential equations are then "aggregated" to build the final ODE satisfied by the matching size. Interestingly, this aggregated ODE has a simple form, while the full system is on the other hand quite intricate.
In the following sub-sections, we separate the proofs in the different building blocks to provide intuitions; the proof of technical lemmas deferred to the appendix.
3.1 Building the graph together with the matching
The first step in the analysis is to notice that the bipartite configuration model can be constructed by sequentially pairing the half-edges coming from V. The matching generated by GREEDY is then constructed simultancously with the graph. More preciscly, given two sequence: of non-
5
negative integers d = (..,... & ) and d U {dl+1) (d ..... d'. dlf+1), we introduce in the following a generating algorithm that simultaneously build the associated bipartite configuration model CM(d4 a together with GREEDY. Recall that the bipartite configuration model is obtained through uniform matching between the half-edges of U and the half-edges of V. To avoid confusion, we will call a marked matching a pairing of two half-edges that corresponds to an edge that will belong to the constructed matching M. This construction pseudo-code is detailed in Algorithm I
Algorithm 1: GREEDY MATCHING CONHIUURATION MODEL WITHOUT CAPACITIES
Input: d (14, d') and d (dl dy) Initialization. Mg t- 0, E + and Hy < half-edges uf for t 1....... T do
Order uniformly at random the edges emanating from ug: ,i....,ef
for i = I....,k; kg do
Choose uniformly an half- ef in H
E + E (u(et), vp}
// Create an edge between of and of // Remove the half-edge
Hu <- -HR \ {(2()
if o2 and u(eft) unmatched then
M, + M (u(e)))
// Ut is matched
end
end end
CM(d'' dd') + (4, (...V)).
Output: Bipartite configuration model CM(d d') and matching My on it.
Since each pairing of each half-edge is done uniformly at random, the graph obtained at the end of the algorithm has indeed the law bipartite configuration model. Moreover, it easy to see that M corresponds to the matching constructed by GREEDY MATCHING CM(d', (P)).
3.2 Differential Equation Method Stochastic Approximation
As mentioned above, several quantities are going to be tracked through time: for all k E .O....,T) and all 2 define:
(((k)) the number of vertices ll that are not yet matched the end of step k and whose remaining degree is i, meaning that dy - of their initial half-edges have been paired.
We will refer them to free vertices.
(k) as the number of vertices u E li already matched at the end of step and whose remaining degree is i. We will refer them as marked vertices.
Notice that for all 0 < l < T, the sum (((k) + (k) corresponds to the total number of vertices of l with remaining degree the end of step k. We also define
F(k) : Ee (k)) is the number of available half-edges attached to free vertices the end of step k.
WWithout loss of generality, assume that the additional extra vertex is always the V side.
8

---

M( E (k) is the number of available half-edges attached to marked vertices at the end of step k.
We are going to study the evolution of these quantities along with the one of GREEDY. major
ingredient of the proof is to show that ()(k) and M,(k) closely follow the solutions of some ODE. This the so-called differential equation method [Wormald, [995]. stated in Appendix C For
instance, it can easily seen that F(k) + M(k) closely follows the function + pu - tjy on (O, pu pu/py) in the following sense.
Lemma 1. For every > O, and for all 0 S k T,
F(A) M(k)
k xn))) N
(per
Se.
N
with probability at least 1 1 exp (
Ne² 20
+ exp
Te' 20
We now turn to each individual quantity F; (resp. M2). We can prove a similar result, yet the limit function is not explicit (unlike for the matching size in Theorem [ statement). The following Lemma 2 states that the discrete sequences (free and marked) half-edges are closely related to the solutions of some system of differential equations.
Before stating it, we first introduce, for any sequence of non-negative numbers (#z)e2o and (ye) such that 0 < Ee flare VE) < oo, every i 2 0, the following mappings
Eizo
2 (20, T1,..., 11.1..... yo..)..... iipa, + (i 1)μyл4+1 - /2 Exzo
( 1)
(5)
Σ120 l(xe + y1)
and
Eczo Eye (r 21,.... yo. 91 .1....) ipves + (i + 1)vee+11 + Erzo (aeetee)
(i 1)
Er ((xt +1/1)
where h is the following function, well-defined on [0, 1].
h(s) 1-pv(s)
Lemma 2. With probability 1- 1-ÇN exp(- there are at most N quantities F; and Mc and
for all 0 I k < T and all i 1 0
(k)
M,(k)
( kk
fo S
SKNN-
and
mi
S
-2
N
N
N
where ç. depend only on the (first two) moments of πy and Tu and c 1/20.
The continuous mappings Js and m, are solutions of the system of disferential equations on [0, /u/ pv)
df,
= P. f1..... Ma, m......:
dma
= (f fi.... ma .).....
(6)
(: = (i)))
(0) = O.
This system well defined stated by the following Lemma
Lemma 3. The system 4 has unique solution which is well-defined on [0, pu/pv). More precisely, denoting by f and m the generating series of the sequences (fi)s20 and (m4)520-
f(t, Σ f(())s
and
m(t,s) Σ
my (t)s)s
120
holds that:
[u (1 - -wr) ,8) (s = ou ((s uuvt + F(t)), f
(7)
my

---

and
S. ('()) ((s 1)e mun + F())) du.
Pb Pu (1 (1-e (vt) --s)
where F is a solution of the following ODE
1 Ky - F(t))
Hi
F((1) = entt
1 - Φv (1
mu S/u (u(1-F(t)) F(t))
3.3 Aggregating solutions to compute GREEDY performances
To get Theorem | notice that the number of vertices matched by GREEDY is N minus the number of
free vertices remaining at the end, which is approximately equal to N y 1) by definition of f and This corresponds to = +oo in Equation
because of Lemma 2
7 thus the performance of GREEDY
is, with arbitrarily high probability, arbitrarily close to
N(1 (r - F(+x)))
The statement of Theorem just follows from a simple final change of variable.
Conclusion
We studied theoretical performances of GREEDY algorithm matching problems with different underlying structures. Those precise results are quite interesting and raise many questions, especially since GREEDY actually outperforms RANKING in many different situations (in theory for 2-regular graphs, but empirical evidence indicates that this happens more generically).
Our approach has also successfully been used to unveil some questions the comparison between different possible models. But more general questions are still open; for instance, assuming that the expected degree is fixed, which situation is the more favorable to GREEDY and online algorithm: small or high variance, or more generally this distribution zy or an alternative one 7/ ? The obvious technique would be to compare the solution of the different associated ODE's. Similarly, the questions of stability/robuutness the solution to variation in the distribution fy and Ty are quite challenging and left for future work.
We believe online matching will become an important problem for the machine learning community in the future. Each year, the complexity of the underlying graphs increases and we are considering adding features to the model in future work (such as random variables on the edges, modeling the interest for consumer for given product), or connection modeled via some Kernel between vertices features (say, if users and products/campaigns are embedded in the same space). In this context, machine learning tools will certainly be needed to tackle the problem.
Acknowledgments and Disclosure of Funding
V. Perchet acknowledges support from the ANR under grant number #ANR-19-CE23-0022 as well as the support grant part of the Investissement d' avenir project, reference LabEx Ecodec/ANR- 11-LABX-0047 Nathan Noiry also acknowledges support from the Telecom Paris DSAIDIS chair and from the ANR ProGraM (ANR-19 19- CE40-0025). Flore Sentenac is supported by IP PARIS' PhD Funding.
References
Nick Arnosti. Greedy matching in bipartite random graphs. working paper, 2019.
Lars Backstrom, Paolo Boldi, Marco Rosa, Johan Ugander, and Sebastiano Vigna. Four degrees of separation, 2012.
Albert-Lászíó Barabási, Réka Albert, and Hawoong Jeong. Scale-free characteristics of random net- works: the topology the world-wide web. Physica A: statistical mechanics and its applications, 281(1-4):69-77220) 2000.
10

---

Edward A. Bender and E. Rodney Canfield. The asymptotic number of labeled graphs with given degree sequences. J. Combinatorial Theory Ser. A, 2463)296--37, 1978.
Benjamin Birnbaum and Claire Mathieu. On-line bipartite matching made simple. SIGAC7 News, 39(1):80- 87, March 2008 ISSN 0163-5700.
doi: 10. 1444//336044333664666 URL https
10w1111111114433 1360462
Béla Bollobás. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European J. Combin., 1(4):311-316, 1980.
Charles Bordenave, Marc Lelarge, and Justin Salez. Matchings on infinite graphs. Probability Theory and Related Fields, 157(1-2):133-28,, 2013.
Allan Borodin, Christodoulos Karavasilis, and Denis Pankratov. Greedy bipartite matching in random type poisson arrival model. arXiv preprint arXiv: 2018.
Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan, and Pan Xu. Online stochastic matching: New algorithms and bounds, 2019.
Nikhil Devanur, Kamal Jain, and Robert Kleinberg. Randomized primal-dual analysis of ranking for online bipartite matching. 2013. doi: 011177/11771611999
Nikhil R. Devanur, Balasubramanian Sivan, and Yossi Azar. Asymptotically optimal algorithm for stochastic adwords. In Proceedings of the 13th ACM Conference on Electronic Commerce, EC '12, page 388-404, New York, NY, USA, 2012. Association for Computing Machinery. ISBN 9781450314152. doi: 10. 10.1145/2229112222290 URL https:///// ftrg/10..r 1145/222012 2229043
Martin Dyer, Alan Frieze, and Boris Pittel. The average performance of the greedy matching algorithm. The Annals of Applied Probability, pages 526-552, 1993.
Nathanaël Enriquez. Gabriel Faraud, Laurent Ménard, and Nathan Noiry. Depth first exploration of a configuration model. arXiv preprint arXiv:1911.1008,, 2019.
Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. On power-law relationships of the internet topology. In Proceedings of the Conference on Applications. Technologies, Architectures, and Protocols for Computer Communication, SIGCOMM '99, page 251-262, New York, NY, USA. 1999. Association for Computing Machinery, ISBN 1581131356. doi: 0011145/16118.316222 URL https:///ooo...... org/ 10. 1145/316118 316229
Jon Feldman, Aranyak Mehta, Vahab Mirronni, and Shan Muthukrishnan. Online stochastic matching: Beating 1-1/e. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 117-126. IEEE, 2009.
Alan Frieze and Michal Karoński. Introduction to random graphs. Cambridge University Press, 2016.
Christopher David Godsil. Matchings and walks in graphs. Journal of Graph Theory, 5(3):285-297, 1981.
Gagan Goel and Aranyak Mehta. Online budgeted matching in random input models with applications to adwords. In Proceedings of the Nineteenth Annual ACM-SIAM -SAM Symposium on Discrete Algo- rithms, SODA '08, page 982 991. USA, 2008a. Society for Industrial and Applied Mathematics.
Gagan Goel and Aranyak Mehta. Online budgeted matching in random input models with applications to adwords. pages 982-991, 01 2008b. doi: 10. 10111145114477 347002.113771888 1347189.
Patrick Jaillet and Xin Lu. Online stochastic matching: New algorithms with better bounds. Mathe- matics of Operations Research, 39(3):624-646, 2014.
R. M. Karp, U. V. Vazirani, and V. V. Vazirani. An optimal algorithm for on-line bipartite match- ing. In Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, STOC 190. page 352-358, New York, NY, USA, 1990. Association for Computing Machinery. ISBN 0897913612, doi: 10.1 00.1145/100216.11 100262. URL, http::ttt////t :/dp:: .rceii.org/1..0 114100111411001111 100262

---

László Lovász and Michael D Plummer. Matching theory, volume 367. American Mathematical Soc., 2009.
Mohammad Mahdian and Qiqi Yan. Online bipartite matching with random arrivals: An approach based strongly factor-revealing lps. pages 597-606, 01 2011. doi: 10.1145/199366. 1993716
Vahideh H Manshadi, Shayan Oveis Gharan, and Amin Saberi. Online stochastic matching: Online actions based on offline statistics. Mathematics of Operations Research, 37(4):559-53 (500)3559-55555 2012.
Andrew Mastin and Patrick Jaillet. Greedy online bipartite matching on random graphs. arXiv preprint arXiv:1307.2536 2013.
Aranyak Mehta. Online matching and ad allocation. Theoretical Computer Science, 8(4):265-363) 2012.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407, 1951.
Remco Van Der Hofstad. Random graphs and complex networks, volume 1. Cambridge university press, 2016.
Nicholas C Wormald. Differential equations for random processes and random graphs. The annals of applied probability, 5(4):1217-1235, 1995.
Lenka Zdeborová and Mare Mézard. The number of matchings in random graphs. Journal of Statistical Mechanics: Theory and Experiment, P006(35,,,00003, 2006.
12

---

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? [Yes]
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]
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 URL)? [Yes]
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No] The experiments can be run any personal laptop.
4. If you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're
using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "nxZvGk8XWLd", "reviewer": "Reviewer_tZCg", "summary": "The paper studies the performance of a greedy algorithm for online bipartite matching under the configuration model. In this model the vertex degrees of the input graph adhere to a fixed distribution. The authors estimate the competitive ratio of the greedy algorithm and show that in this model the greedy algorithm achieves better performance guarantees than related methods.", "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": "Originality/Significance: The authors present an interesting result in the area of online matching under a stochastic model. It has to be said that I am not an expert in this area, but it seems both the result and the proof technique are original and should be of interest to the community.\n\nQuality/Clarity: The paper is mostly clear. At times the authors use terminology that could be improved, such as:\n- \"subGaussian\" (line 113) -- What do you mean by that?\n- \"half-edges\" -- requires definition\n- \"multiple edges\" (line 158) -- Should be replaced by \"parallel edges\" (the standard terminology)\n- The statement in Proposition 1 should be formalized.\n\nI did not have time to check the proof of the main claim.\n\nFrom a presentation point of view the paper should meet the bar of acceptance, given the authors improve on the issues pointed out above.\n\nTypos:\n- $N$ instead of $n$ (line 164)\n- *reason (line 69)\n- \"worst\" -> \"worse\" (line 214)\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "YCE8vH9iwIk", "reviewer": "Reviewer_8M7X", "summary": "The paper studies the online bipartite matching problem with capacities in random graphs that are generated by a stochastic process called the configuration model. The configuration model generates random graphs whose degree distributions are sub-Gaussian. The main contribution of the paper is an analysis of the competitive ratio achieved by the well-studied Greedy algorithm for online bipartite matching. The main result relates the competitive ratio to the solution of a certain ODE. The ODE can either be solved in closed form for some special cases of interest or it can be solved numerically to obtain estimates of the competitive ratio. As a corollary of the main result, the paper derives competitive ratios for several special cases, including random d-regular graphs and Erdos-Renyi graphs.\n", "questions": "", "limitations": "", "rating": 5, "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": "Significance: The paper addresses a fundamental problem in online algorithms, which is well studied and has applications in online advertising. The Greedy algorithm is also a well-studied algorithm in both the adversarial setting as well as stochastic settings. The current paper contributes to this line of work by analyzing Greedy in a more general random graph models, and relating its competitive ratio by relating it to an ODE that can be solved either numerically or in closed form in some settings. The questions addressed are mathematically interesting. \n\nOn the negative side, the paper does not discuss how the mathematical results presented can benefit the machine learning community. The paper does not connect the random graph model considered to real-world instances. Overall, the paper seems to be a better fit for a TCS or Mathematics venue.\n\nNovelty/originality: The result appears to be novel and the approach could potentially lead to explicit competitive ratios for more general random instances.\n\nClarity: The content in the main body is reasonably clear. I have not checked the correctness of the proofs included in the appendix.", "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": "I did not track the hours"}, "extra_text": {}}, {"review_id": "UOARTKViXJc", "reviewer": "Reviewer_mSP9", "summary": "This paper analyzes the performance of the GREEDY algorithm for online matching on random bipartite graphs generated by the configuration model with given degree distributions.\nThe analysis is based the differential equation method, a stochastic approximation using an ODE to represent the time evolution of matching size under the GREEDY algorithm with overwhelming probability.\nThe paper reports the following main results:\n- A proof that the matching size of the GREEDY algorithm is the solution to an ODE.\n- Competitive ratios of the GREEDY algorithm in different graph models (d-regular graphs, Erdos-Reny graphs).\n- A proof that GREEDY beats RAKNING on 2-regular graph, with experimental evidence suggesting that the same holds for higher degrees.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "- Very readable, great writing, though typos are noticeable.\n- Main idea is to consider the random process of graph generation in the configuration model together with the time evolution of GREEDY matching, which is interesting.\n- The main result generalizes or complements some known results on special graph families.\n- The paper is easy to follow.\n\nSome nitpicks:\n- Typo: line 19, Page 1, second paragraph of Introduction, Internal advertising should be Internet advertising.\n- Typo: Algorithm ??, Page 4, line 129.\n- Great introduction on online matching and its variants (weighted, configuration model).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper only studies theoretical performance and does not mention societal impacts.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "QejgzWWKPAP", "reviewer": "Reviewer_v6Xy", "summary": "The authors investigate bipartite matching in an online setting were the graph edges are generated via the configuration model (i.e. from a chosen degree distribution). They bound the estimation error, measured via the expected ratio between the online matching obtained by Greedy and the hindsight-optimal matching. This allows them to compare the performance guarantee for Greedy versus the state-of-the-art Ranking algorithm. The authors prove that surprisingly, there exist problem instances (including simple and natural ones) where Greedy outperforms Ranking.", "questions": "", "limitations": "", "rating": 5, "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": "REVIEW\nThe main result, which is a bound on the estimation error of Greedy for configuration graphs, is of theoretical interest. It is also interesting that this result permits a convenient comparison of Greedy's performance on different configuration graphs. Finally, I agree with the authors that it is interesting that Greedy outperforms Ranking on simple/natural graphs, such as 2-regular graphs. Obtaining these results is nontrivial. I see this not as a breakthrough theoretical result, but rather as an interesting step forward in a relevant area that requires nontrivial analysis.\n\nIn terms of style, the paper is generally well-written. However, typical NeurIPS papers make better use of subheadings throughout and offer brief exposition/high-level intuitions around each section. This paper is written more like a math journal paper. More structure and more high-level exposition would improve the writeup.\n\nThe experimental results figures are in general very difficult to parse and have some issues: They are missing labels on the axes; linetypes (dashes/dots) are not used to distinguish the lines; points are not used to show the actual points of comparison; I infer that (for example) the 4 panels in Appendix Fig. 5 and 6 are used to plot d=2,4,10,20 (this should be stated), but there are no titles on the figures, so is the top right plot d=4 or the bottom left plot d=4?\n\nAlso, in the figures shown in the paper's text (Fig. 1), we are shown results for d=[2,3,4,6,10], and we are told results are nearly instantaneous. Given that computation is not a limiting factor, why not show us more results (in a different type of plot)? In general, for a NeurIPS paper I would expect a greater effort to articulate and display experimental results---improving this will improve the paper. Also, one of the last sentences of the paper mentions that you expect Greedy will outperform Ranking in various other scenarios---this is a tantalizing opportunity for a broader experimental approach (either for this or another paper).\n\nI will consider revising my review based on the authors' response.\n\nMinor suggestions for improving the writing, figures, etc.:\n\n- References are all lacking numbers in the References section. This makes it very difficult to check your references.\n\n-Line 69 states \"The main is that \" --> maybe there is a missing word such as 'main limitation'?\n\n-Convention suggests that your introduction should have subsections. It is a well-written introduction, but we only learn about your main result in the penultimate paragraph. You might consider highlighting it under a \"Main contribution\" substitle or bold paragraph heading.\n\n- The Algorithm \\ref in line 129 is undefined.\n\n- Multiple instances of the word GREEDY have a missing space after. If this is a macro, try a \\ (slash) between GREEDY and any non-punctuation letters/words.\n\n- Missing 's' in 'situations' on line 308\n\n- Line 212: folline -> offline", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are addressed. Societal impact is not applicable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers generally thought this was an interesting paper on stochastic matchings. Novel ideas and analysis are presented.  The criticism is the fit for the community. 
Decision: Accept (Poster)