Document Open Access Logo

Social Distancing Network Creation

Authors Tobias Friedrich, Hans Gawendowicz, Pascal Lenzner, Anna Melnichenko

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.62.pdf
  • Filesize: 1.07 MB
  • 21 pages

Document Identifiers

Author Details

Tobias Friedrich
  • Hasso Plattner Institute, University of Potsdam, Germany
Hans Gawendowicz
  • Hasso Plattner Institute, University of Potsdam, Germany
Pascal Lenzner
  • Hasso Plattner Institute, University of Potsdam, Germany
Anna Melnichenko
  • Hasso Plattner Institute, University of Potsdam, Germany

Funding

This work was supported by the DFG project GEONET under grant DFG 442003138.

Cite As Get BibTex

Tobias Friedrich, Hans Gawendowicz, Pascal Lenzner, and Anna Melnichenko. Social Distancing Network Creation. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 62:1-62:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ICALP.2022.62

Abstract

During a pandemic people have to find a trade-off between meeting others and staying safely at home. While meeting others is pleasant, it also increases the risk of infection. We consider this dilemma by introducing a game-theoretic network creation model in which selfish agents can form bilateral connections. They benefit from network neighbors, but at the same time, they want to maximize their distance to all other agents. This models the inherent conflict that social distancing rules impose on the behavior of selfish agents in a social network. Besides addressing this familiar issue, our model can be seen as the inverse to the well-studied Network Creation Game by Fabrikant et al. [PODC 2003] where agents aim at being as central as possible in the created network. Thus, our work is in-line with studies that compare minimization problems with their maximization versions.
We look at two variants of network creation governed by social distancing. In the first variant, there are no restrictions on the connections being formed. We characterize optimal and equilibrium networks, and we derive asymptotically tight bounds on the Price of Anarchy and Price of Stability. The second variant is the model’s generalization that allows restrictions on the connections that can be formed. As our main result, we prove that Swap-Maximal Routing-Cost Spanning Trees, an efficiently computable weaker variant of Maximum Routing-Cost Spanning Trees, actually resemble equilibria for a significant range of the parameter space. Moreover, we give almost tight bounds on the Price of Anarchy and Price of Stability. These results imply that, compared the well-studied inverse models, under social distancing the agents' selfish behavior has a significantly stronger impact on the quality of the equilibria, i.e., allowing socially much worse stable states.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory
  • Mathematics of computing → Graph algorithms
Keywords
  • Algorithmic Game Theory
  • Equilibrium Existence
  • Price of Anarchy
  • Network Creation Game
  • Social Distancing
  • Maximization vs. Minimization Problems

Metrics

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

Related Versions

