  For online resource allocation problems, we propose a new demand arrival
model where the sequence of arrivals contains both an adversarial component and
a stochastic one. Our model requires no demand forecasting; however, due to the
presence of the stochastic component, we can partially predict future demand as
the sequence of arrivals unfolds. Under the proposed model, we study the
problem of the online allocation of a single resource to two types of
customers, and design online algorithms that outperform existing ones. Our
algorithms are adjustable to the relative size of the stochastic component, and
our analysis reveals that as the portion of the stochastic component grows, the
loss due to making online decisions decreases. This highlights the value of
(even partial) predictability in online resource allocation. We impose no
conditions on how the resource capacity scales with the maximum number of
customers. However, we show that using an adaptive algorithm---which makes
online decisions based on observed data---is particularly beneficial when
capacity scales linearly with the number of customers. Our work serves as a
first step in bridging the long-standing gap between the two well-studied
approaches to the design and analysis of online algorithms based on (1)
adversarial models and (2) stochastic ones. Using novel algorithm design, we
demonstrate that even if the arrival sequence contains an adversarial
component, we can take advantage of the limited information that the data
reveals to improve allocation decisions. We also study the classical secretary
problem under our proposed arrival model, and we show that randomizing over
multiple stopping rules may increase the probability of success.
