Understanding the Generalized Median Stable Matchings

作者：Cheng Christine T^*

来源：Algorithmica, 2010, 58(1): 34-51.

DOI：10.1007/s00453-009-9307-2

• Stable matchings
• Fair stable matchings
• Medians in distributive lattices
• Counting closed subsets or antichains

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 alpha (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 alpha (i) a matching, it is also stable. The alpha (i) 's are called the generalized median stable matchings of I. Determining if these stable matchings can be computed efficiently is an open problem.
In this paper, we present a new characterization of the generalized median stable matchings that provides interesting insights. It implies that the generalized median stable matchings in the middle-alpha ((N 1)/2) when N is odd, alpha (N/2) and alpha (N/2 1) when N is even-are fair not only in a local sense but also in a global sense because they are also medians of the lattice of stable matchings. We then show that there are some families of SM instances for which computing an alpha (i) is easy but that the task is NP-hard in general. Finally, we also consider what it means to approximate a median stable matching and present results for this problem.

• 出版日期2010-9