# Multiway Online Correlated Selection

Guy Blanc
Stanford University Moses Charikar
Stanford University

###### Abstract

We give a $0.5368$-competitive algorithm for edge-weighted online bipartite
matching. Prior to our work, the best competitive ratio was $0.5086$ due to
Fahrbach, Huang, Tao, and Zadimoghaddam (FOCS 2020). They achieved their
breakthrough result by developing a subroutine called _online correlated
selection_ (OCS) which takes as input a sequence of pairs and selects one item
from each pair. Importantly, the selections the OCS makes are negatively
correlated.

We achieve our result by defining _multiway_ OCSes which receive arbitrarily
many elements at each step, rather than just two. In addition to better
competitive ratios, our formulation allows for a simpler reduction from edge-
weighted online bipartite matching to OCSes. While Fahrbach et al. used a
factor-revealing linear program to optimize the competitive ratio, our
analysis directly connects the competitive ratio to the parameters of the
multiway OCS. Finally, we show that the formulation of Farhbach et al. can
achieve a competitive ratio of at most $0.5239$, confirming that multiway
OCSes are strictly more powerful.

##  1 Introduction

The matching problem has played a pivotal role in the development of
algorithmic techniques in combinatorial optimization. The online version of
the problem was one of the first graph optimization problems studied in the
online literature. Karp, Vazirani and Vazirani [KVV90] initiated a study of
the problem and gave a $1-1/e$ competitive algorithm for unweighted graphs.
Here, the vertices of one side (the offline side) are known to the algorithm
in advance. The vertices of the other side appear in an online fashion. As
they appear, they must be matched irrevocably to an offline vertex (or
discarded). Since the work of [KVV90], online bipartite matching received
considerable attention and their ideas were applied to a variety of other
online assignment problems.

More than a decade later, the emergence of sponsored search auctions gave
renewed impetus to the study of online matching and its variants. There is a
natural correspondence here – the offline side corresponds to advertisers and
the online side corresponds to impressions (i.e. opportunities to place ads).
Aggarwal et al [AGKM11] generalized the [KVV90] result to the vertex-weighted
case, obtaining a $1-1/e$ competitive algorithm.

The edge-weighted case had remained a tantalizing open problem until very
recently. Here, it is not hard to see that no non-trivial competitive ratio is
possible without giving the algorithm additional flexibility. Researchers have
focused on the free disposal setting where offline vertices can be assigned
multiple online vertices but the contribution of an offline vertex to the
objective function is the largest of the edge weights assigned to that vertex.
(i.e. previously matched edges can be disposed for free to make room for
higher weight edges). In the display advertising setting, this corresponds to
assigning multiple impressions to an advertiser.

For the edge weighted problem, a natural greedy algorithm achieves competitive
ratio 0.5. This was the best known until the recent breakthrough by Fahrbach,
Huang, Tao and Zadimoghaddam [FHTZ20] who gave a 0.5086 competitive algorithm.
One of their main technical contributions was a novel algorithmic ingredient
called online correlated selection (OCS). This is an online subroutine that
takes a sequence of pairs of vertices as input and selects one vertex from
each pair such that decisions across pairs are negatively correlated. A
suitable quantification of this negative correlation was plugged into a factor
revealing linear program to obtain a bound on the competitive ratio.

In this work we give a series of generalizations of the OCS definition of
Fahrbach et al [FHTZ20] to multiway OCSes which take in multiple vertices at
each step. Our analysis directly connects the parameters of our multiway OCS
to the eventual competitive ratio without the need to go through a factor
revealing linear program. We give a general framework for obtaining multiway
OCSes and instantiate this framework to obtain an improved competitive ratio
of $0.5368$ for online weighted matching. Finally, we show that the OCS
definition of Fahrbach et al [FHTZ20] cannot lead to a competitive ratio
better than 0.5239 demonstrating that our multiway OCSes are strictly more
powerful.

###  1.1 Related Work

Online weighted matching has been extensively studied in the literature. See
the excellent survey by Mehta [Meh13] for a comprehensive overview. Two
popular settings where competitive ratios better than 0.5 have been obtained
are
(1) the case where offline vertices have large capacity (i.e a large number of
online vertices can be assigned to an offline vertex). This includes work of
Kalyanasundaram and Pruhs [KP00], Feldman et al [FKM+09] on Display Ads and
work on the Adwords problem [MSVV07, BJN07].
(2) the case where stochastic information is available about the online
vertices. This includes work in the setting where online vertices are drawn
from a known or unknown distribution [FMMM09, KMT11, DJSW19, HMZ11, MGS12,
MP12, JL14] or the setting that they arrive in a random order [GM08, DH09,
FHK+10, MY11, MGZ12, MWZ14, HTWZ19].
In addition to these, several recent advances have been made in more general
settings including non-bipartite graphs and different arrival models [HKT+18,
GKS19, GKM+19, HPT+19].

##  2 Our contributions

We have three main contributions.

  1. 1.

We give a series of generalizations of the OCS definition of Fahrbach et al.
so that they can take in arbitrarily many elements at each step, rather than
just $2$. In addition to allowing for more flexible and powerful OCSes, our
definition allows for a simpler reduction from edge-weighted online bipartite
matching to OCSes.

  2. 2.

We give a general framework for multiway OCSes. This framework reduces the
task of constructing an OCS to that of finding a distribution over infinite
sequences of real numbers, $\bm{x}_{1},\bm{x}_{2},\ldots$, where the elements
are sufficiently negatively correlated. Then, we instantiate this framework to
give a multiway OCS leading to a $\Gamma=0.5368$ competitive ratio.

  3. 3.

We prove that Fahrbach et al.’s formulation can achieve a competitive ratio of
at most $0.5238$ confirming that multiway OCSes are strictly more powerful.

###  2.1 OCS definitions and consequences

We begin by describing the input and output of an OCS.

######  Definition 1 (Discrete OCS).

Consider a set of ground elements. A _m-discrete OCS_ is an online algorithm
that at each time step $j=1,2,\ldots$, is given a size-$m$ multiset $A_{j}$ of
elements and irrevocably selects a single winner from $A_{j}$.

In order to achieve a good competitive ratio, we want the decisions of our OCS
to be negatively correlated. If an element is not selected in one time step,
it should be more likely to be selected the next time it appears. There are a
variety of ways to quantify this. We begin with the definition of Fahrbach et
al. In the below definition, a sequence of time steps $S\subseteq\mathds{N}$
is _consecutive_ if it is of the form $S=\\{j_{1},\ldots,j_{2}\\}$ for some
$j_{1}<j_{2}$. Two sequences $S_{1},S_{2}\subseteq\mathds{N}$ and _disjoint_
if their intersection is empty.

######  Definition 2 ($\gamma$-OCS of [FHTZ20]).

For any $\gamma\in[0,1]$, a $\gamma$-OCS is a $2$-discrete OCS with the
following guarantee. For any element $i$ and disjoint, consecutive time steps
$S_{1},\ldots,S_{k}$, the probability $i$ is never selected at a time step in
$S_{1}\cup\ldots\cup S_{k}$ is upper bounded by

$\displaystyle\prod_{\ell=1}^{k}2^{-\mathrm{count}_{i}(S_{\ell})}\cdot(1-\gamma)^{(\mathrm{count}_{i}(S_{\ell}))-1)_{+}}$

where $\mathrm{count}_{i}(S)$ is the total number of times $i$ appears in
$A_{j}$ for $j\in S$.

######  Remark 1.

Even for $j_{1}$ and $j_{2}$ far apart, whether $i$ is selected in $j_{1}$ and
whether it is selected in $j_{2}$ are anticorrelated as long as $i$ does not
appear between $j_{1}$ and $j_{2}$. In that case, we can just set the
$S=\\{j_{1},\ldots,j_{2}\\}$. Using the fact that $i$ cannot be selected in
rounds in which it does not appear, $i$ must be selected in $j_{1}$ or $j_{2}$
with probability at least $1-\frac{1}{4}\cdot(1-\gamma)$. The same effect
occurs in Definitions 3 and 5.

We generalize Definition 2 in two ways: We allow $m\geq 2$, and make the
function mapping $\mathrm{count}_{i}(S_{\ell})$ to a probability more flexible
than a piecewise exponential.

######  Definition 3 (Parameters of a discrete OCS).

For any $m\in\mathds{N}$ and $F:\mathds{Z}_{\geq 0}\to[0,1]$, an
$(F,m)$-discrete OCS is an $m$-discrete with the following guarantee. For any
element $i$, and disjoint, consecutive time steps $S_{1},\ldots,S_{k}$, the
probability $i$ never wins at any time step in $S_{1}\cup\ldots\cup S_{k}$ is
upper bounded by

$\displaystyle\prod_{\ell=1}^{k}F\left(\mathrm{count}_{i}(S_{\ell})\right).$

For example, the OCS that independently and uniformly picks a winner at each
round achieves $F_{\mathrm{trivial}}(n)=(1-1/m)^{n}$. Our goal is to construct
OCSes with $F<F_{\mathrm{trivial}}$, which directly leads to competitive
ratios better than $\frac{1}{2}$.

######  Theorem 1 (Informal version of Theorem 6).

For any $m\in\mathds{N}$ and convex $F:\mathds{Z}_{\geq 0}\to[0,1]$, if is
there an $(F,m)$-discrete OCS, there is an algorithm for edge-weighted online
bipartite matching with competitive ratio of

$\displaystyle\Gamma\coloneqq
1-\sum_{n=0}^{\infty}\frac{m^{n}}{(m+1)^{n+1}}\cdot F(n).$

As an corollary of Theorem 1, we are able to derive an explicit formula
mapping $\gamma$ to a competitive ratio for the OCS in Definition 2.

######  Theorem 2.

For any $\gamma\in(0,1)$, if there is a $\gamma$-OCS, there is an algorithm
for edge-weighted online bipartite matching with a competitive ratio of

$\displaystyle\Gamma=\frac{3+2\gamma}{6+3\gamma}.$ (1)

In contrast, Fahrbach et al. derive their matching algorithm using a factor-
revealing linear program that obfuscates the connection between $\gamma$ and
the derived competitive ratio. We confirmed that Theorem 2 gives the same
competitive ratio as their linear program at a variety of $\gamma$ to high
precision (our competitive ratios are slightly higher, likely due to
computational constraints).

Ultimately, we will construct a discrete OCS for a modest $m$. We use $m=6$ as
it gives the best competitive ratio for our construction. However, in order to
prove Theorem 1, we need to consider a generalization of Definition 1 to the
case of $m\to\infty$, which we call a _continuous OCS_. Later, we will show
how to construct a continuous OCS from a discrete OCS. In the following
definition, a _probability vector_ is a nonnegative vector whose elements sum
to $1$.

######  Definition 4 (Continuous OCS).

Consider a set of ground elements, $L$. A _continuous OCS_ is an online
algorithm that at each time step $j=1,2,\ldots$ receives a probability vector
$p^{(j)}$ with $|L|$ elements and irrevocably chooses a winner in $i\in L$
among those with $(p^{(j)})_{i}\geq 0$.

Element $i$ will be selected in round $j$ with marginal probability
approximately $(p^{(j)})_{i}$. Once again, we want these selects to be
negatively correlated. We quantify this negative correlation in the following
definition, though we defer the full formal definition to later.

######  Definition 5 (Parameters of a continuous OCS, informal version of
Definition 11).

For any function $f:\mathds{R}_{\geq 0}\to[0,1]$, a $f$-continuous OCS is a
continuous OCS with the following guarantee. For any element $i\in L$ and
disjoint, consecutive time steps $S_{1},\ldots,S_{k}$, the probability $i$
never wins at any time step in $S_{1}\cup\ldots\cup S_{k}$ is upper bounded by

$\displaystyle\prod_{\ell=1}^{k}f\left(\mathrm{weight}_{i}(S_{\ell})\right)$

where

$\displaystyle\mathrm{weight}_{i}(S)\coloneqq\sum_{j\in S}(p^{(j)})_{i}.$

For example, the OCS that independently picks $i$ at step $j$ with probability
$(p^{(j)})_{i}$ is $f_{\mathrm{trivial}}$-continuous OCS for
$f_{\mathrm{trivial}}(x)\coloneqq e^{-x}$. Once again, constructions of
$f$-continuous OCSes for $f<f_{\mathrm{trivial}}$ lead to competitive ratios
better than $\frac{1}{2}$.

######  Theorem 3 (Informal version of Theorem 5).

For any differentiable and convex $f:\mathds{R}_{\geq 0}\to[0,1]$, if is there
an $f$-continuous OCS, there is an algorithm for edge-weighted online
bipartite matching with competitive ratio of

$\displaystyle\Gamma\coloneqq 1-\int_{0}^{\infty}e^{-t}f(t)dt.$

Our proof of Theorem 5 uses a similar online primal-dual formulation as that
used by Fahrbach et al. We find that using the continuous OCS definition in
place of a their OCS simplifies that primal-dual formulation and allows us to
solve for all of the parameters analytically. Part of the reason that their
primal-dual formulation is complex is because, in each round, their algorithm
needs to decide whether to execute one of three round types, referred to in
their work as a “deterministic” rounds, “randomized” rounds, and “unmatched”
rounds. Our continuous formulation eliminates this need as the algorithm can
implicitly interpolate between all three round types.

Lastly, we remark that “perfect negative correlation” for Definition 2
corresponds to $\gamma=1$. As noted in [FHTZ20] and can be confirmed by
plugging $\gamma=1$ into Theorem 2, that corresponds to a competitive ratio of
$\Gamma=\frac{5}{9}$. This is far from the best known upper bound of
$\Gamma=1-\frac{1}{e}$. On the other hand, perfect negative correlation for a
continuous OCS corresponds to $f(x)=(1-x)_{+}$ which gives a competitive ratio
of $\Gamma=1-\frac{1}{e}$. While perfect negative correlation is impossible,
the fact that it corresponds to a competitive ratio equal to the best known
upper bound seems to suggest that continuous OCSes are a step in the right
direction towards finding the optimal competitive ratio.

###  2.2 Construction of a multiway OCS

We reduce the task of constructing a multiway OCS to that of constructing an
anti-correlated “win distribution,” an infinite sequence of random variables
$(\bm{x}_{1},\bm{x}_{2},\ldots)\in[0,1]$. Roughly speaking, the
$k^{\mathrm{th}}$ time vertex $i$ appears, it wins the round with probability
$\bm{x}_{k}$. This win distribution has to obey certain properties. For
example, since only $1$ of the $m$ elements in $A_{j}$ can be a winner, it
must be the case $\mathop{{\mathds{E}}\/}[\bm{x}]\leq\frac{1}{m}$. In Section
7 we formally state these properties, describe why they are necessary, and
give pseudocode for our meta algorithm. We also state Theorem 7 which gives a
formula mapping the win distribution to a function $F$ such that our meta
algorithm is an $(F,m)$-discrete OCS. In order to minimize this $F$, and hence
maximize the resulting competitive ratio, we want the variables
$\bm{x}_{1},\bm{x}_{2},\ldots$ to be as strongly negatively correlated from
the surrounding variables as possible

In order to prove Theorem 7, we need a number of tools from probability
theory. We require the variables $(\bm{x}_{1},\bm{x}_{2},\ldots)$ to be
_negatively associated_ , a generalization of negative correlation to more
than two variables. Negatively associated variables satisfy a number of
desirable properties and are an integral part of our proof. Later on, we
formalize what it means for one variable to be “larger and more spread out”
than another using the _increasing convex order_. We do so to take advantage
of a powerful result by Müller and Rüschendorf [MR01] which generalizes a
classic result of Strassen [Str65]. That result guarantees the existence of a
particular coupling $(\bm{a},\bm{b})$ whenever $\bm{b}$ is “larger and more
spread out” than $\bm{a}$. These techniques are described in more detail in
Section 7.

Then, in Section 8, we construct a parameters family of win distributions and
prove it has the properties required by Theorem 7. Using brute-force search
over the parameter, we pick one such distribution that maximizes the resulting
competitive ratio proving the following theorem.

######  Theorem 4.

There is a $\Gamma=0.5368$-competitive algorithm for edge-weighted online
bipartite matching.

For technical reasons (see Remark 2), we get the best competitive ratio with
$m=6$. However, we believe that these technical issues are surmountable and
that a better analysis would show that larger $m$ lead to a better competitive
ratio. In the limit of $m\to\infty$, our construction directly gives a
continuous OCS; analysis of that continuous OCS is a promising direction
towards an improved competitive ratio.

###  2.3 Negative results

Lastly, we prove the following for Fahrbach et al.’s formulation of an OCS.

######  Lemma 2.1.

No $\gamma$-OCS exists for $\gamma>\frac{1}{3}$.

Both Theorem 2 and the linear program of [FHTZ20] agree that the competitive
ratio for $\gamma=\frac{1}{3}$ is less than $0.5239$. Hence, this is an upper
bound on the competitive ratios that can be achieved simply by constructing
better $\gamma$-OCSes . Our competitive ratio of $0.5367$ is larger,
confirming that multiway OCSes are strictly more powerful.

###  2.4 Comparison to the concurrent work of Gao et al.

Concurrently and independently, Gao et al. also explored the use of multiway
OCSes in the construction of improved online matching algorithms [GHH+21]. The
bulk of their work focuses on _vertex-weighted_ online bipartite matching.
This is a special case of _edge-weighted_ online bipartite matching where we
assume that all edges to any particular offline vertex have the same weight.
While an algorithm achieving the optimal competitive ratio competitive ratio
of $(1-\frac{1}{e})$ is known in this setting [AGKM11], Gao et al. are able to
show that OCSes can also be used to tackle this problem and achieve a
competitive ratio of $0.593$.

They do so by developing a definition of multiway OCSes similar to our
definition of continuous OCSes. In the vertex-weighted setting we only care
about whether an element $i$ is selected at least once at some time step and
do not care about which time step it is selected in. Their definition for a
“multi-way semi-OCS” is equivalent to Definition 5 where we take $k=1$ and
$S_{1}$ the set containing all time steps. For vertex-weighted online
bipartite matching, they derive the same formula for the competitive ratio as
we do in Theorem 3 using “multi-way semi-OCSes.” A similar result could be
derived using our algorithm by never executing Equation 15 (since we only care
about whether a vertex is matched, not when it is matched). The resulting
algorithm and analysis simplifies.

We stress that extending multiway OCSes to the historically challenging edge-
weighted setting requires overcoming additional hurdles.

  1. 1.

The informal definition of Definition 5 isn’t strong enough to derive Theorem
3. We needed to identify an additional constraint on the OCS (see “partially
ignore small gaps” of Definition 11) that is both feasible to construct and
sufficient to developing an algorithm for edge-weighted online bipartite
matching.

  2. 2.

Constructing a multiway OCS is more challenging than a “multi-way semi-OCS”
and we need to develop a new framework to do so. For example, in the
construction of Gao et al., the probability a vertex is selected in a late
time step can be made arbitrarily small (since they only need each vertex to
be matched once), and so would not meet our definition.

Gao et al. also contribute to the _edge-weighted_ setting. In this setting,
they give $0.519$-competitive algorithm by constructing an improved $2$-way
OCS. Their result improves upon the competitive ratio of Fahrbach et al.
[FHTZ20] though isn’t as large as ours. They also derive Theorem 2 with a
different proof than ours. Finally, they prove that no $\gamma$-OCS exists for
$\gamma>\frac{1}{4}$, which is stronger than the $\frac{1}{3}$ bound we show
in Lemma 2.1. For our purposes, the conclusion is the same: Multiway OCSes are
strictly more powerful than two-way OCSes for edge-weighted online bipartite
matching.

##  3 Organization of this paper

In Section 5, we formalize Theorems 1 and 3 and prove Theorems 1 and 2 as
consequences of Theorem 3. In Section 6, we prove Theorem 3. Then in Section
7, we give the meta algorithm for constructing multiway OCSes and prove
Theorem 7 quantifying the performance of the meta algorithm as a function of
the “win distribution”. In Section 8 we give a particular win distribution,
which when plugged into our meta algorithm, gives OCS leading to a competitive
ratio of $\Gamma=0.5386$, completing the proof of Theorem 4. Finally, in
Section 9 we provide a short proof of Lemma 2.1.

##  4 Preliminaries

###  4.1 The edge-weighted online bipartite matching problem

Consider some weighted bipartite graph $G=(L,R,w)$, where $L$ and $R$ are the
left and right vertices respectively. If there is an edge between $i\in L$ and
$j\in R$ then $w_{ij}>0$ is the weight of that edge. Otherwise, $w_{ij}=0$.

