TY - GEN
T1 - Student-project-resource matching-aiiocation problems
T2 - 18th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2019
AU - Ismaili, Anisse
AU - Yahiro, Kentaro
AU - Yamaguchi, Tomoaki
AU - Yokoo, Makoto
N1 - Funding Information:
This work was partially supported by JSPS KAKENHI Grant Number JP17H00761 and JST Strategic International Collaborative Research Program, SICORP.
Publisher Copyright:
© 2019 International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.
PY - 2019
Y1 - 2019
N2 - We consider a student-project-resource matching-allocation problem, in which students (resp. resources) are matched (resp. allocated) to projects. A project's capacity for students is endogenously determined by the resources allocated to it. Traditionally, (1) resources are allocated to projects based on some expectations, and then (2) students are matched with projects based on the capacities determined by (1). Although resource allocation and two-sided matching are well-understood, unless the expectations used in the first problem are correct, we obtain a suboptimal outcome. Thus, it is desirable to solve this problem as a whole without dividing it. In this paper, we show that finding a nonwasteful matching is FPNP [log]-hard, and that deciding whether a stable matching (i.e. nonwasteful and fair) exists is NPNP-complete. We also show that no strategyproof mechanism can satisfy fairness and very weak efficiency requirements. Then, we develop a new strategyproof mechanism, called Sample and Vote Deferred Acceptance (SVDA), that strikes a good balance between fairness and efficiency.
AB - We consider a student-project-resource matching-allocation problem, in which students (resp. resources) are matched (resp. allocated) to projects. A project's capacity for students is endogenously determined by the resources allocated to it. Traditionally, (1) resources are allocated to projects based on some expectations, and then (2) students are matched with projects based on the capacities determined by (1). Although resource allocation and two-sided matching are well-understood, unless the expectations used in the first problem are correct, we obtain a suboptimal outcome. Thus, it is desirable to solve this problem as a whole without dividing it. In this paper, we show that finding a nonwasteful matching is FPNP [log]-hard, and that deciding whether a stable matching (i.e. nonwasteful and fair) exists is NPNP-complete. We also show that no strategyproof mechanism can satisfy fairness and very weak efficiency requirements. Then, we develop a new strategyproof mechanism, called Sample and Vote Deferred Acceptance (SVDA), that strikes a good balance between fairness and efficiency.
UR - http://www.scopus.com/inward/record.url?scp=85077045196&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85077045196&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85077045196
T3 - Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
SP - 2033
EP - 2035
BT - 18th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2019
PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Y2 - 13 May 2019 through 17 May 2019
ER -