Jiang, Ma and Zhang

Tightness without Counterexamples: A New Approach and New Results for Prophet
Inequalities

$\text{Jiashuo Jiang}^{\dagger}$ $\text{Will Ma}^{\ddagger}$ $\text{Jiawei
Zhang}^{\S}$

$\dagger\leavevmode\nobreak\ $Department of Industrial Engineering & Decision
Analytics, Hong Kong University of Science and Technology
$\ddagger\leavevmode\nobreak\ $Decision, Risk, and Operations Division,
Graduate School of Business, Columbia University
$\S\leavevmode\nobreak\ $Department of Technology, Operations & Statistics,
Stern School of Business, New York University

Prophet inequalities consist of many beautiful statements that establish tight
performance ratios between online and offline allocation algorithms.
Typically, tightness is established by constructing an algorithmic guarantee
and a worst-case instance separately, whose bounds match as a result of some
“ingenuity”. In this paper, we instead formulate the construction of the
worst-case instance as an optimization problem, which directly finds the tight
ratio without needing to construct two bounds separately.

Our analysis of this complex optimization problem involves identifying
structure in a new “Type Coverage” dual problem. It can be seen as akin to the
celebrated Magician and OCRS (Online Contention Resolution Scheme) problems,
except more general in that it can also provide tight ratios relative to the
optimal offline allocation, whereas the earlier problems only establish tight
ratios relative to the ex-ante relaxation of the offline problem.

Through this analysis, our paper provides a unified framework that derives new
prophet inequalities and recovers existing ones, with our principal results
being two-fold. First, we show that the “oblivious” method of setting a static
threshold due to Chawla et al. (2020), surprisingly, is best-possible among
all static threshold algorithms, under any number $k$ of starting units. We
emphasize that this result is derived without needing to explicitly find any
counterexample instances. This implies the tightness of the asymptotic
convergence rate of $1-O(\sqrt{\log k/k})$ for static threshold algorithms
from Hajiaghayi et al. (2007). Turning to the IID setting, our second
principal result is to use our framework to numerically illustrate the tight
guarantee (of adaptive algorithms) under any number $k$ of starting units. The
tight guarantee has been previously characterized only under $k=1$ by Correa
et al. (2017), and our guarantees for $k>1$ exceed the state-of-the-art from
the free-order setting due to Beyhaghi et al. (2021).

##  1 Introduction

Prophet inequalities describe fundamental problems in online decision making.
In the multi-unit variant of prophet inequalities, there is a decision maker
with $k$ slots and there are $n$ agents arriving sequentially. Each agent has
a discrete valuation drawn from a known distribution, which will be convenient
for us to denote in the following form. There are $m$ possible types and each
agent $i$ belongs to one type $j$ independently with a given probability
$p_{i,j}$. Then, the valuation or value for an agent of type $j$ is given by
$r_{j}$, with $r_{1}\geq\cdots\geq r_{m}\geq 0$. After the type of an incoming
agent is revealed, the reward of accepting this agent is known and the
decision maker has to decide immediately whether to spend one slot to collect
this reward, or reject the agent. The decision has to be made on-the-fly;
i.e., the decision is irrevocable and cannot look ahead at the types of the
agents who have not yet arrived. The performance of the decision maker is
measured as the total value collected in expectation.

The guarantee of an online policy for the decision maker is defined by the
ratio of its performance to that of a benchmark. The typical benchmark for
prophet inequalities is the expected value collected by a prophet, who sees in
advance the types of all agents and fills the slots prioritizing the agents
with highest values. By comparing with the prophet, the classical work Krengel
and Sucheston (1978) obtains the tight guarantee of $1/2$ when there is one
slot (i.e. $k=1$). Correa et al. (2017) show that the tight guarantee improves
to $0.745$ under the $\mathrm{IID}$ special case, where the value distribution
is identical for each agent. Another widely used benchmark is the ex-ante
relaxation, which can be formulated via linear programming (LP). The benefits
of the ex-ante benchmark are twofold: (i) it is generally easier to analyze
(Alaei 2014) and possesses special structure such that the optimal policy and
tight guarantee can be derived even when $k>1$ (Jiang et al. 2022); (ii) it
enables a decomposition technique where guarantees for a single resource can
easily extend to online allocation problems with multiple resources (i.e.
multiple types of slots) (Alaei et al. 2012), even allowing for very general
allocation procedures involving customer choice (Gallego et al. 2015).

Various online policies have been developed in the literature in order to
achieve a good performance guarantee relative to the benchmarks. Some of the
tight performance guarantees are derived from optimal adaptive policies, where
the decision depends both on the realization of the current agent’s value and
the number of remaining agents and slots; see, e.g., Correa et al. (2017) and
Jiang et al. (2022). Simpler but more restrictive static threshold policies
also enjoy strong performance guarantees (Hajiaghayi et al. 2007). A static
threshold policy must fix a threshold value at the start and accept any agent
with valuation exceeding the threshold, while there are empty slots. The
further distinction of an oblivious static threshold policy was introduced in
Chawla et al. (2020), where the threshold is allowed to depend on the
probabilities $\\{p_{i,j}\\}_{\forall i\in[n],\forall j\in[m]}$ but not the
values $\\{r_{j}\\}_{\forall j\in[m]}$.

The goal of this paper is to characterize tight performance guarantees for
general online policies as well as (oblivious) static threshold policies, with
respect to either the prophet benchmark or the ex-ante benchmark, in both the
IID and non-IID settings. We denote by $I$ the problem instance and
$\mathcal{I}^{\mathrm{IID}}_{k,n}$ (resp, $\mathcal{I}_{k,n}$) the collection
of all IID (resp. non-IID) problem instances with $n$ agents and $k$ slots. We
also denote by $\mathsf{DP}(I)$ the performance of the optimal dynamic
program, $\mathsf{ST}(I)$ the performance of the optimal non-oblivious
threshold policy, $\mathsf{OST}(I)$ the performance of the optimal oblivious
threshold policy, $\mathsf{Proph}(I)$ the prophet benchmark, and
$\mathsf{ExAnte}(I)$ the ex-ante benchmark, all for the problem instance $I$
(see Section 2 for formal definitions of these concepts).

###  1.1 Outline of Techniques and All Results

The main difference between our approach and existing ones is that we are able
to formulate the problem of finding the worst-case instance as an optimization
problem, while existing approaches rely on constructing an algorithmic
guarantee and a worst-case instance separately. In what follows, we elaborate
on our techniques in comparison to the literature.

We introduce a new LP framework which explicitly computes the tight guarantee
of a class of online policy versus a benchmark. Note that in order to compute
the guarantee of a policy, one needs to minimize the ratio of the expected
value collected by the policy divided by the benchmark, over all instances,
where an instance is described by $\\{p_{i,j},r_{j}\\}_{\forall
i\in[n],\forall j\in[m]}$. The new idea of our framework is to break down this
minimization problem into two stages. Given a fixed number of slots $k$ and
agents $n$, we first minimize over $m$ and the type distributions
$\\{p_{i,j}\\}_{\forall i\in[n],\forall j\in[m]}$, and we then minimize over
the type valuations $\\{r_{j}\\}_{\forall j\in[m]}$. For example, if we are
computing the tight guarantee for adaptive online algorithms relative to the
prophet over general non-IID instances, then our formulation would be

$\inf_{m,\\{p_{i,j}\\}_{\forall i\in[n],\forall
j\in[m]}}\inf_{\\{r_{j}\\}_{\forall
j\in[m]}}\frac{\mathsf{DP}(I)}{\mathsf{Proph}(I)}.$ (1)

The inner optimization problem over $\\{r_{j}\\}_{\forall j\in[m]}$ can be
formulated as an LP. The dual of this LP gives us a new problem that is
defined for each $m$ and $\\{p_{i,j}\\}_{\forall i\in[n],\forall j\in[m]}$,
whose optimal solution has a nice structure. This structure enables us to
derive multiple new results, and recover several existing results in a clean
way.

#### Type Coverage problem.

The new dual LP can be interpreted as a “Type Coverage” problem, defined as
follows. For each type $j$, let $Q_{j}$ denote the expected number of agents
of type $j$ or better accepted by the benchmark. For example, if the benchmark
is the prophet, then

$Q_{j}=\mathbb{E}[\min\\{\sum_{i=1}^{n}\mathrm{Ber}\Big{(}\sum_{j^{\prime}=1}^{j}p_{i,j^{\prime}}\Big{)},k\\}],$
(2)

where $\mathrm{Ber}(p)$ denotes an independent Bernoulli random variable of
mean $p$. The RHS of (2) then counts the total agents among $i=1,\ldots,n$ who
realize to a type $j^{\prime}$ whose value is at least as good as that of type
$j$, and truncates this total by $k$ to indicate the number of such agents
accepted by the prophet. Finally, for an online policy to achieve a guarantee
of $\theta$ in this dual Type Coverage problem, for every type $j\in[m]$, the
number of agents of type $j$ or better accepted by the online policy must be
at least $\theta\cdot Q_{j}$.

Our framework shows that the guarantee under the worst-case instance in the
original problem is equivalent to the guarantee under the worst-case instance
for the Type Coverage problem, where now the parameters $r_{j}$ have been
eliminated. If the original prophet problem is restricted to an oblivious
static threshold policy, then the corresponding dual restriction is to have
any static threshold policy. Meanwhile, if the original problem allowed non-
oblivious static thresholds, then the dual allows randomized static thresholds
(which can achieve a strictly greater $\theta$ for the Type Coverage problem,
as we show later in Lemma 3.8). These correspondences in the restrictions,
which are not a priori obvious, are consequences of our framework and
formalized in Section 2.2.

Another interpretation of our approach in (1) is that we are decoupling the
adversary’s optimization into an outer problem over ordinal distributions (of
$m$ ranked types) and an inner problem over cardinal valuations consistent
with these ordinal rankings. General static thresholds can be set after the
adversary decides these cardinal valuations, whereas oblivious static
thresholds must be set before the adversary decides them.

#### Comparison: Magician/OCRS (Online Contention Resolution Scheme) problems.

Magician (Alaei 2014) and OCRS (Feldman et al. 2021) are existing auxiliary
problems used to derive prophet inequalities against the ex-ante benchmark. In
these problems, each agent has an active probability and must be guaranteed to
be accepted with a probability at least $\theta$ conditional on being active,
by the online policy. The goal is to achieve the maximum $\theta$. It has been
shown in Lee and Singla (2018) that the worst-case for ex-ante prophet
inequalities always occurs on weighted Bernoulli distributions and using LP
duality, they show that the tight guarantee matches that of a Magician/OCRS
problem.

Although ex-ante prophet inequalities are stronger and hence imply non-ex-ante
prophet inequalities, no analogues of Magician/OCRS have been known for
deriving tight non-ex-ante prophet inequalities, until now. Our new Type
Coverage problem essentially generalizes the Magician/OCRS problems to allow
for agents who take non-binary states, which leads to a formulation of tight
guarantees for non-ex-ante prophet inequalities. Our Type Coverage problem is
also more general in that it can recover the Magician/OCRS problems when we
use ex-ante as the benchmark in our framework, as we derive in Section 3.1.

We now proceed to describe other results achieved by our framework.

#### (Oblivious) Static thresholds in Non-IID setting.

First, for $\mathsf{OST}$ policies in the non-IID setting, we recover the
following positive result, which has been previously established in Chawla et
al. (2020):

$\displaystyle\inf_{I\in\mathcal{I}_{k,n}}\frac{\mathsf{OST}(I)}{\mathsf{ExAnte}(I)}$
$\displaystyle\geq\mathrm{BernOpt}(k,n).$ (3)

In (3), $\mathrm{BernOpt}(k,n)$ is an optimization problem over $n-1$
Bernoulli random variables that tweaks what Chawla et al. (2020) derived, with
the formal specification of $\mathrm{BernOpt}(k,n)$ found in Corollary 3.6 in
Section 3.2. We then show this specification to be tight for oblivious static
thresholds:

$\displaystyle\inf_{I\in\mathcal{I}_{k,n}}\frac{\mathsf{OST}(I)}{\mathsf{Proph}(I)}\leq\mathrm{BernOpt}(k,n),$
(4)

even when competing against the weaker prophet benchmark. We derive this upper
bound without explicitly constructing any counterexamples. Instead, we show
that when the online policy is restricted to $\mathsf{OST}$, the value of the
dual Type Coverage problem cannot exceed a quantity (exact formulation given
in (19)) which can be shown to be equivalent to $\mathrm{BernOpt}(k,n)$.

We then prove that even non-oblivious static threshold policies cannot do
better than the method of Chawla et al. (2020) in the worst case. Although
there can be a separation between $\mathsf{OST}$ and $\mathsf{ST}$ on a given
instance (see Lemma 3.8 in Section 3.3), we can use the fact that the worst
case arises when certain Bernoulli random variables have equal probabilities,
and then show through a technical saddle-point argument (Theorem 3.10) that
randomized static thresholds (corresponding to $\mathsf{ST}$) cannot do better
than a deterministic one (corresponding to $\mathsf{OST}$) in the dual Type
Coverage problem on this worst-case instance. In this way, we show that the
ratios $\mathsf{ST}/\mathsf{Proph}$, $\mathsf{ST}/\mathsf{ExAnte}$,
$\mathsf{OST}/\mathsf{Proph}$, and $\mathsf{OST}/\mathsf{ExAnte}$ are all
equivalent in the worst case over non-IID distributions, which is new to the
literature.

Finally, we show that all four of these ratios, after taking an infimum over
$n$ (which is the typical way $k$-unit prophet inequalities are stated), grow
at the rate of $1-\Theta(\sqrt{\log k/k})$. This establishes that the
asymptotic guarantee of $1-O(\sqrt{\log k/k})$ for static threshold policies
from Hajiaghayi et al. (2007) is tight (Proposition 3.7).

#### Adaptive policies in IID setting.

When valuations are IID, the probability $p_{i,j}$ of drawing any type $j$ is
identical across agents $i$, equal to some value $p_{j}$. In this setting, the
hardest case of our type coverage problem can be characterized—it is the limit
where there are an infinite number of types $j$ each with infinitesimally
small probability $p_{j}$. This allows us to further reduce our dual problem
into a single semi-infinite LP. That is, for any of the policy classes
$\mathsf{DP}$, $\mathsf{ST}$, or $\mathsf{OST}$, relative to either of the
benchmarks $\mathsf{Proph}$ or $\mathsf{ExAnte}$, and for any values of $k$
and $n$, we can write a single semi-infinite LP whose objective value equals
the tight guarantee.

For the class of adaptive policies $\mathsf{DP}$, relative to the benchmark
$\mathsf{Proph}$, and for $n>k>1$, we can only computationally solve this
semi-infinite LP, approximately. More specifically, we establish for any
$\varepsilon>0$ a finite LP with a discretized subset of constraints, whose
objective value is within an $\varepsilon$-error of the original semi-infinite
LP (Lemma 4.8). We solve the discretized LP’s for $\varepsilon=0.0001$,
$k\in\\{2,\ldots,10\\}$, and $n$ as large as $8000$, and display the results
in Table 1. They suggest significantly improved bounds for $k$-unit prophet
inequalities in the IID setting, compared to the best-known bounds that carry
over from the free-order setting (Beyhaghi et al. 2021).

In all other cases, we can exactly characterize the optimal solution to our
semi-infinite LP, recovering existing results in a unified way. First, when
$k=1$, we obtain a new derivation of the classical $0.745$ guarantee for
$\mathsf{DP}/\mathsf{Proph}$ under the IID setting (Hill and Kertz 1982,
Correa et al. 2017). The key step of our derivation is that the simplified
semi-infinite LP admits a closed-form optimal solution, which helps us to
establish the worst case as $n\rightarrow\infty$ and obtain the value of the
optimal guarantee. Section 1.3 compares our derivation to other recent
simplifications of this result.

#### (Oblivious) Static thresholds in IID setting.

We can also characterize the optimal solution to our semi-infinite LP for all
five other ratios ($\mathsf{DP}/\mathsf{ExAnte}$,
$\mathsf{ST}/\mathsf{Proph}$, $\mathsf{ST}/\mathsf{ExAnte}$,
$\mathsf{OST}/\mathsf{Proph}$, $\mathsf{OST}/\mathsf{ExAnte}$), for any values
of $k$ and $n$, showing them to be equal to
$\frac{\mathbb{E}[\min\\{\mathrm{Bin}(n,k/n),k\\}]}{k}$ in the worst case
(Section 4.1). That is, unlike the non-IID setting, even the optimal adaptive
policy $\mathsf{DP}$ cannot do any better than static thresholds when compared
to the ex-ante benchmark. We then establish a stronger equivalence between
oblivious and non-oblivious static thresholds in the IID setting. Recall that
in the non-IID setting, the equivalence was only true in the worst case, i.e.,
only after taking an infimum over problem instance $I$ were the ratios
$\mathsf{ST}/\mathsf{Proph}$, $\mathsf{ST}/\mathsf{ExAnte}$,
$\mathsf{OST}/\mathsf{Proph}$, $\mathsf{OST}/\mathsf{ExAnte}$ equal. In the
IID setting, we show that $\mathsf{ST}$ is no better than $\mathsf{OST}$ with
respect to both $\mathsf{Proph}$ and $\mathsf{ExAnte}$, on every type
distribution. As a result, $\mathsf{OST}$’s are instance-optimal for static
threshold policies in the IID setting, which is surprising to us (see Section
4.2).

Finally, we should mention that the aforementioned bound of
$\frac{\mathbb{E}[\min\\{\mathrm{Bin}(n,k/n),k\\}]}{k}$ is already known in
some cases, as the relationships

$\inf_{I\in\mathcal{I}^{\mathrm{IID}}_{k,n}}\frac{\mathsf{OST}(I)}{\mathsf{ExAnte}(I)}\geq\frac{\mathbb{E}[\min\\{\mathrm{Bin}(n,k/n),k\\}]}{k}\geq\inf_{I\in\mathcal{I}^{\mathrm{IID}}_{k,n}}\frac{\mathsf{DP}(I)}{\mathsf{ExAnte}(I)}$

are straight-forward to derive and sometimes considered folklore. However, an
upper bound on
$\inf_{I\in\mathcal{I}^{\mathrm{IID}}_{k,n}}\frac{\mathsf{ST}(I)}{\mathsf{Proph}(I)}$,
which is needed to complete our result, appears to require lengthier
derivation. For example, Arnosti and Ma (2022) are only able to do this in the
limit as $n\to\infty$, and require a complicated counterexample. By contrast,
the tight ratio of $\frac{\mathbb{E}[\min\\{\mathrm{Bin}(n,k/n),k\\}]}{k}$
directly falls out of our framework for every value of $k$ and $n$, without
ever constructing any counterexamples.

###  1.2 Recap of Main Results

Beyond our new framework that derives tight guarantees without
counterexamples, we would like to summarize our contributions in terms of new
statements that were previously unknown.

  1. 1.

In the non-IID setting, we show that the guarantees for static threshold
policies from Chawla et al. (2020) are tight for every $k$, and moreover grow
as $1-\Theta(\sqrt{\log k/k})$ when $k\to\infty$. This establishes the
tightness of the asymptotic guarantee of $1-O(\sqrt{\log k/k})$ for static
threshold policies from Hajiaghayi et al. (2007), and also separates static
threshold policies from the asymptotic guarantee of $1-O(\sqrt{1/k})$ for
adaptive policies due to Alaei (2014).

  2. 2.