At the start, the algorithm is given the entire set of left vertices, $L$, but
not access to $R$ or $w$. These vertices from $R$ appear in an online fashion,
one by one. Hence, we refer to $L$ as the _offline_ vertices $R$ as the
_online_ vertices. When an online vertex $j\in R$ appears the entries $w_{ij}$
for each $i\in L$ are also revealed to the algorithm. The algorithm must
irrevocably decide which offline vertex to match $j$ to before the next online
vertex appears.

We operate in the _free disposal model_. This means a single online vertex $i$
may be matched to multiple online vertices, but when computing the weight of
the matching, only the largest such weight is used for each $i$. The goal of
our algorithm is to maximize the total weight of the matching. We say a
randomized algorithm is “$\Gamma$-competitive” or “has competitive ratio of
$\Gamma$” if the expected total weight of the matching output by the algorithm
is within a multiplicative factor of $\Gamma$ of the optimal total weight with
hindsight.

###  4.2 Notation and definitions

For brevity, we use _decreasing_ in place of _nondecreasing_ and _increasing_
in place of _nondecreasing_. The notation $(x)_{+}$ is used as shorthand for
$\max(x,0)$.

We use boldface (e.g. $\bm{x}\sim\mathcal{D}$) to denote random variables. The
notation $\bm{a}\overset{d}{=}\bm{b}$ signifies that $\bm{a}$ and $\bm{b}$
have the same distribution. The following distributions are of interest.

  1. 1.

The uniform distribution $\bm{x}\sim\mathrm{Uniform}(0,1)$, gives a continuous
$\bm{x}$ equally likely to be anywhere on the interval $[0,1]$.

  2. 2.

The Bernoulli distribution, $\bm{x}\sim\mathrm{Ber}(p)$, gives a discrete
$\bm{x}$ that is $1$ with probability $p$ and $0$ otherwise.

  3. 3.

The geometric distribution, $\bm{x}\sim\mathrm{Geo}(p)$ gives $i-1$, where $i$
is the smallest index such that $\bm{y}_{i}=1$ for
$\bm{y}_{1},\bm{y}_{2},\ldots\overset{\mathrm{iid}}{\sim}\mathrm{Ber}(p)$.

  4. 4.

The Poisson distribution, $\bm{x}\sim\mathrm{Poi}(\lambda)$ gives $\bm{x}$
defined as the following limit

$\displaystyle\bm{x}\coloneqq\lim_{n\to\infty}\left(\sum_{i=1}^{n}\bm{x}_{i}\quad\text{where}\quad\bm{x}_{i}\overset{\mathrm{iid}}{\sim}\mathrm{Ber}(\lambda/n)\right).$

  5. 5.

The categorical distribution,
$\bm{i}\sim\mathrm{Categorical}(p_{1},\ldots,p_{m})$ where
$\sum_{j=1}^{m}p_{j}=1$, gives a discrete $\bm{i}$ where $\bm{i}=i$ with
probability $p_{i}$.

We’ll need various ways to compare distributions. The simplest is _stochastic
dominance_.

######  Definition 6 (Stochastic dominance).

Let $\bm{a}$ and $\bm{b}$ be random variables over $\mathds{R}$. We say that
$\bm{a}$ _stochastically dominates_ $\bm{b}$, denoted $\bm{a}\succeq\bm{b}$
if, for any $t\in\mathds{R}$,

$\displaystyle\operatorname{{Pr}}[\bm{a}\leq
t]\leq\operatorname{{Pr}}[\bm{b}\leq t]$

######  Definition 7 (Stochastically increasing/decreasing functions).

A stochastic function ${\bm{f}}$ from $\mathds{R}^{n}$ to a distribution over
$\mathds{R}$ is said to be _increasing_ in coordinate $i\in[n]$ if for any
$x,y\in\mathds{R}^{n}$ where $x_{j}=y_{j}$ for each $j\neq i$ and $x_{i}\geq
y_{i}$, ${\bm{f}}(x)$ stochastically dominates ${\bm{f}}(y)$. It is said to be
stochastically _decreasing_ in coordinate $i$ if the ${\bm{f}}(y)$
stochastically dominates ${\bm{f}}(x)$ under the same conditions. A function
is stochastically increasing (or decreasing) if it is stochastically
increasing (or decreasing) in all of its coordinates.

In some cases, we’ll need for one distribution to be “less spread out“ than
another. We use the following two notions. For a more thorough overview, see
[SS07].

######  Definition 8 (Convex order).

Let $\bm{a},\bm{b}$ be two univariate random variables such that,

$\displaystyle\mathop{{\mathds{E}}\/}[\phi(\bm{a})]\leq\mathop{{\mathds{E}}\/}[\phi(\bm{b})]$

for all convex functions $\phi:\mathds{R}\to\mathds{R}$ for which the above
expectations exist. Then, we say $\bm{a}$ is smaller than $\bm{b}$ in the
_convex order_ and denote this,

$\displaystyle\bm{a}\preceq_{\mathrm{cx}}\bm{b}.$

Similar to the above, but where we restrict $\phi$ to be increasing,

######  Definition 9 (Increasing convex order).

Let $\bm{a},\bm{b}$ be two univariate random variables such that,

$\displaystyle\mathop{{\mathds{E}}\/}[\phi(\bm{a})]\leq\mathop{{\mathds{E}}\/}[\phi(\bm{b})]$

for all increasing convex functions $\phi:\mathds{R}\to\mathds{R}$ for which
the above expectations exist. Then, we say $\bm{a}$ is smaller than $\bm{b}$
in the _increasing convex order_ and denote this,

$\displaystyle\bm{a}\preceq_{\mathrm{icx}}\bm{b}.$

We’ll also use _discrete derivatives_

######  Definition 10 (Discrete derivative).

For any function $F:\mathds{Z}\to\mathds{R}$, the discrete derivative of $F$
is defined as

$\displaystyle(\Delta F)(n)\coloneqq F(n+1)-F(n).$

We use the notation $\Delta^{(\ell)}$ to denote the discrete derivative
operator composed $\ell$ times.

##  5 Formal statement of theorems

In this section we formalize Theorems 1 and 3 and prove that both Theorems 1
and 2 are consequences of Theorem 3. Before doing so, we need to formalize our
definition of a continuous OCS. Recall in Definition 5, that we guarantee the
probability $i$ isn’t picked in disjoint and consecutive sequences $S_{1}$ and
$S_{2}$ is at most

$\displaystyle f(\mathrm{weight}_{i}(S_{1}))\cdot
f(\mathrm{weight}_{i}(S_{2})).$ (2)

On the other hand, if $S_{1}$ and $S_{2}$ are actually consecutive, then the
probability $i$ isn’t picked is at most

$\displaystyle
f\big{(}\mathrm{weight}_{i}(S_{1})+\mathrm{weight}_{i}(S_{2})\big{)}.$ (3)

We should think of $f(x+y)<f(x)\cdot f(y)$ and so Equation 3 gives a stronger
guarantee than Equation 2. Now, suppose that $S_{1}$ and $S_{2}$ are almost
consecutive. For $S_{1}=\\{j_{1},\ldots,j_{2}\\}$ and
$S_{2}=\\{j_{3},\ldots,j_{4}\\}$, perhaps its the case that $j_{3}=j_{2}+2$.
Then, intuitively, we should expect a guarantee close to that of Equation 3 to
hold.

Let $G$ be the time steps in the “gap”, meaning
$G\coloneqq\\{j_{2}+1,\ldots,j_{3}-1\\}$. For some rate parameter $r$ and
$w\coloneqq\prod_{j\in G}(1-r\cdot p^{(j)}_{i})_{+}$, we will guarantee that
the probability $i$ is not selected in $S_{1}$ or $S_{2}$ is at most

$\displaystyle w\cdot
f\big{(}\mathrm{weight}_{i}(S_{1})+\mathrm{weight}_{i}(S_{2})\big{)}+(1-w)\cdot
f(\mathrm{weight}_{i}(S_{1}))\cdot f(\mathrm{weight}_{i}(S_{2}))$

Essentially, when determining the probability $i$ is picked, we pretend the
gap $G$ doesn’t exist with probability $w$. This guarantee smoothly
interpolates between Equations 3 and 2 as $S_{1}$ and $S_{2}$ grow further
apart. We generalize this idea to more than two sets in the following
definition.

######  Definition 11 (Parameters of a continuous OCS, formal version of
Definition 5).

For any rate $r\geq 0$ and function $f:\mathds{R}_{\geq 0}\to[0,1]$, an OCS is
$(f,r)$-_continuous OCS_ if, for any element $i\in L$ and set of time steps
$S$, the probability that $i$ never wins in $S$ is upper bounded by
$\mathcal{F}(S,p)$, where $p$ is the vector who’s $j^{\mathrm{th}}$ entry is
$(p^{(j)})_{i}$ and $\mathcal{F}$ satisfies

  1. 1.

Consecutive: If $S=\\{j_{1},\ldots,j_{2}\\}$, then

$\displaystyle\mathcal{F}(S,p)\leq f\left(\sum_{j\in S}p_{j}\right)$

  2. 2.

Partially ignore small gaps: For any disjoint (not necessarily consecutive)
$S_{1},S_{2}\subseteq\mathds{N}$ satisfying

$\displaystyle j_{1}<j_{2}\text{ for each $j_{1}\in S_{1},j_{2}\in S_{2}$}$

Let $j^{\star}$ be some time step between $j_{1},j_{2}$ for every $j_{1}\in
S_{1},j_{2}\in S_{2}$. For

$\displaystyle\mathrm{del}_{j^{\star}}(S_{1}\cup S_{2})$
$\displaystyle\coloneqq\\{j\text{ for each }j\in S_{1}\\}\cup\\{j-1\text{ for
each }j\in S_{2}\\}$ $\displaystyle(\mathrm{del}_{j^{\star}}(p))_{j}$
$\displaystyle\coloneqq\begin{cases}p_{j}&j<j^{\star}\\\ p_{j+1}&j\geq
j^{\star}\end{cases}$

Then, for $w=(1-r\cdot p_{j^{\star}})_{+}$,

$\displaystyle\mathcal{F}(S_{1}\cup S_{2},p)\leq
w\cdot\mathcal{F}(\mathrm{del}_{j^{\star}}(S_{1}\cup
S_{2}),\mathrm{del}_{j^{\star}}(p))+(1-w)\cdot\mathcal{F}(S_{1},p)\cdot\mathcal{F}(S_{2},p)$
(4)

Smaller $r$ corresponds to ignoring larger gaps, making the OCS anticorrelated
over larger distances. We next give a formal version of Theorem 3, with the
main difference being that we $r$ can’t be too large.

######  Theorem 5 (Formal version of Theorem 3).

For any thrice differentiable convex $f:\mathds{R}_{\geq 0}\to[0,1]$ where
$f^{\prime}$ is log-concave, meaning

$\displaystyle f^{\prime\prime\prime}(x)\cdot
f^{\prime}(x)\leq(f^{\prime\prime}(x))^{2}\quad\quad\text{for all $x\geq 0$}$

satisfying $\lim_{x\to\infty}f(x)=0$, let,

$\displaystyle\Gamma\coloneqq 1-\int_{0}^{\infty}e^{-t}f(t)dt.$ (5)

For any $r$ satisfying

$\displaystyle r\leq\frac{-f^{\prime}(0)-\Gamma}{\Gamma+(1-\Gamma)\cdot
f^{\prime}(0)}$ (6)

If there is a $(f,r)$-continuous OCS, then there is a $\Gamma$-competitive
algorithm for edge-weighted online bipartite matching.

We prove Theorem 5 in Section 6.

###  5.1 Discrete OCS $\to$ continuous OCS

In this section, we show how to construct a continuous OCS from a discrete
OCS. That will allow us to prove Theorems 2 and 1 assuming Theorem 5.

######  Lemma 5.1.

If there is an $(F,m)$-discrete OCS for convex and log-concave $F$, there is
an $(f,r=m)$-continuous OCS for

$\displaystyle
f(x)\coloneqq\mathop{{\mathds{E}}\/}_{\bm{k}\sim\mathrm{Poi}(\lambda=m\cdot
x)}[F(\bm{k})]$ (7)

The continuous OCS algorithm in Lemma 5.1 is simple. When the continuous OCS
receives the probability vector $p^{(j)}$, it sets the multiset
$A_{j}=\\{\bm{i}_{1},\ldots,\bm{i}_{m}\\}$ where each $\bm{i}_{\ell}$ is
sampled iid from $\mathrm{Categorical}(p^{(j)})$. It passes this multiset into
the $(F,m)$-discrete OCS, and then selects the same vertex selected by the
discrete OCS.

Before analyzing this OCS, we’ll need some well-known facts about the convex
order (recall Definition 8).

######  Fact 5.2 (Theorem 3.A.4 of [SS07]).

For any univariate random variables $\bm{a},\bm{b}$, if there exists a
coupling $(\hat{\bm{a}},\hat{\bm{b}})$ where
$\bm{a}\overset{d}{=}\hat{\bm{a}}$ and $\bm{b}\overset{d}{=}\hat{\bm{b}}$ such
that

$\displaystyle\mathop{{\mathds{E}}\/}[\hat{\bm{b}}\mid\hat{\bm{a}}]=\hat{\bm{a}}$

then $\bm{a}\preceq_{\mathrm{cx}}\bm{b}$.

######  Fact 5.3 (Theorem 3.A.12(d) of [SS07]).

The convex order is closed under convolution: Let
$\bm{a}_{1},\ldots,\bm{a}_{k}$ and $\bm{b}_{1},\ldots,\bm{b}_{k}$ each be
independent univariate random variables. If
$\bm{a}_{\ell}\preceq_{\mathrm{cx}}\bm{b}_{\ell}$ for each $\ell=1,\ldots,m$,
then

$\displaystyle\sum_{\ell=1}^{m}\bm{a}_{\ell}\preceq_{\mathrm{cx}}\sum_{\ell=1}^{m}\bm{b}_{\ell}.$

The following proposition is a simple consequence of the above two facts.

######  Proposition 5.4.

For any $p_{1},\ldots,p_{n}\in[0,1]$, let $\bm{x}_{i}\sim\mathrm{Ber}(p_{i})$
and $\bm{y}\sim\mathrm{Poi}(\lambda=\sum_{i=1}^{n}p_{i})$. Then,

$\displaystyle\sum_{i=1}^{n}\bm{x}_{i}\preceq_{\mathrm{cx}}\bm{y}.$

###### Proof.

By 5.3, it is enough to prove that $\bm{x}_{i}\preceq_{\mathrm{cx}}\bm{y}_{i}$
where $\bm{y}_{i}\sim\mathrm{Poi}(\lambda=p_{i})$. First, we note that
$\bm{y}_{i}$ is more likely to be $0$ than $\bm{x}_{i}$.

$\displaystyle\operatorname{{Pr}}[\bm{y}_{i}=0]$
$\displaystyle=\frac{p_{i}^{k}\cdot
e^{-{p_{i}}}}{0!}=e^{-(p_{i})}\geq(1-p_{i})=\operatorname{{Pr}}[\bm{x}_{i}=0].$

Consider the following coupling: First draw
$\hat{\bm{y}}_{i}\sim\mathrm{Poi}(p_{i})$. If $\hat{\bm{y}_{i}}=0$, then with
probability
$(\operatorname{{Pr}}[\bm{x}_{i}=0])/(\operatorname{{Pr}}[\bm{y}_{i}=0])$, set
$\hat{\bm{x}_{i}}=0$ as well. Otherwise, set $\hat{\bm{x}_{i}}=1$. This
coupling meets all the criteria of 5.2 so
$\bm{x}_{i}\preceq_{\mathrm{cx}}\bm{y}_{i}$. ∎

Now, we are ready to prove Lemma 5.1.

###### Proof.

Let $\mathcal{A}$ be some $(F,m)$ discrete OCS. We construct a continuous OCS
$\mathcal{B}$ as before: Whenever $\mathcal{B}$ receives the probability
vector $p^{(j)}$, it sets $\bm{A}_{j}=\\{\bm{i}_{1},\ldots,\bm{i}_{m}\\}$
where each $\bm{i}_{\ell}$ is sampled iid from
$\mathrm{Categorical}(p^{(j)})$. It passes this multiset into $\mathcal{A}$,
and selects the same winner that $\mathcal{A}$ selected. By Definition 3, for
any disjoint consecutive sequences of time steps $S_{1},\ldots,S_{k}$,

$\displaystyle\operatorname{{Pr}}[i\text{ never selected in
$S_{1}\cup\ldots\cup
S_{k}$}]\leq\prod_{\ell=1}^{k}F(\textbf{count}_{i}(S_{\ell})).$

It will be helpful for us to pretend that the above actually holds with
equality. $\textbf{count}_{i}(S_{\ell})$ is a random variable defined as

$\displaystyle\textbf{count}_{i}(S_{\ell})=\sum_{j\in
S_{\ell}}(\bm{r}_{j}(i))\quad\quad\text{where $\bm{r}_{j}(i)$ is the
multiplicity of $i$ in $\bm{A}_{j}$}.$

Based on how we defined $\bm{A}_{j}$, we have that $\bm{r}_{j}(i)$ is the sum
of $m$ independent variables distributed according to
$\mathrm{Ber}((p^{(j)})_{i})$. Therefore, by Proposition 5.4,

$\displaystyle\textbf{count}_{i}(S_{\ell})\preceq_{\mathrm{cx}}\bm{k}_{\ell}\quad\quad\text{where
}\bm{k}_{\ell}\sim\mathrm{Poi}\left(m\cdot\sum_{j\in
S_{\ell}}(p^{(j)})_{i}\right).$

We are ready to show that $\mathcal{B}$ meets the requirements of Definition
11. First, we consider some consecutive $S=\\{j_{1},\ldots,j_{2}\\}$. Since
$F$ is convex,

$\displaystyle\operatorname{{Pr}}[i\text{ not selected in }S]$
$\displaystyle=\mathop{{\mathds{E}}\/}[F(\textbf{count}_{i}(S))]$
$\displaystyle\leq\mathop{{\mathds{E}}\/}[F(\bm{k})]\quad\quad\text{where
}\bm{k}\sim\mathrm{Poi}\left(m\cdot\sum_{j\in S}(p^{(j)})_{i}\right)$
($\textbf{count}_{i}(S)\preceq_{\mathrm{cx}}\bm{k}$)
$\displaystyle=f\left(\sum_{j\in S}(p^{(j)})_{i}\right)$ (Equation 7)

For the second requirement of Definition 11, consider any disjoint
$S_{1},S_{2}\subseteq\mathds{N}$ where every element of $S_{1}$ precedes every
element of $S_{2}$. Define $j^{\star}$ as in Definition 11. Then, the
probability $\bm{r}_{j^{\star}}(i)=0$ is at least $w=(1-m\cdot\sum_{j\in
G}(p^{(j)})_{i})$. If $\bm{r}_{j^{\star}}(i)=0$ then the probability $i$ is
selected in $S_{1}\cup S_{2}$ is the same as if the time step $j^{\star}$
didn’t exist (since $\mathcal{A}$ won’t see $i$ in it). Furthermore, since $F$
is log-concave, underestimating $w$ can only give a worse bound. Hence,
Equation 4 holds. ∎

In order to give a formal version of Theorem 1 we’ll need to know the
derivatives of $f$. There is a convenient relation between the _discrete
derivatives_ of $F$ and the _derivatives_ of $f$.

######  Lemma 5.5.

Choose any $F:\mathds{Z}_{\geq 0}\to\mathds{R}$, $m\in Z$ and let
$f:\mathds{R}_{\geq 0}\to\mathds{R}$ be

$\displaystyle
f(x)=\mathop{{\mathds{E}}\/}_{\bm{k}\sim\mathrm{Poi}(mx)}[F(\bm{k})].$

Then, for any $\ell\in\mathds{N}$ and $x\in\mathds{R}_{\geq 0}$, the
derivatives satisfy the relation

$\displaystyle
f^{(\ell)}(x)=m^{\ell}\cdot\mathop{{\mathds{E}}\/}_{\bm{k}\sim\mathrm{Poi}(mx)}[\Delta^{(\ell)}F(\bm{k})].$

###### Proof.

It is enough to prove the case where $\ell=1$, as larger $\ell$ follow by
induction. We expand

