Title: The Price of Diversity in Assignment Problems,
Abstract: We introduce and analyze an extension to the matching problem on a weighted
bipartite graph: Assignment with Type Constraints. The two parts of the graph
are partitioned into subsets called types and blocks; we seek a matching with
the largest sum of weights under the constraint that there is a pre-specified
cap on the number of vertices matched in every type-block pair. Our primary
motivation stems from the public housing program of Singapore, accounting for
over 70% of its residential real estate. To promote ethnic diversity within its
housing projects, Singapore imposes ethnicity quotas: each new housing
development comprises blocks of flats and each ethnicity-based group in the
population must not own more than a certain percentage of flats in a block.
Other domains using similar hard capacity constraints include matching
prospective students to schools or medical residents to hospitals. Limiting
agents' choices for ensuring diversity in this manner naturally entails some
welfare loss. One of our goals is to study the trade-off between diversity and
social welfare in such settings. We first show that, while the classic
assignment program is polynomial-time computable, adding diversity constraints
makes it computationally intractable; however, we identify a
$\tfrac{1}{2}$-approximation algorithm, as well as reasonable assumptions on
the weights that permit poly-time algorithms. Next, we provide two upper bounds
on the price of diversity -- a measure of the loss in welfare incurred by
imposing diversity constraints -- as functions of natural problem parameters.
We conclude the paper with simulations based on publicly available data from
two diversity-constrained allocation problems -- Singapore Public Housing and
Chicago School Choice -- which shed light on how the constrained maximization
as well as lottery-based variants perform in practice.