{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T05:32:39Z","timestamp":1771651959853,"version":"3.50.1"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,10,16]],"date-time":"2021-10-16T00:00:00Z","timestamp":1634342400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001870","name":"Foundation for Polish Science","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001870","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Poland\u2019s National Science Center","award":["UMO-2019\/35\/B\/ST6\/02215"],"award-info":[{"award-number":["UMO-2019\/35\/B\/ST6\/02215"]}]},{"name":"European Research Council","award":["677651 (JC) and 714704 (MS)"],"award-info":[{"award-number":["677651 (JC) and 714704 (MS)"]}]},{"name":"WWTF research","award":["VRG18-012"],"award-info":[{"award-number":["VRG18-012"]}]},{"DOI":"10.13039\/100005156","name":"Alexander von Humboldt Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100005156","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>\n            We propose two solution concepts for matchings under preferences:\n            <jats:italic>robustness<\/jats:italic>\n            and\n            <jats:italic>near stability<\/jats:italic>\n            . The former strengthens while the latter relaxes the classical definition of stability by Gale and Shapley (1962). Informally speaking, robustness requires that a matching must be stable in the classical sense, even if the agents slightly change their preferences. Near stability, however, imposes that a matching must become stable (again, in the classical sense) provided the agents are willing to adjust their preferences a bit. Both of our concepts are quantitative; together they provide means for a fine-grained analysis of the stability of matchings. Moreover, our concepts allow the exploration of tradeoffs between stability and other criteria of social optimality, such as the egalitarian cost and the number of unmatched agents. We investigate the computational complexity of finding matchings that implement certain predefined tradeoffs. We provide a polynomial-time algorithm that, given agent preferences, returns a socially optimal robust matching (if it exists), and we prove that finding a socially optimal and nearly stable matching is computationally hard.\n          <\/jats:p>","DOI":"10.1145\/3485000","type":"journal-article","created":{"date-parts":[[2021,10,17]],"date-time":"2021-10-17T02:06:47Z","timestamp":1634436407000},"page":"1-55","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Matchings under Preferences: Strength of Stability and\u00a0Tradeoffs"],"prefix":"10.1145","volume":"9","author":[{"given":"Jiehua","family":"Chen","sequence":"first","affiliation":[{"name":"TU Wien, Wien, Austria and University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piotr","family":"Skowron","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manuel","family":"Sorge","sequence":"additional","affiliation":[{"name":"TU Wien, Wien, Austria and University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,10,16]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11238-017-9598-8"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-011-9184-3"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00650-0"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.01.022"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11238-012-9319-2"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-020-09470-x"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i02.5550"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2020.103403"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1965-0180568-2"},{"issue":"128","key":"e_1_3_2_12_2","first-page":"1","article-title":"Selected open problems in matching under preferences","volume":"2","author":"Cechl\u00e1rov\u00e1 Katar\u00edna","year":"2019","unstructured":"Katar\u00edna Cechl\u00e1rov\u00e1, \u00c1gnes Cseh, and David Manlove. 2019. Selected open problems in matching under preferences. Bull. EATCS 2, 128 (2019), 1\u201326.","journal-title":"Bull. EATCS"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1086\/701791"},{"key":"e_1_3_2_14_2","first-page":"35:1","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming","author":"Chen Jiehua","year":"2018","unstructured":"Jiehua Chen, Danny Hermelin, Manuel Sorge, and Harel Yedidsion. 2018. How hard is it to satisfy (almost) all roommates? In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918). 35:1\u201335:15."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219168"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.5555\/2815661"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.5555\/2568438"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/2540128.2540145"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1093\/restud\/rdz041"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1111\/1468-0262.00383"},{"key":"e_1_3_2_21_2","volume-title":"Handbook of Computational Social Choice","author":"Faliszewski Piotr","year":"2016","unstructured":"Piotr Faliszewski and J\u00f6rg Rothe. 2016. Control and bribery in voting. In Handbook of Computational Social Choice. Cambridge University Press."},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.5555\/1121738"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.4169\/amer.math.monthly.120.05.386"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.5555\/578533"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.5555\/3297863.3297933"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.12.017"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1287\/orsc.10.1.104"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.5555\/3027519"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.5555\/184652.179219"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/0215048"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28871"},{"key":"e_1_3_2_32_2","first-page":"36:1","volume-title":"Proceedings of the Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","volume":"60","author":"Kanade Varun","year":"2016","unstructured":"Varun Kanade, Nikos Leonardos, and Fr\u00e9d\u00e9ric Magniez. 2016. Stable matching with evolving preferences. In Proceedings of the Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM\u201916), Vol. 60. 36:1\u201336:13."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188848"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1162\/qjec.2010.125.3.1297"},{"key":"e_1_3_2_35_2","volume-title":"Mariages Stables","author":"Knuth Donald","year":"1976","unstructured":"Donald Knuth. 1976. Mariages Stables. Les Presses de L\u2019Universit\u00e9 de Montr\u00e9al."},{"key":"e_1_3_2_36_2","first-page":"60:1","volume-title":"Proceedings of the 26th European Symposium on Algorithms","author":"Mai Tung","year":"2018","unstructured":"Tung Mai and Vijay V. Vazirani. 2018. Finding stable matchings that are robust to errors in the input. In Proceedings of the 26th European Symposium on Algorithms (ESA\u201918). 60:1\u201360:11."},{"key":"e_1_3_2_37_2","volume-title":"A Generalization of Birkhoff\u2019s Theorem for Distributive Lattices, with Applications to Robust Stable Matchings","author":"Mai Tung","year":"2018","unstructured":"Tung Mai and Vijay V. Vazirani. 2018. A Generalization of Birkhoff\u2019s Theorem for Distributive Lattices, with Applications to Robust Stable Matchings. Technical Report. arXiv:1804.05537 [cs.DM]. Cornell University."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00206-7"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1142\/8591"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-04612-5_23"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1037\/h0043158"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-019-00402-4"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481.004"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.3390\/a6040782"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90007-2"},{"key":"e_1_3_2_47_2","volume-title":"Two-sided Matching: A Study in Game-theoretic Modeling and Analysis","author":"Roth Alvin E.","year":"1992","unstructured":"Alvin E. Roth and Marilda A. Oliveira Sotomayor. 1992. Two-sided Matching: A Study in Game-theoretic Modeling and Analysis. Cambridge University Press."},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.5555\/2484920.2484987"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2020.01.009"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485000","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3485000","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:15Z","timestamp":1750191435000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485000"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,16]]},"references-count":47,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3485000"],"URL":"https:\/\/doi.org\/10.1145\/3485000","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,16]]},"assertion":[{"value":"2019-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}