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-Complete 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.
@InProceedings{bodwin_et_al:LIPIcs.ITCS.2020.21, author = {Bodwin, Greg and Grossman, Ofer}, title = {{Strategy-Stealing Is Non-Constructive}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {21:1--21:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.21}, URN = {urn:nbn:de:0030-drops-117069}, doi = {10.4230/LIPIcs.ITCS.2020.21}, annote = {Keywords: PSPACE-hard, Hex, Combinatorial Game Theory} }
Feedback for Dagstuhl Publishing