TY - GEN
T1 - Strategyproof and fair matching mechanism for union of symmetric m-convex constraints
AU - Zhang, Yuzhe
AU - Yahiro, Kentaro
AU - Barrot, Nathanaël
AU - Yokoo, Makoto
N1 - Funding Information:
This work was partially supported by JSPS KAKENHI Grant Number 17H00761.
Publisher Copyright:
© 2018 International Joint Conferences on Artificial Intelligence. All right reserved.
PY - 2018
Y1 - 2018
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85055706286&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85055706286&partnerID=8YFLogxK
U2 - 10.24963/ijcai.2018/82
DO - 10.24963/ijcai.2018/82
M3 - Conference contribution
AN - SCOPUS:85055706286
T3 - IJCAI International Joint Conference on Artificial Intelligence
SP - 590
EP - 596
BT - Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018
A2 - Lang, Jerome
PB - International Joint Conferences on Artificial Intelligence
T2 - 27th International Joint Conference on Artificial Intelligence, IJCAI 2018
Y2 - 13 July 2018 through 19 July 2018
ER -