1

arXiv:1711.05764v1 [] 15 Nov 2017

Online Allocation with Traffic Spikes: Mixing Adversarial and
Stochastic Models
HOSSEIN ESFANDIARI, University of Maryland
NITISH KORULA, Google Research
VAHAB MIRROKNI, Google Research
Motivated by Internet advertising applications, online allocation problems have been studied extensively in
various adversarial and stochastic models. While the adversarial arrival models are too pessimistic, many
of the stochastic (such as i.i.d or random-order) arrival models do not realistically capture uncertainty in
predictions. A significant cause for such uncertainty is the presence of unpredictable traffic spikes, often due
to breaking news or similar events. To address this issue, a simultaneous approximation framework has been
proposed to develop algorithms that work well both in the adversarial and stochastic models; however, this
framework does not enable algorithms that make good use of partially accurate forecasts when making online
decisions. In this paper, we propose a robust online stochastic model that captures the nature of traffic spikes
in online advertising. In our model, in addition to the stochastic input for which we have good forecasting, an
unknown number of impressions arrive that are adversarially chosen. We design algorithms that combine a
stochastic algorithm with an online algorithm that adaptively reacts to inaccurate predictions. We provide
provable bounds for our new algorithms in this framework. We accompany our positive results with a set of
hardness results showing that our algorithms are not far from optimal in this framework. As a byproduct of
our results, we also present improved online algorithms for a slight variant of the simultaneous approximation
framework.
Additional Key Words and Phrases: Online Matching, Online Budgeted Allocation, Traffic Spikes, Online
Advertisement
ACM Reference format:
Hossein Esfandiari, Nitish Korula, and Vahab Mirrokni. 2017. Online Allocation with Traffic Spikes: Mixing
Adversarial and Stochastic Models. 1, 1, Article 1 (November 2017), 23 pages.
https://doi.org/10.1145/nnnnnnn.nnnnnnn

1

INTRODUCTION

In the past decade, online budgeted allocation problems have been studied extensively due to their
important applications in Internet Advertising. In such problems, we are given a bipartite graph
G = (X , Y , E) with a set of fixed nodes (also known as agents, or advertisers) Y , a set of online nodes
(corresponding to items or impressions) X , and a set E of edges between them. Each agent / fixed
node j ∈ Y is associated with a total weighted capacity (or budget) c j ; in the context of Internet
advertising, each agent corresponds to an advertiser with a fixed budget to spend on showing
their ad to users. The items / online nodes i ∈ X arrive one at a time, along with their incident
edges (i, j) ∈ E(G) and the weights w i, j on these edges. These online nodes correspond to search
queries, page-views, or in general, impressions of ads by users. Upon the arrival of an item i ∈ X ,
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee
provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and
the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored.
Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires
prior specific permission and/or a fee. Request permissions from permissions@acm.org.
© 2017 Association for Computing Machinery.
XXXX-XXXX/2017/11-ART1 $15.00
https://doi.org/10.1145/nnnnnnn.nnnnnnn

, Vol. 1, No. 1, Article 1. Publication date: November 2017.

1:2

Hossein Esfandiari, Nitish Korula, and Vahab Mirrokni

the algorithm can assign i to at most one agent j ∈ Y where (i, j) ∈ E(G) and the total weight of
nodes assigned to j does not exceed c j . The goal is to maximize the total weight of the allocation.
This problem is known as the Budgeted Allocation or AdWords problem, and it has been studied
maxi, j w i, j
→ 0, in [Buchbinder et al. 2007; Devanur and Hayes 2009;
under the assumption that min
j cj
Mehta et al. 2007] (called the large-degree assumption). Many variants of this problem such as the
display ads problem [Feldman et al. 2009a] have been studied, and techniques to solve the budgeted
allocation problem have been generalized to solve those problems.
Traditionally, results have been developed for a worst-case arrival model in which the algorithm
does not have any prior on the arrival model of online nodes. Under this most basic online model,
known as the adversarial model, the online algorithm does not know anything about the items
or E(G) beforehand. In this model, the seminal result of Karp, Vazirani and Vazirani [Karp et al.
1990] gives an optimal online 1 − e1 -competitive algorithm to maximize the size of the matching
for unweighted graphs where w i j = 1 for each (i, j) ∈ E(G). For weighted graphs, Mehta et
al. [Buchbinder et al. 2007; Mehta et al. 2007] presented the first 1 − e1 -approximation algorithm to
maximize the total weight of the allocation for the AdWords problem.
In practical settings motivated by placement of Internet ads, the incoming traffic of page-views
may be predicted with a reasonable precision using a vast amount of historical data. Motivated
by this ability to forecast traffic patterns, various stochastic online arrival models have been
introduced. Such models include (i) the i.i.d. stochastic arrival model in which there is a (known or
unknown) distribution over the types of items, and each item that arrives is drawn i.i.d. from this
distribution [Feldman et al. 2009b; Vee et al. 2010], or (ii) the random order model [Agrawal et al.
2009; Devanur and Hayes 2009; Feldman et al. 2010], which makes the weaker assumption that
individual items and edge weights can be selected by an adversary, but that they arrive in a random
order. Several techniques have been developed to design asymptotically optimal online allocation
algorithms for these stochastic arrival models (For example, these algorithms include a set of
dual-based algorithms [Devanur and Hayes 2009; Feldman et al. 2010], and a set of primal-based
algorithms discussed later).
These algorithms for the stochastic models are useful mainly if the incoming traffic of items
(i.e. online impressions) can be predicted with high precision. In other words, such algorithms
tend to rely heavily on a precise forecast of the online traffic patterns (or if the forecast is not
explicitly provided in advance, that the pattern ‘learnt’ by the algorithm is accurate), and hence
these algorithms may not react quickly to sudden changes in traffic. In fact, the slow reaction to
such traffic spikes imposes a serious limitation in the real-world use of stochastic algorithms for
online advertising, and more generally, this is a common issue in applying stochastic optimization
techniques to online resource allocation problems (see e.g., [Wang et al. 2006]). To the best of our
knowledge, no large Internet advertising systems deploy such stochastic allocation algorithms
‘as-is’ without modifications to deal with situations where the forecasts are inaccurate. Various
techniques such as robust or control-based stochastic optimization have been described in the
literature [Ben-Tal and Nemirovski 2002; Bertsimas et al. 2004; Tan and Srikant 2011; Wang et al.
2006] to deal with this shortcoming, but they do not provide theoretical guarantees when the input
is near-adversarial.
One recent theoretical result in this direction is the simultaneous adversarial and stochastic
framework [Mirrokni et al. 2011]. The main question of this recent work is whether there exists
an algorithm which simultaneously achieves optimal approximation ratios in both the adversarial
and random-order settings. More specifically, does there exist an algorithm achieving a 1 − ε
approximation for the random-order model, and at the same time achieving a 1 − e1 -approximation
for the adversarial model? Mirrokni et al. [2011] showed that the answer to this question is positive

, Vol. 1, No. 1, Article 1. Publication date: November 2017.

Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models

1:3

for unweighted bipartite graphs, but it is negative for the general budgeted allocation problem.
Further, they show that the best 1 − e1 -competitive algorithm for the adversarial model achieves a
0.76-approximation in the random-order model. Though this shows that the adversarial algorithm
has an improved competitive ratio in stochastic settings, it does not use forecast information
explicitly, and hence it can be quite far from optimal even when the forecast is perfectly accurate.
Moreover, the simultaneous approximation framework is still trying to design an algorithm that is
guaranteed to work well in extreme situations (where the input follows the forecast perfectly, or
is completely adversarial). What if the forecast is mostly, but not entirely accurate? For instance,
suppose traffic to a website largely follows the prediction, but there is a sudden spike due to a
breaking news event? Treating this as entirely adversarial input is too pessimistic.
Our Model and Results. In this paper, we propose a model of online stochastic budgeted
allocation with traffic spikes, referred to as Robust Budgeted Allocation, that goes beyond the worstcase analysis in the adversarial model, and develop algorithms that explicitly use the stochastic
information available for arrival pattern. In our model, in addition to the stochastic input for which
we have good forecasting, an unknown number of impressions arrive that are adversarially chosen.
This model is motivated by the patterns of traffic spikes in online advertising in which part of the
incoming traffic of users may be the result of a new event that we did not predict, corresponding
to a new traffic pattern. We design an algorithm that adaptively checks if the traffic forecast is
accurate, and reacts to flaws in traffic forecasting due to traffic spikes. We measure the accuracy
of the forecast in terms of a parameter λ which, roughly speaking, captures the fraction of the
value of an optimal solution that can be obtained from the stochastic input (as opposed to the
adversarially chosen impressions). In general, the competitive ratio of the algorithm will naturally
increase with λ. Furthermore, we accompany our results with a set of hardness results showing
that our provable approximation guarantees are not far from the optimal achievable bounds. Hence,
compare to the simultaneous approximation framework of [Mirrokni et al. 2011], our method
provides almost-optimal approximation guarantees for all values of λ, and not only for the extreme
cases where either the input is totally adversarial or totally stochastic.
Interestingly, our techniques also result in new approaches for the simultaneous approximation
framework of [Mirrokni et al. 2011]; though the models are slightly different (i.i.d. vs. random
order, as well as the fact that we require a possibly inaccurate forecast of traffic), our algorithm
gives improved performance for the weighted case under uncertain input compared to what was
achieved in that paper. Section 2 describes the model precisely, allowing us to formally state our
results.
Our technique is based on defining a notion of ε-closeness in distributions, and then understanding the behaviour of an online algorithm over sequences that are ε-close to a given distribution.
Most notably, we can show how to modify any online stochastic algorithm to work for online
adversarial input sequences that are ε-close to a known distribution. This technique is summarized
in the next section. We then combine such a modified stochastic algorithm with an adversarial
algorithm to guarantee robustness. Converting this idea to provable algorithms for the robust
online allocation problem requires applying several combinatorial lemmas and proving invariants
that can be converted to a factor-revealing mathematical program, which can then be analyzed
numerically and analytically to prove desirable competitive ratios.
1.1

