Randomized Rounding Approaches to Online Allocation, Sequencing, and Matching

Will Ma Graduate School of Business and Data Science Institute, Columbia
University, New York, NY 10027<EMAIL_ADDRESS>
Randomized rounding is a technique that was originally used to approximate
hard offline discrete optimization problems from a mathematical programming
relaxation. Since then it has also been used to approximately solve sequential
stochastic optimization problems, overcoming the curse of dimensionality. To
elaborate, one first writes a tractable linear programming relaxation that
prescribes probabilities with which actions should be taken. Rounding then
designs a (randomized) online policy that approximately preserves all of these
probabilities, with the challenge being that the online policy faces hard
constraints, whereas the prescribed probabilities only have to satisfy these
constraints in expectation. Moreover, unlike classical randomized rounding for
offline problems, the online policy’s actions unfold sequentially over time,
interspersed by uncontrollable stochastic realizations that affect the
feasibility of future actions. This tutorial provides an introduction for
using randomized rounding to design online policies, through four self-
contained examples representing fundamental problems in the area: online
contention resolution, stochastic probing, stochastic knapsack, and stochastic
matching.

To appear as an INFORMS 2024 Tutorial.

online algorithms, stochastic optimization, randomized rounding, approximation
ratio

##  1 Introduction

In online decision-making, one must commit to a sequence of decisions while
facing uncertainty about the future. We consider online decision-making
problems where we have full probabilistic knowledge of the way in which future
uncertainties may unfold, and the performance of a decision-making policy is
defined by expected reward. In these problems, an optimal policy that
maximizes performance can always be described using dynamic programming.
However, computing such a policy is often intractable, due to an exponential
state space in the dynamic programming.

We take instead a relax-and-round approach to these problems. In the first
step, we write a computationally tractable Linear Program (LP) that is a
relaxation, which means that its optimal objective value
$\mathsf{OPT}_{\mathsf{LP}}$ is no worse than the performance of dynamic
programming. In the second step, we “round” a solution of this LP to construct
an online decision-making policy in a computationally tractable manner.

We illustrate the Relax-and-Round approach through the following problem.
There are agents $i=1,\ldots,n$, each with a known weight $w_{i}\geq 0$ and a
known independent probability $p_{i}$ with which they will show up. The policy
observes sequentially whether each agent shows up, and must immediately decide
accept or reject for each agent who shows up. There is capacity to accept up
to $k$ agents, and the performance of a policy (to be maximized) is the
expected total weight of agents it accepts.

For the first step, we write the following LP relaxation:

$\displaystyle\max\quad$ $\displaystyle\sum_{i=1}^{n}w_{i}x_{i}$ (1a)
$\displaystyle\mathrm{s.t.}\quad$ $\displaystyle\sum_{i=1}^{n}x_{i}\leq k$
(1b) $\displaystyle 0\leq x_{i}\leq p_{i}$ $\displaystyle\forall i=1,\ldots,n$
(1c)

This LP is computationally tractable because it is polynomially sized. To see
that it is a relaxation, suppose we set each variable $x_{i}$ equal to the
probability of an optimal policy accepting agent $i$. Constraint (1b), which
says that at most $k$ agents are accepted in expectation, is satisfied because
the policy accepts at most agents $k$ on every sample path. Constraint (1c) is
satisfied because the policy cannot accept an agent $i$ with probability
greater than the probability $p_{i}$ with which they show up. This proves that
setting the $x_{i}$’s equal to the acceptance probabilities of an optimal
policy defines a feasible solution to the LP, whose objective value
$\sum_{i}w_{i}x_{i}$ equals the performance of the optimal policy. Therefore,
$\mathsf{OPT}_{\mathsf{LP}}$ is no less than the performance the optimal
policy; i.e., the LP is a relaxation.

For the second step, given a feasible solution $(x_{i})_{i=1}^{n}$ to the LP,
the goal is to find an online policy that accepts every agent $i$ with
probability at least $cx_{i}$, for a constant $c$ as large as possible. We
call this a sequential randomized rounding (SRR) problem. To explain why, let
$X_{i}\in\\{0,1\\}$ indicate whether our online policy accepts agent $i$. The
goal can be restated as to randomly “round” the fractional vector
$(x_{i})_{i=1}^{n}$ into an integer vector $(X_{i})_{i=1}^{n}$, approximately
preserving acceptance probabilities in that

$\displaystyle\mathbb{E}[X_{i}]$ $\displaystyle\geq cx_{i}$
$\displaystyle\forall i=1,\ldots,n.$ (2)

Importantly, the rounding is sequential, where an online policy must decide
each $X_{i}$ without knowing which future agents will show up, while biding by
the problem constraints that at most $k$ agents can be accepted and only
agents who show up can be accepted.

Generally, that goal of SRR is to establish a constant $c\in[0,1]$ such that
(2) can be satisfied for any instance of the problem and any feasible solution
to the LP, in a computationally tractable manner. This would imply a
$c$-approximate algorithm, which is an algorithm that can compute tractably
for any instance an online policy whose performance is at least $c$ times that
of an optimal policy. To see why, we can run the policy satisfying (2) on an
optimal solution $(x_{i})_{i=1}^{n}$ to the LP, and the expected total weight
of agents accepted would be at least $\sum_{i}w_{i}(cx_{i})$, i.e. the
performance would be at least $c\cdot\mathsf{OPT}_{\mathsf{LP}}$. This in turn
is at least $c$ times the performance of an optimal policy, by virtue of the
LP being a relaxation. Constant $c$ is often referred to as the approximation
ratio.

That being said, the SRR approach has additional implications beyond
approximation ratios. In fact, for this problem a $c$-approximate algorithm is
meaningless, because an optimal policy can be directly computed using dynamic
programming (the state space is not exponential). However, for this problem
the SRR approach additionally implies that an online policy can have
performance at least $c$ times that of the offline policy, which knows in
advance the agents who will show up and accepts from among them the $k$ agents
with highest weights. To see why, suppose we set each $x_{i}$ equal to the
probability of the offline policy accepting agent $i$. It follows from the
same argument that constraints (1b)–(1c) are satisfied, and hence the
performance $\sum_{i}w_{i}x_{i}$ of the offline policy can be feasibly
attained in the LP. Therefore, it is no greater than
$\mathsf{OPT}_{\mathsf{LP}}$, and the SRR policy that has performance at least
$c\cdot\mathsf{OPT}_{\mathsf{LP}}$ also has performance at least $c$ times
that of the offline policy. Turning to a second additional implication of SRR,
we note that (2) promises every agent $i$ that they will be accepted with
probability at least $c$ conditional on showing up. This can be interpreted as
a form of “fairness”, which is not satisfied by dynamic programming.

###  1.1 Outline of Tutorial

This tutorial serves as an introduction to SRR, expounding on concepts and
providing details that are difficult to find in academic papers. It also
provides a list of references to more advanced topics that can serve as a
(brief) survey.

We describe four self-contained problems that represent fundamental
applications of SRR. The first is an SRR problem by definition, whereas SRR is
used to derive state-of-the-art approximation algorthms for the latter three
problems.

  * •

Online Bayesian Selection (Section 2): we study an SRR problem that is
essentially identical to the one from the Introduction, motivated by a mobile
pantry allocating food supplies while satisfying fairness across agents. We
discuss the differences between agents being encountered in a fixed order
(Subsection 2.1) vs. random order (Subsection 2.2), and explain how these are
special cases of the Online Contention Resolution Scheme (OCRS) problem
(Subsection 2.3).

  * •

Probing and Search (Section 3): we study the simplest stochastic probing
problem, motivated by a hiring firm that dynamically decides on the order to
send offers to candidates. We write an LP relaxation and solve the
corresponding SRR problem to derive approximation ratios and adaptivity gaps.
We later extend to problems where the firm must first interview applicants to
decide their value, as well as the ProbeMax problem (Subsection 3.1).

  * •

Stochastic Knapsack (Section 4): we study the stochastic knapsack problem,
which can be viewed as a stochastic scheduling problem where rewards are
collected for completing jobs in a finite horizon. We write an LP relaxation
and solve the corresponding SRR problem to derive an approximation ratio,
where the technique can be flexibly extended to finite-horizon Markovian
bandits problems.

  * •

Stochastic Matching (Section 5): we study variants of the maximum matching
problem in graphs that have both sequential decisions and stochastic
realizations. We first apply the SRR result from Section 2 to derive a
1/2-approximate algorithm for online stochastic matching, before specializing
to IID arrivals (Subsection 5.1), discussing stochastic probing and search in
graphs (Subsection 5.2), and returning to OCRS for the matching polytope
(Subsection 5.3). Some of these problems were instrumental to the development
of the SRR approach, but are deferred to the end due to being more advanced.

We conclude with a summary of the key techniques and concepts in SRR learned
through this tutorial, along with a discussion of future directions (Section
6).

###  1.2 Related Materials

First, the online allocation and matching problems we study often consider the
“competitive ratio” against the offline policy. Positive results for SRR can
generally be translated into positive results for competitive ratio, but we do
not focus on this in the tutorial, instead referring to surveys about prophet
inequalities (Lucier [53], Correa et al. [23]) and online matching (Mehta et
al. [60], Huang and Tröbst [43], Huang et al. [42]). We note that the online
matching literature also considers competitive ratios in the “adversarial”
setting, in which case one can use “online” randomized rounding procedures
that do not know the inputs to be rounded in advance. By contrast, we focus on
“sequential” randomized rounding in stochastic settings where one does know
the input probabilities in advance.

Second, we limit our scope to sequential randomized rounding for sequential
stochastic optimization problems, whereas randomized rounding itself has a
much longer history in approximating NP-hard integer programming problems in
combinatorial optimization. Classical examples of randomized rounding can be
found in many chapters of books on approximation algorithms (Vazirani [73],
Williamson and Shmoys [75]).

Finally, we restrict to Bayesian settings where the given probability
distributions are assumed to be correct. Meanwhile, several tutorials have
been written about distributionally robust optimization (Kuhn et al. [50],
Blanchet et al. [14]), where the goal is to hedge against distribution shifts.

##  2 Online Bayesian Selection

We study a fundamental problem in sequential randomized rounding problem that
we motivate using fairness. We will later use it as a building block for
online resource allocation in Section 5.

######  Problem 2.1 ($k$-unit Rationing)

There is a set of agents $[n]$, where we will generally let $[n]$ denote
$\\{1,\ldots,n\\}$. A mobile food pantry produces $k$ units of food supplies
at the start of each day and drives by the agents in fixed order $1,\ldots,n$.
As long as food remains upon reaching an agent $i$, the mobile pantry can
optionally offer a unit of food to the agent. If the mobile pantry offers
food, then the agent takes it independently with probability (w.p.) $x_{i}$,
representing the probability of agent $i$ needing food on a given day that is
known to the mobile pantry. The mobile pantry aims to maximize the probability
$\gamma$ with which it can promise every agent that they will be offered food.
The mobile pantry can skip offering food to earlier agents in order to ration
food for later agents, but it cannot turn around to return to a skipped agent.

###### Remark 2.2

An alternate, equivalent formulation of Problem 2.1 is that the mobile pantry
first asks if the agent needs food, and if so, decides whether to give food.
This alternate formulation is better known in the literature, as the Online
Contention Resolution Scheme (OCRS) problem which has a wide array of
applications (see Subsection 2.3). Regardless, in this tutorial we focus on
the formulation in Problem 2.1 instead, which originally appeared in Alaei [2]
as the “Magician’s problem”.

An optimal rationing policy for Problem 2.1 requires randomization. For
example, suppose there is $k=1$ food supply and $n=2$ agents with
$x_{1}=x_{2}=1/2$. If the mobile pantry always offers food to agent 1, then it
would get taken with w.p. $x_{1}$, leaving food for agent 2 w.p. only
$1-x_{1}=1/2$. On the other hand, if the mobile pantry always skips agent 1,
then agent 1 is being offered food w.p. 0. In this example the mobile pantry
can in fact promise $\gamma=2/3$ to both agents: each day, it randomly decides
to offer food to agent 1 w.p. 2/3; it then offers any remaining food to agent
2. Agent 1 would be offered food w.p. 2/3, while agent 2 would be offered food
w.p.

$\displaystyle 1-\Pr[\text{agent 1 was offered food}]\Pr[\text{agent 1 needs
food}]=1-\frac{2}{3}\cdot\frac{1}{2}=\frac{2}{3}.$

This is the optimal policy and promise guarantee for this example.

Alaei [2] showed how to solve this rationing problem in general, when $k=1$.
Indeed, consider any fixed $\gamma>0$ that the mobile pantry would like to
guarantee. If there is food remaining when the mobile pantry drives by agent
$i$, then it must offer food w.p.

$\displaystyle\frac{\gamma}{\Pr[\text{food remains for agent $i$}]},$ (3)

so that the unconditional probability of agent $i$ being offered food is
exactly

$\displaystyle\Pr[\text{food remains for agent
$i$}]\cdot\frac{\gamma}{\Pr[\text{food remains for agent $i$}]}=\gamma.$

Therefore, given any $\gamma$, the rationing policy is determined. The optimal
promise is then the maximum $\gamma$ for which this determined policy is
feasible, which requires the probability in (3) to be at most 1. This is
established in the theorem below.

###### Theorem 2.3

For any instance of Problem 2.1 defined by $k=1$ and vector
$(x_{i})_{i\in[n]}$, Algorithm 1 with $\gamma=1/(1+\sum_{i<n}x_{i})$ is the
optimal policy and guarantee.

Algorithm 1 for Problem 2.1 assuming $k=1$, parameterized by $\gamma>0$

for agents $i=1,\ldots,n$ do

Draw an independent random bit $A_{i}$ that is 1 w.p.
$\gamma/(1-\gamma\sum_{j<i}x_{j})$

if food remains and $A_{i}=1$ then

Offer food to agent $i$

end if

end for

###### Proof 2.4

