# Online Dependent Rounding Schemes

Joseph (Seffi) Naor Supported in part by Israel Science Foundation grant
2233/19 and United States - Israel Binational Science Foundation grant
2018352. Technion – Israel Institute of Technology  Aravind Srinivasan
Supported in part by NSF award number CCF-1918749, and by research awards from
Amazon and Google. University of Maryland, College Park  David Wajc111Part of
this work done while the author was at Stanford University. Google Research

###### Abstract

We study the abstract problem of rounding fractional bipartite $b$-matchings
online. The input to the problem is an unknown fractional bipartite
$b$-matching, which is exposed node-by-node on one side. The objective is to
maximize the _rounding ratio_ of the output matching $\mathcal{M}$, which is
the minimum over all fractional $b$-matching $\mathbf{x}$, and edges $e$, of
the ratio $\Pr[e\in\mathcal{M}]/x_{e}$. In offline settings, dependent
rounding schemes achieving a ratio of one and strong negative correlation
properties are known (e.g., Gandhi et al., FOCS’02, J.ACM’06 and Chekuri et
al., FOCS’10), and have found numerous applications. Motivated by online
applications, we present _online dependent-rounding schemes_ (ODRSes) for
$b$-matching.

For the basic case of a single offline node, i.e., uniform matroids (a.k.a.
_level sets_), we achieve an online rounding ratio of one. Moreover, we show
that our ODRS yields _the same distribution_ as (offline) pivotal sampling
(Srinivasan, FOCS’01, J.ACM’06), and so inherits the latter’s known strong
correlation properties. In arbitrary bipartite graphs, for which online
rounding ratios of one are impossible, we show that a combination of our
level-set ODRS with repeated invocations of _offline_ contention resolution
schemes (CRSes) yields a rounding ratio of $1-\frac{1}{e}\approx 0.632$. Our
main technical contribution is an ODRS breaking this pervasive bound, yielding
rounding ratios of $0.646$ and for $b$-matchings and simple matchings,
respectively. We obtain these results by grouping nodes and using CRSes for
negatively-correlated distributions, together with a new method we call _group
discount and individual markup_ , analyzed using the theory of negative
association.

Extending and applying our ODRSes, we obtain a number of new results,
including (directly) the first online bipartite edge-weighted matching
algorithms with ML predictions, and:

  1. 1.

The first results for online edge coloring _multigraphs_ under adversarial
arrivals, adding to the recent exciting work on online edge coloring, e.g.,
Kulkarni et al. (STOC’22), Bhattacharya et al. (SODA’21) and Cohen et al.
(FOCS’19).

  2. 2.

Improved polytime online approximation of the optimum (computationally-
unbounded) _online_ algorithm for online stochastic weighted bipartite
matching, improving on recent works of Papadimitriou et al. (EC’21) and
Braverman et al. (EC’22).

  3. 3.

A generalization of a result of Srinivasan (SODA’07) that improved a previous
result of Swamy and Shmoys (FOCS’05, SICOMP’12) to multi-stage stochastic
_multi-_ coverage.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Contributions
      1. 1.1.1 Extensions and Applications
    2. 1.2 Techniques
    3. 1.3 Further related work
  2. 2 Preliminaries
    1. 2.1 Negative association and strong Rayleigh properties
  3. 3 Online Level-Set Rounding
    1. 3.1 Offline level-set rounding
    2. 3.2 The online level-set rounding algorithm
    3. 3.3 Coupling the online and offline algorithms
  4. 4 Rounding $b$-Matchings Online
    1. 4.1 The improved ODRS: Overview and intuition
    2. 4.2 The core of the improved ODRS
      1. 4.2.1 The improved ODRS
      2. 4.2.2 The $b$-matching ODRS
  5. 5 Applications
    1. 5.1 Applications and extensions of the matching ODRS
      1. 5.1.1 Online edge coloring (multigraphs)
      2. 5.1.2 Stochastic extension
    2. 5.2 Application of the level-set ODRS
      1. 5.2.1 Multi-stage stochastic optimization
      2. 5.2.2 Negative association, fairness, diversity, and streaming
  6. 6 Lower Bounds
  7. 7 Summary and Open Questions
  8. A Additional Preliminaries
    1. A.1 Contention Resolution Schemes
    2. A.2 Negative correlation properties
    3. A.3 Odds and Ends
  9. B Deferred Proofs of Section 3
    1. B.1 Direct analysis of Algorithm 3
    2. B.2 Coupling the offline and online algorithms
  10. C Deferred Proofs of Section 4
    1. C.1 Polytime implementation
    2. C.2 Deferred proofs of the $b$-matching ODRS
  11. D Deferred Proofs of Section 6

##  1 Introduction

Online bipartite $b$-matching is a prototypical online problem, tracing its
origin to the seminal work of Karp et al. [51]. Here, nodes on one side of a
bipartite graph are revealed over time, and each node $v$ can be matched at
most $b_{v}$ times, with arriving nodes matched immediately and irrevocably.
This influential problem has been widely studied in various settings (e.g.,
fractional/integral, simple/capacitated, unweighted/vertex-weighted/edge-
weighted) [60, 50, 51, 2, 39, 12, 29, 11, 36, 41] and has been a cornerstone
of the online algorithms literature.

We study the abstract problem of online _randomized rounding of fractional
$b$-matchings_. Here, both online nodes and their edges’ associated fractions
in a fractional $b$-matching are revealed online. (The fractional matching may
be provided by a online fractional algorithm, or some machine-learned
advice—see discussion in Section 1.1.1.) An online dependent rounding scheme
(ODRS) must decide immediately and irrevocably, upon a node’s arrival, which
of its edges to match.222As in the offline dependent rounding schemes of [44],
the term _dependent_ here underscores the need for random choices to depend on
each other, since independent coin tosses do not yield a valid high-value
($b$-)matching.

In _offline_ settings, where all fractions and nodes are given upfront,
numerous dependent rounding schemes for $b$-matching are known with the
following desirable properties: they (1) match each edge with marginal
probability equal to its fraction in the fractional $b$-matching (thus
preserving any linear objective, while being oblivious to this objective), and
(2) guarantee strong negative correlation properties (thus guaranteeing
concentration and preservation of _submodular_ objectives) [66, 44, 22, 23,
19]. These dependent rounding schemes have been highly influential, and
yielded numerous applications in the approximation algorithms literature.

Unfortunately for _online_ applications, not only are all above offline
rounding schemes not implementable online, but online schemes satisfying
Property (1) are provably impossible [29, 28, 17]. For example, in recent work
[17], Buchbinder et al. asked what additional constraints can be imposed on
the fractional matching to allow for Property (1) to be satisfied exactly. In
this work, guided by the observation that approximate satisfaction of Property
(1) would still allow us to approximately preserve linear objectives (with the
ensuing applications), we study the natural complementary question: _How well
can one approximate Property (1)?_ Capturing this objective, we introduce the
notion of an _oblivious online rounding ratio_ , defined generally as follows.

######  Definition 1.1.

An ODRS $\mathcal{A}$ for a maximization problem has _(oblivious) rounding
ratio_ $\alpha\in[0,1]$ if, when (batches of) elements $e_{1},\dots,e_{n}$ are
revealed online with their associated fractions $x_{1},\dots,x_{n}$, with
$\vec{x}$ a valid fractional solution, $\mathcal{A}$ outputs an _integral_
solution $\mathcal{I}$ satisfying

$\Pr[e_{i}\in\mathcal{I}]\geq\alpha\cdot x_{i}\quad\forall i\in[n].$

This question has been intensely studied for matchings in the context of one
algorithmic paradigm: _online (batched) contention resolution schemes_
(OCRSes), e.g., [43, 58, 37, 38]. There, each arriving element $e_{i}$ is
_active_ independently with probability $x_{i}$,333Batched OCRSes [38] only
require independence between _batches_ of elements (e.g., edges of an arriving
node). and an OCRS outputs a feasible subset of active elements. An ODRS can
be obtained from an OCRS directly by simulating the activation process for
arriving elements. However, even for simple $b$-matching problems such as
rank-1 uniform matroids (selecting a single element), no rounding ratio beyond
$0.5$ is possible, via standard connections between OCRSes and the prophet
inequality problem [54, 43, 38]. Better oblivious rounding ratios are known
(via different approaches) for simple bipartite matchings [62, 28, 73, 65],
with the current best ratio standing at $0.526$ [65].

Can we improve on the previous best oblivious rounding ratios (for
$b$-matchings more generally)? Can we achieve the ratio of
$1-\frac{1}{e}$—ubiquitous in _competitive_ ratios of online matching
algorithms? Can we beat this bound, at least for key special cases?

###  1.1 Our Contributions

We provide positive answers to the above questions, and give multiple
applications of our new ODRSes. We focus on the online rounding questions in
this section.

One special case we consider is rounding $b$-matchings in a star graph with a
single offline node, also known as rounding uniform matroids, or _level sets_.
Herein, a sequence of fractions arrive online over time and the goal is to
round them to $\\{0,1\\}$ while preserving their marginals and the sum of
every prefix (up to floors or ceilings). As we show later, this is a useful
subroutine for rounding $b$-matchings in arbitrary bipartite graphs (and other
applications).

Our first contribution is an online level-set rounding algorithm breaking the
ratio of $1-\frac{1}{e}$ that is best possible via (even offline) CRSes [58,
24], attaining an oblivious rounding ratio of _one_. We thus provide an online
counterpart to the well-known offline algorithm of Srinivasan [66]. Indeed, as
we show, our algorithm’s output distribution matches the offline algorithm’s
output distribution, together with its useful properties, including strong
negative correlations (“Strong Rayleigh" property, see Section 2) implying
e.g., preservation of monotone _submodular_ objectives.

######  Theorem 1.2 (Informal).

There exists an online level-set rounding algorithm with rounding ratio of
one, and strong negative correlation properties.

In arbitrary bipartite graphs, an ODRS with rounding ratio of one is
impossible, even for simple matching, as discussed above. We further rule out
any better than $2\sqrt{2}-2\approx 0.828$ rounding ratio. On the positive
side, we show that combining our online level-set algorithm with the single-
item _offline_ contention resolution scheme (CRS) of Feige and Vondrák [40]
yields a simple ODRS with rounding ratio of $1-1/e\approx 0.632$. Our main
result breaks this ubiquitous bound.

######  Theorem 1.3.

There exist bipartite matching ($b$-matching) ODRSes with rounding ratio
($0.646$). No such ODRS has rounding ratio greater than $2\sqrt{2}-2\approx
0.828$.

####  1.1.1 Extensions and Applications

Our ODRSes and the techniques underlying them have a number of applications
and extensions. We briefly discuss these here, deferring detailed discussions
to Section 5.

##### Online edge coloring.

Our ability to round fractional matchings has implications to online edge
coloring. For this problem, it is known that the greedy algorithm’s
competitive ratio of $2$ is tight for graphs of low maximum degree
$\Delta=O(\log n)$ [8], while better competitive ratios are known for high-
degree graphs under various arrival models, mostly for simple graphs [27, 65,
55, 10, 3, 6]. For _multigraphs_ , positive results (competitive ratios
smaller than $2$) were only known under _random-order arrivals_ [3].
Addressing this gap between simple graphs and multigraphs, in Section 5.1.1 we
extend known reductions from $\alpha$-competitive edge coloring ($\alpha\geq
1$) to computing online matchings that match each (in this case, parallel)
edge with probability $\frac{1}{\alpha\Delta}$ [27]. We thus show that a
rounding ratio of $1/\alpha$ implies a competitive ratio of $\alpha+o(1)$ for
edge coloring multigraphs (and is, in fact, equivalent to it). Combined with
our rounding algorithms, this yields the first positive result for online
edge-coloring in multigraphs under adversarial arrivals, achieving a
competitive factor of $e/(e-1)-\Omega(1)$ in bipartite multigraphs, answering
a question of Schrijver [28, Sec. VI].

##### Stochastic optimization.

Another application of our techniques concerns the online stochastic bipartite
weighted matching problem, much studied in the online Prophet-Inequality
literature [38, 42, 35, 54]. (See Section 5.1.2 for formal definition.)
Recently, Papadimitriou et al. [62] initiated the study of efficiently
approximating the optimum _online_ algorithm for this problem. They showed
that it is pspace-hard to approximate the optimum algorithm within some
universal constant $\beta<1$, and provided a polynomial-time online algorithm
that $0.51$-approximates this online optimum. (In contrast, the best
competitive ratio, or approximation of the _offline_ optimum, is $0.5$ for
this problem [38].) The bound of [62] can be improved to $0.526$ using ideas
in [65] and was significantly improved to $1-1/e\approx 0.632$ by Braverman et
al. [16]. All three results are achieved via online rounding. Extending our
online rounding approach of 1.3 to such stochastic settings, we improve on the
recent bound of [16] and break the ubiquitous bound of $1-1/e$, providing an
online polytime -approximation of the optimal (computationally-unbounded)
online algorithm.

##### Algorithms with predictions.

Our ODRS of 1.3 finds a direct application in the burgeoning area of _online
algorithms with advice_ (see the survey [61] and site [1]). Here, an online
algorithm is equipped with machine-learned (ML) predictions concerning the
input. For example, many works show that for related problems, high-quality
fractional solutions are efficiently learnable and can guide integral
algorithms, via online rounding schemes [57, 56, 59]. Our ODRS immediately
yields the first online _edge-weighted_ bipartite matching algorithm with
predictions, getting a competitive ratio of $(1-1/e+\Omega(1))$ with
sufficiently good predictions. In contrast, with no predictions, only recently
was it shown how to break the barrier of $1/2$ for this problem (using _free
disposal_) [39, 12, 45], and $1-1/e+\Omega(1)$ is impossible to achieve even
in unweighted graphs [51].

##### Multi-Stage stochastic optimization.

In multi-stage stochastic optimization, uncertain parameters are stochastic
but their distributions get refined over time: actions in earlier stages are
cheaper but perhaps less accurate due to the stochasticity, while actions in
later stages are more expensive but more accurate. (See the survey [68].) A
basic example is the (hyper-)graph covering problem, where sets (hyperedges)
are revealed in $k$ stages, and must be covered by bought elements (nodes).
Swamy and Shmoys [69] presented a $2k$-approximation for this problem, later
improved to $2$, matching the offline hardness of the non-stochastic single-
stage problem, in [67]. Building on the framework of [69, 67], in Section
5.2.1 we generalize this result to allow for sets with _muti-_ coverage
demands. Our algorithms have approximation ratio of $2$ (and tending to _one_
in some settings), and these ratios hold w.h.p., building on our algorithm’s
strong negative correlation properties.

##### Fairness and diversity in allocation.

Building on the previous sentence, an even-stronger negative correlation
property—negative association—helps our rounding guarantee that its resultant
intersectional unfairness [18] (if any) is limited. Continuing on the theme of
ML advice, we prove that our rounding algorithm produces online allocations
(e.g., of vaccines as they are produced) from ML advice such that these
allocations do not impact multiple intersectional groups unfairly, with high
probability. Furthermore, our online-rounding algorithm only needs $O(\log n)$
space. In Section 5.2.2 we leverage this and the fact that diversity/fairness
models often lead to _monotone submodular_ objectives which work very well
with our rounding scheme, in order to develop logarithmic-space streaming
algorithms that act on ML advice, in order to produce provably-diverse search
results.

###  1.2 Techniques

In this section we highlight some of the key ideas that allow us to achieve
our main results, namely Theorems 1.2 and 1.3, deferring detailed discussions
of applications to later sections.

For level-set rounding, we provide a simple ODRS using _limited memory_ (i.e.,
both online and streaming) – only remembering how many edges/elements were
matched/taken – that achieves a rounding ratio of one. Surprisingly, we show
via a coupling argument that this online algorithm’s distribution is
_identical_ to that of (offline) pivotal sampling, a.k.a. Srinivasan sampling
[66]. This allows us to inherit this well-studied algorithm’s concentration
properties [66, 15, 31]. In particular, this implies that our online
algorithm’s output distribution satisfies the _Strong Rayleigh_ property (see
Section 2), which in turn implies a slew of negative correlation properties,
useful for our applications.

For our impossibility result, we rely on a Ramsey-theoretic probabilistic
lemma, whereby in any sufficiently large set of binary variables, some
(near-)positive correlation is inevitable. An extension of this lemma (6.3),
of possible independent interest, rules out algorithmic approaches based on
guaranteeing strict negative correlation between offline nodes’ matched
statuses.

##### ODRSes for $b$-matching.

Our first ODRS for $b$-matchings more broadly is obtained by interleaving our
level-set algorithm with repeated invocations of the _offline_ single-item
contention resolution scheme (CRS) of Feige and Vondrák [40]. (This is, to the
best of our knowledge, the first online algorithm to use offline CRSes in such
a black-box manner.) Specifically, we run independent copies of our level-set
algorithm, one per offline node, thus having each offline node $i$ “bid” for
arriving online node $t$ independently of other offline nodes with probability
$x_{i,t}$, while preserving the $b$-matching constraints of the offline nodes.
To preserve online nodes’ matching constraints, we then use the single-item
offline CRS of [40] at each time $t$: this CRS guarantees for such product
distributions that $t$ is allocated to at most one buyer, with every buyer $i$
being allocated item $t$ (i.e., $(i,t)$ being matched) with probability at
least $(1-1/e)\cdot x_{i,t}$, thus yielding a rounding ratio of $1-1/e$.

To improve on the above, we first note that the $(1-1/e)\cdot x_{it}$ bound is
loose if any of the $x_{it}$ fractions are bounded away from $0$. Indeed, this
$1-1/e$ factor is of the form

$\bigg{(}1-\prod_{j}(1-x_{it})\bigg{)}\bigg{/}\sum_{i}x_{i,t}\geq 1-1/e,$

where the inequality is loose if any $x_{it}$ is large. To beat this $1-1/e$
bound, we therefore simulate the existence of a large $x_{it}$, by _grouping_
offline nodes via a bin-packing heuristic, and letting at most one node per
group (bin) $B$ bid for $t$. The obtained distribution over biding offline
nodes is no longer a product distribution, but it is strongly negatively
correlated, and even negatively associated (see Section 2). This allows us to
achieve the same $1-1/e$ bound using CRSes for negatively correlated
distributions of Bansal and Cohen [7]. Moreover, this grouping allows us to
beat the $1-1/e$ ratio in some cases: In a very concrete sense, it results in
effectively a single aggregated offline node bidding with large probability
$\sum_{i\in B}x_{i,t}$, thus allowing us to beat the bound of $1-1/e$, if much
grouping occurs. Furthermore, thinking of bids as “costing” the offline node
future matching opportunities, we can even beat the bound of $1-1/e$ after
giving nodes in a group a “group discount”, and having them bid with lower
probability than $x_{i,t}$. This discounting then leaves offline nodes with
more budget (probability of not being matched), thus allowing us to charge
these nodes more at later times: in particular, when these offline nodes are
not grouped, we charge them an “individual markup”, by having them bid with
higher probability than $x_{i,t}$. This then increases the matching
probability of those $t$ for which little grouping occurs to beyond
$1-\frac{1}{e}$, and the improved rounding ratio follows.

###  1.3 Further related work

A natural approach to round a feasible fractional solution $\vec{x}$ is to
_activate_ each element $e$ independently w.p. $x_{e}$ and then pick a
feasible subset $\mathcal{I}$ of active elements, such that
$\Pr[e\in\mathcal{I}]\geq\alpha\cdot x_{e}$. The latter is obtained by
_contention resolution schemes_ (CRSes), first studied in offline settings for
single-item problems (rank-one matroids) by Feige and Vondrák [40] (see
Section 2), and later for arbitrary matroids by Chekuri et al. [22]. This
approach was then extended to online settings by Feldman et al. [43], and has
since become a bedrock of stochastic online problems, from prophet
inequalities [43], secretary problems [33, 34], posted-price mechanisms [21,
52] and sequential pricing [64], algorithmic contract design [9] and more.
Unfortunately, for bipartite matching ODRSes, using OCRSes (letting each $i$
bid for $t$ with probability $x_{i,t}$ independently of all prior bids,
including $i$’s) is of limited use: such OCRS-based OCRSes have rounding ratio
better at most $0.5$ even for rank-one matroids, by connections to the
prophet-inequality problem [38, 54]. Going beyond independent bids for each
pair $(i,t)$ is therefore crucial to obtain high oblivious rounding ratios.

Another online matching rounding approach is provided by the recent exciting
literature on Online Correlated Selection (OCS), first introduced in the
groundbreaking paper of Fahrbach et al. [39] (and its predecessor by Huang and
Tao [48]). Specifically, the OCSes of Gao et al. [45] underlie many rounding-
based online algorithms for edge-weighted matching [45], fair matching [46]
and i.i.d matching [70, 47]. This powerful machinery, however, does not
provide oblivious rounding guarantees, but rather per-offline-vertex
guarantees, and so is inapplicable for our problem applications.

##  2 Preliminaries

Problem Definition. In the online $b$-matching rounding problem, an a priori
unknown bipartite graph $G=(L,R,E)$ is revealed online, together with
fractions on the edges incident to the arriving edge’s vertices that satisfy
the $b$-matching constraints. In more detail, at each time $t$ an online
vertex $t\in L$ arrives, together with fractions $x_{i,t}$ assigned to its
edges to _offline neighbors_ $i\in R=[n]$. The fractions $x_{i,t}\in[0,1]$,
are promised to satisfy the (fractional) $b$-matching constraints, namely each
vertex $v\in(L\cup R)$ has fractional degree $\sum_{e\ni v}x_{e}$ at most
$b_{v}$. By splitting each online node $t$ with capacity $b_{t}$ into $b_{t}$
online unit-capacity nodes with identical edge sets and fractions
$x_{it}/b_{t}$ for each copy of edge $(i,t)$, we can assume WLOG that all
online nodes have unit capacity. Following arrival $t$, we must decide,
immediately and irrevocably, which edges of $t$ to add to the output
$b$-matching $\mathcal{M}$, while satisfying the (integral) $b$-matching
constraints of matching each vertex $v$ no more than $b_{v}$ times, and
striving for a large oblivious rounding ratio.

Our ODRSes for $b$-matchings will repeatedly invoke offline _contention
resolution schemes_ (CRSes), whose guarantees for product distributions, due
to Feige and Vondrák [40], and arbitrary distributions, due to Bansal and
Cohen [7], are given below. (For completeness, we provide a self-contained
proof for the general case in Appendix A.)

######  Lemma 2.1.

Let $\mathcal{D}:2^{[n]}\to\mathbb{R}_{\geq 0}$ be a distribution over subsets
of $[n]$, with its support denoted by
$\textrm{supp}(\mathcal{D})=\\{S\subseteq[n]\mid\Pr_{R\sim\mathcal{D}}[R=S]\neq
0\\}$. Then, there exists a randomized algorithm CRS($R,\vec{v})$ which on
input set $R\sim\mathcal{D}$ and vector $\vec{v}\in\mathbb{R}^{n}$, outputs a
subset $O\subseteq R$ of size $|O|\leq 1$ satisfying

$\Pr[i\in O]=v_{i}\cdot\min_{S\subseteq[n]}\frac{\Pr[R\cap
S\neq\emptyset]}{\sum_{i\in S}v_{i}}\qquad\qquad\forall i\in[n].$

The algorithm runs in time polynomial in $n$ if $\mathcal{D}$ is a product
distribution. Otherwise, it runs in time $\mathrm{poly}(n,T)$, where
$T\geq|\textrm{supp}(\mathcal{D})|$ is the time to compute and write down the
support of $\mathcal{D}$.

###  2.1 Negative association and strong Rayleigh properties

######  Definition 2.2.

Random variables $X_{1},\dots,X_{n}$ are _negatively associated (NA)_ if for
any two disjoint index sets $I,J\subseteq[n]$, $I\cap J=\emptyset$, and two
functions $f:\mathbb{R}^{|I|}\to\mathbb{R}$ and
$g:\mathbb{R}^{|J|}\to\mathbb{R}$ both non-decreasing,

$\mathbb{E}[f(X_{i}:i\in I)\cdot g(X_{j}:j\in J)]\leq\mathbb{E}[f(X_{i}:i\in
I)]\cdot\mathbb{E}[g(X_{j}:j\in J)].$

By a simple inductive argument, negative association implies negative cylinder
dependence [49].

######  Lemma 2.3.

For any real NA r.v.s $X_{1},\dots,X_{n}$ and reals $x_{1},\dots,x_{n}$, it
holds that

$\Pr\bigg{[}\bigwedge_{i}(X_{i}\geq x_{i})\bigg{]}\leq\prod_{i}\Pr[X_{i}\geq
x_{i}]\qquad\mbox{ {and} }\qquad\Pr\bigg{[}\bigwedge_{i}(X_{i}\leq
x_{i})\bigg{]}\leq\prod_{i}\Pr[X_{i}\leq x_{i}].$

The following family of NA distributions is due to Dubhashi and Ranjan [32].

######  Lemma 2.4.

If $X_{1},\dots,X_{n}$ are binary r.v.s with $\sum_{i}X_{i}\leq 1$ always,
then they are NA.

More elaborate NA distributions can be obtained via simple NA-preserving
operations [49].

######  Lemma 2.5.

NA is closed under products and under disjoint non-decreasing function
composition. That is, if $\vec{X}=(X_{1},\dots,X_{n})$ is NA, then:

  1. 1.

if $\vec{Y}=(Y_{1},\dots,Y_{m})$ is NA and $\vec{Y}$ is independent of
$\vec{X}$, then $(X_{1},\dots,X_{n},Y_{1},\dots,Y_{m})$ are NA;

  2. 2.

$(f_{1}(X_{i}:i\in I_{1}),\dots,f_{k}(X_{i}:i\in I_{k}))$ are NA, for any
concordant functions (i.e., all non-decreasing or all non-increasing)
$f_{1},\dots,f_{k}$ and disjoint sets $I_{1},\dots,I_{k}\subset[n]$,
$I_{j}\cap I_{k}=\emptyset\,\forall j\neq k$.

Negative association implies many more useful properties, most notably the
applicability of Chernoff-Hoeffding type tail bounds [32] and submodular
stochastic dominance (see Appendix A).

An even stronger negative correlation property than NA is the _strong Rayleigh
property (SRP)_ (see Appendix A for a precise definition). This property
implies NA (even under conditioning), as well as concentration of any
Lipschitz function [63], and numerous other useful properties.

##  3 Online Level-Set Rounding

In this section we introduce our online level-set rounding algorithm. As its
analysis will involve coupling with the _offline_ level-set rounding algorithm
of Srinivasan [66], we first start by revisiting this algorithm and its
properties.

###  3.1 Offline level-set rounding

Here we consider an _offline_ procedure due to [66]. This algorithm, on input
$\vec{x}\in[0,1]^{n}$ with integer sum $\sum_{i}x_{i}\in\mathbb{Z}$ (possibly
by adding a dummy value) and partial sums $s_{j}:=\sum_{i\leq j}x_{j}$,
outputs a set $\mathcal{S}\subseteq[n]$ with characteristic vector $\vec{X}$
given by $X_{i}:=\mathds{1}[i\in\mathcal{S}]$ with partial sums
$S_{j}:=\sum_{i\leq j}X_{i}=|\mathcal{S}\cap[j]|$ satisfying the following
properties for all $i$.

  1. (P1)

(Marginals) $\mathbb{E}[X_{i}]=x_{i}.$

  2. (P2)

(Rounding) $S_{i}\in\\{\lfloor s_{i}\rfloor,\lceil s_{i}\rceil\\}$.

Property (P1) and linearity of expectation imply that
$\mathbb{E}[S_{i}]=s_{i}$. Property (P2) requires that $S_{i}$ always equals
this expectation, “up to rounding”. In addition, we require the following
strong negative correlation property.

  1. (P3)

(Strongly Rayleigh) The joint distribution $\vec{X}$ is strongly Rayleigh (and
thus, also NA).

Our objective will be to design an _online_ algorithm satisfying the above,
but for now we revisit the offline algorithm of [66] and prove that when run
with a certain specific way of choosing the key indices $i_{1}$ and $i_{2}$
(see Algorithm 1), then it satisfies the above three properties.

As usual, “$\min(S)$" in Algorithm 1 refers to the minimum element of a
nonempty set $S$; the index $i_{2}$ in Algorithm 1 is always well-defined
since $\sum_{i}x_{i}\in\mathbb{Z}$ and, as we shall see,
$\sum_{i}y_{i}=\sum_{i}x_{i}$ always. We emphasize that the algorithm of [66]
allows much liberty in the choice of $i_{1}$ and $i_{2}$, and that our
specific choice of $i_{1}$ and $i_{2}$ is required to satisfy Property (P2).
Also, the random choice in each call to STEP is independent of the random
choices of the past.

Algorithm 1 Offline Level-Set Rounding

1:Initialize $\vec{y}\leftarrow\vec{x}$

2:while $frac(y):=\\{i\mid y_{i}\not\in\\{0,1\\}\\}\neq\emptyset$ do

3: Let $i_{1}\leftarrow\min(frac(y))$

4: Let $i_{2}\leftarrow\min(frac(y)\setminus\\{i_{1}\\})$

5: STEP$(y_{i_{1}},y_{i_{2}})$

6:Output $\mathcal{S}:=\\{i\mid y_{i}=1\\}$

Algorithm 2 STEP$(A,B)\quad\vartriangleright$ modifies inputs

1:if $A+B<1$ then

2: $(A,B)\leftarrow\begin{cases}(A+B,0)&\textrm{w.p. }\frac{A}{A+B}\\\
(0,A+B)&\textrm{w.p. }\frac{B}{A+B}\end{cases}$

3:else$\rhd$ $A+B\in[1,2)$

4: $(A,B)\leftarrow\begin{cases}(1,A+B-1)&\textrm{w.p. }\frac{1-B}{2-A-B}\\\
(A+B-1,1)&\textrm{w.p. }\frac{1-A}{2-A-B}\end{cases}$

That Algorithm 1 terminates and outputs a random set satisfying Property (P1)
is known [66]. Nonetheless, for completeness, we provide a proof of this fact
in Appendix B. In the same appendix we prove by induction on the number of
invocations of STEP() that every prefix sum is preserved with probability one,
up to rounding, and so Algorithm 1 satisfies Property (P2).

######  Lemma 3.1.

Let $s_{j}:=\sum_{i\leq j}x_{i}$ and $Y^{t}_{j}:=\sum_{i\leq j}y^{t}_{i}$,
where $y^{t}_{i}$ is the value $y_{i}$ after $t$ applications of STEP in
Algorithm 1. Then, $Y^{t}_{j}\in\left[\lfloor s_{j}\rfloor,\lceil
s_{j}\rceil\right]$ for all $j$ and $t$.

Strong negative correlation (Property (P3)) was proven in [15] as long as,
e.g., we use some fixed choice of $i_{1}$ and $i_{2}$ as in Algorithm 1:

######  Lemma 3.2.

Let $X_{i}:=\mathds{1}[i\in\mathcal{S}]$ be the indicators for $i$ being in
the output set of Algorithm 1. Then, $\vec{X}=(X_{1},X_{2},\dots,X_{n})$ is a
family of strongly Rayleigh random variables.

To conclude, we have the following.

######  Lemma 3.3.

Algorithm 1 satisfies properties (P1) (P2) and (P3).

###  3.2 The online level-set rounding algorithm

We now turn to providing an online counterpart to Algorithm 1. Here, the input
is a sequence of reals, $x_{1},x_{2},\dots\in[0,1]$, revealed in an online
fashion. Algorithm 3 maintains a set $\mathcal{S}\subseteq\mathbb{N}$
(initially empty), and decides at time $t$ (when $x_{t}$ is revealed) whether
to add $t$ to its output set $\mathcal{S}$, immediately and irrevocably. Let
$X_{t}:=\mathds{1}[t\in\mathcal{S}]$, and let $S_{t}:=\sum_{t^{\prime}\leq
t}X_{t^{\prime}}$ denote the cardinality of $\mathcal{S}$ right after time
$t$, i.e., $S_{t}=|\mathcal{S}\cap[t]|$. Finally, let
$s_{t}:=\sum_{t^{\prime}\leq t}x_{t^{\prime}}$. We will show that Algorithm 3
satisfies properties (P1), (P2) and (P3) given by its offline counterpart,
Algorithm 1.

Algorithm 3 Online Level-Set Rounding

1:Initialize $\mathcal{S}\leftarrow\emptyset$

2:for arrival $x_{t}$ (at time $t\geq 1$) do

3: add $t$ to $\mathcal{S}$ with probability
$p_{t}:=\begin{cases}0&|\mathcal{S}|=\lceil s_{t}\rceil\\\
1&|\mathcal{S}|<\lfloor s_{t}\rfloor\\\ \frac{x_{t}}{\lfloor
s_{t-1}\rfloor+1-s_{t-1}}&|\mathcal{S}|=\lfloor s_{t}\rfloor=\lfloor
s_{t-1}\rfloor\\\ \frac{s_{t}-\lfloor s_{t}\rfloor}{s_{t-1}-\lfloor
s_{t-1}\rfloor}&|\mathcal{S}|=\lfloor s_{t}\rfloor>\lfloor
s_{t-1}\rfloor\textrm{ and }s_{t-1}\neq\lfloor s_{t-1}\rfloor\\\
0&\textrm{else.}\end{cases}$

4:Output $\mathcal{S}$

The random bits used to make the random choice in each step of Algorithm 3 are
independent of the random bits used in the past: i.e., while $p_{t}$ depends
on $S_{t-1}$, the random bits used to generate the event of probability
$p_{t}$ in step $t$, are independent of the random bits of past steps.

###  3.3 Coupling the online and offline algorithms

Here we prove that Algorithm 3 satisfies properties (P1), (P2) and (P3).
Proving properties (P1), (P2) directly is not too hard (see B.2).444 In fact,
Algorithm 3 can be shown to be the _only_ online algorithm satisfying both
these simple properties if we further restrict it to only storing in memory
the partial sums $s_{t-1}$ and $S_{t-1}$ at the beginning of step $t$. Proving
Property (P3), on the other hand, is slightly more involved; we do so now,
using that the much-simpler properties (P1) and (P2) hold for both the offline
and online algorithms. To prove that the last property holds, we show that
both algorithms induce the _same distribution_ over outputs. We outline a
proof here, deferring a complete proof to Appendix B.

######  Theorem 3.4.

Fix a vector $\vec{x}\in[0,1]^{n}$. Let $\mathcal{D}$ and
$\mathcal{D}^{\prime}$ denote the probability distributions on $\\{0,1\\}^{n}$
induced by the online and offline algorithms run on $\vec{x}$, respectively.
Then, $\mathcal{D}=\mathcal{D}^{\prime}$.

###### Proof (Sketch).

We prove by induction on $t\in[n]$ that the following holds:

$\forall(b_{1},\ldots,b_{t-1})\in\\{0,1\\}^{t-1},~{}\Pr_{\mathcal{D}}[X_{t}=1\bigm{|}(\forall
i<t,~{}X_{i}=b_{i})]=\Pr_{\mathcal{D}^{\prime}}[X_{t}=1\bigm{|}(\forall
i<t,~{}X_{i}=b_{i})].$ (1)

The (strong) inductive hypothesis, whereby Equation 1 holds for all
$t^{\prime}<t$, clearly implies that for all
$(b_{1},\dots,b_{t})\in\\{0,1\\}^{t-1}$ we have that
$\Pr_{\mathcal{D}}[(\forall
i<t,~{}X_{i}=b_{i})]=\Pr_{\mathcal{D}^{\prime}}[(\forall
i<t,~{}X_{i}=b_{i})]$. Similarly, Equation 1 holds for all $t\leq n$ iff the
two distributions are equal. The proof then proceeds by considering the
different possibilities for the prefix sums $s_{t-1}$ and $s_{t}$, which for
the online algorithm directly determine the above conditional probability.
These conditions also determine the offline algorithm’s performance up to the
$(t-1)^{st}$ invocation of STEP(), from which a careful analysis implies that
the conditional probabilities of the offline and online algorithms are equal.
∎

3.4 combined with 3.3 immediately implies the desired properties of our
Algorithm 3, as these properties are determined by the distribution over
output sets.

######  Lemma 3.5.

Algorithm 3 is an online algorithm satisfying properties (P1), (P2) and (P3).

##  4 Rounding $b$-Matchings Online

In this section we address the ODRS problem in bipartite $b$-matching
instances more broadly.

We start with a simple algorithm, combining our ODRS for uniform matroids
(Algorithm 3) with repeated invocations of an _offline_ CRS (2.1).

##### Warm-up: $1-1/e$ rounding ratio.

We consider the following simple algorithm: Run, for each offline node $i$, an
instance of Algorithm 3, applied to $x_{i1},x_{i2},\dots$. When the $i$-th
copy of Algorithm 3 fixes $X_{it}=1$, we say that $i$ _bids_ for online node
$t$. Out of the set of bidders (potential buyers) $P_{t}$, we then pick at
most one $i\in P_{t}$ to match $t$ to, using the offline contention resolution
scheme of 2.1, guaranteeing each node $i$ a probability of
$x_{i,t}\cdot\min_{S\subseteq[n]}\frac{\Pr[S\cap
P_{t}\neq\emptyset]}{\sum_{i\in S}x_{i,t}}$ of being matched. This step runs
in polytime, by independence of the bids. Since Algorithm 3 is an online
algorithm, so is the resultant algorithm. Moreover, since the output of
Algorithm 3 satisfies the $b$-matching constraints, and $t$ is matched to at
most one neighbor by the CRS, this algorithm’s output satisfies the
$b$-matching constraints. Finally, for each offline node set $S\subseteq[n]$,
by independence of the bids, the Taylor expansion of $\exp(-x)$ and convexity
(see A.5), we have

$\displaystyle\Pr[S\cap P_{t}\neq\emptyset]$ $\displaystyle=1-\prod_{i\in
S}(1-x_{it})\geq 1-\prod_{i\in
S}\exp(-x_{it})\geq\left(1-\frac{1}{e}\right)\cdot\sum_{i\in S}x_{it}.$ (2)

Therefore, by 2.1, this ODRS matches each edge $(i,t)$ with probability at
least $(1-1/e)\cdot x_{i,t}$.

######  Lemma 4.1.

There exists a polytime ODRS for bipartite $b$-matching with rounding ratio
$1-1/e$.

One natural approach to improve the above algorithm’s rounding ratio would be
to attempt to negatively correlate the probability of different offline nodes
to have previously bid, thus increasing $\Pr[S\cap P_{t}\neq\emptyset]$ for
all offline sets $S\subseteq[n]$. Unfortunately, for a sufficiently large
number of offline nodes, (near-)positive correlation is, generally,
unavoidable: see 6.3 for a proof of such a Ramsey-theoretic statement.
Instead, to achieve a better rounding ratio, we explicitly negatively
correlate _the bids_ of previously-non-bidding offline nodes when they do bid.

###  4.1 The improved ODRS: Overview and intuition

In this section we outline our improved ODRS. We focus here and in most
subsequent sections on simple matchings, for clarity’s sake, deferring an
extension to $b$-matchings to Section 4.2.2.

##### A bad example, and a false start.

Consider a graph with a single online node $t$ with $x_{it}=\frac{1}{n}$ for
all $n$ offline nodes. In this case, under independent bids, $t$ gets no bids
with probability $(1-\frac{1}{n})^{n}\approx\frac{1}{e}$, and so one of the
$n$ offline nodes must get matched with probability no greater than
$(1-\frac{1}{e})\cdot\frac{1}{n}$. For this simple example a rounding ratio of
one is possible, by correlating bids for $t$: if we pick exactly one neighbor
$i$ to bid with probability $x_{it}$, then each offline node both bids and
buys (is matched to) $t$ with probability $x_{it}$. Unfortunately, this
approach is impossible to implement in general: if we let each offline node
$i$ bid for at most one time $t$ (recall that this is a simple matching
instance) with probability $x_{i,t}$, then, for
$s_{it}:=\sum_{t^{\prime}<t}x_{it^{\prime}}$ the fractional degree of $i$ at
time $t$, we must have $i$ bid for $t$ with probability
$p_{it}:=x_{it}/(1-s_{it})$, and yet $\sum_{i}p_{it}$ may exceed one.

##### Bin-packing low-degree nodes.

Our first step is to adopt a _partial_ implementation of the above approach,
by grouping offline nodes into groups $B$ for which $\sum_{i\in B}p_{it}\leq
1$, and using one $\textrm{Uni}(0,1)$ variable to offer at most one bid per
group. Specifically, if we denote the set of low-degree neighbors of $t$ by
$L_{t}:=\\{i\in N(t)\mid s_{it}\leq\theta\\}$ for some threshold
$\theta\in[0,1]$ that we will optimize later, we will pack low-degree
neighbors into bins using a greedy bin-packing heuristic such that each bin
$B$ has $\sum_{i\in B}p_{i,t}\leq 1$. Moreover, each such bin $B$ (but one)
has $\sum_{i\in B}p_{i,t}\geq 1/2$ and hence has high total $x$-value of
$\sum_{i\in B}x_{i,t}\geq\frac{1-\theta}{2}$. (Here we use that
$p_{i,t}=x_{i,t}/(1-s_{i,t})\leq x_{i,t}/(1-\theta)$.) Using negative
association arguments (see Section 2), we can show that this approach
essentially replaces multiple bids of small $x$-value with bids of $x$-value
equal to the small bids’ sum. In particular, if the total $x$-value of low-
degree neighbors $i\in L_{t}$ is high, this results in
$\min_{S\subseteq[n]}\frac{\Pr[S\cap P_{t}\neq\emptyset]}{\sum_{i\in
S}x_{i,t}}\geq 1-\frac{1}{e}+\Omega(1)$, and a rounding ratio greater than
$1-\frac{1}{e}$, by 2.1.

##### Group discounting and individual markup.

It remains to address the challenge of increasing $\Pr[S\cap
P_{t}\neq\emptyset]$ if the total $x$-value of low-degree nodes $L_{t}$ is
small, and so very little grouping occurs. For this, we note that from the
perspective of every offline node $i$, a time step $t$ has: (1) a value
(matching probability), and (2) a cost (bidding probability). The latter is
indeed a cost, since we do not allow offline nodes to bid more than once. The
value at each time is monotone increasing in offline nodes’ costs. Now, when
we use grouping we decrease the contention faced by the CRS, as it now faces
fewer bidding nodes, due to each bin only providing one bid (or none). We can
therefore safely decrease the bidding probability (cost) in the case that much
grouping occurs, giving the grouped nodes a _group discount_ , while still
obtaining a rounding ratio greater than $1-1/e$. The upshot of the group
discount is that offline nodes now have a higher chance of not having bid
before later time steps where they are not grouped, in which case such
individual bidders can pay an _individual markup_ , allowing us to guarantee
that in this case too $\min_{S\subseteq[n]}\frac{\Pr[S\cap
P_{t}\neq\emptyset]}{\sum_{i\in S}x_{i,t}}\geq 1-\frac{1}{e}+\Omega(1)$, with
the ensuing $1-\frac{1}{e}+\Omega(1)$ rounding ratio following from the
offline CRS of 2.1.

###  4.2 The core of the improved ODRS

In this section we introduce our improved ODRS’ core subroutine, Algorithm 4.
(The parameter $\theta\in[0,1]$ will be optimized later, and for now it is
safe to think of the input vectors $\mathbf{x},\mathbf{v}$ as both equaling
the input fractional matching.) At each time step $t$, the algorithm groups
low-fractional-degree offline nodes, and then all remaining nodes, into
buckets, using the classic first-fit bin-packing heuristic,555This algorithm
maintains a sorted list of bins with each bin $B$ containing items of overall
size at most one, $\sum_{i\in B}s_{i}\leq 1$, and for each item $i$ in order,
adds $i$ to the first (possibly newly-opened) bin that has enough room left.
with each offline node $i$ having a size of $\frac{x_{i,t}}{1-s_{i,t}}$. This
is the conditional probability with which $i$ should bid for $t$ if $i$ is
_free_ , i.e., has not bid before, to guarantee a marginal bidding probability
of $x_{i,t}$. (This follows from our online level-set rounding algorithm’s
probabilities.) Items are grouped into bins of size one, and then at most one
offline node bids per bin (lines 9-12), resulting in the set of _candidates_ ,
$C_{t}$. The free candidates $P_{t}=C_{t}\cap F$ then _bid_ for $t$, who is
then matched to (at most) one bidding neighbor $i\in P_{t}$, chosen by a CRS.

Algorithm 4 ODRS-core($\theta,\mathbf{x},\mathbf{v}$)

1:$\mathcal{M}\leftarrow\emptyset$

2:$F\leftarrow[n]$ $\rhd$ Free offline nodes

3:for each time $t$ do

4: for each $i\in[n]$ do

5: $s_{i,t}\leftarrow\sum_{t^{\prime}<t}x_{i,t^{\prime}}$

6:
$\mathcal{B}_{t}\leftarrow\textrm{FirstFit}\left(\left\\{\left(i,\frac{x_{i,t}}{1-s_{i,t}}\right)\,\middle|\,i\in[n],s_{i,t}\leq\theta\right\\}\right)$
$\rhd$ Bucketing low-degree nodes

7:
$\mathcal{B}_{t}\leftarrow\mathcal{B}_{t}\cup\textrm{FirstFit}\left(\left\\{\left(i,\frac{x_{i,t}}{1-s_{i,t}}\right)\,\middle|\,i\in[n],s_{i,t}>\theta\right\\}\right)$
$\rhd$ Bucketing high-degree nodes

8: $C_{t}\leftarrow\emptyset$ $\rhd$ Candidates

9: for each $B\in\mathcal{B}_{t}$ do

10: $U\sim\textrm{Uni}[0,1]$

11: if $U\leq\sum_{i\in B}\frac{x_{i,t}}{1-s_{i,t}}$ then

12: $C_{t}\leftarrow
C_{t}\cup\min_{i}\left\\{i\in[k]\,\middle|\,U\leq\sum_{\begin{subarray}{c}j\in
B\\\ j\leq i\end{subarray}}\frac{x_{j,t}}{1-s_{j,t}}\right\\}$

13: $P_{t}\leftarrow F\cap C_{t}$ $\rhd$ Bidders = free candidates

14: $F\leftarrow F\setminus P_{t}$ $\rhd$ Bidders cease being free

15: $O\leftarrow\textrm{CRS}(P_{t},\\{v_{i,t}\\}_{i})$ $\rhd$ Contention
Resolution

16: if $|O|=1$ then

17: $\mathcal{M}\leftarrow\mathcal{M}\cup\\{(i,t)\mid i\in O\\}$

18:Output $\mathcal{M}$

First, we note that Algorithm 4—including the bin-packing steps that require
$\frac{x_{i,t}}{1-s_{i,t}}\leq 1$—is well-defined provided
$\sum_{t}x_{i,t}\leq 1$ for all $i,t$, since this implies that $x_{i,t}\leq
1-\sum_{t^{\prime}\leq t}x_{i,t^{\prime}}=1-s_{i,t}$. Next, by construction,
each offline node bids (and is thus matched) at most once, while the CRS
guarantees that each online node is matched at most once. To summarize, we
have the following.

######  Observation 4.2.

Algorithm 4 is well-defined and outputs a matching if $\sum_{t}x_{i,t}\leq
1\,\,\,\forall i\in[n]$.

We turn to analyzing the algorithm’s rounding ratio, starting with the
following lemma asserting that if much grouping occurs, then most bins have
high $x$-value.

######  Fact 4.3.

For each time $t$, at most one bin $B\in\mathcal{B}_{t}$ at 6 has $\sum_{i\in
B}x_{i,t}<\frac{1-\theta}{2}.$

###### Proof.

A well-known property of the First-Fit bin packing heuristic is that at most
one bin in the output of this algorithm is less than $\frac{1}{2}$ full (see,
e.g., [74, 72]). Therefore, since $s_{i,t}\leq\theta$ for each offline node
$i$ in a bin $B\in\mathcal{B}_{t}$ computed in 6, each such bin $B$ (barring
perhaps one) has

$\displaystyle\frac{1}{2}$ $\displaystyle\leq\sum_{i\in
B}\frac{x_{i,t}}{1-s_{i,t}}\leq\sum_{i\in B}\frac{x_{i,t}}{1-\theta}.\qed$

The following lemma, combined with 4.3, provides a guarantee no worse than the
independent-proposals approach. Indeed, as we will show shortly, it implies a
better rounding ratio if much grouping of low-degree neighbors occurs.

######  Lemma 4.4.

For any time $t$ and set of offline nodes $S\subseteq[n]$, Algorithm 4
satisfies

$\Pr[S\cap P_{t}\neq\emptyset]\geq
1-\prod_{B\in\mathcal{B}_{t}}\left(1-\sum_{i\in B\cap S}x_{it}\right).$

###### Proof.

Let $F_{t}$ denote $F$ at time $t$, and let $C_{t}$ and $P_{t}=C_{t}\cap
F_{t}$ be as in Algorithm 4. Next, let $C_{i,t}=\mathds{1}[i\in C_{t}]$
indicate whether $i$ is a candidate at time $t$, and define $F_{i,t}$ and
$P_{i,t}$ similarly. By independence of $C_{i,t}$ and $F_{i,t}$ and since
$\Pr[C_{i,t}]=\frac{x_{i,t}}{1-s_{i,t}}$ and $\Pr[F_{i,t}]=1-s_{i,t}$
(provable by a simple induction on $t\geq 0$), we have that
$\Pr[P_{i,t}]=x_{i,t}$. Therefore, by linearity of expectation and $\sum_{i\in
B}C_{i,t}\leq 1$, we have that $\Pr[P_{t}\cap S\cap B=\emptyset]=1-\sum_{i\in
B\cap S}x_{i,t}$. It remains to show that the events $[P_{t}\cap S\cap
B=\emptyset]$ for different $B$ are negative cylinder dependent, giving the
desired inequality

$\displaystyle\Pr[P_{t}\cap
S=\emptyset]=\Pr\left[\bigwedge_{B\in\mathcal{B}_{t}}(P_{t}\cap S\cap
B=\emptyset)\right]\leq\prod_{B\in\mathcal{B}_{t}}\Pr[P_{t}\cap S\cap
B=\emptyset]=\prod_{B\in\mathcal{B}_{t}}\left(1-\sum_{i\in B\cap
S}x_{i,t}\right).$

To this end, we will show that the events $[P_{t}\cap S\cap B=\emptyset]$ are
negatively associated (NA), which by 2.3 yields the required above inequality,
and hence yields the lemma. First, by 2.4, for any bin $B^{\prime}$ at time
$t^{\prime}<t$, the binary variables $C_{i,t^{\prime}}$ for all nodes $i\in
B^{\prime}\cap S$, whose sum is at most one, are NA. Moreover, the
distributions over different bins and different time steps are independent,
and so by closure of NA under products (2.5), all $C_{i,t^{\prime}}$ are NA.
Therefore, the variables $F_{i,t}=1-\max_{t^{\prime}<t}C_{i,t^{\prime}}$ are
non-increasing functions of disjoint NA variables $C_{i,t^{\prime}}$, and so
by closure of NA under such functions (2.5), the variables $F_{i,t}$ are NA.
Moreover, the variables $C_{i,t}$ are independent from the variables $F_{i,t}$
(who are functions only of $C_{i,t^{\prime}}$ for all $t^{\prime}<t$), and
consequently, by another application of closure of NA under products (2.5),
all variables $\\{F_{i,t},C_{i,t}\mid i\in S\\}$ are NA. Finally, since
$\mathds{1}[P_{t}\cap S\cap B=\emptyset]=1-\sum_{i\in B\cap S}C_{i,t}\cdot
F_{i,t}$ are monotone decreasing functions of disjoint NA variables (different
bins $B$), then by closure of NA under such functions (2.5), the variables
$\mathds{1}[P_{t}\cap S\cap B=\emptyset]$ are NA, as desired. ∎

####  4.2.1 The improved ODRS

4.4 and 4.3 allow us to argue that if much of $t$’s fractional degree is
contributed by neighbors $i$ with low fractional degree, $s_{i,t}\leq\theta$,
then $\Pr[S\cap P_{t}\neq\emptyset]\geq 1-\frac{1}{e}+\Omega(1)$. By 2.1, this
allows to match edges of such nodes $t$ with probability greater than
$(1-\frac{1}{e})\cdot x_{i,t}$. Indeed, we can afford to decrease the
fractions $x_{i,t}$ of low-degree nodes (that may be grouped effectively) and
still retain a similar $1-\frac{1}{e}+\Omega(1)$ rounding ratio for such $t$.
In return, we can afford to increase the fractions $x_{i,t}$ of nodes of high
degree (who might not be grouped). More precisely, we consider the following
transformation to $\mathbf{x}$, capturing this aforementioned _group discount
and individual markup_. For $\theta=\frac{\delta}{\epsilon+\delta}$, with
$\epsilon,\delta\in[0,1]$ to be optimized shortly, we consider the following
assignment $\hat{\mathbf{x}}:E\to\mathbb{R}_{\geq 0}$.

$\displaystyle\hat{x}_{i,t}=x_{i,t}\cdot(1-\epsilon)+\int_{z=\max(\theta,s_{i,t})}^{\max(\theta,\,s_{i,t}+x_{i,t})}(\epsilon+\delta)\,dz.$
(3)

Intuitively, $\hat{\mathbf{x}}$ decreases/increases the $x$-value of (parts
of) edges of $i$ until/after $i$ has fractional degree $\theta$, by a
$(1-\epsilon)$ and $(1+\delta)$ factor, respectively. So, for example,
$\hat{x}_{i,t}\geq x_{i,t}\cdot(1-\epsilon)$ if $s_{i,t}\leq\theta$ and
$\hat{x}_{i,t}=x_{i,t}\cdot(1+\delta)$ if $s_{i,t}>\theta$. While
$\mathbf{\hat{x}}$ is not a fractional matching, since online nodes $t$ may
have $\sum_{i}\hat{x}_{i,t}>1$, this assignment does satisfy the fractional
degree constraints of _offline_ nodes.

######  Fact 4.5.

For every offline node $i\in[n]$ and time $t$, we have that
$\hat{s}_{i,t}:=\sum_{t^{\prime}<t}\hat{x}_{i,t^{\prime}}\leq s_{i,t}\leq 1$.

###### Proof.

If $s_{i,t}\leq\theta$, trivially $\hat{s}_{i,t}=s_{i,t}\cdot(1-\epsilon)\leq
s_{i,t}$. Otherwise, by our choice of $\theta=\frac{\delta}{\epsilon+\delta}$,
we have

$\displaystyle\hat{s}_{i,t}$
$\displaystyle=s_{i,t}\cdot(1-\epsilon)+(s_{i,t}-\theta)^{+}\cdot(\epsilon+\delta)=s_{i,t}\cdot(1+\delta)-\delta\leq
s_{i,t}.\qed$

Our ODRS, given in Algorithm 5, first scales the fractions as in Equation 3
(easily computable online, as these $\hat{x}_{i,t}$ only depend on information
known by time $t$) and feeds the resultant vectors
$\mathbf{\hat{x}},\mathbf{x}$ (playing the roles of $\mathbf{x}$ and
$\mathbf{v}$, respectively) into our core ODRS subroutine, Algorithm 4. By 4.5
and 4.2, we have that Algorithm 5 is a well-defined online algorithm,
outputting a valid matching. It remains to analyze this algorithm’s rounding
ratio, starting with the following lemma.

Algorithm 5 ODRS($\epsilon,\delta,\mathbf{x}$)

1:$\theta\leftarrow\frac{\delta}{\epsilon+\delta}$

2:Init ODRS-core($\theta\cdot(1-\epsilon),\mathbf{\hat{x}},\mathbf{x}$)

3:for each time $t$ do

4: for each $i\in[n]$ do

5: $s_{i,t}\leftarrow\sum_{t^{\prime}<t}x_{i,t^{\prime}}$

6: Compute $\hat{x}_{i,t}$ from $(x_{i,t},s_{i,t},\epsilon,\delta)$ as in
Equation 3

7: Run next step of ODRS-
core($\theta\cdot(1-\epsilon),\mathbf{\hat{x}},\mathbf{x}$)

8:Output $\mathcal{M}$ computed by ODRS-
core($\theta\cdot(1-\epsilon),\mathbf{\hat{x}},\mathbf{x}$)

######  Lemma 4.6.

If $\epsilon,\delta\in[0,1]$ guarantee that for all
$z\geq\frac{1-\theta}{2}=\frac{\epsilon}{2(\epsilon+\delta)}$,

$\displaystyle
f_{\epsilon,\delta}(z):=\exp(-z\cdot(1+\delta))-(1-z\cdot(1-\epsilon))\geq 0,$
(4)

then Algorithm 5 with parameters $\epsilon$ and $\delta$ has rounding ratio at
least

$1-\exp\left(-1-\delta+\frac{\epsilon+\delta}{1-\epsilon}\right)\cdot\frac{1-\epsilon}{1+\delta}.$

###### Proof.

By construction of $\hat{x}_{i,t}$, we have that
$\hat{s}_{i,t}\leq\theta\cdot(1-\epsilon)$ iff $s_{i,t}\leq\theta$. Define
$L_{t}:=\\{i\mid
s_{i,t}\leq\theta\\}=\\{i\mid\hat{s}_{i,t}\leq\theta\cdot(1-\epsilon)\\}$. By
4.4 and the Taylor expansion of $1-\exp(-z)$, for any offline node set
$S\subseteq[n]$ and time $t$, the set of bidders $P_{t}$ computed by ODRS-
core($\theta\cdot(1-\epsilon),\mathbf{\hat{x}},\mathbf{x}$) satisfies

$\displaystyle\Pr[S\cap P_{t}\neq\emptyset]$ $\displaystyle\geq
1-\prod_{B\not\subseteq L_{t}}\left(1-\sum_{i\in B\cap
S}\hat{x}_{it}\right)\cdot\prod_{B\subseteq L_{t}}\left(1-\sum_{i\in B\cap
S}\hat{x}_{it}\right)$ $\displaystyle\geq 1-\exp\left(-\sum_{i\in S\setminus
L_{t}}x_{it}\cdot(1+\delta)\right)\cdot\prod_{B\subseteq
L_{t}}\left(1-\sum_{i\in B\cap S}x_{it}\cdot(1-\epsilon)\right).$

We now lower bound the ratio $\frac{\Pr[S\cap P_{t}\neq\emptyset]}{\sum_{i\in
S}x_{it}}$. To do so, we note that our lower bound for $\Pr[S\cap
P_{t}\neq\emptyset]$ is a concave function in $\sum_{i\in S}x_{it}$ in the
range $[0,1]$, and so our lower bound for the above ratio is minimized by
virtually increasing $\sum_{i\in S}x_{it}$ until $\sum_{i\in S}x_{it}=1$, by
adding all $i\notin S$ to the set and possibly adding dummy nodes $J$ with
$s_{j,t}=\theta$ for all $j\in J$ and $\sum_{J}x_{jt}=1-\sum_{i}x_{it}\geq 0$
(see A.5).666Concretely: adding any value to $\sum_{i\in S}x_{i,t}$
corresponding to adding (part of) another (dummy) element to $S$ decreases the
value, so concavity of the resulting function together with A.5 completes the
proof of this claim. On the other hand, by 4.3, every bin $B\subseteq L_{t}$
but at most one bin $B^{*}$ has $\sum_{i\in
B}\hat{x}_{i,t}\geq\frac{1-\theta(1-\epsilon)}{2}\geq\frac{(1-\theta)(1-\epsilon)}{2}$,
and hence $\sum_{i\in B}{x}_{i,t}\geq\frac{1-\theta}{2}$. Combining the above,
we get

$\displaystyle\frac{\Pr[S\cap P_{t}\neq\emptyset]}{\sum_{i}x_{it}}$
$\displaystyle\geq 1-\exp\left(-\left(1-\sum_{i\not\in
L_{t}}x_{it}\right)\cdot(1+\delta)\right)\cdot\prod_{B\subseteq
L_{t}}\left(1-\sum_{i\in B}x_{it}\cdot(1-\epsilon)\right)$ $\displaystyle\geq
1-\exp\left(-\left(1-\sum_{i\in
B^{*}}x_{it}\right)\cdot(1+\delta)\right)\cdot\left(1-\sum_{i\in
B^{*}}x_{it}\cdot(1-\epsilon)\right)$ $\displaystyle\geq
1-\exp\left(-1-\delta+\frac{\epsilon+\delta}{1-\epsilon}\right)\cdot\frac{1-\epsilon}{1+\delta}.$
(5)

Above, the second inequality follows from the lemma’s hypothesis, in Equation
4, and the last inequality follows from the following claim, whose proof by
inspection of the function $g$ is deferred to Appendix C.

######  Claim 4.7.

If $\epsilon,\delta\in[0,1]$, the function
$g(y):=1-\exp\left(-\left(1-y\right)\cdot(1+\delta)\right)\cdot\left(1-y\cdot(1-\epsilon)\right)$
satisfies

$\forall y\in\mathbb{R}:\qquad g(y)\geq
g\left(\frac{\epsilon+\delta}{(1-\epsilon)(1+\delta)}\right)=1-\exp\left(-1-\delta+\frac{\epsilon+\delta}{1-\epsilon}\right)\cdot\frac{1-\epsilon}{1+\delta}.$

Finally, the rounding ratio of the ODRS then follows from 2.1 and Equation 5.
∎

4.6 provides a sufficient condition for $\epsilon,\delta$ to (possibly) allow
for greater-than-$(1-1/e)$ rounding ratios, though this condition requires
satisfying infinitely many non-linear constraints. The following lemma, which
follows from convexity of $f_{\epsilon,\delta}$ and is proven in Appendix C,
provides a simpler condition that is sufficient to guarantee all the above
infinitely-many constraints.

######  Lemma 4.8.

Let $f_{\epsilon,\delta}(z)$ be as in 4.6. If $f_{\epsilon,\delta}(a)\geq 0$
and $f^{\prime}_{\epsilon,\delta}(a)\geq 0$, then $f_{\epsilon,\delta}(b)\geq
0$ $\forall b\geq a$.

Combining the above, we are finally ready to optimize the rounding ratio of
Algorithm 5.

######  Theorem 4.9.

Algorithm 5 run with $(\epsilon,\delta)\approx(0.0480,0.0643)$ achieves a
rounding ratio of .

###### Proof.

By lemmas 4.6 and 4.8, the rounding ratio of Algorithm 4 with parameters
$(\epsilon,\delta)$ is at least as high as
$1-\exp\left(-1-\delta+\frac{\epsilon+\delta}{1-\epsilon}\right)\cdot\frac{1-\epsilon}{1+\delta}$,
provided that $f_{\epsilon,\delta}\left(\frac{1-\theta}{2}\right)\geq 0$ and
$f^{\prime}_{\epsilon,\delta}\left(\frac{1-\theta}{2}\right)\geq 0$, where
$\frac{1-\theta}{2}=\frac{\epsilon}{2(\epsilon+\delta)}$ and
$f_{\epsilon,\delta}$ is as in 4.6. Thus, the algorithm’s rounding ratio is at
least as high as the value of the following program, when run with parameters
given by its optimal solution $(\epsilon,\delta)$. Off-the-shelf numerical
solvers yield a maximum value of $\alpha=\ratio$ at
$(\epsilon,\delta)\approx(0.0480,0.0643)$.

$\displaystyle\max\quad$
$\displaystyle\alpha=1-\exp\left(-1-\delta+\frac{\epsilon+\delta}{1-\epsilon}\right)\cdot\frac{1-\epsilon}{1+\delta}$
s.t.
$\displaystyle\exp\left(-\frac{\epsilon}{2(\epsilon+\delta)}\cdot(1+\delta)\right)-1+\frac{\epsilon}{2(\epsilon+\delta)}\cdot(1-\epsilon)\geq
0$
$\displaystyle-(1+\delta)\cdot\exp\left(-\frac{\epsilon}{2(\epsilon+\delta)}\cdot(1+\delta)\right)+1-\epsilon\geq
0$ $\displaystyle\epsilon,\delta\in[0,1].\qed$

Computational considerations. The algorithm implied by 4.9, as stated, takes
exponential time, due to its reliance on the CRS of 2.1 for non-independent
bid distributions. As we show in Section C.1, a slight downscaling of the
$x$-values allows us to achieve essentially the same rounding ratio, while
also guaranteeing that the number of bidders at each time step is small. This
allows us to compute the support of the distribution of $P_{t}$ in polynomial
time, which by 2.1 then gives us the following polytime counterpart to 4.9.

######  Theorem 4.10.

For any $\gamma>0$, there exists an $n^{O(1/\gamma)}$-time bipartite matching
ODRS with rounding ratio of $\ratio-\gamma$.

####  4.2.2 The $b$-matching ODRS

In this section we extend our ODRS from matchings to $b$-matchings. To avoid
repetition, we only outline the changes needed in the algorithm and analysis,
and defer the proofs to Appendix C.

##### The change to the core algorithm.

As we did (implicitly) in Algorithm 4, we let the online level-set algorithm
dictate the marginal probabilities with which an offline node $i$ should bid
to $t$, based on the number of times $i$ has bid by time $t$, which we denote
by $S_{i,t}$. (This corresponds to $S_{t}$ in Algorithm 3 run from the
perspective of the offline node $i$.) We process offline nodes at different
times $t$ as follows, with the choice of probabilities guided by Algorithm 3
to guarantee that $\mathbb{E}[S_{i,t+1}-S_{i,t}]=x_{i,t}$, by Property (P1),
and $S_{i,t}\in[\lfloor s_{i,t}\rfloor,\lceil s_{i,t}\rceil]$, by Property
(P2).

For nodes with $\lceil s_{t+1}\rceil=\lceil s_{t}\rceil$ — whose fractional
degrees both before and after time $t$ lie in the range $[\lfloor
s_{i,t}\rfloor,\lceil s_{i,t}\rceil]$ — we group these offline nodes and have
them bid (at most one bid per bin) as in Algorithm 4, with the following
changes: $s_{i,t}$ is replaced by its fractional part, $s_{i,t}-\lfloor
s_{i,t}\rfloor$: this is done both in the bidding probability, so these items
have size $\frac{x_{i,t}}{1-(s_{i,t}-\lfloor s_{i,t}\rfloor)}$ when bin
packing, and in the condition $s_{i,t}\leq\theta$, which are now replaced by
the condition $s_{i,t}-\lfloor s_{i,t}\rfloor\leq\theta$ (and similarly for
the condition $s_{i,t}>\theta$), with $\theta$ to be chosen later. Moreover,
we add a candidate offline node $i\in C_{t}$ to the list of potential matches
$P_{t}$ (the bidders) if $S_{i,t}<\lfloor s_{i,t}\rfloor$ (corresponding to
$i\in F\cap C_{t}$ in Algorithm 4 for simple matchings).

For all offline nodes with $\lfloor s_{i,t+1}\rfloor=\lfloor
s_{i,t}\rfloor+1$, we place these nodes in singleton bins, and we have them
bid with probability if $S_{i,t}=\lfloor s_{i,t}\rfloor$, or with probability
$\frac{s_{i,t+1}-\lfloor s_{i,t+1}\rfloor}{s_{i,t}-\lfloor s_{i,t}\rfloor}$ if
$S_{i,t}=\lceil s_{i,t}\rceil=\lfloor s_{i,t+1}\rfloor$.

##### Change to core ODRS’ analysis:

4.3 and its proof hold unchanged for our extension of the core ODRS. 4.4, too,
holds unchanged, although the proof, deferred to Section C.2, is now slightly
more involved. Specifically, the key ingredient, proving that the events
$[P_{t}\cap S\cap B]$ over different bins $B$ are negatively associated (NA)
requires a proof that the variables $S_{i,t}$ are NA.

##### Change to the improved ODRS.

In our ODRS for $b$-matchings, since offline nodes $i$ for which $\lfloor
s_{i,t+1}\rfloor=\lfloor s_{i,t}\rfloor+1$ are grouped into singelton bins, we
wish to apply a markup to these nodes’ $x_{i,t}$-values, if $x_{i,t}$ is
small. We therefore consider the following assignment, with
$0\leq\theta_{1}\leq\theta_{2}\leq 1$ satisfying
$\theta_{2}-\theta_{1}=\frac{\delta}{\epsilon+\delta}$, to be chosen shortly.

$\displaystyle\hat{x}_{i,t}=\int_{z=s_{i,t}}^{s_{i,t+1}}(1-\epsilon)\cdot\mathds{1}\left[\lfloor
z\rfloor\in[\theta_{1},\theta_{2})\right]+(1+\delta)\cdot\mathds{1}\left[\lfloor
z\rfloor\not\in[\theta_{1},\theta_{2})\right]\,dz.$ (6)

In words: this assignment decreases the part of $x_{i,t}$ corresponding to the
parts of $i$’s fractional degree that are bounded away from $0$ and $1$
(specifically, those in the range $[\theta_{1},\theta_{2})$, and increases the
part of the fractional degree that is somewhat close to $0$ or $1$. Our new
ODRS then runs the modified core ODRS with inputs
$\theta:=\theta_{2}\cdot(1-\epsilon)+\theta_{1}\cdot(\delta+\epsilon)$ and
$\mathbf{\hat{x}},\mathbf{x}$. The choice of the parameter $\theta$ is taken
to have $\hat{s}_{i,t}-\lfloor\hat{s}_{i,t}\rfloor\leq\theta$ if and only if
${s}_{i,t}-\lfloor{s}_{i,t}\rfloor\leq\theta_{2}$.

##### Change to the improved ODRS’ analysis.

First, 4.5 generalizes as follows, arguing that modified fractional degrees
$\hat{s}_{i,t}=\sum_{t^{\prime}<t}\hat{x}_{i,t^{\prime}}$ fall within the same
integer range for all $(i,t)$.

######  Fact 4.11.

For every offline node $i\in[n]$ and time $t$, we have that
$\lfloor\hat{s}_{i,t}\rfloor=\lfloor s_{i,t}\rfloor$ and
$\lceil\hat{s}_{i,t}\rceil=\lceil s_{i,t}\rceil.$

4.11 and Property (P2) of Algorithm 3 imply that offline node $i$ makes some
$S_{i,t}\in[\lfloor s_{i,t}\rfloor,\lceil s_{i,t}\rceil]$ many bids by time
$t$. As $i$ is not matched more time than it bids, this implies that the
extended ODRS outputs a valid $b$-matching.

Next, the key lemma in the analysis of Algorithm 5, namely 4.6, needs to be
extended slightly, and in particular the condition of Equation 4 needs to hold
for all
$z\geq\max\left\\{\frac{1-\theta_{2}}{2(1+\delta)},\theta_{1}\right\\}$. To
make this constraint as less restrictive as possible, we take $\theta_{1}$ and
$\theta_{2}$ to guarantee the needed
$\theta_{2}-\theta_{1}=\frac{\delta}{\epsilon+\delta}$, and also satisfy
$\frac{1-\theta_{2}}{2(1+\delta)}=\theta_{1}$, resulting in
$\theta_{1}=\frac{\epsilon}{(3+2\delta)(\epsilon+\delta)}$ and
$\theta_{2}=\frac{\epsilon+3\delta+2\delta^{2}}{(3+2\delta)(\epsilon+\delta)}$.
This modification of the range for which we require Condition (4) to hold will
again allow us to argue that for all bins $B$ except for at most one bin
$B^{*}$ (to be characterized shortly), we have the following:

$\displaystyle 1-\sum_{i\in B}\hat{x}_{i,t}\leq\exp\left(-\sum_{i\in
B}x_{i,t}(1+\delta)\right)$ (7)

Specifically, for bins containing a single offline node $i$ with $\lfloor
s_{i,t+1}\rfloor=\lfloor s_{i,t}\rfloor+1$, we have the following: If
$s_{i,t+1}-\lfloor s_{i,t+1}\rfloor\geq\theta_{1}$, then

$x_{i,t}=s_{i,t+1}-s_{i,t}\geq s_{i,t+1}-\lfloor
s_{i,t+1}\rfloor\geq\theta_{1}.$

Similarly, if $s_{i,t}-\lfloor s_{i,t+1}\rfloor\leq\theta_{2}$, then

$x_{i,t}=s_{i,t+1}-s_{i,t}\geq\lfloor s_{i,t+1}\rfloor-s_{i,t}=1+\lfloor
s_{i,t}\rfloor-s_{i,t}\geq 1-\theta_{2}\geq\frac{1-\theta_{2}}{2(1+\delta)}.$

In both cases, Condition (4) holding for all
$z\geq\max\left\\{\frac{1-\theta_{2}}{2(1+\delta)},\theta_{1}\right\\}$
implies Equation 7. In the alternative scenario where $s_{i,t+1}-\lfloor
s_{i,t+1}\rfloor\leq\theta_{1}$ and $s_{i,t}-\lfloor
s_{i,t}\rfloor\leq\theta_{2}$, we have that $\hat{x}_{i,t}=(1+\delta)\cdot
x_{i,t}$, and Equation 7 follows from the basic inequality $1-z\leq\exp(-z)$.
Finally, by 4.3, for all bins $B$ containing offline nodes $i$ with $\lfloor
s_{i,t}\rfloor=\lfloor s_{i,t+1}\rfloor$ and $\hat{s}_{i,t}\leq\theta$ (i.e.,
$s_{i,t}\leq\theta_{2}$), except for at most one bin $B^{*}$, we have that

$\sum_{i\in B}{x}_{i,t}\cdot(1+\delta)\geq\sum_{i\in
B}\hat{x}_{i,t}\geq\frac{1-\theta}{2}\geq\frac{1-\theta_{2}}{2},$

where the last inequality, whereby $\theta\leq\theta_{2}$, is proven similarly
to 4.11. So, Condition (4) holding for all
$z\geq\frac{1-\theta_{2}}{2(1+\delta)}$ implies Equation 7 for all remaining
bins other than $B^{*}$. The analysis then proceeds as in 4.6, yielding the
following.

######  Lemma 4.12.

If $\epsilon,\delta\in[0,1]$ guarantee that for all
$z\geq\max\left\\{\frac{1-\theta_{2}}{2},\,\theta_{1}\right\\}=\frac{\epsilon}{\mathbf{(3+2\delta)}\cdot(\epsilon+\delta)}$,

$\displaystyle
f_{\epsilon,\delta}(z):=\exp(-z\cdot(1+\delta))-(1-z\cdot(1-\epsilon))\geq 0,$
(8)

then the extension of Algorithm 5 to $b$-matchings with parameters $\epsilon$
and $\delta$ has rounding ratio at least

$1-\exp\left(-1-\delta+\frac{\epsilon+\delta}{1-\epsilon}\right)\cdot\frac{1-\epsilon}{1+\delta}.$

Combined with 4.8, the above lemma then yields our $b$-matching ODRS’ rounding
ratio, after solving the appropriate modification of the mathematical program
used to prove 4.9.

######  Theorem 4.13.

The extension of Algorithm 5 to $b$-matchings, run with
$(\epsilon,\delta)\approx(0.0347,0.0425)$, achieves a rounding ratio of
$0.646$.

##  5 Applications

In this section we provide applications and extensions of our online rounding
algorithms. Mirroring the exposition in Section 1.1.1, we start with the
application of our online ($b$-)matching algorithms, omitting the edge-
weighted matching application with ML predictions, which follows directly from
our main result.

###  5.1 Applications and extensions of the matching ODRS

####  5.1.1 Online edge coloring (multigraphs)

We show here how to obtain the first online algorithm that achieves a better-
than-$2$ competitive factor for online edge-coloring in bipartite multigraphs
under adversarial arrivals, specifically under one-sided node arrivals, as
studied in [27]. We assume that upon arrival of each node, its neighboring
edges are revealed and must be colored. As already mentioned, for online edge
coloring, it is known that the greedy algorithm’s competitive ratio of $2$ is
tight for graphs of low maximum degree $\Delta=O(\log n)$ [8], while better
competitive ratios are known for high-degree graphs under various arrival
models, all for simple graphs [27, 65, 55, 10, 6], with the exception of the
random-order result of [3].

We obtain our improved bounds for multigraphs by extending a reduction from
online edge coloring to “fair” matching, suggested by [27] for simple graphs
(see also Saberi and Wajc [65, Appendix B]), given in 5.2.

######  Definition 5.1.

We say that a random matching $\mathcal{M}$ in a multigraph with maximum
degree $\Delta$ is _$\alpha$ -fair_ if for each (parallel) edge $e$ we have
that $\Pr[e\in\mathcal{M}]\geq\frac{1}{\alpha\Delta}$.

An $\alpha$-fair algorithm with $\alpha=1$ gives the highest uniform lower
bound on edges’ matching probability. An $\alpha$-fair algorithm with other
$\alpha$ ($\alpha>1$) therefore $\alpha$-approximates this maximally-fair
algorithm.

With the above terminology, we can now state the reduction.

######  Lemma 5.2.

An online $\alpha$-fair matching algorithm yields an online
$(\alpha+o(1))\Delta$-edge-coloring algorithm for $n$-node bipartite
multigraphs with maximum degree $\Delta=\omega(\log n)$.

We defer a brief proof sketch of the above to the end of the section, and turn
to discussing its consequences and converses.

######  Corollary 5.3.

An ODRS with rounding ratio $1/\alpha$ yields an online
$(\alpha+o(1))\Delta$-edge-coloring algorithm for $n$-node multigraphs with
maximum degree $\Delta=\omega(\log n)$.

###### Proof.

Consider the fractional matching $\mathbf{x}$ assigning value
$x_{e}=\frac{\kappa(e)}{\Delta}$ to the simple edge $e$ with $\kappa(e)$
parallel copies in the multigraph. (Note that $\sum_{e\ni
v}\kappa(e)\leq\Delta$ by definition, so this is indeed a fractional
matching.) Applying an ODRS with rounding ratio $1/\alpha$ to this fractional
matching $\mathbf{x}$ yields a randomized matching $\mathcal{M}$ that matches
every (parallel) edge in the graph with probability $\frac{1}{\alpha\Delta}$,
i.e., it yields an $\alpha$-fair matching. ∎

We note that there is in fact an equivalence between $\alpha$-fair matching
algorithms and $\alpha$-competitive edge-coloring algorithms, as “the
converse” also holds.

######  Observation 5.4.

An online $\alpha\Delta$-edge-coloring algorithm $\mathcal{A}$ for $n$-node
multigraphs with maximum degree $\Delta$ yields an ODRS with rounding ratio
$1/\alpha$ for fractional matchings $\mathbf{x}$ with $x_{e}\cdot\Delta$
integral for all $e$.

###### Proof.

Given a fractional matching $\mathbf{x}\in\mathbb{Q}^{E}$ in a simple graph
$G=(V,E)$, using that $x_{e}\cdot\Delta$ is integral for each edge $e$, we
provide to $\mathcal{A}$ a multigraph $\mathcal{H}=(V,F)$ with each edge $e$
having multiplicity $\kappa(e)=x_{e}\cdot\Delta$ in $\mathcal{H}$, and then
randomly sample one of the $\alpha\Delta$ edge colors (matchings)
$\mathcal{M}$ computed by $\mathcal{A}$. This yields an ODRS with rounding
ratio of $1/\alpha$, since for each edge $e\in E$ we have that

$\displaystyle\Pr[e\in\mathcal{M}]$
$\displaystyle=\kappa(e)\cdot\frac{1}{\alpha\Delta}=\frac{x_{e}}{\alpha}.\qed$

By the equivalence between edge coloring multigraphs and ODRSes for matchings,
together with our (upper and lower) bounds on the rounding ratio of such
ODRSes, we obtain the following bounds on the number of colors needed to edge-
color multigraphs online.

######  Theorem 5.5.

In $n$-node bipartite multigraphs with maximum degree $\Delta$ under
adversarial one-sided vertex arrivals, there exists an online
$1.533\Delta$-edge-coloring algorithm, assuming $\Delta=\omega(\log n)$. In
contrast, no
$(1/(2\sqrt{2}-2+\epsilon))\Delta\approx(1.207-O(\epsilon))\Delta$-edge-
coloring exists even for $\Delta=2$.

We note in passing that all known positive results for online edge coloring
under adversarial arrivals follow from 5.2, and indeed from 5.3 [27, 65, 55].
The reason most of these results do not extend to multigraphs is that their
ODRSes required their input fractional matchings $\mathbf{x}$ to be of the
form $x_{e}=\frac{1}{\Delta}$, or more generally for $x_{e}=o(1)$ for each
edge $e$ (including its multiplicities). The work of Saberi and Wajc [65] is a
lone exception to this rule, and combining its ODRS with 5.2 also yields an
algorithm for multigraphs, but using as many as $1.9\Delta$ colors.

We conclude the section with a brief proof sketch of 5.2.

###### Proof sketch of 5.2.

We describe the algorithm in an offline setting first. Let $C$ be such that
$C=\omega(\log n)$ and $C=o(\Delta)$. (Such $C$ exist, by our necessary
assumption that $\Delta=\omega(\log n)$.) Initially, the entire multigraph is
uncolored. For some $\Delta/C$ many rounds, compute $\alpha\cdot C$ colors as
follows: In the uncolored subgraph $U$, compute $\alpha\cdot C$ many
$\alpha$-fair matchings $\mathcal{M}_{1},\dots,\mathcal{M}_{\alpha C}$, and
let these occupy the next $\alpha C$ colors. Since every vertex has at most
$\alpha C=o(\Delta)$ many edges colored during a round, any vertex with degree
close to $\Delta$ at the beginning of the round has degree $\Delta-o(\Delta)$
by the end of the round. Therefore, since these $\mathcal{M}_{i}$ are
$\alpha$-fair matchings, and so match each (parallel) edge with probability at
least $\frac{1}{\alpha\cdot\Delta}$, by standard concentration bounds, all
vertices that have degree close to $\Delta$ have some $C\cdot(1-o(1))$ many
edges colored during a round (with high probability). This allows us to
compute a high-probability upper bound of on the resultant uncolored
multigraph at the end of the round (possibly useful to compute $\alpha$-fair
matchings), and moreover implies that after $\Delta/C$ many rounds (and so
with $(\Delta/C)\cdot\alpha\cdot C=\alpha\cdot\Delta$ colors used), the
uncolored multigraph has maximum degree $\Delta-(\Delta/C)\cdot
C\cdot(1-o(1))=o(\Delta)$, and can be colored greedily using a further $2\cdot
o(\Delta)=o(\Delta)$ many colors, for $(\alpha+o(1))\Delta$ colors overall.

While the above algorithm was described in an offline setting, if one can
compute an $\alpha$-fair algorithm online (possibly with information regarding
the high-probability upper bound on $\Delta$ in each round), then the entire
algorithm can be made to run online: for each (vertex/edge) arrival, perform
the next steps of the $\alpha\Delta$ many $\alpha$-fair matching algorithms
outputting color classes $\mathcal{M}_{1},\dots,\mathcal{M}_{\alpha\Delta}$,
where for the $i$-th such algorithm, we simulate only the arrival of the parts
of the subgraph that are not contained
$\mathcal{M}_{1},\dots,\mathcal{M}_{i-1}$. The same approach is used to
simulate the final greedy coloring steps, using the fact that the greedy
$(2\Delta-1)$-edge-coloring algorithm is an online algorithm. ∎

####  5.1.2 Stochastic extension

In this section, we generalize our matching ODRS and its analysis to the
following stochastic online bipartite matching problem. At each time $t$, an
online node arrives with weight vector $\vec{w}_{t}\sim\mathcal{D}_{t}$, where
$\mathcal{D}_{1},\mathcal{D}_{2},\dots$ are a priori known independent
distributions. A simple example which we focus on for notational simplicity
(though our approach generalizes to this problem in full generality) is as
follows: each online node $t$ arrives according to a Bernoulli event
$A_{t}\sim\mathrm{Ber}(p_{t})$, each edge $(i,t)$ having some intrinsic value
$w_{it}$, but realized weight $v_{it}=w_{it}\cdot A_{t}$. This problem (in its
full generality) is an online Bayesian selection problem, and a number of
algorithms with competitive ratio of $\frac{1}{2}$ are known for it [38, 35,
42]. By the classic lower bound of Krengel and Sucheston for the single-item
prophet inequality problem [54], the above ratio is best-possible when
comparing with the offline optimum algorithm.

In [62], Papadimitriou et al. initiate the study of this problem in terms of
the (polytime) approximability of the optimum _online_ algorithm. Perhaps
surprisingly, they show that while for simple cases of the problem (e.g., the
single-offline-node problem), the optimum online algorithm is computable using
a simple poly-sized dynamic program, in general it is pspace-hard to
approximate the optimum online algorithm within some absolute constant
$\alpha<1$ (say, $\alpha\approx 0.999999$), and showed that a better-
than-$0.5$ approximation of the optimum online algorithm can be obtained by
polytime online algorithms. This positive result was subsequently improved to
$0.526$ implicitly [65] and to $1-1/e\approx 0.632$ explicitly [16]. All these
results are achieved by rounding the following LP, which can be shown to upper
bound the optimum online algorithm’s value [62, 71].

$\displaystyle\max\quad$ $\displaystyle\sum_{i,t}w_{i,t}\cdot x_{i,t}$ (LP
$OPT_{on}$) s.t. $\displaystyle\sum_{t,r}x_{i,t}\leq 1$ $\displaystyle\forall
i\in[n]$ (9) $\displaystyle\sum_{i}x_{i,t}\leq p_{t}$ $\displaystyle\forall t$
(10) $\displaystyle x_{i,t}\leq
p_{t}\cdot\left(1-\sum_{t^{\prime}<t}x_{i,t^{\prime}}\right)$
$\displaystyle\forall i,t$ (11) $\displaystyle x_{i,t}\geq 0$
$\displaystyle\forall i,t.$ (12)

######  Lemma 5.6.

The optimum of the above LP upper bounds the expected gain of any online
algorithm.

Most of these constraints are evident, and follow from (expected) matching
constraints, which apply also to offline algorithms. The one constraint which
applies to online algorithms but not to offline ones is Constraint (11). This
constraint follows from the fact that if offline node $i$ is matched to $t$,
then $t$ has already arrived, and that $i$ is unmatched before time $t$ — two
events which are independent for online algorithms.

We note that in their paper’s full version, Papadimitriou et al. [62] (private
communication) show that the above LP has a “gap” of $1-\frac{1}{2e}$, in the
sense that no online algorithm (even computationally-unbounded ones) can get a
better-than-$(1-\frac{1}{2e})$ fraction of this LP’s value. So, an
approximation ratio greater than $1-\frac{1}{2e}$ is unachievable using this
LP, and a ratio of $1-\frac{1}{e}$ is achievable [16]. Is the latter bound
tight? In what follows, who show how the approach underlying our ODRSes,
combined with (and simplifying) the high-level analysis of [16], allows one to
break this bound.

##### ODRS for the stochastic setting.

As in the non-stochastic setting of Section 4, specifically Algorithm 4, we
group offline nodes and have them coordinate a single bid per group (bin).
Similarly, our stochastic counterpart to Algorithm 5 applies group discounting
and individual markup to the target marginal bidding probability, and then
calls the (soon-to-be) modified Algorithm 4 with parameter
$\theta\cdot(1-\epsilon)$ and vector $\hat{x}_{i,t}$ given by Equation 3,
restated below for ease of reference.

$\displaystyle\hat{x}_{i,t}=x_{i,t}\cdot(1-\epsilon)+\int_{z=\max(\theta,s_{i,t})}^{\max(\theta,\,s_{i,t}+x_{i,t})}(\epsilon+\delta)\,dz.$

The three main differences compared to Section 4 are as follows: First, to
account for the probability $p_{t}$ of $t$ to arrive, the conditional
probability for $i$ to bid if $i$ is free and $t$ arrives used in 6-12 is now
$\frac{\hat{x}_{i,t}}{p_{t}\cdot(1-\hat{s}_{i,t})}$, for
$\hat{s}_{i,t}:=\sum_{t^{\prime}<t}\hat{x}_{i,t}$. Second, we allow offline
nodes to bid more than once, and denote them as _free_ (i.e., belonging to
$F$) as long as they are not matched. This avoids offline nodes becoming
positively correlated due to an unlikely online node’s arrival. The offline
nodes’ matching constraints are trivially satisfied. Finally, satisfying the
online nodes’ matching constraints is even easier than in Algorithm 4 for the
non-stochastic setting. Rather than using a CRS, we have an arriving online
node $t$ that receives bids simply greedily match to the bidding node $i$
maximizing the value $w_{i,t}$. See the pseudocode in Algorithm 6.

Algorithm 6 Stochastic Matching Algorithm

1:$\mathcal{M}\leftarrow\emptyset$

2:$\mathbf{x}\leftarrow$ solution to (LP $OPT_{on}$)

3:for each time $t$ do

4: for each $i\in[n]$ do

5: compute $\hat{x}_{i,t}$ as in Equation 3, and
$\hat{s}_{i,t}=\sum_{t^{\prime}<t}\hat{x}_{i,t}$.

6:
$\mathcal{B}_{t}\leftarrow\textrm{FirstFit}\left(\left\\{\left(i,\frac{\hat{x}_{i,t}}{p_{t}\cdot(1-\hat{s}_{i,t})}\right)\,\middle|\,i\in[n],s_{i,t}\leq\theta\right\\}\right)$
$\rhd$ Bucketing high-degree nodes

7:
$\mathcal{B}_{t}\leftarrow\mathcal{B}_{t}\cup\left\\{\\{i\\}\,\middle|\,i\in[n],s_{i,t}>\theta\right\\}$
$\rhd$ Bucketing low-degree nodes

8: $C_{t}\leftarrow\emptyset$ $\rhd$ Candidates

9: for each $B\in\mathcal{B}_{t}$ do

10: $U\sim\textrm{Uni}[0,1]$

11: if $U\leq\sum_{i\in B}\frac{\hat{x}_{i,t}}{p_{t}\cdot(1-\hat{s}_{i,t})}$
then

12: $C_{t}\leftarrow
C_{t}\cup\min_{i}\left\\{i\in[k]\,\middle|\,U\leq\sum_{j\in B,\,j\leq
i}\frac{\hat{x}_{j,t}}{p_{t}\cdot(1-\hat{s}_{j,t})}\right\\}$

13: $P_{t}\leftarrow C_{t}\setminus V(\mathcal{M})$ $\rhd$ Bidders = free
candidates

14: if $P_{t}\neq\emptyset$ and  $t$ arrived then

15: pick some $i\in\arg\max\\{w_{i,t}\mid i\in P_{t}\\}$

16: $\mathcal{M}\leftarrow\mathcal{M}\cup\\{(i,t)\\}$

17:Output $\mathcal{M}$

######  Fact 5.7.

Algorithm 6 is well-defined. In particular,
$\frac{\hat{x}_{i,t}}{p_{t}\cdot(1-\hat{s}_{i,t})}\leq 1$ for every pair
$(i,t)$.

###### Proof.

By 4.5, we have that
$\hat{s}_{i,t}=s_{i,t}\cdot(1-\epsilon)+(s_{i,t}-\theta)^{+}\cdot(\epsilon+\delta)\leq
s_{i,t}$. Therefore, by our choice of $\theta=\frac{\delta}{\epsilon+\delta}$
and LP Constraint (11), we have that, indeed

$\displaystyle\frac{\hat{x}_{i,t}}{p_{t}\cdot(1-\hat{s}_{i,t})}$
$\displaystyle\leq\begin{cases}\frac{{x}_{i,t}\cdot(1-\epsilon)}{p_{t}\cdot(1-{s}_{i,t})}\leq\frac{{x}_{i,t}}{p_{t}\cdot(1-{s}_{i,t})}\leq
1&s_{i,t}\leq\theta\\\
\frac{{x}_{i,t}\cdot(1+\delta)}{p_{t}\cdot(1-{s}_{i,t}(1+\delta)+\delta)}=\frac{{x}_{i,t}}{p_{t}\cdot(1-{s}_{i,t}))}\leq
1&s_{i,t}>\theta.\end{cases}\qed$

Algorithm 6 is clearly a polytime algorithm. It remains to analyze its
approximation ratio.

The following lemma makes explicit a fact implicit in the proof of the main
theorem of [16]: specifically, that a per-online-node “approximation ratio”,
relating $w(\mathcal{M}(t),t)$—the weight obtained by matching $t$—to the LP
solution’s value from $t$, implies a global approximation ratio of the same
value. We provide a short self-contained proof of this fact for completeness.

######  Lemma 5.8.

If for each online node $t$ and $z\geq 0$ we have that
$\Pr[w(\mathcal{M}(t),t)\geq z]\geq\sum_{i:w_{i,t}\geq z}\alpha\cdot x_{i,t}$,
then the algorithm is an $\alpha$-approximation of the optimum online
algorithm.

###### Proof.

Denote by $w_{t}:=w(\mathcal{M}(t),t)$ the weight of the matched edge of $t$,
with $w_{t}=0$ if $t$ is not matched (possibly due to non-arrival). Then, the
weight of the output matching $\mathcal{M}$ satisfies

$\displaystyle\sum_{t}\mathbb{E}[w_{t}]$
$\displaystyle=\sum_{t}\int_{z=0}^{\infty}\Pr[w_{t}\geq
z]\,dz\geq\sum_{t}\int_{z=0}^{\infty}\alpha\cdot\sum_{i:w_{i,t}\geq
z}x_{i,t}\,dz=\alpha\cdot\sum_{i,t}w_{i,t}\cdot x_{i,t}.$

The proof is then completed by 5.6, implying that the RHS upper bounds
$\alpha$ times the value of the optimum online algorithm’s gain. ∎

The objective of our analysis will therefore be to lower bound
$\Pr[w(\mathcal{M}(t))\geq z]$ for all $z\geq 0$.

In our analysis, we let $F_{t}=[n]\setminus V(\mathcal{M})$ be the set of free
offline nodes at time $t$, and let $F_{i,t}=\mathds{1}[i\in
F_{t}]=1-\sum_{t^{\prime}<t}\mathds{1}[(i,t^{\prime})\in\mathcal{M}]$ indicate
whether $i$ is free by time $t$. Similarly, we let $E_{i,t}=1-F_{i,t}$
indicate whether $i$ was matched (“ _engaged_ ”) before time $t$.

Our first observation is that our modification to the notion of freedom
results in the following lower bound on the probability of a node being free
at time $t$.

######  Observation 5.9.

For each time $t$ and offline $i\in[n]$, we have that $\Pr[F_{i,t}]\geq
1-\hat{s}_{i,t}$.

###### Proof.

Let $B^{1}_{i,t}$ indicate that $i$ bid for the first before time $t$. We
prove that $\mathbb{E}[B^{1}_{i,t}]=\hat{s}_{i,t}$, by induction on $t\geq 1$.
The base case, is trivial, as $F_{i,1}\equiv 1$ and $\hat{s}_{i,1}\equiv 0$.
Now, by induction, we have

$\mathbb{E}[B^{1}_{i,t+1}-B^{1}_{i,t}]=p_{t}\cdot\frac{\hat{x}_{i,t}}{p_{t}\cdot(1-\hat{s}_{i,t})}\cdot(1-\mathbb{E}[B^{1}_{i,t}])=\hat{x}_{i,t},$

where the first equality relies on independence of $t$’s arrival, $i$ becoming
a candidate at time $t$, and $i$ not having yet bid, and the second equality
follows from the inductive hypothesis. By linearity, we then have that
$\mathbb{E}[B^{1}_{i,t+1}]=\hat{s}_{i,t+1}$. Since $1-F_{i,t}=E_{i,t}\leq
B^{1}_{i,t}$, the claim follows. ∎

Next, for any time $t$ and offline node set $S\subseteq[n]$, we let
$F_{S,t}=\bigwedge_{i\in S}F_{i,t}$ and $E_{S,t}=\bigwedge_{i\in S}E_{i,t}$
indicate whether all of $S$ is free (respectively, engaged) by time $t$. So
far, we have established that $\Pr[E_{i,t}]\leq\hat{s}_{i,t}$. The following
lemma, whose statement and proof mirror that of [16, Lemma 3.3] (who use
$x_{i,t}$ and $s_{i,t}$, as opposed to $\hat{x}_{i,t}$ and $\hat{s}_{i,t}$),
asserts that this upper bound is “sub-multiplicative”.

######  Lemma 5.10.

For each time $t$ and set of offline nodes $S\subseteq[n]$, we have that

$\Pr[E_{S,t}]\leq\prod_{i\in S}\hat{s}_{i,t}.$

To prove the above, we need the following claim from [16]. For completeness,
we provide a short probabilistic proof of this lemma (see [16, Lemma 3.2] for
a longer algebraic proof).

######  Lemma 5.11.

For all $i\in[n]$, let $q_{i}\in[0,1]$. Then,

$\sum_{A\subseteq S}\Pr[E_{A,t},F_{S\setminus A,t}]\cdot\prod_{i\in S\setminus
A}q_{i}=\sum_{A\subseteq S}\Pr[E_{A,t}]\cdot\prod_{i\in A}(1-q_{i})\prod_{i\in
S\setminus A}q_{i}.$

###### Proof.

Consider a probability space where at time $t$ all offline nodes toss a coin
with success probability $q_{i}$, independently. The LHS corresponds to all
free nodes having their coin come up heads. The RHS corresponds to the same
event, i.e., all nodes whose coin came up tails were engaged. ∎

###### Proof of 5.10.

The proof is by induction on $t\geq 1$ for all sets $S$. The base case $t=1$,
for which $s_{it}\equiv 0$ for all $i$, is trivial. For the inductive step,
denote the marginal probability of $i$ bidding at time $t$ (requiring $t$’s
arrival) by

$m_{i,t}:=\Pr[i\in P_{t}]=\frac{\hat{x}_{i,t}}{1-\hat{s}_{i,t}}.$

We note that with this terminology, we have that

$\displaystyle\hat{s}_{i,t+1}$
$\displaystyle=\hat{s}_{i,t}+\hat{x}_{i,t}=\hat{s}_{i,t}+m_{i,t}\cdot(1-\hat{s}_{i,t})=\hat{s}_{i,t}\cdot(1-m_{it})+m_{it}.$
(13)

The inductive step follows by noting that at most one of the nodes $i\in S$
may be matched at time $t$, and this requires that the single free node $i\in
S$ bid for $t$, which happens with probability $m_{i,t}$ (conditioned on any
event determined by randomness up to time $t$ that implies that the node is
free), as follows.

$\displaystyle\Pr[E_{S,t+1}]$
$\displaystyle\leq\sum_{\begin{subarray}{c}A\subseteq S\\\ |S\setminus A|\leq
1\end{subarray}}\Pr[E_{A,t},F_{S\setminus A,t}]\cdot\prod_{i\in S\setminus
A}m_{i,t}$ $\displaystyle=\sum_{\begin{subarray}{c}A\subseteq S\\\ |S\setminus
A|\leq 1\end{subarray}}\Pr[E_{A,t}]\cdot\prod_{i\in
A}\left(1-m_{i,t}\right)\prod_{i\in S\setminus A}m_{i,t}$ Lem 5.11
$\displaystyle\leq\sum_{A\subseteq S}\Pr[E_{A,t}]\cdot\prod_{i\in
A}\left(1-m_{i,t}\right)\prod_{i\in S\setminus A}m_{i,t}$
$\displaystyle\leq\sum_{A\subseteq S}\prod_{i\in A}U_{i,t}\cdot\prod_{i\in
A}\left(1-m_{i,t}\right)\prod_{i\in S\setminus A}m_{i,t}$ I.H.
$\displaystyle=\prod_{i\in S}\left(\hat{s}_{i,t}\cdot(1-m_{it})+m_{it}\right)$
binomial expansion $\displaystyle\leq\prod_{i\in S}\hat{s}_{i,t+1}$
$\displaystyle\textrm{Eqn. \eqref{U_it-recurrence}}.$

The preceding lemma allows us to prove the following counterpart to 4.4, key
to our improved approximation ratios.

######  Lemma 5.12.

For any time $t$ and set of offline nodes $S\subseteq[n]$, Algorithm 6
satisfies

$\Pr[S\cap P_{t}\neq\emptyset]\geq
1-\prod_{B\in\mathcal{B}_{t}}\left(1-\sum_{i\in B\cap
S}\hat{x}_{it}/p_{t}\right).$

###### Proof.

Let $C_{t}$ and $P_{t}$ be as in Algorithm 6. Since
$P_{t}=C_{t}\setminus\\{i\mid E_{i,t}=1\\}$, there are no bids from set $S$
($S\cap P_{t}=\emptyset$) iff all $i\in A=C_{t}\cap S$ are no longer free,
i.e., iff $E_{A,t}$ holds. So, by total probability over $C_{t}\cap S$, we
have that $(\star):=\Pr[t\textrm{ arrives and }S\cap P_{t}=\emptyset]$
satisfies

$\displaystyle(\star)$ $\displaystyle=\sum_{A\subseteq S}\Pr[C_{t}\cap
S=A]\cdot\Pr[E_{A,t}]$ $\displaystyle=\sum_{A\subseteq S}\prod_{B:|B\cap
A|=0}\Pr[C_{t}\cap B\cap A=\emptyset]\prod_{B:|B\cap A|=1}\sum_{i\in B\cap
A}\Pr[C_{t}\cap B\cap A=\\{i\\}]\cdot\Pr[E_{A,t}]$
$\displaystyle\leq\sum_{A\subseteq S}\prod_{B:|B\cap A|=0}\Pr[C_{t}\cap B\cap
A=\emptyset]\prod_{B:|B\cap A|=1}\sum_{i\in B\cap A}\Pr[C_{t}\cap B\cap
A=\\{i\\}]\cdot\Pr[E_{i,t}]$
$\displaystyle=\prod_{B\in\mathcal{B}_{t}}\left(\Pr[C_{t}\cap B\cap
S=\emptyset]+\sum_{i\in B\cap S}\Pr[C_{t}\cap
B=\\{i\\}]\cdot\Pr[E_{i,t}]\right)$
$\displaystyle=\prod_{B\in\mathcal{B}_{t}}\left(1-\sum_{i\in B\cap
S}\Pr[C_{t}\cap B=\\{i\\}]\cdot\Pr[F_{i,t}]\right)$
$\displaystyle\leq\prod_{B\in\mathcal{B}}\left(1-\sum_{i\in B\cap
S}\hat{x}_{i,t}/p_{t}\right).$

Above, the second and third equality follow from independence of the sets
$\\{C_{t}\cap B\mid B\in\mathcal{B}_{t}\\}$ and from $|C_{t}\cap B|\leq 1$
always. The first inequality follows from 5.10. The fourth equality follows
from $|C_{t}\cap B|\leq 1$, and $F_{i,t}=1-E_{i,t}$. Finally, the last
inequality follows from $\Pr[C_{t}\cap
B=\\{i\\}]=\frac{\hat{x}_{i,t}}{p_{t}\cdot(1-\hat{s}_{i,t})}$ and 5.9,
implying that $\Pr[C_{t}\cap
B=\\{i\\}]\cdot\Pr[F_{i,t}]\geq\frac{\hat{x}_{i,t}}{p_{t}\cdot(1-\hat{s}_{i,t})}\cdot(1-\hat{s}_{i,t})\geq\hat{x}_{i,t}/p_{t}$.
∎

The following lemma, which is a counterpart to 4.6 for the non-stochastic
setting, allows us to obtain a concrete lower bound from 5.12.

######  Lemma 5.13.

If $\epsilon,\delta\in[0,1]$ guarantee that for all
$z\geq\frac{1-\theta}{2}=\frac{\epsilon}{2(\epsilon+\delta)}$,

$\displaystyle
f_{\epsilon,\delta}(z):=\exp(-z\cdot(1+\delta))-(1-z\cdot(1-\epsilon))\geq 0,$
(14)

then Algorithm 6 with parameters $\epsilon$ and $\delta$ satisfies for each
time $t$ and set $S\subseteq[n]$

$\Pr[S\cap
P_{t}\neq\emptyset]\geq\left(1-\exp\left(-1-\delta+\frac{\epsilon+\delta}{1-\epsilon}\right)\cdot\frac{1-\epsilon}{1+\delta}\right)\cdot\sum_{i\in
S}x_{i,t}/p_{t}.$

The proof is near identical to that of 4.6, and is therefore omitted.777The
only changes to the proof are (1) the syntactic generalization of 4.3 implies
that all but one bin $B\in\mathcal{B}_{t}$ computed in 6 has
$\sum_{i}\hat{x}_{i,t}/\mathbf{p_{t}}\geq\frac{1-\theta}{2}$, and (2) the
convexity argument requires that we add dummy nodes $J$ with $s_{j,t}=\theta$
for all $j\in J$ and $\sum_{j\in J}x_{j,t}=p_{t}-\sum_{i}x_{i,t}$, where this
sum is non-negative, by LP Constraint 10.

Finally, the same optimization over $\epsilon,\delta$ as in Section 4 yields
our main result of this section.

######  Theorem 5.14.

Algorithm 6 with parameters $(\epsilon,\delta)\approx(0.0480,0.0643)$ is a
polytime online stochastic weighted bipartite matching algorithm that
-approximates the optimum online algorithm.

###### Proof.

Let
$\alpha=1-\exp\left(-1-\delta+\frac{\epsilon+\delta}{1-\epsilon}\right)\cdot\frac{1-\epsilon}{1+\delta}\geq\ratio$.
By our algorithm’s greedy matching choice, $t$ gets matched to a node $i$ with
$w_{i,t}\geq w$ iff $t$ arrives and gets a bid from the set $S_{t,w}:=\\{i\mid
w_{i,t}\geq w\\}$. So, by 5.13, as $(\epsilon,\delta)$ above satisfy Equation
14 for all $z\geq 0$ (see the proof of 4.9),

$\Pr[w(\mathcal{M}(t),t)\geq w]=\Pr[t\textrm{ arrives}\wedge P_{t}\cap
S_{t,w}\neq\emptyset]\geq p_{t}\cdot\alpha\cdot\sum_{i\mid w_{i,t}\geq
w}x_{i,t}/p_{t}=\alpha\cdot\sum_{i\mid w_{i,t}\geq w}x_{i,t}.$

The approximation ratio of Algorithm 6 then follows from 5.8, while the
algorithm’s polynomial running time is immediate. ∎

###  5.2 Application of the level-set ODRS

We now turn to discussing applications of our level-set algorithm, and its
strong negative correlation properties.

####  5.2.1 Multi-stage stochastic optimization

We consider an application to multi-stage stochastic optimization, building on
the framework of [67]. We recall briefly that in such multi-stage problems,
various parameters of an optimization problem materialize stochastically over
some number $k$ of stages, where each stage contains stochastic information
about the following stage(s) and wherein we can take actions—with actions
cheaper in earlier stages, but possibly inaccurate since we only know the
future stochastically.

Motivated by the results of [69], a broad class of multi-stage stochastic
covering problems can be cast as the following family of _online_ problems:
see Section 2 of [67], from which we quote the framework almost verbatim next.
There is a hidden covering problem “minimize $c^{T}\cdot x$ subject to $Ax\geq
b$ and with all variables in $x$ being non-negative integers” that is revealed
online as follows.We let $m$ denote the number of rows of $A$; also, the
variables in $x$ are indexed as $x_{j,\ell}$, where $1\leq j\leq n$ and
$1\leq\ell\leq k$. (We interchange $m$ and $n$ from [67].) Such a covering
problem, as well as a feasible fractional solution $x^{*}$ for it (where each
$x^{*}_{j,\ell}$ is allowed to be a non-negative _real_), are revealed to us
in $k$ stages as follows. In each stage $\ell$ where $1\leq\ell\leq k$, we are
given the $\ell^{th}$-stage fractional values $(x^{*}_{j,\ell}:~{}1\leq j\leq
n)$ of the variables along with their respective columns in the coefficient
matrix $A$, and their respective coefficients in the objective-function vector
$c$. Given this setup, we need to round the variables
$(x^{*}_{j,\ell}:~{}1\leq j\leq n)$ immediately and irrevocably at stage
$\ell$, using randomization if necessary. (Note the direct connection to
online computation.) The goal is to develop such a rounded vector
$(s_{j,\ell}:~{}1\leq j\leq n,1\leq\ell\leq k)$ that satisfies the constraints
$Ay\geq b$, and whose (expected) approximation ratio $\mathbb{E}[c^{T}\cdot
y]/c^{T}\cdot x^{*}$ is small, where the expectation is only over any random
choices made by our online algorithm in this arrival model. This completes the
description of the framework from [67].

We make two contributions in this framework. A motivating family of problems
to consider is vertex-(multi-)cover on graphs and hypergraphs. The multi-stage
stochastic version of the classical vertex-cover problem on a given graph
$G=(V,E)$ is basically as follows: the coverage constraint corresponding to an
edge $e=(u,v)\in E$ is now

$\left(\sum_{\ell=1}^{k}x_{u,\ell}\right)+\left(\sum_{\ell=1}^{k}x_{v,\ell}\right)\geq
1.$ (15)

Improving on the $2k$-approximation of Swamy and Shmoys [69] for this
problem—in the “online rounding” model mentioned in the previous paragraph—a
$2$-approximation is developed in [67].

Our _first contribution_ is the following generalization of the
$2$-approximation for multi-stage stochastic vertex cover from [67]. Consider
the following more-general problem in $d$-regular hypergraphs $H=(V,E)$ (or
hypergraphs with all edge-sizes lower bounded by $d$): for some integer
parameter $t$, we want the vertices in each edge $e\in E$ to be covered in
total to an extent of at least $t$, where vertices can be multi-covered. That
is, generalizing (15), the coverage constraint corresponding to an edge
$e=\\{v_{1},v_{2},\ldots,v_{d}\\}\in E$ is

$\sum_{i=1}^{d}\sum_{\ell=1}^{k}x_{v_{i},\ell}\geq t,$ (16)

where each $x_{v_{i},\ell}$ is allowed to be any non-negative integer; note
that the above-seen stochastic vertex cover is the special case where $d=2$
and $t=1$. Recalling our online arrival model, we need to round the LP
solution $(x^{*}_{v,\ell}:~{}v\in V)$ right away at stage $\ell$, for each
$\ell\in[k]$. We proceed as follows to obtain an
$\alpha:=(d+t-1)/t$–approximation in this model, generalizing the
$2$-approximation for $d=2$ and $t=1$. In particular, if $t$ is large, this is
essentially a $1$-approximation.

Our algorithm works as follows. For each vertex $v\in V$, consider the scaled
vector $z(v):=(\alpha\cdot x^{*}_{v,\ell}:~{}\ell\in[k])$ and independently
for all $v$, run Algorithm 3 on $z(v)$ to obtain the final rounded values
$X_{v,\ell}:~{}\ell\in[k])$. (As usual, we imagine padding this vector with a
dummy final element so that the sum of the entries is an integer.) We first
verify that (16) is satisfied with probability one for each
$e=\\{v_{1},v_{2},\ldots,v_{d}\\}\in E$:

$\displaystyle\sum_{i=1}^{d}\sum_{\ell=1}^{k}X_{v_{i},\ell}$
$\displaystyle\geq\sum_{i=1}^{d}\left\lfloor\sum_{\ell=1}^{k}\alpha\cdot
x^{*}_{v_{i},\ell}\right\rfloor$ (by Property (P2)) (17)
$\displaystyle>\sum_{i=1}^{d}\left(\left(\sum_{\ell=1}^{k}\alpha\cdot
x^{*}_{v_{i},\ell}\right)-1\right)$ ($\lfloor\beta\rfloor>\beta-1$ for all
$\beta$) (18) $\displaystyle\geq\alpha\cdot t-d$ (since $x^{*}$ satisfies
(16)) $\displaystyle=t-1,$

which implies that $\sum_{i=1}^{d}\sum_{\ell=1}^{k}X_{v_{i},\ell}\geq t$, as
required, since the LHS here is an integer and because of the strict
inequality connecting (17) and (18). We thus obtain an online solution to the
rounding problem which satisfies all constraints with probability one, and
whose expected objective function value is at most $\alpha(c^{T}\cdot x^{*})$.
We observe that the work of [67] also runs an online rounding algorithm, but
that the problem considered there is much simpler since all we require there
(in place of Property (P2)) is that if the entries of the given input vector
sum to at least one, then at least one entry is rounded to one with
probability one. In particular, this does not address the multi-coverage
constraint we satisfy here.

