{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:47:33Z","timestamp":1781077653409,"version":"3.54.1"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,5,7]],"date-time":"2019-05-07T00:00:00Z","timestamp":1557187200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGecom Exch."],"published-print":{"date-parts":[[2019,5,7]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/3331033.3331039","type":"journal-article","created":{"date-parts":[[2019,5,8]],"date-time":"2019-05-08T14:11:11Z","timestamp":1557324671000},"page":"61-70","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":55,"title":["Recent developments in prophet inequalities"],"prefix":"10.1145","volume":"17","author":[{"given":"Jose","family":"Correa","sequence":"first","affiliation":[{"name":"Universidad de Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Patricio","family":"Foncea","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ruben","family":"Hoeksma","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Bremen"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tim","family":"Oosterwijk","sequence":"additional","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tjark","family":"Vredeveld","sequence":"additional","affiliation":[{"name":"Maastricht University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,5,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055479"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1080\/07474940701620857"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Azar P. D. Kleinberg R. and Weinberg S. M. 2018. Prior independent mechanisms via prophet inequalities with limited information. Games and Economic Behavior.  Azar P. D. Kleinberg R. and Weinberg S. M. 2018. Prior independent mechanisms via prophet inequalities with limited information. Games and Economic Behavior.","DOI":"10.1016\/j.geb.2018.05.006"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219182"},{"key":"e_1_2_1_5_1","unstructured":"Beyhaghi H. Golrezaei N. Leme R. P. Pal M. and Sivan B. 2018. Improved approximations for free-order prophets and second-price auctions. CoRR abs\/1807.03435.  Beyhaghi H. Golrezaei N. Leme R. P. Pal M. and Sivan B. 2018. Improved approximations for free-order prophets and second-price auctions. CoRR abs\/1807.03435."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806733"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085137"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Correa J. Foncea P. Pizarro D. and Verdugo V. 2019. From pricing to prophets and back! Operations Research Letters 47 1 25--29.  Correa J. Foncea P. Pizarro D. and Verdugo V. 2019. From pricing to prophets and back! Operations Research Letters 47 1 25--29.","DOI":"10.1016\/j.orl.2018.11.010"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '19","author":"Correa J.","unstructured":"Correa , J. , Saona , R. , and Ziliotto , B . 2019. Prophet secretary through blind strategies . In Proceedings of the thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '19 . Correa, J., Saona, R., and Ziliotto, B. 2019. Prophet secretary through blind strategies. In Proceedings of the thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '19."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science. FOCS '17.","author":"D\u00fcetting P.","unstructured":"D\u00fcetting , P. , Feldman , M. , Kesselheim , T. , and Lucier , B . 2017. Prophet inequalities made easy: Stochastic optimization by pricing non-stochastic inputs . In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science. FOCS '17. D\u00fcetting, P., Feldman, M., Kesselheim, T., and Lucier, B. 2017. Prophet inequalities made easy: Stochastic optimization by pricing non-stochastic inputs. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science. FOCS '17."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 29th annual ACM-SIAM symposium on Discrete algorithms. SODA 2018.","author":"Ehsani S.","unstructured":"Ehsani , S. , Hajiaghayi , M. , Kesselheim , T. , and Singla , S . 2018. Prophet secretary for combinatorial auctions and matroids . In Proceedings of the 29th annual ACM-SIAM symposium on Discrete algorithms. SODA 2018. Ehsani, S., Hajiaghayi, M., Kesselheim, T., and Singla, S. 2018. Prophet secretary for combinatorial auctions and matroids. In Proceedings of the 29th annual ACM-SIAM symposium on Discrete algorithms. SODA 2018."},{"key":"e_1_2_1_12_1","volume-title":"The 23rd Annual European Symposium on Algorithms. ESA 2015.","author":"Esfandiari H.","unstructured":"Esfandiari , H. , Hajiaghayi , M. , Liaghat , V. , and Monemizadeh , M . 2015. Prophet secretary . In The 23rd Annual European Symposium on Algorithms. ESA 2015. Esfandiari, H., Hajiaghayi, M., Liaghat, V., and Monemizadeh, M. 2015. Prophet secretary. In The 23rd Annual European Symposium on Algorithms. ESA 2015."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219211"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 22nd Conference on Artificial Intelligence. AAAI 2007.","author":"Hajiaghayi M.","unstructured":"Hajiaghayi , M. , Kleinberg , R. , and Sandholm , T . 2007. Automated online mechanism design and prophet inequalities . In Proceedings of the 22nd Conference on Artificial Intelligence. AAAI 2007. Hajiaghayi, M., Kleinberg, R., and Sandholm, T. 2007. Automated online mechanism design and prophet inequalities. In Proceedings of the 22nd Conference on Artificial Intelligence. AAAI 2007."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1983-0691293-4"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993861"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/125\/1160620"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00535745"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0047-259X(86)90095-3"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219205"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213991"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1977-14378-4"},{"key":"e_1_2_1_23_1","first-page":"197","article-title":"On semiamarts, amarts, and processes with finite value","volume":"4","author":"Krengel U.","year":"1978","unstructured":"Krengel , U. and Sucheston , L. 1978 . On semiamarts, amarts, and processes with finite value . Adv. in Probability 4 , 197 -- 266 . Krengel, U. and Sucheston, L. 1978. On semiamarts, amarts, and processes with finite value. Adv. in Probability 4, 197--266.","journal-title":"Adv. in Probability"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3144722.3144725"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993150"}],"container-title":["ACM SIGecom Exchanges"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3331033.3331039","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3331033.3331039","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:26:05Z","timestamp":1750206365000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3331033.3331039"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,7]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,5,7]]}},"alternative-id":["10.1145\/3331033.3331039"],"URL":"https:\/\/doi.org\/10.1145\/3331033.3331039","relation":{},"ISSN":["1551-9031"],"issn-type":[{"value":"1551-9031","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,7]]},"assertion":[{"value":"2019-05-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}