Welfare Guarantees in Schelling Segregation

Martin Bullinger, Warut Suksompong, Alexandros A. Voudouris

Introduction

Thomas Schelling’s seminal 1969 model demonstrated how individual preferences for similar neighbors can lead to large-scale residential segregation. While traditional research has focused on the dynamic processes of cluster formation, recent work in algorithmic game theory shifts the focus toward efficiency: how "good" are these segregated states for the population as a whole? This paper investigates the social welfare of Schelling environments, exploring the computational limits of finding optimal arrangements and the inherent trade-offs between different notions of optimality and fairness.

Social Welfare and Computational Complexity

Social welfare in this context is defined as the sum of all agents' utilities, where an individual's utility is the fraction of neighbors who share their "type" (e.g., Red or Blue). A central question is whether we can efficiently find an assignment of agents to houses that maximizes this total happiness.

The authors prove that maximizing social welfare is NP-hard, even on regular graphs where every house has the same number of neighbors and every house is occupied. This result is significant as it closes a theoretical gap; previous hardness proofs often relied on the presence of "stubborn" agents or empty nodes. By reducing known hard problems to a Schelling instance on a regular graph, the researchers demonstrate that even simple neighborhood structures do not escape computational complexity.

Despite this hardness, the paper provides a strong welfare guarantee. By analyzing the expected welfare of a completely random assignment, the authors show that a random state already captures at least half of the maximum possible welfare (approximately $n/2$ for $n$ agents). Using the method of conditional expectations—a standard derandomization technique—they derive a deterministic, polynomial-time algorithm that guarantees this 1/2-approximation of the optimum. This suggests that while the absolute best arrangement is hard to find, a "good enough" arrangement is always accessible.

Optimality Notions and the Price of Efficiency

Beyond simple welfare maximization, the paper introduces more nuanced definitions of optimality to capture different aspects of fairness and stability:

  • Utility-Vector Optimality (UVO): An assignment where the sorted vector of individual utilities cannot be lexicographically improved.
  • Group-Welfare Optimality (GWO): An assignment where the total welfare of one group cannot be increased without decreasing the welfare of the other.
  • Pareto Optimality (PO): A state where no individual's utility can be improved without making someone else worse off.
Hierarchy of optimality notions and their relationships to maximum social welfare.

The "Price of Optimality" measures the worst-case ratio between the maximum possible welfare and the welfare of the least efficient optimal state. The authors find that for UVO and GWO, this price is linear ($\Theta(n)$), suggesting that prioritizing these specific fairness or group-level notions can lead to significant losses in overall population happiness. For Pareto Optimality, a gap remains in the literature: the price is currently bounded between $n-3$ and $n\sqrt{n}$. The authors conjecture that the true value is likely $\Theta(n)$, aligning it with the other optimality notions.

Connectivity and Positive Utility

A final contribution concerns "positive utility"—the ability to ensure that no agent is completely isolated (i.e., everyone has at least one neighbor of the same type). The authors demonstrate that on any graph where every node has at least two neighbors (minimum degree $\ge 2$), an assignment with positive utility for all agents is guaranteed to exist.

Example assignments on star graphs. These topologies are used to study how central node placement affects individual and total utility.

For more restricted topologies like trees, the paper provides a polynomial-time algorithm to determine if such a "no-isolation" assignment is possible. These results highlight how the physical layout of a city—its connectivity—plays a crucial role in preventing social isolation.

Conclusion

This work provides a rigorous framework for evaluating the efficiency of Schelling-style segregation. By establishing welfare floors, proving computational hardness, and quantifying the "price" of various optimality criteria, the authors offer a comprehensive look at the limits of social engineering in segregated environments. Future research may extend these findings to models with more than two agent types or dynamic city topologies.

Summary updated

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.
BibTeX
@inproceedings{bullinger2021welfare,
  author = {Martin Bullinger and Warut Suksompong and Alexandros A. Voudouris},
  title = {{Welfare Guarantees in Schelling Segregation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i6.16661},
}
Figure