A Natural Generalization of Stable Matching Solved via New Insights into Ideal Cuts

Tung Mai, Vijay V. VaziraniarXiv 2018 · OpenReview

Abstract

We study a natural generalization of the classic stable matching problem: the maximum weight stable matching problem. We present the first combinatorial polynomial-time algorithm for this problem by reducing it to finding a maximum weight ideal cut in a directed acyclic graph (DAG). We also provide the first combinatorial polynomial-time algorithm for the maximum weight ideal cut problem itself. Beyond algorithmic efficiency, our approach reveals deep structural properties: the set of maximum weight stable matchings forms a sublattice of the lattice of all stable matchings. We introduce "meta-rotations" to traverse this sublattice and provide algorithms for finding boy-optimal and girl-optimal matchings within the optimal set.

Introduction

The Stable Matching problem, famously addressed by the Gale-Shapley algorithm, involves pairing two sets of agents such that no pair has an incentive to deviate. While Gale-Shapley finds a stable matching, many applications require finding the "best" stable matching according to specific weights assigned to potential pairs. This is formalized as the maximum weight stable matching problem.

While Linear Programming (LP) techniques can solve this problem due to the known integrality of the stable matching polytope, a purely combinatorial algorithm—one that relies on graph-theoretic operations rather than general-purpose LP solvers—has remained elusive. This paper fills that gap by linking stable matching to the theory of ideal cuts in directed acyclic graphs (DAGs).

The Maximum Weight Ideal Cut Problem

A central contribution of this work is a new algorithm for the maximum weight ideal cut problem. Given a DAG with weights on its vertices, an ideal cut partitions the vertices into a source-set $S$ and a sink-set $\bar{S}$ such that no edges exist from $S$ to $\bar{S}$. The goal is to maximize the total weight of the vertices in $S$.

The authors demonstrate that this problem can be solved combinatorially by examining the dual of its LP formulation. They interpret this dual as a network flow problem where edge capacities serve as lower bounds on the flow. By designing a Ford-Fulkerson-style algorithm to minimize flow in this context, they achieve a polynomial-time solution that avoids the overhead of general LP methods. Furthermore, they prove the integrality of the ideal cut polyhedron, showing that its vertices correspond exactly to ideal cuts.

Reducing Stable Matching to Ideal Cuts

To solve the maximum weight stable matching problem, the authors leverage the existing theory of rotations. In the context of stable matching, a rotation is a cyclic shift of partners that moves from one stable matching to another. These rotations possess a natural partial order, forming a DAG known as the rotation poset.

The authors construct a specialized edge-weighted DAG based on this poset. They prove a fundamental correspondence: a maximum weight ideal cut in this rotation-based DAG corresponds precisely to a maximum weight stable matching. This reduction allows their new ideal cut algorithm to solve the weighted matching problem efficiently.

Structural Insights: Sublattices and Meta-rotations

The combinatorial approach reveals significant structural properties of the solution space:

  1. The Optimal Sublattice: The set of all stable matchings ($\cal L$) is known to form a distributive lattice. The authors prove that the set of maximum weight stable matchings ($\cal M'$) is not merely a collection of points but a sublattice ($\cal L'$) of $\cal L$. This means that the "join" and "meet" (the least upper bound and greatest lower bound) of any two maximum weight stable matchings are also maximum weight stable matchings.
  2. Meta-rotations: In standard stable matching, rotations are the atomic units used to move between adjacent matchings in the lattice. To navigate the sublattice of optimal matchings, the authors introduce meta-rotations. By analyzing the residual graph of their flow algorithm and collapsing strongly connected components, they identify groups of rotations that must be triggered together to maintain optimality. These meta-rotations form their own poset, providing a high-level map of the optimal solution space.

Algorithmic Results and Extensions

The structural findings lead to several practical algorithmic outcomes:

  • Extreme Optimal Matchings: Because the optimal matchings form a sublattice, there exist unique "boy-optimal" and "girl-optimal" matchings within the set of maximum weight matchings. The authors provide efficient methods to locate these specific points.
  • Bi-objective Optimization: The framework naturally extends to hierarchical objectives. If multiple matchings achieve the maximum weight for one criteria, the algorithm can find the one among them that maximizes a second weight function.
  • Complexity: The overall complexity is dominated by the max-flow computation on a graph with $O(n^2)$ vertices, where $n$ is the number of agents, ensuring practical efficiency for large-scale matching markets.

Conclusion

By bridging the gap between stable matching theory and the combinatorial optimization of ideal cuts, this research provides both a powerful new algorithmic toolset and a deeper understanding of the geometry of stable matchings. The introduction of meta-rotations and the proof of the sublattice structure offer a robust foundation for future work in constrained and multi-objective matching problems.

Summary updated

Abstract

We study a natural generalization of stable matching to the maximum weight stable matching problem and we obtain a combinatorial polynomial time algorithm for it by reducing it to the problem of finding a maximum weight ideal cut in a DAG. We give the first polynomial time algorithm for the latter problem; this algorithm is also combinatorial. The combinatorial nature of our algorithms not only means that they are efficient but also that they enable us to obtain additional structural and algorithmic results: - We show that the set, $\cal M'$, of maximum weight stable matchings forms a sublattice $\cal L'$ of the lattice $\cal L$ of all stable matchings. - We give an efficient algorithm for finding boy-optimal and girl-optimal matchings in $\cal M'$. - We generalize the notion of rotation, a central structural notion in the context of the stable matching problem, to meta-rotation. Just as rotations help traverse the lattice of all stable matchings, macro-rotations help traverse the sublattice over $\cal M'$.
BibTeX
@misc{mai2018natural,
  author = {Tung Mai and Vijay V. Vazirani},
  title = {{A Natural Generalization of Stable Matching Solved via New Insights into Ideal Cuts}},
  year = {2018},
  eprint = {1802.06621},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1802.06621},
}
Figure