{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:34Z","timestamp":1787337574685,"version":"build-2736575974"},"reference-count":42,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1350900"],"award-info":[{"award-number":["CCF-1350900"]}],"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-2009060"],"award-info":[{"award-number":["CCF-2009060"]}],"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":[[2025,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We show that the matroid secretary problem is equivalent to correlated contention resolution in the online random-order model. Specifically, the matroid secretary conjecture is true if and only if every matroid admits an online random-order contention resolution scheme which, given an arbitrary (possibly correlated) prior distribution over subsets of the ground set, matches the balance ratio of the best offline scheme for that distribution up to a constant. Integral to our result is a polyhedral characterization of the (correlated) distributions permitting offline contention resolution over a given matroid\u2014we refer to these distributions as uncontentious. Our characterization can be viewed as a distributional generalization of the matroid covering theorem and isolates the kind and degree of positive correlation that is benign for offline contention resolution. Using this characterization, we are able to show that the set of improving elements for a subsample of a weighted matroid is uncontentious\u2014a fact that serves as a key technical component of our result. One direction of our equivalence is relatively straightforward: a competitive secretary algorithm yields a random-order contention resolution scheme\u2014one which approximately matches the best possible offline balance ratio\u2014by providing an approximate solution to its dual. The other direction is more technical and involves a composition of three reductions each of which isolates a technical hurdle: from the secretary problem to the (correlated) prophet secretary problem, then from that to a labeled generalization of (random-order) contention resolution, and finally from labeled contention resolution to its unlabeled counterpart. The uncontentiousness of the set of improving elements implies that the resulting contention resolution problem features an (offline) uncontentious distribution, which therefore implies our main result. One interpretation of our result is that handling the positive correlation inherent to uncontentious distributions is the key technical barrier to resolving the matroid secretary conjecture.<\/jats:p>","DOI":"10.1137\/24m1630207","type":"journal-article","created":{"date-parts":[[2025,5,9]],"date-time":"2025-05-09T03:12:37Z","timestamp":1746760357000},"page":"585-624","source":"Crossref","is-referenced-by-count":3,"title":["From Contention Resolution to Matroid Secretary and Back"],"prefix":"10.1137","volume":"54","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2784-1868","authenticated-orcid":true,"given":"Shaddin","family":"Dughmi","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Southern California, Los Angeles, CA 90089 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,5,9]]},"reference":[{"key":"ref1","doi-asserted-by":"crossref","unstructured":"M. Adamczyk and M. W\u0142odarczyk, Random order contention resolution schemes, in Proceedings of the 59th Annual Symposium on Foundations of Computer Science, IEEE, 2018, pp. 790\u2013801.","DOI":"10.1109\/FOCS.2018.00080"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1110.1011"},{"key":"ref3","doi-asserted-by":"crossref","unstructured":"Y. Azar, A. Chiplunkar, and H. Kaplan, Prophet secretary: Surpassing the 1-1\/e barrier, in Proceedings of the Conference on Economics and Computation, ACM, 2018, pp. 303\u2013318.","DOI":"10.1145\/3219166.3219182"},{"key":"ref4","unstructured":"M. Babaioff, N. Immorlica, and R. Kleinberg, Matroids, secretary problems, and online mechanisms, in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2007, pp. 434\u2013443."},{"key":"ref5","unstructured":"C. Bechtel and S. Dughmi, Delegated stochastic probing, in Proceedings of the Conference on Innovations in Theoretical Computer Science, 2021."},{"key":"ref6","doi-asserted-by":"crossref","unstructured":"C. Bechtel, S. Dughmi, and N. Patel, Delegated pandora\u2019s box, in Proceedings of the 23rd ACM Conference on Economics and Computation, 2022, pp. 666\u2013693.","DOI":"10.1145\/3490486.3538267"},{"key":"ref7","doi-asserted-by":"crossref","unstructured":"Y. Cai and A. Oikonomou, On simple mechanisms for dependent items, in Proceedings of the 22nd ACM Conference on Economics and Computation, ACM, New York, 2021, pp. 242\u2013262.","DOI":"10.1145\/3465456.3467643"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"I. Caragiannis, N. Gravin, P. Lu, and Z. Wang, Relaxing the independence assumption in sequential posted pricing, prophet inequality, and random bipartite matching, in International Conference on Web and Internet Economics, Springer, New York, 2021, pp. 131\u2013148.","DOI":"10.1007\/978-3-030-94676-0_8"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2024.114814"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"C. Chekuri, J. Vondr\u00e1k, and R. Zenklusen, Dependent randomized rounding via exchange properties of combinatorial structures, in Proceedings of the 51st Annual Symposium on Foundations of Computer Science, IEEE, 2010, pp. 575\u2013584.","DOI":"10.1109\/FOCS.2010.60"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1137\/110839655"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1145\/2491533.2491557"},{"key":"ref13","volume-title":"Proceedings of the 50th International Colloquium on Automata, Languages, and Programming","author":"Dughmi S.","year":"2023"},{"key":"ref14","doi-asserted-by":"crossref","unstructured":"S. Dughmi, Y. H. Kalayci, and N. Patel, Limitations of Stochastic selection with pairwise independent priors, in Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024.","DOI":"10.1145\/3618260.3649718"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_37"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1137\/20M1323850"},{"key":"ref17","first-page":"627","volume":"4","author":"Dynkin E. B.","year":"1963","journal-title":"Soviet Math."},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.6028\/jres.069B.004"},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"S. Ehsani, M. Hajiaghayi, T. Kesselheim, and S. Singla, Prophet secretary for combinatorial auctions and matroids, in Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2018, pp. 700\u2013714.","DOI":"10.1137\/1.9781611975031.46"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1137\/15M1029394"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"M. Feldman, O. Svensson, and R. Zenklusen, A simple o (log log (rank))-competitive algorithm for the matroid secretary problem, in Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2014, pp. 1189\u20131201.","DOI":"10.1137\/1.9781611973730.79"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch72"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9795-y"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/125\/1160620"},{"key":"ref25","volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik","author":"Hoefer M.","year":"2017"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0865-5_26"},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"N. Immorlica, S. Singla, and B. Waggoner, Prophet inequalities with linear correlations and augmentations, in Proceedings of the ACM Conference on Economics and Computation, ACM, 2020.","DOI":"10.1145\/3391403.3399452"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585865"},{"key":"ref29","doi-asserted-by":"crossref","unstructured":"R. Kleinberg and S. M. Weinberg, Matroid prophet inequalities, in Proceedings of the 44th Annual ACM Symposium on Theory of Computing, ACM, 2012, pp. 123\u2013136.","DOI":"10.1145\/2213977.2213991"},{"key":"ref30","first-page":"630","volume-title":"Proceedings of SODA","author":"Kleinberg R. D.","year":"2005"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1977-14378-4"},{"key":"ref32","first-page":"197","volume":"4","author":"Krengel U.","year":"1978","journal-title":"Probab. Banach Spaces"},{"key":"ref33","doi-asserted-by":"crossref","unstructured":"O. Lachish, O (log log rank) competitive ratio for the matroid secretary problem, in Proceedings of the 55th Annual Symposium on Foundations of Computer Science, IEEE, 2014, pp. 326\u2013335.","DOI":"10.1109\/FOCS.2014.42"},{"key":"ref34","unstructured":"E. Lee and S. Singla, Optimal online contention resolution schemes via ex-ante prophet inequalities, in Proceedings of the 26th Annual European Symposium on Algorithms, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018."},{"key":"ref35","doi-asserted-by":"crossref","unstructured":"V. Livanos, K. Patton, and S. Singla, Improved mechanisms and prophet inequalities for graphical dependencies, in Proceedings of the 25th ACM Conference on Economics and Computation, ACM, 2024.","DOI":"10.1145\/3670865.3673462"},{"key":"ref36","volume-title":"Matroid Theory","author":"Oxley J. G.","year":"1992"},{"key":"ref37","first-page":"44:1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Qiu F.","year":"2022"},{"key":"ref38","first-page":"1482","volume":"15","author":"Rinott and Y.","year":"1987","journal-title":"Ann. Statist."},{"key":"ref39","doi-asserted-by":"crossref","unstructured":"A. Rubinstein, Beyond matroids: Secretary problem and prophet inequality with general constraints, in Proceedings of the 48th Annual ACM Symposium on Theory of Computing, ACM, 2016, pp. 324\u2013332.","DOI":"10.1145\/2897518.2897540"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1016\/0167-7152(91)90080-B"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2020.1083"},{"key":"ref42","volume-title":"Matroid Theory","author":"Welsh D. J.","year":"2010"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/24M1630207","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:18:28Z","timestamp":1787336308000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1630207"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,9]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1137\/24M1630207"],"URL":"https:\/\/doi.org\/10.1137\/24m1630207","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,9]]}}}