@article{BiloBiloLenzneretal.2022,
  author    = {Bilo, Davide and Bilo, Vittorio and Lenzner, Pascal and Molitor, Louise},
  title     = {Topological influence and locality in swap schelling games},
  series = {Autonomous Agents and Multi-Agent Systems},
  volume    = {36},
  journal   = {Autonomous Agents and Multi-Agent Systems},
  number    = {2},
  publisher = {Springer},
  address   = {Dordrecht},
  issn      = {1387-2532},
  doi       = {10.1007/s10458-022-09573-7},
  pages     = {60},
  year      = {2022},
  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.},
  language  = {en}
}
@article{BiloLenzner2019,
  author    = {Bil{\`o}, Davide and Lenzner, Pascal},
  title     = {On the tree conjecture for the network creation game},
  series = {Theory of computing systems},
  volume    = {64},
  journal   = {Theory of computing systems},
  number    = {3},
  publisher = {Springer},
  address   = {New York},
  issn      = {1432-4350},
  doi       = {10.1007/s00224-019-09945-9},
  pages     = {422 -- 443},
  year      = {2019},
  abstract  = {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.},
  language  = {en}
}
@misc{BiloFriedrichLenzneretal.2019,
  author    = {Bilo, Davide and Friedrich, Tobias and Lenzner, Pascal and Melnichenko, Anna},
  title     = {Geometric Network Creation Games},
  series = {SPAA '19: The 31st ACM Symposium on Parallelism in Algorithms and Architectures},
  journal   = {SPAA '19: The 31st ACM Symposium on Parallelism in Algorithms and Architectures},
  publisher = {Association for Computing Machinery},
  address   = {New York},
  isbn      = {978-1-4503-6184-2},
  doi       = {10.1145/3323165.3323199},
  pages     = {323 -- 332},
  year      = {2019},
  abstract  = {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.},
  language  = {en}
}