Efficient best response computation for strategic network formation under attack

DOI10.1007/978-3-319-66700-3_16zbMATH Open1403.91067arXiv1610.01861OpenAlexW2962779256MaRDI QIDQ681871FDOQ681871

Authors: Tobias Friedrich, Sven Ihde, Christoph W. Keßler, Pascal Lenzner, Stefan Neubert, David Schumann 

Publication date: 13 February 2018

Abstract: Inspired by real world examples, e.g. the Internet, researchers have introduced an abundance of strategic games to study natural phenomena in networks. Unfortunately, almost all of these games have the conceptual drawback of being computationally intractable, i.e. computing a best response strategy or checking if an equilibrium is reached is NP-hard. Thus, a main challenge in the field is to find tractable realistic network formation models. We address this challenge by investigating a very recently introduced model by Goyal et al. [WINE'16] which focuses on robust networks in the presence of a strong adversary who attacks (and kills) nodes in the network and lets this attack spread virus-like to neighboring nodes and their neighbors. Our main result is to establish that this natural model is one of the few exceptions which are both realistic and computationally tractable. In particular, we answer an open question of Goyal et al. by providing an efficient algorithm for computing a best response strategy, which implies that deciding whether the game has reached a Nash equilibrium can be done efficiently as well. Our algorithm essentially solves the problem of computing a minimal connection to a network which maximizes the reachability while hedging against severe attacks on the network infrastructure and may thus be of independent interest.

Full work available at URL: https://arxiv.org/abs/1610.01861

Recommendations

• Optimal attack and reinforcement of a network
• Strategic network formation with attack and immunization
• On strategic defense in stochastic networks
• Optimal attack strategy of complex networks based on tabu search
• Attack and defense strategies in complex networks based on game theory
• Optimal control of networks in the presence of attackers and defenders
• Optimal design and defense of networks under link attacks
• Optimal response to epidemics and cyber attacks in networks

zbMATH Keywords

attackbest response computationstrategic network formation

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04) Evolutionary games (91A22) Games involving graphs (91A43)

Cited In (6)

• Game-theoretic robustness of many-to-one networks
• Geometric Network Creation Games
• Strategic network formation with attack and immunization
• Quantifying network topology robustness under budget constraints: general model and computational complexity
• Social distancing network creation
• On the tree conjecture for the network creation game

This page was built for publication: Efficient best response computation for strategic network formation under attack

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q681871)