  Prophet inequalities compare the expected performance of an online algorithm
for a stochastic optimization problem to the expected optimal solution in
hindsight. They are a major alternative to classic worst-case competitive
analysis, of particular importance in the design and analysis of simple
(posted-price) incentive compatible mechanisms with provable approximation
guarantees.
  A central open problem in this area concerns subadditive combinatorial
auctions. Here $n$ agents with subadditive valuation functions compete for the
assignment of $m$ items. The goal is to find an allocation of the items that
maximizes the total value of the assignment. The question is whether there
exists a prophet inequality for this problem that significantly beats the best
known approximation factor of $O(\log m)$.
  We make major progress on this question by providing an $O(\log \log m)$
prophet inequality. Our proof goes through a novel primal-dual approach. It is
also constructive, resulting in an online policy that takes the form of static
and anonymous item prices that can be computed in polynomial time given
appropriate query access to the valuations. As an application of our approach,
we construct a simple and incentive compatible mechanism based on posted prices
that achieves an $O(\log \log m)$ approximation to the optimal revenue for
subadditive valuations under an item-independence assumption.
