Matchings under Preferences: Strength of Stability and Tradeoffs

Jiehua Chen, Piotr Skowron, Manuel Sorge

TL;DR

This paper introduces "robustness" and "near stability" as quantitative measures of matching stability, going beyond the classic binary "stable/unstable" definition. They develop algorithms and analyze the computational complexity of finding matchings that balance stability with social optimality criteria like egalitarian cost and completeness, revealing surprising trade-offs.

What Problem Does This Paper Address?

The classic Stable Marriage Problem (SMP) aims to find a matching where no pair of agents would prefer to be matched with each other over their current partners. However, this definition of stability can be too rigid. Preferences might not perfectly reflect true desires, agents' preferences can change over time, or external factors might incentivize breaking a stable matching. This paper addresses the need for more nuanced stability concepts that account for these real-world complexities. They introduce two new concepts:

  • Robustness: A matching is robust if it remains stable even if agents' preferences change slightly. This is crucial for scenarios where preferences are uncertain or dynamic.
  • Near Stability: A matching is nearly stable if it can be made stable with only minor adjustments to agents' preferences. This acknowledges that agents might be willing to compromise slightly for other benefits, like improved social welfare.

The paper also explores the trade-offs between these stability notions and other desirable matching properties, such as minimizing the "egalitarian cost" (sum of ranks of matched partners) and maximizing the number of matched agents.

Methods

The authors introduce novel quantitative definitions for robustness and near stability, based on the "swap distance" between preference profiles. A swap involves reordering two adjacent agents in a preference list.

  • Robustness (d-robustness): A matching is d-robust if it remains stable for any preference profile within a swap distance of d from the original. They develop a polynomial-time algorithm for finding a d-robust matching by leveraging structural properties of "rotations" in stable matchings and a concept called "stable quadruples." This involves constructing a "rotation digraph" and analyzing its closed subsets.
  • Near Stability (d-near stability): This concept is further divided into "global" and "local" versions, differing in how preference changes are aggregated. They analyze the computational complexity of finding matchings that are d-nearly stable and also optimize for egalitarian cost or perfectness.
  • Trade-off Analysis: The paper uses computational complexity (NP-hardness, approximation hardness, parameterized complexity) to understand the inherent trade-offs between stability and social optimality criteria. They employ reductions from classic problems like Independent Set to prove hardness results.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithmic development for preference profiles, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Stability is a Spectrum: The paper convincingly argues that stability isn't a binary property but rather a spectrum, quantifiable by how much preferences can change before a matching becomes unstable.
  • Robustness vs. Near Stability: These two concepts offer complementary views: robustness guards against external changes, while near stability allows for internal adjustments for greater good.
  • Computational Trade-offs: A key finding is the stark contrast in computational difficulty: finding a robust matching is often tractable (polynomial time), while finding a nearly stable matching with good social optimality is generally NP-hard, even for small numbers of allowed preference changes.
  • Rotations as Building Blocks: The paper effectively uses the concept of "rotations" from stable matching theory as fundamental building blocks for analyzing and constructing robust matchings.
  • Ties Introduce Hardness: The introduction of ties in preferences significantly increases the computational difficulty, making the robust matching problem NP-hard.

Key Results

  • Polynomial-Time Algorithm for Robust Matching: The paper presents an O(n⁴) algorithm to find a d-robust matching if one exists. They also show that finding a d-robust perfect matching or one with minimum egalitarian cost can be done in polynomial time using linear programming.
  • NP-Hardness for Near Stability: Finding a nearly stable matching that is also socially optimal (perfect or with low egalitarian cost) is NP-hard. This hardness holds even for very small values of d (e.g., d=1 for local near stability).
  • Approximation Hardness: The paper demonstrates that even approximation algorithms for nearly stable matchings with social optimality guarantees are unlikely to exist unless P=NP.
  • Parameterized Complexity: For global near stability, algorithms exist with running times that depend exponentially on the number of allowed swaps (d), but this dependence is unavoidable unless FPT = W[1].

Limitations and Future Work

  • Preference Restrictions: The paper suggests exploring whether special preference structures can lead to tractable cases for nearly stable matchings.
  • Generalizing to Non-Bipartite Settings: The concepts of robustness and near stability were introduced for the bipartite Stable Marriage Problem. Extending these to the Stable Roommates Problem is a promising future direction.
  • Handling Ties: While the paper shows NP-hardness for robust matching with ties, further research could explore specific tractable cases or approximation algorithms.
  • Worst-Case Blocking Pairs: For scenarios where no d-robust matchings exist, the authors suggest investigating matchings that minimize the number of blocking pairs in profiles at a swap distance d.

Summary updated

Abstract

We propose two solution concepts for matchings under preferences: robustness and near stability. The former strengthens while the latter relaxes the classical definition of stability by Gale and Shapley (1962). Informally speaking, robustness requires that a matching must be stable in the classical sense, even if the agents slightly change their preferences. Near stability, however, imposes that a matching must become stable (again, in the classical sense) provided the agents are willing to adjust their preferences a bit. Both of our concepts are quantitative; together they provide means for a fine-grained analysis of the stability of matchings. Moreover, our concepts allow the exploration of tradeoffs between stability and other criteria of social optimality, such as the egalitarian cost and the number of unmatched agents. We investigate the computational complexity of finding matchings that implement certain predefined tradeoffs. We provide a polynomial-time algorithm that, given agent preferences, returns a socially optimal robust matching (if it exists), and we prove that finding a socially optimal and nearly stable matching is computationally hard.
BibTeX
@article{chen2021matchings,
  author = {Jiehua Chen and Piotr Skowron and Manuel Sorge},
  title = {{Matchings under Preferences: Strength of Stability and Tradeoffs}},
  journal = {ACM Trans. Economics and Comput.},
  year = {2021},
  url = {https://openreview.net/forum?id=PKyvh3OXTy},
}
Figure