Other Related Work

Online Stochastic Allocation. Two general techniques have been applied to get improved approximation algorithms for online stochastic allocation problems: primal-based and dual-based
, Vol. 1, No. 1, Article 1. Publication date: November 2017.

1:4

Hossein Esfandiari, Nitish Korula, and Vahab Mirrokni

techniques. The dual-based technique is based on solving a dual linear program on a sample instance, and using this dual solution in the online decisions. This method was pioneered by Devanur
and Hayes [Devanur and Hayes 2009] for the AdWords problem and extended to more general
problems [Agrawal et al. 2009; Feldman et al. 2010; Vee et al. 2010]. It gives a 1 − ε-approximations
for the random order model if the number of items m is known to the algorithm in advance, and
m log n
O PT
w i j ≥ O( ε 3 ), where n := |Y | is the number of agents. The primal-based technique is based on
solving an offline primal instance, and applying this solution in an online manner. This method
applies the idea of power-of-two choices, and gives improved approximation algorithms for the
iid model with known distributions. This technique was initiated by [Feldman et al. 2009b] for
the online (unweighted) matching problem and has been improved [Bahmani and Kapralov 2010;
Haeupler et al. 2011; Jaillet and Lu 2013; Menshadi et al. 2011]. All the above algorithms heavily
rely on an accurate forecast of the traffic. An alternative technique that has been applied to online
stochastic allocation problems is based on optimizing a potential function at each stage of the
algorithm [Devanur et al. 2011, 2012]. This technique has been analyzed and proved to produce
asymptotically optimal results under the i.i.d. model with unknown distributions. Although this
technique does not rely on the accurate predictions as much, it does not combine stochastic and
adversarial models, and the analysis techniques used are not applicable to our robust online allocation model. For unweighted graphs, it has been recently observed that the Karp-Vazirani-Vazirani
1 − e1 -competitive algorithm for the adversarial model also achieves an improved approximation
ratio of 0.70 in the random arrival model [Karande et al. 2011; Mahdian and Yan 2011]. This holds
even without the assumption of large degrees. It is known that without this assumption, one
cannot achieve an approximation factor better than 0.82 for this problem (even in the case of i.i.d.
draws from a known distribution) [Menshadi et al. 2011]. All the above results rely on stochastic
assumptions and apply only to the random-order or the iid stochastic models.
Robust stochastic optimization. Dealing with traffic spikes and inaccuracy in forecasting the
traffic patterns is a central issue in operations research and stochastic optimization. Methods including robust or control-based stochastic optimization [Ben-Tal and Nemirovski 2002; Bertsimas et al.
2004; Tan and Srikant 2011; Wang et al. 2006] have been proposed. These techniques either try to
deal with a larger family of stochastic models at once [Ben-Tal and Nemirovski 2002; Bertsimas et al.
2004; Wang et al. 2006], try to handle a large class of demand matrices at the same time [Applegate
and Cohen 2006; Azar et al. 2003; Wang et al. 2006], or aim to design asymptotically optimal
algorithms that react more adaptively to traffic spikes [Tan and Srikant 2011]. These methods have
been applied in particular for traffic engineering [Wang et al. 2006] and inter-domain routing [Applegate and Cohen 2006; Azar et al. 2003]. Although dealing with similar issues, our approach and
results are quite different from the approaches taken in these papers. For example, none of these
previous models give theoretical guarantees in the adversarial model while preserving an improved
approximation ratio for the stochastic model. Finally, an interesting related model for combining
stochastic and online solutions for the Adwords problem is considered in [Mahdian et al. 2007],
however their approach does not give an improved approximation algorithm for the i.i.d. model.

2
2.1

PRELIMINARIES AND TECHNIQUES
Model

Let I denote a set of item ‘types’; in the Internet advertising applications, these represent queries /
ad impressions with different properties that are relevant to advertiser targeting and bidding. A
forecast F = (D, f ) has two components: A distribution D over I, together with a number f ; this is
interpreted as a prediction that f items will arrive, each of which is drawn independently from D.
, Vol. 1, No. 1, Article 1. Publication date: November 2017.

Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models

1:5