$\displaystyle f^{\prime}(x)$
$\displaystyle=\frac{d}{dx}\left(\sum_{k=0}^{\infty}\frac{e^{-mx}\cdot(mx)^{k}}{k!}\cdot
F(k)\right)$
$\displaystyle=\sum_{k=0}^{\infty}\left(\frac{d}{dx}e^{-mx}x^{k}\right)\cdot\frac{m^{k}\cdot
F(k)}{k!}$

We compute the derivative of the above coefficients.

$\displaystyle\frac{d}{dx}e^{-mx}x^{k}=\begin{cases}-me^{-mx}\cdot
x^{k}&k=0\\\ -me^{-mx}\cdot x^{k}+ke^{-mx}x^{k-1}&k\geq 1\end{cases}$

Therefore,

$\displaystyle f^{\prime}(x)$
$\displaystyle=-m\cdot\sum_{k=0}^{\infty}\frac{e^{-mx}\cdot(mx)^{k}}{k!}\cdot
F(k)+\sum_{k=1}^{\infty}\frac{ke^{-mx}(mx)^{k-1}\cdot m}{k!}\cdot F(k)$
$\displaystyle=m\cdot\left(-\sum_{k=0}^{\infty}\frac{e^{-mx}\cdot(mx)^{k}}{k!}\cdot
F(k)+\sum_{k=0}^{\infty}\frac{e^{-mx}(mx)^{k}\cdot m}{k!}\cdot F(k+1)\right)$
$\displaystyle=m\cdot\left(\sum_{k=0}^{\infty}\frac{e^{-mx}\cdot(mx)^{k}}{k!}\cdot(F(k+1)-F(k))\right)$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{k}\sim\mathrm{Poi}(mx)}[\Delta
F(\bm{k})],$

as desired. ∎

As a consequence we give the main theorem of this subsection. formal version
of Theorem 1

######  Theorem 6 (Formal version of Theorem 1).

For any $m\in\mathds{N}$ and convex $F:\mathds{Z}_{\geq 0}\to[0,1]$ where $F$
is log concave, $F(k)$ approaches $0$ as $k\to\infty$, and for any
$k_{1},k_{2}\in\mathds{Z}_{\geq 0}$,

$\displaystyle\Delta^{(3)}F(k_{1})\cdot\Delta F(k_{2})+\Delta
F(k_{1})\cdot\Delta^{(3)}F(k_{2})\leq
2\cdot\Delta^{(2)}F(k_{1})\cdot\Delta^{(2)}F(k_{2}).$ (8)

Let

$\displaystyle\Gamma\coloneqq
1-\sum_{n=0}^{\infty}\frac{m^{n}}{(m+1)^{n+1}}\cdot F(n),$ (9)

and suppose that

$\displaystyle m\leq\frac{-m\cdot\Delta F(0)-\Gamma}{\Gamma+(1-\Gamma)\cdot
m\cdot\Delta F(0)}.$ (10)

Then, if there an $(F,m)$-discrete OCS, there is an $\Gamma$-competitive
algorithm for edge-weighted online bipartite matching.

###### Proof.

Apply Lemma 5.1 to construct an $(f,m)$-continuous OCS for $f$ defined
Equation 7. We wish to apply Theorem 5 to that continuous OCS. If $F$ is
convex, then $f$ is convex by Lemma 5.5. We verify that if $f^{\prime}$ is
log-concave:

$\displaystyle f^{\prime\prime\prime}(x)\cdot
f^{\prime}(x)-(f^{\prime\prime}(x))^{2}=\mathop{{\mathds{E}}\/}_{\bm{k}_{1},\bm{k}_{2}\sim\mathrm{Poi}(mx)}\left[\Delta^{(3)}F(k_{1})\cdot\Delta
F(k_{2})-\Delta^{(2)}F(k_{1})\cdot\Delta^{(2)}F(k_{2})\right]\leq 0.$

Therefore, the desired result holds with

$\displaystyle\Gamma=1-\int_{0}^{\infty}e^{-t}\mathop{{\mathds{E}}\/}_{\bm{k}\sim\mathrm{Poi}(mt)}[F(\bm{k})]dt$

We just need to show the above simplifies to Equation 9.

$\displaystyle 1-\Gamma$
$\displaystyle=\int_{0}^{\infty}e^{-t}\sum_{k=0}^{\infty}\operatorname{{Pr}}[\mathrm{Poi}(m\cdot
t)=k]\cdot F(k)dt$
$\displaystyle=\int_{0}^{\infty}e^{-t}\sum_{k=0}^{\infty}\frac{e^{-mt}\cdot(mt)^{k}}{k!}\cdot
F(k)dt$
$\displaystyle=\sum_{k=0}^{\infty}\frac{m^{k}}{k!}F(k)\cdot\int_{0}^{\infty}e^{-(m+1)t}\cdot
t^{k}dt$
$\displaystyle=\sum_{k=0}^{\infty}\frac{m^{k}}{k!}F(k)\cdot\left(\frac{k!}{(m+1)^{k+1}}\right)$
$\displaystyle=\sum_{k=0}^{\infty}\frac{m^{k}}{(m+1)^{k+1}}\cdot F(k).$

Hence, Theorem 5 guarantees the same competitive ratio as in Theorem 6. ∎

######  Remark 2.

Equation 10 constrains how large $m$ can be (we should think of $m\cdot\Delta
F(0)$ as fixed; it is $-1$ in our constructions). For that reason, we are
forced to set $m\leq 6$ in order to achieve a competitive ratio of more than
$0.533$. Depending on the construction, the constraint in Equation 10 may not
be fully necessary. That constraint comes from the fact that in Lemma 5.1, the
continuous OCS is $(f,r)$-continuous for $r=m$. There may be tighter bounds
for $r$ that allow $m$ to be set significantly higher. For our constructions,
we believe that even in the case of $m\to\infty$, that $r$ approaches some
constant. Since Equation 9 is often increasing in $m$ (it is for various
constructions we tried), more tight analysis of $r$ coupled with larger $m$
could lead to an improved competitive ratio.

###  5.2 Proof of Theorems 2 and 4

We first prove the following more general result, and then use it for both
Theorems 2 and 4.

######  Lemma 5.6.

For any $m,k^{\star}\in\mathds{N}$, $c\in[0,1]$, and log-concave
$F:\mathds{Z}_{\geq 0}\to[0,1]$ where, for all $k\geq k_{\star}$,

$\displaystyle F(k)=F(k^{\star})\cdot(1-c)^{k-k^{\star}}.$ (11)

Suppose $\Delta^{2}F(k)\geq 0$ for all $k<k^{\star}$, that Equation 8 holds
for all $k_{1},k_{2}<k^{\star}$, and

$\displaystyle\Delta^{(3)}F(k)+2c\cdot\Delta^{(2)}F(k)+c^{2}\cdot\Delta
F(k)\geq 0.$ (12)

Let,

$\displaystyle\Gamma\coloneqq
1-\left(\sum_{n=0}^{k^{\star}-1}\frac{m^{n}}{(m+1)^{n+1}}\cdot
F(n)\right)-\left(\frac{m}{m+1}\right)^{k^{\star}}\cdot\frac{1}{1+m\cdot
c}\cdot F(k^{\star}),$ (13)

and suppose that

$\displaystyle m\leq\frac{-m\cdot\Delta F(0)-\Gamma}{\Gamma+(1-\Gamma)\cdot
m\cdot\Delta F(0)}.$ (14)

Then, if there an $(F,m)$-discrete OCS, there is an $\Gamma$-competitive
algorithm for edge-weighted online bipartite matching.

###### Proof.

To verify the conditions of Theorem 6, we need to compute the derivatives of
$F$ in the case where $k\geq k^{\star}$.

$\displaystyle\Delta^{(\ell)}F(k)=(-c)^{\ell}\cdot F(k)\quad\quad\text{for
}k\geq k^{\star}$

Therefore, the condition $\Delta^{(2)}F(k)\geq 0$ for $k<k^{\star}$ is enough
to guarantee that $F$ is convex.

We need to show Equation 8 holds in the case where exactly one of $k_{1}$ and
$k_{2}$ is at least $k^{\star}$ and in the case where both are at least
$k^{\star}$. In the case where $k_{1},k_{2}\geq k^{\star}$, Equation 8
simplifies to

$\displaystyle c^{4}\cdot F(k_{1})\cdot F(k_{2})+c^{4}\cdot F(k_{1})\cdot
F(k_{2})\leq 2c^{4}\cdot F(k_{1})\cdot F(k_{2})$

which is true with equality. Consider the other case, where exactly one of
$k_{1},k_{2}$ is less than $k^{\star}$. Without loss of generality, let it be
$k_{1}$. Then, Equation 8 is equivalent to

$\displaystyle-c\cdot\Delta^{(3)}F(k_{1})\cdot F(k_{2})-c^{3}\cdot\Delta
F(k_{1})\cdot F(k_{2})\leq 2c^{2}\cdot\Delta^{(2)}F(k_{1})\cdot F(k_{2})$

which is equivalent to Equation 12. Therefore, we can apply Theorem 6 to
determine the competitive ratio. First, we compute

$\displaystyle\sum_{n=k^{\star}}^{\infty}\frac{m^{n}}{(m+1)^{n+1}}\cdot F(n)$
$\displaystyle=\sum_{n=k^{\star}}^{\infty}\frac{m^{n}}{(m+1)^{n+1}}\cdot
F(k^{\star})\cdot(1-c)^{n-k^{\star}}$
$\displaystyle=\frac{\frac{m^{k^{\star}}}{(m+1)^{k^{\star}+1}}\cdot
F(k^{\star})}{1-\frac{m}{m+1}\cdot(1-c)}$
$\displaystyle=\left(\frac{m}{m+1}\right)^{k^{\star}}\cdot\frac{1}{(m+1)-m\cdot(1-c)}\cdot
F(k^{\star})$
$\displaystyle=\left(\frac{m}{m+1}\right)^{k^{\star}}\cdot\frac{1}{1+m\cdot
c}\cdot F(k^{\star})$

By Equation 9, the competitive ratio is,

$\displaystyle\Gamma$
$\displaystyle=1-\sum_{n=0}^{\infty}\frac{m^{n}}{(m+1)^{n+1}}\cdot F(n)$
$\displaystyle=1-\left(\sum_{n=0}^{k^{\star}-1}\frac{m^{n}}{(m+1)^{n+1}}\right)-\left(\frac{m}{m+1}\right)^{k^{\star}}\cdot\frac{1}{1+m\cdot
c}\cdot F(k^{\star}).$

∎

Next we prove the following theorem, restated for convenience.

See 2

###### Proof.

Recall that a $\gamma$-OCS is $(F,2)$-discrete OCS for $F$,

$\displaystyle F(k)\coloneqq 2^{-k}\cdot(1-\gamma)^{(k-1)_{+}}.$

$F$ has the form in Equation 11 for $k^{\star}=1$ and $c=\frac{1+\gamma}{2}$.
$F$ being log-concave is equivalent to $\frac{F(k+1)}{F(k)}$ decreasing, which
holds because that ratio is $\frac{1}{2}$ for $k=0$ and $1-c$ for $k\geq 1$.
We compute discrete derivatives for $k=0$:

$\displaystyle\Delta F(0)$ $\displaystyle=-\textstyle\frac{1}{2}$
$\displaystyle\Delta^{(2)}F(0)$ $\displaystyle=\frac{1-\gamma}{4}$
$\displaystyle\Delta^{(3)}F(0)$ $\displaystyle=\frac{\gamma^{2}+4\gamma-1}{8}$

The second derivative is positive for all $\gamma\in(0,1)$, so $F$ is convex.
We verify Equation 8 for all $k_{1},k_{2}<k^{\star}$. The only such case is
when $k_{1}=k_{2}=0$ in which case we need the following quantity to be
nonpositive.

$\displaystyle-2\cdot\frac{1}{2}\cdot\frac{\gamma^{2}+4\gamma-1}{8}-2\cdot\frac{1-\gamma}{4}=-\frac{\gamma^{2}+3}{8}\leq
0$

We verify Equation 12 for $k=0$

$\displaystyle\frac{\gamma^{2}+4\gamma-1}{8}+(1+\gamma)\cdot\frac{1-\gamma}{4}+\frac{(1+\gamma)^{2}}{4}\cdot(-\frac{1}{2})=\frac{\gamma(1-\gamma)}{4}\geq
0$

Then, we compute the competitive ratio.

$\displaystyle\Gamma$
$\displaystyle=1-\left(\sum_{n=0}^{k^{\star}-1}\frac{m^{n}}{(m+1)^{n+1}}\cdot
F(n)\right)-\left(\frac{m}{m+1}\right)^{k^{\star}}\cdot\frac{1}{1+m\cdot
c}\cdot F(k^{\star})$ $\displaystyle=1-\frac{1}{3}\cdot
1-\frac{2}{3}\cdot\frac{1}{2+\gamma}\cdot\frac{1}{2}$
$\displaystyle=\frac{3+2\gamma}{6+3\gamma}$

Lastly, we need to verify Equation 14. Since $\Delta
F(0)=-\textstyle\frac{1}{m}$, the upper bound on $m$ simplifies to

$\displaystyle\frac{1-\Gamma}{\Gamma-(1-\Gamma)}=\frac{1-\Gamma}{2\Gamma-1}$

This is a decreasing function of $\Gamma$. The largest possible value for
$\Gamma$ is $\frac{5}{9}$, corresponding to when $\gamma=1$. In the case, the
above simplifies to $4$. Since $m=2\leq 4$, Equation 14 holds. ∎

Theorem 4 is a consequence of Lemma 5.6 and the existence of an
$(F,6)$-discrete OCS for $F$ described in Figure 1. In a publicly available
Colab notebook111To see our code, go to
https://colab.research.google.com/drive/1mykkfnPj-
PuEV02GrOkLlnGFKromTkU1?usp=sharing, we verify that OCS has the properties
required by Lemma 5.6 and that the competitive ratio computed by Equation 13
is $\Gamma\geq 0.5368$.

$n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | $n\geq 10$
---|---|---|---|---|---|---|---|---|---|---|---
$F(n)$ | 1.0 | 0.833 | 0.677 | 0.54 | 0.426 | 0.333 | 0.260 | 0.201 | 0.156 | 0.121 | $0.093\cdot 0.773^{n-10}$
Figure 1: We prove the existence of an $(F,6)$-discrete OCS for the $F$
described in this table. The construction is given in Sections 7 and 8 with
the hyperparameter $p=0.48$.

##  6 Primal dual formulation

In this section, we prove Theorem 5. We begin with the standard primal linear
program for (offline) edge-weighted bipartite matching. Let $w_{ij}$ be the
weight of the edge between $i\in L$ to $j\in R$ where $w_{ij}=0$ indicate no
such edge exists and $x_{ij}$ be the probability that $(i,j)$ is the heaviest
edge matched to vertex $i$.

$\displaystyle\max\quad$ $\displaystyle\sum_{i\in L}\sum_{j\in R}w_{ij}x_{ij}$
$\displaystyle\mathrm{s.t.}\quad$ $\displaystyle\sum_{j\in R}x_{ij}\leq 1$
$\displaystyle\forall i\in L$ $\displaystyle\sum_{i\in L}x_{ij}\leq 1$
$\displaystyle\forall j\in R$ $\displaystyle x_{ij}\geq 0$
$\displaystyle\forall i\in L,j\in R$

This gives rise to a dual linear program.

$\displaystyle\min\quad$ $\displaystyle\sum_{i\in L}\alpha_{i}+\sum_{j\in
R}\beta_{j}$ $\displaystyle\mathrm{s.t.}\quad$
$\displaystyle\alpha_{i}+\beta_{j}\geq w_{ij}$ $\displaystyle\forall i\in
L,j\in R$ $\displaystyle\alpha_{i}\geq 0$ $\displaystyle\forall i\in L$
$\displaystyle\beta_{j}\geq 0$ $\displaystyle\forall j\in R$

We use $P$ to denote the primal objective and $D$ to denote the dual
objective. Our online algorithm will simultaneously maintain a matching for
the graph and a dual assignment that will meet the two criteria in the
following fact.

######  Fact 6.1 (Lemma 2 from [FHTZ20]).

Suppose an algorithm maintains primal and dual assignments such that, for some
$0\leq\Gamma\leq 1$, the following conditions hold at all time steps.

  1. 1.

_Approximate dual feasibility:_ For any $i\in L$ and $j\in R$

$\displaystyle\alpha_{i}+\beta_{j}\geq\Gamma\cdot w_{ij}$

  2. 2.

_Reverse weak duality:_ The objectives of the primal and dual assignments
satisfy $P\geq D$.

Then the algorithm is $\Gamma$-competitive.

Inspired by [DHK+16, FHTZ20], we do not directly maintain the primal variables
$x_{ij}$. Instead, for each $i\in L$ and weight-level $w\geq 0$, we define

$\displaystyle y_{i}(w)\coloneqq\operatorname{{Pr}}[i\text{ not matched to a
vertex of weight at least }w]$

In contrast, [DHK+16, FHTZ20] defines their $\overline{y_{i}(w)}$ to be
$\overline{y_{i}(w)}=1-y_{i}(w)$. We find our “reversed” definition simplifies
later analysis. The primal objective is then

$\displaystyle P=\int_{0}^{\infty}(1-y_{i}(w))dw$

Similarly, we introduce and maintain new variables $\alpha_{i}(w)$ for each
$i\in L$ and weight-level $w\geq 0$ and then set the value of $\alpha_{i}$ to

$\displaystyle\alpha_{i}=\int_{0}^{\infty}(\Gamma-\alpha_{i}(w))dw.$

Note that $y_{i}(w)$ and $\alpha_{i}(w)$ are both step functions with at most
one step per unique value $w_{ij},j\in R$. Hence, they can be stored in
polynomial time.

###  6.1 High level algorithmic overview

Fix some $(f,r)$-continuous OCS. At each time step $j\in[T]$, the value
$w_{ij}$ is revealed for all $i\in L$. As a function of these weights and the
state of the primal and dual variables, our algorithm will determine a
probability vector $p^{(j)}$ to pass into the OCS. The OCS then returns a
single winning vertex $i\in L$, which we match to vertex $j\in R$. Afterwards,
we update the primal variables accounting for the fact that the probability
$i$ is matched to a high weight vertex has increased. The quantity of this
update is directly controlled by the parameters of the OCS. Lastly, we update
the dual variables to maintain approximate dual feasibility and reverse weak
duality.

We wish to emphasize that the primal-dual algorithm does not actually “know”
which vertex $j$ is matched too. Instead, it only maintains the probability
that each $i$ is matched to a vertex at each weight-level. This separates the
algorithm into a deterministic component, the primal-dual formulation, and a
randomized component, the OCS.

The remainder of this section is divided as follows. In Section 6.2 and
Section 6.3, we define how the primal and dual variables respectively are
updated given $p^{(j)}$. In particular, $\beta_{j}$ is set to exactly the
minimum value so that approximate dual feasiblity holds. In Section 6.4 we
will discuss how $p^{(j)}$ is determined. In Section 6.5, we will prove that
reverse weak duality holds, completing the proof that our algorithm is
$\Gamma$-competitive.

Throughout this section, $f:\mathds{R}_{\geq 0}\to[0,1]$ and
$r\in\mathds{R}^{+}$ refer to the parameters of our OCS.

###  6.2 Primal updates

For each $i\in L$ and weight-level $w\geq 0$, we maintain two random variables
initialized as follows.

$\displaystyle\bm{x}_{i}(w)\overset{\mathrm{init}}{\longleftarrow}0\quad\text{with
probability $1$}$
$\displaystyle\bm{c}_{i}(w)\overset{\mathrm{init}}{\longleftarrow}1\quad\text{with
probability $1$}$

Our algorithm maintains the _distribution_ over
$(\bm{x}_{i}(w),\bm{c}_{i}(w))$ rather than just a single element of it. See
Remark 3 for the computational complexity of maintaining this distribution.

At time step $j$, our algorithm will pass a vector $p^{(j)}$ into the OCS.
After doing so, it updates, for each $w\leq w_{ij}$,

$\displaystyle\bm{x}_{i}(w)\leftarrow\bm{x}_{i}(w)+(p^{(j)})_{i}$

For each $w>w_{ij}$, with probability $1-(1-r\cdot(p^{(j)})_{i})_{+}$ we set

$\displaystyle\begin{split}\bm{c}_{i}(w)\leftarrow\bm{c}_{i}(w)\cdot
f(\bm{x}_{i}(w))\\\ \bm{x}_{i}(w)\leftarrow 0\end{split}$ (15)

