# Approximating Optimum Online for Capacitated Resource Allocation111This work
was done in part while the authors were visiting the Simons Institute for the
Theory of Computing. Research supported in part in by Deutsche
Forschungsgemeinschaft (DFG, German Research Foundation), Project No.
437739576, NSF Awards CCF2209520, CCF2312156, and a gift from CISCO.

Alexander Braun222University of Bonn<EMAIL_ADDRESS>Thomas
Kesselheim333University of Bonn<EMAIL_ADDRESS>Tristan
Pollner444Stanford University<EMAIL_ADDRESS>Amin Saberi555Stanford
University<EMAIL_ADDRESS>
###### Abstract

We study online capacitated resource allocation, a natural generalization of
online stochastic max-weight bipartite matching. This problem is motivated by
ride-sharing and Internet advertising applications, where online arrivals may
have the capacity to serve multiple offline users.

Our main result is a polynomial-time online algorithm which is
$(\nicefrac{{1}}{{2}}+\kappa)$-approximate to the optimal online algorithm for
$\kappa=0.0115$. This can be contrasted to the (tight)
$\nicefrac{{1}}{{2}}$-competitive algorithms to the optimum offline benchmark
from the prophet inequality literature. Optimum online is a recently popular
benchmark for online Bayesian problems which can use unbounded computation,
but not “prophetic” knowledge of future inputs.

Our algorithm (which also works for the case of stochastic rewards) rounds a
generalized LP relaxation from the unit-capacity case via a two-proposal
algorithm, as in previous works in the online matching literature. A key
technical challenge in deriving our guarantee is bounding the positive
correlation among users introduced when rounding our LP relaxation online.
Unlike in the case of unit capacities, this positive correlation is
unavoidable for guarantees beyond $\nicefrac{{1}}{{2}}$. Conceptually, our
results show that the study of optimum online as a benchmark can reveal
problem-specific insights that are irrelevant to competitive analysis.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Techniques
    2. 1.2 Capacitated Allocation Lacks Negative Correlation
    3. 1.3 Interlude on an Equivalent View: Online Combinatorial Auctions
    4. 1.4 Additional Related Work
    5. 1.5 Paper Organization
  2. 2 Formal Problem Statement and Preliminaries
    1. 2.1 Pivotal Sampling
  3. 3 The Algorithm: A Two-Step Approach
  4. 4 Analysis: Beating a 1/2-Approximation
    1. 4.1 Analysis for Early Pairs
    2. 4.2 Analysis for Late Pairs implies Theorem 4.1
      1. 4.2.1 Proof of Lemma 4.5 (i)
      2. 4.2.2 Proof of Lemma 4.5 (ii)
    3. 4.3 Bounding the Correlation — Proof of Lemma 4.9
  5. 5 Analyzing the Sample-based Algorithm
  6. 6 Conclusion and Future Directions
  7. A Informative Examples and Observations
    1. A.1 The Generalization of [BDL22] Fails
    2. A.2 Positive Correlation is Required
    3. A.3 On the Gap of (LPon)
    4. A.4 A Bound Depending on min c_t
  8. B Deferred Proofs
    1. B.1 Proof of Theorem 1.5
    2. B.2 Proof of 2.1
    3. B.3 Proof of 4.14
  9. C Beyond Bernoulli Distributions
  10. D Stochastic Rewards

##  1 Introduction

We study an _online capacitated allocation problem_ , in which users
$\\{1,2,\ldots,n\\}$ should be assigned to resources arriving online.
Specifically, at each timestep $t\in\\{1,2,\ldots,T\\}$, a new resource $t$
arrives and its capacity $c_{t}$ and the values $v_{i,t}\geq 0$ for every user
$i\in[n]$ are sampled from a known distribution $\mathcal{D}_{t}$. Upon the
arrival of a resource, we observe its realized capacity and values, and must
irrevocably decide which users to allocate to it. Our goal is to maximize
social welfare, i.e., the sum of the values of assigned user-resource pairs.

This problem naturally arises in a number of settings, for example in the
context of ride-sharing: after a spike in demand (e.g. at the arrival of a
flight, or at the end of a large concert), waiting passengers need to be
assigned to cabs who become available online. Another example is online
advertising, which initiated the vast literature on online Bayesian matching
[FMMM09], where ads should be assigned to search queries arriving online.
Further examples are abundant: the assignment of orders to trucks by a
shipping fulfillment center, the procurement of goods for stores with limited
inventories, etc. Our formulation goes beyond the intensely-studied setting
where each online resource can be matched to at most one offline node (e.g.
[BK10, HMZ11, MGS12, JL13, EFGT20, BSSX20, HS21, TWW22, HSY22]). In many cases
resources have capacity larger than one; multiple passengers can share a cab
and multiple ads can be displayed under a search query.

The literature has studied this problem from the “prophet inequality”
perspective, designing algorithms which compare favorably to the _optimum
offline_ algorithm which sees all realizations upfront. In particular, for
online capacitated allocation, it is possible to obtain $\nicefrac{{1}}{{2}}$
of the optimum offline benchmark [FGL15, DFKL20], and that is the best
possible [KS78].

Still, comparing to the optimum offline algorithm as a benchmark might be too
pessimistic in Bayesian settings. Its “prophetic” access to future
realizations is unattainable for online algorithms (see [PPSW21] for further
discussion). Therefore, a recent line of work (also including, e.g., [ANSS19,
BDL22, DGR+23]) has shifted attention towards the following question: _how
well can we approximate the optimal (computationally unbounded) online
algorithm in polynomial time?_

In other words, how much must we lose when restricting to efficient algorithms
instead of solving the optimal dynamic program? On the one hand, even for unit
capacities it is PSPACE-hard to approximate the optimum online algorithm
within some absolute constant $1-\epsilon$ [PPSW21].

Luckily, approximations strictly better than $\nicefrac{{1}}{{2}}$ exist for
unit capacities: [PPSW21] gave a $0.51$-approximate algorithm, later improved
to 0.52 [SW21], $1-\nicefrac{{1}}{{\mathrm{e}}}\approx 0.632$ [BDL22], and
$0.652$ [NSW23]. Motivated by this, we ask:

_Can we obtain a better than $\nicefrac{{1}}{{2}}$-approximate algorithm to
the optimal (computationally unbounded) online algorithm beyond unit-capacity
allocations?_

Our main result is to answer this question in the affirmative. In particular,
we show that for online capacitated resource allocation problems, we can beat
$\nicefrac{{1}}{{2}}$ by a constant.

######  Theorem 1.1.

For online capacitated allocation, there exists a polynomial time
$\left(\nicefrac{{1}}{{2}}+\kappa\right)$-approximation to the social welfare
of the optimal online algorithm, for a constant ${\kappa\geq 0.0115}$.

Interestingly, through the lens of prophet inequalities, the unit-capacity and
the general capacity variant of the problem behave nearly identically. These
variants (and more general ones) can all be handled by the same algorithmic
template and techniques for the unit-capacity case directly carry over (for
example, applying a $\nicefrac{{1}}{{2}}$-balanced online contention
resolution scheme (OCRS) to each offline user). As we will discuss, studying
capacitated resource allocation with the optimum online benchmark leads to
technical challenges distinct from the unit-capacity case, and reveals
differences that do not arise in competitive analysis. Our work hence gives
evidence for the richness of studying optimum online as a benchmark.

We also provide an extension to where allocations are probabilistically
successful, motivated by our initial example of Internet advertising. As in
the literature on online matching with stochastic rewards [MP12, HZ20, GU23],
after displaying ads under a search request, typically the advertiser is only
charged if the ad is eventually clicked. This is typically modeled as
happening with known probability called the click-through-rate. We hence
update our setting so that after allocating at most $c_{t}$ users to the
resource $t$, each user $i$ is _successfully allocated_ with known probability
$q_{i,t}$. If an offline user $i$ is not successfully allocated, it remains
available to be matched in future rounds; however, online arrivals do not get
to adaptively pick new allocations.

######  Theorem 1.2.

For online capacitated allocation with stochastic rewards, there exists a
polynomial time $\left(\nicefrac{{1}}{{2}}+\kappa\right)$-approximation to the
social welfare of the optimal online algorithm, for a constant ${\kappa\geq
0.0115}$.

Note Theorem 1.1 is the special case of Theorem 1.2 in which all successes are
deterministic, i.e. success probabilities $q_{i,t}=1$ for every $i$, $t$.

###  1.1 Our Techniques

Our algorithm rounds an LP relaxation online while introducing a controllable
amount of positive correlation among offline users. For each online arrival
$t$, we apply two rounds of pivotal sampling to the unallocated offline nodes,
to guarantee never “over-allocating” $t$ beyond its remaining capacity. In
each round, we only randomly allocate a subset of this sampled group to avoid
large positive correlation between users.

Throughout, in the main body of the paper, we focus on the special case where
resource arrivals are “Bernoulli” (i.e., in step $t$, resource $t$ with known
capacity $c_{t}$ and known values $v_{i,t}\geq 0$ arrives with probability
$p_{t}$ and does not show up with probability $1-p_{t}$.)

##### LP relaxation.

In order to bound the social welfare achieved by the optimum online algorithm,
we will use a linear program (LP) relaxation with variables $\\{x_{i,t}\\}$.
The variables can be interpreted as the probabilities we would like an online
algorithm to assign each user $i$ to resource $t$ (see Section 2). We require
that at most $p_{t}\cdot c_{t}$ users are allocated to resource $t$ in
expectation, and also make use of an “online constraint” which does not hold
for offline algorithms, as in [PPSW21, TT22]. In particular, for online
algorithms, the arrival of resource $t$ and the event that user $i$ is
unallocated at $t$ are independent. We account for stochastically successful
allocations in this constraint and the LP’s objective via the independence of
success along edges from an online algorithm’s allocation decisions.

##### A two-proposal algorithmic approach.

Our algorithm rounds an optimal LP solution online such that (i) for every
resource $t$, we do not allocate more users than its capacity, and (ii) every
pair $(i,t)$ is successfully allocated with probability
$(\nicefrac{{1}}{{2}}+\kappa)\cdot x_{i,t}\cdot q_{i,t}$ for a constant
$\kappa:=0.0115$. To achieve guarantees (i) and (ii), we use a two-proposal
algorithm inspired by the algorithm used for matching by [PPSW21]. For every
resource $t$, we run up to two rounds; in each we propose to a subset of users
whose size does not exceed the remaining capacity and a random subset of users
accepts.

While our LP relaxation and high-level framework are similar to [PPSW21], new
ideas are needed for the specifics of the algorithm and (more importantly) its
analysis. For example, when a new resource $t$ arrives, we would like to
sample a subset of users such that $i$ is included with probability
proportional to $x_{i,t}$. In the matching case, summing $x_{i,t}/p_{t}$ over
all users $i$ never exceeds one, and hence, the vector
$\left(x_{i,t}/p_{t}\right)_{i}$ naturally forms a probability distribution
over users. This is no longer true in our more general capacitated allocation
problem. Naïvely sampling users _independently_ with the given marginals has
the issue that we might exceed the capacity of resource $t$. We instead rely
on the technique of _pivotal sampling_ (also known as _dependent rounding_) to
ensure that the sampled set of users never exceeds the capacity of resource
$t$ and that sampled users are negatively correlated. Via the pivotal sampling
subroutine we get a _first proposal set_ of users. We note that in order to
obtain this first proposal set, we apply the pivotal sampling in a history-
agnostic way. That is, we may include previously successfully allocated users
in the proposal set for resource $t$ at first. From the proposal set, we then
randomly allocate each available user $i$ with some probability. This is
essentially done according to a $(\nicefrac{{1}}{{2}}+\kappa)$-balanced online
contention resolution scheme (OCRS).

After this allocation process, there might remain a gap between the capacity
of resource $t$ and the number of allocated users. We crucially exploit this
gap by drawing a _second proposal set_ of users by another call of the pivotal
sampling subroutine with reduced marginal probabilities. The reduction is
precisely to ensure that the capacity of resource $t$ is not exceeded.
Afterwards, we probabilistically assign a subset of these users, with a
carefully chosen downsampling function.

##### Analyzing the algorithm.

For the analysis, we distinguish for each pair $(i,t)$ whether it is assigned
with probability at least $(\nicefrac{{1}}{{2}}+\kappa)\cdot x_{i,t}\cdot
q_{i,t}$ already from the first proposal, or requires the second proposal to
reach this threshold. In the first case, the analysis proceeds in a
straightforward way via the calculations originally from the OCRS literature
(see e.g. [EFGT20]).

For the remaining pairs $(i,t)$, bounding their contribution to the social
welfare requires analyzing the second proposal, and doing so is our main
technical contribution. For the second proposal along $(i,t)$ to contribute to
social welfare, clearly user $i$ needs to be unallocated just before $t$
arrives. Furthermore, we are required to reduce the marginal probability that
$i$ is sampled in the second proposal depending on the number of allocated
users in $t$’s first proposal. This number in turn depends on the availability
of _other_ users $j\neq i$. In particular, if a user $j$ is already assigned
before the arrival of resource $t$, even when sampled as a first proposal, we
cannot allocate the user. This increases the remaining capacity of resource
$t$, which is beneficial for the marginal reduction required in our second
proposal.

Conversely, if we condition on other users $j\neq i$ being free before the
arrival of resource $t$, it leads to a _larger_ decrease of the marginal
probabilities in our second proposal. Still, this implies a decrease of the
social welfare contribution of $(i,t)$. The relevant technical question, then,
is if we condition on $i$ being free before $t$ arrives (necessary for $(i,t)$
to contribute to social welfare), how much can the conditional probabilities
of users $j\neq i$ being free increase? Equivalently, how significantly can
the availabilities of offline users be correlated?

In the matching case this challenge was readily handled by showing negative
correlation. While this is not possible for our problem (Section 1.2), we show
that our algorithm obtains a good approximation if it can just avoid
introducing “large” amounts of positive correlation. In the most technical
part of our paper, we show our two-proposal algorithm achieves this by
inductively tracking the availability of users over multiple rounds. In
particular, we show the probability of both users being free at time $t$ is at
most the product of the users’ individual probabilities of being free,
multiplied by $f\left(\sum_{t^{\prime}<t}x_{i,t^{\prime}}\cdot
q_{i,t^{\prime}}\right)$, for
$f(z):=1+z\cdot\left(\frac{(0.5+\kappa)^{2}}{1-z\cdot(0.5+\kappa)}\right)$.
Interestingly, the point at which we evaluate the function $f$ does not depend
on user $j$ at all.

###  1.2 Capacitated Allocation Lacks Negative Correlation

Even in the case where every success probability $q_{i,t}$ equals $1$, the
potential positive correlation among offline users underlies the challenge for
capacities exceeding 1. For example, a tempting naïve approach for general
capacities is to directly reduce to the unit-capacity case: upon the arrival
of a resource with capacity $c_{t}$, model this as $c_{t}$ resources with unit
capacities, and simply run the algorithms from prior work. Unfortunately, this
fails; a crucial assumption of the relevant literature is that arrivals are
independent across different rounds, and introducing positive correlation
across arrivals can be extremely problematic for existing algorithms. For
example, consider the natural generalization of the algorithm by [BDL22]: in
round $t$, let users propose to the arriving resource and allocate the $c_{t}$
proposing users with the highest values. Here the positive correlation
introduced can create severe problems.

######  Observation 1.3.

For any $\epsilon>0$, there exists an online capacitated allocation instance
where the (generalized) algorithm of [BDL22] is no more than
$\epsilon$-approximate with respect to the welfare achieved by the optimal
(computationally unbounded) online algorithm.

The formal proof can be found in Appendix A. The approach of [BDL22] is LP-
based and one of the crucial steps is an upper bound on the probability that a
subset of users is matched simultaneously. Intuitively speaking, their bound
can be interpreted as a form of negative correlation among the offline users
with respect to the LP variables.666It is possible to extend the algorithm of
[BDL22] to one with the same approximation ratio which furthermore has full
negative correlation between offline nodes. Unfortunately, simple examples
show that in our case positive correlation is _required_ to go beyond an
approximation ratio of $\nicefrac{{1}}{{2}}$.

######  Observation 1.4.

Any algorithm for online capacitated allocation which has an approximation
ratio better than $\nicefrac{{1}}{{2}}$ with respect to (LPon) must create
positive correlation between the events of offline users being available.

A formal version of the argument can be found in Appendix A. We note that the
proof even rules out the “negative correlation with respect to the LP” showed
by [BDL22], also used by follow-up work [NSW23]. In contrast to the line of
work by [BDL22] and [NSW23], Papadimitriou _et al._ [PPSW21] gave a different
algorithm for the unit-capacity case which operates in the mentioned “two-
proposals framework” that has been successful for multiple problems in the
online matching literature [FMMM09, MGS12]. Critically, their analysis shows
that almost all of the matches create negative correlation of offline nodes
(in fact, satisfying the very strong property of _negative association_).
While our algorithm is inspired by the two-proposals framework, the example
above demonstrates that there is no reasonable way to generalize this
statement to the capacitated case while beating a
$\nicefrac{{1}}{{2}}$-approximation.

###  1.3 Interlude on an Equivalent View: Online Combinatorial Auctions

Online capacitated resource allocation problems can also be interpreted in the
context of _online combinatorial auctions_ — a commonly studied setting in the
prophet inequality literature, as in e.g. [FGL15, DFKL20, CC23] and many
others. Here, online arrivals correspond to _buyers_ and offline nodes are
_items_. Our capacities translate to the assumption that each buyer $t$ has a
_$c_{t}$ -demand_ valuation function, interpolating between unit-demand and
fully additive valuations.

In online capacitated allocation, we assume valuations are given upfront to
the algorithm designer through a centralized planner. This view is (at first
glance) less realistic for online combinatorial auctions — here we would
expect buyers to report their own valuations, and would need to consider
incentives. Luckily, applying recent work of [BHK+24], we can argue that our
algorithm can be made dominant strategy incentive-compatibility (DISC) if we
bound the demand size of buyers by a constant (a reasonable assumption for
motivating applications). In particular, Theorem 1.1 implies the following
result which we formally prove in Section B.1.

######  Theorem 1.5.

Say every buyer $t$ samples a $c_{t}$-demand valuation function, where $c_{t}$
is upper bounded by a constant. Then, for online combinatorial auctions, there
exists a polynomial-time DSIC mechanism giving a
$\left(\nicefrac{{1}}{{2}}+\kappa\right)$-approximation to the social welfare
of the optimal online algorithm.

Note that our main Theorem 1.1 does not require any upper bounds on the
capacities $c_{t}$. In particular, the capacities $c_{t}$ can be as large as
the number of offline users. The upper bound on $c_{t}$ in the combinatorial
auction interpretation is only required such that the reduction from [BHK+24]
runs in polynomial time.

###  1.4 Additional Related Work

Online resource allocation problems have gained attention in the last decades
due to a plethora of applications introduced by large marketplaces (see e.g.
[Meh13]).