In the Stochastic Budgeted Allocation problem, the input known to the algorithm in advance is a
forecast F = (D, f ), and a set of agents Y , with a capacity c j for agent j. A sequence of f items is
drawn from the distribution D and sent to the algorithm one at a time; the algorithm must allocate
these items as they appear online. The total weight of items allocated to agent j must not exceed c j ,
and the objective is to maximize the weight of the allocation. As discussed above, there has been
considerable work on near-optimal algorithms for Stochastic Budgeted Allocation [Agrawal et al.
2009; Alaei et al. 2012; Devanur and Hayes 2009; Feldman et al. 2010; Vee et al. 2010].
In this paper, we define the new Robust Budgeted Allocation problem, for which our input model is
the following: The adversary can create in advance an arbitrary forecast F = (D, f ), and a collection
of agents Y . Further, at each time step, the adversary can either create a new arbitrary item (together
with its incident edges and weights) and send it to the algorithm, or choose to send an item drawn
from D. After at least f items have been drawn from D, the adversary can either send additional
(arbitrary) items, or choose to terminate the input. The online algorithm knows in advance only
the forecast F and the agents Y , and so it knows that it will receive f items corresponding to i.i.d.
draws from D; it does not know anything about the items created by the adversary, where in the
sequence they arrive, or the total number m of items that will arrive. As usual, the competitive ratio
of the algorithm is measured by the worst-case ratio (over all inputs) of the value of its allocation
to the value of the optimal allocation on the sequence that arrives.
With the preceding description of the model, no algorithm can have a competitive ratio better
than 1 − 1/e, for the simple reason that we could set f = 0, allowing the adversary to control the
entire input. (Or even for larger f , the edge weights for the adversarial items could be considerably
larger than the weights for the forecast items in I.) We have not quantified the accuracy of the
forecast, or meaningfully limited the power of the adversary. Our goal is to design algorithms with
a competitive ratio that improves with the accuracy of the forecast. We quantify this accuracy as
follows:
Definition 2.1. For an instance I of the Robust Budgeted Allocation problem with forecast (D, f ),
let S(I ) denote the set of f ‘stochastic’ items drawn from distribution D. Let A(I ) denote the set
of n − f ‘adversarial’ items. When I is clear from context, we simply use S and A to denote the
stochastic and adversarial items respectively. We mildly abuse notation and, when clear from
context, also use I to refer to the sequence of items in an instance. For a solution Sol to an instance I ,
let ValS (Sol) denote the value obtained by Sol from allocating the items of S to agents, and ValA (Sol)
denote the value obtained by Sol from allocating the items of A.
Definition 2.2. An instance I of the Robust Budgeted Allocation problem is said to be λ-stochastic
S (Sol )]
if λ = maxSol ∈O PT (I ) { E[ValSE[Val
(Sol )+ValA (Sol )] }, where OPT (I ) is the set of all optimal solutions of I .
Note that when the forecast is completely accurate (there are no adversarial items), the instance
is 1-stochastic, and when f = 0 (all items are adversarial), the input is 0-stochastic. Though λ is
unknown to the algorithm, our goal is to design algorithms which, when restricted to λ-stochastic
instances, have good competitive ratio (ideally, increasing in λ).
2.2

Algorithms for Working with Forecasts

In this section, we consider how to solve the Stochastic Budgeted Allocation problem. Similar
problems have been applied before (see e.g. [Alaei et al. 2012]), but we describe a specific approach
below that will be a useful tool for the Robust Budgeted Allocation problem. Further, our argument
implies that this approach performs well even for an adversarial input sequence if it is sufficiently
‘close’ to the forecast.
, Vol. 1, No. 1, Article 1. Publication date: November 2017.

1:6

Hossein Esfandiari, Nitish Korula, and Vahab Mirrokni

Roughly speaking, given a forecast F = (D, f ), if the number of items f is sufficiently large, then
we can work with an ‘expected instance’. In the expected instance, the set of items is created by
assuming each type t ∈ I arrives in proportion to P D=t . We then run any (offline) algorithm Alg on
the expected instance; when an item arrives in the real online instance, we assign it according to
the allocation given by Alg on the expected instance. If the number of items f is sufficiently large,
then only a small error is induced because we assign according to the expected instance instead of
the random realization of the forecast.
We begin by defining the notion of a sequence being ε-close to a distribution. Indeed, we show that
with high probability a ‘long’ sequence of draws from a distribution is ε-close to that distribution,
where ε is an arbitrary small constant. We next prove that if we ignore inputs which are not
ε-close to the input distribution, we lose only m1 in the competitive ratio. Finally, we show that we
can modify any online stochastic algorithm, or more strongly any offline algorithm for Budgeted
Allocation to work for online adversarial input sequences which are guaranteed to be ε-close to a
known distribution. Interestingly, this reduction loses only 4ε on the competitive ratio.
Definition 2.3. Let S = ⟨s 1 , s 2 , ..., sm ⟩ be a sequence of items and let D be a distribution over a
set of item types I. For a type t ∈ I, let P D=t be the probability that a draw from D is t. We say S
is ε-close to distribution D, if for any continuous sub-sequence Si,k = si , si+1 , . . . , sk ⊂ S and any
type t, the number of items of type t in Si,k is within the range (k − i + 1 ± εm)P D=t . If S is not
ε-close to distribution D we say it is ε-far from the distribution.
Consider that (k − i + 1)P D=t is the expected number of items of type t in a set of k − i + 1 draws
from D. When k − i + 1 is large, using the Chernoff bound we can show that the number of items of
type t is close to the expectation. On the other hand, when k − i + 1 is small, the term εm dominates
k − i + 1, and thus the number of items of type t is in the range (k − i + 1 ± εm)P D=t . Lemma 2.6
formalizes this intuition, showing that with high probability a [long enough] sequence of items
drawn from a distribution D is ε-close to D.
Definition 2.4. Given a distribution D, a sequence of f items is said to satisfy the long input
f
condition for D if log(f ) ≥ ε 2mint 15
.
∈D (P D=t )
We use the following version of the Chernoff bound in Lemma 2.6.
Proposition 2.5. Let x 1 , x 2 , . . . , xm be a set of independent boolean random variables. For X =
Ím
−δ 2
i=1 x i and µ = E[X ] we have: Pr (|X − µ | ≥ δ ) ≤ 2 exp( 3µ )
Lemma 2.6. Let S be a sequence of m items drawn from a distribution D. Assuming the long input
condition, the probability that S is ε-far from D is at most m12 .
Proof. S contains m(m−1)
subsequences. In addition, the long input condition gives us P D=t ≥
2
2m
3
15 log(m)
. This means that there are at most 15 εlog(m)
different types. Thus, we have fewer than m2
ε 2m
combinations of a type and a subsequence. We next argue that the probability that the number of
items of a fixed type t in a fixed sub sequence Si,k is out of the range (k − i + 1 ± εm)P D=t is at
3
most m25 . Applying the union bound, the probability that S is ε-far from D is at most m25 m2 = m12 ,
as desired.
For a type t and an index 1 ≤ ℓ ≤ m, let x ℓt be a random variable which is 1 if the ℓ-th item in
sequence S is of type t and is 0 otherwise. The variables x kt are independent for a fixed type t and
t be Ík x t , which is the number of items of type t in the sub sequence
different indices. Let X i,k
ℓ=i ℓ
, Vol. 1, No. 1, Article 1. Publication date: November 2017.

Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models

1:7

t is (k − i + 1)P
Si,k . The expected value of X i,k
D=t , and by applying the Chernoff bound we have:

−ε 2m 2
)
3(j − i + 1)Pt =D
−ε 2m 2
)
≤ 2 exp(
2
3n 15 mε
log(m)

Pr (|X i,t j − (j − i + 1)P D=t | ≥ εm) ≤ 2 exp(

= 2 exp(−5 log(m)) =
This completes the proof of the lemma.

2
.
m5
□

In the rest of this section, we use the monotonicity and subadditivity properties of Budgeted
Allocation, stated in Lemma 2.7 and Lemma 2.8 respectively.
Lemma 2.7 (Monotonicity). Budgeted Allocation is monotone: Fixing the set of agents and their
capacities, for any sequence of items S and any sequence T ⊆ S, we have Opt(T ) ≤ Opt(S) where
Opt(S) and Opt(T ) are the values of the optimum solutions when the items that arrive are S and T
respectively.
Proof. Any feasible allocation of items of T is a feasible allocation of items of S as well. This
immediately means Opt(T ) ≤ Opt(S) as desired.
□
Lemma 2.8 (subadditivity). Budgeted Allocation is subadditive: Fixing the set of agents and
their capacities, for any sequence of items S and any sequence of items T , we have Opt(S ∪ T ) ≤
Opt(S) + Opt(T ) where Opt(X ) indicates the size of the optimum solution when the sequence of items
that arrive is X.
Proof. Fix an optimum solution Opt(S ∪ T ). The allocation of items of S in Opt(S ∪ T ) is a
feasible allocation for S. Similarly the allocation of items of T in Opt(S ∪ T ) is a feasible allocation
for T . Therefore we have Opt(S ∪ T ) ≤ Opt(S) + Opt(T ).
□
Lemma 2.6 says that w.h.p, a sequence of items drawn from a distribution D is ε-close to D. That
is, inputs which are ε-far from the input distribution are rare, but this does not immediately imply
that the total value of such rare ε-far inputs is small as well. Lemma 2.9 says that we may ignore all
inputs which are ε-far from the input distribution and only lose a small fraction in the competitive
ratio.
Lemma 2.9. Let S be a sequence of m items drawn from a distribution D, satisfying the long input
condition. Let Alg be an α-competitive algorithm for Stochastic Budgeted Allocation with forecast
(D, m). Let Algclose be an algorithm that has the same outcome as Alg when the input is ε-close to D
and 0 otherwise. Algclose is (α − m1 )-competitive.
Proof. Let Algfar be an algorithm that has the same outcome as Alg when the input is ε-far
from D and 0 otherwise. We slightly abuse notation and use Alg, Algclose , Algfar to refer both to
the algorithms and the expected values of their outcomes. By definition we have Alg = Algclose +
Algfar . Let Opt denote the expected value of an optimal solution on the sequence drawn from the
distribution. We bound the expected outcome of Algfar to compare the competitive ratio of Alg and
Algclose .
Let Sk be an input that contains k items of each type. The monotonicity of Budgeted Allocation
implies that for any sequence S of size m, Opt(Sm ) is greater than Opt(S). Moreover, by subadditivity,
Opt(Sm ) is at most m2 times Opt(S 2 ). Together, these imply that, for any sequence S of size m, we
, Vol. 1, No. 1, Article 1. Publication date: November 2017.

1:8

Hossein Esfandiari, Nitish Korula, and Vahab Mirrokni

have Opt(S) ≤ m2 Opt(S 2 ). On the other hand, the number of items of type t in any sequence S of
size m which is ε-close to D is at least
15
15
(1 − ε)f P D=t ≥ (1 − ε) 2
P D=t ≥ (1 − ε) 2 ≥ 2.
ε mint ∈D (P D=t )
ε
Thus by monotonicity we have
of size m we have

1
P r (S is ε close to D) Optclose

Opt(S) ≤

≥ Opt(S 2 ). Therefore, for any sequence S

m
m
1
Optclose ≤ mOpt
Opt(S 2 ) ≤
2
2 (1 − m12 )

This together with Lemma 2.6 gives us
Algclose = Alg − Algfar ≥ Alg − mOpt
as desired.

1
1
1
≥ αOpt − Opt = (α − )Opt
2
m
m
m
□

Note that any algorithm Alg for Budgeted Allocation has a random outcome when the items are
drawn from a forecast, simply due to the randomness in the sequence of items. We now define a
derandomization of such algorithms: Given an algorithm Alg, a forecast F = (D, f ) and a constant
ε, algorithm DeRandεF (Alg) is defined as follows:
Let S ′ be a sequence of (1 − ε)f impressions, with (1 − ε)f P D=t impressions of type t, for each
type t. Run algorithm Alg on sequence S ′. Let Alg(S ′, t, i) be the agent to which Alg assigns the ith
impression of type t in S ′. Note that any sequence of f items which is ε-close to D contains at least
(1 − ε)f P D=t impressions of each type t. We can now describe how DeRandεF (Alg) allocates items of
a sequence S. For each type t, Algorithm DeRandεF (Alg) allocates the first (1 −ε)f · P D=t impressions
of type t in S in the same manner as Alg allocated S ′. That is, we assign the ith impression of type
t in S to Alg(S ′, t, i). After the first (1 − ε)f P D=t impressions of type t have been allocated, we do
not allocate any more items of this type. Finally, if at any time during the algorithm, we observe
that the input sequence (so far) is not ε-close to distribution D, the algorithm stops and returns
false. Otherwise, it returns true.
When it is clear from the context, we drop F and ε from the notation of DeRandεF (Alg).
Remark 2.10. Note that for any forecast F = (D, f ) and constant ε, the outcome of DeRandεF (Alg)
on any item sequence of length f that is ε-close to D is a function purely of D and ε, but not the actual
impressions in the sequence.
Theorem 2.11. Let F = (D, f ) be a distribution, and let A be an adversarial input with length
f such that A satisfies the long input condition and A is ε-close to D. Let Alg be an α-competitive
algorithm for Stochastic Budgeted Allocation. Though A is not explicitly drawn from D, DeRandεF (Alg)
is α − 2ε competitive on sequence A.
Proof. Since A is ε-close to D, DeRand(Alg) will not return false on S, and thus, the allocation
of DeRand(Alg) on S is identical to that of Alg on S ′. Let S ′′ be a sequence of (1 + ε)d impressions,
(1 + ε)f P D=t from each type t. Using the subadditivity of Budgeted Allocation, we have Opt(S ′) ≥
1−ε
′′
′′
1+ε Opt(S ) ≥ (1 − 2ε)Opt(S ).
On the other hand, using the monotonicity of Budgeted Allocation, Opt(A) ≤ Opt(S ′′). Together,
these inequalities imply that Opt(S ′) ≥ (1 − 2ε)Opt(A), which means that DeRandεF (Alg) is (α − 2ε)competitive.
□
Consider an α-competitive online algorithm (or α-approximate offline algorithm), Alg, for
Budgeted Allocation with stochastic input. By Theorem 2.11, for inputs which are ε-close to
, Vol. 1, No. 1, Article 1. Publication date: November 2017.

Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models

1:9

Fig. 1. Summary of results, parametrized by λ. The blue curve denotes the upper bound on the competitive
ratio of any algorithm, the green curve is our algorithm for the unweighted case, and the red curve is our
algorithm for the weighted case.

D, DeRandεF (Alg) has a competitive ratio that is only 2ε worse than that of Alg. Moreover, Lemma
2.9 says that if we ignore all inputs which are ε-far from the input distribution, we lose only m1 on
the competitive ratio. Together with the assumption that ε ≥ m1 , we obtain the following corollary.
Corollary 2.12. Let Alg be an α-competitive algorithm for Stochastic Budgeted Allocation (or
α-approximate offline algorithm for Budgeted Allocation). Assuming the long input condition, for any
small constant ε ≥ m1 and any forecast F , DeRandεF (Alg) is an (α − 3ε)-competitive algorithm for
Stochastic Budgeted Allocation.
3

ROBUST ONLINE BUDGETED ALLOCATION

In this section, we consider the Robust Budgeted Allocation problem. As described above, the
algorithm knows in advance the set of agents Y , together with a capacity c j for each agent j ∈ Y .
Further, it knows the forecast F = (D, f ), but not how many additional items will be sent by the
adversary, nor how they are intermixed with the f items drawn from D.
Recall that a λ-stochastic instance is one where the ‘stochastic items’ (those drawn from D)
provide λ-fraction of the value of an optimal solution. (Also, note that λ is not known to the
algorithm.) As λ increases (corresponding to an increase in the accuracy of our forecast, or a smaller
traffic spike), we expect the performance of our algorithms to improve. However, we wish our
algorithms to be robust, obtaining good performance compared to an optimal offline solution even
when λ is close to 0 (corresponding to a very large traffic spike, when the typical ‘forecast’ traffic is
only a small fraction of the total).
First, in Section 3.1, we consider the unweighted Robust Budgeted Allocation problem, in which
w i j is the same for all (i, j) ∈ E. As desired, we obtain an algorithm with competitive ratio tending
to 1 as λ tends to 1, and 1 − 1/e when λ tends to 0. Then, in Section 3.2, we consider the general
weighted Robust Budgeted Allocation problem, and finally, in Section 3.3, we give upper bounds on
the competitive ratio of any algorithm. All our competitive ratios are parametrized by λ, and they
are summarized in Figure 1.
, Vol. 1, No. 1, Article 1. Publication date: November 2017.

1:10

Hossein Esfandiari, Nitish Korula, and Vahab Mirrokni

For simplicity, throughout this section, we assume that the capacity of all the agents are the
same (normalized to 1). This assumption can be removed by dividing agents with large capacities
into multiple dummy agents. Moreover, as usual we assume maxi, j w i, j → 0 (a.k.a., large degree
assumption).

3.1

Unweighted Robust Budgeted Allocation

Our general approach will be to simulate the following idea: Suppose we first receive the f stochastic
items drawn from D. We could allocate these items optimally (assuming they are the entire input).
If this uses up most of the budgets of the agents, we automatically have a good solution, even if we
do not allocate any of the adversarial items. If some fraction of the budgets remain unused, use this
remaining capacity to allocate any adversarial items that arrive. If there is a way to allocate these
adversarial items using the remaining capacities, we obtain 1 − 1/e fraction of this value.
Unfortunately, in the real Robust Budgeted Allocation model, we do not know which items are
stochastic and which are adversarial, so we cannot perform this clean separation perfectly. Still, we
can approximate this separation as follows: Let A be an algorithm for Stochastic Budgeted Allocation.
We have two algorithms running simultaneously. The first is a slight variant of DeRandεF (A), and
the second is Balance [Kalyanasundaram and Pruhs 2000]. More precisely, we send each item to
DeRandεF (A); recall that this algorithm first checks if the input seen so far is ε-close to D. If it is, it
allocates this item according to A; otherwise, it returns false. Now, instead of returning false, we
assume that this item must have been sent by the adversary. As such, we erase this item from the
history of DeRandεF (A), and try to allocate it using Balance. That is, we ‘guess’ that all items that
are matched by DeRandεF (A) are stochastic items and all other items are adversarial.
Note that DeRandεF (A) does not match more than (1 − ε)f items, (1 − ε)f P D=t from each type t.
From Lemmas 2.6 and 2.9, we know that w.h.p., the sequence of stochastic items is ε-close to D; by
ignoring the case when it is ε-far from D, we lose at most m1 in the competitive ratio. Given the
long input assumption, 1/m < ε, and hence by losing ε in the competitive ratio, we assume that the
stochastic items are always ε-close to D. Since the sequence of stochastic items is ε-close to D, we
have at least (1 − ε)f P D=t items of type t. Therefore, the items that DeRandεF (A) leaves unallocated
are a superset of all the adversarial items. (More precisely, there may be an adversarial item of type
t that we guess is stochastic, but there must be a corresponding stochastic item of type t that we
treat as adverarial instead.)
We now complete the description of our combined algorithm: Given an allocation, let x j denote
the fraction of agent j’s budget used in this allocation. Let AlgS be a (1 − ε)-competitive algorithm
Í
for Stochastic Budgeted Allocation with the further property that it minimizes nj=1 x j2 . (In other
words, AlдS reproduces an optimal offline solution such that each item is allocated to an eligible
agent with the lowest x j .) We run DeRandεF (AlgS ) as the first of our two algorithms. Recall from
Remark 2.10 we know the exact allocation of DeRandεF (AlдS ), which is independent of the random
draws. If x j denotes the fraction of agent j’s capacity used by this allocation, for items unallocated
by DeRandεF (AlдS ), we run the Balance algorithm on the instance of Budgeted Allocation with the
adversarial items, and in which the capacity of agent j is 1 − x j .
How does this combined algorithm perform? We use S to denote the stochastic items, and A the
adversarial items. From Corollary 2.12 we know that DeRandεF (AlgS ) is 1 − O(ε) competitive against
Opt(S). We will prove in Lemma 3.12 that the optimum solution on the items of A using the remaining
capacities 1−x j is at least (1−λ −O(ε))(Opt(A∪S)−Opt(S)). Since Balance is a (1−1/e)-competitive
algorithm, the value we derive from Balance is at least (1 − e1 )(1 − λ − O(ε))(Opt(A ∪ S) − Opt(S)).

, Vol. 1, No. 1, Article 1. Publication date: November 2017.

Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models

1:11

Ín
Minimize:

j=1 (y j − z j )
Ín
j=1 y j

Subject to: z j ≤ max(0, x j + y j − 1)
n
Õ
(x k + yk ) ≤ n − j

∀1 ≤ j ≤ n
∀1 ≤ j ≤ n − 1 s.t. x j < x j+1

k =j+1

x j ≤ x j+1
n
n
n
Õ
Õ
Õ
λ( x j +
yj ) ≥
xj
j=1

j=1

∀1 ≤ j ≤ n − 1

j=1

0 ≤ x j , yj , zj ≤ 1

∀1 ≤ j ≤ n

Fig. 2. Mathematical Program 2 to bound the optimum allocation of adversarial items on the remaining
capacities in uniform weight case.

Therefore, the competitive ratio of the combined algorithm is at least:
(1 − O(ε))Opt(S) + (1 − λ − O(ε))(1 − e1 )(Opt(A ∪ S) − Opt(S))
Opt(S ∪ A)
λOpt(S ∪ A) + (1 − λ)2 (1 − e1 )Opt(S ∪ A) − O(ε)Opt(S ∪ A)
=
Opt(S ∪ A)
1
= λ + (1 − λ)2 (1 − ) − O(ε)
e
where the first equality uses the definition of λ-stochastic to replace Opt(S) with λOpt(S ∪ A). This
proves the following theorem.
Theorem 3.1. Assuming the long input condition, there exists a λ +(1−λ)2 (1− e1 )−O(ε) competitive
algorithm for Robust Budgeted Allocation when the input is λ-stochastic. This algorithm does not
depend on λ.
In order to prove the key Lemma 3.12, we first write Mathematical Program 2, and show in
Lemma 3.3 that this lower bounds the ratio of the optimum allocation of the adversarial items on
the remaining capacities to the overall optimum. Next, in Lemma 3.4, we show that the solution of
this mathematical program is at least 1 − λ. Lemma 3.12 is an immediate result of combining these
two lemmas.
We now show that there exists an optimum allocation of all items such that the contribution of
stochastic items in this allocation is exactly Opt(S). We will need this for Lemma 3.3.
Lemma 3.2. For any disjoint sets of items A and S, there exist an optimum allocation of S ∪ A such
that the contribution of items of S in this allocation is exactly Opt(S).
Proof. We prove this lemma by contradiction. Assume that in all optimum allocations of S ∪ A,
the contribution of items of S is less than Opt(S). Consider an optimum allocation Opt ′(S ∪ A)
of S ∪ A such that the items of S have the maximum contribution to the allocation. Denote the
allocation of items of S in Opt ′(S ∪ A) by A′(S). By definition, A′(S) is not an optimum allocation of
S. Thus, there exists an augmenting path in A′(S) which can increase the number of assigned items
to one of the agents by exactly one, and keep the number of assigned items to all other agents the
, Vol. 1, No. 1, Article 1. Publication date: November 2017.

1:12

Hossein Esfandiari, Nitish Korula, and Vahab Mirrokni

same. This change increases the number of assigned items in A′(S) by one, and may decrease the
number of assigned items from A by at most one. Therefore, it is an optimal solution of S ∪ A in
which items from S have more contribution, and hence gives a contradiction.
□
Lemma 3.3. The optimum allocation of the adversarial items on the remaining capacities is at least
Opt(S ∪ A) − Opt(S) times the solution of Mathematical Program 2.
Proof. Let x j be the fraction of the capacity of the agent j which is filled by AlgS . Without
loss of generality, assume that x j s are in increasing order. That is, for all 1 ≤ j ≤ n − 1, we have
x j ≤ x j+1 , which is the third constraint in Mathematical Program 2.
Consider the optimum solution of S ∪ A from Lemma 3.2. Let y j be the fraction of the capacity
of the agent j that is filled by the adversarial items in this solution. One can see that the fourth
constraint says that the contribution of the stochastic items is at most λ fraction of the total value.
(From Lemma 3.2, we could have equality in the fourth constraint, but for simplicity of analysis,
we maintain the inequality.)
Note that we want to compare the optimum solution of the adversarial items on the remaining
Í
capacities 1 − x j with the total value nj=1 y j of the adversarial items in the optimum solution of
S ∪A. For some agent j, if we have y j +x j ≤ 1, we can assign the same adversarial items to the agent
j as in the optimum allocation. On the other hand, if y j + x j ≥ 1, we can only use 1 − x j fraction of
the capacity of agent j for the adversarial items. Thus, we can always assign y j − max(0, x j + y j − 1)
fraction of the capacity of agent i to the adversarial items. This quantity is denoted by z j in the
first constraint.
By assigning adversarial items as in the optimum solution of S ∪A using the remaining capacities,
Í
we can obtain at least nj=1 y j − z j . The objective function of Mathematical Program 2 compares
this to what the optimum solution of S ∪ A can get from adversarial items.
Finally, fix an index j such that x j < x j+1 and look at all agents with index greater than j. All
stochastic items that we match to agents with index greater than j have no edge to the agents with
index less than or equal to j. (By definition of AlgS , which assigns items to the eligible agent with
Í
lowest value of x j .) Thus, in any optimum solution of S, they cover at least nk=j+1 x k of the agents
Ín
with index greater than j. Thus, this optimum solution of S ∪ A covers k=j+1 (x k +yk ) of the agents
Í
with index greater than j. Consider that we have n − j such agents, we get nk =j+1 (x k + yk ) ≤ n − j.
This is the second constraint in Mathematical program 2.
□
Lemma 3.4. For any small number δ , the solution of the mathematical program 2 is at least
1 − λ − O(δ ).
Proof. First, we show that given any solution to the Mathematical Program 2, we can construct
a related solution with a very restricted structure that only increases the objective function by O(δ ).
We will lower bound the objective value of this new solution, which will imply a lower bound on
the original competitive ratio.
Our restricted solution will satisfy Properties 3.5, 3.7, 3.8, 3.9 ,3.10, and 3.11, which we state
below. Finally, we use these properties to bound the value of the objective function by 1 − λ. This
means that the solution of MP 2 is bounded by 1 − λ − O(δ ).
Property 3.5. Without loss of generality we can assume that for any positive number δ , we have,
≤ δ.
yj

Ín 1

j=1

To prove this property given an instance of the Mathematical program 2, we provide another instance that satisfy this property and has a solution equal to the optimum solution of
the initial instance. Consider a solution Sol n =< (x 1 , . . . , x n ), (y1 , . . . , yn ), (z 1 , . . . , zn ) >, to
, Vol. 1, No. 1, Article 1. Publication date: November 2017.

Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models

1:13

the MP 2 with n agents. For any integer C, one can construct an equivalent feasible solution,
′ ), (y ′ , . . . , y ′ ), (z ′ , . . . , z ′ ) > to an extended Mathematical Program equivSol Cn =< (x 1′ , . . . , xCn
1
1
Cn
Cn
alent to 2 with Cn agents as follow. For all 1 ≤ j ≤ n and all 1 ≤ k ≤ C, set
′
′
′
xC(j−1)+k
= x j , yC(j−1)+k
= y j , zC(j−1)+k
= zj .

One can easily check that if Sol n is feasible, Sol Cn is feasible as well. The value of the objective
functions in both Sol n and Sol Cn are the same. Thus, if we bound the value of the objective function
in Sol Cn , this bound holds for Sol n as well. Moreover, since we have C copies of each variable here,
Í
Ín
′
Í1
we have Cn
j=1 y j = C j=1 y j . Hence, if we set C = δ nj=1 y j , it satisfies Property 3.5. In the rest of
the proof, we assume that the solution that we are considering has Property 3.5, and for simplicity
we refer to it as a solution with n agents and variables x j s, y j s and z j s.
Note that Property 3.5 means that if we decrease the value of a constant number of z j s to 0, we
only increase the objective value by O(δ ). We later use this to provide Property 3.7.
Definition 3.6. We say an agent j is harmful if we have z j > 0. Otherwise, we say the agent is a
sink.
If an agent j is harmful, z j is positive and thus it contributes to reducing the objective value
below 1.
Property 3.7. All y j s are either 0 or 1.
Let j be the largest index such that the agent j is harmful and y j is neither 1 nor 0. If this is not
the only harmful agent with this property, there is some other index k such that agent k is harmful
and yk is neither 1 nor 0. We decrease the value of y j and z j by some ε and increase y j and zk by ε.
This change has no effect on the objective function, or the third and fourth constraints. It increases
both sides of the first constraint by ε for agent k and decreases both sides by ε for agent j, keeping
them both feasible. One can verify that this change may only decrease the left hand side of the
second constraint for indices between k and j.
We can repeat this procedure until there is just one harmful agent j with a fractional y j . We
decrease y j and z j of this agent to 0, and by property 3.5, only increase the objective value by O(δ ).
Note that harmful agents with y j = 0 now become sink agents.
We can use the same procedure to make the y j s of all sink agents either 0 or 1.
Property 3.8. If agent j is harmful, z j = x j .
For each harmful agent j, the value of z j can be as much as x j (since y j for a harmful agent is
now 1). Increasing z j s of harmful agents up to their x j s may only decrease the objective function,
and keeps all the constraints feasible.
From now on, for each harmful agent j, we keep x j and z j the same, and if we change one of
these two, we change the other one as well. This implicit change of z j keeps the constraints feasible.
However, each time we decrease x j of a harmful agent, we need to guarantee that the objective
function does not increase. This guarantee is trivial when we are increasing the value of some other
x k to match.
Property 3.9. If an agent j > 1 is a sink, we have x j−1 = x j .
Let j and h be two consecutive harmful agents with j < h. For all agents k in the range [j, h)
Íh−1

xk

=j
we replace the value of x k with the average value of xs in this range i.e. we set x k = kh−j
. This
keeps the sum of all x k s the same, and keeps all of the constraints feasible. Moreover, since x j has
the minimum value in the range [j, h), and agent j is the only harmful agent in this range, we are
only increasing the x valuess of harmful agents. This only decreases the objective function.

, Vol. 1, No. 1, Article 1. Publication date: November 2017.

1:14

Hossein Esfandiari, Nitish Korula, and Vahab Mirrokni

Let k be the number of different x j values that we have, and let α h be the h-th smallest value
among distinct x j s. For simplicity, we assume we always have some x j = 0. Let βh be the number
of x j s which are at most α h , and set β 0 = 0. Thus, βh−1 ≤ j < βh means that x j = α h .
Property 3.10. For any 1 ≤ h ≤ k, all harmful agents in the range (β −h1 , βh], are the first agents
in the range.
Let i be a sink and let i + 1 be a harmful agent, such that x i = x i+1 . We can replace the value of
the variables for these two agents and make i harmful, instead of i + 1. It is easy to see that this
keeps the mathematical program feasible. By repeating this, for each range (β j−1 , βj], we can move
all harmful agents to be the first agents in the range.
Property 3.11. All x j s are either 0 or the same fixed number x ∗ .
We iteratively decrease the number of distinct x j s as follow.
Let ξ be some small number that we set later. It is easy to see that one of the following two
actions decreases the objective function, since the effect of one on the objective function is the
negative of the effect of the other one. The action that decreases the objective function is the one
that we do.
ξ
ξ
• For all β 1 < j ≤ β 2 decrease x j by β2 −β1 and for all β 2 < ℓ ≤ β 3 increase x ℓ by β3 −β2
• For all β 1 < j ≤ β 2 increase x j by

ξ
β 2 −β 1

and for all β 2 < ℓ ≤ β 3 decrease x ℓ by

ξ
β 3 −β 2

We can set ξ , such that the mathematical program remains feasible and one of the following
situations happen.
• x j s in the range (β 1 , β 2 ] are all 0.
• x j s in the range (β 2 , β 3 ] are all x β3 +1 .
• The second constraint of the MP is tight for j = β 2 .
In the first two cases, the number of distinct x i s is reduced by one and we are done in these cases.
Therefore, we assume that we are in the third case. Now suppose that k > 3 (that is, there are
more than 3 distinct values of x j ); later, we consider the case that k = 3. Let ξ ′ be some small number
ξ′
that we set later. For all β 2 < j ≤ βk −1 we increase x j by βk −1 −β2 and for all βk −1 < ℓ ≤ βk we
ξ′

decrease x ℓ by βk −βk −1 . Below, we show that by doing so, the objective function does not increase.
We can set ξ ′ to make the largest and second largest value of x j s become equal. This decreases the
number of distinct values of x i s.
The second constraint in MP 2 for j = βk −1 says that the fraction of harmful agents in the
range (βk −1 , βk ] is at most 1 − x n . This constraint is tight for j = β 2 . Thus, the fraction of harmful
agents in the range (β 2 , βk ] is at least 1 − x n , which means the fraction of harmful agents in the
range (β 2 , βk −1 ] is at least 1 − x n . Thus, taking some fraction of x ℓ s in the range (βk −1 , βk ] and
distributing it equally over the range (β 2 , βk −1 ] increases the sum of z j s and thus decreases the
objective function.
In the case that k = 3, we move the harmful agents in the range (β 1 , β 2 ] to some higher indices,
to make the second constraint tight. Then, we can use the above technique and decrease the value
of the only two non zero distinct x j s to become equal.
Now, given the property 3.11 we can easily bound the objective function of the mathematical
program as follow. If x ∗ ≤ λ, all z j s are at most λ, while y j s are all 1. This bounds the objective
function by 1−λ. On the other hand, if x ∗ > λ, the second constraint in MP 2 says that the number of
harmful agents is at most 1 −x ∗ fraction of the value from the stochastic items. This means that sum
λ
of z j s is at most 1 − x ∗ fraction of value of the stochastic items. Thus, it is at most (1 − x ∗ ) 1−λ
≤λ
and this bounds the objective function by 1 − λ.
□
, Vol. 1, No. 1, Article 1. Publication date: November 2017.

Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models

1:15

The following lemma is an immediate result of combining Lemma 3.3 and Lemma 3.4.
Lemma 3.12. The optimum allocation of adversarial items on the remaining capacities is at least
(1 − λ − O(δ ))(Opt(S ∪ A) − Opt(S)).
3.2

Weighted Robust Budgeted Allocation

We can now describe our algorithm for general weighted case of Budgeted Allocation. As in the
unweighted case, we combine the allocations of two algorithms: One that runs on the (stochastic)
items that we guess are drawn from the forecast, and one on the items that we guess are constructed
by the adversary.
For the stochastic items, we start with a base algorithm for Stochastic Budgeted Allocation that
is not necessarily optimal. Instead of maximizing the weight of the allocation from the stochastic
items, we start with an algorithm Algpot that maximizes the potential of the allocation, as defined
below.
Definition 3.13. Let X = (x 1 , x 2 , . . . , x n ) be a vector of numbers, such that for all 1 ≤ j ≤ n, we
have 0 ≤ x j ≤ 1. We defineÍ
the potential of x j , Pot(x j ) to be x j − e (x j −1) . We define the potential of
the vector X , Pot(X ) to be nj=1 Pot(x j ).
Let x j denote the fraction of capacity c j used by the potential-maximizing allocation of Algpot .
Similarly to the unweighted case, when items arrive, we send them to DeRand(Algpot ); for those
items that are unmatched, by DeRand(Algpot ), we send them to the Balance algorithm using the
remaining capacities 1 − x j . Exactly the same argument that we provide for the unweighted case
works here to show that by losing O(ε) on the competitive ratio, we can assume that we match
all stochastic items using DeRand(Algpot ) and all adversarial items using the Balance algorithm.
We use Alg to denote this combined algorithm. In order to analyze our algorithm Alg, we need to
define another potential function based on Pot(X ).
Definition 3.14. Let X = (x 1 , x 2 , . . . , x n ) and Y = (y1 , y2 , . . . , yn ) be two vectors of numbers
between 0 and 1. For each 1 ≤ j ≤ n, we define Pot X (y j ) as follow. If x j ≤ y j , we have Pot X (y j ) =
Pot(y j ). Otherwise, we have Pot X (y j ) = Pot(x j )+(y j −x j )Pot ′(x j ), where Pot ′(.) is the first derivative
of Pot(.). Thus, for x j < y j we have:
Pot X (y j ) = x j − e x j −1 + (y j − x j )(1 − e x j −1 )
We define Pot X (Y ) to be

Ín

j=1 Pot X (y j ).

Note that the second derivative of Pot(x j ) is −e x j −1 which is always negative. Thus, Pot(x j ) is
a concave function. Notice that in the range [0, x j ], Pot X (y j ) is equal to Pot(y j ) and in the range
(x j , 1], it is the tangent line to Pot(x j ) at x j . Hence, Pot X (y j ) is a concave function as well.
Consider that, in the range (x j , 1], the function Pot X (y j ) is the degree 2 Taylor series of Pot(y j )
at point x j . In addition, the second derivative of Pot(y j ) in the range [0, 1] is lower-bounded by −1,
yielding the following lemma.
Lemma 3.15. For any constant ε and any vector of positive numbers X and any y j such that
0 ≤ y j ≤ x j + ε ≤ 1 we have |Pot X (y j ) − Pot(y j )| ≤ ε 2 .
We now have the tools to analyze Alg via means of a mathematical program: First, in Lemma
3.17, we show that the competitive ratio of our algorithm is lower bounded by the solution of the
Mathematical program 4. Next, in Lemma 3.18, we lower bound the solution of the mathematical
program; this lower bound is shown in Figure 3. Together, these lemmas allow us to prove the
following theorem:
, Vol. 1, No. 1, Article 1. Publication date: November 2017.

1:16

Hossein Esfandiari, Nitish Korula, and Vahab Mirrokni

Fig. 3. Competitive ratio of Alд parametrized by λ.

Ín
Minimize:

j=1 x j

Í
+ (1 − e1 ) nj=1 (y j − z j )
Ín
Ín
j=1 y j + j=1 t j

Subject to: z j ≤ max(0, x j + y j − 1)

∀1 ≤ j ≤ n

(1)
(2)

Pot X (T ) ≤ Pot(X )

(3)

tj + yj ≤ 1
∀1 ≤ j ≤ n
n
n
n
Õ
Õ
Õ
λ( t j +
yj ) =
tj

(4)

j=1

j=1

0 ≤ tj , x j , yj , zj ≤ 1

(5)

j=1

∀1 ≤ j ≤ n

(6)

Fig. 4. Mathematical Program 4 to bound the competitive ratio of Alд.

Theorem 3.16. There exists an algorithm for λ-stochastic weighted budgeted allocation with competitive ratio presented in Figure 3.
Lemma 3.17. The competitive ratio of Alд is bounded by the solution of the Mathematical program
4.
Proof. For each agent j, let x j be the expected fraction of c j used by Algpot on the stochastic
E[Stochastic(Opt )]

λ
items. Consider the optimum assignment Opt λ that maximizes
. For each agent j,
E[Opt λ ]
let t j and y j respectively denote the expected fraction of c j used by stochastic items and adversarial
items in Opt λ . Therefore, the expected fraction of c j used in Opt λ is t j +y j , which is upper-bounded
by 1. This gives us the Inequality 4.
By definition of λ, the contribution of the stochastic items to Opt λ is λ fraction of the total value;
equality 5 captures this fact.
For any agent j, if we have y j ≤ 1 − x j , an offline algorithm can allocate all the same adversarial
items to agent j as Opt λ did by using the remaining 1 − x j fraction of c j . On the other hand, if

, Vol. 1, No. 1, Article 1. Publication date: November 2017.

Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models

1:17

we have y j > 1 − x j , the offline algorithm can use the entire remaining capacitity 1 − x j of agent
j. Thus, an offline algorithm that assigns all the adversarial items using the 1 − x j fraction of
capacities that remain (after allocating the stochastic items according to Algpot ) only loses at most
max(0, x j + y j − 1) from agent j when compared to the allocation of adverarial items by Opt λ . We
denote max(0, x j + y j − 1) by z j , as shown in Inequality 2.
One can see that the numerator of the objective function lower-bounds the expected outcome of
Alд and the denominator is the expected outcome of Opt λ . Thus, the objective function is a lower
bound on the competitive ratio of Alд.,
It remains only to verify inequality 3. By definition of Algpot as an algorithm maximizing potential,
we know that Pot(T ) ≤ Pot(X ). However, this does not imply the inequality directly. We will show
that if the inequality does not hold, we will be able to construct a new allocation with a larger
potential, contradicting the definition of X . Suppose by way of contradiction that there exists some
T , and some positive number δ such that Pot X (T ) − Pot(X ) ≥ δ . For some arbitrary small constant
η, consider the vector ηT + (1 − η)X , which allocates η fraction of each stochastic item according to
T and 1 − η fraction of each stochastic item according to X . By concavity of Pot X (.) we have
Pot X (ηT + (1 − η)X ) ≥ ηPot X (T ) + (1 − η)Pot X (X ) = ηPot X (T ) + (1 − η)Pot(X ).
Together with the assumption that Pot X (T ) − Pot(X ) ≥ δ , this gives Pot X (ηT + (1 − η)X ) ≥
Pot(x) + ηδ . On the other hand, Lemma 3.15 implies that Pot X (ηT + (1 − η)X ) ≤ Pot(x) + nη 2 .
By setting η to be smaller than δn , we obtain a contradiction. Thus, for any solution T we have
Pot X (T ) ≤ Pot(X ) which is the inequality 3.
□
Lemma 3.18. The solution of Mathematical Program 4 is lower-bounded by the curve in Figure 3.
Proof. Again, as in the unweighted case, given any solution to Mathematical program 4, we
find a new solution with a restricted structure that only increases the objective function by O(δ ).
Eventually, we lower bound the objective value of this new solution; this provides a lower bound
on the original competitive ratio.
Our restricted solution will satisfy properties 3.19, 3.20, 3.21 and 3.22 below. Similar to the
unweighted case, we can replace each variable with with O(1/δ ) copies with the same value in
order to satisfy Property 3.19, which implies that if we change a constant number of the y j and / or
t j variables, it changes the objective function by at most O(δ ).
Property 3.19. For any positive number δ , we can create an equivalent solution such that Ín 1 y j ≤ δ
and

Ín1

j =1 t j

≤ δ.

j=1

Again as in the unweighted section, we call an agent j with positive z j a harmful agent. We say
that an agent j is a source if both z j and t j are zero. If an agent is neither harmful nor a source, we
call it a sink.
Property 3.20. All y j s and t j s are either 0 or 1.
To satisfy this property, we add some new extra agents with x . = 0, y . = 0, z . = 0, t . = 0 initially.
(Note that this requires slightly modifying the mathematical program to add constraints for the
new agents, and including them in the summations. However, it is easy to see that this does not
change the objective or feasibility of any constraint.)
Now, for any original agent j with positive y j and such that j is either a sink or a source, we
decrease y j to 0 and increase yk by the same amount for some newly added agent k. It is easy to
see that this does not affect the sum of the y variables (and hence the objective function or the
feasibility of any constraint), and that this can be done so that only a single agent has a fractional
value of y.
, Vol. 1, No. 1, Article 1. Publication date: November 2017.

1:18

Hossein Esfandiari, Nitish Korula, and Vahab Mirrokni

Let Γ be an integer such that the sum of t j s for all sinks is in the range [Γ, Γ + 1). (Note that
sources have t j = 0.) We redistribute the t j values to be 1 on the Γ sources and sinks with the
maximum x j s, leaving at most one sink with fractional t j . Using the concavity of Pot X (T ), this
change only decreases Pot X (T ). Since all sources and sinks now have y j = 0, we still have t j +y j ≤ 1
for each agent j. (Note that some agents may change status from source to sink or vice versa during
this process.)
Now, y j and t j are either 0 or 1 for all except the harmful agents. (Further, y j is 1 only on newly
added agents, and t j is 1 only on sink agents.)
For the harmful agents, let YH and TH denote the sum of their y j and t j values respectively. From
constraint (4), we know that YH +TH is less than the total number of harmful agents. We redistribute
the y j and t j values as follows: Set y j = 1 on the ⌊YH ⌋ harmful agents with the smallest values of x j ,
and 0 otherwise; similarly, set t j = 1 on the ⌊TH ⌋ harmful agents with the largest values of x j , and
0 otherwise. In this process, we lose the fractional y j and t j values of at most one agent, possibly
increasing the competitive ratio by O(δ ). Further, note that this process leaves some of these agents
harmful (those with y j = 1), while the others (all but ⌊YH ⌋ of them) are no longer harmful; ⌊TH ⌋
of them now become sinks. There are two further effects of this move: First, as argued above for
the sinks, by setting t j = 1 on the agents with highest x j , Pot X (T ) only decreases. Second, the
redistribution of y j values affects the z j values. To satisfy constraint (2), we must decrease z j to 0
on each agent which is no longer harmful. However, we can increase the z j values on the the ⌊YH ⌋
agents which are still harmful, and it is easy to see that this only decreases the objective function
(because the increase in these z j values exceeds the decrease on the agents which are no longer
harmful).
Therefore, we satisfy Property 3.20 while increasing the objective by at most O(δ ).
For each harmful vertex i, Inequality (2) says that z j ≤ x j (since y j = 1). Increasing z j to x j only
decreases the objective function. Thus, in the rest of the proof, for any harmful vertex j we assume
z j = x j . Changing x j of a harmful vertex j implicitly affects z j as well.
Property 3.21. All harmful agents have the same x j , denoted by α 1 . All sink agents have the same
x j , denoted by α 2 .
We replace the x j of all harmful agents with their average. By concavity of the potential function,
this
Pot(X ). (Note that all harmful agents j have t j = 0.) It also does not change
Ín does notÍdecrease
n
x
and
z
,
and
thus, keeps all the constraints feasible.
j=1 j
j=1 j
Í
We also replace the x j of sinks with their average. One can rewrite Inequality 3 as nj=1 (Pot X (t j )−
Pot(x j )) ≤ 0. The left term for sink j is Pot(x j ) + (1 − x j )(1 − e x j −1 ) − Pot(x j ) = (1 − x j )(1 − e x j −1 ).
Thus, for each sink, the left term is a convex function. This means that this change does not increase
Í
Í
the left hand side of nj=1 (Pot X (t j ) − Pot(x j )) ≤ 0. This change also does not affect nj=1 x j and
Ín
j=1 z j , and hence keeps all the constraints feasible.
We use β 1 to denote the number of agents j with y j = 1; this includes harmful agents and newly
added agents. We use β 2 and β 3 to denote the number of sinks and sources respectively. We use γ
Í
to denote j x j for sources.
Property 3.22.

i is source Pot(x i )

Í

is bounded by (1 − e1 )γ − e1 β 3

This follows from the fact that Pot(x) is always less than (1 − e1 )x − e1 .
, Vol. 1, No. 1, Article 1. Publication date: November 2017.

Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models

1:19

Now, using Properties 3.20, 3.21 and 3.22, one can show that the objective function is lower
bounded by
(α 1 β 1 + α 2 β 2 + γ ) + (1 − e1 )(1 − α 1 )β 1
.
(7)
β1 + β2
Í
(This is a lower bound because in the numerator, we have ( y j − z j ), which is 1 for the newly
added agents included in β 1 , and (1 − α 1 ) for the harmful agents.)
We can write Equality (5) as
λ(β 1 + β 2 ) = β 2 ,

(8)

and write Inequality (3) as
β 1 (0 − e −1 ) + β 2 (α 2 − e α 2 −1 + (1 − α 2 )(1 − e α 2 −1 )) + β 3 (0 − e −1 ) ≤
1
β 1 (α 1 − e α 1 −1 ) + β 2 (α 2 − e α 2 −1 ) + (1 − )γ + β 3 (0 − e −1 ).
e
One can drop the terms β 2 (α 2 − e α 2 −1 ) and β 3 (0 − e −1 ) from both sides of the inequality, and
rearrange as follows:
e
1
(β 1 (− − α 1 + e α 1 −1 ) + β 2 (1 − α 2 )(1 − e α 2 −1 )) ≤ γ .
e −1
e
We replace γ in the objective function (Equation 7 with the max of zero and left hand side of
the inequality. Then, we replace β 1 with 1−λ
λ β 2 using Equality (8). Now we can cancel out β 2 and
simplify the objective function as follows.
α1
1
(1 − λ) + (1 − λ)(1 − ) + λα 2 +
e
e
e
1
max(0,
((1 − λ)(− − α 1 + e α 1 −1 ) + λ(1 − α 2 )(1 − e α 2 −1 )))
e −1
e
Unfortunately, it is hard to solve this analytically to obtain a closed-form experssion for the
competitive ratio as a function of λ. When λ ≥ 0.6882, we can lower bound the competitive ratio
by the line 0.3714 + 0.4362λ. However, this is not necessarily tight. Numerically solving, the curve
lower bounding the competitive ratio as a function of λ can be seen in Figure 3
□
3.3

Hardness of Robust Budgeted Allocation

Theorem 3.23. No online algorithm for Robust Budgeted Allocation (even in the unweighted case)
has competitive ratio better than 1 − e1−λ
1−λ for λ-stochastic inputs.
Proof. Consider the following instance: We have n agents each with capacity one and n items.
Initially, all of the agents are unmarked. Each item is connected to all agents which are unmarked
upon its arrival. The first λn items are connected to all agents. After the arrival of the first λn items,
we mark the λn agents with minimum expected load. Subsequently, after assigning each item we
mark the agent with the minimum expected load among all unmarked agents.
Note that all of the first λn items are adjacent to all agents, and there is no uncertainty about
them. Thus, one can consider the first λn items as being part of the forecast F = (D, λn), where
the distribution D has a single type (items adjacent to all agents). The last (1 − λ)n vertices as
adversarially chosen items. Let v j denote the jth agent that we mark. An optimum algorithm that
knows the whole graph in advance can match the jth item to the jth agent and obtain a matching
of size n.
Now consider an arbitrary online algorithm. Let ℓij be the expected load of agent v j after assigning
the ith item and let ℓj = ℓnj be its expected load at the end of the algorithm. One can see that
, Vol. 1, No. 1, Article 1. Publication date: November 2017.

1:20

Hossein Esfandiari, Nitish Korula, and Vahab Mirrokni

Ín
Maximize:
Subject to:

j=1 ℓ j

n
λn
Õ
ℓ j ≤ λ 2n
j=1

ℓj ≤

j−

Íj−1

ℓ
k =1 k

n−j+1
0 ≤ ℓj ≤ 1

∀ λn + 1 ≤ j ≤ n
∀1≤j ≤n

Fig. 5. Linear program to bound the competitive ratio of the best online algorithm.

ℓj = ℓjmax(λn, j) . The first λn items put a load of λn on the agents and agents v 1 to v λn are the λn
agents with lowest expected loads. Thus, we have
λn
Õ

ℓj ≤ λ2n.

j=1

In addition, for each λn < j ≤ n, the first j items put a load of at most j on the agents, and the
Í
expected load on the agents v 1 to v j−1 is kj−1
ℓ . Therefore, we can bound the expected load of
=1 k
the jth agent as follows:
Í
j − kj−1
ℓ
=1 k
.
ℓj ≤
n−j+1
Further, the expected load of an agent cannot exceed 1, and the optimum solution is a matching
in which each agent has a load of 1. Therefore, the competitive ratio of any algorithm for Robust
Budgeted Allocation on λ-stochastic inputs is bounded by Linear program 5.
First note that w.l.o.g., we can assume that in any optimal solution to LP 5, each ℓj for 1 ≤ j ≤ λn
has the same value. Consider an optimal solution in which as many constraints as possible are
tight. It is easy to see that if the constraint for ℓj is not tight, we can raise ℓj by ε and decrease ℓk by
at most ε (to maintain feasibility) for the first k > j such that ℓk > 0. By repeating this procedure
iteratively, we make all of the constraints tight. This solution is correspond to the algorithm that
matches items to their eligible agents uniformly. Hence, it allocates all λn stochastic items and at
Íξ n
1
most ξn adversarial items, for some ξ such that i=1 (1−λ)n−(i−1)
≥ 1 − λ. Notice that we have
ξn
Õ
i=1

1
≥
(1 − λ)n − (i − 1)

∫

(1−λ)n

(1−λ−ξ )n

1
1−λ
dx = log((1 − λ)n) − log((1 − λ − ξ )n) = log(
).
x
1 − (λ + ξ )

1−λ
By setting log( 1−(λ+ξ
) ) = 1 − λ and rearranging the parameters we have λ + ξ = 1 −

4

1−λ
.
e 1−λ

□

APPROXIMATING ADVERSARIAL AND STOCHASTIC BUDGETED ALLOCATION

In this section, we study a class of algorithms for Budgeted Allocation problem that provide good
approximation ratios in both stochastic and adversarial settings. We say an algorithm is (α, β)competitive if it is α-competitive in the adversarial setting and β-competitive in the stochastic
setting.
The best algorithms for the stochastic setting have a competitive ratio of 1 − ε when the input
is stochastic. However, these algorithms may have a competitive ratio close to zero when the
, Vol. 1, No. 1, Article 1. Publication date: November 2017.

Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models

1:21

input is adversarial. On the other hand, the Balance algorithm has the best possible competitive
ratio of 1 − e1 when the input is adversarial, but, under some mild assumption, is 0.76-competitive
for stochastic inputs [Mirrokni et al. 2011]. Indeed, this result holds when, 1) the capacities are
Í
w
large i.e. maxi, j ci,j j ≤ ε 3 , and 2) the optimum solution is large i.e. ε −6 j maxi:opt (i)=j w i, j ≤
Opt, where Opt(i) is the agent the optimum matches to node i, and ε is a vanishingly small
w
number. In this section, we refer to maxi, j ci,j j ≤ ε 3 as the large capacities condition, and refer to
 Í

max ε −6 j maxi:opt (i)=j w i, j , ε 1/3m · maxi, j w i, j ≤ Opt as the large optimum condition.
Of course, one can design algorithms with ‘intermediate’ performance: Simply use the stochastic
algorithm with probability p and Balance with probability 1 − p; this yields an algorithm with
competitive ratios of ((1 − p)(1 − e1 ) and (p + (1 − p) × 0.76) − O(ε)) in the adversarial and stochastic
settings respectively. These competitive ratios for different values of p lie on the straight line with
endpoints (1 − e1 , 0.76) and (0, 1 − ε). In this section, we use the tools that we developed in Section 2
to obtain competitive ratios those are ‘above’ this straight line.
We devise a mixed algorithm for this setting as follows: Divide the capacity of each agent /
offline vertex into two parts. The first part has 1 − p fraction of the capacity, and the second part
has the remaining p fraction of the capacity. Given a forecast F = (D, f ), at the beginning, run the
Balance algorithm on 1 − p fraction of the forecast input (that is, on the first (1 − p) · f items, using
the first (1 − p) fraction of the capacities. Then, for any 1 − ε-competitive stochastic algorithm
Alg, run Alg on the rest of the forecast input (that is, the next p f items), using the remaining p
fraction of the capacities. If at any time during the algorithm, we observe that the input sequence
is ε-far from D, or the length of the input is more than f , we can detect that (w.h.p.) we are in
the adversarial setting. We therefore flush out the items we assigned to the second part (the p
fraction) of the capacities, if any, and return to the Balance algorithm. However, we now run two
independent copies of Balance: The first using 1 − p fraction of the capacities (with some items
previously allocated by Balance), and the second using the remaining p fraction of the capacities
(beginning with an empty allocation of items to this part of the capacities). For each item arriving
online, with probability 1 − p we send it to the Balance algorithm on the first part of the capacities,
and with probability p we send it to the Balance algorithm on the second part of the capacities.
In the next two lemmas, we bound the competitive ratios of our mixed algorithm when the input
is stochastic and adversarial respectively.
Lemma 4.1. Assuming the long input, the large capacities and the large optimum conditions, if
the input is stochastic, for any constant p ∈ [0, 1] the mixed algorithm has a competitive ratio of
(1 − p) ∗ β + p − O(ε), where β is 0.76.
Proof. From Theorem 2.11, we know that by ignoring the inputs which are ε-far from the
distribution, we lose only O(ε) fraction in the competitive ratio. We use 1 − p fraction of the input
sequence on the first 1 −p fraction of the capacities. Therefore, the Balance algorithm gets (1 −p) ∗ β
fraction of the optimal solution from this part of the input, where β = 0.76 is the competitive ratio
for Balance on stochastic inputs [Mirrokni et al. 2011]. On the other hand, we use p fraction of the
input on the remaining p fraction of the capacities. Since we use a 1 − ε competitive stochastic
algorithm, we get p − O(ε) fraction of the optimal solution from this part of the input sequence. □
Lemma 4.2. Assuming the long input, the large capacities and the large optimum conditions, if
the input is adversarial, for any constant p ∈ [0, 1] the mixed algorithm has a competitive ratio of
0.76(1−p)
1/3 ).
1+0.202(1−p) − O(ε
Proof. Let S be the maximal prefix of the input before observing that the input is not ε-close
to the distribution and let A be the rest of the input. (Note that either S or A may be empty.) If
, Vol. 1, No. 1, Article 1. Publication date: November 2017.

1:22

Hossein Esfandiari, Nitish Korula, and Vahab Mirrokni

ε
S contains at least ϵ 2/3m nodes, since S is ϵ 2/3
= ϵ 1/3 -close to the distribution and satisfies the
long input condition, we obtain at least β(1 − p − O(ϵ 1/3 ))Opt(S) from this fraction of the input
(Note that if S is smaller than (1 − p) · f , for example, we would obtain a larger fraction of Opt(S).).
On the other hand, if S contains less than ϵ 2/3m nodes, using large optimum condition, we have
Opt(S) ≤ ϵ 2/3m · max i, j w i, j ≤ ϵ 1/3Opt(A ∪ S). Thus, the competitive ratio is lower bounded by

β(1 − p)Opt(S)
β(1 − p)Opt(S)
− O(ϵ 1/3 ) ≥
− O(ϵ 1/3 ).
Opt(S ∪ A)
Opt(S) + Opt(A)
On the other hand, if we ignore ϵm nodes, the Balance algorithm on the first 1 − p fraction of
the capacities always runs on at least 1 − p fraction of the items, we always get at least (1 − e1 )(1 −
p − O(ϵ 2/3 ))Opt(S ∪ A) from this fraction of the capacities. Further, once the input stops being
ε-close to the distribution (that is, for the entire sequence A), we use the remaining p fraction of the
capacities on p fraction of A. Therefore, we always get at least (1 − e1 )pOpt(A) from this p fraction
of the capacities. Thus, the competitive ratio is lower bounded by
(1 − e1 )(1 − p − O(ϵ 2/3 ))Opt(S ∪ A) + (1 − e1 )pOpt(A)
=
Opt(S ∪ A)


(1 − e1 )pOpt(A)
1
1−
(1 − p) +
− O(ϵ 2/3 ) ≥
e
Opt(S ∪ A)


(1 − e1 )pOpt(A)
1
(1 − p) +
− O(ϵ 2/3 )
1−
e
Opt(S) + Opt(A)
where the inequality follows from the subadditivity of Budgeted Allocation.
The first of these lower bounds is decreasing in Opt(A), while the second lower bound is increasing
in Opt(A). Thus, the worst case happen when these two bounds are equal. By setting the two equal
and β = 0.76, one can achieve the desired bound.
□
The following theorem is the immediate result of combining Lemmas 4.1 and 4.2.
Theorem 4.3. Assuming the long input, the large capacities and the large optimum conditions, for
any constant p ∈ [0, 1] the mixed algorithm is (1 − p) ∗ 0.76 + p − O(ε) competitive for stochastic input
0.76(1−p)
and 1+0.202(1−p) − O(ε 1/3 ) competitive for adversarial input.
REFERENCES
Shipra Agrawal, Zizhuo Wang, and Yinyu Ye. 2009. A Dynamic Near-Optimal Algorithm for Online Linear Programming.
Computing Research Repository (2009).
Saeed Alaei, MohammadTaghi Hajiaghayi, and Vahid Liaghat. 2012. Online prophet-inequality matching with applications
to ad allocation. In Proceedings of the 13th ACM Conference on Electronic Commerce. ACM, 18–35.
David Applegate and Edith Cohen. 2006. Making routing robust to changing traffic demands: algorithms and evaluation.
IEEE/ACM Transactions on Networking (TON) 14, 6 (2006), 1193–1206.
Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, and Harald Racke. 2003. Optimal oblivious routing in polynomial time.
In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing. ACM, 383–388.
Bahman Bahmani and Michael Kapralov. 2010. Improved bounds for online stochastic matching. In European Symposium on
Algorithms. Springer, 170–181.
Aharon Ben-Tal and Arkadi Nemirovski. 2002. Robust optimization–methodology and applications. Mathematical Programming 92, 3 (2002), 453–480.
Dimitris Bertsimas, Dessislava Pachamanova, and Melvyn Sim. 2004. Robust linear optimization under general norms.
Operations Research Letters 32, 6 (2004), 510–516.
Niv Buchbinder, Kamal Jain, and Joseph Seffi Naor. 2007. Online primal-dual algorithms for maximizing ad-auctions revenue.
In ESA. Springer, 253–264.
Nikhil Devanur and Thomas Hayes. 2009. The Adwords Problem: Online Keyword Matching with Budgeted Bidders under
Random Permutations. In EC. 71–78.
, Vol. 1, No. 1, Article 1. Publication date: November 2017.

Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models

1:23

Nikhil R. Devanur, Kamal Jain, Balasubramanian Sivan, and Christopher A. Wilkens. 2011. Near optimal online algorithms
and fast approximation algorithms for resource allocation problems. In EC. ACM, 29–38.
Nikhil R Devanur, Balasubramanian Sivan, and Yossi Azar. 2012. Asymptotically optimal algorithm for stochastic adwords.
In Proceedings of the 13th ACM Conference on Electronic Commerce. ACM, 388–404.
Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S. Mirrokni, and Cliff Stein. 2010. Online stochastic packing applied
to display ad allocation. In ESA. Springer, 182–194.
J. Feldman, N. Korula, V. Mirrokni, S. Muthukrishnan, and M. Pal. 2009a. Online Ad Assignment with Free Disposal. In
WINE.
Jon Feldman, Aranyak Mehta, Vahab Mirrokni, and S. Muthukrishnan. 2009b. Online Stochastic Matching: Beating 1 - 1/e.
In FOCS. 117–126.
B. Haeupler, V. Mirrokni, and M. ZadiMoghaddam. 2011. Online Stochastic Weighted Matching: Improved Approximation
Algorithms. In WINE. 170–181.
Patrick Jaillet and Xin Lu. 2013. Online stochastic matching: New algorithms with better bounds. Mathematics of Operations
Research 39, 3 (2013), 624–646.
Bala Kalyanasundaram and Kirk R. Pruhs. 2000. An optimal deterministic algorithm for online b -matching. Theoretical
Computer Science 233, 1–2 (2000), 319–325. citeseer.ist.psu.edu/8238.html
Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi. 2011. Online Bipartite Matching with Unknown Distributions. In
STOC. 587–596.
R.M. Karp, U.V. Vazirani, and V.V. Vazirani. 1990. An optimal algorithm for online bipartite matching. In STOC. 352–358.
Mohammad Mahdian, Hamid Nazerzadeh, and Amin Saberi. 2007. Allocating online advertisement space with unreliable
estimates. In Proceedings of the 8th ACM conference on Electronic commerce. ACM, 288–294.
Mohammad Mahdian and Qiqi Yan. 2011. Online Bipartite Matching with Random Arrivals: A Strongly Factor Revealing LP
Approach. In STOC. 597–606.
Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. 2007. AdWords and generalized online matching. J. ACM
54, 5 (2007), 22. https://doi.org/10.1145/1284320.1284321
Vahideh H. Menshadi, Shayan Oveis Gharan, and A. Saberi. 2011. Online Stochastic Matching: Online Actions Based on
Offline Statistics. In SODA. 1285–1294.
Vahab S. Mirrokni, Shayan Oveis Gharan, and Morteza ZadiMoghaddam. 2011. Simultaneous Approximations of Stochastic
and Adversarial Budgeted Allocation Problems. In SODA. 1690–1701.
Bo Tan and R Srikant. 2011. Online advertisement, optimization and stochastic networks. In CDC-ECC. IEEE, 4504–4509.
Erik Vee, Sergei Vassilvitskii, and Jayavel Shanmugasundaram. 2010. Optimal Online Assignment with Forecasts. In EC.
109–118.
Hao Wang, Haiyong Xie, Lili Qiu, Yang Richard Yang, Yin Zhang, and Albert Greenberg. 2006. COPE: traffic engineering in
dynamic networks. ACM SIGCOMM 36, 4 (2006), 99–110.

, Vol. 1, No. 1, Article 1. Publication date: November 2017.

