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.

Network Movement Games

FLAMMINI, MICHELE;
2017

Abstract

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.
Movement problems; Network creation games; Price of anarchy; Price of stability; Speed of convergence; Theoretical Computer Science; Computer Science (all)
File in questo prodotto:
File Dimensione Formato  
2017_TheorComputSci_667_Flammini.pdf

non disponibili

Descrizione: Articolo principale
Licenza: Non pubblico
1.12 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.12571/2344
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact