On the tree conjecture for the network creation game (Q1987511)

The paper focuses on modeling real world networks from a game-theoretic point of view. In the network creation game agents correspond to nodes in a network and buy incident edges for the price of \(\alpha\) per edge to minimize their total distance to all other nodes. The price of anarchy PoA is the ratio of the overall network quality of the worst possible outcome of the uncoordinated network creation process and the network quality of the centrally designed optimal network. It was conjectured that the price of anarchy is constant for all \(\alpha\) and that for \(\alpha\ge n\) all equilibrium networks are trees. Authors introduce a new technique for analyzing stable non-tree networks for high edge-price \(\alpha\) and use it to improve on the current best lower bound for \(\alpha\) for which all stable networks must be trees. They prove that for \(\alpha > 4n-13\) any stable network must be a tree, a significant improvement over the known bound of \(\alpha > 65n\) by \textit{A. Mamageishvili} et al. [Lect. Notes Comput. Sci. 8305, 118--129 (2013; Zbl 1342.05169)] and the recently claimed bound of \(\alpha > 17n\) by \textit{C. Álvarez} and \textit{A. Messegué} [``Network creation games: structure vs anarchy'', Preprint, \url{arXiv:1706.09132}]. Since it is known that the PoA for stable tree networks is constant, this new bound directly implies a constant PoA for \(\alpha > 4n-13\). Their new technique exploits properties of cycles in stable networks by focusing on critical pairs, strong critical pairs and min cycles. The main new contribution is revelation of a rich combinatorial structure within any non-tree Nash equilibrium (NE) network for \(\alpha > 2n-6\). Authors show that in this case any agent in any min cycle with a certain minimum length owns exactly one edge of the respective min cycle. As a result the biconnected component of any non-tree NE network cannot be a cycle and thus must contain two nodes with are situated in a particular critical pair configuration. The existence of this specific critical pair leads finally to a contradiction with \(\alpha > 4n-13\).