We use our framework to numerically illustrate the first $k$-unit prophet
inequalities (with $k>1$) in the IID setting, for adaptive policies. Our
guarantees exceed the best-known $k$-unit prophet inequalities from the free-
order setting (Beyhaghi et al. 2021), and are tight in the IID setting up to
numerical error (from having a finite $n$) and a discretization error (of
$0.0001$).

  3. 3.

Our framework shows that oblivious static thresholds perform as well as non-
oblivious ones on any instance in the IID setting, but that this only holds
after taking a worst-case over instances in the non-IID setting. Our framework
also seamlessly implies tight guarantees for all combinations of $k$ and $n$,
some of which were previously only proven in the limit as $n\to\infty$.

###  1.3 Further Related Work

Multi-unit prophet inequalities. Since first posed by Krengel and Sucheston
(1978), prophet inequalities have been extensively studied (see a survey
Correa et al. (2019a)) and in recent years, there has been a lot of work
studying prophet inequalities with various feasibility constraints over the
agents that can be accepted, including knapsack constraint (Feldman et al.
2021) and general matroid constraints (Kleinberg and Weinberg 2012). Our
problem poses a uniform matroid constraint for the agents, and our problem is
also referred to as the multi-unit prophet inequalities (Hajiaghayi et al.
2007). In a seminal work, Alaei (2014) obtains a $1-1/\sqrt{k+3}$-guarantee
when there are $k$ slots in total. Jiang et al. (2022) improves the guarantee
for every $k>1$ and shows that their guarantee is tight with respect to the
ex-ante benchmark. Our work further improves the existing results by
formulating an LP to compute the ratio of a policy for every given value
distribution densities. By minimizing the value distribution densities, we are
able to obtain the tight guarantee, not only with respect to the ex-ante
benchmark, but also with respect to the prophet benchmark. Our framework also
enables us to study various types of policies, including the (oblivious)
static threshold policies, at the same time, while the approaches developed in
Alaei (2014), Jiang et al. (2022) are to analyze adaptive policies.

The connection to online pricing. Prophet inequalities have also been
extensively used as an algorithmic subroutine for online pricing and mechanism
design, since the seminal works of Hajiaghayi et al. (2007), Chawla et al.
(2010), Alaei (2014). Interested readers are referred to Lucier (2017) for a
more detailed survey. Recently, Correa et al. (2019b) proves that designing
posted price mechanisms is equivalent to designing online policies for prophet
inequalities, in terms of performance guarantees. As a result, our approaches
can be directly applied to designing online pricing policies with tight
guarantees. Moreover, the static threshold policies we developed for prophet
inequalities imply static threshold policies for online pricing, which are
easy to describe and enjoy practical benefits - it is anonymous, non-adaptive,
and order-oblivious (Chawla et al. 2020).

Static thresholds. Static threshold policies are important policies for both
prophet inequalities and online pricing and have been extensively studied. In
particular, Hajiaghayi et al. (2007) shows that a static threshold policy
enjoys a guarantee of $1-O(\sqrt{\log k/k})$, where $k$ is the number of
slots. In the $\mathrm{IID}$ setting, Yan (2011) shows that a static threshold
policy achieves a guarantee of $1-k^{k}/e^{k}k!$, which is tight with respect
to the ex-ante benchmark. This guarantee has been extended in Arnosti and Ma
(2022) to the prophet secretary setting where the agents arrive in a random
order, and has been shown to be tight among the static threshold policies.
Beyond explicitly computing the tight guarantees for the optimal static
threshold policies, our framework also reveals that the optimal static
threshold policy can be value-oblivious under various settings, which implies
that only the type distributions are required to be known when designing the
optimal static threshold policy. The benefits of being oblivious have been
illustrated in Arnosti and Ma (2022) when only a monotone transformation of
values (rather than the values themselves) can be observed.

Other simplifications of prophet inequalities. We note that a simplified proof
of the IID 0.745 bound has also been recently introduced in Liu et al. (2021),
using the notion of $(\varepsilon,\delta)$-smallness. Our proof is of a
different nature, where we directly solve the adversary’s optimization problem
over all instances. Another simplified proof of the 0.745 bound is obtained in
Brustle et al. (2022). They formulate an infinite-dimensional non-linear
optimization problem and analyze when the objective value of their
optimization problem is non-negative. Additionally, their optimization problem
concerns how often each agent is accepted by $\mathsf{DP}$ and
$\mathsf{Proph}$. By contrast, our optimization problem concerns how many of
each type of agent is accepted by $\mathsf{DP}$ and $\mathsf{Proph}$, and we
have a semi-infinite linear program which directly yields the tight guarantee.

##  2 Problem Classes Considered and General Framework

We consider the prophet inequality problem where $k$ out of $n>k$ agents can
be accepted. That is, initially there are $k$ slots, and $n$ agents arrive in
order $i=1,\ldots,n$, each with a valuation $R_{i}\geq 0$ that is revealed
only when agent $i$ arrives. One must then immediately decide whether to use a
slot to accept agent $i$, or to reject agent $i$ forever, with this decision
being irrevocable. Once all $k$ slots have been used, no further agents can be
accepted. The valuations $R_{i}$ are drawn independently at random from known
distributions. The objective is to make accept/reject decisions on-the-fly, in
a way that maximizes the expected sum of valuations of accepted agents.

We assume that each $R_{i}$ is drawn from a discrete distribution, input as
follows. There is a universe of $m$ possible valuations, sorted in the order
$r_{1}\geq\cdots\geq r_{m}\geq 0$. For each agent $i$, we let $p_{ij}\geq 0$
denote the probability that their valuation $R_{i}$ realizes to $r_{j}$, for
all $j=1,\ldots,m$, with $\sum_{j=1}^{m}p_{ij}=1$. We refer to index $j$ as
the type of an agent, with smaller indices $j$ said to be better. For
simplicity, we also assume that agents arrive in exactly the order
$i=1,\ldots,n$, which is known in advance. Although many of the algorithms we
discuss hold under certain adversarial manipulations of the arrival order, we
do not attempt to make such distinctions comprehensively.

######  Definition 2.1 (Instance, IID vs. Non-IID)

An instance $I$ of the prophet inequality problem is defined by the number of
slots $k$, agents $n$, types $m$, the valuations $r_{1},\ldots,r_{m}$, and the
probability vectors $(p_{1j})_{j=1}^{m},\ldots,(p_{nj})_{j=1}^{m}$ under the
fixed arrival order $i=1,\ldots,n$. We let $\mathcal{I}_{k,n}$ denote the
class of all instances with $k$ slots and $n$ agents, with
$\mathcal{I}_{k}:=\bigcup_{n=1}^{\infty}\mathcal{I}_{k,n}$. If $p_{ij}$ is
identical to some $p_{j}$ across all agents $i$, for each type $j$, then we
say that the instance is IID (independent and identically distributed), and we
let $\mathcal{I}^{\mathrm{IID}}_{k,n}$ denote the class of all IID instances
with $k$ slots and $n$ agents, with
$\mathcal{I}^{\mathrm{IID}}_{k}:=\bigcup_{n=1}^{\infty}\mathcal{I}^{\mathrm{IID}}_{k,n}$.
We sometimes refer to general instances as non-IID.

Under the assumptions mentioned earlier, given an instance, the optimal policy
for making accept/reject decisions is easy to compute using dynamic
programming (DP). However, as discussed in the Introduction, there is great
interest and applicability in comparing the performance of DP to that of a
prophet who knows the realizations of $R_{i}$ in advance, over different
instances. Furthermore, one can compare against the stronger ex-ante benchmark
in which the number of agents of each type always equals its expectation. We
now formally define these benchmarks.

######  Definition 2.2 (Prophet)

The prophet’s performance on an instance $I$, denoted $\mathsf{Proph}(I)$, is
the expected sum of the $k$ largest realized valuations. Formally, letting
$[n]$ denote the set $\\{1,\ldots,n\\}$,

$\displaystyle\mathsf{Proph}(I)=\mathbb{E}\left[\max_{S\subseteq[n],|S|\leq
k}\sum_{i\in S}R_{i}\right].$

######  Definition 2.3 (Ex-ante Relaxation)

The ex-ante relaxation is defined by the following LP:

$\displaystyle\mathsf{ExAnte}(I)=$ $\displaystyle\max$
$\displaystyle\sum_{j=1}^{m}r_{j}a_{j}$ $\displaystyle\mathrm{s.t.\ }$
$\displaystyle\sum_{j=1}^{m}a_{j}\leq k$ $\displaystyle 0\leq
a_{j}\leq\sum_{i=1}^{n}p_{ij}\quad\quad\forall j\in[m]$

in which variable $a_{j}$ can be interpreted as the number of agents of type
$j$ accepted.

The following standard result is easy to show, holding because on every sample
path, the prophet’s selection of $k$ largest valuations forms a feasible
solution to the ex-ante LP.

######  Proposition 2.4 (Folklore)

$\mathsf{Proph}(I)\leq\mathsf{ExAnte}(I)$ for all instances $I$.

Having explained the benchmarks $\mathsf{Proph}(I)$ and $\mathsf{ExAnte}(I)$,
we are now ready to define the notion of a prophet inequality. Let
$\mathsf{DP}(I)$ denote the expected sum collected by the optimal DP algorithm
on an instance $I$. Let $\mathcal{I}$ denote a class of instances.

###### Definition 2.5

A prophet inequality (resp. ex-ante prophet inequality) is a statement of the
form

$\displaystyle\frac{\mathsf{DP}(I)}{\mathsf{Proph}(I)}\geq\alpha\qquad(\text{resp.
}\frac{\mathsf{DP}(I)}{\mathsf{ExAnte}(I)}\geq\alpha)$ $\displaystyle\forall
I\in\mathcal{I}$ (5)

for some constant $\alpha\leq 1$. We refer to $\alpha$ as the guarantee
relative to the prophet (resp. ex-ante relaxation). We say that $\alpha$ is
tight if it is the supremum value for which (5) holds.

In this paper we are interested in tight guarantees relative to both the
prophet and ex-ante relaxation, for both the classes of IID and non-IID
instances with a particular number of slots $k$. That is, we are interested in
the values of
$\alpha=\inf_{I\in\mathcal{I}}\frac{\mathsf{DP}(I)}{\mathsf{Proph}(I)}$ and
$\alpha=\inf_{I\in\mathcal{I}}\frac{\mathsf{DP}(I)}{\mathsf{ExAnte}(I)}$ when
$\mathcal{I}$ can be $\mathcal{I}_{k}$ or $\mathcal{I}^{\mathrm{IID}}_{k}$ for
some $k$, which will affect the value of $\alpha$. Many of our results also
imply tight guarantees for more granular classes of instances, e.g.
$\mathcal{I}=\mathcal{I}_{k,n}$ or
$\mathcal{I}^{\mathrm{IID}}=\mathcal{I}_{k,n}$, which restrict to having
exactly $n$ agents. Guarantees relative to the ex-ante relaxation are worse
than those relative to the prophet (due to Proposition 2.4), and guarantees
are also be worse for larger classes of instances (e.g. non-IID instead of
IID). Finally, we sometimes consider the following subclass of policies that
are not as powerful as the optimal DP, which would also make guarantees worse.

######  Definition 2.6 (Static Threshold Policies)

A static threshold policy accepts the first $k$ agents to arrive who have
valuation at least $r_{J}$, or equivalently have a type $j$ with $j\leq J$,
for some fixed index $J\in[m]$. A static threshold policy is also allowed to
set a tie-break probability $\rho\in(0,1]$, where each agent of type exactly
$J$ is accepted (while slots remain) according to an independent coin flip of
probability $\rho$.

We emphasize that a static threshold policy is not allowed to change $J$ on-
the-fly based on the remaining number of slots or agents, making them less
powerful than the optimal DP. Static policies of this type have been
previously studied in Ehsani et al. (2018), Chawla et al. (2020), Arnosti and
Ma (2022), who note that the tie-break probability is unnecessary (i.e. one
can always set $\rho=1$) under alternative models where the valuation
distributions are continuous.

We further distinguish between oblivious static threshold algorithms that must
set $J,\rho$ without knowing the cardinal values of $r_{1},\ldots,r_{m}$ (but
knowing $m$ and $\\{p_{ij}:i\in[n],j\in[m]\\}$), vs. an algorithm that can set
$J,\rho$ optimally with full knowledge of the instance $I$. This distinction
was introduced by Chawla et al. (2020) and the benefits of being oblivious are
elaborated on in Arnosti and Ma (2022). As an example of this distinction, a
thresholding rule based on the median value of $\mathsf{Proph}(I)$ (as
proposed in Samuel-Cahn (1984)) is oblivious, but a thresholding rule based on
the mean value (as proposed in Kleinberg and Weinberg (2012)) is not.

###  2.1 Main Idea of General Framework

The idea of our general framework is to explicitly formulate the adversary’s
optimization problem of minimizing some prophet inequality ratio, e.g.
$\mathsf{DP}(I)/\mathsf{Proph}(I)$, over all instances $I$ belonging to some
class. This allows us to directly compute the tight guarantee $\alpha$ in
different settings, without having to separately construct a lower bound
(usually based on analyzing a simple algorithm) and hoping that it is possible
to construct a matching upper bound. Of course, the adversary’s problem can be
highly intractable, because it needs to optimize over the space of
distributions, and encapsulate the best response from the (possibly
restricted) algorithm on each instance $I$.

Our general framework overcomes this intractability by breaking down the
adversary’s problem into two stages. Treating the number of slots $k$ and
agents $n$ as fixed, we assume that the adversary first optimizes over $m$ and
the type distributions $\\{p_{ij}:i\in[n],j\in[m]\\}$, and then optimizes over
the specific valuations $\\{r_{j}:j\in[m]\\}$. The inner optimization problem
over $r_{j}$’s can then be formulated as an LP, which encapsulates the
algorithm’s best response using constraints that are linear when the
$p_{ij}$’s are fixed. The dual of this LP gives rise to a new problem that is
expressed solely in terms of the type distributions, whose optimal solution
has a nice structure. This allows us to solve the outer optimization problem
over type distributions in many settings.

Before proceeding we define some notation that will simplify the formulation
of these problems.

######  Definition 2.7 ($\Delta_{j},G_{ij}$)

Let $\Delta_{j}:=r_{j}-r_{j+1}$ for all $j\in[m]$, with $r_{m+1}$ understood
to be 0. We will equivalently write the adversary’s inner optimization problem
using decision variables $\Delta_{j}$. Recalling that $r_{1}\geq\cdots\geq
r_{m}\geq 0$, we have $\Delta_{j}\geq 0$ for all $j$, where $\Delta_{j}$ can
be interpreted as the “valuation gain” when going from type $j+1$ to type $j$.

Also, let $G_{ij}:=\sum_{j^{\prime}=1}^{j}p_{ij^{\prime}}$, the probability
that agent $i$’s valuation is at least $r_{j}$, for all $i\in[n]$ and
$j=0,\ldots,m$. Note that $0=G_{i0}\leq\cdots\leq G_{im}=1$ for all $i$.

###### Proposition 2.8

For any instance $I$,

$\displaystyle\mathsf{Proph}(I)=\sum_{j=1}^{m}\Delta_{j}\cdot\mathbb{E}[\min\\{\sum_{i=1}^{n}\mathrm{Ber}(G_{ij}),k\\}]\qquad\text{and}\qquad\mathsf{ExAnte}(I)=\sum_{j=1}^{m}\Delta_{j}\cdot\min\\{\sum_{i=1}^{n}G_{ij},k\\},$
(6)

where $\mathrm{Ber}(G_{ij})$ denotes an independent Bernoulli random variable
with success probability $G_{ij}$.

Proposition 2.8 is proven in Section 7. Letting $Q_{j}$ denote
$\mathbb{E}[\min\\{\sum_{i=1}^{n}\mathrm{Ber}(G_{ij}),k\\}]$ (resp.
$\min\\{\sum_{i=1}^{n}G_{ij},k\\}$), $Q_{j}$ can be interpreted as the
expected number of agents of type $j$ or better accepted by the prophet (resp.
ex-ante relaxation), which explains the formulas in (6).

We are now ready to formulate the adversary’s inner problem of minimizing
$\mathsf{DP}(I)/\mathsf{Proph}(I)$ or $\mathsf{DP}(I)/\mathsf{ExAnte}(I)$ over
decision variables $\Delta_{j}$. By Proposition 2.8, as long as the type
distributions given by $G_{ij}$ are fixed, both $\mathsf{Proph}(I)$ and
$\mathsf{ExAnte}(I)$ can be expressed as linear combinations of $\Delta_{j}$,
which the adversary normalizes to 1. Subject to this, the adversary then tries
to minimize $\mathsf{DP}(I)$.

######  Definition 2.9 (Inner Problem for Minimizing $\mathsf{DP}$)

Consider the following linear program, with $Q_{j}$ set to
$\mathbb{E}[\min\\{\sum_{i=1}^{n}\mathrm{Ber}(G_{ij}),k\\}]$ (resp.
$\min\\{\sum_{i=1}^{n}G_{ij},k\\}$) for all $j\in[m]$.

$\displaystyle\min\ $ $\displaystyle V^{k}_{1}$ (7a)
$\displaystyle\mathrm{s.t.\ }$ $\displaystyle
V_{i}^{l}=\sum_{j=1}^{m}p_{ij}U^{l}_{ij}+V^{l}_{i+1}$ $\displaystyle\forall
i\in[n],l\in[k]$ (7b) $\displaystyle
U^{l}_{ij}\geq\sum_{j^{\prime}=j}^{m}\Delta_{j^{\prime}}-(V^{l}_{i+1}-V^{l-1}_{i+1})$
$\displaystyle\forall i\in[n],j\in[m],l\in[k]$ (7c)
$\displaystyle\sum_{j=1}^{m}Q_{j}\Delta_{j}=1$ (7d)
$\displaystyle\Delta_{j},U^{l}_{ij}\geq 0$ $\displaystyle\forall
i\in[n],j\in[m],l\in[k]$ (7e)

In constraint (7b), free variable $V^{l}_{i}$ denotes the value-to-go of the
DP when agent $i$ arrives with exactly $l$ slots remaining, with $V^{l}_{i}$
understood to be 0 if $i=n+1$ or $l=0$. Meanwhile, auxiliary variable
$U^{l}_{ij}$ denotes the utility gain when agent $i$ realizes to type $j$ with
$l$ slots remaining. The utility gain $U^{l}_{ij}$ is lower-bounded by both 0
and the expression
$\sum_{j^{\prime}=j}^{m}\Delta_{j^{\prime}}-V^{l}_{i+1}+V^{l-1}_{i+1}$ in
(7c), which denotes the immediate gain from accepting agent $i$ (who has
valuation $r_{j}=\sum_{j^{\prime}=j}^{m}\Delta_{j^{\prime}}$) minus the loss
$(V^{l}_{i+1}-V^{l-1}_{i+1})$ from proceeding to agent $i+1$ with $l-1$
instead of $l$ slots remaining. Finally, constraint (7d) normalizes the value
of $\mathsf{Proph}(I)$ (resp. $\mathsf{ExAnte}(I)$) to 1.

