In the classical version of the prophet inequality problem, a decision maker (“player”) faces a sequence of random rewards presented online. The player can either accept or reject each reward as it is presented. Rejecting a reward results in its permanent loss, while accepting a reward immediately ends the game. The game continues until the player decides to accept a reward. The player’s expected reward is compared to the expected reward of a “prophet” who sees the entire sequence in advance and can simply choose the best reward. A prophet inequality states that the player can achieve a certain fraction of the prophet’s expected reward, in the worst case, over a class of reward distributions. This problem and its generalizations have grown in popularity in the last decade due to their relevance in various applications, such as ad auctions, pricing, and ridesharing services. This has led to new perspectives, and the primary questions have evolved towards understanding the computational and informational aspects of prophet inequalities.
This course offers a comprehensive introduction to the mathematical and algorithmic theory of prophet inequalities and their applications. We will explore advanced techniques and their applications in auctions, pricing, and ridesharing platforms.
Lecture 1
• Overview of the classical prophet inequality problem.
• Origins and applications of the problem in combinatorial optimization and economics.
• Relationship with other classical online selection/stopping problems
• Formal introduction to the basic single-choice model with independent distributions.
• Analysis of the optimal online policy.
• Proof of the prophet inequality.
• Economic interpretation in terms of utility and prices.
Lecture 2
• Related single-selection models
• Prophet inequalities with samples
• Variants of the basic prophet inequality problem.
• i.i.d. models and the power of single and multiple threshold algorithms.
• Introduction to the prophet secretary model and the free-order model.
Lecture 3
• The prophet inequality in combinatorial environments
• Extension of the classical model to selecting up to k rewards.
• Matching problem in graphs with arriving edges.
• Extension to hypergraph matching.
• Fixed-point techniques.
Lecture 4
• Prophet Inequality for Matching with vertex arrivals
• Online contention resolution schemes.
• Introduction to combinatorial auctions with complementary valuations.
• Online combinatorial auctions with sets of bounded size
• Online combinatorial auctions with XOS valuations
• Online combinatorial auctions with subadditive valuations
Some References
• S. Alaei. Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers. Proceedings FOCS 2011, 512-521, 2011. (Also in SICOMP 2014.)
• P. Azar, R. Kleinberg, S. M. Weinberg. Prophet Inequalities with Limited Information. Proceedings SODA 2014, 1358-1377, 2014.
• C. Caramanis, P. Dütting, M. Faw, D. Fusco, P. Lazos, S. Leonardi, O. Papadigenopoulos, E. Pountourakis, R. Reiffenhäuser. Single-Sample Prophet Inequalities via Greedy-Ordered Selection. Proceedings SODA 2022, 1298-1325, 2022.
• S. Chawla, J. Hartline, D. L. Malec, B. Sivan. Multi-Parameter Mechanism Design and Sequential Posted Pricing. Proceedings STOC 2010, 311-320, 2010.
• J. Correa, P. Dütting, F. A. Fischer, K. Schewior. Prophet Inequalities for I.I.D. Random Variables from an Unknown Distribution. Proceedings EC 2019, 3-17, 2019. (Also in MOR 2022.)
• J. Correa, A. Cristi. A Constant Factor Prophet Inequality for Online Combinatorial Auctions. Working paper.
• J. Correa, A. Cristi, A. Fielbaum, T. Pollner, S. M. Weinberg. Optimal Item Pricing in Online Combinatorial Auctions. Proceedings IPCO 2022, 126-139, 2022.
• J. Correa, R. Saona, B. Ziliotto. Prophet Secretary through Blind Strategies. Proceedings SODA 2019, 1946-1961, 2019. (Also in Mathematical Programming 2021.)
• J. Correa, A. Cristi, B. Epstein, J. A. Soto. The Two-Sided Game of Googol and Sample-Based Prophet Inequalities. Proceedings SODA 2020, 2066-2081, 2020.
• P. Dütting, M. Feldman, T. Kesselheim, B. Lucier. Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-stochastic Inputs. Proceedings FOCS 2017, 540-551, 2017. (Also in SICOMP 2020.)
• P. Dütting, T. Kesselheim, B. Lucier. An O(log logm) Prophet Inequality for Subadditive Combinatorial Auctions. Proceedings FOCS 2020, 306-317, 2020.
• H. Esfandiari, M. Hajiaghayi, V. Liaghat, M. Monemizadeh. Prophet Secretary. Proceedings ESA 2015, 496-508, 2015. (Also in SIAM Journal on Discrete Mathematics 2017.)
• T. Ezra, M. Feldman, N. Gravin, Z.G. Tang. Online Stochastic Max-Weight Matching: Prophet Inequality for Vertex and Edge Arrival Models. Proceedings EC 2020, 769-787, 2020. (Also in MOR 2022.)
• M. Feldman, N. Gravin, B. Lucier. Combinatorial Auctions via Posted Prices. Proceedings SODA 2015, 123-135, 2015.
• M. Feldman, O. Svensson, R. Zenklusen. Online Contention Resolution Schemes with Applications to Bayesian Selection Problems. Proceedings SODA 2016, 1014-1033, 2016. (Also in SICOMP 2021.)
• T. S. Ferguson. Who Solved the Secretary Problem? Statistical Science, 4(3):282-289, 1989.
• M. Hajiaghayi, R. D. Kleinberg, T. Sandholm. Automated Online Mechanism Design and Prophet Inequalities. Proceedings AAAI 2007, 58-65, 2007.
• H. Kaplan, D. Naori, D. Raz. Online Weighted Matching with a Sample. Proceedings SODA 2022, 1247-1272, 2022.
• R. Kleinberg, S. M. Weinberg. Matroid Prophet Inequalities. Proceedings STOC 2012, 123-136, 2012. (Also in GEB 2019.)
• U. Krengel, L. Sucheston. How to Bet Against a Prophet. Notices of the American Mathematical Society, 24.1(175), 245 (A-159), 1976.
• U. Krengel, L. Sucheston. On Semiamarts, Amarts, and Processes with Finite Value. Advances in Probability and Related Topics, 4:197–266, 1978.
• U. Krengel, L. Sucheston. Semiamarts and Finite Values. Bulletin of the American Mathematical Society, 83(4):745-847, 1977.
• B. Lucier. An Economic View of Prophet Inequalities. SIGecom Exchanges, 16(1):24-47, 2017.
• B. Peng, Z. G. Tang. Order Selection Prophet Inequality: From Threshold Optimization to Arrival Time Design. Proceedings FOCS 2022, to appear.
• A. Rubinstein, J. Z. Wang, S. M. Weinberg. Optimal Single-Choice Prophet Inequalities from Samples. Proceedings ITCS 2020, 60:1-60:10, 2020.
• E. Samuel-Cahn. Comparison of Threshold Stop Rules and Maximum for Independent Non-Negative Random Variables. Annals of Probability, 12(4):1213-1216, 1984.