Please use this identifier to cite or link to this item:
Title: Many-to-one stable matching: Geometry and fairness
Authors: Sethuraman, J.
Teo, C.-P. 
Qian, L. 
Keywords: Fairness
Linear programming
Matching with couples
Randomized rounding
Stable matching
Two-sided market
University admissions
Issue Date: 2006
Source: Sethuraman, J., Teo, C.-P., Qian, L. (2006). Many-to-one stable matching: Geometry and fairness. Mathematics of Operations Research 31 (3) : 581-596. ScholarBank@NUS Repository.
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.
Source Title: Mathematics of Operations Research
ISSN: 0364765X
DOI: 10.1287/moor.1060.0207
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Feb 28, 2018


checked on Feb 20, 2018

Page view(s)

checked on Feb 27, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.