Therefore, in the linear program $V^{k}_{1}$ will equal precisely the optimal
performance $\mathsf{DP}(I)$ of dynamic programming (see e.g. Puterman 2014),
and hence LP (7) correctly describes the adversary’s inner problem of
minimizing $\mathsf{DP}(I)/\mathsf{Proph}(I)$ (resp.
$\mathsf{DP}(I)/\mathsf{ExAnte}(I)$) over all instances $I$ with some given
type distributions. We now take the dual of (7) to uncover a new problem.

######  Definition 2.10 (Dual of Inner Problem for Minimizing $\mathsf{DP}$)

Defining dual variables $x^{l}_{i},y^{l}_{ij},\theta$ for constraints
(7b),(7c),(7d) respectively, the following LP is dual to (7).

$\displaystyle\max\ $ $\displaystyle\theta$ (8a) $\displaystyle\mathrm{s.t.\ \
}$ $\displaystyle\theta\cdot
Q_{j}\leq\sum_{i=1}^{n}\sum_{l=1}^{k}\sum_{j^{\prime}=1}^{j}y^{l}_{ij^{\prime}}$
$\displaystyle\forall j\in[m]$ (8b) $\displaystyle y^{l}_{ij}\leq
p_{ij}x^{l}_{i}$ $\displaystyle\forall i\in[n],j\in[m],l\in[k]$ (8c)
$\displaystyle x^{l}_{i}=\begin{cases}1,&i=1,l=k\\\ 0,&i=1,l<k\\\
x^{l}_{i-1}-\sum_{j=1}^{m}(y^{l}_{i-1,j}-y^{l+1}_{i-1,j}),&i>1\\\ \end{cases}$
$\displaystyle\forall i\in[n],l\in[k]$ (8d) $\displaystyle y^{l}_{ij}\geq 0$
$\displaystyle\forall i\in[n],j\in[m],l\in[k]$ (8e)

Before trying to interpret the LP (8), we notice the following structure. An
optimal solution will always saturate constraints (8c) for better types $j$
before setting $y^{l}_{ij^{\prime}}>0$ for types $j^{\prime}>j$. This allows
us to reformulate the LP using collapsed variables
$y^{l}_{i}=\sum_{j}y^{l}_{ij}$, as formalized below.

######  Lemma 2.11 (Dual Simplification)

LP (8) has the same optimal value as the following LP.

$\displaystyle\max\ $ $\displaystyle\theta$ (9a) $\displaystyle\mathrm{s.t.\ \
}$ $\displaystyle\theta\cdot
Q_{j}\leq\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{y^{l}_{i},G_{ij}x^{l}_{i}\\}$
$\displaystyle\forall j\in[m]$ (9b) $\displaystyle y^{l}_{i}\leq x^{l}_{i}$
$\displaystyle\forall i\in[n],l\in[k]$ (9c) $\displaystyle
x^{l}_{i}=\begin{cases}1,&i=1,l=k\\\ 0,&i=1,l<k\\\
x^{l}_{i-1}-y^{l}_{i-1}+y^{l+1}_{i-1},&i>1\\\ \end{cases}$
$\displaystyle\forall i\in[n],l\in[k]$ (9d) $\displaystyle y^{l}_{i}\geq 0$
$\displaystyle\forall i\in[n],l\in[k]$ (9e)

Lemma 2.11 is proven in Section 7. We refer to (9) as an LP since the non-
linear term $\min\\{y^{l}_{i},G_{ij}x^{l}_{i}\\}$ can easily be represented
using an auxiliary variable and linear constraints.

We note that LP (9) has the following interpretation. Free variable
$x^{l}_{i}$ denotes the probability of having exactly $l$ slots remaining when
agent $i$ arrives, and $y^{l}_{i}$ denotes the (unconditional) probability of
accepting the agent in this state, which must lie in $[0,x^{l}_{i}]$ as
enforced by (8c), (8e). Meanwhile, (8d) correctly updates the state
probabilities $x^{l}_{i}$ based on the acceptance probabilities $y^{l}_{j}$,
which are understood to be 0 if $l=k+1$. Finally,
$\min\\{y^{l}_{i},G_{ij}x^{l}_{i}\\}$ represents the probability of accepting
agent $i$ with type $j$ or better when there are $l$ slots remaining, which is
bottlenecked by $G_{ij}x^{l}_{i}$ (the probability of agent $i$ having type
$j$ or better in state $l$) and $y^{l}_{i}$ (the unconditional probability of
accepting agent $i$ in state $l$). Therefore, constraint (8b) says that the
expected number of agents of type $j$ or better accepted must be at least
$\theta$ in comparison to $Q_{j}$, which is the number of agents of type $j$
or better accepted by the prophet or ex-ante relaxation. The algorithm’s
guarantee is then given by the maximum $\theta$ that can be uniformly achieved
across all types $j$.

We now formalize some more notation and summarize the developments of this
section.

######  Definition 2.12 ($\mathbf{G}$, Simplified Duals for $\mathsf{DP}$)

