On Heuristics for Two-Sided Matching: Revisiting the Stable Marriage Problem as a Multiobjective Problem∗

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 algo-rithm (GS/DAA) are used to find stable matches. Using evolutionary computation and an agent-based model heuris-tics, 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