14

#  Robust Secretary and Prophet Algorithms
for Packing Integer Programs††thanks: CJA and AG were supported in part by NSF
awards CCF-1907820, CCF1955785, and CCF-2006953. MM was partially supported by
the Coordenação de Aperfeiçoamento de Pessoal de Nivel Superior - Brasil
(CAPES) - Finance Code 001, CNPq Bolsa de Produtividade em Pesquisa
$\\#4$310516/2017-0 and FAPERJ grant Jovem Cientista do Nosso Estado.

C.J. Argue Carnegie Mellon University<EMAIL_ADDRESS>Anupam Gupta
Carnegie Mellon University<EMAIL_ADDRESS>Marco Molinaro PUC Rio,
<EMAIL_ADDRESS>Sahil Singla Georgia Tech<EMAIL_ADDRESS>
###### Abstract

We study the problem of solving Packing Integer Programs (PIPs) in the online
setting, where columns in $[0,1]^{d}$ of the constraint matrix are revealed
sequentially, and the goal is to pick a subset of the columns that sum to at
most $B$ in each coordinate while maximizing the objective. Excellent results
are known in the secretary setting, where the columns are adversarially
chosen, but presented in a uniformly random order. However, these existing
algorithms are susceptible to adversarial attacks: they try to “learn”
characteristics of a good solution, but tend to over-fit to the model, and
hence a small number of adversarial corruptions can cause the algorithm to
fail.

In this paper, we give the first robust algorithms for Packing Integer
Programs, specifically in the recently proposed Byzantine Secretary framework
[BGSZ20]. Our techniques are based on a two-level use of online learning, to
robustly learn an approximation to the optimal value, and then to use this
robust estimate to pick a good solution. These techniques are general and we
use them to design robust algorithms for PIPs in the prophet model as well,
specifically in the Prophet-with-Augmentations framework [ISW20]. We also
improve known results in the Byzantine Secretary framework: we make the non-
constructive results algorithmic and improve the existing bounds for single-
item and matroid constraints.

##  1 Introduction

Resource allocation is a central problem in online decision making: here, a
set of requests for resources arrive one-by-one, each having an associated
value. The goal is to accept a subset of the requests with a large total
value, subject to satisfying given resource constraints. In online algorithms,
we have to make these decisions sequentially and irrevocably, without the
knowledge of future requests. It is common to model these problems as _packing
integer programs_ (PIPs) of the form:

$\displaystyle\max\\{\langle c,x\rangle\mid Ax\leq
b,~{}x\in\\{0,1\\}^{n}~{}\\},$ (1)

where the columns of an unknown constraint matrix $A\in[0,1]^{d\times n}$
appear one-by-one, and the decisions of the algorithm are encoded as variables
$x_{t}\in\\{0,1\\}$.

Although online packing IPs are difficult to solve in the worst-case, one of
the remarkable successes has been for settings where the PIP instance is
chosen adversarially, but the columns are then presented in a _uniformly
random order_. If the constraints are “not-too-tight”, we can get very good
solutions: e.g., for a PIP where the constraint matrix $A\in[0,1]^{d\times n}$
and the entries of $b$ are $\Omega(\varepsilon^{-2}\log d)$, we know
algorithms that obtain a $(1-\varepsilon)$-approximation as long as the
columns of $A$ arrive in a uniformly random order [KRTV14, GM16, AD15]. In
fact, these results can be thought of as extensions of the _multiple-
secretary_ problem [Kle05] (which is the case where $d=1$ and the matrix $A$
is the all-$1$s matrix), and ultimately as extensions of the classical
_secretary problem_ [Dyn63] where the goal is to pick a single item to
maximize the value.

However, previous algorithms rely heavily on the random-order assumption, and
are susceptible to worst-case corruptions: If an adversary is allowed to add
in a small number of columns that arrive at specific times, most existing
algorithms for the random-order setting fail disastrously. E.g., the classical
single-item secretary algorithm—which waits for $n/e$ items and then picks the
first item bigger than all preceding items—fails even if a single high-value
item is added at the beginning. Many algorithms for solving LPs essentially
try to estimate duals/thresholds, which can be skewed by a small number of
adversarial items. In short, most current algorithms are non-robust, and seem
to over-fit to the model. Our central motivating questions are:

> _Can we get robust algorithms for online resource allocation, and for PIPs
> in particular? More broadly, when we give algorithms that make assumptions
> on the data, how do we ensure that their performance degrades gracefully as
> we allow adversarial corruptions?_

The _Byzantine secretary_ model [KM20, BGSZ20] is one attempt to model
adversarial corruptions in the random-order model. In this model, each request
(i.e., column of $A$) is either red (i.e., adversarial) or green (i.e.,
benign), where these colors are not known to the algorithm. The adversary
chooses the arrival time of each red column, whereas the green columns choose
their arrival times independently and uniformly at random. The benchmark is
now the value of the optimal green set (sometimes with one green item
removed).

In [BGSZ20], the authors give robust algorithms for the single- and multi-item
secretary settings, but leave open the question of getting robust algorithms
for the setting of packing integer programs. In this paper, we resolve this
question positively, and also give simpler and better robust algorithms for
the single-item case. Our techniques are general and also extend to robust
algorithms for PIPs in the prophet model, specifically to the Prophet-with-
Augmentations model of [ISW20].

###  1.1 Our Results

PIPs in the Byzantine Secretary Model. Our first set of results give robust
algorithms for packing integer programs. To state the result, let
$\mathcal{G}$ denote the green columns of matrix $A$, and let $g_{\max}$
denote the green column with largest value. Let
$\operatorname{OPT}(\mathcal{G})$ and $\operatorname{OPT}(\mathcal{G}\setminus
g_{\max})$ denote the optimal value of the offline PIP (1) when restricted to
the green columns, with and without $g_{\max}$ respectively.

######  Theorem 1.1 (Informal: Robust PIPs).

There exists an algorithm for packing integer programs with value
$\Omega(\operatorname{OPT}(\mathcal{G}\setminus g_{\max}))$ in the Byzantine
secretary model when the entries of $b$ are $\Omega(\operatorname{poly}(\log
n))$.

(See §2 for formal statements.) One may ask whether we can compare to
$\operatorname{OPT}(\mathcal{G})$ instead: sadly, [BGSZ20] showed instances
where it is impossible to compare to $\operatorname{OPT}(\mathcal{G})$ without
further assumptions. However, if we make (mild) regularity assumptions on the
input, we can indeed get much more nuanced results. Indeed, suppose we are
given even a very rough estimate of $\operatorname{OPT}(\mathcal{G})$—to
within _polynomial_ in $n$ factors—then we can achieve the following:

######  Theorem 1.2 (Informal: Robust PIPs with a Rough Estimate).

There exists algorithms for packing integer programs which take a rough
estimate of the $\operatorname{OPT}(\mathcal{G})$ and achieve the following
guarantees:

  * (i)

value $\operatorname{OPT}(\mathcal{G})\cdot\Omega(1)$ for any instance.

  * (ii)

value $\operatorname{OPT}(\mathcal{G})\cdot(1-\alpha-O(\varepsilon))$ for
instances where $\alpha$ is the fraction of red/adversarial columns and the
value of any $\approx\log d/\varepsilon^{4}$ columns accounts for only an
$\varepsilon$-fraction of the optimum (i.e., the optimal value is not
concentrated on a small set of columns).

Both these algorithms require that the entries of $b$ are at least
$B:=\Omega(\log d\cdot\log\\!\log n/\varepsilon^{4})$.

(See §2 and §5 for formal statements.) Note that the performance of this
algorithm in part (ii) approaches $1$ as the fraction $\alpha$ of adversarial
corruptions gets small. The algorithm of part (i) is the same as in Theorem
1.1, but we need new ideas for part (ii), the case of “smooth” instances where
the optimal value is spread out. Theorems 1.1 and 1.2 both use our technique
of _robust threshold estimation_ , which is based on two conceptually clean
ideas using tools from online learning: Firstly, we show that given an
estimate $\gamma\approx\frac{\operatorname{OPT}(\mathcal{G})}{B}$, we can pick
a set of items that achieve value close to $\operatorname{OPT}(\mathcal{G})$.
This uses a low-regret online linear optimization algorithm to learn a good
set of duals, which are then used to select items. Secondly, we break the time
horizon into $K$ pieces, and then use another online learning algorithm to
“learn” the parameter $\gamma$. This is where we use our coarse estimate of
the optimal value: it allows us to focus on a set of $O(\varepsilon^{-1}\log
n)$ possible values for $\gamma$. We discuss the technical ideas in §1.2.

PIPs in the Prophet-with-Augmentations Model. We think that our approach of
using online learning to get robust algorithms will be useful in other
contexts as well. As an example, we consider PIPs in the _prophet model_ where
the columns are known up-front, but the value of each column is independently
drawn from a known distribution. In the _prophet-with-augmentations_ model of
[ISW20], the adversary is allowed to adaptively add arbitrary positive
perturbations/augmentations to the random column values, and the algorithm has
to be robust to these augmentations. The algorithm competes against the base
instance, i.e., the expected value $\operatorname{OPT}_{base}$ of the offline
optimum when all perturbations are zero.

It may appear that adding positive perturbations should only improve the
algorithm’s performance, but [ISW20] show that the popular $1/2$-approximation
median threshold algorithm [SC84] for single-item prophets can become
arbitrarily bad due to augmentations. (The reason is similar to that for the
Byzantine Secretary model: the adversary can present a single high-valued item
in the beginning that is just above the threshold.) [ISW20] show how to avoid
these problems, and design robust prophet algorithms for the single-item and
uniform-matroid problems. In §4 we show robust prophet algorithms for the
general setting of PIPs, where our underlying technique is again based on
robust threshold estimation using tools from online learning.

######  Theorem 1.3 (Robust Prophet PIPs).

There exists an algorithm for packing integer programs that gets value
$\Omega(\operatorname{OPT}_{base})$ in the Prophet-with-Augmentations model
when the right-hand sides of the PIP are $\Omega(\log d)$.

Improved Results for Single-Item and Matroid Cases. Our next results improves
on those of [BGSZ20], for the case of picking a single item or an independent
set in a matroid. (Details in §3.)

######  Theorem 1.4 (Single-Item Probability Max).

There is an algorithm for the single-item Byzantine secretary problem that
picks value at least $\operatorname{OPT}(\mathcal{G}\setminus g_{\max})$ with
probability $\Omega\big{(}\nicefrac{{1}}{{\log n}}\big{)}$.

In the case of a single-item, observe that
$\operatorname{OPT}(\mathcal{G}\setminus g_{\max})$ is the same as the value
$\mathsf{val}(g_{2})$ of the 2nd-highest green item. The previous result of
[BGSZ20] was non-constructive, and only showed _existence_ of an algorithm
with success probability $\Omega\big{(}\nicefrac{{1}}{{(\log n)^{2}}}\big{)}$;
hence our result improves on the previous results both qualitatively and
quantitatively. We also improve the value maximization results of [BGSZ20].

######  Theorem 1.5 (Value-Maximization for Secretary Problems).

There exist algorithms for the following Byzantine secretary problems that aim
to maximize the expected value of selected items:

  * (i)

for the single-item case, we can get expected value
$\Omega\big{(}\nicefrac{{1}}{{\log^{*}n}}\big{)}\cdot\operatorname{OPT}(\mathcal{G}\setminus
g_{\max})$, and

  * (ii)

for the case of a matroid of rank $r$, we can get expected value
$\Omega\big{(}\nicefrac{{1}}{{\big{(}(\log^{*}n)^{2}\cdot\log
r\big{)}}}\big{)}\cdot\operatorname{OPT}(\mathcal{G}\setminus g_{\max})$

(See §6 for proofs.) The former result improves on the the previous expected
value of
$\Omega\big{(}\nicefrac{{1}}{{(\log^{*}n)^{2}}}\big{)}\cdot\operatorname{OPT}(\mathcal{G}\setminus
g_{\max})$, and the latter result improves the previous expected value of
$\Omega\big{(}\nicefrac{{1}}{{\log
n}}\big{)}\cdot\operatorname{OPT}(\mathcal{G}\setminus g_{\max})$ when the
rank $r$ is sufficiently smaller than the number of items $n$.

###  1.2 Our Techniques

The general idea of all our algorithms is to find _robust thresholds_. For
packing IPs in the secretary and prophet settings, these robust thresholds are
obtained by using a Multiplicative-Weight Updates (MWU) algorithm, and for
single-item probability/value maximization the idea is to perform a robust
binary search on a set of candidate thresholds as we gather more information
over time. Let us now flesh these ideas out in the context of two of our
results: for Byzantine PIPs and for single-item probability maximization.

#### Byzantine Packing IPs.

At a high level, our robust algorithm looks at a Lagrangified value
$c_{t}x_{t}-\gamma\langle\lambda_{t},A_{t}x_{t}\rangle$ of the $t^{th}$ item
to make its decision. Here the dual $\lambda_{t}$ (computed using MWU) puts a
relative “penalty” on each constraint, with higher penalties for constraints
that are more occupied. The scale parameter $\gamma$ balances between the
value and the occupation penalty. Given this, our algorithm
$\operatorname{Alg}(\gamma)$ picks item $t$ if its Lagrangian value is non-
negative, namely if $c_{t}\geq\gamma\langle\lambda_{t},A_{t}\rangle$. Variants
of this algorithm have been previously used to study packing IPs in the
_stochastic_ setting [AD15, GM16]. Our first algorithmic contribution is that
this algorithm can be made robust in the Byzantine Secretary model, _assuming
that the right $\gamma$ is known_. Intuitively, the algorithm has a “self-
correcting” nature that balances the occupation of the different constraints,
and the worst-case guarantees of MWU can be used to show its robustness.

In stochastic settings, the right $\gamma$ is easy to estimate from the
initial items; however, a few adversarial items can bias the estimation in the
Byzantine setting. So our second algorithmic contribution is to use a second
layer of learning to estimate $\gamma$. We break the time horizon into $K$
intervals, learn $\gamma_{1},\gamma_{2},\ldots,\gamma_{K}$ online and run
$\operatorname{Alg}(\gamma_{i},I_{i})$ in each interval $I_{i}$. The $i^{th}$
reward of expert $\gamma$ is the value the algorithm would have obtained on
interval $I_{i}$ is on using $\gamma$. Since MWU algorithms choose the
sequence $(\gamma_{i})_{i}$ to do almost as well as the right $\gamma^{*}$, we
get
$\sum_{i}\operatorname{Alg}(\gamma_{i},I_{i})\gtrsim\sum_{i}\operatorname{Alg}(\gamma^{*},I_{i})$,
which is essentially the value of the algorithm that knew the right
$\gamma^{*}$ in hindsight. One difficulty is that the additive regret
typically scales with the range of the possible rewards of the experts, and
the red items can make this range too big. To handle this we introduce a
truncation to these rewards (note we don’t know
$\operatorname{OPT}(\mathcal{G})$, so this step needs care), and also use a
recent multiscale experts result of [BDHN19] to make the regret scale with the
range of the reward of the _best expert_ , not with all the ranges.

This idea (with some changes) extends to the case of robust prophets. Again,
we define robust thresholds using MWU: we start off considering the
Lagrangified value $c_{t}x_{t}-\gamma\langle\lambda_{t},A_{t}x_{t}\rangle$ of
the $t^{th}$ item to make our decisions. The challenge of estimating the right
$\gamma$ now becomes simpler since we are given the distributions. But a new
challenge arises: the expected occupation is different at each time step $t$
(which was not the case with random-order). To handle this issue and get the
eventual solution, we further refine the Lagrangian penalty function (see §4
for details).

#### Single-item: probability maximization.

The classical secretary algorithm has two phases: _sample_ items to estimate a
good threshold and _select_ an item above the threshold. Recall that an
adversary can thwart such an algorithm by sending a red item of very large
value in the sample phase (which makes the threshold too high, so the
algorithm does not pick any item). However, this failure gives us information:
namely, that the max value seen in the sample phase is an upper bound on the
value of future items. By running $O(\log n)$ copies of the secretary
algorithm with distinct sample phases, we can force the adversary to plant a
high-valued red item in each sample phase, and these values must decrease over
time. (Running these multiple algorithms picks up to $O(\log n)$ items, but we
can subsample down to 1; this is where we lose our approximation factor.)

Now, assuming this nice structure, we can give our Search procedure that takes
an initial set of candidate thresholds and narrows it down as it gets more
information, using a robust binary-search procedure. The algorithm uses the
values of items in an initial prefix $I_{0}=[0,\frac{1}{4}]$ as a candidate
set $\Theta$ for the “right” threshold $\mathsf{val}(g_{2})$. At each time, it
maintains upper and lower estimates that is used to filter these candidates:

  * 1.

The upper bound $\widehat{u}$ is the maximum value seen in the previous
interval, and the lower bound $\widehat{\ell}$ is the maximum value we have
picked so far.

  * 2.

The threshold for the current interval is the median of the “surviving”
candidates of $\Theta$, namely those of value in
$(\widehat{\ell},\widehat{u}]$. These have value strictly above what we have
already picked.

  * 3.

The algo picks the first item in the interval that is above this threshold.

Suppose that, as discussed above, all intervals have a high-value item;
namely, the maximum-value item $\rho_{i}$ of the $i$th interval has value
$\geq\mathsf{val}(g_{2})$. Then the upper bound $\widehat{u}$ never excludes
the “right” threshold $\mathsf{val}(g_{2})$. Moreover, assume that these max
values $\rho_{i}$ are non-increasing. In this case, the set of surviving
candidates halves in each interval! Indeed, if we pick an item in the interval
the lower bound increases to the median value, else all items in the interval
were below the median and the upper bound decreases to the current median
value. Since there are more than $\log n$ intervals, at some point the set of
candidates becomes empty. Now if $g_{2}$ comes in interval $I_{0}$ (which
happens with probability $\frac{1}{4}$), the right threshold
$\mathsf{val}(g_{2})$ is an initial candidate but the lower bound must have
excluded it, so we have already picked an item with at least this much value.

The idea for our _value-maximization_ algorithms is to iteratively refine the
thresholds: we start with a polynomially-approximate threshold, but each time
we pick an item, we prove that we either get good expected value, or else we
get an exponentially-better threshold. Naturally, this has to be done
robustly, so that the red items have a limited impact.

###  1.3 Further Related Work

See [GS20] for general works on random-order online problems. In particular,
generalizations to matroid and Packing LPs in stochastic models have been
extensively studied, e.g., see [BIKK18, Lac14, FSZ15] for matroids and
[KRTV14, GM16, AD15] and references therein for packing. In the last two
decades, there is a long line of work extending the classical single-item
$\nicefrac{{1}}{{2}}$-approximation prophet inequality [KS77, SC84] to packing
constraints. In particular, see [KW12] for matroids and [Rub16, RS17] for
arbitrary packing constraints. For applications of prophet inequalities to
pricing mechanisms and online algorithms, we suggest the tutorial [FKS21] and
the survey [Luc17].

The above online algorithms for secretary and prophet models rely heavily on
the stochastic assumption, and are susceptible to even slight worst-case
corruptions. We believe that the robust algorithms in this paper are
interesting in their own right. They bridge the gap between the (optimistic)
stochastic and (pessimistic) adversarial models, which has been a topic of
significant interest in both online algorithms [Mey01, MGZ12, KMZ15, KKN15,
EKM18, Mol17, KM20, GKRS20, Mol21] and online learning (see [LMPL18, GKT19]
and references within).

The recent paper [Mol21] considers a Byzantine-type model with adversarial and
stochastic items, and studies Online Convex Optimization and Welfare
Maximization problems. A major difference from our work is that both of these
problems are unconstrained. In [KM20], the authors consider the Knapsack
Secretary problem (i.e., PIP’s with a single constraint) in a similar
Byzantine model but with the additional assumption that the adversarial items
come in bursts. They obtain a $(1-\varepsilon)$-approximation when
$B\gtrsim\frac{1}{\varepsilon^{2}}$ and there are at most
$\approx\frac{n}{\sqrt{B}}$ adversarial items in bursts of size
$\approx\sqrt{B}$. Finally, [GKRS20] consider streaming problems (i.e. the
algorithm has limited memory) in a similar Byzantine model, and design
algorithms for max-matching and submodular maximization.