Let $\mathbf{G}$ denote the collective information about the type
distributions, which includes $m$ and the values of $G_{ij}$ that must satisfy
$G_{i1}\leq\cdots\leq G_{im}=1$ for all $i$. For any such valid $\mathbf{G}$,
let $\mathrm{innerLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}(\mathbf{G})$ (resp.
$\mathrm{innerLP}^{\mathsf{DP}/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$) denote the
LP (9) where $Q_{j}$ is set to
$\mathbb{E}[\min\\{\sum_{i=1}^{n}\mathrm{Ber}(G_{ij}),k\\}]$ (resp.
$\min\\{\sum_{i=1}^{n}G_{ij},k\\}$) for all $j\in[m]$.

######  Theorem 2.13 (Reformulation of Tight Guarantees for $\mathsf{DP}$)

For any fixed $k$ and $n>k$,

$\displaystyle\inf_{I\in\mathcal{I}_{k,n}}\frac{\mathsf{DP}(I)}{\mathsf{Proph}(I)}=\inf_{\mathbf{G}}\
\mathrm{innerLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}(\mathbf{G})\qquad\text{and}\qquad\inf_{I\in\mathcal{I}_{k,n}}\frac{\mathsf{DP}(I)}{\mathsf{ExAnte}(I)}=\inf_{\mathbf{G}}\
\mathrm{innerLP}^{\mathsf{DP}/\mathsf{ExAnte}}_{k,n}(\mathbf{G}).$

Put in words, Theorem 2.13 says that the tight guarantee for the optimal DP
relative to the prophet (resp. ex-ante relaxation) is given by
$\inf_{\mathbf{G}}\
\mathrm{innerLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}(\mathbf{G})$ (resp.
$\inf_{\mathbf{G}}\
\mathrm{innerLP}^{\mathsf{DP}/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$), which are
based on our simplified dual formulation and have reduced the adversary’s
problem to be only over type distributions $\mathbf{G}$. Before delving into
how to solve these problems over $\mathbf{G}$, we develop analogues of Theorem
2.13 in the settings where the algorithm in the primal problem is restricted
to static threshold policies. We note that in the IID special case, there is a
significant further simplification that expresses the adversary’s entire
problem as a single semi-infinite LP, which we derive in Section 4.

###  2.2 General Framework for (Oblivious) Static Threshold Algorithms

When the algorithm is restricted to static threshold policies, we can
similarly formulate an inner primal LP and take its dual to uncover a new
problem that depends on the type distributions but not on the specific
valuations of agents. In fact, a nice distinction emerges in the dual
depending on whether the algorithm must set the static threshold while
oblivious to the specific valuations.

######  Definition 2.14 (Oblivious vs. Non-oblivious Static Thresholds)

For any instance $I$, let $\mathsf{ST}(I)$ denote the expected performance of
the best static threshold policy on $I$, whose parameters $J,\rho$ can be set
knowing instance $I$. By contrast, an oblivious static threshold (OST)
algorithm must set the parameters $J,\rho$ without knowing the specific agent
valuations in the instance (but knowing everything else, including the type
distributions).

The tight guarantee for OST algorithms relative to the prophet (resp. ex-ante
relaxation) is defined by the following sequence of optimizations. First, for
a fixed $k$ and $n$, the adversary sets $\mathbf{G}$, which we recall is
defined by $m$ and $\\{G_{ij}:i\in[n],j\in[m]\\}$. Based on $\mathbf{G}$, the
algorithm fixes the parameters $J,\rho$ of the static threshold policy to be
used. Finally, the adversary sets the valuations, defined by $\Delta_{j}$, to
minimize the policy’s performance relative to $\mathsf{Proph}(I)$ (resp.
$\mathsf{ExAnte}(I)$).

We first focus on tight guarantees for OST algorithms, which are simpler to
capture using our framework. For a fixed $\mathbf{G}$ and parameters $J,\rho$
chosen by the OST, we write the adversary’s inner optimization problem over
$\Delta_{j}$.

######  Definition 2.15 (Inner Problem for Minimizing OST)

Consider the following LP, where coefficient $Q_{j}$ can be set to either
$\mathbb{E}[\min\\{\sum_{i=1}^{n}\mathrm{Ber}(G_{ij}),k\\}]$ or
$\min\\{\sum_{i=1}^{n}G_{ij},k\\}$ like before.

$\displaystyle\min\ $ $\displaystyle V^{k}_{1}$ (10a)
$\displaystyle\mathrm{s.t.\ \ }$ $\displaystyle
V_{i}^{l}=\sum_{j<J}p_{ij}U^{l}_{ij}+p_{iJ}\rho U^{l}_{iJ}+V^{l}_{i+1}$
$\displaystyle\forall i\in[n],l\in[k]$ (10b) $\displaystyle
U^{l}_{ij}=\sum_{j^{\prime}=j}^{m}\Delta_{j^{\prime}}-V^{l}_{i+1}+V^{l-1}_{i+1}$
$\displaystyle\forall i\in[n],j\in[m],l\in[k]$ (10c)
$\displaystyle\sum_{j=1}^{m}Q_{j}\Delta_{j}=1$ (10d)
$\displaystyle\Delta_{j}\geq 0$ $\displaystyle\forall j\in[m]$ (10e)

Compared to the inner LP (7) for the optimal DP algorithm, LP (10) differs in
two ways. First, $U^{l}_{ij}$ is now a free variable that could be negative,
representing the change in utility when agent $i$ takes type $j$ and is
accepted with $l$ slots remaining, as set in (10c). Second, the policy is now
forced to accept an agent with type $j<J$ w.p. 1 and an agent with type $j=J$
w.p. $\rho$, regardless of $l$ and $i$, as reflected in constraints (10b).
This allows the adversary to create a smaller objective value in LP (10),
ultimately yielding a maximization problem for the dual in which the collapsed
variable $y^{l}_{i}$ (from the simplification in Lemma 2.11) must satisfy
essentially the same static threshold rule as defined by $J$ and $\rho$. This
is formalized in the definition and theorem below.

######  Definition 2.16 (Simplified Duals for $\mathsf{OST}$)

For any type distributions $\mathbf{G}$ and static threshold policy $J,\rho$,
let $\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{Proph}}_{k,n}(\mathbf{G})$
(resp.
$\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$)
be identical to LP
$\mathrm{innerLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}(\mathbf{G})$ (resp.
$\mathrm{innerLP}^{\mathsf{DP}/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$), except
with the additional constraints

$\displaystyle y^{l}_{i}$
$\displaystyle=(\sum_{j<J}p_{ij}+p_{iJ}\rho)x^{l}_{i}=((1-\rho)G_{i,J-1}+\rho
G_{iJ})x^{l}_{i}$ $\displaystyle\forall i\in[n],l\in[k].$ (11)

######  Theorem 2.17 (Reformulating the Tight Guarantees for $\mathsf{OST}$)

For any fixed $k$ and $n>k$, the tight guarantee for OST algorithms relative
to the prophet (resp. ex-ante relaxation) is equal to
$\inf_{\mathbf{G}}\sup_{J,\rho}\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{Proph}}_{k,n}(\mathbf{G})$
(resp.
$\inf_{\mathbf{G}}\sup_{J,\rho}\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$).

The proof of Theorem 2.17 is similar to Section 2.1 and deferred to Section 7.

We proceed to study tight guarantees for non-oblivious static thresholds.
Earlier, the way in which the static threshold restriction directly translated
into dual constraint (11) was crucially dependent on the fact that in the
primal LP (10), $J$ and $\rho$ were set before the $\Delta_{j}$’s. We now show
that if $J$ and $\rho$ are decided after the $\Delta_{j}$’s, then this
translates into the dual algorithm being able to employ an arbitrary convex
combination of static threshold rules, which can change the dual objective.
First we formulate the adversary’s inner problem for minimizing
$\mathsf{ST}(I)$, which must set $\Delta_{j}$’s such that the performance of
any static threshold policy defined by $J,\rho$ is poor.

######  Definition 2.18 (Inner Problem for Minimizing $\mathsf{ST}$)

Consider the following LP, where coefficient $Q_{j}$ can be set to either
$\mathbb{E}[\min\\{\sum_{i=1}^{n}\mathrm{Ber}(G_{ij}),k\\}]$ or
$\min\\{\sum_{i=1}^{n}G_{ij},k\\}$ like before.

$\displaystyle\min\ $ $\displaystyle\alpha$ (12a) $\displaystyle\mathrm{s.t.\
\ }$ $\displaystyle
V_{i}^{l}(J,\rho)=\sum_{j<J}p_{ij}U^{l}_{ij}(J,\rho)+p_{iJ}\rho
U^{l}_{iJ}(J,\rho)+V^{l}_{i+1}(J,\rho)$ $\displaystyle\forall
i,l,J\in[m],\rho\in(0,1]$ (12b) $\displaystyle
U^{l}_{ij}(J,\rho)=\sum_{j^{\prime}=j}^{m}\Delta_{j^{\prime}}-V^{l}_{i+1}(J,\rho)+V^{l-1}_{i+1}(J,\rho)$
$\displaystyle\forall i,j,l,J\in[m],\rho\in(0,1]$ (12c)
$\displaystyle\alpha\geq V^{k}_{1}(J,\rho)$ $\displaystyle\forall
J\in[m],\rho\in(0,1]$ (12d) $\displaystyle\sum_{j=1}^{m}Q_{j}\Delta_{j}=1$
(12e) $\displaystyle\Delta_{j}\geq 0$ $\displaystyle\forall j\in[m]$ (12f)

We note that LP (12) is similar to LP (10), except a copy of the variables has
been created for every possible static threshold $J,\rho$, all of which must
perform no better than $\alpha$. The simplified dual formulation corresponding
to LP (12) will be easier to write using the following additional notation.

######  Definition 2.19 ($\mathbf{x},\mathbf{y},\mathcal{P}^{k}_{n}$)

Let
$\mathbf{x}:=(x^{l}_{i})_{i\in[n],l\in[k]},\mathbf{y}:=(y^{l}_{i})_{i\in[n],l\in[k]}$,
and let $\mathcal{P}^{k}_{n}$ denote the set of vectors
$(\mathbf{x},\mathbf{y})$ that satisfy the simplified dual problem’s state-
updating constraints (9c)–(9e).

######  Definition 2.20 (Simplified Duals for $\mathsf{ST}$)

For any $\mathbf{G}$, let
$\mathrm{innerLP}^{\mathsf{ST}/\mathsf{Proph}}_{k,n}(\mathbf{G})$ (resp.
$\mathrm{innerLP}^{\mathsf{ST}/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$) denote the
following LP, with coefficient $Q_{j}$ set to
$\mathbb{E}[\min\\{\sum_{i=1}^{n}\mathrm{Ber}(G_{ij}),k\\}]$ (resp.
$\min\\{\sum_{i=1}^{n}G_{ij},k\\}$) for all $j\in[m]$.

$\displaystyle\max\ $ $\displaystyle\theta$ (13a) $\displaystyle\mathrm{s.t.\
\ }$ $\displaystyle\theta\cdot
Q_{j}\leq\int_{J,\rho}\mu(J,\rho)\left(\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{y^{l}_{i}(J,\rho),G_{ij}x^{l}_{i}(J,\rho)\\}\right)$
$\displaystyle\forall j\in[m]$ (13b) $\displaystyle
y^{l}_{i}(J,\rho)=((1-\rho)G_{i,J-1}+\rho G_{iJ})x^{l}_{i}(J,\rho)$
$\displaystyle\forall i,l,J\in[m],\rho\in(0,1]$ (13c)
$\displaystyle(\mathbf{x}(J,\rho),\mathbf{y}(J,\rho))\in\mathcal{P}^{k}_{n}$
$\displaystyle\forall J\in[m],\rho\in(0,1]$ (13d)
$\displaystyle\int_{J,\rho}\mu(J,\rho)=1$ (13e) $\displaystyle\mu(J,\rho)\geq
0$ $\displaystyle\forall J\in[m],\rho\in(0,1]$ (13f)

We note that there is no benefit for the primal algorithm using a convex
combination of static thresholds (its expectation is maximized by choosing the
best one), but since the dual problem has to uniformly cover each type $j$,
there can be a benefit.

######  Theorem 2.21 (Reformulating the Tight Guarantees for $\mathsf{ST}$)

For any fixed $k$ and $n>k$,

$\displaystyle\inf_{I\in\mathcal{I}_{k,n}}\frac{\mathsf{ST}(I)}{\mathsf{Proph}(I)}=\inf_{\mathbf{G}}\
\mathrm{innerLP}^{\mathsf{ST}/\mathsf{Proph}}_{k,n}(\mathbf{G})\qquad\text{and}\qquad\inf_{I\in\mathcal{I}_{k,n}}\frac{\mathsf{ST}(I)}{\mathsf{ExAnte}(I)}=\inf_{\mathbf{G}}\
\mathrm{innerLP}^{\mathsf{ST}/\mathsf{ExAnte}}_{k,n}(\mathbf{G}).$

The proof of Theorem 2.21 is similar to Section 2.1 and also deferred to
Section 7.

##  3 General Framework applied to the Non-IID Setting

In this section we study tight guarantees over general non-IID instances,
starting with those for the optimal DP. Recall that for any number of slots
$k$ and agents $n>k$, we have established in Theorem 2.13 that the tight
guarantees relative to the prophet and ex-ante relaxation are given by
$\inf_{\mathbf{G}}\mathrm{innerLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}(\mathbf{G})$
and
$\inf_{\mathbf{G}}\mathrm{innerLP}^{\mathsf{DP}/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$
respectively. As a recap,by using the notation from Definition 2.19 that
treats $\mathbf{x},\mathbf{y}$ as vectors,
$\mathrm{innerLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}(\mathbf{G})$ can be
rewritten as

$\displaystyle\mathrm{innerLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}(\mathbf{G})=$
$\displaystyle\max$ $\displaystyle\theta$ (14a) $\displaystyle\mathrm{s.t.\ }$
$\displaystyle\theta\cdot\mathbb{E}[\min\\{\sum_{i=1}^{n}\mathrm{Ber}(G_{ij}),k\\}]\leq\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{y^{l}_{i},G_{ij}x^{l}_{i}\\}\
\ \forall j\in[m]$ (14c)
$\displaystyle(\mathbf{x},\mathbf{y})\in\mathcal{P}^{k}_{n},$

and $\mathrm{innerLP}^{\mathsf{DP}/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$ can be
rewritten as

$\displaystyle\mathrm{innerLP}^{\mathsf{DP}/\mathsf{ExAnte}}_{k,n}(\mathbf{G})=$
$\displaystyle\max$ $\displaystyle\theta$ (15a) $\displaystyle\mathrm{s.t.\ }$
$\displaystyle\theta\cdot\min\\{\sum_{i=1}^{n}G_{ij},k\\}\leq\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{y^{l}_{i},G_{ij}x^{l}_{i}\\}\
\ \forall j\in[m]$ (15c)
$\displaystyle(\mathbf{x},\mathbf{y})\in\mathcal{P}^{k}_{n}$

###  3.1 $\mathsf{DP}/\mathsf{ExAnte}$ in Non-IID Setting

In general non-IID setting, we obtain the following result regarding
$\mathsf{DP}/\mathsf{ExAnte}$.

###### Theorem 3.1

$\inf_{\mathbf{G}}\
\mathrm{innerLP}^{\mathsf{DP}/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$ is equal to
the optimal objective value of the following problem:

$\displaystyle\inf_{\begin{subarray}{c}\sum_{i\in[n]}g_{i}\leq k\\\ 1\geq
g_{i}\geq 0\ \forall i\end{subarray}}\ \ \ \ $ $\displaystyle\max\ \theta$
(16a) $\displaystyle\mathrm{s.t.\ }$ $\displaystyle\theta\cdot
g_{i}\leq\sum_{l=1}^{k}\min\\{y^{l}_{i},g_{i}x^{l}_{i}\\}\quad\forall i\in[n]$
(16c) $\displaystyle(\mathbf{x},\mathbf{y})\in\mathcal{P}^{k}_{n}$

The proof is deferred to Section 8. The result derived in Theorem 3.1 has a
nice interpretation. The variable $g_{i}$ for each $i\in[n]$ can be
interpreted as the marginal probability that agent $i$ got accepted in the ex-
ante relaxation. Denote by $\theta^{*}$ the optimal value of LP (16) after
taking minimum over $\mathbf{g}=(g_{1},\ldots,g_{n})$. Denote by
$\\{\theta^{*},\mathbf{x}_{\mathbf{g}},\mathbf{y}_{\mathbf{g}}\\}$ a feasible
solution to LP (16) for a fixed $\mathbf{g}$, where the value of
$(\mathbf{x}_{\mathbf{g}},\mathbf{y}_{\mathbf{g}})$ depends on $\mathbf{g}$.
Then constraint (16c) implies that each agent $i$ got accepted by the policy
specified by $(\mathbf{x}_{\mathbf{g}},\mathbf{y}_{\mathbf{g}})$ with a
probability at least $\theta^{*}$ conditional on being accepted in the ex-ante
relaxation, for any $\mathbf{g}$. Such an implication corresponds to the
definition of $\theta^{*}$-balancedness online contention resolution scheme
(OCRS) in Feldman et al. (2021). Thus, Theorem 3.1 implies that an OCRS
achieves the tight guarantee of the $\mathsf{DP}$ policy, with respect to the
ex-ante relaxation. Note that this point has been previously proved in Jiang
et al. (2022). Here, we prove the same result in an alternative way by
exploiting the structures of our LP framework $\inf_{\mathbf{G}}\
\mathrm{innerLP}^{\mathsf{DP}/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$.

###  3.2 Optimal Oblivious Static Thresholds in Non-IID Setting

Recall that for any fixed $k$ and $n>k$, we have established in Theorem 2.17
that the tight guarantees for OST algorithms relative to the prophet and ex-
ante relaxation are given by
$\inf_{\mathbf{G}}\sup_{J,\rho}\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{Proph}}_{k,n}(\mathbf{G})$
and
$\inf_{\mathbf{G}}\sup_{J,\rho}\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$
respectively, where the inner LP’s correspond to (14) and (15) respectively
but both have the added constraints

$\displaystyle y^{l}_{i}$ $\displaystyle=((1-\rho)G_{i,J-1}+\rho
G_{iJ})x^{l}_{i}$ $\displaystyle\forall i\in[n],l\in[k].$ (17)

The inner LP’s for OST’s are substantially easier to analyze because under
constraints (17), the RHS that is common to (14c) and (15c) can be rewritten
as

$\displaystyle\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{y^{l}_{i},G_{ij}x^{l}_{i}\\}=\sum_{i=1}^{n}\min\\{((1-\rho)G_{i,J-1}+\rho
G_{iJ}),G_{ij}\\}\sum_{l=1}^{k}x^{l}_{i},$ (18)

where term $\min\\{((1-\rho)G_{i,J-1}+\rho G_{iJ}),G_{ij}\\}$ for each agent
$i$ depends on the choices of $J,\rho$ but not on the number of remaining
slots $l$. Moreover, we have the following relationships.

###### Lemma 3.2

Fix an OST $J,\rho$ and define $\tau_{i}=(1-\rho)G_{i,J-1}+\rho G_{i,J}$ for
all $i\in[n]$. Suppose vectors $\mathbf{x},\mathbf{y}$ satisfy (17), i.e.
$y^{l}_{i}=\tau_{i}x^{l}_{i}$ for all $i$ and $l$, as well as
$(\mathbf{x},\mathbf{y})\in\mathcal{P}^{k}_{n}$. Then for all $i\in[n]$, we
have

$\displaystyle\sum_{l=1}^{k}x^{l}_{i}=\Pr[\sum_{i^{\prime}<i}\mathrm{Ber}(\tau_{i^{\prime}})<k]\qquad\text{and}\qquad\sum_{i^{\prime}=1}^{i}\tau_{i^{\prime}}\sum_{l=1}^{k}x^{l}_{i^{\prime}}=\mathbb{E}[\min\\{\sum_{i^{\prime}=1}^{i}\mathrm{Ber}(\tau_{i^{\prime}}),k\\}].$

Lemma 3.2 is formally proven in Section 8, but natural under the
interpretation that $x^{l}_{i}$ denotes the probability of having exactly $l$
slots remaining when agent $i$ arrives. Note that each agent $i$ “clears the
bar” for acceptance independently with probability $\tau_{i}$. An agent $i$ is
accepted if and only if they clear the bar and there is at least 1 slot
remaining when they arrive, with the latter probability given by
$\sum_{l=1}^{k}x^{l}_{i}$. The second part of Lemma 3.2 then follows because
the number of agents accepted among $i^{\prime}=1,\ldots,i$ is equal to the
number of them who clear the bar, truncated by $k$. Meanwhile, the first part
of Lemma 3.2 follows because there is a slot remaining for agent $i$ if and
only if the number of previous agents $i^{\prime}<i$ who cleared the bar is
less than $k$.

Equipped with Lemma 3.2, we are now ready to prove our result that the tight
guarantees for OST algorithms relative to the stronger ex-ante benchmark are
no worse than relative to the prophet. We first show a lower bound of
$\mathsf{OST}/\mathsf{ExAnte}$ in the following lemma.

###### Lemma 3.3

For any type distributions $\mathbf{G}$ and static threshold policy $J,\rho$,
we have

$\displaystyle\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$
$\displaystyle\geq$
$\displaystyle\min\left\\{\Pr\left[\sum_{i<n}\mathrm{Ber}((1-\rho)G_{i,J-1}+\rho
G_{iJ})<k\right],\frac{\mathbb{E}[\min\\{\sum_{i<n}\mathrm{Ber}((1-\rho)G_{i,J-1}+\rho
G_{iJ}),k\\}]}{k}\right\\}.$

We then show an upper bound of $\mathsf{OST}/\mathsf{Proph}$ in the following
lemma, which matches the lower bound established in Lemma 3.3.

###### Lemma 3.4

For any fixed type distributions $\mathbf{G}$, the value of
$\inf_{\mathbf{G}^{\prime}}\sup_{J,\rho}\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{Proph}}_{k,n}(\mathbf{G}^{\prime})$
can be at most

$\sup_{J,\rho}\
\min\left\\{\Pr\left[\sum_{i<n}\mathrm{Ber}((1-\rho)G_{i,J-1}+\rho
G_{iJ})<k\right],\frac{\mathbb{E}[\min\\{\sum_{i<n}\mathrm{Ber}((1-\rho)G_{i,J-1}+\rho
G_{iJ}),k\\}]}{k}\right\\}.$ (19)

Note that the ex-ante benchmark is a stronger benchmark than the prophet.
Combining Lemma 3.3 and Lemma 3.4, we have the following result.

###### Theorem 3.5

For any fixed $k$ and $n$,

$\displaystyle\inf_{\mathbf{G}}\sup_{J,\rho}\
\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{Proph}}_{k,n}(\mathbf{G})=\inf_{\mathbf{G}}\sup_{J,\rho}\
\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$
(20) $\displaystyle=$ $\displaystyle\inf_{\mathbf{G}}\sup_{J,\rho}\
\min\left\\{\Pr\left[\sum_{i<n}\mathrm{Ber}((1-\rho)G_{i,J-1}+\rho
G_{iJ})<k\right],\frac{\mathbb{E}[\min\\{\sum_{i<n}\mathrm{Ber}((1-\rho)G_{i,J-1}+\rho
G_{iJ}),k\\}]}{k}\right\\}.$

The formal proofs of Lemma 3.3, Lemma 3.4 and Theorem 3.5 are referred to
Section 8.

It is direct to see that for the formula in (20), the first term in the min
operator is decreasing over the threshold $J,\rho$, while the second term in
the min operator is increasing over the threshold $J,\rho$. Thus, in order to
achieve the supremum, the two terms within the min operator must be
equivalent, which yields the following result.

###### Corollary 3.6

For any number of slots $k$ and agents $n>k$, the best-possible guarantees for
OST algorithms relative to the prophet or ex-ante relaxation are identically
equal to

$\displaystyle\min\ \alpha$ (21a) $\displaystyle\mathrm{s.t.\ }\alpha$
$\displaystyle=\Pr\left[\sum_{i=1}^{n-1}\mathrm{Ber}(q_{i})<k\right]=\frac{\mathbb{E}[\min\\{\sum_{i=1}^{n-1}\mathrm{Ber}(q_{i}),k\\}]}{k}$
(21b) $\displaystyle q_{i}$ $\displaystyle\in[0,1]\quad\forall i\in[n-1]$
(21c)

Chawla et al. (2020) show that for a fixed $k$, the infimum value of problem
(21) over $n>k$ occurs as $n\to\infty$, and is equal to
$\Pr[\mathrm{Pois}(\lambda)<k]=\frac{\mathbb{E}[\min\\{\mathrm{Pois}(\lambda),k\\}]}{k}$,
where $\lambda$ is the unique real number that makes these quantities
identical. They also show how to achieve this guarantee using an oblivious
static threshold algorithm. Our framework shows that their guarantees are
tight, regardless of whether one is comparing to the prophet or ex-ante
relaxation, and moreover never required explicitly computing its value or
constructing a family of counterexamples to establish a matching upper bound!
We further show that the infimum value of problem (21) over $n>k$ grows at the
order of $1-\Theta(\sqrt{\log k/k})$, establishing the tight order dependence
on $k$ for the error term of static threshold policies.

###### Proposition 3.7

For any integer $k$, let $\lambda_{k}$ be the solution to the equation

$\Pr[\mathrm{Pois}(\lambda_{k})<k]=\frac{\mathbb{E}[\min\\{\mathrm{Pois}(\lambda_{k}),k\\}]}{k}.$

Then, it holds that

$\Pr[\mathrm{Pois}(\lambda_{k})<k]=\frac{\mathbb{E}[\min\\{\mathrm{Pois}(\lambda_{k}),k\\}]}{k}=1-\Theta(\sqrt{\log
k/k}).$

###  3.3 Oblivious vs. Non-oblivious Static Thresholds in Non-IID Setting

We further study the performances of oblivious static threshold policies
versus general non-oblivious static threshold policies in the non-IID setting.
We first show that there exists an instance $\mathbf{G}$ such that
$\mathsf{ST}$ performs better than $\mathsf{OST}$, with respect to both the
ex-ante benchmark and the prophet.

###### Lemma 3.8

There exists an instance $\mathbf{G}$ such that

$\mathrm{innerLP}^{\mathsf{ST}/\mathsf{Proph}}_{k,n}(\mathbf{G})>\sup_{J,\rho}\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{Proph}}_{k,n}(\mathbf{G})$

and

$\mathrm{innerLP}^{\mathsf{ST}/\mathsf{ExAnte}}_{k,n}(\mathbf{G})>\sup_{J,\rho}\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$

The proof is referred to Section 8. Note that in the proof of Lemma 3.8, we
construct an instance where there are two agents, $n=2$, four types, $m=4$,
and one slot, $k=1$. The distribution for the first agent is given by
$\mathbf{G}_{1}=(0,\frac{1}{2},\frac{1}{2},1)$, and the distribution for the
second agent is given by $\mathbf{G}_{2}=(\varepsilon,\varepsilon,1,1)$, for
some $\varepsilon\rightarrow 0$. For this instance, we show that
$\mathsf{ST}/\mathsf{Proph}$ and $\mathsf{ST}/\mathsf{ExAnte}$ achieve the
value of $2/3$, while the values for $\mathsf{OST}/\mathsf{Proph}$ and
$\mathsf{OST}/\mathsf{ExAnte}$ are no greater than $1/2$.

Therefore the method of Chawla et al. (2020) is not instance-optimal. However,
we now show that it is optimal in the worst case, hence their bound is tight
even for the more powerful class of ST policies. First we need the following
analogue of Lemma 3.4 for non-oblivious static thresholds.

###### Lemma 3.9

For any fixed type distributions $\mathbf{G}$, the value of
$\inf_{\mathbf{G}^{\prime}}\mathrm{innerLP}^{\mathsf{ST}/\mathsf{Proph}}_{k,n}(\mathbf{G}^{\prime})$
can be at most the supremum of

$\displaystyle\min\left\\{\int_{J,\rho}\Pr\left[\sum_{i<n}\mathrm{Ber}((1-\rho)G_{i,J-1}+\rho
G_{iJ})<k\right]\mu(J,\rho),\int_{J,\rho}\frac{\mathbb{E}[\min\\{\sum_{i<n}\mathrm{Ber}((1-\rho)G_{i,J-1}+\rho
G_{iJ}),k\\}]}{k}\mu(J,\rho)\right\\}$

over all measures $\mu$ over $J\in[m]$ and $\rho\in(0,1]$.

The proof is deferred to Section 8.

In Theorem 3.5, we have shown that both the quantities
$\inf_{\mathbf{G}}\sup_{J,\rho}\
\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{Proph}}_{k,n}(\mathbf{G})$ and
$\inf_{\mathbf{G}}\sup_{J,\rho}\
\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$ are
identical to the quantity

$\displaystyle\inf_{\mathbf{G}}\sup_{J,\rho}\
\min\left\\{\Pr\left[\sum_{i<n}\mathrm{Ber}((1-\rho)G_{i,J-1}+\rho
G_{iJ})<k\right],\frac{\mathbb{E}[\min\\{\sum_{i<n}\mathrm{Ber}((1-\rho)G_{i,J-1}+\rho
G_{iJ}),k\\}]}{k}\right\\}.$ (22)

The results in Chawla et al. (2020) imply that this infimum is in fact
achieved in the simple case where there is only $m=1$ type and $G_{i1}=1$ for
all $i$, in which case (22) reduces to

$\displaystyle\sup_{\rho\in(0,1]}\min\left\\{\Pr\left[\mathrm{Bin}(n-1,\rho)<k\right],\frac{\mathbb{E}[\min\\{\mathrm{Bin}(n-1,\rho),k\\}]}{k}\right\\}.$
(23)

We now show that
$\inf_{\mathbf{G}}\mathrm{innerLP}^{\mathsf{ST}/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$
cannot do any better, because even the larger quantity from Lemma 3.9, which
on this one-type instance reduces to

$\displaystyle\sup_{\mu:(0,1]\to\mathbb{R}_{\geq
0},\int_{\rho}\mu(\rho)=1}\min\left\\{\int_{\rho}\Pr\left[\mathrm{Bin}(n-1,\rho)<k\right]\mu(\rho),\int_{\rho}\frac{\mathbb{E}[\min\\{\mathrm{Bin}(n-1,\rho),k\\}]}{k}\mu(\rho)\right\\},$
(24)

is actually no larger than (23). The above arguments are formalized in the
following theorem, where the proof is deferred to Section 8.

###### Theorem 3.10

For any fixed $n$ and $k$, it holds that

$\displaystyle\inf_{\mathbf{G}}\
\mathrm{innerLP}^{\mathsf{ST}/\mathsf{Proph}}_{k,n}(\mathbf{G})=\inf_{\mathbf{G}}\
\mathrm{innerLP}^{\mathsf{ST}/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$
$\displaystyle=$ $\displaystyle\inf_{\mathbf{G}}\sup_{J,\rho}\
\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{Proph}}_{k,n}(\mathbf{G})=\inf_{\mathbf{G}}\sup_{J,\rho}\
\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{ExAnte}}_{k,n}(\mathbf{G}).$

##  4 Further Simplified General Framework, applied to the IID Setting

In this section we study tight guarantees for DP/OST/ST algorithms relative to
the prophet/ex-ante relaxation, under the restriction that the type
distributions $\mathbf{G}$ must be IID. That is, for each type $j\in[m]$, it
is imposed that $G_{ij}$ is identically equal to some value $G_{j}$ across all
agents $i\in[n]$.

When this is the case, the key dual constraints from Section 3 that compare to
the prophet, e.g. (14c) in
$\mathrm{innerLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}(\mathbf{G})$, can be
rewritten as

$\displaystyle\theta\cdot\mathbb{E}[\min\\{\sum_{i=1}^{n}\mathrm{Ber}(G_{j}),k\\}]$
$\displaystyle\leq\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{y^{l}_{i},G_{j}x^{l}_{i}\\}$
$\displaystyle\forall j\in[m].$ (25)

where the values $G_{j}$ no longer depend on $i$. Consequently, these
constraints will always be hardest to satisfy when the IID type distribution
becomes infinitely granular, i.e. $G_{j}=j/m$ for all $j\in[m]$ with
$m\to\infty$, simply because there are more constraints. The overall problem
of interest,
$\inf_{\mathbf{G}}\mathrm{innerLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}(\mathbf{G})$,
can then have its outer optimization problem dropped, since the infimum always
arises at the infinitely-granular $\mathbf{G}$. This leads to a drastic
reduction where the tight guarantees are now described by a single semi-
infinite LP, as formalized below. We note that the same reduction can be made
for the dual constraints from before that compare to the ex-ante relaxation:

$\displaystyle\theta\cdot\min\\{\sum_{i=1}^{n}G_{j},k\\}$
$\displaystyle\leq\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{y^{l}_{i},G_{j}x^{l}_{i}\\}$
$\displaystyle\forall j\in[m].$ (26)

######  Definition 4.1 (Semi-infinite LP’s for $\mathsf{DP}$ in IID Setting)

Let $\mathrm{Bin}(n,q)$ denote a Binomial random variable with $n$ independent
trials of success probability $q$. Consider the semi-infinite families of
constraints

$\displaystyle\theta\cdot\mathbb{E}[\min\\{\mathrm{Bin}(n,q),k\\}]$
$\displaystyle\leq\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{y^{l}_{i},qx^{l}_{i}\\}$
$\displaystyle\forall q\in(0,1]$ (27) $\displaystyle\theta\cdot\min\\{nq,k\\}$
$\displaystyle\leq\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{y^{l}_{i},qx^{l}_{i}\\}$
$\displaystyle\forall q\in(0,1]$ (28)

which correspond to the limiting cases of (25) and (26) as $G_{j}=j/m=q$ and
$m\to\infty$. Then for any $k$ and $n>k$, let
$\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}$ (resp.
$\mathrm{iidLP}^{\mathsf{DP}/\mathsf{ExAnte}}_{k,n}$) denote the semi-infinite
LP defined by: maximize $\theta$, subject to constraints (27) (resp. (28)) and
$(\mathbf{x},\mathbf{y})\in\mathcal{P}^{k}_{n}$.

Static threshold policies $J,\rho$ also simplify nicely in this semi-infinite
dual problem in the IID setting. Namely, the previous dual constraints (17)
for a static threshold policy, $y^{l}_{i}=((1-\rho)G_{i,J-1}+\rho
G_{iJ})x^{l}_{i}$, by setting $\tau=(1-\rho)G_{i,J-1}+\rho G_{iJ}$ which is
identical across $i$, can be reduced to

$y^{l}_{i}=\tau x^{l}_{i}\quad\forall i\in[n],l\in[k]$ (29)

Note that $\tau\in(0,1]$ is a single number in the IID setting; we no longer
need an index $J\in[m]$ combined with a tiebreak probability $\rho\in(0,1]$.

######  Definition 4.2 (Semi-infinite LP’s for $\mathsf{OST}$ in IID Setting)

For any $k$, $n>k$, and fixed static threshold policy defined by $\tau$, let
$\mathrm{iidLP}^{\mathsf{OST}(\tau)/\mathsf{Proph}}_{k,n}$ (resp.
$\mathrm{iidLP}^{\mathsf{OST}(\tau)/\mathsf{ExAnte}}_{k,n}$) denote the semi-
infinite LP defined by: maximize $\theta$, subject to (27) (resp. (28)),
constraints (29) for a static threshold policy in the IID setting, and
$(\mathbf{x},\mathbf{y})\in\mathcal{P}^{k}_{n}$.

Finally, for non-oblivious static thresholds, we define the analogue of (13)
for the IID setting.

######  Definition 4.3 ($\mathsf{ST}$ in IID Setting)

For any $k$ and $n>k$, let $\mathrm{iidLP}^{\mathsf{ST}/\mathsf{Proph}}_{k,n}$
(resp. $\mathrm{iidLP}^{\mathsf{ST}/\mathsf{ExAnte}}_{k,n}$) denote the
following optimization problem, when
$Q(q)=\mathbb{E}[\min\\{\mathrm{Bin}(n,q),k\\}]$ (resp. $Q(q)=\min\\{nq,k\\}$)
for all $q\in(0,1]$.

$\displaystyle\max\ $ $\displaystyle\theta$ (30a) $\displaystyle\mathrm{s.t.\
\ }$ $\displaystyle\theta\cdot
Q(q)\leq\int_{\tau\in(0,1]}\mu(\tau)\left(\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{y^{l}_{i}(\tau),qx^{l}_{i}(\tau)\\}\right)$
$\displaystyle\forall q\in(0,1]$ (30b) $\displaystyle y^{l}_{i}(\tau)=\tau
x^{l}_{i}(\tau)$ $\displaystyle\forall i\in[n],l\in[k],\tau\in(0,1]$ (30c)
$\displaystyle(\mathbf{x}(\tau),\mathbf{y}(\tau))\in\mathcal{P}^{k}_{n}$
$\displaystyle\forall\tau\in(0,1]$ (30d)
$\displaystyle\int_{\tau\in(0,1]}\mu(\tau)=1$ (30e)
$\displaystyle\mu(\tau)\geq 0$ $\displaystyle\forall\tau\in(0,1]$ (30f)

We now formalize that all of these are the correct formulations, which compute
tight guarantees for DP/OST/ST algorithms relative to the prophet/ex-ante
relaxation in the IID special case.

######  Theorem 4.4 (Reformulations in IID Setting)

For any $k$ and $n>k$, when type distributions $\mathbf{G}$ are constrained to
be IID, the adversary’s optimization problems over $\mathbf{G}$ can be
reformulated as

$\displaystyle\inf_{\mathbf{G}:G_{1j}=\cdots=G_{nj}\forall
j}\mathrm{innerLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}(\mathbf{G})$
$\displaystyle=\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}$
$\displaystyle\inf_{\mathbf{G}:G_{1j}=\cdots=G_{nj}\forall
j}\mathrm{innerLP}^{\mathsf{DP}/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$
$\displaystyle=\mathrm{iidLP}^{\mathsf{DP}/\mathsf{ExAnte}}_{k,n}$
$\displaystyle\inf_{\mathbf{G}:G_{1j}=\cdots=G_{nj}\forall j}\sup_{J,\rho}\
\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{Proph}}_{k,n}(\mathbf{G})$
$\displaystyle=\sup_{\tau}\
\mathrm{innerLP}^{\mathsf{OST}(\tau)/\mathsf{Proph}}_{k,n}$
$\displaystyle\inf_{\mathbf{G}:G_{1j}=\cdots=G_{nj}\forall j}\sup_{J,\rho}\
\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$
$\displaystyle=\sup_{\tau}\
\mathrm{innerLP}^{\mathsf{OST}(\tau)/\mathsf{ExAnte}}_{k,n}$
$\displaystyle\inf_{\mathbf{G}:G_{1j}=\cdots=G_{nj}\forall
j}\mathrm{innerLP}^{\mathsf{ST}/\mathsf{Proph}}_{k,n}(\mathbf{G})$
$\displaystyle=\mathrm{iidLP}^{\mathsf{ST}/\mathsf{Proph}}_{k,n}$
$\displaystyle\inf_{\mathbf{G}:G_{1j}=\cdots=G_{nj}\forall
j}\mathrm{innerLP}^{\mathsf{ST}/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$
$\displaystyle=\mathrm{iidLP}^{\mathsf{ST}/\mathsf{ExAnte}}_{k,n}$

Theorem 4.4 is proven in Section 9.

###  4.1 Equivalence of $\mathsf{DP}/\mathsf{ExAnte}$,
$\mathsf{OST}/\mathsf{Proph}$, and $\mathsf{OST}/\mathsf{ExAnte}$ in IID
Setting

Similar to before, OST’s are easier to analyze because under constraints (29),
the RHS that is common to (27) and (28) can be rewritten as

$\displaystyle\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{y^{l}_{i},qx^{l}_{i}\\}=\min\\{\tau,q\\}\sum_{i=1}^{n}\sum_{l=1}^{k}x^{l}_{i},$
(31)

where now term $\min\\{\tau,q\\}$ depends only on the choice of $\tau$ and not
on agent $i$ nor the number of remaining slots $l$. Moreover, the analogues of
the relationships in Lemma 3.2 are that assuming $y^{l}_{i}=\tau x^{l}_{i}$
for all $i$ and $l$, for all $i\in[n]$, we have

$\displaystyle\sum_{l=1}^{k}x^{l}_{i}=\Pr[\mathrm{Bin}(i-1,\tau)<k]\qquad\text{and}\qquad\tau\sum_{i^{\prime}=1}^{i}\sum_{l=1}^{k}x^{l}_{i^{\prime}}=\mathbb{E}[\min\\{\mathrm{Bin}(i,\tau),k\\}].$
(32)

This allows us to prove the following theorem in Section 9. Although this
result is well-known in the literature, as explained in Section 1.1, we
emphasize that our framework simultaneously obtain both the lower bound and
the upper bound of the ratios, without explicitly constructing a
counterexample to show the upper bound and constructing a policy to show the
lower bound.

###### Theorem 4.5

For any fixed $k$ and $n$,

$\displaystyle\mathrm{iidLP}^{\mathsf{DP}/\mathsf{ExAnte}}_{k,n}=\sup_{\tau}\
\mathrm{iidLP}^{\mathsf{OST}(\tau)/\mathsf{Proph}}_{k,n}=\sup_{\tau}\
\mathrm{iidLP}^{\mathsf{OST}(\tau)/\mathsf{ExAnte}}_{k,n}=\frac{\mathbb{E}[\min\\{\mathrm{Bin}(n,k/n),k\\}]}{k}.$

###  4.2 Equivalence of Oblivious and Non-oblivious Static Thresholds in IID
Setting

We now show that even the best static threshold performance $\mathsf{ST}(I)$
knowing the full instance $I$ cannot beat the quantities in Theorem 4.5. In
fact, we prove a stronger result which was not true in the non-IID setting
(Section 3.2)—$\mathsf{ST}(I)$ is no better than oblivious static thresholds
on any instance.

To prove this fact, we show that in the $\mathsf{ST}$ dual problem (30), one
never benefits from using a convex combination of thresholds instead of a
single threshold. It suffices to show that given any two thresholds
$\underline{\tau},\overline{\tau}$ with $\underline{\tau}<\overline{\tau}$,
there exists a $\tau$ lying between them which contributes more to the RHS of
(30b) than the average of $\underline{\tau}$ and $\overline{\tau}$,
simultaneously for every $q\in(0,1]$. This is formalized in the theorem below.

###### Theorem 4.6

Given any $\underline{\tau},\overline{\tau}$ with
$\underline{\tau}<\overline{\tau}$, there exists a
$\tau\in[\underline{\tau},\overline{\tau}]$ such that

$\displaystyle\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{y^{l}_{i}(\tau),qx^{l}_{i}(\tau)\\}$
$\displaystyle\geq\frac{1}{2}\left(\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{y^{l}_{i}(\underline{\tau}),qx^{l}_{i}(\underline{\tau})\\}+\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{y^{l}_{i}(\overline{\tau}),qx^{l}_{i}(\overline{\tau})\\}\right)$
$\displaystyle\forall q\in(0,1].$ (33)

Theorem 4.6 is proven in Section 9. The main idea involves setting $\tau$ so
that
$\mathbb{E}[\min\\{\mathrm{Bin}(n,\tau),k\\}]=(\mathbb{E}[\min\\{\mathrm{Bin}(n,\underline{\tau}),k\\}]+\mathbb{E}[\min\\{\mathrm{Bin}(n,\overline{\tau}),k\\}])/2$,
and showing through a careful sequence of stochastic comparisons that this
implies

$\displaystyle\sum_{i=1}^{n}\Pr[\mathrm{Bin}(i-1,\tau)<k]\geq\frac{1}{2}\left(\sum_{i=1}^{n}\Pr[\mathrm{Bin}(i-1,\underline{\tau})<k]+\sum_{i=1}^{n}\Pr[\mathrm{Bin}(i-1,\overline{\tau})<k]\right).$
(34)

That is, if $\tau$ is set so that the number of agents accepted is the mean of
that for $\underline{\tau}$ and $\overline{\tau}$, then its average
probability of having a slot available across $i=1,\ldots,n$ can only be
higher than the mean of that for $\underline{\tau}$ and $\overline{\tau}$. We
note that simply setting $\tau=(\underline{\tau}+\overline{\tau})/2$ does not
work, which can be seen through a simple example where $k=1$, $n=3$,
$\underline{\tau}=1/3$, $\overline{\tau}=1$. Then the LHS of (34) when
$\tau=2/3$ is $1+1/3+1/9=13/9$. Meanwhile, the RHS of (34) is
$\frac{(1+2/3+4/9)+1}{2}=14/9$, and hence setting
$\tau=(\underline{\tau}+\overline{\tau})/2$ would not suffice.

Theorem 4.6 shows that when designing the convex combination of thresholds
given by $\mu(\tau)$ in problem (30), if there is mass on two distinct
thresholds $\underline{\tau},\overline{\tau}$, then it is always better to
move them to be a single mass at some intermediate threshold. This means that
ultimately it is better to place all the mass at one point, leading to the
following corollary.

###### Corollary 4.7

It holds that

$\mathrm{iidLP}^{\mathsf{ST}/\mathsf{Proph}}_{k,n}=\sup_{\tau}\mathrm{iidLP}^{\mathsf{OST}(\tau)/\mathsf{Proph}}_{k,n}$

and

$\mathrm{iidLP}^{\mathsf{ST}/\mathsf{ExAnte}}_{k,n}=\sup_{\tau}\mathrm{iidLP}^{\mathsf{OST}(\tau)/\mathsf{ExAnte}}_{k,n}.$

We note that the same argument works on a particular instance, defined by the
type distribution given by $\\{G_{j}:j\in[m]\\}$ that is common across agents
(in which case constraints (30b) only need to be checked at the points
$q=G_{j}$ for some $j\in[m]$). Therefore, OST’s are instance-optimal for
static threshold policies in the IID setting.

###  4.3 $\mathsf{DP}/\mathsf{Proph}$ in IID Setting: a Numerical Procedure
for General $k\geq 1$

We now develop a numerical procedure to compute the guarantee of
$\mathsf{DP}/\mathsf{Proph}$ for each fixed $k$ and $n$, i.e., we compute the
value of $\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}$ for fixed $k$ and
$n$. By letting $n\rightarrow\infty$, we obtain the tight guarantee of
adaptive algorithms for $k$ starting units, and our guarantees for $k>1$
exceed the state-of-the-art from the free-order setting due to Beyhaghi et al.
(2021). Note that $\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}$ enjoys
the following formulation.

$\displaystyle\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}=\max\ \theta$
$\displaystyle\mathrm{s.t.\
}\theta\cdot\mathbb{E}[\min\\{\mathrm{Bin}(n,q),k\\}]$
$\displaystyle\leq\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{y^{l}_{i},qx^{l}_{i}\\}$
$\displaystyle\forall q\in(0,1]$ $\displaystyle(\mathbf{x},\mathbf{y})$
$\displaystyle\in\mathcal{P}^{k}_{n}.$

The main difficulty for obtaining the value of
$\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}$ is that the above
optimization problem is a semi-infinite LP where there are infinite number of
constraints, which is due to the requirement that
$\theta\cdot\mathbb{E}[\min\\{\mathrm{Bin}(n,q),k\\}]\leq\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{y^{l}_{i},qx^{l}_{i}\\}$
needs to be satisfied for any $q\in(0,1]$. We now develop a way to discretize
the interval $(0,1]$ into a finite number of points and we approximate the
value of $\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}$ by solving a
finite-dimensional LP, with promised theoretical guarantees.

To ease notations, we treat $k$ as a fixed value and omit $k$ in our
expression unless otherwise specified. We denote by
$B_{n}(q)=\mathbb{E}[\min\\{\mathrm{Bin}(n,q),k\\}]$ and denote by
$A_{n}(q,\mathbf{x},\mathbf{y})=\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{y^{l}_{i},qx^{l}_{i}\\}$.
For any set of constraints $\mathcal{K}\subseteq(0,1]$, we denote by

$\displaystyle\mathrm{iidLP}_{n}(\mathcal{K}):=\max_{(\mathbf{x},\mathbf{y})\in\mathcal{P}_{n}}\inf_{q\in\mathcal{K}}\frac{A_{n}(q,\mathbf{x},\mathbf{y})}{B_{n}(q)}.$

Our goal is to approximate $\mathrm{iidLP}_{n}((0,1])$ within any additive
error by specifying a $\mathcal{K}\subseteq(0,1]$ that contains a finite
number of elements. In the following lemma, we show how to specify
$\mathcal{K}\subseteq(0,1]$ to achieve this goal.

###### Lemma 4.8

Fix $n$. For any $\varepsilon>0$, let $\mathcal{K}=\\{q_{M},\ldots,q_{1}\\}$
be a discretization of $(0,1]$ with $0<q_{M}<\cdots<q_{1}=1$, satisfying:

  1. 1.

$B_{n}(q_{j+1})\geq(1-\varepsilon)B_{n}(q_{j})$, for all $j\in[M-1]$;

  2. 2.

$\Pr[\mathrm{Pois}(nq_{M})>k]\leq nq_{M}\varepsilon$.

Then it holds

$\mathrm{iidLP}_{n}(\mathcal{K})\geq\mathrm{iidLP}_{n}((0,1])\geq(1-\varepsilon)\mathrm{iidLP}_{n}(\mathcal{K}).$

Therefore, for each $k$ and $n$, we fix the accuracy level $\varepsilon$ and
we obtain the set $\mathcal{K}$ using Lemma 4.8. We approximate
$\mathrm{iidLP}_{n}((0,1])$ within an additive error $\varepsilon$ by solving
the finite-dimensional LP $\mathrm{iidLP}_{n}(\mathcal{K})$. We report the
numerical results for $\mathsf{DP}/\mathsf{Proph}$ in IID setting for general
$k\geq 1$, following the approach described above. For each fixed $k$, we set
$\varepsilon=0.0001$ to approximate the value of
$\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}$, for any $n$. We let
$n\rightarrow\infty$ until the value of
$\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}$ becomes stable, as
illustrated in Figure 1 in Section 6. $n=8000$ appears to suffice for
$k\in\\{1,\ldots,10\\}$. We display these stabilized values as an
approximation of the tight guarantee for each $k\in\\{1,\ldots,10\\}$, below
in Table 1. Our numerical guarantees for $n$ up to $8000$ are significantly
higher than the previous-best bounds.

$k$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
---|---|---|---|---|---|---|---|---|---|---
Numerical guarantee, $n=8000$ | 0.7489 | 0.8417 | 0.8795 | 0.9006 | 0.9143 | 0.9247 | 0.9332 | 0.9393 | 0.9434 | 0.9464
$1-\frac{k^{k}}{k!e^{k}}$ | 0.6321 | 0.7293 | 0.7760 | 0.8046 | 0.8245 | 0.8394 | 0.8510 | 0.8604 | 0.8682 | 0.8749
Beyhaghi et al. (2021) | 0.6543 | 0.7427 | 0.7857 | 0.8125 | 0.8311 | 0.8454 | 0.8567 | 0.8656 | 0.8734 | 0.8807
Table 1: Our approximation of tight guarantees for general $k\geq 1$, when
$n=8000$. We also report the previously best known guarantee
$1-\frac{k^{k}}{k!e^{k}}$ and the guarantees from the free-order setting due
to Beyhaghi et al. (2021).

###  4.4 $\mathsf{DP}/\mathsf{Proph}$ in IID Setting: A Simplified Derivation
of the Tight $\alpha=0.745$ for $k=1$

We now assume $k=1$ and show how our framework can be used to recover the
tight guarantee $0.745$ for the optimal online policy relative to the prophet,
by further exploiting the optimality structure of
$\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{1,n}$. In the following part, we
first derive a relaxation of
$\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{1,n}$, denoted as
$\mathsf{LP}^{\mathsf{relax}}_{n}$, and we obtain an optimal solution of
$\mathsf{LP}^{\mathsf{relax}}_{n}$ with a closed form. We then establish that
the relaxation does not improve the objective value, i.e.
$\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{1,n}=\mathsf{LP}^{\mathsf{relax}}_{n}$
, showing that an optimal solution of $\mathsf{LP}^{\mathsf{relax}}_{n}$ can
be transformed into an optimal solution of
$\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{1,n}$. Finally, based on the
closed form solution of $\mathsf{LP}^{\mathsf{relax}}_{n}$, we show that the
worst case occurs as $n\rightarrow\infty$ and we obtain $0.745$ as the tight
guarantee. We now elaborate on the key techniques in this three-step
derivation, with all proofs of statements relegated to Section 9.

#### First step.

We rewrite $\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{1,n}$ with
superscript $l$ omitted:

$\displaystyle\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{1,n}=$
$\displaystyle\max\ $ $\displaystyle\theta$ (35a) s.t.
$\displaystyle(1-(1-\kappa)^{n})\theta\leq\sum_{i=1}^{n}\min\\{y_{i},\kappa(1-\sum_{i^{\prime}=1}^{i-1}y_{i^{\prime}})\\}\quad\forall\kappa\in(0,1]$
$\displaystyle\sum_{i=1}^{n}y_{i}\leq 1$ $\displaystyle y_{i}\geq
0\quad\forall i\in[n]$

This is a semi-infinite program. The constraint (35) is equivalent to

$\displaystyle(1-(1-\kappa)^{n})\theta$ $\displaystyle\leq\sum_{i\in
S}y_{i}+\kappa\cdot\sum_{i\in[n]\setminus
S}(1-\sum_{i^{\prime}=1}^{i-1}y_{i^{\prime}})\quad\quad\forall\kappa\in[0,1],S\subseteq[n],$
(36)

which can be relaxed to

$(1-(1-\kappa)^{n})\theta\leq\sum_{i=1}^{I}y_{i}+\kappa\sum_{i=I+1}^{n}(1-\sum_{i^{\prime}=1}^{i-1}y_{i^{\prime}})\quad\quad\forall\kappa\in(0,1],I=0,1\ldots,n.$
(37)

We later show that this relaxation does not improve the objective value of
$\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{1,n}$.

Letting $Y_{i}=\sum_{i^{\prime}=1}^{i}y_{i^{\prime}}$ for all $i\in[n]$, we
now consider the optimization problem

$\displaystyle\max\ $ $\displaystyle\theta$ (38a) s.t.
$\displaystyle\max_{\kappa\in(0,1]}\left\\{(1-(1-\kappa)^{n})\theta-\kappa\sum_{i=I}^{n-1}(1-Y_{i})\right\\}\leq
Y_{I}\quad\forall I=0,\ldots,n$ (38c) $\displaystyle Y_{0}\leq 0\leq
Y_{1}\leq\cdots\leq Y_{n}\leq 1.$

Notice that the LHS of (38c) involves solving a concave maximization problem
with $\kappa$ being the decision variable, which has a closed-form solution.
Thus the semi-infinite constraint (38c) can be replaced by an equivalent
nonlinear but finite-dimensional constraint. Thus, we have obtained a finite-
dimensional nonlinear program as a relaxation of
$\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{1,n}$. This discussion is
formalized in Lemma 4.9 below. Its proof, which requires a variable
substitution of the form $z_{I}=\frac{1}{n\theta}\sum_{i=I}^{n-1}(1-Y_{i})$,
is elementary.

######  Lemma 4.9 (Relaxation after Eliminating $\kappa$ and Substituting
Variables)

It holds that
$\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{1,n}\leq\mathsf{LP}^{\mathsf{relax}}_{n}$
where

$\displaystyle\mathsf{LP}^{\mathsf{relax}}_{n}:=$ $\displaystyle\max\ $
$\displaystyle\theta$ $\displaystyle\mathrm{s.t.}$
$\displaystyle(n-1)z_{I}^{n/(n-1)}\leq
nz_{I+1}+\frac{1}{\theta}-1\quad\quad\forall I=0,\ldots,n-1$ $\displaystyle
z_{0}=1,z_{n}=0$ $\displaystyle z_{i}\in[0,1]\quad\quad\forall i\in[n-1].$

The optimization problem in Lemma 4.9 then has the following structured
optimal solution where the $z_{I}$’s are decreasing from $z_{0}=1$ to
$z_{n}=0$.

######  Lemma 4.10 (Closed-Form Solution for
$\mathsf{LP}^{\mathsf{relax}}_{n}$)

Denote $\\{\theta,z_{I}\\}_{I=0}^{n}$ such that $z_{0}=1$, $z_{n}=0$ and

$z_{I+1}=\frac{n-1}{n}z_{I}^{n/(n-1)}-\frac{1}{n\theta}+\frac{1}{n},\leavevmode\nobreak\
\leavevmode\nobreak\ \forall I=0,\ldots,n-1$

Then $\\{\theta,z_{I}\\}_{I=0}^{n}$ is an optimal solution of
$\mathsf{LP}^{\mathsf{relax}}_{n}$.

#### Second step.

We must show that the solution constructed in Lemma 4.10 can be converted into
a feasible solution of $\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{1,n}$
with identical objective value. The challenge lies in verifying that the
reverse substitution $y_{i}=n\theta(z_{i+1}-2z_{i}+z_{i-1})$ (with the
$z_{i}$’s defined according to Lemma 4.10) satisfies all of the constraints in
$\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{1,n}$, which can be distilled
down to showing inequality (36). A priori, (36) is only satisfied when $S$
takes the form $\\{1,\ldots,I\\}$ (since those are the constraints we kept in
the first relaxation (37)); in fact (36) is even non-obvious when $\kappa=0$
and $S$ consists of a singleton $i$ (in which case (36) is equivalent to
analytically checking that $y_{i}\geq 0$). To streamline the proof of (36), we
define a set function $f(S)$ that substitutes the pessimal value of $\kappa$
into (36) for each set $S$, and show this set function to be supermodular.
This allows us to ultimately show that it is maximized when $S$ takes the form
of an interval $\\{1,\ldots,I\\}$, for which we already knew by construction
that (36) is satisfied as equality. This is all formalized in the proof of the
lemma below.

###### Lemma 4.11

It holds that
$\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{1,n}=\mathsf{LP}^{\mathsf{relax}}_{n}$
for each $n\geq 1$.

#### Third step.

Having established
$\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{1,n}=\mathsf{LP}^{\mathsf{relax}}_{n}$,
the proof is completed by showing that the objective value of
$\mathsf{LP}^{\mathsf{relax}}_{n}$ is minimized as $n\to\infty$. Although
monotonicity in $n$ is difficult to prove in general, we bypass this
difficulty by comparing the values of $\mathsf{LP}_{n}$ with
$\mathsf{LP}_{2n}$, which our closed-form solution allows us to do.

###### Lemma 4.12

For any $n\geq 1$, it holds that
$\mathsf{LP}^{\mathsf{relax}}_{n}\geq\mathsf{LP}^{\mathsf{relax}}_{2n}$.

Thus, in order to obtain the tight worst case guarantee, it remains to analyze
the behavior of the optimal solution $\\{\theta,z_{I}\\}_{I=0}^{n}$ of
$\mathsf{LP}^{\mathsf{relax}}_{n}$ when $n\to\infty$. By Lemma 4.10, we have
the recursive equation

$z_{I+1}=\frac{n-1}{n}z_{I}^{n/(n-1)}-\frac{1}{n\theta}+\frac{1}{n},\leavevmode\nobreak\
\leavevmode\nobreak\ \forall I=0,\ldots,n-1$

with $z_{0}=1$ and $z_{n}=0$. By treating $x$ as $I/n$ and $H(x)$ as
$z_{I}$,the recursive equation above motivates the following differential
equation,

$\frac{1}{\theta^{*}}-1=H(x)(\ln H(x)-1)-H^{\prime}(x),\qquad\forall
x\in[0,1]$ (39)

with the boundary conditions $H(0)=1$ and $H(1)=0$, with $\theta^{*}$ being
the precise constant that allows these relationships to hold. Then, we have
the following result, which is the guarantee for $\mathsf{DP}/\mathsf{Proph}$
in the IID setting with $k=1$.

###### Theorem 4.13

It holds that
$\inf_{n}\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{1,n}=\lim_{n\rightarrow\infty}\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{1,n}=\theta^{*}$,
where $\theta^{*}$ is defined in (39).

Note that from the definition of the function $H(x)$ and $\theta^{*}$, it
holds that

$\int_{1}^{0}\frac{1}{1-\frac{1}{\theta^{*}}-H(1-\ln H)}dH=1.$

This recovers the same integral relationship as in Hill and Kertz (1982),
Correa et al. (2017), Liu et al. (2021) which is used to establish the
numerical guarantee of $\alpha=\theta^{*}\approx 0.745$.

##  5 Concluding Remarks

In this work, we derive tight guarantees for multi-unit prophet inequalities.
The procedure of computing the tight guarantees is formulated as an
optimization problem (LP) and by analyzing this optimization problem, we
directly find the tight ratios without constructing any worst-case instances.
Our analysis of this optimization problem is based on identifying a new “Type
Coverage” dual problem from the optimization problem formulation. This new
problem can be seen as akin to the celebrated Magician/OCRS problems, except
more general in that it can also provide tight ratios relative to the prophet
directly, whereas the Magician/OCRS problems only establish tight ratios
relative to the ex-ante relaxation. By further analyzing the structures of the
“Type Coverage” dual problem, we derive new prophet inequalities and recover
existing ones. We first show that the “oblivious” static threshold policy
achieves a best-possible guarantee among static threshold algorithms, under
any number $k$ of starting units (even though it is not instance-optimal in
the non-IID setting). This result implies the tightness of the asymptotic
convergence rate of $1-O(\sqrt{\log k/k})$ for static threshold algorithms,
which dates back to Hajiaghayi et al. (2007), and establishes a separation
with the convergence rate of adaptive algorithms, which is
$1-\Theta(\sqrt{1/k})$ due to Alaei (2014). Under the IID setting, we then use
our framework to numerically illustrate the tight guarantee (of adaptive
algorithms) under any number $k$ of starting units. The tight guarantee has
been previously characterized under $k=1$ by Correa et al. (2017), and our
guarantees for $k>1$ exceed the state-of-the-art from the free-order setting
due to Beyhaghi et al. (2021).

There are multiple new prospective directions for future research. First,
there is a recent stream of work studying the performance of the online
algorithm against the online optimum (DP) (e.g. Papadimitriou et al. (2021)).
For the online optimum benchmark, one could still apply a similar LP duality
approach by interpreting the coefficient $Q_{j}$ as the expected number of
agents of type $j$ or better accepted by the online optimum. However, the
caveat is that when making sense of the “Type Coverage” formulation, the value
of $Q_{j}$ is implicitly defined through a DP (cf. the formulations in
Proposition 2.8), from which it may be difficult to prove results using the
“Type Coverage” problem. Second, there are other variants of prophet
inequalities defined on more general matroids beyond the $k$-uniform matroids
(e.g. Kleinberg and Weinberg (2012)). The challenge of extending our approach
to general matroid prophet inequalities relies on lower bounding what an
online policy can earn in the primal problem, which is also the adversary’s
problem of designing a worst-case instance. For $k$-uniform matroids, we could
finish this step fairly cleanly for the DP/static threshold online policies by
having $k$ state variables for when each agent arrives. However, for more
general matroid constraints, if we still apply the same approach, there may
need to be exponentially many variables for the state when each agent arrives,
which might lead to an unwieldy dual.

We finally remark that although we prove our positive results by assuming the
value distributions of the agents take finite support, all our results can be
directly extended to the setting where the value distributions can be
continuous and take infinite support. To see this point, for fixed $n$, $k$,
and for infinite support, we specify an interval $[0,\bar{r}]$ to cover the
support of the value distribution of each agent and specify
$r(q)=q\cdot\bar{r}$ for any $q\in[0,1]$. Therefore, we are able to express
the value using the index $q$ for each agent, and following this notation, we
can express the value distribution for agent $i$ using CDF $F_{i}(q)$, which
is defined on $q\in[0,1]$. This formulation will cover the continuous support
case and LP (7) can be rewritten in the following way.

$\displaystyle\min\ $ $\displaystyle V^{k}_{1}$ (40a)
$\displaystyle\mathrm{s.t.\ }$ $\displaystyle
V_{i}^{l}=\int_{q=0}^{1}U^{l}_{i}(q)\cdot dF_{i}(q)+V^{l}_{i+1}$
$\displaystyle\forall i\in[n],l\in[k]$ (40b) $\displaystyle
U^{l}_{i}(q)\geq\int_{q^{\prime}=q}^{1}dr(q)-(V^{l}_{i+1}-V^{l-1}_{i+1})$
$\displaystyle\forall i\in[n],q\in[0,1],l\in[k]$ (40c)
$\displaystyle\int_{q=0}^{1}Q(q)dr(q)=1$ (40d) $\displaystyle
dr(q),U^{l}_{i}(q)\geq 0$ $\displaystyle\forall i\in[n],q\in[0,1],l\in[k]$
(40e)

Here, we would regard $dr(q)$ and $U_{i}^{l}(q)$ as decision variables, which
play the same role as $\Delta_{j}$ and $U^{l}_{ij}$ in the original finite
support formulation in LP (7), except we are replacing the index $j$ by the
index $q$. Also, $Q(q)$ plays the same role as $Q_{j}$ in the original finite
support formulation in LP (7), and $Q(q)$ denotes the expected number for the
agents with valuation among $[q\cdot\bar{r},\bar{r}]$ to be accepted by the
benchmark.

Note that the above problem (40) is infinite linear programming and we can
write out the (simplified) dual exactly in the same way as we write out the
dual for the finite support formulation. One can easily verify that slater’s
conditions hold for infinite LP (40) by setting $U^{l}_{i}(q)$ to always be
larger than the right-hand side of constraint (40c), which implies that strong
duality holds between infinite LP (40) and its dual. The dual is as follows

$\displaystyle\max\ $ $\displaystyle\theta$ (41a) $\displaystyle\mathrm{s.t.\
\ }$ $\displaystyle\theta\cdot
Q(q)\leq\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{y^{l}_{i},F_{i}(q)\cdot
x^{l}_{i}\\}$ $\displaystyle\forall q\in[0,1]$ (41b) $\displaystyle
y^{l}_{i}\leq x^{l}_{i}$ $\displaystyle\forall i\in[n],l\in[k]$ (41c)
$\displaystyle x^{l}_{i}=\begin{cases}1,&i=1,l=k\\\ 0,&i=1,l<k\\\
x^{l}_{i-1}-y^{l}_{i-1}+y^{l+1}_{i-1},&i>1\\\ \end{cases}$
$\displaystyle\forall i\in[n],l\in[k]$ (41d) $\displaystyle y^{l}_{i}\geq 0$
$\displaystyle\forall i\in[n],l\in[k]$ (41e)

As we can see, the only difference between the dual (41) and the dual for the
finite support formulation (LP (9)) is that the discrete index $j$ has been
replaced by the continuous index $q\in[0,1]$. Following this line, we can
write the other duals for $\mathsf{OST}$ and $\mathsf{ST}$ by replacing the
discrete index with the continuous index and we will be able to obtain the
same result for the continuous index formulation where the value distributions
for the agents can take infinite support.

## Acknowledgments

The authors would like to thank the three anonymous reviewers of the EC
conference, where the preliminary version of the paper is published. Their
insightful comments greatly help us to improve the paper.

## References

  * Alaei (2014) Alaei S (2014) Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. _SIAM Journal on Computing_ 43(2):930–972.
  * 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.
  * Arnosti and Ma (2022) Arnosti N, Ma W (2022) Tight guarantees for static threshold policies in the prophet secretary problem. _Proceedings of the 23rd ACM Conference on Economics and Computation_ , 242–242.
  * Beyhaghi et al. (2021) Beyhaghi H, Golrezaei N, Leme RP, Pál M, Sivan B (2021) Improved revenue bounds for posted-price and second-price mechanisms. _Operations Research_ 69(6):1805–1822.
  * Brustle et al. (2022) Brustle J, Correa J, Dütting P, Verdugo V (2022) The competition complexity of dynamic pricing. _Proceedings of the 23rd ACM Conference on Economics and Computation_ , 303–320.
  * Chawla et al. (2020) Chawla S, Devanur N, Lykouris T (2020) Static pricing for multi-unit prophet inequalities. _arXiv preprint arXiv:2007.07990_ .
  * Chawla et al. (2010) Chawla S, Hartline JD, Malec DL, Sivan B (2010) Multi-parameter mechanism design and sequential posted pricing. _Proceedings of the forty-second ACM symposium on Theory of computing_ , 311–320.
  * Correa et al. (2017) Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2017) Posted price mechanisms for a random stream of customers. _Proceedings of the 2017 ACM Conference on Economics and Computation_ , 169–186.
  * Correa et al. (2019a) Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2019a) Recent developments in prophet inequalities. _ACM SIGecom Exchanges_ 17(1):61–70.
  * Correa et al. (2019b) Correa J, Foncea P, Pizarro D, Verdugo V (2019b) From pricing to prophets, and back! _Operations Research Letters_ 47(1):25–29.
  * Duembgen (2010) Duembgen L (2010) Bounding standard gaussian tail probabilities. _arXiv preprint arXiv:1012.2063_ .
  * 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).
  * 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.
  * Gallego et al. (2015) Gallego G, Li A, Truong VA, Wang X (2015) Online resource allocation with customer choice. _arXiv preprint arXiv:1511.01837_ .
  * Hajiaghayi et al. (2007) Hajiaghayi MT, Kleinberg R, Sandholm T (2007) Automated online mechanism design and prophet inequalities. _AAAI_ , volume 7, 58–65.
  * Harremoës (2016) Harremoës P (2016) Bounds on tail probabilities for negative binomial distributions. _Kybernetika_ 52(6):943–966.
  * Hill and Kertz (1982) Hill TP, Kertz RP (1982) Comparisons of stop rule and supremum expectations of iid random variables. _The Annals of Probability_ 336–345.
  * 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).
  * Kertz (1986) Kertz RP (1986) Stop rule and supremum expectations of iid random variables: a complete comparison by conjugate duality. _Journal of multivariate analysis_ 19(1):88–112.
  * 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.
  * Krengel and Sucheston (1978) Krengel U, Sucheston L (1978) On semiamarts, amarts, and processes with finite value. _Probability on Banach spaces_ 4:197–266.
  * Lee and Singla (2018) Lee E, Singla S (2018) Optimal online contention resolution schemes via ex-ante prophet inequalities. _arXiv preprint arXiv:1806.09251_ .
  * Liu et al. (2021) Liu A, Leme RP, Pál M, Schneider J, Sivan B (2021) Variable decomposition for prophet inequalities and optimal ordering. _Proceedings of the 22nd ACM Conference on Economics and Computation_ , 692–692.
  * Lucier (2017) Lucier B (2017) An economic view of prophet inequalities. _ACM SIGecom Exchanges_ 16(1):24–47.
  * 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.
  * Puterman (2014) Puterman ML (2014) _Markov decision processes: discrete stochastic dynamic programming_ (John Wiley & Sons).
  * Samuel-Cahn (1984) Samuel-Cahn E (1984) Comparison of threshold stop rules and maximum for independent nonnegative random variables. _the Annals of Probability_ 1213–1216.
  * Shapiro (2009) Shapiro A (2009) Semi-infinite programming, duality, discretization and optimality conditions. _Optimization_ 58(2):133–161.
  * Topkis (2011) Topkis DM (2011) Supermodularity and complementarity. _Supermodularity and Complementarity_ (Princeton 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).

