Scarf's algorithm and stable marriages
From MaRDI portal
Publication:6428110
arXiv2303.00791MaRDI QIDQ6428110FDOQ6428110
Authors: Yuri Faenza, Chengyue He, Jay Sethuraman 
Publication date: 1 March 2023
Abstract: Scarf's algorithm gives a pivoting procedure to find a special vertex -- a dominating vertex -- in down-monotone polytopes. 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.
This page was built for publication: Scarf's algorithm and stable marriages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6428110)
