Convergence and hardness of strategic Schelling segregation

DOI10.1007/978-3-030-35389-6_12zbMATH Open1435.91135arXiv1907.07513OpenAlexW2991414458MaRDI QIDQ776259FDOQ776259

Authors: Hagen Echzell, Tobias Friedrich, Pascal Lenzner, Louise Molitor, Marcus Pappik, Friedrich Schöne, Fabian Sommer, David Stangl 

Publication date: 30 June 2020

Abstract: The phenomenon of residential segregation was captured by Schelling's famous segregation model where two types of agents are placed on a grid and an agent is content with her location if the fraction of her neighbors which have the same type as her is at least $au$, for some $0<au<1$. Discontent agents simply swap their location with a randomly chosen other discontent agent or jump to a random empty cell. We analyze a generalized game-theoretic model of Schelling segregation which allows more than two agent types and more general underlying graphs modeling the residential area. For this we show that both aspects heavily influence the dynamic properties and the tractability of finding an optimal placement. We map the boundary of when improving response dynamics (IRD), i.e., the natural approach for finding equilibrium states, are guaranteed to converge. For this we prove several sharp threshold results where guaranteed IRD convergence suddenly turns into the strongest possible non-convergence result: a violation of weak acyclicity. In particular, we show such threshold results also for Schelling's original model, which is in contrast to the standard assumption in many empirical papers. Furthermore, we show that in case of convergence, IRD find an equilibrium in $mathcalO(m)$ steps, where $m$ is the number of edges in the underlying graph and show that this bound is met in empirical simulations starting from random initial agent placements.

Full work available at URL: https://arxiv.org/abs/1907.07513

Recommendations

• Schelling segregation with strategic agents
• Schelling games on graphs
• Schelling redux: an evolutionary dynamic model of residential segregation
• An analysis of one-dimensional Schelling segregation
• Welfare guarantees in Schelling segregation

zbMATH Keywords

potential gamesSchelling segregationcomputational hardnessconvergence of improving response dynamics

Mathematics Subject Classification ID

Mathematical geography and demography (91D20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Introduction to algorithms
• Emergence of segregation in evolving social networks
• Title not available (Why is that?)
• Potential games
• Some simplified NP-complete graph problems
• The Evolution of Conventions
• Dynamic models of segregation†
• Algorithmic approach to the satisfactory graph partitioning problem
• The satisfactory partition problem
• Unperturbed Schelling segregation in two or three dimensions
• A DYNAMIC MODEL OF RESIDENTIAL SEGREGATION
• An analysis of one-dimensional schelling segregation
• Exponential Segregation in a Two-Dimensional Schelling Model with Tolerant Individuals
• Computing the complexity for Schelling segregation models
• Schelling segregation with strategic agents
• Simulating Society
• Digital morphogenesis via Schelling segregation
• Clustering and Mixing Times for Segregation Models on ℤ²
• Convergence and hardness of strategic Schelling segregation

Cited In (12)

• Welfare Guarantees in Schelling Segregation
• Topological Influence and Locality in Swap Schelling Games.
• Stochastic Stability in Schelling’s Segregation Model with Markovian Asynchronous Update
• Modified Schelling games
• Not all strangers are the same: the impact of tolerance in Schelling games
• The parameterized complexity of welfare guarantees in Schelling segregation
• Modified Schelling games
• Convergence and hardness of strategic Schelling segregation
• Schelling games on graphs
• The impact of geometry on monochrome regions in the flip Schelling process
• Topological distance games
• Diversity-seeking jump games in networks

This page was built for publication: Convergence and hardness of strategic Schelling segregation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q776259)