On dynamics in selfish network creation

摘要: We consider the dynamic behavior of several variants 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 decentralized creation overlay-networks. Unfortunately, due to non-constructiveness Nash equilibrium, no distributed algorithm finding such is known. treat games as sequential-move analyze if (uncoordinated) selfish play eventually converges an equilibrium. Thus, we shed light on one most natural algorithms this problem: local search, where each step some agent performs a myopic improving move.We show that fast convergence guaranteed all versions Swap Games, Alon [SPAA'10], initial network tree. Furthermore, prove process can be sped up almost optimal number moves employing very move policy. positive results are longer true has cycles surprising result even non-tree edge suffices destroy guarantee. This answers open problem from Ehsani [SPAA'11] negative. Moreover, policy enforce convergence. extend our negative well-studied original version, agents allowed buy delete edges well. For model there guarantee - optimally. Even worse, played non-complete host-graph, then instances sequence leads stable network. whether cost-sharing impact behavior. version Corbo Parkes [PODC'05] bilateral consent needed edge-costs shared among involved agents. rule yields worse behavior..