×

zbMATH — the first resource for mathematics

On selfish creation of robust networks. (English) Zbl 1403.91063
Gairing, Martin (ed.) et al., Algorithmic game theory. 9th international symposium, SAGT 2016, Liverpool, UK, September 19–21, 2016. Proceedings. Berlin: Springer (ISBN 978-3-662-53353-6/pbk; 978-3-662-53354-3/ebook). Lecture Notes in Computer Science 9928, 141-152 (2016).
Summary: Robustness is one of the key properties of nowadays networks. However, robustness cannot be simply enforced by design or regulation since many important networks, most prominently the internet, are not created and controlled by a central authority. Instead, internet-like networks emerge from strategic decisions of many selfish agents. Interestingly, although lacking a coordinating authority, such naturally grown networks are surprisingly robust while at the same time having desirable properties like a small diameter. To investigate this phenomenon we present the first simple model for selfish network creation which explicitly incorporates agents striving for a central position in the network while at the same time protecting themselves against random edge-failure. We show that networks in our model are diverse and we prove the versatility of our model by adapting various properties and techniques from the non-robust versions which we then use for establishing bounds on the price of anarchy. Moreover, we analyze the computational hardness of finding best possible strategies and investigate the game dynamics of our model.
For the entire collection see [Zbl 1344.91004].

MSC:
91A43 Games involving graphs
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 TEAC 2(1), 2 (2014) · Zbl 1192.91036
[2] Alon, N., Demaine, E.D., Hajiaghayi, M.T., Leighton, T.: Basic network creation games. SIAM J. Discrete Math. 27(2), 656–668 (2013) · Zbl 1273.90167 · doi:10.1137/090771478
[3] Anshelevich, E., Bhardwaj, O., Usher, M.: Friend of my friend: Network formation with two-hop benefit. Theor. Comput. Syst. 57(3), 711–752 (2015) · Zbl 1327.91059 · doi:10.1007/s00224-014-9582-4
[4] Bala, V., Goyal, S.: A noncooperative model of network formation. Econometrica 68(5), 1181–1229 (2000) · Zbl 1022.91047 · doi:10.1111/1468-0262.00155
[5] Bilò, D., Gualà, L., Proietti, G.: Bounded-distance network creation games. ACM Trans. Econ. Comput. 3(3), 16 (2015) · doi:10.1145/2770639
[6] Chauhan, A., Lenzner, P., Melnichenko, A., Münn, M.: On selfish creation of robust networks. arXiv preprint (2016). arXiv:1607.02071 · Zbl 1403.91063
[7] Corbo, J., Parkes, D.: The price of selfish behavior in bilateral network formation. In: Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, PODC 2005, pp. 99–107. ACM, New York, NY, USA (2005) · Zbl 1314.91051 · doi:10.1145/1073814.1073833
[8] Demaine, E.D., Hajiaghayi, M.T., Mahini, H., Zadimoghaddam, M.: The price of anarchy in network creation games. ACM Trans. Algorithms 8(2), 13 (2012) · Zbl 1295.68041 · doi:10.1145/2151171.2151176
[9] Ehsani, S., Fadaee, S.S., Fazli, M., Mehrabian, A., Sadeghabad, S.S., Safari, M.A., Saghafian, M.: A bounded budget network creation game. ACM Trans. Algorithms 11(4), 34 (2015) · Zbl 1398.91109 · doi:10.1145/2701615
[10] Fabrikant, A., Luthra, A., Maneva, E., Papadimitriou, C.H., Shenker, S.: On a network creation game. In: PODC 2003, pp. 347–351. ACM, New York, USA (2003) · Zbl 1322.91013 · doi:10.1145/872035.872088
[11] Flammini, M., Gallotti, V., Melideo, G., Monaco, G., Moscardelli, L.: Mobile network creation games. In: Even, G., Halldórsson, M.M. (eds.) SIROCCO 2012. LNCS, vol. 7355, pp. 159–170. Springer, Heidelberg (2012) · Zbl 06086654 · doi:10.1007/978-3-642-31104-8_14
[12] Goyal, S., Jabbari, S., Kearns, M., Khanna, S., Morgenstern, J.: Strategic network formation with attack and immunization. arXiv preprint 2015. arXiv:1511.05196 · Zbl 1404.91055
[13] Jackson, M.O., Wolinsky, A.: A strategic model of social and economic networks. J. Econ. Theor. 71(1), 44–74 (1996) · Zbl 0871.90144 · doi:10.1006/jeth.1996.0108
[14] Kawald, B., Lenzner, P.: On dynamics in selfish network creation. In: SPAA 2013, pp. 83–92. ACM, New York, NY, USA (2013) · doi:10.1145/2486159.2486185
[15] Kliemann, L.: The price of anarchy for network formation in an adversary model. Games 2(3), 302–332 (2011) · Zbl 1311.91058 · doi:10.3390/g2030302
[16] Kliemann, L.: The price of anarchy in bilateral network formation in an adversary model. arXiv preprint (2013). arXiv:1308.1832 · Zbl 1411.91143
[17] Lenzner, P.: Greedy selfish network creation. In: Goldberg, P.W. (ed.) WINE 2012. LNCS, vol. 7695, pp. 142–155. Springer, Heidelberg (2012) · Zbl 06153226 · doi:10.1007/978-3-642-35311-6_11
[18] Meirom, E.A., Mannor, S., Orda, A.: Network formation games with heterogeneous players and the internet structure. In: Proceedings of the 15th ACM Conference on Economics and Computation, pp. 735–752. ACM (2014) · doi:10.1145/2600057.2602862
[19] Meirom, E.A., Mannor, S., Orda, A.: Formation games of reliable networks. In: INFOCOM 2015, pp. 1760–1768. IEEE (2015) · doi:10.1109/INFOCOM.2015.7218557
[20] Mihalák, M., Schlegel, J.C.: The price of anarchy in network creation games Is (Mostly) constant. In: Kontogiannis, S., Koutsoupias, E., Spirakis, P.G. (eds.) SAGT 2010. LNCS, vol. 6386, pp. 276–287. Springer, Heidelberg (2010) · Zbl 1310.91045 · doi:10.1007/978-3-642-16170-4_24
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.