{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T01:46:56Z","timestamp":1782265616682,"version":"3.54.5"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T00:00:00Z","timestamp":1778803200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T00:00:00Z","timestamp":1778803200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"NSF-CSIRO","award":["RG23083"],"award-info":[{"award-number":["RG23083"]}]},{"DOI":"10.13039\/501100003825","name":"Magyar Tudom\u00e1nyos Akad\u00e9mia","doi-asserted-by":"publisher","award":["Momentum LP2021-2"],"award-info":[{"award-number":["Momentum LP2021-2"]}],"id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Ministry of Culture and Innovation of Hungary","award":["OTKA K143858"],"award-info":[{"award-number":["OTKA K143858"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2026,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We study the problem of determining whether a given random matching can be implemented as a lottery over weakly stable deterministic matchings \u2013 a property known as ex-post stability. This concept arises in randomized allocation mechanisms such as school choice, where stability in each realized outcome is essential for fairness. Despite its importance in practice, the computational complexity of verifying ex-post stability has remained unresolved. We settle this question by showing that testing ex-post stability is NP-complete, even under highly restricted conditions \u2013 specifically, when both sides have dichotomous preferences or one of the sides has strict preferences. On the positive side, we present an integer programming formulation that finds a decomposition of a random matching with maximum weight on stable matchings. We also consider stronger versions of ex-post stability (in particular robust ex-post stability and ex-post strong stability) and prove that they can be tested in polynomial time.<\/jats:p>","DOI":"10.1007\/s00453-026-01388-2","type":"journal-article","created":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T18:14:56Z","timestamp":1778868896000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Ex-post Stability under Two-Sided Matching: Complexity and Characterization"],"prefix":"10.1007","volume":"88","author":[{"given":"Haris","family":"Aziz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"P\u00e9ter","family":"Bir\u00f3","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gergely","family":"Cs\u00e1ji","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ali","family":"Pourmiri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,5,15]]},"reference":[{"key":"1388_CR1","doi-asserted-by":"crossref","unstructured":"Abdulkadiro\u011flu, A., Andersson, T.: School choice, in: Handbook of the Economics of Education. Elsevier. volume\u00a06, pp. 135\u2013185 (2023)","DOI":"10.1016\/bs.hesedu.2022.11.001"},{"key":"1388_CR2","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1257\/000282805774670167","volume":"95","author":"A Abdulkadiro\u011flu","year":"2005","unstructured":"Abdulkadiro\u011flu, A., Pathak, P.A., Roth, A.E.: The new york city high school match. American Economic Review 95, 364\u2013367 (2005)","journal-title":"American Economic Review"},{"key":"1388_CR3","doi-asserted-by":"publisher","first-page":"1954","DOI":"10.1257\/aer.99.5.1954","volume":"99","author":"A Abdulkadiro\u011flu","year":"2009","unstructured":"Abdulkadiro\u011flu, A., Pathak, P.A., Roth, A.E.: Strategy-proofness versus efficiency in matching with indifferences: Redesigning the nyc high school match. American Economic Review 99, 1954\u20131978 (2009)","journal-title":"American Economic Review"},{"key":"1388_CR4","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1257\/000282803322157061","volume":"93","author":"A Abdulkadiro\u011flu","year":"2003","unstructured":"Abdulkadiro\u011flu, A., S\u00f6nmez, T.: School choice: A mechanism design approach. American economic review 93, 729\u2013747 (2003)","journal-title":"American economic review"},{"key":"1388_CR5","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.geb.2018.03.010","volume":"110","author":"MO Afacan","year":"2018","unstructured":"Afacan, M.O.: The object allocation problem with random priorities. Games Econom. Behav. 110, 71\u201389 (2018)","journal-title":"Games Econom. Behav."},{"key":"1388_CR6","doi-asserted-by":"publisher","first-page":"707","DOI":"10.3982\/TE4762","volume":"18","author":"M Allman","year":"2023","unstructured":"Allman, M., Ashlagi, I., Nikzad, A.: On rank dominance of tie-breaking rules. Theor. Econ. 18, 707\u2013748 (2023)","journal-title":"Theor. Econ."},{"key":"1388_CR7","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1287\/mnsc.2022.4338","volume":"69","author":"N Arnosti","year":"2023","unstructured":"Arnosti, N.: Lottery design for school choice. Manage. Sci. 69, 244\u2013259 (2023)","journal-title":"Manage. Sci."},{"key":"1388_CR8","doi-asserted-by":"publisher","first-page":"1247","DOI":"10.1287\/opre.2014.1319","volume":"62","author":"I Ashlagi","year":"2014","unstructured":"Ashlagi, I., Shi, P.: Improving community cohesion in school choice via correlated-lottery implementation. Oper. Res. 62, 1247\u20131264 (2014)","journal-title":"Oper. Res."},{"key":"1388_CR9","volume-title":"The Future of Economic Design","author":"H Aziz","year":"2019","unstructured":"Aziz, H.: A probabilistic approach to voting, allocation, matching, and coalition formationc approach to voting, allocation, matching, and coalition formation. In: Laslier, J.F., Moulin, H., Sanver, R., Zwicker, W.S. (eds.) The Future of Economic Design. Springer-Verlag (2019)"},{"key":"1388_CR10","doi-asserted-by":"publisher","first-page":"124","DOI":"10.4230\/DagRep.11.6.124","volume":"11","author":"H Aziz","year":"2021","unstructured":"Aziz, H., Bir\u00f3, P., Fleiner, T., Klaus, B.: Matching under preferences: Theory and practice (dagstuhl seminar 21301). Dagstuhl Reports 11, 124\u2013146 (2021). https:\/\/doi.org\/10.4230\/DagRep.11.6.124","journal-title":"Dagstuhl Reports"},{"key":"1388_CR11","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1016\/j.geb.2022.06.002","volume":"135","author":"H Aziz","year":"2022","unstructured":"Aziz, H., Brandl, F.: The vigilant eating rule: A general approach for probabilistic economic design with constraints. Games Econom. Behav. 135, 168\u2013187 (2022)","journal-title":"Games Econom. Behav."},{"key":"1388_CR12","doi-asserted-by":"crossref","unstructured":"Aziz, H., Klaus, B.: Random matching under priorities: Stability and no envy concepts. Social Choice and Welfare , 213\u2013259 (2019)","DOI":"10.1007\/s00355-019-01181-x"},{"key":"1388_CR13","doi-asserted-by":"crossref","unstructured":"Aziz, H., Mackenzie, S., Xia, L., Ye, C.: Ex-post efficiency of random assignments, in: Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS) (2015)","DOI":"10.65109\/VAYK3512"},{"key":"1388_CR14","doi-asserted-by":"publisher","first-page":"3540","DOI":"10.1111\/poms.13449","volume":"30","author":"M Bichler","year":"2021","unstructured":"Bichler, M., Merting, S.: Randomized scheduling mechanisms: Assigning course seats in a fair and efficient way. Prod. Oper. Manag. 30, 3540\u20133559 (2021)","journal-title":"Prod. Oper. Manag."},{"key":"1388_CR15","first-page":"147","volume":"5","author":"G Birkhoff","year":"1946","unstructured":"Birkhoff, G.: Three observations on linear algebra. Univ. Nac. Tacuman Rev. Ser. A 5, 147\u2013151 (1946)","journal-title":"Univ. Nac. Tacuman Rev. Ser. A"},{"key":"1388_CR16","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1006\/jeth.2000.2710","volume":"100","author":"A Bogomolnaia","year":"2001","unstructured":"Bogomolnaia, A., Moulin, H.: A new solution to the random assignment problem. Journal of Economic theory 100, 295\u2013328 (2001)","journal-title":"Journal of Economic theory"},{"key":"1388_CR17","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1006\/jeth.2000.2710","volume":"100","author":"A Bogomolnaia","year":"2001","unstructured":"Bogomolnaia, A., Moulin, H.: A new solution to the random assignment problem. Journal of Economic Theory 100, 295\u2013328 (2001)","journal-title":"Journal of Economic Theory"},{"key":"1388_CR18","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1111\/j.1468-0262.2004.00483.x","volume":"72","author":"A Bogomolnaia","year":"2004","unstructured":"Bogomolnaia, A., Moulin, H.: Random matching under dichotomous preferences. Econometrica 72, 257\u2013279 (2004)","journal-title":"Econometrica"},{"key":"1388_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3274646","volume":"6","author":"S Bronfman","year":"2018","unstructured":"Bronfman, S., Alon, N., Hassidim, A., Romm, A.: Redesigning the Israeli medical internship match. ACM Transactions on Economics and Computation (TEAC) 6, 1\u201318 (2018)","journal-title":"ACM Transactions on Economics and Computation (TEAC)"},{"key":"1388_CR20","volume":"295","author":"I Caragiannis","year":"2021","unstructured":"Caragiannis, I., Filos-Ratsikas, A., Kanellopoulos, P., Vaish, R.: Stable fractional matchings. Artificial intelligence 295, 103416 (2021)","journal-title":"Stable fractional matchings. Artificial intelligence"},{"key":"1388_CR21","doi-asserted-by":"crossref","unstructured":"Chen, J., Roy, S., Sorge, M.: Fractional matchings under preferences: Stability and optimality. (2020) CoRR abs\/2011.12259","DOI":"10.24963\/ijcai.2021\/13"},{"key":"1388_CR22","doi-asserted-by":"publisher","first-page":"2689","DOI":"10.1257\/aer.20210096","volume":"113","author":"D Delacr\u00e9taz","year":"2023","unstructured":"Delacr\u00e9taz, D., Kominers, S.D., Teytelboym, A.: Matching mechanisms for refugee resettlement. American Economic Review 113, 2689\u20132717 (2023)","journal-title":"American Economic Review"},{"key":"1388_CR23","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1016\/j.ejor.2022.07.013","volume":"305","author":"T Demeulemeester","year":"2023","unstructured":"Demeulemeester, T., Goossens, D., Hermans, B., Leus, R.: A pessimist\u2019s approach to one-sided matching. Eur. J. Oper. Res. 305, 1087\u20131099 (2023)","journal-title":"Eur. J. Oper. Res."},{"key":"1388_CR24","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.geb.2015.12.001","volume":"95","author":"B Dogan","year":"2016","unstructured":"Dogan, B., Yildiz, K.: Efficiency and stability of probabilistic assignments in marriage problems. Games Econom. Behav. 95, 47\u201358 (2016)","journal-title":"Games Econom. Behav."},{"key":"1388_CR25","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1257\/aer.98.3.669","volume":"98","author":"A Erdil","year":"2008","unstructured":"Erdil, A., Ergin, H.: What\u2019s the matter with tie-breaking? Improving efficiency in school choice. American Economic Review 98, 669\u2013689 (2008)","journal-title":"American Economic Review"},{"key":"1388_CR26","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","volume":"69","author":"D Gale","year":"1962","unstructured":"Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Mon. 69, 9\u201315 (1962)","journal-title":"Am. Math. Mon."},{"key":"1388_CR27","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","volume":"69","author":"D Gale","year":"1962","unstructured":"Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Mon. 69, 9\u201315 (1962)","journal-title":"Am. Math. Mon."},{"key":"1388_CR28","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, W. H (1979)"},{"key":"1388_CR29","volume-title":"The stable marriage problem: Structure and algorithms","author":"D Gusfield","year":"1989","unstructured":"Gusfield, D., Irving, R.W.: The stable marriage problem: Structure and algorithms. MIT Press, Cambridge, MA, USA (1989)"},{"issue":"3","key":"1388_CR30","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/0166-218X(92)00179-P","volume":"48","author":"RW Irving","year":"1994","unstructured":"Irving, R.W.: Stable marriage and indifference. Discret. Appl. Math. 48(3), 261\u2013272 (1994)","journal-title":"Discret. Appl. Math."},{"key":"1388_CR31","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1145\/1240233.1240238","volume":"3","author":"T Kavitha","year":"2007","unstructured":"Kavitha, T., Mehlhorn, K., Michail, D., Paluch, K.E.: Strongly stable matchings in time O(nm) and extension to the hospitals-residents problem. ACM Trans. Algorithms 3, 15 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"1388_CR32","doi-asserted-by":"publisher","first-page":"1297","DOI":"10.1162\/qjec.2010.125.3.1297","volume":"125","author":"O Kesten","year":"2010","unstructured":"Kesten, O.: School choice with consent. Q. J. Econ. 125, 1297\u20131348 (2010)","journal-title":"Q. J. Econ."},{"key":"1388_CR33","doi-asserted-by":"publisher","first-page":"543","DOI":"10.3982\/TE1558","volume":"10","author":"O Kesten","year":"2015","unstructured":"Kesten, O., Unver, U.: A theory of school choice lotteries. Theor. Econ. 10, 543\u2013595 (2015)","journal-title":"Theor. Econ."},{"key":"1388_CR34","unstructured":"Kunysz, A.: An algorithm for the maximum weight strongly stable matching problem, in: 29th International Symposium on Algorithms and Computation, ISAAC 2018, December 16-19, 2018, Jiaoxi, Yilan, Taiwan, pp. 42:1\u201342:13 (2018)"},{"key":"1388_CR35","doi-asserted-by":"crossref","unstructured":"Manlove, D.F.: Algorithmics of Matching Under Preferences. World Scientific Publishing Company (2013)","DOI":"10.1142\/8591"},{"issue":"1\u20132","key":"1388_CR36","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0304-3975(01)00206-7","volume":"276","author":"DF Manlove","year":"2002","unstructured":"Manlove, D.F., Irving, R.W., Iwama, K., Miyazaki, S., Morita, Y.: Hard variants of stable marriage. Theoret. Comput. Sci. 276(1\u20132), 261\u2013279 (2002)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"1388_CR37","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1287\/moor.18.4.803","volume":"18","author":"AE Roth","year":"1993","unstructured":"Roth, A.E., Rothblum, U.G., Vande Vate, J.H.: Stable matchings, optimal assignments, and linear programming. Math. Oper. Res. 18(4), 803\u2013828 (1993). (803\u2013828 803\u2013828 803\u2013828 803\u2013828 803\u2013828)","journal-title":"Math. Oper. Res."},{"key":"1388_CR38","doi-asserted-by":"crossref","unstructured":"Roth, A.E., Sotomayor, M.A.O.: Two-Sided Matching: A Study in Game Theoretic Modelling and Analysis. Cambridge University Press (1990)","DOI":"10.1017\/CCOL052139015X"},{"key":"1388_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1162\/edfp_a_00237","volume":"14","author":"N Ruijs","year":"2019","unstructured":"Ruijs, N., Oosterbeek, H.: School choice in amsterdam: Which schools are chosen when school choice is free? Education Finance and Policy 14, 1\u201330 (2019)","journal-title":"Education Finance and Policy"},{"key":"1388_CR40","doi-asserted-by":"crossref","unstructured":"Ruszn\u00e1k, A., Bir\u00f3, P., Fleiner, R.: Seat transfers in the course allocation mechanism of e\u00f6tv\u00f6s lor\u00e1nd university, in: 2021 IEEE 15th International Symposium on Applied Computational Intelligence and Informatics (SACI), IEEE. pp. 503\u2013508 (2021)","DOI":"10.1109\/SACI51354.2021.9465548"},{"key":"1388_CR41","doi-asserted-by":"publisher","first-page":"874","DOI":"10.1287\/moor.23.4.874","volume":"23","author":"CP Teo","year":"1998","unstructured":"Teo, C.P., Sethuraman, J.: The geometry of fractional stable matchings and its applications. Math. Oper. Res. 23, 874\u2013891 (1998)","journal-title":"Math. Oper. Res."},{"key":"1388_CR42","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1007\/s003550200197","volume":"20","author":"GJ Woeginger","year":"2003","unstructured":"Woeginger, G.J.: Banks winners in tournaments are difficult to recognize. Soc. Choice Welfare 20, 523\u2013528 (2003)","journal-title":"Soc. Choice Welfare"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01388-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-026-01388-2","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01388-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T01:10:42Z","timestamp":1782263442000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-026-01388-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,15]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["1388"],"URL":"https:\/\/doi.org\/10.1007\/s00453-026-01388-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,15]]},"assertion":[{"value":"25 April 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 April 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 May 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"45"}}