The Assignment Problem with Diversity Constraints with an application to Ethnic Integration in Public Housing - Sorbonne Université Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

The Assignment Problem with Diversity Constraints with an application to Ethnic Integration in Public Housing

Résumé

The state of Singapore operates a national public housing program, accounting for over 70% of its residential real estate. Singapore uses its housing allocation program to promote ethnic diversity in its neighborhoods; it does so by imposing ethnic quotas: every ethnic group must not own more than a certain percentage in a housing project, thus ensuring that every neighborhood contains members from each group. However, these diversity constraints naturally result in some welfare loss. Our work studies the tradeoff between diversity and (utilitarian) social welfare from the perspective of computational economics. We model the problem as an extension of the classic assignment problem, with additional diversity constraints. While the classic assignment program is poly-time computable, we show that adding diversity constraints makes the problem computationally intractable; however, we identify a 1 2-approximation algorithm, as well as reasonable agent utility models which admit poly-time algorithms. In addition, we study the price of diversity: this is the loss in welfare due to the diversity constraints; we provide upper bounds on the price of diversity as functions of natural problem parameters. Finally, we use recent, public demographic and real-estate data from Singapore to create a simulated framework testing the welfare loss due to diversity constraints in realistic large-scale scenarios.
Fichier principal
Vignette du fichier
DiverseAlloc_comsoc.pdf (637.55 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02154938 , version 1 (13-06-2019)

Identifiants

  • HAL Id : hal-02154938 , version 1

Citer

Nawal Benabbou, Mithun Chakraborty, Xuan-Vinh Ho, Jakub Sliwinski, Yair Zick. The Assignment Problem with Diversity Constraints with an application to Ethnic Integration in Public Housing. International Workshop on Computational Social Choice (COMSOC'18), Jun 2018, Troy, NY, United States. ⟨hal-02154938⟩
84 Consultations
51 Téléchargements

Partager

Gmail Facebook X LinkedIn More