{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T19:02:03Z","timestamp":1742929323837,"version":"3.40.3"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031489730"},{"type":"electronic","value":"9783031489747"}],"license":[{"start":{"date-parts":[[2023,12,31]],"date-time":"2023-12-31T00:00:00Z","timestamp":1703980800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,31]],"date-time":"2023-12-31T00:00:00Z","timestamp":1703980800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-48974-7_16","type":"book-chapter","created":{"date-parts":[[2023,12,30]],"date-time":"2023-12-30T18:01:32Z","timestamp":1703959292000},"page":"272-289","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Prophet Inequalities via\u00a0the\u00a0Expected Competitive Ratio"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0626-4851","authenticated-orcid":false,"given":"Tomer","family":"Ezra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9809-7191","authenticated-orcid":false,"given":"Stefano","family":"Leonardi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0959-2589","authenticated-orcid":false,"given":"Rebecca","family":"Reiffenh\u00e4user","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2047-4089","authenticated-orcid":false,"given":"Matteo","family":"Russo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7558-2215","authenticated-orcid":false,"given":"Alexandros","family":"Tsigonias-Dimitriadis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,12,31]]},"reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"Alaei, S.: Bayesian combinatorial auctions: expanding single buyer mechanisms to many buyers. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp. 512\u2013521 (2011)","DOI":"10.1109\/FOCS.2011.90"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Alaei, S., Hajiaghayi, M., Liaghat, V.: Online prophet-inequality matching with applications to ad allocation. In: Proceedings of the 13th ACM Conference on Electronic Commerce, EC 2012. ACM Press (2012)","DOI":"10.1145\/2229012.2229018"},{"key":"16_CR3","unstructured":"Babaioff, M., Immorlica, N., Kleinberg, R.: Matroids, secretary problems, and online mechanisms. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, pp. 434\u2013443. SIAM (2007)"},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"Blum, A., Caragiannis, I., Haghtalab, N., Procaccia, A.D., Procaccia, E.B., Vaish, R.: Opting into optimal matchings. In: Klein, P.N. (ed.) Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pp. 2351\u20132363. SIAM (2017)","DOI":"10.1137\/1.9781611974782.155"},{"issue":"3","key":"16_CR5","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1002\/(SICI)1098-2418(200005)16:3<277::AID-RSA4>3.0.CO;2-1","volume":"16","author":"S Boucheron","year":"2000","unstructured":"Boucheron, S., Lugosi, G., Massart, P.: A sharp concentration inequality with application. Random Struct. Algorithms 16(3), 277\u2013292 (2000)","journal-title":"Random Struct. Algorithms"},{"key":"16_CR6","doi-asserted-by":"crossref","unstructured":"Boucheron, S., Lugosi, G., Massart, P.: On concentration of self-bounding functions. Electron. J. Probab. 14 (2009)","DOI":"10.1214\/EJP.v14-690"},{"key":"16_CR7","doi-asserted-by":"crossref","unstructured":"Chawla, S., Hartline, J.D., Malec, D.L., Sivan, B.: Multi-parameter mechanism design and sequential posted pricing. In: Schulman, L.J. (ed.) Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010. ACM (2010)","DOI":"10.1145\/1806689.1806733"},{"key":"16_CR8","unstructured":"Chekuri, C., Livanos, V.: On submodular prophet inequalities and correlation gap. In: Algorithmic Game Theory - 14th International Symposium, SAGT 2021. Lecture Notes in Computer Science, vol. 12885, p. 410. Springer, Cham (2021)"},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"Correa, J., Foncea, P., Hoeksma, R., Oosterwijk, T., Vredeveld, T.: Recent developments in prophet inequalities. SIGecom Exch. 17(1), 61\u201370 (2019)","DOI":"10.1145\/3331033.3331039"},{"issue":"1","key":"16_CR10","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.orl.2018.11.010","volume":"47","author":"J Correa","year":"2019","unstructured":"Correa, J., Foncea, P., Pizarro, D., Verdugo, V.: From pricing to prophets, and back! Oper. Res. Lett. 47(1), 25\u201329 (2019)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"16_CR11","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1137\/20M1323850","volume":"49","author":"P D\u00fctting","year":"2020","unstructured":"D\u00fctting, P., Feldman, M., Kesselheim, T., Lucier, B.: Prophet inequalities made easy: stochastic optimization by pricing nonstochastic inputs. SIAM J. Comput. 49(3), 540\u2013582 (2020)","journal-title":"SIAM J. Comput."},{"key":"16_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/978-3-662-48350-3_37","volume-title":"Algorithms - ESA 2015","author":"P D\u00fctting","year":"2015","unstructured":"D\u00fctting, P., Kleinberg, R.: Polymatroid prophet inequalities. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 437\u2013449. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48350-3_37"},{"key":"16_CR13","doi-asserted-by":"crossref","unstructured":"Ehsani, S., Hajiaghayi, M., Kesselheim, T., Singla, S.: Prophet secretary for combinatorial auctions and matroids. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. SIAM (2018)","DOI":"10.1137\/1.9781611975031.46"},{"issue":"3","key":"16_CR14","doi-asserted-by":"publisher","first-page":"1685","DOI":"10.1137\/15M1029394","volume":"31","author":"H Esfandiari","year":"2017","unstructured":"Esfandiari, H., Hajiaghayi, M., Liaghat, V., Monemizadeh, M.: Prophet secretary. SIAM J. Discret. Math. 31(3), 1685\u20131701 (2017)","journal-title":"SIAM J. Discret. Math."},{"key":"16_CR15","unstructured":"Esfandiari, H., Hajiaghayi, M., Lucier, B., Mitzenmacher, M.: Prophets, secretaries, and maximizing the probability of choosing the best. In: The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020. Proceedings of Machine Learning Research, vol. 108, pp. 3717\u20133727. PMLR (2020)"},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"Ezra, T., Feldman, M., Gravin, N., Tang, Z.G.: Online stochastic max-weight matching: prophet inequality for vertex and edge arrival models. In: EC 2020: The 21st ACM Conference on Economics and Computation, pp. 769\u2013787. ACM (2020)","DOI":"10.1145\/3391403.3399513"},{"key":"16_CR17","doi-asserted-by":"crossref","unstructured":"Ezra, T., Leonardi, S., Reiffenh\u00e4user, R., Russo, M., Tsigonias-Dimitriadis, A.: Prophet inequalities via the expected competitive ratio. CoRR abs\/2207.03361 (2022)","DOI":"10.1007\/978-3-031-48974-7_16"},{"key":"16_CR18","doi-asserted-by":"crossref","unstructured":"Feldman, M., Gravin, N., Lucier, B.: Combinatorial auctions via posted prices. In: Indyk, P. (ed.) Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, pp. 123\u2013135. SIAM (2015)","DOI":"10.1137\/1.9781611973730.10"},{"issue":"2","key":"16_CR19","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1137\/18M1226130","volume":"50","author":"M Feldman","year":"2021","unstructured":"Feldman, M., Svensson, O., Zenklusen, R.: Online contention resolution schemes with applications to Bayesian selection problems. SIAM J. Comput. 50(2), 255\u2013300 (2021)","journal-title":"SIAM J. Comput."},{"key":"16_CR20","unstructured":"Garg, N., Gupta, A., Leonardi, S., Sankowski, P.: Stochastic analyses for online combinatorial optimization problems. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, pp. 942\u2013951 (2008)"},{"issue":"313","key":"16_CR21","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1080\/01621459.1966.10502008","volume":"61","author":"JP Gilbert","year":"1966","unstructured":"Gilbert, J.P., Mosteller, F.: Recognizing the maximum of a sequence. J. Am. Stat. Assoc. 61(313), 35\u201373 (1966)","journal-title":"J. Am. Stat. Assoc."},{"key":"16_CR22","doi-asserted-by":"crossref","unstructured":"Gravin, N., Wang, H.: Prophet inequality for bipartite matching: merits of being simple and non adaptive. In: Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, pp. 93\u2013109. ACM (2019)","DOI":"10.1145\/3328526.3329604"},{"key":"16_CR23","unstructured":"Hajiaghayi, M.T., Kleinberg, R., Sandholm, T.: Automated online mechanism design and prophet inequalities. In: Proceedings of the 22nd National Conference on Artificial Intelligence, AAAI 2007, vol. 1, pp. 58\u201365. AAAI Press (2007)"},{"key":"16_CR24","unstructured":"Hartline, J., Johnsen, A.: Lower bounds for prior independent algorithms (2021)"},{"key":"16_CR25","doi-asserted-by":"crossref","unstructured":"Hill, T.P., Kertz, R.P.: A survey of prophet inequalities in optimal stopping theory. Contemp. Math. 125 (1992)","DOI":"10.1090\/conm\/125\/1160620"},{"key":"16_CR26","doi-asserted-by":"crossref","unstructured":"Jiang, J., Ma, W., Zhang, J.: Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack. In: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2022)","DOI":"10.1137\/1.9781611977073.51"},{"key":"16_CR27","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.geb.2014.11.002","volume":"113","author":"R Kleinberg","year":"2019","unstructured":"Kleinberg, R., Weinberg, S.M.: Matroid prophet inequalities and applications to multi-dimensional mechanism design. Games Econ. Behav. 113, 97\u2013115 (2019)","journal-title":"Games Econ. Behav."},{"issue":"4","key":"16_CR28","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1090\/S0002-9904-1977-14378-4","volume":"83","author":"U Krengel","year":"1977","unstructured":"Krengel, U., Sucheston, L.: Semiamarts and finite values. Bull. Am. Math. Soc. 83(4), 745\u2013747 (1977)","journal-title":"Bull. Am. Math. Soc."},{"key":"16_CR29","first-page":"197","volume":"4","author":"U Krengel","year":"1978","unstructured":"Krengel, U., Sucheston, L.: On semiamarts, amarts, and processes with finite value. Adv. Probab. Relat. Top. 4, 197\u2013266 (1978)","journal-title":"Adv. Probab. Relat. Top."},{"issue":"1","key":"16_CR30","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/3144722.3144725","volume":"16","author":"B Lucier","year":"2017","unstructured":"Lucier, B.: An economic view of prophet inequalities. ACM SIGecom Exchanges 16(1), 24\u201347 (2017)","journal-title":"ACM SIGecom Exchanges"},{"key":"16_CR31","doi-asserted-by":"crossref","unstructured":"Rubinstein, A.: Beyond matroids: secretary problem and prophet inequality with general constraints. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, pp. 324\u2013332. ACM (2016)","DOI":"10.1145\/2897518.2897540"},{"key":"16_CR32","doi-asserted-by":"crossref","unstructured":"Rubinstein, A., Singla, S.: Combinatorial prophet inequalities. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pp. 1671\u20131687. SIAM (2017)","DOI":"10.1137\/1.9781611974782.110"},{"key":"16_CR33","doi-asserted-by":"crossref","unstructured":"Samuel-Cahn, E.: Comparison of threshold stop rules and maximum for independent nonnegative random variables. Ann. Probab. 12(4) (1984)","DOI":"10.1214\/aop\/1176993150"},{"issue":"1","key":"16_CR34","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1145\/1120582.1120585","volume":"53","author":"M Scharbrodt","year":"2006","unstructured":"Scharbrodt, M., Schickinger, T., Steger, A.: A new average case analysis for completion time scheduling. J. ACM 53(1), 121\u2013146 (2006)","journal-title":"J. ACM"},{"key":"16_CR35","unstructured":"Vondr\u00e1k, J.: A note on concentration of submodular functions (2010)"},{"key":"16_CR36","doi-asserted-by":"crossref","unstructured":"Yan, Q.: Mechanism design via correlation gap. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, pp. 710\u2013719 (2011)","DOI":"10.1137\/1.9781611973082.56"}],"container-title":["Lecture Notes in Computer Science","Web and Internet Economics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-48974-7_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,31]],"date-time":"2023-12-31T02:04:23Z","timestamp":1703988263000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-48974-7_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,31]]},"ISBN":["9783031489730","9783031489747"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-48974-7_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023,12,31]]},"assertion":[{"value":"31 December 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WINE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Web and Internet Economics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Shanghai","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 December 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 December 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wine2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/wine2023.shanghaitech.edu.cn\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"221","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"37","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"17% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"8","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"29 one-page abstracts accepted","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}