# Rounding Bipartite Matchings Online without Loss
and with Optimal Randomness

Niv Buchbinder Supported in part by by Israel Science Foundation grant 2233/19
and United States - Israel Binational Science Foundation grant 2018352. Tel
Aviv University<EMAIL_ADDRESS>Joseph (Seffi) Naor Supported in
part by by Israel Science Foundation grant 2233/19 and United States - Israel
Binational Science Foundation grant 2018352. Technion<EMAIL_ADDRESS>David Wajc Supported in part by NSF Award CCF1812919, ONR award N000141912550,
and a gift from Cisco Research. Stanford University<EMAIL_ADDRESS>
# A Randomness Threshold for Online Bipartite Matching,
via Lossless Online Rounding

Niv Buchbinder Supported in part by by Israel Science Foundation grant 2233/19
and United States - Israel Binational Science Foundation grant 2018352. Tel
Aviv University<EMAIL_ADDRESS>Joseph (Seffi) Naor Supported in
part by by Israel Science Foundation grant 2233/19 and United States - Israel
Binational Science Foundation grant 2018352. Technion<EMAIL_ADDRESS>David Wajc Supported in part by NSF Award CCF1812919, ONR award N000141912550,
and a gift from Cisco Research. Stanford University<EMAIL_ADDRESS>
###### Abstract

Over three decades ago, Karp, Vazirani and Vazirani (STOC’90) introduced the
online bipartite matching problem. They observed that deterministic
algorithms’ competitive ratio for this problem is no greater than
$\nicefrac{{1}}{{2}}$, and proved that randomized algorithms can do better. A
natural question thus arises: _how random is random_? i.e., how much
randomness is needed to outperform deterministic algorithms? The ranking
algorithm of Karp et al. requires $\tilde{O}(n)$ random bits, which, ignoring
polylog terms, remained unimproved. On the other hand, Pena and Borodin
(TCS’19) established a lower bound of $(1-o(1))\log\log n$ random bits for any
$\nicefrac{{1}}{{2}}+\Omega(1)$ competitive ratio.

We close this doubly-exponential gap, proving that, surprisingly, this lower
bound is tight. In fact, we prove a _sharp threshold_ of $(1\pm o(1))\log\log
n$ random bits for the randomness necessary and sufficient to outperform
deterministic algorithms for this problem, as well as its vertex-weighted
generalization. Our work implies the same threshold for the advice complexity
(nondeterminism) of these problems.

Similar to recent breakthrough results in the online matching literature, for
the edge-weighted matching problem (Fahrbach et al. FOCS’20) and adwords
without the small bids assumption (Huang et al. FOCS’20), our algorithms break
the barrier of $\nicefrac{{1}}{{2}}$ by randomizing matching choices over two
neighbors. Unlike these works, our approach does not rely on the recently-
introduced OCS machinery, nor the more established randomized primal-dual
method. Instead, our work revisits a highly-successful online design
technique, which was nonetheless under-utilized in the area of online
matching, namely (lossless) online rounding of fractional algorithms. While
this technique is known to be hopeless for online matching in general, we show
that it is nonetheless applicable to carefully designed fractional algorithms
with additional (non-convex) constraints.

##  1 Introduction

We study the online bipartite matching problem and its vertex-weighted
generalization. Online bipartite matching was introduced three decades ago by
Karp, Vazirani, and Vazirani [35], who presented optimal deterministic and
randomized algorithms for this problem, i.e., with competitive ratios
$\nicefrac{{1}}{{2}}$ and $1-\nicefrac{{1}}{{e}}$, respectively. This problem
and its extensions have been widely studied over the years; see Mehta [38] for
a survey of earlier work, and for more recent developments see, e.g., [30, 34,
22, 33, 18, 25, 43, 29, 31]. This line of work has led to a deeper
understanding of the power of computation in online settings, and has
introduced a number of powerful algorithmic techniques. Most prominent among
these techniques is the randomized primal-dual framework of Devanur, Jain, and
Kleinberg [19], which has proven tremendously useful in recent years [30, 22,
33, 29, 28, 50, 37, 34, 31]. Despite the progress on many fundamental
questions in the area, many open questions still remain, both on the results
side, and on the techniques side. We address a number of such questions in
this paper, focusing on the following two.

The Power of Randomness and Nondeterminism. A core goal of online algorithms
research is determining the power of randomized algorithms compared to
deterministic algorithms. A refinement of this question is determining the
_amount_ of randomness needed to outperform deterministic algorithms. A
related question is studied in the advice model, introduced by Emek et al.
[21]. In this model a deterministic online algorithm is equipped with an
advice string, and the algorithm’s guarantees for any input are with respect
to the best advice string for the input. Non-deterministic advice bits are
always at least as powerful as random bits, and in many cases are strictly
more powerful [46, 47, 40, 9, 45, 10].

For online bipartite matching Karp et al. [35] proved that any deterministic
online bipartite matching algorithm is at best $\nicefrac{{1}}{{2}}$
competitive, and designed a $(1-\nicefrac{{1}}{{e}})$-competitive randomized
algorithm, using $\log(n!)=O(n\log n)$ bits of randomness. The amount of
randomness needed to outperform deterministic algorithms was slightly improved
later by [20], who gave a $(1-\nicefrac{{1}}{{e}}-\epsilon)$-competitive
algorithm using $O_{\epsilon}(n)$ random bits. On the other hand, Pena and
Borodin [45] showed that any algorithm which is
$(\nicefrac{{1}}{{2}}+\epsilon)$-competitive for any constant $\epsilon>0$
must use at least $(1-o(1))\log\log n$ advice bits, and hence at least that
amount of random bits.111All logarithms in this paper are to base $2$. The
best known bounds on the number of advice bits needed to outperform
deterministic algorithms for the problem are $O(\log n)$, using exponential
time, and $O(n)$, using polynomial time [9, 45, 20]. Closing these
(doubly-)exponential gaps between upper and lower bounds on the amount of
randomness and nondeterminism needed to outperform deterministic online
bipartite matching algorithms has remained a tantalizing open question.

######  Question 1.1.

How much randomness/advice is needed to achieve a
$(\nicefrac{{1}}{{2}}+\Omega(1))$ competitive ratio for online bipartite
matching?

The Power of (Online) Rounding. A very general and widely-used algorithmic
framework for the design of randomized online algorithms is the following two-
step approach: first, design an online algorithm for a fractional relaxation
of the problem, and then randomly round the fractional solution in an online
fashion. This approach has been highly successful, playing a pivotal role in
the resolution of many fundamental online problems, such as the $k$-server
problem [5, 12, 13, 36], weighted paging [6, 1], generalized caching [7, 1],
Metrical task systems [8, 11, 16], online set cover [3], online weighted
steiner tree [41], online edge coloring [17, 48], and more. However, this
design pattern has not been as helpful for the extensively-studied class of
online bipartite matching problems. This is surprising, given the integrality
of the bipartite matching polytope, implying that fractional bipartite
matchings can be rounded without loss. More formally, a lossless rounding
scheme is a polytime randomized algorithm that given a fractional bipartite
matching $\vec{x}$ outputs a matching $\mathcal{M}$ that satisfies

$\Pr[e\in\mathcal{M}]=x_{e}\qquad\forall e\in E.$ (1)

For the bipartite matching polytope such lossless rounding exists, and
moreover can satisfy strong and useful negative correlation properties [27].
Lossless rounding implies that the output matching’s value is as good as the
fractional matching, for any linear objective. Therefore, a similar _online_
rounding scheme combined with known fractional algorithms [23, 14, 51] would
result in improved/optimal randomized algorithms for many problems in this
area. Put otherwise, the lack of such rounding schemes poses a major obstacle
for the design of optimal randomized algorithms for edge-weighted online
matching [22], online matching with two-sided arrivals [25], and adwords
without the small bid assumption [33]. Unfortunately, as pointed out by [19,
18] (and elaborated in Section 1.2), such _online_ lossless rounding of
fractional bipartite matchings is in general _impossible_. Nevertheless, in
this work, we ask what can be salvaged from this seemingly hopeless approach
of (lossless) online rounding for bipartite matching problems.

###  1.1 Our Main Contributions

In this paper we initiate the study of lossless online rounding of fractional
bipartite matchings. As discussed above, such rounding is generally
impossible. However, in this paper, we argue (and show) that despite this
general impossibility, lossless online rounding is possible for competitive
fractional matchings which are designed _with rounding in mind_. Indeed, since
every randomized algorithm induces a fractional matching which, by
construction, is losslessly roundable, it is natural to search for roundable
fractional matching algorithms. We identify a non-trivial family of such
roundable algorithms. In particular, we design fractional algorithms which:

  1. 1.

Are better than $\nicefrac{{1}}{{2}}$-competitive.

  2. 2.

Are losslessly roundable, using polynomially-many random bits.

  3. 3.

Are near-losslessly roundable, using (optimal) $(1+o(1))\cdot\log\log n$
random bits.

Describing the fractional algorithms we consider requires some notation, which
we now provide. (For formal definitions, we refer the reader to Section 2.)
The input to the online matching problem is a bipartite graph, with the left
and right sides referred to as offline and online nodes, respectively. Each
offline node $i$ has weight $w_{i}>0$ (in the unweighted version $w_{i}=1$ for
all $i$). Initially, only the $n$ offline nodes are known. Online nodes arrive
sequentially. At times $t=1,2,\dots$, online node $t$ arrives. An online
matching algorithm must assign for each edge $(i,t)\in E$, immediately and
irrevocably, a fractional value $x_{i,t}\in[0,1]$ (or $x_{i,t}\in\\{0,1\\}$,
for integral algorithms). These values should satisfy that each node $v$ has
_fractional degree_ at most one, i.e., $\sum_{e\ni v}x_{e}\leq 1$. So, for
example, $x^{(t)}_{i}:=\sum_{t^{\prime}<t}x_{i,t^{\prime}}$, the fractional
degree of offline node $i$ before time $t$, satisfies $x^{(t)}_{i}\leq 1$. The
goal is to maximize the weighted value of the matching, $\sum_{i,t}w_{i}\cdot
x_{i,t}$. We focus on _two-choice_ algorithms, which, for any online node $t$
set $x_{i,t}>0$ for at most two offline nodes $i$. Such two-choice algorithms
were previously used to obtain breakthrough results breaking the barrier of
$\nicefrac{{1}}{{2}}$ for other online bipartite matching problems [22, 34].
On the other hand, prior work shows that two-choice are not, in general,
losslessly roundable online [18, 19].

The main new ingredient in our work is the following set of (non-convex)
constraints for fractional two-choice algorithms, which we motivate and
provide intuition for in Section 1.2.

######  Definition 1.2.

A two-choice fractional online matching algorithm $\mathcal{A}$ is _sound_ if
for every online node $t$ with $P_{t}:=\\{i\mid x_{i,t}>0\\}$, the fractional
matching $\vec{x}$ of $\mathcal{A}$ satisfies $\sum_{i\in P_{t}}x_{i,t}\leq
1-\prod_{i\in P_{t}}x^{(t)}_{i}.$ (2) If Equation 2 is met at equality for
each $t$, we say that $\mathcal{A}$ is also _maximal_.

Our main technical contribution is a proof that sound two-choice algorithms
can be rounded losslessly online.

######  Theorem 1.3 (Lossless Rounding).

Let $\mathcal{A}$ be a sound two-choice online fractional algorithm, and its
output be $\vec{x}$. Then, there exists a randomized online algorithm whose
output matching $\mathcal{M}$ matches each edge $(i,t)$ with probability
$\Pr[(i,t)\in\mathcal{M}]=x_{i,t}.$ Moreover, if $\mathcal{A}$ is maximal,
then this randomized online algorithm is implementable in poly-time.

Given the above rounding scheme, we ask whether such lossless (or near-
lossless) rounding can be implemented with less randomness. We show that this
is indeed possible for certain two-choice algorithms, which we refer to as
_$k$ -level $b$-bit algorithms_ (see Section 3.3 for definitions).

######  Theorem 1.4 (Low-Randomness Rounding).

Let $\mathcal{A}$ be a $k$-level $b$-bit fractional algorithm, with output
$\vec{x}$. Then, there exists a polytime randomized online algorithm using
$(1+o(1))\cdot\log\log n+b\cdot 2^{k+1}$ random bits, whose output matching
$\mathcal{M}$ matches each edge $(i,t)$ with probability
$\Pr[(i,t)\in\mathcal{M}]=x_{i,t}\pm o(1).$

The above rounding schemes are, of course, worthless without good accompanying
online fractional solutions. Fortunately, designing (deterministic) fractional
online algorithms is in general a much easier task than designing randomized
algorithms. However, adding the extra (non-convex) constraints of Definition
1.2 adds a new dimension of complexity, and requires somewhat non-standard
analysis (more on this later). We show that even with these extra constraints,
designing online fractional algorithms with good competitive ratios is
possible.

######  Theorem 1.5 (Fractional Algorithms).

There exist sound two-choice fractional algorithms that are: • -competitive
for online bipartite matching. • $k$-level $2^{k-1}$-bit, and
$(\ratio-O(2^{-2^{k}}))$-competitive for online bipartite matching. •
$2$-level $2$-bit, and $\nicefrac{{11}}{{21}}\approx 0.524$-competitive for
online vertex-weighted bipartite matching.

A Sharp Threshold for Randomness and Nondeterminism. Our main quantitative
result, obtained by combining theorems 1.4 and 1.5, are randomized algorithms
with a random seed of $(1+o(1))\log\log n$ bits which are -competitive and
$0.524$-competitive for the unweighted and vertex-weighted online bipartite
matching problem, respectively. Combing these upper bounds with the
$(1-o(1))\log\log n$ advice bits (and hence random bits) lower bound of [45],
this provides a sharp _threshold_ for the randomness needed to outperform
deterministic algorithms, and likewise for the advice complexity of this
problem. To conclude, we obtain the following sharp answer to 1.1 and its
vertex-weighted generalization.

######  Theorem 1.6.

$(1\pm o(1))\log\log n$ random (advice) bits are both necessary and sufficient
to achieve a competitive ratio of $(\nicefrac{{1}}{{2}}+\Omega(1))$ for online
vertex-weighted bipartite matching.

###  1.2 Techniques

In this section we give a high-level intuition and overview of our techniques
for lossless rounding two-choice algorithms. We first briefly recall the
motivation for such lossless rounding.

Motivation and challenges of lossless online rounding. The impossibility of
lossless online rounding was first observed by Devanur et al. [19]. (We refer
the unfamiliar reader to an illustrative example in Appendix A.)
Correspondingly, prior work applying rounding to online matchings [18, 25, 48,
44] studied _lossy_ rounding schemes. Given the delicate constants involved in
online (fractional) matching problems, for which optimal competitive ratios
are in the range $[\nicefrac{{1}}{{2}},1-\nicefrac{{1}}{{e}}]$, this approach
may cause the rounding to lose some of the poignancy of the fractional
results. For example, the lossy rounding of Gamlath et al. [25] rounds a
family of fractional algorithms for online matching in general graphs which
include a $0.526$-competitive algorithm [51], but only obtains a randomized
$\nicefrac{{1}}{{2}}+\epsilon$ competitive ratio, for some small constant
$\epsilon>0$. More importantly, lossy rounding cannot hope to obtain the
competitive ratios which are known to be achievable fractionally and
conjectured to be achievable randomly for many problems in the area [22, 23,
14, 22, 34, 25].

In this work we deviate from the lossy rounding approach, and show how to
round well-structured (competitive) fractional algorithms online,
_losslessly_. To this end, we revisit the design of fractional algorithms with
the explicit objective of losslessly rounding their output online.

What fractional solutions are roundable? Suppose we have managed to losslessly
round a fractional matching $\vec{x}$ until time $t$. Consequently, each
offline node is matched before time $t$ with probability $x_{i}^{(t)}$.
Suppose for now that these probabilities are independent. Then, since $t$ can
only be matched to a neighbor in $P_{t}:=\\{i\mid x_{i,t}>0\\}$ if at least
one node in $P_{t}$ is free at this point, we find that for lossless rounding
to be possible, we have

$\sum_{i\in P_{t}}x_{i,t}=\Pr[t\textrm{ matched}]\leq 1-\Pr[\textrm{all
}P_{t}\textrm{ matched before time }t]=1-\prod_{i\in P_{t}}x_{i}^{(t)}.$

Therefore, we have that $\sum_{i\in P_{t}}x_{i,t}\leq 1-\prod_{i\in
P_{t}}x_{i}^{(t)}$ is a _necessary condition_ for lossless rounding in this
scenario, where all offline nodes are matched independently. We say that our
fractional matchings are _sound_ precisely since this inequality is a
necessary condition for lossless rounding. For two-choice algorithms (i.e.,
with $|P_{t}|\leq 2$), it is not hard to match edges of $t$ with marginal
probabilities $x_{i,t}$, assuming $\vec{x}$ is sound and the matched statuses
of offline nodes are independent. Rounding becomes a challenge when there are
(possibly) correlations between these offline nodes.

Dealing with correlations. In general, the matched status of offline nodes may
depend on each other in intricate ways, based on the rounding so far. Positive
correlations between nodes in $P_{t}$ may cause the probability of all $P_{t}$
being matched before time $t$ to be strictly greater than $\prod_{i\in
P_{t}}x_{i}^{(t)}$. This would rule out lossless rounding of maximal sound
algorithms, as it would imply the following.

$\Pr[t\textrm{ matched}]=\sum_{i\in P_{t}}x_{i,t}=1-\prod_{i\in
P_{t}}x_{i}^{(t)}>1-\Pr[\textrm{all $P_{t}$ matched before time }t].$

However, _negative dependence_ between the matched status of offline nodes in
$P_{t}$ would still be consistent with matching edges of $t$ with marginal
probabilities $x_{i,t}$ output by a sound algorithm. Indeed, such dependence
(and lossless rounding up to time $t$) would guarantee the necessary condition
for lossless online rounding, namely $\Pr[t\textrm{ matched}]\leq
1-\Pr[\textrm{ all $P_{t}$ matched before time $t$}]$:

$\Pr[t\textrm{ matched}]=\sum_{i\in P_{t}}x_{i,t}\leq 1-\prod_{i\in
P_{t}}x_{i}^{(t)}\leq 1-\Pr[\textrm{all $P_{t}$ matched before time }t].$

