zbMATH — the first resource for mathematics

Strategic network formation with attack and immunization. (English) Zbl 1404.91055
Cai, Yang (ed.) et al., Web and internet economics. 12th international conference, WINE 2016, Montreal, Canada, December 11–14, 2016. Proceedings. Berlin: Springer (ISBN 978-3-662-54109-8/pbk; 978-3-662-54110-4/ebook). Lecture Notes in Computer Science 10123, 429-443 (2016).
Summary: Strategic network formation arises in settings where agents receive some benefit from their connectedness to other agents, but also incur costs for forming these links. We consider a new network formation game that incorporates an adversarial attack, as well as immunization or protection against the attack. An agent’s network benefit is the expected size of her connected component post-attack, and agents may also choose to immunize themselves from attack at some additional cost. Our framework can be viewed as a stylized model of settings where reachability rather than centrality is the primary interest (as in many technological networks such as the internet), and vertices may be vulnerable to attacks (such as viruses), but may also reduce risk via potentially costly measures (such as an anti-virus software).
Our main theoretical contributions include a strong bound on the edge density at equilibrium. In particular, we show that under a very mild assumption on the adversary’s attack model, every equilibrium network contains at most only \(2n-4\) edges for \(n \geq 4\), where \(n\) denotes the number of agents and this upper bound is tight. We also show that social welfare does not significantly erode: every non-trivial equilibrium with respect to several adversarial attack models asymptotically has social welfare at least as that of any equilibrium in the original attack-free model.
We complement our sharp theoretical results by a behavioral experiment on our game with over 100 participants, where despite the complexity of the game, the resulting network was surprisingly close to equilibrium.
For the entire collection see [Zbl 1352.68009].

91A43 Games involving graphs
91A90 Experimental studies
Full Text: DOI
[1] Alpcan, T., Baar, T.: Network security: a decision and game-theoretic approach, 1st edn. Cambridge University Press, Cambridge (2010) · Zbl 1209.90001 · doi:10.1017/CBO9780511760778
[2] Anderson, R.: Security engineering: a guide to building dependable distributed systems, 2nd edn. Wiley Publishing (2008)
[3] Aspnes, J., Chang, K., Yampolskiy, A.: Inoculation strategies for victims of viruses and the sum of squares partition problem. J. Comput. Syst. Sci. 72(6), 1077–1093 (2006) · Zbl 1100.68073 · doi:10.1016/j.jcss.2006.02.003
[4] Bala, V., Goyal, S.: A noncooperative model of network formation. Econometrica 68(5), 1181–1230 (2000) · Zbl 1022.91047 · doi:10.1111/1468-0262.00155
[5] Bloch, F., Jackson, M.: Definitions of equilibrium in network formation games. Int. J. Game Theo. 34(3), 305–318 (2006) · Zbl 1178.91033 · doi:10.1007/s00182-006-0022-9
[6] Blume, L., Easley, D., Kleinberg, J., Kleinberg, R., Tardos, É.: Network formation in the presence of contagious risk. In: EC, pp. 1–10 (2011) · doi:10.1145/1993574.1993576
[7] Cerdeiro, D., Dziubinski, M., Goyal, S.: Contagion risk and network design. Working Paper (2014)
[8] Cunningham, W.: Optimal attack and reinforcement of a network. J. ACM 32(3), 549–561 (1985) · Zbl 0629.90034 · doi:10.1145/3828.3829
[9] Fabrikant, A., Luthra, A., Maneva, E., Papadimitriou, C., Shenker, S.: On a network creation game. In: PODC, pp. 347–351 (2003) · Zbl 1322.91013 · doi:10.1145/872035.872088
[10] Goyal, S.: Connections: an introduction to the economics of networks. Princeton University Press, Princeton (2007) · Zbl 1138.91005
[11] Goyal, S.: Conflicts and Networks. The Oxford Handbook on the Economics of Networks (2015)
[12] Gueye, A., Walrand, J., Anantharam, V.: A network topology design game, how to choose communication links in an adversarial environment. In: GameNets (2011) · Zbl 1298.91061
[13] Ihde, S., Keßler, C., Neubert, S., Schumann, D., Lenzner, P., Friedrich, T.: Efficient best-response computation for strategic network formation under attack. CoRR abs/1610.01861 (2016) · Zbl 1403.91067
[14] Kearns, M., Ortiz, L.: Algorithms for interdependent security games. In: NIPS, pp. 561–568 (2003)
[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] Laszka, A., Szeszlér, D., Buttyán, L.: Linear loss function for the network blocking game: an efficient model for measuring network robustness and link criticality. In: Grossklags, J., Walrand, J. (eds.) GameSec 2012. LNCS, vol. 7638, pp. 152–170. Springer Berlin Heidelberg, Berlin, Heidelberg (2012). doi: 10.1007/978-3-642-34266-0_9 · Zbl 1377.68023 · doi:10.1007/978-3-642-34266-0_9
[17] Lenzner, P.: Greedy selfish network creation. In: Goldberg, P.W. (ed.) WINE 2012. LNCS, vol. 7695, pp. 142–155. Springer, Heidelberg (2012). doi: 10.1007/978-3-642-35311-6_11 · Zbl 06153226 · doi:10.1007/978-3-642-35311-6_11
[18] Roy, S., Ellis, C., Shiva, S., Dasgupta, D., Shandilya, V., Wu, Q.: A survey of game theory as applied to network security. In: HICSS, pp. 1–10 (2010) · doi:10.1109/HICSS.2010.35
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.