Understanding the Generalized Median Stable Matchings

摘要

Let I be a stable matching instance with N stable matchings. For each man m, order his (not necessarily distinct) N partners from his most preferred to his least preferred. Denote the ith woman in his sorted list as p _i (m). Let α _i consist of the man-woman pairs where each man m is matched to p _i (m). Teo and Sethuraman proved this surprising result: for i=1 to N, not only is α _i a matching, it is also stable. The α _i ’s are called the generalized median stable matchings of I. Determining if these stable matchings can be computed efficiently is an open problem.