Recent Developments in Prophet Inequalities

José Correa*, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, Tjark Vredeveld

*Corresponding author for this work

Research output: Contribution to journalArticleProfessional

Abstract

The classic prophet inequality states that, when faced with a finite sequence of non-negative independent random variables, a gambler who knows their distribution and is allowed to stop the sequence at any time, can obtain, in expectation, at least half as much reward as a prophet who knows the values of each random variable and can choose the largest one. Following this classic theorem from the 70s, many results have been obtained for several related optimal stopping problems. Moreover, the recently uncovered connection between prophet inequalities and posted price mechanisms, has given the area a new surge. We survey some new developments and highlight some compelling open problems.
Original languageEnglish
Pages (from-to)61-70
Number of pages10
JournalSI Gecom exchanges
Volume17
Issue number1
DOIs
Publication statusPublished - Nov 2018
Externally publishedYes

Keywords

  • Algorithms Design
  • Optimal stopping
  • Economics
  • Prophet inequalities
  • Mechanism Design
  • Posted Price Mechanisms

Fingerprint Dive into the research topics of 'Recent Developments in Prophet Inequalities'. Together they form a unique fingerprint.

  • Cite this

    Correa, J., Foncea, P., Hoeksma, R., Oosterwijk, T., & Vredeveld, T. (2018). Recent Developments in Prophet Inequalities. SI Gecom exchanges, 17(1), 61-70. https://doi.org/10.1145/3331033.3331039