{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T08:25:20Z","timestamp":1768465520698,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":30,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,7,8]],"date-time":"2024-07-08T00:00:00Z","timestamp":1720396800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"ANID","award":["ACT210005"],"award-info":[{"award-number":["ACT210005"]}]},{"name":"ANID","award":["FB210005"],"award-info":[{"award-number":["FB210005"]}]},{"name":"Harvard University Center of Mathematical Sciences and Applications"},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["866132"],"award-info":[{"award-number":["866132"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Amazon Research"},{"name":"NSF-BSF","award":["2020788"],"award-info":[{"award-number":["2020788"]}]},{"name":"TAU Center for AI and Data Science"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,7,8]]},"DOI":"10.1145\/3670865.3673467","type":"proceedings-article","created":{"date-parts":[[2024,12,17]],"date-time":"2024-12-17T20:13:33Z","timestamp":1734466413000},"page":"807-830","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["The Competition Complexity of Prophet Inequalities"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-2523-8051","authenticated-orcid":false,"given":"Johannes","family":"Brustle","sequence":"first","affiliation":[{"name":"Sapienza University of Rome, Rome, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3012-7622","authenticated-orcid":false,"given":"Jos\u00e9","family":"Correa","sequence":"additional","affiliation":[{"name":"Universidad de Chile, Santiago, Chile"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0635-6812","authenticated-orcid":false,"given":"Paul","family":"D\u00fctting","sequence":"additional","affiliation":[{"name":"Google, Zurich, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0626-4851","authenticated-orcid":false,"given":"Tomer","family":"Ezra","sequence":"additional","affiliation":[{"name":"Harvard University, Cambridge, United States of America"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2915-8405","authenticated-orcid":false,"given":"Michal","family":"Feldman","sequence":"additional","affiliation":[{"name":"Tel Aviv University and Microsoft ILDC, Tel Aviv, Israel"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0817-7356","authenticated-orcid":false,"given":"Victor","family":"Verdugo","sequence":"additional","affiliation":[{"name":"Pontificia Universidad Cat\u00f3lica de Chile, Santiago, Chile"}]}],"member":"320","published-online":{"date-parts":[[2024,12,17]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"STOC","author":"Abolhassani M.","year":"2017","unstructured":"M. Abolhassani, S. Ehsani, H. Esfandriari, M. Hajiaghayi, R. Kleinberg, and B. Lucier. 2017. Beating 1-1\/e for Ordered Prophets. In STOC 2017. 61--71."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.90"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"crossref","unstructured":"N. Arnosti and W. Ma. 2022. Tight guarantees for static threshold policies in the prophet secretary problem. Operations Research (2022).","DOI":"10.1145\/3490486.3538377"},{"key":"e_1_3_2_1_4_1","volume-title":"Bulow-Klemperer-Style Results for Welfare Maximization in Two-Sided Markets. In SODA","author":"Babaioff M.","year":"2020","unstructured":"M. Babaioff, K. Goldner, and Y. A. Gonczarowski. 2020. Bulow-Klemperer-Style Results for Welfare Maximization in Two-Sided Markets. In SODA 2020. 2452--2471."},{"key":"e_1_3_2_1_5_1","volume-title":"STOC","author":"Beyhaghi H.","year":"2019","unstructured":"H. Beyhaghi and S. M. Weinberg. 2019. Optimal (and Benchmark-Optimal) Competition Complexity for Additive Buyers over Independent Items. In STOC 2019. 686--696."},{"key":"e_1_3_2_1_6_1","volume-title":"The Competition Complexity of Dynamic Pricing. In EC","author":"Brustle J.","year":"2022","unstructured":"J. Brustle, J. Correa, P. D\u00fctting, and V. Verdugo. 2022. The Competition Complexity of Dynamic Pricing. In EC 2022. 303--320."},{"key":"e_1_3_2_1_7_1","first-page":"180","article-title":"Auctions versus Negotiations","volume":"86","author":"Bulow J.","year":"1996","unstructured":"J. Bulow and P. Klemperer. 1996. Auctions versus Negotiations. American Economic Review 86, 1 (1996), 180--94.","journal-title":"American Economic Review"},{"key":"e_1_3_2_1_8_1","volume-title":"Multiparameter Mechanism Design and Sequential Posted Pricing. In STOC","author":"Chawla S.","year":"2010","unstructured":"S. Chawla, J. Hartline, D. Malec, and B. Sivan. 2010. Multiparameter Mechanism Design and Sequential Posted Pricing. In STOC 2010. 311--320."},{"key":"e_1_3_2_1_9_1","volume-title":"STOC","author":"Correa J.","year":"2023","unstructured":"J. Correa and A. Cristi. 2023. A constant-factor prophet inequality for online combinatorial auctions. In STOC 2023. 686--697."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2020.1105"},{"key":"e_1_3_2_1_11_1","volume-title":"Resource Augmentation for Online Bounded Space Bin Packing. In ICALP","author":"Csirik J.","year":"2000","unstructured":"J. Csirik and G.J. Woeginger. 2000. Resource Augmentation for Online Bounded Space Bin Packing. In ICALP 2000. 296--304."},{"key":"e_1_3_2_1_12_1","volume-title":"FOCS","author":"D\u00fctting P.","year":"2017","unstructured":"P. D\u00fctting, M. Feldman, T. Kesselheim, and B. Lucier. 2017. Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs. In FOCS 2017. 540--551."},{"key":"e_1_3_2_1_13_1","volume-title":"FOCS","author":"D\u00fctting P.","year":"2020","unstructured":"P. D\u00fctting, T. Kesselheim, and B. Lucier. 2020. An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions. In FOCS 2020. 306--317."},{"key":"e_1_3_2_1_14_1","first-page":"343","article-title":"The Competition Complexity of Auctions","volume":"2017","author":"Eden A.","year":"2017","unstructured":"A. Eden, M. Feldman, O. Friedler, I. Talgam-Cohen, and S. M. Weinberg. 2017. The Competition Complexity of Auctions: A Bulow-Klemperer Result for Multi-Dimensional Bidders. In EC 2017. 343.","journal-title":"A Bulow-Klemperer Result for Multi-Dimensional Bidders. In EC"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2021.1152"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3373715"},{"key":"e_1_3_2_1_17_1","volume-title":"SODA","author":"Feldman M.","year":"2015","unstructured":"M. Feldman, N. Gravin, and B. Lucier. 2015. Combinatorial Auctions via Posted Prices. In SODA 2015. 123--135."},{"key":"e_1_3_2_1_18_1","volume-title":"Online Contention Resolution Schemes. In SODA","author":"Feldman M.","year":"2016","unstructured":"M. Feldman, O. Svensson, and R. Zenklusen. 2016. Online Contention Resolution Schemes. In SODA 2016, Robert Krauthgamer (Ed.). 1014--1033."},{"key":"e_1_3_2_1_19_1","first-page":"93","article-title":"Prophet Inequality for Bipartite Matching: Merits of Being Simple and Non Adaptive","volume":"2019","author":"Gravin N.","year":"2019","unstructured":"N. Gravin and H. Wang. 2019. Prophet Inequality for Bipartite Matching: Merits of Being Simple and Non Adaptive. In EC 2019. 93--109.","journal-title":"EC"},{"key":"e_1_3_2_1_20_1","volume-title":"Automated Mechanism Design and Prophet Inequalities. In AAAI","author":"Hajiaghayi M.","year":"2007","unstructured":"M. Hajiaghayi, R. Kleinberg, and T. Sandholm. 2007. Automated Mechanism Design and Prophet Inequalities. In AAAI 2007. 58--65."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/347476.347479"},{"key":"e_1_3_2_1_22_1","volume-title":"Matroid Prophet Inequalities. In STOC","author":"Kleinberg R.","year":"2012","unstructured":"R. Kleinberg and S. M. Weinberg. 2012. Matroid Prophet Inequalities. In STOC 2012. 123--136."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1977-14378-4"},{"key":"e_1_3_2_1_24_1","first-page":"197","article-title":"On semiamarts, amarts, and processes with finite value","volume":"4","author":"Krengel U.","year":"1978","unstructured":"U. Krengel and L. Sucheston. 1978. On semiamarts, amarts, and processes with finite value. Advances in Probability and Related Topics 4 (1978), 197--266.","journal-title":"Advances in Probability and Related Topics"},{"key":"e_1_3_2_1_25_1","volume-title":"Variable Decomposition for Prophet Inequalities and Optimal Ordering. In EC","author":"Liu A.","year":"2021","unstructured":"A. Liu, R. Paes Leme, M. P\u00e1l, J. Schneider, and B. Sivan. 2021. Variable Decomposition for Prophet Inequalities and Optimal Ordering. In EC 2021. 692."},{"key":"e_1_3_2_1_26_1","volume-title":"STOC","author":"Phillips C. A.","year":"1997","unstructured":"C. A. Phillips, C. Stein, E. Torng, and J. Wein. 1997. Optimal Time-Critical Scheduling via Resource Augmentation (Extended Abstract). In STOC 1997. 140--149."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/506147.506153"},{"key":"e_1_3_2_1_28_1","volume-title":"Combinatorial Prophet Inequalities. In SODA","author":"Rubinstein A.","year":"2017","unstructured":"A. Rubinstein and S. Singla. 2017. Combinatorial Prophet Inequalities. In SODA 2017. 1671--1687."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993150"},{"key":"e_1_3_2_1_30_1","volume-title":"Amortized Efficiency of List Update Rules. In STOC","author":"Sleator D. D.","year":"1984","unstructured":"D. D. Sleator and R. E. Tarjan. 1984. Amortized Efficiency of List Update Rules. In STOC 1984. 488--492."}],"event":{"name":"EC '24: 25th ACM Conference on Economics and Computation","location":"New Haven CT USA","acronym":"EC '24","sponsor":["SIGecom Special Interest Group on Economics and Computation"]},"container-title":["Proceedings of the 25th ACM Conference on Economics and Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3670865.3673467","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3670865.3673467","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:05:42Z","timestamp":1750291542000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3670865.3673467"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,8]]},"references-count":30,"alternative-id":["10.1145\/3670865.3673467","10.1145\/3670865"],"URL":"https:\/\/doi.org\/10.1145\/3670865.3673467","relation":{},"subject":[],"published":{"date-parts":[[2024,7,8]]},"assertion":[{"value":"2024-12-17","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}