Equitable Stable Matchings in Quadratic Time

Nikolaos Tziavelis, Ioannis Giannakopoulos, Katerina Doka, Nectarios Koziris, Panagiotis KarrasNeurIPS 2019

Introduction

Finding a "fair" stable matching in a two-sided market—such as assigning students to schools or doctors to hospitals—is a notoriously difficult problem. The standard Gale-Shapley "Deferred Acceptance" (DA) algorithm is celebrated for its speed, solving the problem in $O(n^2)$ time. However, it heavily favors one side of the market. Finding the most equitable stable matching is an NP-hard problem. This paper introduces Deferred Local Search (DLS) and related algorithms, the first approaches to achieve high-equity stable matchings in quadratic time ($O(n^2)$), effectively bridging the gap between computational efficiency and social fairness.

The Challenge of Equity

In the classic Stable Marriage Problem, the goal is to match two groups (e.g., men and women, or students and colleges) based on their ranked preferences such that no two agents would rather be with each other than their current partners.

While the Gale-Shapley DA algorithm efficiently guarantees stability, it is strictly "proposer-optimal." The side making the offers receives their best possible stable matches, while the receiving side gets their worst. In real-world scenarios like labor markets or school admissions, this inherent bias is highly undesirable. The ideal outcome is an equitable matching where the "unhappiness" (the rank of the assigned partner) is balanced between both sides.

Unfortunately, minimizing equity measures—such as the "Sex Equality" cost or the "Balance" cost—is NP-hard. Previous attempts to find fairer matchings either suffered from prohibitive runtimes ($O(n^4)$ or worse) or provided poor approximations.

Proposed Methods

The authors propose a multi-stage approach to find the "sweet spot" in the lattice of all possible stable matchings:

  1. Monotonic Deferred Acceptance (MDA): A framework ensuring the matching process always moves forward toward a stable state without looping. It achieves this by tracking "frontier indices," which represent the furthest an agent has looked down their preference list.
  2. Strongly Deferred Acceptance (SDA): A novel proposal mechanism. Unlike standard DA, where a recipient accepts any better offer, SDA uses a stricter criterion: an agent accepts a proposal only if the proposer is better than their next potential target. This prevents the formation of "non-idle" couples that complicate algorithm termination.
  3. POWERBALANCE: This algorithm leverages SDA to allow both sides to propose. It tracks which side is currently "better off" and lets the other side propose to balance the scales. If it doesn't converge quickly, it uses a "COMPROMISE" procedure to force a stable, balanced termination in $O(n^2)$ time.
  4. Deferred Local Search (DLS): To further refine the result, the authors apply low-cost local search steps. Instead of moving between matchings by breaking pairs (which is computationally expensive), they use "rotations"—fine-grained mathematical structures that allow them to traverse the space of stable matchings much more efficiently.

Key Insights

  • The "Middle" is Better: Standard local search algorithms usually start at one extreme (e.g., the proposer-optimal matching) and try to crawl toward the middle. This paper's core insight is to use POWERBALANCE to jump directly into the "middle" of the stable matching lattice, followed by a very limited local search to polish the result.
  • SDA as a Termination Guarantee: The biggest hurdle in two-sided proposal algorithms is ensuring they actually stop. By introducing the SDA acceptance criterion, the authors mathematically guarantee a stable matching in quadratic time, a massive improvement over the $O(n^4)$ complexity of previous "compensation chain" methods.

Experimental Evaluation and Results

The authors evaluated their algorithms using both synthetic data (Uniform, Discrete, Gaussian, and Asymmetric distributions) and real-world data from LibimSeTi, a Czech online dating service with over 17 million ratings.

Speed and Scalability

DLS and its variants (like HybridMultiSearch) maintain a runtime that scales quadratically ($O(n^2)$). This matches the efficiency of the original Gale-Shapley algorithm while being orders of magnitude faster than previous equity-focused algorithms.

Runtime scaling of various stable matching algorithms.

Equity and Fairness

In experiments, the proposed methods consistently outperformed state-of-the-art heuristics (like BiLS) in terms of Sex Equality and Balance costs. On the real-world dating dataset, the POWERBALANCE mechanism successfully narrowed the gap between the two sides' total preference scores significantly before the final local search even began.

Balance and Sex Equality ratios compared to Deferred Acceptance.

Limitations and Future Work

  • Parameter Tuning: The limit parameter in POWERBALANCE (which determines when to force a compromise) currently needs to be tuned based on the dataset size ($n \log^2 n$). While the authors provide a heuristic, a more automated or adaptive approach would be beneficial.
  • Strategic Manipulation: The paper focuses on the algorithmic efficiency of finding equitable matchings but does not deeply explore "incentive compatibility." In fairer systems, agents might have more incentive to lie about their preferences to manipulate the outcome—a common issue in matching theory that remains an open avenue for future research.

Summary updated

BibTeX
@inproceedings{tziavelis2019equitable,
  author = {Nikolaos Tziavelis and Ioannis Giannakopoulos and Katerina Doka and Nectarios Koziris and Panagiotis Karras},
  title = {{Equitable Stable Matchings in Quadratic Time}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
}
Figure