Our _second contribution_ is that because of Property (P3), the objective
function is strongly concentrated around its mean (given by the Chernoff
bound). This is an especially useful property in areas like stochastic
optimization, where _the algorithm can be run only once_. This is in
comparison to _offline_ minimization problems with a non-negative objective
where we can repeat the algorithm $O(1/\epsilon)$ times and choose the best
solution obtained, and apply Markov’s inequality to each iteration to show
that the best solution is at most $(1+\epsilon)$ times the expected value with
high probability. Thus, the fact that Algorithm 3 yields sharp concentration
as implied by Property (P3)—and does not just guarantee Properties (P1) and
(P2)—is very useful in the stochastic-optimization context.

Summarizing the preceding discussion (and formalizing the preceding
paragraph), we obtain the following result.

######  Theorem 5.15.

For any $k\geq 1$, there exists a $k$-stage stochastic hypergraph vertex cover
algorithm for $d$-regular hypergraphs where each hyper-edge must be covered
$t$ times, with approximation ratio that is $\alpha=\frac{d+t-1}{t}$ in
expectation and is $\alpha(1+o(1))$ w.h.p. if costs are polynomially bounded
and $OPT=\omega(\log n)$.

###### Proof.

Our algorithm satisfies the (multi-)coverage constraint, by the above, and has
expected approximation ratio $\alpha$ by construction. The high-probability
bound follows from standard Chernoff bounds for negatively-associated
variables, relying on Property (P3) and closure of NA under products (2.5),
relevant since we run independent copies of Algorithm 3 for each vertex. ∎

