# Strategy-Stealing is Non-Constructive

arXiv: https://arxiv.org/abs/1911.06907 · HTML: https://mlsanity.com/paper/1911.06907/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Nov 2019.

## Built on by (most cited first, 1 of 1)

- [Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography](https://mlsanity.com/paper/2106.02114/) (2021)

## Abstract (arXiv)

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.