Abstract | ||
---|---|---|
The stable marriage problem is a well-known problem of matching men to women so that no man and woman who are not married to each other both prefer each other. Such a problem has a wide variety of practical applications ranging from matching resident doctors to hospitals to matching students to schools. A well-known algorithm to solve this problem is the Gale-Shapley algorithm, which runs in polynomial time. It has been proven that stable marriage procedures can always be manipulated. Whilst the Gale-Shapley algorithm is computationally easy to manipulate, we prove that there exist stable marriage procedures which are NP-hard to manipulate. We also consider the relationship between voting theory and stable marriage procedures, showing that voting rules which are NP-hard to manipulate can be used to define stable marriage procedures which are themselves NP-hard to manipulate. Finally, we consider the issue that stable marriage procedures like Gale-Shapley favour one gender over the other, and we show how to use voting rules to make any stable marriage procedure gender neutral. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1145/1558013.1558105 | Clinical Orthopaedics and Related Research |
Keywords | DocType | Volume |
stable marriage procedure,gender neutrality,stable marriage problem,practical application,voting rule,gale-shapley algorithm,polynomial time,well-known problem,gale-shapley favour,stable marriage procedure gender,well-known algorithm | Conference | abs/0909.4437 |
Citations | PageRank | References |
15 | 0.79 | 16 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Maria Silvia Pini | 1 | 353 | 30.28 |
Francesca Rossi | 2 | 2067 | 176.42 |
K. Brent Venable | 3 | 162 | 13.58 |
Toby Walsh | 4 | 4836 | 416.00 |