##  2 Byzantine Packing Integer Programs

In this section we discuss how to solve PIPs given in (1) and get a constant
factor of the expected optimal value. The approach will be to solve the its
_linear programming_ relaxation: since we assume that the right-hand sides are
large (i.e., $\Omega(\log d)$) compared to the entries of the constraint
matrix, scaling down the solution slightly and independently rounding each
variable immediately give an integer solution with almost as much value with
high probability.

Each item $i$ is a pair $(c_{i},a_{i})$ of a column $a_{i}\in[0,1]^{d}$ of
$A$, and its value $c_{i}\in\mathbb{R}_{\geq 0}$. The $n$ items consist of $G$
green items (denoted by $\mathcal{G}$) and $R=n-G$ red items (denoted by
$\mathcal{R}$). The arrival times of red items are chosen by an adversary.
Then each green item $i\in\mathcal{G}$ chooses its arrival time independently
and uniformly in the time horizon $[0,1]$.

Our algorithm breaks the time horizon $[0,1]$ into several intervals and
considers the items that fall into each interval seperately. To argue about
this and other objects, it is useful to define the induced LP (denoted
$\textrm{LP}(S)$) for any subset $S$ of columns/items:

$\displaystyle\max$ $\displaystyle~{}\textstyle\sum_{i\in S}c_{i}x_{i}$
($\textrm{LP}(S)$) s.t. $\displaystyle~{}\textstyle\sum_{i\in S}a_{i}x_{i}\leq
B\cdot\mathbbm{1}_{d}$ $\displaystyle~{}\mathbf{x}\in[0,1]^{n}\enspace,$

where $\mathbbm{1}_{d}$ is the $d$-dimensional all-ones vector. Let its
optimal solution be $\textbf{x}^{*}(S)$, having value $\langle
c,\textbf{x}^{*}\rangle=\operatorname{OPT}(S)$. By rescaling rows, we can
assume a common value $B$ on the RHS. We focus on two benchmarks:
$\operatorname{OPT}(\mathcal{G})$ and $\operatorname{OPT}(\mathcal{G}\setminus
g_{\max})$ where $g_{\max}$ denoting the green item with the highest value.

###  2.1 Algorithm Outline

The first step of our algorithm to reduce to solving the following “smooth”
instances:

######  Assumption 2.1 (Smooth Instance).

An instance with $\operatorname{OPT}:=\operatorname{OPT}(\mathcal{G})$ is
_smooth_ if:

  * 1.

the total value of the green items of value $>\frac{\operatorname{OPT}}{B}$ is
at most $\frac{\operatorname{OPT}}{2}$.

  * 2.

we are given an estimate $\widehat{O}$ for $\operatorname{OPT}$, such that
$\widehat{O}\in[\operatorname{OPT}/n,\operatorname{OPT}\cdot n]$.

######  Lemma 2.2 (Reduction to Smooth Instances).

Suppose $B\geq\Omega(\operatorname{poly}(\log n))$. Given an algorithm to
solve Packing LPs in the Byzantine Secretary setting that with constant
probability is $\rho$-competitive w.r.t. $\operatorname{OPT}(\mathcal{G})$ for
all smooth instances, we can obtain an algorithm which is
$\Omega(\rho)$-competitive in expectation for all instances w.r.t.
$\operatorname{OPT}(\mathcal{G}\setminus g_{\max})$.

Given this reduction (which is proved in §C), we prove our main result for
smooth instances:

######  Theorem 2.3 (Algorithm for Smooth Instances).

Suppose $B\geq\Omega\big{(}K\log(dK/\delta^{\prime})\big{)}$ and
$K\geq\Omega(\log\\!\log n)$. The solution returned by Algorithm 2 for a
smooth Byzantine Secretary instance satisfies:

  * i.

(Feasibility) The solution always packs into the modified budget of
$(B+K)\cdot\mathbbm{1}_{d}$.

  * ii.

(Value) The solution has value at least $\Omega(\operatorname{OPT})$ with
probability at least $1-\delta^{\prime}$.

We can scale down each $x_{t}$ by $\frac{B}{B+K}=1-o(1)$ to get a feasible
solution with the same value guarantee up to a constant. Then, applying Lemma
2.2 to Theorem 2.3 gives us the constant factor approximation of Theorem 1.1.
We now prove Theorem 2.3 in the rest of this section: here are the main
conceptual steps:

  * •

We break the time horizon into $K$ time intervals of equal size (we will
choose $K:=\Theta(\log\\!\log n)$). For interval $I$, use $\mathcal{G}(I)$ and
$G(I)$ to denote the green items and their number in $I$, respectively. Note
that $\mathbb{E}[G(I)]=|I|\cdot G$, where $|I|$ is the fraction of total time
$[0,1]$ covered by interval $I$.

  * •

In §2.2 we give our algorithm for a single interval $I$. Given a parameter
$\gamma$, this algorithm runs a low-regret OLO subroutine on a carefully
chosen Lagrangification of the problem. Let $\operatorname{Alg}(I,\gamma)$
denote the expected value that the algorithm gets when applied to interval $I$
with parameter $\gamma$, where the expectation is over the random arrival
times of the green items. Algorithm 1 gives a lower bound on
$\operatorname{Alg}(I,\gamma)$.

  * •

Finally, in §2.3 we use a multi-scale low regret algorithm to learn the
optimal choice of $\gamma$. This allows us to combine the single-interval
algorithms and prove Theorem 2.3.

###  2.2 Algorithm for a Single Interval

So in this section we fix an interval $I\subseteq[0,1]$, and give an algorithm
that gets good value in this interval as long as it knows the “correct” scalar
parameter $\gamma$. We use r.v.s $(C_{t},A_{t})$ to denote the value and size
of the $t$-th item that appears in this interval: these depend on which of the
items from $\mathcal{G}$ actually fall into this interval, and on their
locations. As mentioned before, the idea of the algorithm is to look at the
Lagrangified value $C_{t}x_{t}-\gamma\langle\lambda_{t},A_{t}x_{t}\rangle$ to
make the decision $x_{t}\in\\{0,1\\}$ to pick or not the $t$-th item in the
interval. The duals $\lambda_{t}$’s are computed using an online learning
algorithm and put a relative “price” on each constraint, with higher prices
for constraints that are more occupied.

To make this precise, let
$\triangle^{d-1}:=\big{\\{}\mathbf{p}\in[0,1]^{d}\mid\|\mathbf{p}\|_{1}=1\big{\\}}$
be the probability simplex. Given the algorithm’s choice ${x}_{t}\in[0,1]$ for
time step $t$, define the linear penalty function
$f_{t}:\triangle^{d-1}\to[0,1]$ as

$\displaystyle f_{t}(\lambda):=\langle\lambda,A_{t}{x}_{t}\rangle\enspace.$
(2)

The algorithm for interval $I$ (given a $\gamma$) is then described in
Algorithm 1. Note that the algorithm does not depend on the exact arrival
times of the items, just on their relative arrival order and step $t$ denotes
the $t$-th arrival in interval $I$.

Algorithm 1 IntervalByzLP$(I,\gamma)$

1:for steps $t=1,2,\ldots$ in interval $I$ do

2: Use the low-regret OLO algorithm from Lemma A.1 with
$\varepsilon=\frac{1}{2}$ on $f_{1},\ldots,f_{t-1}$ to get
${\lambda}_{t}\in\triangle^{d-1}$

3: Compute ${x}_{t}\in[0,1]$ maximizing $x\mapsto
C_{t}x-\gamma\langle{\lambda}_{t},A_{t}x\rangle$

4: break if the scaled budget is violated, i.e., if a coordinate of
$\sum_{s\leq t}A_{s}{x}_{s}$ exceeds $B\,|I|$

In the rest of this section, we prove a lower bound on the value that this
algorithm obtains over the interval $I$. For that, let $x^{*}$ denote the
optimal solution consisting only of green items whose value is at most
$\frac{OPT}{B}$. By Assumption 2.1, this solution has value at least
$\frac{OPT}{2}$. Also, define for any set $S$ of timesteps the Lagrangified
value of the optimal solution using the algorithm’s choices of
$\gamma{\lambda}_{t}$’s as the Lagrangian multipliers:
$\textstyle\mathcal{L}(S,\gamma):=\sum_{t\in
S}\Big{(}C_{t}x^{*}_{t}-\gamma\langle{\lambda}_{t},A_{t}x^{*}_{t}\rangle\Big{)}.$
Let $\operatorname{\mathcal{G}_{T}}(I)\subseteq\mathbb{N}$ denote the steps
$t$ where the $t$-th item in the interval $I$ is green, which is a random set
since each green item chooses its arrival times uniformly at random in $[0,1]$
whereas the red items choose their arrival times adversarially.

The first step for analyzing our algorithm is showing that it obtains value in
$I$ comparable to the Lagrangified value of the optimal solution $x^{*}$ in
this interval.

######  Lemma 2.4 (Value Comparable to Lagrangified $\operatorname{OPT}$).

For any $I\subseteq[0,1]$ and $\gamma>0$, we have

$\displaystyle\operatorname{Alg}(I,\gamma)~{}\geq~{}\min\Big{\\{}\tfrac{1}{2}\,|I|\gamma
B~{},~{}\mathcal{L}\big{(}\operatorname{\mathcal{G}_{T}}(I),\gamma\big{)}\Big{\\}}-2\gamma\log
d\enspace.$ (3)

###### Proof.

Consider the algorithm’s run. Let $\tau$ be the number of items seen when the
algorithm stops; that is, the smallest value $\tau$ such that
$\sum_{t\leq\tau}A_{t}{x}_{t}\not\leq|I|\cdot B\cdot\mathbbm{1}_{d}$. If the
algorithm does not exhaust the budget, set $\tau$ to be the number of items
$|\operatorname{items}(I)|$ in interval $I$. The value of the algorithm is
exactly $\sum_{t\leq\tau}C_{t}{x}_{t}$ and its occupation is
$\sum_{t\leq\tau}A_{t}{x}_{t}$.

#### Case 1 (Budget exhausted):

The multiplicative-plus-additive guarantees of the low-regret algorithm from
Lemma A.1 for $\varepsilon=1/2$ gives

$\displaystyle\textstyle\sum_{t\leq\tau}f_{t}({\lambda}_{t})~{}\geq~{}\frac{1}{2}\max_{\lambda\in\Delta^{d-1}}\sum_{t\leq\tau}f_{t}(\lambda)-2\log
d\enspace.$

Substituting the definition
$f_{t}(\lambda)=\langle\lambda,A_{t}{x}_{t}\rangle$, we get

$\displaystyle\textstyle\sum_{t\leq\tau}\langle{\lambda}_{t},A_{t}{x}_{t}\rangle~{}\geq~{}\frac{1}{2}\max_{\lambda\in\Delta^{d-1}}\,\sum_{t\leq\tau}\langle\lambda,A_{t}{x}_{t}\rangle-2\log
d~{}=~{}\frac{1}{2}\|A_{1}{x}_{1}+\ldots+A_{\tau}{x}_{\tau}\|_{\infty}-2\log
d\enspace.$

Hence, we can infer that

$\displaystyle\sum_{t\leq\tau}C_{t}{x}_{t}~{}-~{}\frac{\gamma}{2}\cdot\|A_{1}{x}_{1}+\ldots+A_{\tau}{x}_{\tau}\|_{\infty}$
$\displaystyle~{}\geq~{}\sum_{t\leq\tau}C_{t}{x}_{t}-\gamma\sum_{t\leq\tau}\langle{\lambda}_{t},A_{t}{x}_{t}\rangle-2\gamma\log
d~{}\geq~{}-\,2\gamma\log d,$ (4)

where the second inequality uses that ${x}_{t}$ is a best-response, and hence
is no worse than playing $x=0$. Moreover, if we exhaust our budget, the
occupation $\|\sum_{t\leq\tau}A_{t}{x}_{t}\|_{\infty}\geq|I|\cdot B$, and thus

$\displaystyle\textstyle\sum_{t\leq\tau}C_{t}{x}_{t}~{}\geq~{}\mathbf{1}{\text{(budget
exhausted)}}\cdot\frac{1}{2}\gamma|I|\cdot B-2\gamma\log d\enspace.$ (5)

#### Case 2 (Budget left):

To give a lower bound on the value in the case we do not exhaust our budget,
we use that for any $t$ the value $x^{*}_{t}$ is not a better response than
${x}_{t}$:

$\displaystyle
C_{t}{x}_{t}~{}\geq~{}C_{t}{x}_{t}-\gamma\langle{\lambda}_{t},A_{t}{x}_{t}\rangle~{}\geq~{}C_{t}x^{*}_{t}-\gamma\langle{\lambda}_{t},A_{t}x^{*}_{t}\rangle\enspace.$

Summing over all times and using the non-negativity of $C_{t}{x}_{t}$ to drop
the red items,

$\displaystyle\textstyle\sum_{t\leq\tau}C_{t}{x}_{t}~{}\geq~{}\sum_{t\in\operatorname{\mathcal{G}_{T}}(I),\,t\leq\tau}C_{t}{x}_{t}~{}\geq~{}\sum_{t\in\operatorname{\mathcal{G}_{T}}(I),\,t\leq\tau}\Big{(}C_{t}x^{*}_{t}-\gamma\langle{\lambda}_{t},A_{t}x^{*}_{t}\rangle\Big{)}\enspace.$

But when the algorithm does not exhaust its budget, the RHS is precisely
$\mathcal{L}\big{(}\operatorname{\mathcal{G}_{T}}(I),\gamma\big{)}$, and so

$\displaystyle\sum_{t\leq\tau}C_{t}{x}_{t}~{}\geq~{}\mathbf{1}{\text{(budget
left)}}\cdot\mathcal{L}\big{(}\operatorname{\mathcal{G}_{T}}(I),\gamma\big{)}\enspace.$
(6)

Combining (5) and (6) concludes the proof. ∎

The final piece is to lower bound the Lagrangified value of the optimal
solution $x^{*}$ on the interval $I$. The proof of this lemma crucially uses
the random arrival times of the green items.

######  Lemma 2.5.

Let $|I|\leq\tfrac{1}{4}$ and
$B\geq\Omega\big{(}\frac{\log(4d/\delta)}{|I|}\big{)}$. Then for any
$\gamma>0$,

$\displaystyle\Pr\Big{[}\mathcal{L}\big{(}\operatorname{\mathcal{G}_{T}}(I),\gamma\big{)}~{}\geq~{}|I|\cdot\big{(}\tfrac{\operatorname{OPT}}{4}-4\gamma
B\big{)}\Big{]}\geq 1-\delta\enspace,$

where the probability is taken over the random arrival times of the green
items.

We give the essential intuition of this lemma here (at least in expectation)
and defer the details to Section C.1. Consider any timestep
$t\in\operatorname{\mathcal{G}_{T}}(I)$:

$\displaystyle\mathbb{E}\Big{[}C_{t}x^{*}_{t}-\gamma\langle{\lambda}_{t},A_{t}x^{*}_{t}\rangle\Big{]}~{}\geq~{}\tfrac{\operatorname{OPT}}{2G}-\gamma\mathbb{E}\Big{[}\langle{\lambda}_{t},A_{t}x^{*}_{t}\rangle\Big{]}\enspace,$
(7)

where the expectation is over the random ordering. For intuition only, suppose
each column $A_{t}$ is an i.i.d. sample (this is not w.l.o.g.), so that
$A_{t}x^{*}_{t}$ is independent of ${\lambda}_{t}$. Then the expectation can
be pushed into the inner product; hence if there are $G$ green items overall,
the expected value $\mathbb{E}[A_{t}x^{*}_{t}]\leq B/G\cdot\mathbbm{1}_{d}$,
and so

$\displaystyle\mathbb{E}\Big{[}C_{t}x^{*}_{t}-\gamma\langle{\lambda}_{t},A_{t}x^{*}_{t}\rangle\Big{]}~{}~{}\geq~{}~{}\tfrac{\operatorname{OPT}}{2G}-\gamma\langle\mathbb{E}{\lambda}_{t},\tfrac{B}{G}\cdot\mathbbm{1}_{d}\rangle~{}~{}\geq~{}~{}\tfrac{\operatorname{OPT}}{2G}-\gamma\tfrac{B}{G}\enspace,$
(8)

where the last inequality uses that ${\lambda}_{t}\in\Delta^{d-1}$. Finally,
$\mathbb{E}[|\operatorname{\mathcal{G}_{T}}(I)|]=|I|\cdot G$, so we get
$\mathbb{E}[\mathcal{L}]\geq|I|(\frac{\operatorname{OPT}}{2}-\gamma B)$ to
complete the proof of Lemma 2.5 in expectation. However, the reason why this
is just intuition and not a proof is that we sample _without replacement_ , so
${\lambda}_{t}$ (which depends on the $t-1$ first items on the interval $I$)
is correlated with $A_{t}x^{*}_{t}$. To handle this, in Section C.1 we have to
argue why these correlations are small.

Combining these lemmas gives the desired guarantee for our algorithm.

######  Lemma 2.6 (Value of Algorithm 1).

Let $|I|\leq\tfrac{1}{4}$ and
$B\geq\Omega\big{(}\frac{\log(4d/\delta)}{|I|}\big{)}$. Then for any
$\gamma>0$, with probability at least $1-\delta$ we have

$\displaystyle\operatorname{Alg}(I,\gamma)\geq|I|\cdot\min\Big{\\{}\tfrac{\gamma
B}{2}\,,\,\tfrac{\operatorname{OPT}}{4}-4\gamma B\Big{\\}}-2\gamma\log d.$

As mentioned earlier, we see that a good choice of $\gamma$ is
$\Theta(\frac{\operatorname{OPT}}{B})$, but this requires us to know the value
of $\operatorname{OPT}$; we now show how another layer of online learning can
learn this value well enough.

###  2.3 A Robust LP Algorithm via Learning the Multiplier $\gamma$

We partition the time interval $[0,1]$ into $K$ intervals
$I_{1},I_{2},\ldots,I_{K}$ of equal size, and run Algorithm 1 in each interval
with the value of $\gamma$ learned from previous intervals via an online
learning algorithm. Formally, define the gain functions:

