ECAI-2002 Conference Paper

[full paper]

An Empirical Study of the Stable Marriage Problem with Ties and Incomplete Lists

Ian Gent, Patrick Prosser

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) 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 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. 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.

Keywords: constraint programming, constraint satisfaction, search

Citation: Ian Gent, Patrick Prosser: An Empirical Study of the Stable Marriage Problem with Ties and Incomplete Lists. In F. van Harmelen (ed.): ECAI2002, Proceedings of the 15th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2002, pp.141-145.