{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T23:31:53Z","timestamp":1783726313821,"version":"3.55.0"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2025,7,10]],"date-time":"2025-07-10T00:00:00Z","timestamp":1752105600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,7,10]],"date-time":"2025-07-10T00:00:00Z","timestamp":1752105600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2217069"],"award-info":[{"award-number":["CCF-2217069"]}],"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-1955785"],"award-info":[{"award-number":["CCF-1955785"]}],"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-2006953"],"award-info":[{"award-number":["CCF-2006953"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010629","name":"Fulbright Association","doi-asserted-by":"publisher","award":["Fulbright Israel Postdoctoral Fellowship"],"award-info":[{"award-number":["Fulbright Israel Postdoctoral Fellowship"]}],"id":[{"id":"10.13039\/100010629","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2026,3]]},"abstract":"Abstract<\/jats:title>\n \n We study online contention resolution schemes (OCRSes) and prophet inequalities for non-product distributions. Specifically, when the active set is sampled according to a\n pairwise-independent<\/jats:italic>\n (PI) distribution, we show a\n \n \n $$(1-o_k(1))$$<\/jats:tex-math>\n \n \n (<\/mml:mo>\n 1<\/mml:mn>\n -<\/mml:mo>\n \n o<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -selectable OCRS for uniform matroids of rank\n k<\/jats:italic>\n , and\n \n \n $$\\Omega (1)$$<\/jats:tex-math>\n \n \n \u03a9<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -selectable OCRSes for laminar, graphic, cographic, transversal, and regular matroids. These imply prophet inequalities with the same ratios when the set of values is drawn according to a PI distribution. Our results complement recent work of Dughmi et al. [2] showing that no\n \n \n $$\\omega (1\/k)$$<\/jats:tex-math>\n \n \n \u03c9<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n \/<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -selectable OCRS exists in the PI setting for general matroids of rank\n k<\/jats:italic>\n .\n <\/jats:p>","DOI":"10.1007\/s10107-025-02253-w","type":"journal-article","created":{"date-parts":[[2025,7,10]],"date-time":"2025-07-10T10:05:44Z","timestamp":1752141944000},"page":"295-338","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Pairwise-independent contention resolution"],"prefix":"10.1007","volume":"216","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jinqiao","family":"Hu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gregory","family":"Kehne","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2907-7186","authenticated-orcid":false,"given":"Roie","family":"Levin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,7,10]]},"reference":[{"key":"2253_CR1","doi-asserted-by":"crossref","unstructured":"Gupta, A., Hu, J., Kehne, G., Levin, R.: Pairwise-independent contention resolution. In: Integer Programming and Combinatorial Optimization - 25th International Conference, IPCO 2024, Wroc\u0142aw, Poland, July 3-5, 2024, Proceedings, vol. 14679, pp. 196\u2013209 (2024)","DOI":"10.1007\/978-3-031-59835-7_15"},{"key":"2253_CR2","doi-asserted-by":"crossref","unstructured":"Dughmi, S., Kalayci, Y.H., Patel, N.: Limitations of stochastic selection problems with pairwise independent priors. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pp. 479\u2013490 (2024)","DOI":"10.1145\/3618260.3649718"},{"key":"2253_CR3","first-page":"197","volume":"4","author":"U Krengel","year":"1978","unstructured":"Krengel, U., Sucheston, L.: On semiamarts, amarts, and processes with finite value. Probability on Banach Spaces. In: Adv. Probab. Related Topics 4, 197\u2013266 (1978)","journal-title":"In: Adv. Probab. Related Topics"},{"key":"2253_CR4","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 Econom. Behav. 113, 97\u2013115 (2019)","journal-title":"Games Econom. Behav."},{"key":"2253_CR5","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, SODA 2016, pp. 1014\u20131033 (2016)","DOI":"10.1137\/1.9781611974331.ch72"},{"key":"2253_CR6","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, Cambridge, MA, USA, June 18-21, 2016, pp. 324\u2013332 (2016)","DOI":"10.1145\/2897518.2897540"},{"issue":"3","key":"2253_CR7","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":"2253_CR8","doi-asserted-by":"crossref","unstructured":"Arsenis, M., Drosis, O., Kleinberg, R.: Constrained-order prophet inequalities. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pp. 2034\u20132046 (2021)","DOI":"10.1137\/1.9781611976465.121"},{"key":"2253_CR9","unstructured":"Giambartolomei, G., Mallmann-Trenn, F., Saona, R.: Prophet inequalities: Separating random order from order selection. CoRR abs\/2304.04024 (2023)"},{"key":"2253_CR10","doi-asserted-by":"crossref","unstructured":"Adamczyk, M., Wlodarczyk, M.: Random order contention resolution schemes. In: 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pp. 790\u2013801 (2018)","DOI":"10.1109\/FOCS.2018.00080"},{"key":"2253_CR11","unstructured":"Lee, E., Singla, S.: Optimal online contention resolution schemes via ex-ante prophet inequalities. In: 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, vol. 112, pp. 57\u201315714 (2018)"},{"issue":"4","key":"2253_CR12","doi-asserted-by":"publisher","first-page":"1452","DOI":"10.1287\/moor.2020.1105","volume":"46","author":"JR Correa","year":"2021","unstructured":"Correa, J.R., Foncea, P., Hoeksma, R., Oosterwijk, T., Vredeveld, T.: Posted price mechanisms and optimal threshold strategies for random arrivals. Math. Oper. Res. 46(4), 1452\u20131478 (2021)","journal-title":"Math. Oper. Res."},{"key":"2253_CR13","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, Barcelona, Spain, Hotel Porta Fira, January 16-19, pp. 1671\u20131687 (2017)","DOI":"10.1137\/1.9781611974782.110"},{"key":"2253_CR14","unstructured":"Goyal, V., Humair, S., Papadigenopoulos, O., Zeevi, A.: Mnl-prophet: Sequential assortment selection under uncertainty. CoRR arXiv: 2308.05207 (2023)"},{"key":"2253_CR15","doi-asserted-by":"crossref","unstructured":"Rinott, Y., Samuel-Cahn, E.: Optimal stopping values and prophet inequalities for some dependent random variables. In: Stochastic Inequalities (Seattle, WA, 1991). IMS Lecture Notes Monogr. Ser., vol. 22, pp. 343\u2013358 (1992)","DOI":"10.1214\/lnms\/1215461961"},{"issue":"4","key":"2253_CR16","doi-asserted-by":"publisher","first-page":"1482","DOI":"10.1214\/aos\/1176350605","volume":"15","author":"Y Rinott","year":"1987","unstructured":"Rinott, Y., Samuel-Cahn, E.: Comparisons of optimal stopping values and prophet inequalities for negatively dependent random variables. Ann. Statist. 15(4), 1482\u20131490 (1987)","journal-title":"Ann. Statist."},{"key":"2253_CR17","doi-asserted-by":"crossref","unstructured":"Hill, T.P., Kertz, R.P.: A survey of prophet inequalities in optimal stopping theory. In: Strategies for Sequential Search and Selection in Real Time (Amherst, MA, 1990). Contemp. Math., vol. 125, pp. 191\u2013207 (1992)","DOI":"10.1090\/conm\/125\/1160620"},{"key":"2253_CR18","doi-asserted-by":"crossref","unstructured":"Immorlica, N., Singla, S., Waggoner, B.: Prophet inequalities with linear correlations and augmentations. In: EC \u201920: The 21st ACM Conference on Economics and Computation, Virtual Event, Hungary, July 13-17, 2020, pp. 159\u2013185 (2020)","DOI":"10.1145\/3391403.3399452"},{"key":"2253_CR19","doi-asserted-by":"crossref","unstructured":"Caragiannis, I., Gravin, N., Lu, P., Wang, Z.: Relaxing the independence assumption in sequential posted pricing, prophet inequality, and random bipartite matching. In: Web and Internet Economics - 17th International Conference, WINE 2021, Potsdam, Germany, December 14-17, 2021, Proceedings, vol. 13112, pp. 131\u2013148 (2021)","DOI":"10.1007\/978-3-030-94676-0_8"},{"key":"2253_CR20","doi-asserted-by":"crossref","unstructured":"Luby, M., Wigderson, A.: Pairwise independence and derandomization. Found. Trends Theor. Comput. Sci. 1(4) (2005)","DOI":"10.1561\/0400000009"},{"key":"2253_CR21","doi-asserted-by":"crossref","unstructured":"Feige, U., Vondr\u00e1k, J.: Approximation algorithms for allocation problems: Improving the factor of 1 - 1\/e. In: 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pp. 667\u2013676 (2006)","DOI":"10.1109\/FOCS.2006.14"},{"issue":"1","key":"2253_CR22","doi-asserted-by":"publisher","first-page":"247","DOI":"10.4086\/toc.2010.v006a011","volume":"6","author":"U Feige","year":"2010","unstructured":"Feige, U., Vondr\u00e1k, J.: The submodular welfare problem with demand queries. Theory Comput. 6(1), 247\u2013290 (2010)","journal-title":"Theory Comput."},{"key":"2253_CR23","doi-asserted-by":"crossref","unstructured":"Babaioff, M., Dinitz, M., Gupta, A., Immorlica, N., Talwar, K.: Secretary problems: weights and discounts. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, pp. 1245\u20131254 (2009)","DOI":"10.1137\/1.9781611973068.135"},{"key":"2253_CR24","unstructured":"Dughmi, S.: Matroid secretary is equivalent to contention resolution. In: 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA, vol. 215, pp. 58\u201315823 (2022)"},{"key":"2253_CR25","unstructured":"Hajiaghayi, M.T., Kleinberg, R.D., Sandholm, T.: Automated online mechanism design and prophet inequalities. In: Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, July 22-26, 2007, Vancouver, British Columbia, Canada, pp. 58\u201365 (2007)"},{"key":"2253_CR26","doi-asserted-by":"crossref","unstructured":"Chawla, S., Hartline, J.D., Malec, D.L., Sivan, B.: Multi-parameter mechanism design and sequential posted pricing. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pp. 311\u2013320 (2010)","DOI":"10.1145\/1806689.1806733"},{"issue":"6","key":"2253_CR27","doi-asserted-by":"publisher","first-page":"1831","DOI":"10.1137\/110839655","volume":"43","author":"C Chekuri","year":"2014","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J. Comput. 43(6), 1831\u20131879 (2014)","journal-title":"SIAM J. Comput."},{"key":"2253_CR28","doi-asserted-by":"crossref","unstructured":"Bateni, M., Dehghani, S., Hajiaghayi, M., Seddighin, S.: Revenue maximization for selling multiple correlated items. In: Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, vol. 9294, pp. 95\u2013105 (2015)","DOI":"10.1007\/978-3-662-48350-3_9"},{"key":"2253_CR29","unstructured":"Chawla, S., Gergatsouli, E., McMahan, J., Tzamos, C.: Approximating pandora\u2019s box with correlations. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2023, September 11-13, 2023, Atlanta, Georgia, USA, vol. 275, pp. 26\u201312624 (2023)"},{"key":"2253_CR30","doi-asserted-by":"crossref","unstructured":"Makur, A., Mertzanidis, M., Psomas, A., Terzoglou, A.: On the robustness of mechanism design under total variation distance. In: Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023 (2023)","DOI":"10.52202\/075280-0080"},{"key":"2253_CR31","doi-asserted-by":"crossref","unstructured":"Cai, Y., Oikonomou, A.: On simple mechanisms for dependent items. In: Bir\u00f3, P., Chawla, S., Echenique, F. (eds.) EC \u201921: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary, July 18-23, 2021, pp. 242\u2013262 (2021)","DOI":"10.1145\/3465456.3467643"},{"key":"2253_CR32","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2024.114814","volume":"1019","author":"C Chekuri","year":"2024","unstructured":"Chekuri, C., Livanos, V.: On submodular prophet inequalities and correlation gap. Theor. Comput. Sci. 1019, 114814 (2024)","journal-title":"Theor. Comput. Sci."},{"key":"2253_CR33","unstructured":"Qiu, F., Singla, S.: Submodular dominance and applications. In: Chakrabarti, A., Swamy, C. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2022, September 19-21, 2022, University of Illinois, Urbana-Champaign, USA (Virtual Conference), vol. 245, pp. 44\u201314421 (2022)"},{"key":"2253_CR34","doi-asserted-by":"crossref","unstructured":"Livanos, V., Patton, K., Singla, S.: Improved mechanisms and prophet inequalities for graphical dependencies. In: Bergemann, D., Kleinberg, R., Sab\u00e1n, D. (eds.) Proceedings of the 25th ACM Conference on Economics and Computation, EC 2024, New Haven, CT, USA, July 8-11, 2024, pp. 782\u2013805 (2024)","DOI":"10.1145\/3670865.3673462"},{"key":"2253_CR35","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, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pp. 1358\u20131377 (2014)","DOI":"10.1137\/1.9781611973402.100"},{"key":"2253_CR36","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1016\/j.geb.2018.05.006","volume":"118","author":"PD Azar","year":"2019","unstructured":"Azar, P.D., Kleinberg, R., Weinberg, S.M.: Prior independent mechanisms via prophet inequalities with limited information. Games Econ. Behav. 118, 511\u2013532 (2019)","journal-title":"Games Econ. Behav."},{"key":"2253_CR37","unstructured":"Caramanis, C., Faw, M., Papadigenopoulos, O., Pountourakis, E.: Single-sample prophet inequalities revisited. CoRR abs\/2103.13089 (2021)"},{"key":"2253_CR38","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kehne, G., Levin, R.: Set covering with our eyes wide shut. In: Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pp. 4530\u20134553 (2024)","DOI":"10.1137\/1.9781611977912.160"},{"key":"2253_CR39","unstructured":"Schrijver, A.: Combinatorial Optimization. Polyhedra and Efficiency. Algorithms and Combinatorics, vol. 24, p. 1881. Springer, Berlin (2003)"},{"key":"2253_CR40","unstructured":"Rubinstein, A., Wang, J.Z., Weinberg, S.M.: Optimal single-choice prophet inequalities from samples. In: 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, vol. 151, pp. 60\u201316010 (2020)"},{"issue":"1","key":"2253_CR41","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1137\/110852061","volume":"42","author":"JA Soto","year":"2013","unstructured":"Soto, J.A.: Matroid secretary problem in the random-assignment model. SIAM J. Comput. 42(1), 178\u2013211 (2013)","journal-title":"SIAM J. Comput."},{"key":"2253_CR42","unstructured":"Seymour, P.: Decomposition of regular matroids. A source book in matroid theory, 339 (1986)"},{"issue":"5","key":"2253_CR43","doi-asserted-by":"publisher","first-page":"1807","DOI":"10.1137\/13094030X","volume":"43","author":"M Dinitz","year":"2014","unstructured":"Dinitz, M., Kortsarz, G.: Matroid secretary for regular and decomposable matroids. SIAM Journal on Computing 43(5), 1807\u20131830 (2014)","journal-title":"SIAM Journal on Computing"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02253-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-025-02253-w","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02253-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T07:10:59Z","timestamp":1777360259000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-025-02253-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,10]]},"references-count":43,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["2253"],"URL":"https:\/\/doi.org\/10.1007\/s10107-025-02253-w","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,10]]},"assertion":[{"value":"15 July 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 June 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 July 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}