Bullinger, Martin and Suksompong, Warut and Voudouris, Alexandros A (2021) Welfare Guarantees in Schelling Segregation. Journal of Artificial Intelligence Research, 71. pp. 143-174. DOI https://doi.org/10.1613/jair.1.12771
Bullinger, Martin and Suksompong, Warut and Voudouris, Alexandros A (2021) Welfare Guarantees in Schelling Segregation. Journal of Artificial Intelligence Research, 71. pp. 143-174. DOI https://doi.org/10.1613/jair.1.12771
Bullinger, Martin and Suksompong, Warut and Voudouris, Alexandros A (2021) Welfare Guarantees in Schelling Segregation. Journal of Artificial Intelligence Research, 71. pp. 143-174. DOI https://doi.org/10.1613/jair.1.12771
Abstract
Schelling’s model is an influential model that reveals how individual perceptions and incentives can lead to residential segregation. Inspired by a recent stream of work, we study welfare guarantees and complexity in this model with respect to several welfare measures. First, we show that while maximizing the social welfare is NP-hard, computing an assignment of agents to the nodes of any topology graph with approximately half of the maximum welfare can be done in polynomial time. We then consider Pareto optimality, introduce two new optimality notions based on it, and establish mostly tight bounds on the worst-case welfare loss for assignments satisfying these notions as well as the complexity of computing such assignments. In addition, we show that for tree topologies, it is possible to decide whether there exists an assignment that gives every agent a positive utility in polynomial time; moreover, when every node in the topology has degree at least 2, such an assignment always exists and can be found efficiently.
Item Type: | Article |
---|---|
Additional Information: | Appears in the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021 |
Uncontrolled Keywords: | cs.GT |
Divisions: | Faculty of Science and Health Faculty of Science and Health > Computer Science and Electronic Engineering, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 29 Jun 2021 14:41 |
Last Modified: | 16 May 2024 20:38 |
URI: | http://repository.essex.ac.uk/id/eprint/30526 |
Available files
Filename: 12771-Article (PDF)-27077-1-10-20210529.pdf