×

zbMATH — the first resource for mathematics

On the tree conjecture for the network creation game. (English) Zbl 1443.91071
The paper focuses on modeling real world networks from a game-theoretic point of view. In the network creation game agents correspond to nodes in a network and buy incident edges for the price of \(\alpha\) per edge to minimize their total distance to all other nodes. The price of anarchy PoA is the ratio of the overall network quality of the worst possible outcome of the uncoordinated network creation process and the network quality of the centrally designed optimal network. It was conjectured that the price of anarchy is constant for all \(\alpha\) and that for \(\alpha\ge n\) all equilibrium networks are trees.
Authors introduce a new technique for analyzing stable non-tree networks for high edge-price \(\alpha\) and use it to improve on the current best lower bound for \(\alpha\) for which all stable networks must be trees. They prove that for \(\alpha > 4n-13\) any stable network must be a tree, a significant improvement over the known bound of \(\alpha > 65n\) by A. Mamageishvili et al. [Lect. Notes Comput. Sci. 8305, 118–129 (2013; Zbl 1342.05169)] and the recently claimed bound of \(\alpha > 17n\) by C. Álvarez and A. Messegué [“Network creation games: structure vs anarchy”, Preprint, arXiv:1706.09132]. Since it is known that the PoA for stable tree networks is constant, this new bound directly implies a constant PoA for \(\alpha > 4n-13\).
Their new technique exploits properties of cycles in stable networks by focusing on critical pairs, strong critical pairs and min cycles. The main new contribution is revelation of a rich combinatorial structure within any non-tree Nash equilibrium (NE) network for \(\alpha > 2n-6\). Authors show that in this case any agent in any min cycle with a certain minimum length owns exactly one edge of the respective min cycle. As a result the biconnected component of any non-tree NE network cannot be a cycle and thus must contain two nodes with are situated in a particular critical pair configuration. The existence of this specific critical pair leads finally to a contradiction with \(\alpha > 4n-13\).

