{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T17:37:03Z","timestamp":1771004223674,"version":"3.50.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"name":"JST ERATO","award":["JPMJER2301, Japan"],"award-info":[{"award-number":["JPMJER2301, Japan"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2026,3,31]]},"abstract":"<jats:p>Super-stability and strong stability are properties of a matching in the stable matching problem with ties. In this paper, we introduce a common generalization of super-stability and strong stability, which we call non-uniform stability. First, we prove that we can determine the existence of a non-uniformly stable matching in polynomial time. Next, we give a polyhedral characterization of the set of non-uniformly stable matchings. Finally, we prove that the set of non-uniformly stable matchings forms a distributive lattice.<\/jats:p>","DOI":"10.1145\/3773033","type":"journal-article","created":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T10:11:29Z","timestamp":1761387089000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Non-uniformly Stable Matchings"],"prefix":"10.1145","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7712-2730","authenticated-orcid":false,"given":"Naoyuki","family":"Kamiyama","sequence":"first","affiliation":[{"name":"Kyushu University","place":["Fukuoka, Japan"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,2,13]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718158"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2025.12"},{"key":"e_1_3_2_4_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/978-3-642-15781-3_13","volume-title":"Proceedings of the 18th Annual European Symposium on Algorithms, Part II","volume":"6347","author":"Chen Ning","year":"2010","unstructured":"Ning Chen and Arpita Ghosh. 2010. Strongly stable assignment. In Proceedings of the 18th Annual European Symposium on Algorithms, Part II(Lecture Notes in Computer Science, Vol. 6347), Mark de Berg and Ulrich Meyer (Eds.). Springer, Berlin, Germany, 147\u2013158. DOI:10.1007\/978-3-642-15781-3_13"},{"key":"e_1_3_2_5_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-11008-0","volume-title":"Integer Programming","author":"Conforti Michele","year":"2014","unstructured":"Michele Conforti, G\u00e9rard Cornu\u00e9jols, and Giacomo Zambelli. 2014. Integer Programming. Springer, Cham, Switzerland."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.1.103.14256"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.2307\/2312726"},{"issue":"1","key":"e_1_3_2_8_2","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1112\/jlms\/s1-10.37.26","article-title":"On representatives of subsets","volume":"1","author":"Hall Philip","year":"1935","unstructured":"Philip Hall. 1935. On representatives of subsets. Journal of the London Mathematical Society 1, 1 (1935), 26\u201330.","journal-title":"Journal of the London Mathematical Society"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_3_2_10_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1007\/978-3-030-83508-8_35","volume-title":"Proceedings of the 17th Algorithm and Data Structures Symposium","volume":"12808","author":"Hu Changyong","year":"2021","unstructured":"Changyong Hu and Vijay K. Garg. 2021. Characterization of super-stable matchings. In Proceedings of the 17th Algorithm and Data Structures Symposium(Lecture Notes in Computer Science, Vol. 12808), Anna Lubiw and Mohammad R. Salavatipour (Eds.). Springer, Cham, Switzerland, 485\u2013498. DOI:10.1007\/978-3-030-83508-8_35"},{"key":"e_1_3_2_11_2","volume-title":"Characterization of Super-stable Matchings","author":"Hu Changyong","year":"2021","unstructured":"Changyong Hu and Vijay K. Garg. 2021. Characterization of Super-stable Matchings. Technical Report arXiv:2105.09602. Retrieved from https:\/\/arxiv.org\/abs\/2105.09602"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)00179-P"},{"key":"e_1_3_2_13_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/3-540-44985-X_24","volume-title":"Proceedings of the 7th Scandinavian Workshop on Algorithm Theory","volume":"1851","author":"Irving Robert W.","year":"2000","unstructured":"Robert W. Irving, David F. Manlove, and Sandy Scott. 2000. The hospitals\/residents problem with ties. In Proceedings of the 7th Scandinavian Workshop on Algorithm Theory(Lecture Notes in Computer Science, Vol. 1851), Magn\u00fas M. Halld\u00f3rsson (Ed.). Springer, Berlin, Heidelberg, Germany, 259\u2013271. DOI:10.1007\/3-540-44985-X_24"},{"key":"e_1_3_2_14_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1007\/3-540-36494-3_39","volume-title":"Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science","volume":"2607","author":"Irving Robert W.","year":"2003","unstructured":"Robert W. Irving, David F. Manlove, and Sandy Scott. 2003. Strong stability in the hospitals\/residents problem. In Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science(Lecture Notes in Computer Science, Vol. 2607), Helmut Alt and Michel Habib (Eds.). Springer, Berlin, Germany, 439\u2013450. DOI:10.1007\/3-540-36494-3_39"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.01.002"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-30162-4_395"},{"key":"e_1_3_2_17_2","first-page":"219","article-title":"Marriage market with indifferences: A linear programming approach","volume":"11","author":"Juarez Noelia","year":"2023","unstructured":"Noelia Juarez, Pablo A. Neme, and Jorge Oviedo. 2023. Marriage market with indifferences: A linear programming approach. Journal of the Operations Research Society of China 11, 1 (2023), 219\u2013242.","journal-title":"Journal of the Operations Research Society of China"},{"key":"e_1_3_2_18_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-3-662-48433-3_1","volume-title":"Proceedings of the 8th International Symposium on Algorithmic Game Theory","volume":"9347","author":"Kamiyama Naoyuki","year":"2015","unstructured":"Naoyuki Kamiyama. 2015. Stable Matchings with Ties, Master Preference Lists, and Matroid Constraints. In Proceedings of the 8th International Symposium on Algorithmic Game Theory(Lecture Notes in Computer Science, Vol. 9347), Martin Hoefer (Ed.). Springer, Berlin, Germany, 3\u201314. DOI:10.1007\/978-3-662-48433-3_1"},{"key":"e_1_3_2_19_2","first-page":"583","volume-title":"Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems","author":"Kamiyama Naoyuki","year":"2019","unstructured":"Naoyuki Kamiyama. 2019. Many-to-many stable matchings with ties, master preference lists, and matroid constraints. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems, Edith Elkind, Manuela Veloso, Noa Agmon, and Matthew E. Taylor (Eds.). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 583\u2013591."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/21m1437214"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","unstructured":"Naoyuki Kamiyama. 2025. Strongly stable matchings under matroid constraints. SIAM Journal on Discrete Mathematics 39 3 (2025) 1471\u20131490. 10.1137\/23M1587658","DOI":"10.1137\/23M1587658"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/1240233.1240238"},{"key":"e_1_3_2_23_2","series-title":"CRM Proceedings and Lecture Notes","volume-title":"Stable Marriage and its Relation to Other Combinatorial Problems","volume":"10","author":"Knuth Donald E.","year":"1997","unstructured":"Donald E. Knuth. 1997. Stable Marriage and its Relation to Other Combinatorial Problems. CRM Proceedings and Lecture Notes, Vol. 10. American Mathematical Society, Providence, RI. DOI:10.1090\/crmp\/010"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ISAAC.2018.42"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17402-6_25"},{"key":"e_1_3_2_26_2","first-page":"107","volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Kunysz Adam","year":"2016","unstructured":"Adam Kunysz, Katarzyna E. Paluch, and Pratik Ghosal. 2016. Characterisation of strongly stable matchings. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, Robert Krauthgamer (Ed.). Society for Industrial and Applied Mathematics, Philadelphia, PA, 107\u2013119. DOI:10.1137\/1.9781611974331.ch8"},{"key":"e_1_3_2_27_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1007\/978-3-540-30140-0_46","volume-title":"Proceedings of the 12th Annual European Symposium on Algorithms","volume":"3221","author":"Malhotra Varun S.","year":"2004","unstructured":"Varun S. Malhotra. 2004. On the stability of multiple partner stable marriages with ties. In Proceedings of the 12th Annual European Symposium on Algorithms(Lecture Notes in Computer Science, Vol. 3221), Susanne Albers and Tomasz Radzik (Eds.). Springer, Berlin, Germany, 508\u2013519. DOI:10.1007\/978-3-540-30140-0_46"},{"key":"e_1_3_2_28_2","volume-title":"Stable Marriage with Ties and Unacceptable Partners","author":"Manlove David F.","year":"1999","unstructured":"David F. Manlove. 1999. Stable Marriage with Ties and Unacceptable Partners. Technical Report TR-1999-29. The University of Glasgow, Department of Computing Science."},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00322-5"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1142\/8591"},{"key":"e_1_3_2_31_2","series-title":"SIAM Monographs on Discrete Mathematics and Applications","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718508","volume-title":"Discrete Convex Analysis","author":"Murota Kazuo","year":"2003","unstructured":"Kazuo Murota. 2003. Discrete Convex Analysis. SIAM Monographs on Discrete Mathematics and Applications, Vol. 10. Society for Industrial and Applied Mathematics, Philadelphia, PA. DOI:10.1137\/1.9780898718508"},{"key":"e_1_3_2_32_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1007\/978-3-030-39219-2_31","volume-title":"Proceedings of the 8th Annual International Conference on Algorithms and Discrete Applied Mathematics","volume":"12016","author":"Olaosebikan Sofiat","year":"2020","unstructured":"Sofiat Olaosebikan and David F. Manlove. 2020. An algorithm for strong stability in the student-project allocation problem with ties. In Proceedings of the 8th Annual International Conference on Algorithms and Discrete Applied Mathematics(Lecture Notes in Computer Science, Vol. 12016), Manoj Changat and Sandip Das (Eds.). Springer, Cham, Switzerland, 384\u2013399. DOI:10.1007\/978-3-030-39219-2_31"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-020-00632-x"},{"key":"e_1_3_2_34_2","volume-title":"Algorithmic Aspects of Stable Matching Problems","author":"O\u2019Malley Gregg","year":"2007","unstructured":"Gregg O\u2019Malley. 2007. Algorithmic Aspects of Stable Matching Problems. Ph. D. Dissertation. The University of Glasgow."},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01586041"},{"key":"e_1_3_2_36_2","series-title":"Algorithms and Combinatorics","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"Schrijver Alexander","year":"2002","unstructured":"Alexander Schrijver. 2002. Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics, Vol. 24. Springer, Berlin, Germany."},{"key":"e_1_3_2_37_2","volume-title":"A Study of Stable Marriage Problems with Ties","author":"Scott Sandy","year":"2005","unstructured":"Sandy Scott. 2005. A Study of Stable Marriage Problems with Ties. Ph. D. Dissertation. The University of Glasgow."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00080-W"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(89)90041-2"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3773033","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T16:57:41Z","timestamp":1771001861000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3773033"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,13]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3,31]]}},"alternative-id":["10.1145\/3773033"],"URL":"https:\/\/doi.org\/10.1145\/3773033","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,13]]},"assertion":[{"value":"2024-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-14","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-02-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}