$\displaystyle\operatorname{Alg}_{i}(\gamma)$ $\displaystyle:=\textrm{value
from \lx@cref{creftypecap~refnum}{alg:AD-oneint} with parameter $\gamma$ over
the $i^{th}$ interval $I_{i}$ }$
$\displaystyle\overline{\operatorname{Alg}}_{i}(\gamma)$
$\displaystyle:=\min\\{\operatorname{Alg}_{i}(\gamma)~{},~{}\tfrac{B}{K}\gamma\\}\text{
the algorithm's truncated value}\enspace.$

Using Assumption 2.1 that we know $\operatorname{OPT}$ up to
$\operatorname{poly}(n)$ factors, let $\Gamma$ be a list of $O(\log n)$ values
that contains $\frac{\operatorname{OPT}}{16B}$ within a factor of 2. The
complete algorithm is the following:

Algorithm 2 ByzLP

1:for interval $i=1,\ldots,K$ do

2: pick ${\gamma}_{i}\in\Gamma$ using the multiscale experts algorithm of
Lemma A.2 on
$\overline{\operatorname{Alg}}_{1},\overline{\operatorname{Alg}}_{2},\ldots,\overline{\operatorname{Alg}}_{i-1}$.

3: run Algorithm 1 over interval $I_{i}$ with parameter ${\gamma}_{i}$,
thereby getting value $\operatorname{Alg}_{i}({\gamma}_{i})$.

###### Proof of Theorem 2.3.

Since there are $K$ intervals, the feasibility follows directly from the
stopping rule for the algorithm, and the fact that item sizes are at most $1$.
For the second claim, the value of the algorithm is
$\sum_{i}\operatorname{Alg}_{i}({\gamma}_{i})$, which is at least
$\sum_{i}\overline{\operatorname{Alg}}_{i}({\gamma}_{i})$, so it suffices to
lower bound the latter. Let $\gamma^{*}$ be a value in $\Gamma$ that is in
$\left[\frac{1}{32}\frac{\operatorname{OPT}}{B},\frac{1}{16}\frac{\operatorname{OPT}}{B}\right]$.
Due to the truncation $\overline{\operatorname{Alg}}_{i}(\gamma^{*})$ is
$O(\frac{\operatorname{OPT}}{K})$, so the multiscale regret guarantee of Lemma
A.2 with $\varepsilon=\Theta(\sqrt{\log|\Gamma|/K})$ gives that in every
scenario,

$\displaystyle\sum_{i}\overline{\operatorname{Alg}}_{i}({\gamma}_{i})~{}\geq~{}\sum_{i}\overline{\operatorname{Alg}}_{i}(\gamma^{*})-O(1)\cdot\sqrt{K\log|\Gamma|}\cdot\tfrac{\operatorname{OPT}}{K}~{}=~{}\sum_{i}\overline{\operatorname{Alg}}_{i}(\gamma^{*})-\operatorname{OPT}\cdot
O(\tfrac{\sqrt{\log\log n}}{\sqrt{K}})\enspace.$ (9)

Using the guarantee of Lemma 2.6 with $\delta=\frac{\delta^{\prime}}{K}$, we
have that with probability at least $1-\frac{\delta^{\prime}}{K}$, (using
$\operatorname{Alg}(I,\gamma^{*})$ for the value obtained by the algorithm of
the previous section, and $I_{i}$ for the $i$-th interval)

$\displaystyle\overline{\operatorname{Alg}}_{i}(\gamma^{*})~{}\geq~{}\min\big{\\{}\operatorname{Alg}(I_{i},\gamma^{*})~{},~{}\tfrac{\gamma^{*}B}{K}\big{\\}}~{}\geq~{}\tfrac{1}{K}\cdot\min\big{\\{}\tfrac{\gamma^{*}B}{2}~{},~{}\tfrac{\operatorname{OPT}}{4}-4\gamma^{*}B\big{\\}}-2\gamma^{*}\log
d\enspace,$

where the last inequality uses Lemma 2.4 and Lemma 2.5. Since
$\gamma^{*}\in\left[\frac{1}{32}\frac{\operatorname{OPT}}{B},\frac{1}{16}\frac{\operatorname{OPT}}{B}\right]$,
we get

$\overline{\operatorname{Alg}}_{i}(\gamma^{*})~{}\geq~{}\left(\tfrac{1}{K}\cdot\min\big{\\{}\tfrac{1}{64},\tfrac{1}{4}-\tfrac{1}{8}\big{\\}}-\tfrac{\log
d}{8B}\right)\operatorname{OPT}~{}\geq~{}\Omega(1)\cdot\tfrac{\operatorname{OPT}}{K}\enspace.$

Taking sum over all $K$ intervals we get with probability at least
$1-\delta^{\prime}$ that
$\sum_{i}\overline{\operatorname{Alg}}_{i}(\gamma^{*})\geq\Omega(\operatorname{OPT}).$
Using this on (9) and using $K\geq\Omega(\log\log n)$ concludes the proof of
Theorem 2.3. ∎

In §5 we give an algorithm that gets an approximation approaching $1$ when the
number of red items gets small, thereby proving Theorem 1.2.

##  3 Byzantine Secretary for Single-Item Probability Maximization

We now consider the (single-item) Byzantine Secretary Problem, where the
online model is exactly the same as in the previous section but now we can
only pick one item: the goal is to maximize the _probability_ of selecting an
item of value at least $\operatorname{OPT}(\mathcal{G}\setminus g_{\max})$,
i.e., the value of the second-most valuable green item. We show the following:

See 1.4

This improves on the algorithm of [BGSZ20], which (a) is nonconstructive,
relying on the use of Yao’s minimax principle, and (b) succeeds with a smaller
probability of $\Theta(1/\log^{2}n)$.

###  3.1 Algorithm

Our algorithm is based on two procedures, Struct and Search. Both pick
$K=O(\log n)$ items. We will show that with constant probability at least one
of Struct and Search succeeds in picking an item with value at least
$\operatorname{OPT}(\mathcal{G}\setminus g_{\max})$. By picking all items
chosen by either procedure, we get an algorithm that picks $2K=O(\log n)$
items and succeeds with probability $\Omega(1)$. Now picking uniformly at
random one of these $2K$ items, we get an algorithm that picks a single item
of value at least $\operatorname{OPT}(\mathcal{G}\setminus g_{\max})$ with
probability $\Omega(1/\log n)$. In §1.2 we outline the intuition behind these
algorithms.

For both our procedures, we partition the time interval
$(\frac{1}{4},\frac{3}{4}]$ into $K=\Theta(\log n)$ intervals
$I_{1},\dots,I_{K}$, each of equal width $\frac{1}{2K}$. Let
$I_{0}:=[0,\frac{1}{4}]$. For all $i$, let $\rho_{i}$ be the maximum value of
a _red item_ in interval $I_{i}$ and let $\widehat{\mu}_{i}$ be the maximum
value of any item in interval $I_{i}$ (note that $\rho_{i}$ is deterministic
but unknown to the algorithm and $\widehat{\mu}_{i}$ depends on when the green
items arrive). For an item $e$, let $\textsf{time}(e)$ and $\mathsf{val}(e)$
denote the arrival time and value of $e$ respectively. Recall that $g_{2}$ is
the 2nd-most valuable green item. To simplify the notation, let
$C^{*}:=\operatorname{OPT}(\mathcal{G}\setminus
g_{\max})=\mathsf{val}(g_{2})$.

The procedure Struct runs $K$ independent subroutines similar to the classic
single-item secretary algorithm: the $i^{th}$ one sets a threshold
$\widehat{\mu}_{i}$ and picks the first item after $I_{i}$ that reaches this
threshold.

Algorithm 3 Procedure Struct

1:for value $i=1,2,\ldots,K$ in parallel do

2: $\widehat{\mu}_{i}:=$ maximum value of any item seen in interval $I_{i}$

3: pick the first item (if any) arriving after interval $I_{i}$ with value at
least $\widehat{\mu}_{i}$.

The second procedure Search maintains a _set of candidate thresholds_
containing a subset of all the values $\widehat{\Theta}_{1}$ seen in interval
$I_{0}=[0,\tfrac{1}{4}]$. In each interval, the current candidate set is
obtained by focusing on these values lying between the maximum value of an
item seen in the previous interval, and the largest value item picked by this
procedure so far. The threshold for the current interval is set to the median
of these values. (We define $\operatorname{median}(\varnothing)=-\infty$.)

Algorithm 4 Procedure Search

1:for interval $i=1,2,\ldots,K$ do

2: $\widehat{L}_{i}\leftarrow$ max value of an item already picked by this
procedure, $-\infty$ if no item has been picked

3: $\widehat{U}_{i}\leftarrow\widehat{\mu}_{i-1}$ := maximum value of any item
seen in interval $I_{i-1}$

4:
$\widehat{\Theta}_{i}\leftarrow\\{\mathsf{val}(e)\mid\textsf{time}(e)\in[0,\frac{1}{4}]\text{
and }\widehat{L}_{i}<\mathsf{val}(e)\leq\widehat{U}_{i}\\}$

5: pick the first item (if any) in the interval $I_{i}$ having value at least
$\operatorname{median}(\widehat{\Theta}_{i})$

###  3.2 Analysis

It is clear that both procedures pick at most $K=O(\log n)$ items. We show
that with probability $\Omega(1)$, at least one of the two procedures picks an
item with value at least $C^{*}$. The intuition is this: if the maximum value
items in each interval are monotone decreasing and greater than $C^{*}$, then
in each interval procedure Search halves the candidate set size. If this set
contains the value $C^{*}$ (which happens, e.g., when $g_{2}$ arrives in the
interval $I_{0}$), then we must eventually pick an item of large value. Of
course, the maximum value items may not be monotone, and they may have values
below $C^{*}$, but then we show that Struct gets large value.

We now give the proof details. Recall that $\rho_{i}$ is the maximum value of
any red item in interval $I_{i}$; define $\rho_{i}\leftarrow-\infty$ if no
such items exist. We say an interval $I_{i}$ (including $I_{0}$) is _high_ if
$\rho_{i}\geq C^{*}$, and _low_ otherwise. Recall that the property of being
high just depends on the location of the red items, which we assume are
deterministically placed.

######  Lemma 3.1.

For any value of $K$, Struct succeeds (i.e. picks an item of value at least
$C^{*}$) with probability $\Omega(1)$ if either of the following properties
fail:

  * (i)

If $I_{i}$ and $I_{j}$ are high intervals with $i<j$, then
$\rho_{i}>\rho_{j}$.

  * (ii)

There are fewer than $\frac{K}{4}$ low intervals.

###### Proof.

Suppose property (i) fails, and let $I_{i}$ and $I_{j}$ be high intervals with
$i<j$ and $\rho_{i}\leq\rho_{j}$. The highness of $I_{i}$ implies
$\rho_{i}\geq C^{*}$. Now if $g_{\max}$ does not fall in $I_{i}$ (which
happens with probability $1-\nicefrac{{1}}{{2K}}$), then the maximum value
$\widehat{\mu}_{i}$ in this interval is $\rho_{i}$, and therefore the run of
Struct corresponding to interval $i$ sets a threshold of $\rho_{i}\geq C^{*}$.
This run would definitely select the item corresponding to $\rho_{j}$ in
$I_{j}$, if it has not picked an item earlier; this selected item has value at
least $\rho_{i}\geq C^{*}$.

Else suppose property (ii) fails, and there are at least $\nicefrac{{K}}{{4}}$
low intervals. If $g_{2}$ arrives in a low interval $I_{i}$, then we set the
threshold to be $\mathsf{val}(g_{2})=C^{*}$; now if $g_{\max}$ arrives in
$(\frac{3}{4},1]$, the $i^{th}$ run of Struct is guaranteed to pick an item.
Since there are at least $\frac{K}{4}$ low intervals, this event occurs with
probability at least
$\frac{K}{4}\cdot\frac{1}{2K}\cdot\frac{1}{4}\geq\frac{1}{32}$. ∎

The remainder of the proof shows that if the two properties of Lemma 3.1 are
indeed satisfied, then Search succeeds with constant probability. Define
$U_{i}:=\min\\{\rho_{j}\mid j<i\text{ and }I_{j}$ is high$\\}$, and

$\textstyle\Theta_{i}:=\\{\mathsf{val}(e)\mid\textsf{time}(e)\in\left[0,\frac{1}{4}\right]\text{
and }\widehat{L}_{i}<\mathsf{val}(e)\leq U_{i}\\}.$

The only difference from $\widehat{\Theta}_{i}$ is that the upper bound is
$U_{i}$ instead of $\widehat{U}_{i}$. (The intuition is that if property (i)
of Lemma 3.1 holds, then loosely speaking $\widehat{\Theta}_{i}$ and
$\Theta_{i}$ should behave similarly, and we can argue about the latter
instead of the former.) Observe that $\widehat{L}_{i}$ can only increase and
$U_{i}$ can only decrease, so $\Theta_{i}\supseteq\Theta_{i+1}$.

To make this precise, define an interval $I_{i}$ (for $i\geq 1$) to be _nice_
if the intervals $I_{i}$ and $I_{i-1}$ are both high, and moreover the item
$g_{\max}$ does not arrive in interval $I_{i-1}$. This property of being nice
does depend on the location of the top green item $g_{\max}$, but otherwise is
independent of the random locations of other green items.

######  Lemma 3.2.

If property (i) from Lemma 3.1 holds and the interval $I_{i}$ is nice, then
$|\Theta_{i+1}|\leq\frac{1}{2}|\Theta_{i}|$.

###### Proof.

Property (i) of Lemma 3.1 means the $\rho$-values of the high intervals are in
decreasing order, and the minimum in the definition of $U_{i}$ is achieved at
the last high interval before $i$. Since interval $I_{i-1}$ is high, we have
$U_{i}=\rho_{i-1}$. Moreover, $g_{\max}$ does not arrive in interval
$I_{i-1}$, and therefore $\rho_{i-1}=\widehat{\mu}_{i-1}$. This in turn means
that $U_{i}=\widehat{\mu}_{i-1}=\widehat{U}_{i}$, and
$\widehat{\Theta}_{i}=\Theta_{i}$.

If
$m_{i}:=\operatorname{median}(\Theta_{i})=\operatorname{median}(\widehat{\Theta}_{i})$,
then define $\Theta_{i}^{+}:=\\{v\in\Theta_{i}\mid v>m_{i}\\}$ and
$\Theta_{i}^{-}:=\\{v\in\Theta_{i}\mid v<m_{i}\\}$. Each has size at most
$\frac{1}{2}|\Theta_{i}|$. If the Search procedure chose an item in $I_{i}$,
then $\widehat{L}_{i+1}\geq m_{i}$ and therefore
$\Theta_{i+1}\subseteq\Theta_{i}^{+}$. Otherwise Search did not chose an item
in $I_{i}$, so all its items must have been smaller than $m_{i}$; in
particular, $\rho_{i}<m_{i}$. Since $I_{i}$ is high,
$u_{i+1}\leq\rho_{i}<m_{i}$ and $\Theta_{i+1}\subseteq\Theta_{i}^{-}$. ∎

######  Lemma 3.3.

Let $K=2\log_{2}n+4$. Then with probability $\Omega(1)$, at least one of
Struct and Search picks an item of value at least $C^{*}$.

###### Proof.

By Lemma 3.1, if either of its properties (i) or (ii) fails then Struct
succeeds with constant probability. So suppose both properties hold. Now
condition on the location of item $g_{\max}$; this decides on the niceness of
the intervals. Property (ii) being satisfied means there are at least
$K-\frac{K}{4}-\frac{K}{4}-1=K/2-1>\log_{2}n$ nice intervals. (Indeed, we may
discard at most $K/4$ intervals because $I_{i-1}$ is bad, $K/4$ others because
$I_{i}$ is bad, and one more because $g_{\max}$ falls in $I_{i-1}$.)

Now let us condition on the event that $g_{2}$ arrives in the time interval
$[0,\frac{1}{4}]$, which happens with probability $\nicefrac{{1}}{{4}}$. Since
$|\Theta_{1}|\leq n$, applying Lemma 3.2 (which relies on property (i)) to
each of the nice intervals implies that after $\log_{2}n$ nice intervals, we
get to some index $i$ for which $\Theta_{i}$ is empty, and interval $I_{i}$ is
nice. The upper bound $U_{i}$ for $\Theta_{i}$ is at least $C^{*}$, by
definition. Since item $g_{2}$ arrived in $[0,\frac{1}{4}]$ but yet
$C^{*}=\mathsf{val}(g_{2})\notin\Theta_{i}$, the only reason would be that
$\widehat{L}_{i}\geq C^{*}$. This means that Search must have already chosen
an item of value at least $C^{*}$. ∎

###### Proof of Theorem 1.4.

Since Struct and Search pick at most $K$ items each, the final algorithm is to
run a random one of these two algorithms, and to randomly output one of the
$K=O(\log n)$ items picked by that algorithm. This gives an item of value at
least $C^{*}$ with probability $\Omega(\nicefrac{{1}}{{\log n}})$. ∎

##  4 Prophet-with-Augmentations for Packing Integer Programs

To show the power of our robust threshold selection idea from §2, we use it to
give robust algorithms for PIPs in the _prophet model_ as well. Recall that in
the classic prophets model, the inputs are drawn from independent (but
possibly non-identical) distributions. Here we consider the _Prophets-with-
Augmentations_ model [ISW20], in which an adversary is allowed to perturb the
values by adding non-negative values. We now show how to make PIP algorithms
robust to such perturbations.

###  4.1 Model and Notation

We are given a _base prophet_ instance
$((a_{1},\mathcal{D}_{1}),\ldots,\allowbreak(a_{n},\mathcal{D}_{n}),B)$ with
budget $B\cdot\mathbbm{1}_{d}$ and $n$ items whose values will be perturbed by
an adversary. The $t^{th}$ item has a known deterministic size vector
$a_{t}\in[0,1]^{d}$ and an initially unknown value $V_{t}\geq 0$ that is drawn
independently from a known distribution $\mathcal{D}_{t}$. Items values are
revealed one-by-one, and before the $t$-th item’s value is revealed, an
adversary adds an unknown perturbation $R_{t}\geq 0$ to $V_{t}$. This
perturbation may depend on the history up to (and including) time $t$, as well
as the algorithm’s decisions up to time $t-1$. The player then sees
$C_{t}:=V_{t}+R_{t}$ and has to immediately pick or reject the item. The goal
is to pick a set of items that pack into the known budget
$B\cdot\mathbbm{1}_{d}$, in order to maximize the sum of seen values $C_{t}$
of the picked items.

The algorithm competes against the base instance, i.e., the expected offline
optimum when all perturbations $R_{t}$ are zero. Let
$\operatorname{OPT}_{base}$ be the value of this expected offline optimum. The
main result of this section is as follows.

See 1.3

To make our proofs simpler, we assume w.l.o.g. that there are no “large
values”. Here we sketch the proof; the full proof is deferred to §D.1.

######  Assumption 4.1.

Each distribution $\mathcal{D}_{t}$ is supported on values that are at most
$\frac{\operatorname{OPT}_{base}}{20}$.

###### Proof Sketch.

Consider running simultaneously an algorithm that obtains a constant
approximation under Assumption 4.1 and also an algorithm that picks the first
item that takes a value above $\frac{\operatorname{OPT}_{base}}{20}$.
Intuitively, in the scenarios where all items come up with value at most
$\frac{\operatorname{OPT}_{base}}{20}$ the approximation guarantee of the
first algorithm kicks in, and in the remaining scenarios the second algorithm
already guarantees value at least $\frac{\operatorname{OPT}_{base}}{20}$;
overall, we should get a constant approximation. Running both algorithm may
lead to budget occupation up to $(B+1)\cdot\mathbbm{1}_{d}$, but rescaling the
solution by $\frac{B}{B+1}>1-o(1)$ restores feasible while maintaining the
same approximation guarantee. ∎

###  4.2 Algorithm

The idea of the algorithm is similar to that used for Byzantine PIPs in §2: to
make decisions $x_{t}\in\\{0,1\\}$ based on the Lagrangified value
$C_{t}x_{t}-\gamma\langle\lambda_{t},a_{t}x_{t}\rangle$, for a scaling factor
$\gamma$. As before, the “right” value for $\gamma$ is
$\approx\frac{\operatorname{OPT}_{base}}{B}$. Previously we learned $\gamma$
over multiple intervals using online learning (since $\operatorname{OPT}$ was
not known), we can now directly compute it using the known value distributions
$\mathcal{D}_{t}$’s. However, new challenges arise. Firstly, we will again
need to bound a Lagrangified value of the offline optimum with _good
probability_ (as in Lemma 2.5), but since the optimal solution’s decisions to
pick items depend on the outcomes of the values of _all_ other items, we are
not guaranteed to have any concentration. (Previously $\operatorname{OPT}$ was
such that picking the $t$-th item only depended on the identity of that item.)
To fix this, we compare not against the optimal solution, but against a
surrogate $\psi_{t}(V_{t})\in\\{0,1\\}$ that makes decisions about item $t$
based only on its base value $V_{t}$. Another challenge is that the expected
occupation of such a solution is different in each time step $t$ (which was
not the case in random-order, see Equation 8): this makes it harder to bound
the quantity $\langle\lambda_{t},a_{t}\,\psi(V_{t})\rangle$. To fix this, we
define the Lagrangian in terms of the modified penalty function
$f_{t}(\lambda):=\langle\lambda,a_{t}x_{t}-a_{t}\,\mathbb{E}\psi_{t}(V_{t})\rangle$.
On a technical note, since this penalty can be negative, we consider $\lambda$
values in the “full-dimensional simplex” (including the 0 vector), namely
$\blacktriangle^{d}:=\\{\lambda\in[0,1]^{d}:\sum_{i}\lambda_{i}\leq 1\\}$.

To make this precise, we start with the existence of the good solution
$\psi_{1}(V_{1}),\ldots,\psi_{n}(V_{n})$ for the base prophet instance.
Similar solutions algorithms have been previously designed for related
problems (e.g., see [Ala14, AHL12]), and we defer the proof to Appendix D.2.

######  Lemma 4.2.

Given a base prophet instance
$((a_{1},\mathcal{D}_{1}),\ldots,\allowbreak(a_{n},\mathcal{D}_{n}),B)$, there
are functions $\psi_{1},\ldots,\psi_{n}$, where each $\psi_{t}$ maps the value
$V_{t}$ to a decision in $\\{0,1\\}$ such that:

  1. 1.

Total expected value
$\mathbb{E}[\sum_{t}V_{t}\,\psi_{t}(V_{t})]\geq\frac{\operatorname{OPT}_{base}}{4}$.

  2. 2.

Total expected utilization
$\mathbb{E}[\sum_{t}a_{t}\,\psi_{t}(V_{t})]\leq\frac{B}{4}\cdot\mathbbm{1}_{d}$.

We now describe our robust algorithm for the prophet-with-augmentations model.
To simplify notation, define $x^{*}_{t}:=\mathbb{E}[\psi_{t}(V_{t})]$, that
is, the probability that this solution picks the $t$-th item. Our algorithm
requires these $x^{*}_{t}$’s, but since they only depend on the distributions
of the $V_{t}$’s thay can be computed a priori. It also needs to know
$\operatorname{OPT}_{base}$ to set the value of $\gamma$, which can also be
computed a priori (and as the proof shows, a constant-factor approximation to
this value suffices).

Algorithm 5 Procedure Prophet-with-Augmentations

1:for steps $t=1,2,\cdots$ do

2: Compute $\lambda_{t}\in\blacktriangle^{d}$ by using the low-regret
algorithm of Lemma A.1 with $\varepsilon=\frac{1}{2}$ on the functions
$f_{1},\ldots,f_{t-1}$, where
$f_{t}(\lambda):=\langle\lambda,a_{t}x_{t}-a_{t}x^{*}_{t}\rangle$.

3: Compute $x_{t}\in[0,1]$ maximizing $x_{t}\mapsto
C_{t}x_{t}-\gamma\langle\lambda_{t},a_{t}x_{t}-a_{t}x^{*}_{t}\rangle$, where
$\gamma=\frac{\operatorname{OPT}_{base}}{B}$.

4: break if the budget is exhausted, i.e., if a coordinate of $\sum_{s\leq
t}a_{s}{x}_{s}$ exceeds $B$. Let $\tau$ denote this stopping time step, where
$\tau=n$ if the budget is never exhausted.

###  4.3 Analysis

We now analyze the above algorithm, proving that it attains the guarantee
stated in Theorem 1.3 under Assumption 4.1 (without loss of generality).
First, the algorithm violates the budget by at most +1, but this is easily
fixed by rescaling or subsampling, so we ignore this issue henceforth. To
prove that it gets high value, fix a scenario of $V_{t}$ and $R_{t}$. In this
scenario, since our decision $x_{t}$ is a best response, it is at least as
good as $\psi_{t}(V_{t})$. In other words, the best-response ensures

$\displaystyle\underbrace{\sum_{t\leq\tau}C_{t}x_{t}}_{=\operatorname{Alg}}-\gamma\underbrace{\sum_{t\leq\tau}\langle\lambda_{t},a_{t}(x_{t}-x^{*}_{t})\rangle}_{=:M_{lhs}}~{}\geq~{}\sum_{t\leq\tau}C_{t}\;\psi_{t}(V_{t})-\gamma\underbrace{\sum_{t\leq\tau}\langle\lambda_{t},a_{t}(\psi_{t}(V_{t})-x^{*}_{t})\rangle}_{=:M_{rhs}}.$

Rewriting, we get

$\displaystyle\operatorname{Alg}~{}\geq~{}\sum_{t\leq\tau}C_{t}\;\psi_{t}(V_{t})+\gamma
M_{lhs}-\gamma M_{rhs}.$ (10)

To lower bound the value of $\operatorname{Alg}$, we first lower bound
$M_{lhs}$. From the regret guarantee in Lemma A.1, we can compare against the
action $\lambda=0$ to infer

$\displaystyle M_{lhs}$ $\displaystyle~{}\geq~{}-O(\log d).$ (11)

Similarly, comparing against the action $\lambda=e_{i}$ we get (using
$|\langle e_{i},a_{t}(x_{t}-x^{*}_{t})\rangle|\leq\langle
e_{i},a_{t}x_{t}\rangle+\langle e_{i},a_{t}x^{*}_{t}\rangle$)

$\displaystyle M_{lhs}~{}\geq~{}\frac{1}{2}\langle
e_{i},{\textstyle\sum}_{t\leq\tau}a_{t}x_{t}\rangle-\frac{3}{2}\langle
e_{i},{\textstyle\sum}_{t\leq\tau}a_{t}x^{*}_{t}\rangle-O(\log d),$

which then implies

$\displaystyle M_{lhs}$
$\displaystyle~{}\geq~{}\frac{1}{2}\bigg{\|}\sum_{t\leq\tau}a_{t}x_{t}\bigg{\|}_{\infty}-\frac{3}{2}\bigg{\|}\sum_{t\leq\tau}a_{t}x^{*}_{t}\bigg{\|}_{\infty}-O(\log
d)$
$\displaystyle~{}\geq~{}\frac{1}{2}\bigg{\|}\sum_{t\leq\tau}a_{t}x_{t}\bigg{\|}_{\infty}-~{}\frac{3B}{8}~{}-O(\log
d),$ (12)

where the last inequality uses that
$\|\sum_{t\leq\tau}a_{t}x^{*}_{t}\|_{\infty}\leq B/4$ due to Item 2 in Lemma
4.2 and the definition $x^{*}_{t}=\mathbb{E}[\psi_{t}(V_{t})]$.

For the scenario when $\tau=n$, (10) and (11) give that

$\displaystyle\operatorname{Alg}~{}\geq~{}\sum_{\color[rgb]{0,0,1}t}C_{t}\;\psi_{t}(V_{t})-\gamma\cdot
O(\log d)-\gamma M_{rhs}.$

Note that the sum is now over all $t$, not only $t\leq\tau$. For the other
scenario, when $\tau<n$ (i.e., we exhaust the budget), we know that
$\|\sum_{t\leq\tau}a_{t}x_{t}\|_{\infty}>B$, and so using (10) and (12) we get

$\displaystyle\operatorname{Alg}~{}\geq~{}\frac{\gamma B}{8}-\gamma\cdot
O(\log d)-\gamma M_{rhs}.$

Taking a minimum of both the scenarios $\tau=n$ and $\tau<n$, we get the
following bound that holds for every scenario:

$\displaystyle\operatorname{Alg}~{}\geq~{}\min\bigg{\\{}\sum_{t}C_{t}\;\psi_{t}(V_{t})~{},~{}\frac{\gamma
B}{8}\bigg{\\}}~{}-\gamma\cdot O(\log d)~{}-\gamma M_{rhs}.$

To calculate $\mathbb{E}[M_{rhs}]$, notice that both $\mathbf{1}(\tau\geq t)$
and $\lambda_{t}$ depend only on the history up to time $t-1$. (This is where
we crucially use that the augmentations $R_{t}$ do not depend on the future.)
So taking conditional expectation,

$\displaystyle\mathbb{E}_{t-1}[\mathbf{1}(\tau\geq
t)\cdot\langle\lambda_{t},a_{t}(\psi_{t}(V_{t})-x^{*}_{t})\rangle]$
$\displaystyle~{}=~{}\mathbf{1}(\tau\geq
t)\cdot\langle\lambda_{t},a_{t}\,\mathbb{E}_{t-1}[\psi_{t}(V_{t})-x^{*}_{t}]\rangle$
$\displaystyle~{}=~{}\mathbf{1}(\tau\geq
t)\cdot\langle\lambda_{t},a_{t}\,\mathbb{E}[\psi_{t}(V_{t})-x^{*}_{t}]\rangle~{}=~{}0,$

where the second equality follows from the fact that $\psi_{t}$ decides based
only on $V_{t}$, and hence is independent of the past. Taking expectations and
summing over $t$ gives $\mathbb{E}[M_{rhs}]=0$. Hence,

$\displaystyle\mathbb{E}[\operatorname{Alg}]\geq\mathbb{E}\min\bigg{\\{}\sum_{t}C_{t}\;\psi_{t}(V_{t})~{},~{}\frac{\gamma
B}{8}\bigg{\\}}~{}-\gamma\cdot O(\log d).$ (13)

To prove Theorem 1.3, it suffices to show that the first term in the
minimization is $\Omega(\operatorname{OPT}_{base})$ with constant probability.
Notice that this term is always non-negative, and that the second term in the
minimization is $\Omega(\operatorname{OPT}_{base})$, since we set
$\gamma=\Theta(\frac{\operatorname{OPT}_{base}}{B}$).

######  Lemma 4.3.

With probability at least $0.6$ it holds that
$\sum_{t}C_{t}\;\psi_{t}(V_{t})\geq\Omega(\operatorname{OPT}_{base}).$

###### Proof.

First, we always have
$\sum_{t}C_{t}\;\psi_{t}(V_{t})\geq\sum_{t}V_{t}\;\psi_{t}(V_{t})$, since
$R_{t}\geq 0$. By the upper bound in Assumption 4.1 on $V_{t}$, and the fact
that $\psi_{t}(V_{t})\in[0,1]$ and that for any random variable
$X\in[0,\alpha]$ its variance satisfies
$\text{Var}(X)\leq\alpha\mathbb{E}[X]$, we have

$\text{Var}(V_{t}\,\psi_{t}(V_{t}))~{}\leq~{}\frac{\operatorname{OPT}_{base}}{20}\,\mathbb{E}[V_{t}\,\psi_{t}(V_{t})].$

Using the fact that $\psi_{t}(V_{t})$ are independent and Item 1 in Lemma 4.2,
we have

$\text{Var}\Big{(}\sum_{t}V_{t}\psi_{t}(V_{t})\Big{)}~{}\leq~{}\frac{\operatorname{OPT}_{base}}{20}\,\mathbb{E}\Big{[}\sum_{t}V_{t}\,\psi_{t}(V_{t})\Big{]}~{}\leq~{}\frac{1}{10}\Big{(}\mathbb{E}\Big{[}\sum_{t}V_{t}\,\psi_{t}(V_{t})\Big{]}\Big{)}^{2}.$

Applying Chebychev’s inequality, we have

$\displaystyle\Pr\Big{(}\sum_{t}V_{t}\,\psi_{t}(V_{t})\leq\tfrac{1}{2}\mathbb{E}\Big{[}\sum_{t}V_{t}\,\psi_{t}(V_{t})\Big{]}\Big{)}~{}\leq~{}0.4.$

Finally, using
$\mathbb{E}[\sum_{t}V_{t}\,\psi_{t}(V_{t})]\geq\frac{\operatorname{OPT}_{base}}{2}$
by Item 1 in Lemma 4.2 concludes the proof. ∎

Combining Lemma 4.3 with (13) shows the expected value of the algorithm is at
least a constant fraction of the $\operatorname{OPT}_{base}$, and hence proves
Theorem 1.3.

##  5 Refined Approximation for Byzantine Packing Integer Programs

We consider again the Byzantine Packing Integer Program problem
$\textrm{LP}(S)$ from §2. In contrast to the constant approximation presented
in that section, here we design a $(1-O(\varepsilon+\alpha))$-approximation
when only an $\alpha<1$ fraction of the items is red and a weak estimate of
$\operatorname{OPT}(\mathcal{G})$ is available.

######  Theorem 5.1.

Consider $\varepsilon\in(0,\frac{1}{10}]$ and $\delta\in[0,1]$ and assume
$B\geq\Omega\big{(}\frac{K\log(dK/\delta)}{\varepsilon^{2}}\big{)}$ and
$K\geq\Omega(\frac{\log\\!\log n+\log 1/\varepsilon}{\varepsilon^{2}})$.
Suppose the total value of the green items of value
$>\frac{\operatorname{OPT}}{B}$ is at most $\varepsilon\operatorname{OPT}$,
and that it is available an estimate
$\widehat{\operatorname{OPT}}\in[\frac{1}{n}\operatorname{OPT},n\operatorname{OPT}]$.
Then the solution returned by Algorithm 7 satisfies the following:

  * i.

(Feasibility) The solution always packs into the modified budget of
$(B+K)\cdot\mathbbm{1}_{d}$.

  * ii.

(Value) The solution has value at least
$(1-\alpha-O(\varepsilon))\operatorname{OPT}$ with probability at least
$1-\delta^{\prime}$, where $\alpha$ is the fraction of red items in the
instance.

Again notice that we can scale down the solution found by the algorithm by
$\frac{B}{B+K}=1-O(\varepsilon^{2})$ to get a feasible solution with the same
approximation guarantee.

The algorithm is very similar to the one used for the constant-factor
approximation in §2, but: 1) we now use a slightly modified version of
Algorithm 1 for each interval, and 2) we use a finer discretized set $\Gamma$
of possible $\gamma$’s. We now make these modifications precise and prove
Theorem 5.1.

