Controlled School Choice with Soft Bounds and Overlapping Types


  • Ryoji Kurata Kyushu University
  • Masahiro Goto Kyushu University
  • Atsushi Iwasaki University of Electro-Communications
  • Makoto Yokoo Kyushu University



Matching theory, School choice, Affirmative action, Strategy-proof, Stability


School choice programs are implemented to give students/parents an opportunity to choose the public school the students attend. Controlled school choice programs need to provide choices for students/parents while maintaining distributional constraints on the balance on the composition of students, typically in terms of socioeconomic status. Previous works show that setting soft-bounds, which flexibly change the priorities of students based on their types, is more appropriate than setting hard-bounds, which strictly limit the number of accepted students for each type. We consider a case where soft-bounds are imposed and one student can belong to multiple types, e.g., ``financially-distressed'' and ``minority'' types. We first show that when we apply a model that is a straightforward extension of an existing model for disjoint types, there is a chance that no stable matching exists. Thus, we propose an alternative model and an alternative stability definition, where a school has reserved seats for each type. We show that a stable matching is guaranteed to exist in this model, and develop a mechanism called Deferred Acceptance for Overlapping Types (DA-OT). The DA-OT mechanism is strategy-proof and obtains the student-optimal matching within all stable matchings. Computer simulation results illustrate that the DA-OT outperforms an artificial cap mechanism, where the number of seats for each type is fixed.




How to Cite

Kurata, R., Goto, M., Iwasaki, A., & Yokoo, M. (2015). Controlled School Choice with Soft Bounds and Overlapping Types. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1).



AAAI Technical Track: Game Theory and Economic Paradigms