Accordingly, the crux of our rounding algorithm for sound two-choice
algorithms is in designing a way of matching edges of $t$ that simultaneously:
(1) guarantees the marginal probabilities, and (2) preserves pairwise negative
correlations between the matched status of different nodes. The second
requirement is challenging to prove directly, and we end up proving
significantly stronger forms of negative correlation between offline nodes to
obtain our guarantees.

Our negative correlation properties. Let $F_{i,t}$ be an indicator for offline
node $i$ being free (unmatched by the rounding algorithm) by time $t$, and let
$F_{I,t}:=\bigwedge_{i\in I}F_{i,t}$ be an indicator for all of offline node-
set $I$ being free at time $t$. In addition to satisfying the target marginal
probabilities, our algorithm also satisfies the following strong negative
correlation property

$\displaystyle\Pr[F_{i,t}\mid F_{K,t}]\leq\Pr[F_{i,t}\mid
F_{J,t}]\qquad\forall t,\,\forall i\in[n],\,\forall J\subseteq
K\subseteq[n]\setminus\\{i\\}\textrm{ s.t.}\Pr[F_{K,t}]>0.$

In words, the probability of node $i$ to be free at time $t$ decreases when we
condition on a larger set of other offline nodes being free at that time. This
strong negative correlation property, while natural, is not shared by prior
online bipartite matching algorithms.222E.g., the ranking algorithm of Karp et
al. [35] is easily seen to induce _positively_ correlated variables
$\\{F_{i,t}\\}_{i}$. If the fractional matching $x$ is also maximal, our
rounding algorithm satisfies the stronger invariant that at any time $t$,
offline nodes in every set $I$ are either matched independently, or at least
one node in $I$ must be matched, i.e., $\Pr[F_{I,t}]\in\left\\{0,\,\prod_{i\in
I}\Pr[F_{i,t}]\right\\}.$ We believe that the strong negative correlation
properties of our rounding algorithms (both strong enough to imply exponential
tail bounds, similarly to known offline lossless rounding schemes [26]) are of
independent interest, and might find uses beyond this work.

Low-randomness implementation. A surprising useful property of our lossless
online rounding scheme is that for particularly well-structured fractional
algorithms, which we refer to as $k$-level algorithms (see Section 3.3), the
number of random variables of our rounding algorithm which any node’s matched
status depends on is constant. This property, combined with the theory of
small-bias distributions (see Section 2) allows us to implement our rounding
scheme for these algorithms with little randomness. This low-randomness
rounding, applied to the competitive $k$-level algorithms which we design in
Section 4, underlies our qualitative results of 1.6.

######  Remark 1.7 (Generalization to $d$-choice algorithms).

Given the above discussion, it is reasonable to suspect that Condition (2) is
sufficient for lossless online rounding of $d$-choice algorithms for $d>2$.
Surprisingly, in Appendix B, we show that this condition is _not_ sufficient
for lossless online rounding even when $d=3$. Our work therefore suggests the
following question.

######  Question 1.8.

What is a sufficient condition for (good) fractional algorithms to be
(efficiently) losslessly roundable online?

###  1.3 Further Related Work

Following the seminal work of Karp et al. [35], extensions and generalizations
of the online bipartite matching problem were widely studied. In 2005, Mehta
et al. [39] introduced the adwords problem and drew attention to the
connection between online matching and its extensions to Internet advertising,
which sparked a flurry of research in this field. Furthermore, [39] gave an
(optimal) $(1-1/e)$-competitive algorithm for the adwords problem under the
small-bid assumption; Buchbinder et al. [14] obtained the same result via the
online primal-dual method, and also presented an optimal fractional algorithm
for the problem (without assumptions). A similar $1-\nicefrac{{1}}{{e}}$
competitive ratio was obtained for the vertex-weighted bipartite matching
problem [2]. For edge-weighted matching, a $1-\nicefrac{{1}}{{e}}$ fractional
algorithm was given by [23]. In a celebrated recent result, the barrier of
$\nicefrac{{1}}{{2}}$ for randomized (integral) algorithms was broken by
Fahrbach et al. [22]. A similar first super-deterministic randomized algorithm
was recently achieved for adwords without the small-bids assumption [34]. For
both problems, as well as for online matching in more general arrivals ([25,
29, 31, 51]), online rounding has the potential to improve the state of the
art further, and possibly even yield optimal competitive ratios, if lossless
rounding is achievable.

##  2 Preliminaries

In the online bipartite matching problem, the underlying input is a bipartite
graph $G=(L,R,E)$. Initially, only the $n$ offline nodes (nodes), $L=[n]$, are
known, as well as the weight $w_{i}>0$ of each offline node $i\in L$. At times
$t=1,2,\dots$, online node $t\in R$ arrives, together with its edges.

A fractional online matching algorithm, at each time $t$, must decide,
immediately and irrevocably, what values $x_{i,t}$ to assign edges $(i,t)\in
E$, while guaranteeing that the _fractional degree_ of each vertex $v\in L\cup
R$ satisfies $\sum_{e\ni v}x_{e}\leq 1$. We denote by
$x^{(t)}_{i}:=\sum_{t^{\prime}<t}x_{i,t^{\prime}}$ the fractional degree of
vertex $i$ before time $t$, and by $x_{t}:=\sum_{i}x_{i,t}$ the fractional
degree of vertex $t$. Thus, a fractional online algorithm guarantees that
$x_{t}\leq 1$ and $x^{(t)}_{i}\leq 1$ for any time $t$ and offline vertex $i$.
Thus, such an algorithm maintains a feasible solution to the fractional
(vertex-weighted) matching problem, whose linear programming relaxation is
given (together with its dual) in Figure 1.

Primal | Dual
---|---
maximize | $\sum_{(i,t)\in E}w_{i}\cdot x_{it}$ | minimize | $\sum_{i\in L}{y_{i}}+\sum_{t\in R}{y_{t}}$
subject to: |  | subject to: |
$\forall i\in L$: | $\sum_{t}x_{i,t}\leq 1$ |  $\forall(i,t)\in E$: | $y_{i}+y_{t}\geq w_{i}$
$\forall t\in R$: | $\sum_{i}x_{i,t}\leq 1$ |  $\forall i\in L$: | $y_{i}\geq 0$
$\forall(i,t)\in E$: | $x_{i,t}\geq 0$ |  $\forall t\in R$: | $y_{t}\geq 0$
Figure 1: The fractional vertex-weighted bipartite matching LP and its dual

The analysis of our fractional algorithms uses these LPs and the well-
established online primal-dual method [15]. The challenge in the analysis is
dealing with the non-convex Constraint (2).

##### Bounded Independence.

A useful notion we will make use of is $(\delta,k)$-dependence, introduced by
Naor and Naor [42], generalizing $k$-wise independence.

######  Definition 2.1 ([42]).

Binary random variables $Y_{1},Y_{2},\dots,Y_{m}$ are _$(\delta,k)$
-dependent_ if for any subset of $k$ or fewer indices, $I\subseteq[m]$,
$|I|\leq k$,

$\sum_{\vec{v}\in\\{0,1\\}^{|I|}}\left|\Pr\left[\bigwedge_{i\in
I}(Y_{i}=v_{i})\right]-2^{-|I|}\right|\leq\delta.$

A $(0,k)$-dependent distribution is _$k$ -wise independent_, satisfying that
any subset of $k$ or fewer variables is independent. More generally, a joint
distribution $\vec{Y}$ is $(\delta,k)$-dependent if for any subset
$I\subseteq[m]$ of $k$ or fewer variables, the total variation distance
between the distribution on the variables indexed by $I$ and the uniform
distribution on $|I|$ i.i.d bernoulli($\nicefrac{{1}}{{2}}$) variables is at
most $\delta$. Consequently, such a distribution satisfies the following.

######  Lemma 2.2.

Let $\mathcal{U}$ be the uniform distribution and let $\mathcal{D}$ be a
$(\delta,k)$-dependent distribution over $m$ binary variables
$Y_{1},Y_{2},\dots,Y_{m}$. Then, for any event $A$ which is determined by $k$
or fewer random variables in $Y_{1},Y_{2},\dots,Y_{m}$,

$\Pr_{\vec{Y}\sim\mathcal{U}}[A]-\delta\leq\Pr_{\vec{Y}\sim\mathcal{D}}[A]\leq\Pr_{\vec{Y}\sim\mathcal{U}}[A]+\delta.$

###### Proof.

Let $I\subseteq[m]$ be a set of $k$ or fewer indices such that $\\{Y_{i}\mid
i\in I\\}$ determine $A$, and let $S\subseteq 2^{|I|}$ be such that
$A=\bigcup_{\vec{v}\in S}\left[\vec{Y}=\vec{v}\right]$. Then, by triangle
inequality and definition of $(\delta,k)$-dependence,

$\displaystyle\left|\Pr_{\vec{Y}\sim\mathcal{D}}[A]-\Pr_{\vec{Y}\sim\mathcal{U}}[A]\right|$
$\displaystyle\leq\sum_{\vec{v}\in S}\left|\Pr\left[\bigwedge_{i\in
I}(Y_{i}=v_{i})\right]-2^{-|I|}\right|\leq\sum_{\vec{v}\in\\{0,1\\}^{|I|}}\left|\Pr\left[\bigwedge_{i\in
I}(Y_{i}=v_{i})\right]-2^{-|I|}\right|\leq\delta.~{}~{}~{}~{}\qed$

A useful property of $(\delta,k)$-dependent distributions is that such
distributions can be specified—and constructed in polynomial time—using a
small random seed [42, 49]. For completeness, a proof of this lemma, following
the construction of Naor and Naor [42], is given in Appendix E.

######  Lemma 2.3.

For any $\delta>0$, a $(\delta,k)$-dependent joint distribution on $n$ binary
variables can be constructed using $\log\log n+O(k+\log(\frac{1}{\delta}))$
random bits. Moreover, after polytime preprocessing, each random variable in
this distribution can be sampled in $O(k\cdot\log n)$ time.

##  3 Rounding, and an FKG-like Inequality

In this section we show how to round losslessly two-choice sound fractional
solutions online, proving 1.3 and 1.4. In Section 3.1 and Section 3.2 we
present the lossless rounding algorithm, and prove its properties. In Appendix
C an analysis of a special case of our algorithm for _maximal_ 2-choice sound
algorithms, which, while less general, has the advantage of being simpler to
describe, having stronger negative correlation properties, and allowing for a
polytime implementation. In Section 3.3 we then prove that this algorithm can
be implemented with $o(1/n^{2})$ additive loss per edge using
$(1+o(1))\log\log n$ bits of randomness.

###  3.1 The Algorithm and its Invariants

In this section we design our lossless rounding algorithm. We are given a
$2$-choice fractional algorithm that satisfies property (2) meaning that for
any online node $t$, $\sum_{i\in P_{t}}x_{i,t}\leq 1-\prod_{i\in
P_{t}}x^{(t)}_{i}$. Let $F_{i,t}$ be the event that offline node $i$ is free
(unmatched in $\mathcal{M}$) by time $t$, and let $F_{I,t}:=\bigwedge_{i\in
I}F_{i,t}$ be the event that all nodes in $I\subseteq[n]$ are free by time
$t$. Our online rounding algorithm maintains the following two invariants for
any time $t$.

$\displaystyle\Pr[(i,t)\in\mathcal{M}]$ $\displaystyle=x_{i,t}$
$\displaystyle\qquad\forall(i,t)\in E$ (3) $\displaystyle\Pr[F_{i,t}\mid
F_{K,t}]$ $\displaystyle\leq\Pr[F_{i,t}\mid F_{J,t}]$
$\displaystyle\qquad\forall t,\,\forall i\in[n],\,\forall J\subseteq
K\subseteq[n]\setminus\\{i\\}\textrm{ s.t.}\Pr[F_{K,t}]>0$ (4)

The first condition is precisely losslessness, while the second monotonicity
property is precisely log-submodularity of the function $f(I):=\Pr[F_{I,t}]$,

$\log\Pr[F_{K+i,t}]-\log\Pr[F_{K,t}]\leq\log\Pr[F_{J+i,t}]-\log\Pr[F_{J,t}].$

Equivalently, this is a (reverse) FKG-like lattice condition [24],

$\Pr[F_{A\cap B,t}]\cdot\Pr[F_{A\cup B,t}]\leq\Pr[F_{A,t}]\cdot\Pr[F_{B,t}].$

Invariant (4) implies negative pairwise correlation between the $F_{i,t}$
variables, i.e., $\Pr[F_{i,t},F_{j,t}]\leq\Pr[F_{i,t}]\cdot\Pr[F_{j,t}]$ for
all $i\neq j,$ and hence between these variables’ complements,
$M_{i,t}:=1-F_{i,t}$, i.e.,
$\Pr[M_{i,t},M_{j,t}]\leq\Pr[M_{i,t}]\cdot\Pr[M_{j,t}]$. Therefore, combining
Condition (2) with Invariants (3) and (4) we obtain the following bound on the
probability of any online node $t$ being matched.

$\Pr[t\textrm{ matched}]\stackrel{{\scriptstyle\eqref{invariant:marginals-non-
maximal}}}{{=}}\sum_{i\in P_{t}}x_{i,t}\stackrel{{\scriptstyle\eqref{rounding-
weaker-condition}}}{{\leq}}1-\prod_{i\in
P_{t}}x^{(t)}_{i}\stackrel{{\scriptstyle\eqref{invariant:marginals-non-
maximal}}}{{=}}1-\prod_{i\in
P_{t}}\Pr[M_{i,t}]\stackrel{{\scriptstyle\eqref{invariant:FKG}}}{{=}}1-\Pr\left[\bigwedge_{i\in
P_{t}}M_{i,t}\right].$

The conclusion of this chain of inequalities, whereby $\Pr[t\textrm{
matched}]\leq 1-\Pr\left[\bigwedge_{i\in
P_{t}}M_{i,t}\right]=1-\Pr[\textrm{all nodes in $P_{t}$ matched before time
$t$}]$, is a trivial necessary condition for any randomized matching
algorithm. We show that the conditions we impose on our fractional solution,
together with the invariants we maintain, allow us to inductively maintain
these properties, while outputting a randomized matching, online.

We next describe formally the algorithm. Assume without loss of generality
that online node $t$ increases two neighbors: $1,2$. Let
$x_{1}:=x^{(t)}_{1},x_{2}:=x^{(t)}_{2}$ be their fractional values, and
$\Delta x_{1}:=x_{1,t},\Delta x_{2}:=x_{2,t}$ be their change. By the
properties of the fractional agorithm we are guaranteed that we have that
$\Delta x_{1}+\Delta x_{2}\leq 1-x_{1}x_{2}$. Our pseudocode is given in
Algorithm 1.

Algorithm 1 Online Lossless Rounding

1:for arrival of online node $t$ do

2: if $t$ has less than two neighbors then

3: add two dummy neighbors $i$ with $\Delta x_{i}=0$ and $x_{i}=1$ $\rhd$ used
to simplify notation

4: let $P_{t}:=\\{1,2\\}$ be the two neighbors of $t$ of highest $\Delta
x_{i}:=x_{i,t}$, and let $x_{i}:=x_{i}^{(t)}$

5: let $p_{12}:=\Pr[F_{\\{1,2\\},t}]$ $\rhd$ assuming $p_{12}$ is known

6: let $a_{1},a_{2},b_{1},b_{2}$ be solutions to Program (Prob-Program) with
input $\Delta x1,\Delta x_{2},x_{1},x_{2},p_{12}$

7: if $1,2$ are both free then

8: match $t$ to $1$ with probability $a_{1}$ and to $2$ with probability
$a_{2}$

9: else if a single $i\in\\{1,2\\}$ is free then

10: match $t$ to $i$ with probability $b_{i}$

Probability-Setting Program($\Delta x1,\Delta x_{2},x_{1},x_{2},p_{12}$):

(Prob-Program) $\displaystyle a_{1}+a_{2}$ $\displaystyle\leq 1$ (5)
$\displaystyle a_{i}$ $\displaystyle\geq 0$ $\displaystyle\forall i=1,2$ (6)
$\displaystyle b_{i}$ $\displaystyle\leq 1$ $\displaystyle\forall i=1,2$ (7)
$\displaystyle b_{i}$ $\displaystyle\geq a_{i}$ $\displaystyle\forall i=1,2$
(8) $\displaystyle b_{i}$ $\displaystyle\leq\frac{a_{i}}{1-a_{3-i}}$
$\displaystyle\forall i=1,2$ (9) $\displaystyle a_{i}\cdot
p_{12}+b_{i}\cdot(1-x_{i}-p_{12})$ $\displaystyle=\Delta x_{i}$
$\displaystyle\forall i=1,2$ (10)

We first show that the algorithm’s steps at time $t$ are well-defined,
provided our claimed invariants hold until this time.

######  Lemma 3.1.

Assuming invariants (3) and (4) hold before time $t$, then the algorithm’s
steps at time $t$ are well-defined. In particular, Program (Prob-Program) is
solvable (efficiently). Consequently,

  1. 1.

$a_{1}+a_{2}\leq 1$ and $a_{i}\geq 0$ for all $i=1,2$. (8 is well-defined)

  2. 2.

$b_{i}\in[a_{i},1]\subseteq[0,1]$ for all $i=1,2$. (10 is well-defined)

###### Proof.

Properties 1 and 2 follow from constraints (5), (6), (7) and (8) of Program
(Prob-Program). It remains to prove that this program is (efficiently)
solvable, which we do using the following algorithm. Initially, we set
$a_{i},b_{i}\leftarrow\Delta x_{i}/(1-x_{i})$ for both $i=1,2$. If
$\sum_{i}\Delta x_{i}/(1-x_{i})\leq 1$, we terminate, as this solution
satisfies all the constraints of Program (Prob-Program), with the non-trivial
constraints following from the fractional matching constraints implying
$\Delta x_{i}/(1-x_{i})\in[0,1]$. Otherwise, for $i=1,2$, we decrease $a_{i}$
and increase $b_{i}$ while maintaining Equation 10, until $a_{1}+a_{2}=1$ or
$b_{i}=1$.333This algorithm, which we state as a continuous algorithm, is
trivial to discretize and implement in constant time. We note that one of the
two stopping conditions will occur. Indeed, if we set $a_{i}=0$, then, since
$a_{3-i}\leq\Delta x_{3-i}/(1-x_{3-i})\leq 1$, we have that $a_{1}+a_{2}\leq
1$. We conclude that by the algorithm’s termination, constraints (5) and (6)
and (7) are satisfied. Moreover, by construction (of the algorithm), the
equality constraint (10) is satisfied. From this, we obtain the following.

