Haris Aziz: Wiretapping: the nucleolus of connectivity
04.12.2009 14:15
We consider the problem of maximizing the probability of hitting a strategically
chosen hidden network by placing a wiretap on a single link of a communication
network. This can be seen as a two-player win-lose game that we call the wiretap game.
We also study this problem in a cooperative
game setting. For the cooperative game we study, the spanning connectivity
game, we provide a polynomial-time algorithm for computing the nucleolus.
The nucleolus of the connectivity game corresponds to a maxmin strategy
in the wiretap game with desirable properties, for example, it minimizes the
number of pure best responses of the player choosing the hidden network.
The nucleolus of a connectivity game is also of interest as a mechanism for
cost-sharing, where those links most likely to be used in connected spanning
subgraphs are seen as most important.
(Joint work with Oded Lachish, Rahul Savani and Mike Paterson)
Artikelaktionen
abgelegt unter:
Oberseminar