Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Recent developments in prophet inequalities

Recent developments in prophet inequalities 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. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM SIGecom Exchanges Association for Computing Machinery

Recent developments in prophet inequalities

Download PDF
10 pages

Loading next page...
 
/lp/association-for-computing-machinery/recent-developments-in-prophet-inequalities-m0L0Xqocis
Publisher
Association for Computing Machinery
Copyright
Copyright © 2019 Authors
ISSN
1551-9031
eISSN
1551-9031
DOI
10.1145/3331033.3331039
Publisher site
See Article on Publisher Site

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.

Journal

ACM SIGecom Exchanges – Association for Computing Machinery

Published: May 7, 2019

References

  • Beating 1-1/e for ordered prophets
    Abolhassani, ; M., ; Ehsani, ; S., ; Esfandiari, ; H., ; Hajiaghayi, ; M., ; Kleinberg, ; R., ; Lucier, ; B.,
  • Prophet inequalities for i
    Allaart, ; C., P.
  • Prior independent mechanisms via prophet inequalities with limited information
    Azar, ; D., P.; Kleinberg, ; R., ; Weinberg, ; M., S.
  • Prophet secretary: Surpassing the 1-1/e barrier
    Azar, ; Y., ; Chiplunkar, ; A., ; Kaplan, ; H.,
  • Improved approximations for free-order prophets and second-price auctions
    Beyhaghi, ; H., ; Golrezaei, ; N., ; Leme, ; P., R.; Pal, ; M., ; Sivan, ; B.,
  • Multi-parameter mechanism design and sequential posted pricing
    Chawla, ; S., ; Hartline, ; J., ; Malec, ; D., ; Sivan, ; B.,
  • Posted price mechanisms for a random stream of customers
    Correa, ; J., ; Foncea, ; P., ; Hoeksma, ; R., ; Oosterwijk, ; T., ; Vredeveld, ; T.,
  • From pricing to prophets, and back! Operations Research Letters 47, 1, 25--29
    Correa, ; J., ; Foncea, ; P., ; Pizarro, ; D., ; Verdugo, ; V.,
  • Prophet secretary through blind strategies
    Correa, ; J., ; Saona, ; R., ; Ziliotto, ; B.,
  • Prophet inequalities made easy: Stochastic optimization by pricing non-stochastic inputs
    Düetting, ; P., ; Feldman, ; M., ; Kesselheim, ; T., ; Lucier, ; B.,
  • Prophet secretary for combinatorial auctions and matroids
    Ehsani, ; S., ; Hajiaghayi, ; M., ; Kesselheim, ; T., ; Singla, ; S.,
  • Prophet secretary
    Esfandiari, ; H., ; Hajiaghayi, ; M., ; Liaghat, ; V., ; Monemizadeh, ; M.,
  • Prophets and secretaries with overbooking
    Ezra, ; T., ; Feldman, ; M., ; Nehama, ; I.,
  • Automated online mechanism design and prophet inequalities
    Hajiaghayi, ; M., ; Kleinberg, ; R., ; Sandholm, ; T.,
  • Prophet inequalities and order selection in optimal stopping problems
    Hill, ; T.,
  • Comparisons of stop rule and supremum expectations of i
    Hill, ; T., ; Kertz, ; R.,
  • A survey of prophet inequalities in optimal stopping theory
    Hill, ; T., ; Kertz, ; R.,
  • Ratio comparisons of supremum and stop rule expectations
    Hill, ; P., T.; Kertz, ; P., R.
  • Stop rule and supremum expectations of i
    Kertz, ; R.,
  • Delegated search approximates efficient search
    Kleinberg, ; M., J.; Kleinberg, ; R.,
  • Matroid prophet inequalities
    Kleinberg, ; R., ; Weinberg, ; M., S.
  • Semiamarts and finite values
    Krengel, ; U., ; Sucheston, ; L.,
  • On semiamarts, amarts, and processes with finite value
    Krengel, ; U., ; Sucheston, ; L.,
  • An economic view of prophet inequalities
    Lucier, ; B.,
  • Comparisons of threshold stop rule and maximum for independent nonnegative random variables
    Samuel-Cahn, ; E.,