◎橋本直幸・上田　俊・岩崎　敦（九大）・安田洋祐（政策研究大学院大）・横尾　真（九大）

This paper considers the problem of matching with regional minimum quotas. There exist many real world settings where such quotas are relevant. For example, in a hospital-resident matching problem, unconstrained matching may produce too few assignments to hospitals in a rural region. We examine how the structure of regional quotas makes the problem difficult, and show that, without restriction on the structure of regions, checking the existence of a feasible matching that satisfies all quotas is NP-complete. Assuming regions are hierarchical, we develop mechanisms for handling them.