Modeling Stable Matching Problems with Answer Set Programming

The Stable Marriage Problem (SMP) is a well-known matching problem fi rst introduced and
solved by Gale and Shapley [7]. Several variants and extensions to this problem have since been
investigated to cover a wider set of applications. Each time a new variant is considered, however,
a new algorithm needs to be developed and implemented. As an alternative, in this paper we
propose an encoding of the SMP using Answer Set Programming (ASP). Our encoding can easily
be extended and adapted to the needs of specifi c applications. As an illustration we show how
stable matchings can be found when individuals may designate unacceptable partners and ties
between preferences are allowed. Subsequently, we show how our ASP based encoding naturally
allows us to select specifi fic stable matchings which are optimal according to a given criterion. Each
time, we can rely on generic and efficient o f-the-shelf answer set solvers to find (optimal) stable
matchings.

ISBN:978-3-642-39616-8

Publication year:2013

Keywords:Answer Set Programming, Logic Rules, Stable Marriage