- search hit 1 of 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.
Author details: | Davide BilòORCiDGND, Pascal LenznerORCiDGND |
---|---|
DOI: | https://doi.org/10.1007/s00224-019-09945-9 |
ISSN: | 1432-4350 |
ISSN: | 1433-0490 |
Title of parent work (English): | Theory of computing systems |
Publisher: | Springer |
Place of publishing: | New York |
Publication type: | Article |
Language: | English |
Date of first publication: | 2019/08/16 |
Publication year: | 2019 |
Release date: | 2023/03/21 |
Tag: | algorithmic; game theory; network creation games; price of anarchy; tree conjecture |
Volume: | 64 |
Issue: | 3 |
Number of pages: | 22 |
First page: | 422 |
Last Page: | 443 |
Organizational units: | An-Institute / Hasso-Plattner-Institut für Digital Engineering gGmbH |
DDC classification: | 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 |
Publishing method: | Open Access / Green Open-Access |