An Essay on Sabotage and Obstruction
Johan van Benthem

Abstract:
We investigate the complexity jump which occurs when an algorithm of
known complexity is turned into a game by adding an opposing
player. Our specific examples are reachability and circuit algorithms,
which now have a Demon trying to prevent successful completion. We get
a PSPACE upper bound by translating the problems into first-order
model checking tasks on finite models.  Finally, we consider general
jumps in coalitional powers when we add players to a game.