###  5.1 Modified Version of Algorithm 1

As the “within-a-single-interval” algorithm we use the original Agrawal-
Devanur algorithm for Packing LP’s in the stochastic model [AD15] applied to
items in an interval $I$ with the scaled budget $|I|B$. Using again the r.v.s
$(C_{t},A_{t})$ to denote the value and size of the $t$-th item that appears
in this interval, the main difference between this new algorithm and Algorithm
1 is that it now uses the penalty functions

$\displaystyle\textstyle\tilde{f}_{t}(\lambda):=\langle\lambda,A_{t}x_{t}{\color[rgb]{0,0,1}-\frac{B\cdot\mathbbm{1}_{d}}{n}}\rangle,$

(recall that $n$ is the total number of items in the whole instance) and,
because some of the penalties can be negative, it considers $\lambda$ to be in
the “full-dimensional simplex” that includes the 0 vector, namely
$\blacktriangle^{d}:=\\{\lambda\in[0,1]^{d}:\sum_{i}\lambda_{i}\leq 1\\}$. The
motivation for the additional term $-\frac{B\cdot\mathbbm{1}_{d}}{n}$ is that
when there are few red items it helps canceling out the “first order term” of
the green $\operatorname{OPT}$’s occupation given that
$A_{t}x^{*}_{t}\leq\frac{B\mathbbm{1}_{d}}{G}\approx\frac{B\mathbbm{1}_{d}}{n}$.
For convenience, the algorithm is presented in Algorithm 6.

Algorithm 6 Modified IntervalByzLP$(I,\gamma)$

1:for steps $t=1,2,\cdots$ in interval $I$ do

2: Use the low-regret OLO algorithm from Lemma A.1 on
$\tilde{f}_{1},\ldots,\tilde{f}_{t-1}$ to get
${\lambda}_{t}\in{\color[rgb]{0,0,1}\blacktriangle^{d}}$.

3: Compute ${x}_{t}\in[0,1]$ maximizing $x\mapsto
C_{t}x-\gamma\langle{\lambda}_{t},A_{t}x\rangle$.

4: break if the scaled budget is violated, i.e., if a coordinate of
$\sum_{s\leq t}A_{s}{x}_{s}$ exceeds $B\,|I|$.

The following is the guarantee of this algorithm for interval $I$, with a
proof similar to that of Lemma 2.4.

######  Lemma 5.2.

Under the assumptions from Theorem 5.1, for any interval $I\subseteq[0,1]$
with $|I|=\frac{1}{K}$ and $\gamma\in[0,\frac{\operatorname{OPT}}{B}]$, with
probability at least $1-\delta$ we have

$\displaystyle\operatorname{Alg}(I,\gamma)~{}\geq~{}\frac{1}{K}\cdot\min\bigg{\\{}\gamma
B\,,\,\operatorname{OPT}-\alpha\gamma
B\bigg{\\}}~{}-~{}O\bigg{(}\frac{\varepsilon\operatorname{OPT}}{K}+\frac{\varepsilon\gamma
B}{K}+\frac{\varepsilon\gamma Bn_{I}}{n}\bigg{)}\enspace.$

###### Proof.

Let $G(I)$ be the number of green items in the interval $I$, and let $n_{I}$
be the total number of items in $I$. Again let $\tau$ be the number of items
seen when the algorithm stops.

Let $x^{*}$ be the optimal solution for the whole instance (not just on the
interval $I$) considering only the green items that have individual value at
most $\frac{\operatorname{OPT}}{B}$. Recall that by the assumption $x^{*}$ has
value at least $(1-\varepsilon)\operatorname{OPT}$. By the “best response”
definition of $x_{t}$ we have

$\displaystyle\sum_{t\leq\tau}C_{t}{x}_{t}-\gamma\sum_{t\leq\tau}\langle\lambda_{t},A_{t}{x}_{t}-\tfrac{B\mathbbm{1}_{d}}{n}\rangle~{}\geq~{}\underbrace{\sum_{t\leq\tau}C_{t}x^{*}_{t}-\gamma\sum_{t\leq\tau}\langle\lambda_{t},A_{t}x^{*}_{t}-\tfrac{B\mathbbm{1}_{d}}{n}\rangle}_{=:\widetilde{\mathcal{L}}(\gamma)}.$

Moreover, since for any $x\in[0,1]$ the absolute value of
$\langle\lambda_{t},A_{t}x-\tfrac{B\mathbbm{1}_{d}}{n}\rangle$ can be checked
to be at most
$\langle\lambda_{t},A_{t}x-\tfrac{B\mathbbm{1}_{d}}{n}\rangle+\frac{2B}{n}$,
by the regret guarantee of the OLO algorithm have

$\displaystyle\sum_{t\leq\tau}\langle\lambda_{t},A_{t}{x}_{t}-\tfrac{B\mathbbm{1}_{d}}{n}\rangle$
$\displaystyle\geq(1-\varepsilon)\max_{\lambda\in\blacktriangle^{d}}\,\sum_{t\leq\tau}\langle\lambda,A_{t}{x}_{t}-\tfrac{B\mathbbm{1}_{d}}{n}\rangle-\varepsilon\tau\frac{2B}{n}-\frac{\log
d}{\varepsilon}$
$\displaystyle\geq(1-\varepsilon)\max_{\lambda\in\blacktriangle^{d}}\,\sum_{t\leq\tau}\langle\lambda,A_{t}{x}_{t}-\tfrac{B\mathbbm{1}_{d}}{n}\rangle-O\bigg{(}\varepsilon\frac{Bn_{I}}{n}+\varepsilon\frac{B}{K}\bigg{)},$

where the last inequality uses the fact $B\geq\Omega(\frac{K\log
d}{\varepsilon^{2}})$. Combining these inequalities we get

$\displaystyle\operatorname{Alg}(I,\gamma)~{}\geq~{}\widetilde{\mathcal{L}}(\gamma)\,+\,\gamma(1-\varepsilon)\max_{\lambda\in\blacktriangle^{d}}\,\sum_{t\leq\tau}\langle\lambda,A_{t}{x}_{t}-\tfrac{B\mathbbm{1}_{d}}{n}\rangle-O\bigg{(}\varepsilon\frac{\gamma
Bn_{I}}{n}\bigg{)}-O\bigg{(}\varepsilon\frac{\gamma B}{K}\bigg{)}.$ (14)

