Network Movement Games

We introduce a new class of games, called Network Movement Games, naturally related to the movement problems of [7], which models the spontaneous creation of multi-hop communication networks by the distributed and uncoordinated movement of k selfish mobile devices placed on the nodes of an underlying graph. Devices are players aiming to find the final positions which achieve a global property of the induced subnetwork. We actually focus on solutions (i.e. Nash equilibria) connecting all the players while minimizing the distances from their home locations. We show that the game always admits a pure Nash equilibrium, and that the convergence after a finite number of improving moves is guaranteed only when players perform their best possible moves; in this case, we provide tight bounds on the speed of convergence to Nash equilibria, both when initial positions are arbitrary and when players start at their home positions. As for the Nash equilibria performances, we first prove that the price of stability is 1 (i.e., an optimal solution is also a Nash equilibrium). Furthermore, we provide tight bounds on the price of anarchy, also showing that better performances are obtained when players start at their home positions. Finally, through extensive experiments, we show that high bounds on the price of anarchy as well as high convergence time of best move dynamics to Nash equilibria are only due to pathological worst cases. Moreover, quite often improving move dynamics (i.e., where players do not necessarily perform a best possible move) converge to Nash equilibria on the tested instances even though the class of instances does not guarantee the convergence.