zbMATH — the first resource for mathematics

On the price of anarchy for high-price links. (English) Zbl 1435.91034
Caragiannis, Ioannis (ed.) et al., Web and Internet economics. 15th international conference, WINE 2019, New York, NY, USA, December 10–12, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11920, 316-329 (2019).
Summary: We study Nash equilibria and the price of anarchy in the classic model of Network Creation Games introduced by A. Fabrikant et al. [in: Proceedings of the 22nd annual ACM symposium on principles of distributed computing, PODC ’03, Boston, MA, USA, July 13–16, 2003. New York, NY: Association for Computing Machinery (ACM). 347–351 (2003; Zbl 1322.91013)]. This is a selfish network creation model where players correspond to nodes in a network and each of them can create links to the other \(n-1\) players at a prefixed price \(\alpha>0\). The player’s goal is to minimise the sum of her cost buying edges and her cost for using the resulting network. One of the main conjectures for this model states that the price of anarchy, i.e. the relative cost of the lack of coordination, is constant for all \(\alpha\). This conjecture has been confirmed for \(\alpha=O(n^{1-\delta})\) with \(\delta\ge 1/\log n\) and for \(\alpha>4n-13\). The best known upper bound on the price of anarchy for the remaining range is \(2^{O(\sqrt{\log n})}\).
We give new insights into the structure of the Nash equilibria for \(\alpha>n\) and we enlarge the range of the parameter \(\alpha\) for which the price of anarchy is constant. Specifically, we prove that for any small \(\epsilon>0\), the price of anarchy is constant for \(\alpha>n(1+\epsilon)\) by showing that any biconnected component of any non-trivial Nash equilibrium, if it exists, has at most a constant number of nodes.
For the entire collection see [Zbl 1429.91006].

91A43 Games involving graphs
Full Text: DOI
[1] Àlvarez, C., Messegué, A.: Network creation games: structure vs anarchy. CoRR, abs/1706.09132. http://arxiv.org/abs/1706.09132 (2017)
[2] Àlvarez, C., Messegué, A.: On the constant price of anarchy conjecture. CoRR, abs/1809.08027. http://arxiv.org/abs/1809.08027 (2018) · Zbl 1435.91034
[3] Àlvarez, C., Messegué, A.: On the price of anarchy for high-price links. CoRR, abs/1909.09799. http://arxiv.org/abs/1909.09799 (2019) · Zbl 1435.91034
[4] Albers, S., Eilts, S., Even-Dar, E., Mansour, Y., Roditty, L.: On Nash equilibria for a network creation game. ACM Trans. Econ. Comput. 2(1), 2 (2014) · Zbl 1192.91036
[5] Bilò, D., Lenzner, P.: On the tree conjecture for the network creation game. STACS 2018, 14:1-14:15 (2018) · Zbl 1443.91071
[6] Demaine, E.D., Hajiaghayi, M.T., Mahini, H., Zadimoghaddam, M.: The price of anarchy in network creation games. In: PODC 2007, pp. 292-298 (2007) · Zbl 1283.68053
[7] Demaine, E.D., Hajiaghayi, M.T., Mahini, H., Zadimoghaddam, M.: The price of anarchy in network creation games. ACM Trans. Algorithms 8(2), 13 (2012) · Zbl 1295.68041
[8] Fabrikant, A., Luthra, A., Maneva, E.N., Papadimitriou, C.H., Shenker, S.: On a network creation game. In: PODC 2003, pp. 347-351 (2003) · Zbl 1322.91013
[9] Lin, H.: On the price of anarchy of a network creation game. Class final project (2003)
[10] Mihalák, M., Schlegel, J.C.: The price of anarchy in network creation games is (Mostly) constant. Theor. Comput. Syst. 53(1), 53-72 (2013) · Zbl 1293.91031
[11] Mamageishvili, A.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.