Scarf's Algorithm and Stable Marriages

• 成果类型: Article; Early Access
• 署名作者: Faenza, Yuri; He, Chengyue; Sethuraman, Jay
• 署名单位: Columbia University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2023.0055
• 发表日期: 2025
• 关键词: matchings; complexity; STABILITY; admissions

摘要

Scarf's algorithm gives a pivoting procedure to find a special vertex-a dominating vertex-in a down-monotone polytope. This paper studies the behavior of Scarf's algorithm when employed to find stable matchings in bipartite graphs. First, it proves that Scarf's 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's algorithm outputs a matching from an exponentially small subset of all stable matchings, thus showing a structural weakness of the approach.