{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T01:53:02Z","timestamp":1725846782523},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,8,16]],"date-time":"2022-08-16T00:00:00Z","timestamp":1660608000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,16]],"date-time":"2022-08-16T00:00:00Z","timestamp":1660608000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004238","name":"Universit\u00e4t Potsdam","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004238","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Agent Multi-Agent Syst"],"published-print":{"date-parts":[[2022,10]]},"abstract":"Abstract<\/jats:title>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\u2019s 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\u2019s 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.<\/jats:p>","DOI":"10.1007\/s10458-022-09573-7","type":"journal-article","created":{"date-parts":[[2022,8,16]],"date-time":"2022-08-16T05:02:32Z","timestamp":1660626152000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Topological influence and locality in swap schelling games"],"prefix":"10.1007","volume":"36","author":[{"given":"Davide","family":"Bil\u00f2","sequence":"first","affiliation":[]},{"given":"Vittorio","family":"Bil\u00f2","sequence":"additional","affiliation":[]},{"given":"Pascal","family":"Lenzner","sequence":"additional","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0002-9166-9927","authenticated-orcid":false,"given":"Louise","family":"Molitor","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,8,16]]},"reference":[{"key":"9573_CR1","doi-asserted-by":"publisher","first-page":"103576","DOI":"10.1016\/j.artint.2021.103576","volume":"301","author":"A Agarwal","year":"2021","unstructured":"Agarwal, A., Elkind, E., Gan, J., Igarashi, A., Suksompong, W., & Voudouris, A. A. (2021). Schelling games on graphs. Artificial Intelligence, 301, 103576.","journal-title":"Artificial Intelligence"},{"key":"9573_CR2","unstructured":"Aits, D., Carver, A., & Turrini, P. (2019). Group segregation in social networks. In: AAMAS\u201919, pp. 1524\u20131532."},{"issue":"4","key":"9573_CR3","doi-asserted-by":"publisher","first-page":"1602","DOI":"10.1137\/070680096","volume":"38","author":"E Anshelevich","year":"2008","unstructured":"Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, E., Wexler, T., & Roughgarden, T. (2008). The price of stability for network design with fair cost allocation. SIAM Journal on Computing, 38(4), 1602\u20131923.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"9573_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3327970","volume":"7","author":"H Aziz","year":"2019","unstructured":"Aziz, H., Brandl, F., Brandt, F., Harrenstein, P., Olsen, M., & Peters, D. (2019). Fractional hedonic games. ACM Transactions on Economics and Computation, 7(2), 1\u201329.","journal-title":"ACM Transactions on Economics and Computation"},{"key":"9573_CR5","doi-asserted-by":"crossref","unstructured":"Barmpalias, G., Elwes, R., & Lewis-Pye, A. (2014). Digital morphogenesis via schelling segregation. In: FOCS\u201914, pp. 156\u2013165.","DOI":"10.1109\/FOCS.2014.25"},{"issue":"6","key":"9573_CR6","doi-asserted-by":"publisher","first-page":"1460","DOI":"10.1007\/s10955-016-1589-6","volume":"164","author":"G Barmpalias","year":"2016","unstructured":"Barmpalias, G., Elwes, R., & Lewis-Pye, A. (2016). Unperturbed schelling segregation in two or three dimensions. Journal of Statistical Physics, 164(6), 1460\u20131487.","journal-title":"Journal of Statistical Physics"},{"key":"9573_CR7","doi-asserted-by":"crossref","unstructured":"Bhakta, P., Miracle, S., & Randall, D. (2014). Clustering and mixing times for segregation models on $$\\cal{Z}^2$$. In: SODA\u201914, pp. 327\u2013340.","DOI":"10.1137\/1.9781611973402.24"},{"key":"9573_CR8","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1613\/jair.1.11211","volume":"62","author":"V Bil\u00f2","year":"2018","unstructured":"Bil\u00f2, V., Fanelli, A., Flammini, M., Monaco, G., & Moscardelli, L. (2018). Nash stable outcomes in fractional hedonic games: Existence, efficiency and computation. Journal of Artificial Intelligence Research, 62, 315\u2013371.","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"2","key":"9573_CR9","first-page":"201","volume":"38","author":"A Bogomolnaia","year":"2002","unstructured":"Bogomolnaia, A., & Jackson, M. O. (2002). The stability of hedonic coalition structures. Global Ecology and Biogeography, 38(2), 201\u2013230.","journal-title":"Global Ecology and Biogeography"},{"key":"9573_CR10","doi-asserted-by":"crossref","unstructured":"Brandt, C., Immorlica, N., Kamath, G., & Kleinberg, R. (2012). An analysis of one-dimensional schelling segregation. In: STOC\u201912, pp. 789\u2013804.","DOI":"10.1145\/2213977.2214048"},{"key":"9573_CR11","unstructured":"Bredereck, R., Elkind, E., & Igarashi, A. (2019). Hedonic diversity games. In: AAMAS\u201919, pp. 565\u2013573."},{"key":"9573_CR12","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1613\/jair.1.12771","volume":"71","author":"M Bullinger","year":"2021","unstructured":"Bullinger, M., Suksompong, W., & Voudouris, A. A. (2021). Welfare guarantees in schelling segregation. Journal of Artificial Intelligence Research, 71, 143\u2013174.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9573_CR13","unstructured":"Carosi, R., Monaco, G., & Moscardelli, L. (2019). Local core stability in simple symmetric fractional hedonic games. In: AAMAS\u201919, pp. 574\u2013582."},{"key":"9573_CR14","unstructured":"Carver, A., & Turrini, P. (2018). Intolerance does not necessarily lead to segregation: A computer-aided analysis of the schelling segregation model. In: AAMAS\u201918, pp. 1889\u20131890."},{"key":"9573_CR15","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1613\/jair.3075","volume":"39","author":"G Chalkiadakis","year":"2010","unstructured":"Chalkiadakis, G., Elkind, E., Markakis, E., Polukarov, M., & Jennings, N. (2010). Cooperative games with overlapping coalitions. Journal of Artificial Intelligence Research, 39, 179\u2013216.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9573_CR16","unstructured":"Chan, H., Irfan, M. T., & Than, C. V. (2020). Schelling models with localized social influence: A game-theoretic framework. In: AAMAS\u201920, pp. 240\u2013248."},{"key":"9573_CR17","doi-asserted-by":"crossref","unstructured":"Chauhan, A., Lenzner, P., & Molitor, L. (2018). Schelling segregation with strategic agents. In: SAGT\u201918. Springer, pp. 137\u2013149.","DOI":"10.1007\/978-3-319-99660-8_13"},{"key":"9573_CR18","doi-asserted-by":"publisher","first-page":"987","DOI":"10.2307\/1912943","volume":"48","author":"JH Dr\u00e8ze","year":"1980","unstructured":"Dr\u00e8ze, J. H., & Greenberg, J. (1980). Hedonic coalitions: Optimality and stability. Econometrica: Journal of the Econometric Society, 48, 987\u20131003.","journal-title":"Econometrica: Journal of the Econometric Society"},{"key":"9573_CR19","doi-asserted-by":"crossref","unstructured":"Easley, D. A., & Kleinberg, J. M. (2010). Networks, crowds, and markets: Reasoning about a highly connected world. Cambridge University Press.","DOI":"10.1017\/CBO9780511761942"},{"key":"9573_CR20","doi-asserted-by":"crossref","unstructured":"Echzell, H., Friedrich, T., Lenzner, P., Molitor, L., Pappik, M., Sch\u00f6ne, F., Sommer, F., & Stangl, D. (2019). Convergence and hardness of strategic schelling segregation. In: WINE\u201919, pp. 156\u2013170.","DOI":"10.1007\/978-3-030-35389-6_12"},{"key":"9573_CR21","unstructured":"Fichtenberger, H., Krivosija, A., & Rey, A. (2019). Testing individual-based stability properties in graphical hedonic games. In: AAMAS\u201919, pp. 882\u2013890."},{"key":"9573_CR22","unstructured":"Fossett, M. A. (1998). Simseg\u2013a computer program to simulate the dynamics of residential segregation by social and ethnic status. RESI Technical Report and Program, Texas A &M University."},{"key":"9573_CR23","doi-asserted-by":"publisher","first-page":"2236","DOI":"10.1016\/j.cnsns.2007.04.023","volume":"13","author":"S Gerhold","year":"2008","unstructured":"Gerhold, S., Glebsky, L., Schneider, C., Weiss, H., & Zimmermann, B. (2008). Computing the complexity for schelling segregation models. Communications in Nonlinear Science and Numerical Simulation, 13, 2236\u20132245.","journal-title":"Communications in Nonlinear Science and Numerical Simulation"},{"key":"9573_CR24","doi-asserted-by":"crossref","unstructured":"Igarashi, A., Ota, K., Sakurai, Y., & Yokoo, M. (2019). Robustness against agent failure in hedonic games. In: AAMAS\u201919, pp. 2027\u20132029.","DOI":"10.24963\/ijcai.2019\/52"},{"key":"9573_CR25","doi-asserted-by":"crossref","unstructured":"Immorlica, N., Kleinberg, R., Lu-cier, B., & Zadomighaddam, M. (2017). Exponential segregation in a two-dimensional schelling model with tolerant individuals. In: SODA\u201917, pp. 984\u2013993.","DOI":"10.1137\/1.9781611974782.62"},{"key":"9573_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2021.05.032","volume":"880","author":"P Kanellopoulos","year":"2021","unstructured":"Kanellopoulos, P., Kyropoulou, M., & Voudouris, A. A. (2021). Modified schelling games. Theoretical Computer Science, 880, 1\u201319.","journal-title":"Theoretical Computer Science"},{"key":"9573_CR27","unstructured":"Kerkmann, A. M., & Rothe, J. (2019). Stability in fen-hedonic games for single-player deviations. In: AAMAS\u201919, pp. 891\u2013899."},{"key":"9573_CR28","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1613\/jair.1.11531","volume":"67","author":"AM Kerkmann","year":"2020","unstructured":"Kerkmann, A. M., Lang, J., Rey, A., Rothe, J., Schadrack, H., & Schend, L. (2020). Hedonic games with ordinal preferences and thresholds. Journal of Artificial Intelligence Research, 67, 705\u2013756.","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"2","key":"9573_CR29","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.cosrev.2009.04.003","volume":"3","author":"E Koutsoupias","year":"2009","unstructured":"Koutsoupias, E., & Papadimitriou, C. H. (2009). Worst-case equilibria. Computer Science Review, 3(2), 65\u201369.","journal-title":"Computer Science Review"},{"key":"9573_CR30","doi-asserted-by":"crossref","unstructured":"Monaco, G., Moscardelli, L., & Velaj, Y. (2019). On the performance of stable outcomes in modified fractional hedonic games with egalitarian social welfare. In: AAMAS\u201919, pp. 873\u2013881.","DOI":"10.1007\/s10458-019-09431-z"},{"issue":"1","key":"9573_CR31","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1007\/s10458-019-09431-z","volume":"34","author":"G Monaco","year":"2020","unstructured":"Monaco, G., Moscardelli, L., & Velaj, Y. (2020). Stable outcomes in modified fractional hedonic games. Autonomous Agents and Multi-Agent Systems, 34(1), 4.","journal-title":"Autonomous Agents and Multi-Agent Systems"},{"issue":"1","key":"9573_CR32","first-page":"124","volume":"14","author":"D Monderer","year":"1996","unstructured":"Monderer, D., & Shapley, L. S. (1996). Potential games. Global Ecology and Biogeography, 14(1), 124\u2013143.","journal-title":"Global Ecology and Biogeography"},{"issue":"4","key":"9573_CR33","doi-asserted-by":"publisher","first-page":"748","DOI":"10.1007\/s10955-017-1942-4","volume":"170","author":"H Omidvar","year":"2018","unstructured":"Omidvar, H., & Franceschetti, M. (2018). Self-organized segregation on the grid. Journal of Statistical Physics, 170(4), 748\u2013783.","journal-title":"Journal of Statistical Physics"},{"key":"9573_CR34","doi-asserted-by":"crossref","unstructured":"Omidvar, H., & Franceschetti, M. (2018). Shape of diffusion and size of monochromatic region of a two-dimensional spin system. In: STOC\u201918, pp. 100\u2013113.","DOI":"10.1145\/3188745.3188836"},{"issue":"2","key":"9573_CR35","first-page":"488","volume":"59","author":"TC Schelling","year":"1969","unstructured":"Schelling, T. C. (1969). Models of segregation. The American Economic Review, 59(2), 488\u2013493.","journal-title":"The American Economic Review"},{"issue":"2","key":"9573_CR36","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1080\/0022250X.1971.9989794","volume":"1","author":"TC Schelling","year":"1971","unstructured":"Schelling, T. C. (1971). Dynamic models of segregation. Journal of Mathematical Sociology, 1(2), 143\u2013186.","journal-title":"Journal of Mathematical Sociology"},{"issue":"51","key":"9573_CR37","doi-asserted-by":"publisher","first-page":"19261","DOI":"10.1073\/pnas.0609371103","volume":"103","author":"D Vinkovi\u0107","year":"2006","unstructured":"Vinkovi\u0107, D., & Kirman, A. (2006). A physical analogue of the schelling model. Proceedings of the National Academy of Sciences, 103(51), 19261\u201319265.","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"9573_CR38","doi-asserted-by":"crossref","unstructured":"Young, H. P. (1998). Individual strategy and social structure: An evolutionary theory of institutions. Princeton University Press.","DOI":"10.1515\/9780691214252"},{"issue":"3","key":"9573_CR39","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1080\/00222500490480202","volume":"28","author":"J Zhang","year":"2004","unstructured":"Zhang, J. (2004). A dynamic model of residential segregation. Journal of Mathematical Sociology, 28(3), 147\u2013170.","journal-title":"Journal of Mathematical Sociology"},{"issue":"4","key":"9573_CR40","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1016\/j.jebo.2003.03.005","volume":"54","author":"J Zhang","year":"2004","unstructured":"Zhang, J. (2004). Residential segregation in an all-integrationist world. Journal of Economic Behavior & Organization, 54(4), 533\u2013550.","journal-title":"Journal of Economic Behavior & Organization"},{"key":"9573_CR41","doi-asserted-by":"publisher","first-page":"847","DOI":"10.1613\/jair.4237","volume":"50","author":"Y Zick","year":"2014","unstructured":"Zick, Y., Markakis, E., & Elkind, E. (2014). Arbitration and stability in cooperative games with overlapping coalitions. Journal of Artificial Intelligence Research, 50, 847\u2013884.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9573_CR42","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.artint.2018.11.006","volume":"271","author":"Y Zick","year":"2019","unstructured":"Zick, Y., Chalkiadakis, G., Elkind, E., & Markakis, E. (2019). Cooperative games with overlapping coalitions: Charting the tractability frontier. Artificial Intelligence, 271, 74\u201397.","journal-title":"Artificial Intelligence"}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-022-09573-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10458-022-09573-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-022-09573-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T12:56:10Z","timestamp":1667048170000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10458-022-09573-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,16]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["9573"],"URL":"https:\/\/doi.org\/10.1007\/s10458-022-09573-7","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"value":"1387-2532","type":"print"},{"value":"1573-7454","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,16]]},"assertion":[{"value":"28 June 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 August 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"47"}}