Document Open Access Logo

Not All Strangers Are the Same: The Impact of Tolerance in Schelling Games

Authors Panagiotis Kanellopoulos , Maria Kyropoulou , Alexandros A. Voudouris

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.60.pdf
  • Filesize: 0.78 MB
  • 14 pages

Document Identifiers

Author Details

Panagiotis Kanellopoulos
  • School of Computer Science and Electronic Engineering, University of Essex, UK
Maria Kyropoulou
  • School of Computer Science and Electronic Engineering, University of Essex, UK
Alexandros A. Voudouris
  • School of Computer Science and Electronic Engineering, University of Essex, UK

Cite AsGet BibTex

Panagiotis Kanellopoulos, Maria Kyropoulou, and Alexandros A. Voudouris. Not All Strangers Are the Same: The Impact of Tolerance in Schelling Games. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 60:1-60:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.MFCS.2022.60

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory and mechanism design
Keywords
  • Schelling games
  • Equilibria
  • Price of anarchy
  • Price of stability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Aishwarya Agarwal, Edith Elkind, Jiarui Gan, and Alexandros A. Voudouris. Swap stability in Schelling games on graphs. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), 2020. Google Scholar
  2. Elliot Anshelevich, Anirban Dasgupta, Jon M. Kleinberg, Éva Tardos, Tom Wexler, and Tim Roughgarden. The price of stability for network design with fair cost allocation. SIAM Journal on Computing, 38(4):1602-1623, 2008. Google Scholar
  3. Haris Aziz, Florian Brandl, Felix Brandt, Paul Harrenstein, Martin Olsen, and Dominik Peters. Fractional hedonic games. ACM Transactions on Economics and Computation, 7(2):6:1-6:29, 2019. Google Scholar
  4. George Barmpalias, Richard Elwes, and Andrew Lewis-Pye. Digital morphogenesis via Schelling segregation. In Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 156-165, 2014. Google Scholar
  5. Patrick Bayer, Robert McMillan, and Kim Rueben. The causes and consequences of residential segregation: An equilibrium analysis of neighborhood sorting, 2001. Google Scholar
  6. Prateek Bhakta, Sarah Miracle, and Dana Randall. Clustering and mixing times for segregation models on ℤ². In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 327-340, 2014. Google Scholar
  7. Davide Bilò, Vittorio Bilò, Pascal Lenzner, and Louise Molitor. Topological influence and locality in swap Schelling games. In Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 15:1-15:15, 2020. Google Scholar
  8. Thomas Bläsius, Tobias Friedrich, Martin S. Krejca, and Louise Molitor. The impact of geometry on monochrome regions in the flip schelling process. In Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC), pages 29:1-29:17, 2021. Google Scholar
  9. Christina Brandt, Nicole Immorlica, Gautam Kamath, and Robert Kleinberg. An analysis of one-dimensional Schelling segregation. In Proceedings of the 44th Symposium on Theory of Computing (STOC), pages 789-804, 2012. Google Scholar
  10. Martin Bullinger, Warut Suksompong, and Alexandros A. Voudouris. Welfare guarantees in Schelling segregation. Journal of Artificial Intelligence Research, 71:143-174, 2021. Google Scholar
  11. Hau Chan, Mohammad T. Irfan, and Cuong Viet Than. Schelling models with localized social influence: A game-theoretic framework. In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 240-248, 2020. Google Scholar
  12. Ankit Chauhan, Pascal Lenzner, and Louise Molitor. Schelling segregation with strategic agents. In Proceedings of the 11th International Symposium on Algorithmic Game Theory (SAGT), pages 137-149, 2018. Google Scholar
  13. William Clark and Mark Fossett. Understanding the social context of the Schelling segregation model. Proceedings of the National Academy of Sciences, 105(11):4109-4114, 2008. Google Scholar
  14. Argyrios Deligkas, Eduard Eiben, and Tiger-Lily Goldsmith. The parameterized complexity of welfare guarantees in schelling segregation. CoRR, abs/2201.06904, 2022. URL: http://arxiv.org/abs/2201.06904.
  15. Hagen Echzell, Tobias Friedrich, Pascal Lenzner, Louise Molitor, Marcus Pappik, Friedrich Schöne, Fabian Sommer, and David Stangl. Convergence and hardness of strategic Schelling segregation. In Proceedings of the 15th International Conference on Web and Internet Economics (WINE), pages 156-170, 2019. Google Scholar
  16. Edith Elkind, Jiarui Gan, Ayumi Igarashi, Warut Suksompong, and Alexandros A. Voudouris. Schelling games on graphs. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pages 266-272, 2019. Google Scholar
  17. Nicole Immorlica, Robert Kleinberg, Brendan Lucier, and Morteza Zadimoghaddam. Exponential segregation in a two-dimensional Schelling model with tolerant individuals. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 984-993, 2017. Google Scholar
  18. Panagiotis Kanellopoulos, Maria Kyropoulou, and Alexandros A. Voudouris. Modified Schelling games. Theoretical Computer Science, 880:1-19, 2021. Google Scholar
  19. Elias Koutsoupias and Christos H. Papadimitriou. Worst-case equilibria. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pages 404-413, 1999. Google Scholar
  20. Romans Pancs and Nicolaas J. Vriend. Schelling’s spatial proximity model of segregation revisited. Journal of Public Economics, 91(1-2):1-24, 2007. Google Scholar
  21. Thomas C. Schelling. Models of segregation. American Economic Review, 59(2):488-493, 1969. Google Scholar
  22. Thomas C. Schelling. Dynamic models of segregation. Journal of Mathematical Sociology, 1(2):143-186, 1971. Google Scholar
  23. Charles M. Tiebout. A pure theory of local expenditures. Journal of Political Economy, 64(5):416-424, 1956. Google Scholar
  24. Dejan Vinković and Alan Kirman. A physical analogue of the schelling model. Proceedings of the National Academy of Sciences, 103(51):19261-19265, 2006. Google Scholar
  25. Junfu Zhang. Residential segregation in an all-integrationist world. Journal of Economic Behavior and Organization, 54(4):533-550, 2004. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact