Provided by: Budapest University of Technology and Economics
Date Added: Apr 2012
In this paper, the authors study the robustness of networks that are characterized by many-to-one communications (e.g., access networks and sensor networks) in a game-theoretic model. More specifically, they model the interactions between a network operator and an adversary as a two player zero-sum game, where the network operator chooses a spanning tree in the network, the adversary chooses an edge to be removed from the network, and the adversary's payoff is proportional to the number of nodes that can no longer reach a designated node through the spanning tree. They show that the payoff in every Nash equilibrium of the game is equal to the reciprocal of the persistence of the network.