eduzhai > Applied Sciences > Computer Science >

From Matching with Diversity Constraints to Matching with Regional Quotas

  • KanKan
  • (0) Download
  • 20210424
  • Save

... pages left unread,continue reading

Document pages: 20 pages

Abstract: In the past few years, several new matching models have been proposed andstudied that take into account complex distributional constraints. Relevantlines of work include (1) school choice with diversity constraints wherestudents have (possibly overlapping) types and (2) hospital-doctor matchingwhere various regional quotas are imposed. In this paper, we present apolynomial-time reduction to transform an instance of (1) to an instance of (2)and we show how the feasibility and stability of corresponding matchings arepreserved under the reduction. Our reduction provides a formal connectionbetween two important strands of work on matching with distributionalconstraints. We then apply the reduction in two ways. Firstly, we show that itis NP-complete to check whether a feasible and stable outcome for (1) exists.Due to our reduction, these NP-completeness results carry over to setting (2).In view of this, we help unify some of the results that have been presented inthe literature. Secondly, if we have positive results for (2), then we havecorresponding results for (1). One key conclusion of our results is thatfurther developments on axiomatic and algorithmic aspects of hospital-doctormatching with regional quotas will result in corresponding results for schoolchoice with diversity constraints.

Please select stars to rate!


0 comments Sign in to leave a comment.

    Data loading, please wait...