Paper ID: 9378
Improving man-optimal stable matchings by minimum change of preference lists
Proceedings of the 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications (Kyoto, Japan)
Page Numbers : 309-313
In the stable marriage problem, any instance admits so-called the man-optimal stable matching, in which every man is assigned the best possible partner. However, there are instances for which all men receive low-ranked partners even in the man-optimal stable matching. In this paper we consider the problem of improving the man-optimal stable matching by changing only one man’s preference list. We
show that the optimization variant and the decision variant of this problem can be solved in time O(n^3) and O(n^2), respectively, where n is the number of men (women)
in an input.
Keywords: stable marriage problem, man-optimal stable matching