Jiang, Ma and Zhang

Multi-unit Prophet Inequalities and Online Knapsack

Tight Guarantees for Multi-unit Prophet Inequalities and Online Stochastic
Knapsack

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

$\dagger\leavevmode\nobreak\ $Department of Technology, Operations &
Statistics, Stern School of Business, New York University
$\ddagger\leavevmode\nobreak\ $Decision, Risk, and Operations Division,
Graduate School of Business, Columbia University

Abstract: Prophet inequalities are a useful tool for designing online
allocation procedures and comparing their performance to the optimal offline
allocation. In the basic setting of $k$-unit prophet inequalities, the well-
known procedure of Alaei (2011) with its celebrated performance guarantee of
$1-\frac{1}{\sqrt{k+3}}$ has found widespread adoption in mechanism design and
general online allocation problems in online advertising, healthcare
scheduling, and revenue management. Despite being commonly used to derive
approximately-optimal algorithms for multi-resource allocation problems that
suffer from the curse of dimensionality, the tightness of Alaei’s procedure
for a given $k$ has remained unknown. In this paper we resolve this question,
characterizing the optimal procedure and tight bound, and consequently
improving the best-known guarantee for $k$-unit prophet inequalities for all
$k>1$.

We also consider the more general online stochastic knapsack problem where
each individual allocation can consume an arbitrary fraction of the initial
capacity. Here we introduce a new “best-fit” procedure with a performance
guarantee of $\frac{1}{3+e^{-2}}\approx 0.319$, which we also show is tight
with respect to the standard LP relaxation. This improves the previously best-
known guarantee of 0.2 for online knapsack. Our analysis differs from existing
ones by eschewing the need to split items into “large” or “small” based on
capacity consumption, using instead an invariant for the overall utilization
on different sample paths. Finally, we refine our technique for the unit-
density special case of knapsack, and improve the guarantee from 0.321 to
0.3557 in the multi-resource appointment scheduling application of Stein et
al. (2020).

All in all, our results imply tight Online Contention Resolution Schemes for
$k$-uniform matroids and the knapsack polytope, respectively, which has
further implications.

This version from June 6th, 2022. A preliminary version appeared in SODA2022.

##  1 Introduction

Online resource allocation problems arise in many domains, such as online
advertising, healthcare operations, and revenue management. In these problems
the decision-maker faces a sequence of stochastically-generated queries, and
must irrevocably assign each query to be served by a resource as it arrives
online. The resources have limited capacities, and the objective is to
maximize the cumulative reward collected from serving queries over a finite
time horizon. Due to the curse of dimensionality caused by having multiple
resources, this problem is deemed generally intractable, and it is of central
interest in many academic communities to derive approximately-optimal
algorithms.

A keystone ingredient for algorithm design throughout these communities has
been to start with a Linear Programming (LP) relaxation, which is also known
as the ex-ante, fluid, or deterministic relaxations. The LP relaxation
decomposes the multi-resource allocation problem into single-resource
subproblems, which allows for the capacity of each resource to be controlled
separately. Deriving an approximation guarantee relative to the LP for each
individual resource, which can be called a prophet inequality, then implies
the same approximation guarantee in the original multi-resource problem (see
e.g. Alaei et al. (2012); Alaei (2014); Gallego et al. (2015); Wang et al.
(2018); Feng et al. (2020); we also formalize this reduction in Section 3.1).
Once reduced to single-resource subproblems, the guarantees that are possible
depend on whether a resource’s capacity: 1) takes the form of $k$ discrete
units that are consumed one at a time; or 2) an arbitrary amount of its
capacity may be needed to serve a single query.

In this paper we derive the best-possible guarantees for the single-resource
subproblem in both cases 1) and 2) above, resolving long lines of
investigation. Specifically, the $k$-unit setting described in 1) originated
from Hajiaghayi et al. (2007), and a celebrated guarantee of $1-1/\sqrt{k+3}$
was derived by Alaei (2011) through a ?Magician’s problem?. These guarantees
have been recently improved in Wang et al. (2018); Chawla et al. (2020), and
in this paper we fully resolve (see Table 1 and Figure 1) the question of
$k$-unit prophet inequalities relative to the LP. Meanwhile, for 2) above
which we will call the knapsack setting, we derive the tight guarantee of
$\frac{1}{3+e^{-2}}\approx 0.319$ which improves earlier results of Dutting et
al. (2020) and Alaei et al. (2013). We emphasize that our results can be
directly applied to improve the guarantees in all of the papers cited thus
far, among others (which we discuss in Section 2). The tightness of our
results also characterizes the limits of any approach that seeks
approximately-optimal algorithms through the LP relaxation.

Table 1: Our tight ratios for multi-unit prophet inequalities. The previous lower bounds are obtained as the maximum of the ratios in Alaei (2011); Chawla et al. (2020). The previously best-known upper bounds were 1/2 for $k=1$ and $1-e^{-k}k^{k}/k!$ for $k>1$, with the latter inherited from the ?correlation gap? in the i.i.d. special case (see Yan, 2011). value of $k$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
---|---|---|---|---|---|---|---|---
Existing lower bounds | 0.5000 | 0.5859 | 0.6309 | 0.6605 | 0.6821 | 0.6989 | 0.7125 | 0.7240
Our tight ratios | 0.5000 | 0.6148 | 0.6741 | 0.7120 | 0.7389 | 0.7593 | 0.7754 | 0.7887
Existing upper bounds | 0.5000 | 0.7293 | 0.7760 | 0.8046 | 0.8245 | 0.8394 | 0.8510 | 0.8604

In order to obtain the tight guarantees, it is sufficient to consider a
reduced problem, called Online Contention Resolution Scheme (OCRS) that
generalizes the Magician’s problem in the $k$-unit setting and can capture the
knapsack setting as well. Then, our $k$-unit result is derived through a new
LP that re-interprets the OCRS problem, whose dual has a structured optimal
solution, which allows us to solve the adversary’s outer problem over
instances to minimize the algorithm’s guarantee. Meanwhile, our knapsack
result is derived through a new ?best-fit? algorithm for the OCRS problem,
motivated by the bin packing problem, which allows us to establish the tight
guarantee of $\frac{1}{3+e^{-2}}\approx 0.319$ using an invariant. As a
practical takeaway, our work suggests a stark contrast between how resources
should be allocated in cases 1) and 2) above—in 1), the decision-maker wants
to have a small amount of each resource remaining; whereas in 2), the
decision-maker wants resources to either be fully utilized or have large
amounts remaining. Our theoretical techniques are also general and can be
adapted to other settings—in fact, we show that in the unit-density knapsack
setting, our invariant method leads to an improved guarantee of 0.355, and
hence our best-fit algorithm beats the state-of-the-art 0.321-approximate
algorithm of Stein et al. (2020) in their healthcare scheduling problem. We
now explain the OCRS problem and elaborate on our new techniques to solve the
single-resource subproblems in cases 1) and 2).

Figure 1: Our tight ratios in comparison to the previously best-known
guarantees from Alaei (2011); Chawla et al. (2020) and the previously best-
known upper bounds (see Yan, 2011).

###  1.1 New Techniques for $k$-unit Prophet Inequalities

We formalize what we mean by deriving an approximation guarantee relative to
the LP for a single resource, which enables our approximation algorithms for
the multi-resource problem. In fact, it suffices to solve a simpler problem
where each query for the single resource has a binary state, which can be
called the $k$-unit Online Contention Resolution Scheme (OCRS) problem. The
formal reduction to this problem is presented in Section 3.2, and we now
describe how we solve this problem optimally.

######  Definition 1 ($k$-unit OCRS Problem)

There is a sequence of queries $t=1,\ldots,T$, each of which is active
independently according to a known probability $p_{t}$. Whether a query is
active is sequentially observed, and active queries can be immediately served
or rejected, while inactive queries must be rejected. At most $k$ queries can
be served in total, and it is promised that $\sum_{t}p_{t}\leq k$. The goal of
an online algorithm is to serve every query $t$ with probability at least
$\gamma$ conditional on it being active, for a constant $\gamma\in[0,1]$ as
large as possible, potentially with the aid of randomization.

It is easy to see111 For example, suppose that $k=1$, $T=2$, and
$p_{1}=p_{2}=1/2$. If we attempt to set $\gamma=1$, then the first query would
be served ex ante w.p. 1/2, i.e., whenever it is active. This means that half
the time no capacity would remain for query 2, i.e., half the time query 2 is
active it does not get served. For this example, the optimal value of $\gamma$
can be calculated to be 2/3.  that despite $\bm{p}$ being fractionally
feasible, a guarantee of $\gamma=1$ in 1 is generally impossible. The work of
Alaei (2011) implies a solution to 1 with $\gamma=1-\frac{1}{\sqrt{k+3}}$.
Presented in the slightly different context of a “$\gamma$-Conservative
Magician,” Alaei’s procedure has the further appealing property that it does
not need to know vector $\bm{p}$ in advance, as long as each $p_{t}$ is
revealed when query $t$ is observed, and it is promised that
$\sum_{t}p_{t}\leq k$. However, it has remained unknown whether Alaei’s
$\bm{p}$-agnostic procedure or its analyzed bound of
$\gamma=1-\frac{1}{\sqrt{k+3}}$ is tight for an arbitrary positive integer
$k$. In this paper we resolve this question, in the following steps.

  1. 1.

Under the assumption that $\bm{p}$ is known, we formulate the optimal $k$-unit
OCRS problem using a new LP. This LP tracks the probability distribution of
the capacity utilization, which must lie in $\\{0,\frac{1}{k},\ldots,1\\}$,
over time $t=1,\ldots,T$. The decision variables correspond to subdividing and
selecting sample paths at each time $t$, with total measure exactly $\gamma$,
on which the algorithm will serve query $t$ whenever it is active. This
selection is constrained to sample paths with at least $\frac{1}{k}$ capacity
remaining, which is enforced in the LP through tracking the capacity
utilization. Finally, $\gamma$ is also a decision variable, with the objective
being to maximize $\gamma$.

  2. 2.

For an arbitrary $\bm{p}$, we characterize an optimal solution to this LP
based on the structure of its dual. The optimal selection prioritizes sample
paths with the least capacity utilized, at every time $t$, irrespective of the
values $p_{t+1},p_{t+2},\ldots$ in the future. Such a solution corresponds to
the $\gamma$-Conservative Magician from Alaei (2011), except that $\gamma$,
instead of being fixed to $1-\frac{1}{\sqrt{k+3}}$, is set to an optimal value
that depends on the vector $\bm{p}$.

  3. 3.

We derive a closed-form expression for this optimal value of $\gamma$ as a
function of $\bm{p}$. We show that $\gamma$ is minimized when $p_{t}=k/T$ for
each $t$ and $T\to\infty$, corresponding to a Poisson distribution of rate
$k$. We characterize this infimum value of $\gamma$ using an ODE and provide
an efficient procedure for computing it numerically.

For any $k$, let $\gamma^{*}_{k}$ denote the infimum value of $\gamma$
described in Step 3 above. The conclusion is that setting
$\gamma=\gamma^{*}_{k}$ is a feasible solution to 1, with
$\gamma^{*}_{k}>1-\frac{1}{\sqrt{k+3}}$ for all $k>1$, achieved using the
$\bm{p}$-agnostic procedure described above. Moreover, the guarantee of
$\gamma^{*}_{k}$ is the best-possible, since even a procedure that knows
$\bm{p}$ in advance cannot do better than a $\gamma$-Conservative Magician
with an optimized value of $\gamma$, which in the Poisson worst case can be as
low as $\gamma^{*}_{k}$.

Comparison to Alaei et al. (2012). $k$-unit prophet inequalities have been
analyzed using LP’s before in Alaei et al. (2012), who formulate a primal LP
encoding the adversary’s problem of minimizing an online algorithm’s optimal
dynamic programming value. They then use an auxiliary “Magician’s problem,”
analyzed through a “sand/barrier” process, to construct a feasible dual
solution with $\gamma=1-\frac{1}{\sqrt{k+3}}$. By contrast, we directly
formulate the $k$-unit OCRS problem using an LP under the assumption that the
vector $\bm{p}$ is known. Our LP dual along with complementary slackness
allows us to establish the structure of the optimal $k$-unit OCRS, showing
that it indeed corresponds to a $\gamma$-Conservative Magician. However, in
our case $\gamma$ is set to a value dependent on $\bm{p}$, which we show is
always at least $\gamma^{*}_{k}$, and strictly greater than
$1-\frac{1}{\sqrt{k+3}}$ for all $k>1$.

Comparison to Wang et al. (2018). The values of $\gamma^{*}_{k}$ we derive
have previously appeared in Wang et al. (2018) through the stochastic analysis
of a “reflecting” Poisson process. Our work differs by establishing optimality
for these values $\gamma^{*}_{k}$, as the solutions to a sequence of
optimization problems from our framework. Moreover, their paper assumes
Poisson arrivals to begin with, while we allow arbitrary probability vectors
$\bm{p}$ and show the limiting Poisson case to be the worst case.

The classical prophet inequality comparison. We should note that classically
in the $k$-unit prophet inequality problem, the goal is to compute the worst-
case performance of an online algorithm, who sequentially observes independent
draws from known distributions and can keep $k$ of them, and compare instead
to a prophet, whose performance is the expected sum of the $k$ highest
realizations. The prophet’s performance is upper-bounded by the LP relaxation,
so our guarantees that are tight relative to the LP also imply the best-known
prophet inequalities to date for all $k>1$. We do give an example that
demonstrates this guarantee to be “almost” tight even when comparing to the
weaker prophet benchmark. Through our LP’s and complementary slackness, we can
convert the Poisson worst case for the $k$-unit OCRS problem into an explicit
instance of $k$-unit prophet inequalities, on which the reward of any online
algorithm relative to the LP relaxation is upper-bounded by $\gamma^{*}_{k}$.
Moreover, by modifying such an instance, we also provide a new upper bound of
$0.6269$ relative to the prophet, when $k=2$ (Proposition 1). Since
$\gamma^{*}_{2}\approx 0.6148$, this shows that not much improvement beyond
$\gamma^{*}_{k}$ is possible relative to the prophet when $k=2$.

###  1.2 New Techniques for the Knapsack Setting

Under the knapsack setting, we formalize the problem of comparing an online
algorithm to the LP relaxation for a single resource, which enables our
approximation algorithm for the general multi-resource problem. Following the
reduction described in Section 3.2, it is enough to consider a simpler problem
where the size of each query $t$ is realized as $d$ independently with a given
probability $p_{t}(d)$. We call this problem the knapsack OCRS problem.

######  Definition 2 (Knapsack OCRS Problem)

There is a sequence of queries $t=1,\ldots,T$, and for each query $t$, the
size is realized as $d\in[0,1]$ independently with a known probability
$p_{t}(d)$. After the query’s size is observed, the query must be immediately
served or rejected. The total size of queries served cannot exceed 1, and it
is promised that $\sum_{t}\sum_{d}p_{t}(d)\cdot d\leq 1$. The goal of an
online algorithm is to serve every query $t$ with probability at least
$\gamma$ conditional on the size being realized to $d$, for each $d\in[0,1]$,
and for a constant $\gamma\in[0,1]$ as large as possible.

Similar to our approach for the multi-unit setting, we design solution for the
knapsack OCRS by tracking the distribution of capacity utilization over time.
For each size realization $d\in[0,1]$, we select for each query $t$ a
$\gamma$-measure of sample paths on which it should be served whenever the
size is realized as $d$, under the constraint that these paths have a current
utilization of at most $1-d$. However, different from the multi-unit setting,
in the knapsack setting, we need to always maintain a $\gamma$-measure of
sample paths on which utilization is 0, in case an item $T$ with size
realization $d_{T}=1$ and $p_{T}(d_{T})=\varepsilon$ arrives at the end.
Accordingly, in stark contrast to the $\gamma$-Conservative Magician, our
knapsack procedure selects for each query and each size realization the sample
paths with the most capacity utilized, on which that query still fits. We dub
this procedure a “Best-fit Magician.”222This is because it resembles the
“best-fit” heuristic for bin packing (Garey et al., 1972). In the more general
knapsack setting, capacity utilization can only be tracked in polynomial time
after discretizing size realizations by $1/K$ for some large integer $K$;
nonetheless, we will show (in Section 6.1) that this loses a negligible
additive term of $O(1/K)$ in the guarantee.

To derive the maximum feasible guarantee $\gamma$ for a Best-fit Magician, we
note that the expected capacity utilization over the sample paths is
$\gamma\cdot\sum_{t}\sum_{d}p_{t}(d)\cdot d$, which is always upper-bounded by
$\gamma$, since $\sum_{t}\sum_{d}p_{t}(d)\cdot d\leq 1$. Therefore, to lower-
bound the measure of sample paths with 0 utilization, it suffices to upper-
bound the measure of sample paths whose utilization is small but non-zero. To
do so, we use the rule of the Best-fit Magician, namely, that an arriving
query with a size realization $d$ will only be served on a previously empty
sample path if there is less than a $\gamma$-measure of sample paths with
utilization in $(0,1-d]$. Based on this fact, we derive an invariant that
holds after each query $t$, and upper-bounds the measure of sample paths with
utilization in $(0,b]$ by a decreasing exponential function of the measure
with utilization in $(b,1-b]$, for any small size $b\in(0,1/2]$. This allows
us to show that a $\gamma$ as large as $\frac{1}{3+e^{-2}}\approx 0.319$
allows for a $\gamma$-measure of sample paths to have 0 utilization at all
times, and hence is feasible. The Best-fit Magician is also agnostic to
knowing the probabilities $\\{p_{t}(d)\\}_{\forall t,\forall d}$ in advance,
as long as it is promised that $\sum_{t}\sum_{d}p_{t}(d)\cdot d\leq 1$.
Nonetheless, we construct a counterexample showing it to be optimal, in that
$\gamma=\frac{1}{3+e^{-2}}$ is an upper bound on the guarantee for the
knapsack OCRS problem even if the probabilities $\\{p_{t}(d)\\}_{\forall
t,\forall d}$ are known in advance.

To our knowledge, our analysis differs from all existing ones for knapsack in
an online setting (Dutting et al., 2020; Stein et al., 2020; Feldman et al.,
2021) by eschewing the need to split queries into “large” vs. “small” based on
their size (usually, whether their size is greater than 1/2). In fact, we show
that any algorithm that packs large and small queries separately is limited to
$\gamma\leq 0.25$ in our problem (Proposition 2), whereas our tight guarantee
is $\gamma=\frac{1}{3+e^{-2}}\approx 0.319$.

Our result can be further improved in a case of unit-density online knapsack,
where the random size and reward of a query are always identical. Indeed,
since it is no longer possible for a small query to have a high reward, we no
longer need to guarantee a uniform lower bound $\gamma$ on the probability of
serving any query with any size realization. Instead, we show that our
invariant still holds for a decreasing sequence of service probabilities
$\gamma_{1}\geq\cdots\geq\gamma_{T}$, and devise a particular sequence that
guarantees an expected reward that is at least 0.3557 times the optimal LP
value. This then implies a 0.3557-approximation for the multi-resource
appointment scheduling problem of Stein et al. (2020), improving upon their
0.321-approximation.

Comparison to Alaei et al. (2013). Another related setting is the online
stochastic generalized assignment problem of Alaei et al. (2013), for which
the authors establish a guarantee of $1-\frac{1}{\sqrt{k}}$, when each query
can realize a random size that is at most $1/k$. They eliminate the
possibility of “large” queries by imposing $k$ to be at least 2, showing that
a constant-factor guarantee is impossible when $k=1$. Although our problem can
be generalized to random sizes, we need to assume that size is observed before
the algorithm makes a decision, whereas in their problem size is randomly
realized after the algorithm decides to serve a query. This distinction allows
our problem to have a constant-factor guarantee that holds even when queries
can have size 1. Moreover, our procedure starkly contrasts with theirs in that
we prioritize selecting sample paths with the most capacity utilized on which
a query fits, while they prioritize sample paths with the least capacity
utilized.

###  1.3 Roadmap

Section 3 formalizes the model/notation for our general problem, illustrates
the LP reduction approach, and establishes the equivalence between the single-
resource problem and the OCRS problem. Section 4 presents all of our results
for $k$-unit prophet inequalities, in which the sizes are always $1/k$.
Section 5 considers the single-resource problem under the knapsack setting.
Section 6 discusses the polynomial-time implementation of our algorithm under
the knapsack setting, and presents our improvement in the unit-density special
case.

##  2 Further Related Work

Online knapsack. The discrete version of the online stochastic knapsack
problem as studied in this paper, which generalizes the $k$-unit prophet
inequality problem, was originally posed in Papastavrou et al. (1996) to model
classical applications in operations research such as freight transportation
and scheduling. We derive the best competitive ratios for this problem known
to date, for both the general and unit-density settings, which extend to
multiple knapsacks. We should point out though that in the unit-density
setting with a single knapsack, a competitive ratio of 1/2, better than our
guarantee of 0.3557, is possible under any fixed sequence of adversarial
arrivals (Han et al., 2015). However, such a guarantee fails333An additional
factor of 1/2 would be lost, resulting in a guarantee of only 1/4; see Ma et
al. (2019). In fact, a guarantee of 1/2 relative to the LP is impossible, due
to the upper bound of 0.432 presented in our Proposition 3. to extend to
multiple knapsacks, whereas our guarantee of 0.3557, which holds relative to
the LP, directly extends there, following the same reduction argument as in
Stein et al. (2020).

Prophet inequalities. Prophet inequalities were originally posed in the
statistics literature by Krengel and Sucheston (1978). Due to their
implications for posted pricing and mechanism design, prophet inequalities
have been a surging topic in algorithmic game theory since the seminal works
of Hajiaghayi et al. (2007); Chawla et al. (2010); Yan (2011); Alaei (2011).
Of particular interest in these works are bounds for $k$-item prophet
inequalities, and in this paper we improve such bounds for all $k>1$, and show
that our bounds are tight relative to the LP relaxation, under an adversarial
arrival order. More recently, prophet inequalities have also been studied
under random order (Esfandiari et al., 2017; Correa et al., 2021; Arnosti and
Ma, 2021), free order (Correa et al., 2021; Beyhaghi et al., 2021), or IID
arrivals (Hill and Kertz, 1982; Correa et al., 2017), with $k$-unit prophet
inequalities in particular being studied by Beyhaghi et al. (2021) under free
order and Arnosti and Ma (2021) under random order. Prophet inequalities have
also been studied under the batched setting (Alaei et al., 2022) with
applications to descending-price auctions, and also been used as algorithmic
subroutine for other revenue management problems (e.g. Cominetti et al.
(2010); Alaei et al. (2021)). A survey of recent results in prophet
inequalities can be found in Correa et al. (2019).

Online Contention Resolution Schemes (OCRS). A guarantee of $\gamma$ for our
problem in 1 (resp. 2) is identical to a $\gamma$-selectable OCRS for the
$k$-uniform matroid (resp. knapsack polytope) as introduced in Feldman et al.
(2021). However, we should clarify some assumptions about what is known
beforehand and the choice of arrival order. Our OCRS hold against an online
adversary, who can adaptively choose the next query to arrive, but does not
know the realizations of queries yet to arrive. We show that the guarantee
does not improve against the weakest adversary, who has to reveal the arrival
order in advance. However, our OCRS do not satisfy the greedy property, and
consequently do not hold against the almighty adversary, who knows the
realizations of all queries before having to choose the order.

In Feldman et al. (2021), the authors derive a 1/4-selectable444 Lee and
Singla (2018) have improved this to a 1/2-selectable OCRS for general
matroids, against the weakest adversary. Our guarantees of $\gamma^{*}_{k}$
are all greater than 1/2 and hold against the online adversary, but in the
special case of $k$-uniform matroids.  greedy OCRS for general matroids, and a
$0.085$-selectable greedy OCRS for the knapsack polytope, both of which hold
against an almighty adversary. We establish significantly improved
selectabilities against the weaker online adversary, and, importantly, show
that our guarantees are tight for our setting.

Magician’s problem. Our algorithms do enjoy a property not featured in the
OCRS setting though: they need not know the universe of elements in advance,
holding even if the adversary can adaptively “create” the $p_{t}$ (and
$d_{t}$) of the next query $t$, under the promise that $\sum_{t}p_{t}d_{t}\leq
1$. This property is inherited from the Magician’s problem, introduced by
Alaei (2011) as a powerful black box for approximately solving combinatorial
auctions. Our work fully resolves555 The main difference in the Magician’s
problem is that a query must be selected before it is known whether it is
active, and, if so, is irrevocably served. The goal is to select each query
with an ex-ante probability at least $\gamma$. Our problem can be
reinterpreted as selecting a $\gamma$-measure of sample paths on which each
query should be served whenever it is active, which is completely equivalent.
Therefore, all of our results also hold for Alaei’s Magician problem and its
applications.  his $k$-unit Magician problem, showing his
$\gamma$-Conservative Magician to be optimal, and, importantly, showing how to
find the optimal value $\gamma=\gamma^{*}_{k}$, which is greater than the
value of $\gamma=1-\frac{1}{\sqrt{k+3}}$, for all $k>1$. This improves all of
the guarantees for combinatorial auctions, summarized in Alaei (2014), that
depend on this value of $\gamma$.

##  3 Online Generalized Assignment

In this section, we formalize the model and the notations for a generalized
online multi-resource assignment problem, as well as illustrate the LP
reduction approach that reduces the multi-resource problem into single-
resource subproblems. We further show that the single-resource problem can be
simplified equivalently into an OCRS problem. We note that in even more
general settings where there is stochasticity after each decision in which
resource gets consumed, the same reduction still holds (see e.g. the online
assortment problem in Ma et al. (2021)). However, for simplicity, we restrict
to the online generalized assignment problem in this paper which suffices to
illustrate our contribution.

We consider an online generalized assignment problem over $T$ discrete time
periods. We assume that there are $m$ resources and the initial capacity of
each resource is without loss of generality scaled to $1$. At the beginning of
each period $t=1,2,\dots,T$, a query arrives, denoted by query $t$, and is
associated with a non-negative stochastic reward
$\mathbf{\tilde{r}}_{t}=(\tilde{r}_{t1},\dots,\tilde{r}_{tm})$ and a positive
stochastic size
$\mathbf{\tilde{d}}_{t}=(\tilde{d}_{t1},\dots,\tilde{d}_{tm})$, where
$(\mathbf{\tilde{r}}_{t},\mathbf{\tilde{d}}_{t})$ is assumed to follow a joint
distribution $F_{t}(\cdot)$ that can be inhomogeneous in time and is
independent across time. After the value of
$(\mathbf{\tilde{r}}_{t},\mathbf{\tilde{d}}_{t})$ is revealed, the decision
maker has to decide irrevocably whether to serve or reject this query. If
served, the decision maker also needs to assign a resource
$j\in\\{1,\ldots,m\\}$ to serve query $t$. Then, query $t$ will take up
$\tilde{d}_{tj}$ capacity of resource $j$ and a reward $\tilde{r}_{tj}$ will
be collected. If rejected, then no reward is collected and no resource is
consumed. The goal is to maximize the total collected reward subject to the
capacity constraint of each resource.

We classify the elements described above into two categories: (i) the problem
setup $\mathcal{H}=(F_{1},F_{2},\dots,F_{T})$ denoting all distributions; and
(ii) the realization of the rewards and sizes of the arriving queries
$\bm{I}=((\mathbf{\tilde{r}}_{1},\mathbf{\tilde{d}}_{1}),(\mathbf{\tilde{r}}_{2},\mathbf{\tilde{d}}_{2}),\dots,(\mathbf{\tilde{r}}_{T},\mathbf{\tilde{d}}_{T}))$.

Any online policy $\pi$ for the decision maker can be specified by a set of
decision variables $\\{x^{\pi}_{jt}\\}_{j=1,\dots,m,t=1,\dots,T}$, where
$x^{\pi}_{jt}$ is a binary variable and denotes whether query $t$ is served by
resource $j$. Note that if $\pi$ is a randomized policy, then $x^{\pi}_{jt}$
is a random binary variable. A policy $\pi$ is feasible if and only if $\pi$
is non-anticipative; i.e., for each $t$, the value of $x^{\pi}_{jt}$ can only
depend on the problem setup $\mathcal{H}$ and the rewards and the sizes of the
arriving queries up to query $t$, denoted by
$\\{(\mathbf{\tilde{r}}_{1},\mathbf{\tilde{d}}_{1}),\dots,(\mathbf{\tilde{r}}_{t},\mathbf{\tilde{d}}_{t})\\}$.
Moreover, $\pi$ needs to satisfy the following capacity constraint:

$\sum_{t=1}^{T}\tilde{d}_{jt}\cdot x^{\pi}_{jt}\leq 1,\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall j=1,\dots,m.$ (1)

and the constraint $\sum_{j=1}^{m}x^{\pi}_{jt}\leq 1$ for all $t=1,\dots,T$.
The total collected reward of policy $\pi$ is denoted by
$V^{\pi}(\bm{I})=\sum_{t=1}^{T}\sum_{j=1}^{m}\tilde{r}_{jt}\cdot
x^{\pi}_{jt}$, and the expected total collected reward of policy $\pi$ is
denoted by $\mathbb{E}_{\pi,\bm{I}\sim\mathcal{H}}[V^{\pi}(\bm{I})]$.

We compare to the prophet, who can make decisions based on the knowledge of
the realizations of all the queries. Similarly, the optimal offline decision
is specified by $\\{x^{\text{off}}_{jt}(\bm{I})\\}_{j=1,\dots,m,t=1,\dots,T}$,
which is the optimal solution to the following offline problem

$\displaystyle V^{\text{off}}(\bm{I})=$ $\displaystyle\leavevmode\nobreak\
\max\leavevmode\nobreak\ \leavevmode\nobreak\
\sum_{t=1}^{T}\sum_{j=1}^{m}\tilde{r}_{jt}\cdot x_{jt}$ (2)
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
\mbox{s.t.}\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \sum_{t=1}^{T}\tilde{d}_{jt}\cdot x_{jt}\leq
1,\leavevmode\nobreak\ \leavevmode\nobreak\ \forall j=1,\dots,m$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \sum_{j=1}^{m}x_{jt}\leq
1,\leavevmode\nobreak\ \leavevmode\nobreak\ \forall t=1,\dots,T$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
x_{jt}\in\\{0,1\\},\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \forall j,\forall t.$

The prophet’s value is denoted by
$\mathbb{E}_{\bm{I}\sim\mathcal{H}}[V^{\text{off}}(\bm{I})]$. For any feasible
online policy $\pi$, its competitive ratio $\gamma$ is defined as

$\gamma=\inf_{\mathcal{H}}\frac{\mathbb{E}_{\pi,\bm{I}\sim\mathcal{H}}[V^{\pi}(\bm{I})]}{\mathbb{E}_{\bm{I}\sim\mathcal{H}}[V^{\text{off}}(\bm{I})]}.$
(3)

In this paper, however, instead of directly comparing to
$\mathbb{E}_{\bm{I}\sim\mathcal{H}}[V^{\text{off}}(\bm{I})]$, we compare to a
linear programming (LP) upper bound of
$\mathbb{E}_{\bm{I}\sim\mathcal{H}}[V^{\text{off}}(\bm{I})]$, which will be
useful for decomposing into single-resource subproblems.. We consider the
following LP as an upper bound:

$\displaystyle\text{UP}(\mathcal{H})=$ $\displaystyle\leavevmode\nobreak\
\max\leavevmode\nobreak\ \leavevmode\nobreak\
\sum_{t=1}^{T}\mathbb{E}_{(\tilde{\mathbf{r}}_{t},\tilde{\mathbf{d}}_{t})\sim
F_{t}}[\sum_{j=1}^{m}\tilde{r}_{tj}\cdot
x_{tj}(\tilde{\mathbf{r}}_{t},\tilde{\mathbf{d}}_{t})]$ (4)
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
\mbox{s.t.}\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
\sum_{t=1}^{T}\mathbb{E}_{(\tilde{\mathbf{r}}_{t},\tilde{\mathbf{d}}_{t})\sim
F_{t}}[\tilde{d}_{tj}\cdot
x_{tj}(\tilde{\mathbf{r}}_{t},\tilde{\mathbf{d}}_{t})]\leq
1,\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall
j=1,\dots,m$ $\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\sum_{j=1}^{m}x_{tj}(\mathbf{r}_{t},\mathbf{d}_{t})\leq 1,\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall
t,\forall(\mathbf{r}_{t},\mathbf{d}_{t})$ $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ x_{tj}(\mathbf{r}_{t},\mathbf{d}_{t})\geq
0,\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall
t,\forall(\mathbf{r}_{t},\mathbf{d}_{t}).$

Here $\mathcal{H}=(F_{1},\dots,F_{T})$ denotes the problem setup, while
$x_{tj}(\mathbf{r}_{t},\mathbf{d}_{t})$ denotes the probability of assigning
resource $j$ to serve query $t$ conditional on its reward and size vectors
realizing to $\mathbf{r}_{t}=(r_{t1},\dots,r_{tm})$ and
$\mathbf{d}_{t}=(d_{t1},\dots,d_{tm})$, respectively. The following lemma
shows that for a policy $\pi$ to have a competitive ratio of at least
$\gamma$, it suffices that
$\mathbb{E}_{\pi,\bm{I}\sim\mathcal{H}}[V^{\pi}(\bm{I})]$ is at least $\gamma$
times the optimal fractional allocation value $\text{UP}(\mathcal{H})$ for
every setup $\mathcal{H}$.

###### Lemma 1

For all problem setups $\mathcal{H}$, it holds that
$\mathbb{E}_{\bm{I}\sim\mathcal{H}}[V^{\text{off}}(\bm{I})]\leq\text{UP}(\mathcal{H})$.

The proof of Lemma 1 is relegated to the Section A1. In what follows, we will
derive our results based on the optimal solution to $\text{UP}(\mathcal{H})$.

###  3.1 Reduction to Single-resource Problems

In this section, we explain how to reduce the multi-resource problem into
multiple single-resource problems. Denote by
$\\{x^{*}_{tj}(\mathbf{r}_{t},\mathbf{d}_{t})\\}$ the optimal solution to
$\text{UP}(\mathcal{H})$. Then, at each period $t$, after query $t$ has
arrived and the value of $(\mathbf{\tilde{r}}_{t},\mathbf{\tilde{d}}_{t})$ is
revealed, we randomly route query $t$ to a resource $j$ with probability
$x^{*}_{tj}(\mathbf{\tilde{r}}_{t},\mathbf{\tilde{d}}_{t})$. Specifically, we
choose a resource $j$ with probability
$x^{*}_{tj}(\mathbf{\tilde{r}}_{t},\mathbf{\tilde{d}}_{t})$ to be the only
potential resource to serve query $t$ and whether or not query $t$ is served
will depend on the individual serve/reject rule of resource $j$. Note that
this random routing approach has also been applied in previous literature
(Alaei et al., 2012, 2013; Wang et al., 2018; Stein et al., 2020) for reducing
to the single-dimensional setting.

For each resource $j$ and each $t$, we denote by $F_{tj}(\cdot)$ the
distribution of the following random variable:

$(\tilde{r}_{tj},\tilde{d}_{tj})\cdot\text{Ber}(x^{*}_{tj}(\tilde{\bm{r}}_{t},\tilde{\bm{d}}_{t})).$

Here, for each $x^{*}_{tj}(\tilde{\bm{r}}_{t},\tilde{\bm{d}}_{t})$,
$\text{Ber}(x^{*}_{tj}(\tilde{\bm{r}}_{t},\tilde{\bm{d}}_{t}))$ is a Bernoulli
random variable with mean $x^{*}_{tj}(\tilde{\bm{r}}_{t},\tilde{\bm{d}}_{t})$,
where $\text{Ber}(x^{*}_{tj}(\tilde{\bm{r}}_{t},\tilde{\bm{d}}_{t}))=1$ (resp.
$=0$) denotes query $t$ with reward and size
$(\tilde{\bm{r}}_{t},\tilde{\bm{d}}_{t})$ is (resp. not) routed to resource
$j$. Then, we denote $\mathcal{H}_{j}=(F_{1j},\dots,F_{Tj})$ to be the problem
setup faced by resource $j$. Note that

$\sum_{t=1}^{T}\mathbb{E}_{(\tilde{r}_{t},\tilde{d}_{t})\sim
F_{tj}}[\tilde{d}_{t}]=\sum_{t=1}^{T}\mathbb{E}_{(\tilde{\mathbf{r}}_{t},\tilde{\mathbf{d}}_{t})\sim
F_{t}}[\tilde{d}_{tj}\cdot
x^{*}_{tj}(\tilde{\mathbf{r}}_{t},\tilde{\mathbf{d}}_{t})]\leq 1.$

Obviously, we have

$\text{UP}(\mathcal{H}_{j})=\sum_{t=1}^{T}\mathbb{E}_{(\tilde{r}_{t},\tilde{d}_{t})\sim
F_{tj}}[\tilde{r}_{t}]=\sum_{t=1}^{T}\mathbb{E}_{(\tilde{\mathbf{r}}_{t},\tilde{\mathbf{d}}_{t})\sim
F_{t}}[\tilde{r}_{tj}\cdot
x^{*}_{tj}(\tilde{\mathbf{r}}_{t},\tilde{\mathbf{d}}_{t})]$

