Online Matching in Sparse Random Graphs: Non-Asymptotic Performances of Greedy Algorithm
Year: 2021

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, which 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, GREEDYcan have better performance guarantees than RANKING, another celebrated algorithm for online matching that usually outperforms the former.

heading: 1 Introduction
text: Finding matchings in bipartite graphs (U[V , E), where E ⇢ U⇥V is a set of edges, is a long-standing problem with different motivations and approaches [Godsil, 1981, Zdeborová and Mézard, 2006, Lovász and Plummer, 2009, Bordenave et al., 2013]. If U is seen as a set of resources and V as demands, the objective is to allocate as many resources to demands (an allocation - or a matching - between u and v is admissible if (u, v) 2 E) with the constraint that a resource is allocated to 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 to the excellent survey [Mehta, 2012] for more applications, specific settings, results and techniques). In this case, the set of vertices U is present at the beginning and the graph unveils sequentially: vertices v 2 V are observed sequentially, one after the other, along with the edges they belong to. An online algorithm must decide, right after observing vk and its associated set of edges Ek := {(u, vk) 2 E} to match it to some other vertex u 2 U , at the conditions that (u, vk) 2 Ek and u 2 U 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 it has created and the highest possible matching in hindsight [Feldman et al., 2009].
This theoretical setting is particularly well suited for online advertising: U is the set of campaigns/ads that an advertiser can run and users v1, v2, . . . , vT 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 (NeurIPS 2021).
on their attributes/features, such as the geographic localization, the browsing history, or any other relevant information). The objective of an advertiser (in this over-simplified model) is to maximize the number of displayed ads. In practice, campaigns/ads are not displayed only once but have a maximal budget of impressions (say, a 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 ! 2 N (a vertex v 2 V is matched once while u 2 U can be matched !u times).
This online matching problem with capacities has been quite extensively studied. It 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 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 1/e on any instance [Karp et al., 1990, Devanur et 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 a finite set of L “base” vertices v(1), . . . , v(L) associated to base edge-sets E(1), . . . , E(L). When a vertex vk arrives, its type ✓k 2 {1, . . . , L} is drawn iid from some distribution (either known beforehand or not) and then its edge set is set as Ek = E(✓k). In the context where the distribution is known, algorithms with much better competitive ratios than GREEDY or RANKING were designed [Manshadi et al., 2012, Jaillet and Lu, 2014, Brubach et al., 2019], specifically with a competitive ratio of 1 2/e2 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 Mehta, 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 ( for example when the degrees of each vertex U increase linearly with the number of vertices in V , or when the set U of campaigns must be fixed so that the model is well specified, etc...). Another tentative is to consider Erdős-Rényi graphs assuming that each possible edge is present in U ⇥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 U has an expected degree independent of the size n 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 [Borodin et al., 2018, Arnosti, 2019, Dyer et al., 1993, Mastin and Jaillet, 2013]. Unfortunately, although this Erdős-Rényi model is compatible with growing sets U and V , it 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 [Barabási et al., 2000, Van Der Hofstad, 2016].
We, therefore, consider a more appropriate random graphs generation process called configuration model, introduced by [Bender and Canfield, 1978] and [Bollobás, 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) or “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 U 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
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 et al. [1999]). The configuration model also displays the so called “small-world phenomenon” (observed for instance in the graph of Facebook by Backstrom et al. [2012]) as its diameter is 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, 1995]; we prove that the increasing size of the random matching created is 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 2 describes precisely the problem and Theorem 1 is our first main result: it describes the performances of GREEDY in the capacity-less problem. The proof of Theorem 1 is delayed to Appendix D, but the main ideas and intuitions are provided in Section 3. The online matching with capacities problem is treated in Appendix A.