$\displaystyle
a_{i}\cdot\frac{p_{12}}{1-x_{i}}+b_{i}\cdot\frac{1-x_{i}-p_{12}}{1-x_{i}}$
$\displaystyle=\frac{\Delta x_{i}}{1-x_{i}}.$ (11)

Now, by invariants (3) and (4), we have that $p_{12}=Pr[F_{\\{1,2\\},t}]\leq
Pr[F_{1,t}]\cdot Pr[F_{2,t}]=(1-x_{1})(1-x_{2})$. Therefore,
$p_{12}\leq(1-x_{i})$ and so Equation 11 implies that $\Delta x_{i}/(1-x_{i})$
is a convex combination of $a_{i}$ and $b_{i}$. Since we initialize
$a_{i},b_{i}\leftarrow\Delta x_{i}/(1-x_{i})$, and decrease $a_{i}$ while
increasing $b_{i}$, we obtain $b_{i}\geq\Delta x_{i}/(1-x_{i})\geq a_{i}$,
implying Constraint (8). Finally, to prove Constraint (9), we show that if
$\sum_{i}\Delta x_{i}/(1-x_{i})>1$, then $a_{1}+a_{2}=1$, and so Constraint
(9) follows from Constraint (7), since $a_{i}/(1-a_{3-i})=1$. Indeed, if
$a_{1}+a_{2}>1$ by the algorithm’s termination, then we must have stopped both
iterations of the loop decreasing $a_{i}$ and increasing $b_{i}$ after
reaching $b_{i}=1$. But then, we have

$\displaystyle\Delta x_{1}+\Delta x_{2}$
$\displaystyle=b_{1}\cdot(1-x_{1}-p_{12})+a_{1}\cdot
p_{12}+b_{2}\cdot(1-x_{2}-p_{12})+a_{2}\cdot p_{12}$
$\displaystyle=(1-x_{1})+(1-x_{2})+(a_{1}+a_{2}-2)\cdot p_{12}$ $\displaystyle
b_{1}=b_{2}=1$ $\displaystyle>(1-x_{1})+(1-x_{2})-p_{12}$ $\displaystyle
a_{1}+a_{2}>1$ $\displaystyle\geq(1-x_{1})+(1-x_{2})-(1-x_{1})(1-x_{2})$ inv.
(3) and (4) $\displaystyle=1-x_{1}\cdot x_{2},$

thus contradicting Condition (2), i.e., $\Delta x_{1}+\Delta x_{2}\leq
1-x_{1}\cdot x_{2}$. We conclude that this algorithm terminates with a
feasible solution to (Prob-Program), and thus Algorithm 1 is well-defined. ∎

###  3.2 Lossless Rounding using Algorithm 1

So far, we have proven that assuming the claimed invariants—(3) and (4)—hold
prior to time $t$, then Algorithm 1 is well defined. We now prove that if
these invariants hold prior to time $t$, then they likewise hold prior to time
$t+1$.

For our proof we will need the following simple corollary of Bayes’ Law.

######  Observation 3.2.

If $(A,B)\bot(C,D)$, (i.e., $(A,B)$ and $(C,D)$ are independent), then

$\Pr[A,C\mid B,D]=\Pr[A\mid B]\cdot\Pr[C\mid D].$

The special case of $\Pr[C]=1$ implies that if $D\bot(A,B)$, then $\Pr[A\mid
B,D]=\Pr[A\mid B].$

###### Proof.

By Bayes’ Law, we have that

$\displaystyle\Pr[A,C\mid B,D]$
$\displaystyle=\frac{\Pr[A,B,C,D]}{\Pr[B,D]}=\frac{\Pr[A,B]\cdot\Pr[C,D]}{\Pr[B]\cdot\Pr[D]}=\Pr[A\mid
B]\cdot\Pr[C\mid D].\qed$

######  Lemma 3.3.

Algorithm 1 satisfies Invariants (3) and (4).

###### Proof.

First, we prove Invariant (3). Fix a time $t$. By construction (of the
algorithm) we trivially have $\Pr[(i,t)\in\mathcal{M}]=0$ for all $i$ with
$\Delta x_{i}=0$. Now, let $P_{t}=\\{1,2\\}$ be as in 4, and let $i\in P_{t}$.
Then, by our choice of $a_{i},b_{i}$, and Constraint (10), the probability $i$
is matched to $t$ is precisely

$\displaystyle\Pr[(i,t)\in\mathcal{M}]$
$\displaystyle=\Pr[(i,t)\in\mathcal{M},F_{P_{t},t}]+\Pr[(i,t)\in\mathcal{M},F_{i,t},\overline{F_{3-i,t}}]$
$\displaystyle=a_{i}\cdot p_{12}+b_{i}\cdot(p_{1}-p_{12})=\Delta x_{i}.$

We now turn to proving Invariant (4). We prove this invariant holds for all
tuples $(i,J,K,t)$, by induction on $t$. The invariant clearly holds for
$t=1$. Assume the invariant holds for time $t\geq 1$. We prove that this
implies the same for time $t+1$. For the inductive step, when wishing to prove
Invariant (4) for the tuple $(i,J,K,t+1)$, we may safely assume that both
$\Pr[F_{K,t}]\neq 0$ and $\Pr[F_{K\cup\\{i\\},t}]\neq 0$ hold. Indeed, the
converse would imply that
$\Pr[F_{K\cup\\{i\\},t+1}]\leq\Pr[F_{K\cup\\{i\\},t}]=0$, in which case
Invariant (4) holds trivially for this tuple.

Let $E_{i}$ denote the event that the algorithm does not match $(i,t)$ at time
$t$. We further denote by $C_{1}\sim\mathrm{Ber}(a_{1})$ and
$C_{2}\sim\mathrm{Ber}(a_{2})$ the Bernoulli random variables corresponding to
the probability of matching $t$ to $1$ and $2$, respectively, in 8, if both
$1$ and $2$ are free at time $t$. We can imagine our algorithm tosses these
(correlated) coins regardless of the event $F_{\\{1,2\\},t}$, and only
inspects these variables if the event $F_{\\{1,2\\},t}$ occurs. We note that
the random variables $C_{1}$ and $C_{2}$ are independent of all events
determined by random choices made by the algorithm until time $t$.

With this notation and these observations at hand, we now turn to proving the
desired invariant holds for the tuple $(i,J,K,t+1)$. There are five cases to
consider, based on the inclusions between $P_{t}=\\{1,2\\}$ and
$K\cup\\{i\\}$, where if $i\in\\{1,2\\}$, we assume without loss of generality
that $i=1$.

##### Case 1: $\\{1,2\\}\cap(K\cup\\{i\\})=\emptyset$.

In this case $F_{I,t+1}\equiv F_{I,t}$ for all $I\subseteq K\cup\\{i\\}$, and
so the invariant follows trivially from the inductive hypothesis.

##### Case 2: $\\{1,2\\}\subseteq K$:

By the inductive hypothesis, and independence of $(C_{1},C_{2})$ from
$F_{i,t}$, we obtain the desired inequality for the tuple $(i,J,K,t+1)$.

$\displaystyle\Pr[F_{i,t+1}\mid F_{J,t+1}]=\Pr[F_{i,t}\mid
F_{J,t}]\geq\Pr[F_{i,t}\mid F_{K,t}]=\Pr[F_{i,t+1}\mid F_{K,t+1}].$

Here, the equalities follow from $F_{i,t}\equiv F_{i,t+1}$ and
$F_{i,t}\bot(C_{1},C_{2})$ together with 3.2, while the inequality follows
from the inductive hypothesis.

##### Case 3: $\\{1,2\\}\cap K=\emptyset,i=1$.

For this case we rely on the probability of $1$ not being matched decreasing
when we condition on a larger set of offline nodes being free, as in the
following inequality.

$\displaystyle\Pr[E_{1}\mid F_{K\cup\\{1\\},t}]\leq\Pr[E_{1}\mid
F_{J\cup\\{1\\},t}].$ (12)

Indeed, subtracting $\Pr[E_{1}\mid F_{J\cup\\{1\\},t}]$ from both sides,
expanding both terms using the law of total probability, we get

$\displaystyle\Pr[E_{1}\mid F_{K\cup\\{1\\},t}]-\Pr[E_{1}\mid
F_{J\cup\\{1\\},t}]$ $\displaystyle=$ $\displaystyle\Pr[E_{1}\mid
F_{\\{1,2\\},t}]\cdot\Big{(}\Pr[F_{2,t}\mid
F_{K\cup\\{1\\},t}]-\Pr[F_{2,t}\mid F_{J\cup\\{1\\},t}]\Big{)}$
$\displaystyle+$ $\displaystyle\Pr[E_{1}\mid
F_{1,t},\overline{F_{2,t}}]\cdot\Big{(}\Pr[\overline{F_{2,t}}\mid
F_{K\cup\\{1\\},t}]-\Pr[\overline{F_{2,t}}\mid F_{J\cup\\{1\\},t}]\Big{)}$
$\displaystyle=$ $\displaystyle((1-a_{1})-(1-b_{1}))\cdot(\Pr[F_{2,t}\mid
F_{K\cup\\{1\\},t}]-\Pr[F_{2,t}\mid F_{J\cup\\{1\\},t}])~{}\leq~{}0.$ (13)

Here, the second equality follows from $\Pr[E_{1}\mid
F_{\\{1,2\\},t}]=1-a_{1}$ and $\Pr[E_{1}\mid
F_{1,t},\overline{F_{2,t}}]=1-b_{1}$ by definition. For any event $A$,
$\Pr[F_{2,t}\mid A]+\Pr[\overline{F_{2,t}}\mid A]=1$, implying

$\Pr[F_{2,t}\mid F_{K\cup\\{1\\},t}]-\Pr[F_{2,t}\mid
F_{J\cup\\{1\\},t}]=-(\Pr[\overline{F_{2,t}}\mid
F_{K\cup\\{1\\},t}]-\Pr[\overline{F_{2,t}}\mid F_{J\cup\\{1\\},t}]).$

Finally, Inequality (13) follows from Constraint (8) implying that
$(1-a_{1})-(1-b_{1})\geq 0$, and by the inductive hypothesis together with the
assumption that $\Pr[F_{K\cup\\{1\\},t}]\neq 0$ implying that $\Pr[F_{2,t}\mid
F_{K\cup\\{1\\},t}]-\Pr[F_{2,t}\mid F_{J\cup\\{1\\},t}]\leq 0$. We conclude
that Equation 12 holds.

The desired inequality of Invariant (4) for the tuple $(i,J,K,t+1)$ then
follows from Equation 12, the inductive hypothesis and the assumption that
$\Pr[F_{K,t}]\neq 0$, implying

$\displaystyle\Pr[F_{1,t+1}\mid F_{K,t+1}]$ $\displaystyle=\Pr[F_{1,t+1}\mid
F_{K,t}]$ $\displaystyle=\Pr[E_{1}\mid F_{K\cup\\{1\\},t}]\cdot\Pr[F_{1,t}\mid
F_{K,t}]$ $\displaystyle\leq\Pr[E_{1}\mid
F_{J\cup\\{1\\},t}]\cdot\Pr[F_{1,t}\mid F_{J,t}]$ I.H. + (12)
$\displaystyle=\Pr[E_{1},F_{1,t}\mid F_{J,t}]$
$\displaystyle=\Pr[F_{1,t+1}\mid F_{J,t+1}].$

##### Case 4: $\\{1,2\\}\cap(K\setminus J)=\\{2\\}$, and $i=1$.

Independence of $(C_{1},C_{2})$ from $(F_{1,t},F_{K,t})$, and the inductive
hypothesis yield the desired inequality for the tuple $(i,J,K,t+1)$, as
follows.

$\displaystyle\Pr[F_{1,t+1}\mid F_{K,t+1}]$
$\displaystyle=\Pr[\overline{C_{1}},F_{1,t}\mid F_{K,t},\overline{C_{2}}]$
$\displaystyle=\Pr[\overline{C_{1}}\mid\overline{C_{2}}]\cdot\Pr[F_{1,t}\mid
F_{K,t}]$
$\displaystyle(C_{1},C_{2})\bot(F_{1,t},F_{K,t})+\textrm{\ref{obs:bayes-
double-condition-ind}}$
$\displaystyle=\left(1-\frac{a_{1}}{1-a_{2}}\right)\cdot\Pr[F_{1,t}\mid
F_{K,t}]$ $\displaystyle\leq(1-b_{1})\cdot\Pr[F_{1,t}\mid F_{K,t}]$ (9)
$\displaystyle\leq(1-b_{1})\cdot\Pr[F_{1,t}\mid F_{J,t}]$ I.H.
$\displaystyle\leq\Pr[E_{1}\mid F_{1,t}]\cdot\Pr[F_{1,t}\mid F_{J,t}]$
$\displaystyle a_{1}\leq b_{1}$ $\displaystyle=\Pr[F_{1,t+1}\mid F_{J,t}]$
$\displaystyle=\Pr[F_{1,t+1}\mid F_{J,t+1}],$

where the last inequality relied on Constraint (8), whereby $a_{1}\leq b_{1}$,
implying that

$\Pr[E_{1}\mid F_{1,t}]=(1-a_{1})\cdot\Pr[F_{2,t}\mid
F_{1,t}]+(1-b_{1})\cdot\Pr[\overline{F_{2,t}}\mid F_{1,t}]\geq(1-b_{1}).$

##### Case 5: $\\{1,2\\}\cap J=\\{2\\}$, and $i=1$.

Independence of $(C_{1},C_{2})$ from $(F_{1,t},F_{J,t},F_{K,t})$, together
with the inductive hypothesis, proves the desired inequality for the tuple
$(i,J,K,t+1)$.

$\displaystyle\Pr[F_{1,t+1}\mid F_{K,t+1}]$
$\displaystyle=\Pr[\overline{C_{1}},F_{1,t}\mid\overline{C_{2}},F_{K,t}]$
$\displaystyle=\Pr[\overline{C_{1}}\mid\overline{C_{2}}]\cdot\Pr[F_{1,t}\mid
F_{K,t}]$
$\displaystyle(C_{1},C_{2})\bot(F_{1,t},F_{K,t})+\textrm{\ref{obs:bayes-
double-condition-ind}}$
$\displaystyle\leq\Pr[\overline{C_{1}}\mid\overline{C_{2}}]\cdot\Pr[F_{1,t}\mid
F_{J,t}]$ I.H.
$\displaystyle=\Pr[\overline{C_{1}},F_{1,t}\mid\overline{C_{2}},F_{J,t}]$
$\displaystyle(C_{1},C_{2})\bot(F_{1,t},F_{J,t})+\textrm{\ref{obs:bayes-
double-condition-ind}}$ $\displaystyle=\Pr[F_{1,t+1}\mid F_{J,t+1}].$

Combining 3.1 and 3.3, we find that Algorithm 1 is well-defined throughout its
execution. Moreover, we find that each edge is matched with the appropriate
marginal probability prescribed by the fractional solution. In other words, we
obtain the following.

######  Theorem 3.4.

Algorithm 1, when run on a fractional matching $\vec{x}$ satisfying Condition
(2), outputs a random matching $\mathcal{M}$ such that

$\Pr[(i,t)\in\mathcal{M}]=x_{i,t}\qquad\forall(i,t)\in E.$

###  3.3 Small Random Seed for $k$-level Algorithms

The randomized algorithms derived from Algorithm 1 require (at least)
polynomially-large random seeds. In this section we show that this is not
really necessary, and essentially the same competitive ratio can be achieved
using only a doubly-logarithmic random seed.

The need for a large random seed of our algorithms of the previous section is
due to two reasons. The first one is because of precision issues: some of the
probabilities in this algorithm can be arbitrarily small, and so these require
arbitrarily-large random seeds. We overcome this first issue by explicitly
restricting our attention to algorithms requiring only $b$ bits of randomness
to determine the random choices of Algorithm 4, as follows.

######  Definition 3.5.

A fractional algorithm $\mathcal{A}$ is _$b$ -bit precise_ if for each online
node $t$ with $P_{t}=\\{1,2\\}=\\{i\mid x_{i,t}>0\\}$, the fractional matching
$\vec{x}$ output by $\mathcal{A}$ satisfies

$\left\\{\frac{x_{i,t}}{1-x^{(t)}_{i}},\frac{1-x^{(t)}_{i}-x_{i,t}}{(1-x_{1})(1-x_{2})}\right\\}\in\left\\{\frac{a}{2^{b}}\,\,\bigg{|}\,\,a\in\\{0,1,\dots,2^{b}\\}\right\\}.$

The second, more fundamental reason, for the large random seed is our
(implicit) requirement of complete independence between the random choices
during each time step. For $n$ random variables—one per arrival—this trivially
requires at least $n$ random bits. As we show, a significant saving over this
amount of randomness can be obtained by considering small-bias distributions.
For this, we will further restrict our attention to the following kind of two-
choice algorithms.

######  Definition 3.6 ($k$-level Algorithm).

A $k$-level algorithm has some $k+2$ possible values, denoted by
$0=z_{0}<z_{1}<\ldots<z_{k}<z_{k+1}=1$, and maintains the invariant that each
offline node has fractional degree equal to one of these $z_{i}$. At each step
of the algorithm the fractions $x^{(t)}_{1},x^{(t)}_{2}$ of at most two
offline nodes $\\{1,2\\}$ are increased to $x^{(t+1)}_{1},x^{(t+1)}_{2}$, with
the following options:

  * •

deterministic step: $x^{(t)}_{1}$ is increased to $1$.
($x^{(t+1)}_{2}\leftarrow x^{(t)}_{2}$.)

  * •

random step: $x^{(t)}_{1},x^{(t)}_{2}$ are increased to
$x^{(t+1)}_{1},x^{(t+1)}_{2}>\max\\{x^{(t)}_{1},x^{(t)}_{2}\\}$ (strict
inequality).

  * •

shift step: $x^{(t)}_{1}=0$ and $x^{(t)}_{2}\in(0,1)$ are increased to
$x^{(t+1)}_{1}\leftarrow x^{(t)}_{2},x^{(t+1)}_{2}\leftarrow 1$.