A particularly well-studied variety of such problems is _online matching_. As
initiated by [KVV90], here we have a set of offline vertices and a set of
vertices arriving online. Upon arrival, online nodes reveal a subset of
offline nodes they could be matched to, and we can allocate at most one that
is still available. [KVV90] give an online algorithm for this problem that
achieves a $(1-1/e)$-approximation to the value of the best possible matching
in hindsight. This guarantee was later extended to vertex-weighted instances,
where offline vertices might have different values [AGKM11]. The case we
consider where edges are only successful with known probability has also been
studied in the literature, often going by _online matching with stochastic
rewards_ [MP12, MWZ15, HZ20, GU23, HJS+23]. When online nodes can adaptively
attempt to “rematch” based on the successful status of edges, the problem is
often called _stochastic probing_ , and it has been studied in both online
[BGL+12, AGM15, BMR20] and offline settings [CIK+09, Ada11, GKS19].

In the most general edge-weighted case, it is unfortunately impossible to
obtain _any_ constant-factor approximation for adversarial arrivals; a recent
line of work studies the case where we relax the requirement of decisions
being irrevocable [FHTZ20, GHH+21, BC21]. But in settings where allocations
cannot be easily reversed, the only other option is to move beyond the
pessimistic assumption of fully adversarial arrivals. The most natural way to
do so is to consider the intermediate model of stochastic arrivals, a
reasonable assumption for settings with large amounts of historical data
available. There is a long line of work designing matching algorithms in such
settings, including edge-weighted problems (e.g. [HMZ11, AHL12, BSSX16,
EFGT20]) and vertex-weighted/unweighted problems (e.g. [FMMM09, MGS12, JL13,
HS21, HSY22]). There is also very recent work studying _correlated_ arrivals
in online stochastic matching [AM23], showing guarantees of half against the
offline benchmark when online nodes are independent across different types
rather than arrival rounds.

Most of the literature on Bayesian online resource allocation problems focuses
on competitive algorithms against the expected offline optimum, also called
prophet inequalities. Originally introduced in the 70s and 80s by [KS78] and
[SC84], statements of this form gained renewed attention in the past decades
due to connections with mechanism design [HKS07, CHMS10, KW19]. In these
mechanisms, a sequence of buyers arrives one-by-one and faces item prices,
buying the most desirable feasible bundle. These mechanisms are incentive
compatible and individually rational by design and lead to desirable
approximation guarantees of the optimum achievable welfare. This explains the
rise of literature in this area during the recent years [FGL15, DFKL20, DKL20,
GW19, CCF+22, BK23]. For more details, we refer to the survey by Lucier
[Luc17].

Typical problems studied in the literature are weighted bipartite matching
(a.k.a. unit-demand combinatorial auctions) as well as its generalizations
towards more general scenarios, such as XOS or subadditive valuations in
combinatorial auctions [FGL15, DFKL20, DKL20, CC23]. In complementing work,
also feasibility constraints such as (poly-)matroids [DK15, KW19, CGKM20],
knapsacks [DFKL20, JMZ22] and beyond [GHK+14, Rub16, BM19] are considered.

The paradigm of _online contention resolution schemes_ (OCRS) has been an
influential technique for proving prophet inequalities. Here, we start with an
LP relaxation of the offline allocation problem and run a rounding procedure
online while observing realizations one-by-one. Introduced by [FSZ16], this
technique has been broadly applied, see e.g. [LS18, EFGT20, PRSW22, FLT+22,
ACCB+23, MMG23]. The LP relaxation we use for our algorithm differs from
standard OCRS settings as there are additional constraints in our LP which are
_only_ valid for online algorithms.

Online allocation has also been studied in the literature where offline nodes
have capacities and can be allocated simultaneously in different rounds
[Ala14, AHL13]. For example, [AHL12] study such a setting and derive
competitive ratios against the offline benchmark which can be improved beyond
$\nicefrac{{1}}{{2}}$ once there is a lower bound of at least 2 on the offline
capacities. The literature has also considered the impact of reusability of
offline nodes [FNS19, DSSX21, FNS22].

###  1.5 Paper Organization

In Section 2, we formally state our problem and review some preliminaries. In
Section 3, we introduce our algorithm and argue that it is well-defined.
Afterwards, in Section 4, we analyze the algorithm’s approximation ratio, the
main technical contribution of our work. We conclude in Section 6 with some
future directions suggested by our work. Appendix A contains a discussion of
informative examples and observations for our problem. In Appendix B, we give
proofs that are deferred from the main body.

In the first part of the main body of our paper, we prove a simpler result for
ease of exposition; the remaining sections and appendices include the details
required to prove our result in full generality. Our algorithm as stated in
Section 3 requires an exponential-time computation; in Section 5 we analyze
the natural Monte Carlo variant and hence provide a truly polynomial-time
algorithm. Our algorithm in Section 3 also focuses on the special case of
Bernoulli arrivals; in Appendix C we show how to extend our techniques to
online arrivals with values and capacities drawn from general distributions.
Finally, for simpler notation, when analyzing our algorithm we consider the
special case where every success probability $q_{i,t}$ is one; in Appendix D
we discuss the necessary changes to prove the result for arbitrary
probabilities.

##  2 Formal Problem Statement and Preliminaries

In the following section, we will give a formal definition of a special case
of our problem. For ease of exposition, in the first part of the main body of
our paper we describe our algorithm and analysis for this special case, and
list the additional details required to solve the general version only
afterwards. We also will review some preliminaries including statements about
our LP relaxation and the basics of pivotal sampling, an important ingredient
for our algorithm.

##### Problem definition.

Recall that we defined the input to our problem as a set of $n$ users $I$
which are available offline. In addition, there is a set of resources $[T]$
which are revealed online in known order. In step $t$, resource $t$ arrives
(also noted as active) independently with known probability $p_{t}$. In
addition, value $v_{i,t}\geq 0$ is user $i$’s value for being served by
resource $t$. Every user can be served by at most one resource; any resource
can serve up to $c_{t}$ many users. We call $c_{t}$ the _capacity_ of resource
$t$ and emphasize that $c_{t}$ can be resource-specific, i.e. we allow
different resources to have different capacities. Upon the arrival of resource
$t$, we observe the random realization if the resource is active, and can
choose which users $I_{t}\subseteq I$ (if any) we would like to allocate to
it, subject to the constraints that each user can be assigned to at most one
resource and $|I_{t}|\leq c_{t}$. If resource $t$ does not arrive, for
convenience, we take $I_{t}=\emptyset$.

Upon assigning $I_{t}$, each $i\in I_{t}$ is _successfully allocated_ with
probability $q_{i,t}$ independently. We denote the successful set by
$S(I_{t})$. More generally, the set $S(J)\subseteq J$ denotes the set of
successful allocations from some allocated set $J$. Our objective is to
maximize the _expected social welfare_ , defined as
$\mathbb{E}\left[\mathrm{SW}\right]:=\mathbb{E}\left[\sum_{t}\sum_{i\in
S(I_{t})}v_{i,t}\right]$.

Our goal is to design a polynomial-time approximation algorithm for this
problem. An algorithm is a _$\zeta$ -approximation_ if for any instance of the
problem, we have
$\mathbb{E}\left[\mathrm{SW}\right]\geq\zeta\cdot\mathrm{OPT}_{\mathrm{on}}$,
where $\mathrm{OPT}_{\mathrm{on}}$ is the expected welfare achieved by the
optimal online algorithm. The optimal online algorithm has unlimited
computational power and also knows all distributions upfront, but only
observes realizations one at a time and needs to make an irrevocable decision
before observing the next realization. Formally, we can define
$\mathrm{OPT}_{\mathrm{on}}$ via a Bellman equation. To this end, let
$\mathrm{OPT}_{\mathrm{on}}(t,J)$ denote the optimum gain achievable from
resources $\\{t,t+1,\ldots,T\\}$ with users $J\subseteq I$ available. Then,
recursively we have

$\displaystyle\mathrm{OPT}_{\mathrm{on}}(t,J)$
$\displaystyle:=(1-p_{t})\cdot\mathrm{OPT}_{\mathrm{on}}(t+1,J)$
$\displaystyle\quad\quad+p_{t}\cdot\max_{J^{\prime}\subseteq
J,|J^{\prime}|\leq c_{t}}\mathbb{E}\left[\sum_{i\in
S(J^{\prime})}v_{i,t}+\mathrm{OPT}_{\mathrm{on}}(t+1,J\setminus
S(J^{\prime}))\right].$

We recall that even in the case of unit capacities with deterministically
successful assignments, it is PSPACE-hard to approximate
$\mathrm{OPT}_{\mathrm{on}}$ within a $(1-\epsilon)$ factor [PPSW21].

##### LP relaxation.

We will use an LP relaxation of the optimum online algorithm which generalizes
that for the unit-capacity and deterministic rewards case [PPSW21, BDL22,
TT22]. It has a variable $x_{i,t}$ for every pair of a user $i$ and a resource
$t$.

$\displaystyle\max\ $ $\displaystyle\sum_{i,t}x_{i,t}\cdot q_{i,t}\cdot
v_{i,t}$ (LPon) s.t. $\displaystyle\sum_{i}x_{i,t}\leq p_{t}\cdot c_{t}$
$\displaystyle\text{for all }t\in[T]$ (1) $\displaystyle\ 0\leq x_{i,t}\leq
p_{t}\cdot\left(1-\sum_{t^{\prime}<t}x_{i,t^{\prime}}\cdot
q_{i,t^{\prime}}\right)$ $\displaystyle\text{for all }i\in I,t\in[T]$ (2)

This LP indeed relaxes the optimal online algorithm: set $x_{i,t}$ to be the
marginal probability that this algorithm attempts to allocate $i$ to $t$.
Constraint (1) holds as any algorithm can only allocate at most $c_{t}$ users
to resource $t$ if it arrives. Constraint (2) only holds for online
algorithms: the event of users being not yet successfully allocated at step
$t$ and the event of resource $t$ arriving are independent. We note it implies
the natural constraint that $\sum_{t}x_{i,t}\cdot q_{i,t}\leq 1$.777Indeed, we
can apply Constraint (2) to $(i,T)$ and observe $\sum_{t}x_{i,t}\cdot
q_{i,t}\leq x_{i,T}+\sum_{t^{\prime}<T}x_{i,t^{\prime}}\cdot
q_{i,t^{\prime}}\leq x_{i,T}+1-\frac{x_{i,T}}{p_{T}}\leq 1.$

######  Observation 2.1.

The optimum objective value of (LPon) upper bounds the gain of optimum online,
i.e., $\mathrm{OPT}\eqref{LP}\geq\mathrm{OPT}_{\mathrm{on}}$.

For completeness the short formal proof is included in Section B.2.

##### Generalized problem definition.

In the above problem definition, we made the simplifying assumption that the
resource arriving at time $t$ has a simple “Bernoulli” distribution
determining if it is active or not. In the general model, in every round, a
resource randomly realizes one of many possible pairs of valuation vectors to
the users and capacities. Formally, in our general model, resource $t$
realizes one of $m$ possible capacities $c_{t,j}$ together with a vector of
values $(v_{i,t,j})_{i}$, where each realization $j$ is sampled with
probability $p_{t,j}$. We highlight that capacities and values during a single
round $t$ can be arbitrarily correlated, although across different rounds we
assume independence. In Appendix C we argue that our LP, algorithm, and
analysis extend to such general settings as well.

###  2.1 Pivotal Sampling

As a part of our online algorithm we invoke the randomized offline rounding
framework of _pivotal sampling_ (also called _Srinivasan rounding_ and
_dependent rounding_) [Sri01, GKPS06]. Imagine we are given marginals
$x_{1},\ldots,x_{n}$ with each $x_{i}\in[0,1]$ and $\sum_{i}x_{i}\leq k$ for
some positive integer $k$. We would like to randomly select at most $k$
indices from $\\{1,2,\ldots,n\\}$ such that $i$ is selected with probability
$x_{i}$. Pivotal sampling selects such a subset while also guaranteeing strong
negative correlation properties between individual indices. It does so by
sequentially choosing a pair of fractional marginals, and applying a
randomized “pivot” operation that makes at least one integral. We formally
state some of the properties of the algorithm below which suffice for our
analysis.

######  Theorem 2.2 (as in [Sri01]).

The pivotal sampling algorithm with input $(x_{i})_{i=1}^{n}$ where
$\sum_{i}x_{i}\leq k$ efficiently produces a random subset of $[n]$, denoted
$\textup{{PS}}(x_{1},\ldots,x_{n})$, with the following properties:

  1. (P1)

For every $i\in[n]$, we have
$\Pr[i\in\textup{{PS}}(x_{1},\ldots,x_{n})]=x_{i}$.

  2. (P2)

The number of elements in $\textup{{PS}}(x_{1},\ldots,x_{n})$ is always at
most $k$.

  3. (P3)

(Negative cylinder dependence) For any $I\subseteq[n]$, we have

$\Pr\left[\bigwedge_{i\in
I}i\in\textup{{PS}}(x_{1},\ldots,x_{n})\right]\leq\prod_{i\in
I}\Pr[i\in\textup{{PS}}(x_{1},\ldots,x_{n})]$

and

$\Pr\left[\bigwedge_{i\in
I}i\notin\textup{{PS}}(x_{1},\ldots,x_{n})\right]\leq\prod_{i\in
I}\Pr[i\notin\textup{{PS}}(x_{1},\ldots,x_{n})]\enspace.$

##  3 The Algorithm: A Two-Step Approach

We begin by a short description of our algorithm, before presenting the
pseudocode in Algorithm 1. First we fix some useful definitions: we say user
$i$ is “allocated to $t$” if it is one of the at most $c_{t}$ users served by
the resource, and “successfully allocated to $t$” if it is allocated to $t$
and $(i,t)$ is successful (recall this is with probability $q_{i,t}$). We say
user $i$ is “free at $t$” or “available at $t$” (or “free”/“available”, if the
context is clear) if just before the arrival of resource $t$, user $i$ has not
yet been successfully allocated to any previous resource.

Our algorithm uses an optimal solution $\\{x_{i,t}\\}$ to (LPon) as input.
After observing if resource $t$ arrives, if so, we sample a set of at most
$c_{t}$ users $\mathsf{FP}_{t}$ (denoting the first proposal for $t$) using
pivotal sampling, such that each user $i$ is selected with marginal
probability $\nicefrac{{x_{i,t}}}{{p_{t}}}$. For every user
$i\in\mathsf{FP}_{t}$, if $i$ is still available, we toss a coin independently
with probability
$\alpha_{i,t}:=\min\left(1,\frac{0.5+\kappa}{1-(0.5+\kappa)\cdot\sum_{t^{\prime}<t}x_{i,t^{\prime}}\cdot
q_{i,t^{\prime}}}\right)$, and allocate user $i$ to resource $t$ if this coin
toss is successful.

After this procedure, we have a number $A_{t}$ of users allocated to resource
$t$, where $A_{t}$ is a random variable which can take values in
$\\{0,\dots,c_{t}\\}$. In order to make use of the remaining space in the
demand size of resource $t$, we allow $t$ to make a second proposal. Again via
the pivotal sampling subroutine, this time with a reduced marginal probability
of $(1-\frac{A_{t}}{c_{t}})\cdot x_{i,t}/p_{t}$ for every user $i$, we sample
a set of users $\mathsf{SP}_{t}$, denoting the second proposal with size at
most $c_{t}-A_{t}$. Among these users, we consider only those $i$ for which
$\alpha_{i,t}=1$, $i$ was free at $t$, and $i$ was not yet allocated to $t$.
For each such user $i$, we allocate to $t$ with probability $\beta_{i,t}$. The
factor $\beta_{i,t}$ is chosen in a way to ensure that $\Pr[i\text{ allocated
to }t]=(0.5+\kappa)\cdot x_{i,t}$, i.e., such that we don’t _overmatch_ any
$(i,t)$.

Algorithm 1

1:$\kappa\leftarrow 0.0115$

2:Solve (LPon) for $\\{x_{i,t}\\}$

3:for each time $t$, if $t$ arrives do $\triangleright$ w.p. $p_{t}$

4: Define users $\mathsf{FP}_{t}:=\textsf{PS}((x_{i,t}/p_{t})_{i\in I})$
$\triangleright$ at most $c_{t}$ users get first proposal

5: for each user $i\in\mathsf{FP}_{t}$ do

6: if $i$ is available then

7: Allocate $i$ to $t$ with probability
$\alpha_{i,t}:=\min\left(1,\frac{0.5+\kappa}{1-(0.5+\kappa)\cdot\sum_{t^{\prime}<t}x_{i,t^{\prime}}\cdot
q_{i,t^{\prime}}}\right)$

8: Let $A_{t}\leftarrow\text{number of users allocated to }t\text{ thus far}$

9: Define users $\mathsf{SP}_{t}:=\textsf{PS}(((1-\frac{A_{t}}{c_{t}})\cdot
x_{i,t}/p_{t})_{i\in I})$ $\triangleright$ $\leq c_{t}-A_{t}$ users get second
proposal

10: for each user $i\in\mathsf{SP}_{t}$ with $\alpha_{i,t}=1$ do

11: if $i$ is available and currently unallocated then

12: Compute $\rho_{i,t}:=\mathbb{E}[\mathbbm{1}[i\text{ available and
unallocated after
\lx@cref{creftypecap~refnum}{line:sample_defAt}}]\cdot(1-\frac{A_{t}}{c_{t}})\mid
t\text{ arrived}]$

13:
$\beta_{i,t}\leftarrow\min\Big{(}1,\left((0.5+\kappa)\cdot\sum_{t^{\prime}<t}x_{i,t^{\prime}}\cdot
q_{i,t^{\prime}}-(0.5-\kappa)\right)\cdot\frac{1}{\rho_{i,t}}\Big{)}.$

14: Allocate $i$ to $t$ with prob. ${\beta_{i,t}}$

Concerning the definition of $\rho_{i,t}$, we note that the expectation is
over the randomness in the arrivals and algorithm up to when it reaches 8 for
arrival $t$ in Algorithm 1 (in particular, we consider “re-running” the
algorithm as defined thus far on a fresh instance). The indicator
$\mathbbm{1}[i\text{ available and unallocated after
\lx@cref{creftypecap~refnum}{line:sample_defAt}}]$ refers to the event that
$i$ was not successfully allocated to some $t^{\prime}<t$ and is also not
allocated yet to $t$ (it could be the case that $i$ was allocated to some
$t^{\prime}<t$, and this was unsuccessful). This indicator is potentially
correlated with the number of allocated users $A_{t}$.

The $\min(1,\cdot)$ in the definition of $\beta_{i,t}$ is for convenience
only; in particular, it is thus easy to see that the algorithm is well-
defined. As a crux of our analysis, we will show that using $\kappa=0.0115$
ensures that the $\min(1,\cdot)$ in the definition of $\beta_{i,t}$ is
actually redundant.

In the remainder of this section, we will argue that Algorithm 1 is well-
defined and guarantees to respect the capacity constraints of online
resources.

######  Observation 3.1.

Algorithm 1 is well-defined.

###### Proof.

Note first that in 4, our call to the pivotal sampling algorithm
$\textsf{PS}(\cdot)$ is well-defined as each marginal
$\nicefrac{{x_{i,t}}}{{p_{t}}}$ is in $[0,1]$ by LPon Constraint (2). Each
$\alpha_{i,t}$ as defined in 7 is clearly a probability by construction. Our
second call to $\textsf{PS}(\cdot)$ is similarly well-defined. Note that
$\beta_{i,t}$ is always a probability — if $\alpha_{i,t}=1$, it implies that
$(0.5+\kappa)\cdot\sum_{t^{\prime}<t}x_{i,t^{\prime}}\cdot
q_{i,t^{\prime}}\geq(0.5-\kappa)$ by definition. This in turn shows that
$\beta_{i,t}$ is always in the interval $[0,1]$.

Finally, note that user $i$ is allocated only if available, and hence never
successfully allocated to two different resources (or to the same resource
twice). ∎

We also have that our algorithm respects capacity constraints for each online
arrival.

######  Observation 3.2.

The number of users allocated to resource $t$ by Algorithm 1 is always at most
$c_{t}$.

###### Proof.

By Property (P2) of pivotal sampling, the size of $\textsf{FP}_{t}$ is never
larger than $c_{t}$ as $\sum_{i}\frac{x_{i,t}}{p_{t}}\leq c_{t}$ by Constraint
(1). In addition, as we scale the marginals down for the second proposal set
$\textsf{SP}_{t}$, we are guaranteed that resource $t$ is only allocated at
most $c_{t}-A_{t}$ many users during the second proposal. ∎

We also note that every line except 12 can be implemented in polynomial time.
Indeed, note 2 can be run efficiently as (LPon) has polynomial size, and that
our calls to pivotal sampling can be implemented efficiently [Sri01].

12 requires exponential time as written, and for ease of presentation, in the
next section we analyze the above exponential time algorithm. In Section 5 we
show that we can replace this computation with a sample average and appeal to
concentration bounds, while only losing an arbitrarily small $\epsilon$ in the
approximation ratio. The main point of care is to argue that $\rho_{i,t}$ is
bounded away from 0 so that we can get a close multiplicative approximation.

##  4 Analysis: Beating a $\nicefrac{{1}}{{2}}$-Approximation

Our main result is as follows.

######  Theorem 4.1.

For $\kappa=0.0115$, the social welfare achieved by Algorithm 1 satisfies

$\mathbb{E}\left[\mathrm{SW}\right]\geq(0.5+\kappa)\cdot\mathrm{OPT}_{\mathrm{on}}\enspace.$

This section is dedicated to the proof of our main result. As mentioned
before, we analyze the algorithm which has access to the expectation
$\rho_{i,t}$ exactly. Note that this requires exponential time; however, in
Section 5 we show that our sampling-based estimation only results in an
additional loss of $\epsilon$ in the approximation. To prove this, we will
rely on a consequence of our analysis, namely that the quantity $\rho_{i,t}$
is always bounded away from zero by some constant. Using this, we can apply
standard Chernoff-Hoeffding concentration bounds to get reasonably close to
the exact $\rho_{i,t}$ within small multiplicative error.

To simplify the exposition, we will additionally assume that every allocation
is successful, i.e., each success probability $q_{i,t}$ equals 1. In Appendix
D we outline the necessary steps to generalize our analysis to the case of
arbitrary success probabilities $\\{q_{i,t}\\}_{i,t}$.

##### Outline.

Before diving into details we outline the ingredients in our proof of Theorem
4.1. Firstly we note that by 3.2, the size of $I_{t}$ (the set of users
allocated to $t$) is always at most $c_{t}$, so

$\mathbb{E}\left[\mathrm{SW}\right]=\mathbb{E}\left[\sum_{t}\max_{S\subseteq
I_{t},|S|\leq c_{t}}\left(\sum_{i\in
S}v_{i,t}\right)\right]=\sum_{i,t}v_{i,t}\cdot\Pr[i\text{ allocated to }t].$

We will note that bounding the term $\Pr[i\text{ allocated to }t]$ naturally
brings us into one of two cases. If $(i,t)$ is such that $\alpha_{i,t}<1$, the
allocation of $i$ to $t$ can only happen in 7 of our algorithm, and
consequently it is straightforward to bound the resulting welfare (which we do
in 4.4). We then turn our perspective towards pairs $(i,t)$ with a subsampling
probability $\alpha_{i,t}=1$; for these, the analysis requires much more care.
Again, we start by considering the contribution of allocating via a first
proposal in Lemma 4.5 (i). Here the first proposal alone is not sufficient,
and we are required to compensate for this via a suitable bound on the
allocation probability via a second proposal. We do so by proving Lemma 4.5
(ii) which gives a sufficient lower bound of the contribution via a second
proposal. This is the main technical contribution and will use lemmas
analyzing the evolution of the correlation between offline users in Section
4.3.

##### Notation.

For convenience, we let $y_{i,t}:=\sum_{t^{\prime}<t}x_{i,t^{\prime}}.$ Note
that $\alpha_{i,t}<1$ exactly when
$y_{i,t}<(0.5-\kappa)\cdot(0.5+\kappa)^{-1}$. We hence define
$\tau:=(0.5-\kappa)\cdot(0.5+\kappa)^{-1}$ as this threshold for $y_{i,t}$
after which the subsampling probability $\alpha_{i,t}$ becomes one. If for
resource $t$ and user $i$ we have $y_{i,t}\leq\tau$, then we call the pair
$(i,t)$ _early_. Otherwise, we call the pair $(i,t)$ _late_. In addition, we
define $\mathcal{A}_{1}$ as the set of all pairs $(i,t)$ such that user $i$
was allocated to resource $t$ in 7, and $\mathcal{A}_{2}$ as the set of all
pairs $(i,t)$ such that $i$ was allocated to $t$ in 14.

As $i$ is not allocated more than once in our algorithm, we quickly observe
the following claim.

######  Observation 4.2.

For any resource $t$, we have

$\mathbb{E}\left[\max_{S\subseteq I_{t},|S|\leq c_{t}}\left(\sum_{i\in
S}v_{i,t}\right)\right]=\sum_{i\in
I}v_{i,t}\cdot(\Pr[(i,t)\in\mathcal{A}_{1}]+\Pr[(i,t)\in\mathcal{A}_{2}]).$

To analyze the probabilities $\Pr[(i,t)\in\mathcal{A}_{1}]$ and
$\Pr[(i,t)\in\mathcal{A}_{2}]$, we consider two separate cases based on
whether $(i,t)$ is early (Section 4.1) or late (Section 4.2).

###  4.1 Analysis for Early Pairs

It will be crucial to bound the probability of a user $i$ being free at time
$t$. We denote the event that user $i$ is _free_ or _available_ (i.e., not
allocated) at the arrival of resource $t$ by $F_{i,t}$. The following
observation gives an expression of the probability with respect to the LP
variables. It is crucial to note that if a pair $(i,t)$ is early, so is every
pair $(i,t^{\prime})$ with $t^{\prime}<t$.

######  Observation 4.3.

For early pairs $(i,t)$, we have $\Pr[F_{i,t}]=1-(0.5+\kappa)\cdot y_{i,t}$.

###### Proof.

We proceed via induction on $t$. Before the arrival of the first resource, the
claim is trivially true, as all users are available with probability one.
Afterwards, note that

$\displaystyle\Pr[(i,t)\in\mathcal{A}_{1}]$
$\displaystyle=p_{t}\cdot\Pr[i\in\mathsf{FP}_{t}]\cdot\Pr[F_{i,t}]\cdot\alpha_{i,t}$
(3)

as $t$’s arrival, $i$ being included in $\mathsf{FP}_{t}$, $F_{i,t}$ and the
algorithm’s $\text{Ber}(\alpha_{i,t})$ coin flip are mutually independent
events. If $(i,t)$ is early, then
$\alpha_{i,t}=\frac{0.5+\kappa}{1-(0.5+\kappa)\cdot y_{i,t}}$, so we have

$\Pr[(i,t)\in\mathcal{A}_{1}]=p_{t}\cdot\frac{x_{i,t}}{p_{t}}\cdot(1-(0.5+\kappa)\cdot
y_{i,t})\cdot\frac{0.5+\kappa}{1-(0.5+\kappa)\cdot y_{i,t}}=(0.5+\kappa)\cdot
x_{i,t},$

where we also use the induction hypothesis for the probability of the user
being free at the arrival of resource $t$. For early $(i,t)$, we also clearly
have $\Pr[(i,t)\in\mathcal{A}_{2}]=0$, so

$\displaystyle\Pr[F_{i,t+1}]$
$\displaystyle=\Pr[F_{i,t}]-\Pr[(i,t)\in\mathcal{A}_{1}]=1-(0.5+\kappa)\cdot
y_{i,t+1}.\qed$

As a consequence we can bound the contribution of an early pair $(i,t)$ to
$\mathcal{A}_{1}$ and $\mathcal{A}_{2}$, as follows.

######  Observation 4.4.

For early pairs $(i,t)$, $\Pr[(i,t)\in\mathcal{A}_{1}]=(0.5+\kappa)\cdot
x_{i,t}$ and ${\Pr[(i,t)\in\mathcal{A}_{2}]=0}$.

Thus for early pairs $(i,t)$, our algorithm achieves the desired allocation
probability.

###  4.2 Analysis for Late Pairs implies Theorem 4.1

For late pairs, we show the following lemma which will be sufficient to prove
our main Theorem 4.1.

######  Lemma 4.5.

For late pairs $(i,t)$, the following two statements hold:

  * (i)

$\Pr[(i,t)\in\mathcal{A}_{1}]=(1-(0.5+\kappa)\cdot y_{i,t})\cdot x_{i,t}$, and

  * (ii)

$\Pr[(i,t)\in\mathcal{A}_{2}]=((0.5+\kappa)\cdot y_{i,t}-0.5+\kappa)\cdot
x_{i,t}$.

We note that this immediately implies our main result.

###### Proof of Theorem 4.1..

We have
$\Pr[(i,t)\in\mathcal{A}_{1}]+\Pr[(i,t)\in\mathcal{A}_{2}]=(0.5+\kappa)\cdot
x_{i,t}$ for any pair $(i,t)$ by 4.4 and Lemma 4.5. Hence, using the
decomposition in 4.2, we have

$\displaystyle\mathbb{E}\left[\sum_{t}v_{t}(I_{t})\right]$
$\displaystyle=\sum_{t}\sum_{i\in
I}v_{i,t}\cdot(\Pr[(i,t)\in\mathcal{A}_{1}]+\Pr[(i,t)\in\mathcal{A}_{2}])$
$\displaystyle=\sum_{t}\sum_{i\in I}v_{i,t}\cdot(0.5+\kappa)\cdot x_{i,t}$
$\displaystyle=(0.5+\kappa)\cdot\mathrm{OPT}\eqref{LP}\geq(0.5+\kappa)\cdot\mathrm{OPT}_{\mathrm{on}}.\qed$

Thus, it remains to prove Lemma 4.5. Our analysis here requires significantly
more care as it must bound the gain from the second proposal. As the second
proposal’s marginal probabilities are dependent on which offline users were
allocated in the first proposal, a complete analysis must consider the
correlation introduced.

####  4.2.1 Proof of Lemma 4.5 (i)

As for early pairs, the remainder of our proof will proceed by induction on
$t$. Thus, for every late pair $(i,t^{\prime})$ with $t^{\prime}<t$, by the
inductive hypothesis we have
$\Pr[(i,t^{\prime})\in\mathcal{A}_{1}]+\Pr[(i,t^{\prime})\in\mathcal{A}_{2}]=(0.5+\kappa)\cdot
x_{i,t^{\prime}}$. Recall also that for every early pair $(i,t^{\prime})$ we
know from 4.4 that
$\Pr[(i,t^{\prime})\in\mathcal{A}_{1}]+\Pr[(i,t^{\prime})\in\mathcal{A}_{2}]=(0.5+\kappa)\cdot
x_{i,t^{\prime}}$. Thus, we may assume that for the late pair $(i,t)$ being
considered we have

$\displaystyle\Pr[F_{i,t}]=1-(0.5+\kappa)\cdot y_{i,t}.$ (4)

With this, bounding the probability of allocation along a first proposal is
very straightforward.

###### Proof of Lemma 4.5 (i)..

Note that

$\displaystyle\Pr[(i,t)\in\mathcal{A}_{1}]$
$\displaystyle=p_{t}\cdot\Pr[F_{i,t}]\cdot\Pr[i\in\textsf{FP}_{t}]\cdot\alpha_{i,t}$
(Equation (3)) $\displaystyle=p_{t}\cdot\left(1-(0.5+\kappa)\cdot
y_{i,t}\right)\cdot\frac{x_{i,t}}{p_{t}}\cdot 1$ (Equation 4)
$\displaystyle=(1-(0.5+\kappa)\cdot y_{i,t})\cdot x_{i,t}.$

This completes the proof of Lemma 4.5 (i), and the remainder of this section
is dedicated to the proof of Lemma 4.5 (ii).

####  4.2.2 Proof of Lemma 4.5 (ii)

We begin by bounding $\Pr[(i,t)\in\mathcal{A}_{2}]$ for late pairs $(i,t)$, in
the natural way which depends on the number of allocated users during the
first proposal in 7. (Recall that this is because for second proposals, we
reduce the marginal probabilities for pivotal sampling algorithm by a factor
of $1-\nicefrac{{A_{t}}}{{c_{t}}}$). Note that for $(i,t)$ to be matched as a
second proposal we need all of the following to happen: (i) $t$ should arrive,
(ii) $i$ must be available and unallocated after 8, and included as a second
proposal, and (iii) the potential match $(i,t)$ should survive the final
downsampling by $\beta_{i,t}$. This lets us observe

$\displaystyle\Pr[(i,t)$ $\displaystyle\in\mathcal{A}_{2}]$
$\displaystyle=p_{t}\cdot\Pr[i\text{ available and unallocated after
\lx@cref{creftypecap~refnum}{line:sample_defAt}}\wedge i\in\textsf{SP}_{t}\mid
t\text{ arrived}]\cdot\beta_{i,t}$
$\displaystyle=p_{t}\cdot\mathbb{E}\left[\mathbbm{1}[i\text{ available and
unallocated after
\lx@cref{creftypecap~refnum}{line:sample_defAt}}]\cdot\left(1-\frac{A_{t}}{c_{t}}\right)\cdot\frac{x_{i,t}}{p_{t}}\bigm{|}t\text{
arrived}\right]\cdot\beta_{i,t}$
$\displaystyle=x_{i,t}\cdot\rho_{i,t}\cdot\beta_{i,t}.$ (5)

For the second equality, we relied on Property (P1) of pivotal sampling, which
guarantees that individual elements are sampled with exactly their marginal
probability. Note that this marginal probability is random, and potentially
correlated with $\mathbbm{1}[i\text{ available and unallocated after
\lx@cref{creftypecap~refnum}{line:sample_defAt}}]$.

Recall that $\beta_{i,t}:=\min\Big{(}1,\left((0.5+\kappa)\cdot
y_{i,t}-(0.5-\kappa)\right)\cdot\frac{1}{\rho_{i,t}}\Big{)}$. If the
$\min(1,\cdot)$ here is redundant, we are immediately done; this is
concretized in the following observation.

######  Observation 4.6.

If $\rho_{i,t}\geq(0.5+\kappa)y_{i,t}-(0.5-\kappa)$, then

$\Pr[(i,t)\in\mathcal{A}_{2}]=x_{i,t}\cdot\left((0.5+\kappa)\cdot
y_{i,t}-(0.5-\kappa)\right).$

Thus it suffices to show that the hypothesis of this observation holds. In
other words, for the remainder of the proof, the only thing we need to show is
the following proposition.

######  Proposition 4.7.

For any late pair $(i,t)$, we have
$\rho_{i,t}\geq(0.5+\kappa)y_{i,t}-(0.5-\kappa)$.

As a first step, we start with the following lower bound on $\rho_{i,t}$.

######  Lemma 4.8.

For late pairs $(i,t)$,

$\rho_{i,t}\geq(1-(0.5+\kappa)\cdot
y_{i,t})\cdot\left(\tau-\frac{\mathbb{E}[A_{t}\mid t\textup{
arrived},F_{i,t}]}{c_{t}}\right).$

###### Proof of Lemma 4.8..

Note first that we can expand

$\displaystyle\rho_{i,t}$ $\displaystyle=\mathbb{E}\left[\mathbbm{1}[i\text{
available and unallocated after
\lx@cref{creftypecap~refnum}{line:sample_defAt}}]\cdot\left(1-\frac{A_{t}}{c_{t}}\right)\mid
t\text{ arrived}\right]$ $\displaystyle=\Pr[F_{i,t}\mid t\text{
arrived}]\cdot\mathbb{E}\left[\mathbbm{1}[i\text{ not allocated in
\lx@cref{creftypecap~refnum}{line:firstmatch}}]\cdot\left(1-\frac{A_{t}}{c_{t}}\right)\mid
t\text{ arrived},F_{i,t}\right]$
$\displaystyle=\Pr[F_{i,t}]\cdot\mathbb{E}\left[\mathbbm{1}[i\text{ not
allocated in
\lx@cref{creftypecap~refnum}{line:firstmatch}}]\cdot\left(1-\frac{A_{t}}{c_{t}}\right)\mid
t\text{ arrived},F_{i,t}\right].$

Note that as the pair $(i,t)$ is late, we have $\alpha_{i,t}=1$. Hence,
conditioned on being free and the arrival of resource $t$, user $i$ is not
allocated in 7 if and only if it is not contained in the set
$\mathsf{FP}_{t}$. This allows us to bound

$\displaystyle\mathbb{E}\Bigg{[}\mathbbm{1}[i\text{ not allocated in
\lx@cref{creftypecap~refnum}{line:firstmatch}}]$
$\displaystyle\cdot\left(1-\frac{A_{t}}{c_{t}}\right)\mid t\text{
arrived},F_{i,t}\Bigg{]}$
$\displaystyle=\mathbb{E}\left[\mathbbm{1}[i\notin\textsf{FP}_{t}]\cdot\left(1-\frac{A_{t}}{c_{t}}\right)\mid
t\text{ arrived},F_{i,t}\right]$
$\displaystyle=\left(1-\frac{x_{i,t}}{p_{t}}\right)\cdot\mathbb{E}\left[\left(1-\frac{A_{t}}{c_{t}}\right)\mid
t\text{ arrived},F_{i,t},i\notin\textsf{FP}_{t}\right]$
$\displaystyle\geq\tau\cdot\mathbb{E}\left[\left(1-\frac{A_{t}}{c_{t}}\right)\mid
t\text{ arrived},F_{i,t},i\notin\textsf{FP}_{t}\right].$

