×
Kanellopoulos, Panagiotis; Kyropoulou, Maria; Voudouris, Alexandros A.

Not all strangers are the same: the impact of tolerance in Schelling games. (English) Zbl 07729841

Theor. Comput. Sci. 971, Article ID 114065, 18 p. (2023).
Summary: Schelling’s famous model of segregation assumes agents of different types, who would like to be located in neighborhoods having at least a certain fraction of agents of the same type. We consider natural generalizations that allow for the possibility of agents being tolerant towards other agents, even if they are not of the same type. In particular, we consider an ordering of the types, and make the realistic assumption that the agents are in principle more tolerant towards agents of types that are closer to their own according to the ordering. Based on this, we study the strategic games induced when the agents aim to maximize their utility for a variety of tolerance levels. We provide a collection of results about the existence of equilibria, and their quality in terms of social welfare.

Cited in 2 Documents

MSC:

68Qxx Theory of computing

Keywords:

Schelling’s segregation model; Nash equilibria; price of anarchy
Cite Review PDF
Full Text: DOI arXiv
OA License

References:

[1] Agarwal, Aishwarya; Elkind, Edith; Gan, Jiarui; Voudouris, Alexandros A., Swap stability in Schelling games on graphs, (Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI) (2020)) · Zbl 1481.91037
[2] Agarwal, Aishwarya; Elkind, Edith; Gan, Jiarui; Igarashi, Ayumi; Suksompong, Warut; Voudouris, Alexandros A., Schelling games on graphs, Artif. Intell., 301, Article 103576 pp. (2021) · Zbl 1481.91037
[3] Anshelevich, Elliot; Dasgupta, Anirban; Kleinberg, Jon M.; Tardos, Éva; Wexler, Tom; Roughgarden, Tim, The price of stability for network design with fair cost allocation, SIAM J. Comput., 38, 4, 1602-1623 (2008) · Zbl 1173.91321
[4] Aziz, Haris; Brandl, Florian; Brandt, Felix; Harrenstein, Paul; Olsen, Martin; Peters, Dominik, Fractional hedonic games, ACM Trans. Econ. Comput., 7, 2, 6:1-6:29 (2019)
[5] Barmpalias, George; Elwes, Richard; Lewis-Pye, Andrew, Digital morphogenesis via Schelling segregation, (Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS) (2014)), 156-165 · Zbl 1391.82032
[6] Bayer, Patrick; McMillan, Robert; Rueben, Kim, The causes and consequences of residential segregation: An equilibrium analysis of neighborhood sorting (2001)
[7] Bhakta, Prateek; Miracle, Sarah; Randall, Dana, Clustering and mixing times for segregation models on \(\mathbb{Z}^2\), (Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2014)), 327-340 · Zbl 1426.91187
[8] Bilò, Davide; Bilò, Vittorio; Lenzner, Pascal; Molitor, Louise, Tolerance is necessary for stability: single-peaked swap Schelling games, (Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI) (2022)), 81-87
[9] Bilò, Davide; Bilò, Vittorio; Lenzner, Pascal; Molitor, Louise, Topological influence and locality in swap Schelling games, Auton. Agents Multi-Agent Syst., 36, 2, 47 (2022) · Zbl 07559386
[10] Bläsius, Thomas; Friedrich, Tobias; Krejca, Martin S.; Molitor, Louise, The impact of geometry on monochrome regions in the flip Schelling process, (Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC) (2021)), 29:1-29:17 · Zbl 1500.91098
[11] Brandt, Christina; Immorlica, Nicole; Kamath, Gautam; Kleinberg, Robert, An analysis of one-dimensional Schelling segregation, (Proceedings of the 44th Symposium on Theory of Computing (STOC) (2012)), 789-804 · Zbl 1286.05154
[12] Bullinger, Martin; Suksompong, Warut; Voudouris, Alexandros A., Welfare guarantees in Schelling segregation, J. Artif. Intell. Res., 71, 143-174 (2021) · Zbl 1521.91102
[13] Chan, Hau; Irfan, Mohammad T.; Than, Cuong Viet, Schelling models with localized social influence: a game-theoretic framework, (Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS) (2020)), 240-248
[14] Chauhan, Ankit; Lenzner, Pascal; Molitor, Louise, Schelling segregation with strategic agents, (Proceedings of the 11th International Symposium on Algorithmic Game Theory (SAGT) (2018)), 137-149 · Zbl 1415.91053
[15] Clark, William; Fossett, Mark, Understanding the social context of the Schelling segregation model, Proc. Natl. Acad. Sci., 105, 11, 4109-4114 (2008)
[16] Deligkas, Argyrios; Eiben, Eduard; Goldsmith, Tiger-Lily, The parameterized complexity of welfare guarantees in Schelling segregation (2022), CoRR
[17] Echzell, Hagen; Friedrich, Tobias; Lenzner, Pascal; Molitor, Louise; Pappik, Marcus; Schöne, Friedrich; Sommer, Fabian; Stangl, David, Convergence and hardness of strategic Schelling segregation, (Proceedings of the 15th International Conference on Web and Internet Economics (WINE) (2019)), 156-170 · Zbl 1435.91135
[18] Elkind, Edith; Gan, Jiarui; Igarashi, Ayumi; Suksompong, Warut; Voudouris, Alexandros A., Schelling games on graphs, (Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI) (2019)), 266-272 · Zbl 1481.91037
[19] Friedrich, Tobias; Lenzner, Pascal; Molitor, Louise; Seifert, Lars, Single-peaked jump Schelling games (2023), CoRR
[20] Immorlica, Nicole; Kleinberg, Robert; Lucier, Brendan; Zadimoghaddam, Morteza, Exponential segregation in a two-dimensional Schelling model with tolerant individuals, (Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2017)), 984-993 · Zbl 1417.91400
[21] Kanellopoulos, Panagiotis; Kyropoulou, Maria; Voudouris, Alexandros A., Modified Schelling games, Theor. Comput. Sci., 880, 1-19 (2021) · Zbl 1512.91021
[22] Koutsoupias, Elias; Papadimitriou, Christos H., Worst-case equilibria, (Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS) (1999)), 404-413 · Zbl 1099.91501
[23] Kreisel, Luca; Boehmer, Niclas; Froese, Vincent; Niedermeier, Rolf, Equilibria in Schelling games: computational hardness and robustness, (Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS) (2022)), 761-769
[24] Pancs, Romans; Vriend, Nicolaas J., Schelling’s spatial proximity model of segregation revisited, J. Public Econ., 91, 1-2, 1-24 (2007)
[25] Schelling, Thomas C., Models of segregation, Am. Econ. Rev., 59, 2, 488-493 (1969)
[26] Schelling, Thomas C., Dynamic models of segregation, J. Math. Sociol., 1, 2, 143-186 (1971) · Zbl 1355.91061
[27] Tiebout, Charles M., A pure theory of local expenditures, J. Polit. Econ., 64, 5, 416-424 (1956)
[28] Vinković, Dejan; Kirman, Alan, A physical analogue of the Schelling model, Proc. Natl. Acad. Sci., 103, 51, 19261-19265 (2006)
[29] Zhang, Junfu, Residential segregation in an all-integrationist world, J. Econ. Behav. Organ., 54, 4, 533-550 (2004)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.