We show that when rounding such fractional algorithms using Algorithm 1, the
following holds: for each edge $(i,t)$, the event that $(i,t)$ is matched in
the random matching $\mathcal{M}$ output by Algorithm 4 depends on a bounded
number of random choices of this algorithm. To this end, we denote by
$A_{i,t}\sim Bernoulli(a^{t}_{i})$ the random variable corresponding to the
random choice in 6 of Algorithm 4 and by $B_{i,t}\sim Bernoulli(b^{t}_{i})$
the random variables of 11, where $a^{t}_{i},b^{t}_{i}$ are the solution to
Program (Prob-Program) used by the algorithm at time $t$. We prove the
following.

######  Lemma 3.7.

The event $[(i,t)\in\mathcal{M}]$ is determined by at most $2^{k+2}$ random
variables
$\\{A_{i^{\prime},t^{\prime}},B_{i^{\prime},t^{\prime}}\\}_{i^{\prime},t^{\prime}}$.

###### Proof.

We say an offline node $i$ has level $\ell$ before time $t$ if
$x_{i}^{(t)}=z_{\ell}$. We prove by induction on all times $t$ and on the
level $\ell\leq k$ of node $i$ before time $t$ that $F_{i,t}$ is determined by
at most $2^{\ell+1}-2$ random variables. From this we find that
$\mathds{1}[(i,t)\in\mathcal{M}]=F_{i,t}-F_{i,t+1}$ is determined by at most
$2^{k+1}-2+2^{k+1}-2\leq 2^{k+2}$ random variables the set in
$S:=\\{A_{i^{\prime},t^{\prime}},B_{i^{\prime},t^{\prime}}\\}_{i^{\prime},t^{\prime}}$.

For nodes at level $0$, we have that $F_{i,t}\equiv 1$. Consequently, since at
time $t=1$ all offline nodes $i$ are at level $\ell=0$, the variables
$F_{i,t}$ are determined by $0=2^{0}-1$ random variables. Now, consider a time
$t$ where the level of $i$ increases, depending on what kind of step caused
the increase to level $\ell$. If this increase is due to a deterministic step
(i.e., $\ell=k$), then $F_{i,t+1}\equiv 0$ is deterministic, by Invariant (3),
and so this variable depends on $0\leq 2^{k+1}-2$ random variables in $S$.
Suppose next that the level increase of $i$ is due to a random step, with $j$
the second neighbor of $t$ whose level increases at time $t$. Then we have
that
$F_{i,t+1}=F_{i,t}\cdot\left(F_{j,t}\cdot\overline{A_{i,t}}+\overline{F_{j,t}}\cdot\overline{B_{i,t}}\right)$.
Consequently, since both $i$ and $j$ had level strictly lower than the new
level $\ell$ of $i$, we have by the inductive hypothesis that $F_{i,t+1}$ is
determined by $2+2\cdot(2^{\ell}-2)=2^{\ell+1}-2$ random variables in $S$.

Finally, if the level of $i$ increased to level $\ell$ due to a shift step,
then if $\ell=k$, as argued before, $F_{i,t+1}\equiv 0$, and therefore
$F_{i,t+1}$ is a function of zero variables. Otherwise, the level of the other
node $j$ whose level increased was $\ell$ before, while the previous level of
$i$ was zero. Consequently, by Invariant (3), we have that $t$ is matched with
probability one. That is, $(F_{i,t}-F_{i,t+1})+(F_{j,t}-F_{j,t+1})=1$. But,
similarly, by Invariant (3) we have that $F_{j,t+1}\equiv 0$, and since $i$
was at level zero before time $t$, we have that $F_{i,t}\equiv 1$. Putting the
above together, we find that $F_{i,t+1}=F_{j,t}$. Consequently, by the
inductive hypothesis, since $j$ previously had level $\ell$, we have that
$F_{i,t+1}=F_{j,t}$ is the function of at most $2^{\ell+1}-2$ random variables
in $S$. ∎

We can now rely on our analysis for Algorithm 4 using independent random
variables to analyze the same algorithm when using $(\delta,b\cdot
2^{k+1})$-dependent binary variables to sample variables $A_{i,t},B_{i,t}$. In
particular, we can show that such a random seed yields an essentially lossless
rounding.

######  Theorem 3.8.

Let $\mathcal{M}$ be the random matching output by Algorithm 4 when rounding a
$b$-bit precision restricted $k$-level algorithm, using a distribution
$\mathcal{D}$ over $(\delta,b\cdot 2^{k+2})$-dependent binary variables for
the random choices. Then,

$\Pr_{\mathcal{D}}[(i,t)\in\mathcal{M}]=x_{i,t}\pm\delta\qquad\forall(i,t)\in
E.$

###### Proof.

By definition of $b$-bit precisions, the probabilities of Algorithm 4 can be
specified using $b$ binary variables. On the other hand, by 3.7, each event
$[(i,t)\in\mathcal{M}]$ is determined by $2^{k+2}$ random variables, or
$b\cdot 2^{k+2}$ random binary variables. Now, if we denote by $\mathcal{U}$
the uniform distribution, then by 3.4 and 2.2 we obtain the desired result,

$\displaystyle\Pr_{\mathcal{D}}[(i,t)\in\mathcal{M}]$
$\displaystyle=\Pr_{\mathcal{U}}[(i,t)\in\mathcal{M}]\pm\delta=x_{i,t}\pm\delta\qed.$

Since there are $n$ offline nodes and each node can change levels at most $k$
times, the total number of random variable $A_{i,t},B_{i,t}$ is bounded by
$O(nk)$. Hence, by 2.3 and the above lemma, all $k$-level algorithms can be
rounded with loss $\delta=\frac{1}{\log\log n}=o(1)$, using $(1+o(1))\log\log
n+2^{k+2}b$ random bits, if we take. This concludes 1.4.

We note that using standard $k$-wise independence, one can round a $k$-level
$b$-bit algorithm without _any_ loss (even $o(1)$) using
$O(2^{k+2}b\cdot\log(nk))$ bits of randomness.

Finally, we note that an efficient implementation of Algorithm 1 with perfect
independence implies an implementation with similar running time, only slowed
down by the time to sample from a $(\delta,b\cdot 2^{k+2})$-dependent
distributions. So, for example, C.5 yields polytime implementations of
Algorithm 1 when applied to the $k$-level fractional matching algorithms we
design in the sequel.

##  4 Online Roundable Fractional Matching Algorithms

In this section we prove Theorem 1.5, by designing two-choice maximally-
independent fractional algorithms with high competitive ratios.

###  4.1 The Bounded Water-Level Algorithm

In this section we design a two-choice maximally-independent fractional
algorithm for unweighted matching. The algorithm simply picks the two offline
vertices with smallest fractional degree. It then applies “water level" on
these two vertices (i.e., it raises the fractional degree of the neighbors of
lowest degree among the pair) until it is maximally independent (i.e., until
(2) holds with equality). The formal description appears as Algorithm 2.

Algorithm 2 Restricted Water Level

1:initially, set $\vec{x}\leftarrow\vec{0}$.

2:for arrival of online node $t$ do

3: if $t$ has less than two neighbors then

4: add two dummy neighbors $i$ with $x^{(t)}_{i}=1$ $\rhd$ used to simplify
notation

5: let $0\leq x^{(t)}_{1}\leq x^{(t)}_{2}\leq\dots\leq x^{(t)}_{k}\leq 1$ be
the fractional degrees of neighbors of $t$

6: Let $x_{f}=\frac{x^{(t)}_{1}+x^{(t)}_{2}+1-x^{(t)}_{1}\cdot
x^{(t)}_{2}}{2}$. Set $x_{1,t}\leftarrow x_{f}-x^{(t)}_{1}$,
$x_{2,t}\leftarrow x_{f}-x^{(t)}_{2}$

First, we note that Algorithm 2 is well-defined, as it outputs a feasible
fractional matching.

######  Observation 4.1.

Algorithm 2 outputs a feasible fractional matching $\vec{x}$, with $x_{i,t}=0$
for all dummy nodes $i$ and online nodes $t$.

###### Proof.

We show by induction on $t$ that $\vec{x}$ satisfies the fractional matching
constraints for all nodes. We thus assume that for all offline nodes
$x^{(t)}_{i}\in[0,1]$. First,

$x^{(t)}_{2}\leq
x^{(t)}_{2}+\frac{(1-x^{(t)}_{2})\cdot(1+x^{(t)}_{1})}{2}=\frac{x^{(t)}_{1}+x^{(t)}_{2}+1-x^{(t)}_{1}\cdot
x^{(t)}_{2}}{2}=1-\frac{(1-x^{(t)}_{1})(1-x^{(t)}_{2})}{2}\leq 1,$

meaning that $x^{(t)}_{1}\leq x^{(t)}_{2}\leq x_{f}\leq 1$. This proves that
for all $i$, $x^{(t)}_{i}\leq x^{(t+1)}_{i}\leq 1$ (and $x_{i,t}\geq 0$). In
particular, if $x^{(t)}_{2}=1$ then $x_{f}=1$ and so we do not increase dummy
vertices. Finally,

$\displaystyle x_{1,t}+x_{2,t}$
$\displaystyle=2x_{f}-(x^{(t)}_{1}+x^{(t)}_{2})=1-x^{(t)}_{1}\cdot
x^{(t)}_{2}\leq 1.\qed$

We now turn to analyzing the competitive ratio of this algorithm. We prove the
following:

######  Lemma 4.2.

Let $g:[0,1]\rightarrow[0,1]$ be a twice differentiable function that is
monotone increasing, convex and bijective in $[0,1]$ (and so, in particular,
satisfy $g(0)=0$ and $g(1)=1$). Then, Algorithm 2 is $\alpha_{g}$-competitive,
where

$\alpha_{g}:=\min_{x\in[0,1]}\frac{1-x^{2}}{1-3g(x)+2g\left(x+\frac{1-x^{2}}{2}\right)}.$
(14)

We first prove the following Claim.

######  Claim 4.3.

Let $g:[0,1]\rightarrow[0,1]$ be a twice differentiable function that is
monotone increasing, convex and bijective in $[0,1]$ Then, for any
$x\in[0,1]$, we have

$g^{\prime}(x)\leq g^{\prime}(1)\leq\frac{1}{\alpha_{g}}.$

###### Proof.

The first inequality follows from $f$ being convex and twice differentiable.
For the second inequality, we note that the RHS can be written as

$\displaystyle\alpha_{g}=\max_{x\in[0,1]}\frac{1-3g(x)+2g\left(x+\frac{1-x^{2}}{2}\right)}{1-x^{2}}$
$\displaystyle=\max_{x\in[0,1]}\left(\frac{1-g(x)}{1-x^{2}}+\frac{g\left(x+\frac{1-x^{2}}{2}\right)-g(x)}{\frac{1-x^{2}}{2}}\right)$
$\displaystyle\geq\max_{x\in[0,1]}\frac{g\left(x+\frac{1-x^{2}}{2}\right)-g(x)}{\frac{1-x^{2}}{2}}$
$\displaystyle\geq g^{\prime}(1),$

where the first inequality follows follows from $1-g(x)\geq 0$ for $x\in[0,1]$
and so $\frac{1-g(x)}{1-x^{2}}\geq 0$, while the second inequality follows by
considering $x\rightarrow 1$.444For the reader uncomfortable thinking of
$\lim_{x\rightarrow
1}\frac{g\left(x+\frac{1-x^{2}}{2}\right)-g(x)}{\frac{1-x^{2}}{2}}$ as being
of the form $\lim_{x\rightarrow 1}\lim_{h\rightarrow 0}\frac{g(x+h)-g(x)}{h}$,
since $h=(1-x^{2})/2$ depends on $x$ here, consider applying L’hôpital’s rule,
which yields  $\lim_{x\rightarrow
1}\frac{g\left(x+\frac{1-x^{2}}{2}\right)-g(x)}{\frac{1-x^{2}}{2}}=\lim_{x\rightarrow
1}\frac{y^{\prime}\left(x+\frac{1-x^{2}}{2}\right)\cdot(1-x)-g^{\prime}(x)}{-x}=g^{\prime}(1)+\frac{g^{\prime}(1)-g^{\prime}(1)}{-1}=g^{\prime}(1).$
∎

We next prove that Algorithm 2 is $\alpha_{g}$-competitive.

###### Proof.

The proof relies on dual fitting. Let $g$ be a function that satisfies the
conditions of the lemma. We use the function $g(\cdot)$ to assign dual values
to offline node with fractional degree $x_{i}$. When an online node $t$
arrives, we denote by $0\leq x_{1}\leq x_{2}\leq\dots\leq x_{k}\leq 1$ the
fractional degrees of its neighbors (including dummy neighbors). Algorithm 2
increases the fractional degree of neighbors $i=\\{1,2\\}$ of $t$ to
$x_{f}:=\frac{x_{1}+x_{2}+1-x_{1}x_{2}}{2}=\hat{x}+\frac{1-x_{1}x_{2}}{2}$,
where $\hat{x}:=\frac{x_{1}+x_{2}}{2}$. (Note that this is indeed an increase,
as by 4.1, for $i=1,2$, we have $x_{f}-x_{i}=x_{i,t}\geq 0$, and so $x_{f}\geq
x_{i}$.) We set the dual of the online node at time $y_{t}$ to $1-g(x_{2})$,
while maintaining the invariant that each offline node $i$ with fractional
degree $x_{i}$ has dual value $y_{i}=g(x_{i})$. This satisfies the dual
constraint for each edges $(i,t)$, due to the monotonicity of $y$, implying
$1-g(x_{2})+g(x_{i})\geq 1$ for all $x_{i}\geq x_{2}$, and due to the final
fractional degree of $1$ and $2$ satisfying $x_{f}\geq x_{2}$.

We show that the primal gain is at least $\alpha_{g}$ times the dual cost,
which implies the lemma, by weak duality. Let
$\hat{x}_{f}=\hat{x}+\frac{1-\hat{x}^{2}}{2}$. By the AM-GM inequality we
have:

$\displaystyle\hat{x}_{f}$
$\displaystyle=\hat{x}+\frac{1-\hat{x}^{2}}{2}\leq\hat{x}+\frac{1-x_{1}x_{2}}{2}=x_{f}.$

We now show that the dual and primal changes satisfy $\Delta
D-\frac{1}{\alpha_{g}}\cdot\Delta P\leq 0$. Indeed,

$\displaystyle\Delta D-\frac{1}{\alpha_{g}}\cdot\Delta P$
$\displaystyle=1-g(x_{2})+(g(x_{f})-g(x_{1}))+(g(x_{f})-g(x_{2}))-\frac{1}{\alpha_{g}}\cdot
2(x_{f}-\hat{x})$ $\displaystyle\leq
1-g(\hat{x})+2g(x_{f})-2g(\hat{x})-\frac{1}{\alpha_{g}}\cdot 2(x_{f}-\hat{x})$
(15) $\displaystyle\leq
1-g(\hat{x})+2g(\hat{x}_{f})-2g(\hat{x})-\frac{1}{\alpha_{g}}\cdot
2(\hat{x}_{f}-\hat{x})$ (16)
$\displaystyle\leq\max_{x\in[0,1]}\left\\{1-3g(x)+2g\left(x+\frac{1-x^{2}}{2}\right)-\frac{1}{\alpha_{g}}\cdot(1-x^{2})\right\\}=0.$

Inequality (15) follows by convexity of $y$ implying $2g(\hat{x})\leq
g(x_{1})+g(x_{2})$, and $x_{2}\geq\hat{x}$ together with $y$ being monotone
increasing. Inequality (16) follows from $\hat{x}_{f}\leq x_{f}$ and the
function $g(x)-\frac{1}{\alpha_{g}}\cdot x$ being monotone decreasing in $x$,
as $g^{\prime}(x)-\frac{1}{\alpha_{g}}\leq 0$ for all $x\in[0,1]$, by 4.3. The
final equality follows by the definition of $\alpha_{g}$. ∎

Finally, we prove the upper and lower bounds on the competitive ratio of the
algorithm.

######  Theorem 4.4.

Algorithm 2 is $\alpha$-competitive, where $\alpha$ is $\approx\ratio$ and at
most $\approx 0.536$.

###### Proof.

For the lower bound we note that the function $g(x):=\frac{a^{x}-1}{a-1}$ for
$a=1.6$ satisfies the conditions of Lemma 4.2, and achieves a value of
$\alpha_{g}\approx\ratio$. For the upper bound we design a bad example that
shows that the competitive ratio of the algorithm is at most $\sum_{i\geq
0}\frac{1}{3}\cdot\left(\frac{2}{3}\right)^{i}\cdot\left(1-2^{-2^{i}+1}\right)\approx
0.536$.

The bad example consists of a bipartite graph with $n=3^{k}$ nodes on either
side, with a perfect matching. The online nodes arrive in rounds, as follows.
At the beginning of round $i<k$, a subset of the offline nodes is active, and
they all have the same fractional degree. The online nodes of a round each
have three distinct neighbors among the active offline nodes. In every such
three-tuple of offline nodes (neighboring a common online node in round $i$),
one node is not matched at all. This node is chosen to be de-activated. A
simple proof by induction shows that the number of active offline nodes in
round $i=0,1,2,\dots,k-1$ is $\left(\frac{2}{3}\right)^{i}\cdot n$, while the
fractional degree of active nodes in round $i$ is $1-2^{-2^{i}+1}$. Therefore,
the nodes which are de-activated in round $i$ only accrue a gain of
$1-2^{-2^{i}+1}$. As these de-activated nodes in round $i$ are a third of the
active nodes in this round, we find that the total gain of the algorithm from
nodes de-activaed in round $i$ is
$\frac{1}{3}\cdot\left(\frac{2}{3}\right)^{i}n\cdot\left(1-2^{-2^{i}+1}\right)$.
Finally, in the last round, each of the $\left(\frac{2}{3}\right)^{k}\cdot
n=2^{k}=o(n)$ active nodes has one distinct online neighbor, and so each of
these offline nodes gets a gain of one. The nodes of this last round guarantee
the existence of a perfect matching in $G$, consisting of the edges of the
last round, together with an edge between every online node $t$ and its
offline neighbor de-activated in the round $t$ arrived in. We conclude that
the algorithm’s competitive ratio is at most

