IJPAM: Volume 52, No. 3 (2009)

GLOBALLY-SATISFYING AND EQUITABLE STABLE
MARRIAGES AND THEIR COMPLEXITY

Nikom Suvonvorn$^1$, Bertrand Zavidovique$^2$
$^{1,2}$Institut d'Electronique Fondamentale
Bât. 220, Université Paris-Sud
Centre Scientifique d'Orsay
Orsay Cedex, 91405, FRANCE
$^1$e-mail: [email protected]
$^2$e-mail: [email protected]


Abstract.This paper deals with designing algorithms based on the ``stable marriages" paradigm, for them to take additional constraints into account. First algorithms scan the so-called ``marriage table" to optimize ``global satisfaction" and ``equity" over all couples. Then, we introduce an hybrid version between the Gale-Shappley classical algorithm and ours. Results on thousands of populations, up to 200 person large, are systematically evaluated. These algorithms progressively improve both satisfaction and equity but they do not guarantee complete stability. Thus, the BZ algorithm is made to blow blockages out. It still produces about 5% instable results in average. After a case study that sorts blocking situations into 4 types, we explain how to resolve instability in forcing blocking pairs to marry wrt. their type. The resulting S-procedure applies after every previous algorithm, and results are systematically compared to Gale-Shapley's on 1000 instances of a 200-person-large population. In conclusion, a more experimental study of the complexity allows to suggest trade off criterions between maximal quality and rapidity.

Received: March 29, 2009

AMS Subject Classification: 68W40

Key Words and Phrases: stable marriages, marriage table, matching algorithm

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2009
Volume: 52
Issue: 3