Haris Aziz: Wiretapping: the nucleolus of connectivity
—
abgelegt unter:
Oberseminar
04.12.2009 14:15
| Was |
|
|---|---|
| Wann |
04.12.2009 von 14:15 bis 15:45 |
| Wo | Z1.09 (neu: L109) |
| Termin übernehmen |
|
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)




