Document Open Access Logo

Topological Influence and Locality in Swap Schelling Games

Authors Davide Bilò , Vittorio Bilò , Pascal Lenzner , Louise Molitor

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.15.pdf
  • Filesize: 0.66 MB
  • 15 pages

Document Identifiers

Author Details

Davide Bilò
  • Department of Humanities and Social Sciences, University of Sassari, Italy
Vittorio Bilò
  • Department of Mathematics and Physics "Ennio De Giorgi", University of Salento, Lecce, Italy
Pascal Lenzner
  • Hasso Plattner Institute, University of Potsdam, Germany
Louise Molitor
  • Hasso Plattner Institute, University of Potsdam, Germany

Acknowledgements

We thank an anonymous reviewer for providing an idea on how to improve the PoA for balanced 2-SSGs (Corollary 11) to min{8/3, (2n+2)/n} and possibly even further. We will incorporate this improvement in the journal version of the paper.

Cite As Get BibTex

Davide Bilò, Vittorio Bilò, Pascal Lenzner, and Louise Molitor. Topological Influence and Locality in Swap Schelling Games. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.MFCS.2020.15

Abstract

Residential segregation is a wide-spread phenomenon that can be observed in almost every major city. In these urban areas residents with different racial or socioeconomic background tend to form homogeneous clusters. Schelling’s famous agent-based model for residential segregation explains how such clusters can form even if all agents are tolerant, i.e., if they agree to live in mixed neighborhoods. For segregation to occur, all it needs is a slight bias towards agents preferring similar neighbors. Very recently, Schelling’s model has been investigated from a game-theoretic point of view with selfish agents that strategically select their residential location. In these games, agents can improve on their current location by performing a location swap with another agent who is willing to swap. 
We significantly deepen these investigations by studying the influence of the underlying topology modeling the residential area on the existence of equilibria, the Price of Anarchy and on the dynamic properties of the resulting strategic multi-agent system. Moreover, as a new conceptual contribution, we also consider the influence of locality, i.e., if the location swaps are restricted to swaps of neighboring agents. We give improved almost tight bounds on the Price of Anarchy for arbitrary underlying graphs and we present (almost) tight bounds for regular graphs, paths and cycles. Moreover, we give almost tight bounds for grids, which are commonly used in empirical studies. For grids we also show that locality has a severe impact on the game dynamics.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory
  • Theory of computation → Quality of equilibria
  • Theory of computation → Convergence and learning in games
  • Theory of computation → Network games
Keywords
  • Residential Segregation
  • Schelling’s Segregation Model
  • Non-cooperative Games
  • Price of Anarchy
  • Game Dynamics

Metrics

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

Related Versions