and we have $\sum_{j=1}^{m}\text{UP}(\mathcal{H}_{j})=\text{UP}(\mathcal{H})$.
Clearly, if an online policy $\pi$ can collect an expected reward of at least
$\gamma\cdot\text{UP}(\mathcal{H}_{j})$ on the problem setup
$\mathcal{H}_{j}$, then, we can simply specify the policy $\pi$ as the
serve/reject rule for each resource after random routing, and the total reward
collected from all resources is lower-bounded by
$\gamma\cdot\sum_{j=1}^{m}\text{UP}(\mathcal{H}_{j})=\gamma\cdot\text{UP}(\mathcal{H})$.
The above discussion is summarized in the following lemma.

###### Lemma 2

To derive an online multi-resource allocation policy with competitive ratio at
least $\gamma$, it suffices to derive an online policy $\pi$ such that
$\mathbb{E}_{\pi,\bm{I}\sim\mathcal{H}_{j}}[V^{\pi}(\bm{I})]\geq\gamma\cdot\text{UP}(\mathcal{H}_{j})$
is satisfied for all single resource instances $\mathcal{H}_{j}$ satisfying
$\sum_{t=1}^{T}\mathbb{E}[\tilde{d}_{t}]\leq 1$.

###  3.2 LP Duality and OCRS

We now analyze the problem faced by each resource. To be specific, we now
assume that there is a single resource with an initial capacity $1$, and each
query $t$ is associated with a random reward $\tilde{r}_{t}$ and a random size
$\tilde{d}_{t}$, where $(\tilde{r}_{t},\tilde{d}_{t})$ follows a given joint
distribution $F_{t}(\cdot)$ but is still realized independently of other
queries. After $(\tilde{r}_{t},\tilde{d}_{t})$ is revealed, the online
decision maker has to decide irrevocably whether or not to serve this query
without violating the capacity constraint. Following Lemma 2, we restrict
$\mathcal{H}$ to describe a single-resource problem instance and the
constraint $\sum_{t=1}^{T}\mathbb{E}[\tilde{d}_{t}]\leq 1$ is satisfied.

We now show that in order to obtain the tight guarantee, it is sufficient to
consider knapsack OCRS problem (1 for the $k$-unit setting and 2 for the
knapsack setting) and we obtain a new LP to work with. In a preliminary
version (Jiang et al., 2022) of this work, we establish the sufficiency under
a special case where the size of each query is deterministic. We generalize to
the setting where the size can be random, through (infinite) LP duality.

We begin with considering the optimal online policy given by dynamic
programming (DP). For notation brevity, we denote by
$\omega_{t}=(r_{t},d_{t})$ a scenario for query $t$, and we denote by
$r(\omega_{t})$ and $d(\omega_{t})$ the reward and size of query $t$ under
scenario $\omega_{t}$. Denote by $V^{*}_{t}(c_{t})$ the “value-to-go” function
at period $t$ with remaining capacity $c_{t}$. We have the following backward
induction for the DP:

$V^{*}_{t}(c_{t})=V^{*}_{t+1}(c_{t})+\mathbb{E}_{\omega_{t}\sim
F_{t}}[\underbrace{\max\left\\{0,1_{\\{c_{t}\geq
d(\omega_{t})\\}}\cdot(r(\omega_{t})+V^{*}_{t+1}(c_{t}-d(\omega_{t}))-V^{*}_{t+1}(c_{t}))\right\\}}_{\text{marginal\leavevmode\nobreak\
increase}}],$ (5)

for all $t$ and $0\leq c_{t}\leq 1$, where $V^{*}_{T+1}(\cdot)=0$. Having this
notation, we are interested in characterizing the quantity

$\displaystyle\inf_{\mathcal{H}}\frac{V^{*}_{1}(1)}{\text{UP}(\mathcal{H})}.$
(6)

Note that under the constraint $\sum_{t=1}^{T}\mathbb{E}_{\omega_{t}\sim
F_{t}}[d(\omega_{t})]\leq 1$, we must have
$\text{UP}(\mathcal{H})=\sum_{t=1}^{T}\mathbb{E}_{\omega_{t}\sim
F_{t}}[r(\omega_{t})]$ (because setting all the $x$-values to 1 forms a
feasible solution to the LP describing $\text{UP}(\mathcal{H})$). We scale the
values of $\tilde{r}_{t}$ so that
$\text{UP}(\mathcal{H})=\sum_{t=1}^{T}\mathbb{E}_{\omega_{t}\sim
F_{t}}[r(\omega_{t})]=1$. We denote by $p_{t}(\omega_{t})$ the probability
that scenario $\omega_{t}$ happens for query $t$, and
$p_{t}(d_{t})=\sum_{\omega_{t}:d(\omega_{t})=d_{t}}p_{t}(\omega_{t})$ the
probability that the size of query $t$ is realized as $d_{t}$. With some
further massaging, we can re-express (6) as the infimum value of an LP
Primal$(\bm{p},\bm{D})$, as well as its dual which we denote by
Dual$(\bm{p},\bm{D})$, over $\bm{p}=\\{p_{t}(\omega_{t})\\}_{\forall t,\forall
d_{t}}$ and $\bm{D}=\\{d_{t}\\}_{\forall t,\forall d_{t}}$ such that
$\sum_{t=1}^{T}\sum_{d_{t}}p_{t}(d_{t})\cdot d_{t}\leq 1$. The following lemma
formalizes this fact, where the proof is relegated to Section A2.

###### Lemma 3

It holds that

$\inf_{\mathcal{H}}\frac{V^{*}_{1}(1)}{\text{UP}(\mathcal{H})}=\inf_{(\bm{p},\bm{D}):\sum_{t=1}^{T}\sum_{d_{t}}p_{t}(d_{t})\cdot
d_{t}\leq
1}\text{Primal}({\bm{p},\bm{D}})=\inf_{(\bm{p},\bm{D}):\sum_{t=1}^{T}\sum_{d_{t}}p_{t}(d_{t})\cdot
d_{t}\leq 1}\text{Dual}({\bm{p},\bm{D}}).$

where the formulations of $\text{Primal}({\bm{p},\bm{D}})$ and
$\text{Dual}({\bm{p},\bm{D}})$ are given in and (7) and (8).

We work with the following LP

$\displaystyle\text{Primal}(\bm{p},\bm{D})=$
$\displaystyle\leavevmode\nobreak\ \min\leavevmode\nobreak\
\leavevmode\nobreak\ V_{1}(1)$ (7) $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ \mbox{s.t.}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ V_{t}(c_{t})\geq
V_{t+1}(c_{t})+\mathbb{E}_{\omega_{t}\sim F_{t}}[1_{\\{d(\omega_{t})\leq
c_{t}\\}}\cdot W_{t}(\omega_{t},c_{t})],\leavevmode\nobreak\ \forall t,\forall
c_{t}$ (7a) $\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ W_{t}(\omega_{t},c_{t})\geq
r(\omega_{t})+V_{t+1}(c_{t}-d(\omega_{t}))-V_{t+1}(c_{t}),\leavevmode\nobreak\
\forall t,\forall\omega_{t},\forall c_{t}\geq d(\omega_{t})$ (7b)
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\sum_{t=1}^{T}\sum_{\omega_{t}}r(\omega_{t})\cdot p_{t}(\omega_{t})=1$ (7c)
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
V_{T+1}(c)=0,\leavevmode\nobreak\ \forall c$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
V_{t}(c)\in\mathbb{R},W_{t}(\omega_{t},c_{t})\geq 0,r(\omega_{t})\geq 0$

In this LP $\text{Primal}(\bm{p},\bm{D})$, decision variable $V_{t}(c_{t})$
represents the dynamic programming value-to-go $V^{*}_{t}(c_{t})$, decision
variable $W_{t}(\omega_{t},c_{t})$ represents the marginal increase term given
scenario $\omega_{t}$ for query $t$, and decision variable $r(\omega_{t})$
must be scaled to respect
$\text{UP}(\mathcal{H})=\sum_{t=1}^{T}\mathbb{E}_{\omega_{t}\sim
F_{t}}[r(\omega_{t})]=1$. It is known that in an optimal solution, the
decision variables $V_{t}(c_{t})$ equal $V^{*}_{t}(c_{t})$ of the DP
formulation (Adelman, 2007). We obtain an LP dual with the interpretable set
of constraints (8b) below.

$\displaystyle\text{Dual}(\bm{p},\bm{D})=$ $\displaystyle\leavevmode\nobreak\
\max\leavevmode\nobreak\ \theta$ (8) $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ \mbox{s.t.}\leavevmode\nobreak\ \leavevmode\nobreak\
\theta\cdot p_{t}(d_{t})\leq\sum_{c_{t}:c_{t}\geq
d_{t}}\alpha_{t}(d_{t},c_{t}),\leavevmode\nobreak\ \leavevmode\nobreak\
\forall t,\forall d_{t}$ (8a) $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \alpha_{t}(d_{t},c_{t})\leq
p_{t}(d_{t})\cdot\sum_{\tau\leq
t-1}\sum_{d_{\tau}}(\alpha_{\tau}(d_{\tau},c_{t}+d_{\tau})-\alpha_{\tau}(d_{\tau},c_{t})),\leavevmode\nobreak\
\forall t,\forall d_{t},\forall c_{t}<1$ (8b)
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \alpha_{t}(d_{t},1)\leq
p_{t}(d_{t})\cdot(1-\sum_{\tau\leq
t-1}\sum_{d_{\tau}}\alpha_{\tau}(d_{\tau},1)),\leavevmode\nobreak\
\leavevmode\nobreak\ \forall t,\forall d_{t}$ (8c)
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\alpha_{t}(d_{t},c_{t})=0,\leavevmode\nobreak\ \leavevmode\nobreak\ \forall
t,\forall d_{t},\forall c_{t}>1$ $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \theta,\alpha_{t}(d_{t},c_{t})\geq 0,\leavevmode\nobreak\
\leavevmode\nobreak\ \forall t,\forall d_{t},\forall c_{t}$

In fact, for general $\bm{p}$ and $\bm{D}$, $\text{Dual}(\bm{p},\bm{D})$
characterizes the knapsack OCRS problem described in 2, where each query $t$
has a size $d_{t}$ with probability $p_{t}(d_{t})$. To see this, we interpret
the variable $\theta$ as the guarantee $\gamma$ in the knapsack OCRS problem,
and we interpret the variable $\alpha_{t}(d_{t},c_{t})$ for each $t$, each
$d_{t}$, and each $0\leq c_{t}\leq 1$ as the ex-ante probability (the
unconditional probability) that query $t$ becomes active with size $d_{t}$ and
is served when the remaining capacity is $c_{t}$ at the beginning of period
$t$. Then, constraint (8a) corresponds to each query $t$ being served with
probability at least $\theta=\gamma$ conditional on it being active with size
$d_{t}$. Moreover, for each $t$ and each $0\leq c_{t}<1$, the term
$\sum_{\tau=1}^{t-1}\sum_{d_{\tau}}\alpha_{\tau}(d_{\tau},c_{t}+d_{\tau})$
denotes the ex-ante probability that the remaining capacity has “reached” the
state $c_{t}$ in the first $t-1$ periods and the term
$\sum_{\tau=1}^{t-1}\sum_{d_{\tau}}\alpha_{\tau}(d_{\tau},c_{t})$ denotes the
ex-ante probability that the remaining capacity has “left” the state $c_{t}$.
Thus, the difference
$\sum_{\tau=1}^{t-1}\sum_{d_{\tau}}(\alpha_{\tau}(d_{\tau},c_{t}+d_{\tau})-\alpha_{\tau}(d_{\tau},c_{t}))$
denotes exactly the ex-ante probability that the remaining capacity at the
beginning of period $t$ is $c_{t}$. Similarly, the difference
$1-\sum_{\tau=1}^{t-1}\sum_{d_{\tau}}\alpha_{\tau}(d_{\tau},1)$ denotes the
ex-ante probability that the remaining capacity at the beginning of period $t$
is $1$. Since each query $t$ can only be served after the size is realized as
some $d_{t}$, which happens independently with probability $p_{t}(d_{t})$, we
recover constraint (8b) and constraint (8c).

When each $d_{t}$ in $\bm{D}$ only takes value $0$ or $1/k$,
Dual$(\bm{p},\bm{D})$ characterizes the $k$-unit OCRS problem described in 1,
where each query $t$ becomes active with probability $p_{t}(1/k)$. We provide
further explanation on the characterization in Section 4.1.

Following the discussions above, the duality between Dual$(\bm{p},\bm{D})$ and
Primal$(\bm{p},\bm{D})$ implies that OCRS is the dual problem of our online
resource allocation problem, under both the $k$-unit setting (in which case
our online resource allocation problem becomes the $k$-unit prophet inequality
problem) and the knapsack setting. Consequently, the worst-case guarantee for
the OCRS problem is equivalent to the worst-case guarantee of the optimal
online policy relative to the LP relaxation.

##  4 Multi-unit Prophet Inequalities

We now consider the single-resource problem under the multi-unit setting. To
be specific, we assume that $d_{t}=\frac{1}{k}$ for an integer $k$, for each
$t$, i.e., the online decision maker can serve at most $k$ queries to collect
the corresponding rewards. Note that when $k=1$, our problem reduces to the
well-known prophet inequality (Krengel and Sucheston, 1978), and for general
$k$, we get the so-called multi-unit prophet inequalities (Alaei, 2011). The
main result of this section is that for each $k$, we derive the tight
competitive ratio for the $k$-unit prophet inequality problem with respect to
the LP upper bound, or equivalently the optimal solution $\gamma^{*}_{k}$ to
the $k$-unit OCRS problem. Note that our values $\gamma^{*}_{k}$ strictly
exceed $1-\frac{1}{\sqrt{k+3}}$ for all $k>1$, and hence we also improve the
best-known prophet inequalities for all $k>1$.

The structure of our proof follows the three steps outlined in Section 1.1. In
a preliminary version (Jiang et al., 2022) of this work, we illustrate our
approach for a special case $k=2$.

###  4.1 LP Formulation of $k$-unit OCRS Problem

We first present a new LP formulation of the $k$-unit OCRS problem, assuming
that the vector $\bm{p}$ is given in advance. This LP is derived from taking
the dual of the LP formulation of the optimal dynamic programming (DP) policy.
We name our LP as $\text{Dual}(\bm{p},k)$, which is exactly
$\text{Dual}(\bm{p},\bm{D})$ in (8) under the $k$-unit setting. Then, the
restriction $\sum_{t=1}^{T}\sum_{d_{t}}p_{t}(d_{t})\cdot d_{t}\leq 1$, which
follows from Lemma 2, can be translated into $\sum_{t=1}^{T}p_{t}\leq k$ by
noting $d_{t}$ takes a single value $1/k$ when query $t$ becomes active.
Therefore, Lemma 3 implies that it is enough to consider
$\text{Dual}(\bm{p},k)$ to obtain the tight guarantee for the $k$-unit prophet
inequality problem.

$\displaystyle\text{Dual}(\bm{p},k)=\leavevmode\nobreak\ $
$\displaystyle\max\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \theta$ (9) $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ \text{s.t.}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
\theta\leq\frac{\sum_{l=1}^{k}x_{l,t}}{p_{t}}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall t$ (9a)
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ x_{1,t}\leq
p_{t}\cdot(1-\sum_{\tau<t}x_{1,\tau})\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \forall t$ (9b) $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ x_{l,t}\leq
p_{t}\cdot\sum_{\tau<t}(x_{l-1,\tau}-x_{l,\tau})\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall t,\forall l=2,\dots,k$ (9c)
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ x_{1,t}\geq
0,x_{2,t}\geq 0,\dots,x_{k,t}\geq 0.$

Here, the variable $\theta$ can be interpreted as guarantee $\gamma$ in the
$k$-unit OCRS problem and $x_{l,t}$ can be interpreted as the ex-ante
probability of serving query $t$ as the $l$-th one. Then, constraint (9a)
guarantees that each query $t$ is served with an ex-ante probability
$\theta\cdot p_{t}$. Moreover, it is easy to see that the term
$\sum_{\tau<t}x_{l-1,\tau}$ can be interpreted as the probability that the
number of served queries has “reached” $l-1$ during the first $t-1$ periods,
while the term $\sum_{\tau<t}x_{l,\tau}$ can be interpreted as the probability
that the number of served queries is larger than $l-1$. Then, the term
$\sum_{\tau<t}(x_{l-1,\tau}-x_{l,\tau})$ denotes the probability that the
number of served queries is $l-1$ at the beginning of period $t$. Similarly,
the term $1-\sum_{\tau<t}x_{1,\tau}$ denotes the probability that no query is
served at the beginning of period $t$. Further note that each query $t$ can be
served only after it becomes active, which happens independently with
probability $p_{t}$, and hence we get constraint (9b) and (9c).

Although presented in a different context, the “$\gamma$-Conservative
Magician” procedure of Alaei (2011) implies a feasible solution to
$\text{Dual}(\bm{p},k)$, for any $\bm{p}$ and any $k$ satisfying
$\sum_{t=1}^{T}p_{t}\leq k$. We now describe this implied solution in
Definition 3, which is based on a predetermined $\theta$.

###### Definition 3

A candidate solution to $\text{Dual}(\bm{p},k)$ in (9) given $\theta$
(potentially infeasible)

  1. 1.

For a fixed $\theta\in[0,1]$, we define $x_{1,t}(\theta)=\theta\cdot p_{t}$
from $t=1$ up to $t=t_{2}$, where $t_{2}$ is defined as the first time among
$\\{1,\dots,T\\}$ such that $\theta>1-\sum_{t=1}^{t_{2}}\theta\cdot p_{t}$ and
if such a $t_{2}$ does not exist, we denote $t_{2}=T$. Then we define
$x_{1,t}(\theta)=p_{t}\cdot(1-\sum_{\tau=1}^{t-1}x_{1,\tau}(\theta))$ from
$t=t_{2}+1$ up to $t=T$.

  2. 2.

For $l=2,3,\dots,k-1$, we do the following:

    1. (a)

Define $x_{l,t}(\theta)=0$ from $t=1$ up to $t=t_{l}$.

    2. (b)

Define $x_{l,t}(\theta)=\theta\cdot p_{t}-\sum_{v=1}^{l-1}x_{v,t}(\theta)$
from $t=t_{l}+1$ up to $t=t_{l+1}$, where $t_{l+1}$ is defined as the first
time among $\\{1,\dots,T\\}$ such that

$\theta\cdot
p_{t_{l+1}+1}-\sum_{v=1}^{l-1}x_{v,t_{l+1}+1}(\theta)>p_{t_{l+1}+1}\cdot\sum_{t=1}^{t_{l+1}}(x_{l-1,t}(\theta)-x_{l,t}(\theta))$

and if such a $t_{l+1}$ does not exist, we denote $t_{l+1}=T$.

    3. (c)

