Strategy-Proof Approximation Algorithms for the Stable Marriage Problem with Ties and Incomplete Lists

Koki Hamada, Shuichi Miyazaki, Hiroki Yanagisawa

In the stable marriage problem (SM), a mechanism that always outputs a stable matching is called a stable mechanism. One of the well-known stable mechanisms is the man-oriented Gal…