$\displaystyle\inf_{k}\sum_{i=0}^{k}\frac{1}{3}\cdot\left(\frac{2}{3}\right)^{i}\cdot(1-2^{-2^{i}+1})+\frac{2^{k}}{3^{k}}\approx
0.536\qed$

###  4.2 The $k$-Level Unweighted Algorithm

In this section we design a fractional $k$-level algorithm for the unweighted
matching problem. The algorithm uses levels
$z_{0}=0<z_{1}<z_{2}<\ldots<z_{k}<1$, where
$z_{i}=z_{i-1}+\frac{1-z_{i-1}^{2}}{2}$. Solving the recursion yields
$z_{i}:=1-2^{-2^{i}+1}$.555Indeed, by induction on $i$, we have that
$z_{i+1}=z_{i}+\frac{1-z_{i}^{2}}{2}=\frac{(1-z_{i})^{2}}{2}=\frac{(1-(1-2^{-2^{i}+1}))^{2}}{2}=(1-2^{-2^{i+1}+1})$.
The algorithm is as follows:

Algorithm 3 The $k$-Level Algorithm

1:initially, set $\vec{x}\leftarrow\vec{0}$

2:for arrival of online node $t$ do

3: if $t$ has less than two neighbors then

4: add two dummy neighbors $i$ with $x^{(t)}_{i}=1$ $\rhd$ used to simplify
notation

5: let $0\leq x^{(t)}_{1}\leq x^{(t)}_{2}\leq\dots\leq x^{(t)}_{k}\leq 1$ be
the fractional degrees of neighbors of $t$

6: if $x^{(t)}_{1}<x^{(t)}_{2}$ or $x^{(t)}_{1}=z_{k}$ then

7: set $x^{(t+1)}_{1}\leftarrow 1$ $\rhd$ $x_{1,t}\leftarrow 1-x^{(t)}_{1}$

8: else if $x^{(t)}_{1}=x^{(t)}_{2}=z_{i}<z_{k}$ then

9: set $x^{(t+1)}_{1}=x^{(t+1)}_{2}\leftarrow z_{i+1}$ $\rhd$
$x_{1,t}=x_{2,t}\leftarrow z_{i+1}-z_{i}$

The following observation shows that Algorithm 3 indeed satisfies Definitions
3.5 and 3.6, and so can be rounded with less randomness.

######  Observation 4.5.

Algorithm 3 is a $k$-level independent maximal and $2^{k-1}$-bit precise.

###### Proof.

It is easy to verify that the steps of the algorithm satisfy the $k$-level
requirements in Definition 3.6. Also, since
$z_{i}=z_{i-1}+\frac{1-z_{i-1}^{2}}{2}$ it is easy to see that the algorithm
is maximal independent. Finally, we need to prove that the algorithm is
$b$-bit precise (satisfies Definition 3.5). We should prove that at any time
$t$:

$\left\\{\frac{x_{i,t}}{1-x^{(t)}_{i}},\frac{1-x^{(t)}_{i}-x_{i,t}}{(1-x_{1})(1-x_{2})}\right\\}\in\left\\{\frac{a}{2^{b}}\mid
a\in\\{0,1,\dots,2^{b}\\}\right\\}.$

As each time $t$, the first term is either $1$ or of the form:
$\frac{z_{i}-z_{i-1}}{1-z_{i-1}}=\frac{1-z_{i-1}^{2}}{2(1-z_{i-1})}=\frac{1+z_{i-1}}{2}=1-2^{-2^{i-1}}$,
where $i\leq k$. The second term is always of the form
$\frac{1-z_{i}}{(1-z_{i-1})^{2}}=\frac{1}{2}$. Therefore the algorithm is
$b$-bit precise for $b=2^{k-1}$. ∎

####  4.2.1 Warm-up: Analysis of the $2$-level Algorithm

As a warm-up, we analyze the algorithm when $k=2$. In this case the algorithm
uses only two levels: $z_{1}=\frac{1}{2},z_{2}=\frac{7}{8}$. The algorithm has
the following 4 cases:

  * •

$x^{(t)}_{1}=x^{(t)}_{2}=0$: set
$x^{(t+1)}_{1}=x^{(t+1)}_{2}\leftarrow\frac{1}{2}$.

  * •

$x^{(t)}_{1}=x^{(t)}_{2}=\frac{1}{2}$: set
$x^{(t+1)}_{1}=x^{(t+1)}_{2}\leftarrow\frac{7}{8}$.

  * •

$x^{(t)}_{1}=x^{(t)}_{2}=\frac{7}{8}$: set $x^{(t+1)}_{1}\leftarrow 1$.

  * •

$x^{(t)}_{1}<x^{(t)}_{2}$: set $x^{(t+1)}_{1}\leftarrow 1$.

######  Theorem 4.6.

The fractional $2$-level algorithm is
$\nicefrac{{1}}{{2}}+\nicefrac{{1}}{{36}}\approx 0.527$-competitive.

###### Proof.

The analysis is via a dual fitting argument. Let $\\{1,2\\}$ be the two
vertices that were increased, and for simplicity we denote by $x_{1},x_{2}$
their fractional degree at time $t$. We use the following (optimized) values
for the dual nodes: $y_{1}=y(\frac{1}{2})=17/38,y_{2}=y(\frac{7}{8})=67/76$.
These are the values of the offline nodes at the corresponding levels. To
guarantee that the dual solution is feasible, we set the dual value of node
$t$ to $1-y(x_{2})$. This satisfies the dual constraints of all edges $(i,t)$,
and as the dual values are only increasing the dual constraints remain
satisfied. We next analyze the four cases, proving that in each one the ratio
between the values of the primal and dual changes is at most
$1+\frac{17}{19}$. This concludes the proof.

Case 1 ($x_{1}=0,x_{2}=0$): $x_{1}=x_{2}\leftarrow\frac{1}{2}$. The value of
the online node can be set to $1-y(0)=1$. Thus,

$\frac{\Delta D}{\Delta P}=\frac{1+y_{1}+y_{1}}{1}=1+\frac{17}{19}.$

Case 2 ($x_{1}=\frac{1}{2},x_{2}=\frac{1}{2}$):
$x_{1}=x_{2}\leftarrow\frac{7}{8}$. The value of the online node can be set to
$\min\\{1-y_{1}\\}$. Thus,

$\frac{\Delta D}{\Delta
P}=\frac{1-y_{1}+2(y_{2}-y_{1})}{2\cdot\frac{3}{8}}=1+\frac{17}{19}.$

Case 3 ($x_{1}=\frac{7}{8},x_{2}=\frac{7}{8}$): We set $x_{1}\leftarrow 1$ and
we can set the value of the online node to $1-y_{2}$. Thus,

$\frac{\Delta D}{\Delta
P}=\frac{1-y_{2}+1-y_{2}}{\frac{1}{8}}=1+\frac{17}{19}.$

Case 4 ($x_{1}<x_{2}$): We set $x_{1}\leftarrow 1$ and the value of the online
node can be set to $1-y(x_{2})$. There are several possible cases here (some
are easily dominated by others in terms of competitiveness).
$(x_{1},x_{2})\in\\{(0,\frac{1}{2}),(0,\frac{7}{8}),(0,1),(\frac{1}{2},\frac{7}{8}),(\frac{1}{2},1),(\frac{7}{8},1)\\}$.
The worst ratio is obtained when $x_{1}=0,x_{2}=\frac{1}{2}$. Thus,

$\displaystyle\frac{\Delta D}{\Delta P}$
$\displaystyle=\frac{1-y(x_{2})+1-y(x_{1})}{1-x_{1}}\leq\frac{1-y_{1}+1}{1}=1+\frac{21}{38}.\qed$

####  4.2.2 Analysis of the $k$-level Algorithm

In this section we give a general analysis of the $k$-level algorithm. We
prove the following Lemma.

######  Lemma 4.7.

Let $g:[0,1]\rightarrow[0,1]$ be a twice differentiable function that is
monotone increasing, convex and bijective in $[0,1]$ (and so, in particular,
satisfy $g(0)=0$ and $g(1)=1$). Then, Algorithm 2 is
$\left(\alpha_{g}-O(2^{-2^{k}})\right)$-competitive, where

$\alpha_{g}:=\min_{x\in[0,1]}\left\\{\frac{1-x^{2}}{1-3g(x)+2g\left(x+\frac{1-x^{2}}{2}\right)},\frac{1-x}{2-g(x)-g(x+\frac{1-x^{2}}{2})}\right\\}.$
(17)

###### Proof.

The proof relies on dual fitting. Let $g$ be a function that satisfies the
conditions of the lemma. We use the function $g(\cdot)$ to assign dual values
to offline node with fractional degree $x_{i}$. We assign a dual value
$y_{i}=g(x_{i})$. For any online node $t$ whose neighbors’ fractional degrees
at time $t$ are $x^{(t)}_{1}\leq x^{(t)}_{2}\leq\dots$, we set
$y_{t}=1-g(x^{(t)}_{2})$. This dual solution is trivially feasible. Now,
consider $\Delta P$ and $\Delta D$ following an online node’s arrival. We will
show that $\Delta P/\Delta D$ is at least $\alpha_{g}$ for all arrivals except
for a small fraction of arrivals, when weighted by their contribution to $P$.
This will prove the competitive ratio. There are three cases to consider.

##### Case 1: $x^{(t)}_{1}=x^{(t)}_{2}=z_{m}<z_{k}$.

In this case we have that the primal gain and dual change are

$\displaystyle\Delta P$ $\displaystyle=1-z_{m}^{2},$ $\displaystyle\Delta D$
$\displaystyle=2(g(z_{m+1})-g(z_{m}))+1-g(z_{m}).$

By the definition of $\alpha_{g}$, and since
$z_{m+1}=z_{m}+\frac{(1-z_{m})^{2}}{2}$, we have

$\Delta P/\Delta
D=\frac{1-z_{m}^{2}}{1-3g(z_{m})+2g\left(z_{m}+\frac{1-z_{m}^{2}}{2}\right)}\geq\min_{x\in[0,1]}\frac{1-x^{2}}{1-3g(x)+2g\left(x+\frac{1-x^{2}}{2}\right)}\geq\alpha_{g}.$

##### Case 2: $x^{(t)}_{1}=z_{m}<x^{(t)}_{2}<1$, with $m<k$.

In this case we have that the primal gain and dual cost are

$\displaystyle\Delta P$ $\displaystyle=1-z_{m},$ $\displaystyle\Delta D$
$\displaystyle\leq
1-g(z_{m})+1-g(z_{m+1})=2-g(z_{m})-g(z_{m+1})=2-g(z_{m})-g(z_{m}+\frac{1-z_{i-1}^{2}}{2}).$

By the definition of $\alpha_{g}$,

$\Delta P/\Delta
D=\frac{1-z_{m}}{2-g(z_{m})-g(z_{m}+\frac{1-z_{i-1}^{2}}{2})}\geq\min_{x\in[0,1]}\frac{1-x}{2-g(x)-g(x+\frac{1-x^{2}}{2})}\geq\alpha_{g}.$

##### Case 3: $x^{(t)}_{1}=z_{k}$.

In this case we have that the primal gain and dual change are

$\displaystyle\Delta P$ $\displaystyle=1-z_{k},$ $\displaystyle\Delta D$
$\displaystyle=1-g(z_{k})+1-g(z_{k})=2-2g(z_{k}).$

Every time we get to case $3$ the fraction of a new offline node becomes 1.
Hence the total dual cost in all these steps, $D^{\prime}$, is at most
$2(1-g(z_{k}))P$, where $P$ is the final primal solution.

Summing up over all steps, we get that:

$P\geq\alpha_{g}\cdot\left(D-D^{\prime}\right)=\alpha_{g}\cdot\left(D-2(1-g(z_{k}))P\right)\geq\alpha_{g}\cdot\left(D-\frac{2(1-z_{k})}{\alpha_{g}}P\right)=\alpha_{g}\cdot
D-2(1-z_{k})P,$

where the last inequality follows since by Claim 4.3 for each
$g\in\mathcal{F}$, we have $\frac{1-g(z_{k})}{1-z_{k}}=g^{\prime}(\hat{x})\leq
g^{\prime}(1)\leq\frac{1}{\alpha_{g}}\leq\frac{1}{\alpha^{\prime}_{g}}$, where
$0<\hat{x}<1$. Overall, we get
$P\geq\frac{\alpha_{g}}{1+2(1-z_{k})}D=\frac{\alpha_{g}}{1+2^{-2^{k}+2}}D=\left(\alpha_{g}-O(2^{-2^{k}})\right)D$.
∎

The proof of the competitive ratio of the $k$-level algorithm follows the same
argument as Theorem 4.4. In particular, the same function $g$ can be used to
show the competitive ratio, and the adversarial sequence that shows the upper
bound is the same.

######  Theorem 4.8.

Algorithm 3 is $\left(\alpha_{g}-O(2^{-2^{k}})\right)$-competitive with
$\alpha\in[\ratio,0.536]$.

###  4.3 A $2$-level Fractional Vertex-Weighted Algorithm

In this section we design a two-choice $2$-level fractional algorithm for the
more general _vertex-weighted_ problem, where offline nodes have a weight
associated with them, and we wish to output a matching of maximum weight. We
prove the following:

######  Theorem 4.9.

There exists a fractional $2$-level $\nicefrac{{11}}{{21}}\approx
0.524$-competitive vertex-weighted online matching algorithm.

###### Proof.

The algorithm draws ideas from the 2-level algorithm for the unweighted case
in Section 4.2.1, but is more involved, due to the offline weights adding
another dimension of asymmetry. As in the unweighted case, the algorithm has
two possible levels for the offline nodes:
$z_{1}=\frac{1}{2},z_{2}=\frac{7}{8}$. Let $w_{i}>0$ be the weight of node
$i$. At time $t$, let $w_{1}(1-x^{(t)}_{1})\geq
w_{2}(1-x^{(t)}_{2})\geq\ldots,\geq w_{k}(1-x^{(t)}_{k})$ be the neighbors of
$t$ sorted by their dual slack. We again assume wlog of generality that there
are at least two neighbors. Otherwise, we add dummy neighbors with
$x^{(t)}_{i}=1$ that will not change the behavior of the algorithm or the
analysis. Let $\\{1,2\\}$ be the two offline nodes with the maximal slack (not
necessarily sorted). By normalizing, we assume wlog of generality that
$w_{1}=1$. We use the following (optimized) numbers:
$y_{1}=\frac{5}{11},y_{2}=\frac{79}{88}$. The algorithm is defined by the
following cases:

  * •

$x_{1}=0,x_{2}=0$: If $w_{2}\leq\frac{1}{1-y_{1}}$ then set
$x_{1}=x_{2}=\frac{1}{2}$, otherwise set $x_{1}\leftarrow 1$.

  * •

$x_{1}=\frac{1}{2},x_{2}=\frac{1}{2}$: If $w_{2}\leq\frac{1-y_{1}}{1-y_{2}}$
then set $x_{1}=x_{2}=\frac{7}{8}$, otherwise set $x_{1}\leftarrow 1$.

  * •

$x_{1}=\frac{7}{8},x_{2}=\frac{7}{8}$: If $w_{2}\leq 1$ then set
$x_{1}\leftarrow 1$, otherwise set $x_{2}\leftarrow 1$.

  * •

$x_{1}=0,x_{2}=\frac{1}{2}$: If $w_{2}\leq\frac{3}{2}$ then set
$x_{1}\leftarrow 1$, otherwise set $x_{1}\leftarrow\frac{1}{2},x_{2}\leftarrow
1$.

  * •

$x_{1}=0,x_{2}=\frac{7}{8}$: If $w_{2}\leq 5.5$ then set $x_{1}\leftarrow 1$,
otherwise set $x_{1}\leftarrow\frac{7}{8},x_{2}\leftarrow 1$.

  * •

$x_{1}=\frac{1}{2},x_{2}=\frac{7}{8}$: If $w_{2}\leq 4$ then set
$x_{1}\leftarrow 1$, otherwise set $x_{2}\leftarrow 1$.

  * •

$x_{1}<1,x_{2}=1$: set $x_{1}\leftarrow 1$.

As in Observation 4.5 it is not hard to verify the following.

######  Observation 4.10.

The algorithm is $k$-level independent maximal and $2$-bit precise.

##### Analysis.

