Haris Aziz: Wiretapping: the nucleolus of connectivity

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.