To reason about the resulting expectation, we first apply the following
bounding to remove the conditioning on $i\notin\textsf{FP}_{t}$:

$\displaystyle\mathbb{E}[A_{t}\mid t\text{
arrived},F_{i,t},i\notin\mathsf{FP}_{t}]$
$\displaystyle=\frac{\mathbb{E}[A_{t}\cdot\mathds{1}_{i\notin\mathsf{FP}_{t}}\mid
t\text{ arrived},F_{i,t}]}{\Pr[i\notin\mathsf{FP}_{t}\mid t\text{
arrived},F_{i,t}]}$ $\displaystyle\leq\frac{\mathbb{E}[A_{t}\mid t\text{
arrived},F_{i,t}]}{\Pr[i\notin\mathsf{FP}_{t}\mid t\text{
arrived},F_{i,t}]}\enspace.$

In addition, note that $\Pr[i\notin\mathsf{FP}_{t}\mid t\text{
arrived},F_{i,t}]=1-\frac{x_{i,t}}{p_{t}}\geq y_{i,t}\geq\tau$ as pair $(i,t)$
is late. Thus we get

$\displaystyle\mathbb{E}[A_{t}\mid t\text{
arrived},F_{i,t},i\notin\textsf{FP}_{t}]\leq\frac{1}{\tau}\cdot\mathbb{E}[A_{t}\mid
t\text{ arrived},F_{i,t}].$

By substitution and using Equation 4, we directly conclude

$\displaystyle\rho_{i,t}$
$\displaystyle\geq\Pr[F_{i,t}]\cdot\tau\cdot\left(1-\frac{\mathbb{E}[A_{t}\mid
t\text{ arrived},F_{i,t}]}{c_{t}}\cdot\tau^{-1}\right)$ (6)
$\displaystyle=(1-(0.5+\kappa)\cdot
y_{i,t})\cdot\left(\tau-\frac{\mathbb{E}[A_{t}\mid t\text{
arrived},F_{i,t}]}{c_{t}}\right).$ (via Equation 4)

as claimed. ∎

In order to exploit the bound obtained in Lemma 4.8, we need to control
$\mathbb{E}[A_{t}\mid t\text{ arrived},F_{i,t}]$. In particular, our goal is
to show that $\mathbb{E}[A_{t}\mid t\text{ arrived},F_{i,t}]$ is bounded away
from $c_{t}$ by a multiplicative constant smaller than $1$. If there was no
conditioning on $F_{i,t}$, it is easy to check that

$\mathbb{E}[A_{t}\mid t\text{
arrived}]=\sum_{j}\Pr[F_{j,t}]\cdot\Pr[j\in\textsf{FP}_{t}]\cdot\alpha_{j,t}\leq(0.5+\kappa)\cdot
c_{t}.$

The conditioning could however lead us into trouble in the following way: When
facing the conditioning, we end up with the expression

$\mathbb{E}[A_{t}\mid t\text{ arrived},F_{i,t}]=\sum_{j}\Pr[F_{j,t}\mid
F_{i,t}]\cdot\Pr[j\in\textsf{FP}_{t}]\cdot\alpha_{j,t}.$

If $F_{i,t}$ implies $F_{j,t}$ for every $j\neq i$, and $\alpha_{j,t}\approx
1$ for every $j\neq i$, then

${\mathbb{E}[A_{t}\mid t\text{
arrived},F_{i,t}]}\approx\sum_{i}1\cdot\frac{x_{i,t}}{p_{t}}\cdot 1$

where the right-hand side could equal $c_{t}$. This, in particular, would make
the second proposal in our algorithm completely useless as we would reduce the
marginal probabilities for the pivotal sampling in 9 to (almost) zero. The
most crucial part of our analysis is to demonstrate that this cannot happen,
by bounding the possible positive correlation introduced between offline
users.

######  Lemma 4.9.

For any distinct users $i$ and $j$, and
$\Delta_{\kappa}:=\left(1+\frac{(0.5+\kappa)^{2}}{0.5-\kappa}\right)\cdot\left(\frac{0.5+\kappa}{0.5-\kappa}\right)^{2}$,
for any $t$ we have

$\Pr[F_{i,t}\wedge
F_{j,t}]\leq\Delta_{\kappa}\cdot\Pr[F_{i,t}]\cdot\Pr[F_{j,t}].$

The proof of Lemma 4.9 is deferred to Section 4.3; in the remainder of this
section we demonstrate why it implies our bound on the approximation ratio. We
note that for $\kappa=0.0115$ (the value we choose in Algorithm 1), we have
$\Delta_{\kappa}\approx 1.68$. As a concrete example, note that if $(i,t)$ and
$(j,t)$ are both late with
$\Pr[F_{i,t}]\approx\Pr[F_{j,t}]\approx\nicefrac{{1}}{{2}}$, this bound
quantifies that we avoid perfect positive correlation between $F_{i,t}$ and
$F_{j,t}$.

Having Lemma 4.9, we can prove the bound on $\mathbb{E}[A_{t}\mid t\text{
arrived},F_{i,t}]$ which we state formally in 4.10 via

$\displaystyle\mathbb{E}[A_{t}\mid t\text{ arrived},F_{i,t}]$
$\displaystyle=\sum_{j}\Pr[F_{j,t}\mid
F_{i,t}]\cdot\Pr[j\in\textsf{FP}_{t}]\cdot\alpha_{j,t}$
$\displaystyle=\frac{x_{i,t}}{p_{t}}+\sum_{j\neq i}\frac{\Pr[F_{i,t}\wedge
F_{j,t}]}{\Pr[F_{i,t}]}\cdot\frac{x_{j,t}}{p_{t}}\cdot\alpha_{j,t}$ (7)
$\displaystyle\leq\frac{x_{i,t}}{p_{t}}+\sum_{j\neq
i}\Delta_{\kappa}\cdot\Pr[F_{j,t}]\cdot\frac{x_{j,t}}{p_{t}}\cdot\alpha_{j,t}$
$\displaystyle\leq\frac{x_{i,t}}{p_{t}}+\Delta_{\kappa}\cdot(0.5+\kappa)\cdot
c_{t}.$

The last inequality uses the fact that $\Pr[F_{j,t}]\cdot\alpha_{j,t}\leq
0.5+\kappa$ and upper bounds $\sum_{j\neq i}\frac{x_{j,t}}{p_{t}}$ by $c_{t}$.
By the online constraint (2) and the property that $y_{i,t}>\tau$ for late
pairs $(i,t)$, we have that $\frac{x_{i,t}}{p_{t}}\leq 1-\tau$. Hence, we can
conclude that

$\displaystyle\mathbb{E}[A_{t}\mid t\text{ arrived},F_{i,t}]$
$\displaystyle\leq 1-\tau+\Delta_{\kappa}\cdot(0.5+\kappa)\cdot c_{t}$ (8)
$\displaystyle\leq\left(1-\tau+\Delta_{\kappa}\cdot(0.5+\kappa)\right)\cdot
c_{t}.$

Although this appears quite loose if $c_{t}$ is larger than 1, in Section A.4
we show that a fine-grained bound in terms of $\min_{t}c_{t}$ only results in
limited improvements in the analysis. Equation 8 implies the following
corollary of our correlation bound.

######  Corollary 4.10.

Let
$\Delta_{\kappa}:=\left(1+\frac{(0.5+\kappa)^{2}}{0.5-\kappa}\right)\cdot\left(\frac{0.5+\kappa}{0.5-\kappa}\right)^{2}$.
For any late $(i,t)$ we have

$\mathbb{E}[A_{t}\mid t\textup{
arrived},F_{i,t}]\leq\left(1-\tau+\Delta_{\kappa}\cdot(0.5+\kappa)\right)\cdot
c_{t}.$

We are now able to conclude the proof of Lemma 4.5 (ii), as follows.

###### Proof of Lemma 4.5 (ii)..

By 4.6, it suffices to show that
$\rho_{i,t}\geq(0.5+\kappa)y_{i,t}-(0.5-\kappa).$ Combining the bound of Lemma
4.8 with 4.10 implies

$\displaystyle\rho_{i,t}\geq(1-(0.5+\kappa)\cdot
y_{i,t})\cdot\left(\tau-\left(1-\tau+\Delta_{\kappa}\cdot(0.5+\kappa)\right)\right).$
(9)

For convenience let $g(\kappa):=2\tau-1-\Delta_{\kappa}\cdot(0.5+\kappa)$,
recalling that $\tau$ is a function of $\kappa$. Then, it suffices to show
$(1-(0.5+\kappa)\cdot y_{i,t})\cdot
g(\kappa)\geq(0.5+\kappa)y_{i,t}-(0.5-\kappa)$, or equivalently

$g(\kappa)+0.5-\kappa\geq(0.5+\kappa+(0.5+\kappa)g(\kappa))\cdot y_{i,t}.$

For $\kappa=0.0115$, we can confirm that the coefficient of $y_{i,t}$ on the
right-hand side is positive, and hence it suffices to show this inequality
when $y_{i,t}=1$. This reduces to

$g(\kappa)\geq\frac{2\kappa}{0.5-\kappa}$

which is readily confirmed by direct computation at $\kappa=0.0115$. ∎

As a side remark, using Equation 9, we can observe that for our choice of
$\kappa=0.0115$, the expectation $\rho_{i,t}$ is bounded away from zero by a
constant. In particular, for $\kappa=0.0115$, we have that $\rho_{i,t}\geq
0.02389$. This can be used to estimate $\rho_{i,t}$ via sampling with small
multiplicative error, as we formalize in Section 5.

In order to finalize our proof of Lemma 4.5 (ii), it only remains to prove our
bound on the correlation introduced between offline users, which we do in the
following section.

###  4.3 Bounding the Correlation — Proof of Lemma 4.9

What remains to conclude the proof of our main Theorem 4.1 is to control the
correlation of two users $i$ and $j$ to be free simultaneously, i.e., the
bound from Lemma 4.9. To this end, we first state and prove Lemma 4.11 which
uses the assumption that $y_{i,t-1}$ and $y_{j,t-1}$ are at most $\tau$.

######  Lemma 4.11.

Define $\gamma_{\kappa}:=1+\frac{(0.5+\kappa)^{2}}{0.5-\kappa}$. For any
distinct users $i$ and $j$, and any time $t$ such that
$y_{i,t-1},y_{j,t-1}\leq\tau$, we have

$\Pr[F_{i,t}\wedge
F_{j,t}]\leq\gamma_{\kappa}\cdot\Pr[F_{i,t}]\cdot\Pr[F_{j,t}].$

To prove this lemma we consider the function

$f(z):=1+z\cdot\left(\frac{(0.5+\kappa)^{2}}{1-z\cdot(0.5+\kappa)}\right),$

which depends on our choice of $\kappa$. Note that $\gamma_{\kappa}=f(1)$. For
this function, we can prove the following claim.

######  Claim 4.12.

For any distinct users $i$ and $j$, and any time $t$ such that
$y_{i,t-1},y_{j,t-1}\leq\tau$, we have

$\Pr[F_{i,t}\wedge F_{j,t}]\leq f(y_{i,t})\cdot\Pr[F_{i,t}]\cdot\Pr[F_{j,t}],$

where
$f(z):=1+z\cdot\left(\frac{(0.5+\kappa)^{2}}{1-z\cdot(0.5+\kappa)}\right)$.

In order to prove Lemma 4.11 from Claim 4.12, it suffices to note that $f$ is
a monotone increasing function in $[0,1]$, and hence, $f(z)\leq
f(1)=\gamma_{\kappa}$ for all $z\in[0,1]$.

###### Proof of Claim 4.12..

We give a proof by induction. As $f(0)=1$ and all users are available
initially, the base case is clear. Assuming the claim is true for fixed $t$,
we will prove it for $t+1$ with the assumption $y_{i,t},y_{j,t}\leq\tau$.

##### Proof outline for the inductive step.

Our proof proceeds with the following steps:

  1. (S1)

We find an upper bound for the probability that both $i$ and $j$ are not
assigned to $t$ via a first proposal conditioned on being free.

  2. (S2)

We compute $\Pr[F_{i,t+1}]/\Pr[F_{i,t}]$, in order to apply the inductive
hypothesis.

  3. (S3)

We apply the induction hypothesis, and use Step (S2) to write our bound in
terms of $\Pr[F_{i,t+1}]$ and $\Pr[F_{j,t+1}]$.

  4. (S4)

We argue that we can upper bound the coefficient in front of
$\Pr[F_{i,t+1}]\cdot\Pr[F_{j,t+1}]$ with $f(y_{i,t+1})$.

##### Step (S1): Bounding the probability of not assigning both users via a
first proposal.

As $y_{i,t},y_{j,t}\leq\tau$, they can only be matched as first proposals;
hence the probability both $i$ and $j$ are free at time $t+1$ is

$\displaystyle\Pr[F_{i,t+1}\wedge F_{j,t+1}]$ $\displaystyle=\Pr[F_{i,t}\wedge
F_{j,t}]\cdot\underbrace{\Pr[(i,t)\notin\mathcal{A}_{1}\wedge(j,t)\notin\mathcal{A}_{1}\mid
F_{i,t}\wedge F_{j,t}]}_{(\star)}.$ (10)

The first term on the right-hand side of Equation 10 will later be bounded via
the induction hypothesis. The second term
$(\star):=\Pr[(i,t)\notin\mathcal{A}_{1}\wedge(j,t)\notin\mathcal{A}_{1}\mid
F_{i,t}\wedge F_{j,t}]$ can be equivalently written as

$\displaystyle(\star)=1-\Pr[(i,t)\in\mathcal{A}_{1}\mid F_{i,t}\wedge
F_{j,t}]-\Pr[(j,t)$ $\displaystyle\in\mathcal{A}_{1}\mid F_{i,t}\wedge
F_{j,t}]$ (11)
$\displaystyle+\Pr[(i,t)\in\mathcal{A}_{1}\wedge(j,t)\in\mathcal{A}_{1}\mid
F_{i,t}\wedge F_{j,t}].$

Now, observe that $\Pr[(i,t)\in\mathcal{A}_{1}\mid F_{i,t}\wedge
F_{j,t}]=p_{t}\cdot\Pr[i\in\textsf{FP}_{t}]\cdot\alpha_{i,t}=x_{i,t}\cdot\alpha_{i,t}$.
The analogous equality holds for $j$. Hence, it remains to get a suitable
bound on the joint probability that both users $i$ and $j$ are assigned via a
first proposal given they were both free. To this end, we make use of the
negative cylinder dependence in pivotal sampling, observing

$\displaystyle\Pr[(i,t)\in\mathcal{A}_{1}$
$\displaystyle\wedge(j,t)\in\mathcal{A}_{1}\mid F_{i,t}\wedge F_{j,t}]$
$\displaystyle=p_{t}\cdot\Pr[i\in\textsf{FP}_{t}\wedge
j\in\textsf{FP}_{t}]\cdot\alpha_{i,t}\cdot\alpha_{j,t}$ $\displaystyle\leq
p_{t}\cdot\Pr[i\in\textsf{FP}_{t}]\cdot\Pr[j\in\textsf{FP}_{t}]\cdot\alpha_{i,t}\cdot\alpha_{j,t}$
(Pivotal Sampling Property (P3)) $\displaystyle=p_{t}\cdot\frac{x_{i,t}\cdot
x_{j,t}}{p_{t}^{2}}\cdot\alpha_{i,t}\cdot\alpha_{j,t}$
$\displaystyle=\frac{x_{i,t}\cdot
x_{j,t}}{p_{t}}\cdot\alpha_{i,t}\cdot\alpha_{j,t}.$

Combining all of the above, we can bound the conditional probability that
neither $i$ nor $j$ is allocated to $t$ via a first proposal. In other words,
the left-hand side of Equation 11 is at most

$\displaystyle\Pr[(i,t)\notin\mathcal{A}_{1}\wedge(j,t)\notin\mathcal{A}_{1}\mid
F_{i,t}\wedge F_{j,t}]$ $\displaystyle\leq
1-x_{i,t}\alpha_{i,t}-x_{j,t}\alpha_{j,t}+\frac{1}{p_{t}}\cdot
x_{i,t}\alpha_{i,t}x_{j,t}\alpha_{j,t}$ (12)
$\displaystyle=(1-x_{i,t}\alpha_{i,t})(1-x_{j,t}\alpha_{j,t})+\left(\frac{1}{p_{t}}-1\right)x_{i,t}\alpha_{i,t}x_{j,t}\alpha_{j,t}.$

##### Step (S2): Comparing $\Pr[F_{i,t+1}]$ to $\Pr[F_{i,t}]$.

To prepare for our use of the inductive hypothesis, we compute
$\Pr[F_{i,t+1}]/\Pr[F_{i,t}]$ via a straightforward calculation:

$\displaystyle\Pr[F_{i,t+1}]$ $\displaystyle=1-(0.5+\kappa)\cdot
y_{i,t+1}=\Pr[F_{i,t}]\cdot\frac{1-(0.5+\kappa)\cdot
y_{i,t+1}}{1-(0.5+\kappa)\cdot
y_{i,t}}=\Pr[F_{i,t}]\cdot\left(1-x_{i,t}\cdot\alpha_{i,t}\right).$ (13)

In the final line we used that $(i,t)$ is early. For $j$, we analogously have

$\Pr[F_{j,t+1}]=\Pr[F_{j,t}]\cdot\left(1-x_{j,t}\cdot\alpha_{j,t}\right).$

##### Step (S3): Applying the induction hypothesis.

Applying the induction hypothesis to Equation 10, plugging in Inequality (12)
and using Equation 13, we can bound

$\displaystyle\Pr[F_{i,t+1}\wedge F_{j,t+1}]$ $\displaystyle=\Pr[F_{i,t}\wedge
F_{j,t}]\cdot\Pr[(i,t)\notin\mathcal{A}_{1}\wedge(j,t)\notin\mathcal{A}_{1}\mid
F_{i,t}\wedge F_{j,t}]$ $\displaystyle\leq\Pr[F_{i,t}\wedge
F_{j,t}]\cdot\Big{(}(1-x_{i,t}\alpha_{i,t})(1-x_{j,t}\alpha_{j,t})+\left(\frac{1}{p_{t}}-1\right)x_{i,t}\alpha_{i,t}x_{j,t}\alpha_{j,t}\Big{)}$
$\displaystyle\leq
f(y_{i,t})\cdot\Pr[F_{i,t}]\cdot\Pr[F_{j,t}]\cdot\Big{(}(1-x_{i,t}\alpha_{i,t})(1-x_{j,t}\alpha_{j,t})+\left(\frac{1}{p_{t}}-1\right)x_{i,t}\alpha_{i,t}x_{j,t}\alpha_{j,t}\Big{)}$
$\displaystyle=f(y_{i,t})\cdot\Pr[F_{i,t+1}]\cdot\Pr[F_{j,t+1}]+f(y_{i,t})\left(\frac{1}{p_{t}}-1\right)\cdot\Pr[F_{i,t}]\cdot\Pr[F_{j,t}]\cdot
x_{i,t}\alpha_{i,t}x_{j,t}\alpha_{j,t}.$ (14)

