{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,22]],"date-time":"2025-11-22T11:39:20Z","timestamp":1763811560097,"version":"3.41.0"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,2,7]],"date-time":"2025-02-07T00:00:00Z","timestamp":1738886400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF-CSIRO grant on \u201cFair Sequential Collective Decision-Making\u201d","award":["RG230833"],"award-info":[{"award-number":["RG230833"]}]},{"name":"Hungarian Scientific Research Fund, OTKA","award":["K143858"],"award-info":[{"award-number":["K143858"]}]},{"name":"Momentum Grant of the Hungarian Academy of Sciences","award":["2021-2\/2021"],"award-info":[{"award-number":["2021-2\/2021"]}]},{"name":"Ministry of Culture and Innovation of Hungary from the National Research, Development and Innovation fund, financed under the KDP-2023 funding scheme","award":["C2258525"],"award-info":[{"award-number":["C2258525"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>\n            We study deviations by a group of agents in the three main types of matching markets: the house allocation, the marriage, and the roommates models. For a given instance, we call a matching\n            <jats:italic>k-stable<\/jats:italic>\n            if no other matching exists that is more beneficial to at least\n            <jats:italic>k<\/jats:italic>\n            out of the\n            <jats:italic>n<\/jats:italic>\n            agents. The concept generalizes the recently studied majority stability [\n            <jats:xref ref-type=\"bibr\">57<\/jats:xref>\n            ]. We prove that whereas the verification of\n            <jats:italic>k<\/jats:italic>\n            -stability for a given matching is polynomial-time solvable in all three models, the complexity of deciding whether a\n            <jats:italic>k<\/jats:italic>\n            -stable matching exists depends on\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\frac{k}{n}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            and is characteristic of each model.\n          <\/jats:p>","DOI":"10.1145\/3708507","type":"journal-article","created":{"date-parts":[[2024,12,13]],"date-time":"2024-12-13T10:52:27Z","timestamp":1734087147000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Computational Complexity of\n            <i>k<\/i>\n            -stable Matchings"],"prefix":"10.1145","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9757-4956","authenticated-orcid":false,"given":"Haris","family":"Aziz","sequence":"first","affiliation":[{"name":"UNSW Sydney, Sydney, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3811-4332","authenticated-orcid":false,"given":"Gergely","family":"Cs\u00e1ji","sequence":"additional","affiliation":[{"name":"HUN-REN Centre for Economic and Regional Studies, Budapest, Hungary"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4991-2599","authenticated-orcid":false,"given":"\u00c1gnes","family":"Cseh","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Bayreuth, Bayreuth, Germany"}]}],"member":"320","published-online":{"date-parts":[[2025,2,7]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"3","volume-title":"Proceedings of the 15th International Symposium on Algorithms and Computation, ISAAC 2004","author":"Abraham David J.","year":"2004","unstructured":"David J. Abraham, Katar\u00edna Cechl\u00e1rov\u00e1, David F. Manlove, and Kurt Mehlhorn. 2004. Pareto optimality in house allocation problems. In Proceedings of the 15th International Symposium on Algorithms and Computation, ISAAC 2004. Springer, 3\u201315."},{"key":"e_1_3_2_3_2","doi-asserted-by":"crossref","first-page":"1030","DOI":"10.1137\/06067328X","article-title":"Popular matchings","volume":"37","author":"Abraham David J.","year":"2007","unstructured":"David J. Abraham, Robert W. Irving, Telikepalli Kavitha, and Kurt Mehlhorn. 2007. Popular matchings. SIAM Journal on Computing 37, 4 (2007), 1030\u20131045.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2013.08.006"},{"key":"e_1_3_2_5_2","first-page":"964","volume-title":"Proceedings of the AAMAS\u201918","author":"Aziz Haris","year":"2018","unstructured":"Haris Aziz, Jiayin Chen, Serge Gaspers, and Zhaohong Sun. 2018. Stability and Pareto optimality in refugee allocation matchings. In Proceedings of the AAMAS\u201918. 964\u2013972."},{"key":"e_1_3_2_6_2","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/978-3-031-43254-5_18","volume-title":"Algorithmic Game Theory","author":"Aziz Haris","year":"2023","unstructured":"Haris Aziz, Gergely Cs\u00e1ji, and \u00c1gnes Cseh. 2023. Computational complexity of k-stable matchings. In Algorithmic Game Theory. Argyrios Deligkas and Aris Filos-Ratsikas (Eds.), Springer Nature Switzerland, Cham, 311\u2013328."},{"issue":"1","key":"e_1_3_2_7_2","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1006\/jeth.1998.2469","article-title":"A tale of two mechanisms: Student placement","volume":"84","author":"Balinski Michel","year":"1999","unstructured":"Michel Balinski and Tayfun S\u00f6nmez. 1999. A tale of two mechanisms: Student placement. Journal of Economic Theory 84, 1 (1999), 73\u201394.","journal-title":"Journal of Economic Theory"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2022.103768"},{"key":"e_1_3_2_9_2","doi-asserted-by":"crossref","first-page":"504","DOI":"10.1007\/978-3-662-47666-6_40","volume-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming","author":"Bhattacharya Sayan","year":"2015","unstructured":"Sayan Bhattacharya, Martin Hoefer, Chien-Chung Huang, Telikepalli Kavitha, and Lisa Wagner. 2015. Maintaining near-popular matchings. In Proceedings of the International Colloquium on Automata, Languages, and Programming. Springer, 504\u2013515."},{"issue":"2","key":"e_1_3_2_10_2","doi-asserted-by":"crossref","first-page":"614","DOI":"10.1016\/j.ejor.2020.03.018","article-title":"Complexity of finding Pareto-efficient allocations of highest welfare","volume":"291","author":"Bir\u00f3 P\u00e9ter","year":"2021","unstructured":"P\u00e9ter Bir\u00f3 and Jens Gudmundsson. 2021. Complexity of finding Pareto-efficient allocations of highest welfare. European Journal of Operational Research 291, 2 (2021), 614\u2013628.","journal-title":"European Journal of Operational Research"},{"key":"e_1_3_2_11_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/978-3-642-13073-1_10","volume-title":"CIAC \u201910: Proceedings of the 7th International Conference on Algorithms and Complexity","volume":"6078","author":"Bir\u00f3 P\u00e9ter","year":"2010","unstructured":"P\u00e9ter Bir\u00f3, Robert W. Irving, and David F. Manlove. 2010. Popular matchings in the marriage and roommates problems. In CIAC \u201910: Proceedings of the 7th International Conference on Algorithms and Complexity(Lecture Notes in Computer Science, Vol. 6078). Springer, 97\u2013108."},{"issue":"1","key":"e_1_3_2_12_2","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1111\/j.1468-0262.2004.00483.x","article-title":"Random matching under dichotomous preferences","volume":"72","author":"Bogomolnaia Anna","year":"2004","unstructured":"Anna Bogomolnaia and Herv\u00e9 Moulin. 2004. Random matching under dichotomous preferences. Econometrica 72, 1 (2004), 257\u2013279.","journal-title":"Econometrica"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.2202\/1935-1682.2294\/html#MLA"},{"key":"e_1_3_2_14_2","first-page":"213","volume-title":"Proceedings of the AAMAS\u201920","author":"Bullinger Martin","year":"2020","unstructured":"Martin Bullinger. 2020. Pareto-optimality in cardinal hedonic games. In Proceedings of the AAMAS\u201920. 213\u2013221."},{"issue":"4","key":"e_1_3_2_15_2","doi-asserted-by":"crossref","first-page":"700","DOI":"10.1007\/s00224-016-9677-1","article-title":"Pareto optimal matchings in many-to-many markets with ties","volume":"59","author":"Cechl\u00e1rov\u00e1 Katar\u00edna","year":"2016","unstructured":"Katar\u00edna Cechl\u00e1rov\u00e1, Pavlos Eirinakis, Tam\u00e1s Fleiner, Dimitrios Magos, David Manlove, Ioannis Mourtos, Eva Ocel\u00e1kov\u00e1, and Baharak Rastegari. 2016. Pareto optimal matchings in many-to-many markets with ties. Theory of Computing Systems 59, 4 (2016), 700\u2013721.","journal-title":"Theory of Computing Systems"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","unstructured":"Katar\u00edna Cechl\u00e1rov\u00e1 Pavlos Eirinakis Tam\u00e1s Fleiner Dimitrios Magos Ioannis Mourtos and Eva Potpinkov\u00e1. 2014. Pareto optimality in many-to-many matching problems. Discrete Optimization 14 (2014) 160\u2013169. DOI:10.1016\/j.disopt.2014.09.002","DOI":"10.1016\/j.disopt.2014.09.002"},{"key":"e_1_3_2_17_2","doi-asserted-by":"crossref","first-page":"1669","DOI":"10.1257\/000282802762024728","article-title":"Improving efficiency of on-campus housing: An experimental study","volume":"92","author":"Chen Yan","year":"2002","unstructured":"Yan Chen and Tayfun S\u00f6nmez. 2002. Improving efficiency of on-campus housing: An experimental study. American Economic Review 92, 5 (2002), 1669\u20131686.","journal-title":"American Economic Review"},{"key":"e_1_3_2_18_2","volume-title":"Essai Sur L\u2019application de L\u2019analyse \u00e0 La Probabilit\u00e9 des D\u00e9cisions Rendues \u00e0 la Pluralit\u00e9 Des Voix","author":"Condorcet Marie Jean Antoine Nicolas de Caritat, Marquis de","year":"1785","unstructured":"Marie Jean Antoine Nicolas de Caritat, Marquis de Condorcet. 1785. Essai Sur L\u2019application de L\u2019analyse \u00e0 La Probabilit\u00e9 des D\u00e9cisions Rendues \u00e0 la Pluralit\u00e9 Des Voix. L\u2019Imprimerie Royale."},{"issue":"3","key":"e_1_3_2_19_2","article-title":"Popular matchings","volume":"105","author":"Cseh \u00c1gnes","year":"2017","unstructured":"\u00c1gnes Cseh. 2017. Popular matchings. Trends in Computational Social Choice 105, 3 (2017).","journal-title":"Trends in Computational Social Choice"},{"issue":"4","key":"e_1_3_2_20_2","doi-asserted-by":"crossref","first-page":"2348","DOI":"10.1137\/16M1076162","article-title":"Popular matchings with two-sided preferences and one-sided ties","volume":"31","author":"Cseh \u00c1gnes","year":"2017","unstructured":"\u00c1gnes Cseh, Chien-Chung Huang, and Telikepalli Kavitha. 2017. Popular matchings with two-sided preferences and one-sided ties. SIAM Journal on Discrete Mathematics 31, 4 (2017), 2348\u20132377.","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"5","key":"e_1_3_2_21_2","doi-asserted-by":"crossref","first-page":"1493","DOI":"10.1007\/s00453-020-00791-7","article-title":"Popular matchings in complete graphs","volume":"83","author":"Cseh \u00c1gnes","year":"2021","unstructured":"\u00c1gnes Cseh and Telikepalli Kavitha. 2021. Popular matchings in complete graphs. Algorithmica 83, 5 (2021), 1493\u20131523.","journal-title":"Algorithmica"},{"issue":"05","key":"e_1_3_2_22_2","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1142\/S0129054113500226","article-title":"Popular spanning trees","volume":"24","author":"Darmann Andreas","year":"2013","unstructured":"Andreas Darmann. 2013. Popular spanning trees. International Journal of Foundations of Computer Science 24, 05 (2013), 655\u2013677.","journal-title":"International Journal of Foundations of Computer Science"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.mathsocsci.2018.01.005"},{"issue":"3","key":"e_1_3_2_24_2","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/s001860200207","article-title":"On the number of criteria needed to decide Pareto optimality","volume":"55","author":"Ehrgott Matthias","year":"2002","unstructured":"Matthias Ehrgott and Stefan Nickel. 2002. On the number of criteria needed to decide Pareto optimality. Mathematical Methods of Operations Research 55, 3 (2002), 329\u2013345.","journal-title":"Mathematical Methods of Operations Research"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2020.103357"},{"key":"e_1_3_2_26_2","first-page":"2790","volume-title":"Proceedings of SODA \u201919: the 30th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Faenza Yuri","year":"2019","unstructured":"Yuri Faenza, Telikepalli Kavitha, Vladlena Powers, and Xingyu Zhang. 2019. Popular matchings and limits to tractability. In Proceedings of SODA \u201919: the 30th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM-SIAM, 2790\u20132809."},{"key":"e_1_3_2_27_2","doi-asserted-by":"crossref","unstructured":"Monique Florenzano Pascal Gourdel and Alejandro Jofr\u00e9. 2006. Supporting weakly pareto optimal allocations in infinite dimensional nonconvex economies. Economic Theory 29 3 (2006) 549\u2013564. Retrieved December 21 2024 from http:\/\/www.jstor.org\/stable\/25056127","DOI":"10.1007\/s00199-005-0033-y"},{"issue":"2","key":"e_1_3_2_28_2","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1145\/321941.321942","article-title":"An efficient implementation of Edmonds algorithm for maximum matching on graphs","volume":"23","author":"Gabow Harold N.","year":"1976","unstructured":"Harold N. Gabow. 1976. An efficient implementation of Edmonds algorithm for maximum matching on graphs. Journal of the ACM 23, 2 (1976), 221\u2013234.","journal-title":"Journal of the ACM"},{"key":"e_1_3_2_29_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"825","DOI":"10.1007\/978-3-540-74466-5_88","volume-title":"Euro-Par \u201907: Proceedings of the 13th International Euro-Par Conference (European Conference on Parallel and Distributed Computing).","volume":"4641","author":"Gai Anh-Tuan","year":"2007","unstructured":"Anh-Tuan Gai, Dmitry Lebedev, Fabien Mathieu, Fabien De Montgolfier, Julien Reynier, and Laurent Viennot. 2007. Acyclic preference systems in P2P networks. In Euro-Par \u201907: Proceedings of the 13th International Euro-Par Conference (European Conference on Parallel and Distributed Computing).Anne-Marie Kermarrec, Luc Boug\u00e9, and Thierry Priol (Eds.), Lecture Notes in Computer Science, Vol. 4641, Springer, 825\u2013834."},{"key":"e_1_3_2_30_2","doi-asserted-by":"crossref","unstructured":"David Gale and Lloyd S. Shapley. 1962. College admissions and the stability of marriage. The American Mathematical Monthly 69 1 (1962) 9\u201315.","DOI":"10.1080\/00029890.1962.11989827"},{"key":"e_1_3_2_31_2","doi-asserted-by":"crossref","unstructured":"Peter G\u00e4rdenfors. 1975. Match making: Assignments based on bilateral preferences. Behavioral Science 20 3 (1975) 166\u2013173.","DOI":"10.1002\/bs.3830200304"},{"key":"e_1_3_2_32_2","volume-title":"Computers and Intractability","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S. Johnson. 1979. Computers and Intractability. Freeman, San Francisco, CA."},{"issue":"2","key":"e_1_3_2_33_2","first-page":"9","article-title":"Popular matching in roommates setting is NP-hard","volume":"13","author":"Gupta Sushmita","year":"2021","unstructured":"Sushmita Gupta, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi. 2021. Popular matching in roommates setting is NP-hard. ACM Transactions on Computation Theory 13, 2, Article 9 (2021), 20 pages.","journal-title":"ACM Transactions on Computation Theory"},{"key":"e_1_3_2_34_2","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1137\/0202019","article-title":"A  \\(n^{5\/2}\\)  algorithm for maximum matchings in bipartite graphs","volume":"2","author":"Hopcroft John E.","year":"1973","unstructured":"John E. Hopcroft and Richard M. Karp. 1973. A \\(n^{5\/2}\\) algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing 2, 4 (1973), 225\u2013231.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"e_1_3_2_35_2","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1137\/110852838","article-title":"Near-popular matchings in the roommates problem","volume":"27","author":"Huang Chien-Chung","year":"2013","unstructured":"Chien-Chung Huang and Telikepalli Kavitha. 2013. Near-popular matchings in the roommates problem. SIAM Journal on Discrete Mathematics 27, 1 (2013), 43\u201362.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","unstructured":"Chien-Chung Huang and Telikepalli Kavitha. 2013. Popular matchings in the stable marriage problem. Information and Computation 222 (2013) 180\u2013194. DOI:10.1016\/j.ic.2012.10.012","DOI":"10.1016\/j.ic.2012.10.012"},{"issue":"2","key":"e_1_3_2_37_2","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1287\/moor.2020.1063","article-title":"Popularity, mixed matchings, and self-duality","volume":"46","author":"Huang Chien-Chung","year":"2021","unstructured":"Chien-Chung Huang and Telikepalli Kavitha. 2021. Popularity, mixed matchings, and self-duality. Mathematics of Operations Research 46, 2 (2021), 405\u2013427.","journal-title":"Mathematics of Operations Research"},{"issue":"3","key":"e_1_3_2_38_2","doi-asserted-by":"crossref","first-page":"738","DOI":"10.1007\/s00453-010-9434-9","article-title":"Bounded unpopularity matchings","volume":"61","author":"Huang Chien-Chung","year":"2011","unstructured":"Chien-Chung Huang, Telikepalli Kavitha, Dimitrios Michail, and Meghana Nasre. 2011. Bounded unpopularity matchings. Algorithmica 61, 3 (2011), 738\u2013757.","journal-title":"Algorithmica"},{"key":"e_1_3_2_39_2","doi-asserted-by":"crossref","unstructured":"Robert W. Irving. 1985. An efficient algorithm for the \u201cstable roommates\u201d problem. Journal of Algorithms 6 4 (1985) 577\u2013595.","DOI":"10.1016\/0196-6774(85)90033-1"},{"key":"e_1_3_2_40_2","doi-asserted-by":"crossref","unstructured":"Telikepalli Kavitha. 2014. A size-popularity tradeoff in the stable marriage problem. SIAM Journal on Computing 43 1 (2014) 52\u201371.","DOI":"10.1137\/120902562"},{"key":"e_1_3_2_41_2","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1137\/1.9781611977073.6","volume-title":"SODA \u201922: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Kavitha Telikepalli","year":"2022","unstructured":"Telikepalli Kavitha, Tam\u00e1s Kir\u00e1ly, Jannik Matuschke, Ildik\u00f3 Schlotter, and Ulrike Schmidt-Kraepelin. 2022. The popular assignment problem: when cardinality is more important than popularity. In SODA \u201922: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 103\u2013123."},{"issue":"1","key":"e_1_3_2_42_2","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1007\/s10107-021-01659-6","article-title":"Popular branchings and their dual certificates","volume":"192","author":"Kavitha Telikepalli","year":"2022","unstructured":"Telikepalli Kavitha, Tam\u00e1s Kir\u00e1ly, Jannik Matuschke, Ildik\u00f3 Schlotter, and Ulrike Schmidt-Kraepelin. 2022. Popular branchings and their dual certificates. Mathematical Programming 192, 1 (2022), 567\u2013595.","journal-title":"Mathematical Programming"},{"key":"e_1_3_2_43_2","doi-asserted-by":"crossref","unstructured":"Telikepalli Kavitha Juli\u00e1n Mestre and Meghana Nasre. 2011. Popular mixed matchings. Theoretical Computer Science 412 24 (2011) 2679\u20132690.","DOI":"10.1016\/j.tcs.2010.03.028"},{"key":"e_1_3_2_44_2","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/j.dam.2023.06.041","article-title":"On weakly and strongly popular rankings","volume":"340","author":"Kraiczy Sonja","year":"2023","unstructured":"Sonja Kraiczy, \u00c1gnes Cseh, and David Manlove. 2023. On weakly and strongly popular rankings. Discrete Applied Mathematics 340 (2023), 134\u2013152.","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"e_1_3_2_45_2","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1002\/nav.3800020109","article-title":"The Hungarian method for the assignment problem","volume":"2","author":"Kuhn Harold W.","year":"1955","unstructured":"Harold W. Kuhn. 1955. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly 2, 1-2 (1955), 83\u201397.","journal-title":"Naval Research Logistics Quarterly"},{"key":"e_1_3_2_46_2","doi-asserted-by":"crossref","DOI":"10.1142\/8591","volume-title":"Algorithmics of Matching Under Preferences","author":"Manlove David F.","year":"2013","unstructured":"David F. Manlove. 2013. Algorithmics of Matching Under Preferences. World Scientific."},{"key":"e_1_3_2_47_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1007\/978-3-540-78773-0_51","volume-title":"Proceedings of LATIN \u201908: the 8th Latin-American Theoretical Informatics Symposium","volume":"4957","author":"McCutchen Richard Matthew","year":"2008","unstructured":"Richard Matthew McCutchen. 2008. The least-unpopularity-factor and least-unpopularity-margin criteria for matching problems with one-sided preferences. In Proceedings of LATIN \u201908: the 8th Latin-American Theoretical Informatics Symposium. EduardoSany Laber, Claudson Bornstein, LoanaTito Nogueira, and Luerbio Faria (Eds.), Lecture Notes in Computer Science, Vol. 4957, Springer, Berlin, 593\u2013604."},{"key":"e_1_3_2_48_2","first-page":"17","volume-title":"Proceedings of FOCS \u201980: the 21st Annual IEEE Symposium on Foundations of Computer Science","author":"Micali Silvio","year":"1980","unstructured":"Silvio Micali and Vijay V. Vazirani. 1980. An \\(O(\\sqrt {|V|} \\cdot |E|)\\) algorithm for finding maximum matching in general graphs. In Proceedings of FOCS \u201980: the 21st Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society, 17\u201327."},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4020-9160-5_341"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00182-007-0083-4#citeas"},{"key":"e_1_3_2_51_2","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","author":"Peters Dominik","year":"2016","unstructured":"Dominik Peters. 2016. Complexity of hedonic games with dichotomous preferences. In Proceedings of the AAAI Conference on Artificial Intelligence."},{"key":"e_1_3_2_52_2","doi-asserted-by":"crossref","unstructured":"Alvin E. Roth. 1982. Incentive compatibility in a market with indivisible goods. Economics Letters 9 2 (1982) 127\u2013132.","DOI":"10.1016\/0165-1765(82)90003-9"},{"key":"e_1_3_2_53_2","series-title":"Econometric Society Monographs","doi-asserted-by":"crossref","DOI":"10.1017\/CCOL052139015X","volume-title":"Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis","author":"Roth Alvin E.","year":"1990","unstructured":"Alvin E. Roth and Marilda A. Oliveira Sotomayor. 1990. Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Econometric Society Monographs. Cambridge University Press."},{"issue":"3","key":"e_1_3_2_54_2","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1007\/s00224-020-09978-5","article-title":"Unpopularity factor in the marriage and roommates problems","volume":"65","author":"Ruangwises Suthee","year":"2021","unstructured":"Suthee Ruangwises and Toshiya Itoh. 2021. Unpopularity factor in the marriage and roommates problems. Theory of Computing Systems 65, 3 (2021), 579\u2013592.","journal-title":"Theory of Computing Systems"},{"key":"e_1_3_2_55_2","unstructured":"Alexander Schrijver. 2003. Combinatorial optimization: polyhedra and efficiency. Springer."},{"issue":"1","key":"e_1_3_2_56_2","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1016\/0196-6774(91)90028-W","article-title":"A necessary and sufficient condition for the existence of a complete stable matching","volume":"12","author":"Tan Jimmy J. M.","year":"1991","unstructured":"Jimmy J. M. Tan. 1991. A necessary and sufficient condition for the existence of a complete stable matching. Journal of Algorithms 12, 1 (1991), 154\u2013178.","journal-title":"Journal of Algorithms"},{"issue":"1","key":"e_1_3_2_57_2","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0166-218X(93)E0154-Q","article-title":"A generalization of the stable matching problem","volume":"59","author":"Tan Jimmy J. M.","year":"1995","unstructured":"Jimmy J. M. Tan and Hsueh Yuang-Cheh. 1995. A generalization of the stable matching problem. Discrete Applied Mathematics 59, 1 (1995), 87\u2013102.","journal-title":"Discrete Applied Mathematics"},{"key":"e_1_3_2_58_2","volume-title":"Proceedings of the 25th Annual ISNIE\/SIOE Conference","author":"Thakur Ashutosh","year":"2021","unstructured":"Ashutosh Thakur. 2021. Combining social choice and matching theory to understand institutional stability. In Proceedings of the 25th Annual ISNIE\/SIOE Conference. Society for Institutional and Organizational Economics."},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","unstructured":"Anke van Zuylen Frans Schalekamp and David P. Williamson. 2014. Popular ranking. Discrete Applied Mathematics 165 (2014) 312\u2013316. DOI:10.1016\/j.dam.2012.07.006","DOI":"10.1016\/j.dam.2012.07.006"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","unstructured":"A. R. Warburton. 1983. Quasiconcave vector maximization: Connectedness of the sets of Pareto-optimal and weak Pareto-optimal alternatives. J. Optim. Theory Appl. 40 4 (August 1983) 537\u2013557. DOI:10.1007\/BF00933970","DOI":"10.1007\/BF00933970"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3708507","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3708507","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:09:55Z","timestamp":1750295395000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3708507"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,7]]},"references-count":59,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3,31]]}},"alternative-id":["10.1145\/3708507"],"URL":"https:\/\/doi.org\/10.1145\/3708507","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2025,2,7]]},"assertion":[{"value":"2024-01-25","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-28","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-07","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}