Define
$x_{l,t}(\theta)=p_{t}\cdot\sum_{\tau=1}^{t-1}(x_{l-1,\tau}(\theta)-x_{l,\tau}(\theta))$
from $t=t_{l+1}+1$ up to $t=T$.

  3. 3.

Define $x_{k,t}(\theta)=0$ from $t=1$ up to $t=t_{k}$ and define
$x_{k,t}(\theta)=\theta\cdot p_{t}-\sum_{v=1}^{k-1}x_{v,t}(\theta)$ from
$t=t_{k}+1$ up to $t=T$.

Note that in the above construction, the values of $\\{t_{l}\\}$ and
$\\{x_{l,t}(\theta)\\}$ are uniquely determined by $\theta$. Obviously, for an
arbitrary $\theta$, the solution $\\{\theta,x_{l,t}(\theta)\\}$ is not
necessarily a feasible solution to $\text{Dual}(\bm{p},k)$, much less an
optimal one. Alaei et al. (2012) shows that if we set
$\theta=1-\frac{1}{\sqrt{k+3}}$, then $\\{\theta,x_{l,t}(\theta)\\}$ is a
feasible solution to $\text{Dual}(\bm{p},k)$. Thus, they obtain a
$1-\frac{1}{\sqrt{k+3}}$-lower bound of the optimal competitive ratio.
However, we now try to identify a $\theta^{*}$, which is dependent on
$\bm{p}$, such that $\\{\theta^{*},x_{l,t}(\theta^{*})\\}$ is an optimal
solution to $\text{Dual}(\bm{p},k)$.

Remark. In 3 we describe the LP solution instead of the corresponding policy,
because our proof of optimality is implicit, relying on duality and
complementary slackness to eventually show that our derived bound of
$\gamma^{*}_{k}$ (which does not have a closed form) is tight. By contrast,
later for knapsack (see Section 5) we described the corresponding policy,
since we were able to explicitly establish the bound $\frac{1}{3+e^{-2}}$ and
show through a counterexample that it is tight. Although here we are able to
construct counterexamples as well, this will be done implicitly through LP
duality.

###  4.2 Characterizing the Optimal LP Solution for a Given p

We begin by proving the condition on $\theta$ for
$\\{\theta,x_{l,t}(\theta)\\}$ to be a feasible solution to
$\text{Dual}(\bm{p},k)$.

###### Lemma 4

For any vector $\bm{p}$, there exists a unique $\theta^{*}\in[0,1]$ such that
$\sum_{\tau=1}^{T-1}x_{k,\tau}(\theta^{*})=1-\theta^{*}$. Moreover, for any
$\theta\in[0,\theta^{*}]$, $\\{\theta,x_{l,t}(\theta)\\}$ is a feasible
solution to $\text{Dual}(\bm{p},k)$.

The proof is relegated to Section B1. We now prove that
$\\{\theta^{*},x_{l,t}(\theta^{*})\\}$ is an optimal solution to
$\text{Dual}(\bm{p},k)$. The dual of $\text{Dual}(\bm{p},k)$ can be formulated
as follows:

$\displaystyle\text{Primal}(\bm{p},k)\leavevmode\nobreak\
=\leavevmode\nobreak\ \min\ \ $
$\displaystyle\sum_{t=1}^{T}p_{t}\cdot\beta_{1,t}$ (10) s.t.
$\displaystyle\beta_{l,t}+\sum_{\tau>t}p_{\tau}\cdot(\beta_{l,\tau}-\beta_{l+1,\tau})-\xi_{t}\geq
0,\leavevmode\nobreak\ \leavevmode\nobreak\ \forall
t=1,\dots,T,\leavevmode\nobreak\ \forall l=1,2,\dots,k-1$
$\displaystyle\beta_{k,t}+\sum_{\tau>t}p_{\tau}\cdot\beta_{k,\tau}-\xi_{t}\geq
0,\leavevmode\nobreak\ \leavevmode\nobreak\ \forall t=1,\dots,T$
$\displaystyle\sum_{t=1}^{T}p_{t}\cdot\xi_{t}=1$ $\displaystyle\beta_{l,t}\geq
0,\xi_{t}\geq 0,\leavevmode\nobreak\ \leavevmode\nobreak\ \forall
t=1,\dots,T,\forall l=1,\dots,k.$

$\text{Primal}(\bm{p},k)$ in (10) is actually a re-formulation of
$\text{Primal}(\bm{p},\bm{D})$ in (7), through variable substitution. We
substitute $\beta_{l,t}=V_{t}(1-\frac{l-1}{k})-V_{t+1}(1-\frac{l-1}{k})$ for
each $l=1,\dots,k$ and $\xi_{t}=\hat{r}_{t}$ for each $t$. Then the variable
$W_{t}(\omega_{t},c_{t})$ can be canceled by summing constraint (7a) and
constraint (7b) after taking expectation over all scenario $\omega_{t}$, while
constraint $W_{t}(\omega_{t},c_{t})\geq 0$ is equivalent to $\beta_{l,t}$ are
non-negative for all $l$. Thus, for each $l$ and $t$, the variable
$\beta_{l,t}$ can be interpreted as the marginal increase of the total
collected reward over time, when there are $l-1$ queries being served prior to
time $t$, and the variable $\xi_{t}$ can be interpreted as the reward of query
$t$ in the worst case.

To prove the optimality of $\\{\theta^{*},x_{l,t}(\theta^{*})\\}$, we will
construct a feasible dual solution $\\{\beta^{*}_{l,t},\xi^{*}_{t}\\}$ to
$\text{Primal}(\bm{p},k)$ such that complementary slackness conditions hold
for the primal-dual pair $\\{\theta^{*},x_{l,t}(\theta^{*})\\}$ and
$\\{\beta^{*}_{l,t},\xi^{*}_{t}\\}$; then, the well-known primal-dual
optimality criterion (Dantzig and Thapa, 2006) establishes that
$\\{\theta^{*},x_{l,t}(\theta^{*})\\}$ and $\\{\beta^{*}_{l,t},\xi^{*}_{t}\\}$
are the optimal primal-dual pair to $\text{Dual}(\bm{p},k)$ and
$\text{Primal}(\bm{p},k)$, which completes our proof. The above arguments are
formalized in the following theorem. The detailed construction of
$\\{\beta^{*}_{l,t},\xi^{*}_{t}\\}$ and the proof of Theorem 1 are relegated
to Section B4.

###### Theorem 1

The solution $\\{\theta^{*},x_{l,t}(\theta^{*})\\}$ is optimal for
$\text{Dual}(\bm{p},k)$, where $\theta^{*}$ is the unique solution to
$\sum_{\tau=1}^{T-1}x_{k,\tau}(\theta^{*})=1-\theta^{*}$.

Theorem 1 shows that 3 constructs an optimal solution to
$\text{Dual}(\bm{p},k)$, as long as the $\theta$ is set as the optimal
$\theta^{*}$, as defined in Lemma 4. This optimal $\theta^{*}$ is uniquely
defined based on $\bm{p}$. Lemma 4 further shows that any
$\theta\leq\theta^{*}$ is feasible, and hence if we can find a $\theta$ that
is no greater than the $\theta^{*}$ arising from any $\bm{p}$, then 3 will
correspond to a $\bm{p}$-agnostic procedure for the $k$-unit prophet
inequality or OCRS problem with a guarantee of $\theta$.

###  4.3 Characterizing the Worst-case Distribution

Our goal is now to find the $\bm{p}$ such that the optimal objective value
$\theta^{*}$ of $\text{Dual}(\bm{p},k)$ in (9) reaches its minimum. We would
like to characterize the worst-case distribution and then compute the
competitive ratio.

We first characterize the worst-case distribution for which the optimal
objective value of $\text{Dual}(\bm{p},k)$ reaches its minimum. Obviously, it
is enough for us to consider only the $\bm{p}$ satisfying
$\sum_{t=1}^{T}p_{t}=k$. We show in the following lemma that splitting one
query into two queries can only make the optimal objective value of
$\text{Dual}(\bm{p},k)$ become smaller, and thus, in the worst-case
distribution, each $p_{t}$ should be infinitesimally small.

###### Lemma 5

For any $\bm{p}=(p_{1},\dots,p_{T})$ satisfying $\sum_{t=1}^{T}p_{t}=k$, and
any $\sigma\in[0,1]$, $1\leq q\leq T$, if we define a new sequence of arrival
probabilities $\tilde{\bm{p}}=(\tilde{p}_{1},\dots,\tilde{p}_{T+1})$ such that

$\displaystyle\tilde{p}_{t}=p_{t}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \forall t<q,\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\tilde{p}_{q}=p_{q}\cdot\sigma,\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\tilde{p}_{q+1}=p_{q}\cdot(1-\sigma)\text{\leavevmode\nobreak\
\leavevmode\nobreak\ and\leavevmode\nobreak\ \leavevmode\nobreak\
}\tilde{p}_{t+1}=p_{t}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \forall q+1\leq t\leq T,$

then it holds that $\text{Dual}(\bm{p},k)\geq\text{Dual}(\tilde{\bm{p}},k)$.

The proof is relegated to Section B5. Now, for each
$\bm{p}=(p_{1},\dots,p_{T})$ satisfying $\sum_{t=1}^{T}p_{t}=k$, we assume
without loss of generality that $p_{t}$ is a rational number for each $t$,
i.e., $p_{t}=\frac{n_{t}}{N}$ where $n_{t}$ is an integer for each $t$ and $N$
is an integer denoting the common denominator. We first split $p_{1}$ into
$\frac{1}{N}$ and $\frac{n_{1}-1}{N}$ to form a new sequence of arrival
probabilities. By Lemma 5, we know that such an operation can only decrease
the optimal objective value of $\text{Dual}(\bm{p},k)$. We then split
$\frac{n_{1}-1}{N}$ into $\frac{1}{N}$ and $\frac{n_{1}-2}{N}$ and so on. In
this way, we split $p_{1}$ into $n_{1}$ copies of $\frac{1}{N}$ to form a new
sequence of arrival probabilities and Lemma 5 guarantees that the optimal
objective value of $\text{Dual}(\bm{p},k)$ can only become smaller. We repeat
the above operation for each $t$. Finally, we form a new sequence of arrival
probabilities, denoted by
$\bm{p}^{N}=(\frac{1}{N},\dots,\frac{1}{N})\in\mathbb{R}^{Nk}$, and we have
$\text{Dual}(\bm{p},k)\geq\text{Dual}(\bm{p}^{N},k)$. Intuitively, when
$N\rightarrow\infty$, then the optimal objective value of
$\text{Dual}(\bm{p},k)$ reaches its minimum. Note that when
$N\rightarrow\infty$, we always have $\sum_{t=1}^{Nk}p_{t}^{N}=k$, and then
the Bernoulli arrival process approximates a Poisson process with rate $1$
over the time interval $[0,k]$. The above argument implies that the worst-case
arrival process is a Poisson process.

Under the Poisson process, for each fixed ratio $\theta\in[0,1]$, our solution
in Definition 3 can be interpreted as a solution to an ordinary differential
equation (ODE). We further note that for $\bm{p}^{N}$ and any
$\theta\in[0,1]$, our solution in Definition 3 can be regarded as the solution
obtained from applying Euler’s method to solve this ODE by uniformly
discretizing the interval $[0,k]$ into $Nk$ discrete points. Then, for any
fixed ratio $\theta\in[0,1]$, after showing the Lipschitz continuity of the
function defining this ODE, we can apply the global truncation error theorem
of Euler’s method (Theorem 212A in Butcher and Goodwin (2008)) to establish
the solution under the Poisson process as the limit of the solution under
$\bm{p}^{N}$ when $N\rightarrow\infty$. Based on this convergence, we can
prove that the optimal value under the Poisson process is equivalent to
$\lim_{N\rightarrow\infty}\text{Dual}(\bm{p}^{N},k)$, which is the optimal
ratio we are looking for.

For general $k$, the values of $\gamma^{*}_{k}$ have previously been shown in
Wang et al. (2018) through the analysis of a “reflecting” Poisson process.
However, we show that these values $\gamma^{*}_{k}$ are optimal, deriving them
instead from $\text{Dual}(\bm{p},\bm{D})$. Moreover, Wang et al. (2018) assume
Poisson arrivals to begin with, whereas we allow for arbitrary probability
vectors $\bm{p}$ and show that the limiting Poisson case is the worst case.

Specifically in the case of $k=2$, we construct an example showing that
relative to the weaker prophet benchmark
$\mathbb{E}_{\bm{I}\sim\bm{F}}[V^{\text{off}}(\bm{I})]$, it is not possible to
do much better than $\gamma^{*}_{2}$. Our construction is based on adapting
the tight example relative to the stronger benchmark $\text{UP}(\mathcal{H})$.
We note that this suggests that there is some separation between optimal ex-
ante vs. non-ex-ante prophet inequalities when $k>1$, which is not the case
when $k=1$ (because they are both 1/2). The formal proof of Proposition 1
below is relegated to Section B6.

###### Proposition 1

For the $2$-unit prophet inequality problem, it holds that
$\inf_{\mathcal{H}}\frac{\mathbb{E}_{\pi,\bm{I}\sim\bm{F}}[V^{\pi}(\bm{I})]}{\mathbb{E}_{\bm{I}\sim\bm{F}}[V^{\text{off}}(\bm{I})]}\leq
0.6269$ for any online algorithm $\pi$.

We now discuss how the construction in Definition 3 should be interpreted when
the arrival process is a Poisson process. We find it is more convenient to
work with the functions $\\{\tilde{y}_{l,\theta}(\cdot)\\}_{\forall
l=1,\dots,k}$ over $[0,k]$, where $\tilde{y}_{l,\theta}(t)$ denotes the ex-
ante probability that there is a query served as the $l$-th one during the
period $[0,t]$. Note that the variable $x_{l,t}(\theta)$ denotes the ex-ante
probability that there is a query accepted as the $l$-th query at time $t$,
and hence we have $x_{l,t}(\theta)=d\tilde{y}_{l,\theta}(t)$. We denote
$\tilde{y}_{0,\theta}(t)=1$ for each $t\in[0,k]$. Then the functions
$\\{\tilde{y}_{l,\theta}(\cdot)\\}_{\forall l=1,\dots,k}$ corresponding to the
construction in Definition 3 under Poisson arrivals can be interpreted as
follows.

###### Definition 4

Ordinary Differential Equation (ODE) formula under Poisson arrival

  1. 1.

For each fixed $\theta\in[0,1]$, we define $\tilde{y}_{0,\theta}(t)=1$ for
each $t\in[0,k]$ and $t_{1}=0$.

  2. 2.

For each $l=1,2,\dots,k-1$, we do the following:

    1. (a)

$\tilde{y}_{l,\theta}(t)=0$ when $t\leq t_{l}$.

    2. (b)

When $t_{l}\leq t\leq t_{l+1}$, it holds that

$\frac{d\tilde{y}_{l,\theta}(t)}{dt}=\theta-\sum_{v=1}^{l-1}\frac{d\tilde{y}_{v,\theta}(t)}{dt}=\theta-1+\tilde{y}_{l-1,\theta}(t),\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall t_{l}\leq t\leq t_{l+1},$
(11)

where $t_{l+1}$ is defined as the first time that
$\tilde{y}_{l,\theta}(t_{l+1})=1-\theta$. If such a $t_{l+1}$ does not exist,
we denote $t_{l+1}=k$.

    3. (c)

When $t_{l+1}\leq t\leq k$, it holds that

$\frac{d\tilde{y}_{l,\theta}(t)}{dt}=\tilde{y}_{l-1,\theta}(t)-\tilde{y}_{l,\theta}(t),\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall t_{l+1}\leq t\leq k.$ (12)

  3. 3.

$\tilde{y}_{k,\theta}(t)=0$ if $t\leq t_{k}$ and
$\frac{d\tilde{y}_{k,\theta}(t)}{dt}=\theta-1+\tilde{y}_{k-1,\theta}(t)$ if
$t_{k}\leq t\leq k$.

Thus, by Theorem 1, the solution to the equation
$\tilde{y}_{k,\theta}(k)=1-\theta$ should be the minimum of the optimal
objective value of $\text{Dual}(\bm{p},k)$ in (9), which is the competitive
ratio $\gamma^{*}_{k}$ we are looking for. The above arguments are formalized
in the following theorem and the proof is relegated to Section B7. Note that
the following Theorem 2 is our ultimate result for the $k$-unit case, while 4
characterizes the ODE formula mentioned in Section 1.1. In the remaining part
of this section, we will describe the computational procedure for
$\gamma^{*}_{k}$.

###### Theorem 2

For each $\theta\in[0,1]$, denote by $\\{\tilde{y}_{l,\theta}(\cdot)\\}$ the
functions defined in Definition 4. Then there exists a unique
$\gamma^{*}_{k}\in[0,1]$ such that
$\tilde{y}_{k,\gamma^{*}_{k}}(k)=1-\gamma^{*}_{k}$ and it holds that

$\gamma^{*}_{k}=\leavevmode\nobreak\ \leavevmode\nobreak\
\inf_{\bm{p}}\leavevmode\nobreak\ \text{Dual}(\bm{p},k)\leavevmode\nobreak\
\leavevmode\nobreak\ \mbox{s.t.}\leavevmode\nobreak\ \sum_{t=1}^{T}p_{t}=k.$

We now show that the ODE in Definition 4 admits an analytical solution that
enables us to compute $\gamma^{*}_{k}$ for each $k$. For each fixed $\theta$,
when $l=1$, it is immediate that

$\tilde{y}_{1,\theta}(t)=\theta\cdot t,\leavevmode\nobreak\
\leavevmode\nobreak\ \text{when\leavevmode\nobreak\ }t\leq
t_{2}=\frac{1-\theta}{\theta},\text{\leavevmode\nobreak\ \leavevmode\nobreak\
and\leavevmode\nobreak\ \leavevmode\nobreak\
}\tilde{y}_{1,\theta}(t)=1-\theta\cdot\exp(t_{2}-t),\leavevmode\nobreak\
\leavevmode\nobreak\ \text{for\leavevmode\nobreak\ }t_{2}\leq t\leq k.$

Now suppose that there exists a fixed $2\leq l\leq k$ such that for each
$1\leq v\leq l-1$, it holds that

$\displaystyle\tilde{y}_{v,\theta}(t)=\zeta_{v}+\theta\cdot
t+\sum_{q=0}^{v-2}\zeta_{v,q}\cdot t^{q}\cdot\exp(-t),\leavevmode\nobreak\
\leavevmode\nobreak\ $ $\displaystyle\text{when\leavevmode\nobreak\ }t_{v}\leq
t\leq t_{v+1}$
$\displaystyle\tilde{y}_{v,\theta}(t)=1+\sum_{q=0}^{v-1}\psi_{v,q}\cdot
t^{q}\cdot\exp(-t),\leavevmode\nobreak\ \leavevmode\nobreak\ $
$\displaystyle\text{when\leavevmode\nobreak\ }t_{v+1}\leq t\leq k$

