{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T04:17:24Z","timestamp":1751516244033,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":49,"publisher":"ACM","funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["101077862"],"award-info":[{"award-number":["101077862"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Harvard University Center of Mathematical Sciences and Applications"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,7,7]]},"DOI":"10.1145\/3736252.3742521","type":"proceedings-article","created":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T18:49:32Z","timestamp":1751482172000},"page":"226-249","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["The Competition Complexity of Prophet Inequalities with Correlations"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0626-4851","authenticated-orcid":false,"given":"Tomer","family":"Ezra","sequence":"first","affiliation":[{"name":"Harvard University, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-3922-4160","authenticated-orcid":false,"given":"Tamar","family":"Garbuz","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,7,2]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"On Optimal Ordering in the Optimal Stopping Problem. In EC '20: The 21st ACM Conference on Economics and Computation","author":"Agrawal Shipra","year":"2020","unstructured":"Shipra Agrawal, Jay Sethuraman, and Xingyu Zhang. 2020. On Optimal Ordering in the Optimal Stopping Problem. In EC '20: The 21st ACM Conference on Economics and Computation, Virtual Event, Hungary, July 13\u201317, 2020. ACM, 187\u2013188."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.100"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219182"},{"key":"e_1_3_2_1_4_1","volume-title":"Symposium on Discrete Algorithms (SODA'07)","author":"Babaioff Moshe","year":"2007","unstructured":"Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. 2007. Matroids, secretary problems, and online mechanisms. In Symposium on Discrete Algorithms (SODA'07). 434\u2013443."},{"key":"e_1_3_2_1_5_1","volume-title":"Martin P\u00e1l, and Balasubramanian Sivan.","author":"Beyhaghi Hedyeh","year":"2021","unstructured":"Hedyeh Beyhaghi, Negin Golrezaei, Renato Paes Leme, Martin P\u00e1l, and Balasubramanian Sivan. 2021. Improved revenue bounds for posted-price and second-price mechanisms. Operations research 69, 6 (2021), 1805\u20131822."},{"key":"e_1_3_2_1_6_1","volume-title":"Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark. In EC '22: The 23rd ACM Conference on Economics and Computation","author":"Braverman Mark","year":"2022","unstructured":"Mark Braverman, Mahsa Derakhshan, and Antonio Molina Lovett. 2022. Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark. In EC '22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11 - 15, 2022. ACM, 967\u2013985."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.98"},{"key":"e_1_3_2_1_8_1","volume-title":"The Competition Complexity of Dynamic Pricing. Mathematics of Operations Research","author":"Brustle Johannes","year":"2023","unstructured":"Johannes Brustle, Jos\u00e9 Correa, Paul Duetting, and Victor Verdugo. 2023. The Competition Complexity of Dynamic Pricing. Mathematics of Operations Research (2023)."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3670865.3673467"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465456.3467643"},{"key":"e_1_3_2_1_11_1","volume-title":"International Conference on Web and Internet Economics. Springer, 131\u2013148","author":"Caragiannis Ioannis","year":"2021","unstructured":"Ioannis Caragiannis, Nick Gravin, Pinyan Lu, and Zihe Wang. 2021. Relaxing the Independence Assumption in Sequential Posted Pricing, Prophet Inequality, and Random Bipartite Matching. In International Conference on Web and Internet Economics. Springer, 131\u2013148."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01544-8"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/24M1630207"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649718"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1323850"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00037"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_37"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175316"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1029394"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2021.1152"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch145"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219211"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3670865.3673620"},{"key":"e_1_3_2_1_24_1","volume-title":"International Conference on Web and Internet Economics. Springer, 256\u2013271","author":"Ezra Tomer","year":"2023","unstructured":"Tomer Ezra and Tamar Garbuz. 2023. The importance of knowing the arrival order in combinatorial Bayesian settings. In International Conference on Web and Internet Economics. Springer, 256\u2013271."},{"key":"e_1_3_2_1_25_1","volume-title":"The Competition Complexity of Prophet Secretary. arXiv preprint arXiv:2411.10892","author":"Ezra Tomer","year":"2024","unstructured":"Tomer Ezra and Tamar Garbuz. 2024. The Competition Complexity of Prophet Secretary. arXiv preprint arXiv:2411.10892 (2024)."},{"key":"e_1_3_2_1_26_1","volume-title":"International Conference on Web and Internet Economics. Springer Nature Switzerland Cham, 272\u2013289","author":"Ezra Tomer","year":"2023","unstructured":"Tomer Ezra, Stefano Leonardi, Rebecca Reiffenh\u00e4user, Matteo Russo, and Alexandros Tsigonias-Dimitriadis. 2023b. Prophet inequalities via the expected competitive ratio. In International Conference on Web and Internet Economics. Springer Nature Switzerland Cham, 272\u2013289."},{"key":"e_1_3_2_1_27_1","volume-title":"Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms. SIAM, 123\u2013135","author":"Feldman Michal","year":"2014","unstructured":"Michal Feldman, Nick Gravin, and Brendan Lucier. 2014. Combinatorial auctions via posted prices. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms. SIAM, 123\u2013135."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch72"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Nikolai Gravin and Hongao Wang. 2019. Prophet Inequality for Bipartite Matching: Merits of Being Simple and Non Adaptive. In EC. ACM 93\u2013109.","DOI":"10.1145\/3328526.3329604"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-59835-7_15"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1983-0697070-7"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399452"},{"key":"e_1_3_2_1_33_1","volume-title":"Optimal stopping of independent random variables and maximizing prophets. The Annals of Probability","author":"Kennedy Douglas P","year":"1985","unstructured":"Douglas P Kennedy. 1985. Optimal stopping of independent random variables and maximizing prophets. The Annals of Probability (1985), 566\u2013571."},{"key":"e_1_3_2_1_34_1","volume-title":"Prophet-type inequalities for multi-choice optimal stopping. Stochastic Processes and their applications 24, 1","author":"Kennedy Douglas P","year":"1987","unstructured":"Douglas P Kennedy. 1987. Prophet-type inequalities for multi-choice optimal stopping. Stochastic Processes and their applications 24, 1 (1987), 77\u201388."},{"key":"e_1_3_2_1_35_1","volume-title":"Comparison of optimal value and constrained maxima expectations for independent random variables. Advances in applied probability 18, 2","author":"Kertz Robert P","year":"1986","unstructured":"Robert P Kertz. 1986. Comparison of optimal value and constrained maxima expectations for independent random variables. Advances in applied probability 18, 2 (1986), 311\u2013340."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490486.3538374"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2014.11.002"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1977-14378-4"},{"key":"e_1_3_2_1_39_1","volume-title":"On semiamarts, amarts, and processes with finite value. Probability on Banach spaces 4","author":"Krengel Ulrich","year":"1978","unstructured":"Ulrich Krengel and Louis Sucheston. 1978. On semiamarts, amarts, and processes with finite value. Probability on Banach spaces 4 (1978), 197\u2013266."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3670865.3673462"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.100"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-04612-5_24"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465456.3467613"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00023"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176350605"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/0047-259X(91)90114-H"},{"key":"e_1_3_2_1_47_1","volume-title":"Optimal stopping values and prophet inequalities for some dependent random variables. Lecture Notes-Monograph Series (1992), 343\u2013358","author":"Rinott Yosef","unstructured":"Yosef Rinott and Ester Samuel-Cahn. 1992. Optimal stopping values and prophet inequalities for some dependent random variables. Lecture Notes-Monograph Series (1992), 343\u2013358."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897540"},{"key":"e_1_3_2_1_49_1","volume-title":"48th International Colloquium on Automata, Languages, and Programming (ICALP 2021","author":"Saberi Amin","year":"2021","unstructured":"Amin Saberi and David Wajc. 2021. The greedy algorithm is not optimal for on-line edge coloring. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik. Ester Samuel-Cahn. 1984. Comparison of threshold stop rules and maximum for independent nonnegative random variables. the Annals of Probability (1984), 1213\u20131216."}],"event":{"name":"EC '25: 26th ACM Conference on Economics and Computation","location":"Stanford University Stanford CA USA","acronym":"EC '25","sponsor":["SIGecom ACM Special Interest Group on Economics and Computation"]},"container-title":["Proceedings of the 26th ACM Conference on Economics and Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3736252.3742521","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T18:51:31Z","timestamp":1751482291000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3736252.3742521"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,2]]},"references-count":49,"alternative-id":["10.1145\/3736252.3742521","10.1145\/3736252"],"URL":"https:\/\/doi.org\/10.1145\/3736252.3742521","relation":{},"subject":[],"published":{"date-parts":[[2025,7,2]]},"assertion":[{"value":"2025-07-02","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}