Proof of Theorem 2.3. Let $Y_{i},X_{i}\in\\{0,1\\}$ be the indicator random
variables for agent $i$ being offered food and needing food, respectively. In
order to have a guarantee of $\gamma$, we must have $\mathbb{E}[Y_{i}]=\gamma$
for all $i$. However, $Y_{n}\leq 1-\sum_{i<n}Y_{i}X_{i}$, because food can
only be offered to agent $n$ if it was not already offered to an earlier agent
who needed the food. We get

$\displaystyle\gamma=\mathbb{E}[Y_{n}]\leq
1-\sum_{i<n}\mathbb{E}[Y_{i}]\mathbb{E}[X_{i}]=1-\sum_{i<n}\gamma x_{i},$ (4)

applying both the linearity of expectation and the independence of $X_{i}$.
Rearranging (4) proves that the guarantee $\gamma$ cannot exceed
$1/(1+\sum_{i<n}x_{i})$.

We now prove that if Algorithm 1 is run with parameter
$\gamma=1/(1+\sum_{i<n}x_{i})$, then
$\mathbb{E}[Y_{i}]=\gamma=1/(1+\sum_{i<n}x_{i})$ for all $i$. We induct over
$i=1,\ldots,n$. By definition, $\mathbb{E}[Y_{1}]=\mathbb{E}[A_{1}]=\gamma$.
For $i>1$, food is offered if and only if it still remains and $A_{i}=1$, so

$\displaystyle\mathbb{E}[Y_{i}]$
$\displaystyle=\mathbb{E}\left[1-\sum_{j<i}Y_{j}X_{j}\right]\mathbb{E}[A_{i}]$
$\displaystyle=(1-\sum_{j<i}\gamma
x_{j})\frac{\gamma}{1-\gamma\sum_{j<i}x_{j}}$

where the first equality applies the independence of $A_{i}$; the second
equality applies the independence of $X_{j}$ and the definition of $A_{i}$.
The final expression cancels to equal $\gamma$, completing the induction.

Finally, we must that verify Algorithm 1 is feasible, by showing that the
probability of random bit $A_{i}$ lies in [0,1] for all $i$. Substituting in
the value of $\gamma$, this probability can be re-written as

$\displaystyle\mathbb{E}[A_{i}]=\frac{1}{1/\gamma-\sum_{j<i}x_{j}}=\frac{1}{1+\sum_{i<n}x_{i}-\sum_{j<i}x_{j}}=\frac{1}{1+\sum_{j=i}^{n-1}x_{j}}$

which clearly satisfies
$0\leq\mathbb{E}[A_{1}]\leq\cdots\leq\mathbb{E}[A_{n}]=1$.

###  2.1 What if $k>1$?

Food pantries should have starting supply $k$ greater than 1. However, this
significantly complicates the problem, illustrating perhaps the main intricacy
of sequential randomized rounding. Indeed, suppose $k=2$, and the mobile
pantry is deciding whether to offer food to agent 2. At this point, there
would be either 1 or 2 units remaining, with

$\displaystyle\Pr[\text{1 unit remaining}]$
$\displaystyle=\Pr[\text{agent\leavevmode\nobreak\ 1 was offered
food}]\Pr[\text{agent\leavevmode\nobreak\ 1 needs food}]=\gamma x_{1}.$

To offer food to agent 2 w.p. $\gamma$, the algorithm must define random bits
$A_{2}^{\prime},A_{2}^{\prime\prime}$ satisfying

$\displaystyle\Pr[\text{1 unit
remaining}]\cdot\mathbb{E}[A_{2}^{\prime}]+\Pr[\text{2 units
remaining}]\cdot\mathbb{E}[A_{2}^{\prime\prime}]=\gamma$
$\displaystyle\Longleftrightarrow$ $\displaystyle\gamma
x_{1}\mathbb{E}[A_{2}^{\prime}]+(1-\gamma
x_{1})\mathbb{E}[A_{2}^{\prime\prime}]=\gamma$ (5)

where $A_{2}^{\prime},A_{2}^{\prime\prime}$ indicate whether to offer food to
agent $2$ when there are $1,2$ units remaining, respectively. The key
difference from the $k=1$ case is even that for a fixed promise $\gamma$, the
rationing policy is no longer determined—the algorithm has a choice on how to
balance between the probabilities of $A_{2}^{\prime}$ and
$A_{2}^{\prime\prime}$.

Alaei [2] also proposed a rule for handling this case—first try to satisfy (5)
by fixing $\mathbb{E}[A_{2}^{\prime}]=0$ and setting
$\mathbb{E}[A_{2}^{\prime\prime}]=\gamma/(1-\gamma x_{1})$; if this is
infeasible because $\gamma/(1-\gamma x_{1})>1$, then instead set
$\mathbb{E}[A_{2}^{\prime\prime}]=1$ and increase $\mathbb{E}[A_{2}^{\prime}]$
as needed to satisfy (5). This is saying that we would always rather offer
food to agent 2 when there are 2 units remaining instead of 1 unit remaining;
only if this is insufficient to promise agent 2 a probability $\gamma$ of
being offered food (because the probability of having both units remaining is
too low), might we offer them the last remaining food supply. Alaei’s rule can
be generalized to an arbitrary $k$, and is quite intuitive: be more willing
offer food when there is more remaining, which is essentially the philosophy
of rationing.

Alaei’s rule is in fact optimal, as later proven by Jiang et al. [48], for any
instance defined by $k$, $n$, and $(x_{i})_{i\in[n]}$. They formalized Alaei’s
rule using the following LP:

$\displaystyle\max\quad$ $\displaystyle\gamma$ (6a) s.t.
$\displaystyle\gamma=\sum_{\ell=1}^{k}\alpha^{\ell}_{i}$ $\displaystyle\forall
i\in[n]$ (6b) $\displaystyle\beta^{\ell}_{i}=\begin{cases}1&i=1,\ell=k\\\
0&i=1,\ell<k\\\
\beta^{\ell}_{i-1}-(\alpha^{\ell}_{i-1}+\alpha^{\ell+1}_{i-1})x_{i-1}&i>1\end{cases}$
$\displaystyle\forall i\in[n],\ell\in[k]$ (6c) $\displaystyle
0\leq\alpha^{\ell}_{i}\leq\beta^{\ell}_{i}$ $\displaystyle\forall
i\in[n],\ell\in[k]$ (6d)

In this LP, $\alpha^{\ell}_{i}$ is a decision variable representing the
probability to offer food to agent $i$ when there are $\ell$ units remaining.
Note that $\alpha^{\ell}_{i}$ is an unconditional probability; e.g.
$\alpha^{1}_{2}$ would be correspond to the expression $\gamma
x_{1}\mathbb{E}[A_{2}^{\prime}]$ from (5) (trying to make $\alpha^{1}_{2}$
correspond to $\mathbb{E}[A_{2}^{\prime}]$ would result in non-linearities).
Meanwhile, $\beta^{\ell}_{i}$ is a “state” variable representing the
probability of having $\ell$ units remaining when driving by agent $i$,
updated via the equations (6c). For an agent $i>1$, we need to remove mass
from $\beta^{\ell}_{i}$ if we had $\ell$ units for agent $i-1$ and they took
one, and add mass to $\beta^{\ell}_{i}$ if we had $\ell+1$ units for agent
$i-1$ and they took one, reflecting the final equation in (6c) (in which
$\alpha^{k+1}_{i-1}$ is understood to be 0). Finally, $\gamma$ is a free
variable tuned to be the optimal guarantee.

######  Theorem 2.5 (Jiang et al. [48])

For any instance of Problem 2.1 defined by $k$, $n$, and $(x_{i})_{i\in[n]}$,
the optimal guarantee $\gamma$ is found by solving LP (6). Moreover, there
exists an optimal solution corresponding to Alaei’s rule, found by defining
$(\beta^{\ell}_{i})_{\ell\in[k]}$ via (6c) and then
$(\alpha^{\ell}_{i})_{\ell\in[k]}$ via

$\displaystyle\alpha^{k}_{i}=\min\\{\gamma,\beta^{\ell}_{i}\\},\quad\alpha^{k-1}_{i}=\min\\{\gamma-\alpha^{k}_{i},\beta^{\ell}_{i}\\},\quad\ldots,\quad\alpha^{1}_{i}=\min\\{\gamma-\sum_{\ell>1}\alpha^{\ell}_{i},\beta^{\ell}_{i}\\}$

over iterations $i=1,\ldots,n$. The corresponding optimal policy is: for
agents $i=1,\ldots,n$, conditional on the number of units remaining being
$\ell\in[k]$, offer one to the agent w.p.
$\alpha^{\ell}_{i}/\beta^{\ell}_{i}$.

######  Remark 2.6 (State Tracking)

The food rationing problem with $k>1$ is a good way to highlight two general
intricacies about sequential randomized rounding:

  * •

The algorithm should track the probabilities of the parallel states that it
could be in at any given time (achieved in this problem via the
$\beta^{\ell}_{i}$ variables in (6c), where $\ell$ is state and $i$ is time);

  * •

The action to take in one state depends on the hypothetical action that would
have been taken in another parallel state (achieved in this problem via (6b),
which couples the $\alpha^{\ell}_{i}$ variables across $\ell$).

In dynamic programming, updating Bellman’s equations requires knowing the
value-to-go from future states, but not the probability of being on the
current sample path, let alone the probabilities and actions for parallel
hypothetical sample paths that the algorithm could be in at the current time.
Therefore, the two intricacies in Remark 2.6 may seem counter-intuitive from a
dynamic programming perspective for online stochastic optimization. However,
they are crucial from the randomized rounding perspective, and in particular
crucial for this problem where there is a probabilistic fairness constraint.

###  2.2 What if the agents can be visited in a different order?

Although the optimal rationing policy can now be found, the fairness
constraint that every agent must be offered food with the same probability
results in a loss in efficiency. To illustrate this, we return to the earlier
example where there was $k=1$ unit and $n=2$ agents with $x_{1}=x_{2}=1/2$. We
saw that the optimal fair policy has guarantee $\gamma=2/3$, which means that
the food gets taken and utilized w.p. $\gamma(x_{1}+x_{2})=2/3$.
Alternatively, the policy that never skips the first agent utilizes the food
w.p. $x_{1}+(1-x_{1})x_{2}=3/4$, which is higher and hence more efficient.

In this example, the mobile pantry can in fact get the best of both worlds, if
on half of the days, if reversed its route and offered the food to agent 2
first. Indeed, each agent would then be offered food w.p.
$\gamma=\frac{1+1/2}{2}=3/4$, which in this case means that the utilization
probability is also $3/4(x_{1}+x_{2})=3/4$. Of course, in general it could be
costly to re-route, so it is useful to quantify the gain from being able to
visit agents in different orders on different days.

To quantify this, we define the efficiency to be $\gamma$, because subject to
the fairness constraint that every agent is offered food with the same
probability $\gamma$, the expected utilization is proportional to $\gamma$.
For an instance defined a vector $\mathbf{x}=(x_{i})_{i\in[n]}\in[0,1]^{n}$ of
arbitrary length $n$, we let $\gamma_{k}(\mathbf{x})$ denote the maximum
$\gamma$ possible when the mobile pantry produces $k$ units and visits the
agents in order $i=1,\ldots,n$, noting that $\gamma_{k}(\mathbf{x})$ equals
the optimal objective value of LP (6). Meanwhile, we let
$\gamma^{\mathsf{RO}}_{k}(\mathbf{x})$ denote the maximum $\gamma$ possible
when the mobile pantry produces $k$ units and visits the agents in a uniformly
random order. We are interested in how $\gamma_{k}(\mathbf{x})$ compares to
$\gamma^{\mathsf{RO}}_{k}(\mathbf{x})$; e.g. earlier we showed that
$\gamma_{1}(1/2,1/2)=2/3$ while $\gamma^{\mathsf{RO}}_{1}(1/2,1/2)=3/4$.

Following the literature, we compare the values of $\gamma_{k}(\mathbf{x})$
and $\gamma^{\mathsf{RO}}_{k}(\mathbf{x})$ under worst-case instances.
Although not critical for the results, we restrict to instances where
$\sum_{i=1}^{n}x_{i}\leq k$, an assumption that the supply meets the expected
demand. (This will always be satisfied when we apply these results beyond
fairness problems in Section 5.) For a fixed $k$, we compare the measures
$\gamma_{k}$ and $\gamma^{\mathsf{RO}}_{k}$, defined as

$\displaystyle\gamma_{k}=\inf_{n}\inf_{\mathbf{x}\in[0,1]^{n}:\sum_{i}x_{i}\leq
k}\gamma_{k}(\mathbf{x});$
$\displaystyle\gamma^{\mathsf{RO}}_{k}=\inf_{n}\inf_{\mathbf{x}\in[0,1]^{n}:\sum_{i}x_{i}\leq
k}\gamma^{\mathsf{RO}}_{k}(\mathbf{x}).$

Although it is perhaps more useful compare $\gamma_{k}(\mathbf{x})$ to
$\gamma^{\mathsf{RO}}_{k}(\mathbf{x})$ for the specific instance $\mathbf{x}$
in practice, the theoretical canon is to compare worst-case measures like
$\gamma_{k}$ and $\gamma^{\mathsf{RO}}_{k}$, because they are not specific to
the application at hand and not sensitive to a change in the instance. In this
particular problem, it is also unknown how to compute
$\gamma^{\mathsf{RO}}(\mathbf{x})$; there is no known LP formulation like (6).

We now derive the values of $\gamma_{1}$ and $\gamma^{\mathsf{RO}}_{1}$.
Theorem 2.3 says that $\gamma_{1}(\mathbf{x})=1/(1+\sum_{i<n}x_{i})$ for any
instance $\mathbf{x}$, from which it is easy to see that
$\gamma_{1}(\mathbf{x})\geq 1/2$ as long as $\sum_{i}x_{i}\leq 1$, and that
this lower bound is attained, implying $\gamma_{1}=1/2$. For
$\gamma^{\mathsf{RO}}_{1}$, although it is unknown how to compute
$\gamma^{\mathsf{RO}}(\mathbf{x})$, it can be lower-bounded using an algorithm
of Lee and Singla [51]. They employ a well-known trick for analyzing random
orders, which is to model every agent as arriving at a random “time” drawn
independently and uniformly from [0,1]. This will later allow for a clever
integration in the analysis.

