Bribery in Multiple-Adversary Path-Disruption Games Is Hard for the Second Level of the Polynomial Hierarchy

Path-disruption games, a class of cooperative games introduced by Bachrach and Porat [1], model situations where the players, sitting on the vertices of a given graph, try to prevent-by blocking all possible paths-their adversaries from traveling from a set of source vertices to a set of target vertices. Rey and Rothe [3] studied bribery in these games and showed that when costs are assigned to the vertices, the corresponding problem is NP-complete in the single-adversary case, and is in Σ p 2 = NP NP , the second level of the polynomial hierarchy, in the multiple-adversary case. They left open whether the latter problem is Σ p 2-complete. In this note, we solve this open question in the affirmative.