Strategyproof and Fair Matching Mechanism for Union of Symmetric M-convex Constraints

Yuzhe Zhang, Kentaro Yahiro, Nathanaël Barrot, Makoto YokooIJCAI 2018 · DOI

TL;DR

This paper introduces a new class of complex constraints for two-sided matching problems, called "union of symmetric M-convex sets," which can model a wider range of real-world scenarios. They propose a novel mechanism, QRDA, that is both strategyproof (agents can't benefit from lying) and fair, and experimentally shown to be better than existing methods in terms of student welfare and efficiency.

What Problem Does This Paper Address?

In many real-world matching scenarios, like assigning students to schools or residents to hospitals, we need to go beyond simple capacity limits. We often have "distributional constraints" that dictate how many agents can be assigned to certain groups of entities. For example, a school might need a minimum number of students from a specific region, or a hospital might have a maximum number of residents it can accept from a particular specialty.

The challenge is that these constraints can make it impossible to find a "stable" matching, a concept that ensures no agent would prefer to unilaterally switch their assignment. When constraints are complex, finding a mechanism that is both "strategyproof" (agents have no incentive to lie about their preferences) and "fair" (no agent is unjustly disadvantaged) becomes very difficult. Existing mechanisms that handle complex constraints often sacrifice too much efficiency or strategyproofness. This paper aims to find a mechanism that works for a broader class of constraints while maintaining desirable properties.

Methods

The core of this paper is the introduction of a new class of constraints: the "union of symmetric M-convex sets." This class is a generalization of previously studied "M-convex sets," which are well-behaved mathematically. The authors then propose a new mechanism called Quota Reduction Deferred Acceptance (QRDA).

QRDA works by repeatedly applying the standard Deferred Acceptance (DA) algorithm (the classic Gale-Shapley algorithm). The key innovation is how it handles the complex constraints: it sequentially reduces artificial maximum quotas for schools in a specific round-robin order. This iterative reduction allows the mechanism to explore a wider range of feasible matchings while still adhering to the original, more complex constraints. The authors prove that QRDA is strategyproof and fair for this new class of constraints.

Datasets

Not discussed in the paper. The paper focuses on theoretical contributions and uses simulated data for experimental evaluation.

Key Insights and Ideas

  • A New Class of Constraints: The "union of symmetric M-convex sets" is a significant theoretical contribution. It bridges the gap between simpler, well-understood constraints and the more complex, real-world scenarios that current mechanisms struggle with. This opens the door for designing better matching systems in diverse applications.
  • QRDA's Iterative Approach: The QRDA mechanism's clever use of sequential quota reduction is a novel way to navigate complex feasibility sets. By systematically "testing" different quota configurations, it can find a desirable outcome without needing to know the exact optimal quotas beforehand.
  • Theoretical Guarantees: Proving that QRDA is strategyproof and fair for this new, broader class of constraints is a strong theoretical result. It provides a solid foundation for its practical application.
  • Welfare Improvement: The theoretical result that QRDA always weakly dominates the baseline ACDA mechanism in terms of student welfare is important. It suggests that QRDA is not just a theoretical curiosity but offers tangible benefits to the agents being matched.

Key Results

  • Theoretical: QRDA is proven to be strategyproof and fair for matching problems with constraints defined as a union of symmetric M-convex sets.
  • Theoretical Comparison: QRDA always produces a matching that is weakly preferred by students compared to the baseline Artificial Cap Deferred Acceptance (ACDA) mechanism.
  • Experimental: In simulations with "difference constraints" (a type of union of symmetric M-convex set), QRDA was shown to be experimentally better than ACDA in terms of student welfare. Furthermore, QRDA was found to be less wasteful (i.e., more efficient) than ACDA in these experiments. For instance, in some scenarios, up to 60% more students strictly preferred QRDA's outcome.

Limitations and Future Work

  • Limitations: The paper acknowledges that while QRDA is theoretically better in terms of student welfare, it cannot guarantee nonwastefulness compared to ACDA. Experimental results suggest QRDA is often less wasteful, but not always. The strategyproofness proof for QRDA relies on a specific round-robin order for quota reduction, and the paper notes that results hold for any "balanced sequence" of schools, but the exact implications of different sequences are not fully explored.
  • Future Work: The authors suggest exploring whether there exist even broader classes of constraints for which fair and strategyproof mechanisms can be developed. They also hint at further clarifying the conditions under which QRDA outperforms ACDA in terms of nonwastefulness.

Summary updated

BibTeX
@inproceedings{zhang2018strategyproof,
  author = {Yuzhe Zhang and Kentaro Yahiro and Nathanaël Barrot and Makoto Yokoo},
  title = {{Strategyproof and Fair Matching Mechanism for Union of Symmetric M-convex Constraints}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/82},
}
Figure