for some parameters $\\{\zeta_{v},\zeta_{v,q},\psi_{v,q}\\}$, which are
specified by $\theta$. Then by ODE (11) and (12), it must hold that

$\displaystyle\tilde{y}_{l,\theta}(t)=\zeta_{l}+\theta\cdot
t+\sum_{q=0}^{l-2}\zeta_{l,q}\cdot t^{q}\cdot\exp(-t),\leavevmode\nobreak\
\leavevmode\nobreak\ $ $\displaystyle\text{when\leavevmode\nobreak\ }t_{l}\leq
t\leq t_{l+1}$
$\displaystyle\tilde{y}_{l,\theta}(t)=1+\sum_{q=0}^{l-1}\psi_{l,q}\cdot
t^{q}\cdot\exp(-t),\leavevmode\nobreak\ \leavevmode\nobreak\ $
$\displaystyle\text{when\leavevmode\nobreak\ }t_{l+1}\leq t\leq k.$

The parameters $\\{\zeta_{l},\zeta_{l,q},\psi_{l,q}\\}$ can be computed in the
following steps:

  1. 1.

Set $\zeta_{l,l-1}=0$ and compute $\zeta_{l,q}$ iteratively from $q=l-2$ up to
$q=0$ by setting

$\zeta_{l,q}=(q+1)\cdot\zeta_{l,q+1}-\psi_{l-1,q}.$

  2. 2.

Set the value of $\zeta_{l}$ such that $\tilde{y}_{l,\theta}(t_{l})=0$. If
$l=k$, we set $t_{l+1}=k$; otherwise, we set $t_{l+1}$ to be the solution to
the following equation:

$1-\theta=\tilde{y}_{l,\theta}(t)=\zeta_{l}+\theta\cdot
t+\sum_{q=0}^{l-2}\zeta_{l,q}\cdot t^{q}\cdot\exp(-t).$

Note that by definition $\tilde{y}_{l,\theta}(t)$ is monotone increasing with
$t$, and hence we can do a bisection search on the interval $[t_{l},k]$ to
obtain the value of $t_{l+1}$.

  3. 3.

Set $\psi_{l,q}=\frac{\psi_{l-1,q-1}}{q}$ for each $q=1,\dots,l-1$. If $l<k$,
the value of $\psi_{l,0}$ is determined such that

$1-\theta=1+\sum_{q=0}^{l-1}\psi_{l,q}\cdot t_{l+1}^{q}\cdot\exp(-t_{l+1}).$

Thus, for each fixed $\theta$, we can follow the above procedure to obtain the
value of $\tilde{y}_{k,\theta}(k)$. Note that Lemma 10 established in Section
B1 implies that the value of $\tilde{y}_{k,\theta}(k)$ is monotone increasing
with $\theta$, and hence we can do a bisection search on $\theta\in[0,1]$ to
obtain the value of $\gamma^{*}_{k}$ as the unique solution of the equation
$\tilde{y}_{k,\theta}(k)=1-\theta$. By Theorem 2, $\gamma^{*}_{k}$ is the
optimal value for the competitive ratio.

##  5 Results for the Knapsack Setting

In this section, we present our results for the knapsack problem. A
combination of the random routing approach and the algorithm presented in this
section would fully solve the multi-resource problem under the knapsack
setting with the optimal competitive ratio guarantee. Following Lemma 2, we
restrict $\mathcal{H}$ to describe a single-resource problem instance and the
constraint $\sum_{t=1}^{T}\mathbb{E}[\tilde{d}_{t}]\leq 1$ is satisfied. Note
that now we have the LP upper bound
$\text{UP}(\mathcal{H})=\sum_{t=1}^{T}\mathbb{E}[\tilde{r}_{t}]$. We are now
ready to describe our policy.

The structure of our proof follows the steps outlined in Section 1.2. In a
preliminary version (Jiang et al., 2022) of this work, we illustrate our
approach for the special case where each $\tilde{d}_{t}$ can take at most two
values, one of which is 0.

###  5.1 Algorithm and Interpretation

Our policy differs from existing ones for knapsack in an online setting
(Dutting et al., 2020; Feldman et al., 2021; Stein et al., 2020) by eschewing
the need to split queries into “large” vs. “small” based on whether its size
is greater than 1/2. In fact, we can show that any algorithm which considers
large and small queries separately in our problem is limited to $\gamma\leq
1/4$, and hence could not match the $\frac{1}{3+e^{-2}}$ upper bound provided
earlier. The result follows by considering a problem setup $\mathcal{H}$ where
there are 4 queries and $(\tilde{r}_{t},\tilde{d}_{t})$ is realized as
$(\hat{r}_{t},\hat{d}_{t})$ with probability $p_{t}$ and is realized as
$(0,0)$ otherwise, for each query $t$, and letting

$(\hat{r}_{1},p_{1},\hat{d}_{1})=(r,1,\epsilon),\leavevmode\nobreak\
\leavevmode\nobreak\
(\hat{r}_{2},p_{2},\hat{d}_{2})=(\hat{r}_{3},p_{3},\hat{d}_{3})=(r,\frac{1-2\epsilon}{1+2\epsilon},\frac{1}{2}+\epsilon),\leavevmode\nobreak\
\leavevmode\nobreak\ (\hat{r}_{4},p_{4},\hat{d}_{4})=(r/\epsilon,\epsilon,1)$

for $r>0$ and some small $\epsilon>0$. We formalize the above arguments as
follows, where the formal proof is relegated to Section C1.

###### Proposition 2

If the policy $\pi$ serves only either “large” queries with a size larger than
1/2, or “small” queries with a size no larger than 1/2, then it holds that
$\inf_{\hat{\mathcal{H}}}\frac{\mathbb{E}_{\hat{\bm{I}}\sim\hat{\bm{F}}}[V^{\pi}(\hat{\bm{I}})]}{\text{UP}(\hat{\mathcal{H}})}\leq\frac{1}{4}$.

Our policy is formally stated in Algorithm 1. Our policy is based on a pre-
specified parameter $\gamma$ and a salient feature of our policy is that each
query $t$, as long as its reward and size are realized as $(d_{t},r_{t})$, is
included in the knapsack with a probability $\gamma$. This guarantees that our
policy enjoys a competitive ratio $\gamma$. Based on $\gamma$, for each $t$,
we use $\tilde{X}_{t-1,\gamma}$ to denote the distribution of the capacity
consumption under our policy at the beginning of period $t$, where
$\tilde{X}_{0,\gamma}$ takes value $0$ deterministically. Then, for each
realization $(r_{t},d_{t})$ of query $t$, we specify a threshold
$\eta_{t,\gamma}(r_{t},d_{t})$ such that the probability of
$\tilde{X}_{t-1,\gamma}\in(\eta_{t,\gamma}(r_{t},d_{t}),1-d_{t}]$ is smaller
than or equal to $\gamma$, and the probability that
$\tilde{X}_{t-1,\gamma}\in[\eta_{t,\gamma}(r_{t},d_{t}),1-d_{t}]$ is larger
than or equal to $\gamma$. When query $t$ is realized as
$(\hat{r}_{t},\hat{d}_{t})$, we serve query $t$ when the realized capacity
consumption is among $(\eta_{t,\gamma}(\hat{r}_{t},\hat{d}_{t}),1-d_{t}]$, or
we serve query $t$ with a certain probability (specified in step 4), when the
realized capacity consumption equals
$\eta_{t,\gamma}(\hat{r}_{t},\hat{d}_{t})$. It is clear to see that our policy
guarantees that query $t$ is served with a total probability $\gamma$. We
finally update the distribution of capacity consumption in step 5.

In this section we establish competitive ratios while ignoring implementation
runtime; in Section 6.1 we show how through discretization, a runtime
polynomial in $K$ is attainable while losing only an additive $O(1/K)$ in the
competitive ratio, for any large integer $K$.

Algorithm 1 Best-fit Magician policy for single-knapsack ($\pi_{\gamma}$)

1:For a fixed $\gamma$, we initialize $\tilde{X}_{0,\gamma}$ as a random
variable that takes the value $0$ deterministically.

2:For $t=1,2,\dots,T$, we do the following:

3:For each realization $(r_{t},d_{t})$ of $(\tilde{r}_{t},\tilde{d}_{t})$, we
denote by $p(r_{t},d_{t})=P((\tilde{r}_{t},\tilde{d}_{t})=(r_{t},d_{t}))$.
Then, we denote a threshold $\eta_{t,\gamma}(r_{t},d_{t})$ satisfying:
$P(\eta_{t,\gamma}(r_{t},d_{t})<\tilde{X}_{t-1,\gamma}\leq
1-d_{t})\leq\gamma\leq
P(\eta_{t,\gamma}(r_{t},d_{t})\leq\tilde{X}_{t-1,\gamma}\leq 1-d_{t}).$ (13)

4:Denote by $(\hat{r}_{t},\hat{d}_{t})$ the realization of query $t$ and by
$X_{t-1}$ the consumed capacity at the end of period $t-1$. Then we serve
query $t$ if $\eta_{t,\gamma}(\hat{r}_{t},\hat{d}_{t})<X_{t-1}\leq
1-\hat{d}_{t}$; we serve query $t$ with probability
$\frac{\gamma-P(\eta_{t,\gamma}(\hat{r}_{t},\hat{d}_{t})<\tilde{X}_{t-1,\gamma}\leq
1-\hat{d}_{t})}{P(\eta_{t,\gamma}(\hat{r}_{t},\hat{d}_{t})=\tilde{X}_{t-1,\gamma})}$
if $X_{t-1}=\eta_{t,\gamma}(\hat{r}_{t},\hat{d}_{t})$.

5:Based on $\tilde{X}_{t-1,\gamma}$, for each realization $(r_{t},d_{t})$ of
$(\tilde{r}_{t},\tilde{d}_{t})$ and each point
$x\in(\eta_{t,\gamma}(r_{t},d_{t}),1-d_{t}]$, we move the $p(r_{t},d_{t})\cdot
P(\tilde{X}_{t-1,\gamma}=x)$ measure of probability mass from point $x$ to the
new point $x+d_{t}$ and when $x=\eta_{t,\gamma}(r_{t},d_{t})$, we move the
$p(r_{t},d_{t})\cdot(\gamma-P(\eta_{t,\gamma}(r_{t},d_{t})<\tilde{X}_{t-1,\gamma}\leq
1-d_{t}))$ measure of probability mass from point $x$ to the new point
$x+d_{t}$. We obtain a new distribution and we denote by
$\tilde{X}_{t,\gamma}$ a random variable with this distribution.

In fact, the policy $\pi_{\gamma}$ constructs a feasible solution to
$\text{Dual}(\bm{p},\bm{D})$ in (8). Specifically, we denote variable $\theta$
in $\text{Dual}(\bm{p},\bm{D})$ as $\gamma$ in our policy $\pi_{\gamma}$.
Then, for each $t$ and each $0\leq c_{t}\leq 1$, we denote the variable
$\alpha_{t}(d_{t},c_{t})$ in $\text{Dual}(\bm{p},\bm{D})$ as the ex-ante
probability that query $t$ is served when the remaining capacity is $c_{t}$ at
the beginning of period $t$, which also denotes the amount of probability mass
of $\tilde{X}_{t-1,\gamma}$ that is moved from point $1-c_{t}$ to the point
$1-c_{t}+d_{t}$ when defining $\tilde{X}_{t,\gamma}$ in step 5 in Algorithm 1.
Obviously, when $\gamma$ is feasible, the policy $\pi_{\gamma}$ guarantees
that each query $t$ with size $d_{t}$ is served with an ex-ante probability
$\gamma\cdot p_{t}(d_{t})$ where $p_{t}(d_{t})=\sum_{r_{t}}p(r_{t},d_{t})$,
which corresponds to constraint (8a). Moreover, from step 5, it is clear to
see that

$P(\tilde{X}_{t,\gamma}=0)=P(\tilde{X}_{t-1,\gamma}=0)-\sum_{d_{t}}\alpha_{t}(d_{t},1)$

and

$P(\tilde{X}_{t,\gamma}=1-c)=P(\tilde{X}_{t-1,\gamma}=1-c)+\sum_{d_{t}}(\alpha_{t}(d_{t},c+d_{t})-\alpha_{t}(d_{t},c)),\leavevmode\nobreak\
\leavevmode\nobreak\ \forall c<1$

which implies that

$P(\tilde{X}_{t-1,\gamma}=0)=1-\sum_{\tau=1}^{t-1}\sum_{d_{\tau}}\alpha_{\tau}(d_{\tau},1)$

and

$P(\tilde{X}_{t-1,\gamma}=1-c)=\sum_{\tau=1}^{t-1}\sum_{d_{\tau}}(\alpha_{\tau}(d_{\tau},c+d_{\tau})-\alpha_{\tau}(d_{\tau},c)),\leavevmode\nobreak\
\leavevmode\nobreak\ \forall c<1$

Then, the constraint $\alpha_{t}(d_{t},c)\leq p_{t}(d_{t})\cdot
P(\tilde{X}_{t-1,\gamma}=1-c)$ for each $0\leq c\leq 1$ in the policy
$\pi_{\gamma}$ corresponds to constraint (8b) and constraint (8c).

###  5.2 Proof of Competitive Ratio and Tightness

In this section, we analyze the competitive ratio of our Best-fit Magician
policy in Algorithm 1 and show that it is tight. When $\gamma$ is fixed, our
policy $\pi_{\gamma}$ guarantees that the decision maker collects at least
$\gamma$ times the LP upper bound
$\text{UP}(\mathcal{H})=\sum_{t=1}^{T}\mathbb{E}[\tilde{r}_{t}]$. Thus, the
key point is to find the largest possible $\gamma$ such that the policy
$\pi_{\gamma}$ is feasible for all problem setups $\mathcal{H}$, i.e., the
random variables $\tilde{X}_{t,\gamma}$ are well defined for each $t$.

We now find such a $\gamma$. For any $a$ and $b$, denote
$\mu_{t,\gamma}(a,b]=P(a<\tilde{X}_{t,\gamma}\leq b)$ assuming
$\tilde{X}_{t,\gamma}$ is well defined. A key observation of the Best-fit
Magician is that an arriving query with a realized size $d_{t}$ gets accepted
in the previously empty sample path of $\tilde{X}_{t-1,\gamma}$ only if there
is less than a $\gamma$-measure of sample paths with utilization in
$(0,1-d_{t}]$. Then, we can establish an invariant that upper-bounds the
measure of sample paths with utilization in $(0,b]$ by a decreasing
exponential function of the measure with utilization in $(b,1-b]$. Our
invariant holds for all $b\in(0,1/2]$, at all times $t$.

###### Lemma 6

For any $0<b\leq\frac{1}{2}$ and any $0<\gamma<1$ such that
$\tilde{X}_{t,\gamma}$ is well-defined, the following inequality

$\frac{1}{\gamma}\cdot\mu_{t,\gamma}(0,b]\leq\exp(-\frac{1}{\gamma}\cdot\mu_{t,\gamma}(b,1-b])$
(14)

holds for all $t=0,1,\dots,T$.

We omit proving Lemma 6 since we will prove a more general Lemma 7 in Section
6.2. For a fixed $t$, assume that the random variable $\tilde{X}_{t,\gamma}$
is well defined. Then, given the invariant (14) established in Lemma 6, we can
lower-bound the measure of zero-utilization sample paths, i.e.,
$P(\tilde{X}_{t,\gamma}=0)$, by the constraint

$\displaystyle\sum_{\tau=1}^{t}\sum_{(r_{\tau},d_{\tau})}d_{\tau}\cdot
p(r_{\tau},d_{\tau})$
$\displaystyle=\sum_{\tau=1}^{t}\sum_{(r_{\tau},d_{\tau})}d_{\tau}\cdot
P((\tilde{r}_{\tau},\tilde{d}_{\tau})=(r_{\tau},d_{\tau}))$
$\displaystyle=\sum_{\tau=1}^{t}\mathbb{E}_{(\tilde{r}_{\tau},\tilde{d}_{\tau})\sim
F_{\tau}}[\tilde{d}_{\tau}]\leq 1,$

where the last inequality holds from our restriction stated at the beginning
that $\sum_{t=1}^{T}\mathbb{E}[\tilde{d}_{t}]\leq 1$. Note that invariant (14)
enables us a way to upper-bound the measure of “bad” sample paths with
utilization within $(0,b]$ by the measure of sample paths with utilization
within $(b,1-b]$ for some $0<b<\frac{1}{2}$. Therefore, on the remaining
sample paths the utilization must be either 0 or greater than $1-b$, which are
good cases for us. From this, we show that a $\gamma$ as large as
$\frac{1}{3+e^{-2}}\approx 0.319$ allows for a $\gamma$-measure of sample
paths to have zero utilization at time $t$, which implies that the random
variable $\tilde{X}_{t+1,\gamma}$ is well defined. We iteratively apply the
above arguments for each $t=1$ up to $t=T$, and hence we prove the feasibility
of our Best-fit Magician policy. The above arguments are formalized in the
following theorem and the proof is relegated to Section C2.

###### Theorem 3

When $\gamma=\frac{1}{3+e^{-2}}$, the threshold policy $\pi_{\gamma}$ is
feasible and has a competitive ratio at least $\frac{1}{3+e^{-2}}$.

Finally, we show that the guarantee $\gamma=\frac{1}{3+e^{-2}}$ is tight. From
Lemma 3, by bounding the optimal value of $\text{Dual}(\bm{p},\bm{D})$ when
$\bm{p}$ and $\bm{D}$ (size of query $t$ is deterministic) are specified as
follows,

$(p_{1},d_{1})=(1,\epsilon),\leavevmode\nobreak\ \leavevmode\nobreak\
(p_{t},d_{t})=(\frac{1-2\epsilon}{(T-2)(\frac{1}{2}+\epsilon)},\frac{1}{2}+\epsilon)\text{\leavevmode\nobreak\
\leavevmode\nobreak\ for\leavevmode\nobreak\ all\leavevmode\nobreak\ }2\leq
t\leq T-1\text{\leavevmode\nobreak\ \leavevmode\nobreak\
and\leavevmode\nobreak\ \leavevmode\nobreak\ }(p_{T},d_{T})=(\epsilon,1)$ (15)

for some $\epsilon>0$, we obtain the following upper bound of the guarantee of
any online algorithm. We refer the formal proof to Section C3.

###### Theorem 4

For any feasible online policy $\pi$, it holds that
$\inf_{\hat{\mathcal{H}}}\frac{\mathbb{E}_{\hat{\bm{I}}\sim\hat{\bm{F}}}[V^{\pi}(\hat{\bm{I}})]}{\text{UP}(\hat{\mathcal{H}})}\leq\frac{1}{3+e^{-2}}$.