Here, the first inequality uses Inequality (12) from Step (S1), i.e., the
upper bound on the probability of both users not being allocated via a first
proposal. The second inequality applies the induction hypothesis for
$\Pr[F_{i,t}\wedge F_{j,t}]$, and the last equality uses Equation 13 from Step
(S2) for both users $i$ and $j$ and rearranges terms.

We now bound the second summand of (14), via the following inequality.

######  Fact 4.13.

For any $(i,t)$ we have

$\displaystyle
x_{i,t}\cdot\alpha_{i,t}\cdot\left(\frac{1}{p_{t}}-1\right)\leq(0.5+\kappa)\cdot\left(1-x_{i,t}\alpha_{i,t}\right).$
(15)

###### Proof.

By Constraint (2) of the LP, we have that
$\frac{1}{p_{t}}\leq\frac{1-y_{i,t}}{x_{i,t}}.$ Thus it suffices to show that

$\alpha_{i,t}(1-y_{i,t})-x_{i,t}\alpha_{i,t}\leq(0.5+\kappa)(1-x_{i,t}\alpha_{i,t})$

which is equivalent to

$\alpha_{i,t}(1-y_{i,t}-(0.5-\kappa)x_{i,t})\leq 0.5+\kappa.$

As $\alpha_{i,t}\leq\frac{0.5+\kappa}{1-(0.5+\kappa)y_{i,t}}$, the claim
follows. ∎

We can apply Fact 4.13 to user $j$ and combine it with Equation 13 in order to
bound the second summand via

$\displaystyle\hskip
15.6491ptf(y_{i,t})\left(\frac{1}{p_{t}}-1\right)\cdot\Pr[F_{i,t}]\cdot\Pr[F_{j,t}]\cdot
x_{i,t}\alpha_{i,t}x_{j,t}\alpha_{j,t}$ $\displaystyle\leq
f(y_{i,t})\cdot\Pr[F_{i,t}]\cdot\Pr[F_{j,t}]\cdot(0.5+\kappa)\cdot(1-x_{j,t}\alpha_{j,t})\cdot
x_{i,t}\alpha_{i,t}$ $\displaystyle=(0.5+\kappa)\cdot
f(y_{i,t})\cdot\Pr[F_{j,t+1}]\cdot
x_{i,t}\alpha_{i,t}\cdot\Pr[F_{i,t+1}]\cdot(1-x_{i,t}\cdot\alpha_{i,t})^{-1}.$

Overall, we thus have

$\displaystyle\Pr[F_{i,t+1}\wedge F_{j,t+1}]$ $\displaystyle\leq
f(y_{i,t})\cdot\Pr[F_{i,t+1}]\cdot\Pr[F_{j,t+1}]\cdot\left(1+(0.5+\kappa)\cdot\frac{x_{i,t}\alpha_{i,t}}{1-x_{i,t}\alpha_{i,t}}\right).$

##### Step (S4): Upper bounding the coefficient by $f(y_{i,t+1})$.

In order to complete the inductive step, we would like to show that

$f(y_{i,t})\cdot\left(1+(0.5+\kappa)\cdot\frac{x_{i,t}\alpha_{i,t}}{1-x_{i,t}\alpha_{i,t}}\right)\leq
f(y_{i,t}+x_{i,t}).$

First, note that as we only consider early pairs, $\alpha_{i,t}$ is always
equal to $\frac{0.5+\kappa}{1-(0.5+\kappa)\cdot y_{i,t}}$, so we know
$\frac{x_{i,t}\alpha_{i,t}}{1-x_{i,t}\alpha_{i,t}}=\frac{(0.5+\kappa)\cdot
x_{i,t}}{1-(0.5+\kappa)\cdot(x_{i,t}+y_{i,t})}.$ Thus to conclude the proof,
it suffices to show that

$f(y_{i,t})\cdot\left(1+(0.5+\kappa)\cdot\frac{(0.5+\kappa)\cdot
x_{i,t}}{1-(0.5+\kappa)\cdot(x_{i,t}+y_{i,t})}\right)\leq f(y_{i,t}+x_{i,t}).$

This is a consequence of our definition

$f(z):=1+z\cdot\left(\frac{(0.5+\kappa)^{2}}{1-z\cdot(0.5+\kappa)}\right).$

In particular the following claim, whose proof can be found in Section B.3,
completes the inductive step.

######  Claim 4.14.

For any $x,y\in[0,1]$ with $x+y\leq 1$ and $f(\cdot)$ as stated above, we have

$f(y)\cdot\left(1+(0.5+\kappa)\cdot\frac{(0.5+\kappa)\cdot
x}{1-(0.5+\kappa)\cdot(x+y)}\right)\leq f(y+x).$

This concludes the proof of Claim 4.12. ∎

Now, we can finally prove Lemma 4.9 which concludes the proof of our main
Theorem 4.1. Let us restate Lemma 4.9 and prove it afterwards.

See 4.9

###### Proof of Lemma 4.9..

We assume that both $y_{i,t}>\tau$ and $y_{j,t}>\tau$; if neither inequality
holds the result is clear and follows directly from Lemma 4.11 while if just
one holds the proof proceeds nearly identically with a slightly better
guarantee.

Let $t^{i}$ denote the latest resource in $[T]$ such that
$y_{i,t^{i}-1}\leq\tau$ and $y_{i,t^{i}}>\tau$ and similarly let $t^{j}$
denote the latest resource in $[T]$ such that $y_{j,t^{j}-1}\leq\tau$ and
$y_{i,t^{j}}>\tau$.

Let $A_{i}$ denote the event that $i$ is allocated to some arrival in
$[t^{i},t-1]$ and let $A_{j}$ denote the event that $j$ is allocated to some
arrival in $[t^{j},t-1]$. By the hypothesis that
$\Pr[(i,t^{\prime})\in\mathcal{A}_{1}]+\Pr[(i,t^{\prime})\in\mathcal{A}_{2}]=(0.5+\kappa)\cdot
x_{i,t^{\prime}}$ for all $t^{\prime}<t$, we have

$\Pr[A_{i}]=\sum_{t^{\prime}\in[t^{i},t-1]}(0.5+\kappa)\cdot
x_{i,t^{\prime}}=(0.5+\kappa)\cdot(y_{i,t}-y_{i,t^{i}})\leq(0.5+\kappa)\cdot(1-\tau)=2\kappa.$

An analogous upper bound holds for $\Pr[A_{j}]$.

To simplify notation, let us assume for a moment that $i^{j}\leq
i^{j^{\prime}}$ (if $i^{j}>i^{j^{\prime}}$, simply swap the roles of $j$ and
$j^{\prime}$ in the following line). We apply Lemma 4.11 to get

$\displaystyle\Pr[F_{i,j}\wedge F_{i,j^{\prime}}]$
$\displaystyle\leq\Pr[F_{i^{j},j}\wedge F_{i^{j^{\prime}},j^{\prime}}]$
$\displaystyle=\Pr[F_{i^{j},j}\wedge
F_{i^{j},j^{\prime}}]\cdot\Pr[F_{i^{j},j}\wedge
F_{i^{j^{\prime}},j^{\prime}}\mid F_{i^{j},j}\wedge F_{i^{j},j^{\prime}}]$
$\displaystyle\leq\gamma_{\kappa}\cdot\Pr[F_{i^{j},j}]\cdot\Pr[F_{i^{j},j^{\prime}}]\cdot\Pr[F_{i^{j},j}\wedge
F_{i^{j^{\prime}},j^{\prime}}\mid F_{i^{j},j}\wedge F_{i^{j},j^{\prime}}]$
(via Lemma 4.11)
$\displaystyle=\gamma_{\kappa}\cdot\Pr[F_{i^{j},j}]\cdot\Pr[F_{i^{j},j^{\prime}}]\cdot\Pr[F_{i^{j^{\prime}},j^{\prime}}\mid
F_{i^{j},j}\wedge F_{i^{j},j^{\prime}}]\enspace.$

In this expression, we aim to combine the last two factors concerning the
events if item $j^{\prime}$ is free at some point in time. To this end,
observe that

$\displaystyle\Pr[F_{i^{j},j^{\prime}}]\cdot\Pr[F_{i^{j^{\prime}},j^{\prime}}\mid
F_{i^{j},j}\wedge F_{i^{j},j^{\prime}}]$
$\displaystyle=\Pr[F_{i^{j},j^{\prime}}]\cdot\prod_{i^{\prime}=i^{j}}^{i^{j^{\prime}}-1}\left(1-q_{i^{\prime}}\cdot\Pr[j^{\prime}\in\mathsf{FP}_{i^{\prime}}]\cdot\alpha_{i^{\prime},j^{\prime}}\right)$
$\displaystyle=\Pr[F_{i^{j},j^{\prime}}]\cdot\prod_{i^{\prime}=i^{j}}^{i^{j^{\prime}}-1}\left(1-x_{i^{\prime},j^{\prime}}\cdot\alpha_{i^{\prime},j^{\prime}}\right)$
$\displaystyle=\Pr[F_{i^{j^{\prime}},j^{\prime}}]\enspace,$

where the last equality uses the same ideas as Step (S2) in the proof of 4.12.
So, overall, we have

$\displaystyle\Pr[F_{i,j}\wedge F_{i,j^{\prime}}]\leq\Pr[F_{i^{j},j}\wedge
F_{i^{j^{\prime}},j^{\prime}}]\leq\gamma_{\kappa}\cdot\Pr[F_{i^{j},j}]\cdot\Pr[F_{i^{j^{\prime}},j^{\prime}}]\enspace.$
(16)

With this in mind, we are ready to prove the final statement as

$\displaystyle\Pr[F_{i,j}\wedge F_{i,j^{\prime}}]$
$\displaystyle\leq\Pr[F_{i^{j},j}\wedge F_{i^{j^{\prime}},j^{\prime}}]$
$\displaystyle\leq\gamma_{\kappa}\cdot\Pr[F_{i^{j},j}]\cdot\Pr[F_{i^{j^{\prime}},j^{\prime}}]$
(via Equation 16)
$\displaystyle=\gamma_{\kappa}\cdot\left(\Pr[F_{i,j}]+\Pr[A_{j}]\right)\cdot\left(\Pr[F_{i,j^{\prime}}]+\Pr[A_{j^{\prime}}]\right)$
$\displaystyle\leq\gamma_{\kappa}\cdot\left(\Pr[F_{i,j}]+2\kappa\right)\cdot\left(\Pr[F_{i,j^{\prime}}]+2\kappa\right)$
$\displaystyle\leq\gamma_{\kappa}\cdot\left(1+\frac{4\kappa}{0.5-\kappa}+\frac{4\kappa^{2}}{(0.5-\kappa)^{2}}\right)\cdot\Pr[F_{i,j}]\cdot\Pr[F_{i,j^{\prime}}]$
$\displaystyle=\gamma_{\kappa}\cdot\left(\frac{0.5+\kappa}{0.5-\kappa}\right)^{2}\cdot\Pr[F_{i,j}]\cdot\Pr[F_{i,j^{\prime}}]$
$\displaystyle=\Delta_{\kappa}\cdot\Pr[F_{i,j}]\cdot\Pr[F_{i,j^{\prime}}],$

where in the last inequality we used $\Pr[F_{i,j}],\Pr[F_{i,j^{\prime}}]\geq
0.5-\kappa$ and the last equality applies
$\gamma_{\kappa}:=1+\nicefrac{{(0.5+\kappa)^{2}}}{{0.5-\kappa}}$. ∎

##  5 Analyzing the Sample-based Algorithm

To update Algorithm 1 to run in polynomial time, instead of computing the
exact value of $\rho_{i,t}$ we estimate it with polynomially many samples. For
simplicity, we present the algorithm and its analysis for Bernoulli arrivals
when every success probability $q_{i,t}$ equals 1 (the relevant changes needed
for the generalizations are described in Appendix C and Appendix D,
respectively). The pseudocode is presented below; observe that we reduce the
constant $\kappa$ by an arbitrarily small $\epsilon>0$ in 1.

Algorithm 2 (parametrized by $\epsilon>0$)

1:$\kappa\leftarrow 0.0115-\epsilon$

2:Solve (LPon) for $\\{x_{i,t}\\}$

3:for each time $t$, if $t$ arrives do $\triangleright$ w.p. $p_{t}$

4: Define users $\mathsf{FP}_{t}:=\textsf{PS}((x_{i,t}/p_{t})_{i\in I})$
$\triangleright$ at most $c_{t}$ users get first proposals

5: for each user $i\in\mathsf{FP}_{t}$ do

6: if $i$ is available then

7: Allocate $i$ to $t$ with probability
$\alpha_{i,t}:=\min\left(1,\frac{0.5+\kappa}{1-(0.5+\kappa)\cdot\sum_{t^{\prime}<t}x_{i,t^{\prime}}}\right)$

8: Let $A_{t}\leftarrow\text{number of users allocated to }t\text{ thus far}$

9: Define users $\mathsf{SP}_{t}:=\textsf{PS}(((1-\frac{A_{t}}{c_{t}})\cdot
x_{i,t}/p_{t})_{i\in I})$ $\triangleright$ $\leq c_{t}-A_{t}$ users get second
proposal

10: for each user $i\in\mathsf{SP}_{t}$ with $\alpha_{i,t}=1$ do

11: if $i$ is available then

12: Do not compute $\sigma_{i,t}:=\mathbb{E}[\mathbbm{1}[i\text{ available
after
\lx@cref{creftypecap~refnum}{line:sample_based:sample_defAt}}]\cdot(1-\frac{A_{t}}{c_{t}})\mid
t\text{ arrived},(\hat{\sigma}_{i,t^{\prime}})_{t^{\prime}<t}]$;

13: Instead compute $\hat{\sigma}_{i,t}\leftarrow$ Empirical average of
$\sigma_{i,t}$ over $N:=50nT\cdot(\epsilon/400T)^{-2}\cdot\kappa^{-2}$
independent simulations, using previously computed values
$(\hat{\sigma}_{i,t^{\prime}})_{t^{\prime}<t}$

14:
$\hat{\beta}_{i,t}\leftarrow\min\Big{(}1,\left((0.5+\kappa)\cdot\sum_{t^{\prime}<t}x_{i,t^{\prime}}-(0.5-\kappa)\right)\cdot\frac{1}{\hat{\sigma}_{i,t}}\Big{)}.$

15: Allocate $i$ to $t$ with prob. $\hat{\beta}_{i,t}$

As before, the definition of $\rho_{i,t}$ is over the randomness in the
arrivals and algorithm up to when it reaches 8 for arrival $t$ in Algorithm 1,
with the previously computed values of $(\hat{\sigma}_{i,t^{\prime}})$ for
$t^{\prime}<t$. In particular, we do not recalculate these, but rather
inductively use them as defined previously. This is why we use the shorthand
of “conditioning on $(\hat{\sigma}_{i,t^{\prime}})_{t^{\prime}<t}$” when
defining $\rho_{i,t}$.

We start with the observation that our algorithm is unchanged for early pairs
$(i,t)$. In particular, the following lemmas still hold for Algorithm 2.

See 4.4

See 4.12

In the remainder of the analysis, we will need to track the errors incurred by
sampling. Note that by the Chernoff-Hoeffding bound, if $\sigma_{i,t}$ is
bounded away from 0 then the empirical average $\hat{\sigma}_{i,t}$ will be
within a close multiplicative factor.

######  Observation 5.1.

If $\sigma_{i,t}\geq\kappa$ then we have that
$\sigma_{i,t}/\hat{\sigma}_{i,t}\in\left[1-\frac{\epsilon}{200T},1+\frac{\epsilon}{200T}\right]$
with probability at least $1-2\cdot\exp(-100nT).$

###### Proof.

We straightforwardly bound

$\displaystyle\Pr\left[|\hat{\sigma}_{i,t}-\sigma_{i,t}|\geq\frac{\epsilon}{400T}\cdot\sigma_{i,t}\right]$
$\displaystyle\leq 2\cdot\exp\left(-2\cdot
N\cdot((\epsilon/400T)\cdot\sigma_{i,t})^{2}\right)$ $\displaystyle\leq
2\cdot\exp\left(-2\cdot N\cdot((\epsilon/400T)\cdot\kappa)^{2}\right)$
$\displaystyle\leq 2\cdot\exp\left(-100nT\right).$

Thus with probability at least $1-2\cdot\exp(-100nT)$, we have

$\sigma_{i,t}/\hat{\sigma}_{i,t}\in[(1+\epsilon/400T)^{-1},(1-\epsilon/400T)^{-1}].$

The observation follows directly. ∎

We now show inductively that our algorithm allocates each $(i,t)$ with
probability close to the idealized value of $(0.5+\kappa)\cdot x_{i,t}$ from
the exact (exponential-time) calculations. In particular, we show that that we
achieve a value of $(0.5+\kappa\pm\epsilon_{t})\cdot x_{i,t}$ where the error
$\epsilon_{t}$ accumulates only linearly in $t$.

######  Lemma 5.2.

For any online arrival $t$, with probability at least
$1-2nt\cdot\exp(-100nT)$, we have for every $t^{\prime}\leq t$ that

$\displaystyle\Pr[(i,t^{\prime})\in\mathcal{A}_{1}]+\Pr[(i,t^{\prime})\in\mathcal{A}_{2}]\in[(0.5+\kappa-\epsilon\cdot
t^{\prime}/T)\cdot x_{i,t^{\prime}},(0.5+\kappa+\epsilon\cdot
t^{\prime}/T)\cdot x_{i,t^{\prime}}].$ (17)

Note that once we have Lemma 5.2, it is immediate to bound the gain of
Algorithm 2. In particular, the social welfare achieved by Algorithm 2 is with
probability at least $1-2nT\cdot\exp(-100nT)$ lower-bounded by

$\displaystyle\sum_{t}\sum_{i}(0.5+\kappa-\epsilon\cdot t/T)\cdot x_{i,t}\cdot
v_{i,t}$ $\displaystyle\geq\sum_{t}\sum_{i}(0.5+\kappa-\epsilon)\cdot
x_{i,t}\cdot v_{i,t}$
$\displaystyle=(0.5115-2\epsilon)\cdot\text{OPT}\eqref{LP}$
$\displaystyle\geq(0.5115-2\epsilon)\cdot\mathrm{OPT}_{\mathrm{on}}.$

Note that for a realization of Algorithm 2, we can estimate its gain within a
small multiplicative error factor by simulating it over polynomially-many
independently sampled arrival sequences. Thus, this guarantee can be obtained
with high probability, and it only remains to prove Lemma 5.2.

###### Proof of Lemma 5.2..

