Data-Driven Decision Processes - Whiteboard Talk

Title: Prophet Inequalities via Balanced Prices

Abstract: The prophet inequality [Krengel, Sucheston, Garling, 1978] is a famous result from optimal stopping theory. One is presented a random sequence of rewards. Whenever a reward is revealed, one can choose to pick it and stop the sequence or to irrevocably discard this reward and continue. For this problem, already very simple policies guarantee a 1/2 fraction of the expected maximum reward (in hindsight).

The first half of the talk is meant to be a slow-paced introduction, in which we will prove and discuss this basic result. Further, we show how it generalizes to online edge-weighted bipartite matching with vertex arrivals via the technique of balanced prices.

In the second half, we will see that these techniques extend to more advanced settings namely combinatorial auctions in which buyers arrive over time [Feldman, Gravin, Lucier, SODA 2015] and to matroid feasibility constraints [Kleinberg, Weinberg, STOC 2012]. We will also discuss how recent work goes beyond the technique of balanced prices, in particular for combinatorial auctions with subadditive buyers [Dütting, Kesselheim, Lucier, FOCS 2020].