Paper Info
Title
On heuristics for two-sided matching: revisiting the stable marriage problem as a multiobjective problem
Abstract
The stable marriage problem is prototypical of two-sided matching problems, widely encountered in practice, in which agents having preferences, interests and capacities for action of their own are paired up or matched. Standardly, variants of the well-known Gale-Shapley deferred acceptance algorithm (GS/DAA) are used to find stable matches. Using evolutionary computation and an agent-based model heuristics, this paper investigates the stable marriage problem as a multiobjective problem, looking at social welfare and equity or fairness, in addition to stability as important aspects of any proposed match. The paper finds that these heuristics are reliably able to discover matches that are Pareto superior to those found by the GS/DAA procedure. Ramifications of this finding are briefly explored, including the question of whether stability in a matching is often strictly required
Year
DOI
Venue
2010
10.1145/1830483.1830712
GECCO
Keywords
Field
DocType
daa procedure,evolutionary computation,multiobjective problem,stable marriage problem,proposed match,agent-based model heuristics,social welfare,important aspect,two-sided matching problem,stable match,stable matching,evolutionary computing
Stable roommates problem,Mathematical optimization,Mathematical economics,Stable marriage problem,Computer science,Evolutionary computation,Heuristics,Equity (finance),Artificial intelligence,Machine learning,Pareto principle,Social Welfare
Conference
Citations 
PageRank 
References 
6
0.48
7
Authors
2
Name
Order
Citations
PageRank
Steven O. Kimbrough1600103.93
Ann Kuo281.27