Search
 
loader loading subjects...
cover
Probabilistic Path-Disruption Games
Anja Rey, Jörg Rothe
264 - 269
10.3233/978-1-61499-096-3-264
Frontiers in Artificial Intelligence and Applications
Volume 241: STAIRS 2012
Abstract

Path-disruption games, recently introduced by Bachrach and Porat [1], 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.

Download
Creative Commons License