Path-disruption games, recently introduced by Bachrach and Porat , are coalitional games played on graphs where one or multiple adversaries each seek to reach a given target vertex from a given source vertex and a coalition of agents seeks to prevent that from happening by blocking every path from the source to the target, for each adversary. We expand their model by allowing uncertainty about the targets. In probabilistic path-disruption games, we assign to each vertex the probability that an adversary wants to reach it. We study the complexity of various problems related to such games.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com