Otherwise, we leave $\bm{c}_{i}(w)$ and $\bm{x}_{i}(w)$ unchanged. This is the
step that makes $\bm{c}_{i}(w)$ and $\bm{x}_{i}(w)$ random variables rather
than fixed.

At all steps, we maintain that

$\displaystyle y_{i}(w)=\operatorname{{\mathds{E}}}[\bm{c}_{i}(w)\cdot
f(\bm{x}_{i}(w))]$

Note that these updates correspond to Definition 11. For $S=\\{j\in
R|w_{ij}\geq w\\}$, that definition guarantees the probability that $i$ is not
matched to a vertex in $S$ is at most $y_{i}(w)$.

######  Remark 3.

The full support of $(\bm{x}_{i}(w),\bm{c}_{i}(w))$ can be exponentially
large, and so inefficient to maintain. However, our updates never need full
access to the distribution over $(\bm{x}_{i}(w),\bm{c}_{i}(w)$. It is
sufficient to maintain a distribution over the possible values of
$\bm{x}_{i}(w)$, and for each possible value for $\bm{x}_{i}(w)=x$, the
quantity $\mathop{{\mathds{E}}\/}[\bm{c}_{i}(w)\mid\bm{x}_{i}(w)=x]$. Since
there are only $|R|$ many possible values for $\bm{x}_{i}(w)$, that
information can be stored efficiently.

###  6.3 Dual updates

Our dual updates depend on some function $a:\mathds{R}_{\geq 0}\to[0,\Gamma]$
with the properties in the below Lemma.

######  Lemma 6.2.

Let $f:\mathds{R}_{\geq 0}\to[0,1]$ be thrice differentiable, convex, and have
a log concave derivative. For $r$ satisfying Equation 6 and $\Gamma$ defined
in Equation 5, there is some function $a:\mathds{R}_{\geq 0}\to[0,1]$ with the
following properties.

$\displaystyle a^{\prime}(x)=f^{\prime}(x)+a(x)$ $\displaystyle\forall x\geq
0$ (16) $\displaystyle a^{\prime}(x)\leq 0$ $\displaystyle\forall x,\text{
with equality only when $f(x)=0$}$ (17) $\displaystyle a(0)=\Gamma$ (18)
$\displaystyle f(x)\cdot a(0)=f(x)\cdot\Gamma\leq a(x)$ $\displaystyle\forall
x\geq 0$ (19) $\displaystyle r\leq\frac{\Gamma-a(x)}{a(x)-f(x)\cdot\Gamma}$
$\displaystyle\forall x\geq 0$ (20)

We prove Lemma 6.2 and give an analytical formula for the $a$ meeting the
above criteria in Section 6.6.

For any $i\in L$ and weight-level $w\geq 0$, we maintain that

$\displaystyle\alpha_{i}(w)=\mathop{{\mathds{E}}\/}\Big{[}\bm{c}_{i}(w)\cdot
a\big{(}\bm{x}_{i}(w)\big{)}\Big{]},$

where $\bm{c}_{i}(w),$ $\bm{x}_{i}(w)$ are the same as in the primal updates.
After $\alpha_{i}$ for is updated at time step $j$, we set $\beta_{j}$ to the
minimum value so that approximate dual feasibility holds. Specifically,

$\displaystyle\beta_{j}=\max\Big{(}0,\max_{i\in L}\,\Gamma\cdot
w_{ij}-\alpha_{i}\Big{)}$ (21)

For the above setting of $\beta_{j}$, dual feasibility will hold for $w_{ij}$
at time step $j$. It remains satisfied in future time steps as a consequence
of the following proposition.

######  Proposition 6.3 ($\alpha_{i}$ can only increase).

For each $i\in L$, and $w\geq 0$, the quantity $\alpha_{i}(w)$ can only
decrease as more online vertices arrive. As a consequence, for all $i\in L$,
$\alpha_{i}$ can only increase.

###### Proof.

Suppose that offline vertex $j$ arrives. First, consider the case where
$w_{ij}\geq w$. Then, each of the $\bm{x}_{i}(w)$ increase by $(p^{(j)})_{i}$.
Since $a$ is a decreasing function (Equation 17), $\alpha_{i}(w)$ can only
decrease.

Next, consider the case where $w_{ij}\geq w$. For each choice of
$(\bm{x}_{i}(w),\bm{c}_{i}(w))$, there is a chance that they become
$\bm{x}_{i}(w)^{\prime}=0$ and $\bm{c}_{i}(w)^{\prime}=\bm{c}_{i}(w)\cdot
f(\bm{x}_{i}(w))$. By Equation 19, this also can only decrease the value of
$\alpha_{i}(w)$ ∎

###  6.4 Determining the probability vector

At time step $j$, our algorithm receives $w_{ij}$ for all $i\in L$. It then
sets $p^{(j)}$ to a vector satisfying Lemma 6.4.

Note that, according to the above rule, $p^{(j)}$ can be set so that the sum
of the elements is less than $1$, but Definition 4 requires the sum of the
elements to be $1$. To remedy this, we just create a dummy vertex and assign
any excess probability to it.

######  Lemma 6.4.

It is always possible to choose $p^{(j)}$ so that, after the updates
corresponding to $p^{(j)}$,

$\displaystyle\beta_{j}=\sum_{i\in L}(p^{(j)})_{i}\cdot(\Gamma\cdot
w_{ij}-\alpha_{i})$ (22)

###### Proof.

Let $\alpha_{i}[p]$ denote the value that $\alpha_{i}$ would have if the
$i^{\mathrm{th}}$ element of $(p^{(j)})_{i}$ is $p$. We only use the fact that
$\alpha_{i}[p]$ is a continuous nondecreasing function of $p$ and strictly
increasing at any $p$ for which $\Gamma\cdot w_{ij}-\alpha_{i}[p]>0$. This is
guaranteed by Proposition 6.3 and the fact that Equation 17 holds with
equality only when $f(x)=0$.

According to Equation 21, after choosing $p^{(j)}$, we’ll set $\beta_{j}$ to

$\displaystyle\beta_{j}=\max\Big{(}0,\max_{i\in L}\,\Gamma\cdot
w_{ij}-\alpha_{i}[(p^{(j)})_{i}]\Big{)}.$

For each $i\in L$, we have an lower bound on $\beta_{j}$, and we set
$\beta_{j}$ to the smallest nonnegative number satisfying all of these lower
bounds. Roughly speaking, we’ll set $p^{(j)}$ so that as many of these lower
bounds are equal to $\beta_{j}$ as possible.

For each choice of $\beta_{j}=\beta$, $\beta\geq 0$, define $p_{i}[\beta]$ to
the minimum value for $p$ such that $\Gamma\cdot w_{ij}-\alpha_{i}[p]=\beta$.
We set $p_{i}[\beta]$ to $0$ if $\Gamma\cdot w_{ij}-\alpha_{i}[0]<\beta$ and
we set $p_{i}[\beta]$ to $\infty$ if no matter how large we make $p$,
$\Gamma\cdot w_{ij}-\alpha_{i}[p]>\beta$ (this can only occur for $\beta=0$).
Since $\alpha_{i}[p]$ is continuous and decreasing, these are the only cases.
Furthermore, $p_{i}[\beta]$ is a decreasing function of $\beta$ and is
continuous for all $\beta\geq 0$ since $\alpha_{i}[p]$ is strictly decreasing
at any $p$ for which $\Gamma\cdot w_{ij}-\alpha_{i}[p]>0$.

First consider the case where $\sum_{i\in L}p_{i}[0]\leq 1$. In this case, set
$(p^{(j)})_{i}=p_{i}[0]$ for each $i\in L$ and $\beta_{j}=0$. Equation 22
holds since both sides are equal to $0$.

Otherwise, we have $\sum_{i\in L}p_{i}[0]>1$. In the limit of
$\beta\to\infty$, we have that $\sum_{i\in L}p_{i}[\beta]=0$. By the
intermediate value theorem, there is some choice $\beta^{\star}$ such that
$\sum_{i\in L}p_{i}[\beta]=1$. We set $\beta_{j}=\beta^{\star}$ and
$(p^{(j)})_{i}=p_{i}[\beta^{\star}]$. By the continuity of $\alpha_{i}[p]$, we
have that

$\displaystyle(p^{(j)})_{i}>0\implies\Gamma\cdot
w_{ij}-\alpha_{i}[p^{(j)}_{i}]=\beta^{\star}.$ (23)

Finally, we show the desired result.

$\displaystyle\sum_{i\in L}(p^{(j)})_{i}\cdot(\Gamma\cdot w_{ij}-\alpha_{i})$
$\displaystyle=\sum_{i\in L}p_{i}[\beta^{\star}]\cdot(\Gamma\cdot
w_{ij}-\alpha_{i}[p_{i}[\beta_{j}]])$ $\displaystyle=\sum_{i\in
L}p_{i}[\beta^{\star}]\cdot\beta^{\star}$ (Equation 23)
$\displaystyle=\left(\sum_{i\in
L}p_{i}[\beta^{\star}]\right)\cdot\beta^{\star}$
$\displaystyle=1\cdot\beta^{\star}=\beta_{j}.$

∎

###  6.5 Reverse weak duality

Since we already have that approximate dual feasibility holds, we only need to
prove that reverse weak duality holds to prove that our algorithm is
$\Gamma$-competitive. At the start of our algorithm we have that $P=D=0$. Let
$\Delta_{j}P$ and $\Delta_{j}D$ be the amount the primal and dual respectively
increase after the update corresponding to $j\in R$. We will prove that
$\Delta_{j}P\geq\Delta_{j}D$ which guarantees reverse weak duality holds.

######  Lemma 6.5.

For any $j\in R$, if $p^{(j)}$ is set as in Lemma 6.4, then
$\Delta_{j}P\geq\Delta_{j}D$.

###### Proof.

For each primal and dual variable, with use a superscript of (j) to refer to
its value after the $j^{\mathrm{th}}$ update. Similarly, a superscript of
(j-1) refers to its value before the update. For any variable $\mathrm{var}$,
we use the shorthand $\Delta_{j}\mathrm{var}$ to refer
$\mathrm{var}^{(j)}-\mathrm{var}^{(j-1)}$.

$\displaystyle\Delta_{j}P-\Delta_{j}D$ $\displaystyle=\left(-\sum_{i\in
L}\int_{0}^{\infty}\Delta_{j}y_{i}(w)dw\right)-\left(-\sum_{i\in
L}\int_{0}^{\infty}\Delta_{j}\alpha_{i}(w)dw+\beta_{j}\right)$
$\displaystyle=\sum_{i\in
L}\left(-\int_{0}^{\infty}(\Delta_{j}y_{i}(w)-\Delta_{j}\alpha_{i}(w))dw\right)-\left(\sum_{i\in
L}(p^{(j)})_{i}\cdot(\Gamma\cdot w_{ij}-\alpha_{i}^{(j)})\right)$

Recall that $\alpha_{i}=\int_{0}^{\infty}(\Gamma-\alpha_{i}(w))dw$. Therefore,

$\displaystyle\Gamma\cdot w_{ij}-\alpha_{i}^{(j)}$
$\displaystyle=\left(\int_{0}^{w_{ij}}\Gamma\cdot
dw\right)-\left(\int_{0}^{\infty}(\Gamma-\alpha_{i}^{(j)}(w))dw\right)$
$\displaystyle=\left(\int_{0}^{w_{ij}}\alpha_{i}^{(j)}(w)dw\right)-\left(\int_{w_{ij}}^{\infty}(\Gamma-\alpha_{i}^{(j)}(w))dw\right)$

Combining the above equations, we have that

$\displaystyle\Delta_{j}P-\Delta_{j}D=$ $\displaystyle\sum_{i\in
L}\left(\int_{0}^{w_{ij}}\left(-\Delta_{j}y_{i}(w)+\Delta_{j}\alpha_{i}(w)-(p^{(j)})_{i}\cdot\alpha_{i}^{(j)}(w)\right)dw\right)$
$\displaystyle+$ $\displaystyle\sum_{i\in
L}\left(\int_{w_{ij}}^{\infty}\left(-\Delta_{j}y_{i}(w)+\Delta_{j}\alpha_{i}(w)+(p^{(j)})_{i}\cdot\big{(}\Gamma-\alpha_{i}^{(j)}(w)\big{)}\right)dw\right)$

We will show that for any choice of $w\geq 0$ and $i\in L$, the corresponding
term in the above equation is positive. This implies that
$\Delta_{j}P-\Delta_{j}D$ is also positive.

Case 1: $w\leq w_{ij}$. We wish to show that
$-\Delta_{j}y_{i}(w)+\Delta_{j}\alpha_{i}(w)-(p^{(j)})_{i}\cdot\alpha_{i}^{(j)}(w)\geq
0$. We expand each term separately.

$\displaystyle\Delta_{j}y_{i}(w)$
$\displaystyle=y_{i}^{(j)}(w)-y_{i}^{(j-1)}(w)$
$\displaystyle=\mathop{{\mathds{E}}\/}\left[\bm{c}_{i}^{(j)}(w)\cdot(f(\bm{x}_{i}^{(j)}(w)-f(\bm{x}_{i}^{(j)}(w)-(p^{(j)})_{i}))\right]$
$\displaystyle=\mathop{{\mathds{E}}\/}\left[\int_{\bm{x}_{i}^{(j)}(w)-(p^{(j)})_{i}}^{\bm{x}_{i}^{(j)}(w)}\bm{c}_{i}^{(j)}(w)\cdot
f^{\prime}(x)dx\right]$

Similarly,

$\displaystyle\Delta_{j}\alpha_{i}(w)$
$\displaystyle=\alpha_{i}^{(j)}(w)-\alpha_{i}^{(j-1)}(w)$
$\displaystyle=\mathop{{\mathds{E}}\/}\left[\bm{c}_{i}^{(j)}(w)\cdot(a(\bm{x}_{i}^{(j)}(w)-a(\bm{x}_{i}^{(j)}(w)-(p^{(j)})_{i}))\right]$
$\displaystyle=\mathop{{\mathds{E}}\/}\left[\int_{\bm{x}_{i}^{(j)}(w)-(p^{(j)})_{i}}^{\bm{x}_{i}^{(j)}(w)}\bm{c}_{i}^{(j)}(w)\cdot
a^{\prime}(x)dx\right]$

Finally,

$\displaystyle(p^{(j)})_{i}\cdot\alpha_{i}^{(j)}(w)$
$\displaystyle=(p^{(j)})_{i}\cdot\mathop{{\mathds{E}}\/}\left[\bm{c}_{i}^{(j)}(w)\cdot
a(\bm{x}_{i}^{(j)}(w))\right]$
$\displaystyle=\int_{\bm{x}_{i}^{(j)}(w)-(p^{(j)})_{i}}^{\bm{x}_{i}^{(j)}(w)}\mathop{{\mathds{E}}\/}\left[\bm{c}_{i}^{(j)}(w)\cdot
a(\bm{x}_{i}^{(j)}(w))\right]dx$
$\displaystyle=\mathop{{\mathds{E}}\/}\left[\int_{\bm{x}_{i}^{(j)}(w)-(p^{(j)})_{i}}^{\bm{x}_{i}^{(j)}(w)}\bm{c}_{i}^{(j)}(w)\cdot
a(\bm{x}_{i}^{(j)}(w))dx\right]$

Comparing the above three equations, it is enough to show that for any
$x<x_{i}^{(j)}(w)$, that $-f^{\prime}(x)+a^{\prime}(x)-a(x_{i}^{(j)})\geq 0$.
We do just that

$\displaystyle-f^{\prime}(x)+a^{\prime}(x)-a(x_{i}^{(j)})$
$\displaystyle\geq-f^{\prime}(x)+a^{\prime}(x)-a(x)$ ($a$ is decreasing)
$\displaystyle=0$ (Equation 16)

This completes the first case.

Case 2: $w>w_{ij}$. We wish to show that
$-\Delta_{j}y_{i}(w)+\Delta_{j}\alpha_{i}(w)+(p^{(j)})_{i}\cdot\big{(}\Gamma-\alpha_{i}^{(j)}(w)\big{)}\geq
0$. For $w>w_{ij}$, $y_{i}(w)$ does not change. Hence, we only need to expand
the other two terms. Recall that, for $w\geq w_{ij}$, we set
$\bm{c}_{i}(w)\leftarrow\bm{c}_{i}(w)\cdot f(\bm{x}_{i}(w))$ and
$\bm{x}_{i}(w)\leftarrow 0$ with probability $\min(r\cdot(p^{(j)})_{i},1)$.
Otherwise, we leave the parameters unchanged. Expanding,

$\displaystyle\Delta_{j}\alpha_{i}(w)=\mathop{{\mathds{E}}\/}\left[\min(r\cdot(p^{(j)})_{i},1)\cdot\bm{c}_{i}^{(j-1)}(w)\cdot\big{(}f(\bm{x}_{i}^{(j-1)}(w))\cdot
a(0)-a(\bm{x}_{i}^{(j-1)}(w))\big{)}\right]$

Recall from Equation 19 that $f(x)\cdot a(0)\leq a(x)$ for all $x\geq 0$.
Therefore, we may replace the $\min(r\cdot(p^{(j)})_{i},1)$ factor in the
above equation and bound.

$\displaystyle\Delta_{j}\alpha_{i}(w)\geq\mathop{{\mathds{E}}\/}\left[r\cdot(p^{(j)})_{i}\cdot\bm{c}_{i}^{(j-1)}(w)\cdot\big{(}f(\bm{x}_{i}^{(j-1)}(w))\cdot
a(0)-a(\bm{x}_{i}^{(j-1)}(w))\big{)}\right]$

Using the fact that $\alpha_{i}^{(j)}(w)\leq\alpha_{i}^{(j-1)}(w)$
(Proposition 6.3), we expand the other term of our desired inequality.

$\displaystyle(p^{(j)})_{i}\cdot\big{(}\Gamma-\alpha_{i}^{(j)}(w)\big{)}$
$\displaystyle\geq(p^{(j)})_{i}\cdot\big{(}\Gamma-\alpha_{i}^{(j-1)}(w)\big{)}$
$\displaystyle=(p^{(j)})_{i}\cdot\mathop{{\mathds{E}}\/}\left[\Gamma-\bm{c}_{i}^{(j-1)}(w)\cdot
a(\bm{x}_{i}^{(j-1)}(w))\right]$

Our desired inequality then holds as long as, for all $x\geq 0$

$\displaystyle r\cdot(f(x)\cdot a(0)-a(x))+(\Gamma-a(x))\geq 0$

which is equivalent to Equation 20. This completes the proof of the second
case and reverse weak duality. ∎

###  6.6 Existence of good $a$

See 6.2

###### Proof.

We define $a$ as

$\displaystyle a(x)\coloneqq f(x)-\int_{0}^{\infty}e^{-t}f(t+x)dt.$ (24)

First, we verify Equation 16 holds.

$\displaystyle a^{\prime}(x)$
$\displaystyle=f^{\prime}(x)-\int_{0}^{\infty}e^{-t}f^{\prime}(t+x)$
$\displaystyle a^{\prime}(x)$
$\displaystyle=f^{\prime}(x)-\left(\bigg{[}e^{-t}f(t+x)\bigg{]}_{t=0}^{t=\infty}+\int_{0}^{\infty}e^{-t}f(t+x)\right)$
(integration by parts) $\displaystyle a^{\prime}(x)$
$\displaystyle=f^{\prime}(x)-\left(-f(x)+\int_{0}^{\infty}e^{-t}f(t+x)\right)$
$\displaystyle=f^{\prime}(x)+a(x).$

Next, we verify Equation 17 using the fact that $f$ is convex.

$\displaystyle a^{\prime}(x)$
$\displaystyle=f^{\prime}(x)-\int_{0}^{\infty}e^{-t}f^{\prime}(t+x)$
$\displaystyle\leq f^{\prime}(x)-\int_{0}^{\infty}e^{-t}f^{\prime}(x)$ ($f$ is
convex) $\displaystyle=0$

Hence, $a^{\prime}(x)\leq 0$ always holds. Furthermore, if $f(x)>0$, it must
be the case $f^{\prime}(x)<0$ since $f$ approaches $0$ and is convex. It
follows that for sufficiently large $t$, $f^{\prime}(t+x)>f^{\prime}(x)$.
Otherwise, $f$ won’t be bounded. Hence, the inequality above is strict in the
case where $f(x)\neq 0$, and so Equation 17 holds.

Equation 18 holds directly by the definition $a$ in Equation 24 and of
$\Gamma$ in Equation 5.

Lastly, we’ll prove Equation 20 and show that it implies Equation 19. We wish
to show the following function is increasing in $x$,

$\displaystyle h(x)\coloneqq\frac{\Gamma-a(x)}{a(x)-f(x)\cdot\Gamma}.$

Let us define $A(x)=\frac{a(x)}{\Gamma}$. Then

$\displaystyle h(x)=\frac{1-A(x)}{A(x)-f(x)}=\frac{1-A(x)}{(1-f(x))-(1-A(x))}$

Inverting the above,

$\displaystyle h(x)$
$\displaystyle=\left(\frac{(1-f(x))-(1-A(x))}{(1-A(x))}\right)^{-1}$
$\displaystyle=\left(\frac{(1-f(x))}{(1-A(x))}-1\right)^{-1}$
$\displaystyle=\left(\frac{\int_{0}^{x}f^{\prime}(t)dt}{\int_{0}^{x}A^{\prime}(t)dt}-1\right)^{-1}$
(f(0) = A(0) = 1)

In order to prove that $h(x)$ is increasing, we need $h(x)^{-1}$ to be
decreasing. First, we prove that the quantity
$\frac{f^{\prime}(x)}{A^{\prime}(x)}$ is decreasing:

$\displaystyle\frac{f^{\prime}(x)}{A^{\prime}(x)}$
$\displaystyle=\Gamma\cdot\frac{f^{\prime}(x)}{a^{\prime}(x)}$
$\displaystyle=\Gamma\cdot\frac{f^{\prime}(x)}{f^{\prime}(x)-\int_{0}^{\infty}e^{-t}f^{\prime}(t+x)dt}$
(Equation 16)
$\displaystyle=\Gamma\cdot\left(\frac{f^{\prime}(x)-\int_{0}^{\infty}e^{-t}f^{\prime}(t+x)dt}{f^{\prime}(x)}\right)^{-1}$
$\displaystyle=\Gamma\cdot\left(1-\int_{0}^{\infty}\frac{e^{-t}f^{\prime}(t+x)}{f^{\prime}(x)}dt\right)^{-1}$

We’ll next prove that for any $t\geq 0$, the quantity
$\textstyle\frac{f^{\prime}(t+x)}{f^{\prime}(x)}$ is decreasing in $x$, which
will imply that $\frac{f^{\prime}(x)}{A^{\prime}(x)}$ is decreasing. Here,
we’ll use the fact that $f^{\prime}$ is log concave. This means that

$\displaystyle\frac{f^{\prime\prime}(x)}{f^{\prime}(x)}\quad\quad\text{is
decreasing in $x$}.$

The quantity $\frac{f^{\prime}(t+x)}{f^{\prime}(x)}$ is decreasing iff
$\frac{f^{\prime\prime}(t+x)}{f^{\prime}(t+x)}<\frac{f^{\prime\prime}(x)}{f^{\prime}(x)}$,
exactly what is guaranteed by the above equation. Hence.
$\frac{f^{\prime}(x)}{A^{\prime}(x)}$ is decreasing. Finally, we confirm that
$h(x)$ is increasing by showing the following quantity is decreasing. Consider
any $x_{1}<x_{2}$. Then,

$\displaystyle\frac{\int_{0}^{x_{2}}f^{\prime}(t)dt}{\int_{0}^{x_{2}}A^{\prime}(t)dt}$
$\displaystyle=\frac{\int_{0}^{x_{2}}\textstyle\frac{f^{\prime}(t)}{A^{\prime}(t)}\cdot
A^{\prime}(t)dt}{\int_{0}^{x_{2}}A^{\prime}(t)dt}$
$\displaystyle=\frac{\int_{0}^{x_{1}}\textstyle\frac{f^{\prime}(t)}{A^{\prime}(t)}\cdot
A^{\prime}(t)dt+\int_{x_{1}}^{x_{2}}\textstyle\frac{f^{\prime}(t)}{A^{\prime}(t)}\cdot
A^{\prime}(t)dt}{\int_{0}^{x_{1}}A^{\prime}(t)dt+\int_{x_{1}}^{x_{2}}A^{\prime}(t)dt}$

For any $a,b,c,d$ all nonnegative, $\frac{a+b}{c+d}$ is between $\frac{a}{c}$
and $\frac{b}{d}$. Since $f^{\prime}(t)/A^{\prime}(t)$ is decreasing, it
follows that

$\displaystyle\frac{\int_{x_{1}}^{x_{2}}\textstyle\frac{f^{\prime}(t)}{A^{\prime}(t)}}{\int_{x_{1}}^{x_{2}}A^{\prime}(t)dt}<\frac{\int_{0}^{x_{1}}\textstyle\frac{f^{\prime}(t)}{A^{\prime}(t)}}{\int_{0}^{x_{1}}A^{\prime}(t)dt}$

and therefore that $h^{\prime}(x)$ is decreasing, proving that $h(x)$ is
increasing. This means that $h(x)$ is minimized in the limit of $x\to 0$, and
so

$\displaystyle h(x)\geq\lim_{x\to 0}h(x)$
$\displaystyle=\frac{-a^{\prime}(0)}{a^{\prime}(0)-f^{\prime}(0)\cdot\Gamma}$
(L’ Hôpital’s rule)
$\displaystyle=\frac{-(f^{\prime}(0)+a(0))}{f^{\prime}(0)+a(0)-f^{\prime}(0)\cdot\Gamma}$
(Equation 16)
$\displaystyle=\frac{-f^{\prime}(0)-\Gamma}{\Gamma+(1-\Gamma)\cdot
f^{\prime}(0)}$ (Equation 18) $\displaystyle\geq r$ (Equation 6)

Therefore, Equation 20 holds. Equation 19 is then a consequence of the fact
that $r\geq 0$ and $\Gamma-a(x)\geq 0$ since $a(x)$ is decreasing. ∎

##  7 Meta algorithm for constructing multiway OCSes

We give a general algorithm for constructing $m$-discrete OCSes that whose
performance depends on the quality of a “win distribution,” $\mathcal{W}$,
over $[0,1]^{\mathds{N}}$. A sample from $\mathcal{W}$ is a sequence of
probabilities, $\bm{x}_{1},\bm{x}_{2},\ldots$. During initialization, our
algorithm draws an independent “win sequence”,
$\bm{x}_{1}(i),\bm{x}_{2}(i),\ldots$ for each $i\in L$. Our OCS also stores an
index within the win distribution, $k(i)$ for each $i\in L$ that is
initialized to $k_{i}=1$.

At each time step, the OCS receives $A_{j}=\\{i_{1},\ldots,i_{m}\\}$. For each
$i\in A_{j}$, it determines the “desired win probability” of $i$ in this time
step. In the case where $i$ appears exactly once in $A_{j}$, this desired win
probability is exactly equal to $\bm{x}_{k(i)}(i)$. When $i$ appears $r\geq 2$
times in $A_{j}$, the desired win probability is the probability $i$ would win
in at least one of the next $r$ round if it appeared only once in each. Then,
a tournament algorithm takes in these desired win probabilities and selects a
single winner for the round and $k(i)$ is incremented. We include pseudocode
for our meta algorithm in Figure 2, though defer description of the win
distribution and tournament subroutine for later.

$\mathrm{OCS}_{\mathcal{W},\mathcal{T}}$ 1. Initialization: For each $i\in L$,
independently draw a $\bm{x}(i)\sim\mathcal{W}$ and initialize an index
$k_{1}(i)\leftarrow 1$ 2. Upon receiving $A_{j}=\\{i_{1},\ldots,i_{m}\\}$ (a)
Determine desired win probabilities: For each $i\in A_{j}$, let $r_{j}(i)$ be
it’s multiplicity in $A_{j}$. Compute the desired win probability
$\displaystyle\bm{w}_{j}(i)\coloneqq
1-\prod_{\ell=0}^{r_{j}(i)-1}\left(1-\bm{x}_{k_{j}(i)+\ell}\right)$ (25) (b)
Choose a winner: Use a (possibly randomized) tournament subroutine,
$\mathcal{T}$, to select a single $i\in A_{j}$ as winner. This winner depends
on the values of $\bm{w}_{j}(i)$ for each $i\in A_{j}$. (c) Increment
counters: For each $i\in L$, increment $k_{j+1}(i)\leftarrow
k_{j}(i)+r_{j}(i)$ Figure 2: Our meta algorithm for constructing OCSes as a
function of a win distribution, $\mathcal{W}$ and tournament subroutine
$\mathcal{T}$

The fact that the desired win probabilities of different vertices are
_independent_ makes analysis tractable. To achieve a competitive ratio better
than $0.5$, we need the winners of our OCS to be negatively correlated. We
achieve this by making the random variables in the sequence returned by the
$\mathcal{W}$ negatively correlated. This way, if $i$ has a small chance of
winning in a particular round, it has a larger chance of winning in other
rounds. In particular, we need two types of negative correlation for
$\bm{x}_{1},\bm{x}_{2},\ldots\sim\mathcal{W}$.

  1. 1.

A _qualitative_ and _long-distanced_ negative correlation. We need to ensure
there doesn’t exist any positive correlation between $\bm{w}_{k_{1}}$ and
$\bm{w}_{k_{2}}$ even for $k_{1}$ and $k_{2}$ far apart. We prove that our win
probabilities satisfy a generalization of negatively correlated random
variables called _negative association_.

######  Definition 12 (Negative association [JDP83]).

Random variables $\bm{x}_{1},\bm{x}_{2},\ldots,\bm{x}_{n}$ are said to be
_negatively associated_ if, for every pair of disjoint subsets
$A_{1},A_{2}\subseteq[n]$ and increasing functions $f_{1},f_{2}$,

$\displaystyle\operatorname{{Cov}}[f_{1}(\bm{x}_{A_{1}}),f_{2}(\bm{x}_{A_{2}})]\leq
0$

where $\bm{x}_{A}$ is the vector
$(\bm{x}_{i_{1}},\bm{x}_{i_{2}},\ldots,\bm{x}_{i_{|A|}})$ when
$A=\\{i_{1},i_{2},\ldots,i_{|A|}\\}$.

Proving this ends up being essential to showing our OCS has _any_ guarantees,
even those matching the trivial fully independent OCS.

  2. 2.

A _quantitative_ and _short-distanced_ negative correlation. We want the
values of $\bm{w}_{j}$, $\bm{w}_{j+1}$, and other nearby time steps, to be
strongly negatively correlated. The magnitude of this negative correlation
directly ties into the probability that $i$ is selected in consecutive time
steps and therefore the quality of our OCS.

We prove a meta theorem on the quality of the algorithm in Figure 2 as a
function of the win distribution.

######  Theorem 7 (Quality of our meta algorithm).

Let $\mathcal{W}$ be a win-distribution with the following three properties.

  1. 1.

Negatively associated: For any $n\geq 1$ and $\bm{x}\sim\mathcal{W}$, the
variables $\bm{x}_{1},\ldots,\bm{x}_{n}$ are negative associated.

  2. 2.

Shift-invariant: For any $n\geq 1$ and $\bm{x}\sim\mathcal{W}$, the
distribution of $\bm{x}_{1},\bm{x}_{2},\ldots$ is identical to that of
$\bm{x}_{n},\bm{x}_{n+1},\ldots$.

  3. 3.

Sufficiently small: For each $r\in[m-1]$ and $t\in[0,1]$, defining
$\bm{w}^{(r)}$ to be the random variable indicating the distribution of
desired win probability of a vertex of multiplicity $r$,

$\displaystyle\bm{w}^{(r)}\sim\left(1-\prod_{\ell=1}^{r}\left(1-\bm{x}_{\ell}\right)\right)\quad\quad\text{where}\quad\quad\bm{x}\sim\mathcal{W},$

the following holds

$\displaystyle\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{W}}\left[\left(\bm{w}^{(r)}-t\right)_{+}\right]\leq
1-t-\frac{m-r}{m}\cdot\left(1-t^{\frac{m}{m-r}}\right)$ (26)

where $(z)_{+}$ is short hand for $\max(z,0)$.

Then, there exists some tournament subroutine $\mathcal{T}$ for which
$\mathrm{OCS}_{\mathcal{W},\mathcal{T}}$ is a $(f,m)$-discrete OCS for

$\displaystyle
F(n)\coloneqq\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{W}}\left[\prod_{\ell=1}^{n}(1-\bm{x}_{\ell})\right].$
(27)

The three criteria of Theorem 7 are desirable for intuitive reasons. Let
$S_{1},\ldots,S_{k}$ be disjoints set of time steps. Negative association
ensures that,

$\displaystyle\operatorname{{Pr}}[i\text{ never selected in
}\bigcup_{\ell=1}^{k}S_{\ell}]\leq\prod_{\ell=1}^{k}\operatorname{{Pr}}[i\text{
never selected in }S_{\ell}].$

Shift-invariance ensures that the probability that $i$ is not selected in a
set of $n$ consecutive appearances is independent of whether those are the
first appearances for $i$, or whether they occur later in the algorithm.
Finally, $\bm{w}^{(r)}$ being sufficiently small ensures that it’s possible
for a tournament algorithm to guarantee that the probability $i$ wins a round
with desired win probability $w$ is at least $w$.

We break the proof of Theorem 7 into two steps: In Lemma 7.1 we assuming the
existence of a tournament subroutine with some desirable properties. Then, in
Lemma 7.12, we prove the existence of such a tournament subroutine as long as
the win distribution is sufficiently small.

###  7.1 Proof of Theorem 7 assuming a good tournament subroutine

We prove the following Lemma.

######  Lemma 7.1.

Let $\mathcal{W}$ be a win-distribution with the following properties.

  1. 1.

Negatively associated: For any $n\geq 1$ and $\bm{x}\sim\mathcal{W}$, the
variables $\bm{x}_{1},\ldots,\bm{x}_{n}$ are negative associated.

  2. 2.

Shift-invariant: For any $n\geq 1$ and $\bm{x}\sim\mathcal{W}$, the
distribution of $\bm{x}_{1},\bm{x}_{2},\ldots$ is identical to that of
$\bm{x}_{n},\bm{x}_{n+1},\ldots$.

Let $\mathcal{T}$ be a tournament subroutine with the following properties.

  1. 1.

Consistent: For each $w\in[0,1]$, the probability $i$ wins round $j$ given
that $\bm{w}_{j}(i)=w$ is at least $w$.

  2. 2.

Stochastic ordering: The probability $i$ wins a round is a stochastically
increasing function of $\bm{w}_{j}(i)$ and a stochastically decreasing
function of $\bm{w}_{j}(i^{\prime})$ for each $i^{\prime}\neq i$.

Then, $\mathrm{OCS}_{\mathcal{W},\mathcal{T}}$ is a $(F,m)$-discrete OCS for

$\displaystyle
F(n)\coloneqq\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{D}}\left[\prod_{\ell=1}^{n}(1-\bm{x}_{\ell})\right].$

