  In many combinatorial games, one can prove that the first player wins under
best play using a simple but non-constructive argument called
strategy-stealing. This work is about the complexity behind these proofs: how
hard is it to actually find a winning move in a game, when you know by
strategy-stealing that one exists? We prove that this problem is PSPACE-hard
already for Minimum Poset Games and Symmetric Maker-Maker Games, which are
simple classes of games that capture two of the main types of strategy-stealing
arguments in the current literature.
