From Matching with Diversity Constraints to Matching with Regional Quotas

Haris Aziz, Serge Gaspers, Zhaohong Sun, Toby Walsh

Introduction

In matching theory, researchers have long grappled with "distributional constraints"—rules that dictate how individuals should be allocated across institutions to meet specific policy goals. Two prominent but historically separate models have emerged: school choice with diversity constraints and hospital-doctor matching with regional quotas. While the former focuses on ensuring diverse student bodies through overlapping "types" (e.g., gender, socio-economic status), the latter focuses on geographic distribution to ensure rural areas are adequately staffed.

This paper establishes a formal mathematical bridge between these two domains. By providing a polynomial-time reduction, the authors demonstrate that these problems are computationally equivalent. This unification allows for the direct translation of complexity results and algorithmic solutions between the two fields, simplifying the landscape of matching theory.

The Problem: Bridging Two Worlds

Historically, school choice and hospital matching were viewed as distinct. Influential literature often argued that the models were fundamentally different because the hospital model lacked student "types" and the school model lacked "regions."

  1. School Choice: Schools set minimum and maximum quotas for student types. A student can belong to multiple, overlapping categories (e.g., a student might be both a minority and from a low-income household).
  2. Hospital-Doctor Matching: Governments set quotas on groups of hospitals (regions) to prevent over-concentration in urban centers.

Methods: The Polynomial-Time Reduction

The core contribution of this work is a polynomial-time reduction that transforms an instance of school choice with diversity constraints into an instance of hospital-doctor matching with regional quotas.

The conceptual bridge showing how reduction, algorithms, and NP-completeness results are shared between the two models.

The "secret sauce" of this reduction lies in its handling of overlapping types. To map these to a regional model, the authors:

  • Expand the type space so every unique combination of types becomes a single "new type."
  • Map each school to a specific "region."
  • Create "virtual hospitals" within those regions that correspond to these specific student types.
  • Set regional quotas that mirror the original diversity constraints.
Technical mapping of maximum and minimum quotas and related hospitals used in the reduction process.

Additionally, the paper introduces a method to convert regional minimum quotas into maximum quotas by using a "null hospital" to absorb excess capacity, further simplifying the mathematical representation.

Key Results and Complexity

Because the reduction preserves both feasibility (the existence of a valid matching) and stability (fairness and lack of waste), the authors were able to prove several critical complexity results:

  • Reduction Efficiency: The reduction runs in $O(|C| \cdot |S|^2)$ time, where $C$ is the number of schools and $S$ is the number of students.
  • NP-Completeness of Feasibility: It is NP-complete to determine if a feasible matching exists for school choice with diversity constraints, even in highly restricted cases (e.g., one school, students belonging to at most three types).
  • NP-Completeness of Stability: Checking for the existence of a stable matching is NP-complete, even without minimum quotas and with short preference lists.
  • Algorithmic Portability: Positive results, such as the "Fairness by Master List" concept, can now be ported from hospital-doctor settings to school choice settings.

Discussion and Future Work

The primary challenge identified is that "strong" stability may not exist, and even when it does, finding it is computationally difficult. The authors suggest that future research should pivot toward weaker stability concepts that are easier to compute while remaining sufficiently fair for real-world applications. Furthermore, the reduction framework could be extended to more complex models, such as matching with "slot-specific priorities," where different seats within the same institution have different ranking criteria.

Summary updated

BibTeX
@inproceedings{aziz2019from,
  author = {Haris Aziz and Serge Gaspers and Zhaohong Sun and Toby Walsh},
  title = {{From Matching with Diversity Constraints to Matching with Regional Quotas}},
  booktitle = {AAMAS},
  year = {2019},
}
Figure