Summary
This work addresses the problem of matching two groups of people, like men and women, where not everyone lists all possible partners and where ties in preferences may occur. The researchers developed an exact algorithm to find the largest set of matches that are stable under weak stability rules, meaning no pair wants to deviate given the ties. Importantly, their method runs in single-exponential time, which improves the efficiency over previous approaches for this problem.
What this means in practice
- •For matching platform developers: Improve algorithms used in platforms matching people or entities with incomplete and tied preference lists for faster and exact maximum stable matchings.
- •For marketplace designers: Design efficient matching mechanisms in markets with complex preference scenarios including ties and incomplete information.
Authors
Shuichi Miyazaki, Suguru Tamaki
Abstract
We study Stable Marriage with Ties and Incomplete lists (SMTI) under weak stability. For an instance with $n$ agents on each side, we give an exact algorithm that returns a maximum-cardinality weakly stable matching in $O^*(22.74^n)$ time. To the best of our knowledge, this is the first exact algorithm for this problem running in single-exponential time.