{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T09:10:28Z","timestamp":1778231428857,"version":"3.51.4"},"reference-count":48,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematics of OR"],"published-print":{"date-parts":[[2026,5]]},"abstract":"<jats:p>Scarf\u2019s algorithm gives a pivoting procedure to find a special vertex\u2014a dominating vertex\u2014in a down-monotone polytope. This paper studies the behavior of Scarf\u2019s algorithm when employed to find stable matchings in bipartite graphs. First, it proves that Scarf\u2019s algorithm can be implemented to run in polynomial time, showing the first positive result on its runtime in significant settings. Second, it shows an infinite family of instances where, no matter the pivoting rule and runtime, Scarf\u2019s algorithm outputs a matching from an exponentially small subset of all stable matchings, thus showing a structural weakness of the approach.<\/jats:p>\n                  <jats:p>Funding: This work was supported by the Division of Computing and Communication Foundations [Grant 2046146]: An algorithmic theory of matching markets and the Meta Research Award to Y. Faenza and C. He.<\/jats:p>","DOI":"10.1287\/moor.2023.0055","type":"journal-article","created":{"date-parts":[[2025,5,15]],"date-time":"2025-05-15T12:55:26Z","timestamp":1747313726000},"page":"1174-1204","source":"Crossref","is-referenced-by-count":0,"title":["Scarf\u2019s Algorithm and Stable Marriages"],"prefix":"10.1287","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3148-2159","authenticated-orcid":false,"given":"Yuri","family":"Faenza","sequence":"first","affiliation":[{"name":"IEOR Department, Columbia University, New York, New York 10027"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3198-3719","authenticated-orcid":false,"given":"Chengyue","family":"He","sequence":"additional","affiliation":[{"name":"IEOR Department, Columbia University, New York, New York 10027"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9985-0683","authenticated-orcid":false,"given":"Jay","family":"Sethuraman","sequence":"additional","affiliation":[{"name":"IEOR Department, Columbia University, New York, New York 10027"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(02)00028-X"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1731"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050004"},{"key":"B4","volume-title":"Proc. Sympos. Math. Programming","volume":"301","author":"Balinski ML","year":"1970"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2013.10.001"},{"key":"B6","volume-title":"Introduction to Linear Optimization","volume":"6","author":"Bertsimas D","year":"2017"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2015.02.002"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-015-9491-5"},{"key":"B9","unstructured":"Black A, De Loera J, Kafer S, Sanit\u00e0 L (2021) On the simplex method for 0\/1 polytopes. Preprint, submitted November 28, https:\/\/arxiv.org\/abs\/2111.14050."},{"key":"B10","doi-asserted-by":"crossref","unstructured":"Bobbio F, Carvalho M, Lodi A, Rios I, Torrico A (2023) Capacity planning in stable matching: An application to school choice.\n                      Proc. 24th ACM Conf. Econom. Comput.\n                      (Association for Computing Machinery, New York), 295.","DOI":"10.1145\/3580507.3597771"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2015.0714"},{"key":"B12","doi-asserted-by":"crossref","unstructured":"Chen X, Deng X (2006) Settling the complexity of two-player Nash equilibrium.\n                      2006 47th Annual IEEE Sympos. Foundations Comput. Sci. (FOCS\u201906)\n                      (IEEE, Piscataway, NJ), 261\u2013272.","DOI":"10.1109\/FOCS.2006.69"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1137\/140996690"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2021.2184"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2022.07.025"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1137\/070699652"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2020.2042"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2010.05.162"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1137\/140979150"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0616"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-022-01838-z"},{"key":"B22","unstructured":"Fleiner T (2000) Stable and crossing structures. Unpublished PhD thesis, Eindhoven University of Technology, Eindhoven, Netherlands."},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584085"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989827"},{"key":"B25","volume-title":"The Stable Marriage Problem: Structure and Algorithms","author":"Gusfield D","year":"1989"},{"key":"B26","unstructured":"Haxell PE, Wilfong GT (2008) A fractional model of the border gateway protocol (BGP).\n                      SODA\u201908: Proc. 19th Annual ACM-SIAM Sympos. Discrete Algorithms\n                      (Society for Industrial and Applied Mathematics, Philadelphia), 193\u2013199."},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28871"},{"key":"B28","doi-asserted-by":"crossref","unstructured":"Ishizuka T, Kamiyama N (2018) On the complexity of stable fractional hypergraph matching.\n                      29th Internat. Sympos. Algorithms Comput (ISAAC 2018)\n                      , vol. 11 (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Wadern, Germany), 1\u201312.","DOI":"10.1155\/2018\/7409397"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1137\/120874655"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.07.005"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1090\/chel\/367"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1007\/BF01211824"},{"key":"B33","doi-asserted-by":"publisher","DOI":"10.1142\/8591"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1257\/aer.20141188"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2019.1909"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2020.3869"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614365"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.2307\/2938326"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1287\/moor.18.4.803"},{"key":"B41","doi-asserted-by":"publisher","DOI":"10.1007\/BF01586041"},{"key":"B42","doi-asserted-by":"crossref","unstructured":"Sanit\u00e0 L (2018) The diameter of the fractional matching polytope and its hardness implications.\n                      2018 IEEE 59th Annual Sympos. Foundations Comput. Sci. (FOCS)\n                      , (IEEE, Piscataway, NJ), 910\u2013921.","DOI":"10.1109\/FOCS.2018.00090"},{"key":"B43","doi-asserted-by":"publisher","DOI":"10.2307\/1909383"},{"key":"B44","doi-asserted-by":"publisher","DOI":"10.1080\/00207169108803975"},{"key":"B45","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614369"},{"key":"B46","doi-asserted-by":"publisher","DOI":"10.1287\/moor.23.4.874"},{"key":"B47","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(89)90041-2"},{"key":"B48","unstructured":"Vohra R (2019) Scarf\u2019s lemma and applications. Accessed August 24, 2015, https:\/\/simons.berkeley.edu\/talks\/scarfs-lemma-applications."}],"container-title":["Mathematics of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/moor.2023.0055","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T08:24:04Z","timestamp":1778228644000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/moor.2023.0055"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5]]}},"alternative-id":["10.1287\/moor.2023.0055"],"URL":"https:\/\/doi.org\/10.1287\/moor.2023.0055","relation":{},"ISSN":["0364-765X","1526-5471"],"issn-type":[{"value":"0364-765X","type":"print"},{"value":"1526-5471","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5]]}}}