The Set of all Stable Matchings is always a Distributive Lattice
April 3, 2006
Bailey Hall 201
Pastries and drinks will be served in Bailey 204 at 4:30
Although there is extensive ongoing research into two-sided matching problems, there even the simplest marriage matching problem remains interesting. In this paper, we deal with the model wherein a marriage market consists of n men and n women. Each of the 2n people has a linear preference among those of the opposite sex, and n couples will be formed through this matching. A matching is said to be stable if we cannot find a man in one pair and a woman in another pair each of whom prefers the other to their present partner. We show that the set of all stable matchings can be represented by a distributive lattice, in which each stable matching corresponds to a point in the lattice. Furthermore, we discuss Charles Blairís proof that for every distributive lattice, we can find a marriage matching game whose set of stable matchings is isomorphic to this lattice. There exists a men-optimal stable matching and a women-optimal stable matching. The men-optimal stable matching is found at the very top of the corresponding lattice, and the women-optimal stable matching will be found at the very bottom. Alternatively, if we put the women-optimal matching on the top, then the men-optimal matching will have to be at the bottom. More generally, the lattice order reflects opposing collective preference of the men and the women.
|Union College Math Department Home Page|
Comments to: firstname.lastname@example.org
Created automatically on: Tue Oct 23 19:03:05 EDT 2018