Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs

Authors:
  • PDPaul Dütting
    Paul Dütting
  • MFMichal Feldman
    Michal Feldman
  • TKThomas Kesselheim
    Thomas Kesselheim
  • BLBrendan Lucier
    Brendan Lucier

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...
Funding Information
  • Deutsche Forschungsgemeinschaft
  • FP7 Ideas: European Research Council (337122)
  • Israel Science Foundation (317/17)

This publication has 43 references indexed in Scilit: