Tolerance is Necessary for Stability: Single-Peaked Swap Schelling Games

Davide Bilò, Vittorio Bilò, Pascal Lenzner, Louise MolitorIJCAI 2022 · DOI

TL;DR

This paper introduces a new game-theoretic model for residential segregation that incorporates "single-peaked" utility functions, reflecting real-world preferences for mixed neighborhoods. They demonstrate that this "tolerance" is crucial for the existence of stable equilibria, particularly on certain types of graphs, and provide bounds on the quality of these equilibria.

What Problem Does This Paper Address?

Residential segregation, the physical separation of different groups in urban areas, has significant negative consequences. While traditional models often assume agents prefer to be surrounded by their own type (monotone utility functions), sociological data suggests people often prefer mixed neighborhoods, even to the point of being in the minority. This paper addresses this discrepancy by developing a game-theoretic model that uses "single-peaked" utility functions, where agents have a preferred level of same-type neighbors (not necessarily 100%) and their utility decreases as they move away from this ideal. The core problem is to understand how these more realistic, non-monotone preferences affect the stability and quality of residential arrangements, specifically in the context of agents strategically swapping locations to improve their situation.

Methods

The authors introduce "Single-Peaked Swap Schelling Games" played on a graph representing a residential area. Agents of two types (e.g., blue and red) strategically choose locations to maximize their utility, which is determined by a single-peaked function of the fraction of same-type neighbors. Agents can improve their utility by swapping locations with other agents. The paper focuses on analyzing:

  • Equilibrium Existence: Whether stable states (where no profitable swaps can occur) exist.
  • Finite Improvement Property (FIP): Whether any sequence of profitable swaps eventually leads to an equilibrium. This is related to the existence of an ordinal potential function.
  • Price of Anarchy (PoA): The ratio of the worst equilibrium's social welfare to the optimal social welfare.
  • Price of Stability (PoS): The ratio of the best equilibrium's social welfare to the optimal social welfare.

The "degree of integration" (number of non-segregated agents) is used as the social welfare measure. They analyze these properties on various graph classes (general, bipartite, regular, almost regular) and for different peak positions (Λ) of the utility function.

Datasets

Not discussed in the paper. The paper uses theoretical models and graph structures for analysis, not empirical datasets.

Key Insights and Ideas

  • Tolerance is Key for Stability: The paper's central finding is that agents' tolerance (preferring mixed neighborhoods, i.e., single-peaked utility functions with a peak Λ < 1) is crucial for the existence of stable residential arrangements, especially on certain graph structures. This contrasts with models that might lead to segregation even with tolerant agents if their preferences are not precisely modeled.
  • Single-Peaked Preferences Matter: Moving beyond simple monotone preferences significantly changes the dynamics. The paper shows that for certain graph types and peak positions (Λ < 1/2), equilibria are guaranteed to exist and are reachable through simple improvement steps.
  • Graph Structure is Critical: The existence of equilibria and the quality of outcomes (PoA, PoS) are highly dependent on the underlying graph topology. For instance, equilibria are more likely to exist on almost regular graphs when agents are tolerant.
  • Non-Existence of Equilibria: Interestingly, the paper demonstrates that for some configurations (e.g., peak position Λ > 1/2 on certain graphs), stable equilibria might not exist, highlighting the complexity of strategic interaction even with "tolerant" agents.
  • Bounds on Inefficiency: The paper provides tight bounds on the Price of Anarchy and Price of Stability, quantifying how much worse the outcomes can be in equilibrium compared to the socially optimal arrangement. These bounds are often constant or depend on simple graph parameters, offering valuable insights into the efficiency of decentralized decision-making.

Key Results

  • Equilibrium Existence: For tolerant agents (Λ < 1/2), swap equilibria are guaranteed to exist on almost regular graphs and are reachable via improving swaps. For Λ = 1/2, existence is guaranteed if the graph's independence number is sufficiently large. However, for Λ > 1/2, games on 2-regular graphs (rings) can admit no SE.
  • Price of Anarchy (PoA): Bounds are derived for various graph classes. For instance, on bipartite graphs, the PoA can be as high as 2. On d-regular graphs with Λ < 1/δ, the PoA is bounded by (δ+1)/2.
  • Price of Stability (PoS): For bipartite graphs with Λ = 1/2, the PoS is exactly 2. For almost regular graphs with small degrees (Δ(G) ≤ 3) and Λ < 1/2, the PoS is 1, indicating that the best equilibrium is socially optimal. For balanced games on d-regular graphs with Λ ≤ 1/2, the PoS is also 1.

Limitations and Future Work

  • Graph Topology: While results are provided for various graph classes, the question of equilibrium existence on arbitrary graphs for Λ = 1/2 remains open, though the paper shows no ordinal potential function exists in such cases.
  • Utility Function Variations: The paper focuses on single-peaked utilities. Future work could explore other non-monotone utility functions or how ties in utility are broken.
  • Social Welfare Measure: The primary social welfare measure used is the "degree of integration." The paper suggests investigating other measures, like the standard utilitarian social welfare (sum of utilities), which might yield different results.
  • Computational Complexity: While some results imply efficient computability (e.g., for bipartite graphs), a deeper analysis of the computational complexity of finding equilibria or optimal solutions could be explored.
  • Real-World Data: While the single-peaked functions are motivated by sociological polls, further empirical validation of the model's predictions against real-world segregation patterns would be valuable.

Summary updated

BibTeX
@inproceedings{bilo2022tolerance,
  author = {Davide Bilò and Vittorio Bilò and Pascal Lenzner and Louise Molitor},
  title = {{Tolerance is Necessary for Stability: Single-Peaked Swap Schelling Games}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/12},
}
Figure