AI Insight
This study compares five different computational methods (Answer Set Programming, Constraint Programming, Integer Linear Programming, Propositional Satisfiability, and Local Search) for solving the Stable Marriage problem with Ties and Incomplete preferences (SMTI). The researchers evaluated these methods across three optimization variants: maximizing the number of matches, achieving sex-equal outcomes, and finding egalitarian solutions. The empirical comparison provides insights into which computational approaches are most effective for different variants of this matching problem.
Why it matters
The stable marriage problem has practical applications in real-world matching scenarios such as medical residency assignments, school admissions, and job market matching where participants may have incomplete information or indifference between options. Understanding which computational methods work best can improve the efficiency and fairness of these matching systems.
Understand the Science
⚠️ Preprint – Noch nicht peer-reviewed
Dieser Artikel wurde noch nicht von unabhängigen Experten begutachtet. Die Ergebnisse sind vorläufig und sollten mit Vorsicht interpretiert werden.
Abstract: We study a variation of the Stable Marriage problem, where every man and every woman express their preferences as preference lists which may be incomplete and contain ties. This problem is called the Stable Marriage problem with Ties and Incomplete preferences (SMTI). We consider three optimization variants of SMTI, Max Cardinality, Sex-Equal and Egalitarian, and empirically compare the following methods to solve them: Answer Set Programming, Constraint Programming, Integer Linear Programming. For Max Cardinality, we compare these methods with Local Search methods as well. We also empirically compare Answer Set Programming with Propositional Satisfiability, for SMTI instances.