heading: 2 Online Matching Problems; Models and main result
text: Consider a bipartite graph with capacities G = (U ,V, E ,!) where U = {1, . . . , N} and V = {1, . . . , T} are two finite set of vertices, E ⇢ (u, v), u 2 U , v 2 V is the set of edges and ! : U ! N⇤ is a capacity function. A matching M on G is a subset of edges e 2 E such that any vertex v 2 V is the endpoint of at most one edge e 2 M and any vertex u 2 U is the endpoint of at most !u edges in M . We will denote by M the set of matchings on G; the optimal matching M⇤ 2M 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 a 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 ! are known from the start, and vertices v 2 V arrive sequentially (with the edges they belong to) and M0 = ;. At stage t 2 N – assuming a matching Mt 1 has been constructed –, a decision maker observes a new vertex1 vt and its associated set of edges {(u, vt);u 2 E}. If possible, one of these edges (ut, vt) is added to Mt 1, with the constraint that Mt = Mt 1 [ {(ut, vt)} is still a matching. The objective is to maximize the size of the constructed matching MT . The classical way to evaluate the performances of an algorithm is the competitive ratio, defined as |MT |/|M⇤| 2 [0, 1] (the higher the better).

heading: 2.1 Structured online matching via Configuration Model
text: As mentioned before, the online matching problem can be quite difficult without additional structure. We will therefore assume that the vertex degrees in U and V have (at least asymptotically in N and T ) some given subGaussian2 distributions ⇡U and ⇡V , of respective expectation µU and µV and respective proxy-variance 2U and 2 V . Those numbers are related in the sense that we assume 3 that T = µUµV N 2 N. Given those degree distributions, the graphs we consider are random draws from a bipartite configuration model described below; for the sake of clarity, we first consider the capacity-less case (when !u = 1 for all u 2 U).
Given ⇡U and ⇡V and N,T 1, let dU1 , . . . , dUN 2 N i.i.d. ⇠ ⇡U and dV1 , . . . , dVT 2 N i.i.d. ⇠ ⇡V be independent random variables; intuitively, those numbers are respectively the number of half-edges attached to vertex in U and V . Consider also two extra random variables
dVT+1 = max NX
i=1
dUi TX
j=1
dVj , 0
and dUN+1 = max TX
j=1
dVj NX
i=1
dUi , 0
1Although the order of arrival is irrelevant to the models we studied, it could have an impact on other models. 2X is subGaussian with proxy-variance 2 if for any s 2 R,E[exp(sX)]  exp ⇣ 2s2
2
⌘ . Actually, we only
need that ⇡U and ⇡V have some finite moment of order > 2. 3In the general case, consider T = bNµU/µVc. The proof is identical, up to a negligible 1/N error term
so that equality between total degrees holds, i.e., PN+1
i=1 d U i = PT+1 j=1 d V j . Finally, a random (capacity-
less) bipartite graph denoted by CM(dU ,dV ) is constructed with a uniform pairing of half-edges of U [ {N + 1} with half-edges of V [ {T + 1} and removing vertices T + 1 and N + 1 and their associated edges. These two artificially added vertices are just here to define a pairing between half-edges. Notice that, by the law of large numbers and since T = (µU/µV)N , dVT+1 = o(N) and dUN+1 = o(N) almost surely 4.
The bipartite configuration model CM(dU ,dV) is then the random graph obtained by a uniform matching between the half-edges of U and the half-edges of V , where the random sequences dU = (dUi )i and dV = (dVj )j are defined as above.

heading: 2.2 Competitive ratio of GREEDY algorithm. Main result
text: 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 e = (u, v) 2 E, u(e) = u (resp. v(e) = v) is the extremity of e in U (resp. V); the generating series of ⇡U and ⇡V are denoted by U and V and are defined as
U (s) := X
k 0 ⇡U (k)s
k and V(s) := X
k 0 ⇡V(k)s
k.
Our first main theorem, stated below, identifies the asymptotic size of the matching generated by GREEDY on the bipartite configuration model we have just defined. As the batched problem (i.e., computing the size of the optimal matching M⇤) is well understood [Bordenave et al., 2013], this quantity is sufficient to derive competitive ratios. Again, for the sake of presentation, we first assume that all capacities are fixed, equal to one; the general case is presented in Appendix A. Theorem 1. (Performances of GREEDY in the capacity-less case) Given N 1 and T = µUµV N , let MT be the matching built by GREEDY on CM(d
U ,dV ) then the following convergence in probability holds:
|MT |
N P ! N!+1 1 U (1 G(1)).
where G is the unique solution of the following ordinary differential equation:
G0(s) = 1 V
⇣ 1 1µU 0 U (1 G(s)) ⌘ µV µU 0U (1 G(s)) ; G(0) = 0. (1)
Moreover, for any s 2 [0, 1], if MT (s) is the matching obtained by GREEDY after seeing a proportion s of vertices of V , then
|MT (s)|
N P ! N!+1 1 U (1 G(s)). (2)
Convergence rates are explicit; with probability exponentially large, at least 1 ⇣N exp( ⇠N c/2),
sup s2[0,1]
|MT (s)|
N 1 U (1 G(s))
 N c,
where ⇣, ⇠, depend only on the (first two) moments of both ⇡V and ⇡U , and c is some universal constant (set arbitrarily as 1/20 in the proof).
Theorem 1 generalizes to the case with capacities, see Sections A.1 and A.2. The details of the proof of Theorem 1 are postponed to Appendix D, but the main ideas are given in Section 3.

heading: 2.3 Examples, Instantiations and Corollaries
text: We provide in this section some interesting examples and corollaries that illustrate the powerfulness of Theorem 1, and how it can be used to compare different situations.
4And even O( p N) with probability exponentially large in N as both distributions are sub-Gaussian. 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 2 N, i.e., graphs such that each vertex has an exact degree of d (to avoid trivial examples, we obviously assume d 2).
It is non-trivial to sample a d-regular graph at random, yet it is easy to generate random graphs GN with the configuration model described above, with the specific choices of ⇡U = ⇡V = d, the Dirac mass at d. The downside is that GN is not exactly a d-regular bipartite random graph (as some vertices might be connected more than once, i.e., there might exist parallel edges). However, conditioned to be simple, i.e, 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 0 [Van Der Hofstad, 2016]; as a consequence, any property holding with probability tending to 1 for GN , holds with probability tending to 1 for uniform d-regular bipartite random graphs. Finally, we also mention that Hall’s Theorem [Frieze and Karoński, 2016] implies that GN admits a perfect matching, so that |M⇤| = N .
Instantiating Equation (1) to d-regular graphs yields that the competitive ratio of GREEDY converges, with probability 1, to 1 (1 G(1))d where G is the solution of the following ODE
(1 G(s))d 1
1 (1 (1 G(s))d 1)d G0(s) =
1 d . (3)
As expected, had we taken d = 1, then G(s) = s 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( s2 ) 1, so that the competitive ratio of GREEDY converges to 4 p e (e+ 3) ' 0.877 1 1e ' 0.632, where the latter is a standard bound of the competitive ratio of GREEDY (for general, non-regular graphs) [Mehta, 2012].
Solving Equation (3) In the general case d 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 1)d admits n := d(d 1) roots, among which there is 1 with multiplicity d 1. If X is another root, then
1 (1 X)d 1 d = 1 , 1 (1 X)d 1 = e ik⇡ d , k = 1, . . . , d 1.
Therefore, (1 X)d 1 = 1 e ik⇡ d ,
which admits d 1 distinct solutions for each k = 1, . . . , d 1. The resulting n := (d 1)2 distinct complex, denoted x1, . . . , xn, are the roots of P (X)/(1 X)d 1, so the ODE reduces to:
y0(t)Q 1in y(t) xi = 1 d . (4)
Since the following trivially holds: 1Q
1in(X xi) =
X
1in
1Q j 6=i(xi xj)
1
X xi =:
X
1in
ai X xi .
it is possible to integrate Equation (4) in P
1in ai log(y(t) xi) = s d + c to finally get
Y
1in (y(t) xi)
ai = C exp( s
d ),
and since y(0) = 0, it must hold that C = Q
1in( xi) ai . As a consequence, y(1) solves:
Y
1in (y(1) xi)
ai = e1/d Y
1in ( xi)
ai .
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 d = 3 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 U (1 G(s)) that are more relevant) for various values of d; the end-point obtained at s = 1 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).

