Computing at Glasgow University
Paper ID: 6474

An Empirical Study of the Stable Marriage Problem with Ties and Incomplete Lists
Gent,I.P. Prosser,P.

Publication Type: Conference Proceedings
Appeared in: Proceedings of the 15th European Conference on Artificial Intelligence (ECAI 2002)
Page Numbers :
Publisher: Academic Press
Year: 2002

Note: to appear


We present the first complete algorithm for the SMTI problem, the stable marriage problem with ties and incomplete lists. We do this in the form of a constraint programming encoding of the problem. With this we are able to carry out the first empirical study of the complete solution of SMTI instances. In the stable marriage problem (SM) \cite{gi89} we have $n$ men and $n$ women. Each man ranks the $n$ women, giving himself a preference list. Similarly each woman ranks the men, giving herself a preference list. The problem is then to marry men and women such that they are {\em stable} i.e. such that there is no incentive for individuals to divorce and elope. This problem is polynomial time solvable. However, when preference lists contain ties and are incomplete (SMTI) the problem of determining if there is a stable matching of size $n$ is then NP-complete, as is the optimisation problem of finding the largest or smallest stable matching \cite{smti99,smti2002}. In this paper we present constraint programming solutions for the SMTI decision and optimisation problems, a problem generator for random instances of SMTI, and an empirical study of this problem.

PDF Bibtex entry Endnote XML