Geometric Network Creation Games
- 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 theNetwork 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.…
Verfasserangaben: | Davide BiloORCiDGND, Tobias FriedrichORCiDGND, Pascal LenznerGND, Anna MelnichenkoORCiD |
---|---|
DOI: | https://doi.org/10.1145/3323165.3323199 |
ISBN: | 978-1-4503-6184-2 |
Titel des übergeordneten Werks (Englisch): | SPAA '19: The 31st ACM Symposium on Parallelism in Algorithms and Architectures |
Verlag: | Association for Computing Machinery |
Verlagsort: | New York |
Publikationstyp: | Sonstiges |
Sprache: | Englisch |
Jahr der Erstveröffentlichung: | 2019 |
Erscheinungsjahr: | 2019 |
Datum der Freischaltung: | 26.04.2021 |
Freies Schlagwort / Tag: | Nash equilibrium; Network creation games; computational hardness; edge-weighted networks; game dynamics; price of anarchy |
Seitenanzahl: | 10 |
Erste Seite: | 323 |
Letzte Seite: | 332 |
Fördernde Institution: | COST Action European Network for Game Theory (GAMENET) [CA16228] |
Organisationseinheiten: | Digital Engineering Fakultät / Hasso-Plattner-Institut für Digital Engineering GmbH |
DDC-Klassifikation: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 000 Informatik, Informationswissenschaft, allgemeine Werke |