MSC:
91A43 Games involving graphs
91A68 Algorithmic game theory and complexity
05C90 Applications of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Albers, S.; Eilts, S.; Even-Dar, E.; Mansour, Y.; Roditty, L., On Nash equilibria for a network creation game, ACM Trans. Econ. Comput. (TEAC), 2, 1, 2 (2014)
[2] Alon, N.; Demaine, ED; Hajiaghayi, MT; Leighton, T., Basic network creation games, SIAM J. Discret. Math., 27, 2, 656-668 (2013) · Zbl 1273.90167
[3] Àlvarez, C.; Blesa, MJ; Duch, A.; Messegué, A.; Serna, M., Celebrity games, Theor. Comput. Sci., 648, 56-71 (2016) · Zbl 1410.91115
[4] Àlvarez, C., Messegué, A.: Max celebrity games. In: International workshop on algorithms and models for the web-graph (WAW), pp. 88-99. Springer (2016) · Zbl 1398.91106
[5] Ȧlvarez, C., Messeguė, A.: Network creation games: Structure vs anarchy. arXiv:1706.09132 (2017)
[6] Àlvarez, C., Messegué, A.: On the constant price of anarchy conjecture. arXiv:1809.08027 (2018)
[7] Andelman, N.; Feldman, M.; Mansour, Y., Strong price of anarchy, Games Econom. Behav., 65, 2, 289-317 (2009) · Zbl 1156.91419
[8] Anshelevich, E.; Bhardwaj, O.; Usher, M., Friend of my friend: Network formation with two-hop benefit, Theory Comput. Syst., 57, 3, 711-752 (2015) · Zbl 1327.91059
[9] Bala, V.; Goyal, S., A noncooperative model of network formation, Econometrica, 68, 5, 1181-1229 (2000) · Zbl 1022.91047
[10] Barabási, A., Network science (2016), Cambridge: Cambridge University Press, Cambridge · Zbl 1353.94001
[11] Bilò, D., Gualà, L., Leucci, S., Proietti, G.: Network creation games with traceroute-based strategies. In: International colloquium on structural information and communication complexity (SIROCCO), pp. 210-223. Springer (2014) · Zbl 1318.68124
[12] Bilò, D.; Gualà, L.; Leucci, S.; Proietti, G., The max-distance network creation game on general host graphs, Theor. Comput. Sci., 573, 43-53 (2015) · Zbl 1318.68125
[13] Bilò, D.; Gualà, L.; Leucci, Stefano; Proietti, G., Locality-based network creation games, ACM Transactions on Parallel Computing (TOPC), 3, 1, 6 (2016)
[14] Bilò, D.; Gualà, L.; Proietti, G., Bounded-distance network creation games, ACM Trans. Econ. Comput. (TEAC), 3, 3, 16 (2015)
[15] Bilȯ, D., Lenzner, P.: On the tree conjecture for the network creation game. In: 35th symposium on theoretical aspects of computer science (STACS), pp. 14:1-14:15 (2018)
[16] Brandes, U., Hoefer, M., Nick, B.: Network creation games with disconnected equilibria. In: International workshop on internet and network economics (WINE), pp. 394-401. Springer (2008)
[17] Chauhan, A., Lenzner, P., Melnichenko, A., Molitor, L.: Selfish network creation with non-uniform edge cost. In: International symposium on algorithmic game theory (SAGT), pp. 160-172. Springer (2017) · Zbl 1403.91062
[18] Chauhan, A., Lenzner, P., Melnichenko, A., Münn, M.: On selfish creation of robust networks. In: International symposium on algorithmic game theory (SAGT), pp. 141-152. Springer (2016) · Zbl 1403.91063
[19] Corbo, J., Parkes, D.: The price of selfish behavior in bilateral network formation. In: 24th ACM symposium on principles of distributed computing (PODC), pp. 99-107. ACM (2005) · Zbl 1314.91051
[20] Cord-Landwehr, A., Lenzner, P.: Network creation games: think global-act local. In: International symposium on mathematical foundations of computer science (MFCS), pp. 248-260. Springer (2015) · Zbl 06482813
[21] Cord-Landwehr, A., Mäcker, A., auf der Heide, F.M.: Quality of service in network creation games. In: International conference on web and internet economics (WINE), pp. 423-428. Springer (2014) · Zbl 1404.91046
[22] Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to algorithms. MIT Press (2009) · Zbl 1187.68679
[23] de Keijzer, B., Janus, T.: On strong equilibria and improvement dynamics in network creation games. Internet Mathematics, 2019 (2019) · Zbl 1405.91077
[24] Demaine, ED; Hajiaghayi, MT; Mahini, H.; Zadimoghaddam, M., The price of anarchy in network creation games, ACM Trans. Algorithms (TALG), 8, 2, 13 (2012) · Zbl 1295.68041
[25] Demaine, ED; Hajiaghayi, M.; Mahini, H.; Zadimoghaddam, M., The price of anarchy in cooperative network creation games, ACM SIGecom Exchanges, 8, 2, 2 (2009) · Zbl 1236.68082
[26] Ehsani, S.; Fadaee, SS; Fazli, M.; Mehrabian, A.; Sadeghabad, SS; Safari, M.; Saghafian, M., A bounded budget network creation game, ACM Trans. Algorithms (TALG), 11, 4, 34 (2015) · Zbl 1398.91109
[27] Fabrikant, A., Luthra, A., Maneva, E., Papadimitriou, C., Shenker, S.: On a network creation game. In: 22nd symposium on principles of distributed computing (PODC), pp. 347-351. ACM (2003) · Zbl 1322.91013
[28] Friedrich, T., Ihde, S., Keßler, C., Lenzner, P., Neubert, S., Schumann, D.: Efficient best response computation for strategic network formation under attack. In: International symposium on algorithmic game theory (SAGT), pp. 199-211. Springer (2017) · Zbl 1403.91067
[29] Garey, MR; Johnson, DS, Computers and intractability, vol. 29 (2002), New York: wh Freeman, New York
[30] Goyal, S., Jabbari, S., Kearns, M., Khanna, S., Morgenstern, J.: Strategic network formation with attack and immunization. In: International conference on web and internet economics (WINE), pp. 429-443. Springer (2016) · Zbl 1404.91055
[31] Graham, R., Hamilton, L., Levavi, A., Loh, P.-S.: Anarchy is free in network creation. In: International workshop on algorithms and models for the web-graph (WAW), pp. 220-231. Springer (2013) · Zbl 1342.68036
[32] Jackson, M.O.: A survey of network formation models: stability and efficiency. Group Formation in Economics: Networks Clubs, and Coalitions, pp. 11-49 (2005)
[33] Jackson, MO, Social and economic networks (2010), Princeton: Princeton University Press, Princeton
[34] Jackson, MO; Wolinsky, A., A strategic model of social and economic networks, J. Econ. Theory, 71, 1, 44-74 (1996) · Zbl 0871.90144
[35] Janus, T., de Keijzer, B.: On strong equilibria and improvement dynamics in network creation games. In: International conference on web and internet economics (WINE), pp. 161-176. Springer (2017) · Zbl 1405.91077
[36] Johnson, DS; Lenstra, JK; Kan, RAHG, The complexity of the network design problem, Networks, 8, 4, 279-285 (1978) · Zbl 0395.94048
[37] Kariv, O.; Hakimi, SL, An algorithmic approach to network location problems. ii: The p-medians, SIAM J Appl Math, 37, 3, 539-560 (1979) · Zbl 0432.90075
[38] Kawald, B., Lenzner, P.: On dynamics in selfish network creation. In: 25th ACM symposium on parallelism in algorithms and architectures (SPAA), pp. 83-92. ACM (2013)
[39] Kleinberg, J.: The small-world phenomenon: An algorithmic perspective. In: 32nd ACM symposium on theory of computing (STOC), pp. 163-170. ACM (2000) · Zbl 1296.05181
[40] Kliemann, L., The price of anarchy for network formation in an adversary model, Games, 2, 3, 302-332 (2011) · Zbl 1311.91058
[41] Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: 16th symposium on theoretical aspects of computer science (STACS), pp. 404-413. Springer (1999) · Zbl 1099.91501
[42] Lenzner, P.: On dynamics in basic network creation games. In: International symposium on algorithmic game theory (SAGT), pp. 254-265. Springer (2011) · Zbl 1233.91071
[43] Lenzner, P.: Greedy selfish network creation. In: International workshop on internet and network economics (WINE), pp. 142-155. Springer (2012)
[44] Lenzner, P., On selfish network creation (2014), Humboldt University of Berlin: PhD thesis, Humboldt University of Berlin
[45] Mamageishvili, A.; Mihalák, M.; Müller, D., Tree Nash equilibria in the network creation game, Internet Math., 11, 4-5, 472-486 (2015)
[46] Meirom, E.A., Mannor, S., Orda, A.: Network formation games with heterogeneous players and the internet structure. In: 15th ACM conference on economics and computation (EC), pp. 735-752. ACM (2014)
[47] Mihalák, M., Schlegel, J.C.: Asymmetric swap-equilibrium: a unifying equilibrium concept for network creation games. In: International symposium on mathematical foundations of computer science (MFCS), pp. 693-704. Springer (2012) · Zbl 1366.91037
[48] Mihalák, M.; Schlegel, JC, The price of anarchy in network creation games is (mostly) constant, Theory Comput. Syst., 53, 1, 53-72 (2013) · Zbl 1293.91031
[49] Papadimitriou, C.: Algorithms, games, and the internet. In: 33rd ACM symposium on theory of computing (STOC), pp. 749-753. ACM (2001) · Zbl 1323.68022
[50] Travers, J.; Milgram, S., The small world problem, Phys. Today, 1, 61-67 (1967)
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.