##  6 Numerical Results for $\mathsf{DP}/\mathsf{Proph}$ in IID Setting

In this section, we plot the numerical results for
$\mathsf{DP}/\mathsf{Proph}$ in IID setting for general $k\geq 1$, following
the approach described in Section 4.3. For each fixed $k$, we set
$\varepsilon=0.0001$ to approximate the value of
$\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}$ with an error within
$0.01\%$, for any $n$. We increase the value of $n$ until the value of
$\mathrm{iidLP}^{\mathsf{DP}/\mathsf{Proph}}_{k,n}$ appears to have stablized,
as illustrated in Figure 1 for $k=1$ up to $k=10$. The numbers reported
earlier in Table 1 are for $n=8000$.

(a) $k=1$

(b) $k=2$

(c) $k=3$

(d) $k=4$

(e) $k=5$

(f) $k=6$

(g) $k=7$

(h) $k=8$

(i) $k=9$

(j) $k=10$

Figure 1: The guarantee as $n\rightarrow\infty$, for $k=1$ up to $k=10$, with
x-axis being $\log_{2}(n)$.

##  7 Missing Proofs for Section 2

##### Proof of Proposition 2.8.

We denote by $X_{j}$ the number of agents that have a type $j$ and are
accepted by the prophet. Clearly, we have

$\mathsf{Proph}(I)=\sum_{j=1}^{m}r_{j}\cdot\mathbb{E}[X_{j}]=\sum_{j=1}^{m}\Delta_{j}\cdot\mathbb{E}[\sum_{j^{\prime}=1}^{j}X_{j^{\prime}}]$

Moreover, note that the distribution of
$\sum_{j^{\prime}=1}^{j}X_{j^{\prime}}$ is given by
$\min\\{\sum_{i=1}^{n}\mathrm{Ber}(G_{ij}),k\\}$. Thus, it holds that

$\mathsf{Proph}(I)=\sum_{j=1}^{m}\Delta_{j}\cdot\mathbb{E}[\min\\{\sum_{i=1}^{n}\mathrm{Ber}(G_{ij}),k\\}]$

We now denote by $\\{a^{*}_{j}\\}_{j=1}^{m}$ one optimal solution to
$\mathsf{ExAnte}(I)$. Clearly, for any $j_{1}<j_{2}$, if
$a^{*}_{j_{1}}<\sum_{i=1}^{n}p_{ij_{1}}$, it must hold that $a^{*}_{j_{2}}=0$.
Otherwise, we construct another set of solution
$\\{a^{\prime}_{j}\\}_{j=1}^{m}$ by letting

$\displaystyle a^{\prime}_{j}=a^{*}_{j}\text{\leavevmode\nobreak\
for\leavevmode\nobreak\ }j\neq j_{1}\text{\leavevmode\nobreak\
and\leavevmode\nobreak\ }j_{2},\leavevmode\nobreak\ \leavevmode\nobreak\
a^{\prime}_{j_{1}}=a^{*}_{j_{1}}+\epsilon,\leavevmode\nobreak\
\leavevmode\nobreak\ a^{\prime}_{j_{2}}=a^{*}_{j_{2}}-\epsilon$

where
$0<\epsilon\leq\min\\{a^{*}_{j_{2}},\sum_{i=1}^{n}p_{ij_{1}}-a^{*}_{j_{1}}\\}$.
Clearly, $\\{a^{\prime}_{j}\\}_{j=1}^{m}$ is feasible to $\mathsf{ExAnte}(I)$
and yields a higher objective value than $\\{a^{*}_{j}\\}_{j=1}^{m}$, which
contradicts the optimality of $\\{a^{*}_{j}\\}_{j=1}^{m}$. Thus, it holds that

$\sum_{j^{\prime}=1}^{j}a^{*}_{j^{\prime}}=\min\\{\sum_{i=1}^{n}G_{ij},k\\}\text{\leavevmode\nobreak\
for\leavevmode\nobreak\ any\leavevmode\nobreak\ }j$

and

$\mathsf{ExAnte}(I)=\sum_{j=1}^{m}r_{j}\cdot
a^{*}_{j}=\sum_{j=1}^{m}\Delta_{j}\cdot\sum_{j^{\prime}=1}^{j}a^{*}_{j^{\prime}}=\sum_{j=1}^{m}\Delta_{j}\cdot\min\\{\sum_{i=1}^{n}G_{ij},k\\}$

which completes our proof of (6). $\Halmos$

##### Proof of Lemma 2.11.

Given a feasible solution to (8), we construct the following feasible solution
to (9) with the same value of $\theta$. Let
$y^{l}_{i}=\sum_{j=1}^{m}y^{l}_{ij}$ for all $i\in[n]$ and $l\in[k]$. Clearly
constraints (9d)–(9e) are satisfied. Constraints (9c) are satisfied due to the
fact that $\sum_{j=1}^{m}p_{ij}=1$ for all $i$. Finally, it remains to show
that
$\min\\{y^{l}_{i},G_{ij}x^{l}_{i}\\}\geq\sum_{j^{\prime}=1}^{j}y^{l}_{ij^{\prime}}$
which would make constraints (9b) satisfied. To see this, note that
$\min\\{y^{l}_{i},G_{ij}x^{l}_{i}\\}=\min\\{\sum_{j=1}^{m}y^{l}_{ij},x^{l}_{i}\sum_{j^{\prime}=1}^{j}p_{ij^{\prime}}\\}\geq\min\\{\sum_{j=1}^{m}y^{l}_{ij},\sum_{j^{\prime}=1}^{j}y^{l}_{ij^{\prime}}\\}$
where the inequality applies (8c). Since both arguments in the $\min$ are at
least $\sum_{j^{\prime}=1}^{j}y^{l}_{ij^{\prime}}$, this completes the proof.

Conversely, given a feasible solution to (9), we construct the following
feasible solution to (8) with the same value of $\theta$, which is the harder
direction. For each $i\in[n]$ and $l\in[k]$, we iteratively define

$\displaystyle y^{l}_{i1}$ $\displaystyle=\min\\{y^{l}_{i},p_{i1}x^{l}_{i}\\}$
$\displaystyle y^{l}_{i2}$
$\displaystyle=\min\\{y^{l}_{i}-y^{l}_{i1},p_{i2}x^{l}_{i}\\}$
$\displaystyle\cdots$ $\displaystyle y^{l}_{im}$
$\displaystyle=\min\\{y^{l}_{i}-\sum_{j=1}^{m-1}y^{l}_{ij},p_{im}x^{l}_{i}\\}.$

Constraints (8c) hold from the second argument in the $\min$, while
constraints (8e) hold because by the first argument in the $\min$, the sum
$\sum_{j}y^{l}_{ij}$ can never exceed $y^{l}_{i}$. Meanwhile, it can be
inductively established that
$\sum_{j^{\prime}=1}^{j}y^{l}_{ij^{\prime}}=\min\\{y^{l}_{i},x^{l}_{i}\sum_{j^{\prime}=1}^{j}p_{ij^{\prime}}\\}=\min\\{y^{l}_{i},G_{ij}x^{l}_{i}\\}$
for all $j=1,\ldots,m$, establishing constraints (8b). Finally, by the same
fact $\sum_{j=1}^{m}y^{l}_{ij}=\min\\{y^{l}_{i},x^{l}_{i}\\}=y^{l}_{i}$,
establishing constraints (8d) and completing the proof. $\Halmos$

##### Proof of Theorem 2.17.

We consider the dual of LP (10). We introduce $x_{i}^{l}$ as the dual variable
for constraint (10b), the dual variable $y_{ij}^{l}$ for constraint (10c) and
dual variable $\theta$ for constraint (10d). Then, we get the following LP as
the dual of LP (10).

$\displaystyle\max\ \theta$ (42a) $\displaystyle\mathrm{s.t.\ }\theta\cdot
Q_{j}$
$\displaystyle\leq\sum_{i=1}^{n}\sum_{l=1}^{k}\sum_{j^{\prime}=1}^{j}y_{ij^{\prime}}^{l}$
$\displaystyle\forall j\in[m]$ (42b) $\displaystyle y^{l}_{ij}$
$\displaystyle=\begin{cases}p_{ij}x^{l}_{i},&j<J\\\ p_{iJ}\rho
x_{i}^{l},&j=J\\\ 0,&j>J\\\ \end{cases}$ $\displaystyle\forall
i\in[n],l\in[k]$ (42c) $\displaystyle x^{l}_{i}$
$\displaystyle=\begin{cases}1,&i=1,l=k\\\ 0,&i=1,l<k\\\
x^{l}_{i-1}-\sum_{j=1}^{m}y^{l}_{i-1,j}+\sum_{j=1}^{m}y^{l+1}_{i-1,j},&i>1\\\
\end{cases}$ $\displaystyle\forall i\in[n],l\in[k]$ (42d)
$\displaystyle\theta$ $\displaystyle,x_{i}^{l},y_{ij}^{l}\in\mathbb{R}$
$\displaystyle\forall i\in[n],\forall j\in[m],\forall l\in[k]$ (42e)

For any $i\in[n]$, $l\in[k]$, we define $y_{i}^{l}=\sum_{j=1}^{m}y_{ij}^{l}$.
Then, constraint (42c) implies that

$y^{l}_{i}=(\sum_{j<J}p_{ij}+p_{iJ}\rho)x^{l}_{i}=((1-\rho)G_{i,J-1}+\rho
G_{iJ})x^{l}_{i},\leavevmode\nobreak\ \leavevmode\nobreak\ \forall
i\in[n],l\in[k].$

Moreover, for any $j\in[m]$, constraint (42c) implies that

$\sum_{j^{\prime}=1}^{j}y_{ij^{\prime}}^{l}=\min\\{y_{i}^{l},G_{ij}x_{i}^{l}\\},\leavevmode\nobreak\
\leavevmode\nobreak\ \forall i\in[n],l\in[k]$

Thus, a feasible solution to LP (42) can be translated into a feasible
solution to the following LP, with the same objective value,

$\displaystyle\max\ \theta$ (43a) $\displaystyle\mathrm{s.t.\ }\theta\cdot
Q_{j}$
$\displaystyle\leq\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{y^{l}_{i},G_{ij}x^{l}_{i}\\}$
$\displaystyle\forall j\in[m]$ (43b) $\displaystyle y^{l}_{i}$
$\displaystyle=(\sum_{j<J}p_{ij}+p_{iJ}\rho)x^{l}_{i}=((1-\rho)G_{i,J-1}+\rho
G_{iJ})x^{l}_{i}$ $\displaystyle\forall i\in[n],l\in[k]$ (43c) $\displaystyle
x^{l}_{i}$ $\displaystyle=\begin{cases}1,&i=1,l=k\\\ 0,&i=1,l<k\\\
x^{l}_{i-1}-y^{l}_{i-1}+y^{l+1}_{i-1},&i>1\\\ \end{cases}$
$\displaystyle\forall i\in[n],l\in[k]$ (43d) $\displaystyle y^{l}_{i}$
$\displaystyle\geq 0$ $\displaystyle\forall i\in[n],l\in[k].$ (43e)

We now show that a feasible solution to LP (43), denoted by
$\\{\theta,x_{i}^{l},y_{i}^{l}\\}$, can be translated into a feasible solution
to LP (42) with the same objective value, which implies that the objective
value of LP (42) is equivalent to the objective value of LP (43). To be
specific, we define

$y_{ij}^{l}=\left\\{\begin{aligned} &p_{ij}x_{i}^{l},&j<J\\\ &p_{iJ}\rho
x_{i}^{l},&j=J\\\ &0,&j>J\end{aligned}\right.$

Clearly, $\\{\theta,x_{i}^{l},y_{ij}^{l}\\}$ satisfy the constraint (42c) and
(42d). We also have
$\sum_{j^{\prime}=1}^{j}y_{ij^{\prime}}^{l}=\min\\{y_{i}^{l},G_{ij}x_{i}^{l}\\}$
for any $i\in[n],l\in[k],j\in[m]$, which implies that constraint (42b) is
satisfied. Thus, $\\{\theta,x_{i}^{l},y_{ij}^{l}\\}$ is a feasible solution to
LP (42).

For the problem instance $I=(\mathbf{G},\mathbf{\Delta})$, we denote by
$\mathsf{OST}_{J,\rho}(I)$ the total expected reward collected by the
oblivious static threshold policy $J,\rho$ on problem instance $I$. Then, from
the definition of LP (10), we have that

$\inf_{\mathbf{\Delta}}\frac{\mathsf{OST}_{J,\rho}(I)}{\mathsf{Proph}(I)}=\text{LP\leavevmode\nobreak\
}\eqref{lp:innerPrimalOST}\text{\leavevmode\nobreak\ with\leavevmode\nobreak\
variable\leavevmode\nobreak\
}Q_{j}=\mathbb{E}[\min\\{\sum_{i=1}^{n}\mathrm{Ber}(G_{ij}),k\\}]$

Similarly, we have

$\inf_{\mathbf{\Delta}}\frac{\mathsf{OST}_{J,\rho}(I)}{\mathsf{ExAnte}(I)}=\text{LP\leavevmode\nobreak\
}\eqref{lp:innerPrimalOST}\text{\leavevmode\nobreak\ with\leavevmode\nobreak\
variable\leavevmode\nobreak\ }Q_{j}=\min\\{\sum_{i=1}^{n}G_{ij},k\\}$

Note that LP (42) is the dual of LP (10), and we have shown the objective
value of LP (42) is equivalent to the objective value of LP (43), which gives
the expression of
$\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{Proph}}_{k,n}(\mathbf{G})$
(resp.
$\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$)
when $Q_{j}=\mathbb{E}[\min\\{\sum_{i=1}^{n}\mathrm{Ber}(G_{ij}),k\\}]$ (resp.
$Q_{j}=\min\\{\sum_{i=1}^{n}G_{ij},k\\}$). Thus, we have

$\inf_{\mathbf{\Delta}}\frac{\mathsf{OST}_{J,\rho}(I)}{\mathsf{Proph}(I)}=\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{Proph}}_{k,n}(\mathbf{G})\text{\leavevmode\nobreak\
and\leavevmode\nobreak\
}\inf_{\mathbf{\Delta}}\frac{\mathsf{OST}_{J,\rho}(I)}{\mathsf{ExAnte}(I)}=\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$

Note that according to Definition 2.14, the choice of $J,\rho$ for
$\mathsf{OST}$ can depend on $\mathbf{G}$. Thus, we know that the tight
guarantee for $\mathsf{OST}$ relative to the prophet (resp. ex-ante
relaxation) is given by

$\inf_{\mathbf{G}}\sup_{J,\rho}\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{Proph}}_{k,n}(\mathbf{G})\text{\leavevmode\nobreak\
(resp.\leavevmode\nobreak\
}\inf_{\mathbf{G}}\sup_{J,\rho}\mathrm{innerLP}^{\mathsf{OST}(J,\rho)/\mathsf{ExAnte}}_{k,n}(\mathbf{G}))$

which completes our proof. $\Halmos$

##### Proof of Theorem 2.21.

We consider the dual of LP (12). We introduce the dual variable
$x_{i}^{l}(J,\rho)$ for constraint (12b), the dual variable
$y_{ij}^{l}(J,\rho)$ for constraint (12c), the dual variable $\mu(J,\rho)$ for
constraint (12d) and the dual variable $\theta$ for constraint (12e). Then, we
get the following LP as the dual of LP (12).

$\displaystyle\max\ $ $\displaystyle\theta$ (44a) $\displaystyle\mathrm{s.t.\
\ }$ $\displaystyle\theta\cdot
Q_{j}\leq\int_{J,\rho}\mu(J,\rho)\left(\sum_{i=1}^{n}\sum_{l=1}^{k}\sum_{j^{\prime}=1}^{j}y_{ij^{\prime}}^{l}(J,\rho)\right)$
$\displaystyle\forall j\in[m]\ $ (44b) $\displaystyle
y^{l}_{ij}(J,\rho)=\begin{cases}p_{ij}x^{l}_{i}(J,\rho),&j<J\\\ p_{iJ}\rho
x_{i}^{l}(J,\rho),&j=J\\\ 0,&j>J\\\ \end{cases}$ $\displaystyle\forall
i\in[n],l\in[k],J\in[m],\rho\in(0,1]\ $ (44c) $\displaystyle
x_{i}^{l}(J,\rho)=\begin{cases}1,&i=1,l=k\\\ 0,&i=1,l<k\\\
x^{l}_{i-1}(J,\rho)-\sum_{j=1}^{m}y^{l}_{i-1,j}(J,\rho)+\sum_{j=1}^{m}y^{l+1}_{i-1,j}(J,\rho),&i>1\\\
\end{cases}$ $\displaystyle\forall i\in[n],l\in[k]\ $ (44d)
$\displaystyle\mu(J,\rho)\geq 0$ $\displaystyle\forall J\in[m],\rho\in(0,1]$
(44e)

Note that we can select a positive
$\\{x_{i}^{l}(J,\rho),y_{ij}^{l}(J,\rho)\\}$ satisfying constraints (44c) and
(44d), select $\mu(J,\rho)$ to be a uniform distribution over
$J\in[m],\rho\in(0,1]$, and set $\theta=0$. Then, all the inequality
constraints in LP (44) can be satisfied as strict inequalities by
$\\{\theta,x_{i}^{l}(J,\rho),y_{ij}^{l}(J,\rho),\mu(J,\rho)\\}$. Thus, the
Slater’s condition is satisfied and strong duality hols between LP (12) and LP
(44) (Theorem 2.3 in Shapiro (2009)).

Now we define $y_{i}^{l}(J,\rho)=\sum_{j=1}^{m}y_{ij}^{l}(J,\rho)$ for any
$i\in[n],l\in[k],J\in[m],\rho\in(0,1]$. Then, constraint (44c) implies that

$y^{l}_{i}(J,\rho)=((1-\rho)G_{i,J-1}+\rho
G_{iJ})x^{l}_{i}(J,\rho),\leavevmode\nobreak\ \leavevmode\nobreak\ \forall
i\in[n],l\in[k],J\in[m],\rho\in(0,1]$

and

$\sum_{j^{\prime}=1}^{j}y_{ij^{\prime}}^{l}(J,\rho)=\min\\{y_{i}^{l}(J,\rho),G_{ij}x_{i}^{l}(J,\rho)\\},\leavevmode\nobreak\
\leavevmode\nobreak\ \forall i\in[n],l\in[k],j,J\in[m],\rho\in(0,1]$

Thus, a feasible solution to LP (44) can be translated into a feasible
solution to LP (13) with the same objective value.

On the other hand, we denote by
$\\{\theta,\mathbf{x}(J,\rho),\mathbf{y}(J,\rho),\mu(J,\rho)\\}$ a feasible
solution to LP (13). Then, for any $i\in[n],l\in[k],J\in[m],\rho\in(0,1]$, we
define

$y_{ij}^{l}(J,\rho)=\begin{cases}p_{ij}x^{l}_{i}(J,\rho),&j<J\\\ p_{iJ}\rho
x_{i}^{l}(J,\rho),&j=J\\\ 0,&j>J\\\ \end{cases}$

