Go to the content (press return)

# FUTUR. Website for the scientific production of UPC researchers

## On the constant price of anarchy conjecture

Author
Alvarez, C.; Messegue, A.
Type of activity
Report
Date
2018-09-21
URL
http://arxiv.org/abs/1809.08027
Abstract
We study Nash equilibria and the price of anarchy in the classic model of Network Creation Games introduced by Fabrikant et al. In this model every agent (node) buys links at a prefixed price a>0 in order to get connected to the network formed by all the n agents. In this setting, the reformulated tree conjecture states that for a>n, every Nash equilibrium network is a tree. Moreover, Demaine et al. conjectured that the price of anarchy for this model is constant. Since it was shown that the pri...
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods