Abstract: The Stable Marriage problem (SM), solved by the famous deferred acceptance algorithm of Gale and Shapley (GS), has many natural generalizations. If we allow ties in preferences, then the problem of finding a maximum stable matching becomes NP-hard, and the best known approximation ratio is 1.5, achievable by running GS on a cleverly constructed modified instance. Another elegant generalization of SM is the matroid kernel problem introduced by Fleiner (2001), which is solvable in polynomial time using an abstract matroidal version of GS. Our main result is a simple 1.5-approximation algorithm for the matroid kernel problem when preferences are given as interval orders—a broad subclass of partial orders that covers many applications beyond preferences with ties. In addition, for the bipartite matching case, we show that the output of our algorithm also 1.5-approximates the LP-optimum of the relaxation of the corresponding Integer Program, which shows that the integrality gap is at most 1.5 for the interval order case. To contrast this with hardness results, we show that if arbitrary partial orders are allowed in the preferences, then even in the bipartite matching case, the problem becomes hard to approximate within a factor better than 2 assuming the Unique Games Conjecture, and the integrality gap becomes 2.
Introduction
The classic Stable Marriage problem assumes that all participants have strict, linear rankings of their potential partners. However, real-world scenarios often involve indifference (ties) or incomparable options (partial orders). Furthermore, constraints on matching sets can be more complex than simple one-to-one pairings, often following the structure of matroids. This research bridges these two generalizations, addressing the "matroid kernel problem" under various preference structures.
Methodology
The authors focus on interval orders, a specific type of partial order where elements are represented by intervals on a real line. One element is preferred over another only if its interval is entirely to the right of the other's.
To solve the maximum stable matching problem in this context, the paper introduces a 1.5-approximation algorithm based on a three-step process:
- Instance Transformation: Each element in the original ground set is triplicated into three "parallel" elements in an extended set.
- Total Ordering: Specific total orders are constructed on this extended set that remain consistent with the original interval orders.
- Fleiner’s Algorithm: The algorithm runs a matroidal version of the Gale-Shapley algorithm on this expanded instance, then projects the results back to the original set.
To prove the 1.5 approximation ratio, the authors derived a new Basis Exchange Theorem for matroids. This theorem guarantees the existence of perfect matchings between specific types of exchangeable pairs in disjoint bases, providing the mathematical foundation for the algorithm's performance.
Key Results and Insights
The research identifies a significant "hardness jump" between different types of preference orders:
- Interval Orders: The proposed algorithm achieves a 1.5-approximation. This matches the integrality gap of the natural Linear Programming (LP) relaxation for this class, which is also shown to be at most 1.5.
- General Partial Orders: If arbitrary partial orders are allowed, the problem becomes significantly more difficult. The authors prove that it is NP-hard to approximate the maximum stable matching within a factor better than 2, assuming the Unique Games Conjecture (UGC). In this broader case, the integrality gap of the LP relaxation is exactly 2.
The algorithm is computationally efficient, with a running time quadratic in the size of the ground set $|S|$.
Conclusion and Future Work
By identifying interval orders as a "sweet spot" in matching theory, this work provides a robust 1.5-approximation for complex matroidal constraints that were previously unaddressed. While the factor of 2 appears to be a fundamental barrier for general partial orders under the UGC, future research could investigate other specific subclasses of partial orders or extend these techniques to even more general structures like polymatroids or n-way matching systems.
Summary updated