{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:43:02Z","timestamp":1787341382485,"version":"build-2736575974"},"reference-count":54,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","funder":[{"DOI":"10.13039\/100008047","name":"Carnegie Mellon University","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100008047","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["FA9550-12-1-0423"],"award-info":[{"award-number":["FA9550-12-1-0423"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["SIMPLEX"],"award-info":[{"award-number":["SIMPLEX"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1053605"],"award-info":[{"award-number":["CCF-1053605"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1546108"],"award-info":[{"award-number":["IIS-1546108"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1161365"],"award-info":[{"award-number":["CCF-1161365"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1319811"],"award-info":[{"award-number":["CCF-1319811"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF1536002"],"award-info":[{"award-number":["CCF1536002"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1617790"],"award-info":[{"award-number":["CCF-1617790"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2327010"],"award-info":[{"award-number":["CCF-2327010"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2024,12,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>The secretary and the prophet inequality problems are central to the field of stopping theory. Recently, there has been a lot of work in generalizing these models to multiple items because of their applications in mechanism design. The most important of these generalizations are to matroids and to combinatorial auctions.\u00a0Kleinberg and Weinberg and Feldman, Gravin, and Lucier show that for adversarial arrival order of random variables the optimal prophet inequalities give a [Formula: see text]-approximation. For many settings, however, it is conceivable that the arrival order is chosen uniformly at random, akin to the secretary problem. For such a random arrival model, we improve upon the [Formula: see text]-approximation and obtain [Formula: see text]-approximation prophet inequalities for both matroids and combinatorial auctions. This also gives improvements to the results of Yan and of Esfandiari and colleagues who worked in the special cases where either we can fully control the arrival order or there is only a single item. Our techniques are threshold based. We convert our discrete problem into a continuous setting and then give a generic template on how to dynamically adjust these thresholds to lower bound the expected total welfare.<\/jats:p>","DOI":"10.1137\/19m1264047","type":"journal-article","created":{"date-parts":[[2024,11,12]],"date-time":"2024-11-12T04:11:06Z","timestamp":1731384666000},"page":"1641-1662","source":"Crossref","is-referenced-by-count":1,"title":["Prophet Secretary for Combinatorial Auctions and Matroids"],"prefix":"10.1137","volume":"53","author":[{"given":"Soheil","family":"Ehsani","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Maryland, College Park, MD 20742 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammadtaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Maryland, College Park, MD 20742 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9420-9424","authenticated-orcid":true,"given":"Thomas","family":"Kesselheim","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, University of Bonn, 53115 Bonn, Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8800-6479","authenticated-orcid":true,"given":"Sahil","family":"Singla","sequence":"additional","affiliation":[{"name":"School of Computer Science, Georgia Institute of Technology, Atlanta, GA 30332 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,11,12]]},"reference":[{"key":"ref1","doi-asserted-by":"crossref","unstructured":"M. Abolhassani, S. Ehsani, H. Esfandiari, M. HajiAghayi, R. Kleinberg, and B. Lucier, Beating \\(1-1\/e\\) for ordered prophets, in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, ACM, 2017, pp. 61\u201371.","DOI":"10.1145\/3055399.3055479"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1137\/120878422"},{"key":"ref3","doi-asserted-by":"crossref","unstructured":"S. Alaei, M. Hajiaghayi, and V. Liaghat, Online prophet-inequality matching with applications to ad allocation, in Proceedings of the 13th ACM Conference on Electronic Commerce, ACM, 2012, pp. 18\u201335.","DOI":"10.1145\/2229012.2229018"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1080\/07474940701620857"},{"key":"ref5","first-page":"22","volume-title":"Combinatorial Auctions","volume":"17","author":"Ausubel L. M.","year":"2006"},{"key":"ref6","doi-asserted-by":"crossref","unstructured":"Y. Azar, A. Chiplunkar, and H. Kaplan, Prophet secretary: Surpassing the \\(1-1\/e\\) barrier, in Proceedings of the 2018 ACM Conference on Economics and Computation, EC, 2018, pp. 303\u2013318.","DOI":"10.1145\/3219166.3219182"},{"key":"ref7","unstructured":"M. Babaioff, N. Immorlica, and R. Kleinberg, Matroids, secretary problems, and online mechanisms, in Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, ACM, New York, SIAM, Philadelphia, 2007, pp. 434\u2013443."},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15369-3_4"},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"S. Chawla, J. D. Hartline, D. L. Malec, and B. Sivan, Multi-parameter mechanism design and sequential posted pricing, in Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC, 2010, pp. 311\u2013320.","DOI":"10.1145\/1806689.1806733"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"J. Correa, P. Foncea, R. Hoeksma, T. Oosterwijk, and T. Vredeveld, Posted price mechanisms for a random stream of customers, in Proceedings of the 2017 ACM Conference on Economics and Computation, ACM, 2017, pp. 169\u2013186.","DOI":"10.1145\/3033274.3085137"},{"key":"ref11","doi-asserted-by":"crossref","unstructured":"J. Correa, R. Saona, and B. Ziliotto, Prophet secretary through blind strategies, in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, ACM, New York, SIAM, Philadelphia, 2019, pp. 1946\u20131961, https:\/\/doi.org\/10.1137\/1.9781611975482.118.","DOI":"10.1137\/1.9781611975482.118"},{"key":"ref12","unstructured":"S. Dehghani, S. Ehsani, M. Hajiaghayi, V. Liaghat, and S. Seddighin, Greedy Algorithms for Online Survivable Network Design, ICALP (2018), pp. 152:1\u2013152:14."},{"key":"ref13","series-title":"LIPIcs. Leibniz Int. Proc. Inform. 80","first-page":"126","volume-title":"ICALP 2017","author":"Dehghani S.","year":"2017"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1090.0436"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"P. D\u00fctting, M. Feldman, T. Kesselheim, and B. Lucier, Prophet inequalities made easy: Stochastic optimization by pricing non-stochastic inputs, in IEEE 58th Annual Symposium on Foundations of Computer Science, FOCS, 2017, pp. 540\u2013551.","DOI":"10.1109\/FOCS.2017.56"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_37"},{"key":"ref17","first-page":"627","volume":"4","author":"Dynkin E. B.","year":"1963","journal-title":"Soviet Math. Dokl."},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1137\/15M1029394"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1137\/070680977"},{"key":"ref20","doi-asserted-by":"crossref","unstructured":"M. Feldman, N. Gravin, and B. Lucier, Combinatorial auctions via posted prices, in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2015, pp. 123\u2013135, https:\/\/doi.org\/10.1137\/1.9781611973730.10.","DOI":"10.1137\/1.9781611973730.10"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"M. Feldman, O. Svensson, and R. Zenklusen, A simple \\(O(\\log \\log (\\textrm{rank}))\\)-competitive algorithm for the matroid secretary problem, in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2015, pp. 1189\u20131201, https:\/\/doi.org\/10.1137\/1.9781611973730.79.","DOI":"10.1137\/1.9781611973730.79"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1137\/21M1411822"},{"key":"ref23","doi-asserted-by":"crossref","unstructured":"M. Feldman and R. Zenklusen, The submodular secretary problem goes linear, in IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2015, pp. 486\u2013505.","DOI":"10.1109\/FOCS.2015.37"},{"key":"ref24","doi-asserted-by":"crossref","unstructured":"B. Gamlath, S. Kale, and O. Svensson, Beating greedy for stochastic bipartite matching, in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, T. M. Chan, ed. ACM, New York, SIAM, Philadelphia, 2019, pp. 2841\u20132854, https:\/\/doi.org\/10.1137\/1.9781611975482.176.","DOI":"10.1137\/1.9781611975482.176"},{"key":"ref25","unstructured":"N. Garg, A. Gupta, S. Leonardi, and P. Sankowski, Stochastic analyses for online combinatorial optimization problems, in Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2008, pp. 942\u2013951."},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43951-7_43"},{"key":"ref27","unstructured":"G. Goel and A. Mehta, Online budgeted matching in random input models with applications to Adwords, in Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2008, pp. 982\u2013991."},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17572-5_20"},{"key":"ref29","doi-asserted-by":"crossref","unstructured":"G. P. Guruganesh and S. Singla, Online matroid intersection: Beating half for random arrival, in International Conference on Integer Programming and Combinatorial Optimization, Springer, 2017, pp. 241\u2013253.","DOI":"10.1007\/978-3-319-59250-3_20"},{"key":"ref30","doi-asserted-by":"crossref","unstructured":"M. T. Hajiaghayi, R. Kleinberg, and D. C. Parkes, Adaptive limited-supply online auctions, in Proceedings of the 5th ACM Conference on Electronic Commerce, ACM, 2004, pp. 71\u201380.","DOI":"10.1145\/988772.988784"},{"key":"ref31","unstructured":"M. T. Hajiaghayi, R. Kleinberg, and T. Sandholm, Automated online mechanism design and prophet inequalities, in AAAI\u201907: Proceedings of the 22nd National Conference on Artificial Intelligence, 2007, pp. 58\u201365."},{"key":"ref32","author":"Harb E.","year":"2023","journal-title":"CoRR 2307"},{"key":"ref33","doi-asserted-by":"crossref","unstructured":"C. Karande, A. Mehta, and P. Tripathi, Online bipartite matching with unknown distributions, in Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, ACM, 2011, pp. 587\u2013596.","DOI":"10.1145\/1993636.1993715"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4149(87)90029-9"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993009"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.2307\/1427302"},{"key":"ref37","doi-asserted-by":"crossref","unstructured":"T. Kesselheim, K. Radke, A. T\u00f6nnis, and B. V\u00f6cking, An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions, in European Symposium on Algorithms, Springer, 2013, pp. 589\u2013600.","DOI":"10.1007\/978-3-642-40450-4_50"},{"key":"ref38","unstructured":"R. Kleinberg, A multiple-choice secretary algorithm with applications to online auctions, in Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2005, pp. 630\u2013631."},{"key":"ref39","doi-asserted-by":"crossref","unstructured":"R. Kleinberg and S. M. Weinberg, Matroid prophet inequalities, in Proceedings of the 44th Symposium on Theory of Computing Conference, STOC, 2012, pp. 123\u2013136.","DOI":"10.1145\/2213977.2213991"},{"key":"ref40","doi-asserted-by":"crossref","unstructured":"N. Korula, V. Mirrokni, and M. Zadimoghaddam, Online submodular welfare maximization: Greedy beats \\(1\/2\\) in random order, in Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, ACM, 2015, pp. 889\u2013898.","DOI":"10.1145\/2746539.2746626"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02930-1_42"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1977-14378-4"},{"key":"ref43","unstructured":"U. Krengel and L. Sucheston, On semiamarts, amarts, and processes with finite value, in Probability on Banach Spaces, Adv. Probab. Related Topics 4, Marcel Dekker, New York, 1978, pp. 197\u2013266."},{"key":"ref44","doi-asserted-by":"crossref","unstructured":"O. Lachish, \\(O(\\log \\log rank)\\) competitive ratio for the matroid secretary problem, in Proceedings of the Fifty-Fifth Annual IEEE Symposium on Foundations of Computer Science, 2014, pp. 326\u2013335.","DOI":"10.1109\/FOCS.2014.42"},{"key":"ref45","unstructured":"E. Lee and S. Singla, Optimal online contention resolution schemes via ex-ante prophet inequalities, in Proceedings of 26th Annual European Symposium on Algorithms, ESA, LIPIcs 112, 2018, 57."},{"key":"ref46","doi-asserted-by":"crossref","unstructured":"B. Lucier and A. Borodin, Price of anarchy for greedy auctions, in Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2010, pp. 537\u2013553, https:\/\/doi.org\/10.1137\/1.9781611973075.46.","DOI":"10.1137\/1.9781611973075.46"},{"key":"ref47","doi-asserted-by":"crossref","unstructured":"M. Mahdian and Q. Yan, Online bipartite matching with random arrivals: An approach based on strongly factor-revealing LPs, in Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, ACM, 2011, pp. 597\u2013606.","DOI":"10.1145\/1993636.1993716"},{"key":"ref48","doi-asserted-by":"crossref","unstructured":"A. Meyerson, Online facility location, in Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, IEEE, 2001, pp. 426\u2013431.","DOI":"10.1109\/SFCS.2001.959917"},{"key":"ref49","doi-asserted-by":"crossref","unstructured":"N. Nisan, Bidding and allocation in combinatorial auctions, in Proceedings of the 2nd ACM Conference on Electronic Commerce (EC), A. Jhingran, J. MacKie-Mason, and D. J. Tygar, eds. ACM, 2000, pp. 1\u201312.","DOI":"10.1145\/352871.352872"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1070.0384"},{"key":"ref52","doi-asserted-by":"crossref","unstructured":"A. Rubinstein, 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.","DOI":"10.1145\/2897518.2897540"},{"key":"ref53","doi-asserted-by":"crossref","unstructured":"A. Rubinstein and S. Singla, Combinatorial prophet inequalities, in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2017, pp. 1671\u20131687, https:\/\/doi.org\/10.1137\/1.9781611974782.110.","DOI":"10.1137\/1.9781611974782.110"},{"key":"ref54","doi-asserted-by":"crossref","unstructured":"Q. Yan, Mechanism design via correlation gap, in Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2011, pp. 710\u2013719, https:\/\/doi.org\/10.1137\/1.9781611973082.56.","DOI":"10.1137\/1.9781611973082.56"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1264047","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:16:06Z","timestamp":1787339766000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1264047"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,12]]},"references-count":54,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1137\/19M1264047"],"URL":"https:\/\/doi.org\/10.1137\/19m1264047","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,12]]}}}