heading: 2.3.2 The Erdős-Rényi case.
text: In a Erdős-Rényi graph, there is an edge between two vertices u 2 U and v 2 V with some probability p = cN , independently from each others. As N goes to infinity, the number of edges to a vertex follows (approximately) a Poisson law of parameter c > 1.
As a consequence, we consider the configuration model where ⇡U and ⇡V are Poisson laws of parameter c, which yields µ = c, U (s) = ec(s 1). In this case, Equation (1) becomes:
cG0(s) e cG(s) 1 e c e cG(s) = 1.
The solutions are given by:
G(s) = 1
c log
✓ c
log(ek cs +1)
◆ ,
yielding
X(1 G(s)) = 1
c log
ek cs +1 .
The initial condition U (1 G(0)) = U (1) = 1 gives ek = ec 1, from which we deduce that the number of matches of GREEDY is asymptotically proportional to
1 U (1 G(1)) = 1 log (2 e c)
c ,
which recovers, as a sanity check, some existing results [Mastin and Jaillet, 2013].

heading: 2.3.3 The comparison of different configuration models
text: Using Gronwall’s Lemma, it is possible to show Theorem 1 can be used to compare different configuration models, as in the following Corollary. Corollary 1. Consider two configuration models CM1(dU1 ,d V 1 ) and CM2(d U 2 ,d V 2 ), s.t. d U 1 and dU1 are both drawn i.i.d. from ⇡U , d V 1 is drawn i.i.d. from ⇡ 1 V and d V 2 is drawn i.i.d. from
⇡2V , with P x x⇡ 1 V (x) = P x x⇡ 2 V (x). If 1 V (s)
2 V (s) for any s 2 (0, 1), then by denoting
respectively 1 and 2 the asymptotic proportion of vertices matched by GREEDY in CM1(dU1 ,d V 1 ) and CM2(dU2 ,d V 2 ), it holds that necessarily 2 1.
For instance, let us assume that the degree distribution on 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 a Poisson distribution with expectation d.
A similar result (with a different criterion) holds with fixed degree distribution on the online side and differing one on the offline side.

heading: 2.4 GREEDY can outperform RANKING !
text: We recall that the RANKING algorithm, which is the worse case optimal, chooses at random a ranking over U and uses it to break ties (i.e., if two vertices u and u0 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 a worse competitive ratio than GREEDY, which advocates again for its thorough study. Proposition 1. Let R and G be the assymptotic performances of RANKING and GREEDY on the 2-regular graph. The following holds:
G > R.
In other words, GREEDY outperforms RANKING in the 2-regular graph.
We conjecture that the above result actually holds for any d 2, and more generally for a wide class of distributions ⇡U and ⇡V (finding a general criterion would be very interesting). The proof of Proposition 1 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-edges rather than just one. Indeed, vertices with only one remaining half-edge were not selected previously and thus have a higher rank. The vertices with only one remaining half-edge will not get matched in the subsequent iterations, so not picking them as matches is suboptimal. On the other hand, GREEDY picks any match uniformly at random and does not exhibit such bias.

heading: 3 Ideas of proof of Theorem 1
text: The main idea behind the proof of Theorem 1 (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 as quantitative, properties.
Tracking the matching size is non-trivial because the vertices (in U and V) have different degrees, hence some of them are more likely to be matched than others. However, in the configuration model, each vertex has the same distribution of degrees before the sequences dU and dV are fixed. As a consequence, the proof relies on 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 is obviously crucial).
2. We are not only going to track the size of the matching built as we need to handle different probabilities of matching (and pairing the graph) for each vertex. As a consequence, we are going to track the numbers of non-matched vertices which have still i half-edges to be paired and the number of already matched vertices that have j half-edges remaining. This will give one different ODE per value of i of j. Since ⇡U and ⇡V are sub-Gaussian, we will prove that with arbitrarily high probability - exponential in N -, there are only a polynomial number of such equations
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 are deferred to the appendix.

heading: 3.1 Building the graph together with the matching
text: 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 simultaneously with the graph. More precisely, given two sequences5 of nonnegative integers dU = (dU1 , . . . , dUN ) and d V [ {dVT+1} = (d V 1 , . . . , d V T , d V T+1), we introduce in the following a generating algorithm that simultaneously build the associated bipartite configuration model CM(dU ,dV) together with GREEDY. Recall that the bipartite configuration model is obtained through a 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 1.
Algorithm 1: GREEDY MATCHING CONFIGURATION MODEL WITHOUT CAPACITIES
Input: dU = (dU1 , . . . , d U N ) and d V = (dV1 , . . . , d V T ) Initialization. M0 ;, E0 ; and HU0 { half-edges of U} for t = 1, . . . , T do
Order uniformly at random the edges emanating from vt: et1, . . . , etkt for i = 1, . . . , kt do
Choose uniformly an half-edge eUi in HU E E [ {u(eUi ), vt} // Create an edge between e t i and e U i HU HU \ {eUi } // Remove the half-edge if vt and u(eUi ) unmatched then
Mt Mt 1 [ {u(eUi ), vt} // vt is matched end
end
end CM(dU ,dV) (U ,V, E). Output: Bipartite configuration model CM(dU ,dV) and matching MT 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 of a bipartite configuration model. Moreover, it is easy to see that M corresponds to the matching constructed by GREEDY MATCHING on CM(dU ,dV).

heading: 3.2 Differential Equation Method - Stochastic Approximation
text: As mentioned above, several quantities are going to be tracked through time: for all k 2 {0, . . . , T} and all i 0, we define:
• Fi(k) as the number of vertices u 2 U that are not yet matched at the end of step k and whose remaining degree is i, meaning that du i of their initial half-edges have been paired. We will refer them to as free vertices. • Mi(k) as the number of vertices u 2 U already matched at the end of step k and whose remaining degree is i. We will refer them to as marked vertices.
Notice that for all 0  k  T , the sum Fi(k) +Mi(k) corresponds to the total number of vertices of U with remaining degree i at the end of step k. We also define
• bF (k) := P
i 0 iFi(k) is the number of available half-edges attached to free vertices at the end of step k,
5Without loss of generality, we assume that the additional extra vertex is always on the V side.
• cM(k) := P
i 0 iMi(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. A major ingredient of the proof is to show that Fi(k) and Mi(k) closely follow the solutions of some ODE. This is the so-called differential equation method [Wormald, 1995], stated in Appendix C. For instance, it can easily be seen that bF (k) + cM(k) closely follows the function t 7! µU tµV on (0, µU/µV) in the following sense. Lemma 1. For every " > 0, and for all 0  k  T ,
bF (k) + cM(k)
N µU
k N µV
⌘  ".
with probability at least 1 exp
N✏2 2 2U + exp
T ✏2 2 2V .
We now turn to each individual quantity Fi (resp. Mi). We can prove a similar result, yet the limit function is not explicit (unlike for the matching size as in Theorem 1 statement). The following Lemma 2 states that the discrete sequences of (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 (x`)` 0 and (y`)` 0 such that 0 < P ` `(x` + y`) <1, every i 0, the following mappings
i(x0, x1, . . . , y0, y1, . . .) := iµVxi + (i+ 1)µVxi+1 h
⇣ P ` 0 `y`P
` 0 `(x`+y`)
⌘ (i+ 1)xi+1
P ` 0 `(x` + y`)
(5)
and
i(x0, x1, . . . , y0, y1, . . .) := iµVyi + (i+ 1)µVyi+1 + h
⇣ P ` 0 `y`P
` 0 `(x`+y`)
⌘ (i+ 1)xi+1
P ` 0 `(x` + y`)
,
where h is the following function, well-defined on [0, 1],
h(s) = 1 V(s)
1 s .
Lemma 2. With probability 1 ⇣N exp( ⇠N c/2), there are at most N c quantities Fi and Mi, and for all 0  k  T and all i 0
Fi(k)
N fi
✓ k
N
◆  N 2c and
Mi(k)
N mi
✓ k
N
◆  N 2c,
where ⇣, depend only on the (first two) moments of ⇡V and ⇡U and c = 1/20.
The continuous mappings fi and mi are solutions of the system of differential equations on [0, µU/µV)
dfi dt = i(f0, f1, . . . ,m0,m1, . . .), dmi dt = i(f0, f1, . . . ,m0,m1, . . .),
fi(0) = ⇡U (i), mi(0) = 0.
(6)
This system is well defined as stated by the following Lemma 3. Lemma 3. The system (6) has a unique solution which is well-defined on [0, µU/µV). More precisely, denoting by f and m the generating series of the sequences (fi)i 0 and (mi)i 0,
f(t, s) = X
i 0 fi(t)s
i and m(t, s) =
X i 0 mi(t)s i,
it holds that:
f ✓ µU µV 1 e µV t , s ◆ = U (s 1)e µV t + 1 F (t) , (7)
and
m ✓ µU µV 1 e µV t , s ◆ = ˆ t 0 F 0(u) 0U (s 1)e µVu + 1 F (u) du.
where F is a solution of the following ODE
1 µU 0U (1 F (t))
1 V ⇣ 1 1µU 0 U (1 F (t)) ⌘F 0(t) = e µV t .

heading: 3.3 Aggregating solutions to compute GREEDY performances
text: To get Theorem 1, 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 Nf(µUµV , 1) by definition of f and because of Lemma 2. This corresponds to t = +1 in Equation (7), thus the performance of GREEDY is, with arbitrarily high probability, arbitrarily close to
N(1 U (1 F (+1)))
The statement of Theorem 1 just follows from a simple final change of variable.
Conclusion
We studied theoretical performances of GREEDY algorithm on 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 on 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 ⇡U or an alternative one ⇡0U ? The obvious technique would be to compare the solution of the different associated ODE’s. Similarly, the questions of stability/robustness of the solution to variation in the distribution ⇡U and ⇡V 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 a consumer for a 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-0026 as well as the support grant as part of the Investissement d’avenir project, reference LabEx Ecodec/ANR11-LABX-0047. Nathan Noiry also acknowledges support from the Telecom Paris DSAIDIS chair and from the ANR ProGraM (ANR-19-CE40-0025). Flore Sentenac is supported by IP PARIS’ PhD Funding.

Review summaries:
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. The 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. The paper reports the following main results: - A proof that the matching size of the GREEDY algorithm is the solution to an ODE. - Competitive ratios of the GREEDY algorithm in different graph models (d-regular graphs, Erdos-Reny graphs). - A proof that GREEDY beats RAKNING on 2-regular graph, with experimental evidence suggesting that the same holds for higher degrees.

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.

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. 

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.