By induction on $t$. We consider only the case where the lemma’s statement
holds for all $\\{1,2,\ldots,t-1\\}$, and note this is with probability at
least $1-2n(t-1)\cdot\exp(-100nT)$ by the inductive hypothesis. Note that for
any $i$ such that $(i,t)$ is early, we are done by 4.4.

For convenience of notation, let $\epsilon_{t}:=\epsilon\cdot t/T$ denote the
error accumulated up to time $t$. Using this notation, we can apply the
inductive hypothesis to bound

$\displaystyle\Pr[F_{i,t}]\in[1-(0.5+\kappa+\epsilon_{t})\cdot
y_{i,t},1-(0.5+\kappa-\epsilon_{t})\cdot y_{i,t}].$ (18)

Hence the probability late $(i,t)$ is allocated as a first pick satisfies

$\Pr[(i,t)\in\mathcal{A}_{1}]=x_{i,t}\cdot\Pr[F_{i,t}]\in[x_{i,t}-x_{i,t}\cdot(0.5+\kappa+\epsilon_{t})\cdot
y_{i,t},x_{i,t}-x_{i,t}\cdot(0.5+\kappa-\epsilon_{t})\cdot y_{i,t}]$

where we used the induction hypothesis for bounding $\Pr[F_{i,t}]$.

By Equation (5) the probability $(i,t)$ is allocated as a second pick is given
by

$\displaystyle\Pr[(i,t)\in\mathcal{A}_{2}]=x_{i,t}\cdot\sigma_{i,t}\cdot\hat{\beta}_{i,t}.$
(19)

As before, we aim to show that $\sigma_{i,t}$ is bounded away from $0$. Note
that analogously to Equation 6, we have

$\displaystyle\sigma_{i,t}$
$\displaystyle\geq\Pr[F_{i,t}]\cdot\left(\tau-\frac{\mathbb{E}[A_{t}\mid
t\text{ arrived},F_{i,t}]}{c_{t}}\right)$
$\displaystyle\geq\left(1-((0.5+\kappa+\epsilon_{t})\cdot
y_{i,t})\right)\cdot\left(\tau-\frac{\mathbb{E}[A_{t}\mid t\text{
arrived},F_{i,t}]}{c_{t}}\right).$ (20)

To bound the conditional expectation $\mathbb{E}[A_{t}\mid t\text{
arrived},F_{i,t}]$, we will (as before) upper bound the joint probability
$\Pr[F_{i,t}\wedge F_{j,t}]$, analogously to Lemma 4.9. Here, the main
contribution is from 4.12; the probability mass from late edges does not
greatly affect it for small $\kappa$, even when taking into account the
possible error introduced by sampling. As our algorithm is unchanged along
early edges, the proof from the body of the paper goes through in a very
similar fashion, which we formalize below.

We assume that both $y_{i,t}>\tau$ and $y_{j,t}>\tau$ (if neither, or just one
of these inequalities holds, the proof proceeds nearly identically with better
bounds). Let $t^{i}$ denote the latest resource in $[T]$ such that
$y_{i,t^{i}-1}\leq\tau$ and $y_{i,t^{i}}>\tau$ and similarly let $t^{j}$
denote the latest resource in $[T]$ such that $y_{j,t^{j}-1}\leq\tau$ and
$y_{i,t^{j}}>\tau$. Let $A_{i}$ denote the event that $i$ is allocated to some
arrival in $[t^{i},t-1]$ and let $A_{j}$ denote the event that $j$ is
allocated to some arrival in $[t^{j},t-1]$. Using the hypothesis that
$\Pr[(i,t^{\prime})\in\mathcal{A}_{1}]+\Pr[(i,t^{\prime})\in\mathcal{A}_{2}]\leq(0.5+\kappa+\epsilon_{t^{\prime}})\cdot
x_{i,t^{\prime}}$ for all $t^{\prime}<t$, we have

$\displaystyle\Pr[A_{i}]$
$\displaystyle\leq\sum_{t^{\prime}\in[t^{i},t-1]}(0.5+\kappa+\epsilon_{t^{\prime}})\cdot
x_{i,t^{\prime}}$
$\displaystyle\leq(0.5+\kappa+\epsilon_{t})\cdot(y_{i,t}-y_{i,t^{i}})$
$\displaystyle\leq(0.5+\kappa+\epsilon_{t})\cdot(1-\tau)$
$\displaystyle=(0.5+\kappa+\epsilon_{t})\cdot\frac{2\kappa}{0.5+\kappa}$
$\displaystyle=2\kappa+\epsilon_{t}\cdot\frac{2\kappa}{0.5+\kappa}$

An analogous upper bound holds for $\Pr[A_{j}]$. For convenience, let us
define $\eta_{\kappa}:=\nicefrac{{2\kappa}}{{0.5+\kappa}}$. With this, we can
bound

$\displaystyle\Pr[F_{i,t}\wedge F_{j,t}]$
$\displaystyle\leq\Pr[F_{i,t^{i}}\wedge F_{j,t^{j}}]$
$\displaystyle\leq\gamma_{\kappa}\cdot\Pr[F_{i,t^{i}}]\cdot\Pr[F_{j,t^{j}}]\hskip
156.49014pt\text{(\lx@cref{creftypecap~refnum}{lem:corrbound})}$
$\displaystyle=\gamma_{\kappa}\cdot\left(\Pr[F_{i,t}]+\Pr[A_{i}]\right)\cdot\left(\Pr[F_{j,t}]+\Pr[A_{j}]\right)$
$\displaystyle\leq\gamma_{\kappa}\cdot\left(\Pr[F_{i,t}]+2\kappa+\epsilon_{t}\eta_{\kappa}\right)\cdot\left(\Pr[F_{j,t}]+2\kappa+\epsilon_{t}\eta_{\kappa}\right)$
$\displaystyle\leq\zeta_{\kappa,\epsilon_{t}}\cdot\Pr[F_{i,t}]\cdot\Pr[F_{j,t}]$

where in the last inequality, we first use a lower bound on $\Pr[F_{i,t}]$ and
$\Pr[F_{j,t}]$ of $0.5-\kappa-\epsilon_{t}$ and defined

$\zeta_{\kappa,\epsilon_{t}}:=\gamma_{\kappa}\cdot\left(1+\frac{2(2\kappa+\epsilon_{t}\eta_{\kappa})}{0.5-\kappa-\epsilon_{t}}+\frac{(2\kappa+\epsilon_{t}\eta_{\kappa})^{2}}{(0.5-\kappa-\epsilon_{t})^{2}}\right).$

Now, following the calculation of Equation 7, we have

$\displaystyle\mathbb{E}[A_{t}\mid t\text{ arrived},F_{i,t}]$
$\displaystyle=\frac{x_{i,t}}{p_{t}}+\sum_{j\neq i}\frac{\Pr[F_{i,t}\wedge
F_{j,t}]}{\Pr[F_{i,t}]}\cdot\frac{x_{j,t}}{p_{t}}\cdot\alpha_{j,t}$
$\displaystyle\leq\frac{x_{i,t}}{p_{t}}+\sum_{j\neq
i}\zeta_{\kappa,\epsilon_{t}}\cdot\Pr[F_{j,t}]\cdot\frac{x_{j,t}}{p_{t}}\cdot\alpha_{j,t}$
$\displaystyle\leq\frac{x_{i,t}}{p_{t}}+\zeta_{\kappa,\epsilon_{t}}\cdot(0.5+\kappa+2\epsilon_{t})\cdot
c_{t}.$

For the final inequality, we are using $\Pr[F_{j,t}]\leq
1-(0.5+\kappa-\epsilon_{t})\cdot y_{i,t}$ by our hypothesis and substituting
${\alpha_{j,t}\leq\frac{0.5+\kappa}{1-(0.5+\kappa)y_{i,t}}}.$ Using that
$\nicefrac{{x_{i,t}}}{{p_{t}}}\leq 1-\tau$ as $(i,t)$ is late, we have

$\displaystyle\mathbb{E}[A_{t}\mid t\text{
arrived},F_{i,t}]\leq\left(1-\tau+\zeta_{\kappa,\epsilon_{t}}\cdot(0.5+\kappa+2\epsilon_{t})\right)\cdot
c_{t}$ (21)

as in 4.10.

Now, starting from Equation 20 and using Equation 21, we note

$\displaystyle\sigma_{i,t}$
$\displaystyle\geq\left(1-((0.5+\kappa+\epsilon_{t})\cdot
y_{i,t})\right)\cdot\left(2\tau-1-\zeta_{\kappa,\epsilon_{t}}\cdot(0.5+\kappa+2\epsilon_{t}))\right)$
$\displaystyle\geq\left(0.5-\kappa-\epsilon_{t}\right)\cdot\left(2\tau-1-\zeta_{\kappa,\epsilon_{t}}\cdot(0.5+\kappa+2\epsilon_{t}))\right)$
$\displaystyle\geq(0.5-\kappa-\epsilon_{t})\cdot\left(\frac{2\kappa}{0.5-\kappa}+\epsilon_{t}\right)$
$\displaystyle\text{for }\epsilon_{t}\leq 0.0001$ $\displaystyle\geq
2\kappa+0.1\epsilon_{t},$

where the second inequality uses $y_{i,t}\leq 1$ and the last inequality is a
straightforward calculation for sufficiently small $\epsilon$. The third
inequality is calculation-heavy and holds only for small $\epsilon$ and
$\kappa\leq 0.0115-\epsilon$, and requires some slightly tedious calculations.
For example, we can upper bound $\zeta_{\kappa,\epsilon_{t}}$ by noting that
for $\epsilon_{t}$ sufficiently small
$\frac{2(2\kappa+\epsilon_{t}\eta_{k})}{0.5-\kappa-\epsilon_{t}}\leq\frac{2(2\kappa)}{0.5-\kappa}+0.5\epsilon_{t}$
and
$\frac{(2\kappa+\epsilon_{t}\eta_{\kappa})^{2}}{(0.5-\kappa-\epsilon_{t})^{2}}\leq\frac{(2\kappa)^{2}}{(0.5-\kappa)^{2}}+0.1\epsilon_{t}$.

Thus

$\displaystyle\zeta_{\kappa,\epsilon_{t}}\cdot(0.5+\kappa+2\epsilon_{t})$
$\displaystyle\leq\gamma_{\kappa}\cdot\left(1+\frac{2(2\kappa)}{0.5-\kappa}+\frac{(2\kappa)^{2}}{(0.5-\kappa)^{2}}+0.6\epsilon_{t}\right)\cdot(0.5+\kappa+2\epsilon_{t})$
$\displaystyle\leq\gamma_{\kappa}\cdot\left(1+\frac{2(2\kappa)}{0.5-\kappa}+\frac{(2\kappa)^{2}}{(0.5-\kappa)^{2}}\right)\cdot(0.5+\kappa)+\epsilon_{t}\cdot(\dagger)+1.2\cdot\gamma_{\kappa}\cdot\epsilon_{t}^{2}$

for
$(\dagger):=\gamma_{\kappa}\cdot\left(0.6(0.5+\kappa)+2\left(1+\frac{2(2\kappa)}{0.5-\kappa}+\frac{(2\kappa)^{2}}{(0.5-\kappa)^{2}}\right)\right)<4.$
We loosely bound $4\epsilon_{t}+4\epsilon_{t}^{2}\leq 5\epsilon_{t}$ for
$\epsilon$ sufficiently small. So we just need to show
$2\tau-1-\gamma_{\kappa}\cdot\left(1+\frac{2(2\kappa)}{0.5-\kappa}+\frac{(2\kappa)^{2}}{(0.5-\kappa)^{2}}\right)\cdot(0.5+\kappa)-5\epsilon_{t}\geq\frac{2\kappa}{0.5-\kappa}+\epsilon_{t}.$
Using that $\epsilon_{t}\leq\epsilon$ it suffices to show $6\epsilon\leq
2\tau-1-\gamma_{\kappa}\cdot\left(1+\frac{2(2\kappa)}{0.5-\kappa}+\frac{(2\kappa)^{2}}{(0.5-\kappa)^{2}}\right)\cdot(0.5+\kappa)-\frac{2\kappa}{0.5-\kappa}.$
Recalling that $\kappa:=0.0115-\epsilon$, we note this reduces to a single-
variable inequality in only $\epsilon$. This is not easy to show directly, as
it crucially is true for the magic constant $0.0115$, but can readily be shown
by computer verification. Indeed, the RHS and LHS are easily seen to be
100-Lipschitz as functions of $\epsilon\in[0,0.1]$, say, so we confirm the RHS
is at least $10^{-5}$ larger than the LHS on a grid of $10^{6}$ points on
$[0,0.1]$.

Hence, we get $\sigma_{i,t}$ is bounded away from $0$ and can apply 5.1: for
any fixed $i$ such that $(i,t)$ is late, we have with probability at least
$1-2\cdot\exp(-100nT)$ that
$\sigma_{i,t}/\hat{\sigma}_{i,t}\in[1-\epsilon/200T,1+\epsilon/200T].$ Note
that in this case we have

$\displaystyle\frac{1}{\hat{\sigma}_{i,t}}$
$\displaystyle\leq\frac{1+\epsilon/200T}{\sigma_{i,t}}$
$\displaystyle\leq\frac{1+\epsilon/200T}{2\kappa+0.1\epsilon_{t}}.$

Recall $\hat{\beta}_{i,t}:=\min\Big{(}1,\left((0.5+\kappa)\cdot
y_{i,t}-(0.5-\kappa)\right)\cdot\frac{1}{\hat{\sigma}_{i,t}}\Big{)}.$ Note

$\displaystyle\left((0.5+\kappa)\cdot
y_{i,t}-(0.5-\kappa)\right)\cdot\frac{1}{\hat{\sigma}_{i,t}}\leq
2\kappa\cdot(2\kappa+0.1\epsilon_{t})^{-1}\cdot(1+\epsilon/200T)\leq 1$

where the final (loose) inequality follows as $T\geq 1$ and $\kappa\leq 0.4$.
This implies

$\displaystyle\Pr[(i,t)\in\mathcal{A}_{2}]$
$\displaystyle=x_{i,t}\cdot\sigma_{i,t}\cdot\hat{\beta}_{i,t}$ (Equation 19)
$\displaystyle=x_{i,t}\cdot\sigma_{i,t}\cdot\left((0.5+\kappa)\cdot
y_{i,t}-(0.5-\kappa)\right)\cdot\frac{1}{\hat{\sigma}_{i,t}}$
$\displaystyle\geq x_{i,t}\cdot(1-\epsilon/200T)\cdot\left((0.5+\kappa)\cdot
y_{i,t}-(0.5-\kappa)\right)$

and similarly

$\Pr[(i,t)\in\mathcal{A}_{2}]\leq
x_{i,t}\cdot(1+\epsilon/200T)\cdot\left((0.5+\kappa)\cdot
y_{i,t}-(0.5-\kappa)\right).$

Then, we have

$\displaystyle\Pr[(i,t)\in\mathcal{A}_{1}]$
$\displaystyle+\Pr[(i,t)\in\mathcal{A}_{2}]$ $\displaystyle\geq
x_{i,t}\cdot(1-(0.5+\kappa+\epsilon_{t})\cdot
y_{i,t}+(1-\nicefrac{{\epsilon}}{{200T}})\cdot((0.5+\kappa)y_{i,t}-(0.5-\kappa))$
$\displaystyle=x_{i,t}\cdot\left(1+y_{i,t}\left(-0.5-\kappa-\epsilon_{t}+(1-\nicefrac{{\epsilon}}{{200T}})\cdot(0.5+\kappa)\right)-(1-\nicefrac{{\epsilon}}{{200T}})\cdot(0.5-\kappa)\right)$
$\displaystyle\geq
x_{i,t}\cdot\left(1+\left(-0.5-\kappa-\epsilon_{t}+(1-\nicefrac{{\epsilon}}{{200T}})\cdot(0.5+\kappa)\right)-(1-\nicefrac{{\epsilon}}{{200T}})\cdot(0.5-\kappa)\right),$

where the last inequality uses that the coefficient of $y_{i,t}$ above is
$-0.5-\kappa-\epsilon_{t}+(1-\nicefrac{{\epsilon}}{{200T}})(0.5+\kappa)$,
which is non-positive. Hence we can bound

$\displaystyle\Pr[(i,t)\in\mathcal{A}_{1}]+\Pr[(i,t)\in\mathcal{A}_{2}]$
$\displaystyle\geq
x_{i,t}\cdot(1-(0.5+\kappa+\epsilon_{t})+(1-\epsilon/200T)\cdot 2\kappa)$
$\displaystyle=x_{i,t}\cdot\left(0.5+\kappa-\epsilon_{t}-\frac{\epsilon}{100T}\cdot\kappa\right).$
$\displaystyle\geq x_{i,t}\cdot\left(0.5+\kappa-\epsilon_{t+1}\right).$

We also have the analogous upper bound

$\displaystyle\Pr[(i,t)\in\mathcal{A}_{1}]+\Pr[(i,t)\in\mathcal{A}_{2}]\leq
x_{i,t}\cdot\left(0.5+\kappa+\epsilon_{t+1}\right).$

By the union bound, with probability at least $1-2n\cdot\exp(-100nT)$ these
two bounds hold for all $i$ with $(i,t)$ late. Via the inductive hypothesis,
our starting assumption occurred with probability at least
$1-2n(t-1)\cdot\exp(-100nT)$. Hence, by a final application of the union
bound, we have that our desired property for arrivals $\\{1,2,\ldots,t\\}$
holds with probability at least $1-2nt\cdot\exp(-100nT).$

∎

##  6 Conclusion and Future Directions

We gave the first algorithm achieving an approximation ratio strictly better
than $\nicefrac{{1}}{{2}}$ for capacitated online resource allocation, when
comparing to the (computationally inefficient) optimum online algorithm. Our
algorithm crucially limited the (necessary) positive correlation between
offline users, and analyzed this via an inductive bound depending on the total
LP flow sent to an individual user. This challenge does not arise in
competitive analysis, and lends credence to the value of the optimum online as
a complementary benchmark to the prophet.

Numerous directions for future research are suggested by our work. Can our
guarantee of $0.5+\kappa$ for $\kappa=0.0115$ be improved, perhaps by rounding
stronger LPs? Is there a better tradeoff possible between the amount of
positive correlation we introduce for early arrivals and the approximation
ratio possible on late ones?

Finally, we believe the techniques developed for handling positive correlation
may prove useful for future generalizations. The prophet inequalities
literature has studied more general settings than capacitated allocation where
the tight $\nicefrac{{1}}{{2}}$-guarantee is known [FGL15, DFKL20], and our
work gives some evidence that it is possible to get an improved approximation
ratio against the online benchmark for these problems as well.

## References

  * [ACCB+23] Vashist Avadhanula, Andrea Celli, Riccardo Colini-Baldeschi, Stefano Leonardi, and Matteo Russo.  Fully dynamic online selection through online contention resolution schemes.  In Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence, AAAI’23/IAAI’23/EAAI’23. AAAI Press, 2023.
  * [Ada11] Marek Adamczyk.  Improved analysis of the greedy algorithm for stochastic matching.  Information Processing Letters (IPL), 111(15):731–737, 2011.
  * [AGKM11] Gagan Aggarwal, Gagan Goel, Chinmay Karande, and Aranyak Mehta.  Online vertex-weighted bipartite matching and single-bid budgeted allocations.  In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1253–1264, 2011.
  * [AGM15] Marek Adamczyk, Fabrizio Grandoni, and Joydeep Mukherjee.  Improved approximation algorithms for stochastic matching.  In Nikhil Bansal and Irene Finocchi, editors, Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, volume 9294 of Lecture Notes in Computer Science, pages 1–12. Springer, 2015.
  * [AHL12] Saeed Alaei, MohammadTaghi Hajiaghayi, and Vahid Liaghat.  Online prophet-inequality matching with applications to ad allocation.  In Proceedings of the 13th ACM Conference on Electronic Commerce (EC), pages 18–35, 2012.
  * [AHL13] Saeed Alaei, MohammadTaghi Hajiaghayi, and Vahid Liaghat.  The online stochastic generalized assignment problem.  In Prasad Raghavendra, Sofya Raskhodnikova, Klaus Jansen, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings, volume 8096 of Lecture Notes in Computer Science, pages 11–25. Springer, 2013.
  * [Ala14] Saeed Alaei.  Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers.  SIAM Journal on Computing (SICOMP), 43(2):930–972, 2014.
  * [AM23] Ali Aouad and Will Ma.  A nonparametric framework for online stochastic matching with correlated arrivals.  In Kevin Leyton-Brown, Jason D. Hartline, and Larry Samuelson, editors, Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, United Kingdom, July 9-12, 2023, page 114. ACM, 2023.
  * [ANSS19] Nima Anari, Rad Niazadeh, Amin Saberi, and Ali Shameli.  Nearly optimal pricing algorithms for production constrained and laminar bayesian selection.  In Proceedings of the 20th ACM Conference on Economics and Computation (EC), pages 91–92, 2019.
  * [BC21] Guy Blanc and Moses Charikar.  Multiway online correlated selection.  In Proceedings of the 62nd Symposium on Foundations of Computer Science (FOCS), pages 1277–1284, 2021.
  * [BDL22] Mark Braverman, Mahsa Derakhshan, and Antonio Molina Lovett.  Max-weight online stochastic matching: Improved approximations against the online benchmark.  In David M. Pennock, Ilya Segal, and Sven Seuken, editors, EC ’22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11 - 15, 2022, pages 967–985. ACM, 2022.
  * [BGL+12] Nikhil Bansal, Anupam Gupta, Jian Li, Julián Mestre, Viswanath Nagarajan, and Atri Rudra.  When lp is the cure for your matching woes: Improved bounds for stochastic matchings.  Algorithmica, 63(4):733–762, 2012.
  * [BHK+24] Kiarash Banihashem, MohammadTaghi Hajiaghayi, Dariusz R Kowalski, Piotr Krysta, and Jan Olkowski.  Power of posted-price mechanisms for prophet inequalities.  In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4580–4604. SIAM, 2024.
  * [BK10] Bahman Bahmani and Michael Kapralov.  Improved bounds for online stochastic matching.  In Mark de Berg and Ulrich Meyer, editors, Algorithms - ESA 2010, 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I, volume 6346 of Lecture Notes in Computer Science, pages 170–181. Springer, 2010.
  * [BK23] Alexander Braun and Thomas Kesselheim.  Simplified prophet inequalities for combinatorial auctions.  In 2023 Symposium on Simplicity in Algorithms (SOSA), pages 381–389, 2023.
  * [BM19] Jackie Baek and Will Ma.  Prophet inequalities on the intersection of a matroid and a graph.  CoRR, abs/1906.04899, 2019.
  * [BMR20] Allan Borodin, Calum MacRury, and Akash Rakheja.  Bipartite stochastic matching: Online, random order, and iid models.  arXiv preprint arXiv:2004.14304, 2020.
  * [BSSX16] Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan, and Pan Xu.  New algorithms, better bounds, and a novel model for online stochastic matching.  In Proceedings of the 24th Annual European Symposium on Algorithms (ESA), pages 24:1–24:16, 2016.
  * [BSSX20] Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan, and Pan Xu.  Online stochastic matching: New algorithms and bounds.  Algorithmica, 82(10):2737–2783, 2020.
  * [CC23] José Correa and Andrés Cristi.  A constant factor prophet inequality for online combinatorial auctions.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, page 686–697, New York, NY, USA, 2023. Association for Computing Machinery.
  * [CCF+22] José Correa, Andrés Cristi, Andrés Fielbaum, Tristan Pollner, and S. Matthew Weinberg.  Optimal item pricing in online combinatorial auctions.  In Karen Aardal and Laura Sanità, editors, Integer Programming and Combinatorial Optimization, pages 126–139, Cham, 2022. Springer International Publishing.
  * [CGKM20] Shuchi Chawla, Kira Goldner, Anna R. Karlin, and J. Benjamin Miller.  Non-adaptive matroid prophet inequalities.  CoRR, abs/2011.09406, 2020.
  * [CHMS10] Shuchi Chawla, Jason D Hartline, David L Malec, and Balasubramanian Sivan.  Multi-parameter mechanism design and sequential posted pricing.  In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), pages 311–320, 2010.
  * [CIK+09] Ning Chen, Nicole Immorlica, Anna R Karlin, Mohammad Mahdian, and Atri Rudra.  Approximating matches made in heaven.  In Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP), pages 266–278, 2009.
  * [DFKL20] Paul Dütting, Michal Feldman, Thomas Kesselheim, and Brendan Lucier.  Prophet inequalities made easy: Stochastic optimization by pricing nonstochastic inputs.  SIAM Journal on Computing (SICOMP), 49(3), 2020.
  * [DGR+23] Paul Dütting, Evangelia Gergatsouli, Rojin Rezvan, Yifeng Teng, and Alexandros Tsigonias-Dimitriadis.  Prophet secretary against the online optimal.  In Kevin Leyton-Brown, Jason D. Hartline, and Larry Samuelson, editors, Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, United Kingdom, July 9-12, 2023, pages 561–581. ACM, 2023.
  * [DK15] Paul Dütting and Robert Kleinberg.  Polymatroid prophet inequalities.  In Nikhil Bansal and Irene Finocchi, editors, Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, volume 9294 of Lecture Notes in Computer Science, pages 437–449. Springer, 2015.
  * [DKL20] Paul Dütting, Thomas Kesselheim, and Brendan Lucier.  An ${O}(\log\log m)$ prophet inequality for subadditive combinatorial auctions.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 306–317. IEEE, 2020.
  * [DSSX21] John P. Dickerson, Karthik A. Sankararaman, Aravind Srinivasan, and Pan Xu.  Allocation problems in ride-sharing platforms: Online matching with offline reusable resources.  ACM Trans. Econ. Comput., 9(3), June 2021.
  * [EFGT20] Tomer Ezra, Michal Feldman, Nick Gravin, and Zhihao Gavin Tang.  Online stochastic max-weight matching: prophet inequality for vertex and edge arrival models.  In Proceedings of the 21st ACM Conference on Economics and Computation (EC), pages 769–787, 2020.
  * [FGL15] Michal Feldman, Nick Gravin, and Brendan Lucier.  Combinatorial auctions via posted prices.  In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 123–135, 2015.
  * [FHTZ20] Matthew Fahrbach, Zhiyi Huang, Runzhou Tao, and Morteza Zadimoghaddam.  Edge-weighted online bipartite matching.  In Proceedings of the 61st Symposium on Foundations of Computer Science (FOCS), 2020.  To Appear.
  * [FLT+22] Hu Fu, Pinyan Lu, Zhihao Gavin Tang, Abner Turkieltaub, Hongxun Wu, Jinzhao Wu, and Qianfan Zhang.  Oblivious online contention resolution schemes.  In Symposium on Simplicity in Algorithms (SOSA), pages 268–278, 2022.
  * [FMMM09] Jon Feldman, Aranyak Mehta, Vahab Mirrokni, and S Muthukrishnan.  Online stochastic matching: Beating 1-1/e.  In Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS), pages 117–126, 2009.
  * [FNS19] Yiding Feng, Rad Niazadeh, and Amin Saberi.  Linear programming based online policies for real-time assortment of reusable resources.  SSRN Electronic Journal, 01 2019.
  * [FNS22] Yiding Feng, Rad Niazadeh, and Amin Saberi.  Near-optimal bayesian online assortment of reusable resources.  In Proceedings of the 23rd ACM Conference on Economics and Computation, EC ’22, page 964–965, New York, NY, USA, 2022. Association for Computing Machinery.
  * [FSZ16] Moran Feldman, Ola Svensson, and Rico Zenklusen.  Online contention resolution schemes.  In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1014–1033, 2016.
  * [GHH+21] Ruiquan Gao, Zhongtian He, Zhiyi Huang, Zipei Nie, Bijun Yuan, and Yan Zhong.  Improved online correlated selection.  In Proceedings of the 62nd Symposium on Foundations of Computer Science (FOCS), 2021.  To Appear.
  * [GHK+14] Oliver Göbel, Martin Hoefer, Thomas Kesselheim, Thomas Schleiden, and Berthold Vöcking.  Online independent set beyond the worst-case: Secretaries, prophets, and periods.  In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, volume 8573 of Lecture Notes in Computer Science, pages 508–519. Springer, 2014.
  * [GKPS06] Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, and Aravind Srinivasan.  Dependent rounding and its applications to approximation algorithms.  Journal of the ACM (JACM), 53(3):324–360, 2006.
  * [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.
  * [GU23] Vineet Goyal and Rajan Udwani.  Online matching with stochastic rewards: Optimal competitive ratio via path-based formulation.  Oper. Res., 71(2):563–580, 2023.
  * [GW19] Nikolai Gravin and Hongao Wang.  Prophet inequality for bipartite matching: Merits of being simple and non adaptive.  In Proceedings of the 20th ACM Conference on Economics and Computation (EC), pages 93–109, 2019.
  * [HJS+23] Zhiyi Huang, Hanrui Jiang, Aocheng Shen, Junkai Song, Zhiang Wu, and Qiankun Zhang.  Online matching with stochastic rewards: Advanced analyses using configuration linear programs.  In Jugal Garg, Max Klimm, and Yuqing Kong, editors, Web and Internet Economics - 19th International Conference, WINE 2023, Shanghai, China, December 4-8, 2023, Proceedings, volume 14413 of Lecture Notes in Computer Science, pages 384–401. Springer, 2023.
  * [HKS07] Mohammad Taghi Hajiaghayi, Robert Kleinberg, and Tuomas Sandholm.  Automated online mechanism design and prophet inequalities.  In Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI), pages 58–65, 2007.
  * [HMZ11] Bernhard Haeupler, Vahab S. Mirrokni, and Morteza Zadimoghaddam.  Online stochastic weighted matching: Improved approximation algorithms.  In Ning Chen, Edith Elkind, and Elias Koutsoupias, editors, Internet and Network Economics - 7th International Workshop, WINE 2011, Singapore, December 11-14, 2011. Proceedings, volume 7090 of Lecture Notes in Computer Science, pages 170–181. Springer, 2011.
  * [HS21] Zhiyi Huang and Xinkai Shu.  Online stochastic matching, poisson arrivals, and the natural linear program.  In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 682–693. ACM, 2021.
  * [HSY22] Zhiyi Huang, Xinkai Shu, and Shuyi Yan.  The power of multiple choices in online stochastic matching.  In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 91–103. ACM, 2022.
  * [HZ20] Zhiyi Huang and Qiankun Zhang.  Online primal dual meets online matching with stochastic rewards: configuration lp to the rescue.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, page 1153–1164, New York, NY, USA, 2020. Association for Computing Machinery.
  * [JL13] Patrick Jaillet and Xin Lu.  Online stochastic matching: New algorithms with better bounds.  Mathematics of Operations Research, 2013.
  * [JMZ22] Jiashuo Jiang, Will Ma, and Jiawei Zhang.  Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1221–1246, 2022.
  * [KS78] Ulrich Krengel and Louis Sucheston.  On semiamarts, amarts, and processes with finite value.  Probability on Banach spaces, 4:197–266, 1978.
  * [KVV90] Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani.  An optimal algorithm for on-line bipartite matching.  In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), pages 352–358, 1990.
  * [KW19] Robert Kleinberg and S Matthew Weinberg.  Matroid prophet inequalities and applications to multi-dimensional mechanism design.  Games and Economic Behavior, 113:97–115, 2019.
  * [LS18] Euiwoong Lee and Sahil Singla.  Optimal online contention resolution schemes via ex-ante prophet inequalities.  In Proceedings of the 26th Annual European Symposium on Algorithms (ESA), pages 57:1–57:14, 2018.
  * [Luc17] Brendan Lucier.  An economic view of prophet inequalities.  ACM SIGecom Exchanges, 16(1):24–47, 2017.
  * [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.
  * [MMG23] Calum MacRury, Will Ma, and Nathaniel Grammel.  On (random-order) online contention resolution schemes for the matching polytope of (bipartite) graphs.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1995–2014, 2023.
  * [MP12] Aranyak Mehta and Debmalya Panigrahi.  Online matching with stochastic rewards.  In Symposium on Foundations of Computer Science (FOCS), 2012.
  * [MWZ15] 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 (SODA-15), pages 1388–1404, 2015.
  * [NSW23] Joseph Naor, Aravind Srinivasan, and David Wajc.  Online dependent rounding schemes.  CoRR, abs/2301.08680, 2023.
  * [PPSW21] Christos Papadimitriou, Tristan Pollner, Amin Saberi, and David Wajc.  Online stochastic max-weight bipartite matching: Beyond prophet inequalities.  In Proceedings of the 22nd ACM Conference on Economics and Computation (EC), pages 763–764, 2021.
  * [PRSW22] Tristan Pollner, Mohammad Roghani, Amin Saberi, and David Wajc.  Improved online contention resolution for matchings and applications to the gig economy.  In Proceedings of the 23rd ACM Conference on Economics and Computation, EC ’22, page 321–322, New York, NY, USA, 2022. Association for Computing Machinery.
  * [Rub16] Aviad Rubinstein.  Beyond matroids: secretary problem and prophet inequality with general constraints.  In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’16, page 324–332, New York, NY, USA, 2016. Association for Computing Machinery.
  * [SC84] Ester Samuel-Cahn.  Comparison of threshold stop rules and maximum for independent nonnegative random variables.  the Annals of Probability, 12(4):1213–1216, 1984.
  * [Sri01] Aravind Srinivasan.  Distributions on level-sets with applications to approximation algorithms.  In Proceedings of the 42nd Symposium on Foundations of Computer Science (FOCS), pages 588–597, 2001.
  * [SW21] Amin Saberi and David Wajc.  The greedy algorithm is _not_ optimal for on-line edge coloring.  In Proceedings of the 48th International Colloquium on Automata, Languages and Programming (ICALP), pages 109:1–109:18, 2021.
  * [TT22] Alfredo Torrico and Alejandro Toriello.  Dynamic relaxations for online bipartite matching.  INFORMS Journal on Computing, 2022.
  * [TWW22] Zhihao Gavin Tang, Jinzhao Wu, and Hongxun Wu.  (Fractional) online stochastic matching via fine-grained offline statistics.  In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC), pages 77–90, 2022.

##  Appendix A Informative Examples and Observations

In this section, we give some examples and observations which might help to
gain a deeper understanding of the problem.

###  A.1 The Generalization of [BDL22] Fails

Given the attention previously dedicated to the unit-capacity case, we first
ask how these algorithms perform for the capacitated problem. Previous works
for matching have all used the LP relaxation (LPon) with $c_{t}=1$, in the
special case where each success probability $q_{i,t}$ equals 1. In the
simplest case where every resource $t$ either (i) arrives with a fixed
capacity and values, with probability $p_{t}$ or (ii) does not arrive, with
probability $1-p_{t}$, the algorithm works in the following way: in the case
that resource $t$ arrives, every available user $i$ sends a proposal to $t$
with probability

$\frac{x_{i,t}}{p_{t}\cdot\left(1-\sum_{t^{\prime}<t}x_{i,t^{\prime}}\right)},$

an expression that is at most 1 by (LPon) Constraint (2). The resource is
matched to the proposing user with highest value $v_{i,t}$. [BDL22] show that
this algorithm gives a $(1-1/e)$-approximation against (LPon), and hence also
the optimum online benchmark.

To account for capacities, we might naturally generalize this algorithm to
match an arriving resource $t$ to the top $c_{t}$ proposing users.
Surprisingly, this small modification drastically changes the algorithm’s
performance.

See 1.3

###### Proof.

Take some $n$ such that $n>\frac{2}{\epsilon}$, and consider an instance with
$n$ users and two resources. The first resource has a capacity of $n$ (i.e.,
values are additive over all users), arrives with probability $1-1/n$ and
values are $1$ for each user individually. The second resource is unit-
capacity, arrives with probability 1, and values are $n^{2}$ for each user
individually. All allocations are successful with probability 1.

The unique optimal solution to (LPon) sets $x_{i,1}=1-1/n$ for every pair
$(i,1)$ incident to the first resource, and sets $x_{i,2}=1/n$ for every pair
$(i,2)$ incident to the second resource. Thus, when running (the natural
generalization of) [BDL22], every user proposes to the first resource if it
arrives, and hence with probability $1-1/n$ all users are assigned in the
first timestep. If the first resource does not arrive, exactly one user is
allocated to the second unit-capacity resource. Hence the expected gain of the
algorithm is $\left(1-\frac{1}{n}\right)\cdot n+\frac{1}{n}\cdot n^{2}=2n-1$.
However clearly for this instance $\mathrm{OPT}_{\mathrm{on}}\geq n^{2}$. ∎

###  A.2 Positive Correlation is Required

Next, we argue that we _need_ to have positive correlation for general
capacitated resource allocation.

See 1.4

###### Proof.

Let $F_{i,t}$ denote an indicator for user $i$ being free just before the
arrival of resource $t$. Consider resource $t$ with capacity two arriving with
probability $\epsilon$ which is adjacent to two users $\\{i,j\\}$ with unit
values. Imagine the LP sets a value of $\epsilon$ on each edge. To achieve an
approximation factor of $(0.5+\kappa)$ against LP, we are required to have
that that the expected number of users assigned to $t$ is at least
$(0.5+\kappa)\cdot 2\epsilon$. Equivalently, we must have

$\Pr[F_{i,t+1}]+\Pr[F_{j,t+1}]<2-(0.5+\kappa)\cdot 2\epsilon$

implying

$\Pr[F_{i,t+1}]\cdot\Pr[F_{j,t+1}]<(1-(0.5+\kappa)\cdot\epsilon)^{2}=1-(1+2\kappa)\epsilon+O(\epsilon^{2}).$

