TY - JOUR A1 - Bilo, Davide A1 - Bilo, Vittorio A1 - Lenzner, Pascal A1 - Molitor, Louise T1 - Topological influence and locality in swap schelling games JF - Autonomous Agents and Multi-Agent Systems N2 - 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. KW - residential segregation KW - Schelling's segregation model KW - non-cooperative games KW - price of anarchy KW - game dynamics Y1 - 2022 U6 - https://doi.org/10.1007/s10458-022-09573-7 SN - 1387-2532 SN - 1573-7454 VL - 36 IS - 2 PB - Springer CY - Dordrecht ER - TY - GEN A1 - Bilo, Davide A1 - Friedrich, Tobias A1 - Lenzner, Pascal A1 - Melnichenko, Anna T1 - Geometric Network Creation Games T2 - SPAA '19: The 31st ACM Symposium on Parallelism in Algorithms and Architectures N2 - Network Creation Games are a well-known approach for explaining and analyzing the structure, quality and dynamics of real-world networks like the Internet and other infrastructure networks which evolved via the interaction of selfish agents without a central authority. In these games selfish agents which correspond to nodes in a network strategically buy incident edges to improve their centrality. However, past research on these games has only considered the creation of networks with unit-weight edges. In practice, e.g. when constructing a fiber-optic network, the choice of which nodes to connect and also the induced price for a link crucially depends on the distance between the involved nodes and such settings can be modeled via edge-weighted graphs. We incorporate arbitrary edge weights by generalizing the well-known model by Fabrikant et al. [PODC'03] to edge-weighted host graphs and focus on the geometric setting where the weights are induced by the distances in some metric space. In stark contrast to the state-of-the-art for the unit-weight version, where the Price of Anarchy is conjectured to be constant and where resolving this is a major open problem, we prove a tight non-constant bound on the Price of Anarchy for the metric version and a slightly weaker upper bound for the non-metric case. Moreover, we analyze the existence of equilibria, the computational hardness and the game dynamics for several natural metrics. The model we propose can be seen as the game-theoretic analogue of a variant of the classical Network Design Problem. Thus, low-cost equilibria of our game correspond to decentralized and stable approximations of the optimum network design. KW - Network creation games KW - edge-weighted networks KW - price of anarchy KW - Nash equilibrium KW - game dynamics KW - computational hardness Y1 - 2019 SN - 978-1-4503-6184-2 U6 - https://doi.org/10.1145/3323165.3323199 SP - 323 EP - 332 PB - Association for Computing Machinery CY - New York ER - TY - JOUR A1 - Bilò, Davide A1 - Lenzner, Pascal T1 - On the tree conjecture for the network creation game JF - Theory of computing systems N2 - Selfish Network Creation focuses on modeling real world networks from a game-theoretic point of view. One of the classic models by Fabrikant et al. (2003) is the network creation game, where agents correspond to nodes in a network which buy incident edges for the price of alpha per edge to minimize their total distance to all other nodes. The model is well-studied but still has intriguing open problems. The most famous conjectures state that the price of anarchy is constant for all alpha and that for alpha >= n all equilibrium networks are trees. We introduce a novel technique for analyzing stable networks for high edge-price alpha and employ it to improve on the best known bound for the latter conjecture. In particular we show that for alpha > 4n - 13 all equilibrium networks must be trees, which implies a constant price of anarchy for this range of alpha. Moreover, we also improve the constant upper bound on the price of anarchy for equilibrium trees. KW - network creation games KW - price of anarchy KW - tree conjecture KW - algorithmic KW - game theory Y1 - 2019 U6 - https://doi.org/10.1007/s00224-019-09945-9 SN - 1432-4350 SN - 1433-0490 VL - 64 IS - 3 SP - 422 EP - 443 PB - Springer CY - New York ER -