Matchings Under Diversity Constraints

Matching problems with group fairness constraints have numerous applications, from school choice to committee selection. We consider matchings under diversity constraints. Our problem involves assigning "items" to "platforms" in the presence of diversity constraints. Items belong to various "groups" depending on their attributes, and the constraints are stated in terms of lower bounds on the number of items from each group matched to each platform. In another model, instead of absolute lower bounds, "proportional fairness constraints" are considered. We give hardness results and design approximation algorithms for these problems. The technical core of our proofs is a new connection between these problems and the problem of matchings in hypergraphs. Our third problem addresses a logistical challenge involving opening platforms in the presence of diversity constraints. We give an efficient algorithm for this problem based on dynamic programming.