## The Set of all Stable Matchings is always a Distributive Lattice |

**XingNi Chen**

Union College

April 3, 2006

4:45 pm

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.

For additional information, send e-mail to math@union.edu or call (518) 388-6246.

Union College Math Department Home PageComments to: math@union.edu Created automatically on: Tue Oct 23 19:03:05 EDT 2018 |