###### Remark 2.7

If the agents arrive in a uniformly random order without arrival times, then
they can be assigned arrival times using the following process. Let Unif[0,1]
denote the uniform distribution over [0,1]. The process draws random variables
$U_{1},\ldots,U_{n}$ IID from Unif[0,1] and places them in a stack, sorted so
that the smallest number is on top and the largest number is on the bottom.
Whenever an agent $i$ arrives in the uniformly random order, we pretend that
their arrival time is the (smallest) number on the top of the stack, after
which we remove this number from the stack.

To see that the agents end up with IID Unif[0,1] arrival times, let
$\sigma:[n]\to[n]$ denote the random permutation such that the first agent to
arrive has index $\sigma(1)$, …, the last agent to arrive is $\sigma(n)$. The
distribution of arrival times is unchanged in an alternate world where
$\sigma$ is drawn first, and then the random variables $U_{1},\ldots,U_{n}$
are drawn conditional on $U_{\sigma(1)}<\cdots<U_{\sigma(n)}$. In this
alternate world, agent $\sigma(1)$ arrives at time $U_{\sigma(1)}$, …, agent
$\sigma(n)$ arrives at time $U_{\sigma(n)}$. That is, irrespective of $\sigma$
each agent $i=1,\ldots,n$ always gets assigned the arrival time $U_{i}$, which
is an independent Unif[0,1] random variable. Because this alternate world has
the same distribution of arrival times as the original process, this shows
that each agent $i$ indeed gets assned an independent Unif[0,1] arrival time.

######  Theorem 2.8 (Lee and Singla [51])

For any instance of Problem 2.1 satisfying $\sum_{i=1}^{n}x_{i}\leq k=1$,
Algorithm 2 offers food to every agent w.p. at least111We are technically
changing the problem formulation here, allowing agents to be offered food w.p.
greater than $\gamma$. This is actually the standard problem formulation,
which is equivalent in theory because an optimal policy never wants to offer
food to an agent w.p. greater than the required $\gamma$. $1-1/e$, assuming
agents are encountered in a uniformly random order.

Algorithm 2 for Problem 2.1 assuming $\sum_{i=1}^{n}x_{i}\leq k=1$ and random
order

Draw time $U_{i}$ independently for each agent $i$, uniformly from [0,1]

for agents $i=1,\ldots,n$ in increasing order of $U_{i}$ do

Draw an independent random bit $A_{i}$ that is 1 w.p. $e^{-U_{i}x_{i}}$

if food remains and $A_{i}=1$ then

Offer food to agent $i$

end if

end for

###### Proof 2.9

Proof of Theorem 2.8. Follow the same notation as in the proof of Theorem 2.3.
For any agent $i$,

$\displaystyle\mathbb{E}[Y_{i}]$
$\displaystyle=\int_{0}^{1}\mathbb{E}[Y_{i}|U_{i}=t]dt$
$\displaystyle=\int_{0}^{1}\mathbb{E}\Big{[}A_{i}\prod_{j\neq
i}(1-\mathbbm{1}(U_{j}<t)A_{j}X_{j})\Big{|}U_{i}=t\Big{]}dt$
$\displaystyle=\int_{0}^{1}\mathbb{E}[A_{i}|U_{i}=t]\prod_{j\neq
i}(1-\int_{0}^{t}\mathbb{E}[A_{j}|U_{j}=u]\mathbb{E}[X_{j}]du)dt$
$\displaystyle=\int_{0}^{1}e^{-tx_{i}}\prod_{j\neq
i}(1-\int_{0}^{t}e^{-ux_{j}}x_{j}du)dt$
$\displaystyle=\int_{0}^{1}e^{-tx_{i}}\prod_{j\neq i}(1-(1-e^{-tx_{j}}))dt$
$\displaystyle=\int_{0}^{1}e^{-t\sum_{i=1}^{n}x_{i}}dt$
$\displaystyle\leq\int_{0}^{1}e^{-t}dt.$

The second equality holds because when agent $i$ is encountered, food remains
if and only if no other agent $j$ who has arrived beforehand has
$A_{j}X_{j}=1$, in which case agent $i$ is offered the food whenever
$A_{i}=1$. The third equality holds by independence. The remaining equalities
hold by definitions of random variables and elementary operations. The
inequality holds because $\sum_{i=1}^{n}x_{i}\leq 1$, and the final integral
can be evaluated to equal $1-1/e$, completing the proof.

Theorem 2.8 shows that when $k=1$, assuming supply meets expected demand,
every agent can be offered food w.p. at least $1-1/e\approx 63.2\%$ if we
visit them in a random order. By contrast, if we visit them in a fixed order,
then this guarantee might be as low as 50%. Hence, the benefit of switching to
random order is at least $63.2\%-50\%=13.2\%$, which can then be compared to
the logistical cost of re-routing the mobile pantry on different days. Of
course, the number 13.2% serves as a rough benchmark, and is subject to the
aforementioned caveat about worst-case analysis. Regardless, Theorem 2.3
showed that any instance in which $\sum_{i<n}x_{i}$ is close to 1 will have
$\gamma_{1}(\mathbf{x})$ not much better than 50%, and Theorem 2.8 shows that
$\gamma^{\mathsf{RO}}(\mathbf{x})$ is at least 63.2%, so this combined can be
used to make an argument in favor of switching to random order.

When $k>1$, there is no closed-form for $\gamma_{k}$, but it is characterized
in Jiang et al. [48]. For example, $\gamma_{2}$ is the larger real number
satisfying $e^{1/\gamma_{2}-3}=2/\gamma_{2}-3$, which is approximately
$61.5\%$. Regardless, one difference from $k=1$ is that worst-case instances
now require arrivals to follow a Poisson process, which means that they may be
further away from a typical instance. Thus, one can alternatively just use LP
(6) to compute $\gamma_{k}(\mathbf{x})$ for the instance $\mathbf{x}$ at hand,
and a lower-bound on $\gamma^{\mathsf{RO}}_{k}(\mathbf{x})$ is then given by
the following theorem.

######  Theorem 2.10 (Arnosti and Ma [7], Lee and Singla [51])

For any instance of Problem 2.1 satisfying $\sum_{i=1}^{n}x_{i}\leq k$, there
exists a policy that offers food to every agent w.p. $1-e^{-k}k^{k}/k!$,
assuming agents are encountered in a uniformly random order.

$1-e^{-k}k^{k}/k!$ is actually the correct value of
$\gamma^{\mathsf{RO}}_{k}$, as we later explain in Subsection 3.0.1. In
particular, $\gamma^{\mathsf{RO}}_{1}=1-1/e$ (i.e. Algorithm 2 generates an
optimal policy for a worst-case instance), and
$\gamma^{\mathsf{RO}}_{2}=1-2e^{-2}\approx 72.9\%$. However, there is no
explicit policy behind Theorem 2.10—it follows from applying an equivalence
result of Lee and Singla [51] on an “ex-ante prophet inequality” of Arnosti
and Ma [7]. This illustrates just one of the many subtleties that make the
class of problems studied in this section interesting.

###  2.3 Further References on OCRS

The algorithms studied in this section are called Online Contention Resolution
Schemes (OCRSs) in the literature. In this literature, agents are said to be
“arriving”, instead of being visited by a mobile food pantry. A more salient
difference is that when an agent $i$ arrives, they first declare whether they
need food (occurring independently w.p. $x_{i}$), in which case their state is
said to be “active”. Only for active agents is there an option to give food,
in which case they are said to be “accepted”, and the objective is to accept
every agent w.p. $\gamma x_{i}$. Regardless, our Problem 2.1 is equivalent if
we imagine the offering of food to an agent as deciding, before seeing their
state, to accept them whenever they are active. For every agent $i$, being
offered food w.p. $\gamma$ is then equivalent to being accepted w.p. $\gamma
x_{i}$ (by independence).

In this section we had focused on the constraint where at most $k$ agents can
be accepted, but we now describe the OCRS problem for a general feasibility
constraint. The subset of accepted agents is constrained to lie in
$\mathcal{F}$, a downward-closed collection of subsets of $[n]$. Vector
$\mathbf{x}$ is restricted to lie in a polytope
$P_{\mathcal{F}}\subseteq[0,1]^{n}$ that contains the indicator vector
$(\mathbbm{1}(i\in S))_{i\in[n]}$ of any feasible $S\in\mathcal{F}$. The
agents $i$ arrive in some order, each active independently w.p. $x_{i}$, and
the goal is to accept every agent w.p. at least $\gamma x_{i}$. The maximum
such $\gamma$ that can be achieved for all $\mathcal{F}$ in some class and any
$x\in P_{\mathcal{F}}$, under a particular arrival order, is referred to as
the selectability (for that class and arrival order).

Cast in this language, we had studied the feasibility class where
$\mathcal{F}=\\{S\subseteq[n]:|S|\leq k\\}$ and
$P_{\mathcal{F}}=\\{\mathbf{x}\in[0,1]^{n}:\sum_{i}x_{i}\leq k\\}$, for some
given $k$ and arbitrary $n$. We showed that the selectability is $\gamma_{k}$
under fixed arrival order $i=1,\ldots,n$, and $\gamma^{\mathsf{RO}}_{k}$ under
random arrival order. The feasibility class that we had studied is sometimes
called a $k$-uniform matroid, and we now mention three other classes. First,
pioneering work on OCRS (Feldman et al. [32]) focused on the feasibility class
of general matroids, for which the selectability is known to be $1/2$ under
fixed order (Kleinberg and Weinberg [49], Lee and Singla [51]) and $1-1/e$
under random order (Ehsani et al. [27], Lee and Singla [51]). We defer the
definition of general matroids and the matroid polytope to those papers.
Second, in the knapsack feasibility class, each agent $i$ has a size
$d_{i}\in[0,1]$ and a subset of agents is feasible if and only if their total
size does not exceed 1, i.e. $\mathcal{F}=\\{S\subseteq[n]:\sum_{i\in
S}d_{i}\leq 1\\}$. When $P_{\mathcal{F}}$ is defined to be the knapsack
polytope $\\{\mathbf{x}\in[0,1]^{n}:\sum_{i}d_{i}x_{i}\leq 1\\}$, the
selectability under fixed order is known to be $1/(3+e^{-2})\approx 0.319$
(Jiang et al. [48]). No results are known for random order. Third, a
feasibility class of interest is matchings in graphs, which is an active area
of research for OCRSs in which few tight results are known. We defer defining
this problem to Subsection 5.3, because it is related to stochastic matching
in graphs.

We finish with references to a few other variants and applications of OCRS
that are beyond the scope of this tutorial. First, contention resolution
originated in an offline setting, motivated by randomized rounding for
submodular optimization (Chekuri et al. [21]). There, an important property
for algorithms to satisfy is monotonicity, which we do not consider. We also
do not consider the greedy property for OCRS, which is needed if one wants to
play against an arrival order chosen by the strongest, almighty adversary, as
discussed in Feldman et al. [32]. The stated results for matching (Ezra et al.
[29]) and $k$-uniform matroid/knapsack (Jiang et al. [48]) hold against the
oblivious and online adversary respectively, which are also discussed in
Feldman et al. [32]. Finally, it is interesting to consider contention
resolution with correlated activeness probabilities, as investigated in Dughmi
[26].

##  3 Hiring the Best Candidate

In Section 2 we studied online contention resolution, which was a sequential
randomized rounding problem by definition. In this section we study a
stochastic dynamic programming problem from Purohit et al. [64] that admits a
simple randomized rounding algorithm.

######  Problem 3.1 (Sequential Offering)

A firm has $n$ candidates whom it would like to hire for one of $k<n$
identical positions. It has determined for each candidate $i$ a value
(“weight”) $w_{i}\geq 0$ and their probability $p_{i}$ of accepting an offer.
The firm has time to make $T$ offers sequentially, where it is assumed that
each candidate immediately decides whether to accept the offer, independent of
other candidates. The objective is to maximize performance, which is defined
as the expected total weight of candidates hired.

To build some intuition, note that if $T$ is as large as $n$, then the optimal
policy is to make offers in decreasing order of $w_{i}$. Indeed, because the
firm will never run out of time, it should go for the highest-valued
candidates first, irrespective of their probability of accepting. On the other
hand, if $T$ is as small as $k$, then the optimal policy is to make offers in
decreasing order of $w_{i}p_{i}$. Indeed, because the firm can make only one
offer for each position, it should maximize the expected return from each
offer, which is $w_{i}p_{i}$. In the interesting case where $k<T<n$, the
optimal sequential hiring policy is non-trivial, and a naive dynamic program
would also fail because the state space, described by the set of candidates
yet to receive an offer, is exponential in $n$.

Nonetheless, we can derive a simple algorithm for this problem via randomized
rounding. We write the following LP to guide our decisions:

$\displaystyle\max\quad$ $\displaystyle\sum_{i=1}^{n}w_{i}p_{i}y_{i}$ (7a)
$\displaystyle\mathrm{s.t.}\quad$ $\displaystyle\sum_{i=1}^{n}y_{i}\leq T$
(7b) $\displaystyle\sum_{i=1}^{n}p_{i}y_{i}\leq k$ (7c) $\displaystyle 0\leq
y_{i}\leq 1$ $\displaystyle\forall i\in[n]$ (7d)

In this LP, $y_{i}$ is a decision variable representing the probability of
making an offer to candidate $i$. Constraints (7b) and (7c) impose the
expected number of offers to not exceed $T$, and the excepted number of
accepted offers to not exceed $k$.

###### Lemma 3.2

For any instance of Problem 3.1, the performance of any policy is at most
$\mathsf{OPT}_{\mathsf{LP}}$.

###### Proof 3.3

Proof of Lemma 3.2. Fix any instance and policy for Problem 3.1. The
performance of the policy equals the expected total weight of the candidates
it hires. Let $Y_{i}\in\\{0,1\\}$ indicate whether candidate $i$ is made an
offer, and $P_{i}\in\\{0,1\\}$ indicate whether $i$ would accept an offer if
made. On any sample path, the policy’s execution satisfies $\sum_{i}Y_{i}\leq
T$ and $\sum_{i}P_{i}Y_{i}\leq k$, and its total weight hired equals
$\sum_{i}w_{i}P_{i}Y_{i}$. Taking expectations, we get
$\sum_{i}\mathbb{E}[Y_{i}]\leq T$ and $\sum_{i}\mathbb{E}[P_{i}Y_{i}]\leq k$,
and that the policy’s performance equals
$\sum_{i}w_{i}\mathbb{E}[P_{i}Y_{i}]$. Crucially,
$\mathbb{E}[P_{i}Y_{i}]=\mathbb{E}[P_{i}]\mathbb{E}[Y_{i}]=p_{i}\mathbb{E}[Y_{i}]$
because $P_{i}$ is independent from $Y_{i}$, due to offers being made without
knowing whether the candidate would accept (this argument requires the
independence of acceptance decisions across candidates). Thus, setting
$y_{i}=\mathbb{E}[Y_{i}]$ for all $i\in[n]$ defines a feasible solution to LP
(7), whose objective value equals the performance of the policy under
consideration. Therefore, the optimal objective value of the LP can only be
higher, completing the proof.

We now show how to convert any feasible solution $(y_{i})_{i\in[n]}$ for LP
(7) into a policy for Problem 3.1. Whereas $(y_{i})_{i\in[n]}$ only satisfied
the constraints of $T$ offers and $k$ positions in expectation, the policy
must satisfy them always. A simple observation made in Purohit et al. [64] is
that given any fixed set of candidates to receive offers, it is optimal to
send to those candidates $i$ in decreasing order of $w_{i}$, so that the
highest-valued candidates have a chance to fill the positions first. We will
apply this observation after randomly rounding $(y_{i})_{i\in[n]}$ into an
offer set. The algorithm we present is from Epstein and Ma [28], who observe
that the rounding is actually very easy, given the simple structure of the LP.

###### Theorem 3.4

For any instance of Problem 3.1, the performance of Algorithm 3 is at least
$(1-e^{-k}k^{k}/k!)\mathsf{OPT}_{\mathsf{LP}}$. In particular, when $k=1$,
this guarantee relative to $\mathsf{OPT}_{\mathsf{LP}}$ is $1-1/e$.

Algorithm 3 for Problem 3.1

Solve LP (7), letting $(y_{i})_{i\in[n]}$ denote a basic optimal solution

Set $Y_{i}=y_{i}$ for all candidates $i$ with $y_{i}\in\\{0,1\\}$

Let $S=\\{i:y_{i}\in(0,1)\\}$ $\triangleright$ in a basic solution, $|S|\leq
2$

if $|S|=1$ then

Set $Y_{i}=1$ w.p. $y_{i}$ and $Y_{i}=0$ otherwise, for the candidate $i\in S$

else if $|S|=2$ then $\triangleright$ if $|S|=2$, then constraint (7b) must be
binding and hence $\sum_{i\in S}y_{i}=1$

Set $Y_{i}=1$ for exactly one of the candidates $i\in S$, satisfying
$\mathbb{E}[Y_{i}]=y_{i}$ for both $i\in S$

end if

Make offers to candidates $i$ with $Y_{i}=1$ in decreasing order of $w_{i}$,
while positions remain

###### Proof 3.5

Proof of Theorem 3.4 when $k=1$. We first argue that Algorithm 3 is feasible,
in that it never makes more than $T$ offers. This is immediate if $|S|=0$. If
$|S|=1$, then $\sum_{i\notin S}y_{i}\leq T-1$ by LP constraint (7b), which
means that even if $Y_{i}$ is rounded up to 1 for the $i\in S$, we would have
$\sum_{i=1}^{n}Y_{i}\leq T$. If $|S|=2$, then we know $\sum_{i\notin
S}y_{i}=T-1$, and hence $\sum_{i=1}^{n}Y_{i}=T$ because exactly one of the
candidates in $i\in S$ will have $Y_{i}$ rounded up to 1.

Now, re-index the candidates so that $w_{1}\geq\cdots\geq w_{n}$ and define
$w_{n+1}=0$. Letting $(y_{i})_{i\in[n]}$ refer to the optimal solution from
Algorithm 3, we can express

$\displaystyle\mathsf{OPT}_{\mathsf{LP}}=\sum_{i=1}^{n}w_{i}p_{i}y_{i}=\sum_{i=1}^{n}\left(\sum_{j=i}^{n}(w_{j}-w_{j+1})\right)p_{i}y_{i}=\sum_{j=1}^{n}(w_{j}-w_{j+1})\sum_{i=1}^{j}p_{i}y_{i}$
(8)

where each of the differences $w_{j}-w_{j+1}$ is non-negative.

Meanwhile, let $P_{i}\in\\{0,1\\}$ indicate whether candidate $i$ would accept
an offer. The policy hires a candidate $i\in[n]$ if and only if $P_{i}Y_{i}=1$
(they are made an offer and accept), and $P_{j}Y_{j}=0$ for all $j<i$ (none of
the higher-valued candidates $j$ who came before $i$ were made an offer and
accepted). Following a manipulation analogous to (8), we can express the
policy’s total weight as

$\displaystyle\sum_{i=1}^{n}w_{i}P_{i}Y_{i}(1-P_{i-1}Y_{i-1})\cdots(1-P_{1}Y_{1})$
$\displaystyle=\sum_{j=1}^{n}(w_{j}-w_{j+1})\sum_{i=1}^{j}P_{i}Y_{i}(1-P_{i-1}Y_{i-1})\cdots(1-P_{1}Y_{1})$
$\displaystyle=\sum_{j=1}^{n}(w_{j}-w_{j+1})\left(1-\prod_{i=1}^{j}(1-P_{i}Y_{i})\right)$
(9)

which has an intuitive explanation: the difference $w_{j}-w_{j+1}$ is
accumulated by the policy if and only if at least one of the candidates
$i=1,\ldots,j$ (who have $w_{i}\geq w_{j}$) has $P_{i}Y_{i}=1$. We claim that
these candidates having $P_{i}Y_{i}=1$ is negatively correlated across $i$,
which means that the probability of $w_{j}-w_{j+1}$ not being accumulated
should be lower in than the independence case, or more formally:

$\displaystyle\mathbb{E}\left[\prod_{i=1}^{j}(1-P_{i}Y_{i})\right]\leq\prod_{i=1}^{j}\mathbb{E}[1-P_{i}Y_{i}].$
(10)

This can be argued from first principles: if $|S\cap[j]|<2$ then (10) is
satisfied as equality due to independence; otherwise if
$S=\\{i^{\prime},i^{\prime\prime}\\}$ with $i^{\prime},i^{\prime\prime}\leq j$
then (10) is equivalent to

$(y_{i^{\prime}}(1-p_{i^{\prime}})+y_{i^{\prime\prime}}(1-p_{i^{\prime\prime}}))\prod_{i\leq
j,i\neq
i^{\prime},i^{\prime\prime}}(1-p_{i}y_{i})\leq(1-p_{i^{\prime}}y_{i^{\prime}})(1-p_{i^{\prime\prime}}y_{i^{\prime\prime}})\prod_{i\leq
j,i\neq i^{\prime},i^{\prime\prime}}(1-p_{i}y_{i})$

which is true due to $y_{i^{\prime}}+y_{i^{\prime\prime}}=1$. Given (10), the
expectation of (9) is at least

$\displaystyle\sum_{j=1}^{n}(w_{j}-w_{j+1})\left(1-\prod_{i=1}^{j}(1-p_{i}y_{i})\right)$
$\displaystyle\geq\sum_{j=1}^{n}(w_{j}-w_{j+1})\left(1-\prod_{i=1}^{j}e^{-p_{i}y_{i}}\right)$
$\displaystyle=\sum_{j=1}^{n}(w_{j}-w_{j+1})\left(1-e^{-\sum_{i=1}^{j}p_{i}y_{i}}\right).$

It remains to compare this expression to $\mathsf{OPT}_{\mathsf{LP}}$ as
expressed in (8). By LP constraint (7c), we know that
$\sum_{i=1}^{j}p_{i}y_{i}\leq k=1$. Because the function $(1-e^{-x})/x$ is
decreasing in $x$, we can prove

$\frac{1-e^{-\sum_{i=1}^{j}p_{i}y_{i}}}{\sum_{i=1}^{j}p_{i}y_{i}}\geq\frac{1-e^{-1}}{1}=1-1/e$

for any $j\in[n]$ by letting $x=\sum_{i=1}^{j}p_{i}y_{i}$. Finally, each of
the differences $w_{j}-w_{j+1}$ is non-negative, so the policy’s performance
relative to $\mathsf{OPT}_{\mathsf{LP}}$ is at least $1-1/e$, completing the
proof when $k=1$.

We presented an elementary proof for Theorem 3.4 that only works when $k=1$.
The result for general $k$ is proven in Epstein and Ma [28] using the powerful
tool of correlation gap (Yan [76]).

####  3.0.1 Explaining the $1-e^{-k}k^{k}/k!$ guarantee.

It is no coincidence that the guarantee for general $k$ is identical to what
was found in Theorem 2.10. All of these results compare a relaxation that
hires $k$ candidates in expectation to a reality that is subject to the
randomness in whether each candidates accepts. That is, letting
$x_{i}=y_{i}p_{i}$ denote the probability of hiring candidate $i$, reality can
only hire $\mathbb{E}[\min\\{\sum_{i=1}^{n}\mathrm{Ber}(x_{i}),k\\}]$
candidates, where $\mathrm{Ber}(x_{i})$ denotes an independent Bernoulli
random variable with mean $x_{i}$. These results eventually argue that the
worst case occurs when there are an infinite number of candidates with
infinitesimal probabilities:

$\displaystyle\inf_{n}\inf_{\mathbf{x}\in[0,1]^{n}:\sum_{i}x_{i}\leq
k}\frac{\mathbb{E}[\min\\{\sum_{i=1}^{n}\mathrm{Ber}(x_{i}),k\\}]}{\sum_{i}x_{i}}$
$\displaystyle=\lim_{n\to\infty}\frac{\mathbb{E}[\min\\{\mathrm{Bin}(n,\frac{k}{n}),k\\}]}{k}$
(11) $\displaystyle=\frac{\mathbb{E}[\min\\{\mathrm{Pois}(k),k\\}]}{k}$ (12)
$\displaystyle=1-e^{-k}\frac{k^{k}}{k!}$ (13)

where $\mathrm{Bin}(n,\frac{k}{n})$ denotes a Binomial random variable with
$n$ trials of probability $\frac{k}{n}$ and $\mathrm{Pois}(k)$ denotes a
Poisson random variable with mean $k$. A proof of the very useful sequence of
facts in (11)–(13) (assuming $\sum_{i=1}^{n}x_{i}=k$) can be found in Yan [76,
Lemma 4.2].

Equations 11, 12 and 13 also suggest that the guarantee of $1-e^{-k}k^{k}/k!$
is best possible, or “tight”, relative to the value of
$\mathsf{OPT}_{\mathsf{LP}}$. Indeed, one can construct the following sequence
of instances.

###### Example 3.6

Let $T=n$, and $w_{i}=1,p_{i}=k/n$ for all candidates $i\in[n]$. Setting
$y_{i}=1$ for all $i$ is feasible and hence optimal for LP (7), with
$\mathsf{OPT}_{\mathsf{LP}}=k$. Meanwhile, any policy would make offers to the
symmetric candidates in an arbitrary order until either all $n$ candidates
have been offered or all $k$ positions have been filled, whichever happens
first. The performance of the policy is
$\mathbb{E}[\min\\{\mathrm{Bin}(n,k/n),k\\}]$. Taking $n\to\infty$, the
policy’s performance divided by $k$ is $1-e^{-k}k^{k}/k!$ due to (11)–(13),
and hence it is not possible to have a guarantee better than
$1-e^{-k}k^{k}/k!$ relative to $\mathsf{OPT}_{\mathsf{LP}}$.

This also applies to the fairness problem from Section 2, if we argue that
promising every agent probability $\gamma$ of being offered food would result
in $\gamma\sum_{i=1}^{n}x_{i}$ food being utilized in expectation, which
cannot exceed $\mathbb{E}[\min\\{\sum_{i=1}^{n}\mathrm{Ber}(x_{i}),k\\}]$.
Equations 11, 12 and 13 then show that $\gamma$ must be as small as
$1-e^{-k}k^{k}/k!$ on a worst-case instance satisfying
$\sum_{i=1}^{n}x_{i}\leq k$.

Finally, we note that

$\displaystyle 1-e^{-k}\frac{k^{k}}{k!}\approx 1-\frac{1}{\sqrt{2\pi k}}$

by Stirling’s approximation of $k!$, which means that the guarantee is
approaching 100% as $k\to\infty$. This is intuitive: because each candidate
accepts following an independent random variable, the advantage of the
relaxation over reality vanishes as $k$ grows, by the law of large numbers.

####  3.0.2 Discussion about negative correlation.

Subsection 3.0.1 suggests that the constraint of $T$ offers was
inconsequential for the guarantee relative to the LP, and all of the loss was
coming from the constraint of $k$ positions. This is indeed the case—Algorithm
3 “losslessly” rounds the solution $(y_{i})_{i\in[n]}$ for LP (7) into
variables $(Y_{i})_{i\in[n]}\in\\{0,1\\}^{n}$ that satisfy
$\sum_{i=1}^{n}Y_{i}\leq T$. Lossless here means two things: first, the
marginals are preserved in that $\mathbb{E}[Y_{i}]=y_{i}$ for all $i$; second,
the $(Y_{i})_{i\in[n]}$ variables are negatively correlated in the simplest
and strongest form possible, where at most two of them are random, and if
exactly two are random, then exactly of them will realize to 1. Negative
correlation allows us to argue (in (10)) that the algorithm’s performance in
reality is no worse than that in an alternate reality where agents are sent
offers independently at random with the same probabilities.