The next step is to lower bound the “stopped Lagrangian”
$\widetilde{\mathcal{L}}(\gamma)$. Before that we need a simple concentration
on the number of green items on interval $I$.

######  Lemma 5.3.

With probability at least $1-\frac{\delta}{4}$ we have
$G_{I}\in[(1-\varepsilon)\frac{G}{K},(1+\varepsilon)\frac{G}{K}]$.

###### Proof.

The expected number of green items in $I$ is $\mathbb{E}G(I)=\frac{G}{K}$, and
$\text{Var}(G(I))\leq\mathbb{E}G(I)$ (since $G(I)$ is the sum of independent
random variables in $[0,1]$). Then Bernstein’s inequality (Lemma A.3) we have

$\displaystyle\Pr(|G(I)-G/K|>\varepsilon G/K)\leq
2\exp\bigg{(}-\frac{\frac{\varepsilon^{2}G^{2}}{2K^{2}}}{\text{Var}(G(I))+\frac{\varepsilon
G}{3K}}\bigg{)}\leq
2\exp\bigg{(}-\frac{3}{8}\frac{\varepsilon^{2}G}{K}\bigg{)}\leq\frac{\delta}{4},$
(15)

where the last inequality is because $G\geq(1-\varepsilon)B$ (since by
assumption the green items of value $>\frac{\operatorname{OPT}}{B}$ have total
value at most $\varepsilon\operatorname{OPT}$ there must be at least
$(1-\varepsilon)B$ other green items to obtain the remaining
$(1-\varepsilon)\operatorname{OPT}$ value) and $B\geq\Omega(\frac{K\log
1/\delta}{\varepsilon^{2}})$ ∎

Now we proceed with lower bounding $\widetilde{\mathcal{L}}(\gamma)$. For
that, let $\tilde{\tau}$ denote the number of green items in the interval $I$
before (and including) time step $\tau$.

######  Lemma 5.4.

With probability at least $1-\frac{\delta}{2}$,

$\displaystyle\widetilde{\mathcal{L}}(\gamma)~{}\geq~{}\frac{\tilde{\tau}}{G}\bigg{[}\operatorname{OPT}-\alpha\gamma
B\bigg{]}-O\bigg{(}\varepsilon\frac{\operatorname{OPT}+\gamma B}{K}\bigg{)}.$

###### Proof.

Recall that $G(I)$ denotes the number of green items that fall in interval
$I$, and let $t_{j}$ be the time step of the $j^{th}$ green item to appear in
interval $I$ (notice that the $t_{j}$’s are random). Then

$\displaystyle\widetilde{\mathcal{L}}(\gamma)~{}=~{}\sum_{t\leq\tau}C_{t}x^{*}_{t}-\gamma\sum_{t\leq\tau}\langle\lambda_{t},A_{t}x^{*}_{t}-\tfrac{B\mathbbm{1}_{d}}{n}\rangle~{}=~{}\sum_{j\leq\tilde{\tau}}C_{t_{j}}x^{*}_{t_{j}}-\gamma\sum_{j\leq\tilde{\tau}}\langle\lambda_{t_{j}},A_{j_{t}}x^{*}_{t_{j}}\rangle-\gamma\sum_{t\leq\tau}\langle\lambda_{t},\tfrac{B\mathbbm{1}_{d}}{n}\rangle.$
(16)

We lower bound the first two terms of the right-hand side with high
probability.

For that we condition on the number of green items on this interval $G(I)=N$
where $N\leq\frac{2G}{K}$. Also condition on the positions of the green items
$(t_{1},\ldots,t_{N})=:t_{\leq N}$. Notice that under this conditioning the
stochastic items $(C_{t_{j}},A_{t_{j}})$ are still sampled without replacement
from the green items. Therefore, the conditional expected revenue from one
(any) time step $t_{j}$

$\displaystyle\mu\,:=\,\mathbb{E}[C_{t_{j}}x^{*}_{t_{j}}\mid G(I)=N,t_{\leq
N}]$

takes value between $(1-\varepsilon)\frac{\operatorname{OPT}}{G}$ and
$\frac{\operatorname{OPT}}{G}$, and the conditional expected occupation

$\displaystyle\vec{\mu}:=\mathbb{E}[A_{t_{j}}x^{*}_{t_{j}}\mid
G(I)=N,\,t_{\leq N}]$

is coordinate-wise at most $\frac{B\mathbbm{1}_{d}}{G}$.

Moreover, the revenue is concentrated around the expectations: using the
maximal Bernstein inequality Lemma B.3 conditionally (with
$X_{j}:=C_{t_{j}}x^{*}_{t_{j}}$ and $M=\frac{\operatorname{OPT}}{B}$), we have

$\displaystyle\Pr\Big{(}\max_{\ell\leq
N}\big{|}{\textstyle\sum}_{j\leq\ell}(C_{t_{j}}x^{*}_{t_{j}}-\mu)\big{|}\geq\tfrac{\varepsilon
c\operatorname{OPT}}{K}~{}\Big{|}~{}G(I)=N,t_{\leq N}\Big{)}$
$\displaystyle~{}\leq~{}30\exp\Big{(}-\tfrac{\varepsilon^{2}B}{K}\cdot\min\big{\\{}\tfrac{2G}{KN}\,,\,1\big{\\}}\Big{)}~{}\leq~{}\tfrac{\delta}{8},$

for a suitably large constant $c$. Here the last inequality uses
$B\geq\Omega(\frac{K\log 1/\delta}{\varepsilon^{2}})$ and $N\leq\frac{2G}{K}$.
Notice that since $\tilde{\tau}\leq N$ this also implies concentration for the
sum $\sum_{j\leq\tilde{\tau}}(C_{t_{j}}x^{*}_{t_{j}}-\mu)$ with random range
$j\leq\tilde{\tau}$.

In addition, the occupation is also concentrated: applying Lemma B.1
conditionally we get

$\displaystyle\Pr\bigg{(}\sum_{j\leq\tilde{\tau}}\langle{\lambda}_{t_{j}},A_{t_{j}}x^{*}_{t_{j}}\rangle>(1+4\varepsilon)\sum_{j\leq\tilde{\tau}}\langle\lambda_{t},\vec{\mu}\rangle+\Omega\big{(}\tfrac{\log
d/\delta}{\varepsilon}\big{)}~{}\bigg{|}~{}G(I)=N,t_{\leq
N}\bigg{)}~{}\leq~{}\frac{\delta}{8}.$

Notice we can indeed apply Lemma B.1 because ${\lambda}_{t_{j}}$ is a function
of the green items before the $j^{th}$ green item in the interval, namely
$(C_{t_{1}},A_{t_{1}}),\ldots,(C_{t_{j-1}},A_{t_{j-1}})$ (it also depends on
the red items in $I$, but these are deterministic), and similarly
$\tilde{\tau}$ is a stopping time with respect to the sequence
$((C_{t_{j}},A_{t_{j}}))_{j}$ and $\tilde{\tau}\leq
G(I)=N\leq\frac{2G}{K}\leq\frac{G}{2}$. Taking a union bound over both
concentration inequalities and then expectation over $t_{\leq N}$ and over
$G(I)\leq\frac{2G}{K}$ and using the fact that $B\geq\Omega(\frac{K\log
d/\delta}{\varepsilon^{2}})$ to upper bound the term $\Omega\big{(}\frac{\log
d/\delta}{\varepsilon}\big{)}$ we get

$\displaystyle\Pr\bigg{(}\sum_{j\leq\tilde{\tau}}C_{t_{j}}x^{*}_{t_{j}}-\gamma\sum_{j\leq\tilde{\tau}}\langle{\lambda}_{t_{j}},A_{t_{j}}x^{*}_{t_{j}}\rangle<\tilde{\tau}\mu-(1+4\varepsilon)\gamma\sum_{j\leq\tilde{\tau}}\langle\lambda_{t},\vec{\mu}\rangle+\Omega\big{(}\varepsilon\tfrac{\operatorname{OPT}+\gamma
B}{K}\big{)}~{}\bigg{|}~{}G(I)\leq\frac{2G}{K}\bigg{)}\leq\frac{\delta}{4}.$

From Lemma 5.3, $G(I)\leq\frac{2G}{K}$ with probability at least
$1-\frac{\delta}{4}$, and so taking a union bound with the displayed
inequality and employing it on (16) we get that with probability at least
$1-\frac{\delta}{2}$ we have $G(I)\leq\frac{2G}{K}$ and

$\displaystyle\widetilde{\mathcal{L}}(\gamma)$
$\displaystyle\geq\tilde{\tau}\mu-(1+4\varepsilon)\gamma\sum_{j\leq\tilde{\tau}}\langle\lambda_{t},\vec{\mu}\rangle-\gamma\sum_{t\leq\tau}\langle\lambda_{t},\tfrac{B\mathbbm{1}_{d}}{n}\rangle+\Omega\big{(}\varepsilon\tfrac{\operatorname{OPT}+\gamma
B}{K}\big{)}$
$\displaystyle\geq(1-\varepsilon)\tilde{\tau}\tfrac{\operatorname{OPT}}{G}-(1+4\varepsilon)\gamma\sum_{j\leq\tilde{\tau}}\langle\lambda_{t},\tfrac{B\mathbbm{1}_{d}}{G}\rangle-\gamma\sum_{j\leq\tilde{\tau}}\langle\lambda_{t},\tfrac{B\mathbbm{1}_{d}}{n}\rangle+\Omega\big{(}\varepsilon\tfrac{\operatorname{OPT}+\gamma
B}{K}\big{)}$
$\displaystyle\geq(1-\varepsilon)\tilde{\tau}\tfrac{\operatorname{OPT}}{G}-\tilde{\tau}\gamma
B\big{[}\tfrac{1+4\varepsilon}{G}-\tfrac{1}{n}\big{]}+\Omega\big{(}\varepsilon\tfrac{\operatorname{OPT}+\gamma
B}{K}\big{)}$
$\displaystyle\geq(1-\varepsilon)\tilde{\tau}\tfrac{\operatorname{OPT}}{G}-\tilde{\tau}\gamma
B\big{[}\tfrac{1+4\varepsilon}{G}-\tfrac{1-\alpha}{G}\big{]}+\Omega\big{(}\varepsilon\tfrac{\operatorname{OPT}+\gamma
B}{K}\big{)},$

where the second follows inequality because
$\langle\lambda_{t},\mathbbm{1}_{d}\rangle\leq 1$ and the last inequality
follows from $G\geq(1-\alpha)n$, since by assumption at most an $\alpha$
fraction of the $n$ items are red. Finally, since $G(I)\leq\frac{2G}{K}$ we
have $\frac{\tilde{\tau}}{G}\leq\frac{G(I)}{G}\leq\frac{2}{K}$, and so all
terms depending on $\varepsilon$ can be absorbed by the last term
$O(\varepsilon\frac{\operatorname{OPT}+\gamma B}{K})$. The displayed
inequality then gives the desired result. ∎

Let $\mathcal{E}$ be the event where Lemmas 5.4 and 5.3 hold, so by a union
bound $\Pr(\mathcal{E})\geq 1-\delta$. Fix a scenario in $\mathcal{E}$, and
break the analysis into two cases depending whether the algorithm exhausts a
budget or not.

#### Case 1: $\tau<n_{I}$.

In this case the algorithm exhausted a budget $|I|B$ and hence

$\displaystyle\max_{\lambda\in\blacktriangle^{d}}\,\sum_{t\leq\tau}\langle\lambda,A_{t}{x}_{t}-\tfrac{B\mathbbm{1}_{d}}{n}\rangle~{}\geq~{}|I|B-\frac{\tau
B}{n}\,=\,\frac{B}{K}-\frac{\tau B}{n}.$

Since we are in a scenario in $\mathcal{E}$, (14) gives

$\displaystyle\operatorname{Alg}(I,\gamma)~{}$
$\displaystyle\geq~{}\frac{\tilde{\tau}}{G}\bigg{[}\operatorname{OPT}-\alpha\gamma
B\bigg{]}+(1-\varepsilon)\frac{\gamma B}{K}-2\varepsilon\frac{\gamma B\cdot
n_{I}}{n}-O\bigg{(}\varepsilon\frac{\operatorname{OPT}+\gamma B}{K}\bigg{)}$
$\displaystyle\geq~{}\frac{\gamma
B}{K}-O\bigg{(}\frac{\varepsilon\operatorname{OPT}}{K}+\frac{\gamma
B}{K}+\frac{\varepsilon\gamma B\cdot n_{I}}{n}\bigg{)},$

where the second inequality follows from the fact
$\gamma\leq\frac{\operatorname{OPT}}{B}$, which makes
$\frac{\tilde{\tau}}{G}[\operatorname{OPT}-\alpha\gamma B]\geq 0$ and so we
can just drop this term. This gives the first term in the minimum in Lemma
5.2.

#### Case 2: $\tau=n_{I}$.

Since we can take $\lambda=0$, we have

$\displaystyle\max_{\lambda\in\blacktriangle^{d}}\,\sum_{t\leq\tau}\langle\lambda,A^{t}{x}_{t}-\tfrac{B\mathbbm{1}_{d}}{n}\rangle\geq
0.$

Moreover, in the current case (and scenario in $\mathcal{E}$) we have
$\tilde{\tau}=G_{I}\geq(1-\varepsilon)\frac{G}{K}$. Thus, using Lemma 5.2 and
inequality (14) we get

$\displaystyle\operatorname{Alg}(I,\gamma)~{}\geq~{}\frac{(1-\varepsilon)}{K}\bigg{[}\operatorname{OPT}-\alpha\gamma
B\bigg{]}-\varepsilon\frac{\gamma
Bn_{I}}{n}+O\bigg{(}\varepsilon\frac{\operatorname{OPT}+\gamma B}{K}\bigg{)}.$

This gives the second term in the minimum in Lemma 5.2, and concludes the
proof of the lemma. ∎

###  5.2 Modified Version of Algorithm 2

The only modification to the “across intervals” Algorithm 2 from §2.3 is to
run it using the previous “within-a-single-interval” Algorithm 6 and to use a
finer grid $\Gamma_{\varepsilon}$ of size $O(\frac{\log n}{\varepsilon})$ that
contains $\frac{\operatorname{OPT}}{B}$ within a factor of $(1-\varepsilon)$,
constructed based on the assumed estimate of $\operatorname{OPT}$ within
$\operatorname{poly}(n)$ factors. This is stated more precisely in Algorithm
7.

Algorithm 7 Modified ByzLP

1:for interval $i=1,\ldots,K$ do

2: pick ${\gamma}_{i}\in{\color[rgb]{0,0,1}\Gamma_{\varepsilon}}$ using the
multiscale experts algorithm of Lemma A.2 on
$\overline{\operatorname{Alg}}_{1},\overline{\operatorname{Alg}}_{2},\ldots,\overline{\operatorname{Alg}}_{i-1}$.

3: run  Algorithm 6 over interval $I_{i}$ with parameter ${\gamma}_{i}$,
thereby getting value $\operatorname{Alg}_{i}({\gamma}_{i})$.

We finally prove that the above algorithm has the approximation guarantee
stated in Theorem 5.1.

###### Proof of Theorem 5.1.

Again the feasibility follows directly by the feasibility guarantee of
Algorithm 6.

Let $\gamma^{*}$ be a value in $\Gamma$ in the interval
$\big{[}(1-\varepsilon)\frac{\operatorname{OPT}}{B},\frac{\operatorname{OPT}}{B}\big{]}$.
By the truncation we get that
$\overline{\operatorname{Alg}}_{i}(\gamma^{*})\leq\frac{\operatorname{OPT}}{K}$.
Thus, the multiscale regret guarantee and the fact
$K\geq\Omega(\frac{\log|\Gamma_{\varepsilon}|}{\varepsilon^{2}})$ gives that
in every scenario the total value of the algorithm is at least

$\displaystyle\sum_{i}\overline{\operatorname{Alg}}_{i}({\gamma}_{i})~{}$
$\displaystyle\geq~{}(1-\varepsilon)\sum_{i}\overline{\operatorname{Alg}}_{i}(\gamma^{*})-\operatorname{OPT}\cdot
O\bigg{(}\frac{\log|\Gamma_{\varepsilon}|}{\varepsilon
K}\bigg{)}\geq(1-\varepsilon)\sum_{i}\overline{\operatorname{Alg}}_{i}(\gamma^{*})-O(\varepsilon\operatorname{OPT}).$
(17)

With probability at least $1-\delta^{\prime}$, the guarantee from Lemma 5.2
(with $\delta$ set as $\frac{\delta^{\prime}}{K}$) holds for all $K$
intervals. Whenever this holds we have

$\displaystyle\overline{\operatorname{Alg}}_{i}(\gamma^{*})~{}$
$\displaystyle\geq~{}|I_{i}|\min\bigg{\\{}(1-\varepsilon)\operatorname{OPT}\,,\,(1-\alpha)\operatorname{OPT}\bigg{\\}}~{}-~{}O\bigg{(}\frac{\varepsilon\operatorname{OPT}}{K}+\frac{\varepsilon\operatorname{OPT}n_{I_{i}}}{n}\bigg{)}$
$\displaystyle\geq~{}|I_{i}|(1-\alpha-O(\varepsilon))\operatorname{OPT}-O\bigg{(}\frac{\varepsilon\operatorname{OPT}n_{I_{i}}}{n}\bigg{)}$

for all $i\in[K]$. Adding over all $i$’s then gives
$\sum_{i}\overline{\operatorname{Alg}}_{i}(\gamma^{*})\geq(1-\alpha-O(\varepsilon))\operatorname{OPT}$.
Applying this on (17) then concludes the proof of the theorem. ∎

##  6 Byzantine Secretary for Value Maximization

In this section we consider two classical secretary problems in the Byzantine
framework: that of (i) picking a single item, and (ii) picking an independent
set in a matroid, to maximize the expected value of picked items. The main
results of this section are:

See 1.5

The first claim is proved in §6.1, and improves upon the previous factor of
$\Omega\big{(}\nicefrac{{1}}{{(\log^{*}n)^{2}}}\big{)}$ of [BGSZ20]. The
second claim is then proved in §6.2 and improves upon the previous factor of
$\Omega\big{(}\nicefrac{{1}}{{\log n}}\big{)}$ when the rank $r$ is
sufficiently smaller than the total number of items $n$, also from [BGSZ20].

Note that these packing problems are related to the results we saw in §2 and
§5 : both the current problems can also be modeled as PIPs, but we cannot
assume that the capacities (i.e., the right-hand sides of the PIP) are large,
so we cannot apply results we proved earlier. The single-item _probability
maximization_ result from §3 also gives an $\Omega(1/\log n)$-approximation
for the value-maximization setting, which is much weaker than the result here.

###  6.1 Single Item Value Maximization

For the value-maximization problem, we give three procedures, each of which
picks at most $K=O(\log^{*}n)$ items. By picking all items chosen by any of
the three procedures, we get an algorithm that picks $O(\log^{*}n)$ items and
gets expected value $\Omega(C^{*})$. Then picking one of these items uniformly
at random, we get a single item with expected value $\Omega(C^{*}/\log^{*}n)$.

The main idea of this algorithm is break the time horizon into $K$ intervals,
and to iteratively get a better estimate of the optimum value each time we
fail to get a large expected value. As in §3.1, we divide time into $K$
intervals, and let $\widehat{\mu}_{i}$ be the largest value of any item in
interval $I_{i}$. For the sake of intuition, assume that
$nC^{*}\geq\widehat{\mu}_{0}\geq\widehat{\mu}_{1}\geq\dots\geq\widehat{\mu}_{K}\geq
C^{*}$. Suppose we know that $\widehat{\mu}_{i}$ is an $\alpha$-approximation
to $C^{*}$. Pick $k$ randomly from $[\log\alpha]$ and set the threshold
$2^{-k}\widehat{\mu}_{i}$ for interval $I_{i+1}$. Since we know that
$\widehat{\mu}_{i+1}$ is contained in the interval
$[2^{-k}\widehat{\mu}_{i},2^{-(k-1)}\widehat{\mu}_{i}]$ for some $k\in[\log
n]$, choosing this value of $k$ yields value $\approx\widehat{\mu}_{i+1}$ with
probability at least $\frac{1}{\log\alpha}$. If $\widehat{\mu}_{i+1}\geq
C^{*}\log\alpha$, then we get expected value $C^{*}$. Otherwise, we know that
$\widehat{\mu}_{i+1}$ is a $\log\alpha$-approximation to $C^{*}$. Since
$\widehat{\mu}_{0}$ is an $n$-approximation to $C^{*}$, we find inductively
that each $\widehat{\mu}_{i}$ is a $\log^{(i)}n$-approximation to $C^{*}$.
This implies that we need consider only $K=O(\log^{*}n)$ many intervals. This
gives the main idea: the actual procedure needs to consider situations where
the interval maxima are not monotonically decreasing, so we need more care.

