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
- 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
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- 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
(17)- Schelling segregation with strategic agents
- Schelling games on graphs
- The impact of geometry on monochrome regions in the flip Schelling process
- Altruism and fairness in Schelling's segregation model
- An extension of Young's segregation game
- Welfare guarantees in Schelling segregation
- Topological Influence and Locality in Swap Schelling Games.
- Modified Schelling games
- Modified Schelling games
- Topological distance games
- Stochastic Stability in Schelling’s Segregation Model with Markovian Asynchronous Update
- Not all strangers are the same: the impact of tolerance in Schelling games
- Single-Peaked Jump Schelling Games
- Diversity-seeking jump games in networks
- The parameterized complexity of welfare guarantees in Schelling segregation
- Network creation with homophilic agents
- Convergence and hardness of strategic Schelling segregation
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)
