STABLE ROOMMATES MATCHINGS, MIRROR POSETS, MEDIAN GRAPHS, AND THE LOCAL/GLOBAL MEDIAN PHENOMENON IN STABLE MATCHINGS

摘要

For stable marriage (SM) and solvable stable roommates (SR) instances, it is known that there are stable matchings that assign each participant to his or her (lower/upper) median stable partner. Moreover, for SM instances, a stable matching has this property if and only if it is a median of the distributive lattice formed by the instance's stable matchings. In this paper, we show that the above local/global median phenomenon first observed in SM stable matchings also extends to SR stable matchings because SR stable matchings form a median graph. In the course of our investigations, we also prove that three seemingly different structures are pairwise duals of each other-median graphs give rise to mirror posets and vice versa, and mirror posets give rise to SR stable matchings and vice versa. Together, they imply that for every median graph G with n vertices, there is an SR instance I(G) with O(n~2) participants whose graph of stable matchings is isomorphic to G. Our results are analogous to the pairwise duality results known for distributive lattices, posets, and SM stable matchings. Interestingly, some of these results can also be inferred from the work of Feder in the early 1990s. Our constructions and proofs, however, are more natural generalizations of those used for SM instances.