- Treffer 1 von 1
On the tree conjecture for the network creation game
- 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.
Verfasserangaben: | Davide BilòORCiDGND, Pascal LenznerORCiDGND |
---|---|
DOI: | https://doi.org/10.1007/s00224-019-09945-9 |
ISSN: | 1432-4350 |
ISSN: | 1433-0490 |
Titel des übergeordneten Werks (Englisch): | Theory of computing systems |
Verlag: | Springer |
Verlagsort: | New York |
Publikationstyp: | Wissenschaftlicher Artikel |
Sprache: | Englisch |
Datum der Erstveröffentlichung: | 16.08.2019 |
Erscheinungsjahr: | 2019 |
Datum der Freischaltung: | 21.03.2023 |
Freies Schlagwort / Tag: | algorithmic; game theory; network creation games; price of anarchy; tree conjecture |
Band: | 64 |
Ausgabe: | 3 |
Seitenanzahl: | 22 |
Erste Seite: | 422 |
Letzte Seite: | 443 |
Organisationseinheiten: | An-Institute / Hasso-Plattner-Institut für Digital Engineering gGmbH |
DDC-Klassifikation: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 000 Informatik, Informationswissenschaft, allgemeine Werke |
5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik | |
Peer Review: | Referiert |
Publikationsweg: | Open Access / Green Open-Access |