References

  1. Aishwarya Agarwal, Edith Elkind, Jiarui Gan, and Alexandros A. Voudouris. Swap Stability in Schelling Games on Graphs. In AAAI'20, pages 1758-1765, 2020. Google Scholar
  2. Dominic Aits, Alexander Carver, and Paolo Turrini. Group Segregation in Social Networks. In AAMAS'19, pages 1524-1532, 2019. Google Scholar
  3. Haris Aziz, Florian Brandl, Felix Brandt, Paul Harrenstein, Martin Olsen, and Dominik Peters. Fractional Hedonic Games. ACM TEAC, 7(2):6:1-6:29, 2019. Google Scholar
  4. George Barmpalias, Richard Elwes, and Andrew Lewis-Pye. Digital Morphogenesis via Schelling Segregation. In FOCS'14, pages 156-165, 2014. Google Scholar
  5. George Barmpalias, Richard Elwes, and Andrew Lewis-Pye. Unperturbed Schelling Segregation in Two or Three Dimensions. Journal of Statistical Physics, 164(6):1460-1487, 2016. Google Scholar
  6. Prateek Bhakta, Sarah Miracle, and Dana Randall. Clustering and Mixing Times for Segregation Models on 𝒵². In SODA'14, pages 327-340, 2014. Google Scholar
  7. Vittorio Bilò, Angelo Fanelli, Michele Flammini, Gianpiero Monaco, and Luca Moscardelli. Nash Stable Outcomes in Fractional Hedonic Games: Existence, Efficiency and Computation. JAIR, 62:315-371, 2018. Google Scholar
  8. Davide Bilò, Vittorio Bilò, Pascal Lenzner, and Louise Molitor. Topological Influence and Locality in Swap Schelling Games, 2020. URL: http://arxiv.org/abs/2005.02752.
  9. Anna Bogomolnaia and Matthew O. Jackson. The Stability of Hedonic Coalition Structures. GEB, 38(2):201-230, 2002. Google Scholar
  10. Christina Brandt, Nicole Immorlica, Gautam Kamath, and Robert D. Kleinberg. An Analysis of One-dimensional Schelling Segregation. In STOC'12, pages 789-804, 2012. Google Scholar
  11. Robert Bredereck, Edith Elkind, and Ayumi Igarashi. Hedonic Diversity Games. In AAMAS'19, pages 565-573, 2019. Google Scholar
  12. Raffaello Carosi, Gianpiero Monaco, and Luca Moscardelli. Local Core Stability in Simple Symmetric Fractional Hedonic Games. In AAMAS'19, pages 574-582, 2019. Google Scholar
  13. Alexander Carver and Paolo Turrini. Intolerance does not Necessarily Lead to Segregation: A Computer-aided Analysis of the Schelling Segregation Model. In AAMAS'18, pages 1889-1890, 2018. Google Scholar
  14. Ankit Chauhan, Pascal Lenzner, and Louise Molitor. Schelling Segregation with Strategic Agents. In SAGT'18, pages 137-149. Springer, 2018. Google Scholar
  15. Jacques H. Drèze and J. Greenberg. Hedonic Coalitions: Optimality and Stability. Econometrica, pages 987-1003, 1980. Google Scholar
  16. David A. Easley and Jon M. Kleinberg. Networks, Crowds, and Markets - Reasoning about a Highly Connected World. Cambridge University Proceedings, 2010. Google Scholar
  17. 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 WINE'19, pages 156-170, 2019. Google Scholar
  18. Edith Elkind, Jiarui Gan, Aishwarya Igarashi, Warut Suksompong, and Alexandros A. Voudouris. Schelling Games on Graphs. In IJCAI'19, pages 266-272, 2019. Google Scholar
  19. Hendrik Fichtenberger, Amer Krivosija, and Anja Rey. Testing Individual-based Stability Properties in Graphical Hedonic Games. In AAMAS'19, pages 882-890, 2019. Google Scholar
  20. Mark A. Fossett. SimSeg - A Computer Program to Simulate the Dynamics of Residential Segregation by Social and Ethnic Status. RESI Technical Report and Program, Texas A&M University, 1998. Google Scholar
  21. Stefan Gerhold, Lev Glebsky, Carsten Schneider, Howard Weiss, and Burkhard Zimmermann. Computing the Complexity for Schelling Segregation Models. Communications in Nonlinar Science and Numerical Simulations, (13):2236-2245, 2008. Google Scholar
  22. Ayumi Igarashi, Kazunori Ota, Yuko Sakurai, and Makoto Yokoo. Robustness Against Agent Failure in Hedonic Games. In AAMAS'19, pages 2027-2029, 2019. Google Scholar
  23. Nicole Immorlica, Robert Kleinberg, Brendan Lucier, and Morteza Zadomighaddam. Exponential Segregation in a Two-dimensional Schelling Model with Tolerant Individuals. In SODA'17, pages 984-993, 2017. Google Scholar
  24. Panagiotis Kanellopoulos, Maria Kyropoulou, and Alexandros A Voudouris. Modified schelling games. arXiv preprint arXiv:2005.12149, 2020, to appear at SAGT'20. Google Scholar
  25. Anna Maria Kerkmann and Jörg Rothe. Stability in FEN-Hedonic Games for Single-Player Deviations. In AAMAS'19, pages 891-899, 2019. Google Scholar
  26. Elias Koutsoupias and Christos Papadimitriou. Worst-case Equilibria. In STACS'99, pages 404-413, 1999. Google Scholar
  27. Gianpiero Monaco, Luca Moscardelli, and Yllka Velaj. Stable Outcome in Modified Fractional Hedonic Games. In AAMAS'18, pages 937-945, 2018. Google Scholar
  28. Gianpiero Monaco, Luca Moscardelli, and Yllka Velaj. On the Performance of Stable Outcomes in Modified Fractional Hedonic Games with Egalitarian Social Welfare. In AAMAS'19, pages 873-881, 2019. Google Scholar
  29. Dov Monderer and Lloyd S. Shapley. Potential Games. GEB, 14(1):124-143, 1996. Google Scholar
  30. Hamed Omidvar and Massimo Franceschetti. Self-organized Segregation on the Grid. Journal of Statistical Physics, 170(4):748-783, 2018. Google Scholar
  31. Thomas C. Schelling. Models of Segregation. The American Economic Review, 59(2):488-493, 1969. Google Scholar
  32. Thomas C. Schelling. Dynamic Models of Segregation. Journal of the Mathematical Society, 1(2):143-186, 1971. Google Scholar
  33. 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
  34. H. Peyton Young. Individual Strategy and Social Structure : An Evolutionary Theory of Institutions. Princeton University Press Princeton, N.J, 1998. Google Scholar
  35. Junfu Zhang. A Dynamic Model of Residential Segregation. Journal of the Mathematical Society, 28(3):147-170, 2004. Google Scholar
  36. 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 About DROPS Imprint Privacy Contact