Formally, the structural procedures are Struct—defined in Algorithm 3 of
§3—and a second procedure which simply picks one random item.

Algorithm 8 Procedure Sample

1:Choose one item uniformly at random

To explain the third and main search procedure, let us recall useful notation
from §3: let $\rho_{i}$ be the maximum value of any red item in interval
$I_{i}$; define $\rho_{i}\leftarrow-\infty$ if no such items exist. An
interval $I_{i}$ (including $I_{0}$) is _high_ if $\rho_{i}\geq C^{*}$, and
_low_ otherwise. An interval $I_{i}$ (for $i\geq 1$) is _nice_ if the
intervals $I_{i}$ and $I_{i-1}$ are both high, and moreover the item
$g_{\max}$ does not arrive in interval $I_{i-1}$.

Now in interval $I_{i}$, the new search procedure determines the location of
the previous high intervals, assuming that $I_{i-1}$ is high. The threshold
for interval $I_{i}$ is chosen from among $\log^{(\ell+1)}n$ exponentially-
spaced values centered around the $\widehat{\mu}$ value of the previous nice
interval, where $\ell$ is roughly the number of previous nice intervals.

Algorithm 9 Procedure SearchII

1:for interval $i=1,2,\ldots,K$ do

2:
$\widehat{\mathcal{N}}_{i}\leftarrow\\{j\in[i-1]:\widehat{\mu}_{j}\geq\widehat{\mu}_{i-1}\text{
and }\widehat{\mu}_{j-1}\geq\widehat{\mu}_{i-1}\\}$

3: $\widehat{\ell}_{i}\leftarrow|\widehat{\mathcal{N}}_{i}|+1$

4: if $\widehat{\ell}_{i}>1$ then

5: $\hat{\jmath}_{i}\leftarrow\max(\widehat{\mathcal{N}}_{i})$

6: else

7: $\hat{\jmath}_{i}\leftarrow i-1$

8: $\widehat{k}_{i}\leftarrow$ uniformly random integer in
$[-\log^{(\widehat{\ell}_{i})}n,\log^{(\widehat{\ell}_{i})}n]$

9: In interval $I_{i}$, pick the first item (if any) with value at least
$\tau_{i}:=2^{\widehat{k}_{i}}\cdot\widehat{\mu}_{\hat{\jmath}_{i}}$.

Intuitively, $\widehat{\mathcal{N}}_{i}$ is the index set of nice intervals
among $I_{1},\dots,I_{i-1}$, the number $\widehat{\ell}_{i}$ is one more than
the number of previous nice intervals, and $\hat{\jmath}_{i}$ is the index of
the most recent nice interval. Indeed, these statements are all true when
$I_{i-1}$ is high (Lemma 6.2).

#### The Analysis.

It is clear that each procedure picks at most $K=O(\log^{*}n)$ items.

######  Lemma 6.1.

Struct has expected value $\Omega(C^{*})$ unless the following properties both
hold:

  * (i)

If $I_{i}$ and $I_{j}$ are high intervals with $i<j$, then
$\rho_{i}>\rho_{j}$.

  * (ii)

There are at most $\frac{K}{4}$ low intervals.

Sample has expected value $C^{*}$ unless the following property holds:

  * (iii)

The maximum value of any item is less than $nC^{*}$.

###### Proof.

By Lemma 3.1, if either of $(i)$ or $(ii)$ fails then Struct picks an item of
value at least $C^{*}$ with probability $\Omega(1)$, and hence has expected
value $\Omega(C^{*})$. The second claim is immediate. ∎

Let $j_{1},\dots,j_{m}$ denote the indices of the nice intervals. Let
$N_{\ell}:=I_{j_{\ell}}$ denote the $\ell$-th nice interval and let
$\widehat{\mu}(\widehat{\mathcal{N}}_{\ell}):=\widehat{\mu}_{j_{\ell}}$ denote
its most valuable item. Let $\mathcal{N}_{i}=\\{j_{\ell}\mid j_{\ell}<i\\}$
denote the set of indices of nice intervals before interval $I_{i}$.

######  Lemma 6.2.

Suppose that item $g_{\max}$ arrives in $(\frac{3}{4},1]$ and property (i) of
Lemma 6.1 holds. If interval $I_{i-1}$ is high, then
$\widehat{\mathcal{N}}_{i}=\mathcal{N}_{i}$. In particular, if $I_{i}$ is
nice, then $I_{i}=N_{\widehat{\ell}_{i}}$, and
$I_{\hat{\jmath}_{i}}=N_{\widehat{\ell}_{i}-1}$.

###### Proof.

Since $g_{\max}$ arrives in $(\frac{3}{4},1]$, for each $j$ it holds that
$\rho_{j}=\widehat{\mu}_{j}$. Since $I_{i-1}$ is high, property (i) implies
that $\widehat{\mu}_{i-1}$ is minimal among the $\widehat{\mu}$ values of high
intervals seen so far. Thus, for $j\leq i-1$, interval $I_{j}$ is nice if and
only if $\widehat{\mu}_{j}\geq\widehat{\mu}_{i-1}$. It follows from definition
that $\widehat{\mathcal{N}}_{i}=\mathcal{N}_{i}$. ∎

It is convenient to let $N_{0}$ denote the (high) interval immediately
preceding $N_{1}$, so that for all $\ell=1,\dots,|\mathcal{N}_{i}|$, in
interval $I_{j_{\ell}}=N_{\ell}$, SearchII’s choice of
$\hat{\jmath}_{j_{\ell}}$ satisfies $I_{\hat{\jmath}_{j_{\ell}}}=N_{\ell-1}$.

######  Lemma 6.3.

Let $K=2\log^{*}n+2$. Suppose that (i)-(iii) of Lemma 6.1 all hold. Then
SearchII has expected value $\Omega(C^{*})$.

###### Proof.

By property $(ii)$, the number of nice intervals is at least

$K-\tfrac{K}{4}-\tfrac{K}{4}-1~{}=~{}\tfrac{K}{2}-1~{}\geq~{}\log^{*}n.$

Let $\ell$ be the minimal number $l\geq 1$ satisfying
$\widehat{\mu}(N_{l})\geq C^{*}\log^{(l)}n$. (This is well defined—the
inequality is always satisfied by $l=\log^{*}n$.) We claim that

$C^{*}~{}\leq~{}\widehat{\mu}(N_{\ell-1})~{}<~{}C^{*}\log^{(\ell-1)}n.$

The first inequality follows from the fact that $N_{\ell}$ is nice (in
particular, it is high). When $\ell=1$, the second inequality holds by
property $(iii)$; when $\ell>1$, it holds by the minimality of $\ell$.
Therefore, there is some $k\in[-\log^{(\ell)}n,\log^{(\ell)}n]$ such that

$2^{k}\widehat{\mu}(N_{\ell})~{}\leq~{}C^{*}\log^{(\ell)}n~{}<~{}2^{k+1}\widehat{\mu}(N_{\ell}).$

For ease of notation, let $t=j_{\ell}$ so that $I_{t}=N_{\ell}$. Condition on
$g_{\max}$ arriving in $(\frac{3}{4},1]$—which happens with probability
$\frac{1}{4}$—and consider the choice of SearchII in interval $N_{\ell}$.
Since property $(i)$ also holds, Lemma 6.2 applies. In particular,
$\widehat{\ell}_{t}=\ell$ and
$\widehat{\mu}_{\hat{\jmath}_{t}}=\widehat{\mu}_{j_{\ell-1}}=\widehat{\mu}(N_{\ell-1})$.
Therefore $\widehat{k}_{t}$ is drawn from $[-\log^{(\ell)}n,\log^{(\ell)}n]$,
and the threshold
$\tau_{t}=2^{\widehat{k}_{t}}\cdot\widehat{\mu}(N_{\ell-1})$. With probability
$\Omega\Big{(}\frac{1}{\log^{(\ell)}n}\Big{)}$, the algorithm chooses
$\widehat{k}_{t}=k$. In this case, since
$\widehat{\mu}_{t}=\widehat{\mu}(N_{\ell})\geq
C^{*}\log^{(\ell)}n\geq\tau_{t}$, SearchII will pick an item in $I_{t}$. Thus
SearchII gets expected value at least

$\tfrac{1}{4}\cdot\Omega(1)\cdot\tfrac{1}{\log^{(\ell)}n}\cdot
C^{*}\log^{(\ell)}n~{}=~{}\Omega(C^{*}).\qed$

###### Proof of Theorem 1.5(i).

We now run one of the three algorithms Struct, Sample, and SearchII uniformly
at random. By Lemmas 6.1 and 6.3 the picked algorithm gives expected value at
least $C^{*}$ with probability $\nicefrac{{1}}{{3}}$, while picking at most
$K=O(\log^{*}n)$ items. Actually selecting a random one of these $K$ items
proves the claim. ∎

###  6.2 Byzantine Secretary for Matroids

We consider the setting where the items are the ground set of an arbitrary
matroid and the algorithm can choose any independent set of items. The
algorithm is given the rank $r$ of the matroid and the number $n$ of items,
but only learns the matroid structure as the items arrive. The main result of
this section is Theorem 1.5(ii). The factor of $O((\log^{*}n)^{2}\cdot\log r)$
improves upon the previous factor of $O(\log n)$ if the rank of the matroid
$r$ is much smaller than the number of items $n$. For the rest of the section,
we assume the benchmark $C^{*}:=\operatorname{OPT}(\mathcal{G}\setminus
g_{\max})$ satisfies $C^{*}\geq 2\mathsf{val}(g_{2})$. This is without loss of
generality: indeed, we can run the algorithm from §6.1 with probability
$\frac{1}{2}$ (which suffices when $C^{*}\leq 2\mathsf{val}(g_{2})$) and run
the algorithm below with the remaining probability.

#### The Algorithm.

The idea of our algorithm is to use the approach from §6.1 that, at each step,
it either gets items of high value, or gets a better estimate of the highest-
value items. Define intervals $I_{0}$ and $I_{i}$, and values $\rho_{i}$ and
$\widehat{\mu}_{i}$ for each interval as in §3. Again the algorithm will pick
one of the following 3 procedures uniformly at random and use it for the whole
instance.

#### Procedure 1.

Run the single-item value-maximization algorithm from §6.1.

#### Procedure 2.

The second procedure is adapted from the $O(\log n)$-competitive algorithm of
[BGSZ20]. The intuition is as follows: most of the value in
$\operatorname{OPT}$ comes from items with value in
$[\mathsf{val}(g_{2})/2r,\mathsf{val}(g_{2})]$. If this value interval is
partitioned into exponentially-separated value-levels, an average level
contains a $\frac{1}{\log r}$ fraction of the value of $\operatorname{OPT}$.
The procedure estimates $\mathsf{val}(g_{2})$ by the max-value item in a
random interval, uses this estimate to choose a random-value interval, and
sets a threshold to get the value of this interval. More precisely, the
procedure is the following:

Algorithm 10 Procedure I-bgsz

1:$i\leftarrow$ uniformly random integer in $[K]$

2:$k\leftarrow$ uniformly random integer in $[\log(2r^{2})]$

3:$\widehat{\mu}_{i}=$ max value of an item arriving in $I_{i}$

4:After $I_{i}$, greedily chose items with value at least
$2^{-k}\widehat{\mu}_{i}$.

#### Procedure 3.

The third procedure attempts to capture the value of large red items. It is
simpler than SearchII from §6.1, but similar in spirit:

Algorithm 11 Procedure SearchIII

1:$i\leftarrow$ uniformly random integer in $[K]$

2:$k\leftarrow$ uniformly random integer in $[-\log^{(i)}(n),\log^{(i)}(n)]$

3:$\widehat{\mu}_{i-1}=$ max value of an item arriving in $I_{i-1}$

4:Pick the first item arriving in (or after) $I_{i}$ with value at least
$2^{k}\widehat{\mu}_{i-1}$. If no such item arrives, pick nothing.

#### The Analysis.

Similarly to §3, we analyze the algorithm by breaking into different cases
based on the following structural properties of the instance.

  * (i)

No item has value more than $n\cdot r\cdot\mathsf{val}(g_{2})$.

  * (ii)

$C^{*}\geq 4\mathsf{val}(g_{2})$.

  * (iii)

For every $i$, it holds that $\rho_{i}\geq r\cdot\mathsf{val}(g_{2})$.

Recall that $\rho_{i}$ denotes the maximum value of a red item arriving in
interval $I_{i}$.

######  Lemma 6.4.

If either of properties (i) or (ii) fail, then the algorithm of §6.1 gets
expected value $\Omega(\frac{C^{*}}{\log^{*}n})$.

###### Proof.

Suppose property (i) fails. With probability $\Omega(\frac{1}{\log^{*}n})$,
the algorithm of §6.1 picks a uniformly random item. This item has expected
value at least $r\cdot\mathsf{val}(g_{2})\geq C^{*}$, so the algorithm of §6.1
has expected value $\Omega(\frac{C^{*}}{\log^{*}n})$.

Now suppose property (ii) fails. Then as proved in §6.1, the algorithm of §6.1
has expected value
$\Omega(\frac{\mathsf{val}(g_{2})}{\log^{*}n})\geq\Omega(\frac{C^{*}}{\log^{*}n})$.
∎

######  Lemma 6.5.

If properties (i) and (ii) hold and property (iii) fails, then I-bgsz has
expected value at least $\Omega(\frac{C^{*}}{K^{2}\log r})$.

###### Proof.

Fix $i$ such that $\rho_{i}\leq r\cdot\mathsf{val}(g_{2})$. Condition on the
event that (a) I-bgsz chooses this $i$ in line 1 and (b) $g_{2}$ arrives in
$I_{i}$ but $g_{\max}$ does not, which happens with probability
$\frac{1}{K}\cdot\frac{1}{2K}(1-\frac{1}{2K})\geq\frac{1}{3K^{2}}$. Now
$\widehat{\mu}_{i}=\max\\{\rho_{i},\mathsf{val}(g_{2}2)\\}$, which implies
that

$\mathsf{val}(g_{2})~{}\leq~{}\widehat{\mu}_{i}~{}\leq~{}r\cdot\mathsf{val}(g_{2}).$
(18)

Let $OPT$ denote the items in the optimal solution of green items excluding
$g_{\max}$.

Let $L^{*}=\big{\\{}x\in
OPT\mid\mathsf{val}(x)>\frac{\mathsf{val}(g_{2})}{2r}\big{\\}}$. Since
$|OPT|\leq r$, the items in $OPT\setminus L^{*}$ have total value at most
$\frac{\mathsf{val}(g_{2})}{2}\leq\frac{C^{*}}{2}$. Thus
$\mathsf{val}(L^{*})\geq\frac{C^{*}}{2}$. Given the conditioning, all items in
$L^{*}\setminus\\{g_{2}\\}$ arrive at independent uniformly random times. In
particular, since $I_{i}\subseteq[\frac{1}{4},\frac{3}{4}]$, the expected
value of items in $L^{*}$ that arrive after $I_{i}$ is at least
$\frac{1}{4}(\frac{C^{*}}{2}-\mathsf{val}(g_{2}))\geq\frac{C^{*}}{16}$ (using
property (ii)). The value of each of these items is in
$[\frac{\mathsf{val}(g_{2})}{2r},\mathsf{val}(g_{2})]$. By (18), each of these
items has value in some value-level
$[2^{-k}\widehat{\mu}_{i},2^{-k+1}\widehat{\mu}_{i})$ with
$k\in[\log(2r^{2})]$. An average level therefore contains at least
$\Omega(\frac{C^{*}}{\log r})$ value from $OPT$. The greedy algorithm on one
such value-level gets at least half of $OPT$’s value in that level, so I-bgsz
gets expected value $\Omega(\frac{C^{*}}{\log r})$ as well. Since this holds
when we condition on an event of probability $\Omega(\frac{1}{K^{2}})$, the
result follows. ∎

######  Lemma 6.6.

Let $K=\log^{*}(n)$. If properties (ii) and (iii) hold, then procedure
SearchIII gets expected value $\Omega(\frac{C^{*}}{\log^{*}n})$

###### Proof.

Fix the minimal index $i\geq 0$ for which $\mu_{i}\geq
r\cdot\log^{(i)}n\cdot\mathsf{val}(g_{2})$. Since property (iii) holds, the
index $i=\log^{*}(n)$ satisfies the desired constraint, hence $i$ is well-
defined. Furthermore, since property $(i)$ holds, $i\geq 1$. Then we have the
following inequalities:

$r\cdot\mathsf{val}(g_{2})~{}\leq~{}\mu_{i-1}~{}\leq~{}\log^{(i-1)}(n)\cdot
r\cdot\mathsf{val}(g_{2}),$

the first by property (ii) and the second by minimality of $i$. It follows
that there is a $k\in[\pm\log^{(i)}(n)]$ such that the value level defined by
$2^{k}\mu_{i-1}$ contains an item of value at least
$r\cdot\log^{(i)}n\cdot\mathsf{val}(g_{2})$. With probability $\frac{1}{K\cdot
2\log^{(i)}(n)}$, Procedure 3 picks interval $i$ and level $k$. In this case,
it gets value at least

$r\cdot\log^{(i)}n\cdot\mathsf{val}(g_{2})~{}\geq~{}\log^{(i)}n\cdot C^{*}.$

Thus, SearchIII gets expected value
$\Omega(\frac{C^{*}}{K})=\Omega(\frac{C^{*}}{\log^{*}n})$. ∎

We now complete the proof of Theorem 1.5(ii).

###### Proof of Theorem 1.5(ii).

Consider the algorithm that uses $K=\log^{*}n$ and runs one of the above three
procedures, each with probability $\frac{1}{3}$. By Lemmas 6.4, 6.5 and 6.6,
at least one of these procedures has expected value
$\Omega\big{(}\frac{C^{*}}{(\log^{*}n)^{2}\cdot\log r}\big{)}$. With
probability $\frac{1}{3}$, the algorithm picks the right procedure. Hence, the
same value guarantee applies up to a constant. ∎

Appendix

##  Appendix A Useful Prior Results

Let
$\triangle^{d-1}:=\big{\\{}\mathbf{p}\in[0,1]^{d}\mid\|\mathbf{p}\|_{1}=1\big{\\}}$
be the _probability simplex_ in $\mathbb{R}^{d}$, and
$\blacktriangle^{d}:=\big{\\{}\mathbf{p}\in[0,1]^{d}\mid\|\mathbf{p}\|_{1}\leq
1\big{\\}}$ be the _full-dimensional_ probability simplex. We recall the full-
information online linear optimization (OLO) low regret bound; see, e.g.,
[AHK12].

######  Lemma A.1 (OLO).

Fix $\varepsilon\in(0,\nicefrac{{1}}{{2}}]$. The experts algorithm considers a
setting with $d$ experts. At each time the algorithm plays a probability
distribution $p^{t}\in\triangle^{d-1}$ and receives a linear reward function
$f_{t}:\triangle^{d-1}\rightarrow[-1,1]$. For any time $\tau$, let
$p^{*}=\operatorname{argmax}_{p\in\triangle^{d-1}}\sum_{t\leq\tau}f_{t}(p)$ be
fixed action that gives the best reward over the entire input sequence. Until
any time $\tau$, the following holds:

