On the Complexity of Computing Winning Strategies for Finite Poset Games

This paper is concerned with the complexity of computing winning strategies for poset games. While it is reasonably clear that such strategies can be computed in PSPACE, we give a simple proof of this fact by a reduction to the game of geography. We also show how to formalize the reasoning about poset games in Skelley’s theory $$\mathbf{W}_{1}^{1}$$ for PSPACE reasoning. We conclude that $$\mathbf{W}_{1}^{1}$$ can use the “strategy stealing argument” to prove that in poset games with a supremum the first player always has a winning strategy.