The max-distance network creation game on general host graphs.

*(English)*Zbl 1318.68125Summary: In this paper we study a generalization of the classic network creation game to 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 \(\alpha \geq 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 its \(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 several basic classes of host graphs. More precisely, we first exhibit a lower bound of \(\Omega (\sqrt{ n / (1+\alpha)})\) for any \(\alpha = o(n)\). Notice that this implies a counter-intuitive lower bound of \(\Omega(\sqrt{n})\) for the case \(\alpha = 0\) (i.e., 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 \geq 3\)), or a 2-dimensional grid, the PoA is still \(\Omega(1+\min\{\alpha, \frac{n}{\alpha}\})\), which is proven to be tight for \(\alpha=\Omega(\sqrt{n})\). On the positive side, if \(\alpha \geq n\), we show the PoA is \(O(1)\). 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 \(\alpha \).

##### MSC:

68R10 | Graph theory (including graph drawing) in computer science |

91A10 | Noncooperative games |

91A43 | Games involving graphs |

Full Text:
DOI

##### References:

[1] | Alon, N.; Demaine, E. D.; Hajiaghayi, M.; Leighton, T., Basic network creation games, SIAM J. Discrete Math., 27, 2, 656-668, (2013) · Zbl 1273.90167 |

[2] | Bilò, D.; Gualà, L.; Proietti, G., Bounded-distance network creation games, (Proceedings of the 8th International Workshop on Internet & Network Economics (WINE’12), Lecture Notes in Computer Science, vol. 7695, (2012), Springer), 72-85, An extended version of this paper has been accepted to ACM Transactions on Economics and Computation |

[3] | Demaine, E. D.; Hajiaghayi, M.; Mahini, H.; Zadimoghaddam, M., The price of anarchy in cooperative network creation games, ACM SIGecom Exch., 8, 2, 2, (2009) · Zbl 1236.68082 |

[4] | Demaine, E. D.; Hajiaghayi, M.; Mahini, H.; Zadimoghaddam, M., The price of anarchy in network creation games, ACM Trans. Algorithms, 8, 2, 13, (2012) · Zbl 1295.68041 |

[5] | Ehsani, S.; Fazli, M.; Mehrabian, A.; Sadeghabad, S. S.; Saghafian, M.; Shokatfadaee, S.; Safari, M., On a bounded budget network creation game, (Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA’11, (2011), ACM Press), 207-214 |

[6] | Fabrikant, A.; Luthra, A.; Maneva, E.; Papadimitriou, C. H.; Shenker, S., On a network creation game, (Proceedings of the 22nd Symposium on Principles of Distributed Computing, PODC’03, (2003), ACM Press), 347-351 · Zbl 1322.91013 |

[7] | Jackson, M. O.; Wolinsky, A., A strategic model of social and economic networks, J. Econom. Theory, 71, 1, 44-74, (1996) · Zbl 0871.90144 |

[8] | Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations, (1972), Plenum Press New York), 85-103 |

[9] | Kawald, B.; Lenzner, P., On dynamics in selfish network creation, (Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA’13, (2013), ACM), 83-92 |

[10] | Laoutaris, N.; Poplawski, L. J.; Rajaraman, R.; Sundaram, R.; Teng, S.-H., Bounded budget connection (BBC) games or how to make friends and influence people, on a budget, (Proceedings of the 27th ACM Symposium on Principles of Distributed Computing, PODC’08, (2008), ACM Press), 165-174 · Zbl 1301.91007 |

[11] | Lenzner, P., On dynamics in basic network creation games, (Proceedings of the 4th International Symposium on Algorithmic Game Theory, SAGT’11, Lecture Notes in Computer Science, vol. 6982, (2011), Springer), 254-265 · Zbl 1233.91071 |

[12] | Lenzner, P., Greedy selfish network creation, (Proceedings of the 8th International Workshop on Internet and Network Economics, WINE’12, Lecture Notes in Computer Science, vol. 7695, (2012), Springer), 142-155 |

[13] | Mamageishvili, A.; Mihalák, M.; Müller, D., Tree Nash equilibria in the network creation game, (Proceedings of the 10th International Workshop on Algorithms and Models for the Web Graph, WAW’13, Lecture Notes in Computer Science, vol. 8305, (2013), Springer), 118-129 · Zbl 1342.05169 |

[14] | Mihalák, M.; Schlegel, J. C., Asymmetric swap-equilibrium: a unifying equilibrium concept for network creation games, (Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science, MFCS’12, Lecture Notes in Computer Science, vol. 7464, (2012), Springer), 693-704 · Zbl 1366.91037 |

[15] | Mihalák, M.; Schlegel, J. C., The price of anarchy in network creation games is (mostly) constant, Theory Comput. Syst., 53, 1, 53-72, (2013) · Zbl 1293.91031 |

[16] | Schoone, A. A.; Bodlaender, H. L.; van Leeuwen, J., Improved diameter bounds for altered graphs, (Proceedings of the 12th Workshop on Graph-Theoretic Concepts in Computer Science, WG’86, Lecture Notes in Computer Science, vol. 246, (1986)), 227-236 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.