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 if (uncoordinated) selfish play eventually converges to an equilibrium. 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. Furthermore, we prove 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 we show the surprising result that even one non-tree edge suffices to destroy the convergence guarantee. This answers an open problem from Ehsani et al. [SPAA'11] in the negative. Moreover, we show that on non-tree networks no move policy can enforce convergence. We extend our negative results to the well-studied original version, where agents are allowed to buy and delete edges as well. For this model we prove that there is no convergence guarantee - even if all agents play optimally. Even worse, if played on a non-complete host-graph, then there are instances where no sequence of improving moves leads to a stable network. Furthermore, we analyze whether cost-sharing has positive impact on the convergence behavior. For this we consider a version by Corbo and Parkes [PODC'05] where bilateral consent is needed for the creation of an edge and where edge-costs are shared among the involved agents. We show that employing such a cost-sharing rule yields even worse dynamic behavior..
Our research focus is on theoretical computer science and algorithm engineering. We are equally interested in the mathematical foundations of algorithms and developing efficient algorithms in practice. A special focus is on random structures and methods.