# Stable Marriage Problems with Ties and Incomplete Preferences: An Empirical Comparison of ASP, SAT, ILP, CP, and Local Search Methods

arXiv: https://arxiv.org/abs/2108.05165 · HTML: https://mlsanity.com/paper/2108.05165/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 45 references that are in the map.
- First posted on arXiv 11 Aug 2021.

## Builds on (most cited first, 4 of 4)

- [Multi-shot ASP solving with clingo](https://mlsanity.com/paper/1705.09811/) (2017)
- [Mathematical models for stable matching problems with ties and incomplete lists](https://mlsanity.com/paper/1810.02711/) (2018)
- [A General Framework for Stable Roommates Problems using Answer Set Programming](https://mlsanity.com/paper/2008.03050/) (2020)
- [An Integer Programming Approach to the Hospital/Residents Problem with Ties](https://mlsanity.com/paper/1308.4064/) (2013)

## Built on by (most cited first, 1 of 1)

- [From Preference to Reciprocity: Decentralized Matching with Empirically Grounded LLM-agent Based Modeling](https://mlsanity.com/paper/2609.34679/) (2026)

## Abstract (arXiv)

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.