Computer Science – Computer Science and Game Theory
Scientific paper
2009-09-29
Computer Science
Computer Science and Game Theory
Scientific paper
We consider the problem of maximizing the probability of hitting a strategically chosen hidden virtual network by placing a wiretap on a single link of a communication network. This can be seen as a two-player win-lose (zero-sum) game that we call the wiretap game. The value of this game is the greatest probability that the wiretapper can secure for hitting the virtual network. The value is shown to equal the reciprocal of the strength of the underlying graph. We efficiently compute a unique partition of the edges of the graph, called the prime-partition, and find the set of pure strategies of the hider that are best responses against every maxmin strategy of the wiretapper. Using these special pure strategies of the hider, which we call omni-connected-spanning-subgraphs, we define a partial order on the elements of the prime-partition. From the partial order, we obtain a linear number of simple two-variable inequalities that define the maxmin-polytope, and a characterization of its extreme points. Our definition of the partial order allows us to find all equilibrium strategies of the wiretapper that minimize the number of pure best responses of the hider. Among these strategies, we efficiently compute the unique strategy that maximizes the least punishment that the hider incurs for playing a pure strategy that is not a best response. Finally, we show that this unique strategy is the nucleolus of the recently studied simple cooperative spanning connectivity game.
Aziz Haris
Lachish Oded
Paterson Mike
Savani Rahul
No associations
LandOfFree
Wiretapping a hidden network does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Wiretapping a hidden network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Wiretapping a hidden network will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-664674