[2H4-GS-13] AI application: Data analysis and search

[2H4-GS-13-04] Scheduling for School Choice Problem with Partial Information

〇Ryoji Wada¹, Kentaro Yahiro¹, Taiki Todo^1,2, Makoto Yokoo^1,2 (1. Kyushu University, 2. RIKEN, Center for Advanced Intelligence Project AIP)

Keywords:Matching theory, School choice, Partial preference

In a traditional two-sided matching problem, each agent is assumed to have a complete preference. As markets grow large, however, each agent initially has only partial information of their preference and needs to refine it by costly actions like interviews. In addition, for a practical school choice, a school can conduct multiple interviews to students in a day while a student usually cannot make time to do a lot of interviews in such a short term. Given these backgrounds, we have to appropriately schedule the interviews between students and schools to obtain the student-optimal matching and minimize the interviewing days. In this paper, we develop a static scheduling mechanism called Interview Scheduling Gale Shapley (ISGS), which extends the well-known Gale-Shapley mechanism. We show that ISGS returns the student-optimal matching and no sound and diligent scheduling mechanism exists that requires fewer days than ISGS.