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

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

Yuzhe Zhang, Kentaro Yahiro, Nathanaƫl Barrot, Makoto Yokoo

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 590-596. https://doi.org/10.24963/ijcai.2018/82

In this paper, we identify a new class of distributional constraints defined as a union of symmetric M-convex sets, which can represent a variety of real-life constraints in two-sided matching settings. Since M-convexity is not closed under union, a union of symmetric M-convex sets does not belong to this well-behaved class of constraints in general. Thus, developing a fair and strategyproof mechanism that can handle this class is challenging. We present a novel mechanism called Quota Reduction Deferred Acceptance (QRDA), which repeatedly applies the standard DA mechanism by sequentially reducing artificially introduced maximum quotas. We show that QRDA is fair and strategyproof when handling a union of symmetric M-convex sets. Furthermore, in comparison to a baseline mechanism called Artificial Cap Deferred Acceptance (ACDA), QRDA always obtains a weakly better matching for students and, experimentally, performs better in terms of nonwastefulness.
Keywords:
Agent-based and Multi-agent Systems: Cooperative Games
Agent-based and Multi-agent Systems: Algorithmic Game Theory
Agent-based and Multi-agent Systems: Economic Paradigms, Auctions and Market-Based Systems