Polymatroid Prophet Inequalities

Prophet inequalities bound the reward of an online algorithm—or gambler—relative to the optimum offline algorithm—the prophet—in settings that involve making selections from a sequence of elements whose order is chosen adversarially but whose weights are random. The goal is to maximize total weight.

We consider the problem of choosing quantities of each element subject to polymatroid constraints when the weights are arbitrary concave functions. We present an online algorithm for this problem that does at least half as well as the optimum offline algorithm. This is best possible, as even in the case where a single number has to be picked no online algorithm can do better.

An important application of our result is in algorithmic mechanism design, where it leads to novel, truthful mechanisms that, under a monotone hazard rate (MHR) assumption on the conditional distributions of marginal weights, achieve a constant-factor approximation to the optimal revenue for this multi-parameter setting. Problems to which this result applies arise, for example, in the context of Video-on-Demand, Sponsored Search, or Bandwidth Markets.