The analysis proceeds via a dual fitting argument. Let $\\{1,2\\}$ be the two
vertices with the highest $w_{i}(1-x^{(t)}_{i})$. We note that $\\{1,2\\}$ are
not numbered according to their slack, but rather according to their
fractional degree, as in the algorithm’s description. We assume wlog that
$w_{1}=1$. We use dual values
$y_{1}=y(\frac{1}{2})=\frac{5}{11},y_{2}=y(\frac{7}{8})=\frac{79}{88}$. We
note that if we give the online node a value of
$\max\\{\min\\{1-y(x^{t}_{1}),w_{2}(1-y(x^{t}_{2})\\},1-y(x^{t+1}_{1}),w_{2}(1-y(x^{t+1}_{2})\\}$,
it will satisfy all dual constraints for edges $(i,t)$ at time $t$ (and hence
at all future times). We therefore have that the obtained dual’s cost upper
bounds the optimal matching’s weight. To that end, we prove the following
claim, whose (rather tedious) proof is deferred to Appendix D.

######  Claim 4.11.

The changes to the vertex-weighted algorithm’s dual and primal values at each
time $t$ satisfy

$(\Delta P)_{t}\geq\frac{11}{21}\cdot(\Delta D)_{t}.$

Summing up over all time steps, we have that by 4.11 and weak duality, the
primal gain (i.e., the fractional matching’s value) is at least

$\displaystyle P$ $\displaystyle=\sum_{t}(\Delta
P)_{t}\geq\frac{11}{21}\cdot\sum_{t}(\Delta D)_{t}=\frac{11}{21}\cdot
D\geq\frac{11}{21}\cdot OPT.\qed$

##  5 Conclusion and Open Questions

In this work we present a sharp threshold for the amount of randomness or
advice needed to beat the optimal $\nicefrac{{1}}{{2}}$ ratio of deterministic
algorithms for online (vertex-weighted) matching. We obtain our results by
presenting a family of competitive fractional algorithms which are losslessly
roundable online. We are hopeful that our work will spur follow-ups exploring
the overlooked technique of lossless online rounding in the context of online
matching and related problems. Indeed, we note that any randomized algorithm
trivially induces a roundable fractional algorithm (i.e., the algorithm which
maintains as its solution the marginal probabilities
$x_{i,t}=\Pr[(i,t)\in\mathcal{M}]$). Can the search for roundable fractional
matching algorithms shed more light on the space of randomized algorithms for
online (matching) problems?

Beyond this meta-question, our work suggests a number of further concrete
questions. What is the optimal competitive ratio achievable using
$(1+o(1))\log\log n$ bits of randomness? Can $1-\nicefrac{{1}}{{e}}-o(1)$ be
achieved, or is there another randomness transition for competitiveness above
some ratio $\alpha>\ratio$? Achieving significantly better bounds would
require switching to multiple-choice algorithms. As we show, new conditions
are needed for lossless roundability of multiple-choice algorithms. What are
such conditions which allow for improved approximation ratios? Can we find
similar conditions for other problems in the space of online matching and
online allocation? As outlined in the introduction, progress on this line of
work has the potential to resolve longstanding questions in the area. We see
this work as a first step in this direction.

##### Acknowledgements.

We thank Amin Saberi for useful discussions.

## Appendix

##  Appendix A Impossibility of Online Lossless Rounding

In this short section we briefly present an example demonstrating the
impossibility of online lossless rounding. This example can be seen as a
prefix of the example discussed in Devanur et al. [19] when discussing the
impossibility of lossless online rounding, which is itself a special case of
the lower bound of Cohen and Wajc [18].

Example 1. We consider a bipartite graph with simple a two-choice fractional
matching assigning values $x_{i,t}\leftarrow\nicefrac{{1}}{{2}}$ to all edges
$(i,t)\in E$, and show that this matching cannot be rounded losslessly. The
first two online vertices neighbor offline vertex sets $\\{1,2\\}$ and
$\\{3,4\\}$, respectively. A lossless online rounding scheme must match each
edge $(i,t)$ with probability $x_{i,t}=\nicefrac{{1}}{{2}}$, would match both
offline vertices with probability one. Consequently, both these online
vertices are matched with probability one. A simple averaging argument shows
that for some pair $(i,j)\in\\{1,2\\}\times\\{3,4\\}$, the probability that
they are both matched after these two online vertices arrive is at least
$\frac{1}{4}$. Next, if another online vertex arrives that has these two
vertices as neighbors, it can be matched with probability at most
$\frac{3}{4}$, or strictly less than the fractional solution, which matches it
to an extent of one. That is, this two-choice fractional matching cannot be
rounded losslessly.

##  Appendix B Beyond Two Choices – Challenges

In this section we discuss our focus on two-choice algorithms, and challenges
in generalizing our characterization of online roundable fractional matchings.

By a lower bound of Huang and Tao [32], two-choice fractional algorithms are
at best $\nicefrac{{5}}{{9}}$-competitive. Consequently, two-choice algorithms
cannot yield optimal $1-\nicefrac{{1}}{{e}}(>\nicefrac{{5}}{{9}})$ competitive
ratios for the problems we study and their generalizations. However, two-
choice algorithms shed light on the technical challenge of lossless online
rounding for online matching problems. Moreover, we show that these algorithms
are sufficient to resolve the open question of the amount of randomness (and
nondeterminism) needed to outperform deterministic algorithms’ competitive
ratio of $\nicefrac{{1}}{{2}}$ for online bipartite matching. This mirrors the
recent breakthroughs for online edge-weighted matching and adwords without the
small-bids assumption [22, 34], which are also achieved via such two-choice
algorithms (though using completely different techniques.)

A natural follow-up direction is to study lossless online roundability for
_multiple-choice_ algorithms. (i.e., algorithms with $|P_{t}|=|\\{i\mid
x_{i,t}>0\\}|>2$ for some online nodes $t$). A natural generalization (and
strengthening) of Condition (2) to multiple-choice algorithms, for which
$P_{t}:=\\{i\mid x_{i,t}>0\\}$ need not satisfy $|P_{t}|\leq 2$, is the
following.

$\sum_{i\in I}x_{i,t}\leq 1-\prod_{i\in I}x^{(t)}_{i}\qquad\forall I\subseteq
P_{t}.$ (18)

Similarly to our discussion for two-choice algorithms, this conditioned can be
shown to be necessary condition for lossless online rounding in some
scenarios. Perhaps surprisingly, we show that unlike for two-choice
algorithms, this natural generalization of Condition (2) to multiple-choice
algorithms is _not sufficient_ for lossless online rounding.

######  Lemma B.1.

There exists a three-choice fractional matching algorithm $\mathcal{A}_{f}$
whose output $\vec{x}$ satisfies Condition (18), such that for any randomized
online matching algorithm $\mathcal{A}$, there exists a graph on which the
fractional matching of $\mathcal{A}_{f}$ is strictly greater than the expected
matching size of $\mathcal{A}$. That is, $\mathcal{A}_{f}$ is not losslessly
roundable.

###### Proof.

Our proof goes via Yao’s Lemma [52]. We consider the following distributions
over graphs of maximum degree three, on which any fractional or randomized
algorithm are trivially three-choice algorithms. We label the offline nodes
$i_{1,1},i_{1,2},i_{2,1},i_{2,2},i_{3,1},i_{3,2}$. Each online node $t\in[3]$
neighbors the two offline nodes $i_{t,1},i_{t,2}$. In addition, we have two
online nodes, $4$ and $5$, which neighbor a random node in each of the pairs
$\\{i_{t,1},i_{t,2}\\}_{t\in[3]}$. The three-choice fractional matching we
consider is the following:

$x_{i,t}=\begin{cases}0&(i,t)\not\in E\\\ \frac{1}{2}&(i,t)\in
E,i=i_{t,j},t\in[3]\\\
\frac{7}{24}=\frac{1-\left(\frac{1}{2}\right)^{3}}{3}&(i,t)\in E,t=4\\\
\frac{6965}{41472}=\frac{1-\left(\frac{19}{24}\right)^{3}}{3}&(i,t)\in
E,t=5.\end{cases}$

We note that $\vec{x}$ is a three-choice fractional matching satisfying
Condition (18). We note moreover that $x_{i,t}>\frac{1}{6}$ for $(i,t)\in E$
and $t=5$. Consequently, this fractional matching has value at least
$\sum_{i,t}x_{i,t}>3+\frac{7}{8}+\frac{1}{2}$. We now proceed to show that
every randomized algorithm $\mathcal{A}$ outputs a matching $\mathcal{M}$ of
expected size $\mathbb{E}[\mathcal{M}]=3+\frac{7}{8}+\frac{1}{2}$. That is,
$\mathbb{E}[\mathcal{M}]<\sum_{i,t}x_{i,t}$.

Consider a deterministic algorithm $\mathcal{A}^{\prime}$ run on an input
drawn from the above distribution. By simple exchange arguments, due to the
one-sided vertex arrivals, we may safely assume that $\mathcal{A}^{\prime}$ is
greedy, and matches whenever presented with an online node with at least one
free neighbor [35]. Therefore, precisely one node in each pair
$\\{i_{t,1},i_{t,2}\\}$ is matched two online node $t$, and therefore the
number of free nodes in the neighborhood of $4$ and $5$ before time $4$ is
distributed $Y\sim Bin(3,1/2)$. Consequently, the expected number of online
nodes matched among $4$ and $5$ is precisely
$\mathbb{E}[\max\\{2,Y\\}]=1\cdot\Pr[Y=1]+2\cdot\Pr[Y\geq
2]=\frac{3}{8}+1=\frac{7}{8}+\frac{1}{2}$. We conclude that the matching
$\mathcal{M}$ output by the deterministic algorithm $\mathcal{A}^{\prime}$ on
the above distribution has expected size strictly less than the value of the
fractional matching output by $\mathcal{A}_{f}$, namely

$\mathbb{E}[|\mathcal{M}|]=3+\frac{7}{8}+\frac{1}{2}<\sum_{i,t}x_{i,t}.$

By Yao’s Lemma, for each randomized algorithm $\mathcal{A}$, outputs a
matching on one of the graphs in the support of the above distribution, whose
expected size is strictly smaller than the fractional matching of the three-
choice algorithm $\mathcal{A}_{f}$, whose output satisfies Condition (18). ∎

######  Corollary B.2.

Condition (18) is not sufficient to round multiple-choice algorithms
losslessly.

##  Appendix C Lossless Online Rounding: A Special Case

In this section we study a special case of our rounding algorithm for the case
the input $2$-choice sound algorithm is also maximal, i.e., satisfies
Condition (2) at equality. We also show that this obtained algorithm can be
implemented efficiently, i.e., in polynomial time.

###  C.1 The Algorithm

In this section we show that any _maximal_ two-choice sound fractional
solution $\vec{x}$ can be rounded while preserving the marginal probabilities
of all edges, with even stronger negative correlation properties than for non-
maximal such algorithms. As before, we denote by $F_{I,t}$ the probability
that a set of offline vertices $I\subseteq[n]$ is free at time $t$, and use
$F_{i,t}$ as shorthand for $F_{\\{i\\},t}$.

$\displaystyle\Pr\left[F_{i,t}\right]$ $\displaystyle=1-x^{(t)}_{i}$
$\displaystyle\forall i=1,\ldots,n.$ (19)
$\displaystyle\Pr\left[F_{I,t}\right]$ $\displaystyle\in\left\\{0,\prod_{i\in
I}(1-x^{(t)}_{i})\right\\}$ $\displaystyle\forall I\subseteq\\{1,\ldots,n\\}.$
(20)

We call a subset $I$ of offline nodes negative (at time $t$) if
$\Pr\left[F_{I,t}\right]=0$. Otherwise, we say it is independent, noting that
in this case $\Pr\left[F_{I,t}\right]=\prod_{i\in I}(1-x_{i})=\prod_{i\in
I}\Pr\left[F_{i,t}\right]$. We note that this second name is apt, since for
any independent set $I$ at time $t$, the variables $\\{F_{i,t}\mid i\in I\\}$
are indeed independent as observed in the following. Before proving this fact,
we make the following simple observations.

######  Observation C.1.

A set that is negative at time $t$ remains negative at all times
$t^{\prime}\geq t$.

######  Observation C.2.

If a set $I$ is negative at time $t$, then all supersets of $I$ are negative
at time $t$.

By C.2, If $I$ is independent then all subsets of $I$ are independent at time
$t$. Therefore, for any set $J\subseteq I$, we have that
$\Pr[F_{J,t}]=\prod_{j\in J}\Pr[F_{j,t}]$. Consequently, for any disjoint
subsets $K,J$ of $I$, by the inclusion-exclusion principle and Invariant (19),
we have that

$\displaystyle\Pr[F_{K,t},\overline{F_{J,t}}]$
$\displaystyle=\sum_{r=0}^{|J|}(-1)^{r}\sum_{J^{\prime}\subseteq
J,|J^{\prime}|=r}\Pr[F_{K\cup
J^{\prime},t}]=\sum_{r=0}^{|J|}(-1)^{r}\sum_{J^{\prime}\subseteq
J,|J^{\prime}|=r}\prod_{j\in K\cup J^{\prime}}(1-x_{k}^{(t)})$
$\displaystyle=\prod_{k\in K}(1-x_{k}^{(t)})\cdot\prod_{j\in
J}x_{j}^{(t)}=\prod_{k\in K}\Pr[F_{k,t}]\cdot\prod_{j\in
J}\left(1-\Pr[F_{j,t}]\right).$

######  Observation C.3.

If set $I$ is independent at time $t$, then the variables $\\{F_{i,t}\mid i\in
I\\}$ are independent.

Our rounding algorithm for maximal sound algorithms is a special case of
Algorithm 1. In particular, it is obtained from the solution to Program (Prob-
Program) setting $b_{i}=1$ and $a_{1}=\frac{1-x_{2}-\Delta
x_{2}}{(1-x_{1})(1-x_{2})}$ and $a_{2}=\frac{1-x_{1}-\Delta
x_{1}}{(1-x_{1})(1-x_{2})}$. Our reason to present this special case is
threefold: (1) it is very simple to describe, (ii) its analysis is more
elegant than Algorithm 1, and (iii) it provides stronger negative correlation
properties, which yield efficient polynomial-time implementation of this
rounding scheme. This last point proves particularly useful, given that the
fractional matching algorithms we apply our rounding schemes are all maximal.

As asserted above, our rounding scheme of this section is very simple to
describe. It examines whether the (at most) two vertices whose fractional
value increased are negative or independent, and which of the offline vertices
is available to be matched. Then, it carefully decides probabilistically how
to match the new online vertex. The formal definition of the algorithm is the
following.

Algorithm 4 Lossless Rounding: The Maximal Case

1:for arrival of online node $t$ do

2: if $t$ has less than two neighbors then

3: add two dummy neighbors $i$ with $\Delta x_{i}=0$ and $x_{i}=1$ $\rhd$ used
to simplify notation

4: let $P_{t}:=\\{1,2\\}$ be the two neighbors of $t$ of highest $\Delta
x_{i}:=x_{i,t}$, and let $x_{i}:=x_{i}^{(t)}$

5: if $\\{1,2\\}$ are negative then

6: match $t$ to its sole free neighbor $i$ (if any) with probability
$\frac{\Delta x_{i}}{1-x_{i}}$

7: if $\\{1,2\\}$ are independent then

8: if only one $i\in\\{1,2\\}$ is free then

9: match $t$ to $i$

10: if both $1$ and $2$ are free then

11: match $t$ to node $1$ with prob. $\frac{1-x_{2}-\Delta
x_{2}}{(1-x_{1})(1-x_{2})}$ and to node $2$ with prob. $\frac{1-x_{1}-\Delta
x_{1}}{(1-x_{1})(1-x_{2})}$

We observe that the algorithm is well defined (and dummy vertices are never
matched). Indeed, as the fractional solution guarantees that $\Delta
x_{i}\in[0,1-x_{i}]$, we get that $\frac{\Delta x_{i}}{1-x_{i}}\in[0,1]$ and
$\frac{1-x_{i}-\Delta x_{i}}{(1-x_{1})(1-x_{2})}\geq 0$. On the other hand,
since $\Delta x_{1}+\Delta x_{2}=1-x_{1}x_{2}$, we have in 11 that
$\frac{1-x_{2}-\Delta x_{2}}{(1-x_{1})(1-x_{2})}+\frac{1-x_{1}-\Delta
x_{1}}{(1-x_{1})(1-x_{2})}=1$. The final equality also implies that $1,2$
cannot both be free after time $t$, i.e., $\Pr[F_{\\{1,2\\},t+1}]=0$.

We now turn to proving the key lemma in the analysis of Algorithm 4, namely,
that this algorithm maintains the above desired invariants.

######  Lemma C.4.

Algorithm 4 preserves invariants (19) and (20).

###### Proof.

We prove both invariants in tandem, by induction on $t$. Both invariants
clearly hold for $t=1$. Assume the invariants hold for time $t\geq 1$. We
prove that this implies the same for time $t+1$. For simplicity, we use the
shorthand $x_{i}:=x^{(t)}_{i}$ and $x^{\prime}_{i}:=x^{(t+1)}_{i}=x_{i}+\Delta
x_{i}$, where $\Delta x_{i}:=x_{i,t}$.

##### Proof of Invariant (19):

We prove that $\Pr[(i,t)\in\mathcal{M}]=x_{i,t}$ for each edge $(i,t)\in E$,
which implies Invariant (19) by linearity of expectation. We prove the claim
for $i=1$ (the proof for $i=2$ is symmetric). If $\\{1,2\\}$ are negative,
then, by the inductive hypothesis,

$\Pr[(1,t)\in M]=\Pr[F_{1,t},\overline{F_{2,t}}]\cdot\frac{\Delta
x_{1}}{1-x_{1}}=\Pr[F_{1,t}]\cdot\frac{\Delta x_{1}}{1-x_{1}}=\Delta x_{1}.$

If $\\{1,2\\}$ are independent, then by the inductive hypothesis,
$\Pr[F_{1,t},F_{2,t}]=(1-x_{1})(1-x_{2})$ and similarly,
$\Pr[F_{1,t},\overline{F_{2,t}}]=(1-x_{1})x_{2}=x_{2}-x_{1}x_{2}$.
Consequently, since $\Delta x_{1}+\Delta x_{2}=1-x_{1}x_{2}$, we have

$\displaystyle\Pr[(1,t)\in M]$
$\displaystyle=\Pr[F_{1,t},\overline{F_{2,t}}]+\Pr[F_{1,t},F_{2,t}]\cdot\frac{1-x_{2}-\Delta
x_{2}}{(1-x_{1})(1-x_{2})}=x_{2}-x_{1}x_{2}+1-x_{2}-\Delta x_{2}=\Delta
x_{1}.$

##### Proof of Invariant (20).

By C.1, a set $I$ that ever becomes negative stays negative. Therefore, we
only need to consider the case that $I$ (before the current step) is
independent, i.e., $\Pr\left[F_{I,t}\right]=\prod_{i\in I}(1-x_{i}).$ We prove
that before the arrival of node $t+1$, we have

$\Pr\left[F_{I,t+1}\right]\in\left\\{0,\prod_{i\in
I}(1-x^{\prime}_{i})\right\\}.$

The case $\\{1,2\\}\cap I=\emptyset$: Then $F_{i,t}=F_{i,t+1}$ and
$x_{i}=x^{\prime}_{i}$ for each $i\in I$, and so trivially

$\displaystyle\Pr\left[F_{I,t+1}\right]$
$\displaystyle=\Pr\left[F_{I,t}\right]=\prod_{i\in I}(1-x_{i})=\prod_{i\in
I}(1-x^{\prime}_{i}).$

##### The case $\\{1,2\\}\subseteq I$:

As observed above, after time $t$ at least one of $1,2$ must be matched, i.e.,
$\Pr[F_{\\{1,2\\},t+1}]=0$. Consequently,
$\Pr\left[F_{I,t+1}\right]\leq\Pr[F_{\\{1,2\\},t+1}]=0$.

##### The case $1\in I$ and $2\not\in I$ (the opposite case is symmetric):

Let $E_{1}$ be the event that $1$ is not matched to $t$. There are two sub-
cases to consider.

#####  $\\{1,2\\}$ are negative.

By C.2, $I\cup\\{2\\}$ is also negative, and so by independence of $I$,

$\displaystyle\Pr\left[\overline{F_{2,t}},F_{I,t}\right]=\Pr\left[F_{I,t}\right]-\Pr\left[F_{2,t},F_{I,t}\right]=\Pr\left[F_{I,t}\right]=\prod_{i\in
I}(1-x_{i}).$

Consequently, since $x^{\prime}_{1}=x_{1}+\Delta x_{1}$, we have that

$\displaystyle\Pr\left[F_{I,t+1}\right]$
$\displaystyle=\Pr\left[E_{1}\mid{F_{1,t}},F_{2,t}\right]\cdot\Pr\left[{F_{2,t}},F_{I,t}\right]+\Pr\left[E_{1}\mid{F_{1,t}},\overline{F_{2,t}}\right]\cdot\Pr\left[\overline{F_{2,t}},F_{I,t}\right]$
$\displaystyle=0+\left(1-\frac{\Delta x_{1}}{1-x_{1}}\right)\cdot\prod_{i\in
I}(1-x_{i})=\prod_{i\in I}(1-x^{\prime}_{i}).$

#####  $\\{1,2\\}$ is independent:

If $I\cup\\{2\\}$ are also independent, then $\Pr[F_{2,t},F_{I,t}]=\prod_{i\in
I\cup\\{2\\}}(1-x_{i})$. Therefore, since $\Pr[E_{1}\mid
F_{1,t},F_{2,t}]=\frac{1-x_{1}-\Delta x_{1}}{(1-x_{1})(1-x_{2})}$, and again
using $x^{\prime}_{i}=x_{1}+\Delta x_{1}$, we have that

$\displaystyle\Pr\left[F_{I,t+1}\right]$
$\displaystyle=\Pr\left[E_{1}\mid{F_{1,t}},F_{2,t}\right]\cdot\Pr\left[{F_{2,t}},F_{I,t}\right]+\Pr\left[E_{1}\,\middle|\,F_{1,t},\overline{F_{2,t}},\right]\cdot\Pr\left[\overline{F_{2,t}},F_{I,t}\right]$
$\displaystyle=\frac{1-x_{1}-\Delta
x_{1}}{(1-x_{1})(1-x_{2})}\cdot(1-x_{2})\cdot\prod_{i\in
I}(1-x_{i})+0=\prod_{i\in I}(1-x^{\prime}_{i}).$

Finally, we address the case that $\\{1,2\\}$ is independent and
$I\cup\\{2\\}$ is negative. In this case, either $2$ is not matched before
time $t$, and some node in $I$ must be matched, or $2$ is matched before time
$t$ and the algorithm matches $1$ in 9. Put otherwise, we have that $I$
becomes negative, as

$\displaystyle\Pr\left[F_{I,t+1}\right]$
$\displaystyle=\Pr\left[E_{1}\mid{F_{1,t}},F_{2,t}\right]\cdot\Pr\left[{F_{2,t}},F_{I,t}\right]+\Pr\left[E_{1}\mid{F_{1,t}},\overline{F_{2,t}}\right]\cdot\Pr\left[\overline{F_{2,t}},F_{I,t}\right]=0.\qed$

From Invariant (19), together with linearity of expectation, we have that
$\Pr[(i,t)\in\mathcal{M}]=x_{i,t}$ for each edge $(i,t)$. That is, we obtain
our main technical result: an online lossless rounding scheme for two-choice
independently-maximal fractional algorithms. To conclude 1.3 it remains to
give a polytime implementation of this algorithm.

An Efficient Implementation. Algorithm 4 requires knowledge of whether or not
pairs $\\{1,2\\}$ are negative at time $t$. That is, it must distinguish
between $\Pr[F_{\\{1,2\\},t}]=0$ and
$\Pr[F_{\\{1,2\\},t}]=\Pr[F_{1,t}]\cdot\Pr[F_{2,t}]$. This can be easily done
in exponential time by maintaining the entire probability space. In Section
C.2 we give a more efficient implementation, by explicitly keeping track only
of pairwise correlations.

######  Lemma C.5.

Algorithm 4 can be implemented in $O(n)$ time per online node arrival.

###  C.2 An Efficient Implementation of Algorithm 4

In this section we present an efficient implementation of Algorithm 4 when run
with independent random variables.

The only non-trivial part of an implementation of Algorithm 4 is determining
whether or not pairs $\\{1,2\\}$ are negative. That is, we need to distinguish
between $\Pr[F_{1,t},F_{2,t}]=0$ and
$\Pr[F_{1,t},F_{2,t}]=(1-x^{(t)}_{1})\cdot(1-x^{(t)}_{2})$. This is trivial to
check if $x^{(t)}_{1}=1$ or $x^{(t)}_{2}$, since Invariant (20) implies that
any pair (and indeed, any set) $I$ containing a vertex $i$ with fractional
degree $x^{(t)}_{i}=1$ is negative at time $t$, since
$\Pr\left[F_{I,t}\right]\in\\{0,\prod_{i}(1-x^{(t)}_{i})\\}=\\{0\\}$. We
therefore focus on pairs which are not trivially negative, as in the following
definition.

######  Definition C.6.

A set $I\subseteq[n]$ is _strictly negative_ if it is negative and
$x^{(t)}_{i}\neq 1$ for all $i\in I$.

Now, determining whether a pair $\\{1,2\\}$ is strictly negative can be easily
implemented in exponential time, by considering the decision tree defined by
the algorithm. A much more efficient implementation is possible, however, as
we now show.

Recall that by C.2, if a set $I$ contains a pair of nodes which are negative,
then $I$ must itself be negative. The following lemma, which will prove useful
in order to implement our algorithm efficiently, shows that the converse is
also true for strictly negative sets and pairs. That is, any strictly negative
set $I$ has a strictly negative “witness” consisting of a pair of nodes in
$I$.

######  Lemma C.7.

A set of offline nodes $I$, $|I|\geq 2$ with $x^{(t)}_{i}\neq 1$ for all $i\in
I$ is strictly negative if and only if it contains a pair $J\subseteq I$,
$|J|=2$ which is itself strictly negative.

###### Proof.

The “if” direction follows from C.2 and definition of strict negativity. We
prove the “only if” direction for all sets $I$ by induction on $t$. The claim
holds vacuously at time $t=1$, at which point there are no negative sets. For
the inductive step, consider some such set $I$ with $x^{(t+1)}_{i}\neq 1$ for
all $i\in I$ and time $t+1$.

If $I$ was (strictly) negative by time $t$, then there exists a pair
$J\subseteq I$, $|J|=2$ which is strictly negative by time $t$, and by C.1,
both $I$ and $J$ remain negative at time $t+1$. Therefore, $J$ is the desired
strictly negative pair at time $t+1$ contained in $I$.

Now, suppose $I$ was not strictly negative at time $t$, but it is at time
$t+1$. Denote by $\\{1,2\\}$ the neighbors of $t$ with non-zero probability of
being matched to $t$. (Note that these must indeed be a pair, since if $t$ can
only be matched to at most one node $1$, this node must reach fractional
degree $x_{1}+\Delta x_{1}=\frac{x_{1}+x_{2}+1-x_{1}x_{2}}{2}=1$, and so all
sets that become negative at time $t$ are not strictly negative.) Inspecting
the proof of C.4, we find that either $I\supseteq\\{1,2\\}$, in which case
$J=\\{1,2\\}$ is the desired pair, or (wlog) $I\cap\\{1,2\\}=\\{1\\}$, and we
have that $\\{1,2\\}$ is independent by time $t$ and $I\cup\\{2\\}$ is
(strictly) negative by time $t$. Then, by the inductive hypothesis, we have
that $I\cup\\{2\\}$ contains a (strictly) negative pair $J^{\prime}$ by time
$t$. Since $I$ is not negative by time $t$, C.2 implies that the pair
$J^{\prime}$ cannot be a subset of $I$, and since $\\{1,2\\}$ is also not
negative at time $t$, we know that $J^{\prime}\neq\\{1,2\\}$, and so
$J^{\prime}=\\{2,i\\}$ for some $i\in I$. That is, we have that
$\Pr[F_{i,t},F_{2,t}]=0$, and therefore $F_{i,t}\leq\overline{F_{2,t}}$. (In
words, if $i$ is free, $2$ must be matched.) Consequently, we find that the
pair $\\{1,i\\}\subseteq I$ becomes negative, since

$\displaystyle\Pr[F_{1,t+1},F_{i,t+1}]$
$\displaystyle\leq\Pr[F_{1,t+1},F_{i,t}]\leq\Pr[F_{1,t+1},\overline{F_{2,t}}]=0,$

where the last inequality relies on $\\{1,2\\}$ previously being independent,
and so $\Pr[F_{1,t+1}\mid\overline{F_{2,t}}]=0.$ We conclude that if $I$
satisfying $x^{(t+1)}_{i}\neq 1$ for all $i\in I$ is strictly negative at time
$t+1$, then there exists some pair $J\subseteq I$ which is itself strictly
negative at time $t+1$. ∎

For any offline node $i$ which has $x^{(t)}_{i}\neq 1$, we denote the all
offline nodes $j$ such that the pair $\\{i,j\\}$ is strictly negative by time
$t$ by

$S^{(t)}_{i}:=\\{j\mid\\{i,j\\}\textrm{ are strictly negative by time }t\\}.$

The following lemmas characterize the changes to these sets from time $t$ to
$t+1$, allowing for simple maintenance of these sets over time.

######  Lemma C.8.

If $t$ has a single neighbor $1$ with non-zero probability of being matched to
$t$, then $S^{(t+1)}_{1}=\emptyset$ and
$S^{(t+1)}_{i}=S^{(t)}_{i}\setminus\\{1\\}$ for all $i\neq 1$, while
$S^{(t+1)}_{1}=\emptyset$.

###### Proof.

Follows from $1$ reaching fractional degree $x^{(t+1)}_{1}=1$ in this case,
and therefore $1$ no longer belongs to any strictly negative set, while for
all other nodes $i\neq 1$, we have that $F_{i,t}\equiv F_{i,t+1}$, and so all
pairs $\\{i,j\\}\not\ni 1$ are strictly negative at time $t+1$ if and only if
they are strictly negative at time $t$. ∎

######  Lemma C.9.

Let $t$ be an online node with non-zero probability of being matched to nodes
in $\\{1,2\\}$. Then, we have

$\displaystyle S^{(t+1)}_{i}=\begin{cases}S^{(t)}_{1}\cup
S^{(t)}_{2}\cup\\{2\\}&i=1\\\ S^{(t)}_{2}\cup S^{(t)}_{1}\cup\\{1\\}&i=2\\\
S^{(t)}_{i}\cup\\{2\\}&i\in S^{(t)}_{1}\\\ S^{(t)}_{i}\cup\\{1\\}&i\in
S^{(t)}_{2}\\\ S^{(t)}_{i}&i\not\in\\{1,2\\}\cup S^{(t)}_{1}\cup
S^{(t)}_{2}.\end{cases}$

###### Proof.

We note that for independently-maximal fractional algorithms no node reaches
fractional degree $x^{(t+1)}_{i}=1$ at time $t$. Therefore, by C.1, for all
$i$, we have that $S^{(t+1)}_{i}\supseteq S^{(t)}_{i}$. We will show that our
expression for $S^{(t+1)}_{i}\setminus S^{(t)}_{i}$ is precisely the set of
all other nodes $j$ such that $\\{i,j\\}$ is strictly negative at time $t+1$
but not at time $t$.

Consider a pair $I=\\{i,j\\}$ which was not strictly negative at time $t$, but
became strictly negative at time $t+1$. In particular, by monotonicity of
$x_{i}$ over time, this implies $I$ must have been independent at time $t$. By
the proof of C.4, this implies that one of two cases must hold:

  1. 1.

$I=\\{1,2\\}$.

  2. 2.

$1\in I$ and $2\not\in I$ (or vice versa) and $\\{1,2\\}$ is independent at
time $t$.

For the former case, this implies that $\Pr[F_{1,t+1},F_{2,t+1}]=0$, and
therefore $1\in S^{(t+1)}_{2}$ and $2\in S^{(t+1)}_{1}$. For the latter case,
consider a node $i\in S^{(t)}_{2}$. That is, some node $i$ such that
$\\{i,2\\}$ is negative, and so $\Pr[F_{i,t},F_{2,t}]=0$. This implies that
$F_{i,t}\leq\overline{F_{2,t}}$. (In words, if $i$ is free, $2$ must be
matched.) Consequently, we find that the pair $\\{1,i\\}\subseteq I$ becomes
negative, since

$\displaystyle\Pr[F_{1,t+1},F_{i,t+1}]$
$\displaystyle\leq\Pr[F_{1,t+1},F_{i,t}]\leq\Pr[F_{1,t+1},\overline{F_{2,t}}]=0,$

where the last inequality relies on $\\{1,2\\}$ being independent at time $t$,
and so $\Pr[F_{1,t+1}\mid\overline{F_{2,t}}]=0.$ And indeed, we have that
$S^{(t)}_{2}\subseteq S^{(t+1)}_{1}$. (Symmetrically, we have that
$S^{(t)}_{1}\subseteq S^{(t+1)}_{2}$.)

We conclude that our expression for $S^{(t+1)}_{i}$ is correct. ∎

The two preceding lemmata yield a simple linear-time algorithm for maintaining
the negative pairs (by maintaining the sets $S^{(t)}_{i}$, in addition to the
sets $x^{(t)}_{i}$), which by the preceding discussion yields an efficient
implementation of our algorithm. See C.5

##  Appendix D Deferred Proofs of Section 4

In this section we provide of lemmas and theorems deferred from Section 4,
restated for ease of reference.

###  D.1 The Weighted Algorithm

See 4.11

###### Proof.

Dropping the subscript $t$, since it will be clear from context, what we wish
to prove is that for any online time $t$ and each of the cases in the
algorithm’s definition we have that $\frac{\Delta D}{\Delta P}\leq
1+\frac{10}{11}$. We next analyze all cases, showing that in all cases the
change in the primal value divided by the dual cost is at most
$1+\frac{10}{11}$.

Case 1 ($x_{1}=0,x_{2}=0$): In this case we can assume wlog that $w_{1}=1$ and
$w_{2}\geq 1$. If $w_{2}\leq\frac{1}{1-y_{1}}=\frac{38}{19}$ then,
$x_{1}=x_{2}=\frac{1}{2}$. The value of the online node can be at most
$\max\\{1,w_{2}(1-y_{1})\\}\leq 1$. Thus,

$\frac{\Delta D}{\Delta
P}=\frac{1+y_{1}+w_{2}y_{1}}{\frac{1}{2}(1+w_{2})}\leq\frac{1+y_{1}+y_{1}}{1}=1+\frac{10}{11}.$

If $w_{2}\geq\frac{1}{1-y_{1}}$ we set $x_{2}=1$ and we may set the value of
the online node to $w_{2}$. In this case,

$\frac{\Delta D}{\Delta
P}=\frac{1+w_{2}}{w_{2}}\leq\frac{1+\frac{1}{1-y_{1}}}{\frac{1}{1-y_{1}}}=2-y_{1}=1+\frac{6}{11}.$

Case 2 ($x_{1}=\frac{1}{2},x_{2}=\frac{1}{2}$): In this case we can assume
wlog that $w_{1}=1$ and $w_{2}\geq 1$. If
$w_{2}\leq\frac{1-y_{1}}{1-y_{2}}=\frac{16}{3}\approx 5.3$ then,
$x_{1}=x_{2}=\frac{7}{8}$. The value of the online node can be set to at most
$\max\\{1-y_{1},w_{2}(1-y_{1})\\}\leq 1-y_{1}$. Thus,

$\frac{\Delta D}{\Delta
P}=\frac{1-y_{1}+y_{2}-y_{1}+w_{2}(y_{2}-y_{1})}{\frac{3}{8}(1+w_{2})}\leq\frac{1-y_{1}+y_{2}-y_{1}+1(y_{2}-y_{1})}{\frac{3}{8}(1+1)}=1+\frac{10}{11}.$

If $w_{2}\geq\frac{1-y_{1}}{1-y_{2}}$ we set $x_{2}=1$ and the value of the
online node can be set to $1-y_{1}$. In this case,

$\frac{\Delta D}{\Delta
P}=\frac{1-y_{1}+w_{2}(1-y_{1})}{\frac{1}{2}w_{2}}\leq\frac{1-y_{1}+\frac{(1-y_{1})^{2}}{1-y_{2}}}{\frac{1}{2}\frac{1-y_{1}}{1-y_{2}}}=\frac{1-y_{2}+1-y_{1}}{0.5}=1+\frac{13}{44}.$

Case 3 ($x_{1}=\frac{7}{8},x_{2}=\frac{7}{8}$): In this case we can assume
wlog that $w_{1}=1$ and $w_{2}\geq 1$. We set $x_{2}=1$. Thus,

$\frac{\Delta D}{\Delta
P}=\frac{1-y_{2}+w_{2}(1-y_{2})}{\frac{1}{8}w_{2}}\leq\frac{2-2y_{2}}{\frac{1}{8}}=1+\frac{7}{11}.$

Case 4 ($x_{1}=0,x_{2}=\frac{1}{2}$): Assume that $w_{1}=1$ If
$w_{2}\leq\frac{3}{2}$ then we set $x_{1}=1$. In this case $w_{2}(1-y_{1})\leq
1$ and so the online node can get value of $w_{2}(1-y_{1})$. Thus,

$\frac{\Delta D}{\Delta
P}=\frac{w_{2}(1-y_{1})+1}{1}\leq\frac{\frac{3}{2}(1-y_{1})+1}{1}=1+\frac{9}{11}.$

If $w_{2}\geq\frac{3}{2}$ then we set $x_{1}=\frac{1}{2},x_{2}=1$. In this
case we may set the online node to 1. Thus,

$\frac{\Delta D}{\Delta
P}=\frac{1+y_{1}+w_{2}(1-y_{1})}{\frac{1}{2}(1+w_{2})}\leq\frac{1+y_{1}+\frac{3}{2}(1-y_{1})}{\frac{1}{2}(1+\frac{3}{2})}=1+\frac{9}{11}.$

Case 5 ($x_{1}=0,x_{2}=\frac{7}{8}$): Assume that $w_{1}=1$ If $w_{2}\leq 5.5$
then we set $x_{1}=1$. In this case $w_{2}(1-y_{2})\leq 1$ and we may set the
online node to $w_{2}(1-y_{2})$. Thus,

$\frac{\Delta D}{\Delta
P}=\frac{w_{2}(1-y_{2})+1}{1}\leq\frac{5.5(1-y_{2})+1}{1}=1+\frac{9}{16}.$

If $w_{2}\geq 5.5$ then we set $x_{1}=\frac{7}{8},x_{2}=1$. In this case we
may set the online node to 1. Thus,

$\frac{\Delta D}{\Delta
P}=\frac{1+y_{2}+w_{2}(1-y_{2})}{\frac{7}{8}+\frac{1}{8}w_{2}}\leq\frac{1+y_{2}+5.5(1-y_{2})}{\frac{7}{8}+\frac{5.5}{8}}\approx
1.57.$

Case 6 ($x_{1}=\frac{1}{2},x_{2}=\frac{7}{8}$): Assume that $w_{1}=1$. If
$w_{2}\leq 4$ then we set $x_{1}=1$. In this case $w_{2}(1-y_{2})\leq 1$ and
we may set the online node to $w_{2}(1-y_{2})$. Thus,

$\frac{\Delta D}{\Delta
P}=\frac{w_{2}(1-y_{2})+1-y_{1}}{\frac{1}{2}}\leq\frac{4(1-y_{2})+1-y_{1}}{\frac{1}{2}}=1+\frac{10}{11}.$

If $w_{2}\geq 4$ then we set $x_{2}=1$. In this case we may set the online
node to $1-y_{1}$. Thus,

$\frac{\Delta D}{\Delta
P}=\frac{1-y_{1}+w_{2}(1-y_{2})}{\frac{1}{8}w_{2}}\leq\frac{1-y_{1}+4(1-y_{2})}{\frac{4}{8}}=1+\frac{10}{11}.$

Case 7 ($x_{1}<1,x_{2}=1$): In this case we may set the online node to $0$.
Then,

$\displaystyle\frac{\Delta D}{\Delta P}$
$\displaystyle=\frac{1-y(x_{1})}{1-x_{1}}\leq\frac{12}{11}.\qed$

##  Appendix E Construction of Small-Bias Probability Spaces

In this section we prove 2.3 for the sake of completeness, as it pertains to
the construction of $(\delta,k)$-dependent distributions with $\delta>0$ that
we use.

See 2.3

We describe a construction suggested by Naor and Naor [42]. Consider a
distribution $\mathcal{\mathcal{D}}$ over $\\{0,1\\}^{n}$ random variables.

######  Definition E.1.

The _bias_ of a subset $S\subseteq\\{1,\ldots,n\\}$ for a distribution
$\mathcal{D}$ is

${\rm bias}_{\mathcal{D}}(S):=\left|\Pr_{\mathcal{D}}\left[\sum_{i\in
S}x_{i}\equiv 0\pmod{2}\right]-\Pr_{\mathcal{D}}\left[\sum_{i\in S}x_{i}\equiv
1\pmod{2}\right]\right|.$

We say that $\mathcal{D}$ is _$k$ -wise $\epsilon$-biased_ if for every
$S\subseteq\\{1,\ldots,n\\}$ of size at most $|S|\leq k$, we have ${\rm
bias}_{\mathcal{D}}(S)\leq\epsilon$. It is shown by Naor and Naor [42] that
random variables that are $k$-wise $\epsilon$-biased are also
$(\delta,k)$-dependent for $\delta=2^{{k\over 2}}\cdot\epsilon$.

A construction by [4] for uniform $k$-wise random variables goes as follows.
Let $v_{1},\ldots,v_{n}\in\\{0,1\\}^{h}$ be vectors that are linearly $k$-wise
independent over GF[2], with $h={k\over 2}\log n$. Such vectors are known to
exist, and moreover can be constructed in polynomial time (e.g., rows of a
parity check matrix of a BCH code). Choose $r\in\\{0,1\\}^{h}$ uniformly at
random and define $x_{i}:=\langle v_{i},r\rangle$, for $i=1,\ldots,n$. It is
easy to see that the resulting random variables $x_{1},x_{2},\dots,x_{n}$ over
$\\{0,1\\}^{n}$ are $k$-wise independent.

To construct $k$-wise $\epsilon$-biased random variables, Naor and Naor [42]
use the same construction as above, except that $r$ is now sampled from an
$\epsilon$-biased distribution over $h$ random variables (instead of a
uniformly i.i.d. source).

######  Claim E.2.

The $n$ random variables constructed by sampling $r$ from an $\epsilon$-biased
source are $k$-wise $\epsilon$-biased random variables.

###### Proof.

For every subset $S$ of cardinality at most $|S|\leq k$, we have

$\sum_{i\in S}x_{i}=\sum_{i\in S}\langle v_{i},r\rangle=r\cdot\sum_{i\in
S}v_{i}=r\cdot M_{S},$

where $M_{S}\stackrel{{\scriptstyle\Delta}}{{=}}\sum_{i\in S}v_{i}$. Since the
vectors are $k$-wise independent, $M_{S}\neq\vec{0}$. Denoting by
$I\subseteq[h]$ the set of indices $i$ for which $(M_{S})_{i}=1$, we have

$\displaystyle{\rm bias}(S)$ $\displaystyle=\left|\Pr\left[\sum_{i\in
S}x_{i}\equiv 0\pmod{2}\right]-\Pr\left[\sum_{i\in S}x_{i}\equiv
1\pmod{2}\right]\right|$ $\displaystyle=\left|\Pr\left[r\cdot M_{S}\equiv
0\pmod{2}\right]-\Pr\left[r\cdot M_{S}\equiv 1\pmod{2}\right]\right|$
$\displaystyle=\left|\Pr\left[\sum_{i\in I}r_{i}\equiv
0\pmod{2}\right]-\Pr\left[\sum_{i\in I}r_{i}\equiv 1\pmod{2}\right]\right|$
$\displaystyle\leq\epsilon.\qed$

Thus, the number of $\epsilon$-biased random variables required for the
construction is $h=k\log n$. The cardinality of a sample space of an
$\epsilon$-biased distribution over $h$ variables constructed by [42] is
linear in the number of random variables. Specifically, it is of size
$O(h/\epsilon^{3})$. Therefore, we need $\log(O(h/\epsilon^{3}))$ random bits
to sample uniformly at random from this distribution, from which we obtain
$r$. Finally, in order to compute any $x_{i}=\langle v_{i},r\rangle$, we only
spend $O(h)=O(k\cdot\log n)$ time. As mentioned before, the vectors $v_{i}$
can be computed in polynomial time [42]. This concludes the proof of Lemma
2.3, since to obtain obtain $(\delta,k)$-dependence, we need $\delta\leq
2^{{k\over 2}}\cdot\epsilon$, and so picking $\epsilon=\delta\cdot 2^{-{k\over
2}}$ yields a $(\delta,k)$-dependent distribution, using
$\log(O(h/\epsilon^{3}))=\log\log n+O(k+\log(1/\delta))+O(1)$ random bits.

## References

  * Adamaszek et al. [2012] Adamaszek, A., Czumaj, A., Englert, M., and Räcke, H. 2012\.  An $o(\log k)$-competitive algorithm for generalized caching.  In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1681–1689.
  * Aggarwal et al. [2011] Aggarwal, G., Goel, G., Karande, C., and Mehta, A. 2011\.  Online vertex-weighted bipartite matching and single-bid budgeted allocations.  In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1253–1264.
  * Alon et al. [2009] Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., and Naor, J. 2009\.  The online set cover problem.  SIAM Journal on Computing (SICOMP) 39, 2, 361–370.
  * Alon et al. [1986] Alon, N., Babai, L., and Itai, A. 1986\.  A fast and simple randomized parallel algorithm for the maximal independent set problem.  J. Algorithms 7, 4, 567–583.
  * Bansal et al. [2011] Bansal, N., Buchbinder, N., Madry, A., and Naor, J. 2011\.  A polylogarithmic-competitive algorithm for the k-server problem.  In Proceedings of the 52nd Symposium on Foundations of Computer Science (FOCS). 267–276.
  * Bansal et al. [2012a] Bansal, N., Buchbinder, N., and Naor, J. 2012a.  A primal-dual randomized algorithm for weighted paging.  Journal of the ACM (JACM) 59, 4, 1–24.
  * Bansal et al. [2012b] Bansal, N., Buchbinder, N., and Naor, J. 2012b.  Randomized competitive algorithms for generalized caching.  SIAM Journal on Computing (SICOMP) 41, 2, 391–414.
  * Bansal et al. [2010] Bansal, N., Buchbinder, N., and Naor, J. S. 2010\.  Metrical task systems and the k-server problem on hsts.  In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP). 287–298.
  * Böckenhauer et al. [2014] Böckenhauer, H.-J., Komm, D., Královič, R., and Rossmanith, P. 2014\.  The online knapsack problem: Advice and randomization.  Theoretical Computer Science (TCS) 527, 61–72.
  * Boyar et al. [2017] Boyar, J., Favrholdt, L. M., Kudahl, C., Larsen, K. S., and Mikkelsen, J. W. 2017\.  Online algorithms with advice: a survey.  ACM Computing Surveys (CSUR) 50, 2, 1–34.
  * Bubeck et al. [2019] Bubeck, S., Cohen, M. B., Lee, J. R., and Lee, Y. T. 2019\.  Metrical task systems on trees via mirror descent and unfair gluing.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, T. M. Chan, Ed. SIAM, 89–97.
  * Bubeck et al. [2018] Bubeck, S., Cohen, M. B., Lee, Y. T., Lee, J. R., and Mądry, A. 2018\.  K-server via multiscale entropic regularization.  In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC). 3–16.
  * Buchbinder et al. [2019] Buchbinder, N., Gupta, A., Molinaro, M., and Naor, J. 2019\.  k-servers with a smile: online algorithms via projections.  In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 98–116.
  * Buchbinder et al. [2007] Buchbinder, N., Jain, K., and Naor, J. S. 2007\.  Online primal-dual algorithms for maximizing ad-auctions revenue.  In Proceedings of the 15th Annual European Symposium on Algorithms (ESA). 253–264.
  * Buchbinder and Naor [2009] Buchbinder, N. and Naor, J. S. 2009\.  The design of competitive online algorithms via a primal: dual approach.  Foundations and Trends® in Theoretical Computer Science (TCS) 3, 2–3, 93–263.
  * Coester and Lee [2019] Coester, C. and Lee, J. R. 2019\.  Pure entropic regularization for metrical task systems.  In Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, A. Beygelzimer and D. Hsu, Eds. Proceedings of Machine Learning Research Series, vol. 99. PMLR, 835–848.
  * Cohen et al. [2019] Cohen, I. R., Peng, B., and Wajc, D. 2019\.  Tight bounds for online edge coloring.  In Proceedings of the 60th Symposium on Foundations of Computer Science (FOCS). 1–25.
  * Cohen and Wajc [2018] Cohen, I. R. and Wajc, D. 2018\.  Randomized online matching in regular graphs.  In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 960–979.
  * Devanur et al. [2013] Devanur, N. R., Jain, K., and Kleinberg, R. D. 2013\.  Randomized primal-dual analysis of ranking for online bipartite matching.  In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 101–107.
  * Dürr et al. [2016] Dürr, C., Konrad, C., and Renault, M. 2016\.  On the power of advice and randomization for online bipartite matching.  In Proceedings of the 24th Annual European Symposium on Algorithms (ESA). 37:1–37:16.
  * Emek et al. [2011] Emek, Y., Fraigniaud, P., Korman, A., and Rosén, A. 2011\.  Online computation with advice.  Theoretical Computer Science (TCS) 412, 24, 2642–2656.
  * Fahrbach et al. [2020] Fahrbach, M., Huang, Z., Tao, R., and Zadimoghaddam, M. 2020\.  Edge-weighted online bipartite matching.  In Proceedings of the 61st Symposium on Foundations of Computer Science (FOCS).  To appear.
  * Feldman et al. [2009] Feldman, J., Korula, N., Mirrokni, V., Muthukrishnan, S., and Pál, M. 2009\.  Online ad assignment with free disposal.  In Proceedings of the 5th Conference on Web and Internet Economics (WINE). 374–385.
  * Fortuin et al. [1971] Fortuin, C. M., Kasteleyn, P. W., and Ginibre, J. 1971\.  Correlation inequalities on some partially ordered sets.  Communications in Mathematical Physics 22, 2, 89–103.
  * Gamlath et al. [2019] Gamlath, B., Kapralov, M., Maggiori, A., Svensson, O., and Wajc, D. 2019\.  Online matching with general arrivals.  In Proceedings of the 60th Symposium on Foundations of Computer Science (FOCS). 26–38.
  * Gandhi et al. [2002] Gandhi, R., Khuller, S., Parthasarathy, S., and Srinivasan, A. 2002\.  Dependent rounding in bipartite graphs.  In Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS). 323–332.
  * Gandhi et al. [2006] Gandhi, R., Khuller, S., Parthasarathy, S., and Srinivasan, A. 2006\.  Dependent rounding and its applications to approximation algorithms.  Journal of the ACM (JACM) 53, 3, 324–360.
  * Gupta et al. [2017] Gupta, A., Krishnaswamy, R., Kumar, A., and Panigrahi, D. 2017\.  Online and dynamic algorithms for set cover.  In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC). 537–550.
  * Huang et al. [2020a] Huang, Z., Kang, N., Tang, Z. G., Wu, X., Zhang, Y., and Zhu, X. 2020a.  Fully online matching.  Journal of the ACM (JACM) 67, 3, 1–25.
  * Huang et al. [2018] Huang, Z., Tang, Z. G., Wu, X., and Zhang, Y. 2018\.  Online vertex-weighted bipartite matching: Beating 1-1/e with random arrivals.  In Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP). 1070–1081.
  * Huang et al. [2020b] Huang, Z., Tang, Z. G., Wu, X., and Zhang, Y. 2020b.  Fully online matching ii: Beating ranking and water-filling.  In Proceedings of the 61st Symposium on Foundations of Computer Science (FOCS). To appear.
  * Huang and Tao [2019] Huang, Z. and Tao, R. 2019\.  Understanding zadimoghaddam’s edge-weighted online matching algorithm: Unweighted case.  arXiv preprint arXiv:1910.02569.
  * Huang and Zhang [2020] Huang, Z. and Zhang, Q. 2020\.  Online primal dual meets online matching with stochastic rewards: Configuration lp to the rescue.  In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC). 1153–1164.
  * Huang et al. [2020c] Huang, Z., Zhang, Q., and Zhang, Y. 2020c.  Adwords in a panorama.  In Proceedings of the 61st Symposium on Foundations of Computer Science (FOCS). To appear.
  * Karp et al. [1990] Karp, R. M., Vazirani, U. V., and Vazirani, V. V. 1990\.  An optimal algorithm for on-line bipartite matching.  In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC). 352–358.
  * Lee [2018] Lee, J. R. 2018\.  Fusible hsts and the randomized k-server conjecture.  In Proceedings of the 59th Symposium on Foundations of Computer Science (FOCS). 438–449.
  * Levin and Wajc [2021] Levin, R. and Wajc, D. 2021\.  Streaming submodular matching meets the primal-dual method.  In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). To appear.
  * Mehta [2013] Mehta, A. 2013\.  Online matching and ad allocation.  Foundations and Trends® in Theoretical Computer Science 8, 4, 265–368.
  * Mehta et al. [2007] Mehta, A., Saberi, A., Vazirani, U., and Vazirani, V. 2007\.  Adwords and generalized online matching.  Journal of the ACM (JACM) 54, 5, 22.
  * Mikkelsen [2016] Mikkelsen, J. W. 2016\.  Randomization can be as helpful as a glimpse of the future in online computation.  In Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP). 39:1–39:14.
  * Naor et al. [2011] Naor, J., Panigrahi, D., and Singh, M. 2011\.  Online node-weighted steiner tree and related problems.  In Proceedings of the 52nd Symposium on Foundations of Computer Science (FOCS). 210–219.
  * Naor and Naor [1993] Naor, J. S. and Naor, M. 1993\.  Small-bias probability spaces: Efficient constructions and applications.  SIAM Journal on Computing (SICOMP) 22, 4, 838–856.
  * Naor and Wajc [2018] Naor, J. S. and Wajc, D. 2018\.  Near-optimum online ad allocation for targeted advertising.  ACM Transactions on Economics and Computation (TEAC) 6, 3-4, 16.
  * Papadimitriou et al. [2021] Papadimitriou, C., Pollner, T., Saberi, A., and Wajc, D. 2021\.  Online stochastic max-weight bipartite matching: Beyond prophet inequalities.  In Proceedings of the 22nd ACM Conference on Economics and Computation (EC).
  * Pena and Borodin [2019] Pena, N. and Borodin, A. 2019\.  On extensions of the deterministic online model for bipartite matching and max-sat.  Theoretical Computer Science (TCS) 770, 1–24.
  * Renault and Rosén [2015] Renault, M. P. and Rosén, A. 2015\.  On online algorithms with advice for the k-server problem.  Theoretical Computer Science (TCS) 56, 1, 3–21.
  * Renault et al. [2015] Renault, M. P., Rosén, A., and van Stee, R. 2015\.  Online algorithms with advice for bin packing and scheduling problems.  Theoretical Computer Science (TCS) 600, 155–170.
  * Saberi and Wajc [2021] Saberi, A. and Wajc, D. 2021\.  The greedy algorithm is$\backslash$emph $\\{$not$\\}$ optimal for on-line edge coloring.
  * Ta-Shma [2017] Ta-Shma, A. 2017\.  Explicit, almost optimal, epsilon-balanced codes.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, H. Hatami, P. McKenzie, and V. King, Eds. ACM, 238–251.
  * Tang et al. [2020] Tang, Z. G., Wu, X., and Zhang, Y. 2020\.  Towards a better understanding of randomized greedy matching.  In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC). 1097–1110.
  * Wang and Wong [2015] Wang, Y. and Wong, S. C.-w. 2015\.  Two-sided online bipartite matching and vertex cover: Beating the greedy algorithm.  In Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP). 1070–1081.
  * Yao [1977] Yao, A. C.-C. 1977\.  Probabilistic computations: Toward a unified measure of complexity.  In Proceedings of the 18th Symposium on Foundations of Computer Science (FOCS). 222–227.