Treffer: On the PoA conjecture: Trees versus biconnected components

In the classical model of network creation games introduced by Fabrikant et al. [Ona network creation game, in Proceedings of the Twenty-Second Annual Symposium on Principlesof Distributed Computing (PODC`03), 2003, pp. 347--351],nplayers correspond to the nodes of anetwork buying links of price\alpha and to the other players with the goal of being well-connected tothe resulting network. Still as an open problem, theconstantPoAconjecturestates that thePriceof Anarchy(PoA) is constant for any\alpha . When tackling this problem distinct behaviors must betaken into the account depending on whether\alpha has either large or low value. It is known that for\alpha >4n - 13 everyneis a tree and for\alpha =O(n1 - \delta ) with\delta \geq 1/lognthe diameter of networks thatare in equilibrium when restricting to deviations that consist only in buying links (buying equilibria)is at most a constant. These results imply that the PoA is constant for the disjoint union of thetwo ranges, and thus the constant PoA conjecture seems to be true for most of all the possiblevalues\alpha . In this paper we study the PoA for the remaining range of\alpha and we show the following:(i) For\alpha > n(1 +\epsilon ) the PoA is constant by proving that the size of any biconnected componentof an equilibrium graph is constant. (ii) For\alpha \leq n(1 +\epsilon ) we have that PoA = \Theta (dmax), wheredmaxis the maximum diameter of an equilibrium graph for the same range of\alpha . Therefore if theconstant PoA conjecture was false, it would suffice to construct equilibria of nonconstant diameter.Towards this direction we find nontrivialbuying equilibriaof nonconstant diameter when\alpha > n1 - \delta and\delta =O(2 - \surd \mathrm{l}\mathrm{o}\mathrm{g}n), exploring new intimate relationships betweendistance-uniform graphsandbuying equilibria. ; This work was partially supported by funds from the Spanish Ministry for Economy and Competitiveness (MINECO) and the European Union (FEDER funds) under grant GRAMM (TIN2017-86727-C2-1-R), from ...