Schelling Games with Continuous Types

Davide Bilò, Vittorio Bilò, Michelle Döring, Pascal Lenzner, Louise Molitor, Jonas SchmidtIJCAI 2023 · DOI

TL;DR

This paper introduces a new class of agent-based models for residential segregation, moving beyond discrete ethnic groups to model segregation based on continuous attributes like income or political leaning. They analyze the existence and computation of equilibria in these "Schelling Games with Continuous Types," offering insights into how different preference structures lead to varying segregation patterns.

What Problem Does This Paper Address?

Residential segregation, where people of similar backgrounds cluster together, is a well-documented phenomenon with significant societal impacts. Traditional models, like Schelling's original work, often simplify this by assuming agents belong to a few discrete types (e.g., ethnic groups). However, real-world segregation can be driven by more nuanced, continuous attributes such as household income, age, or political ideology. This paper addresses the limitation of existing models by proposing and analyzing Schelling games where agents have continuous types, allowing for a richer and more realistic representation of agent preferences and their impact on segregation patterns.

Methods

The authors introduce "Schelling Games with Continuous Types," where agents are placed on a graph (representing a city) and their "type" is a real number between 0 and 1. Agents aim to minimize their "cost," which is determined by their neighbors' types. They explore three main cost models:

  • Average Type-Distance (ADG): An agent's cost is the average type-difference to their neighbors.
  • Maximum Type-Distance (MDG): An agent's cost is the maximum type-difference to any neighbor.
  • Cutoff Games (CG): An agent's cost is the fraction of neighbors whose type-difference exceeds a certain threshold (λ).

These models are analyzed under two scenarios for isolated agents: "unhappy-in-isolation" (UIS) and "happy-in-isolation" (HIS). The paper investigates the existence and computational complexity of equilibria (Swap Equilibria - SE, and Jump Equilibria - JE), and analyzes the Price of Anarchy (PoA) and Price of Stability (PoS). They employ game-theoretic tools, including ordinal potential functions, to prove equilibrium existence and analyze convergence properties.

Datasets

Not discussed in the paper. The paper uses simulated environments based on graph structures (e.g., toroidal grids, paths) and randomly generated agent types and initial configurations for simulations.

Key Insights and Ideas

  • Continuous types unlock richer models: Moving from discrete to continuous types allows for modeling more realistic agent preferences, such as comparing oneself to neighbors based on income or political spectrum, rather than just belonging to the same or a different group.
  • Different cost functions lead to distinct segregation patterns: The MDG model tends to produce smoother, more integrated equilibria, while ADG and CG models can result in "hard borders" and more pronounced segregation. This highlights how the specific way agents evaluate their neighbors significantly shapes the resulting spatial patterns.
  • Happy-in-isolation matters: The "happy-in-isolation" assumption (agents are content if they are alone) can significantly impact equilibrium existence and computability, often leading to more positive results compared to the "unhappy-in-isolation" variant.
  • Swap games are more stable than jump games: Swap games (where agents can only trade places) generally guarantee equilibrium existence more readily than jump games (where agents can move to empty spots), especially for the MDG.
  • Computational complexity is a key concern: While equilibria often exist, finding them or the social optimum can be computationally challenging (NP-hard in some cases). However, for specific models and graph structures (like paths or regular graphs), efficient algorithms for finding equilibria are presented.

Key Results

  • Equilibrium Existence:
    • Swap-MDG (S-MDG) always has equilibria that can be efficiently computed on any graph.
  • Jump-HIS-MDG (J-HIS-MDG) equilibria can be efficiently computed on graphs with specific substructures (like K2,e) or on paths.
  • Equilibria are not guaranteed for all variants (e.g., J-UIS-ADG, J-UIS-CG) on general graphs, but can exist on specific graph classes like A-regular graphs.
  • Price of Anarchy (PoA) and Price of Stability (PoS):
    • PoA can be unbounded for many variants, indicating that equilibria can be significantly worse than the social optimum.
  • PoS is generally low (e.g., 1 or 2 for games on paths), suggesting that the "best" equilibrium is often close to the social optimum.
  • Simulation Results:
    • S-MDG produced the most segregated equilibria, followed by S-ADG.
  • Jump games generally resulted in less segregated equilibria compared to their swap counterparts.
  • The CG model produced more integrated equilibria than MDG and ADG.

Limitations and Future Work

  • Limitations:
    • The paper focuses on specific cost functions and graph structures. Generalizing these results to arbitrary functions or more complex network topologies remains an open area.
  • While some computational results are provided, finding equilibria or social optima can still be NP-hard for certain game variants.
  • The "happy-in-isolation" assumption, while simplifying analysis, might not always reflect real-world behavior.
  • Future Work:
    • Exploring a wider range of agent preference functions and cost metrics.
  • Investigating the relationship between agent behavior and the degree of segregation more deeply.
  • Developing more efficient algorithms for computing equilibria in complex scenarios.
  • Analyzing the impact of different graph structures and network properties on segregation patterns.
  • Exploring the possibility of computing social optima efficiently for specific game variants.

Summary updated

BibTeX
@inproceedings{bilo2023schelling,
  author = {Davide Bilò and Vittorio Bilò and Michelle Döring and Pascal Lenzner and Louise Molitor and Jonas Schmidt},
  title = {{Schelling Games with Continuous Types}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/280},
}
Figure