Kanellopoulos, Panagiotis and Kyropoulou, Maria and Voudouris, Alexandros A (2021) Modified Schelling games. Theoretical Computer Science, 880. pp. 1-19. DOI https://doi.org/10.1016/j.tcs.2021.05.032
Kanellopoulos, Panagiotis and Kyropoulou, Maria and Voudouris, Alexandros A (2021) Modified Schelling games. Theoretical Computer Science, 880. pp. 1-19. DOI https://doi.org/10.1016/j.tcs.2021.05.032
Kanellopoulos, Panagiotis and Kyropoulou, Maria and Voudouris, Alexandros A (2021) Modified Schelling games. Theoretical Computer Science, 880. pp. 1-19. DOI https://doi.org/10.1016/j.tcs.2021.05.032
Abstract
We introduce the class of modified Schelling games in which there are different types of agents who occupy the nodes of a location graph; agents of the same type are friends, and agents of different types are enemies. Every agent is strategic and jumps to empty nodes of the graph aiming to maximize her utility, defined as the ratio of her friends in her neighborhood over the neighborhood size including herself. This is in contrast to the related literature on Schelling games which typically assumes that an agent is excluded from her neighborhood whilst computing its size. Our model enables the utility function to capture likely cases where agents would rather be around a lot of friends instead of just a few, an aspect that was partially ignored in previous work. We provide a thorough analysis of the (in)efficiency of equilibria that arise in such modified Schelling games, by bounding the price of anarchy and price of stability for both general graphs and interesting special cases. Most of our results are tight and exploit the structure of equilibria as well as sophisticated constructions.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | Schelling games; Equilibria; Price of anarchy; Price of stability |
Divisions: | Faculty of Science and Health Faculty of Science and Health > Computer Science and Electronic Engineering, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 08 Jun 2021 15:58 |
Last Modified: | 07 Aug 2024 18:23 |
URI: | http://repository.essex.ac.uk/id/eprint/30550 |
Available files
Filename: modified.tcs.revision.pdf
Licence: Creative Commons: Attribution-Noncommercial-No Derivative Works 3.0