Bribery in multiple-adversary path-disruption games is hard for the second level of the polynomial hierarchy
Adrian Marple, Anja Rey, Jörg Rothe · Adaptive Agents and Multi-Agents Systems · 2014
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 Sigma_2^p = NP^NP, the second level of the polynomial hierarchy, in the multiple-adversary case. They left open whether the latter problem is Sigma_2^p-complete. In this note, we solve this open question in the affirmative.