Links und Funktionen

Sie sind hier: Startseite / Lehre / WS 2009/10 / Oberseminar / Haris Aziz: Wiretapping: the nucleolus of connectivity


Haris Aziz: Wiretapping: the nucleolus of connectivity

04.12.2009 14:15
Wann 14:15 15:45 04.12.2009
von bis
Wo Z1.09 (neu: L109)
Termin übernehmen vCal
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)


abgelegt unter: