Approximation Algorithms for Matroidal and Cardinal Generalizations of Stable Matching

Gergely Kál Csáji, Tamás Király, Yu Yokoi

This paper, titled "Maximum Stable Matching with Matroids and Partial Orders," bridges a significant gap in matching theory by combining two powerful generalizations of the classic Stable Marriage problem.

TL;DR

The authors present a 1.5-approximation algorithm for finding the maximum stable matching when constraints are defined by matroids and preferences are given as "interval orders." They also prove that for general partial orders, achieving an approximation ratio better than 2 is NP-hard under the Unique Games Conjecture.

What Problem Does This Paper Address?

The classic Stable Marriage problem (solved by the Gale-Shapley algorithm) assumes everyone has a strict, linear ranking of partners. Real-world scenarios are rarely that simple. Researchers have previously extended this in two main directions:

  1. Preferences with Ties/Partial Orders: When people are indifferent between options (ties) or cannot compare certain options (partial orders), finding the largest stable matching becomes NP-hard.
  2. Matroid Constraints: Instead of simple one-to-one matching, agents might have complex constraints on who they can be matched with (e.g., a hospital needing a specific mix of residents). This is known as the "matroid kernel problem."

While a 1.5-approximation exists for the "ties" case and a polynomial-time solution exists for the "matroid" case with strict preferences, the combination of the two—matroids with partial orders—remained an open challenge. This paper seeks to find how well we can approximate the maximum stable matching in this generalized setting.

Methods

The authors introduce a 1.5-approximation algorithm for the matroid kernel problem with interval orders. Interval orders are a specific type of partial order where elements are represented by intervals on a real line (one element is "better" than another only if its interval is completely to the right of the other).

The algorithm follows three main steps:

  1. Instance Transformation: Each element in the original ground set is replaced by three "parallel" elements in an extended set.
  2. Total Ordering: The authors construct specific total orders on this extended set that are consistent with the original interval orders.
  3. Fleiner’s Algorithm: They run an existing matroidal version of the Gale-Shapley algorithm (Fleiner’s algorithm) on this new, larger instance. The result is then projected back to the original set.

To prove the 1.5 ratio, the authors derive a new Basis Exchange Theorem for matroids, which guarantees the existence of perfect matchings between certain types of exchangeable pairs in disjoint bases.

Datasets

This is a theoretical paper in computer science and discrete mathematics; therefore, no empirical datasets were used. The results are proven mathematically for all possible instances that satisfy the defined constraints.

Key Insights and Ideas

  • The Power of Interval Orders: The paper identifies "interval orders" as the "sweet spot." They are broad enough to model many practical stability notions (like $\alpha$-stability or near-stability) but structured enough to allow for a 1.5-approximation.
  • The "Three-Element" Trick: By triplicating elements, the algorithm effectively allows for a more nuanced "proposal" process that can handle the ambiguity of incomparable preferences without losing too much efficiency.
  • The Hardness Jump: A major insight is the sharp divide between interval orders and general partial orders. While interval orders allow for a 1.5-approximation, general partial orders hit a "barrier" at 2.
  • Integrality Gap Alignment: The authors show that the algorithmic approximation ratio (1.5) matches the integrality gap of the natural Linear Programming (LP) relaxation for interval orders.

Key Results

  • 1.5-Approximation: The proposed algorithm achieves a 1.5-approximation for the maximum matroid kernel problem with interval orders.
  • Hardness of Approximation: Assuming the Unique Games Conjecture (UGC), the authors prove it is NP-hard to approximate the maximum stable matching with general partial orders within a factor better than 2.
  • Integrality Gaps:
    • For interval orders, the integrality gap of the standard LP relaxation is at most 1.5.
  • For general partial orders, the integrality gap is exactly 2.
  • Complexity: The algorithm's running time is quadratic in the size of the ground set $|S|$, making it computationally efficient.

Limitations and Future Work

  • UGC Dependence: The hardness results (the factor of 2) rely on the validity of the Unique Games Conjecture, a famous unproven conjecture in computational complexity.
  • Subclasses of Partial Orders: While the paper draws a line at interval orders, there may be other specific subclasses of partial orders that allow for better than 2-approximations but are not interval orders.
  • Beyond Matroids: The authors suggest that exploring even more general structures, such as polymatroids or $n$-way matching, could be a fruitful direction for future research.

Summary updated

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 (McDermid 2009, Paluch 2011, Z. Kir\'aly 2012), 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.
BibTeX
@inproceedings{csaji2023approximation,
  author = {Gergely Kál Csáji and Tamás Király and Yu Yokoi},
  title = {{Approximation Algorithms for Matroidal and Cardinal Generalizations of Stable Matching}},
  booktitle = {SOSA},
  year = {2023},
  doi = {10.1137/1.9781611977585.ch10},
}

Loading related content...

Figure