Date: April, 29th, 11h30
Place: Room Rotule NO8 – ULB Bruxelles
Abstract: We study combinatorial games arising from removing arcs from a network, to disconnect two distinguished nodes s and t. First we study a two-person zero-sum game where one player, the attacker, chooses every few minutes a set of arcs that intercepts every path from s to t, then a second player, the inspector, chooses every few minutes an arc to inspect trying to find the attacker. We give polynomial algorithms to find optimal strategies for both players.
Then we study a cooperative game where a coalitions corresponds to sets of arcs, and the value of a coalition S is the maximum number of disjoint st-cuts included in S. This is the number of independent ways that a coalition can use to disconnect s and t. We give polynomial algorithms for testing membership to the core and for computing the nucleolus. And if we have time, we study disruption games, where a coalition wins if it disconnects s and t. We give a polynomial combinato- rial algorithms for finding the least-core and for computing the nucleolus of the least-core.
