Document Open Access Logo

On the Tree Conjecture for the Network Creation Game

Authors Davide Bilò, Pascal Lenzner

PDF
Thumbnail PDF

File

LIPIcs.STACS.2018.14.pdf
  • Filesize: 0.68 MB
  • 15 pages

Document Identifiers

Author Details

Davide Bilò
Pascal Lenzner

Cite As Get BibTex

Davide Bilò and Pascal Lenzner. On the Tree Conjecture for the Network Creation Game. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.STACS.2018.14

Abstract

Selfish Network Creation focuses on modeling real world networks from a game-theoretic point of view. One of the classic models by Fabrikant et al.[PODC'03] is the network creation game, where agents correspond to nodes in a network which buy incident edges for the price of alpha per edge to minimize their total distance to all other nodes. The model is well-studied but still has intriguing open problems. The most famous conjectures state that the price of anarchy is constant for all alpha and that for alpha >= n all equilibrium networks are trees.

We introduce a novel technique for analyzing stable networks for high edge-price alpha and employ it to improve on the best known bounds for both conjectures. In particular we show that for alpha > 4n-13 all equilibrium networks must be trees, which implies a constant price of anarchy for this range of alpha. Moreover, we also improve the constant upper bound on the price of anarchy for equilibrium trees.

Subject Classification

Keywords
  • Algorithmic Game Theory
  • Network Creation Game
  • Price of Anarchy
  • Quality of Nash Equilibria

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Susanne Albers, Stefan Eilts, Eyal Even-Dar, Yishay Mansour, and Liam Roditty. On nash equilibria for a network creation game. ACM TEAC, 2(1):2, 2014. Google Scholar
  2. Noga Alon, Erik D Demaine, Mohammad T Hajiaghayi, and Tom Leighton. Basic network creation games. SIAM J. Disc. Math., 27(2):656-668, 2013. Google Scholar
  3. Carme Àlvarez, Maria J Blesa, Amalia Duch, Arnau Messegué, and Maria Serna. Celebrity games. Theoretical Computer Science, 648:56-71, 2016. Google Scholar
  4. Carme Àlvarez and Arnau Messegué. Max celebrity games. In Anthony Bonato, Fan Chung Graham, and Pawel Pralat, editors, Algorithms and Models for the Web Graph - 13th International Workshop, WAW 2016, Montreal, QC, Canada, December 14-15, 2016, Proceedings, volume 10088 of Lecture Notes in Computer Science, pages 88-99, 2016. URL: http://dx.doi.org/10.1007/978-3-319-49787-7_8.
  5. Carme Àlvarez and Arnau Messegué. Network creation games: Structure vs anarchy. CoRR, abs/1706.09132, 2017. URL: http://arxiv.org/abs/1706.09132.
  6. Nir Andelman, Michal Feldman, and Yishay Mansour. Strong price of anarchy. Games and Economic Behavior, 65(2):289-317, 2009. URL: http://dx.doi.org/10.1016/j.geb.2008.03.005.
  7. Elliot Anshelevich, Onkar Bhardwaj, and Michael Usher. Friend of my friend: Network formation with two-hop benefit. Theory Comput. Syst., 57(3):711-752, 2015. URL: http://dx.doi.org/10.1007/s00224-014-9582-4.
  8. Venkatesh Bala and Sanjeev Goyal. A noncooperative model of network formation. Econometrica, 68(5):1181-1229, 2000. Google Scholar
  9. Albert-László Barabási. Network science. Cambridge University Press, 2016. Google Scholar
  10. Davide Bilò, Luciano Gualà, Stefano Leucci, and Guido Proietti. Network creation games with traceroute-based strategies. In Magnús M. Halldórsson, editor, Structural Information and Communication Complexity - 21st International Colloquium, SIROCCO 2014, Takayama, Japan, July 23-25, 2014. Proceedings, volume 8576 of Lecture Notes in Computer Science, pages 210-223. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-319-09620-9_17.
  11. Davide Bilò, Luciano Gualà, Stefano Leucci, and Guido Proietti. The max-distance network creation game on general host graphs. Theor. Comput. Sci., 573:43-53, 2015. URL: http://dx.doi.org/10.1016/j.tcs.2015.01.044.
  12. Davide Bilò, Luciano Gualà, Stefano Leucci, and Guido Proietti. Locality-based network creation games. TOPC, 3(1):6:1-6:26, 2016. URL: http://dx.doi.org/10.1145/2938426.
  13. Davide Bilò, Luciano Gualà, and Guido Proietti. Bounded-distance network creation games. ACM Trans. Economics and Comput., 3(3):16:1-16:20, 2015. URL: http://dx.doi.org/10.1145/2770639.
  14. Davide Bilò and Pascal Lenzner. On the tree conjecture for the network creation game. CoRR, abs/1710.01782, 2017. URL: http://arxiv.org/abs/1710.01782.
  15. Ulrik Brandes, Martin Hoefer, and Bobo Nick. Network creation games with disconnected equilibria. In Christos H. Papadimitriou and Shuzhong Zhang, editors, Internet and Network Economics, 4th International Workshop, WINE 2008, Shanghai, China, December 17-20, 2008. Proceedings, volume 5385 of Lecture Notes in Computer Science, pages 394-401. Springer, 2008. URL: http://dx.doi.org/10.1007/978-3-540-92185-1_45.
  16. Ankit Chauhan, Pascal Lenzner, Anna Melnichenko, and Louise Molitor. Selfish network creation with non-uniform edge cost. In Vittorio Bilò and Michele Flammini, editors, Algorithmic Game Theory - 10th International Symposium, SAGT 2017, L'Aquila, Italy, September 12-14, 2017, Proceedings, volume 10504 of Lecture Notes in Computer Science, pages 160-172. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-66700-3_13.
  17. Ankit Chauhan, Pascal Lenzner, Anna Melnichenko, and Martin Münn. On selfish creation of robust networks. In Martin Gairing and Rahul Savani, editors, Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Liverpool, UK, September 19-21, 2016. Proceedings, volume 9928 of Lecture Notes in Computer Science, pages 141-152. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-662-53354-3_12.
  18. Jacomo Corbo and David C. Parkes. The price of selfish behavior in bilateral network formation. In Marcos Kawazoe Aguilera and James Aspnes, editors, Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing, PODC 2005, Las Vegas, NV, USA, July 17-20, 2005, pages 99-107. ACM, 2005. URL: http://dx.doi.org/10.1145/1073814.1073833.
  19. Andreas Cord-Landwehr and Pascal Lenzner. Network creation games: Think global - act local. In Giuseppe F. Italiano, Giovanni Pighizzini, and Donald Sannella, editors, Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II, volume 9235 of Lecture Notes in Computer Science, pages 248-260. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48054-0_21.
  20. Andreas Cord-Landwehr, Alexander Mäcker, and Friedhelm Meyer auf der Heide. Quality of service in network creation games. In Tie-Yan Liu, Qi Qi, and Yinyu Ye, editors, Web and Internet Economics - 10th International Conference, WINE 2014, Beijing, China, December 14-17, 2014. Proceedings, volume 8877 of Lecture Notes in Computer Science, pages 423-428. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-319-13129-0_34.
  21. Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, and Morteza Zadimoghaddam. The price of anarchy in cooperative network creation games. SIGecom Exch., 8(2):2:1-2:20, 2009. Google Scholar
  22. Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, and Morteza Zadimoghaddam. The price of anarchy in network creation games. ACM Trans. Algorithms, 8(2):13:1-13:13, 2012. URL: http://dx.doi.org/10.1145/2151171.2151176.
  23. Shayan Ehsani, Saber Shokat Fadaee, MohammadAmin Fazli, Abbas Mehrabian, Sina Sadeghian Sadeghabad, Mohammad Ali Safari, and Morteza Saghafian. A bounded budget network creation game. ACM Trans. Algorithms, 11(4):34:1-34:25, 2015. URL: http://dx.doi.org/10.1145/2701615.
  24. Alex Fabrikant, Ankur Luthra, Elitza N. Maneva, Christos H. Papadimitriou, and Scott Shenker. On a network creation game. In Elizabeth Borowsky and Sergio Rajsbaum, editors, Proceedings of the Twenty-Second ACM Symposium on Principles of Distributed Computing, PODC 2003, Boston, Massachusetts, USA, July 13-16, 2003, pages 347-351. ACM, 2003. URL: http://dx.doi.org/10.1145/872035.872088.
  25. Sanjeev Goyal, Shahin Jabbari, Michael J. Kearns, Sanjeev Khanna, and Jamie Morgenstern. Strategic network formation with attack and immunization. In Yang Cai and Adrian Vetta, editors, Web and Internet Economics - 12th International Conference, WINE 2016, Montreal, Canada, December 11-14, 2016, Proceedings, volume 10123 of Lecture Notes in Computer Science, pages 429-443. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-662-54110-4_30.
  26. Matthew O Jackson and Asher Wolinsky. A strategic model of social and economic networks. Journal of economic theory, 71(1):44-74, 1996. Google Scholar
  27. Tomasz Janus and Bart de Keijzer. On strong equilibria and improvement dynamics in network creation games. In Nikhil R. Devanur and Pinyan Lu, editors, Web and Internet Economics - 13th International Conference, WINE 2017, Bangalore, India, December 17-20, 2017, Proceedings, volume 10660 of Lecture Notes in Computer Science, pages 161-176. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-71924-5_12.
  28. O. Kariv and S. L. Hakimi. An algorithmic approach to network location problems. ii: The p-medians. SIAM Journal on Applied Mathematics, 37(3):pp. 539-560, 1979. Google Scholar
  29. Bernd Kawald and Pascal Lenzner. On dynamics in selfish network creation. In Guy E. Blelloch and Berthold Vöcking, editors, 25th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '13, Montreal, QC, Canada - July 23 - 25, 2013, pages 83-92. ACM, 2013. URL: http://dx.doi.org/10.1145/2486159.2486185.
  30. Jon M. Kleinberg. The small-world phenomenon: an algorithmic perspective. In F. Frances Yao and Eugene M. Luks, editors, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 163-170. ACM, 2000. URL: http://dx.doi.org/10.1145/335305.335325.
  31. Lasse Kliemann. The price of anarchy for network formation in an adversary model. Games, 2(3):302-332, 2011. URL: http://dx.doi.org/10.3390/g2030302.
  32. Elias Koutsoupias and Christos H. Papadimitriou. Worst-case equilibria. In Christoph Meinel and Sophie Tison, editors, STACS 99, 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 4-6, 1999, Proceedings, volume 1563 of Lecture Notes in Computer Science, pages 404-413. Springer, 1999. URL: http://dx.doi.org/10.1007/3-540-49116-3_38.
  33. Pascal Lenzner. On dynamics in basic network creation games. In Giuseppe Persiano, editor, Algorithmic Game Theory, 4th International Symposium, SAGT 2011, Amalfi, Italy, October 17-19, 2011. Proceedings, volume 6982 of Lecture Notes in Computer Science, pages 254-265. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-24829-0_23.
  34. Pascal Lenzner. Greedy selfish network creation. In Paul W. Goldberg, editor, Internet and Network Economics - 8th International Workshop, WINE 2012, Liverpool, UK, December 10-12, 2012. Proceedings, volume 7695 of Lecture Notes in Computer Science, pages 142-155. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-35311-6_11.
  35. Pascal Lenzner. On selfish network creation. PhD thesis, Humboldt University of Berlin, 2014. URL: http://edoc.hu-berlin.de/dissertationen/lenzner-pascal-2014-05-30/PDF/lenzner.pdf.
  36. Akaki Mamageishvili, Matús Mihalák, and Dominik Müller. Tree nash equilibria in the network creation game. Internet Mathematics, 11(4-5):472-486, 2015. URL: http://dx.doi.org/10.1080/15427951.2015.1016248.
  37. Eli A. Meirom, Shie Mannor, and Ariel Orda. Network formation games with heterogeneous players and the internet structure. In Moshe Babaioff, Vincent Conitzer, and David Easley, editors, ACM Conference on Economics and Computation, EC '14, Stanford , CA, USA, June 8-12, 2014, pages 735-752. ACM, 2014. URL: http://dx.doi.org/10.1145/2600057.2602862.
  38. Matús Mihalák and Jan Christoph Schlegel. Asymmetric swap-equilibrium: A unifying equilibrium concept for network creation games. In Branislav Rovan, Vladimiro Sassone, and Peter Widmayer, editors, Mathematical Foundations of Computer Science 2012 - 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012. Proceedings, volume 7464 of Lecture Notes in Computer Science, pages 693-704. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-32589-2_60.
  39. Matús Mihalák and Jan Christoph Schlegel. The price of anarchy in network creation games is (mostly) constant. Theory Comput. Syst., 53(1):53-72, 2013. URL: http://dx.doi.org/10.1007/s00224-013-9459-y.
  40. Jeffrey Travers and Stanley Milgram. The small world problem. Phychology Today, 1:61-67, 1967. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact