On Dynamics in Selfish Network Creation
Source: Humboldt-Universitat zu Berlin
The authors consider the dynamic behavior of several variants of the Network Creation Game, introduced by Fabrikant et al. [PODC'03]. For this, they treat these games as sequential-move games and analyze whether selfish play eventually leads to an equilibrium state of the game. They show that fast convergence is guaranteed for all versions of Swap Games, if the initial network is a tree. Furthermore, they show that this process can be sped up to an almost optimal number of moves by employing a very natural move policy. Unfortunately, these positive results are no longer true if the initial network has cycles and they show that even one non-tree edge suffices to destroy the convergence-guarantee.