Legal Assignments and fast EADAM with consent via classical theory of stable matchings

Yuri Faenza, Xuan ZhangarXiv 2018 · OpenReview

TL;DR

This paper bridges the gap between theoretical "legal assignments" and practical "EADAM" algorithms in matching markets (like school choice) by showing that legal assignments can be understood as stable assignments in a modified instance. This allows for significantly faster algorithms for both legal assignments and EADAM, especially when only some participants consent.

What Problem Does This Paper Address?

The classic Gale-Shapley algorithm for stable matching is elegant and efficient, but often sacrifices efficiency for stability. In real-world applications like school choice, this can lead to suboptimal outcomes for students. Researchers have proposed extensions like "legal assignments" and the "EADAM" algorithm to improve efficiency while maintaining fairness. However, these extensions often lack theoretical grounding and efficient algorithms, hindering their practical adoption. This paper aims to unify these concepts under the umbrella of classical stable matching theory, providing theoretical insights and developing significantly faster algorithms.

Methods

The core of the paper's contribution lies in establishing a deep connection between "legal assignments" and "stable assignments." The authors prove that the set of legal assignments for an instance (G, <, q) is precisely the set of stable assignments in a subgraph (G_L, <, q) of the original instance. This insight allows them to leverage existing algorithms for stable matching to solve problems over legal assignments.

A key algorithmic contribution is the development of "student-rotate-remove" and "school-rotate-remove" algorithms. These algorithms efficiently find student-optimal and school-optimal legal assignments by iteratively identifying and eliminating "illegal" edges or resolving "rotations" within the stable matching framework.

Furthermore, the paper adapts the "school-rotate-remove" algorithm to efficiently compute the output of the EADAM (Efficiency Adjusted Deferred Acceptance Mechanism) algorithm, even when only a subset of students consent. This adaptation is crucial for practical applications where consent might not be universal.

Datasets

Not discussed in the paper. The paper focuses on theoretical contributions and algorithmic development, using illustrative examples and computational experiments on randomly generated instances.

Key Insights and Ideas

  • Legal Assignments as Stable Assignments in Disguise: The most significant insight is that the set of legal assignments for a given problem instance is equivalent to the set of stable assignments in a specific subgraph of that instance. This connection is powerful because it allows us to apply the well-developed theory and algorithms for stable matchings to the less understood concept of legal assignments.
  • Algorithmic Efficiency Through Structural Equivalence: By showing the equivalence between legal and stable assignments in a subgraph, the paper unlocks the possibility of solving optimization problems over legal assignments with the same efficiency as their stable matching counterparts. This is a major theoretical advancement.
  • Fast EADAM with Consent: The paper demonstrates that EADAM, a mechanism designed to improve efficiency by allowing consent, can be implemented efficiently by modifying the legal assignment algorithms. This is particularly impactful because it addresses a practical bottleneck in EADAM's application.
  • The Lattice Structure of Legal Assignments: The paper highlights that legal assignments, like stable assignments, form a lattice. This structural property is fundamental to developing efficient algorithms for finding optimal legal assignments.

Key Results

  • Theoretical Equivalence: The paper proves that the set of legal assignments for an instance (G, <, q) is exactly the set of stable assignments in a derived subgraph (G_L, <, q).
  • Efficient Optimization: Optimization problems over legal assignments can be solved within the same time complexity as their stable assignment counterparts.
  • Fast Legal Assignment Algorithms: The paper presents efficient algorithms for finding student-optimal and school-optimal legal assignments.
  • O(|E|) EADAM with Consent: The authors develop an algorithm that computes the output of EADAM with consent in time complexity O(|E|), a significant improvement over previous approaches.
  • Empirical Validation: Computational experiments show that the proposed algorithms are significantly faster in practice than existing methods, especially for large instances and varying consent levels. For example, their algorithm takes approximately 3 minutes for a large instance where simplified EADAM takes 4 hours.

Limitations and Future Work

  • Generalization to Indifference: While the paper focuses on strict preferences, real-world scenarios often involve indifference. Extending the results to handle indifference would be a valuable next step.
  • Characterizing Legal Instances: The paper touches upon the question of characterizing instances that maximize the number of stable matchings. Further research into the relationship between Latin instances and legal matchings could shed light on this open problem.
  • Practical Implementation Details: While the paper provides theoretical guarantees, further work on optimizing the implementation of these algorithms for specific real-world platforms could be beneficial.
  • Strategy-Proofness: The paper acknowledges that EADAM is not strategy-proof. Investigating mechanisms that combine efficiency, fairness, and strategy-proofness remains an active area of research.

Summary updated

Abstract

Gale and Shapley's stable assignment problem has been extensively studied, applied, and extended. In the context of school choice, mechanisms often aim at finding an assignment that is more favorable to students. We investigate two extensions introduced in this framework -- legal assignments and the EADAM algorithm -- through the lens of classical theory of stable matchings. In any instance, the set ${\cal L}$ of legal assignments is known to contain all stable assignments. We prove that ${\cal L}$ is exactly the set of stable assignments in another instance. Moreover, we show that essentially all optimization problems over ${\cal L}$ can be solved within the same time bound needed for solving it over the set of stable assignments. A key tool for this latter result is an algorithm that finds the student-optimal legal assignment. We then generalize our algorithm to obtain the assignment output of EADAM with any given set of consenting students without sacrificing the running time, hence largely improving in both theory and practice over known algorithms. Lastly, we show that the set ${\cal L}$ can be much larger than the set of stable matchings, connecting legal matchings with certain concepts and open problems in the literature.
BibTeX
@misc{faenza2018legal,
  author = {Yuri Faenza and Xuan Zhang},
  title = {{Legal Assignments and fast EADAM with consent via classical theory of stable matchings}},
  year = {2018},
  eprint = {1809.08506},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1809.08506},
}
Figure