$\displaystyle\sum_{t\leq\tau}f_{t}(p^{*})-\sum_{t\leq\tau}f_{t}({p^{t}})\leq\varepsilon\sum_{t\leq\tau}|f_{t}(p^{*})|+\frac{\log
d}{\varepsilon}\enspace.$ (19)

We will also need the following generalization from Bubeck et al. [BDHN19,
Theorem 1] for the full-information multiscale online learning problem.

######  Lemma A.2 (Multi-scale regret of Bubeck et al. [BDHN19]).

Fix $\varepsilon\in(0,1]$. The multi-scale experts algorithm considers a
setting with $M$ experts. At each time the algorithm plays a probability
distribution $p^{t}\in\triangle_{M}$ and receives a reward vector $r^{t}$ with
each $r^{t}_{i}\in[0,c_{i}]$; moreover, $c_{i}$ is known in advance. Let
$R_{i}:=\max_{i}\sum_{t}r^{t}_{i}$ be the reward of action $i$ over the entire
input sequence. The following holds for each $i\in[M]$:

$\displaystyle R_{i}-\sum_{t}\langle r^{t},p^{t}\rangle\leq\varepsilon
R_{i}+O\Big{(}\frac{c_{i}\,\log M}{\varepsilon}\Big{)}\enspace.$ (20)

If we pick a random action in $[M]$ at each timestep $t$ independently from
the distribution $p^{t}$, then the above theorem gives a guarantee for the
expected regret against oblivious adversaries as well.

The following concentration inequality is classical: see, e.g., [Ver18,
Theorem 2.8.4]:

######  Lemma A.3 (Bernstein’s Inequality).

For $X_{1},X_{2},\ldots,X_{n}$ independent mean-zero random variables such
that $|X_{i}|\leq M$ for all $i$, and any $t\geq 0$,

$\Pr\Big{[}\Big{|}\sum_{i}X_{i}\Big{|}>t\Big{]}\leq
2\exp\Big{(}\frac{t^{2}/2}{\sigma^{2}+Mt/3}\Big{)},$

where $\sigma^{2}=\sum_{i}\mathbb{E}[X_{i}^{2}]$ is the variance of the sum.

Our algorithm for Packing Integer Programs will use the following result about
Byzantine Knapsacks (and hence about the multiple-item Byzantine secretary)
from [BGSZ20, Theorem 2 and Lemma 7] in case most of the value is concentrated
on a small number of items.

######  Lemma A.4.

There is an algorithm for Byzantine secretary on knapsacks with size at least
$B\geq poly(\varepsilon^{-1}\log n)$ (and items of at most unit size) that is
$(1-\varepsilon)$-competitive with the benchmark
$\operatorname{OPT}(\mathcal{G}\setminus g_{\max})$. Moreover, there is an
algorithm that given an estimate that is at least
$\operatorname{OPT}(\mathcal{G})$ and at most $\operatorname{poly}(n)$ times
as much, and knapsack size $B\geq poly(\varepsilon^{-1}\log n)$, prodices a
solution that is $(1-\varepsilon)$-competitive with the benchmark
$\operatorname{OPT}(\mathcal{G})$.

##  Appendix B Handling Correlations due to Sampling Without Replacement

In contrast to i.i.d. arrivals, to handle correlations due to sampling without
replacement for secretary problems, we will use the following general lemma.

######  Lemma B.1.

Consider a set of vectors $\\{y^{1},\ldots,y^{m}\\}\in[0,1]^{d}$ and let
$Y^{1},\ldots,Y^{k}$ be sampled without replacement from this set. Let
$Z^{1},\ldots,Z^{k}$ be random vectors in $\blacktriangle^{d}$ such that
$Z^{j}$ is a (possibly random) function of $Y^{1},\ldots,Y^{j-1}$ for all $j$.
Let $\tau$ be a stopping time for the sequence $((Y^{t},Z^{t}))_{t}$ such that
$\tau\leq\frac{m}{2}$. Then for any $\varepsilon\in(0,\frac{1}{10}]$ and
$\delta\in(0,1]$, with probability at least $1-\delta$ we have

$\sum_{j\leq\tau}\langle
Z^{j},Y^{j}\rangle~{}\leq~{}(1+4\varepsilon)\,\sum_{j\leq\tau}\langle\mathbb{E}_{j-1}Z^{j},\mathbb{E}Y^{j}\rangle\,+\,\frac{O(\log\nicefrac{{d}}{{\delta}})}{\varepsilon}\enspace,$

where
$\mathbb{E}_{j-1}Z^{j}=\mathbb{E}[Z^{j}\mid(Y_{1},Z_{1}),\ldots,(Y_{j-1},Z_{j-1})]$.

Special cases of the above lemma have appeared before in the literature, e.g.
of [GM16, Lemma 5]. We will need the following convenient concentration
inequality for “martingales with drift”.

######  Lemma B.2 (Lemma 2.2 of [Ban19]).

Let $X_{1},X_{2},\ldots,X_{k}$ be a sequence of (possibly dependent) random
variables with values in $(-\infty,1]$ and such that there is $\alpha\in(0,1)$
such that

$\mathbb{E}[X_{j}\mid X_{1},\ldots,X_{j-1}]\leq-\alpha\mathbb{E}[X^{2}_{j}\mid
X_{1},\ldots,X_{j-1}]$

for all $j$. Then for all $\lambda\geq 0$

$\displaystyle\Pr(X_{1}+\ldots+X_{k}>t)\leq e^{-\alpha\lambda}.$

We also need a maximal Bernstein’s inequality for sampling without
replacement.It follows by applying Lemma 1 of [GM16] to the scaled random
variables $\frac{X_{i}}{M}\in[0,1]$ and using the fact that
$\text{Var}(X)\leq\mathbb{E}X$ for every random variable in $[0,1]$ (the last
inequality follows from the inequality
$\frac{a}{b+c}\geq\min\\{\frac{a}{2b},\frac{a}{2c}\\}$, valid for all non-
negative reals $a,b,c$).

######  Lemma B.3 (Lemma 1 of [GM16]).

Consider a set of real values $x_{1},\ldots,x_{m}$ in $[0,M]$, and let
$X_{1},\ldots,X_{k}$ be sampled without replacement from this collection.
Assume $k\leq m/2$. Let $S_{i}=X_{1}+\ldots X_{i}$. Also let
$\mu=\frac{1}{m}\sum_{i}x_{i}$ and
$\sigma^{2}=\frac{1}{m}\sum_{i}(x_{i}-\mu)^{2}$. Then for every $\alpha>0$

$\displaystyle\Pr\left(\max_{i\leq k}|S_{i}-i\mu|\geq\alpha\right)\leq
30\exp\left(-\frac{(\alpha/24)^{2}}{M(2k\mu+(\alpha/24))}\right)\leq
30\exp\left(-\min\bigg{\\{}\frac{(\alpha/24)^{2}}{4k\mu
M}~{},~{}\frac{\alpha}{48M}\bigg{\\}}\right)$

Let $\mathcal{F}_{j}$ be the $\sigma$-algebra generated by
$Y^{1},\ldots,Y^{j}$ and $Z^{1},\ldots,Z^{j}$, i.e., the history up to time
$j$. We use $\mathbb{E}_{j-1}[\cdot]:=\mathbb{E}[\
\cdot\mid\mathcal{F}_{j-1}]$ to denote expectation conditioned on the history
up to time $j-1$.

######  Lemma B.4.

Consider $i\in[d]$. Then with probability at least $1-\frac{\delta}{d}$ we
have
$\mathbb{E}_{j-1}Y^{j}_{i}\leq(1+2\varepsilon)\mathbb{E}Y^{j}_{i}+\frac{O(\log
d/\delta)}{m\varepsilon}$ for all $j\leq\frac{m}{2}$ simultaneously.

###### Proof.

Let $\mu=\frac{1}{m}\sum_{j\leq m}y^{j}_{i}$, which is the expected value of
$Y^{j}_{i}$. Moreover, the conditional expectation $\mathbb{E}_{j-1}Y^{j}_{i}$
is the average of the $y^{t}_{i}$’s that have not appeared up until time
$j-1$, namely

$\displaystyle\mathbb{E}_{j-1}Y^{j}_{i}=\frac{\sum_{t}y^{t}_{i}-\sum_{t\leq
j-1}Y^{t}_{i}}{m-(j-1)}=\frac{m\mu-\sum_{t\leq j-1}Y^{t}_{i}}{m-(j-1)}.$ (21)

We then bound the last term uniformly for all $j\leq\frac{m}{2}$ using the
maximal Bernstein’s inequality Lemma B.3.

For that let $\sigma^{2}:=\frac{1}{m}\sum_{t}(y^{t}_{i}-\mu)^{2}$ and notice
that

$\displaystyle\sigma^{2}\,=\,\frac{1}{m}\sum_{t}(y^{t}_{i})^{2}-\mu^{2}\,\leq\,\frac{1}{m}\sum_{t}y^{t}_{i}\,=\,\mu,$

where the inequality uses $y^{t}_{i}\in[0,1]$. Applying Lemma B.3 with

$\alpha:=\varepsilon
m\mu+\frac{2\cdot(24)^{2}}{\varepsilon}\,(\log\nicefrac{{d}}{{\delta}}+\log
30)$

we get, since $\alpha^{2}\geq
4m\mu\,(24)^{2}\,(\log\nicefrac{{d}}{{\delta}}+\log 30)$,

$\displaystyle\Pr\left(\max_{j\leq m/2}|{\textstyle\sum_{t\leq
j}}Y^{j}_{i}-j\mu|\geq\alpha\right)$ $\displaystyle\leq
30\exp\left(-\min\bigg{\\{}\frac{4m\mu(\log\nicefrac{{d}}{{\delta}}+\log
30)}{2m\mu}~{},~{}\frac{2(24)^{2}(\log\nicefrac{{d}}{{\delta}}+\log
30)/\varepsilon}{48}\bigg{\\}}\right)$ $\displaystyle\leq 30e^{-(\log
d/\delta+\log 30)}~{}\leq~{}\frac{\delta}{d}.$

Finally, whenever this event holds, equation (21) gives that for all $j\leq
m/2$

$\mathbb{E}_{j-1}Y^{j}_{i}\leq\frac{(m-(j-1))\,\mu+\alpha}{m-(j-1)}\leq\mu+\frac{\varepsilon
m\mu+O(\frac{\log\nicefrac{{d}}{{\delta}}}{\varepsilon})}{m-(j-1)}\leq(1+2\varepsilon)\mu+\frac{O(\log
d/\delta)}{m\varepsilon},$

the last inequality using $j\leq\frac{m}{2}$. This concludes the proof. ∎

###### Proof of Lemma B.1.

Since $Z^{t}$ and $Y^{j}$ are independent conditioned on $\mathcal{F}_{j-1}$,
we have

$\displaystyle\mathbb{E}_{j-1}\langle
Z^{j},Y^{j}\rangle\,=\,\langle\mathbb{E}_{j-1}Z^{j},\mathbb{E}_{j-1}Y^{j}\rangle$

Moreover, applying a union bound on Lemma B.4 over all coordinates $i$, with
probability at least $1-\frac{\delta}{2}$ for all $j\leq\frac{m}{2}$ (in
particular for all $j\leq\tau$) we have
$\langle\mathbb{E}_{j-1}Z^{j},\mathbb{E}_{j-1}Y^{j}\rangle\leq(1+2\varepsilon)\langle\mathbb{E}_{j-1}Z^{j},\mathbb{E}Y^{j}\rangle+\frac{O(\log
d/\delta)}{m\varepsilon}$. Adding over all $j\leq\tau$ we get that

$\displaystyle\sum_{j\leq\tau}\mathbb{E}_{j}\langle Z^{j},Y^{j}\rangle$
$\displaystyle\leq(1+2\varepsilon)\sum_{j\leq\tau}\langle\mathbb{E}_{j-1}Z^{j},\mathbb{E}Y^{j}\rangle+\frac{O(\log
d/\delta)}{\varepsilon}$ $\displaystyle\textrm{with probability $\geq
1-\frac{\delta}{2}$}\,.$ (22)

We now show using Lemma B.2 that with good probability the desired quantity
$\sum_{j\leq\tau}\langle Z^{j},Y^{j}\rangle$ is close to
$\sum_{j\leq\tau}\mathbb{E}_{j}\langle Z^{j},Y^{j}\rangle$. Define the stopped
random variable

$\displaystyle X_{j}:=\mathbf{1}(\tau\geq j)\cdot\Big{[}(1-\varepsilon)\langle
Z^{j},Y^{j}\rangle-\mathbb{E}_{j}\langle Z^{j},Y^{j}\rangle\Big{]}.$

Recall that by definition of stopping time, the event $\mathbf{1}(\tau\geq j)$
is $\mathcal{F}_{j-1}$-measurable, and hence
$\mathbb{E}_{j}X_{j}=\mathbf{1}(\tau\geq
j)\cdot(-\varepsilon\,\mathbb{E}_{j}\langle Z^{j},Y^{j}\rangle)$. Moreover,

$\displaystyle\mathbb{E}_{j}X^{2}_{j}~{}$
$\displaystyle=~{}\mathbf{1}(\tau\geq
j)\cdot\Big{[}(1-\varepsilon)^{2}\,\mathbb{E}_{j}\underbrace{\langle
Z^{j},Y^{j}\rangle^{2}}_{\leq\langle
Z^{j},Y^{j}\rangle}\,-\,\underbrace{(2(1-\varepsilon)-1)}_{\geq
0}(\mathbb{E}_{j}\langle Z^{j},Y^{j}\rangle)^{2}\Big{]}$
$\displaystyle\leq~{}\mathbf{1}(\tau\geq j)\cdot\mathbb{E}_{j}\langle
Z^{j},Y^{j}\rangle,$

where the first underbrace is because $\langle Z^{j},Y^{j}\rangle\leq 1$ and
the second because $\varepsilon\in(0,\frac{1}{2}]$. Together, these
observations give

$\mathbb{E}_{j}X_{j}\leq-\varepsilon\,\mathbb{E}_{j}X_{j}^{2}.$

Then applying Lemma B.2 to the sequence $(X_{j})_{j}$ with
$\lambda=\frac{\log\nicefrac{{1}}{{2\delta}}}{\varepsilon}$ we obtain

$\displaystyle\Pr\bigg{(}(1-\varepsilon)\sum_{j\leq\tau}\langle
Z^{j},Y^{j}\rangle~{}>~{}\sum_{j\leq\tau}\mathbb{E}_{j}\langle
Z^{j},Y^{j}\rangle+\frac{\log\nicefrac{{1}}{{2\delta}}}{\varepsilon}\bigg{)}$
$\displaystyle~{}\leq~{}\frac{\delta}{2}.$

Then by union bound with (22), with probability at least $1-\delta$ we have

$\displaystyle\sum_{j\leq\tau}\langle
Z^{j},Y^{j}\rangle~{}\leq~{}\frac{(1+2\varepsilon)}{(1-\varepsilon)}\,\sum_{j\leq\tau}\langle\mathbb{E}_{j-1}Z^{j},\mathbb{E}Y^{j}\rangle+\frac{O(\log\nicefrac{{d}}{{\delta}})}{\varepsilon}.$

Verifying that $\frac{(1+2\varepsilon)}{(1-\varepsilon)}\leq 1+4\varepsilon$
for all $\varepsilon\in(0,\frac{1}{10}]$ then proves Lemma B.1.

∎

##  Appendix C Missing Proofs from Section 2

See 2.2

###### Proof.

The desired $O(\rho)$-approximation for general instances is given by choosing
uniformly at random and running one of the following 3 algorithms:

  1. 1.

Pick one of the $n$ items uniformly at random

  2. 2.

Run the algorithm given by Lemma A.4 aiming at picking the best $B$ items

  3. 3.

See the largest value $c^{1/2}_{\max}$ of an item with arrival time in
$[0,\frac{1}{2})$ (do not pick any) and on the remaining times
$[\frac{1}{2},1]$ run an algorithm that is $\rho$-competitive in a smooth
instance with constant probability using $c^{1/2}$ as estimate for
$\operatorname{OPT}(\mathcal{G})$ (still using budget $B$).

By construction this procedure always produces a feasible solution, and we
show it has good value in expectation.

Let $c_{\max}$ be the maximum value of over all (green and red) items. First,
if $c_{\max}\geq\frac{n}{2}\operatorname{OPT}(\mathcal{G}\setminus g_{\max})$
then the procedure has expected value at least
$\frac{1}{3}\operatorname{OPT}(\mathcal{G})$ just from the first algorithm
that it may run, and the result follows. Also, if the $B$ top valued green
items (excluding $g_{\max}$) have combined value at least
$\frac{\operatorname{OPT}(\mathcal{G}\setminus g_{\max})}{4}$, then the
procedure gets expected value at least
$\Omega(\operatorname{OPT}(\mathcal{G}\setminus g_{\max}))$ just from the
second algorithm that it may run, and the result also follows.

So consider the “remaining situation” where neither of these cases happen.
Further, condition on the event where $g_{\max}$ shows up at a time
$[0,\frac{1}{2})$ and $\operatorname{OPT}(\mathcal{G}\cap[\frac{1}{2},1])$
(the optimal value considering only green items on times $[\frac{1}{2},1]$) it
at least $\frac{1}{2}\operatorname{OPT}(\mathcal{G}\setminus g_{\max})$, which
happens with probability at least $\frac{1}{4}$. In this case the instance
over times $[\frac{1}{2},1]$ satisfies both items of the smoothness Assumption
2.1 with $\widehat{O}:=c^{1/2}_{\max}$ because:

  1. 1.

Item 1: The $B$ top valued green items in $[\frac{1}{2},1]$ have combined
value at most $\frac{\operatorname{OPT}(\mathcal{G}\setminus
g_{\max})}{4}\leq\frac{\operatorname{OPT}(\mathcal{G}\cap[\frac{1}{2},1])}{2}$.
Since this set of items contains all items in $[\frac{1}{2},1]$ of value at
least $\frac{\operatorname{OPT}(\mathcal{G}\cap[\frac{1}{2},1])}{B}$, it
satisfies Item 1 of the assumption.

  2. 2.

Item 2: Using $c(g_{\max})$ to denote the value of $g_{\max}$,

$\displaystyle c^{1/2}_{\max}$
$\displaystyle~{}\geq~{}c(g_{\max})~{}\geq~{}\frac{1}{n}\operatorname{OPT}(\mathcal{G})~{}\geq~{}\frac{1}{n}\operatorname{OPT}(\mathcal{G}\cap[\tfrac{1}{2},1])$
$\displaystyle c^{1/2}_{\max}$
$\displaystyle~{}\leq~{}\frac{n}{2}\operatorname{OPT}(\mathcal{G}\setminus
g_{\max})~{}\leq~{}n\operatorname{OPT}(\mathcal{G}\cap[\tfrac{1}{2},1]).$

Thus, under this event, with probability $\frac{1}{3}$ the third algorithm
within the procedure is run and with further constant probability it is
guaranteed to obtain expected value at least
$\Omega(\rho\operatorname{OPT}(\mathcal{G}\cap[\frac{1}{2},1]))\geq\Omega(\rho\operatorname{OPT}(\mathcal{G}\setminus
g_{\max}))$. Overall, in this “remaining situation” the procedure obtains
expected value at least $\Omega(\rho\operatorname{OPT}(\mathcal{G}\setminus
g_{\max}))$, thus concluding the proof. ∎

###  C.1 Proof of Lemma 2.5

Recall that $\operatorname{\mathcal{G}_{T}}(I)\subseteq\mathbb{N}$ denotes the
steps $t$ where the $t$-th item in the interval $I$ is green. We first argue
that the value of the green items in any interval $I$ is large, with high
probability. Recall that $x^{*}$ is the optimal solution consisting only of
green items each of whose value is at most $\frac{OPT}{B}$, and has total
value at least $\frac{OPT}{2}$.

