Strategy-proof school choice mechanisms with minimum quotas and initial endowments

Naoto Hamada, Chia Ling Hsu, Ryoji Kurata, Takamasa Suzuki, Suguru Ueda, Makoto Yokoo

Research output: Contribution to journalArticlepeer-review

22 Citations (Scopus)


We consider a school choice program where minimum quotas are imposed for each school, i.e., a school must be assigned at least a certain number of students to operate. We require that the obtained matching must respect the initial endowments, i.e., each student must be assigned to a school that is at least as good as her initial endowment school. Although minimum quotas are relevant in school choice programs and strategy-proofness is important to many policymakers, few existing mechanisms simultaneously achieve both. One difficulty is that no strategy-proof mechanism exists that is both efficient and fair under the presence of minimum quotas. Furthermore, existing mechanisms require that all students consider all schools acceptable to obtain a feasible matching that respects minimum quotas. This assumption is unrealistic in a school choice program. We consider the environment where a student considers her initial endowment school acceptable and the initial endowments satisfy all the minimum quotas. We develop two strategy-proof mechanisms. One mechanism, which we call the Top Trading Cycles among Representatives with Supplementary Seats (TTCR-SS), is based on the Top Trading Cycles (TTC) mechanism and is significantly extended to handle the supplementary seats of schools while respecting minimum quotas. TTCR-SS is Pareto efficient. The other mechanism, which we call Priority List-based Deferred Acceptance with Minimum Quotas (PLDA-MQ), is based on the Deferred Acceptance (DA) mechanism. PLDA-MQ is fair, satisfies a concept called Priority List-based (PL-) stability, and obtains the student-optimal matching within all PL-stable matchings. Our simulation results show that our new mechanisms are significantly better than simple extensions of the existing mechanisms.

Original languageEnglish
Pages (from-to)47-71
Number of pages25
JournalArtificial Intelligence
Publication statusPublished - Aug 2017

All Science Journal Classification (ASJC) codes

  • Language and Linguistics
  • Linguistics and Language
  • Artificial Intelligence


Dive into the research topics of 'Strategy-proof school choice mechanisms with minimum quotas and initial endowments'. Together they form a unique fingerprint.

Cite this