##  6 Extensions for the Knapsack Setting

In this section, we discuss the polynomial-time implementation of our Best-fit
Magician policy (Section 6.1), and present our improvement in the unit-density
special case (Section 6.2).

###  6.1 A Polynomial-time Implementation Scheme

In this section, we discuss how our Best-fit Magician policy can be
implemented in polynomial time. Note that the key step in our algorithm is to
iteratively compute the distribution of $\tilde{X}_{t,\gamma}$. Our approach
is to discretize the possible sizes to always be a multiple of $\frac{1}{KT}$,
for some large integer $K$. Then the support set of $\tilde{X}_{t,\gamma}$
contains at most $KT$ elements for each $t$, from which it can then be seen
that our algorithm can be implemented in $O(KT^{2})$ time.

For any problem setup $\mathcal{H}$ restricted to the single-resource setting,
we perform this discretization by rounding each potential size $d_{t}$ up to
the nearest multiple of $\frac{1}{KT}$. We denote the rounded sizes using
$d^{\prime}_{t}$. We then define $F^{\prime}_{t}(\cdot)$ as the distribution
of $(r_{t},d_{t}^{\prime})$, which is a discretization of the distribution
$F_{t}(\cdot)$, and we define
$\mathcal{H}^{\prime}=(F^{\prime}_{1},\dots,F^{\prime}_{T})$. The
implementation of our algorithm on the problem setup $\mathcal{H}$ is
equivalent to the implementation on $\mathcal{H}^{\prime}$. To be more
specific, we compute the distribution of $\tilde{X}_{t,\gamma}$ based on
$F^{\prime}_{t}(\cdot)$ for each $t$, and, when we face a query
$(r_{t},d_{t})$, we treat this query as a query with reward $r_{t}$ and a size
$d_{t}^{\prime}$.

We now discuss the loss of the guarantee of our algorithm due to such
discretization. Note that since $d_{t}\leq d^{\prime}_{t}$ for each $t$, if
the algorithm attempts any solution that is feasible for
$\mathcal{H}^{\prime}$, then it is also feasible for $\mathcal{H}$. Moreover,
since $r_{t}$ is never changed, it is easy to see that the total reward
collected by our algorithm in the problem setup $\mathcal{H}$ satisfies

$\mathbb{E}_{\pi_{\gamma},\bm{I}\sim\mathcal{H}}[V^{\pi_{\gamma}}(\bm{I})]=\mathbb{E}_{\pi_{\gamma},\bm{I}\sim\mathcal{H}^{\prime}}[V^{\pi_{\gamma}}(\bm{I})]$

and, when $\gamma\leq\frac{1}{3+e^{-2}}$, it holds that

$\mathbb{E}_{\pi_{\gamma},\bm{I}\sim\mathcal{H}^{\prime}}[V^{\pi_{\gamma}}(\bm{I})]\geq\gamma\cdot\text{UP}(\mathcal{H}^{\prime}).$

It only remains to compare $\text{UP}(\mathcal{H})$ and
$\text{UP}(\mathcal{H}^{\prime})$. Note that the sizes in
$\mathcal{H}^{\prime}$ are bigger, but since at most $\frac{1}{KT}$ can be
added to the size of each of the $T$ queries, the total size added is at most
$1/K$. We will use this to argue that
$\text{UP}(\mathcal{H}^{\prime})\geq\frac{1}{1+1/K}\text{UP}(\mathcal{H})=(1-\frac{1}{K+1})\text{UP}(\mathcal{H})$.

Denote by $\\{x^{*}_{t}(r_{t},d_{t})\\}$ the optimal solution to
$\text{UP}(\mathcal{H})$, and denote

$\hat{x}_{t}(r_{t},d_{t}^{\prime})=\frac{K}{K+1}\cdot\mathbb{E}_{(r_{t},\tilde{d}_{t})\sim
F_{t}}\left[x^{*}_{t}(r_{t},\tilde{d}_{t})|\tilde{d}_{t}\text{\leavevmode\nobreak\
is\leavevmode\nobreak\ rounded\leavevmode\nobreak\ up\leavevmode\nobreak\
to\leavevmode\nobreak\ }d^{\prime}_{t}\right].\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall(r_{t},d_{t}^{\prime})$

Note that if $d_{t}$ is rounded up to $d_{t}^{\prime}$, it must hold that
$d_{t}^{\prime}-d_{t}\leq\frac{1}{KT}$. Then, we have

$\displaystyle\sum_{t=1}^{T}\mathbb{E}_{(\tilde{r}_{t},\tilde{d}_{t}^{\prime})\sim
F_{t}^{\prime}}[\tilde{d}_{t}^{\prime}\cdot\hat{x}_{t}(\tilde{r}_{t},\tilde{d}_{t}^{\prime})]$
$\displaystyle\leq\frac{K}{K+1}\cdot\sum_{t=1}^{T}\mathbb{E}_{(\tilde{r}_{t},\tilde{d}_{t})\sim
F_{t}}[\tilde{d}_{t}\cdot
x^{*}_{t}(\tilde{r}_{t},\tilde{d}_{t})]+\sum_{t=1}^{T}\mathbb{E}_{(\tilde{r}_{t},\tilde{d}_{t}^{\prime})\sim
F_{t}^{\prime}}[\frac{1}{KT}\cdot\hat{x}_{t}(\tilde{r}_{t},\tilde{d}_{t}^{\prime})]$
$\displaystyle\leq\frac{K}{K+1}+\sum_{t=1}^{T}\frac{1}{KT}\cdot\frac{K}{K+1}=1,$

where the last inequality holds by the feasibility of
$\\{x^{*}_{t}(r_{t},d_{t})\\}$ and
$\hat{x}_{t}(r_{t},d_{t}^{\prime})\in[0,\frac{K}{K+1}]$ for each
$(r_{t},d_{t}^{\prime})$. We conclude that
$\\{\hat{x}_{t}(r_{t},d_{t}^{\prime})\\}$ is a feasible solution to
$\text{UP}(\mathcal{H}^{\prime})$. Thus, it holds that

$\text{UP}(\mathcal{H}^{\prime})\geq\sum_{t=1}^{T}\mathbb{E}_{(\tilde{r}_{t},\tilde{d}_{t}^{\prime})\sim
F_{t}^{\prime}}[\tilde{r}_{t}\cdot
x_{t}(\tilde{r}_{t},\tilde{d}_{t}^{\prime})]=\frac{K}{K+1}\cdot\sum_{t=1}^{T}\mathbb{E}_{(\tilde{r}_{t},\tilde{d}_{t})\sim
F_{t}}[\tilde{r}_{t}\cdot
x^{*}_{t}(\tilde{r}_{t},\tilde{d}_{t})]=\frac{K}{K+1}\cdot\text{UP}(\mathcal{H}),$

which implies that

$\mathbb{E}_{\pi_{\gamma},\bm{I}\sim\mathcal{H}}[V^{\pi_{\gamma}}(\bm{I})]\geq\frac{K}{K+1}\cdot\gamma\cdot\text{UP}(\mathcal{H})$

when $\gamma\leq\frac{1}{3+e^{-2}}$. In this way, we show how our algorithm
can be implemented in $O(KT^{2})$ time to achieve a guarantee of
$\frac{K}{K+1}\cdot\frac{1}{3+e^{-2}}$.

###  6.2 Improvement in the Unit-density Special Case

In this section, we consider the unit-density special case of our online
knapsack problem where $\tilde{r}_{t}=\tilde{d}_{t}$ for each $t$. Then we can
suppress the notation $(\tilde{r}_{t},\tilde{d}_{t})$ and simply use
$\tilde{d}_{t}$ to denote the size and the reward of query $t$. We modify our
previous Best-fit Magician policy to obtain an improved guarantee. Following
Lemma 2, we further restrict $\mathcal{H}$ to describe a single-resource
problem instance and the constraint
$\sum_{t=1}^{T}\mathbb{E}[\tilde{r}_{t}]=\sum_{t=1}^{T}\mathbb{E}[\tilde{d}_{t}]\leq
1$ is satisfied. Note that now we have the LP upper bound
$\text{UP}(\mathcal{H})=\sum_{t=1}^{T}\mathbb{E}[\tilde{r}_{t}]=\sum_{t=1}^{T}\mathbb{E}[\tilde{d}_{t}]$.
To maximize the total collected reward, it is enough for us to maximize the
expected capacity utilization.

We now motivate our policy. Note that for the general case where the reward
can be arbitrarily different from the size, our Best-fit Magician policy
guarantees that each query is served with a common ex-ante probability
$\gamma$ after the LP relaxation. In this way, each query is treated “equally”
so that no “extreme” reward can be assigned to the query with the smallest ex-
ante probability, which would worsen the guarantee of our algorithm. However,
in the unit-density case where the reward of each query is restricted to equal
its size, it is no longer essential for us to treat each query “equally.”
Instead, we will serve the later-arriving queries with a smaller probability
to maximize capacity utilization. Our idea can be illustrated through the
following example.

Example $1$. We focus on the following example with $4$ queries to illustrate
how to maximize capacity utilization:

$(p_{1},d_{1})=(\frac{2}{3},\frac{1}{2}),\leavevmode\nobreak\
(p_{2},d_{2})=(\frac{2}{3},\frac{1}{2}),\leavevmode\nobreak\
(p_{3},d_{3})=(1-\epsilon,\frac{1}{3})\text{\leavevmode\nobreak\
and\leavevmode\nobreak\ }(p_{4},d_{4})=(\frac{\epsilon}{3},1).$

Note that if we apply the Best-fit Magician policy with a ratio $\gamma$, then
the feasible condition of our policy is

$P(\tilde{X}_{3,\gamma}=0)=1-\frac{8\gamma}{9}-\frac{5\gamma(1-\epsilon)}{9}\geq\gamma,$
(16)

which implies that $\gamma\leq\frac{9}{22}$ as $\epsilon\rightarrow 0$. Thus,
we conclude that the Best-fit Magician policy can guarantee an expected
capacity utilization of at most $\frac{9}{22}$ for this example. However, if
we serve each query with a different probability, i.e., if we serve query $t$
with probability $\gamma_{t}$ whenever it arrives, then the feasibility
condition (16) becomes
$P(\tilde{X}_{3,\gamma_{1},\gamma_{2},\gamma_{3}}=0)\geq\gamma_{4}$. We can
set $\gamma_{4}=0$, which enables us to set a larger value for
$\gamma_{1},\gamma_{2}$, and $\gamma_{3}$, which in turn leads to a larger
capacity utilization.

To be more specific, if we denote by $\tilde{X}_{t}$ the distribution of
capacity utilization at the end of period $t=1,\dots,4$ under the serving
probabilities $\gamma_{1},\gamma_{2},\gamma_{3},\gamma_{4}$, then the
distribution of $\tilde{X}_{1}$ is

$P(\tilde{X}_{1}=\frac{1}{2})=p_{1}\cdot\gamma_{1}=\frac{2\gamma_{1}}{3}\text{\leavevmode\nobreak\
\leavevmode\nobreak\ and\leavevmode\nobreak\ \leavevmode\nobreak\
}P(\tilde{X}_{1}=0)=1-\frac{2\gamma_{1}}{3}.$

We still proceed to serve query $2$; however, we serve it with probability
$\gamma_{2}$ whenever it arrives. Then, we obtain the following distribution
of $\tilde{X}_{2}$:

$\displaystyle P(\tilde{X}_{2}=1)=\gamma_{1}\cdot p_{1}\cdot
p_{2}=\frac{4\gamma_{1}}{9},\leavevmode\nobreak\ \leavevmode\nobreak\
P(\tilde{X}_{2}=\frac{1}{2})=\gamma_{2}\cdot p_{2}-\gamma_{1}\cdot p_{1}\cdot
p_{2}+p_{1}\cdot\gamma_{1}-\gamma_{1}\cdot p_{1}\cdot
p_{2}=\frac{2\gamma_{2}}{3}-\frac{2\gamma_{1}}{9}$ $\displaystyle
P(\tilde{X}_{2}=0)=1-P(\tilde{X}_{2}=1)-P(\tilde{X}_{2}=\frac{1}{2})=1-\frac{2\gamma_{1}}{9}-\frac{2\gamma_{2}}{3}.$

Finally, we serve query $3$ with probability $\gamma_{3}$ whenever it arrives.
Then, the distribution of $\tilde{X}_{3}$ can be obtained as follows:

$\displaystyle P(\tilde{X}_{3}=1)=\frac{4\gamma_{1}}{9},\leavevmode\nobreak\
\leavevmode\nobreak\
P(\tilde{X}_{3}=\frac{5}{6})=(\frac{2\gamma_{2}}{3}-\frac{2\gamma_{1}}{9})\cdot(1-\epsilon),\leavevmode\nobreak\
\leavevmode\nobreak\
P(\tilde{X}_{3}=\frac{5}{6})=(\frac{2\gamma_{2}}{3}-\frac{2\gamma_{1}}{9})\cdot\epsilon,$
$\displaystyle
P(\tilde{X}_{3}=\frac{1}{3})=(\gamma_{3}-\frac{2\gamma_{2}}{3}+\frac{2\gamma_{1}}{9})\cdot(1-\epsilon),\leavevmode\nobreak\
\leavevmode\nobreak\
P(\tilde{X}_{3}=0)=1-\frac{4\gamma_{1}}{9}-\gamma_{3}+(\frac{2\gamma_{1}}{9}-\frac{2\gamma_{2}}{3}+\gamma_{3})\cdot\epsilon.$

Note that as long as $P(\tilde{X}_{t}=0)\geq\gamma_{t+1}$ for each $t=1,2,3$,
the random variables $\\{\tilde{X}_{t}\\}_{t=1,2,3}$ are well defined and the
above procedure is feasible. Obviously, the probabilities $P(\tilde{X}_{t}=0)$
are decreasing in $t$, which corresponds to the fact that the measure of the
sample paths with no capacity consumed decreases over time. Thus, it is
natural to set $\gamma_{t}$ to decrease in terms of $t$. Specifically, we can
set

$\gamma_{2}=P(\tilde{X}_{1}=0)=1-\frac{2\gamma_{1}}{3}\text{\leavevmode\nobreak\
\leavevmode\nobreak\ and\leavevmode\nobreak\ \leavevmode\nobreak\
}\gamma_{3}=P(\tilde{X}_{2}=0)=1-\frac{2\gamma_{1}}{9}-\frac{2\gamma_{2}}{3}=\frac{1}{3}+\frac{2\gamma_{1}}{9}$

as a function of $\gamma_{1}$. We can also set $\gamma_{4}=0$ since the
expected capacity utilization of the last query is $0$ as $\epsilon\rightarrow
0$. Then, the only feasibility condition we need to satisfy is

$P(\tilde{X}_{3}=0)\geq\gamma_{4}=0,$

which implies that $\gamma_{1}$ can be set as large as $1$ when
$\epsilon\rightarrow 0$. Then $\gamma_{2}=\frac{1}{3}$ and
$\gamma_{3}=\frac{5}{9}$ as $\epsilon\rightarrow 0$. Thus, we can guarantee a
capacity utilization of $\frac{17}{27}$, which improves on the previous
utilization of $\frac{9}{22}$ under the Best-fit Magician policy.

We now present our policy in Algorithm 2, which is based on a sequence of
probabilities with which we serve each query based on its LP relaxation value,
denoted by $\bm{\gamma}=(\gamma_{1},\dots,\gamma_{T})$ and satisfying
$1\geq\gamma_{1}\geq\gamma_{2}\geq\dots\geq\gamma_{T}\geq 0$. We will specify
later how to determine the vector $\bm{\gamma}$ such that our policy is
feasible and achieves the improved guarantee.

Algorithm 2 Modified Best-fit Magician policy for unit-density special case

1:For a fixed sequence $\bm{\gamma}$ satisfying
$1\geq\gamma_{1}\geq\gamma_{2}\geq\dots\geq\gamma_{T}\geq 0$, we initialize
$\tilde{X}_{0,\bm{\gamma}}$ as a random variable taking value $0$ with
probability $1$.

2:For $t=1,2,\dots,T$, we do the following:

3:For each realization $d_{t}$ of $\tilde{d}_{t}$, we denote
$p(d_{t})=P(\tilde{d}_{t}=d_{t})$. Then, we denote a threshold
$\eta_{t,\bm{\gamma}}(d_{t})$ satisfying
$P(\eta_{t,\bm{\gamma}}(d_{t})<\tilde{X}_{t-1,\bm{\gamma}}\leq
1-d_{t})\leq\gamma_{t}\leq
P(\eta_{t,\bm{\gamma}}(d_{t})\leq\tilde{X}_{t-1,\bm{\gamma}}\leq 1-d_{t}).$
(17)

4:Denote by $\hat{d}_{t}$ the realization of query $t$ and by $X_{t-1}$ the
consumed capacity at the end of period $t-1$. Then we serve query $t$ if
$\eta_{t,\bm{\gamma}}(\hat{d}_{t})<X_{t-1}\leq 1-\hat{d}_{t}$; we serve query
$t$ with probability
$\frac{\gamma_{t}-P(\eta_{t,\bm{\gamma}}(\hat{d}_{t})<\tilde{X}_{t-1,\bm{\gamma}}\leq
1-\hat{d}_{t})}{P(\eta_{t,\bm{\gamma}}(\hat{d}_{t})=\tilde{X}_{t-1,\bm{\gamma}})}$
if $X_{t-1}=\eta_{t,\bm{\gamma}}(\hat{d}_{t})$.

5:Based on $\tilde{X}_{t-1,\bm{\gamma}}$, for each realization $d_{t}$ of
$\tilde{d}_{t}$ and each point $x\in(\eta_{t,\bm{\gamma}}(d_{t}),1-d_{t}]$, we
move the $p(d_{t})\cdot P(\tilde{X}_{t-1,\bm{\gamma}}=x)$ measure of
probability mass from point $x$ to the new point $x+d_{t}$ and when
$x=\eta_{t,\bm{\gamma}}(d_{t})$, we move the
$p(d_{t})\cdot(\gamma_{t}-P(\eta_{t,\bm{\gamma}}(d_{t})<\tilde{X}_{t-1,\bm{\gamma}}\leq
1-d_{t}))$ measure of probability mass from point $x$ to the new point
$x+d_{t}$. We obtain a new distribution and we denote by
$\tilde{X}_{t,\bm{\gamma}}$ a random variable with this distribution.

Note that if the sequence $\bm{\gamma}$ is uniform, i.e.,
$\gamma_{1}=\dots=\gamma_{T}$, then the modified Best-fit Magician policy in
Algorithm 2 is identical to the Best-fit Magician policy in Algorithm 1. We
now discuss how to determine the sequence $\bm{\gamma}$ such that our policy
in Algorithm 2 is feasible. Our approach relies crucially on the distribution
of capacity utilization at the end of each period $t$, denoted by
$\tilde{X}_{t,\bm{\gamma}}$, assuming that the sequence $\bm{\gamma}$ is
feasible.

For any $a$ and $b$, we denote
$\mu_{t,\bm{\gamma}}(a,b]=P(a<\tilde{X}_{t,\bm{\gamma}}\leq b)$, where
$\tilde{X}_{t,\bm{\gamma}}$ denotes the distribution of capacity utilization
at the end of period $t$ in Algorithm 2. Then, we can still establish the
following invariant, which generalizes Lemma 6 from the uniform sequence to
any sequence $\bm{\gamma}$ satisfying
$1\geq\gamma_{1}\geq\dots\geq\gamma_{T}\geq 0$.

###### Lemma 7

For any $0<b\leq\frac{1}{2}$ and any sequence $\bm{\gamma}$ satisfying
$1\geq\gamma_{1}\geq\dots\geq\gamma_{T}\geq 0$ such that
$\tilde{X}_{t,\bm{\gamma}}$ is well defined, the following inequality

$\frac{1}{\gamma_{1}}\cdot\mu_{t,\bm{\gamma}}(0,b]\leq\exp(-\frac{1}{\gamma_{1}}\cdot\mu_{t,\bm{\gamma}}(b,1-b])$
(18)

holds for any $t=1,\dots,T$.

Note that the “difficult” case for proving the invariant in Lemma 6
corresponds to when there is a probability mass moved from point $0$ during
the definition of $\tilde{X}_{t,\gamma}$. Then, both $\mu_{t}(0,b]$ and
$\mu_{t}(b,1-b]$ can become larger, for some $b\in(0,1/2)$. However, when
$\bm{\gamma}$ is a non-increasing sequence, the amount of probability mass
that is moved from $0$ into either the interval $(0,b]$ or $(b,1-b]$ under
$\gamma_{t}$ is smaller than the one under $\gamma_{1}$, which makes the
invariant easier to hold. The proof of Lemma 7 is relegated to Section D1.
Using Lemma 7, we can modify the proof of Theorem 3 to obtain the following
result, which will finally lead to our choice of the feasible sequence
$\bm{\gamma}$ and the guarantee of our algorithm.

###### Theorem 5

For any $t$, denote $\psi_{t}=\mathbb{E}_{\tilde{d}_{t}\sim
F_{t}}[\tilde{d}_{t}]$. Then for any sequence $\bm{\gamma}$ satisfying
$1\geq\gamma_{1}\geq\dots\geq\gamma_{T}\geq 0$ such that
$\tilde{X}_{t,\bm{\gamma}}$ is well defined, the following inequality

$P(\tilde{X}_{t,\bm{\gamma}}=0)\geq\min\\{1-\gamma_{1}-\sum_{\tau=1}^{t}\gamma_{\tau}\cdot\psi_{\tau},\leavevmode\nobreak\
\leavevmode\nobreak\
1-2\cdot\sum_{\tau=1}^{t}\gamma_{\tau}\cdot\psi_{\tau}-\gamma_{1}\cdot\exp(-\frac{2}{\gamma_{1}}\cdot\sum_{\tau=1}^{t}\gamma_{\tau}\cdot\psi_{\tau})\\}$
(19)

holds for each $t=1,\dots,T$.

The proof is relegated to Section D2. Note that for each $t$, if the random
variables $\tilde{X}_{\tau,\bm{\gamma}}$ are well defined for each $\tau\leq
t$, and $\gamma_{t+1}$ satisfies

$0\leq\gamma_{t+1}\leq\min\\{1-\gamma_{1}-\sum_{\tau=1}^{t}\gamma_{\tau}\cdot\psi_{\tau},\leavevmode\nobreak\
\leavevmode\nobreak\
1-2\cdot\sum_{\tau=1}^{t}\gamma_{\tau}\cdot\psi_{\tau}-\gamma_{1}\cdot\exp(-\frac{2}{\gamma_{1}}\cdot\sum_{\tau=1}^{t}\gamma_{\tau}\cdot\psi_{\tau})\\},$
(20)

then (19) implies that $P(\tilde{X}_{t,\bm{\gamma}}=0)\geq\gamma_{t+1}$. Thus,
we know that there always exists a threshold $\eta_{t+1,\bm{\gamma}}(d_{t})$
such that (17) holds (since it can be set to $0$), and the random variable
$\tilde{X}_{t+1,\bm{\gamma}}$ is well defined. We apply the above argument
iteratively for each $t=1$ up to $t=T$. In this way, we conclude that a
sufficient condition for the non-increasing sequence $\bm{\gamma}$ to be
feasible for our policy in Algorithm 2 is that (20) holds for each $t$.

Note that the expected utilization of our policy in Algorithm 2 is
$\sum_{t=1}^{T}\gamma_{t}\cdot\psi_{t}$. The above analysis implies we can
focus on solving the following optimization problem to determine the sequence
$\bm{\gamma}$:

$\displaystyle\text{OP}(\bm{\psi}):=$ $\displaystyle\leavevmode\nobreak\
\max\leavevmode\nobreak\ \leavevmode\nobreak\
\sum_{t=1}^{T}\gamma_{t}\cdot\psi_{t}$ (21) $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ \mbox{s.t.}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \gamma_{t+1}\leq
1-\gamma_{1}-\sum_{\tau=1}^{t}\gamma_{\tau}\cdot\psi_{\tau},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall t=1,\dots,T-1$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\gamma_{t+1}\leq
1-2\cdot\sum_{\tau=1}^{t}\gamma_{\tau}\cdot\psi_{\tau}-\gamma_{1}\cdot\exp(-\frac{2}{\gamma_{1}}\cdot\sum_{\tau=1}^{t}\gamma_{\tau}\cdot\psi_{\tau}),\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall t=1,\dots,T-1$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
1\geq\gamma_{1}\geq\dots\geq\gamma_{T}\geq 0,$

where $\bm{\psi}=(\psi_{1},\dots,\psi_{T})$ and it holds that
$\sum_{t=1}^{T}\psi_{t}\leq 1$.

Our solution to $\text{OP}(\bm{\psi})$ can be obtained from the following
function over the interval $[0,1]$, the value of which is iteratively computed
based on an initial value $\gamma_{0}\in(0,1)$:

$\displaystyle h_{\gamma_{0}}(0)=$ $\displaystyle\gamma_{0}$ (22)
$\displaystyle h_{\gamma_{0}}(t)=$
$\displaystyle\min\left\\{\lim_{\tau\rightarrow
t-}h_{\gamma_{0}}(\tau),\leavevmode\nobreak\
1-\gamma_{0}-\int_{\tau=0}^{t}h_{\gamma_{0}}(\tau)d\tau,\right.$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\left.1-2\cdot\int_{\tau=0}^{t}h_{\gamma_{0}}(\tau)d\tau-\gamma_{0}\cdot\exp(-\frac{2}{\gamma_{0}}\cdot\int_{\tau=0}^{t}h_{\gamma_{0}}(\tau)d\tau)\right\\}.$

It is easy to see that the function $h_{\gamma_{0}}(\cdot)$ is non-increasing
and non-negative over $[0,1]$ as long as $0<\gamma_{0}<1$. Thus, the function
$h_{\gamma_{0}}(\cdot)$ specifies a feasible solution to
$\text{OP}(\bm{\psi})$ when each component of $\bm{\psi}$ is infinitesimally
small and $T\rightarrow\infty$, where $h_{\gamma_{0}}(t)$ corresponds to
$\gamma_{t}$ for each $t\in[0,1]$.

We now show that for arbitrary $\bm{\psi}$ satisfying
$\sum_{t=1}^{T}\psi_{t}\leq 1$, we can still construct a feasible solution to
$\text{OP}(\bm{\psi})$ based on the function $h_{\gamma_{0}}(\cdot)$ for each
fixed $0<\gamma_{0}<1$. Specifically, we define a set of indices $0=k_{0}\leq
k_{1}\leq\dots\leq k_{T}\leq 1$ such that $\psi_{t}=k_{t}-k_{t-1}$ for each
$t=1,\dots,T$. Then, we define

$\hat{\gamma}_{t}=\frac{\int_{\tau=k_{t-1}}^{k_{t}}h_{\gamma_{0}}(\tau)d\tau}{k_{t}-k_{t-1}}=\frac{\int_{\tau=k_{t-1}}^{k_{t}}h_{\gamma_{0}}(\tau)d\tau}{\psi_{t}}$
(23)

for each $t=1,\dots,T$. We show in the following lemma that
$\\{\hat{\gamma}_{t}\\}_{t=1}^{T}$ is a feasible solution to
$\text{OP}(\bm{\psi})$.

###### Lemma 8

For each fixed $0<\gamma_{0}<1$, let $h_{\gamma_{0}}(\cdot)$ be the function
defined in (22). Then, for any $\bm{\psi}$, the solution
$\\{\hat{\gamma}_{t}\\}_{t=1}^{T}$ is a feasible solution to
$\text{OP}(\bm{\psi})$, where $\hat{\gamma}_{t}$ is as defined in (23) for
each $t=1,\dots,T$.

The formal proof is relegated to Section D3. Note that for each $\bm{\psi}$
satisfying $\sum_{t=1}^{T}\psi_{t}\leq 1$, if
$\\{\hat{\gamma}_{t}\\}_{t=1}^{T}$ is constructed according to (23), then it
is easy to see that

$\sum_{t=1}^{T}\hat{\gamma}_{t}\cdot\psi_{t}=\int_{t=0}^{k_{T}}h_{\gamma_{0}}(t)dt$

and thus the guarantee of our policy in Algorithm 2 based on the sequence
$\\{\hat{\gamma}_{t}\\}_{t=1}^{T}$ is
$\frac{\int_{t=0}^{k_{T}}h_{\gamma_{0}}(t)dt}{k_{T}}$ for some
$k_{T}\in(0,1]$, where $k_{T}$ depends on the setup $\bm{\psi}$. Since the
function $h_{\gamma_{0}}(\cdot)$ is non-increasing and non-negative over
$[0,1]$ as long as $0<\gamma_{0}<1$, we know that the worst-case setup
corresponds to $k_{T}=1$, i.e., $\sum_{t=1}^{T}\psi_{t}=1$. Then, it is enough
to focus on solving the following problem:

$\max_{0<\gamma_{0}<1}\int_{t=0}^{1}h_{\gamma_{0}}(t)dt$

to obtain the guarantee of our policy. Numerically, we can show that when
$\gamma_{0}\approx 0.3977$, the above optimization problem reaches its
maximum, which is $0.3557$. We conclude that the guarantee of our policy is
$0.3557$. Note that the guarantee of our policy is developed with respect to
the LP upper bound $\text{UP}(\mathcal{H})$, and so it is straightforward to
generalize our results to a multi-knapsack setting (Stein et al., 2020) where
the size of each query can be knapsack-dependent, as explained in Section 3.1.

Also, we can show that no online algorithm can achieve a better guarantee than
$\frac{1-e^{-2}}{2}\approx 0.432$ relative to $\text{UP}(\mathcal{H})$, even
in the single-knapsack setting. The counterexample can be constructed from a
problem setup with $T$ queries, where each query has a deterministic size
$\frac{1}{2}+\frac{1}{T}$ and is active with probability $\frac{2}{T}$. The
proof is relegated to Section D4.

###### Proposition 3

In the single-knapsack unit-density case, no online algorithm can achieve a
better guarantee than $\frac{1-e^{-2}}{2}\approx 0.432$ relative to the LP
upper bound $\text{UP}(\mathcal{H})$.

Our guarantee of 0.3557 relative to $\text{UP}(\mathcal{H})$ in the unit-
density case demonstrates the power of using our invariant-based analysis
instead of a large/small analysis; we leave the possibility of tightening the
guarantee relative to the upper bound of 0.432 as future work.

## References

  * Adelman (2007) Adelman, Daniel. 2007.  Dynamic bid prices in revenue management.  Operations Research 55(4) 647–661.
  * Alaei (2011) Alaei, Saeed. 2011.  Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers.  2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. IEEE Computer Society, 512–521.
  * Alaei (2014) Alaei, Saeed. 2014.  Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers.  SIAM Journal on Computing 43(2) 930–972.
  * Alaei et al. (2012) Alaei, Saeed, MohammadTaghi Hajiaghayi, Vahid Liaghat. 2012.  Online prophet-inequality matching with applications to ad allocation.  Proceedings of the 13th ACM Conference on Electronic Commerce. 18–35.
  * Alaei et al. (2013) Alaei, Saeed, MohammadTaghi Hajiaghayi, Vahid Liaghat. 2013.  The online stochastic generalized assignment problem.  Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, 11–25.
  * Alaei et al. (2021) Alaei, Saeed, Ali Makhdoumi, Azarakhsh Malekian. 2021.  Revenue maximization under unknown private values with non-obligatory inspection.  Proceedings of the 22nd ACM Conference on Economics and Computation. 27–28.
  * Alaei et al. (2022) Alaei, Saeed, Ali Makhdoumi, Azarakhsh Malekian, Rad Niazadeh. 2022.  Descending price auctions with bounded number of price levels and batched prophet inequality.  arXiv preprint arXiv:2203.01384 .
  * Arnosti and Ma (2021) Arnosti, Nick, Will Ma. 2021.  Tight guarantees for static threshold policies in the prophet secretary problem.  arXiv preprint arXiv:2108.12893 .
  * Beyhaghi et al. (2021) Beyhaghi, Hedyeh, Negin Golrezaei, Renato Paes Leme, Martin Pál, Balasubramanian Sivan. 2021.  Improved revenue bounds for posted-price and second-price mechanisms.  Operations Research 69(6) 1805–1822.
  * Butcher and Goodwin (2008) Butcher, John Charles, Nicolette Goodwin. 2008.  Numerical methods for ordinary differential equations, vol. 2.  Wiley Online Library.
  * Chawla et al. (2020) Chawla, Shuchi, Nikhil Devanur, Thodoris Lykouris. 2020.  Static pricing for multi-unit prophet inequalities.  arXiv preprint arXiv:2007.07990 .
  * Chawla et al. (2010) Chawla, Shuchi, Jason D Hartline, David L Malec, Balasubramanian Sivan. 2010.  Multi-parameter mechanism design and sequential posted pricing.  Proceedings of the forty-second ACM symposium on Theory of computing. 311–320.
  * Cominetti et al. (2010) Cominetti, Roberto, Joss Correa, Thomas Rothvoss, Jaime San Martin. 2010.  Optimal selection of customers for a last-minute offer.  Operations research 58(4-part-1) 878–888.
  * Correa et al. (2017) Correa, José, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, Tjark Vredeveld. 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. (2019) Correa, Jose, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, Tjark Vredeveld. 2019\.  Recent developments in prophet inequalities.  ACM SIGecom Exchanges 17(1) 61–70.
  * Correa et al. (2021) Correa, Jose, Raimundo Saona, Bruno Ziliotto. 2021.  Prophet secretary through blind strategies.  Mathematical Programming 190(1) 483–521.
  * Dantzig and Thapa (2006) Dantzig, George B, Mukund N Thapa. 2006.  Linear programming 2: theory and extensions.  Springer Science & Business Media.
  * Dutting et al. (2020) Dutting, Paul, Michal Feldman, Thomas Kesselheim, Brendan Lucier. 2020.  Prophet inequalities made easy: Stochastic optimization by pricing nonstochastic inputs.  SIAM Journal on Computing 49(3) 540–582.
  * Esfandiari et al. (2017) Esfandiari, Hossein, MohammadTaghi Hajiaghayi, Vahid Liaghat, Morteza Monemizadeh. 2017.  Prophet secretary.  SIAM Journal on Discrete Mathematics 31(3) 1685–1701.
  * Feldman et al. (2021) Feldman, Moran, Ola Svensson, Rico Zenklusen. 2021.  Online contention resolution schemes with applications to bayesian selection problems.  SIAM Journal on Computing 50(2) 255–300.
  * Feng et al. (2020) Feng, Yiding, Rad Niazadeh, Amin Saberi. 2020.  Near-optimal bayesian online assortment of reusable resources.  Chicago Booth Research Paper (20-40).
  * Gallego et al. (2015) Gallego, Guillermo, Anran Li, Van-Anh Truong, Xinshang Wang. 2015.  Online resource allocation with customer choice.  arXiv preprint arXiv:1511.01837 .
  * Garey et al. (1972) Garey, Michael R, Ronald L Graham, Jeffrey D Ullman. 1972.  Worst-case analysis of memory allocation algorithms.  Proceedings of the fourth annual ACM symposium on Theory of computing. 143–150.
  * Hajiaghayi et al. (2007) Hajiaghayi, Mohammad Taghi, Robert Kleinberg, Tuomas Sandholm. 2007.  Automated online mechanism design and prophet inequalities.  AAAI, vol. 7. 58–65.
  * Han et al. (2015) Han, Xin, Yasushi Kawase, Kazuhisa Makino. 2015.  Randomized algorithms for online knapsack problems.  Theoretical Computer Science 562 395–405.
  * Hill and Kertz (1982) Hill, Theodore P, Robert P Kertz. 1982.  Comparisons of stop rule and supremum expectations of iid random variables.  The Annals of Probability 336–345.
  * Jiang et al. (2022) Jiang, Jiashuo, Will Ma, Jiawei Zhang. 2022.  Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack.  Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 1221–1246.
  * Krengel and Sucheston (1978) Krengel, Ulrich, Louis Sucheston. 1978.  On semiamarts, amarts, and processes with finite value.  Probability on Banach spaces 4 197–266.
  * Lee and Singla (2018) Lee, Euiwoong, Sahil Singla. 2018.  Optimal online contention resolution schemes via ex-ante prophet inequalities.  arXiv preprint arXiv:1806.09251 .
  * Ma et al. (2019) Ma, Will, David Simchi-Levi, Jinglong Zhao. 2019.  The competitive ratio of threshold policies for online unit-density knapsack problems.  arXiv preprint arXiv:1907.08735 .
  * Ma et al. (2021) Ma, Will, David Simchi-Levi, Jinglong Zhao. 2021.  Dynamic pricing (and assortment) under a static calendar.  Management Science 67(4) 2292–2313.
  * Papastavrou et al. (1996) Papastavrou, Jason D, Srikanth Rajagopalan, Anton J Kleywegt. 1996.  The dynamic and stochastic knapsack problem with deadlines.  Management Science 42(12) 1706–1718.
  * Stein et al. (2020) Stein, Clifford, Van-Anh Truong, Xinshang Wang. 2020.  Advance service reservations with heterogeneous customers.  Management Science 66(7) 2929–2950.
  * Wang et al. (2018) Wang, Xinshang, Van-Anh Truong, David Bank. 2018.  Online advance admission scheduling for services with customer preferences.  arXiv preprint arXiv:1805.10412 .
  * Yan (2011) Yan, Qiqi. 2011.  Mechanism design via correlation gap.  Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 710–719.

