In this paper we study a generalization of the classic network creation game in the scenario in which the n players sit on a given arbitrary host graph , which constrains the set of edges a player can activate at a cost of α≥0 each. This finds its motivations in the physical limitations one can have in constructing links in practice, and it has been studied in the past only when the routing cost component of a player is given by the sum of distances to all the other nodes. Here, we focus on another popular routing cost, namely that which takes into account for each player her maximum distance to any other player. For this version of the game, we first analyze some of its computational and dynamic aspects, and then we address the problem of understanding the structure of associated pure Nash equilibria. In this respect, we show that the corresponding price of anarchy (PoA) is fairly bad, even for very simple host graph topologies. More precisely, we first exhibit a lower bound of Ω(n/(1+α)) for any α=o(n). Notice that this implies a counter-intuitive lower bound of Ω(n) even for α=0, i.e., when edges can be activated for free. Then, we show that when the host graph is restricted to be either k -regular (for any constant k≥3), or a 2-dimensional grid, the PoA is still Ω(1+min⁡{α,nα}), which is proven to be tight for α=Ω(n). On the positive side, if α≥n, we show that the PoA is at most 2. Finally, in the case in which the host graph is very sparse (i.e., |E(H)|=n−1+k, with k=O(1)), we prove that the PoA is O(1), for any α.

Bilò, D., Guala', L., Leucci, S., Proietti, G. (2015). The max-distance network creation game on general host graphs. THEORETICAL COMPUTER SCIENCE, 573, 43-53 [10.1016/j.tcs.2015.01.044].

The max-distance network creation game on general host graphs

GUALA', LUCIANO;
2015-03-30

Abstract

In this paper we study a generalization of the classic network creation game in the scenario in which the n players sit on a given arbitrary host graph , which constrains the set of edges a player can activate at a cost of α≥0 each. This finds its motivations in the physical limitations one can have in constructing links in practice, and it has been studied in the past only when the routing cost component of a player is given by the sum of distances to all the other nodes. Here, we focus on another popular routing cost, namely that which takes into account for each player her maximum distance to any other player. For this version of the game, we first analyze some of its computational and dynamic aspects, and then we address the problem of understanding the structure of associated pure Nash equilibria. In this respect, we show that the corresponding price of anarchy (PoA) is fairly bad, even for very simple host graph topologies. More precisely, we first exhibit a lower bound of Ω(n/(1+α)) for any α=o(n). Notice that this implies a counter-intuitive lower bound of Ω(n) even for α=0, i.e., when edges can be activated for free. Then, we show that when the host graph is restricted to be either k -regular (for any constant k≥3), or a 2-dimensional grid, the PoA is still Ω(1+min⁡{α,nα}), which is proven to be tight for α=Ω(n). On the positive side, if α≥n, we show that the PoA is at most 2. Finally, in the case in which the host graph is very sparse (i.e., |E(H)|=n−1+k, with k=O(1)), we prove that the PoA is O(1), for any α.
30-mar-2015
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore INF/01 - INFORMATICA
English
Network creation games; Pure Nash equilibrium; Price of Anarchy; Host graph
http://www.sciencedirect.com/science/article/pii/S0304397515000912
Bilò, D., Guala', L., Leucci, S., Proietti, G. (2015). The max-distance network creation game on general host graphs. THEORETICAL COMPUTER SCIENCE, 573, 43-53 [10.1016/j.tcs.2015.01.044].
Bilò, D; Guala', L; Leucci, S; Proietti, G
Articolo su rivista
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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: https://hdl.handle.net/2108/133078
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 8
social impact