Clearly, we have
$\sum_{j^{\prime}=1}^{j}y_{ij^{\prime}}^{l}(J,\rho)=\min\\{y_{i}^{l}(J,\rho),G_{ij}x_{i}^{l}(J,\rho)\\}$
for any $i\in[n],l\in[k],j,J\in[m],\rho\in(0,1]$ and constraint (13c) implies
that $\sum_{j=1}^{m}y_{ij}^{l}(J,\rho)=y_{i}^{l}(J,\rho)$ for any
$i\in[n],l\in[k],J\in[m],\rho\in(0,1]$. Then, we have
$\\{\theta,x_{i}^{l}(J,\rho),y_{ij}^{l}(J,\rho),\mu(J,\rho)\\}$ a feasible
solution to LP (44) with the same objective value. Thus, the objective value
of LP (44) is equivalent to the objective value of LP (13).

For the problem instance $I=(\mathbf{G},\mathbf{\Delta})$, we denote by
$\mathsf{ST}_{J,\rho}(I)$ the total expected reward collected by the static
threshold policy $J,\rho$ on problem instance $I$. Then, from the definition
of LP (12), we have that

$\inf_{\mathbf{\Delta}}\sup_{J,\rho}\frac{\mathsf{ST}_{J,\rho}(I)}{\mathsf{Proph}(I)}=\text{LP\leavevmode\nobreak\
}\eqref{lp:innerPrimalST}\text{\leavevmode\nobreak\ with\leavevmode\nobreak\
variable\leavevmode\nobreak\
}Q_{j}=\mathbb{E}[\min\\{\sum_{i=1}^{n}\mathrm{Ber}(G_{ij}),k\\}]$

Similarly, we have

$\inf_{\mathbf{\Delta}}\sup_{J,\rho}\frac{\mathsf{ST}_{J,\rho}(I)}{\mathsf{ExAnte}(I)}=\text{LP\leavevmode\nobreak\
}\eqref{lp:innerPrimalST}\text{\leavevmode\nobreak\ with\leavevmode\nobreak\
variable\leavevmode\nobreak\ }Q_{j}=\min\\{\sum_{i=1}^{n}G_{ij},k\\}$

Note that LP (44) is the dual of LP (12), where strong duality holds, and we
have shown the objective value of LP (44) is equivalent to the objective value
of LP (13), which gives the expression of
$\mathrm{innerLP}^{\mathsf{ST}(J,\rho)/\mathsf{Proph}}_{k,n}(\mathbf{G})$
(resp.
$\mathrm{innerLP}^{\mathsf{ST}(J,\rho)/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$)
when $Q_{j}=\mathbb{E}[\min\\{\sum_{i=1}^{n}\mathrm{Ber}(G_{ij}),k\\}]$ (resp.
$Q_{j}=\min\\{\sum_{i=1}^{n}G_{ij},k\\}$). Thus, we have

$\inf_{\mathbf{\Delta}}\sup_{J,\rho}\frac{\mathsf{ST}_{J,\rho}(I)}{\mathsf{Proph}(I)}=\mathrm{innerLP}^{\mathsf{ST}(J,\rho)/\mathsf{Proph}}_{k,n}(\mathbf{G})\text{\leavevmode\nobreak\
and\leavevmode\nobreak\
}\inf_{\mathbf{\Delta}}\sup_{J,\rho}\frac{\mathsf{ST}_{J,\rho}(I)}{\mathsf{ExAnte}(I)}=\mathrm{innerLP}^{\mathsf{ST}(J,\rho)/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$

Note that according to Definition 2.14, the choice of $J,\rho$ for
$\mathsf{ST}$ can depend both on $\mathbf{G}$ and $\mathbf{\Delta}$. Thus, we
know that the tight guarantee for $\mathsf{ST}$ relative to the prophet is
given by

$\inf_{\mathbf{G}}\inf_{\mathbf{\Delta}}\sup_{J,\rho}\frac{\mathsf{ST}_{J,\rho}(I)}{\mathsf{Proph}(I)}=\inf_{\mathbf{G}}\mathrm{innerLP}^{\mathsf{ST}(J,\rho)/\mathsf{Proph}}_{k,n}(\mathbf{G})$

and the tight guarantee for $\mathsf{ST}$ relative to the ex-ante relaxation
is given by

$\inf_{\mathbf{G}}\inf_{\mathbf{\Delta}}\sup_{J,\rho}\frac{\mathsf{ST}_{J,\rho}(I)}{\mathsf{ExAnte}(I)}=\inf_{\mathbf{G}}\mathrm{innerLP}^{\mathsf{ST}(J,\rho)/\mathsf{ExAnte}}_{k,n}(\mathbf{G}).$

which completes our proof. $\Halmos$

##  8 Missing Proofs for Section 3

##### Proof of Theorem 3.1.

First we show that
$\inf_{\mathbf{G}}\mathrm{innerLP}^{\mathsf{DP}/\mathsf{ExAnte}}_{k,n}(\mathbf{G})\geq\eqref{lp:OCRS}$.
Given a $\mathbf{G}$ for the LHS, we construct an instance defined by
$g_{1},\ldots,g_{n}$ for the inner maximization problem on the RHS and show
that its optimal solution forms a feasible solution to
$\mathrm{innerLP}^{\mathsf{DP}/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$, which
would be sufficient. To accomplish this, let $J\in[m],\rho\in(0,1]$ be such
that $\sum_{i=1}^{n}(G_{i,J-1}+p_{iJ}\rho)=k$, which must uniquely exist since
$G_{im}=1$ for all $i\in[n]$ and $n>k$. Define $g_{i}=G_{i,J-1}+p_{iJ}\rho$
for all $i$, which we take to be our instance for the RHS, and consider an
optimal solution defined by $\theta,\mathbf{x},\mathbf{y}$ for its inner
problem. We claim that this forms a feasible solution to
$\mathrm{innerLP}^{\mathsf{DP}/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$. To see
why, note that for any $i$, the expression

$\frac{\sum_{l=1}^{k}\min\\{y^{l}_{i},G_{ij}x^{l}_{i}\\}}{G_{ij}}=\sum_{l=1}^{k}\min\\{\frac{y^{l}_{i}}{G_{ij}},x^{l}_{i}\\}$

is decreasing in $G_{ij}$. Therefore, for all $j<J$, since $G_{ij}\leq g_{i}$,
we have

$\frac{\sum_{l=1}^{k}\min\\{y^{l}_{i},G_{ij}x^{l}_{i}\\}}{G_{ij}}\geq\frac{\sum_{l=1}^{k}\min\\{y^{l}_{i},g_{i}x^{l}_{i}\\}}{g_{i}}\geq\theta.$

where the final inequality applies (16c). Therefore, for all $j<J$, we deduce

$\displaystyle\frac{\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{y^{l}_{i},G_{ij}x^{l}_{i}\\}}{\min\\{\sum_{i=1}^{n}G_{ij},k\\}}$
$\displaystyle=\frac{\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{y^{l}_{i},G_{ij}x^{l}_{i}\\}}{\sum_{i=1}^{n}G_{ij}}\geq\theta$

as required for (15c). Meanwhile, for all $j\geq J$, since $G_{ij}\geq g_{i}$,
we directly have

$\displaystyle\frac{\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{y^{l}_{i},G_{ij}x^{l}_{i}\\}}{\min\\{\sum_{i=1}^{n}G_{ij},k\\}}$
$\displaystyle\geq\frac{\sum_{i=1}^{n}\sum_{l=1}^{k}\min\\{y^{l}_{i},g_{i}x^{l}_{i}\\}}{\sum_{i=1}^{n}g_{i}}\geq\theta$

which completes the proof that
$\inf_{\mathbf{G}}\mathrm{innerLP}^{\mathsf{DP}/\mathsf{ExAnte}}_{k,n}(\mathbf{G})\geq\eqref{lp:OCRS}$.

To show that
$\inf_{\mathbf{G}}\mathrm{innerLP}^{\mathsf{DP}/\mathsf{ExAnte}}_{k,n}(\mathbf{G})\leq\eqref{lp:OCRS}$,
which is the harder direction, given an instance defined by
$g_{1},\ldots,g_{n}$ for the outer problem in (16) such that
$\sum_{i=1}^{n}g_{i}\leq k$, we construct an instance $\mathbf{G}$ for which
$\mathrm{innerLP}^{\mathsf{DP}/\mathsf{ExAnte}}_{k,n}(\mathbf{G})$ is no
greater than the optimal objective value of the inner problem in (16).

The construction goes as follows. Define $m=n+1$. We let

$G_{ij}=g_{i}\cdot\mathbbm{1}(i\leq j)\text{\leavevmode\nobreak\
for\leavevmode\nobreak\ all\leavevmode\nobreak\ }j<m\text{\leavevmode\nobreak\
and\leavevmode\nobreak\ }G_{im}=1,\forall i\in[n].$ (45)

Note that the feasibility constraints of $G_{i1}\leq\cdots\leq G_{im}=1$ are
satisfied for all $i$. Under this construction, it holds that

$Q_{j}=\min\\{\sum_{i=1}^{n}G_{ij},k\\}=\min\\{\sum_{i=1}^{j}g_{i},k\\}=\sum_{i=1}^{j}g_{i},\forall
j\in[m]$

where $g_{m}=k-\sum_{i=1}^{n}g_{i}$. Now, denote by
$\\{\Delta_{j}^{*},U_{ij}^{l*},V_{i}^{k*}\\}$ one optimal solution of the
following LP:

$\displaystyle\min\ $ $\displaystyle V^{k}_{1}$ (46a)
$\displaystyle\mathrm{s.t.\ \ }$ $\displaystyle
V_{i}^{l}=\sum_{j=1}^{m}p_{ij}U^{l}_{ij}+V^{l}_{i+1}$ $\displaystyle\forall
i\in[n],l\in[k]$ (46b) $\displaystyle
U^{l}_{ij}\geq\sum_{j^{\prime}=j}^{m}\Delta_{j^{\prime}}-(V^{l}_{i+1}-V^{l-1}_{i+1})$
$\displaystyle\forall i\in[n],j\in[m],l\in[k]$ (46c)
$\displaystyle\sum_{j^{\prime}=j}^{m}\Delta_{j^{\prime}}\geq 0$
$\displaystyle\forall j\in[m]$ (46d)
$\displaystyle\sum_{j=1}^{m}Q_{j}\Delta_{j}=1$ (46e)
$\displaystyle\Delta_{j}\in\mathbb{R},\Delta_{m}=0,U^{l}_{ij}\geq 0$
$\displaystyle\forall i\in[n],j\in[m],l\in[k]$ (46f)

with $p_{ij}=G_{ij}-G_{i,j-1}$. We further denote by
$r^{*}_{j}=\sum_{j^{\prime}=j}^{m}\Delta_{j^{\prime}}^{*}$ for each $j\in[m]$
and denote by $\\{\sigma(j),\forall j=1,\ldots,m\\}$ a permutation of
$\\{1,\ldots,m\\}$ such that $r^{*}_{\sigma(1)}\geq
r^{*}_{\sigma(2)}\geq\ldots\geq r^{*}_{\sigma(m)}$. For each $j\in[m]$, we
further denote $\hat{G}_{ij}=\sum_{j^{\prime}=1}^{j}p_{i\sigma(j^{\prime})}$,
for all $i\in[n]$. Then we have the following claim.

###### Claim 1

It holds that
$\mathsf{LP}\eqref{Theorem4innerPrimal}\geq\mathrm{innerLP}^{\mathsf{DP}/\mathsf{ExAnte}}_{k,n}(\hat{\mathbf{G}})$.

On the other hand, the dual of LP(46) is given as

$\displaystyle\max\ $ $\displaystyle\theta$ (47a) $\displaystyle\mathrm{s.t.\
\ }$ $\displaystyle\theta\cdot
Q_{j}+\sum_{j^{\prime}=1}^{j}\alpha_{j^{\prime}}=\sum_{i=1}^{n}\sum_{l=1}^{k}\sum_{j^{\prime}=1}^{j}y^{l}_{ij^{\prime}}$
$\displaystyle\forall j\in[n]$ (47b) $\displaystyle y^{l}_{ij}\leq
p_{ij}x^{l}_{i}$ $\displaystyle\forall i\in[n],j\in[m],l\in[k]$ (47c)
$\displaystyle x^{l}_{i}=\begin{cases}1,&i=1,l=k\\\ 0,&i=1,l<k\\\
x^{l}_{i-1}-\sum_{j=1}^{m}(y^{l}_{i-1,j}-y^{l+1}_{i-1,j}),&i>1\\\ \end{cases}$
$\displaystyle\forall i\in[n],l\in[k]$ (47d) $\displaystyle y^{l}_{ij}\geq
0,\alpha_{j}\geq 0,$ $\displaystyle\forall i\in[n],j\in[m],l\in[k]$ (47e)

Denote by $\\{\theta^{*},\alpha_{j}^{*},x_{i}^{l*},y_{ij}^{l*}\\}$ one optimal
solution of LP(47) and define $y_{i}^{l*}=\sum_{j=1}^{m}y_{ij}^{l*}$ for each
$i\in[n]$, $l\in[k]$. We now show that
$\\{\theta^{*},x_{i}^{l*},y_{i}^{l*}\\}$ is a feasible solution to LP(16).

Clearly, $(\mathbf{x}^{*},\mathbf{y}^{*})\in\mathcal{P}_{n}^{k}$. From
constraint (47b), for $j\in[n]$, we have that

$\theta^{*}\cdot(Q_{j}-Q_{j-1})+\alpha_{j}^{*}=\sum_{l=1}^{k}y_{jj}^{l*}\leq\sum_{l=1}^{k}\min\\{y_{j}^{l*},g_{j}x_{i}^{l*}\\}$

where the last inequality follows from the construction of $\mathbf{G}$ and
constraint (47c). Further note that for $j\in[n]$, we have $\theta^{*}\cdot
g_{j}\leq\theta^{*}\cdot(Q_{j}-Q_{j-1})+\alpha_{j}^{*}$. We conclude that
$\\{\theta^{*},x_{i}^{l*},y_{i}^{l*}\\}$ is a feasible solution to LP(16).
Thus, from 1, we have that

$\mathrm{innerLP}^{\mathsf{DP}/\mathsf{ExAnte}}_{k,n}(\hat{\mathbf{G}})\leq\mathsf{LP}\eqref{Theorem4innerPrimal}=\mathsf{LP}\eqref{Thm4innerDual}=\theta^{*}\leq\mathsf{LP}\eqref{lp:OCRS}$

which completes our proof. $\Halmos$

##### Proof of 1.

Note that from Lemma 2.11,
$\mathrm{innerLP}^{\mathsf{DP}/\mathsf{ExAnte}}_{k,n}(\hat{\mathbf{G}})$ is
given as the optimal objective value of the following LP:

$\displaystyle\min\ $ $\displaystyle V^{k}_{1}$ (48a)
$\displaystyle\mathrm{s.t.\ \ }$ $\displaystyle
V_{i}^{l}=\sum_{j=1}^{m}\hat{p}_{ij}U^{l}_{ij}+V^{l}_{i+1}$
$\displaystyle\forall i\in[n],l\in[k]$ (48b) $\displaystyle
U^{l}_{ij}\geq\sum_{j^{\prime}=j}^{m}\Delta_{j^{\prime}}-(V^{l}_{i+1}-V^{l-1}_{i+1})$
$\displaystyle\forall i\in[n],j\in[m],l\in[k]$ (48c)
$\displaystyle\sum_{j=1}^{m}\hat{Q}_{j}\Delta_{j}=1$ (48d)
$\displaystyle\Delta_{j}\geq 0,U^{l}_{ij}\geq 0$ $\displaystyle\forall
i\in[n],j\in[m],l\in[k]$ (48e)

where $\hat{p}_{ij}=p_{i\sigma(j)}$ and

$\hat{Q}_{j}=\min\\{\sum_{i=1}^{n}\hat{G}_{ij},k\\},\forall
j<m\text{\leavevmode\nobreak\ and\leavevmode\nobreak\
}\hat{Q}_{m}=\min\\{n,k\\}$

Note that $\sigma(m)=m$. We have $\hat{Q}_{j}=\sum_{i=1}^{j}g_{\sigma(i)}$. We
now construct a feasible solution to (48) from
$\\{\Delta^{*}_{j},U_{ij}^{l*},V_{i}^{k*}\\}$, which is the optimal solution
of (46) that gives rise to the definition of the permutation
$\\{\sigma(j),\forall j=1,\ldots,m\\}$. To be specific, we define

$\hat{V}_{i}^{k}=V_{i}^{k^{*}},\hat{U}_{ij}^{l}=U^{l*}_{i\sigma(j)},\text{\leavevmode\nobreak\
and\leavevmode\nobreak\
}\hat{\Delta}_{j}=r^{*}_{\sigma(j)}-r^{*}_{\sigma(j+1)},\forall
i\in[n],l\in[k],j\in[m]$

where we define $r^{*}_{\sigma(m+1)}=0$. Clearly, constraints (46b) and (46c)
imply that constraints (48b) and (48c) are satisfied by
$\\{\hat{\Delta}_{j},\hat{U}_{ij}^{l},\hat{V}_{i}^{k}\\}$. Also, we have

$\sum_{j=1}^{m}\hat{Q}_{j}\Delta_{j}=\sum_{j=1}^{m}r^{*}_{\sigma(j)}\cdot(\hat{Q}_{j}-\hat{Q}_{j-1})=\sum_{j=1}^{m}r^{*}_{\sigma(j)}\cdot
g_{\sigma(j)}=1$

where the last equation follows from constraint (46e). Thus, our proof is
completed. $\Halmos$

##### Proof of Lemma 3.2.

We prove stronger results by induction. First, we show that for any $i$, it
holds that

$\sum_{l^{\prime}=l}^{k}x_{i}^{l^{\prime}}=\Pr[\sum_{i^{\prime}<i}\mathrm{Ber}(\tau_{i^{\prime}})<k-l+1],\leavevmode\nobreak\
\leavevmode\nobreak\ \forall l=1,\ldots,k$ (49)

We prove (49) by induction on $i$. When $i=1$, clearly, for any $l=1,\dots,k$,
we have

$\sum_{l^{\prime}=l}^{k}x_{1}^{l^{\prime}}=1=\Pr[0<k-l+1]=\Pr[\sum_{i^{\prime}<1}\mathrm{Ber}(\tau_{i^{\prime}})<k-l+1]$

which implies that (49) holds. We now assume that (49) holds for $i$, and we
consider $i+1$. For any $l=1,\ldots,k$, we have that

$x_{i+1}^{l}=x_{i}^{l}-y_{i}^{l}+y_{i}^{l+1}=(1-\tau_{i})\cdot
x_{i}^{l}+\tau_{i}\cdot x_{i}^{l+1}$

where we denote $x_{i}^{k+1}=0$. Thus, we have

$\sum_{l^{\prime}=l}^{k}x_{i+1}^{l^{\prime}}=(1-\tau_{i})\cdot\sum_{l^{\prime}=l}^{k}x_{i}^{l^{\prime}}+\tau_{i}\cdot\sum_{l^{\prime}=l+1}^{k}x_{i}^{l^{\prime}}$

On the other hand, conditioning whether $\mathrm{Ber}(\tau_{i})=1$, we have

$\displaystyle\Pr[\sum_{i^{\prime}<i+1}\mathrm{Ber}(\tau_{i^{\prime}})<k-l+1]$