Proofs of Lemmas, Propositions and Theorems

##  7 Proofs in Section 3

###  A1 Proof of Lemma 1

###### Proof.

Proof: Denote $\\{x^{\text{off}}_{jt}(\bm{I})\\}_{j=1,\dots,m,t=1,\dots,T}$ as
the optimal solution to $V^{\text{off}}(\bm{I})$ in (2) and for each $t$, we
denote
$x_{jt}(\mathbf{r}_{t},\mathbf{d}_{t})=\mathbb{E}_{\bm{I}\sim\mathcal{H}}[x^{\text{off}}_{jt}(\bm{I})|\bm{I}_{t}=(\mathbf{r}_{t},\mathbf{d}_{t})]$,
where $\bm{I}_{t}$ denotes the reward of query $t$ in the sequence $\bm{I}$.
Then, we must have

$0\leq x_{jt}(\mathbf{r}_{t},\mathbf{d}_{t})\leq 1,\leavevmode\nobreak\
\leavevmode\nobreak\ \forall t,\leavevmode\nobreak\
\forall(\mathbf{r}_{t},\mathbf{d}_{t}),\leavevmode\nobreak\
\leavevmode\nobreak\ \text{and\leavevmode\nobreak\ \leavevmode\nobreak\
}\sum_{j=1}^{m}x_{jt}(\mathbf{r}_{t},\mathbf{d}_{t})\leq
1,\leavevmode\nobreak\ \leavevmode\nobreak\ \forall t$

and

$1\geq\mathbb{E}_{\bm{I}\sim\mathcal{H}}[\sum_{t=1}^{T}d_{jt}\cdot
x^{\text{off}}_{jt}(\bm{I})]=\sum_{t=1}^{T}\mathbb{E}_{(\mathbf{r}_{t},\mathbf{d}_{t})\sim
F_{t}}[\mathbb{E}_{\bm{I}\sim\mathcal{H}}[d_{jt}\cdot
x^{\text{off}}_{jt}(\bm{I})|\bm{I}_{t}=(\mathbf{r}_{t},\mathbf{d}_{t})]]=\sum_{t=1}^{T}\mathbb{E}_{(\mathbf{r}_{t},\mathbf{d}_{t})\sim
F_{t}}[d_{jt}\cdot x_{jt}(\mathbf{r}_{t},\mathbf{d}_{t})]$

Thus, we conclude that $\\{x_{jt}(\mathbf{r}_{t},\mathbf{d}_{t})\\}$ is a
feasible solution to $\text{UP}(\mathcal{H})$ in (4) and it holds that

$\mathbb{E}_{\bm{I}\sim\mathcal{H}}[V^{\text{off}}(\bm{I})]=\mathbb{E}_{\bm{I}\sim\mathcal{H}}[\sum_{t=1}^{T}\sum_{j=1}^{m}\tilde{r}_{jt}\cdot
x^{\text{off}}_{jt}(\bm{I})]=\sum_{t=1}^{T}\mathbb{E}_{(\mathbf{r}_{t},\mathbf{d}_{t})\sim
F_{t}}[\sum_{j=1}^{m}r_{jt}\cdot
x_{jt}(\mathbf{r}_{t},\mathbf{d}_{t})]\leq\text{UP}(\mathcal{H})$

which completes our proof. ∎

###  A2 Proof of Lemma 3

###### Proof.

Proof: The only part that requires a proof is to establish the strong duality
between $\text{Primal}(\bm{p},\bm{D})$ and $\text{Dual}(\bm{p},\bm{D})$. We
first show that $\text{Primal}(\bm{p},\bm{D})$ can be re-formulated as the
following LP:

$\displaystyle\text{LP}(\bm{p},\bm{D})=$ $\displaystyle\leavevmode\nobreak\
\min\leavevmode\nobreak\ \leavevmode\nobreak\ V_{1}(1)$ (24)
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
\mbox{s.t.}\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
V_{t}(c_{t})\geq V_{t+1}(c_{t})+\sum_{d_{t}:d_{t}\leq c_{t}}p_{t}(d_{t})\cdot
W_{t}(d_{t},c_{t}),\leavevmode\nobreak\ \leavevmode\nobreak\ \forall t,\forall
c_{t}$ (24a) $\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ W_{t}(d_{t},c_{t})\geq
r(d_{t})+V_{t+1}(c_{t}-d_{t})-V_{t+1}(c_{t}),\leavevmode\nobreak\
\leavevmode\nobreak\ \forall t,\forall c_{t}\geq d_{t}$ (24b)
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\sum_{t=1}^{T}\sum_{d_{t}}p_{t}(d_{t})\cdot r(d_{t})=1$ (24c)
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
V_{T+1}(c)=0,\leavevmode\nobreak\ \leavevmode\nobreak\ \forall c$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
V_{t}(c_{t}),W_{t}(c_{t})\geq 0,r(d_{t})\geq 0\leavevmode\nobreak\
\leavevmode\nobreak\ \forall t,\forall c_{t}$

For each $t$ and $d_{t}$, we denote by

$r(d_{t})=\frac{1}{p_{t}(d_{t})}\cdot\sum_{\omega_{t}:d(\omega_{t})=d_{t}}r(\omega_{t})\cdot
p_{t}(\omega_{t})$

We have that

$\sum_{t=1}^{T}\sum_{d_{t}}p_{t}(d_{t})\cdot
r(d_{t})=\sum_{t=1}^{T}\sum_{d_{t}}\sum_{\omega_{t}:d(\omega_{t})=d_{t}}r(\omega_{t})\cdot
p_{t}(\omega_{t})=\sum_{t=1}^{T}\sum_{\omega_{t}}r(\omega_{t})\cdot
p_{t}(\omega_{t})=1$

Thus, we get constraint (24c) in LP$(\bm{p},\bm{D})$ in (24). We also denote
by

$W_{t}(d_{t},c_{t})=\frac{1}{p_{t}(d_{t})}\cdot\sum_{\omega_{t}:d(\omega_{t})=d_{t}}p_{t}(\omega_{t})\cdot
W_{t}(\omega_{t},c_{t})$ (25)

Then we have that

$\mathbb{E}_{\omega_{t}\sim F_{t}}\left[1_{\\{d(\omega_{t})\leq c_{t}\\}}\cdot
W_{t}(\omega_{t},c_{t})\right]=\sum_{d_{t}:d_{t}\leq c_{t}}p_{t}(d_{t})\cdot
W_{t}(d_{t},c_{t})$

which enables us to get constraint (24a) in LP$(\bm{p},\bm{D})$. Finally,
multiplying both sides of (7b) by $p(\omega_{t})$ and summing over all
$\omega_{t}$ satisfying $d(\omega_{t})=d_{t}$, we get

$\displaystyle p_{t}(d_{t})\cdot W_{t}(d_{t},c_{t})$
$\displaystyle=\sum_{\omega_{t}:d(\omega_{t})=d_{t}}p(\omega_{t})\cdot
W_{t}(\omega_{t},c_{t})$
$\displaystyle\geq\sum_{\omega_{t}:d(\omega_{t})=d_{t}}p(\omega_{t})\cdot(r(\omega_{t})+V_{t+1}(c_{t}-d(\omega_{t}))-V_{t+1}(c_{t}))$
$\displaystyle=p_{t}(d_{t})\cdot(r(d_{t})+V_{t+1}(c_{t}-d_{t})-V_{t+1}(c_{t}))$

Thus, we get constraint (24b) in LP$(\bm{p},\bm{D})$. Note that the constraint
(7b) in $\text{Primal}(\bm{p},\bm{D})$ can also be recovered from constraint
(24b) in LP$(\bm{p},\bm{D})$, by setting

$W_{t}(\omega_{t},c_{t})=W_{t}(d_{t},c_{t})\text{\leavevmode\nobreak\
and\leavevmode\nobreak\ }r(\omega_{t})=r(d_{t})$

for all $\omega_{t}$ satisfying $d(\omega_{t})=d_{t}$, and all $d_{t}$. Thus,
we conclude that LP$(\bm{p},\bm{D})$ is a re-formulation of
$\text{Primal}(\bm{p},\bm{D})$ and it holds that

$\inf_{\mathcal{\hat{H}}}\frac{V_{1}^{*}(1)}{\textbf{UP}(\mathcal{\hat{H}})}=\inf_{(\bm{p},\bm{D}):\sum_{t=1}^{T}\sum_{d_{t}}p_{t}(d_{t})\cdot
d_{t}\leq
1}\text{Primal}(\bm{p},\bm{D})=\inf_{(\bm{p},\bm{D}):\sum_{t=1}^{T}\sum_{d_{t}}p_{t}(d_{t})\cdot
d_{t}\leq 1}\text{LP}(\bm{p},\bm{D})$

It remains to show that $\text{LP}(\bm{p},\bm{D})=\text{Dual}(\bm{p},\bm{D})$
for each $(\bm{p},\bm{D})$ satisfying
$\sum_{t=1}^{T}\sum_{d_{t}}p_{t}(d_{t})\cdot d_{t}\leq 1$.

We introduce the dual variable $\kappa_{t}(c_{t})$ for constraint (24a), the
dual variable $\alpha_{t}(d_{t},c_{t})$ for constraint (24b) and a dual
variable $\theta$ for constraint (24c). Then we have the following LP as the
dual of $\text{LP}(\bm{p},\bm{D})$.

$\displaystyle\leavevmode\nobreak\ \max\leavevmode\nobreak\
\leavevmode\nobreak\ \theta$ (26) $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ \mbox{s.t.}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \theta\cdot p_{t}(d_{t})\leq\sum_{c_{t}\geq
d_{t}}\alpha_{t}(d_{t},c_{t}),\leavevmode\nobreak\ \leavevmode\nobreak\
\forall t,\forall d_{t}$ $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \alpha_{t}(d_{t},c_{t})\leq
p_{t}(d_{t})\cdot\kappa_{t}(c_{t}),\leavevmode\nobreak\ \leavevmode\nobreak\
\forall t,\forall d_{t},\forall c_{t}\geq d_{t}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\kappa_{t}(c_{t})=\kappa_{t-1}(c_{t})+\sum_{d_{t-1}}(\alpha_{t-1}(d_{t-1},c_{t}+d_{t-1})-\alpha_{t-1}(d_{t-1},c_{t})),\leavevmode\nobreak\
\leavevmode\nobreak\ \forall t,\forall c_{t}\leq 1$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\kappa_{1}(1)=1$ $\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \alpha_{t}(d_{t},c_{t})=0,\leavevmode\nobreak\
\leavevmode\nobreak\ \forall t,\forall d_{t},\forall c_{t}>1$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\theta,\alpha_{t}(c_{t})\geq 0,\kappa_{t}(c_{t})\geq 0,\leavevmode\nobreak\
\leavevmode\nobreak\ \forall t,\forall c_{t}$

Note that from the binding constraints, it must hold

$\kappa_{t}(c_{t})=\kappa_{1}(c_{t})+\sum_{\tau\leq
t-1}\sum_{d_{\tau}}(\alpha_{\tau}(d_{\tau},c_{t}+d_{\tau})-\alpha_{\tau}(d_{\tau},c_{t}))$

where we set $\kappa_{1}(c)=0$ for all $c<1$. Thus, we further simplify the LP
(26) by eliminating variable $\kappa_{t}(c_{t})$, and derive LP
$\text{Dual}(\bm{p},\bm{D})$ in (8).

In order to establish the strong duality between $\text{LP}(\bm{p},\bm{D})$
and $\text{Dual}(\bm{p},\bm{D})$, we only need to check the so-called Slater’s
condition such that all the inequality constraints in
$\text{LP}(\bm{p},\bm{D})$ can be satisfied as strict inequality. Clearly,
this can be done by setting $\theta=0$ and iteratively setting
$\alpha_{t}(d_{t},c_{t})$ to be strictly smaller than the RHS of the
constraints (24b), (24c) for $t=1,\dots,T$. Thus, our proof is completed. ∎

##  8 Proofs in Section 4

###  B1 Proof of Lemma 4

We first present the following lemma, which show that instead of checking
whether all the constraints of $\text{Dual}(\bm{p},\bm{D})$ are satisfied, it
is enough to consider only one constraint.

###### Lemma 9

For any $\theta\in[0,1]$, $\\{\theta,x_{l,t}(\theta)\\}$ is a feasible
solution to $\text{Dual}(\bm{p},k)$ if and only if
$\sum_{\tau=1}^{T-1}x_{k,\tau}(\theta)\leq 1-\theta$.

The proof is relegated to Section B2. We now prove the condition on $\theta$
such that $\sum_{\tau=1}^{T-1}x_{k,\tau}(\theta)\leq 1-\theta$. Due to Lemma
9, this condition implies the feasibility condition of
$\\{\theta,x_{l,t}(\theta)\\}$. Specifically, we will first show that the term
$\sum_{t=1}^{T-1}x_{k,t}(\theta)$ is continuously monotone increasing with
$\theta$ in the next lemma, where the formal proof is in Section B3.

###### Lemma 10

For any $1\leq l\leq k$ and any $1\leq t\leq T$, define
$y_{l,t}(\theta)=\sum_{\tau=1}^{t}x_{l,t}(\theta)$. Then $y_{l,t}(\theta)$ is
monotone increasing with $\theta$ and $y_{l,t}(\theta)$ is also Lipschitz
continuous with $\theta$.

We are now ready to prove Lemma 4.

###### Proof.

Proof of Lemma 4: Note that when $\theta=0$,
$y_{k,T-1}(0)=\sum_{\tau=1}^{T-1}x_{k,\tau}(0)=0<1-\theta=1$, and when
$\theta=1$, $y_{k,T-1}(1)=\sum_{\tau=1}^{T-1}x_{k,\tau}(1)>0=1-\theta$.
Further note that $1-\theta$ is continuously strictly decreasing with $\theta$
while Lemma 10 shows that
$y_{k,T-1}(\theta)=\sum_{\tau=1}^{T-1}x_{k,\tau}(\theta)$ is continuously
increasing with $\theta$, there must exist a unique $\theta^{*}\in[0,1]$ such
that $\sum_{\tau=1}^{T-1}x_{k,\tau}(\theta^{*})=1-\theta^{*}$ and for any
$\theta\in[0,\theta^{*}]$, it holds that
$\sum_{\tau=1}^{T-1}x_{k,\tau}(\theta)\leq 1-\theta$. Combining the above
arguments with Lemma 9, we complete our proof. ∎

###  B2 Proof of Lemma 9

We first prove that for any $\theta\in[0,1]$, $\\{x_{l,t}(\theta)\\}$ are non-
negative.

###### Lemma 11

For any $\theta\in[0,1]$, we have $x_{l,t}(\theta)\geq 0$ for any
$l=1,\dots,k$ and $t=1,\dots,T$.

###### Proof.

Proof: We now use induction on $l$ to show that for any $l$, we have that
$x_{l,t}(\theta)\geq 0$ and $\sum_{v=1}^{l}x_{v,t}(\theta)\leq\theta\cdot
p_{t}$ for any $t$. Since we focus on a fixed $\theta$, we abbreviate $\theta$
in the expression $x_{l,t}(\theta)$ and substitute $x_{l,t}$ for
$x_{l,t}(\theta)$ in the proof.

For $l=1$, from definition, we have that for $1\leq t\leq t_{2}$, it holds
that $x_{1,t}\geq 0$ and $\sum_{v=1}^{1}x_{v,t}\leq\theta\cdot p_{t}$. We now
use induction on $t$ to show that for $t_{2}+1\leq t\leq T$, we have that
$0\leq x_{1,t}\leq\theta\cdot p_{t}$. Note that from definition, we have that

$x_{1,t_{2}+1}=p_{t_{2}+1}\cdot(1-\sum_{\tau=1}^{t_{2}}\theta\cdot
p_{\tau})<p_{t_{2}+1}\cdot\theta$

Also, note that $1-\sum_{\tau=1}^{t_{2}-1}\theta\cdot p_{\tau}\geq\theta$ and
$p_{t_{2}}\leq 1$, we have that

$1-\sum_{\tau=1}^{t_{2}}\theta\cdot p_{\tau}\geq
1-\sum_{\tau=1}^{t_{2}-1}\theta\cdot p_{\tau}-\theta\geq 0$

Thus, it holds that

$0\leq x_{1,t_{2}+1}=p_{t_{2}+1}\cdot(1-\sum_{\tau=1}^{t_{2}}\theta\cdot
p_{\tau})<p_{t_{2}+1}\cdot\theta$

Now, suppose for a $t$ such that $t_{2}+1\leq t\leq T$, we have that $0\leq
x_{1,\tau}\leq\theta\cdot p_{\tau}$ for any $t_{2}+1\leq\tau\leq t$. Then we
have that

$x_{1,t+1}\leq p_{t+1}\cdot(1-\sum_{\tau=1}^{t}x_{1,\tau})\leq
p_{t+1}\cdot(1-\sum_{\tau=1}^{t_{2}}x_{1,\tau})=p_{t+1}\cdot(1-\sum_{\tau=1}^{t_{2}}\theta\cdot
p_{\tau})<p_{t+1}\cdot\theta$

Also, note that $x_{1,t}\geq 0$ implies that
$1-\sum_{\tau=1}^{t-1}x_{1,\tau}\geq 0$, we have that

$x_{1,t+1}/p_{t+1}=1-\sum_{\tau=1}^{t-1}x_{1,\tau}-x_{1,t}=(1-p_{t})\cdot(1-\sum_{\tau=1}^{t-1}x_{1,\tau})\geq
0$

It holds that $0\leq x_{1,t+1}\leq p_{t+1}\cdot\theta$. Thus, from induction,
for any $t$, we have proved that $0\leq x_{1,t}\leq p_{t}\cdot\theta$.

Suppose that for a $l$ such that $1\leq l\leq k$, we have that $x_{l,t}\geq 0$
and $\sum_{v=1}^{l}x_{v,t}\leq\theta\cdot p_{t}$ for any $t$. We now consider
the case for $l+1$. From definition, $x_{l+1,t}=0$ when $1\leq t\leq t_{l+1}$
and when $t_{l+1}+1\leq t\leq t_{l+2}$, $x_{l+1,t}=\theta\cdot
p_{t}-\sum_{v=1}^{l}x_{v,t}$. Thus, for $1\leq t\leq t_{l+2}$, we have proved
that $x_{l+1,t}\geq 0$ and $\sum_{v=1}^{l+1}x_{v,t}\leq\theta\cdot p_{t}$. We
now use induction on $t$ for $t>t_{l+2}$. When $t=t_{l+2}+1$, from definition,
we have that

$x_{l+1,t_{l+2}+1}=p_{t_{l+2}+1}\cdot\sum_{\tau=1}^{t_{l+2}}(x_{l,\tau}-x_{l+1,\tau})\leq\theta\cdot