{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:07:04Z","timestamp":1750694824833,"version":"3.40.3"},"publisher-location":"Cham","reference-count":41,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031710322"},{"type":"electronic","value":"9783031710339"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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-71033-9_23","type":"book-chapter","created":{"date-parts":[[2024,9,3]],"date-time":"2024-09-03T00:02:17Z","timestamp":1725321737000},"page":"405-422","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Matroid Bayesian Online Selection"],"prefix":"10.1007","author":[{"given":"Ian","family":"DeHaan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kanstantsin","family":"Pashkovich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,8,31]]},"reference":[{"key":"23_CR1","doi-asserted-by":"crossref","unstructured":"Abolhassani, M., Ehsani, S., Esfandiari, H., Hajiaghayi, M., Kleinberg, R., Lucier, B.: Beating 1-1\/e for ordered prophets. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 61\u201371 (2017)","DOI":"10.1145\/3055399.3055479"},{"key":"23_CR2","doi-asserted-by":"publisher","unstructured":"Agrawal, S., Sethuraman, J., Zhang, X.: On optimal ordering in the optimal stopping problem. In: Proceedings of the 21st ACM Conference on Economics and Computation, EC 2020, pp. 187\u2013188. Association for Computing Machinery, New York (2020). https:\/\/doi.org\/10.1145\/3391403.3399484","DOI":"10.1145\/3391403.3399484"},{"key":"23_CR3","doi-asserted-by":"publisher","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)https:\/\/doi.org\/10.1109\/FOCS.2011.90","DOI":"10.1109\/FOCS.2011.90"},{"key":"23_CR4","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, pp. 18\u201335 (2012)","DOI":"10.1145\/2229012.2229018"},{"key":"23_CR5","doi-asserted-by":"crossref","unstructured":"Anari, N., Niazadeh, R., Saberi, A., Shameli, A.: Nearly optimal pricing algorithms for production constrained and laminar Bayesian selection. In: Proceedings of the 2019 ACM Conference on Economics and Computation, pp. 91\u201392 (2019)","DOI":"10.1145\/3328526.3329652"},{"key":"23_CR6","doi-asserted-by":"crossref","unstructured":"Azar, P.D., Kleinberg, R., Weinberg, S.M.: Prophet inequalities with limited information. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM symposium on Discrete algorithms, pp. 1358\u20131377. SIAM (2014)","DOI":"10.1137\/1.9781611973402.100"},{"key":"23_CR7","doi-asserted-by":"crossref","unstructured":"Azar, Y., Chiplunkar, A., Kaplan, H.: Prophet secretary: surpassing the 1-1\/e barrier. In: Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 303\u2013318 (2018)","DOI":"10.1145\/3219166.3219182"},{"key":"23_CR8","doi-asserted-by":"publisher","unstructured":"Braverman, M., Derakhshan, M., Molina\u00a0Lovett, A.: Max-weight online stochastic matching: improved approximations against the online benchmark. In: Proceedings of the 23rd ACM Conference on Economics and Computation, EC 2022, pp. 967\u2013985. Association for Computing Machinery, New York (2022). https:\/\/doi.org\/10.1145\/3490486.3538315","DOI":"10.1145\/3490486.3538315"},{"key":"23_CR9","unstructured":"Chawla, S., Goldner, K., Karlin, A.R., Miller, J.B.: Non-adaptive matroid prophet inequalities. arXiv preprint arXiv:2011.09406 (2020)"},{"key":"23_CR10","doi-asserted-by":"crossref","unstructured":"Correa, J., Foncea, P., Hoeksma, R., Oosterwijk, T., Vredeveld, T.: Posted price mechanisms for a random stream of customers. In: Proceedings of the 2017 ACM Conference on Economics and Computation, pp. 169\u2013186 (2017)","DOI":"10.1145\/3033274.3085137"},{"issue":"1","key":"23_CR11","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1145\/3331033.3331039","volume":"17","author":"J Correa","year":"2019","unstructured":"Correa, J., Foncea, P., Hoeksma, R., Oosterwijk, T., Vredeveld, T.: Recent developments in prophet inequalities. SIGecom Exch. 17(1), 61\u201370 (2019). https:\/\/doi.org\/10.1145\/3331033.3331039","journal-title":"SIGecom Exch."},{"issue":"1\u20132","key":"23_CR12","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/s10107-020-01544-8","volume":"190","author":"J Correa","year":"2021","unstructured":"Correa, J., Saona, R., Ziliotto, B.: Prophet secretary through blind strategies. Math. Program. 190(1\u20132), 483\u2013521 (2021)","journal-title":"Math. Program."},{"key":"23_CR13","doi-asserted-by":"crossref","unstructured":"DeHaan, I., Pashkovich, K.: Matroid Bayesian online selection. arXiv preprint arXiv:2406.00224 (2024)","DOI":"10.1007\/978-3-031-71033-9_23"},{"key":"23_CR14","doi-asserted-by":"publisher","unstructured":"D\u00fctting, P., Gergatsouli, E., Rezvan, R., Teng, Y., Tsigonias-Dimitriadis, A.: Prophet secretary against the online optimal. In: Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, pp. 561\u2013581. Association for Computing Machinery, New York (2023). https:\/\/doi.org\/10.1145\/3580507.3597736","DOI":"10.1145\/3580507.3597736"},{"key":"23_CR15","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, pp. 700\u2013714. SIAM (2018)","DOI":"10.1137\/1.9781611975031.46"},{"issue":"3","key":"23_CR16","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":"23_CR17","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: Proceedings of the 21st ACM Conference on Economics and Computation, pp. 769\u2013787 (2020)","DOI":"10.1145\/3391403.3399513"},{"key":"23_CR18","doi-asserted-by":"crossref","unstructured":"Ezra, T., Feldman, M., Gravin, N., Tang, Z.G.: who is next in line? On the significance of knowing the arrival order in Bayesian online settings. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 3759\u20133776. SIAM (2023)","DOI":"10.1137\/1.9781611977554.ch145"},{"key":"23_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/978-3-031-48974-7_15","volume-title":"Web and Internet Economics","author":"T Ezra","year":"2023","unstructured":"Ezra, T., Garbuz, T.: The importance of knowing the arrival order in combinatorial Bayesian settings. In: Garg, J., Klimm, M., Kong, Y. (eds.) WINE 2023. LNCS, vol. 14413, pp. 256\u2013271. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-48974-7_15"},{"key":"23_CR20","doi-asserted-by":"crossref","unstructured":"Feldman, M., Svensson, O., Zenklusen, R.: Online contention resolution schemes. In: Proceedings of the twenty-seventh annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1014\u20131033. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch72"},{"key":"23_CR21","doi-asserted-by":"crossref","unstructured":"Feng, Y., Niazadeh, R., Saberi, A.: Two-stage stochastic matching with application to ride hailing. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2862\u20132877. SIAM (2021)","DOI":"10.1137\/1.9781611976465.170"},{"key":"23_CR22","doi-asserted-by":"crossref","unstructured":"Feng, Y., Niazadeh, R., Saberi, A.: Near-optimal Bayesian online assortment of reusable resources. In: Proceedings of the 23rd ACM Conference on Economics and Computation, pp. 964\u2013965 (2022)","DOI":"10.1145\/3490486.3538320"},{"key":"23_CR23","unstructured":"Fu, H., Li, J., Xu, P.: A PTAS for a class of stochastic dynamic programs. In: Chatzigiannakis, I., Kaklamanis, C., Marx, D., Sannella, D. (eds.) Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague, Czech Republic, pp. 1\u201356 (2018)"},{"key":"23_CR24","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, pp. 93\u2013109 (2019)","DOI":"10.1145\/3328526.3329604"},{"key":"23_CR25","unstructured":"Gupta, A.: Lecture Notes. IPCO Summer School (2017)"},{"key":"23_CR26","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, p. 58\u201365. AAAI Press (2007)"},{"key":"23_CR27","doi-asserted-by":"crossref","unstructured":"Hill, T.P., Kertz, R.P.: Comparisons of stop rule and supremum expectations of I.I.D. random variables. Ann. Probab. 10(2), 336\u2013345 (1982). http:\/\/www.jstor.org\/stable\/2243434","DOI":"10.1214\/aop\/1176993861"},{"issue":"1","key":"23_CR28","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1090\/conm\/125\/1160620","volume":"125","author":"TP Hill","year":"1992","unstructured":"Hill, T.P., Kertz, R.P.: A survey of prophet inequalities in optimal stopping theory. Contemp. Math. 125(1), 191\u2013207 (1992)","journal-title":"Contemp. Math."},{"key":"23_CR29","doi-asserted-by":"crossref","unstructured":"Kleinberg, R., Weinberg, S.M.: Matroid prophet inequalities. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, pp. 123\u2013136 (2012)","DOI":"10.1145\/2213977.2213991"},{"issue":"4","key":"23_CR30","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."},{"issue":"1","key":"23_CR31","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. SIGecom Exch. 16(1), 24\u201347 (2017). https:\/\/doi.org\/10.1145\/3144722.3144725","journal-title":"SIGecom Exch."},{"key":"23_CR32","unstructured":"Naor, J., Srinivasan, A., Wajc, D.: Online dependent rounding schemes (2023)"},{"key":"23_CR33","unstructured":"Oxley, J.G.: Matroid Theory. Oxford Graduate Texts in Mathematics. Oxford University Press (2006). https:\/\/books.google.ca\/books?id=puKta1Hdz-8C"},{"key":"23_CR34","doi-asserted-by":"publisher","unstructured":"Papadimitriou, C., Pollner, T., Saberi, A., Wajc, D.: Online stochastic max-weight bipartite matching: beyond prophet inequalities. In: Proceedings of the 22nd ACM Conference on Economics and Computation, EC 2021, pp. 763\u2013764. Association for Computing Machinery, New York (2021). https:\/\/doi.org\/10.1145\/3465456.3467613","DOI":"10.1145\/3465456.3467613"},{"key":"23_CR35","unstructured":"Pashkovich, K., Sayutina, A.: Non-adaptive matroid prophet inequalities. arXiv preprint arXiv:2301.01700 (2023)"},{"key":"23_CR36","doi-asserted-by":"crossref","unstructured":"Rubinstein, A.: Beyond matroids: secretary problem and prophet inequality with general constraints. In: Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, pp. 324\u2013332 (2016)","DOI":"10.1145\/2897518.2897540"},{"key":"23_CR37","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, pp. 1671\u20131687. SIAM (2017)","DOI":"10.1137\/1.9781611974782.110"},{"key":"23_CR38","unstructured":"Rubinstein, A., Wang, J.Z., Weinberg, S.M.: Optimal single-choice prophet inequalities from samples. arXiv preprint arXiv:1911.07945 (2019)"},{"key":"23_CR39","doi-asserted-by":"crossref","unstructured":"Samuel-Cahn, E.: Comparison of threshold stop rules and maximum for independent nonnegative random variables. Ann. Probab. 1213\u20131216 (1984)","DOI":"10.1214\/aop\/1176993150"},{"key":"23_CR40","doi-asserted-by":"crossref","unstructured":"Segev, D., Singla, S.: Efficient approximation schemes for stochastic probing and prophet problems. In: Proceedings of the 22nd ACM Conference on Economics and Computation, pp. 793\u2013794 (2021)","DOI":"10.1145\/3465456.3467614"},{"key":"23_CR41","unstructured":"Wajc, D.: Personal Communication (2023)"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Game Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-71033-9_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,27]],"date-time":"2024-11-27T17:54:16Z","timestamp":1732730056000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-71033-9_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031710322","9783031710339"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-71033-9_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"31 August 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SAGT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Algorithmic Game Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Amsterdam","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"The Netherlands","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 September 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sagt2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.cwi.nl\/en\/groups\/networks-and-optimization\/events\/sagt-2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}