Convergence and hardness of strategic Schelling segregation
From MaRDI portal
(Redirected from Publication:776259)
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 , for some . 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 steps, where 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- A DYNAMIC MODEL OF RESIDENTIAL SEGREGATION
- Algorithmic approach to the satisfactory graph partitioning problem
- An analysis of one-dimensional Schelling segregation
- Clustering and mixing times for segregation models on \(\mathbb{Z}^2\)
- Computing the complexity for Schelling segregation models
- Convergence and hardness of strategic Schelling segregation
- Digital morphogenesis via schelling segregation
- Dynamic models of segregation†
- Emergence of segregation in evolving social networks
- Exponential segregation in a two-dimensional Schelling model with tolerant individuals
- Introduction to algorithms
- Potential games
- Schelling segregation with strategic agents
- Simulating Society
- Some simplified NP-complete graph problems
- The Evolution of Conventions
- The satisfactory partition problem
- Unperturbed Schelling segregation in two or three dimensions
Cited in
(15)- Stochastic Stability in Schelling’s Segregation Model with Markovian Asynchronous Update
- An extension of Young's segregation game
- Welfare guarantees in Schelling segregation
- Convergence and hardness of strategic Schelling segregation
- Diversity-seeking jump games in networks
- The impact of geometry on monochrome regions in the flip Schelling process
- Single-Peaked Jump Schelling Games
- Schelling games on graphs
- Modified Schelling games
- Modified Schelling games
- The parameterized complexity of welfare guarantees in Schelling segregation
- Schelling segregation with strategic agents
- Not all strangers are the same: the impact of tolerance in Schelling games
- Topological Influence and Locality in Swap Schelling Games.
- Topological distance games
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)
