[4L2-J-13] AI application: improvements of workplaces

[4L2-J-13-01] Student-Project-Resource Matching-Allocation Problems: Two-Sided Matching Meets Resource Allocation

〇Kentaro Yahiro¹, Tomoaki Yamaguchi¹, Anisse Ismaili², Makoto Yokoo¹ (1. Graduate School of Information Science and Electrical Engineering, Kyushu University, 2. RIKEN, Center for Advanced Intelligence Project AIP)

Keywords:Two-sided Matching Problem, Resource Allocation Problem, Nursery School Waiting List Problem

In this paper, we consider a student-project-resource matching-allocation problem, in which students and resources are assigned to projects. A project's capacity for students is endogenously determined by the resources allocated to it. Traditionally, this problem is divided into two separate problems: (1) resources are allocated to projects based on some expectations (resource allocation problem), and (2) students are matched to projects based on the capacities determined in the previous problem (many-to-one matching problem). Although both problems 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. We show that finding a nonwasteful matching is hard for class FP^NP[log] and deciding a stable matching is complete for class ¥Sigma_2^P. Then, we show that no strategyproof mechanism satisfies fairness and very weak efficiency requirements. Given this impossibility result, we develop a novel strategyproof mechanism that strikes a good balance between fairness and efficiency, which is assessed by experiments.