Research Article
How to Choose Communication Links in an Adversarial Environment?
@INPROCEEDINGS{10.1007/978-3-642-30373-9_17, author={Assane Gueye and Jean Walrand and Venkat Anantharam}, title={How to Choose Communication Links in an Adversarial Environment?}, proceedings={Game Theory for Networks. 2nd International ICST Conference, GAMENETS 2011, Shanghai, China, April 16-18, 2011, Revised Selected Papers}, proceedings_a={GAMENETS}, year={2012}, month={10}, keywords={Network Topology Connectivity Graph Vulnerability Spanning Trees Minimum Cut Set Game Theory Nash Equilibrium Linear Programming Blocking pairs of polyhedra}, doi={10.1007/978-3-642-30373-9_17} }- Assane Gueye
Jean Walrand
Venkat Anantharam
Year: 2012
How to Choose Communication Links in an Adversarial Environment?
GAMENETS
Springer
DOI: 10.1007/978-3-642-30373-9_17
Abstract
Given the topology of a network, characterized by an undirected graph, we consider the following game situation: a network manager is choosing (as communication infrastructure) a spanning tree of the graph, and an attacker is trying to disrupt the communication tree by attacking one link of the network. Attacking a link has a certain cost for the attacker who also has the option of not attacking. We model the interaction between the network manager and the attacker as a bimatrix game and study the set of mixed strategy Nash equilibria. We define the notion of critical subset of links and determine the structure of a particular set of Nash equilibria when the attack cost is nonzero. In each NE of this set, the attacker targets edges in critical subsets and all edges in the same critical subset are attacked with the same probability. For the game of zero cost of attack considered in [8], we characterize the set of all Nash equilibria. Some implications of the results are discussed and a detailed proof of the NE theorem is provided.