######  Claim C.1.

If $|I|=1/K$ and $B\geq K\log 1/\delta$, then with probability at least
$1-\frac{\delta}{2}$ we have

$\sum_{t\in\operatorname{\mathcal{G}_{T}}(I)}C_{t}x_{t}^{*}~{}\geq~{}\frac{1}{4}\frac{OPT}{K}.$

###### Proof.

The LHS is $\sum_{i\in\mathcal{G}}c_{i}x^{*}_{i}\cdot\mathbf{1}(i\in I)$ and
has expectation at least $\frac{1}{2}\frac{\operatorname{OPT}}{K}$ and
variance

$\displaystyle\text{Var}\left(\sum_{i\in\mathcal{G}}c_{i}x^{*}_{i}\cdot\mathbf{1}(i\in
I)\right)~{}\leq~{}\frac{1}{K}\sum_{i\in\mathcal{G}}\big{(}c_{i}x_{i}^{*}\big{)}^{2}~{}\leq~{}\frac{\operatorname{OPT}}{BK}\,\sum_{i\in\mathcal{G}}c_{i}x_{i}^{*}~{}\leq~{}\,\frac{\operatorname{OPT}^{2}}{BK}\enspace,$

where the second inequality uses that $x_{i}^{*}\in[0,1]$ and that, by
definition, $x_{i}^{*}>0$ only when item $i$ has value
$c_{i}\leq\frac{OPT}{B}$. Then applying Bernstein’s Inequality (Lemma A.3) to
$X_{i}:=c_{i}x_{i}^{*}(\mathbf{1}(i\in I)-|I|)$,

$\displaystyle\Pr\bigg{(}\sum_{i\in\mathcal{G}}c_{i}x^{*}_{i}\cdot\mathbf{1}(i\in
I)\leq\frac{1}{2}\frac{\operatorname{OPT}}{K}-\frac{1}{4}\frac{\operatorname{OPT}}{K}\bigg{)}~{}\leq~{}2e^{-\frac{3B}{64K}}\enspace,$

and the result follows from the assumption $B\geq\Omega(K\log 1/\delta)$. ∎

Next we argue that the total cost in the Lagrangified value is not large. The
proof of this claim goes by first conditioning on the stochastic times of the
green items inside interval $I$. This fixes the order in which we see all the
items, and also fixes the number of greens in $I$. Now at each stochastic time
in $I$, we draw an item from the remaining greens (without replacement), and
use Lemma B.1 to bound the effect of sampling without replacement.

######  Claim C.2.

If $|I|=\frac{1}{K}\leq\frac{1}{4}$, and $B\geq\Omega(K\log(4d/\delta))$, then
with probability at least $1-\frac{\delta}{2}$,

$\sum_{t\in\operatorname{\mathcal{G}_{T}}(I)}\langle{\lambda}_{t},A_{t}x^{*}_{t}\rangle~{}\leq~{}\frac{4B}{K}\enspace.$

###### Proof.

Recall that $\mathcal{G}(I)$ and $G(I)$ denote the set and the number of green
items, respectively, that fall in interval $I$. Let $t_{j}$ be the position of
the $j^{th}$ green item to appear in interval $I$. Then
$\sum_{t\in\operatorname{\mathcal{G}_{T}}(I)}\langle{\lambda}_{t},A_{t}x^{*}_{t}\rangle=\sum_{j\leq
G(I)}\langle{\lambda}_{t_{j}},A_{t_{j}}x^{*}_{t_{j}}\rangle$. Notice that the
$t_{j}$’s are random.

We condition on $G(I)=k$, say, and on their positions
$(t_{1},\ldots,t_{k})=:t_{\leq k}$. Notice that under this conditioning the
stochastic items $(C_{t_{j}},A_{t_{j}})$ are still sampled without replacement
from the green items. Moreover, notice that ${\lambda}_{t_{j}}$ is a function
of the green items before the $j^{th}$ green item in the interval, and
therefore on $(C_{t_{1}},A_{t_{1}}),\ldots,(C_{t_{j-1}},A_{t_{j-1}})$. (It
also depends on the red items in $I$, but these are deterministic.)

In order to upper bound $\sum_{j\leq
G(I)}\langle{\lambda}_{t_{j}},A_{t_{j}}x^{*}_{t_{j}}\rangle$ with high-
probability (conditioned on $G(I)=k$ and $t_{\leq k}$) we use Lemma B.1. For
that, we first notice that due to the feasibility of $x^{*}$ we have
$\mathbb{E}[A_{t_{j}}x^{*}_{t_{j}}\mid G(I)=k,\,t_{\leq
k}]\leq\frac{B\cdot\mathbbm{1}_{d}}{G}$ for all $j$, and hence

$\displaystyle\sum_{j\leq
k}{\Big{\langle}\lambda_{t_{j}},\mathbb{E}\big{[}A_{t_{j}}x^{*}_{t_{j}}~{}\big{|}~{}G(I)=k,t_{\leq
k}\big{]}\Big{\rangle}}\leq\sum_{j\leq
k}\langle\lambda_{t_{j}},\tfrac{B\cdot\mathbbm{1}_{d}}{G}\rangle=\frac{B}{G}k.$

Then applying Lemma B.1 conditionally (setting
$Z^{j}:=\lambda_{t_{j}}|_{G(I)=k,t_{\leq k}}$,
$Y^{j}:=A_{t_{j}}x^{*}_{t_{j}}|_{G(I)=k,t_{\leq k}}$, and
$\varepsilon=\frac{1}{10}$) gives that if $k\leq\frac{G}{2}$ then

$\displaystyle\Pr\bigg{(}\sum_{j}\langle{\lambda}_{t_{j}},A_{t_{j}}x^{*}_{t_{j}}\rangle\geq\frac{3B}{2G}\,k\,+\,\Omega(\log\nicefrac{{4d}}{{\delta}})~{}\bigg{|}~{}G(I)=k,\,t_{\leq
k}\bigg{)}~{}\leq~{}\nicefrac{{\delta}}{{4}}\enspace.$

Taking expectation over the $t_{\leq k}$’s and then over the values of $k$
that are at most $\frac{2G}{K}$ (which is at most $\nicefrac{{G}}{{2}}$ by our
assumption on $K\geq 4$), we get

$\displaystyle\Pr\bigg{(}\sum_{j}\langle{\lambda}_{t_{j}},A_{t_{j}}x^{*}_{t_{j}}\rangle\geq\frac{3B}{K}\,+\,\Omega(\log\nicefrac{{4d}}{{\delta}})~{}\bigg{|}~{}G(I)\leq\nicefrac{{2G}}{{K}}\bigg{)}~{}\leq~{}\nicefrac{{\delta}}{{4}}\enspace.$
(23)

Observe that
$\nicefrac{{3B}}{{K}}+\Omega(\log\nicefrac{{4d}}{{\delta}}\\})\leq\nicefrac{{4B}}{{K}}$
by our assumption $B\geq\Omega(K\log(4d/\delta))$. Next we show that the
conditioning holds with high probability. Indeed,
$\mathbb{E}[G(I)]=\nicefrac{{G}}{{K}}$, so by Bernstein’s inequality

$\displaystyle\Pr(G(I)>\nicefrac{{2G}}{{K}})~{}\leq~{}e^{-\frac{G}{2K}}~{}\leq~{}e^{-\frac{B}{4K}}~{}\leq~{}\nicefrac{{\delta}}{{4d}}~{}\leq~{}\nicefrac{{\delta}}{{4}}\enspace,$
(24)

where the second inequality uses Assumption 2.1 that the green items with
value at most $\frac{\operatorname{OPT}}{B}$ contain a solution of value at
least $\frac{\operatorname{OPT}}{2}$ (hence there are at least $\frac{B}{2}$
green items to obtain the remaining value $\frac{\operatorname{OPT}}{2}$) and
the third inequality uses the assumption that $B\geq\Omega(K\log(4d/\delta))$.
Combining (23) and (24),

$\displaystyle\Pr\bigg{(}\sum_{j}\langle{\lambda}_{t_{j}},A_{t_{j}}x^{*}_{t_{j}}\rangle\geq\frac{4B}{K}\bigg{)}~{}\leq~{}\delta/2\enspace,$

which completes the proof of Claim C.2. ∎

Finally, using Claims C.1 and C.2 and taking a union bound concludes the proof
of Lemma 2.5.

##  Appendix D Missing Proofs from Section 4

###  D.1 Proof that Assumption 4.1 is WLOG

The following lemma formalizes the idea that Assumption 4.1 can be made
without loss of generality.

######  Lemma D.1.

Let $\widetilde{\operatorname{Alg}}$ be an algorithm for packing linear
programs in the Prophets with Augmentations model. Suppose that
$\widetilde{\operatorname{Alg}}$ achieves expected value at least
$\Omega(\operatorname{OPT}_{base})$ on instances where each distribution is
supported on values that are at most $\frac{\operatorname{OPT}_{base}}{20}$.
Then there is an algorithm that achieves expected value
$\Omega(\operatorname{OPT}_{base})$ on arbitrary instances.

###### Proof.

Throughout this section, we use $V_{1},\ldots,V_{n}$ to denote the outcome of
the value of the items of the original instance
$((a_{t},\mathcal{D}_{t})_{t},B)$, $R_{1},\ldots,R_{n}$ as the augmentations
performed by the adversary, and $C_{t}=V_{t}+R_{t}$ the final value revealed
to the algorithm.

For notational convenience let $M:=\frac{\operatorname{OPT}_{base}}{40}$. The
idea is to run two algorithms, one over the items that have value at most $M$
and one over items of value above $M$. To make this precise, define the
operation $\textsf{trunc}(v):=\min\\{v,M\\}$ that truncates a value at $M$.
Let $\widetilde{\mathcal{D}}_{t}$ be the distribution of the truncated random
variable $\textsf{trunc}(V_{t})$. Then we consider the algorithm that flips an
unbiased coin runs one of the following procedures on the (augmented version
of) the original instance $((a_{t},\mathcal{D}_{t})_{t},B)$:

  1. 1.

$\operatorname{Alg}_{low}$: It sends the chopped instance
$((a_{t},\widetilde{\mathcal{D}})_{t},B)$ to the algorithm
$\widetilde{\operatorname{Alg}}$ to obtain a selection policy, and apply this
policy to the sequence of truncated values
$\textsf{trunc}(C_{1}),\ldots,\textsf{trunc}(C_{n})$ to decide which items to
take. Let $X_{t}\in\\{0,1\\}$ denote the indicator whether this policy picked
the $t^{th}$ item.

  2. 2.

$\operatorname{Alg}_{high}$: It picks the first items with value $C_{t}$ above
$M$, if any. Let $\tau\in[n]$ be the index of the item picked ($\tau=\infty$
if did not pick any).

We claim that either $\operatorname{Alg}_{low}$ or $\operatorname{Alg}_{high}$
has value at least $\Omega(\operatorname{OPT}_{base})$, which then proves the
lemma. For that, let $p:=\Pr(\tau<\infty)$ be the probability that some item
has value above $M$. If $p\geq\frac{1}{2}$, then $\operatorname{Alg}_{high}$
already has expected value least $pM\geq\Omega(\operatorname{OPT}_{base})$. We
henceforth assume that $p<\frac{1}{2}$.

Let $\operatorname{OPT}_{trunc}$ be the optimal value of the truncated
instance $((a_{t},\widetilde{\mathcal{D}})_{t},B)$, namely

$\operatorname{OPT}_{trunc}=\mathbb{E}\max_{x}\bigg{\\{}\sum_{t}\textsf{trunc}(V_{t})\cdot
x_{t}~{}:~{}\sum_{t}a_{t}x_{t}\leq
B\cdot\mathbbm{1}_{d}\,,\,x\in\\{0,1\\}^{n}\bigg{\\}}.$

We consider two cases:

#### Case 1:
$\operatorname{OPT}_{trunc}\geq\frac{\operatorname{OPT}_{base}}{2}$.

In every scenario the value of $\operatorname{Alg}_{low}$ is

$\displaystyle\operatorname{Alg}_{low}=\sum_{t}C_{t}X_{t}\geq\sum_{t}\textsf{trunc}(C_{t})\cdot
X_{t}.$ (25)

Moreover, notice that the sequence
$\textsf{trunc}(C_{1}),\ldots,\textsf{trunc}(C_{n})$ can be seen as an
augmented version of the truncated instance
$((a_{t},\widetilde{\mathcal{D}})_{t},B)$, where the adversary performed the
augmentation $\widetilde{R}_{t}:=\textsf{trunc}(C_{t})-\textsf{trunc}(V_{t})$
that is non-negative and only depends on $V_{t}$. Moreover, in this Case 1 we
have that all values in the truncated instance are at most
$M=\frac{\operatorname{OPT}_{base}}{40}\leq\frac{\operatorname{OPT}_{trunc}}{20}$.
Therefore, the approximation guarantee of $\widetilde{\operatorname{Alg}}$
holds in this case hence

$\displaystyle\mathbb{E}\sum_{t}\textsf{trunc}(C_{t})\cdot
X_{t}\geq\Omega(\operatorname{OPT}_{trunc})\geq\Omega(\operatorname{OPT}_{base}),$

where the last inequality again uses the assumption of Case 1. Combined with
Equation 25 this gives that $\operatorname{Alg}_{low}$ has expected value at
least $\Omega(\operatorname{OPT}_{base})$ as desired.

#### Case 2: $\operatorname{OPT}_{trunc}<\frac{\operatorname{OPT}_{base}}{2}$.

Let $X^{*}\in\\{0,1\\}^{n}$ be the optimal solution for the original base
instance $((a_{t},\mathcal{D}_{t})_{t},B)$, namely
$\operatorname{OPT}_{base}=\mathbb{E}\sum_{t}V_{t}X^{*}_{t}$. Since

$V_{t}\,=\,\textsf{trunc}(V_{t})+(V_{t}-\textsf{trunc}(V_{t}))\cdot\mathbf{1}(V_{t}>M),$

we get

$\displaystyle\operatorname{OPT}_{base}$
$\displaystyle=\mathbb{E}\sum_{t}\textsf{trunc}(V_{t})\cdot
X^{*}_{t}+\mathbb{E}\sum_{t}(V_{t}-\textsf{trunc}(V_{t}))\cdot\mathbf{1}(V_{t}>M)\cdot
X^{*}_{t}$
$\displaystyle\leq\operatorname{OPT}_{trunc}+\mathbb{E}\sum_{t}V_{t}\cdot\mathbf{1}(V_{t}>M)$
$\displaystyle=\operatorname{OPT}_{trunc}+\sum_{t}\mathbb{E}[V_{t}\mid
V_{t}>M]\,\Pr(V_{t}>M),$

where the inequality follows from the fact that $X^{*}$ is a feasible solution
for $\operatorname{OPT}_{trunc}$. Moreover, since we are in Case 2, the second
term in the RHS must contribute to at least half of
$\operatorname{OPT}_{base}$, namely

$\displaystyle\operatorname{OPT}_{base}\,$
$\displaystyle\leq~{}2\sum_{t}\mathbb{E}[V_{t}\mid V_{t}>M]\,\Pr(V_{t}>M).$
(26)

Now notice that we can express the value of $\operatorname{Alg}_{high}$ in
every scenario as

$\displaystyle\operatorname{Alg}_{high}=C_{\tau}\geq
V_{\tau}=\sum_{t}\mathbf{1}(\tau\geq t)\cdot\mathbf{1}(V_{t}>M)\cdot V_{t},$

so using the fact that $\tau$ is a stopping time (so $\mathbf{1}(\tau\geq t)$
is defined by the history up to time $t-1$) and that the $V_{t}$’s are
independent, the expected value becomes

$\displaystyle\mathbb{E}\operatorname{Alg}_{high}=\sum_{t}\Pr(\tau\geq
t)\cdot\mathbb{E}[V_{t}\mid
V_{t}>M]\,\Pr(V_{t}>M)\geq\frac{1}{2}\sum_{t}\mathbb{E}[V_{t}\mid
V_{t}>M]\,\Pr(V_{t}>M),$

the inequality following because the probability of $\tau<t$ is at most the
probability $p$ that any item takes value above $M$, and because we have
assumed $p\leq\frac{1}{2}$. Comparing with (26) we see that
$\mathbb{E}\operatorname{Alg}_{high}\geq\Omega(\operatorname{OPT}_{base})$ as
desired. This concludes the proof. ∎

###  D.2 Proof of Lemma 4.2

We consider the following the concave relaxation to the base prophet instance,
where intuitively $x_{t}$ denotes the fraction of times item $t$ is picked by
the optimal offline algorithm:

$\displaystyle\max_{x_{1},\ldots,x_{n}}~{}$
$\displaystyle\sum_{t}x_{t}\cdot\mathbb{E}[V_{t}\mid V_{t}\textrm{ is in its
top $x_{t}$-quantile of $\mathcal{D}_{t}$}]$ s.t.
$\displaystyle\sum_{t}a_{t}x_{t}\leq\nicefrac{{B}}{{4}}\cdot\mathbbm{1}_{d}$
$\displaystyle 0\leq x_{t}\leq 1\enspace.$

We assume that the distributions are continuous, so that the quantiles are
well-defined; this is without loss of generality (see, e.g., [RWW20, §2]).

Let $x_{t}^{*}$ denote the optimal solution of the relaxation, and let
$\mathsf{val}_{t}:=\mathbb{E}[V_{t}\mid V_{t}\textrm{ is in its top
$x_{t}^{*}$-quantile}]$. To prove that this relaxation’s objective value
$\sum_{t}x_{t}^{*}\,\mathsf{val}_{t}$ is at least
$\frac{\operatorname{OPT}_{base}}{4}$, observe that if an item $t$ is picked
for $x_{t}$ fraction of times by the offline optimal solution, its
contribution to the offline objective is at most $\mathbb{E}[V_{t}\mid
V_{t}\textrm{ is in its top $x_{t}$-quantile}]$. Note that although the
relaxation only allows budget $\nicefrac{{B}}{{4}}\cdot\mathbbm{1}_{d}$
(instead of $B\cdot\mathbbm{1}_{d}$), this only hurts the relaxation’s
objective by at most a factor of $4$.

Next we design the desired solution $\psi_{1}(V_{1}),\ldots,\psi_{n}(V_{n})$
for the base prophet instance with expected: We pick item $t$ whenever its
value $V_{t}$ is in the top $x_{t}^{*}$-quantile of $\mathcal{D}_{t}$, that
is, $\psi_{t}(V_{t})=\mathbf{1}(V_{t}$ is in the top $x_{t}^{*}$-quantile of
$\mathcal{D}_{t})$. The expected budget consumed by such an algorithm is at
most $\sum_{t}a_{t}x_{t}^{*}\leq\nicefrac{{B}}{{4}}\cdot\mathbbm{1}_{d}$,
which proves Item 2. To prove Item 1, note that the algorithm’s expected value
is precisely the objective value $\sum_{t}x_{t}^{*}\,\mathsf{val}_{t}$ of the
relaxation above, which is at least $\frac{\operatorname{OPT}_{base}}{4}$.

## References

  * [AD15] Shipra Agrawal and Nikhil R. Devanur.  Fast algorithms for online stochastic convex programming.  In Proceedings of SODA, pages 1405–1424, 2015.
  * [AHK12] Sanjeev Arora, Elad Hazan, and Satyen Kale.  The multiplicative weights update method: a meta-algorithm and applications.  Theory of Computing, 8(1):121–164, 2012.
  * [AHL12] Saeed Alaei, MohammadTaghi Hajiaghayi, and Vahid Liaghat.  Online prophet-inequality matching with applications to ad allocation.  In Proceedings of the 13th ACM Conference on Electronic Commerce, EC, pages 18–35, 2012.
  * [Ala14] Saeed Alaei.  Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers.  SIAM Journal on Computing, 43(2):930–972, 2014.