{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T10:50:25Z","timestamp":1778496625668,"version":"3.51.4"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,8,16]],"date-time":"2019-08-16T00:00:00Z","timestamp":1565913600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,8,16]],"date-time":"2019-08-16T00:00:00Z","timestamp":1565913600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2020,4]]},"DOI":"10.1007\/s00224-019-09945-9","type":"journal-article","created":{"date-parts":[[2019,8,16]],"date-time":"2019-08-16T05:03:01Z","timestamp":1565931781000},"page":"422-443","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["On the Tree Conjecture for the Network Creation Game"],"prefix":"10.1007","volume":"64","author":[{"given":"Davide","family":"Bil\u00f2","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3010-1019","authenticated-orcid":false,"given":"Pascal","family":"Lenzner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,8,16]]},"reference":[{"issue":"1","key":"9945_CR1","first-page":"2","volume":"2","author":"S Albers","year":"2014","unstructured":"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)","journal-title":"ACM Trans. Econ. Comput. (TEAC)"},{"issue":"2","key":"9945_CR2","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1137\/090771478","volume":"27","author":"N Alon","year":"2013","unstructured":"Alon, N., Demaine, E.D., Hajiaghayi, M.T., Leighton, T.: Basic network creation games. SIAM J. Discret. Math. 27(2), 656\u2013668 (2013)","journal-title":"SIAM J. Discret. Math."},{"key":"9945_CR3","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.tcs.2016.08.005","volume":"648","author":"C \u00c0lvarez","year":"2016","unstructured":"\u00c0lvarez, C., Blesa, M.J., Duch, A., Messegu\u00e9, A., Serna, M.: Celebrity games. Theor. Comput. Sci. 648, 56\u201371 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"9945_CR4","doi-asserted-by":"crossref","unstructured":"\u00c0lvarez, C., Messegu\u00e9, A.: Max celebrity games. In: International workshop on algorithms and models for the web-graph (WAW), pp. 88\u201399. Springer (2016)","DOI":"10.1007\/978-3-319-49787-7_8"},{"key":"9945_CR5","unstructured":"A\u0307lvarez, C., Messegu\u0117, A.: Network creation games: Structure vs anarchy. arXiv:\n1706.09132\n\n (2017)"},{"key":"9945_CR6","unstructured":"\u00c0lvarez, C., Messegu\u00e9, A.: On the constant price of anarchy conjecture. arXiv:\n1809.08027\n\n (2018)"},{"issue":"2","key":"9945_CR7","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/j.geb.2008.03.005","volume":"65","author":"N Andelman","year":"2009","unstructured":"Andelman, N., Feldman, M., Mansour, Y.: Strong price of anarchy. Games Econom. Behav. 65(2), 289\u2013317 (2009)","journal-title":"Games Econom. Behav."},{"issue":"3","key":"9945_CR8","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1007\/s00224-014-9582-4","volume":"57","author":"E Anshelevich","year":"2015","unstructured":"Anshelevich, E., Bhardwaj, O., Usher, M.: Friend of my friend: Network formation with two-hop benefit. Theory Comput. Syst. 57(3), 711\u2013752 (2015)","journal-title":"Theory Comput. Syst."},{"issue":"5","key":"9945_CR9","doi-asserted-by":"publisher","first-page":"1181","DOI":"10.1111\/1468-0262.00155","volume":"68","author":"V Bala","year":"2000","unstructured":"Bala, V., Goyal, S.: A noncooperative model of network formation. Econometrica 68(5), 1181\u20131229 (2000)","journal-title":"Econometrica"},{"key":"9945_CR10","volume-title":"Network science","author":"A Barab\u00e1si","year":"2016","unstructured":"Barab\u00e1si, A.: Network science. Cambridge University Press, Cambridge (2016)"},{"key":"9945_CR11","doi-asserted-by":"crossref","unstructured":"Bil\u00f2, D., Gual\u00e0, L., Leucci, S., Proietti, G.: Network creation games with traceroute-based strategies. In: International colloquium on structural information and communication complexity (SIROCCO), pp. 210\u2013223. Springer (2014)","DOI":"10.1007\/978-3-319-09620-9_17"},{"key":"9945_CR12","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.tcs.2015.01.044","volume":"573","author":"D Bil\u00f2","year":"2015","unstructured":"Bil\u00f2, D., Gual\u00e0, L., Leucci, S., Proietti, G.: The max-distance network creation game on general host graphs. Theor. Comput. Sci. 573, 43\u201353 (2015)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9945_CR13","first-page":"6","volume":"3","author":"D Bil\u00f2","year":"2016","unstructured":"Bil\u00f2, D., Gual\u00e0, L., Leucci, Stefano, Proietti, G.: Locality-based network creation games. ACM Transactions on Parallel Computing (TOPC) 3(1), 6 (2016)","journal-title":"ACM Transactions on Parallel Computing (TOPC)"},{"issue":"3","key":"9945_CR14","first-page":"16","volume":"3","author":"D Bil\u00f2","year":"2015","unstructured":"Bil\u00f2, D., Gual\u00e0, L., Proietti, G.: Bounded-distance network creation games. ACM Trans. Econ. Comput. (TEAC) 3(3), 16 (2015)","journal-title":"ACM Trans. Econ. Comput. (TEAC)"},{"key":"9945_CR15","unstructured":"Bilo\u0307, 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\u201314:15 (2018)"},{"key":"9945_CR16","doi-asserted-by":"crossref","unstructured":"Brandes, U., Hoefer, M., Nick, B.: Network creation games with disconnected equilibria. In: International workshop on internet and network economics (WINE), pp. 394\u2013401. Springer (2008)","DOI":"10.1007\/978-3-540-92185-1_45"},{"key":"9945_CR17","doi-asserted-by":"crossref","unstructured":"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\u2013172. Springer (2017)","DOI":"10.1007\/978-3-319-66700-3_13"},{"key":"9945_CR18","doi-asserted-by":"crossref","unstructured":"Chauhan, A., Lenzner, P., Melnichenko, A., M\u00fcnn, M.: On selfish creation of robust networks. In: International symposium on algorithmic game theory (SAGT), pp. 141\u2013152. Springer (2016)","DOI":"10.1007\/978-3-662-53354-3_12"},{"key":"9945_CR19","doi-asserted-by":"crossref","unstructured":"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\u2013107. ACM (2005)","DOI":"10.1145\/1073814.1073833"},{"key":"9945_CR20","doi-asserted-by":"crossref","unstructured":"Cord-Landwehr, A., Lenzner, P.: Network creation games: think global\u2013act local. In: International symposium on mathematical foundations of computer science (MFCS), pp. 248\u2013260. Springer (2015)","DOI":"10.1007\/978-3-662-48054-0_21"},{"key":"9945_CR21","doi-asserted-by":"crossref","unstructured":"Cord-Landwehr, A., M\u00e4cker, A., auf der Heide, F.M.: Quality of service in network creation games. In: International conference on web and internet economics (WINE), pp. 423\u2013428. Springer (2014)","DOI":"10.1007\/978-3-319-13129-0_34"},{"key":"9945_CR22","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to algorithms. MIT Press (2009)"},{"key":"9945_CR23","doi-asserted-by":"crossref","unstructured":"de Keijzer, B., Janus, T.: On strong equilibria and improvement dynamics in network creation games. Internet Mathematics, 2019 (2019)","DOI":"10.24166\/im.01.2019"},{"issue":"2","key":"9945_CR24","first-page":"13","volume":"8","author":"ED Demaine","year":"2012","unstructured":"Demaine, E.D., Hajiaghayi, M.T., Mahini, H., Zadimoghaddam, M.: The price of anarchy in network creation games. ACM Trans. Algorithms (TALG) 8(2), 13 (2012)","journal-title":"ACM Trans. Algorithms (TALG)"},{"issue":"2","key":"9945_CR25","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1980522.1980524","volume":"8","author":"ED Demaine","year":"2009","unstructured":"Demaine, E.D, Hajiaghayi, M., Mahini, H., Zadimoghaddam, M.: The price of anarchy in cooperative network creation games. ACM SIGecom Exchanges 8(2), 2 (2009)","journal-title":"ACM SIGecom Exchanges"},{"issue":"4","key":"9945_CR26","first-page":"34","volume":"11","author":"S Ehsani","year":"2015","unstructured":"Ehsani, S., Fadaee, S.S., Fazli, M., Mehrabian, A., Sadeghabad, S.S., Safari, M., Saghafian, M.: A bounded budget network creation game. ACM Trans. Algorithms (TALG) 11(4), 34 (2015)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"9945_CR27","doi-asserted-by":"crossref","unstructured":"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\u2013351. ACM (2003)","DOI":"10.1145\/872035.872088"},{"key":"9945_CR28","doi-asserted-by":"crossref","unstructured":"Friedrich, T., Ihde, S., Ke\u00dfler, 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\u2013211. Springer (2017)","DOI":"10.1007\/978-3-319-66700-3_16"},{"key":"9945_CR29","volume-title":"Computers and intractability, vol. 29","author":"MR Garey","year":"2002","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability, vol. 29. wh Freeman, New York (2002)"},{"key":"9945_CR30","doi-asserted-by":"crossref","unstructured":"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\u2013443. Springer (2016)","DOI":"10.1007\/978-3-662-54110-4_30"},{"key":"9945_CR31","doi-asserted-by":"crossref","unstructured":"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\u2013231. Springer (2013)","DOI":"10.1007\/978-3-319-03536-9_17"},{"key":"9945_CR32","doi-asserted-by":"crossref","unstructured":"Jackson, M.O.: A survey of network formation models: stability and efficiency. Group Formation in Economics: Networks Clubs, and Coalitions, pp. 11\u201349 (2005)","DOI":"10.1017\/CBO9780511614385.002"},{"key":"9945_CR33","doi-asserted-by":"publisher","DOI":"10.2307\/j.ctvcm4gh1","volume-title":"Social and economic networks","author":"MO Jackson","year":"2010","unstructured":"Jackson, M.O.: Social and economic networks. Princeton University Press, Princeton (2010)"},{"issue":"1","key":"9945_CR34","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1006\/jeth.1996.0108","volume":"71","author":"MO Jackson","year":"1996","unstructured":"Jackson, M.O, Wolinsky, A.: A strategic model of social and economic networks. J. Econ. Theory 71(1), 44\u201374 (1996)","journal-title":"J. Econ. Theory"},{"key":"9945_CR35","doi-asserted-by":"crossref","unstructured":"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\u2013176. Springer (2017)","DOI":"10.1007\/978-3-319-71924-5_12"},{"issue":"4","key":"9945_CR36","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1002\/net.3230080402","volume":"8","author":"DS Johnson","year":"1978","unstructured":"Johnson, D.S., Lenstra, J.K., Kan, R.AHG.: The complexity of the network design problem. Networks 8(4), 279\u2013285 (1978)","journal-title":"Networks"},{"issue":"3","key":"9945_CR37","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1137\/0137041","volume":"37","author":"O Kariv","year":"1979","unstructured":"Kariv, O., Hakimi, S.L.: An algorithmic approach to network location problems. ii: The p-medians. SIAM J Appl Math 37(3), 539\u2013560 (1979)","journal-title":"SIAM J Appl Math"},{"key":"9945_CR38","doi-asserted-by":"crossref","unstructured":"Kawald, B., Lenzner, P.: On dynamics in selfish network creation. In: 25th ACM symposium on parallelism in algorithms and architectures (SPAA), pp. 83\u201392. ACM (2013)","DOI":"10.1145\/2486159.2486185"},{"key":"9945_CR39","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.: The small-world phenomenon: An algorithmic perspective. In: 32nd ACM symposium on theory of computing (STOC), pp. 163\u2013170. ACM (2000)","DOI":"10.1145\/335305.335325"},{"issue":"3","key":"9945_CR40","doi-asserted-by":"publisher","first-page":"302","DOI":"10.3390\/g2030302","volume":"2","author":"L Kliemann","year":"2011","unstructured":"Kliemann, L.: The price of anarchy for network formation in an adversary model. Games 2(3), 302\u2013332 (2011)","journal-title":"Games"},{"key":"9945_CR41","doi-asserted-by":"crossref","unstructured":"Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: 16th symposium on theoretical aspects of computer science (STACS), pp. 404\u2013413. Springer (1999)","DOI":"10.1007\/3-540-49116-3_38"},{"key":"9945_CR42","doi-asserted-by":"crossref","unstructured":"Lenzner, P.: On dynamics in basic network creation games. In: International symposium on algorithmic game theory (SAGT), pp. 254\u2013265. Springer (2011)","DOI":"10.1007\/978-3-642-24829-0_23"},{"key":"9945_CR43","doi-asserted-by":"crossref","unstructured":"Lenzner, P.: Greedy selfish network creation. In: International workshop on internet and network economics (WINE), pp. 142\u2013155. Springer (2012)","DOI":"10.1007\/978-3-642-35311-6_11"},{"key":"9945_CR44","volume-title":"On selfish network creation","author":"P Lenzner","year":"2014","unstructured":"Lenzner, P.: On selfish network creation. PhD thesis, Humboldt University of Berlin (2014)"},{"issue":"4-5","key":"9945_CR45","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1080\/15427951.2015.1016248","volume":"11","author":"A Mamageishvili","year":"2015","unstructured":"Mamageishvili, A., Mihal\u00e1k, M., M\u00fcller, D.: Tree Nash equilibria in the network creation game. Internet Math. 11(4-5), 472\u2013486 (2015)","journal-title":"Internet Math."},{"key":"9945_CR46","doi-asserted-by":"crossref","unstructured":"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\u2013752. ACM (2014)","DOI":"10.1145\/2600057.2602862"},{"key":"9945_CR47","doi-asserted-by":"crossref","unstructured":"Mihal\u00e1k, 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\u2013704. Springer (2012)","DOI":"10.1007\/978-3-642-32589-2_60"},{"issue":"1","key":"9945_CR48","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/s00224-013-9459-y","volume":"53","author":"M Mihal\u00e1k","year":"2013","unstructured":"Mihal\u00e1k, M., Schlegel, J.C.: The price of anarchy in network creation games is (mostly) constant. Theory Comput. Syst. 53(1), 53\u201372 (2013)","journal-title":"Theory Comput. Syst."},{"key":"9945_CR49","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.: Algorithms, games, and the internet. In: 33rd ACM symposium on theory of computing (STOC), pp. 749\u2013753. ACM (2001)","DOI":"10.1145\/380752.380883"},{"key":"9945_CR50","first-page":"61","volume":"1","author":"J Travers","year":"1967","unstructured":"Travers, J., Milgram, S.: The small world problem. Phys. Today 1, 61\u201367 (1967)","journal-title":"Phys. Today"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09945-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-019-09945-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-019-09945-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,14]],"date-time":"2020-08-14T23:27:05Z","timestamp":1597447625000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-019-09945-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,16]]},"references-count":50,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["9945"],"URL":"https:\/\/doi.org\/10.1007\/s00224-019-09945-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,8,16]]},"assertion":[{"value":"16 August 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}