Many-to-one stable matching: Geometry and fairness

Abstract

Baïou and Balinski characterized the stable admissions polytope using a system of linear inequalities. The structure of feasible solutions to this system of inequalities - fractional stable matchings - is the focus of this paper. The main result associates a geometric structure with each fractional stable matching. This insight appears to be interesting in its own right, and can be viewed as a generalization of the lattice structure (for integral stable matchings) to fractional stable matchings. In addition to obtaining simple proofs of many known results, the geometric structure is used to prove the following two results: First, it is shown that assigning each agent their "median" choice among all stable partners results in a stable matching, which can be viewed as a "fair" compromise; second, sufficient conditions are identified under which stable matchings exist in a problem with externalities, in particular, in the stable matching problem with couples. © 2006 INFORMS.