  We consider the dynamic behavior of several variants of the Network Creation
Game, introduced by Fabrikant et al. [PODC'03]. Equilibrium networks in these
models have desirable properties like low social cost and small diameter, which
makes them attractive for the decentralized creation of overlay-networks.
Unfortunately, due to the non-constructiveness of the Nash equilibrium, no
distributed algorithm for finding such networks is known. We treat these games
as sequential-move games and analyze whether (uncoordinated) selfish play
eventually converges to an equilibrium state. Thus, we shed light on one of the
most natural algorithms for this problem: distributed local search, where in
each step some agent performs a myopic selfish improving move.
  We show that fast convergence is guaranteed for all versions of Swap Games,
introduced by Alon et al. [SPAA'10], if the initial network is a tree, and show
that this process can be sped up to an almost optimal number of moves. For
non-tree networks we show the surprising result that even one non-tree edge
suffices to destroy the convergence guarantee and no move policy can enforce
convergence. This answers an open problem from Ehsani et al. [SPAA'11] in the
negative. We extend our negative results to the well-studied original version
and prove that there is no convergence guarantee -- even if all agents play
optimally. Furthermore, we show the quite surprising result that employing
cost-sharing yields even worse dynamic behavior.
  Finally, we contrast our mostly negative theoretical results by a careful
empirical study. Our simulations indicate two positive facts: (1) The
non-convergent behavior seems to be confined to a small set of pathological
instances and is unlikely to show up in practice. (2) In all our simulations we
observed a remarkably fast convergence towards a stable network in O(n) steps,
where n is the number of agents.
