Scarf’s Algorithm and Stable Marriages
研究了Scarf算法在二分图中寻找稳定匹配的表现，证明其可在多项式时间内实现，但也发现该算法只能输出指数级小部分稳定匹配，暴露了结构弱点。
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. 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.