11 March 2010, CWI-DIAMANT Seminar Combinatorics and Optimization, Dov Samet

The core of a marriage problem consists of its stable matchings. When men and women are objectively ranked in a marriage problem, say by beauty, then the core is a singleton: pairing individuals of equal rank is the only stable matching. We generalize this observation using natural metrics on rankings and on matchings, as well as a measure of the gap in rank between mates in a matching. We provide bounds on the diameter of the core, and on the rank gap of stable matchings in terms of the diameters of the sets of rankings, and conclude that when the set of rankings is small, so are the core and the rank gap in stable matchings. We also show that when the rank gap in stable matchings is small, then the core is also small.

For more information, see http://homepages.cwi.nl/~monique/acoseminar/.