Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs
Authors:
- Paul DüttingPDPaul Dütting
- Michal FeldmanMFMichal Feldman
- Thomas KesselheimTKThomas Kesselheim
- Brendan LucierBLBrendan Lucier
Top Cited Papers
- 1 January 2020
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 49 (3) , 540-582
Abstract
We present a general framework for stochastic online maximization problems with combinatorial feasibility constraints. The framework establishes prophet inequalities by constructing price-based onl...Keywords
All Related Versions
Funding Information
- Deutsche Forschungsgemeinschaft
- FP7 Ideas: European Research Council (337122)
- Israel Science Foundation (317/17)
This publication has 43 references indexed in Scilit:
- Bayesian Combinatorial AuctionsJournal of the ACM, 2016
- Intrinsic Robustness of the Price of AnarchyJournal of the ACM, 2015
- Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many BuyersSIAM Journal on Computing, 2014
- The Online Stochastic Generalized Assignment Problem2013
- Submodular Maximization over Multiple Matroids via Generalized Exchange PropertiesMathematics of Operations Research, 2010
- Two Randomized Mechanisms for Combinatorial Auctions2007
- Combinatorial auctions with decreasing marginal utilitiesGames and Economic Behavior, 2006
- Comparison of Threshold Stop Rules and Maximum for Independent Nonnegative Random VariablesThe Annals of Probability, 1984
- Semiamarts and finite valuesBulletin of the American Mathematical Society, 1977
- Fast Approximation Algorithms for the Knapsack and Sum of Subset ProblemsJournal of the ACM, 1975