####  5.2.2 Negative association, fairness, diversity, and streaming

While Section 5.2.1 only required the fact that Property (P3) yields sharp
tail bounds for sums of the $X_{i}$ with non-negative weights, we go further
now and use the negative association guaranteed by Property (P3), which helps
us correlate multiple such sums as well as handle submodular objectives well.
The submodular-objective application further benefits from the fact that
Algorithm 3 can also be viewed as a _data-stream_ algorithm: note that at when
$x_{t}$ arrives, the algorithm need only remember $s_{t-1}$ and $S_{t}$, and
hence can be implemented with $O(\log n)$ space.

_Intersectionality_ is a key notion in the study of fairness, where the
intersection of multiple attributes (e.g., race, gender, age) can impact the
outcomes of a person in a more fine-grained manner than does standard group-
fairness (where we typically take a single attribute). Its study has naturally
impacted AI/ML fairness as well—see, e.g., [18] and its followups—and is a
topic of much debate in terms of precise definitions (see, e.g., [53]). We
make a contribution to this nascent area, while being aware that many such
formulations/contributions in the still-early stages of research in AI/ML
fairness are speculative.

Consider people arriving online and requesting a resource whose availability
expands over time: e.g., vaccines for a new pathogen or a popular new model of
car. It is anticipated that by time $t$, at most $a_{t}$ units of this
resource will be available. An ML system that adapts to the changing realities
on the ground (e.g., how the pathogen is spreading and which communities seem
to be impacted the most) decides online, the probability $x_{t}$ with which to
allocate the resource to the request arriving at time $t$; we naturally
require $\sum_{i=1}^{t}x_{i}\leq a_{t}$ for all $t$. We respond to this in
real time by constructing $X_{t}\in\\{0,1\\}$ using Algorithm 3; Property (P2)
ensures that we never exceed the supply-limits $a_{t}$. (In reality, a _batch_
of requests will arrive at time $t$, which of course Algorithm 3 naturally
extends to.) The ML system outputting the vector $x$ may be (required to be)
unware of protected attributes that characterize our underlying demographic
groups and their intersections: given $x$, can we show that while
intersectional unfairness may be present in $x$ (in which case the ML system
needs to be refined), our rounding algorithm tries to at least _limit the
scope_ of such intersectional unfairness in some way?

We formulate this problem as follows. Suppose each person requesting the
resource has three attributes $A_{1},A_{2}$, and $A_{3}$: the “three" here is
just for simplicity, and it is easy to see that the framework below
generalizes to any number of attributes. Suppose
$U_{1},U_{2},\ldots,U_{\alpha}$ is some given partition of the population
according to their values for $A_{1}$ (e.g., if $A_{1}$ is age, the $U_{i}$’s
may be disjoint age-intervals). Similarly, suppose we have a partition of the
population according to $A_{2}$ as $V_{1},V_{2},\ldots,V_{\beta}$ and
according to $A_{3}$ as $W_{1},W_{2},\ldots,W_{\gamma}$. In order to model
intersectionality, let us define the subgroup $G_{i,j,k}:=U_{i}\cap V_{j}\cap
W_{k}$. Let $s_{i,j,k}=\sum_{r\in G_{i,j,k}}X_{r}$ be the random variable
denoting the amount of resource received in total by members of $G_{i,j,k}$.
We ask: “While intersectional unfairness may be present, say inherently in the
vector $x$, does our rounding at least limit the extent of it?" That this is
indeed true follows from Property (P3) which guarantees negative association,
as follows. For any sequence of thresholds $(t_{i,j,k})$, the probabilities of
different subgroups $G_{i,j,k}$ receiving intersectional unfairness in the
sense of $s_{i,j,k}\leq t_{i,j,k}$, can be bounded as well as if the $X_{r}$’s
had been independent:

  * •

$\forall
S\subseteq\left([\alpha]\times[\beta]\times[\gamma]\right),~{}\Pr[\bigwedge_{(i,j,k)\in
S}(s_{i,j,k}\leq t_{i,j,k})]\leq\prod_{(i,j,k)\in S}\Pr[s_{i,j,k}\leq
t_{i,j,k}]$; and, more generally,

  * •

in disease-spread and meme-spread-like contexts, we are often interested in
monotone non-linear functions that model phase transitions: e.g., if a
heavily-interacting subgroup receives fewer than a threshold of vaccines, an
explosive epidemic could happen within that subgroup—with monotone behavior
away from this threshold. Given any sequence of monotone functions (all
increasing or all decreasing) $(f_{i,j,k})$, we have

$\forall
S\subseteq\left([\alpha]\times[\beta]\times[\gamma]\right),~{}\mathbb{E}\left[\prod_{(i,j,k)\in
S}f_{i,j,k}(s_{i,j,k})\right]\leq\prod_{(i,j,k)\in
S}\mathbb{E}\left[f_{i,j,k}(s_{i,j,k})\right].$

As is well-known, letting $\chi(\cdot)$ be the indicator function, this
implies that $\sum_{(i,j,k)\in S}\chi(s_{i,j,k}\leq t_{i,j,k})$ has Chernoff-
like concentration around its mean; in particular, while some subgroups in $S$
may face intersectional unfairness (that needs to be separately analyzed by
inspecting $x$), it is unlikely that many do.

We next present an application to diversity in search results. In addition to
the classical interest in this problem in information retrieval [14], there
has been much recent work in search-result diversification, motivated, e.g.,
by the fact that the document-set retrieved should account for the interests
of the user population [20, 26]. By developing a model of knowledge about the
topics the query or the documents may refer to, the work of [4] presents an
$(1-1/e)$–approximation for their objective of maximizing average-user
satisfaction with the search results. Given a search query $q$, a corpus of
$N$ documents $\mathcal{D}$, and a bound $k$ on the number of documents to
retrieve from $\mathcal{D}$ for $q$, a monotone submodular function
$f:2^{\mathcal{D}}\rightarrow[0,1]$ is developed in [4], where $f(T)$ is the
(approximate) mix of relevance and diversity if the set $T$ with $|T|\leq k$
is then returned to the user. The problem is thus to approximately maximize
$f(T)$ subject to $|T|\leq k$. Consider the setting where $\mathcal{D}$ is
very large, we only get streaming access to it, and where, after encountering
document $d\in\mathcal{D}$, we get ML advice on the probability $x_{d}$ with
which to choose $d$. Algorithm 3 is tailor-made for this, as it needs only
$O(\log N)$ space. Furthermore, by the already-known A.4, we obtain that our
final expected value $F(X_{1},X_{2},\ldots,X_{N})$ is at least as large as if
we had instead chosen the $X_{i}$’s independently with marginals $x_{i}$.
(Also see [5, 30] for applications of submodular functions toward diversity in
bipartite matching.)

##  6 Lower Bounds

In this section we present some impossibility results for ODRSes.

A simple example in [29] rules out a rounding ratio of one, or even just
greater than $\frac{7}{8}=0.875$. In this section we improve this bound to
$(2\sqrt{2}-2)\approx 0.828$ with a similarly simple example.

Before providing our lower bound, we provide an even simpler example ruling
out a rounding ratio of one. This example highlights the need of ODRSes with
high rounding ratio to create some form of negative correlation between all
subsets of offline nodes, motivating our lower bound example. (We are also
hopeful that this insight may inform future ODRSes.)

##### Example.

Suppose an ODRS $\mathcal{A}$ with rounding ratio of one exists, and apply it
to the following input on $n=3$ offline nodes and 4 online nodes: For
$k=1,2,3$, online node $k$ only neighbors offline node $k$, and $x_{kk}=1/2$.
So, each offline node’s matched status so far is a $\mathrm{Ber}(1/2)$ random
variable. Finally, online node $t=4$ arrives, neighboring some two offline
nodes, $i,j$, and $x_{it}=x_{jt}=1/2$. The above is clearly a feasible
fractional matching, but since we assumed that $\mathcal{A}$ has a rounding
ratio of one, it must match $t$ with probability one. Since $t$ cannot be
matched if both $i$ are $j$ previously matched, and both are matched with
probability $1/2$ before time $t$, this requires $i$’s and $j$’s matched
status before time $t$ to be perfectly negatively correlated. That is, $i$ is
unmatched iff $j$ is matched, and vice versa. Since $i,j$ could be any two
offline nodes, this requires perfect negative correlation between any two of
these three variables, which is impossible.888Perfect negative pairwise
correlation between three binary variables $X_{1},X_{2},X_{3}\in\\{0,1\\}$ can
be stated succinctly as $X_{1}+X_{2}=X_{1}+X_{3}=X_{2}+X_{3}=1$, but this
linear system only has a _fractional_ solution $X_{1}=X_{2}=X_{3}=1/2$. Thus,
we reach a contradiction, and an ODRS with rounding ratio of one is
impossible.

To generalize the above and obtain a concrete numeric bound, we need the
following fact, whereby (near-)positive pairwise correlation is unavoidable in
a large set of Bernoulli random variables. (See 6.3 for a potentially useful
generalization to $k$-wise correlations.)

######  Fact 6.1.

Let $Y_{i}\sim Ber(p)$ for $i=1,\dots,n$ be (possibly dependent) Bernoulli
variables. Then,

$\max_{i,j}\mathrm{Cov}(Y_{i},Y_{j})\geq-2p/(n-1).$

###### Proof.

This bound follows from non-negativity of variance and the following, after
rearranging.

$\displaystyle 0$
$\displaystyle\leq\mathrm{Var}\left(\sum_{i}Y_{i}\right)=\sum_{i}\mathrm{Var}(Y_{i})+\sum_{i,j}\mathrm{Cov}(Y_{i},Y_{j})\leq
n\cdot p+{n\choose 2}\max_{ij}\mathrm{Cov}(Y_{i},Y_{j}).\qed$

######  Lemma 6.2.

Any online rounding algorithm for bipartite fractional matchings has some
fractional matching $\mathbf{x}=\frac{1}{2}\cdot\mathbf{1}^{E}$ on graph
$G=(V,E)$ such that for some edge $e\in E$, the output matching $\mathcal{M}$
satisfies

$\Pr[e\in\mathcal{M}]\leq(2\sqrt{2}-2)\cdot x_{e}\approx 0.828\cdot x_{e}.$

###### Proof.

Consider an input with $x_{e}=1/2$ for each edge, with the first $n$ online
nodes neighboring two distinct offline nodes, with one last online node
neighboring two (judiciously chosen) offline nodes, from two prior online
nodes’ neighborhoods. We wish to show that for some instantiation of this
family of $\mathbf{x}$ and $G$, some online node (and hence some edge) is
matched with low probability. Specifically, letting $p=2\sqrt{2}-2$, we wish
to show that for some such $\mathbf{x}$ and $G$,

$\displaystyle\exists t\in[n+1]\textrm{ such that }\Pr[t\in
V(\mathcal{M})]\leq p+\frac{p}{2(n-1)},$ (19)

Since each online node $t$ has $\sum_{i}x_{it}=1$, this implies that some edge
$e$ is matched with probability at most $(2\sqrt{2}-2+\frac{p}{2(n-1)})\cdot
x_{e}$, by linearity of expectation. Taking $n$ to be sufficiently large rules
out any $(2\sqrt{2}-2+\epsilon)$-approximate rounding. We turn to prove
Equation 19.

If any of the first online nodes is matched with probability less than $p$, we
are done. Otherwise, let $Y_{t}=\mathds{1}[t\in V(\mathcal{M})]$ be indicators
for online node $t$ being matched. We couple these with variables
$Z_{t}\geq\mathrm{Ber}(p)$ such that $Y_{t}\geq Z_{t}$ always. By 6.1, there
exist two online nodes $t\neq t^{\prime}$ with
$\mathrm{Cov}(Z_{t},Z_{t^{\prime}})\geq-2p/(n-1)$. Let
$N(t)=\\{i_{1},i_{2}\\}$ and $N(t^{\prime})=\\{i_{3},i_{4}\\}$ be the
neighborhoods of $t$ and $t^{\prime}$, respectively. By a simple averaging
argument, some pair of nodes $(i,j)\in N(t)\times N(t^{\prime})$ are both
matched before the online last arrival with probability at least

$\frac{\Pr[Y_{t},Y_{t^{\prime}}]}{4}\geq\frac{\Pr[Z_{t},Z_{t^{\prime}}]}{4}\geq\frac{\Pr[Z_{t}]\cdot\Pr[Z_{t^{\prime}}]-2p/(n-1)}{4}\geq\frac{p^{2}-2p/(n-1)}{4}.$

So, if the last online node neighbors $\\{i,j\\}$, it is matched with
probability at most $1-\frac{p^{2}-2p/(n-1)}{4}$. However, as $p=2\sqrt{2}-2$
is a root of $1-y-\frac{y^{2}}{4}$, this probability is precisely
$1-\frac{p^{2}}{4}+\frac{p}{2(n-1)}=p+\frac{p}{2(n-1)}$, as desired. ∎

##### Inevitable near-positive cylinder dependence.

A useful extension of 6.1 of possible independent interest argues that for any
(sufficiently large) subset of Bernoulli variables, some subset of these
variables must be (nearly) positively cylinder dependent. In Appendix D we
prove this Ramsey-theoretic lemma.

######  Lemma 6.3.

Let $r\in\mathbb{N}$ and $0\leq\epsilon\leq p\leq 1$. Then, there exists some
$n=n_{r}(p,\epsilon)$ such that any Bernoulli variables
$Y_{1},\dots,Y_{n}\sim\mathrm{Ber}(p)$ contains some subset $I\subseteq[n]$ of
size $|I|=2^{r}$ such that

$\mathbb{E}\left[\prod_{i}Y_{i}\right]\geq\prod_{i}\mathbb{E}[Y_{i}]-\epsilon.$

##  7 Summary and Open Questions

In this work we provided a methodical study of online dependent rounding
schemes (ODRSes) for bipartite $b$-matching. We obtained optimal rounding
ratios with strong concentration for star graphs (uniform-matroid rounding)
and improved bounds beyond a ratio of $1-\frac{1}{e}$ for ($b$-)matchings,
including the first results for $b$-matchings not obtained via OCRSes.
(Consequently, ours is the only ratio beyond $1/2$ known for this problem.) We
furthermore provided a number of applications of our ODRSes and their
algorithmic approach. Beyond the natural question of improving our rounding
ratios for $b$-matchings (and the approximation/competitive ratios of their
derived applications), our work raises a number of directions for future
research.

##### Online applications.

We provided a number of online applications of our ODRSes. What further
applications do these schemes have? The bipartite setting seems particularly
relevant for online scheduling problems, with machines and jobs represented by
offline and online nodes, respectively. For minimization problems, it may
prove useful to observe that our ODRSes for $b$-matching have modest two-sided
error: edges $(i,t)$ are matched with probability at most the probability that
$i$ bids for $t$, namely $\hat{x}_{i,t}\leq(1+\delta)x_{i,t}\approx 1.064\cdot
x_{i,t}$. Moreover, these latter events satisfy strong upper-tail bounds, by
our ODRS’ strong negative correlation properties (see Property (P3) and C.1).

##### Streaming applications.

We note that our ODRSes are not only online algorithms, but moreover are
streaming (for uniform matroids) or semi-streaming algorithms (for arbitrary
$b$-matchings). Indeed, they require us to only remember $O(\log n)$-bit
partial sums and a single number per offline node. Does this property have
further applications in streaming or graph-analytics contexts?

##### Richer ODRSes.

Finally, we recall that online contention resolution schemes (OCRSes) yield
ODRSes, though this connection does not yield optimal rounding ratios. Recent
years have seen an explosion of work on OCRSes for increasingly-rich families
of arrival models and combinatorial constraints. These have been fueled in
large part by connections to various other online and economic applications,
most notably the prophet-inequality problem under more involved combinatorial
constraints (see discussion in the influential work of Kleinberg and Weinberg
[52]). Can a similarly rich theory of online dependent rounding more broadly
be developed, capturing other combinatorial constraints beyond matchings?

### Acknowledgements.

We thank Uri Feige for pointing out the connection of our work to offline
CRSes, and thank Sahil Singla for discussions about (lack of prior) examples
of black-box application of offline CRSes to online problems. We thank Manish
Purohit for asking about the two-sided error of our ODRSes, which we
anticipate may be of use in future applications for online minimization
problems.

## APPENDIX

##  Appendix A Additional Preliminaries

In this section we provide omitted proofs and additional preliminaries not
covered in Section 2.

###  A.1 Contention Resolution Schemes

We start with a brief, self-contained proof of 2.1, restated below for ease of
reference. See 2.1

###### Proof.

The lemma for product distributions follows from the work of Feige and Vondrák
[40]. We focus on the more general case, addressed by Bansal and Cohen [7],
but proven here for completeness.

Let $\alpha:=\min_{S\subseteq[n]}\frac{\Pr[R\cap S\neq\emptyset]}{\sum_{i\in
S}v_{i}}$. We prove the existence of conditional probabilities $p_{i,S}$ with
$p_{i,S}=0$ if $i\not\in S$ and $\sum_{i}p_{i,S}=1$ for all $S$ such that
setting $\Pr[O=\\{i\\}\mid R=S]=p_{i,S}$ yields
$\Pr[O=\\{i\\}]=\sum_{S}\Pr[O=\\{i\\}\mid R=S]\cdot\Pr[R=S]\geq\alpha\cdot
v_{i}$. We prove the existence of these probabilities using the max-flow/min-
cut theorem applied to the following directed flow network that has a source
vertex $src$, a sink vertex $sink$, and two other disjoint sets of vertices
$A$ and $B$. Vertices on side $A$ correspond to subsets of elements in $[n]$,
with an edge of capacity $\Pr[R=S]$ from $src$ to the node in $A$ representing
set $S$. Vertices on side $B$ correspond to elements $i\in[n]$, with an edge
of capacity $\alpha\cdot v_{i}$ leaving this vertex to $sink$. Infinite-
capacity directed edges go from each vertex in $A$ corresponding to some set
$S$, to vertices in $B$ corresponding to each $i\in S$. Each vertex $i\in S$
in $B$, has a directed edge to $sink$ with capacity $\alpha\cdot v_{i}$. This
network is reminiscent of the network used to prove Hall’s Theorem via the
max-flow/min-cut theorem. Indeed, $\min_{S\subseteq[n]}\frac{\Pr[R\cap
S\neq\emptyset]}{\sum_{i\in S}v_{i}}\geq\alpha$ is a (scaled) version of
Hall’s condition, and implies by the same argument the existence of a
“perfect” flow $f$ of value $\alpha\cdot\sum_{i}v_{i}$, implying that each
edge of the form $(i,sink)$ has its capacity $\alpha\cdot v_{i}$ saturated by
this flow. This in turn implies the existence of the probabilities $p_{i,S}$
as desired, where if the flows through the edges $(src,S)$ and $(S,i)$ are
$f_{src,S}$ and $f_{S,i}$ respectively, then $p_{i,S}=f_{S,i}/\Pr[R=S]$ (if
$\Pr[R=S]=0$, we take arbitrary non-negative $p_{i,S}$ with $p_{i,S}=0$ if
$i\not\in S$ and $\sum_{i:i\in S}p_{i,S}=1$). Thus, the above algorithm
outputs a set $O\subseteq R$ of size at most one with each element belonging
to $O$ with the requisite probability. The running time of the algorithm for
general distributions follows by polytime solubility of the maximum flow
problem. ∎

###  A.2 Negative correlation properties

Here we formalize the strong notion of negative correlation that our online
level-set algorithm enjoys.

######  Definition A.1.

A distribution $\mu:2^{[n]}\to\mathbb{R}_{\geq 0}$ is _strongly Rayleigh_ if
its generating polynomial,

$g_{\mu}(z)=\sum_{S\subseteq[n]}\mu(S)\prod_{i\in S}z_{i},$

is _real stable_ , i.e., it has no root $z\in\mathbb{C}^{n}$ satisfying
$\Im(z_{i})>0$ for all $i\in[n]$.

As stated in Section 2 and proven in [13], the strong Rayleigh property
implies NA.

######  Lemma A.2.

If $(X_{1},\dots,X_{n})$ are strongly Rayleigh binary r.v.s, then they are NA.

Moreover, since SRP is closed under conditioning [13], we find that SRP
distributions are NA even after conditioning.

The strong Rayleigh property, central to the area of geometry of polynomials,
has been highly influential in recent years. To the best of our knowledge,
aside from the classic balls-and-bins process, its variants and conditional
counterparts (see [15]), our online level-set algorithm is the only online
algorithm known to satisfy such a strong negative-correlation property. We
believe that this property of our algorithm will find further applications
outside of this work.

##### Submodular dominance.

As stated in Section 2, negative association implies stochastic dominance in
the submodular order. To formally define the above, we briefly recall the
definition of submodular functions, which are set functions capturing the
notion of diminishing returns.

######  Definition A.3.

A set function $f:2^{[n]}\to\mathbb{R}$ is _submodular_ if for all sets
$A\subseteq B\subseteq[n]$ and element $x\in[n]\setminus B$, we have that

$f(A\cup\\{x\\})-f(A)\geq f(B\cup\\{x\\})-f(B).$

The following submodular dominance result of Christofides and Vaggelatou [25]
implies that our online level-set algorithm not only preserves weighted
objectives losslessly, but also preserves submodular objectives. (See Appendix
B.)

######  Theorem A.4.

Let $X_{1},\dots,X_{n}$ be NA random variables and let
$X^{*}_{1},\dots,X^{*}_{n}$ be independent random variables that are place-
wise equal to the $X_{1},\dots,X_{n}$ respectively in distribution. Then, for
any monotone submodular function $f$,

$\mathbb{E}[f(X_{1},\dots,X_{n})]\geq\mathbb{E}[f(X^{*}_{1},\dots,X^{*}_{n})].$

###  A.3 Odds and Ends

We will also make use of the following direct corollary of convexity.

######  Claim A.5.

Let $f$ be a non-negative concave function. Then, for any $0\leq t\leq\alpha$,

$\frac{f(t)}{t}\geq\frac{f(\alpha)}{\alpha}.$

###### Proof.

Writing $t$ as a convex combination of $\alpha$ and $0$, the claim follows
from convexity, as follows.

$\displaystyle f(t)$
$\displaystyle=f\left(\frac{t}{\alpha}\cdot\alpha+\left(1-\frac{t}{\alpha}\right)\cdot
0\right)\geq\frac{t}{\alpha}\cdot
f(\alpha)+\left(1-\frac{t}{\alpha}\right)\cdot f(0)\geq\frac{t}{\alpha}\cdot
f(\alpha).\qed$

##  Appendix B Deferred Proofs of Section 3

We start by briefly proving that Algorithm 1 terminates and preserves
marginals.

######  Fact B.1.

Algorithm 1 terminates, and satisfies $\Pr[i\in\mathcal{S}]=x_{i}$ for all
$i\in[n]$ (Property (P1)).

###### Proof.

It is easy to see that STEP preserves the sum of its inputs/outputs while
decreasing the number of fractional such inputs/outputs. Consequently,
$\sum_{i}y_{i}$ is integral during the execution of Algorithm 1, while the
number of fractional $y_{i}$ decreases and cannot be one, so this algorithm
terminates with all $y_{i}$ binary. Moreover, STEP is easily seen to preserve
these values’ expectations, and so by induction we have that
$\mathbb{E}[y_{i}]=x_{i}$ for all $i$, i.e., Algorithm 1 satisfies Property
(P1). ∎

See 3.1

###### Proof.

We prove this for all $j$ by induction on $t\geq 0$. The base case is trivial.
Fix a time $t$ and let $i_{1}$ and $i_{2}$ be as in Algorithm 1 at time $t+1$.
If $i_{1},i_{2}\not\in[j]$ or $i_{1},i_{2}\in[j]$, then, since
STEP$(y_{i_{1}},y_{i_{2}})$ does not affect $Y^{t}_{j}$ in the former case and
preserves the sums $y_{i_{1}}+y_{i_{2}}$ and $Y_{j}$ in the latter case, the
inductive hypothesis implies $Y^{t+1}_{j}=Y^{t}_{j}\in\left[\lfloor
s_{j}\rfloor,\lceil s_{j}\rceil\right]$. Conversely, if $i_{1}\in[j]$ and
$i_{2}\not\in[j]$ (and therefore $i_{1}=j$), we have that
$y^{t+1}_{i}=y^{t}_{i}\in\\{0,1\\}$ for all $i\in[j-1]$, while
$y^{t+1}_{i_{1}}\in[0,1]$. Since by the inductive hypothesis we have that
$Y^{t}_{j}=Y^{t}_{j-1}+y^{t}_{j}\in\left[\lfloor s_{j}\rfloor,\lceil
s_{j}\rceil\right]$ and $Y^{t}_{j-1}=Y^{t+1}_{j-1}$ is the sum of 0-1 terms,
while $y^{t}_{j}\in(0,1)$, this implies that
$Y^{t+1}_{j}=Y^{t+1}_{j-1}+y^{t+1}_{j}=Y^{t}_{j-1}+y^{t+1}_{j}\in\left[\lfloor
s_{j}\rfloor,\lceil s_{j}\rceil\right]$. ∎

###  B.1 Direct analysis of Algorithm 3

In this section we provide a simple, self-contained proof that Algorithm 3
satisfies the first two properties we desire of it. In the main paper body, we
use this direct proof to prove that our algorithm’s output distribution is the
same as its offline counterpart, from which we also obtain the third
desideratum, namely Property (P3).

######  Lemma B.2.

Algorithm 3 is well-defined (i.e., $p_{t}\in[0,1]$ for all times $t$ and any
realization of the randomness) and it satisfies properties (P1) and (P2).

###### Proof.

We prove the above three properties (including $p_{t}\in[0,1]$) by strong
induction on $t\geq 0$. The base case, $t=0$, is trivial. As our inductive
hypothesis (I.H.), we assume that these properties hold for all
$t^{\prime}\leq t-1$ and prove them for all $t^{\prime}\leq t$, starting with
Property (P2). By the I.H., $S_{t-1}\leq\lceil s_{t-1}\rceil\leq\lceil
s_{t}\rceil$; so, since $p_{t}=0$ if $S_{t-1}=\lceil s_{t}\rceil$, we
trivially have that $S_{t}\leq\lceil s_{t}\rceil$. Moreover, by the I.H.,
$S_{t-1}\geq\lfloor s_{t-1}\rfloor=\lfloor s_{t}-x_{t}\rfloor\geq\lfloor
s_{t}\rfloor-1$; so, since $p_{t}=1$ if $S_{t-1}<\lfloor s_{t}\rfloor$, in
which case $S_{t-1}=\lfloor s_{t}\rfloor-1$, we have that $S_{t}\geq\lfloor
s_{t}\rfloor$. Thus, $S_{t}\in\\{\lfloor s_{t}\rfloor,\lceil s_{t}\rceil\\}$,
proving Property (P2).

Next we prove that Algorithm 3 is well-defined, as $p_{t}\in[0,1]$ (regardless
of prior randomness). The first non-trivial case is when $S_{t-1}=\lfloor
s_{t}\rfloor=\lfloor s_{t-1}\rfloor$. Non-negativity of $p_{t}$—a ratio of
non-negative terms—is immediate, while

$p_{t}=\frac{x_{t}}{\lfloor
s_{t-1}\rfloor+1-s_{t-1}}=\frac{s_{t}-s_{t-1}}{\lfloor
s_{t-1}\rfloor+1-s_{t-1}}\leq\frac{\lfloor s_{t}\rfloor+1-s_{t-1}}{\lfloor
s_{t-1}\rfloor+1-s_{t-1}}=\frac{\lfloor s_{t-1}\rfloor+1-s_{t-1}}{\lfloor
s_{t-1}\rfloor+1-s_{t-1}}=1.$

The second non-trivial case is when $S_{t-1}=\lfloor s_{t}\rfloor>\lfloor
s_{t-1}\rfloor,$ in which case $\lfloor s_{t}\rfloor=\lfloor
s_{t-1}\rfloor+1$. Again, non-negativity of $p_{t}$ is immediate, while

$p_{t}=\frac{s_{t}-\lfloor s_{t}\rfloor}{s_{t-1}-\lfloor
s_{t-1}\rfloor}=\frac{s_{t-1}+x_{t}-\lfloor s_{t-1}\rfloor-1}{s_{t-1}-\lfloor
s_{t-1}\rfloor}\leq\frac{s_{t-1}-\lfloor s_{t-1}\rfloor}{s_{t-1}-\lfloor
s_{t-1}\rfloor}=1.$

To prove Property (P1), we will need a closed form for
$q_{t}:=\Pr[S_{t}=\lfloor s_{t}\rfloor]$, useful when discussing
$\Pr[S_{t-1}=\lfloor s_{t}\rfloor]$, the probability that $t$ may be added to
$\mathcal{S}$, and $\Pr[S_{t-1}<\lfloor s_{t}\rfloor]$, the probability that
$t$ _must_ be added to $\mathcal{S}$ (to satisfy Property (P2)). Note that
$S_{t}\sim\lfloor s_{t}\rfloor+\textrm{Ber}(1-q_{t})$ by Property (P2), while
$\mathbb{E}[S_{t}]=\sum_{t^{\prime}\leq
t}\mathbb{E}[X_{t^{\prime}}]=\sum_{t^{\prime}\leq t}x_{t^{\prime}}=s_{t}$, by
Property (P1) (for all $t^{\prime}\leq t$) and linearity of expectation.
Combining these observations, we obtain $s_{t}=\mathbb{E}[S_{t}]=\lfloor
s_{t}\rfloor+1-q_{t}$, and therefore,

$\displaystyle q_{t}=\lfloor s_{t}\rfloor+1-s_{t}.$ (20)

We now use the closed form for $q_{t-1}$ to prove Property (P1) for time $t$.
The easy case is when $\lfloor s_{t}\rfloor=\lfloor s_{t-1}\rfloor$. Here we
have that $\mathbb{E}[X_{t}\mid S_{t-1}=\lfloor
s_{t}\rfloor]=\frac{x_{t}}{q_{t-1}}$, while trivially $\mathbb{E}[X_{t}\mid
S_{t-1}=\lceil s_{t}\rceil]=0$. Consequently, since $S_{t-1}\in\\{\lfloor
s_{t-1}\rfloor,\lceil s_{t-1}\rceil\\}=\\{\lfloor s_{t}\rfloor,\lceil
s_{t}\rceil\\}$ in this case, then by total probability we have that
$\mathbb{E}[X_{t}]=q_{t-1}\cdot\frac{x_{t}}{q_{t-1}}+0=x_{t}$, as desired.

Finally, we consider the case where $\lfloor s_{t}\rfloor>\lfloor
s_{t-1}\rfloor$, i.e., $\lfloor s_{t}\rfloor=\lfloor s_{t-1}\rfloor+1$. If in
addition $s_{t-1}=\lfloor s_{t-1}\rfloor$ (i.e., $s_{t-1}$ is integral,
implying that $s_{t}=s_{t-1}+1$, and hence $x_{t}=s_{t}-s_{t-1}=1$), we have
by Property (P2) that $S_{t-1}=s_{t-1}<\lfloor s_{t}\rfloor$ (with probability
one), and so we add $t$ to $\mathcal{S}$ with probability one, resulting in
$\mathbb{E}[X_{t}]=1=x_{t}$, as desired. If, conversely, we have that
$s_{t-1}\neq\lfloor s_{t-1}\rfloor<\lfloor s_{t}\rfloor$, then by total
probability, we obtain the desired equality as follows.

$\displaystyle\mathbb{E}[X_{t}]$ $\displaystyle=\Pr[S_{t-1}=\lfloor
s_{t-1}\rfloor]\cdot 1+\Pr[S_{t-1}\neq\lfloor
s_{t-1}\rfloor]\cdot\frac{s_{t}-\lfloor s_{t}\rfloor}{s_{t-1}-\lfloor
s_{t-1}\rfloor}$
$\displaystyle=q_{t-1}+(1-q_{t-1})\cdot\frac{x_{t}+s_{t-1}-(\lfloor
s_{t-1}\rfloor+1)}{s_{t-1}-\lfloor s_{t-1}\rfloor}$
$\displaystyle\begin{cases}s_{t}=x_{t}+s_{t-1}\\\ \lfloor s_{t}\rfloor=\lfloor
s_{t-1}\rfloor+1\end{cases}$
$\displaystyle=q_{t-1}+(1-q_{t-1})\cdot\frac{x_{t}-q_{t-1}}{1-q_{t-1}}$
$\displaystyle=x_{t}.$

###  B.2 Coupling the offline and online algorithms

Here we prove that our online level-set algorithm, Algorithm 3, induces the
same output distribution as the offline algorithm of [66], Algorithm 1 See 3.4

###### Proof.

We prove by induction on $t\in[n]$ that the following holds:

$\forall(b_{1},\ldots,b_{t-1})\in\\{0,1\\}^{t-1},~{}\Pr_{\mathcal{D}}[X_{t}=1\bigm{|}(\forall
i<t,~{}X_{i}=b_{i})]=\Pr_{\mathcal{D}^{\prime}}[X_{t}=1\bigm{|}(\forall
i<t,~{}X_{i}=b_{i})].$ (21)

The (strong) inductive hypothesis, whereby Equation 21 holds for all
$t^{\prime}<t$ clearly implies that for all
$(b_{1},\dots,b_{t})\in\\{0,1\\}^{t-1}$ we have that
$\Pr_{\mathcal{D}}[(\forall
i<t,~{}X_{i}=b_{i})]=\Pr_{\mathcal{D}^{\prime}}[(\forall
i<t,~{}X_{i}=b_{i})]$. Similarly, Equation 21 holds for all $t\leq n$ iff the
two distributions are the same.

The base case $t=1$ follows from Property (P1). So suppose $t>1$. Fix
$b_{1},\ldots,b_{t-1}\in\\{0,1\\}$, and let $\mathcal{E}$ denote the event
“$\forall i<t,~{}X_{i}=b_{i}$" (measured w.r.t. $\mathcal{D}$ or w.r.t.
$\mathcal{D}^{\prime}$). Then, by the strong induction hypothesis,
$\Pr_{\mathcal{D}}[\mathcal{E}]=\Pr_{\mathcal{D}^{\prime}}[\mathcal{E}]$, and
in particular, $\Pr_{\mathcal{D}}[\mathcal{E}]\not=0$ iff
$\Pr_{\mathcal{D}^{\prime}}[\mathcal{E}]\not=0$; thus we may assume that the
events conditioned on in the LHS and in the RHS of (21) both have nonzero
(identical) probabilities. This is the only place where we will need the
induction hypothesis.

Recall that $s_{t-1}=\sum_{i=1}^{t-1}x_{i}$. Furthermore, although $S_{t-1}$
technically depends on the rounding algorithm, it is natural to take it to be
$\sum_{i=1}^{t-1}b_{i}$ here. Note that since both the offline and online