{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T13:16:31Z","timestamp":1763644591303,"version":"3.41.0"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T00:00:00Z","timestamp":1744156800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["DMS-1928930"],"award-info":[{"award-number":["DMS-1928930"]}]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"crossref","award":["G-2021-16778"],"award-info":[{"award-number":["G-2021-16778"]}],"id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"crossref"}]},{"name":"ERC Advanced Grant","award":["788893 AMDROMA"],"award-info":[{"award-number":["788893 AMDROMA"]}]},{"name":"FAIR","award":["PE0000013"],"award-info":[{"award-number":["PE0000013"]}]},{"name":"NextGenerationEU program within the PNRR-PE-AI scheme"},{"name":"PNRR MUR project","award":["IR0000013-SoBigData.it"],"award-info":[{"award-number":["IR0000013-SoBigData.it"]}]},{"name":"MUR PRIN","award":["2022EKNE5K"],"award-info":[{"award-number":["2022EKNE5K"]}]},{"name":"Alexander von Humboldt Foundation with funds from the German Federal Ministry of Education and Research (BMBF), the Deutsche Forschungsgemeinschaft","award":["Projektnummer 277991500"],"award-info":[{"award-number":["Projektnummer 277991500"]}]},{"name":"COST Action","award":["CA16228 \u201cEuropean Network for Game Theory\u201d (GAMENET)"],"award-info":[{"award-number":["CA16228 \u201cEuropean Network for Game Theory\u201d (GAMENET)"]}]},{"name":"ANID, Chile","award":["ACT210005"],"award-info":[{"award-number":["ACT210005"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>\n            We consider prophet inequalities under general downward-closed constraints. In a prophet inequality problem, a decision-maker sees a series of online elements with values and needs to decide immediately and irrevocably whether or not to select each element upon its arrival, subject to an underlying feasibility constraint. Traditionally, the decision-maker\u2019s expected performance has been compared to the expected performance of the\n            <jats:italic>prophet<\/jats:italic>\n            , i.e., the expected offline optimum. We refer to this measure as the\n            <jats:italic>Ratio of Expectations<\/jats:italic>\n            (or, in short,\n            <jats:sans-serif>RoE<\/jats:sans-serif>\n            ). However, a major limitation of the\n            <jats:sans-serif>RoE<\/jats:sans-serif>\n            measure is that it only gives a guarantee against what the optimum would be on average, while, in theory, algorithms still might perform poorly compared to the realized ex-post optimal value. Hence, we study alternative performance measures. In particular, we suggest the\n            <jats:italic>Expectation of Ratio<\/jats:italic>\n            (or, in short,\n            <jats:sans-serif>EoR<\/jats:sans-serif>\n            ), which is the expectation of the ratio between the value of the algorithm and the value of the prophet. This measure yields desirable guarantees, e.g., a constant\n            <jats:sans-serif>EoR<\/jats:sans-serif>\n            implies achieving a constant fraction of the ex-post offline optimum with constant probability. Moreover, in the single-choice setting, we show that the\n            <jats:sans-serif>EoR<\/jats:sans-serif>\n            is equivalent (in the worst case) to the probability of selecting the maximum, a well-studied measure in the literature. However, the probability of selecting the maximum does not generalize meaningfully to combinatorial constraints (beyond single-choice), since its direct equivalent is the probability of selecting an optimal overall set. We, thus, introduce the\n            <jats:sans-serif>EoR<\/jats:sans-serif>\n            as a cardinal variant of the probability of selecting the maximum, which extends naturally to combinatorial settings. Our main goal is to understand the relation between\n            <jats:sans-serif>RoE<\/jats:sans-serif>\n            and\n            <jats:sans-serif>EoR<\/jats:sans-serif>\n            in combinatorial settings. Specifically, we establish two reductions: For every feasibility constraint, the\n            <jats:sans-serif>RoE<\/jats:sans-serif>\n            and the\n            <jats:sans-serif>EoR<\/jats:sans-serif>\n            are at most a constant factor apart on worst-case instances. Additionally, we show that the\n            <jats:sans-serif>EoR<\/jats:sans-serif>\n            is a stronger benchmark than the\n            <jats:sans-serif>RoE<\/jats:sans-serif>\n            in that, for every instance (feasibility constraint and product distribution), the\n            <jats:sans-serif>RoE<\/jats:sans-serif>\n            is at least a constant fraction of the\n            <jats:sans-serif>EoR<\/jats:sans-serif>\n            but not vice versa. Both these reductions imply a wealth of\n            <jats:sans-serif>EoR<\/jats:sans-serif>\n            results in multiple settings where\n            <jats:sans-serif>RoE<\/jats:sans-serif>\n            results are known.\n          <\/jats:p>","DOI":"10.1145\/3717076","type":"journal-article","created":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T11:19:18Z","timestamp":1740568758000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Prophet Inequalities via the Expected Competitive Ratio"],"prefix":"10.1145","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0626-4851","authenticated-orcid":false,"given":"Tomer","family":"Ezra","sequence":"first","affiliation":[{"name":"Center of Mathematical Sciences and Applications, Harvard University, Cambridge, United States"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9809-7191","authenticated-orcid":false,"given":"Stefano","family":"Leonardi","sequence":"additional","affiliation":[{"name":"Computer, Control and Management Sciences, Sapienza University of Rome, Rome, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0959-2589","authenticated-orcid":false,"given":"Rebecca","family":"Reiffenhauser","sequence":"additional","affiliation":[{"name":"Computer Science, University of Amsterdam, Amsterdam, Netherlands"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2047-4089","authenticated-orcid":false,"given":"Matteo","family":"Russo","sequence":"additional","affiliation":[{"name":"Dipartimento di Ingegneria Informatica Automatica e Gestionale, Universita degli Studi di Roma La Sapienza, Rome, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7558-2215","authenticated-orcid":false,"given":"Alexandros","family":"Tsigonias-Dimitriadis","sequence":"additional","affiliation":[{"name":"Technical University Munich: Technische Universitat Munchen, Munich, Germany"}]}],"member":"320","published-online":{"date-parts":[[2025,4,9]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399484"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.90"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229018"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1017\/jpr.2016.63"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329652"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2018.05.006"},{"key":"e_1_3_4_8_2","first-page":"434","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907)","author":"Babaioff Moshe","year":"2007","unstructured":"Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. 2007. Matroids, secretary problems, and online mechanisms. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907). SIAM, 434\u2013443."},{"key":"e_1_3_4_9_2","first-page":"280","volume-title":"Proceedings of the 17th International Conference on Web and Internet Economics (WINE\u201921)","author":"Bahrani Maryam","year":"2021","unstructured":"Maryam Bahrani, Hedyeh Beyhaghi, Sahil Singla, and S. Matthew Weinberg. 2021. Formal barriers to simple algorithms for the matroid secretary problem. In Proceedings of the 17th International Conference on Web and Internet Economics (WINE\u201921). Springer, 280\u2013298."},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.155"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.5555\/346773.346785"},{"key":"e_1_3_4_12_2","doi-asserted-by":"crossref","unstructured":"St\u00e9phane Boucheron G\u00e1bor Lugosi and Pascal Massart. 2009. On concentration of self-bounding functions. Electronic Journal of Probability [electronic only] 14 (2009) 1884\u20131899. Retrieved from http:\/\/eudml.org\/doc\/225950","DOI":"10.1214\/EJP.v14-690"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3490486.3538315"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.54"},{"key":"e_1_3_4_15_2","first-page":"311","volume-title":"Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC\u201910)","author":"Chawla Shuchi","year":"2010","unstructured":"Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. 2010. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC\u201910), Leonard J. Schulman (Ed.). ACM, 311\u2013320."},{"key":"e_1_3_4_16_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1007\/978-3-030-82405-1","volume-title":"Proceedings of the 14th International Symposium on Algorithmic Game Theory (SAGT\u201921)","volume":"12885","author":"Chekuri Chandra","year":"2021","unstructured":"Chandra Chekuri and Vasilis Livanos. 2021. On submodular prophet inequalities and correlation gap. In Proceedings of the 14th International Symposium on Algorithmic Game Theory (SAGT\u201921)(Lecture Notes in Computer Science, Vol. 12885). Springer, 410."},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2023.1363"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3331033.3331039"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2018.11.010"},{"key":"e_1_3_4_20_2","series-title":"Proceedings of Machine Learning Research","first-page":"2112","volume-title":"Proceedings of the 38th International Conference on Machine Learning (ICML\u201921)","volume":"139","author":"Correa Jos\u00e9 R.","year":"2021","unstructured":"Jos\u00e9 R. Correa, Andr\u00e9s Cristi, Paul Duetting, and Ashkan Norouzi-Fard. 2021. Fairness and bias in online selection. In Proceedings of the 38th International Conference on Machine Learning (ICML\u201921)(Proceedings of Machine Learning Research, Vol. 139). PMLR, 2112\u20132121."},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.127"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329627"},{"key":"e_1_3_4_23_2","series-title":"LIPIcs","first-page":"86:1\u201386:1","volume-title":"Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS\u201921)","volume":"185","author":"Correa Jos\u00e9 R.","year":"2021","unstructured":"Jos\u00e9 R. Correa, Paul D\u00fctting, Felix A. Fischer, Kevin Schewior, and Bruno Ziliotto. 2021. Unknown I.I.D. prophets: Better bounds, streaming algorithms, and a new impossibility (extended abstract). In Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS\u201921)(LIPIcs, Vol. 185). 86:1\u201386:1."},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/20M1323850"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3580507.3597736"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_37"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.46"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1029394"},{"key":"e_1_3_4_29_2","series-title":"Proceedings of Machine Learning Research","first-page":"3717","volume-title":"Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS\u201920)","volume":"108","author":"Esfandiari Hossein","year":"2020","unstructured":"Hossein Esfandiari, MohammadTaghi Hajiaghayi, Brendan Lucier, and Michael Mitzenmacher. 2020. Prophets, secretaries, and maximizing the probability of choosing the best. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS\u201920)(Proceedings of Machine Learning Research, Vol. 108). PMLR, 3717\u20133727."},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399513"},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch145"},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.10"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/18M1226130"},{"key":"e_1_3_4_34_2","first-page":"942","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908)","author":"Garg Naveen","year":"2008","unstructured":"Naveen Garg, Anupam Gupta, Stefano Leonardi, and Piotr Sankowski. 2008. Stochastic analyses for online combinatorial optimization problems. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908). 942\u2013951."},{"key":"e_1_3_4_35_2","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1966.10502008"},{"key":"e_1_3_4_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329604"},{"key":"e_1_3_4_37_2","first-page":"58","volume-title":"Proceedings of the 22nd National Conference on Artificial Intelligence (AAAI\u201907)","author":"Hajiaghayi Mohammad Taghi","year":"2007","unstructured":"Mohammad Taghi Hajiaghayi, Robert Kleinberg, and Tuomas Sandholm. 2007. Automated online mechanism design and prophet inequalities. In Proceedings of the 22nd National Conference on Artificial Intelligence (AAAI\u201907). AAAI Press, 58\u201365."},{"key":"e_1_3_4_38_2","article-title":"Lower bounds for prior independent algorithms","volume":"2107","author":"Hartline Jason D.","year":"2021","unstructured":"Jason D. Hartline and Aleck C. Johnsen. 2021. Lower bounds for prior independent algorithms. CoRR abs\/2107.04754 (2021).","journal-title":"CoRR"},{"key":"e_1_3_4_39_2","doi-asserted-by":"crossref","unstructured":"Theodore P. Hill and Robert P. Kertz. 1992. A survey of prophet inequalities in optimal stopping theory. Contemporary Mathematics 125 (1992) 191\u2013207.","DOI":"10.1090\/conm\/125\/1160620"},{"key":"e_1_3_4_40_2","series-title":"LIPIcs","first-page":"133:1\u2013133:14","volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917)","volume":"80","author":"Hoefer Martin","year":"2017","unstructured":"Martin Hoefer and Bojana Kodric. 2017. Combinatorial secretary problems with ordinal information. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917)(LIPIcs, Vol. 80). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 133:1\u2013133:14."},{"key":"e_1_3_4_41_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.51"},{"key":"e_1_3_4_42_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.128"},{"key":"e_1_3_4_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/3465456.3467568"},{"key":"e_1_3_4_44_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2014.11.002"},{"key":"e_1_3_4_45_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1977-14378-4"},{"key":"e_1_3_4_46_2","first-page":"197\u2014266","article-title":"On semiamarts, amarts, and processes with finite value","volume":"4","author":"Krengel Ulrich","year":"1978","unstructured":"Ulrich Krengel and Louis Sucheston. 1978. On semiamarts, amarts, and processes with finite value. Advan. Probab. Relat. Topics 4 (1978), 197\u2014266.","journal-title":"Advan. Probab. Relat. Topics"},{"key":"e_1_3_4_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/3144722.3144725"},{"key":"e_1_3_4_48_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-04612-5_24"},{"key":"e_1_3_4_49_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-06901-7_32"},{"key":"e_1_3_4_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3465456.3467613"},{"key":"e_1_3_4_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897540"},{"key":"e_1_3_4_52_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.110"},{"key":"e_1_3_4_53_2","series-title":"LIPIcs","first-page":"60:1\u201360:10","volume-title":"Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS\u201920)","volume":"151","author":"Rubinstein Aviad","year":"2020","unstructured":"Aviad Rubinstein, Jack Z. Wang, and S. Matthew Weinberg. 2020. Optimal single-choice prophet inequalities from samples. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS\u201920)(LIPIcs, Vol. 151). 60:1\u201360:10."},{"key":"e_1_3_4_54_2","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993150"},{"key":"e_1_3_4_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120585"},{"key":"e_1_3_4_56_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2020.1083"},{"key":"e_1_3_4_57_2","article-title":"A note on concentration of submodular functions","volume":"1005","author":"Vondr\u00e1k Jan","year":"2010","unstructured":"Jan Vondr\u00e1k. 2010. A note on concentration of submodular functions. CoRR abs\/1005.2791 (2010). arXiv:1005.2791","journal-title":"CoRR"},{"key":"e_1_3_4_58_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.56"},{"key":"e_1_3_4_59_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717076","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717076","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:18:55Z","timestamp":1750295935000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717076"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,9]]},"references-count":58,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1145\/3717076"],"URL":"https:\/\/doi.org\/10.1145\/3717076","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2025,4,9]]},"assertion":[{"value":"2024-01-22","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-26","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}