Research Experience for Undergraduates (REU) Seminar

Title: How Good (or Bad) Can Stable Marriages Be?

Speaker: Endre Boros, Rutgers University

Date: June 21, 2005 12:30 - 2:00 pm

Location: DIMACS Center, CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ


Stable marriages are widely used in game theory, economics and sociology to model e.g., job markets, supplier-consumer relations, etc., and even the fairness and/or robustness of certain economic or social processes. A recent bibliography contains well over 100 items published just in the past decade. Most of these studies focus on the properties of and/or algorithms for finding a stable matching in a particular situation. In this study we focus on quality measures associated to stable matchings, and study their properties over all possible input situations. In particular, we associate a so called rank- profile to stable marriages, which describes the quality of the marriages from the point of view of the participating individuals. We give a full characterization of stable rank-profiles, and prove that there are instances when no individual can get better than the middle in his/her preference list in any stable marriage. We also study unique rank-profiles, and demonstrate by troubling examples that a "miserable couple moving into the village can easily spoil the life for everybody."

Joint work with L. Fedzhora, V. Gurvich and S. Jaslar.