However, because $i$ and $j$ can only be matched if $t$ arrives, we have

$\displaystyle\Pr[F_{i,t+1}\wedge F_{j,t+1}]$ $\displaystyle\geq
1-\epsilon>\Pr[F_{i,t+1}]\cdot\Pr[F_{j,t+1}],$

where the final inequality holds for sufficiently small $\epsilon$. ∎

###  A.3 On the Gap of (LPon)

######  Example A.1.

There exists an instance of online capacitated allocation where

$\frac{\mathrm{OPT}_{\mathrm{on}}}{\textup{OPT}\eqref{LP}}\leq 0.75.$

###### Proof.

Consider an instance with two offline users, and two stochastic arrivals. The
first resource has capacity 2, and arrives with probability
$\nicefrac{{1}}{{2}}$; the second resource has capacity 1 and arrives with
probability 1. Both resources have a value of 1 for each user; every edge is
successful with probability 1.

The optimum online algorithm achieves a value of 2 if the first user arrives,
and a value of 1 otherwise, hence achieving $1.5$ in expectation. However, a
feasible solution to (LPon) sets $x_{i,t}=\nicefrac{{1}}{{2}}$ for every edge
$(i,t)$, hence achieving a value of 2. ∎

###  A.4 A Bound Depending on $\min_{t}c_{t}$.

As mentioned in Section 4.2.2, the bound following Equation 8 in the proof of
4.10 is not tight if all $c_{t}$ are strictly greater than one. Still, even
though this step looks quite lossy at first glance, we are not losing much in
our analysis by replacing $\min_{t}c_{t}$ with one. To see this, consider
replacing the last inequality in the proof of 4.10 with a bound depending on
$\min_{t}c_{t}$. Doing so, we get

$\displaystyle\mathbb{E}[A_{t}\mid t\text{ arrived},F_{i,t}]$
$\displaystyle\leq 1-\tau+\Delta_{\kappa}\cdot(0.5+\kappa)\cdot c_{t}$
$\displaystyle=\left(\frac{1-\tau}{c_{t}}+\Delta_{\kappa}\cdot(0.5+\kappa)\right)\cdot
c_{t}$
$\displaystyle\leq\left(\frac{1-\tau}{\min_{t^{\prime}}c_{t^{\prime}}}+\Delta_{\kappa}\cdot(0.5+\kappa)\right)\cdot
c_{t}.$ (22)

As a consequence, in order to show the desired lower bound on $\rho_{i,t}$, we
first can use the same reasoning as we used in order to derive Equation 9, but
use Inequality (A.4) instead:

$\displaystyle\rho_{i,t}\geq(1-(0.5+\kappa)\cdot
y_{i,t})\cdot\left(\tau-\left(\frac{1-\tau}{\min_{t^{\prime}}c_{t^{\prime}}}+\Delta_{\kappa}\cdot(0.5+\kappa)\right)\right).$

Thus, the right-hand side needs to be at least as large as
$(0.5+\kappa)y_{i,t}-(0.5-\kappa)$. In other words, we are required to show
that

$\displaystyle(1-(0.5+\kappa)\cdot
y_{i,t})\cdot\left(\tau-\left(\frac{1-\tau}{\min_{t^{\prime}}c_{t^{\prime}}}+\Delta_{\kappa}\cdot(0.5+\kappa)\right)\right)\geq(0.5+\kappa)y_{i,t}-(0.5-\kappa).$

Hence we can take any $\kappa$ such that

$\displaystyle\tau-\left(\frac{1-\tau}{\min_{t^{\prime}}c_{t^{\prime}}}+\Delta_{\kappa}\cdot(0.5+\kappa)\right)\geq\frac{2\kappa}{0.5-\kappa}.$
(23)

As a consequence, we can now solve Equation 23 for $\kappa$ in order to
improve upon the constant of $0.0115$ which we used initially, as a function
of $\min_{t}c_{t}$. In Table 1, we state these constants for
$\min_{t}c_{t}\in\\{2,\dots,9\\}$, demonstrating that there is little loss in
our analysis of Algorithm 1 when replacing $\min_{t}c_{t}$ with $1$.

$\min_{t}c_{t}$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---|---
$\kappa$ | 0.0115 | 0.0126 | 0.0131 | 0.0133 | 0.0134 | 0.0135 | 0.01362 | 0.01367 | 0.01371
Table 1: Values of $\kappa$ depending on $\min_{t}c_{t}$

##  Appendix B Deferred Proofs

In this section, we provide proofs which were deferred from the main body.

###  B.1 Proof of Theorem 1.5

See 1.5

###### Proof.

We apply Theorem 19 of [BHK+24], as our problem of capacitated resource
allocation can be viewed exactly as what they call a _prophet inequalities
problem_. Using their notation, we take $\mathcal{A}^{\text{inp}}$ to be
Algorithm 3, with expected social welfare
$\mathbb{E}[v(\mathcal{A}^{\text{inp}})]$. Note that Algorithm 3 is what
[BHK+24] call “past-valuation-independent,” as its allocation decision for
buyer $t$ depends only on the set of available items, the arriving
valuation/capacity $v_{t}(\cdot)$, and the LP solution calculated from
knowledge of the input distributions. Note also that for each buyer $t$, the
outcome space (what [BHK+24] refer to as “$X_{t}$”) is of size at most
$\binom{n}{c_{t}}=\text{poly}(n)$ because $c_{t}$ is upper bounded by a
constant. Finally, although our distribution over $v_{t}(\cdot)$ is not
continuous, it is not hard to satisfy this assumption by adding a small amount
of noise or a tiebreaking coordinate (as mentioned in [BHK+24]).

Hence, there is a pricing based algorithm $\mathcal{A}^{\text{out}}$ which
uses $\text{poly}(T,\binom{n}{\max_{t}c_{t}},\nicefrac{{1}}{{\epsilon}})$ many
samples, runs in time
$\text{poly}(T,\binom{n}{\max_{t}c_{t}},\nicefrac{{1}}{{\epsilon}})$ and whose
expected social welfare satisfies

$\mathbb{E}[\mathcal{A}^{\text{out}}]\geq(1-\epsilon)\cdot\mathbb{E}[\mathcal{A}^{\text{in}}].$

∎

###  B.2 Proof of 2.1

See 2.1

###### Proof.

Define an indicator random variable $X_{i,t}$ for every pair $(i,t)$, which is
one if and only if the optimum online algorithm allocates user $i$ to resource
$t$. In addition, let $Q_{i,t}$ be the indicator which is one if the
assignment of the pair $(i,t)$ was successful; i.e. the independent Bernoulli
coin flip with probability $q_{i,t}$ comes up heads.

Denote by $x^{\ast}_{i,t}=\mathbb{E}[X_{i,t}]$. First, note that the welfare
achieved by the optimum online algorithm is

$\mathrm{OPT}_{\mathrm{on}}=\mathbb{E}\left[\sum_{i,t}v_{i,t}X_{i,t}Q_{i,t}\right]=\sum_{i,t}v_{i,t}\cdot
x^{\ast}_{i,t}\cdot q_{i,t},$

coinciding with the objective of (LPon). Here the expectation is over the
randomness in $X_{i,t}$ as well as the success probabilities for $(i,t)$, and
we crucially use that the successful realization of $(i,t)$ is independent of
our decision to allocate along $(i,t)$.

Also, observe that for any resource $t$, we have $\sum_{i}X_{i,t}=0$ if the
resource does not arrive, and $\sum_{i}X_{i,t}\leq c_{t}$ if the resource
arrives, as any algorithm is allowed to allocate at most $c_{t}$ users to
resource $t$ if the resource arrives. Hence

$\sum_{i}x^{\ast}_{i,t}=\mathbb{E}\left[\sum_{i}X_{i,t}\right]=\Pr\left[t\text{
arrives}\right]\cdot\mathbb{E}\left[\sum_{i}X_{i,t}\mathrel{}\middle|\mathrel{}t\text{
arrives}\right]\leq p_{t}\cdot c_{t}.$

Finally, note that if resource $t$ arrives, the optimum online algorithm can
only allocate user $i$ if it is available. For user $i$ being available, it
had not to be allocated to some previous resource $t^{\prime}<t$ whose
independent coin flip $Q_{i,t^{\prime}}$ was successful as well. Crucially,
for any online algorithm, the event that user $i$ is available at time $t$ is
independent of the arrival of resource $t$ (this does not hold for an offline
algorithm). Hence, we observe

$\displaystyle x^{\ast}_{i,t}$
$\displaystyle=\mathbb{E}[X_{i,t}]=\Pr\left[t\text{
arrives}\right]\cdot\mathbb{E}\left[X_{i,t}\mathrel{}\middle|\mathrel{}t\text{
arrives}\right]$ $\displaystyle\leq
p_{t}\cdot\mathbb{E}\left[1-\sum_{t^{\prime}<t}X_{i,t^{\prime}}Q_{i,t^{\prime}}\mathrel{}\middle|\mathrel{}t\text{
arrives}\right]$
$\displaystyle=p_{t}\cdot\mathbb{E}\left[1-\sum_{t^{\prime}<t}X_{i,t^{\prime}}Q_{i,t^{\prime}}\right]=p_{t}\cdot\left(1-\sum_{t^{\prime}<t}x^{\ast}_{i,t^{\prime}}\cdot
q_{i,t^{\prime}}\right).$

As a consequence, $\\{x_{i,t}^{\ast}\\}_{i,t}$ is a feasible solution to
(LPon) and hence, $\text{OPT}\eqref{LP}\geq\mathrm{OPT}_{\mathrm{on}}$. ∎

###  B.3 Proof of 4.14

See 4.14

###### Proof.

Plugging in the definition of
$f(z)=1+z\cdot\left(\frac{(0.5+\kappa)^{2}}{1-z\cdot(0.5+\kappa)}\right)$, the
claim is equivalent to

$\displaystyle\left(1+\frac{(0.5+\kappa)^{2}y}{1-(0.5+\kappa)y}\right)\left(1+\frac{(0.5+\kappa)^{2}x}{1-(0.5+\kappa)(x+y)}\right)\leq
1+\frac{(0.5+\kappa)^{2}(x+y)}{1-(0.5+\kappa)(x+y)}.$

Multiplying out the left-hand side and subtracting
$1+\frac{(0.5+\kappa)^{2}x}{1-(0.5+\kappa)(x+y)}$ on both sides, this is
equivalent to

$\displaystyle\frac{(0.5+\kappa)^{2}y}{1-(0.5+\kappa)y}+\frac{(0.5+\kappa)^{2}y}{1-(0.5+\kappa)y}\cdot\frac{(0.5+\kappa)^{2}x}{1-(0.5+\kappa)(x+y)}\leq\frac{(0.5+\kappa)^{2}y}{1-(0.5+\kappa)(x+y)}.$

If $y=0$, the claim is trivially true. If $y>0$, we can divide both sides by
$(0.5+\kappa)^{2}y$ to get

$\displaystyle\frac{1}{1-(0.5+\kappa)y}+\frac{1}{1-(0.5+\kappa)y}\cdot\frac{(0.5+\kappa)^{2}x}{1-(0.5+\kappa)(x+y)}\leq\frac{1}{1-(0.5+\kappa)(x+y)}.$

Multiplying both sides by $(1-(0.5+\kappa)y)\cdot(1-(0.5+\kappa)(x+y))$, we
get

$\displaystyle 1-(0.5+\kappa)(x+y)+(0.5+\kappa)^{2}x\leq 1-(0.5+\kappa)y.$

Subtracting $1-(0.5+\kappa)y$ on both sides, we finally end up with

$\displaystyle-(0.5+\kappa)x+(0.5+\kappa)^{2}x\leq 0$

which is clear. ∎

##  Appendix C Beyond Bernoulli Distributions

When not restricting the model to Bernoulli arrivals, for every round $t$,
there is a known distribution $\\{p_{t,j}\\}_{j}$ over valuation vectors
$\\{v_{i,t,j}\\}_{i}$ and a capacity $c_{t,j}$. Upon the arrival of resource
$t$, it samples one index $j\in\\{1,\dots,m\\}$ with probability
$p_{t,j}$888We assume without loss of generality that all resource share the
same space of valuation vectors and capacities, and we can set $p_{t,j}=0$ if
realization $j$ is not feasible for resource $t$. Also, we assume that
resources always arrive by adding a valuation vector containing only zeros
with the probability of resource $t$ not arriving., and realizes capacity
$c_{t,j}$ and values $\\{v_{i,t,j}\\}_{i}$ over users. For the ease of
exposition, we discuss general arrivals in the case that each success
probability $q_{i,t,j}=1$, and describe the changes needed to handle arbitrary
success probabilities $q_{i,t,j}\in[0,1]$ in Appendix D.

##### Generalized LP

We generalize LPon as follows.

$\displaystyle\max\ $ $\displaystyle\sum_{i,t,j}x_{i,t,j}\cdot v_{i,t,j}$
(General-LPon) s.t. $\displaystyle\sum_{t}\sum_{j}x_{i,t,j}\leq 1$
$\displaystyle\text{for all }i\in I$ (24) $\displaystyle\sum_{i}x_{i,t,j}\leq
p_{t,j}\cdot c_{t,j}$ $\displaystyle\text{for all }t\in[T],j\in[m]$ (25)
$\displaystyle 0\leq x_{i,t,j}\leq
p_{t,j}\cdot\left(1-\sum_{t^{\prime}<t}\sum_{j^{\prime}}x_{i,t^{\prime},j^{\prime}}\right)$
$\displaystyle\text{for all }i\in I,t\in[T],j\in[m]$ (26)

In an equivalent manner to 2.1, we can argue that also for general
distributions, $\mathrm{OPT}\eqref{generalLP}\geq\mathrm{OPT}_{\mathrm{on}}$,
i.e. General-LPon is a relaxation of the optimum online algorithm.

##### Generalized Algorithm.

In order to round any fractional LP solution to an integral one in an online
fashion, we extend our Algorithm 1 as follows: In round $t$, we see the
realization of index $j$. We replace all previous LP variables with the ones
from the generalized LP for index $j$ and run the slightly modified Algorithm
3.

Algorithm 3

1:$\kappa\leftarrow 0.0115$

2:Solve (General-LPon) for $\\{x_{i,t,j}\\}$

3:for each time $t$ do

4: Observe index $j$ sampled from $(p_{t,j})_{j}$

5: Define users $\mathsf{FP}_{t,j}:=\textsf{PS}((x_{i,t,j}/p_{t,j})_{i\in I})$

6: for each user $i\in\mathsf{FP}_{t,j}$ do

7: if $i$ is available then

8: Allocate $i$ to $t$ with probability
$\alpha_{i,t}:=\min\left(1,\frac{0.5+\kappa}{1-(0.5+\kappa)\cdot\sum_{t^{\prime}<t}\sum_{j^{\prime}}x_{i,t^{\prime},j^{\prime}}}\right)$

9: Let $A_{t,j}\leftarrow\text{number of users allocated to }t\text{ with
sampled index }j\text{ thus far}$

10: Define users
$\mathsf{SP}_{t,j}:=\textsf{PS}\left(\left(\left(1-\frac{A_{t,j}}{c_{t,j}}\right)\cdot
x_{i,t,j}/p_{t,j}\right)_{i\in I}\right)$

11: for each user $i\in\mathsf{SP}_{t,j}$ with $\alpha_{i,t}=1$ do

12: if $i$ is available then

13: Compute $\rho_{i,t,j}:=\mathbb{E}\left[\mathbbm{1}[i\text{ available after
\lx@cref{creftypecap~refnum}{line:sample_defAtj_general}}]\cdot\left(1-\frac{A_{t,j}}{c_{t,j}}\right)\mid
t\text{ sampled index }j\right]$

14:
$\beta_{i,t,j}\leftarrow\min\Big{(}1,\left((0.5+\kappa)\cdot\sum_{t^{\prime}<t}\sum_{j}x_{i,t^{\prime},j}-(0.5-\kappa)\right)\cdot\frac{1}{\rho_{i,t,j}}\Big{)}.$

15: Allocate $i$ to $t$ with prob. ${\beta_{i,t,j}}$

As in our Bernoulli case, observe that we choose ${\beta_{i,t,j}}$ in a way so
that the following holds: $\Pr[(i,t)\text{ assigned for sampled index
}j]=(0.5+\kappa)\cdot x_{i,t,j}$. Also, note that this algorithm can be
implemented in polynomial time in the number of resources and users and the
size of the support of the distributions. Concerning the computation of
$\rho_{i,t,j}$, we can observe that for our choice of $\kappa=0.0115$, the
generalized analysis also shows that any $\rho_{i,t,j}$ is lower bounded by a
constant; equivalently to the Bernoullli case. This can be used to estimate
$\rho_{i,t,j}$ via samples with a multiplicative error as small as desired,
implying a $(0.5+\kappa-\epsilon)$-approximate algorithm, following the logic
of Section 5.

##### Generalized Analysis.

In order to prove the generalization of Theorem 4.1, the major work is to
change the syntax of the lemmas on the way. We do not give details for all
lemmas but rather provide the key steps on what to change and how to overcome
obstacles on the way.

First, we extend and change several definitions such as
$y_{i,t}:=\sum_{t^{\prime}<t}\sum_{j}x_{i,t^{\prime},j}$ or
$\mathcal{A}_{1}^{j}$, $\mathcal{A}_{2}^{j}$ as the set of assignments $(i,t)$
if the realized index is $j$ via a first or second proposal. The lemmas,
observations and statements which referred to “$t$ arriving” are now with
respect to the event “$t$ realizes index $j$”. For example, when talking about
assigning $i$ to $t$ via a first proposal, we replace this by saying that we
assign $i$ to $t$ via a first proposal when $t$ realized the valuation vector
with index $j$.

The proofs for the analysis of early pairs directly carry over after adapting
the syntax. For late pairs, the generalization of the proof of Lemma 4.5 (i)
is also straightforward, as is the combination of both analyses at the end.

We need to take some care in generalizing the proof of Lemma 4.5 (ii). The
majority of the steps can be extended straightforwardly via syntactic
generalization from Section 4 (or Section 5 with an estimate of the
expectation in 13). In contrast, the proof of generalized versions of the
correlation bound from Section 4.3, and in particular 4.12 need some short
updates. Note however that as 4.12 only concerns early pairs, it is not
affected by the updates for a sample-based algorithm as in Section 5.

To see why 4.12 also holds in the more general variant, we go through its
proof steps one-by-one. Concerning the generalization of Step (S1) we note
that the probability of both users being free after time $t+1$ can still be
decomposed as the product of the probability of both being free before times
the conditional probability of assigning neither via a first proposal (as in
Equation 10). Still, we are required to sum the latter conditional
probabilities for all possible realizations of $j$. Doing so, we first follow
Steps (S1) and (S2) from the Bernoulli case. During Step (S3), we need to show
that for two distinct users $i,i^{\prime}$ and resource $t$, the following
inequality holds: