11institutetext: {mihail<EMAIL_ADDRESS>
Department of Computer Science
University of California, Irvine, USA

# Online Matching with High Probability

Milena Mihail The author was supported in part by a UCI-faculty startup grant.
Thorben Tröbst The author was supported in part by NSF grant CCF-1815901. Part
of this work was done while the author attended the “Trimester Program on
Discrete Optimization” at the Hausdorff Institute for Mathematics in Bonn,
Germany.

###### Abstract

We study the classical, randomized Ranking algorithm which is known to be
$(1-\frac{1}{e})$-competitive in expectation for the Online Bipartite Matching
Problem. We give a tail inequality bound (Theorem 1.1), namely that Ranking is
$(1-\frac{1}{e}-\alpha)$-competitive with probability at least
$1-e^{-2\alpha^{2}n}$ where $n$ is the size of the maximum matching in the
instance. Building on this, we show similar concentration results for the
Fully Online Matching Problem and for the Online Vertex-Weighted Bipartite
Matching Problem.

###### Keywords:

Online Algorithms Concentration of Measure Online Matching Randomized
Algorithms

##  1 Introduction

In the Online Bipartite Matching Problem, we have an undirected, bipartite
graph $G=(S,B,E)$ with a set $S$ of _sellers_ and a set $B$ of _buyers_. The
buyers arrive online in adversarial order and every time a buyer $i$ arrives,
all of its neighbors $N(i)$ are revealed. We must then decide irrevocably
which as of yet unmatched neighbor of $i$ should get matched to $i$. The goal
is to maximize the number of edges in the final matching $M$ relative to the
size of the maximum matching in $G$, i.e. the so-called competitive ratio.

A matching $M$ is considered _maximal_ if there is no edge in $E$ which can be
added to $M$ while preserving the matching property. Due to the well-known
fact that every maximal matching contains at least half of the edges of any
_maximum_ matching, it is easy to see that any algorithm which matches
arriving buyers whenever possible must be $\frac{1}{2}$-competitive. Moreover,
because of the adversarial arrival of buyers, this is best possible for
deterministic algorithms. In their seminal work, Karp et al. [10] defined the
randomized Ranking algorithm (see Algorithm 1) and showed that it is
$(1-\frac{1}{e})$-competitive in expectation. They also showed that this is
the best possible competitive ratio for any randomized algorithm.

1 Sample a uniformly random permutation $\pi$ on $S$.

2 for  _each buyer $i$ who arrives_ do

3 Match $i$ to the first unmatched buyer in $N(i)$ wrt. to $\pi$.

Algorithm 1 Ranking

In the years since then, online matching problems have received a large amount
of interest due to the vast number of applications created by the internet and
mobile computing. Online advertising alone poses the AdWords Problem [14, 7,
16] that lies at the heart of a multi-billion dollar market. Another
interesting application, the Fully Online Matching Problem [8, 9], came about
due to the rise of ride-sharing and/or ride-hailing apps such as Uber and
Lyft.

For many online matching problems, there are extensions of Ranking which
achieve competitive ratios of $1-\frac{1}{e}$ or at the very least strictly
greater than $\frac{1}{2}$. Often, these are best-known for their respective
problems. However, to the best of our knowledge, all results on online
matching in the literature only consider the competitive ratio _in
expectation_ without guaranteeing any form of concentration beyond the trivial
bounds that follow from Markov’s inequality.

The analysis of concentration bounds for randomized algorithms goes back to
the 1970s with classic results such as the second moment bound for Quicksort
[15]. See [4] for an extensive overview of the field. However, it has remained
a niche area of interest, including in the analysis of online algorithms
where—with some exceptions (e.g. [11, 12])—results are quantified in terms of
expected solution quality only.

In some sense this is due to the well-known fact that, as a consequence of
standard Chernoff bounds, any randomized algorithm which is good in
expectation can be boosted to be good with probability $1-\frac{1}{n}$ by
simply repeating it $O(\log n)$ many times. But it is precisely in the case of
online algorithms where this argument fails due to the fact that online
algorithms, by definition, can not be repeated. Thus we argue that it is of
particular interest to analyze the concentration of randomized online
algorithms such as Ranking.

###  1.1 Our Results and Techniques

Our results concern Ranking type algorithms in three different settings: the
classic Online Bipartite Matching Problem (see Section 2), the Fully Online
Matching Problem inspired by ride-sharing (see Section 3) and the Online
Vertex-Weighted Bipartite Matching Problem inspired by the internet
advertising markets (see Section 4).

In Section 2 we will show the following result, complementing the classic
$\left(1-\frac{1}{e}\right)$-competitiveness result of Ranking for the Online
Bipartite Matching Problem [10] .

###### Theorem 1.1

Let $G=(S,B,E)$ be an instance of the Online Bipartite Matching Problem which
admits a matching of size $n$. Then for any $\alpha>0$ and any arrival order,

$\mathbb{P}\left[|M|<\left(1-\frac{1}{e}-\alpha\right)n\right]<e^{-2\alpha^{2}n}$

where $M$ is the random variable denoting the matching generated by Ranking.

The key technical ingredient for this result is a bounded differences property
of the random variable $|M|$ (see Lemma 2). We prove this via structural
properties of matchings (see Lemma 3) similar to ones which have been used in
previous analyses of Ranking [6, 2]. Finally, this allows us to apply the
following key lemma which is a consequence of Azuma’s inequality.

######  Lemma 1 (McDiarmid’s Inequality [13])

Let $c_{1},\ldots,c_{n}\in\mathbb{R}_{+}$ and consider some function
$f:[0,1]^{n}\rightarrow\mathbb{R}$ satisfying

$|f(x_{1},\ldots,x_{i-1},x^{\prime}_{i},x_{i+1},\ldots,x_{n})-f(x_{1},\ldots,x_{n})|\leq
c_{i}$

for all $x\in[0,1]^{n}$, $i\in[n]$ and $x^{\prime}_{i}\in[0,1]$. Moreover let
$\Delta^{n}$ be the uniform distribution on $[0,1]^{n}$. Then for all $t>0$,
we have

$\mathbb{P}_{x\sim\Delta^{n}}[f(x)<\mathbb{E}_{y\sim\Delta^{n}}[f(y)]-t]<e^{-\frac{2t^{2}}{\sum_{i=1}^{n}{c_{i}^{2}}}}.$

In Section 3 we will define the Fully Online Matching Problem and the natural
extension of Ranking for this setting. We will then give a similar
concentration bound as in Theorem 1.1.

###### Theorem 1.2

Let $G$ be an instance of the Fully Online Matching Problem which admits a
matching of size $n$. Then for any $\alpha>0$,

$\mathbb{P}\left[|M|<\left(\rho-\alpha\right)n\right]<e^{-\alpha^{2}n}$

where $M$ is the random variable denoting the matching generated by Ranking
and $\rho$ is the competitive ratio of Ranking.

We remark that by [8], we know $\rho>0.521$ and for the special case where $G$
is bipartite, we have $\rho=W(1)\approx 0.567$.

Lastly, in Section 4 we will consider the Online Vertex-Weighted Bipartite
Matching Problem. In this setting, a generalization of Ranking was shown to be
$(1-\frac{1}{e})$-competitive by Aggarwal et al. [1]. We will modify this
algorithm to show the following.

###### Theorem 1.3

For any $\alpha>0$, there exists a variant of Ranking such that for any
instance $G=(S,B,E)$ with weights $w:S\rightarrow\mathbb{R}_{+}$ of the Online
Vertex-Weighted Bipartite Matching, any arrival order of $B$ and any matching
$M^{*}$,

$\mathbb{P}\left[w(M)<\left(1-\frac{1}{e}-\alpha\right)w(M^{*})\right]<e^{-\frac{1}{50}\alpha^{4}\frac{w(M^{*})^{2}}{||w||_{2}^{2}}}$

where $M$ denotes the matching generated by Ranking and

$w(M)\coloneqq\sum_{\\{i,j\\}\in M}w_{j}.$

##  2 Online Bipartite Matching

In order to analyze Ranking, it is common to replace the sampling of the
permutation $\pi$ in Algorithm 1 by sampling an independent, uniform
$x_{j}\in[0,1]$ for every $j\in S$ called the _rank_ of $j$. Then, sorting $S$
by the values of $x_{j}$ yields a uniformly random permutation. Formally, this
is Algorithm 2.

1 for  _$j\in S$_ do

2 Sample a uniformly random $x_{j}\in[0,1]$.

3for  _each buyer $i$ who arrives_ do

4 Match $i$ to an unmatched $j\in N(i)$ minimizing $x_{j}$.

Algorithm 2 Ranking

In the following, consider a fixed graph $G=(S,B,E)$ with a fixed arrival
order. Assume that $|S|=n$ and that $G$ has a matching of size $n$. We define
a function $f:[0,1]^{S}\rightarrow\mathbb{R}$ by letting $f(y)$ be the size of
the matching $M$ generated by Algorithm 2 if $x_{j}=y_{j}$ for all $j\in S$.
Our goal will then be to show the following Lemma which is a different
perspective on a structural property that appears under various forms in the
online matching literature (e.g. Lemma 2 in [2]).

######  Lemma 2 (Bounded Differences)

Let $x\in[0,1]^{S}$, $j^{\star}\in S$ and $\theta\in[0,1]$ be arbitrary.
Define $x^{\prime}_{j}$ to be $\theta$ if $j=j^{\star}$ and $x_{j}$ otherwise.
Then $|f(x)-f(x^{\prime})|\leq 1$.

Note that Lemma 2 implies Theorem 1.1 via McDiarmid’s inequality (Lemma 1).
Specifically, by applying McDiarmid to the function $f$ with $c\equiv 1$ we
get

$\displaystyle\mathbb{P}\left[|M|<\left(1-\frac{1}{e}-\alpha\right)n\right]$
$\displaystyle\leq\mathbb{P}_{x\sim\Delta^{S}}[f(x)<\mathbb{E}_{y\sim\Delta^{S}}[f(y)]-\alpha
n]$ $\displaystyle\leq e^{-\alpha n^{2}}$

where we used that $(1-\frac{1}{e})n\leq\mathbb{E}_{y\sim\Delta^{S}}[f(y)]$
since Ranking is $(1-\frac{1}{e})$-competitive. It remains to prove Lemma 2.

###### Lemma 3

Let $j\in S$, then we can define the graph $G_{-j}$ which contains all
vertices of $G$ except for $j$. For some fixed values of $x\in[0,1]^{S}$, we
let $M$ be the matching produced by Ranking in $G$ and let $M_{-j}$ be the
matching produced by Ranking in $G_{-j}$. Then
$|M_{-j}|\leq|M|\leq|M_{-j}|+1$.

###### Proof

For any buyers $i,i^{\prime}\in B$, let $N^{(i)}(i^{\prime})$ be the set of
neighbors of $i^{\prime}$ in $G$ which are unmatched by the time that $i$
arrives in the run of Ranking with the fixed values of $x$. Likewise, let
$N^{(i)}_{-j}(i^{\prime})$ be the set of unmatched neighbors of $i^{\prime}$
in the run of Ranking on $G_{-j}$ when $i$ arrives. We claim that for all
$i\in B$ there exists some $j^{\prime}\in S$ such that for all $i^{\prime}\in
B$ we have $N^{(i)}(i^{\prime})=N^{(i)}_{-j}(i^{\prime})$ or
$N^{(i)}(i^{\prime})=N^{(i)}_{-j}(i^{\prime})\cup\\{j^{\prime}\\}$.

Let us show this claim via induction on $i\in B$ in order of arrival. Note
that when the first buyer arrives, this holds for $j^{\prime}=j$ because we
have removed only $j^{\prime}$ from the graph and nobody has been matched yet.
Now assume that the statement holds when $i$ arrives, we need to see that it
still holds after $i$ has been matched. Clearly, if $i$ gets matched to the
same vertex in $G$ and in $G_{-j}$, then the inductive step follows trivially.

So now assume that $i$ gets matched to different vertices in $G$ and in
$G_{-j}$. By the inductive hypothesis this can only happen if $i$ gets matched
to $j^{\prime}$ in $G$ and it gets matched to some other $j^{\prime\prime}$
(potentially $j^{\prime\prime}=\bot$, i.e. it is not matched at all) in
$G_{-j}$. But then $N^{(i+1)}(i^{\prime})=N_{-j}^{(i+1)}(i^{\prime})$ or
$N^{(i+1)}(i^{\prime})=N_{-j}^{(i+1)}(i^{\prime})\cup\\{j^{\prime\prime}\\}$
for all $i^{\prime}\in B$. Thus the claim holds by induction.

Finally, let us see that the claim implies the lemma. First note that since
$i$ always has more unmatched neighbors in $G$ than in $G_{-j}$, we have
$|M|\geq|M_{-j}|$. But on the other hand, if at some time in the algorithm $i$
is matched to $j^{\prime}$ in $G$ and not matched at all in $G_{-j}$, then we
have that $N^{(i+1)}(i^{\prime})=N_{-j}^{(i+1)}(i^{\prime})$ for all
$i^{\prime}\in B$. Thus the two runs will be identical from that point onward
and $|M|=|M_{-j}|+1$.∎

Finally, we can show that this implies the bounded differences property of $f$
that we claimed in Lemma 2.

###### Proof

By Lemma 3 we know that removing a seller from the graph can decrease the size
of the matching computed by Ranking by at most one assuming that the values of
the $x_{j}$ are fixed. But of course if we are removing $j^{\star}\in S$, the
matching $M_{-j^{\star}}$ computed by Ranking in $G_{-j^{\star}}$ does not
depend on the value of $x_{j^{\star}}$ or $x^{\prime}_{j^{\star}}$. So we have

$|M_{-j^{\star}}|\leq f(x)\leq|M_{-j^{\star}}|+1$

and

$|M_{-j^{\star}}|\leq f(x^{\prime})\leq|M_{-j^{\star}}|+1$

which implies $|f(x)-f(x^{\prime})|\leq 1$ as claimed.∎

As we have already seen, this is enough to prove Theorem 1.2 in the case where
$|S|=n$. To prove the general case we can use a simple reduction. In
particular, assuming that there is a matching $M$ of size $n$ but $|S|>n$, let
$S_{M}$ be the sellers covered by $M$ and let $G_{M}=(S_{M},B,E)$. We have
seen in Lemma 3 that for any fixed $x\in[0,1]^{S}$, Ranking will produce a
matching in $G$ that is not smaller than the matching it produces in $G_{M}$
when run with $x$ restricted to $S_{M}$. Therefore, Theorem 1.2 on $G_{M}$
implies Theorem 1.2 on $G$ which establishes the general case.

##  3 Fully Online Matching

In the Fully Online Matching Problem we have a not necessarily bipartite graph
$G$ the vertices of which arrive and depart online in adversarial order. When
a vertex arrives, it reveals all of its edges to vertices that have already
arrived. By the time it departs we are guaranteed to have been revealed its
entire neighborhood.

This problem was introduced by Huang et al. [8] and is motivated by ride-
sharing. Each vertex represents a rider who, upon arrival, is willing to wait
only for a certain amount of time. Two riders can only be matched if the time
that they spend on the platform overlaps, even in the offline solution. This
additional condition allows Huang et al. to show that the generalization of
Ranking shown in Algorithm 3 is $0.521$-competitive in general and
$0.567$-competitive on bipartite graphs.

1 for  _vertex $i$ who arrives_ do

2 Sample a uniformly random $x_{i}\in[0,1]$.

3for  _vertex $i$ who departs_ do

4 Match $i$ to an unmatched $j\in N(i)$ minimizing $x_{j}$.

Algorithm 3 Fully Online Ranking

In order to show a concentration bound, we can apply similar techniques as in
Section 2. Let $G=(V,E)$ be a graph which admits a perfect matching of size
$n$. Then let $f:[0,1]^{V}\rightarrow\mathbb{R}$ represent once again the size
of the matching generated by Algorithm 3 when given the $x_{i}$ values. The
corresponding bounded differences condition then becomes:

######  Lemma 4 (Bounded Differences)

Let $x\in[0,1]^{V}$, $i^{\star}\in V$ and $\theta\in[0,1]$ be arbitrary.
Define $x^{\prime}_{i}$ to be $\theta$ if $i=i^{\star}$ and $x_{i}$ otherwise.
Then $|f(x)-f(x^{\prime})|\leq 1$.

This implies Theorem 1.2 as before though note that this time we will lose a
factor of 2 since we now have $2n$ variables. We remark that this follows
directly from Lemma 2.3 in [8] but for completeness we will give a short proof
sketch.

###### Lemma 5

Using the notation from Lemma 3, we have $|M_{-j}|\leq|M|\leq|M_{-j}|+1$ for
any $j\in V$ and fixed values of $x\in[0,1]^{V}$.

###### Proof

As in the proof of Lemma 3, let $N^{(i)}(i^{\prime})$ (or
$N^{(i)}_{-j}(i^{\prime})$) be the set of neighbors of $i^{\prime}$ in $G$ (or
$G_{-j}$) which is unmatched by the time that $i$ departs in the run of Fully
Online Ranking with the fixed values of $x$. We claim that for all $i\in V$,
there exists some $j^{\prime}\in V$ such that for all $i^{\prime}\in V$, we
have $N^{(i)}(i^{\prime})=N^{(i)}_{-j}(i^{\prime})$ or
$N^{(i)}(i^{\prime})=N^{(i)}_{-j}(i^{\prime})\cup\\{j^{\prime}\\}$.

This claim follows via an almost identical induction as in Lemma 3. Then,
since $i$ always has more unmatched neighbors in $G$ than in $G_{-j}$, we have
$|M|\geq|M_{-j}|$. And if at some time in the algorithm, $i$ is matched to
$j^{\prime}$ in $G$ and not matched at all in $G_{-j}$, then we have that
$N^{(i+1)}(i^{\prime})=N_{-j}^{(i+1)}(i^{\prime})$ for all $i^{\prime}\in V$.
Thus the two runs will the identical from that point onward and
$|M|=|M_{-j}|+1$.∎

Since Lemma 5 implies Lemma 4, this yields Theorem 1.2 for graphs which
contain a perfect matching. But as in Section 2, we may drop this condition by
reducing a graph $G$ with a matching $M$ to the subgraph induced by the
vertices covered by $M$. Adding the vertices back in only increases the
performance of Fully Online Ranking by Lemma 5.

##  4 Online Vertex-Weighted Bipartite Matching

In this section we will consider a weighted extension of the Online Bipartite
Matching Problem which has been inspired by online advertising markets. In the
Online Vertex-Weighted Bipartite Matching Problem, we have a bipartite graph
$G=(S,B,E)$ with vertex weights $w:S\rightarrow\mathbb{R}_{+}$ on the offline
vertices. Here $S$ represents the advertisers and $B$ represents website
impressions or search queries which should get matched to ads from the
advertisers. The vertices $B$ arrive online in adversarial order and should
get matched to a neighbor $j$ such that the total weight of the matched
vertices in $S$ is maximized. This problem can be seen as a special case of
the AdWords Problem which instead imposes edge-weights and budgets on the
offline vertices.

Perhaps somewhat surprisingly it took 20 years for Ranking to be extended for
the unweighted to the vertex-weighted setting by Aggarwal et al. [1]. This is
because in the presence of weights, it is no longer enough to pick a uniformly
random permutation over the offline vertices. Instead, one has to skew the
permutation so that heavier vertices are more likely to appear first. This is
done elegantly in Algorithm 4 by ordering the vertices not by their $x_{j}$
but rather by the careful chosen quantity $w_{j}(1-e^{x_{j}-1})$.

1 for  _$j\in S$_ do

2 Sample a uniformly random $x_{j}\in[0,1]$.

3for  _each buyer $i$ who arrives_ do

4 Match $i$ to an unmatched $j\in N(i)$ maximizing
$w_{j}\left(1-e^{x_{j}-1}\right)$.

Algorithm 4 Vertex-Weighted Ranking

However, Algorithm 4 does not lend itself to a straight-forward analysis via
the method of bounded differences. This is because a vertex with small weight,
which should have little impact on the total weight of the matching, can
sometimes be chosen over a vertex with much larger weight. See the example
shown in Figure 1.

$j$$j^{\prime}$$i$$w_{j}=1$$w_{j^{\prime}}=10^{10}$ Figure 1: Shown is a
simple instance in which the value of $x_{j}$ can have a large impact on the
final matching despite the fact that $w_{j}$ is small. If $x_{j^{\prime}}\gg
1-10^{-10}$, $i$ will choose $j$ in line 4 for sufficiently small values of
$x_{j}$.

In particular, the problem lies with the fact that $w_{j}(1-e^{x_{j}-1})$ can
get arbitrarily close to 0 if $x_{j}$ gets close to 1. We will overcome this
problem by changing the function slightly. For any $\epsilon>0$ we consider
$\epsilon$-Ranking as shown in Algorithm 5.

1 for  _$j\in S$_ do

2 Sample a uniformly random $x_{j}\in[0,1]$.

3for  _each buyer $i$ who arrives_ do

4 Match $i$ to an unmatched $j\in N(i)$ maximizing
$w_{j}\left(1-e^{x_{j}-1-\epsilon}\right)$.

Algorithm 5 $\epsilon$-Ranking

In the following fix some instance $G=(S,B,E)$ with vertex-weights $w$ and
some $\epsilon>0$. Then we let $f:[0,1]^{S}\rightarrow\mathbb{R}$ represent
the total weight of the matching generated by Algorithm 5 with fixed samples
$x_{j}$. We will show that $\epsilon$-Ranking is still
$(1-\frac{1}{e}-\epsilon)$-competitive while also allowing us to give a
concentration bound.

To give a concise proof of the $(1-\frac{1}{e}-\epsilon)$-competitiveness we
will use the economic analysis by Eden et al. [5] which is itself based on the
primal-dual viewpoint due to Devanur et al. [3]. This analysis associates
random variables $r_{j}$ with all $j\in S$ and $u_{i}$ with $i\in B$. The idea
is that the value $w_{j}e^{x_{j}-1-\epsilon}$ represents the _price_ of $j$
and whenever a match between $i$ and $j$ is made, this is a _sale_. We will
then set $r_{j}$ (the _revenue_) to be $w_{j}e^{x_{j}-1-\epsilon}$ and $u_{i}$
(the _utility_) to be $w_{j}e^{x_{j}-1-\epsilon}$. If a vertex is never
matched, its revenue / utility will be zero.

###### Lemma 6

Using the notation from Lemma 3, we have that for all $j\in S$ and fixed
samples $x$,

$w(M_{-j})-\frac{2}{\epsilon}w_{j}\leq w(M)\leq w(M_{-j})+w_{j}.$

Additionally, for any $i\in B$, its utility $u_{i}$ in the run on $G$ will be
no less than in the run on $G_{-j}$.

###### Proof

For any buyers $i,i^{\prime}\in B$, let $N^{(i)}(i^{\prime})$ be the set of
neighbors of $i^{\prime}$ in $G$ which are unmatched by the time that $i$
arrives in the run of Algorithm 5 with the fixed values of $x$. Likewise, let
$N^{(i)}_{-j}(i^{\prime})$ be the set of unmatched neighbors of $i^{\prime}$
in the run of $\epsilon$-Ranking on $G_{-j}$ when $i$ arrives. We claim that
for all $i\in B$ there exists some $j^{\prime}\in S$ such that

$w_{j^{\prime}}(1-e^{x_{j^{\prime}}-1-\epsilon})\leq
w_{j}(1-e^{x_{j}-1-\epsilon})$

and for all $i^{\prime}\in B$, we have
$N^{(i)}(i^{\prime})=N^{(i)}_{-j}(i^{\prime})$ or
$N^{(i)}(i^{\prime})=N^{(i)}_{-j}(i^{\prime})\cup\\{j^{\prime}\\}$.

This claim is almost the same as in the proof of Lemma 3 and may likewise be
shown via induction. Note that the extra condition on $w_{j^{\prime}}$ holds
at the beginning where $j^{\prime}=j$ and continues to hold throughout the
induction because whenever $i$ matches to $j^{\prime}$, it can only free up
This clearly holds at the beginning where $j^{\prime}=j$ and whenever $i$
matches to $j^{\prime}$, it frees up a vertex $j^{\prime\prime}$ with

$w_{j^{\prime\prime}}(1-e^{x_{j^{\prime\prime}}-1-\epsilon})\leq
w_{j^{\prime}}(1-e^{x_{j^{\prime}}-1-\epsilon})$

due to the fact that $j^{\prime}$ was picked over $j^{\prime\prime}$ in line
5. If $i$ was not even matched in $G_{-j}$, we can simply set $j^{\prime}=j$
for the induction.

Now note that since $N^{(i)}_{-j}(i)\subseteq N^{(i)}(i)$ for all $i\in B$, we
always maximize over a larger set in line 5. Thus the utility of $i$ will be
no smaller in the run on $G$ compared to the run on $G_{-j}$.

On the other hand, let $T\subseteq S$ be the set of sellers matched in the run
on $G$ and let $T_{-j}\subseteq S\setminus\\{j\\}$ be the set of sellers
matched in the run on $G_{-j}$. Then we observe that $T\setminus
T_{-j}\subseteq\\{j\\}$ because for all $j^{\prime}\neq j$, if $j^{\prime}$
gets matched to $i$ in $M$, then either $j^{\prime}\in N^{(i)}_{-j}(i)$
implying that $i$ will match to $j^{\prime}$ in $M_{-j}$ , or $j^{\prime}$ was
already matched to some other vertex. In both cases, if $j^{\prime}\in T$ then
$j^{\prime}\in T_{-j}$. This implies that $w(M)\leq w(M_{-j})+w_{j}$.

We also have that $|T_{-j}\setminus T|\leq 1$. Simply imagine a buyer
$i^{\star}$ that arrives after all other buyers and has edges to all sellers.
Then by the claim, there exists some $j^{\prime}\in S$ such that

$(S\setminus\\{j\\})\setminus T_{-j}=N^{(i^{\star})}_{-j}(i^{\star})\subseteq
N^{(i^{\star})}(i^{\star})\cup\\{j^{\prime}\\}=S\setminus(T\cup\\{j^{\prime}\\})$

and so $T_{-j}\subseteq T\cup\\{j^{\prime}\\}$. This implies that $w(M)\geq
w(M_{-j})-w_{j^{\prime}}$.

Finally, we also know by the claim that
$w_{j^{\prime}}(1-e^{x_{j^{\prime}}-1-\epsilon})\leq
w_{j}(1-e^{x_{j}-1-\epsilon})$ which implies

$w_{j^{\prime}}\leq\frac{1}{1-e^{-\epsilon}}w_{j}\leq\frac{1}{\left(1-\frac{1}{e}\right)\epsilon}w_{j}\leq\frac{2}{\epsilon}w_{j}.$

Thus we have shown $w(M_{-j})-\frac{2}{\epsilon}w_{j}\leq w(M)\leq
w(M_{-j})+w_{j}$ as required.∎

######  Lemma 7 (Bounded Differences)

Let $x\in[0,1]^{S}$, $j^{\star}\in S$ and $\theta\in[0,1]$ be arbitrary.
Define $x^{\prime}_{j}$ to be $\theta$ if $j=j^{\star}$ and $x_{j}$ otherwise.
Then $|f(x)-f(x^{\prime})|\leq\left(1+\frac{2}{\epsilon}\right)w_{j^{\star}}$.

###### Proof

As in the proof of Lemma 2, we can simply remove $j^{\star}$ and apply Lemma
6. Then

$\displaystyle w(M_{-j^{\star}})-\frac{2}{\epsilon}w_{j^{\star}}$
$\displaystyle\leq f(x)\leq w(M_{-j^{\star}})+w_{j^{\star}},$ $\displaystyle
w(M_{-j^{\star}})-\frac{2}{\epsilon}w_{j^{\star}}$ $\displaystyle\leq
f(x^{\prime})\leq w(M_{-j^{\star}})+w_{j^{\star}}$

which implies the result.∎

###### Lemma 8

For any $\\{i,j\\}\in E$, we have
$\mathbb{E}[r_{j}+u_{i}]\geq(1-\frac{1}{e}-\epsilon)w_{j}$.

###### Proof

Fix all samples $x$ except for $x_{j}$. Then we can define $u^{*}$ to be the
utility of $i$ when $\epsilon$-Ranking is ran on $G_{-j}$. By Lemma 6, we know
that $u_{i}\geq u^{*}$, regardless of the value of $x_{j}$.

On the other hand, if $x_{j}$ is small enough that
$w_{j}(1-e^{x_{j}-1-\epsilon})>u^{*}$, then $j$ will definitely get matched
because if $j$ is not yet matched by the time that $i$ arrives, then clearly
$j$ will be chosen in line 5 of the algorithm and so it gets matched to $i$.
Now if $u^{*}$ is very small, this may be the case for all values of $x_{j}$
and in that case

$\mathbb{E}[r_{j}\mid
x_{-j}]\geq\int_{0}^{1}w_{j}e^{t-1-\epsilon}\,\mathrm{d}t=\left(1-\frac{1}{e}\right)e^{-\epsilon}w_{j}\geq\left(1-\frac{1}{e}-\epsilon\right)w_{j}.$

Otherwise there will be some value $z\in[0,1]$ such that
$w_{j}(1-e^{z-1-\epsilon})=u^{*}$ and then we can compute

$\mathbb{E}[r_{j}\mid
x_{-j}]\geq\int_{0}^{z}w_{j}e^{t-1-\epsilon}\,\mathrm{d}t=\left(1-\frac{1}{e}\right)w_{j}-u^{*}.$

But clearly, in both cases we have

$\mathbb{E}[r_{j}+u_{i}\mid x_{-j}]\geq\mathbb{E}[r_{j}\mid
x_{-j}]+u^{*}\geq\left(1-\frac{1}{e}-\epsilon\right)w_{j}$

and so in particular
$\mathbb{E}[r_{j}+u_{i}]\geq(1-\frac{1}{e}-\epsilon)w_{j}$ as claimed.∎

###### Lemma 9

$\epsilon$-Ranking is $(1-\frac{1}{e}-\epsilon)$-competitive.

###### Proof

Let $M^{*}$ be a maximum weight matching and let $M$ be the matching output by
$\epsilon$-Ranking. Notice that every time we match an edge in the algorithm,
we increase $\sum_{j\in S}r_{j}+\sum_{i\in B}u_{i}$ by exactly the weight of
the edge. Thus by Lemma 8,

$\displaystyle\mathbb{E}[w(M)]$ $\displaystyle=\mathbb{E}\left[\sum_{j\in
S}r_{j}+\sum_{i\in B}u_{i}\right]\geq\sum_{\\{i,j\\}\in
M^{*}}\mathbb{E}[r_{j}+u_{i}]$ $\displaystyle\geq\sum_{\\{i,j\\}\in
M^{*}}\left(1-\frac{1}{e}-\epsilon\right)w_{j}=\left(1-\frac{1}{e}-\epsilon\right)w(M^{*})$

and therefore $\epsilon$-Ranking is $(1-\frac{1}{e}-\epsilon)$-competitive.∎

Finally, we have the tools necessary to show Theorem 1.3 by combining Lemma 7
with Lemma 9.

###### Proof

Given some $\alpha>0$, we consider the algorithm $\frac{\alpha}{2}$-Ranking
which we know to be $(1-\frac{1}{e}-\frac{\alpha}{2})$-competitive by Lemma 9.
We apply Lemma 1 (McDiarmid’s inequality) with Lemma 7 (bounded differences).
This gives us

$\displaystyle\mathbb{P}\left[w(M)<\left(1-\frac{1}{e}-\alpha\right)w(M^{*})\right]$
$\displaystyle<e^{-2\frac{\alpha^{2}}{2}\frac{w(M^{*})^{2}}{(1+4/\alpha)^{2}||w||_{2}^{2}}}$
$\displaystyle\leq
e^{-\frac{\alpha^{4}}{50}\frac{w(M^{*})^{2}}{||w||_{2}^{2}}}$

where we use that $\alpha<1$ since otherwise the bound holds trivially. ∎

The results of this section may also be extended to a generalization of the
Online Vertex-Weighted Bipartite Matching Problem which is called the Online
Single-Valued Bipartite Matching Problem. The setup is almost identical in
that we still have a bipartite graph $G=(S,B,E)$ with vertex weights
$w:S\rightarrow\mathbb{R}_{+}$ on the offline vertices. However, now each
offline vertex $j$ also has a capacity $c_{j}\in\mathbb{N}$ that represents
how often it is allowed to be matched.

Clearly, Theorem 1.3 can be extended to this setting by simply creating
$c_{j}$ many copies of each offline vertex $j$. This can be done implicitly
and in a capacity-oblivious way by simply sampling a new $x_{j}$ every time
$j$ is matched during the Ranking (or $\epsilon$-Ranking) algorithm.

Recently, Vazirani [16] showed that this “resampling” is in fact not
necessary, i.e. that the same value of $x_{j}$ can be used for every copy of
$j$ while still achieving $(1-\frac{1}{e})$-competitiveness of Ranking; see
Algorithm 6.

1 for  _$j\in S$_ do

2 Sample a uniformly random $x_{j}\in[0,1]$.

3for  _each buyer $i$ who arrives_ do

4 Match $i$ to a $j\in N(i)$ which has been matched less than $c_{j}$ times,
maximizing $w_{j}\left(1-e^{x_{j}-1}\right)$.

Algorithm 6 Single-Valued Ranking

The main benefit of Algorithm 6 is that it uses fewer random bits than running
Ranking on the reduced instance with $c_{j}$ many copies of each offline
vertex $j$. However, it will accordingly be less tightly concentrated which
leads to a version of Theorem 1.3 in which the bound depends not on
$||w||_{2}^{2}$ but rather on $\sum_{j}(c_{j}w_{j})^{2}$. Thus we will not
pursue this approach here.

## Acknowledgements

We would like to thank Vijay Vazirani for helpful comments and feedback.

## References

  * [1] Aggarwal, G., Goel, G., Karande, C., Mehta, A.: Online vertex-weighted bipartite matching and single-bid budgeted allocations. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 1253–1264. SIAM (2011)
  * [2] Birnbaum, B., Mathieu, C.: On-line bipartite matching made simple. SIGACT News 39(1), 80–87 (2008). https://doi.org/10.1145/1360443.1360462, https://doi.org/10.1145/1360443.1360462
  * [3] Devanur, N.R., Jain, K., Kleinberg, R.D.: Randomized primal-dual analysis of ranking for online bipartite matching. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete algorithms. pp. 101–107. SIAM (2013)
  * [4] Dubhashi, D.P., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press (2009). https://doi.org/10.1017/CBO9780511581274
  * [5] Eden, A., Feldman, M., Fiat, A., Segal, K.: An economics-based analysis of RANKING for online bipartite matching. In: Le, H.V., King, V. (eds.) 4th Symposium on Simplicity in Algorithms, SOSA 2021. pp. 107–110. SIAM (2021). https://doi.org/10.1137/1.9781611976496.12, https://doi.org/10.1137/1.9781611976496.12
  * [6] Goel, G., Mehta, A.: Online budgeted matching in random input models with applications to AdWords. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 982–991 (2008)
  * [7] Huang, Z., Zhang, Q., Zhang, Y.: Adwords in a panorama. In: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). pp. 1416–1426. IEEE Computer Society, Los Alamitos, CA, USA (nov 2020). https://doi.org/10.1109/FOCS46700.2020.00133, https://doi.ieeecomputersociety.org/10.1109/FOCS46700.2020.00133
  * [8] Huang, Z., Kang, N., Tang, Z.G., Wu, X., Zhang, Y., Zhu, X.: How to match when all vertices arrive online. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. pp. 17–29 (2018)
  * [9] Huang, Z., Peng, B., Tang, Z.G., Tao, R., Wu, X., Zhang, Y.: Tight competitive ratios of classic matching algorithms in the fully online model. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 2875–2886. SIAM (2019)
  * [10] Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing. pp. 352–358 (1990)
  * [11] Komm, D., Královic, R., Královic, R., Mömke, T.: Randomized Online Algorithms with High Probability Guarantees. In: Mayr, E.W., Portier, N. (eds.) 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), vol. 25, pp. 470–481. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2014). https://doi.org/10.4230/LIPIcs.STACS.2014.470, http://drops.dagstuhl.de/opus/volltexte/2014/4480
  * [12] Leonardi, S., Marchetti-Spaccamela, A., Presciutti, A., Rosén, A.: On-line randomized call control revisited. SIAM Journal on Computing 31(1), 86–112 (2001). https://doi.org/10.1137/S0097539798346706, https://doi.org/10.1137/S0097539798346706
  * [13] McDiarmid, C.: On the method of bounded differences, p. 148–188. London Mathematical Society Lecture Note Series, Cambridge University Press (1989). https://doi.org/10.1017/CBO9781107359949.008
  * [14] Mehta, A., Saberi, A., Vazirani, U., Vazirani, V.: Adwords and generalized online matching 54(5), 22–es (Oct 2007). https://doi.org/10.1145/1284320.1284321, https://doi.org/10.1145/1284320.1284321
  * [15] Sedgewick, R.: Quicksort. Ph.D. thesis, Stanford University (May 1975)
  * [16] Vazirani, V.V.: Online bipartite matching and adwords (2021), https://arxiv.org/abs/2107.10777