References

  1. Daron Acemoglu, Asuman Ozdaglar, and Alireza Tahbaz-Salehi. Systemic risk and stability in financial networks. Am. Econ. Review, 105(2):564-608, 2015. URL: https://doi.org/10.1257/aer.20130456.
  2. Susanne Albers, Stefan Eilts, Eyal Even-Dar, Yishay Mansour, and Liam Roditty. On nash equilibria for a network creation game. ACM TEAC, 2(1):1-27, 2014. URL: https://doi.org/10.1145/2560767.
  3. Franklin Allen and Douglas Gale. Financial contagion. Journal of Political Economy, 108(1):1-33, 2000. URL: https://doi.org/10.1086/262109.
  4. Carme Àlvarez and Arnau Messegué. Network creation games: Structure vs anarchy. CoRR, abs/1706.09132, 2017. URL: https://doi.org/10.48550/arXiv.1706.09132.
  5. Carme Àlvarez and Arnau Messegué. On the price of anarchy for high-price links. In WINE 2019, pages 316-329, 2019. URL: https://doi.org/10.1007/978-3-030-35389-6_23.
  6. Nir Andelman, Michal Feldman, and Yishay Mansour. Strong price of anarchy. Games and Economic Behavior, 65(2):289-317, 2009. URL: https://doi.org/10.1016/j.geb.2008.03.005.
  7. Elliot Anshelevich, Anirban Dasgupta, Jon M. Kleinberg, Éva Tardos, Tom Wexler, and Tim Roughgarden. The price of stability for network design with fair cost allocation. SIAM Journal on Computing, 38(4):1602-1623, 2008. URL: https://doi.org/10.1137/070680096.
  8. Elliot Anshelevich, Anirban Dasgupta, Éva Tardos, and Tom Wexler. Near-optimal network design with selfish agents. Theory of Computing, 4(1):77-109, 2008. URL: https://doi.org/10.4086/toc.2008.v004a004.
  9. Venkatesh Bala and Sanjeev Goyal. A noncooperative model of network formation. Econometrica, 68(5):1181-1229, 2000. URL: https://doi.org/10.1111/1468-0262.00155.
  10. Davide Bilò, Tobias Friedrich, Pascal Lenzner, Stefanie Lowski, and Anna Melnichenko. Selfish creation of social networks. In AAAI 2021, pages 5185-5193, 2021. Google Scholar
  11. Davide Bilò, Tobias Friedrich, Pascal Lenzner, and Anna Melnichenko. Geometric network creation games. In SPAA 2019, pages 323-332, 2019. URL: https://doi.org/10.1145/3323165.3323199.
  12. Davide Bilò and Pascal Lenzner. On the tree conjecture for the network creation game. Theory of Computing Systems, 64(3):422-443, 2020. URL: https://doi.org/10.1007/s00224-019-09945-9.
  13. Larry Blume, David A. Easley, Jon M. Kleinberg, Robert D. Kleinberg, and Éva Tardos. Network formation in the presence of contagious risk. In EC 2011, pages 1-10, 2011. URL: https://doi.org/10.1145/1993574.1993576.
  14. Prosenjit Bose and Michiel Smid. On plane geometric spanners: A survey and open problems. Computational Geometry, 46(7):818-830, 2013. URL: https://doi.org/10.1016/j.comgeo.2013.04.002.
  15. Ricardo Caballero and Alp Simsek. Fire sales in a model of complexity. The Journal of Finance, 68, 2009. URL: https://doi.org/10.2139/ssrn.1496592.
  16. P.M. Camerini, G. Galbiati, and F. Maffioli. On the complexity of finding multi-constrained spanning trees. Discrete Applied Mathematics, 5(1):39-50, 1983. URL: https://doi.org/10.1016/0166-218X(83)90014-8.
  17. Yu Chen, Shahin Jabbari, Michael J. Kearns, Sanjeev Khanna, and Jamie Morgenstern. Network formation under random attack and probabilistic spread. In IJCAI 2019, pages 180-186, 2019. URL: https://doi.org/10.24963/ijcai.2019/26.
  18. Jacomo Corbo and David C. Parkes. The price of selfish behavior in bilateral network formation. In PODC 2005, pages 99-107, 2005. URL: https://doi.org/10.1145/1073814.1073833.
  19. Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, and Morteza Zadimoghaddam. The price of anarchy in cooperative network creation games. SIGecom Exchanges, 8(2):2:1-2:20, 2009. URL: https://doi.org/10.1145/1980522.1980524.
  20. Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, and Morteza Zadimoghaddam. The price of anarchy in network creation games. ACM Transactions on Algorithms, 8(2):13, 2012. URL: https://doi.org/10.1145/2151171.2151176.
  21. Jack Dippel and Adrian Vetta. An improved bound for the tree conjecture in network creation games. CoRR, abs/2106.05175, 2021. URL: https://doi.org/10.48550/arXiv.2106.05175.
  22. Andrey A. Dobrynin, Roger C. Entringer, and Ivan Gutman. Wiener index of trees: Theory and applications. Acta Applicandae Mathematica, 66:211-249, 2001. URL: https://doi.org/10.1023/A:1010767517079.
  23. Alex Fabrikant, Ankur Luthra, Elitza N. Maneva, Christos H. Papadimitriou, and Scott Shenker. On a network creation game. In PODC 2003, pages 347-351, 2003. URL: https://doi.org/10.1145/872035.872088.
  24. Wilhelm Friedemann, Tobias Friedrich, Hans Gawendowicz, Pascal Lenzner, Anna Melnichenko, Jannik Peters, Daniel Stephan, and Michael Vaichenker. Efficiency and stability in euclidean network design. In SPAA 2021, pages 232-242, 2021. URL: https://doi.org/10.1145/3409964.3461807.
  25. Tobias Friedrich, Hans Gawendowicz, Pascal Lenzner, and Anna Melnichenko. Social distancing network creation, 2022. URL: http://arxiv.org/abs/2204.10423.
  26. Tobias Friedrich, Sven Ihde, Christoph Keßler, Pascal Lenzner, Stefan Neubert, and David Schumann. Efficient best response computation for strategic network formation under attack. In SAGT 2017, pages 199-211, 2017. URL: https://doi.org/10.1007/978-3-319-66700-3_16.
  27. Giulia Galbiati, Angelo Morzenti, and Francesco Maffioli. On the approximability of some maximum spanning tree problems. Theoretical Computer Science, 181(1):107-118, 1997. Google Scholar
  28. Sanjeev Goyal, Shahin Jabbari, Michael J. Kearns, Sanjeev Khanna, and Jamie Morgenstern. Strategic network formation with attack and immunization. In WINE 2016, pages 429-443, 2016. URL: https://doi.org/10.1007/978-3-662-54110-4_30.
  29. Ronald L. Graham and Pavol Hell. On the history of the minimum spanning tree problem. IEEE Annals of the History of Computing, 7(1):43-57, 1985. URL: https://doi.org/10.1109/MAHC.1985.10011.
  30. Andrew G Haldane and Robert M May. Systemic risk in banking ecosystems. Nature, 469(7330):351-355, 2011. URL: https://doi.org/10.1038/nature09659.
  31. T. C. Hu. Optimum communication spanning trees. SIAM Journal on Computing, 3(3):188-195, 1974. URL: https://doi.org/10.1137/0203015.
  32. Matthew O Jackson. Social and economic networks. Princeton university Press, 2008. URL: https://doi.org/10.2307/j.ctvcm4gh1.
  33. Matthew O. Jackson and Asher Wolinsky. A strategic model of social and economic networks. Journal of Economic Theory, 71(1):44-74, 1996. URL: https://doi.org/10.1006/jeth.1996.0108.
  34. Tomasz Janus and Bart de Keijzer. On strong equilibria and improvement dynamics in network creation games. In WINE 2017, pages 161-176, 2017. URL: https://doi.org/10.1007/978-3-319-71924-5_12.
  35. David S. Johnson, Jan Karel Lenstra, and A. H. G. Rinnooy Kan. The complexity of the network design problem. Networks, 8(4):279-285, 1978. URL: https://doi.org/10.1002/net.3230080402.
  36. David R. Karger, Rajeev Motwani, and G. D. S. Ramkumar. On approximating the longest path in a graph. Algorithmica, 18(1):82-98, 1997. URL: https://doi.org/10.1007/BF02523689.
  37. Bernd Kawald and Pascal Lenzner. On dynamics in selfish network creation. In SPAA 2013, pages 83-92, 2013. URL: https://doi.org/10.1145/2486159.2486185.
  38. Elias Koutsoupias and Christos H. Papadimitriou. Worst-case equilibria. In STACS 1999, pages 404-413, 1999. URL: https://doi.org/10.1007/3-540-49116-3_38.
  39. Pascal Lenzner. On dynamics in basic network creation games. In SAGT 2011, pages 254-265, 2011. URL: https://doi.org/10.1007/978-3-642-24829-0_23.
  40. Pascal Lenzner. Greedy selfish network creation. In WINE 2012, pages 142-155, 2012. URL: https://doi.org/10.1007/978-3-642-35311-6_11.
  41. Thomas L Magnanti and Richard T Wong. Network design and transportation planning: Models and algorithms. Transportation science, 18(1):1-55, 1984. URL: https://doi.org/10.1287/trsc.18.1.1.
  42. 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: https://doi.org/10.1080/15427951.2015.1016248.
  43. Matúš Mihalák and Jan Christoph Schlegel. The price of anarchy in network creation games is (mostly) constant. TCS, 53(1):53-72, 2013. URL: https://doi.org/10.1007/s00224-013-9459-y.
  44. Bojan Mohar and Tomaž Pisanski. How to compute the wiener index of a graph. Journal of Mathematical Chemistry, 2(3):267-277, 1988. URL: https://doi.org/10.1007/BF01167206.
  45. Dov Monderer and Lloyd S. Shapley. Potential games. Games and Economic Behavior, 14(1):124-143, 1996. URL: https://doi.org/10.1006/game.1996.0044.
  46. Giri Narasimhan and Michiel Smid. Geometric spanner networks. Cambridge University Press, 2007. URL: https://doi.org/10.1017/CBO9780511546884.
  47. Tim Roughgarden and Éva Tardos. How bad is selfish routing? Journal of the ACM (JACM), 49(2):236-259, 2002. URL: https://doi.org/10.1145/506147.506153.
  48. Hans Wiener. Structural determination of paraffin boiling points. Journal of the American Chemical Society, 69 1:17-20, 1947. URL: https://doi.org/10.1021/ja01193a005.
  49. Kexiang Xu, Muhuo Liu, Kinkar Das, Ivan Gutman, and Boris Furtula. A survey on graphs extremal with respect to distance–based topological indices. Match (Mulheim an der Ruhr, Germany), 71:461-508, 2014. Google Scholar
  50. Ľubomír Šoltés. Transmission in graphs: A bound and vertex removing. Mathematica Slovaca, 41(1):11-16, 1991. URL: http://hdl.handle.net/10338.dmlcz/132387.
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