Name
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. It has a wide variety of practical applications, ranging from matching resident doctors to hospitals, to matching students to schools, or more generally to any two-sided market. Given a stable marriage problem, it is possible to find a male-optimal (resp., female-optimal) stable marriage in polynomial time. However, it is sometimes desirable to find stable marriages without favoring one group at the expenses of the other one. To achieve this goal, we consider a local search approach to find stable marriages with the aim of exploiting the non-determinism of local search to give a fair procedure. We test our algorithm on classes of stable marriage problems, showing both its efficiency and its sampling capability over the set of all stable marriages, and we compare it to a Markov chain approach. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.5555/2034396.2034491 | AAMAS |
Keywords | Field | DocType |
resident doctor,stable marriage,stable marriage problem,practical application,polynomial time,fair procedure,well-known problem,local search approach,Markov chain approach,procedural fairness,local search | Stable roommates problem,Stable marriage problem,Computer science,Markov chain,Theoretical computer science,Artificial intelligence,Sampling (statistics),Local search (optimization),Time complexity,Machine learning | Conference |
ISBN | Citations | PageRank |
0-9826571-7-X | 4 | 0.46 |
References | Authors | |
3 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mirco Gelain | 1 | 72 | 5.37 |
| Maria Silvia Pini | 2 | 353 | 30.28 |
| Francesca Rossi | 3 | 2067 | 176.42 |
| Kristen Brent Venable | 4 | 351 | 37.00 |
| Toby Walsh | 5 | 4836 | 416.00 |