The benefit of adaptivity in the stochastic knapsack problem with dependence on the state of nature

in which item values are deterministic and item sizes are random
variables with known, arbitrary distributions. These distributions
depend on a common random variable \theta denoting the state of the
nature. We assume that if we fix a
value of \theta, then the size variables are independent. So \theta
induces a limited dependency among the sizes of different items.

Items are placed in the knapsack sequentially, and the act of placing
an item in the knapsack instantiates its size. The goal is to compute
a policy that maximizes the expected value of items successfully
placed in the knapsack, where the final overflowing item contributes
no value. We consider both nonadaptive policies (that designate a
priori a fixed permutation of items to insert) and adaptive policies
(that can make dynamic decisions based on the instantiated sizes of
items placed in the knapsack thus far).

Our work characterizes the benefit of adaptivity. For this purpose we
use a measure called the adaptivity gap: the supremum over instances
of the ratio between the expected value obtained by an optimal
adaptive policy and the expected value obtained by an optimal
non-adaptive policy. We study this measure as a function of the
cardinality of the support of \theta. Assuming that the support of
\theta has at most k values, we show a lower bound of
\Omega(k) and an upper bound of O(k) on the adaptivity gap in our
model. We also introduce an \Omega(\ln{k}) lower bound and O(\ln{k})
upper bound for the case, where the following two additional
assumptions hold. The first assumption is stochastic monotonicity of
the sizes in terms of \theta and the second is that the prior is
uniform. We show that both of assumptions are necessary, i.e. one
assumption without the other does not bring us to sub-linear
adaptivity gap.

Based on a joint work with Aleksander Vainer.