{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,9]],"date-time":"2026-02-09T23:39:19Z","timestamp":1770680359051,"version":"3.49.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T00:00:00Z","timestamp":1664496000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2022,9,30]]},"abstract":"<jats:p>\n            In the stable marriage (SM) problem, there are two sets of agents\u2014traditionally referred to as men and women\u2014and each agent has a preference list that ranks (a subset of) agents of the opposite sex. The goal is to find a matching between men and women that is stable in the sense that no man-woman pair mutually prefers each other to their assigned partners. In a seminal work, Gale and Shapley\u00a0[\n            <jats:xref ref-type=\"bibr\">16<\/jats:xref>\n            ] showed that stable matchings always exist and described an efficient algorithm for finding one.\n          <\/jats:p>\n          <jats:p>\n            Irving and Leather\u00a0[\n            <jats:xref ref-type=\"bibr\">24<\/jats:xref>\n            ] defined the rotation poset of an SM instance and showed that it determines the structure of the set of stable matchings of the instance. They further showed that every finite poset can be realized as the rotation poset of some SM instance. Consequently, many problems\u2014such as counting stable matchings and finding certain \u201cfair\u201d stable matchings\u2014are computationally intractable (NP-hard) in general.\n          <\/jats:p>\n          <jats:p>\n            In this article, we consider SM instances in which certain restrictions are placed on the preference lists. We show that three natural preference models\u2014\n            <jats:italic>k<\/jats:italic>\n            -bounded,\n            <jats:italic>k<\/jats:italic>\n            -attribute, and\n            <jats:italic>\n              (k\n              <jats:sub>1<\/jats:sub>\n              , k\n              <jats:sub>2<\/jats:sub>\n              )\n            <\/jats:italic>\n            -list\u2014can realize arbitrary rotation posets for constant values of\n            <jats:italic>k<\/jats:italic>\n            . Hence, even in these highly restricted preference models, many stable matching problems remain intractable. In contrast, we show that for any fixed constant\n            <jats:italic>k<\/jats:italic>\n            , the rotation posets of\n            <jats:italic>k<\/jats:italic>\n            -range instances are highly restricted. As a consequence, we show that exactly counting and uniformly sampling stable matchings, finding median, sex-equal, and balanced stable matchings, are fixed-parameter tractable when parameterized by the range of the instance. Thus, these problems can be solved in polynomial time on instances of the k-range model for any fixed constant k.\n          <\/jats:p>","DOI":"10.1145\/3565558","type":"journal-article","created":{"date-parts":[[2022,12,1]],"date-time":"2022-12-01T12:37:16Z","timestamp":1669898236000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Stable Matchings with Restricted Preferences: Structure and Complexity"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0524-5368","authenticated-orcid":false,"given":"Christine T.","family":"Cheng","sequence":"first","affiliation":[{"name":"University of Wisconsin, Milwaukee, WI, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7723-9090","authenticated-orcid":false,"given":"Will","family":"Rosenbaum","sequence":"additional","affiliation":[{"name":"Amherst College, Amherst, MA, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,2,15]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"1223","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908)","author":"Bhatnagar Nayantara","year":"2008","unstructured":"Nayantara Bhatnagar, Sam Greenberg, and Dana Randall. 2008. Sampling stable marriages: Why spouse-swapping won\u2019t work. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908). Society for Industrial and Applied Mathematics, Philadelphia, PA, 1223\u20131232. http:\/\/dl.acm.org\/citation.cfm?id=1347082.1347215. event-place: San Francisco, California."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmateco.2006.09.004"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.11.009"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.02.029"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78773-0_49"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9307-2"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.11.016"},{"key":"e_1_3_2_10_2","unstructured":"Christine T. Cheng and Will Rosenbaum. 2020. Simple Counting and Sampling Algorithms for Graphs with Bounded Pathwidth. (2020). Working paper."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00606-4"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1073-y"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.5555\/526453"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9353-9"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1090\/pspum\/007\/0152944"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989827"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90074-5"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2018.10.013"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-24766-9_31"},{"key":"e_1_3_2_21_2","unstructured":"Sushmita Gupta Saket Saurabh and Meirav Zehavi. 2017. On Treewidth and Stable Marriage. (2017). _eprint: 1707.05404."},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/0216010"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.5555\/68392"},{"key":"e_1_3_2_24_2","volume-title":"Marriage, Honesty, and Stability","author":"Immorlica Nicole","year":"2003","unstructured":"Nicole Immorlica and Mohammed Mahdian. 2003. Marriage, Honesty, and Stability. Technical Report MIT-CSAIL-TR-2003-007. Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory. http:\/\/hdl.handle.net\/1721.1\/30405."},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1137\/0215048"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28871"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.01.002"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188848"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF03167200"},{"key":"e_1_3_2_30_2","first-page":"12","volume-title":"20th International Conference on Principles of Distributed Systems (OPODIS\u201916)","volume":"70","author":"Khanchandani Pankaj","year":"2017","unstructured":"Pankaj Khanchandani and Roger Wattenhofer. 2017. Distributed stable matching with similar preference lists. In 20th International Conference on Principles of Distributed Systems (OPODIS\u201916), Vol. 70. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 12."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2009.69"},{"key":"e_1_3_2_32_2","volume-title":"Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms","author":"Knuth D. E.","year":"1997","unstructured":"D. E. Knuth, N. G. De Bruijn, and M. Goldstein. 1997. Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms. American Mathematical Society. cn97006265. https:\/\/books.google.de\/books?id=NSnaBwAAQBAJ."},{"key":"e_1_3_2_33_2","volume-title":"Marriage stables et leurs relations avec d\u2019autres probl\u00e8mes combinatoires","author":"Knuth Donald E.","year":"1976","unstructured":"Donald E. Knuth. 1976. Marriage stables et leurs relations avec d\u2019autres probl\u00e8mes combinatoires. Les Presses de l\u2019Universit\u00e9 de Montr\u00e9al."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00564-x"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746598"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1142\/8591"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00206-7"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9326-z"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2010.07.004"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9672-0"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1137\/0219004"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767424"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1137\/0212053"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.2307\/1913160"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-46908-4_70"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.23.4.874"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3565558","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3565558","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:51Z","timestamp":1750182531000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3565558"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,30]]},"references-count":47,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,9,30]]}},"alternative-id":["10.1145\/3565558"],"URL":"https:\/\/doi.org\/10.1145\/3565558","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,30]]},"assertion":[{"value":"2021-08-13","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-09-30","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-02-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}