A weaker form of negative correlation that often arises in randomized
rounding—see (P3) in Gandhi et al. [37]—is sufficient for establishing our
claim in (10) in the proof for $k=1$. However, the stronger form appears
necessary for $k>1$, and we refer to Qiu and Singla [65] for a recent
reference on how these different forms of negative correlation forms relate.

####  3.0.3 Discussion about adaptivity gap.

After all this, we should reveal that Problem 3.1 actually has a polynomial-
time dynamic programming algorithm when $k=1$. In fact, for any $k$, this
dynamic program efficiently computes the optimal non-adaptive policy, which
fixed the order for making offers beforehand. Purohit et al. [64] show that
there is no loss from fixing the order when $k=1$, and hence the dynamic
program is optimal.

On the other hand, there is a loss when $k>1$. Indeed, conditional on there
being positions remaining after a set of offers, the exact number remaining is
now random, depending on how many of those offers were accepted. The number of
positions remaining determines how the firm should prioritize between sending
“longshot” offers, to candidates $i$ with high $w_{i}$ but low $p_{i}$, vs.
“safe” offers, to candidates $i$ with high expected value $w_{i}p_{i}$. Since
this number cannot be determined beforehand, the dynamic program that fixes
the ordering is not optimal, and Theorem 3.4 provides the state-of-the-art
approximation ratio when $k>1$.

Importantly, Algorithm 3 actually generates a non-adaptive policy, whose order
is fixed beforehand based on the $(Y_{i})_{i\in[n]}$ variables. Theorem 3.4
shows that its performance is at least
$(1-e^{-k}k^{k}/k!)\mathsf{OPT}_{\mathsf{LP}}$, and hence a non-
adaptive222Technically our non-adaptive policy is randomized, but it can
easily be de-randomized by trying both possibilities. policy can have
performance at least $1-e^{-k}k^{k}/k!$ times that of the best adaptive
policy. This comparison is referred to as the adaptivity gap in the literature
(e.g. Dean et al. [24], Purohit et al. [64]), and is sensible in any problem
where the order can be freely decided. We study such problems in Sections 3,
4, and 5.2 of this tutorial.

###  3.1 Extensions: Constrained Free-order Prophets and ProbeTop-$k$

We extend Theorem 3.4 to a more general hiring problem where weights are real-
valued, and applicants must be interviewed to discover their true weight.

######  Problem 3.7 (Constrained Free-order Prophets, ProbeTop-$k$)

A firm has $n$ applicants for $k<n$ identical positions. Each applicant $i$
has a weight $W_{i}\geq 0$ that can be determined upon an interview. The prior
distribution of $W_{i}$ is known (e.g. based on the applicant’s resume) and
independent across $i$. The firm has time to conduct $T$ interviews, and
applicants can only be hired after an interview. In this model, the firm can
directly hire applicants because they are assumed to always333This can capture
adaptive policies for Problem 3.1 if for all $i$, we set $W_{i}$ equal $w_{i}$
w.p. $p_{i}$ and 0 otherwise. Indeed, applicant $i$ would always be rejected
if $W_{i}=0$, and an optimal adaptive policy would not be interviewing $i$
next if $i$ would not be accepted conditional on $W_{i}=w_{i}$ (Epstein and Ma
[28]). Therefore, this is equivalent to the model where applicants $i$ have
deterministic weights $w_{i}$ and decide whether to accept offers w.p.
$p_{i}$. accept an offer. The objective is to maximize performance, which is
defined as the expected total value of applicants hired.

One might realize that there are two variants to Problem 3.7—does the firm
need to to immediately make a hiring decision after each interview, or can it
finish all $T$ interviews and then hire the $k$ applicants with the highest
realized values? The former variant is called the Constrained444This variant
is interesting even without the constraint of $T$ interviews, in which case it
is called the Free-order Prophet problem. Free-order Prophet problem, while
the latter variant is called the ProbeTop-$k$ problem. Clearly the firm is
better off in the ProbeTop-$k$ variant, but deriving optimal policies under
either variant is interesting. In fact, there are further variants depending
on whether the interview order can be decided adaptively.

Randomized rounding derives policies for all of these variants in one fell
swoop. It generates a hiring policy that satisfies the strictest variant
(interview order decided in advance, hiring decision made immediately after
each interview), yet is comparable to policies under the most lenient variant
(interview order decide adaptively, hiring decisions made at end). Indeed,
letting $F_{i}$ denote the CDF of weight $W_{i}$ for all $i$, we can write the
following mathematical program:

$\displaystyle\max\ $
$\displaystyle\sum_{i=1}^{n}z_{i}\int_{1-x_{i}/z_{i}}^{1}F^{-1}_{i}(q)dq$
(14a) $\displaystyle\mathrm{s.t.\ }$ $\displaystyle\sum_{i=1}^{n}z_{i}\leq T$
(14b) $\displaystyle\sum_{i=1}^{n}x_{i}\leq k$ (14c) $\displaystyle 0\leq
x_{i}\leq z_{i}\leq 1$ $\displaystyle\forall i\in[n]$ (14d)

Here, $z_{i}$ and $x_{i}$ are decision variables representing the
probabilities of interviewing and hiring applicant $i$, respectively. Thus,
$x_{i}/z_{i}$ represents the probability of hiring applicant $i$ conditional
on interviewing them. For any $i$, if the probability of hiring applicant $i$
conditional on interviewing them is $p$, then their expected weight
conditional on being hired cannot exceed

$\displaystyle\frac{1}{p}\int_{1-p}^{1}F^{-1}_{i}(q)dq,$ (15)

for any $p\in[0,1]$. To explain (15), note that the best the policy can do is
hire applicant $i$ whenever their weight, after being interviewed, realizes to
an outcome in the top $p$ fraction of scenarios. But (15) denotes precisely
the average value of $W_{i}$ over these scenarios, where $F^{-1}_{i}(\cdot)$
denotes the inverse CDF of the distribution of $W_{i}$, and $q$ denotes the
“quantile” with $F^{-1}_{i}(q)$ being increasing in $q$. We defer a formal
definition of $F^{-1}_{i}(\cdot)$ to Chawla and Sivan [20], and instead
illustrate it through two examples: if $W_{i}$ is uniformly distributed over
[0,1], then the CDF of $W_{i}$ is $F_{i}(w)=w$ and hence $F^{-1}_{i}(q)=q$ for
all $q\in[0,1]$, which means (15) equals $\frac{1+(1-p)}{2}=1-p/2$; if $W_{i}$
is a discrete distribution equally likely to be 1 or 1/2, then (15) equals $1$
for $p\leq 1/2$, and equals $\frac{(1/2)1+(p-1/2)1/2}{p}=1/2+1/(4p)$ for
$p\geq 1/2$.

We design an interviewing policy for Problem 3.7 by reducing to Problem 3.1.
To elaborate, fix an optimal solution $(x_{i},z_{i})_{i\in[n]}$ to (14), and
we would like to compare against the value of objective (14a). We force the
interviewing policy to immediately hire an applicant $i$ if and only if their
weight, upon being interviewed, realizes to a value in its top-$(x_{i}/z_{i})$
quantile. Interviewing an applicant $i$ is now equivalent to making an offer
to candidate $i$ in an instance of Problem 3.1 with the same $k,T,n$ and

$\displaystyle p_{i}=\frac{x_{i}}{z_{i}},\qquad
w_{i}=\frac{1}{p_{i}}\int_{1-p_{i}}^{1}F^{-1}_{i}(q)dq$ $\displaystyle\forall
i\in[n].$

Indeed, in both cases a hire would result independently w.p. $p_{i}$,
conditional on which the weight $W_{i}$ is a random draw over the top $p_{i}$
fraction of scenarios, with expectation $w_{i}$. Therefore, the sequential
offering Algorithm 3 implies a sequential interviewing policy for Problem 3.7
with performance at least $(1-e^{-k}k^{k}/k!)$ times the optimal objective
value of LP (7) on the constructed instance of Problem 3.1. But this value of
LP (7) must be at least $\sum_{i=1}^{n}w_{i}p_{i}z_{i}$, because setting
$y_{i}=z_{i}$ forms a feasible solution. $\sum_{i=1}^{n}w_{i}p_{i}z_{i}$
equals the objective of (14) by construction, showing that the interviewing
policy has performance at least $1-e^{-k}k^{k}/k!$ times the optimal objective
value of (14). We note it can be shown that the latter is an upper bound on
the performance of any policy under the most lenient variant, and hence this
implies a strong result for adaptivity gaps.

We note that solving (14) for general distributions is challenging. The
argument presented here is from Epstein and Ma [28], who show how to solve
(14) by reformulating it as an LP, assuming that distributions are discrete
with finite support. Concurrently, Gallego and Segev [35] show how to solve
(14) assuming that distributions are continuous, through a minimax
reformulation.

All in all, in this subsection we provided an abstract treatment of the
different variants of Problem 3.7, which unified them into a single algorithm
and result. However, this does elude some of the richness in the structure of
optimal policies for each variant. In fact, polynomial-time approximation
schemes with approximation ratios approaching 1 can be derived for some (but
not all) variants; for more details, we defer to Segev and Singla [69].

##  4 Stochastic Knapsack

In Section 3 we studied a hiring problem in which candidates could be made
offers in any order, but given offer probabilities prescribed by the LP, there
was a natural order based on the weights. In this section we study a problem
in which we need to expand the LP to prescribe an order.

######  Problem 4.1 (Stochastic Knapsack)

There is one server for processing $n$ jobs. Each job $i$ has a weight
$W_{i}\geq 0$ and a processing duration $D_{i}$ that are random and can only
be realized by processing the job. The distributions of $W_{i}$ and $D_{i}$
are known and independent across jobs. Only one job can be processed at a
time, and jobs once started cannot be cancelled. The objective is to maximize
performance, which is defined as the expected total weight of jobs completed
during a time horizon of $T$.

Interpreting $D_{i}$ as the size of a job $i$, the objective is to maximize
the total weight of jobs that can fit in a knapsack of size $T$. In the
original formulation of stochastic knapsack, $W_{i}$ and $D_{i}$ were assumed
to be independent from each other, which is equivalent to $W_{i}$ being
deterministic (Dean et al. [24]). The authors used an LP that constrained only
the total expected size of jobs attempted to be inserted into the knapsack:

$\displaystyle\max\quad$ $\displaystyle\sum_{i=1}^{n}\mathbb{E}[W_{i}]y_{i}$
(16a) $\displaystyle\mathrm{s.t.}\quad$
$\displaystyle\sum_{i=1}^{n}\mathbb{E}[\min\\{D_{i},T\\}]y_{i}\leq 2T$ (16b)
$\displaystyle 0\leq y_{i}\leq 1$ $\displaystyle\forall i\in[n]$ (16c)

and derived constant-factor approximation ratios by comparing to
$\mathsf{OPT}_{\mathsf{LP}}$.

In the correlated stochastic knapsack problem, any pair $(W_{i},D_{i})$ can
follow an arbitrary given joint distribution, with these distributions still
being independent across jobs $i$. Gupta et al. [38] show that LP (16) is no
longer able to yield constant-factor approximation ratios, because it has an
unbounded integrality gap. That is, the authors construct a family of
instances for which the performance of the (trivial) optimal policy vanishes
to 0, yet $\mathsf{OPT}_{\mathsf{LP}}$ remains fixed at 1. This means that it
is not possible for an algorithm to generate a policy whose performance can
maintain a constant approximation ratio relative to
$\mathsf{OPT}_{\mathsf{LP}}$ over all instances. We present this family of
instances below.

######  Example 4.2 (Gupta et al. [38])

Fix $T$ to be a large positive integer and let there be $n=T$ jobs. Each job
$i$ has $(W_{i},D_{i})$ jointly distributed to be $(1,T)$ w.p. $1/n$ and
$(0,1)$ otherwise. That is, the job only contributes a positive weight if it
takes the entire time horizon to process, which occurs with a probability of
$1/n$. Note that
$\mathbb{E}[\min\\{D_{i},T\\}]=\mathbb{E}[D_{i}]=T/n+1-1/n\leq 2T/n$.
Therefore, setting $y_{i}=1$ for all $i\in[n]$ forms an optimal solution to LP
(16), with objective value $n(1/n)=1$. Meanwhile, for any actual policy, a job
that started after time 1 cannot both contribute positive weight and complete
in time. Because only one job can be started at time 1, the expected total
weight of jobs completed by the policy is at most $1/n$.

The issue with LP (16), as pointed out by Gupta et al. [38], is that the jobs
in Example 4.2 are only relevant if they are started at time 1, which is not
recognized by the LP. Gupta et al. [38] fix this issue by writing a time-
indexed LP, indicating the times at which jobs are started. This introduces
the scheduling interpretation to stochastic knapsack.

We present a different time-indexed LP here, from Ma [54], that yields a
better approximation ratio and generalizes more directly to other stochastic
knapsack problems (e.g., the variant with cancellation) and the finite-horizon
Markovian bandits problem. Although we do not elaborate on these other
problems, we note that as a result their generality, the LP ends up needing
the following assumption.

Processing durations $D_{i}$ are positive integers in $[T]$, and algorithm
runtimes are allowed to be polynomial in $T$ (instead of needing to be
polynomial in $\log T$).

Only under Section 4 is it permissible to write and solve the following LP
whose size is polynomial in $T$:

$\displaystyle\max\ $
$\displaystyle\sum_{i=1}^{n}\sum_{t=1}^{T}\mathbb{E}[W_{i}\cdot\mathbbm{1}(D_{i}\leq
T-t+1)]y_{it}$ (17a) $\displaystyle\mathrm{s.t.\ }$
$\displaystyle\sum_{i=1}^{n}\sum_{u\leq t}\Pr[D_{i}>t-u]y_{iu}\leq 1$
$\displaystyle\forall t\in[T]$ (17b) $\displaystyle\sum_{t=1}^{T}y_{it}\leq 1$
$\displaystyle\forall i\in[n]$ (17c) $\displaystyle y_{it}\geq 0$
$\displaystyle\forall i\in[n],t\in[T]$ (17d)

In this LP, $y_{it}$ is a decision variable representing the probability of
starting job $i$ at time $t$. The job completes in time if and only if
$D_{i}\leq T-t+1$, and hence starting job $i$ at time $t$ contributes an
expected weight of $\mathbb{E}[W_{i}\cdot\mathbbm{1}(D_{i}\leq T-t+1)]$,
noting that $W_{i}$ and $D_{i}$ can be correlated. Meanwhile, a job $i$
started at time $u\leq t$ is still processing at time $t$ if and only if
$D_{i}>t-u$, noting that this occurs w.p. 1 if $u=t$ (because Section 4 says
that $D_{i}>0$), and hence (17b) imposes the expected number of jobs being
processed at any time $t$ to not exceed 1. Finally, (17c) imposes that each
job $i$ is started at most once in expectation.

###### Lemma 4.3

For any instance of Problem 4.1, the performance of any policy is at most
$\mathsf{OPT}_{\mathsf{LP}}$.

###### Proof 4.4

Proof of Lemma 4.3. Fix any policy for Problem 4.1. Let $Y_{it}\in\\{0,1\\}$
indicate that job $i$ was started at time $t$. On any sample path, the total
weight of completed jobs is $\sum_{i}\sum_{t}W_{i}\mathbbm{1}(D_{i}\leq
T-t+1)Y_{it}$. Meanwhile, the policy’s execution satisfies
$\sum_{i}\sum_{u\leq t}\mathbbm{1}(D_{i}>t-u)Y_{iu}\leq 1$ for all $t$,
because at most one job can be processed at any time. Finally, we have
$\sum_{t}Y_{it}\leq 1$ for all jobs $i$. Now, $Y_{it}$ is independent from
$W_{i}$ and $D_{i}$ for all $i\in[n]$ and $t\in[T]$, because jobs must be
started without knowing their weight or duration (this argument requires the
independence of $(W_{i},D_{i})$ across $i$). Therefore, taking expectations
allows us to deduce that setting $y_{it}=\mathbb{E}[Y_{it}]$ for all $i$ and
$t$ defines a feasible solution to LP (17). Moreover, the objective value of
this feasible solution equals the performance of the policy under
consideration, completing the proof.

We show that if we scale the probabilities $y_{it}$ in a feasible solution of
LP (17) by a factor of 1/2 (which would involving idling the system more),
then it is possible to start every job $i$ at every time $t$ w.p. exactly
$y_{i,t}/2$, in an actual policy for Problem 4.1. This scaling strategy
differs from the sorting strategy for randomized rounding from Section 3, and
is more reminiscent of the fairness problems from Section 2 where we are
making a promise for every job $i$ starting at every time $t$.

######  Theorem 4.5 (Ma [54])

For any instance of Problem 4.1, Algorithm 4 starts every job $i\in[n]$ at
every time $t\in[T]$ w.p. $y_{it}/2$, and hence its performance is exactly
$\mathsf{OPT}_{\mathsf{LP}}/2$.

Algorithm 4 for Problem 4.1

Solve LP (17), letting $(y_{it})_{i\in[n],t\in[T]}$ denote an optimal solution

for time $t=1,\ldots,T$ do

for jobs $i\in[n]$ do

$Y_{it}\leftarrow 0$ $\triangleright$ indicator for starting job $i$ at time
$t$; default is 0

$\mathsf{Free}(i,t)\leftarrow\Pr[\left(\sum_{j=1}^{n}\sum_{u<t}\mathbbm{1}(D_{j}>t-u)Y_{ju}=0\right)\cap\left(\sum_{u<t}Y_{iu}=0\right)]$
$\triangleright$ probability that no job is currently being processed and $i$
has not already been started

end for

$i\leftarrow$ random draw following probability vector
$(\frac{1}{\mathsf{Free}(i,t)}\cdot\frac{y_{it}}{2})_{i\in[n]}$
$\triangleright$ assume $\frac{0}{0}=0$ $\triangleright$ $i=0$ w.p.
$1-\sum_{i=1}^{n}\frac{1}{\mathsf{Free}(i,t)}\cdot\frac{y_{it}}{2}$

if $i>0$ and $\sum_{j=1}^{n}\sum_{u<t}\mathbbm{1}(D_{j}>t-u)Y_{ju}=0$ and
$\sum_{u<t}Y_{iu}=0$ then

$Y_{it}\leftarrow 1$ $\triangleright$ start job $i$ at time $t$

end if

end for

###### Proof 4.6

Proof of Theorem 4.5. We prove inductively over $t=1,\ldots,T$ that every job
$i\in[n]$ is started at time $t$ w.p. exactly $y_{it}/2$. Assuming the
algorithm is valid, this follows by construction of Algorithm 4, because

$\displaystyle\mathbb{E}[Y_{it}]=\frac{1}{\mathsf{Free}(i,t)}\cdot\frac{y_{it}}{2}\Pr\left[\left(\sum_{j=1}^{n}\sum_{u<t}\mathbbm{1}(D_{j}>t-u)Y_{ju}=0\right)\cap\left(\sum_{u<t}Y_{iu}=0\right)\right]=\frac{y_{it}}{2}.$

To prove that the algorithm is valid, it suffices to show

$\displaystyle\sum_{i=1}^{n}\frac{1}{\mathsf{Free}(i,t)}\cdot\frac{y_{it}}{2}\leq
1.$ (18)

In the base case where $t=1$, we know $\mathsf{Free}(i,t)=1$ for all $i$, and
hence (18) holds by the LP constraint (17b) for $t=1$. For $t>1$, we derive

$\displaystyle 1-\mathsf{Free}(i,t)$
$\displaystyle=\Pr\left[\left(\sum_{j=1}^{n}\sum_{u<t}\mathbbm{1}(D_{j}>t-u)Y_{ju}=1\right)\cup\left(\sum_{u<t}Y_{iu}=1\right)\right]$
$\displaystyle\leq\Pr\left[\sum_{j=1}^{n}\sum_{u<t}\mathbbm{1}(D_{j}>t-u)Y_{ju}=1\right]+\Pr\left[\sum_{u<t}Y_{iu}=1\right]$
$\displaystyle=\sum_{j=1}^{n}\sum_{u<t}\Pr[\mathbbm{1}(D_{j}>t-u)Y_{ju}=1]+\sum_{u<t}\Pr[Y_{iu}=1]$
$\displaystyle=\sum_{j=1}^{n}\sum_{u<t}\Pr[D_{j}>t-u]\frac{y_{ju}}{2}+\sum_{u<t}\frac{y_{iu}}{2}.$
$\displaystyle\leq\frac{1}{2}\left(1-\sum_{j=1}^{n}y_{jt}\right)+\frac{1}{2}.$

Indeed, the second-line inequality holds by the union bound. The third-line
equality holds because at most one of the entries in
$(\mathbbm{1}(D_{j}>t-u)Y_{ju})_{j\in[n],u<t}$ can be 1, and also at most one
of the entries in $(Y_{iu})_{u<t}$ can be 1. The fourth-line equality applies
the induction hypothesis for time steps $u<t$. Finally, the fifth-line
inequality applies both constraints (17b) and (17c) from the LP.

Rearranging the derivation above, we get
$\mathsf{Free}(i,t)\geq\sum_{j=1}^{n}\frac{y_{jt}}{2}$, for any $i\in[n]$.
Therefore,
$\min_{i\in[n]}\mathsf{Free}(i,t)\geq\sum_{j=1}^{n}\frac{y_{jt}}{2}$, which
implies

$1\geq\sum_{j=1}^{n}\frac{1}{\min_{i\in[n]}\mathsf{Free}(i,t)}\cdot\frac{y_{jt}}{2}\geq\sum_{j=1}^{n}\frac{1}{\mathsf{Free}(j,t)}\cdot\frac{y_{jt}}{2}$

under the convention that $\frac{0}{0}=0$. This completes the induction and
the proof.

An issue with Algorithm 4, however, is that the probabilities
$\mathsf{Free}(i,t)$ are difficult to compute. Indeed, they refer to events
about the algorithm’s state distribution at a given time $t$, which would
generally have support exponential in $n$ (because the state must describe the
subset of jobs not yet started). This issue can be overcome by self-sampling,
where the algorithm re-samples its past execution at each time $t$ to get
estimates of $\mathsf{Free}(i,t)$. It must be carefully shown that the
sampling errors do not propagate, and that jobs $i$ are still started at times
$t$ with probability close to $y_{it}/2$ even if both $y_{it}$ and
$\mathsf{Free}(i,t)$ are small. We note that tracking its own state
distribution poses a general challenge for sequential randomized rounding
algorithms, which need to satisfy the intricacies discussed in Remark 2.6 to
be optimal.

We defer further details to Ma [54]. There it is also discussed how these
techniques can be generalized to the finite-horizon Markovian bandits problem.

##  5 Stochastic Matching

In this section we discuss stochastic matching in graphs, which includes many
combinatorially-rich problems that exemplify the power of sequential
randomized rounding. We first prove a self-contained result for a simplified
online stochastic matching model (Problem 5.1) that illustrates how the OCRSs
studied in Section 2 can be applied. We then describe several other models, in
some cases simplified versions, to highlight the innovative LPs being rounded.

###### Problem 5.1

Resources $j\in[m]$ can each be matched at most once. Agents $i=1,\ldots,n$
arrive in order, independently “materializing” with a known probability
$p_{i}$. If an agent $i$ materializes, then they can be immediately matched
with up to one available resource $j$, in which case a known reward (“weight”)
of $w_{ji}\geq 0$ is accumulated. The objective is to maximize performance,
which is defined as the expected total reward accumulated.

We write the following LP for Problem 5.1, in which $x_{ji}$ represents the
probability of matching resource $j$ to agent $i$:

$\displaystyle\max\quad$
$\displaystyle\sum_{j=1}^{m}\sum_{i=1}^{n}w_{ji}x_{ji}$ (19a)
$\displaystyle\mathrm{s.t.}\quad$ $\displaystyle\sum_{i=1}^{n}x_{ji}\leq 1$
$\displaystyle\forall j\in[m]$ (19b) $\displaystyle\sum_{j=1}^{m}x_{ji}\leq
p_{i}$ $\displaystyle\forall i\in[n]$ (19c) $\displaystyle x_{ji}\geq 0$
$\displaystyle\forall j\in[m],i\in[n]$ (19d)

It can be shown similarly to the proofs of Lemmas 3.2 and 4.3 that the optimal
objective value of LP (19) upper-bounds the performance of any policy.

###### Theorem 5.2

For any instance of Problem 5.1, the performance of Algorithm 5 is at least
$\mathsf{OPT}_{\mathsf{LP}}/2$.

Algorithm 5 for Problem 5.1

Solve LP (7), letting $(x_{ji})_{j\in[m],i\in[n]}$ denote an optimal solution

for resources $j\in[m]$ do

Run a separate version of Algorithm 1 for resource $j$, with input
$(x_{ji})_{i\in[n]}$ and $\gamma=1/2$, letting $(A_{ji})_{i\in[n]}$ denote the
independent random bits $(A_{i})_{i\in[n]}$ drawn in Algorithm 1

end for

for agents $i=1,\ldots,n$ do

if agent $i$ materializes then

Independently draw $j$ following probability vector
$(\frac{x_{ji}}{p_{i}})_{j\in[m]}$ (with $j=0$ w.p.
$1-\sum_{j=1}^{m}\frac{x_{ji}}{p_{i}}$)

if resource $j$ is available and $A_{ji}=1$ then

Match agent $i$ to resource $j$

end if

end if

end for

###### Proof 5.3

Proof of Theorem 5.2. We first note that for each resource $j$, setting
$\gamma=1/2$ in Algorithm 1 is feasible, because it is no greater than the
optimal guarantee of $1/(1+\sum_{i<n}x_{ji})$, which is at least 1/2 by LP
constraint (19b). We also note that $(\frac{x_{ji}}{p_{i}})_{j\in[m]}$ is a
feasible probability vector satisfying $\sum_{j=1}^{m}\frac{x_{ji}}{p_{i}}\leq
1$, by LP constraint (19c).

Having established the feasibility of Algorithm 5, we now show that every
agent $i\in[n]$ is matched to every resource $j$ w.p. $x_{ji}/2$. By
definition of Algorithm 1, every resource $j$ will be available for each agent
$i$ and draw $A_{ji}=1$ w.p. $1/2$. Meanwhile, each agent $i$ independently
materializes w.p. $p_{i}$, in which case $j$ is drawn independently w.p.
$x_{ji}/p_{i}$. The product of these three probabilities is exactly
$x_{ji}/2$, completing the proof.

Theorem 5.2 was originally derived (in a more general form) in Alaei et al.
[3], who show that the guarantee of $\mathsf{OPT}_{\mathsf{LP}}/2$ is best-
possible. Indeed, consider a simple instance with $m=1$ resource, $n=2$
agents. Agent 1 has $p_{1}=1$ and $w_{1}=1$. Agent 2 has $p_{2}=\varepsilon$
and $w_{2}=1/\varepsilon$ for some small $\varepsilon>0$. In LP it is feasible
to set $x_{11}=1-\varepsilon,x_{12}=\varepsilon$, and hence
$\mathsf{OPT}_{\mathsf{LP}}\geq(1-\varepsilon)+(1/\varepsilon)\varepsilon=2-\varepsilon$.
However, any online policy does not know whether agent 2 will materialize and
hence is indifferent between accepting or rejecting agent 1, with a
performance of 1. The ratio equals $1/(2-\varepsilon)$ which approaches 1/2 as
$\varepsilon\to 0$.

To overcome this impossibility of 1/2, recent work by Papadimitriou et al.
[62] proposes a tightening of LP (19). They add the following constraint to LP
(19):

$\displaystyle x_{ji}\leq p_{i}(1-\sum_{i^{\prime}<i}x_{ji^{\prime}})$
$\displaystyle\forall j\in[m],i\in[n]$ (20)

which says that the probability of matching agent $i$ to resource $j$ cannot
be greater than the product of the (independent) events of $i$ materializing,
and $j$ not being matched to an agent $i^{\prime}$ before $i$. It is easy to
check that (20) must be satisfied by any online (but not offline) policy.
Using the tightened LP, Papadimitriou et al. [62] derive an approximation
ratio strictly exceeding 1/2, which has since been improved by Saberi and Wajc
[68], Braverman et al. [16]. The state-of-the-art approximation ratio for this
setting is currently 0.652 (Naor et al. [61]).

###  5.1 Online Stochastic Matching with IID Types

Theorem 5.2 considered a model of online stochastic matching with
heterogeneous arrivals over time, but online stochastic matching was
originally studied in the IID model where the arrival distribution is
homogeneous over time.

###### Problem 5.4

There are resources $j\in[m]$ and agent types $i\in[n]$. Each resource $j$ can
be matched at most once, and there is a known reward $w_{ji}\geq 0$ for
matching it to each agent type $i$. There is a time horizon of length $T$.
Each time step $t=1,\ldots,T$, an agent arrives following a random type $i$
that is drawn IID from a known probability vector $(\lambda_{i}/T)_{i\in[n]}$
satisfying $\sum_{i=1}^{n}\lambda_{i}=T$.

A naive LP relaxation for Problem 5.4 would look like:

$\displaystyle\max\quad$
$\displaystyle\sum_{j=1}^{m}\sum_{i=1}^{n}w_{ji}x_{ji}$ (21a)
$\displaystyle\mathrm{s.t.}\quad$ $\displaystyle\sum_{i=1}^{n}x_{ji}\leq 1$
$\displaystyle\forall j\in[m]$ (21b)
$\displaystyle\sum_{j=1}^{m}x_{ji}\leq\lambda_{i}$ $\displaystyle\forall
i\in[n]$ (21c) $\displaystyle x_{ji}\geq 0$ $\displaystyle\forall
j\in[m],i\in[n]$ (21d)

In this LP, $x_{ji}$ represents the expected number of times resource $j$ is
matched with type $i$, noting that the expected number of arrivals of type $i$
is $\lambda_{i}$.

The naive LP (21) cannot obtain a guarantee better than $1-1/e$, but a
sequence of early papers (Feldman et al. [31], Manshadi et al. [59], Jaillet
and Lu [45], Brubach et al. [19]) show how to beat $1-1/e$ with progressively
improving guarantees. These papers need to assume either unweighted
($w_{ji}\in\\{0,1\\}$ for all $i,j$) or vertex-weighted
($w_{ji}\in\\{0,w_{j}\\}$ for all $i,j$, for some values of
$(w_{j})_{j\in[m]}$) graphs, or integral arrival rates ($n=T$ and
$\lambda_{i}=1$ for all $i\in[n]$). Beating $1-1/e$ with neither assumption
was recent accomplished by Yan [77], with the state-of-the-art guarantee found
in Qiu et al. [66]. The latter papers round the LP from Jaillet and Lu [45],
whose details are omitted.

We describe here a different “Natural LP”, introduced by Huang and Shu [40],
which has led to the state of the art for unweighted and vertex-weighted
graphs (without the integral arrival rates assumption). The authors show that
it suffices to consider a continuous-time version of Problem 5.4, in which the
arrivals of each type $j$ follow an independent Poisson process of homogeneous
rate $\lambda_{j}$ over [0,1]. Their Natural LP is then (21) with the
following added constraints:

$\displaystyle\sum_{i\in S}x_{ji}\leq 1-\exp(-\sum_{i\in S}\lambda_{i})$
$\displaystyle\forall j\in[m],S\subseteq[n].$ (22)

These constraints are valid for any online (or offline) algorithm because for
any subset of types $S$, the probability of matching one of them to resource
$j$ cannot exceed the probability that an agent of type $S$ exists, which
occurs w.p. $1-\exp(-\sum_{i\in S}\lambda_{i})$ after the Poisson reduction.
Although (22) is an exponential family of constraints, Huang and Shu [40] show
how to separate over them in polynomial time, which implies that the Natural
LP can be solved. The state-of-the-art guarantees for unweighted and vertex-
weighted graphs are derived by combining the Natural LP with the Online
Correlated Selection (OCS) technique, and we defer the details to Tang et al.
[71], Huang et al. [41]. We note that OCS was originally developed to solve
open problems in adversarial settings [30, 44], but can be relevant even for
this IID setting where the arrival probabilities and fractional solution to be
rounded are given in advance.

###  5.2 Stochastic Probing in Graphs

Here we present a model of stochastic matching that has no “online” aspect.
Instead, it is a sequencing problem like in Section 3, where the edges in a
graph can be probed in any order.

###### Problem 5.5

Let $G=(V,E)$ be a graph with vertex set $V$ and edge set $E$. Let
$\partial(v)$ denote the set of edges incident to a vertex $v$. A subset of
edges $S$ is said to be a matching if $|S\cap\partial(v)|\leq 1$ for all $v\in
V$, i.e. no two edges in $S$ are incident to the same vertex. In this problem,
each edge $e$ has a known weight $w_{e}$ and a probability $p_{e}$ with which
it independently exists. Meanwhile, each vertex has a finite patience $T_{v}$
upper-bounding how many times edges in $\partial(v)$ can be probed. An edge is
feasible to probe if it satisfies the patience constraint and forms a matching
with the edges selected so far. An algorithm can sequentially probe the edges
in any order, but a probed edge that exists must be selected into the
matching. The objective is to maximize performance, which is defined as the
expected total weight of the selected edges.

Problem 5.5 is a generalization of the sequential offering problem from
Section 3, and marks the third time we are seeing a problem in which the order
can be freely decided. Unlike the simpler hiring problem where there was a
sorting order (Section 3), or the stochastic knapsack problem where we made
the LP prescribe the order (Section 4), here we write an orderless LP and
resort to random order to prove a guarantee:

$\displaystyle\max\ $ $\displaystyle\sum_{e\in E}w_{e}p_{e}y_{e}$ (23a)
$\displaystyle\mathrm{s.t.\ }$ $\displaystyle\sum_{e\in\partial(v)}y_{e}\leq
T_{v}$ $\displaystyle\forall v\in V$ (23b)
$\displaystyle\sum_{e\in\partial(v)}p_{e}y_{e}\leq 1$ $\displaystyle\forall
v\in V$ (23c) $\displaystyle 0\leq y_{e}\leq 1$ $\displaystyle\forall e\in E$
(23d)

In this LP, decision variable $y_{e}$ represents the probability of probing
edge $e$. For any vertex $v$, constraint (23b) enforces that the number of
edges in $\partial(v)$ probed cannot exceed $T_{v}$, while constraint (23c)
enforces that the number of edges in $\partial(v)$ matched cannot exceed 1.

Problem 5.5 was originally formulated in Chen et al. [22], Bansal et al. [12],
and there is a long line of work (Adamczyk et al. [1], Baveja et al. [13],
Brubach et al. [17]) improving the approximation ratio using LP (23). The
state-of-the-art guarantee is 0.395 (Pollner et al. [63]), achieved by
considering the edges in a uniformly random order.

When there are no patience constraints, i.e. $T_{v}=\infty$ for all $v$,
Gamlath et al. [36] found a way to significantly tighten LP (23) on bipartite
graphs. The key idea is that for any vertex $v$, the following set of
constraints validly describe any policy:

$\displaystyle\sum_{e\in S}p_{e}y_{e}\leq 1-\prod_{e\in S}(1-p_{e})$
$\displaystyle v\in V,S\subseteq\partial(v).$ (24)

Indeed, the LHS of (24) represents the probability of selecting one of the
edges in $S$ incident to $v$; this cannot exceed the probability of an edge in
$S$ existing, which is the RHS of (24). This family of constraints is similar
to (22), and also exponentially-sized, but Gamlath et al. [36] establish a
polynomial-time separation oracle. Using the LP (23) with added constraints
(24), combined with the random-order allocation result from Theorem 2.8,
Gamlath et al. [36] derive $(1-1/e)$-approximate algorithm. This has since
been improved in Derakhshan and Farhadi [25].

The aforementioned results only hold for bipartite graphs (and infinite
patience). For general graphs with infinite patience, Fu et al. [34] return to
the original LP (23) but reduce to a notion of OCRS with random-order vertex
arrivals. They derive an 8/15-approximate algorithm for the problem on general
graphs, which has since been improved in MacRury and Ma [57].

Finally, there is a connection between Problem 5.5 and the Price-of-
Information model (Singla [70]) motivated by the classical Pandora’s box
search problem (Weitzman [74]), in which one can pay a cost of $c_{e}$ to
discover the independently random weight $W_{e}$ of an edge $e$. The infinite-
patience results that we discussed also hold on that model; we defer the
reductions to Gamlath et al. [36], Fu et al. [34].

###  5.3 Contention Resolution for Matching Polytope

Following the notation in Subsections 2.3 and 5.2, one can define the
following OCRS problem for the matching polytope in graphs. The agents are the
edges $e\in E$, each of whom is active w.p. $x_{e}$. A subset of edges
$S\subseteq E$ is feasible if and only if they form a matching, i.e. $S$ must
lie in $\mathcal{F}=\\{S\subseteq E:|S\cap\partial(v)|\leq 1\forall v\in
V\\}$. Vector $(x_{e})_{e\in E}$ is restricted to lie in the matching polytope
$P_{\mathcal{F}}=\\{\mathbf{x}\in[0,1]^{E}:\sum_{e\in\partial(v)}x_{e}\leq
1\forall v\in V\\}$.

This OCRS problem was proposed by Ezra et al. [29] as a means to solve the
“prophet matching” problem under adversarially-ordered edge arrivals; the
authors establish a selectability lower bound (algorithmic result) strictly
exceeding 1/3. Meanwhile, under randomly-ordered edge arrivals, Brubach et al.
[17] establish a selectability lower bound of $(1-e^{-2})/2\approx 0.432$. The
current state of the art for both of these problems can be found in MacRury et
al. [58].

##  6 Conclusion and Future Directions

We summarize the key concepts and techniques for sequential randomized
rounding (SRR) that were encountered in this tutorial. First, the most
important takeaway is perhaps the state tracking described in Remark 2.6,
because these counter-intuitive intricacies are unique to SRR. We illustrated
these intricacies through a basic fair rationing problem (Section 2), although
to achieve state tracking, self-sampling can sometimes be required, as we saw
in the stochastic knapsack problem (Section 4). Meanwhile, we saw in the
hiring problem (Section 3) an extremely simplified version of analyzing
correlation, which forms the basis of a lot of advanced analyses in SRR.
Finally, SRR can be improved by tightening the LP relaxation, and we saw
several examples of this in stochastic matching problems (Section 5).

We now describe some other related problems in which SRR has seen recent use.
First, Ashlagi et al. [9] introduce a sequential assortment optimization
problem motivated by two-sided matching markets, which is reminiscent of the
graph probing problem discussed in Subsection 5.2. Algorithms for this problem
are generally based on randomized rounding (Torrico et al. [72], Rios and
Torrico [67]), with the state of the art found in Housni et al. [39]. Second,
SRR has been fruitful at handling extensions of online decision-making models
in which the length of the time horizon is stochastic. Indeed, algorithms
based on randomized rounding are used in the sequential submodular
maximization problem of Asadpour et al. [8], the product ranking problem of
Brubach et al. [18] (which is just the sequential offering problem from
Section 3 with a random $T$), and several variants of online stochastic
matching with a stochastic horizon (Bai et al. [10], Aouad and Ma [6], Jiang
[47]).

We conclude by discussing three broad directions for SRR in the context of
operations research applications. First, there is a series of papers
suggesting the deployment of randomized rounding algorithms in e-commerce
systems (Jasin and Sinha [46], Lei et al. [52], Ma [55]), with the stated
benefit being that the resulting policies (which are similar to the online
stochastic matching policy from the beginning of Section 5) are simple, fast,
and parallelizable. However, it would be important to quantify these benefits
in practice, and see if the simplicity outweights any potential performance
loss (see Amil et al. [4]). Second, on a related note, there is often a stigma
that SRR performs poorly in practice because it is designed to prove
theoretical worst-case approximation ratios. However, recent work (Borodin et
al. [15], Ma et al. [56]) has shown this to not be the case, where simple
randomized rounding policies for online matching are difficult to beat on a
variety of synthetic setups. That being said, there is still unexplained
discrepancy between algorithms with the best approximation ratios and those
with the best observed performances, and it is not well understood which
properties of the synthetic setups or distributions may be causing this
discrepancy. Finally, randomized rounding provides a form of probabilistic
fairness, which has been recently deployed by Flanigan et al. [33] for
selecting (offline) citizens’ assemblies. It would be interesting to find
other applications where probabilistic fairness is needed, which by definition
would require randomized rounding, potentially in a sequential manner. For
this, we refer to two very recent papers (Aminian et al. [5], Banerjee et al.
[11]) that study fairness in online stochastic settings.

##### Acknowledgements.

We thank Zhiyi Huang for a useful discussion, and anonymous reviewers for
improving the Introduction of this tutorial.

## References

  * Adamczyk et al. [2015] Adamczyk M, Grandoni F, Mukherjee J (2015) Improved approximation algorithms for stochastic matching. _Algorithms-ESA 2015_ , 1–12 (Springer).
  * Alaei [2011] Alaei S (2011) Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. _Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science_ , 512–521.
  * Alaei et al. [2012] Alaei S, Hajiaghayi M, Liaghat V (2012) Online prophet-inequality matching with applications to ad allocation. _Proceedings of the 13th ACM Conference on Electronic Commerce_ , 18–35.
  * Amil et al. [2023] Amil A, Makhdoumi A, Wei Y (2023) Multi-item order fulfillment revisited: Lp formulation and prophet inequality. _Proceedings of the 24th ACM Conference on Electronic Commerce_ , 88.
  * Aminian et al. [2023] Aminian MR, Manshadi V, Niazadeh R (2023) Markovian search with socially aware constraints. _Available at SSRN 4347447_ .
  * Aouad and Ma [2023] Aouad A, Ma W (2023) A nonparametric framework for online stochastic matching with correlated arrivals. _Proceedings of the 24th ACM Conference on Electronic Commerce_ , 114.
  * Arnosti and Ma [2023] Arnosti N, Ma W (2023) Tight guarantees for static threshold policies in the prophet secretary problem. _Operations research_ 71(5):1777–1788.
  * Asadpour et al. [2023] Asadpour A, Niazadeh R, Saberi A, Shameli A (2023) Sequential submodular maximization and applications to ranking an assortment of products. _Operations Research_ 71(4):1154–1170.
  * Ashlagi et al. [2022] Ashlagi I, Krishnaswamy AK, Makhijani R, Saban D, Shiragur K (2022) Assortment planning for two-sided sequential matching markets. _Operations Research_ 70(5):2784–2803.
  * Bai et al. [2023] Bai Y, El Housni O, Jin B, Rusmevichientong P, Topaloglu H, Williamson DP (2023) Fluid approximations for revenue management under high-variance demand. _Management Science_ 69(7):4016–4026.
  * Banerjee et al. [2023] Banerjee S, Hssaine C, Sinclair SR (2023) Online fair allocation of perishable resources. _ACM SIGMETRICS Performance Evaluation Review_ 51(1):55–56.
  * Bansal et al. [2012] Bansal N, Gupta A, Li J, Mestre J, Nagarajan V, Rudra A (2012) When lp is the cure for your matching woes: Improved bounds for stochastic matchings. _Algorithmica_ 63(4):733–762.
  * Baveja et al. [2018] Baveja A, Chavan A, Nikiforov A, Srinivasan A, Xu P (2018) Improved bounds in stochastic matching and optimization. _Algorithmica_ 80(11):3225–3252.
  * Blanchet et al. [2021] Blanchet J, Murthy K, Nguyen VA (2021) Statistical analysis of wasserstein distributionally robust estimators. _Tutorials in Operations Research: Emerging Optimization Methods and Modeling Techniques with Applications_ , 227–254 (INFORMS).
  * Borodin et al. [2020] Borodin A, Karavasilis C, Pankratov D (2020) An experimental study of algorithms for online bipartite matching. _Journal of Experimental Algorithmics (JEA)_ 25:1–37.
  * Braverman et al. [2022] Braverman M, Derakhshan M, Molina Lovett A (2022) Max-weight online stochastic matching: Improved approximations against the online benchmark. _Proceedings of the 23rd ACM Conference on Economics and Computation_ , 967–985.
  * Brubach et al. [2021] Brubach B, Grammel N, Ma W, Srinivasan A (2021) Improved guarantees for offline stochastic matching via new ordered contention resolution schemes. _Advances in Neural Information Processing Systems_ 34:27184–27195.
  * Brubach et al. [2023] Brubach B, Grammel N, Ma W, Srinivasan A (2023) Online matching frameworks under stochastic rewards, product ranking, and unknown patience. _Operations Research_ .
  * Brubach et al. [2016] Brubach B, Sankararaman KA, Srinivasan A, Xu P (2016) New algorithms, better bounds, and a novel model for online stochastic matching. _24th Annual European Symposium on Algorithms (ESA 2016)_ (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik).
  * Chawla and Sivan [2014] Chawla S, Sivan B (2014) Bayesian algorithmic mechanism design. _ACM SIGecom Exchanges_ 13(1):5–49.
  * Chekuri et al. [2014] Chekuri C, Vondrak J, Zenklusen R (2014) Submodular function maximization via the multilinear relaxation and contention resolution schemes. _SIAM Journal on Computing_ 43(6):1831–1879.
  * Chen et al. [2009] Chen N, Immorlica N, Karlin AR, Mahdian M, Rudra A (2009) Approximating matches made in heaven. _Automata, Languages and Programming: 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I 36_ , 266–278 (Springer).
  * Correa et al. [2019] Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2019) Recent developments in prophet inequalities. _ACM SIGecom Exchanges_ 17(1):61–70.
  * Dean et al. [2008] Dean BC, Goemans MX, Vondrák J (2008) Approximating the stochastic knapsack problem: The benefit of adaptivity. _Mathematics of Operations Research_ 33(4):945–964.
  * Derakhshan and Farhadi [2023] Derakhshan M, Farhadi A (2023) Beating (1-1/e)-approximation for weighted stochastic matching. _Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , 1931–1961 (SIAM).
  * Dughmi [2019] Dughmi S (2019) The outer limits of contention resolution on matroids and connections to the secretary problem. _arXiv preprint arXiv:1909.04268_ .
  * Ehsani et al. [2018] Ehsani S, Hajiaghayi M, Kesselheim T, Singla S (2018) Prophet secretary for combinatorial auctions and matroids. _Proceedings of the twenty-ninth annual acm-siam symposium on discrete algorithms_ , 700–714 (SIAM).
  * Epstein and Ma [2024] Epstein B, Ma W (2024) Selection and ordering policies for hiring pipelines via linear programming. _Operations Research_ .
  * Ezra et al. [2022] Ezra T, Feldman M, Gravin N, Tang ZG (2022) Prophet matching with general arrivals. _Mathematics of Operations Research_ 47(2):878–898.
  * Fahrbach et al. [2022] Fahrbach M, Huang Z, Tao R, Zadimoghaddam M (2022) Edge-weighted online bipartite matching. _Journal of the ACM_ 69(6):1–35.
  * Feldman et al. [2009] Feldman J, Mehta A, Mirrokni V, Muthukrishnan S (2009) Online stochastic matching: Beating 1-1/e. _2009 50th Annual IEEE Symposium on Foundations of Computer Science_ , 117–126 (IEEE).
  * Feldman et al. [2021] Feldman M, Svensson O, Zenklusen R (2021) Online contention resolution schemes with applications to bayesian selection problems. _SIAM Journal on Computing_ 50(2):255–300.
  * Flanigan et al. [2021] Flanigan B, Gölz P, Gupta A, Hennig B, Procaccia AD (2021) Fair algorithms for selecting citizens’ assemblies. _Nature_ 596(7873):548–552.
  * Fu et al. [2021] Fu H, Tang ZG, Wu H, Wu J, Zhang Q (2021) Random order vertex arrival contention resolution schemes for matching, with applications. _48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)_ (Schloss-Dagstuhl-Leibniz Zentrum für Informatik).
  * Gallego and Segev [2022] Gallego G, Segev D (2022) A constructive prophet inequality approach to the adaptive probemax problem. _arXiv preprint arXiv:2210.07556_ .
  * Gamlath et al. [2019] Gamlath B, Kale S, Svensson O (2019) Beating greedy for stochastic bipartite matching. _Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms_ , 2841–2854 (SIAM).
  * Gandhi et al. [2006] Gandhi R, Khuller S, Parthasarathy S, Srinivasan A (2006) Dependent rounding and its applications to approximation algorithms. _Journal of the ACM (JACM)_ 53(3):324–360.
  * Gupta et al. [2011] Gupta A, Krishnaswamy R, Molinaro M, Ravi R (2011) Approximation algorithms for correlated knapsacks and non-martingale bandits. _2011 IEEE 52nd Annual Symposium on Foundations of Computer Science_ , 827–836 (IEEE).
  * Housni et al. [2024] Housni OE, Torrico A, Hennebelle U (2024) Two-sided assortment optimization: Adaptivity gaps and approximation algorithms. _arXiv preprint arXiv:2403.08929_ .
  * Huang and Shu [2021] Huang Z, Shu X (2021) Online stochastic matching, poisson arrivals, and the natural linear program. _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ , 682–693.
  * Huang et al. [2022] Huang Z, Shu X, Yan S (2022) The power of multiple choices in online stochastic matching. _Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing_ , 91–103.
  * Huang et al. [2024a] Huang Z, Tang ZG, Wajc D (2024a) Online matching: A brief survey. _SIGECOM Exchanges_ .
  * Huang and Tröbst [2023] Huang Z, Tröbst T (2023) Applications of online matching. _Online and Matching-Based Market Design_ 109\.
  * Huang et al. [2024b] Huang Z, Zhang Q, Zhang Y (2024b) Adwords in a panorama. _SIAM Journal on Computing_ 53(3):701–763.
  * Jaillet and Lu [2014] Jaillet P, Lu X (2014) Online stochastic matching: New algorithms with better bounds. _Mathematics of Operations Research_ 39(3):624–646.
  * Jasin and Sinha [2015] Jasin S, Sinha A (2015) An lp-based correlated rounding scheme for multi-item ecommerce order fulfillment. _Operations Research_ 63(6):1336–1351.
  * Jiang [2023] Jiang J (2023) Constant approximation for network revenue management with markovian-correlated customer arrivals. _arXiv preprint arXiv:2305.05829_ .
  * Jiang et al. [2022] Jiang J, Ma W, Zhang J (2022) Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack. _Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , 1221–1246 (SIAM).
  * Kleinberg and Weinberg [2012] Kleinberg R, Weinberg SM (2012) Matroid prophet inequalities. _Proceedings of the forty-fourth annual ACM symposium on Theory of computing_ , 123–136.
  * Kuhn et al. [2019] Kuhn D, Esfahani PM, Nguyen VA, Shafieezadeh-Abadeh S (2019) Wasserstein distributionally robust optimization: Theory and applications in machine learning. _Operations research & management science in the age of analytics_, 130–166 (Informs).
  * Lee and Singla [2018] Lee E, Singla S (2018) Optimal online contention resolution schemes via ex-ante prophet inequalities. _26th European Symposium on Algorithms, ESA 2018_ , . (Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing).
  * Lei et al. [2022] Lei Y, Jasin S, Uichanco J, Vakhutinsky A (2022) Joint product framing (display, ranking, pricing) and order fulfillment under the multinomial logit model for e-commerce retailers. _Manufacturing & Service Operations Management_ 24(3):1529–1546.
  * Lucier [2017] Lucier B (2017) An economic view of prophet inequalities. _ACM SIGecom Exchanges_ 16(1):24–47.
  * Ma [2018] Ma W (2018) Improvements and generalizations of stochastic knapsack and markovian bandits approximation algorithms. _Mathematics of Operations Research_ 43(3):789–812.
  * Ma [2023] Ma W (2023) Order-optimal correlated rounding for fulfilling multi-item e-commerce orders. _Manufacturing & Service Operations Management_ 25(4):1324–1337.
  * Ma et al. [2023] Ma W, Xu P, Xu Y (2023) Fairness maximization among offline agents in online-matching markets. _ACM Transactions on Economics and Computation_ 10(4):1–27.
  * MacRury and Ma [2023] MacRury C, Ma W (2023) Random-order contention resolution via continuous induction: Tightness for bipartite matching under vertex arrivals. _arXiv preprint arXiv:2310.10101_ .
  * MacRury et al. [2023] MacRury C, Ma W, Grammel N (2023) On (random-order) online contention resolution schemes for the matching polytope of (bipartite) graphs. _Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , 1995–2014 (SIAM).
  * Manshadi et al. [2012] Manshadi VH, Gharan SO, Saberi A (2012) Online stochastic matching: Online actions based on offline statistics. _Mathematics of Operations Research_ 37(4):559–573.
  * Mehta et al. [2013] Mehta A, et al. (2013) Online matching and ad allocation. _Foundations and Trends® in Theoretical Computer Science_ 8(4):265–368.
  * Naor et al. [2023] Naor JS, Srinivasan A, Wajc D (2023) Online dependent rounding schemes. _arXiv preprint arXiv:2301.08680_ .
  * Papadimitriou et al. [2021] Papadimitriou C, Pollner T, Saberi A, Wajc D (2021) Online stochastic max-weight bipartite matching: Beyond prophet inequalities. _Proceedings of the 22nd ACM Conference on Economics and Computation_ , 763–764.
  * Pollner et al. [2023] Pollner T, Roghani M, Saberi A, Wajc D (2023) Improved online contention resolution for matchings and applications to the gig economy. _Mathematics of Operations Research_ .
  * Purohit et al. [2019] Purohit M, Gollapudi S, Raghavan M (2019) Hiring under uncertainty. _International Conference on Machine Learning_ , 5181–5189 (PMLR).
  * Qiu and Singla [2022] Qiu F, Singla S (2022) Submodular dominance and applications. _arXiv preprint arXiv:2207.04957_ .
  * Qiu et al. [2023] Qiu G, Feng Y, Zhou S, Wu X (2023) Improved competitive ratio for edge-weighted online stochastic matching. _International Conference on Web and Internet Economics_ , 527–544 (Springer).
  * Rios and Torrico [2023] Rios I, Torrico A (2023) Platform design in matching markets: A two-sided assortment optimization approach. _arXiv preprint arXiv:2308.02584_ .
  * Saberi and Wajc [2021] Saberi A, Wajc D (2021) The greedy algorithm is not optimal for on-line edge coloring. _48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)_ (Schloss Dagstuhl-Leibniz-Zentrum für Informatik).
  * Segev and Singla [2021] Segev D, Singla S (2021) Efficient approximation schemes for stochastic probing and prophet problems. _Proceedings of the 22nd ACM Conference on Economics and Computation_ , 793–794.
  * Singla [2018] Singla S (2018) The price of information in combinatorial optimization. _Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms_ , 2523–2532 (SIAM).
  * Tang et al. [2022] Tang ZG, Wu J, Wu H (2022) (fractional) online stochastic matching via fine-grained offline statistics. _Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing_ , 77–90.
  * Torrico et al. [2020] Torrico A, Carvalho M, Lodi A (2020) Multi-agent assortment optimization in sequential matching markets. _arXiv preprint arXiv:2006.04313_ .
  * Vazirani [2001] Vazirani VV (2001) _Approximation algorithms_ , volume 1 (Springer).
  * Weitzman [1978] Weitzman M (1978) _Optimal search for the best alternative_ , volume 78 (Department of Energy).
  * Williamson and Shmoys [2011] Williamson DP, Shmoys DB (2011) _The design of approximation algorithms_ (Cambridge university press).
  * Yan [2011] Yan Q (2011) Mechanism design via correlation gap. _Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms_ , 710–719 (SIAM).
  * Yan [2024] Yan S (2024) Edge-weighted online stochastic matching: Beating. _Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , 4631–4640 (SIAM).