We’ll need a variety of desirable properties satisfied by negatively
associated variables. All of the below facts have short proofs (see [JDP83]).

######  Fact 7.2.

If $\bm{x}_{1},\ldots,\bm{x}_{n}$ are independent, then they are negatively
associated.

######  Fact 7.3.

The union of independent sets of negatively associated random variables is
also negatively associated.

######  Fact 7.4.

Any subset of a set of negatively associated variables is also negatively
associated.

######  Fact 7.5.

Increasing functions defined on disjoint subsets of negatively associated
random variables are also negatively associated.

Next, we prove an analogue of 7.5 for stochastically increasing functions.

######  Proposition 7.6.

Stochastically increasing functions defined on disjoint subsets of negatively
associated random variables are also negatively associated.

###### Proof.

Let $\bm{x}=\bm{x}_{1},\ldots,\bm{x}_{n}$ be negatively associated,
$A_{1},\ldots,A_{m}\subseteq[n]$ disjoint subsets, and
${\bm{f}}_{1},\ldots,{\bm{f}}_{m}$ stochastically increasing functions. We
draw $\bm{y}_{1},\ldots,\bm{y}_{m}\overset{iid}{\sim}\mathrm{Uniform}(0,1)$.
By 7.2 and 7.3, the set
$(\bm{x}_{1},\ldots,\bm{x}_{n},\bm{y}_{1},\ldots,\bm{y}_{m})$ is together
negatively associated. Then, we define $\bm{z}_{i}$ for each $i\in M$ as,

$\displaystyle\bm{z}_{i}=\text{min $v$ such that
}\operatorname{{Pr}}[{\bm{f}}_{i}(\bm{x}_{A_{i}})\leq v]\geq\bm{y}_{i}$

Then the distribution of $\bm{z}_{i}$ is equivalent to that of
${\bm{f}}_{i}(\bm{x}_{A_{i}})$. Furthermore, since ${\bm{f}}_{i}$ is
stochastically increasing, $\bm{z}_{i}$ is an increasing function of
$\bm{x}_{A_{i}}$ and $\bm{y}_{i}$. By 7.5, $\bm{z}_{1},\ldots,\bm{z}_{m}$ are
negatively associated. ∎

As a quick corollary of the above,

######  Corollary 7.7.

Let $\bm{x}=\bm{x}_{1},\ldots,\bm{x}_{n}$ be negatively associated. For any
stochastically increasing functions ${\bm{f}}_{1},\ldots,{\bm{f}}_{m}$ defined
on disjoint coordinates of $\bm{x}$, $A_{1},\ldots,A_{m}$ respectively,

$\displaystyle\mathop{{\mathds{E}}\/}\left[\prod_{i=1}^{m}{\bm{f}}_{i}(\bm{x}_{A_{i}})\right]\leq\prod_{i=1}^{m}\mathop{{\mathds{E}}\/}\left[{\bm{f}}_{i}(\bm{x}_{A_{i}})\right]$

###### Proof.

Let $\bm{z}_{i}$ be the output of ${\bm{f}}_{i}(\bm{x}_{A_{i}})$ for
$i=1,\ldots,m$. Then, by Proposition 7.6, $\bm{z}_{1},\ldots,\bm{z}_{m}$ are
negatively associated. By repeated application of Definition 12, we have the
desired result. ∎

We’ll also need that negative association is preserved under
negation.222Negative association is only preserved under negation of _all_ the
variables. Negating only some variables can create a positive correlation.

######  Proposition 7.8.

Let $\bm{x}_{1},\ldots,\bm{x}_{n}$ be negatively associated. Then
$-\bm{x}_{1},\ldots,-\bm{x}_{n}$ are also negatively associated

###### Proof.

Let $f_{1},f_{2}$ be increasing functions over disjoint coordinates
$A_{1},A_{2}\subseteq[n]$. We wish to prove

$\displaystyle\operatorname{{Cov}}[f_{1}((-\bm{x})_{A_{1}}),f_{2}((-\bm{x})_{A_{2}})]\leq
0.$

Since $-f_{1}((-\bm{x})_{A_{1}})$ and $-f_{2}((-\bm{x})_{A_{2}})$ are
increasing and disjoint functions of $\bm{x}$ and $\bm{x}$ is negatively
associated,

$\displaystyle\operatorname{{Cov}}[-f_{1}((-\bm{x})_{A_{1}}),-f_{2}((-\bm{x})_{A_{2}})]\leq
0.$

The Lemma follows from the fact that
$\operatorname{{Cov}}[-\bm{a},-\bm{b}]=\operatorname{{Cov}}[\bm{a},\bm{b}]$
for any random variables $\bm{a},\bm{b}$. ∎

With the above properties established, we are able to make progress towards
proving Lemma 7.1. First, we establish that the desired win probabilities are
negatively associated.

######  Proposition 7.9.

Under the conditions of Lemma 7.1, for each $i\in L$, the variables
$\bm{w}_{1}(i),\bm{w}_{2}(i),\ldots$ in Figure 2 are negatively associated.

###### Proof.

First, we claim that for any $r\geq 1$, the function
$1-\prod_{i=1}^{r}(1-x_{i})$ is an increasing function of
$x_{1},\ldots,x_{r}$. This is by a series of compositions.

$\displaystyle(x_{i}\mapsto 1-x_{i})$ is decreasing $\displaystyle\implies$
$\displaystyle((x_{1},\ldots,x_{r})\mapsto\prod_{i=1}^{r}(1-x_{i}))$ is
decreasing $\displaystyle\implies$ $\displaystyle((x_{1},\ldots,x_{r})\mapsto
1-\prod_{i=1}^{r}(1-x_{i}))$ is increasing

Therefore, $\bm{w}_{j}(i)$ are increasing functions of disjoint subsets of
$(\bm{x}_{1}(i),\bm{x}_{2}(i),\ldots)$. The desired result follows from 7.5. ∎

######  Lemma 7.10.

Under the conditions of Lemma 7.1, for any $i\in L$ and disjoint subsets of
time steps $S_{1},\ldots,S_{k}\subseteq[T]$

$\displaystyle\operatorname{{Pr}}[i\text{ never a winner in
}\bigcup_{\ell=1}^{k}S_{\ell}]\leq\prod_{\ell=1}^{k}\operatorname{{Pr}}[i\text{
never a winner in }S_{\ell}]$

###### Proof.

According to the properties of $\mathcal{T}$, the probability $i$ never wins
in $S_{\ell}$ is a stochastically increasing function of $(-\bm{w}_{j}(i))$
for each $j\in S_{\ell}$ and of $\bm{w}_{j}(i^{\prime})$ for all
$i^{\prime}\neq i,j\in S_{\ell}$. By Proposition 7.8 and Proposition 7.9, the
variables $(-\bm{w}_{1}(i),-\bm{w}_{2}(i),\ldots)$ are negatively associated.
Applying 7.3, we have that

$\displaystyle\bigcup_{j=1}^{\infty}\left(\\{-\bm{w}_{j}(i)\\}\cup\bigcup_{i^{\prime}\neq
i}\bm{w}_{j}(i^{\prime})\right)\text{ are all negatively associated.}$

The desired results follows Corollary 7.7. ∎

Lemma 7.10 allows us to prove Lemma 7.1 by just considering how the OCS
behaves on consecutive subsequences rather than on unions of consecutive
subsequences. We prove a final ingredient.

######  Lemma 7.11.

Under the conditions of Lemma 7.1, for any $i\in L$, subset of time steps
$S\subseteq[T]$ in which $i$ appears, and desired win probabilities $w_{j}(i)$
for each $j\in S$,

$\displaystyle\operatorname{{Pr}}[i\text{ never a winner in
}S\mid\bm{w}_{j}(i)=w_{j}(i)\text{ for each }j\in S]\leq\prod_{j\in
S}(1-w_{j}(i)).$

###### Proof.

Just as in Lemma 7.10,

$\displaystyle\bigcup_{j=1}^{\infty}\left(\bigcup_{i^{\prime}\neq
i}\bm{w}_{j}(i^{\prime})\right)\text{ are all negatively associated.}$

The probability $i$ loses in round $j$ is a stochastically increasing function
of $w_{j}(i^{\prime})$ for each $i\neq i^{\prime}$. Applying Corollary 7.7,

$\displaystyle\operatorname{{Pr}}[i\text{ never a winner in }$ $\displaystyle
S\mid\bm{w}_{j}(i)=w_{j}(i)\text{ for each }j\in S]$
$\displaystyle\leq\prod_{j\in S}\left(\operatorname{{Pr}}[i\text{ loses in
round }j\mid\bm{w}_{j}(i)=w_{j}(i)]\right)$

By the consistency of $\mathcal{T}$, $\operatorname{{Pr}}[i\text{ loses in
round }j\mid\bm{w}_{j}(i)=w_{j}(i)]$ is at most $1-w_{j}(i)$, proving the
desired result. ∎

Finally, we prove Lemma 7.1.

###### Proof of Lemma 7.1.

Our goal is to prove that for any vertex $i\in L$ and disjoint consecutive
time steps $S_{1},\ldots,S_{k}$, that

$\displaystyle\operatorname{{Pr}}[i\text{ never a winner in
}S_{1},\ldots,S_{k}]\leq\prod_{\ell=1}^{k}F(\mathrm{count}_{i}(S_{\ell}))$

where $f$ is as defined in Equation 27. By Lemma 7.10 and the assumption that
$\mathcal{W}$ is shift-invariant, it is enough to prove that

$\displaystyle\operatorname{{Pr}}[i\text{ never a winner in
$S\coloneqq\\{1,\ldots,m\\}$}]\leq F\left(\sum_{j=1}^{m}r_{j}(i)\right).$

We compute,

$\displaystyle\operatorname{{Pr}}[i\text{ never a winner in $S$}]$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{w}_{1}(i),\ldots,\bm{w}_{m}(i)}\left[\operatorname{{Pr}}[i\text{
never a winner in $S$}\mid\bm{w}_{1}(i),\ldots,\bm{w}_{m}(i)]\right]$
$\displaystyle\leq\mathop{{\mathds{E}}\/}_{\bm{w}_{1}(i),\ldots,\bm{w}_{m}(i)}\left[\prod_{j\in
S}(1-\bm{w}_{j}(i))\right]$ (Lemma 7.11)
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{x}(i)\sim\mathcal{W}}\left[\prod_{j\in
S}\left(\prod_{\ell=0}^{r_{j}(i)-1}\left(1-\bm{x}_{k_{j}(i)+\ell}\right)\right)\right]$
(Equation 25)
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{x}(i)\sim\mathcal{W}}\left[\prod_{\ell=1}^{r_{1}(i)+\ldots+r_{m}(i)}\left(1-\bm{x}_{\ell}\right)\right]$
(Combine products) $\displaystyle=F\left(\sum_{j\in S}r_{j}(i)\right)$
(Equation 27)

as desired. ∎

###  7.2 Design of the tournament subroutine

In this subsection, we prove the following Lemma which completes the proof of
Theorem 7.

######  Lemma 7.12 (Sufficiently small $\implies$ good $\mathcal{T}$).

Let $\mathcal{W}$ is a win-distribution for which the following holds. For
each $r\in[m-1]$ define $\bm{w}^{(r)}$ to be the random variable indicating
the distribution of desired win probability of a vertex of multiplicity $r$,

$\displaystyle\bm{w}^{(r)}\sim\left(1-\prod_{\ell=1}^{r}\left(1-\bm{x}_{\ell}\right)\right)\quad\quad\text{where}\quad\quad\bm{x}\sim\mathcal{W},$

If, for each $t\in[0,1]$ and $r\in[m-1]$,

$\displaystyle\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{W}}\left[\left(\bm{w}^{(r)}-t\right)_{+}\right]\leq
1-t-\frac{m-r}{m}\cdot\left(1-t^{\frac{m}{m-r}}\right),$ (28)

then there is a tournament subroutine, $\mathcal{T}$ with the following
properties.

  1. 1.

Consistent: For each $w\in[0,1]$, the probability $i$ wins round $j$ given
that $\bm{w}_{j}(i)=w$ is at least $w$.

  2. 2.

Stochastic ordering: The probability $i$ wins a round is a stochastically
increasing function of $\bm{w}_{j}(i)$ and a stochastically decreasing
function of $\bm{w}_{j}(i^{\prime})$ for each $i^{\prime}\neq i$.

Our tournament subroutine will be simple: We’ll design stochastically
increasing strength functions
$\bm{\mathcal{S}}_{1},\ldots,\bm{\mathcal{S}}_{m-1}$ that map a desired win
probability to a “strength.” For each $i\in A_{j}$, we set its strength to
$\bm{\mathcal{S}}_{r_{j}(i)}(\bm{w}_{j}(i))$, and the vertex with the highest
strength wins the round. We give pseudocode for this subroutine in Figure 3.

$\mathrm{\mathcal{T}}_{\bm{\mathcal{S}}_{1},\ldots,\bm{\mathcal{S}}_{m-1}}$ 1.
If there is a vertex with $r_{j}(i)=m$, then select $i$ as the winner. 2.
Otherwise, for each $i\in A_{j}$, sample a strength,
$\displaystyle\bm{s}_{j}(i)\coloneqq\bm{\mathcal{S}}_{r_{j}(i)}(\bm{w}_{j}(i)),$
and choose the $i$ maximizing $\bm{s}_{j}(i)$ as the winner. Figure 3: A
tournament subroutine for returning a winner given desired win probabilities
$\bm{s}_{j}(i)$ and multiplicities $r_{j}(i)$. This subroutine is
parameterized by strength functions
$\bm{\mathcal{S}}_{1},\ldots,\bm{\mathcal{S}}_{m-1}$.

As long as the strength functions are stochastically increasing, the
stochastic ordering criteria of Lemma 7.12 will hold. On the other hand,
consistency is more challenging. The following fundamental question underlies
this subsection.

> For which distributions of $\bm{w}^{(r)}$ is it possible to design
> stochastically increasing strength functions such that the probability $i$
> wins round $j$ given $\bm{w}_{j}(i)=w$ is at least $w$. ($\diamondsuit$)

Consider the case where $r=1$. Since there can only be one winner in a round,
for ($\diamondsuit$) to hold, it must be the case that
$\operatorname{{\mathds{E}}}[\bm{w}^{(1)}]\leq\frac{1}{m}$. It turns out, that
condition is not sufficient. Suppose that $\bm{w}^{(1)}$ is $1$ with
probability $\frac{1}{m}$ and $0$ otherwise. Then, there is a nonzero
probability that $2$ (or more) vertices will both declare that they should win
with probability $1$, making ($\diamondsuit$) impossible. This example shows
that not only do we want the expectation of $\bm{w}^{(1)}$ to be small, we
want its distribution to not be too spread out.

We will show that these two notions – how large and spread out $\bm{w}^{(r)}$
is – fully capture when ($\diamondsuit$) is possible. Recall the following
definition which formalizes the notion of “large and spread out.” See 9

The following Lemma formalizes our intuition that as long as the desired win
probabilities are sufficiently small and not spread out, ($\diamondsuit$)
holds.

######  Lemma 7.13 (Increasing convex order $\to$ ($\diamondsuit$)).

For any random variables $\bm{w}^{(1)}\ldots,\bm{w}^{(m-1)}$ and
$\bm{w}^{\prime(1)}\ldots,\bm{w}^{\prime(m-1)}$, if

$\displaystyle\bm{w}^{(r)}\preceq_{\mathrm{icx}}\bm{w}^{\prime(r)}\quad\quad\text{for
each $r=1,\ldots,m-1$},$

and ($\diamondsuit$) holds for
$(\bm{w}^{\prime(1)},\ldots,\bm{w}^{\prime(m-1)})$, then it also holds for
$(\bm{w}^{(1)},\ldots,\bm{w}^{(m-1)})$.

Our proof of Lemma 7.13 leverages a powerful theorem of Müller and
Rüschendorf.

######  Theorem 8 ([MR01]).

For univariate random variables $\bm{a},\bm{b}$, the following are equivalent.

  1. 1.

$\bm{a}$ is smaller than $\bm{b}$ in the increasing convex order.

  2. 2.

There is a coupling of $(\hat{\bm{a}},\hat{\bm{b}})$ such that the marginal
distribution of $\hat{\bm{a}}$ and $\hat{\bm{b}}$ are the same as those of
$\bm{a}$ and $\bm{b}$ respectively, and, for any choice of $a$,

$\displaystyle\mathop{{\mathds{E}}\/}[\hat{\bm{b}}\mid\hat{\bm{a}}]\geq\hat{\bm{a}}.$

Furthermore, the stochastic function mapping
$a\mapsto(\hat{\bm{b}}\mid\hat{\bm{a}}=a)$ is stochastically increasing.

Theorem 8 is a generalization of a classic result by Strassen [Str65] who
proved the same result without the restriction that
$a\mapsto(\hat{\bm{b}}\mid\hat{\bm{a}}=a)$ be stochastically increasing. We’ll
need the stronger result since we want our strength functions to be
stochastically increasing.

###### Proof of Lemma 7.13.

For each $r\in[m-1]$, let $(\hat{\bm{w}}^{(r)},\hat{\bm{w}}^{\prime(r)})$ be
the coupling guaranteed to exist by Theorem 8 and let
$\bm{\mathcal{S}}_{1}^{\prime},\ldots,\bm{\mathcal{S}}_{m-1}^{\prime}$ be the
strength functions satisfying ($\diamondsuit$) for
$\bm{w}^{\prime(1)}\ldots,\bm{w}^{\prime(m-1)}$. Define, for each $r\in[m-1]$,

$\displaystyle\bm{\mathcal{S}}_{r}(w)\coloneqq\bm{\mathcal{S}}_{r}^{\prime}(\hat{\bm{w}}^{\prime})\quad\text{where}\quad\hat{\bm{w}^{\prime}}\sim(\hat{\bm{w}}^{\prime(r)}\mid\hat{\bm{w}}^{(r)}=w).$

We claim that $\bm{\mathcal{S}}_{1},\ldots,\bm{\mathcal{S}}_{m-1}$ are
strength functions satisfying ($\diamondsuit$) for
$(\bm{w}^{(1)},\ldots,\bm{w}^{(m-1)})$. First, since the composition of
stochastically increasing functions is stochastically increasing,
$\bm{\mathcal{S}}_{r}$ is stochastically increasing for all $r\in[m-1]$.
Second, the probability $i$ wins a round with strength $w$ is at least
$\operatorname{{\mathds{E}}}[\hat{\bm{w}}^{\prime(r)}\mid\hat{\bm{w}}^{(r)}=w]$,
which is at least $w$. ∎

######  Remark 4 (Computational efficiency of Lemma 7.13).

Computing $\bm{\mathcal{S}}_{r}$ requires knowing the coupling
$(\hat{\bm{w}}^{(r)},\hat{\bm{w}}^{\prime(r)})$. If $\hat{\bm{w}}^{(r)}$ and
$\hat{\bm{w}}^{\prime(r)})$ are discrete random variables, finding a desired
coupling is simply a linear program. If they are continuous, they can be
discretized to any desired accuracy and then treated as discrete.

In order to use Lemma 7.13, we need to be able to verify when one variable is
smaller, in the increasing convex order, than another. We use the following
well known characterization.

######  Fact 7.14 ([SS07]).

For univariate random variables $\bm{a},\bm{b}$, the following are equivalent.

  1. 1.

$\bm{a}$ is smaller than $\bm{b}$ in the increasing convex order.

  2. 2.

For every $t\in\mathds{R}$,

$\displaystyle\mathop{{\mathds{E}}\/}[(\bm{a}-t)_{+}]\leq\mathop{{\mathds{E}}\/}[(\bm{b}-t)_{+}].$

We complete the proof of Lemma 7.12 by giving a particular choice for
$(\bm{w}^{(1)},\ldots,\bm{w}^{(m-1)})$ on which ($\diamondsuit$) holds.

######  Lemma 7.15.

For each $r\in[m-1]$, let $\bm{w}^{(r)}$ be the random variable supported on
$[0,1]$ satisfying

$\displaystyle\mathop{{\mathds{E}}\/}[(\bm{w}^{(r)}-t)_{+}]=1-t-\frac{m-r}{m}\cdot\left(1-t^{\frac{m}{m-r}}\right)\quad\quad\forall
t\in[0,1]$ (29)

Then, ($\diamondsuit$) holds for $(\bm{w}^{(1)},\ldots,\bm{w}^{(m-1)})$

###### Proof.

Straightforward computation verifies that Equation 29 is equivalent to each
$\bm{w}^{(r)}$ having the CDF.

$\displaystyle\operatorname{{Pr}}[\bm{w}^{(r)}\leq
t]=t^{\frac{r}{m-r}}\quad\quad\forall t\in[0,1].$

Consider the strength functions, for each $r\in[m-1]$,

$\displaystyle\bm{\mathcal{S}}_{r}(w)\coloneqq w^{\frac{1}{m-r}}.$

For each $r\in[m-1]$, we have that

$\displaystyle\operatorname{{Pr}}[\bm{\mathcal{S}}_{r}(\bm{w}^{(r)})\leq
t]=\operatorname{{Pr}}[\bm{w}^{(r)}\leq t^{m-r}]=t^{r}.$

Therefore, $\bm{\mathcal{S}}_{r}(\bm{w}^{(r)})$ is distributed according to
the max of $r$ independent variables drawn from $\mathrm{Uniform}(0,1)$. A
vertex $i$ is selected in a round if its strength is larger than the strengths
of each of the other vertices. If $i$ has multiplicity $r(i)$, then the max
strength of the other vertices is distributed according to the maximum of
$m-r(i)$ independent uniforms. Therefore,

$\displaystyle\operatorname{{Pr}}[i\text{ selected with strength }w]$
$\displaystyle=\operatorname{{Pr}}[\text{max of ($m-r(i)$) independent
uniforms}<\bm{\mathcal{S}}_{r(i)}(w)]$
$\displaystyle=\bm{\mathcal{S}}_{r(i)}(w)^{m-r(i)}$ $\displaystyle=w,$

Furthermore, $\bm{\mathcal{S}}_{r}$ is increasing for all $r\in[m-1]$.
Therefore, both criteria of ($\diamondsuit$) hold. ∎

##  8 Constructing a win-distribution

In this section we will construct a distribution
$(\bm{x}_{1},\bm{x}_{2},\ldots)\sim\mathcal{W}$ meeting the three criteria of
Theorem 7 and also leads to a good competitive ratio. We do this in two steps.
First, we construct a “seed distribution” $\mathcal{D}$ that returns an
infinite sequence $(\bm{y}_{1},\bm{y}_{2},\ldots)$ that are negatively
associated and shift-invariant, but the values $\bm{y}_{j}$ do not represent
probabilities. Then, for a carefully chosen increasing function $W$, we set
$\bm{x}_{k}=W(\bm{y}_{k})$ to ensure the third criteria of Theorem 7 holds. We
can think of $W$ as mapping an output of $\mathcal{D}$ to a desired win
probability.

In the remainder of this section, $p$ is a hyperparameter than impacts the
distribution of $\mathcal{D}$ and $\mathcal{W}$. For concreteness, we will
eventually set $p=0.48$ to optimize the competitive ratio, a value we selected
using brute-force search.

######  Definition 13 ($\mathcal{D}$).

A sample $(\bm{y}_{1},\bm{y}_{2},\ldots)\sim\mathcal{D}$ is generated by the
following process, where each random choice is independent.

  1. 1.

Initialize $\bm{z}_{1}\sim\mathrm{Geo}(p)$.

  2. 2.

For $k=1,2,\ldots$,

    1. (a)

With probability $p$, set $\bm{y}_{k}=\bm{z}_{k}$ and then reset $z$, setting
$\bm{z}_{k+1}\leftarrow 0$.

    2. (b)

Otherwise, set $\bm{y}_{k}=-1$ and increment $z$, setting
$\bm{z}_{k+1}\leftarrow\bm{z}_{k}+1$

It will often by convenient for us to refer to the following variants of
$\mathcal{D}$.

######  Definition 14.

We use the following notation to specify variants of $\mathcal{D}$.

  1. 1.

For any $v\geq 0$, we use $\mathcal{D}_{v}$ to refer to the generative process
of Definition 13 where $\bm{z}_{1}$ is initialized to $v$ instead of drawn
from $\mathrm{Geo}(p)$.

  2. 2.

For any $n\geq 1$, we use $\mathcal{D}^{(n)}$ to refer to first $n$ element of
$\mathcal{D}$; i.e. to $\bm{y}_{1},\ldots,\bm{y}_{n}$ where $\bm{y}\sim D$.

  3. 3.

We use $\mathcal{D}(y,z)$ to refer to the distribution that outputs two
infinite sequences, one corresponding to the $(\bm{y}_{1},\bm{y}_{2},\ldots)$
and the other to the $(\bm{z}_{1},\bm{z}_{2},\ldots)$ in Definition 13.

We’ll also mix and match the above notation. For example, we might use
$\bm{y},\bm{z}\sim\mathcal{D}^{(n)}(y,z)$ as shorthand for $\bm{y}$ and
$\bm{z}$ are each $n$-tuples containing $\bm{y}_{1},\ldots,\bm{y}_{n}$ and
$\bm{z}_{1},\ldots,\bm{z}_{n}$ respectively.

By examining the generative process in Definition 13, we observe that
$\mathcal{D}$ is _almost_ memoryless.

######  Fact 8.1 ($\mathcal{D}$ is memoryless except for $z$).

For any $k,v\geq 0$ and $\bm{y},\bm{z}\sim\mathcal{D}(y,z)$, the following
distributions are identical.

  1. 1.

The distribution of $(\bm{y}_{k},\bm{y}_{k+1},\ldots)$ conditioned on
$\bm{z}_{k}=v$.

  2. 2.

The distribution $\mathcal{D}_{v}$.

First, we prove that $\mathcal{D}$ is shift-invariant. This amounts to proving
that for any $k\geq 1$, $\bm{z}_{k}$ is distributed according to a
$\mathrm{Geo}(p)$.

######  Proposition 8.2.

Let $\bm{y},\bm{z}\sim\mathcal{D}(y,z)$. Then, for any $k\geq 1$, $\bm{z}_{k}$
is distributed according to a $\mathrm{Geo}(p)$ distribution,

$\displaystyle\operatorname{{Pr}}[\bm{z}_{k}=v]=(1-p)^{v}\dot{p}.$

###### Proof.

By induction on $k$; $\bm{z}_{1}$ is initialized from a geometric
distribution, so Proposition 8.2 holds for $k=1$.

For the inductive step, consider some $k>1$, $\bm{z}_{k}=0$ only it was reset
at that round, which happens with probability $p$. For $v\geq 1$

$\displaystyle\operatorname{{Pr}}[\bm{z}_{k}=v]$
$\displaystyle=(1-p)\cdot\operatorname{{Pr}}[\bm{z}_{k-1}=v-1]$
$\displaystyle=(1-p)\cdot(1-p)^{v-1}\cdot p$ $\displaystyle=(1-p)^{v}\cdot p.$

Therefore, $\bm{z}_{k}\sim\mathrm{Geo}(p)$. ∎

As a corollary of 8.1 and Proposition 8.2.

######  Corollary 8.3 ($\mathcal{D}$ is shift-invariant).

For any $k\geq 1$ and $\bm{y}\sim\mathcal{D}$, the distribution of
$\bm{y}_{1},\bm{y}_{2},\ldots$ is identical to that of
$\bm{y}_{k},\bm{y}_{k+1},\ldots$.

###  8.1 $\mathcal{D}$ is negatively associated

We devote this subsection to establishing that $\mathcal{D}$ is negatively
associated. Recall See 12

For starters, we the above definition holds if we restrict $A_{1}=\\{n\\}$.

######  Lemma 8.4.

For any $n\geq 1$ and indices $S\subseteq[n-1]$, let
$\bm{y}_{1},\ldots,\bm{y}_{n}$ be drawn as

$\displaystyle(\bm{y}_{1},\ldots,\bm{y}_{n})\sim(\mathcal{D}^{(n)}\mid\bm{y}_{i}=-1\text{
for each $i\in S$})$

Then, for any increasing functions
$f_{1}:\mathds{Z}\to\mathds{R},f_{2}:\mathds{Z}^{n-1}\to\mathds{R}$,

$\displaystyle\mathop{{\operatorname{{Cov}}}\/}_{\bm{y}_{1},\ldots,\bm{y}_{n}}\big{[}f_{1}(\bm{y}_{n}),f_{2}(\bm{y}_{1},\ldots,\bm{y}_{n-1})\big{]}\leq
0$

The same is true when using $\mathcal{D}^{(n)}_{0}$ rather than
$\mathcal{D}^{(n)}$.

We only prove Lemma 8.4 for $\mathcal{D}^{(n)}$ as the proof for
$\mathcal{D}^{(n)}_{0}$ is identical. Throughout the following proof, the
distribution on $\bm{y}_{1},\ldots,\bm{y}_{n}$ is by default
$(\mathcal{D}^{(n)}\mid\bm{y}_{i}=-1\text{ for each $i\in S$})$.

###### Proof.

Without loss of generality, we can assume $f_{1}(-1)=0$; otherwise, add an
appropriate constant to $f_{1}$ so that it’s true. Since $f_{1}$ is an
increasing function of $\bm{y}_{n}$ and $\bm{y}_{n}\geq-1$, we can write,

$\displaystyle f_{1}(k)=\sum_{j=0}^{k}g(j)$

for an appropriate nonnegative function $g:\mathds{Z}\to\mathds{R}_{\geq 0}$.
We then expand the first term of our desired covariance.

$\displaystyle\mathop{{\mathds{E}}\/}_{\bm{y}_{1},\ldots,\bm{y}_{n}}\big{[}f_{1}(\bm{y}_{n})\cdot
f_{2}(\bm{y}_{1}\cdot\ldots,\bm{y}_{n-1})\big{]}$
$\displaystyle=\sum_{k=-1}^{\infty}f_{1}(k)\cdot\operatorname{{Pr}}[\bm{y}_{n}=k]\cdot\mathop{{\mathds{E}}\/}\big{[}f_{2}(\bm{y}_{1},\ldots,\bm{y}_{n-1})\mid\bm{y}_{n}=k\big{]}$
$\displaystyle=\sum_{k=-1}^{\infty}\sum_{j=0}^{k}g(j)\cdot\operatorname{{Pr}}[\bm{y}_{n}=k]\cdot\mathop{{\mathds{E}}\/}\big{[}f_{2}(\bm{y}_{1},\ldots,\bm{y}_{n-1})\mid\bm{y}_{n}=k\big{]}$
$\displaystyle=\sum_{j=0}^{\infty}\sum_{k=j}^{\infty}g(j)\cdot\operatorname{{Pr}}[\bm{y}_{n}=k]\cdot\mathop{{\mathds{E}}\/}\big{[}f_{2}(\bm{y}_{1},\ldots,\bm{y}_{n-1})\mid\bm{y}_{n}=k\big{]}$
$\displaystyle=\sum_{j=0}^{\infty}g(j)\cdot\operatorname{{Pr}}[\bm{y}_{n}\geq
j]\cdot\mathop{{\mathds{E}}\/}\big{[}f_{2}(\bm{y}_{1},\ldots,\bm{y}_{n-1})\mid\bm{y}_{n}\geq
j\big{]}$

We claim that
$\mathop{{\mathds{E}}\/}\big{[}f_{2}(\bm{y}_{1},\ldots,\bm{y}_{n-1})\mid\bm{y}_{n}\geq
j\big{]}$ is a decreasing function of $j$. First we note that conditioning on
$(\bm{y}_{n}\geq j)$ forces that $\bm{y}_{n-j}=\ldots,=\bm{y}_{n-j-1}-1$ and
leaves the distribution of $\bm{y}_{1},\ldots,\bm{y}_{n-j-2}$ unchanged.

Suppose we draw $\bm{y}_{1},\ldots,\bm{y}_{n-1}$ conditioned on
$(\bm{y}_{n}\geq j)$. Then, we set $\bm{y}_{n-(j+1)}$ to $-1$ and leave all
other $\bm{y}_{1},\ldots,\bm{y}_{n-1}$ unchanged. This is equivalent to
drawing $\bm{y}_{1},\ldots,\bm{y}_{n-1}$ conditioned on $(\bm{y}_{n}\geq
j+1)$. Importantly, setting $\bm{y}_{n-(j+1)}=-1$ can only decrease the value
of $f_{2}(\bm{y}_{1},\ldots,\bm{y}_{n-1})$, because $f_{2}$ is increasing.
Therefore, we have that,

$\displaystyle\mathop{{\mathds{E}}\/}\big{[}f_{2}(\bm{y}_{1},\ldots,\bm{y}_{n-1})\mid\bm{y}_{n}\geq
j\big{]}\quad\quad\text{is decreasing in $j$}.$ (30)

We can now prove the desired result.

$\displaystyle\mathop{{\mathds{E}}\/}\big{[}$ $\displaystyle
f_{1}(\bm{y}_{n})\cdot f_{2}(\bm{y}_{1}\cdot\ldots,\bm{y}_{n-1})\big{]}$
$\displaystyle=\sum_{j=0}^{\infty}g(j)\cdot\operatorname{{Pr}}[\bm{y}_{n}\geq
j]\cdot\mathop{{\mathds{E}}\/}\big{[}f_{2}(\bm{y}_{1},\ldots,\bm{y}_{n-1})\mid\bm{y}_{n}\geq
j\big{]}$
$\displaystyle\leq\sum_{j=0}^{\infty}g(j)\cdot\operatorname{{Pr}}[\bm{y}_{n}\geq
j]\cdot\mathop{{\mathds{E}}\/}\big{[}f_{2}(\bm{y}_{1},\ldots,\bm{y}_{n-1})\mid\bm{y}_{n}\geq-1\big{]}$
$\displaystyle=\left(\sum_{j=0}^{\infty}g(j)\cdot\operatorname{{Pr}}[\bm{y}_{n}\geq
j]\right)\cdot\left(\mathop{{\mathds{E}}\/}\big{[}f_{2}(\bm{y}_{1},\ldots,\bm{y}_{n-1})\big{]}\right)$
$\displaystyle=\mathop{{\mathds{E}}\/}\big{[}f_{1}(\bm{y}_{n})\big{]}\cdot\mathop{{\mathds{E}}\/}\big{[}f_{2}(\bm{y}_{1}\cdot\ldots,\bm{y}_{n-1})\big{]}.$

Where the inequality follows from Equation 30. ∎

Next, we prove that $\mathcal{D}^{(n)}$ is negatively associated.

######  Lemma 8.5.

For any $n\geq 1$, draw $\bm{y}_{1},\ldots,\bm{y}_{n}\sim\mathcal{D}^{(n)}$.
Then, $\bm{y}_{1},\ldots,\bm{y}_{n}$ are negatively associated.

###### Proof.

By induction on $n$. For $n=1$, the desired result holds because a single
variable is vacuously negatively associated.

For any $n\geq 2$ fix some disjoint sets $A_{1},A_{2}\subseteq[n]$ and
increasing functions
$f_{1}:\mathds{Z}^{|A_{1}|}\to\mathds{R},f_{2}:\mathds{Z}^{|A_{2}|}\to\mathds{R}$.
Without loss of generality, we can assume that $n\in A_{1}$ and $n\notin
A_{2}$. We define an “averaging” of $f_{1}$ that does _not_ depend upon
$\bm{y}_{n}$.

$\displaystyle\bar{f}_{1}(\bm{y}_{A_{1}})=\mathop{{\mathds{E}}\/}_{\bm{y}\sim\mathcal{D}^{(n)}}\big{[}f_{1}(\bm{y}_{A_{1}})\mid\bm{y}_{i}=\bm{y}_{i}\text{
for each $i\in(A_{1}\setminus\\{n\\})$}\big{]}$

Importantly, neither $\bar{f_{1}}$ nor $f_{2}$ depend on $\bm{y}_{n}$, so we
can apply the inductive hypothesis.

$\displaystyle\mathop{{\mathds{E}}\/}[\bar{f}_{1}(\bm{y}_{A_{1}})\cdot
f_{2}(\bm{y}_{A_{2}})]\leq\mathop{{\mathds{E}}\/}[\bar{f}_{1}(\bm{y}_{A_{1}})]\cdot\mathop{{\mathds{E}}\/}[f_{2}(\bm{y}_{A_{2}})]$
(31)

Furthermore, $\bar{f}_{1}$ and $f_{1}$ have the same expectation. Our next
goal is to show that

$\displaystyle\mathop{{\mathds{E}}\/}[f_{1}(\bm{y}_{A_{1}})\cdot
f_{2}(\bm{y}_{A_{2}})]\leq\mathop{{\mathds{E}}\/}[\bar{f}_{1}(\bm{y}_{A_{1}})\cdot
f_{2}(\bm{y}_{A_{2}})]$

The above two equations will imply the desired result.

Define the “left signature” of some $y_{1},\ldots,y_{n}$ as follows. If
$y_{i}=-1$ for all $i\in A_{1}\setminus\\{n\\}$, then the signature is
$\mathcal{L}(y_{1},\ldots,y_{n})=\emptyset$. Otherwise, let $i^{\star}$ be the
largest $i\in A_{1}\setminus\\{n\\}$ where $y_{i}\geq 0$ and the signature is
$\mathcal{L}(y_{1},\ldots,y_{n})=(y_{1},\ldots,y_{i^{\star}})$. We claim for
any choice of left signature, $\ell$, that

$\displaystyle\mathop{{\mathds{E}}\/}[f_{1}(\bm{y}_{A_{1}})\cdot
f_{2}(\bm{y}_{A_{2}})\mid\mathcal{L}(\bm{y})=\ell]\leq\mathop{{\mathds{E}}\/}[\bar{f}_{1}(\bm{y}_{A_{1}})\cdot
f_{2}(\bm{y}_{A_{2}})\mid\mathcal{L}(\bm{y})=\ell].$

First consider the case where $\ell\neq\emptyset$. Conditioning upon signature
$\ell$ is equivalent to:

  1. 1.

Fixing the values of $\bm{y}_{1},\ldots,\bm{y}_{i^{\star}}$ to those in
$\ell$.

  2. 2.

Conditioning on $\bm{y}_{j}=-1$ for all $j\in A_{1}\setminus\\{n\\}$ where
$j>i^{\star}$.

By 8.1, the distribution of $\bm{y}_{i^{\star}+1},\ldots,\bm{y}_{n}$ is the
same as $\mathcal{D}^{(n-i^{\star})}_{0}$ conditioned on some of the elements
being $-1$. This is a distribution for which we can apply Lemma 8.4. We also
need $f_{1}$ to just depend on the last bit, $\bm{y}_{n}$. Fortunately,
conditioning on the signature fixes all bits in $A_{1}$ except for
$\bm{y}_{n}$ so that property is satisfied. Therefore, by Lemma 8.4.

$\displaystyle\mathop{{\mathds{E}}\/}[f_{1}(\bm{y}_{A_{1}})\cdot
f_{2}(\bm{y}_{A_{2}})\mid\mathcal{L}(\bm{y})=\ell]$
$\displaystyle\leq\mathop{{\mathds{E}}\/}[f_{1}(\bm{y}_{A_{1}})\mid\mathcal{L}(\bm{y})=\ell]\cdot\mathop{{\mathds{E}}\/}[f_{2}(\bm{y}_{A_{2}})\mid\mathcal{L}(\bm{y})=\ell]$
(32)

In the other case where $\ell=\emptyset$, conditioning on $\ell$ is equivalent
to drawing $\bm{y}_{1},\ldots,\bm{y}_{n}$ from $(\mathcal{D}^{(n)}\mid
y_{i}=-1\text{ for each }i\in A_{1}\setminus\\{n\\})$. Once again, after this
conditioning, $f_{1}$ only depends on $\bm{y}_{n}$, so we can apply Lemma 8.4
and Equation 32 holds.

Next, we wish to substitute in $\bar{f}_{1}$ for $f_{1}$. Fixing
$\mathcal{L}(\bm{y})=\ell$ fixes all variables in $A_{1}$ except for $n$. By
the definition of $\bar{f}_{1}$, we have that

$\displaystyle\mathop{{\mathds{E}}\/}[f_{1}(\bm{y}_{A_{1}})\mid\mathcal{L}(\bm{y})=\ell]=\bar{f}_{1}(x)\text{
for any }x\text{ where }\mathcal{L}(x)=\ell.$ (33)

We’ll use two aspects of the above equation:

  1. 1.

That $\bar{f}_{1}(x)$ has the same expectation as $f_{1}$ when conditioning on
the signature.

  2. 2.

That $\bar{f}_{1}(x)$ is constant when conditioning on the signature.

, Combining the above with Equation 32, where $\bm{\ell}$ is drawn from
$\mathcal{L}(\bm{y})$ for $\bm{y}\sim\mathcal{D}^{(n)}$,

$\displaystyle\mathop{{\mathds{E}}\/}\big{[}f_{1}(\bm{y}_{A_{1}})\cdot
f_{2}(\bm{y}_{A_{2}})\big{]}$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{\ell}}\big{[}\mathop{{\mathds{E}}\/}[f_{1}(\bm{y}_{A_{1}})\cdot
f_{2}(\bm{y}_{A_{2}})\mid\mathcal{L}(\bm{y})=\ell]\big{]}$ (Law of total
expectation)
$\displaystyle\leq\mathop{{\mathds{E}}\/}_{\bm{\ell}}\big{[}\mathop{{\mathds{E}}\/}[f_{1}(\bm{y}_{A_{1}})\mid\mathcal{L}(\bm{y})=\ell]\cdot\mathop{{\mathds{E}}\/}[f_{2}(\bm{y}_{A_{2}})\mid\mathcal{L}(\bm{y})=\ell]\big{]}$
(Equation 32)
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{\ell}}\big{[}\mathop{{\mathds{E}}\/}[\bar{f}_{1}(\bm{y}_{A_{1}})\mid\mathcal{L}(\bm{y})=\ell]\cdot\mathop{{\mathds{E}}\/}[f_{2}(\bm{y}_{A_{2}})\mid\mathcal{L}(\bm{y})=\ell]\big{]}$
(Equation 33)
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{\ell}}\big{[}\mathop{{\mathds{E}}\/}[\bar{f}_{1}(\bm{y}_{A_{1}})\cdot
f_{2}(\bm{y}_{A_{2}})\mid\mathcal{L}(\bm{y})=\ell]\big{]}$ ($\bar{f}_{1}$
constant conditioned on $\ell$)
$\displaystyle=\mathop{{\mathds{E}}\/}\big{[}\bar{f}_{1}(\bm{y}_{A_{1}})\cdot
f_{2}(\bm{y}_{A_{2}})\big{]}$ (Law of total expectation)
$\displaystyle\leq\mathop{{\mathds{E}}\/}\big{[}\bar{f}_{1}(\bm{y}_{A_{1}})\big{]}\cdot\mathop{{\mathds{E}}\/}\big{[}f_{2}(\bm{y}_{A_{2}})\big{]}$
(Equation 31)
$\displaystyle=\mathop{{\mathds{E}}\/}\big{[}f_{1}(\bm{y}_{A_{1}})\big{]}\cdot\mathop{{\mathds{E}}\/}\big{[}f_{2}(\bm{y}_{A_{2}})\big{]}$
($\mathop{{\mathds{E}}\/}\big{[}f_{1}\big{]}=\mathop{{\mathds{E}}\/}\big{[}\bar{f}_{1}\big{]}$)

Hence $f_{1}(\bm{y}_{A_{1}})$ and $f_{2}(\bm{y}_{A_{2}})$ are negatively
correlated, so $\bm{y}_{1},\ldots,\bm{y}_{n}$ satisfy the definition of
negative association. ∎

###  8.2 Choosing $W$

Recall that we will set the output of $\mathcal{W}$ to
$(W(\bm{y}_{1}),W(\bm{y}_{2}),\ldots)$ for $\bm{y}\sim\mathcal{D}$, where $W$
is some increasing function. Our goal in this section is to make $W$ as large
as possible while still ensuring that the output of $\mathcal{W}$ isn’t too
large, meaning Equation 28 holds.

First, consider the case when every $A_{j}$ does not contain duplicates
(meaning $r_{j}(i)\leq 1$ for all $i$). In this case, we have that the desired
win probability of each vertex $i\in A_{j}$ is

$\displaystyle\bm{w}_{j}(i)=\bm{x}_{k_{j}(i)}=W(\bm{y}_{k_{j}(i)})$

One natural way to pick a winner in this round is to pick the vertex with the
largest $\bm{y}_{k_{j}(i)}$, breaking ties at random. Indeed, this is what we
will do. Let $\bm{i}_{\max}(y_{1},\ldots,y_{m})$ be the function that return
the index $i$ maximizing $y_{i}$, choosing randomly from maximal $y_{i}$ in
the case of a tie. We define

$\displaystyle
W(y)\coloneqq\mathop{{\operatorname{{Pr}}}\/}_{\bm{y}_{2},\ldots,\bm{y}_{m}\overset{\mathrm{iid}}{\sim}\mathcal{D}^{(1)}}[\bm{i}_{\max}(y,\bm{y}_{2},\ldots,\bm{y}_{m})=1]$
(34)

This $W(y)$ is a general choice than can work for any seed distribution
$\mathcal{D}$ and, as long as $\mathcal{D}$ has negative correlations, this
choice of $W$ results in $\mathcal{W}$ having negative correlations as well.
This choice for $W$ will lead to Equation 28 holding for $r=1$, though it
still needs to be verified separately for $r\geq 2$. First, we compute what
the function $W$ for our $\mathcal{D}$.

######  Lemma 8.6.

For $W$ defined in Equation 34 and $\mathcal{D}$ in Definition 13,

$\displaystyle
W(y)=\frac{G(y+1)^{m}-G(y)^{m}}{m\cdot(G(y+1)-G(y))}\quad\quad\text{where}\quad\quad
G(v)\coloneqq\begin{cases}0&\text{if }v=-1\\\
(1-p)+p\cdot(1-(1-p)^{v})&\text{if }v\geq 0\end{cases}$ (35)

###### Proof.

Let $\bm{y}_{1},\ldots,\bm{y}_{m}$ be $m$ independent samples from
$\mathcal{D}^{(1)}$, and let
$\bm{i}^{\star}=\bm{i}_{\max}(\bm{y}_{1},\bm{y}_{2},\ldots,\bm{y}_{m})$. We
wish to compute the probability $\bm{i}^{\star}=1$ as a function of
$\bm{y}_{1}$. First, we observe that $G$ as defined in Equation 35 satisfies,
for each $i=1,\ldots,m$,

$\displaystyle G(v)=\operatorname{{Pr}}[\bm{y}_{i}\leq v-1]$

We consider a different process for generating $\bm{y}_{1},\ldots,\bm{y}_{m}$
that simplifies the analysis. In general, we can generate any univariate
random variable $\bm{y}$ by first generating $\bm{a}\sim\mathrm{Uniform}(0,1)$
and then setting $\bm{y}$ to the smallest $v$ such that
$\operatorname{{Pr}}[\bm{y}\leq v]\geq\bm{a}$. Applying this to our setting,
we first sample $\bm{a}_{1},\ldots,\bm{a}_{m}\sim\mathrm{Uniform}(0,1)$ and
then for each $i\in[m]$ set $\bm{y}_{i}$ to the smallest $v$ such that
$G(v+1)\geq\bm{y}$. Then, we set $\bm{i}^{\star}$ to the unique $i$ maximizing
$\bm{a}_{i}$ (which exists with probability $1$ since the $\bm{a}_{i}$ are
continuous).

This generating process for $(\bm{y}_{1},\ldots,\bm{y}_{m},\bm{i}^{\star})$
gives the same joint distribution as the original, so we are free to analyze
it instead. Then, the distribution of $\bm{a}_{1}$ conditioned on $\bm{y}_{i}$
is given by

$\displaystyle(\bm{a}_{1}\mid\bm{y}_{1}=y)\sim\mathrm{Uniform}(G(y),G(y+1)).$

We next compute the desired result.

$\displaystyle\operatorname{{Pr}}[\bm{i}^{\star}=1\mid\bm{x}_{1}=x]$
$\displaystyle=\operatorname{{Pr}}[\bm{y}_{i}<\bm{y}_{1}\text{ for all
$i=2,\ldots,m$}\mid\bm{x}_{1}=x]$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{y}_{1}}\left[(\bm{y}_{1})^{m-1}\right]$
($\bm{y}_{i}\sim\mathrm{Uniform}(0,1)$ for each $i=2,\ldots,m$)
$\displaystyle=\frac{1}{G(x+1)-G(x)}\cdot\int_{G(x)}^{G(x+1)}t^{m-1}dt$
($\bm{y}_{1}\sim\mathrm{Uniform}(G(x),G(x+1))$ )
$\displaystyle=\frac{G(x+1)^{m}-G(x)^{m}}{m\cdot(G(x+1)-G(x))},$

which is exactly the definition of $W(x)$.

∎

For computational reasons, we don’t directly use Equation 34. Instead, we use
a “capped” version of $W$. For some $y_{\max}\geq 0$

$\displaystyle W^{\mathrm{capped}}(y)\coloneqq W(\min(y,y_{\max})).$

For concreteness, $y_{\max}=30$ is sufficient to derive our competitive ratio.
To summarize, our distribution $\mathcal{W}$ is defined as follows: First draw
$(\bm{y}_{1},\ldots)\sim\mathcal{D}$, and then output
$(\bm{x}_{1},\bm{x}_{2},\ldots)$ where
$\bm{x}_{j}=W^{\mathrm{capped}}(\bm{y}_{j})$. Since this $W^{\mathrm{capped}}$
is increasing, the output of $\mathcal{W}$ is negatively associated.
Furthermore, it is shift-invariant just as $\mathcal{D}$ is.

We have verified that $\mathcal{W}$ satisfies the first two criteria of
Theorem 7 and so are left with verifying the third criteria, that Equation 26
holds. We verify it by straightforward computation, and all of our code is in
a publicly available Colab notebook.333To see our code, go to
https://colab.research.google.com/drive/1mykkfnPj-
PuEV02GrOkLlnGFKromTkU1?usp=sharing. The first $r$ elements of $\mathcal{W}$
take on only finitely many values (though exponential in $r$). We fully
compute a representation of this distribution for each $r=1,\ldots,m-1$. Given
this representation, we are able to exactly compute the distribution for
$\bm{w}^{(r)}$. Verifying Equation 26 amounts to verifying that $g(t)\geq 0$
for all $t\in[0,1]$ where

$\displaystyle
g(t)\coloneqq\left(1-t-\frac{m-r}{m}\cdot\left(1-t^{\frac{m}{m-r}}\right)\right)-\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{W}}\left[\left(\bm{w}^{(r)}-t\right)_{+}\right].$

The term
$\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{W}}\left[\left(\bm{w}^{(r)}-t\right)_{+}\right]$
is piecewise linear with kinks at the finitely many points on which
$\bm{w}^{(r)}$ is supported. The other term is convex, so between kinks, $g$
is convex. Furthermore, it is Lipschitz. Off-the-shelf minimization procedures
will find the minimum of a one-dimensional, Lipschitz, and convex function on
an interval to arbitrary accuracy. We use them to verify $h(t)\geq 0$ on each
interval between kinks, ensuring that $h(t)\geq 0$ for all $t\in[0,1]$.

As demonstrated in the Colab notebook, for our choice of $\mathcal{W}$,
Equation 26 doesn’t hold for every choice of $p$. We found that for $m=6$, it
holds for all $p\in\\{0.05,0.06,\ldots,0.99\\}$, but not for
$p=\\{0.01,\ldots,0.05\\}$. In particular, it holds for $p=0.48$, which is the
setting that maximized the resulting competitive ratio.

As a result of the above analysis and Theorem 7, we have constructed an
$(F,m)$-discrete OCS for the $F$ defined in Equation 27, restated here for
convenience.

$\displaystyle
F(n)\coloneqq\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mathcal{W}}\left[\prod_{\ell=1}^{n}(1-\bm{x}_{\ell})\right]$

Once again, we use computation (also in the Jupyter notebook) to determine
$F(n)$. Up to $n_{\max}=10$, we store a full representation of the first
$n_{\max}$ elements from $\mathcal{W}$ and then use it to compute $F(n)$ for
$n\leq n_{\max}$. For $n>n_{\max}$, we can upper bound $F(n)\leq
F(n_{\max})\cdot(\textstyle\frac{F(n_{\max})}{F(n_{\max}-1)})^{n-n_{\max}}$ as
a result of the following Lemma.

######  Lemma 8.7.

For the function $F$ defined in Equation 27, the quantity
$\frac{F(n+1)}{F(n)}$ is decreasing in $n$.

Our proof of Lemma 8.7 holds for any increasing function $W$ (so will also
work for $W^{\mathrm{capped}}$), but is specialized to our choice for
$\mathcal{D}$ from Definition 13.

###### Proof.

Draw $\bm{y},\bm{z}\sim\mathcal{D}(y,z)$ and then set
$\bm{a}_{k}=\mathrm{Ber}(W(\bm{y}_{k}))$. We can think of $\bm{a}_{k}$ as
indicating whether the vertex $i$ wins the $k^{\mathrm{th}}$ time it appears.
Then the following equation for $F$ is equivalent to Equation 27.

$\displaystyle
F(n)=\mathop{{\operatorname{{Pr}}}\/}\left[\bm{a}_{1}=\cdots=\bm{a}_{n}=0\right]$

Therefore,

$\displaystyle\frac{F(n+1)}{F(n)}=\mathop{{\operatorname{{Pr}}}\/}\left[\bm{a}_{n+1}=0\mid\bm{a}_{1}=\cdots=\bm{a}_{n}=0\right]$

We want the above quantity to be less than or equal to

$\displaystyle\frac{F(n)}{F(n-1)}=\mathop{{\operatorname{{Pr}}}\/}\left[\bm{a}_{n+1}=0\mid\bm{a}_{2}=\cdots=\bm{a}_{n}=0\right]$

using $E$ to indicate the event [$\bm{a}_{j}=0$ for each
$j\in\\{2,\ldots,n\\}$], proving that
$\frac{F(n+1)}{F(n)}\leq\frac{F(n)}{F(n-1)}$ is equivalent to

$\displaystyle\operatorname{{Pr}}[\bm{a}_{n+1}=0\mid
E,\bm{a}_{1}=0]\leq\operatorname{{Pr}}[\bm{a}_{n+1}=0\mid E]$ (36)

For each $k=1,\ldots,n$, We define the stochastic function
$\bm{h}_{k}:\mathds{R}_{\geq 0}\to\mathds{R}_{\geq 0}$,

$\displaystyle\bm{h}_{k}(z)=(\bm{z}_{k+1}\mid\bm{z}_{1}=z,\bm{a}_{1}=\cdots=\bm{a}_{k}=0).$

We claim that $\bm{h}_{k}$ is a stochastically increasing function for all
$k=1,\ldots,n$. For $k=1$ we wish to prove the following map is stochastically
increasing

$\displaystyle z\mapsto(\bm{z}_{2}\mid\bm{z}_{1}=z,a_{1}=0).$

Recall that by Definition 13, $\bm{z}_{2}$ and $\bm{z}_{1}$ are related as
follows.

  1. 1.

With probability equal to $p$ (the hyperparameter in Definition 13),
$\bm{z}_{2}=0$. If this happens, then $\bm{y}_{1}=\bm{z}_{1}$.

  2. 2.

With probability $1-p$, $\bm{z}_{2}=\bm{z}_{1}+1$ and then $\bm{y}_{1}=0$

If the probability that the first branch happens conditioned on
$(\bm{z}_{1}=z,a_{1}=0)$ is decreasing in $z$ then $\bm{h}_{1}$ is
stochastically increasing. We compute that probability using Bayes theorem.

$\displaystyle\operatorname{{Pr}}[\bm{y}_{1}=z\mid a_{1}=0,\bm{z}_{1}=z]$
$\displaystyle=\frac{\operatorname{{Pr}}[a_{1}=0\mid\bm{y}_{1}=z,z_{1}=z]\cdot\operatorname{{Pr}}[\bm{y}_{1}=z\mid\bm{z}_{1}=z]}{\operatorname{{Pr}}[a_{1}=0\mid\bm{z}_{1}=z]}$
$\displaystyle=\frac{(1-W(z))}{p\cdot(1-W(z))+(1-p)\cdot(1-W(-1))}\cdot\operatorname{{Pr}}[\bm{y}_{1}=z\mid\bm{z}_{1}=z]$

The quantity $\operatorname{{Pr}}[\bm{y}_{1}=zfor\mid\bm{z}_{1}=z]$ is a
constant in $z$ (it is just equal to $p$). Since $W$ is increasing, the above
is decreasing in $z$. Therefore, $\bm{h}_{1}$ is stochastically decreasing.

For $k\geq 2$, by the inductive hypothesis, we may that assume $\bm{h}_{k-1}$
is stochastically increasing. Then,

$\displaystyle\bm{h}_{k}(z)$
$\displaystyle=(\bm{z}_{k+1}\mid\bm{z}_{1}=z,\bm{a}_{1}=\cdots=\bm{a}_{k}=0)$
$\displaystyle=(\bm{z}_{k+1}\mid\bm{z}_{2}=\bm{z}^{\prime},\bm{a}_{2}=\cdots=\bm{a}_{k}=0)\quad\quad\text{where
}\bm{z}^{\prime}\sim(\bm{z}_{2}\mid\bm{z}_{1}=z,a_{1}=0)$ (8.1)
$\displaystyle=(\bm{h}_{k-1}\circ\bm{h}_{1})(z)$ ($\mathcal{D}$ is shift
invariant)

and since both $\bm{h}_{k-1}$ and $\bm{h}_{1}$ are stochastically increasing,
so is $\bm{h}_{k}$. We are now ready to prove Equation 36. If we condition on
$\bm{a}_{1}=0$, then the distribution of $\bm{z}_{2}$ is that of a
$\mathrm{Geo}(p)+1$. If we do not condition on $\bm{a}_{1}$, that distribution
is just $\mathrm{Geo}(p)$. Since $\bm{h}_{n}$ is stochastically increasing and
$\mathrm{Geo}(p)+1$ stochastically dominates $\mathrm{Geo}(p)$, the
distribution of $\bm{z}_{n+1}$ conditioned on $\bm{a}=0$ and $E$
stochastically dominates the distribution of $\bm{z}_{n+1}$ just conditioning
on $E$. The quantity $\bm{y}_{n+1}$ is a stochastically increasing function of
$\bm{z}_{n+1}$ and the quantity $\bm{a}_{n+1}$ is a stochastically increasing
function of $\bm{y}_{n+1}$. Therefore, the probability $\bm{a}_{n+1}=0$
conditioned on $E$ and $\bm{a}_{1}=0$ is lower than just conditioning on $E$.
Equation 36 holds and therefore the desired result does as well. ∎

As a consequence of the above, we have proven the existence of an $(F,6)$-OCS
for the $F$ in Figure 1.

##  9 Proof of Lemma 2.1

See 2.1

###### Proof.

We prove that there is no $2$-OCS satisfying both of the following.

  1. 1.

The probability a vertex is picked in a single time step it appears is
$\frac{1}{2}$

  2. 2.

Let $j_{1},j_{2}$ be two time steps vertex $i$ appears in for which $i$ never
appears in a time step between $j_{1}$ and $j_{2}$. Then, the probability $i$
is selected in $j_{1}$ or $j_{2}$ is strictly greater than $\frac{5}{6}$.

This implies Lemma 2.1. Suppose, for the sake of contradiction, such an OCS
exists. Feed in the following three pairs into the OCS. $((a,b),(b,c),(a,b))$.
In the first round, the OCS must pick $a$ and $b$ each with probability
$\frac{1}{2}$.

Then, in order to guarantee that $b$ is picked in one of the first two time
steps with probability more than $\frac{5}{6}$, if $a$ is picked in the first
round, $b$ must be picked in the second round with probability
$p_{2}>\textstyle\frac{2}{3}$.

We also need the probability that $c$ is picked in the second round to be
$\frac{1}{2}$. To guarantee this, in the case where $b$ is picked in the first
round, we need $c$ to be picked with probability $p_{2}$. Hence, there is a
$\frac{1}{2}\cdot p_{2}$ probability that $b$ is picked in the first round and
$c$ in the second. Let $p_{3}$ be the probability that $a$ is picked in this
case. If $p_{3}\geq\textstyle\frac{1}{2}$, then there is a

$\displaystyle\frac{1}{2}\cdot p_{2}\cdot p_{3}>\frac{1}{6}$

chance that $b$ is not selected in the second or third round. On the other
hand, if $p_{3}\leq\textstyle\frac{1}{2}$, then there is a

$\displaystyle\frac{1}{2}\cdot p_{2}\cdot(1-p_{3})>\frac{1}{6}$

chance that $a$ is not selected in the first or third round. In both cases, we
have a contradiction. ∎

## References

  * [AGKM11] Gagan Aggarwal, Gagan Goel, Chinmay Karande, and Aranyak Mehta.  Online vertex-weighted bipartite matching and single-bid budgeted allocations.  In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1253–1264. SIAM, 2011.
  * [BJN07] Niv Buchbinder, Kamal Jain, and Joseph Seffi Naor.  Online primal-dual algorithms for maximizing ad-auctions revenue.  In European Symposium on Algorithms, pages 253–264. Springer, 2007\.
  * [DH09] Nikhil R Devanur and Thomas P Hayes.  The adwords problem: online keyword matching with budgeted bidders under random permutations.  In Proceedings of the 10th ACM conference on Electronic commerce, pages 71–78, 2009.
  * [DHK+16] Nikhil R Devanur, Zhiyi Huang, Nitish Korula, Vahab S Mirrokni, and Qiqi Yan.  Whole-page optimization and submodular welfare maximization with online bidders.  ACM Transactions on Economics and Computation (TEAC), 4(3):1–20, 2016.
  * [DJSW19] Nikhil R Devanur, Kamal Jain, Balasubramanian Sivan, and Christopher A Wilkens.  Near optimal online algorithms and fast approximation algorithms for resource allocation problems.  Journal of the ACM (JACM), 66(1):1–41, 2019.
  * [FHK+10] Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S Mirrokni, and Cliff Stein.  Online stochastic packing applied to display ad allocation.  In European Symposium on Algorithms, pages 182–194. Springer, 2010\.
  * [FHTZ20] M. Fahrbach, Z. Huang, R. Tao, and M. Zadimoghaddam.  Edge-weighted online bipartite matching.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 412–423, Los Alamitos, CA, USA, nov 2020. IEEE Computer Society.
  * [FKM+09] Jon Feldman, Nitish Korula, Vahab Mirrokni, Shanmugavelayutham Muthukrishnan, and Martin Pál.  Online ad assignment with free disposal.  In International workshop on internet and network economics, pages 374–385. Springer, 2009.
  * [FMMM09] Jon Feldman, Aranyak Mehta, Vahab Mirrokni, and Shan Muthukrishnan.  Online stochastic matching: Beating 1-1/e.  In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 117–126. IEEE, 2009.
  * [GHH+21] Ruiquan Gao, Zhongtian He, Zhiyi Huang, Zipei Nie, Bijun Yuan, and Yan Zhong.  Improved online correlated selection, 2021.
  * [GKM+19] Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, and David Wajc.  Online matching with general arrivals.  In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 26–37. IEEE, 2019.
  * [GKS19] Buddhima Gamlath, Sagar Kale, and Ola Svensson.  Beating greedy for stochastic bipartite matching.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2841–2854. SIAM, 2019.
  * [GM08] Gagan Goel and Aranyak Mehta.  Online budgeted matching in random input models with applications to adwords.  In SODA, volume 8, pages 982–991, 2008.
  * [HKT+18] Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang, and Xue Zhu.  How to match when all vertices arrive online.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of computing, pages 17–29, 2018.
  * [HMZ11] Bernhard Haeupler, Vahab S Mirrokni, and Morteza Zadimoghaddam.  Online stochastic weighted matching: Improved approximation algorithms.  In International workshop on internet and network economics, pages 170–181. Springer, 2011.
  * [HPT+19] Zhiyi Huang, Binghui Peng, Zhihao Gavin Tang, Runzhou Tao, Xiaowei Wu, and Yuhao Zhang.  Tight competitive ratios of classic matching algorithms in the fully online model.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2875–2886. SIAM, 2019.
  * [HTWZ19] Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang.  Online vertex-weighted bipartite matching: Beating 1-1/e with random arrivals.  ACM Transactions on Algorithms (TALG), 15(3):1–15, 2019.
  * [JDP83] Kumar Joag-Dev and Frank Proschan.  Negative Association of Random Variables with Applications.  The Annals of Statistics, 11(1):286 – 295, 1983.
  * [JL14] Patrick Jaillet and Xin Lu.  Online stochastic matching: New algorithms with better bounds.  Mathematics of Operations Research, 39(3):624–646, 2014.
  * [KMT11] Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi.  Online bipartite matching with unknown distributions.  In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 587–596, 2011.
  * [KP00] Bala Kalyanasundaram and Kirk R Pruhs.  An optimal deterministic algorithm for online b-matching.  Theoretical Computer Science, 233(1-2):319–325, 2000.
  * [KVV90] Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani.  An optimal algorithm for on-line bipartite matching.  In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pages 352–358, 1990.
  * [Meh13] Aranyak Mehta.  Online matching and ad allocation.  Foundations and Trends® in Theoretical Computer Science, 8(4):265–368, 2013.
  * [MGS12] Vahideh H Manshadi, Shayan Oveis Gharan, and Amin Saberi.  Online stochastic matching: Online actions based on offline statistics.  Mathematics of Operations Research, 37(4):559–573, 2012.
  * [MGZ12] Vahab S Mirrokni, Shayan Oveis Gharan, and Morteza Zadimoghaddam.  Simultaneous approximations for adversarial and stochastic online budgeted allocation.  In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 1690–1701. SIAM, 2012.
  * [MP12] Aranyak Mehta and Debmalya Panigrahi.  Online matching with stochastic rewards.  In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 728–737. IEEE, 2012.
  * [MR01] Alfred Müller and Ludger Rüschendorf.  On the optimal stopping values induced by general dependence structures.  Journal of applied probability, pages 672–684, 2001.
  * [MSVV07] Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani.  Adwords and generalized online matching.  Journal of the ACM (JACM), 54(5):22–es, 2007.
  * [MWZ14] Aranyak Mehta, Bo Waggoner, and Morteza Zadimoghaddam.  Online stochastic matching with unequal probabilities.  In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 1388–1404. SIAM, 2014.
  * [MY11] Mohammad Mahdian and Qiqi Yan.  Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps.  In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 597–606, 2011.
  * [SS07] Moshe Shaked and J George Shanthikumar.  Stochastic orders.  Springer Science & Business Media, 2007.