Flipping the winner of a poset game
From MaRDI portal
Publication:763499
DOI10.1016/J.IPL.2011.09.016zbMATH Open1233.68146arXiv1111.4872OpenAlexW2021857651MaRDI QIDQ763499FDOQ763499
Authors: Adam O. Kalinich 
Publication date: 9 March 2012
Published in: Information Processing Letters (Search for Journal in Brave)
Abstract: Partially-ordered set games, also called poset games, are a class of two-player combinatorial games. The playing field consists of a set of elements, some of which are greater than other elements. Two players take turns removing an element and all elements greater than it, and whoever takes the last element wins. Examples of poset games include Nim and Chomp. We investigate the complexity of computing which player of a poset game has a winning strategy. We give an inductive procedure that modifies poset games to change the nim- value which informally captures the winning strategies in the game. For a generic poset game G, we describe an efficient method for constructing a game not G such that the first player has a winning strategy if and only if the second player has a winning strategy on G. This solves the long-standing problem of whether this construction can be done efficiently. This construction also allows us to reduce the class of Boolean formulas to poset games, establishing a lower bound on the complexity of poset games.
Full work available at URL: https://arxiv.org/abs/1111.4872
Recommendations
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 2-person games (91A05) Combinatorial games (91A46)
Cites Work
Cited In (4)
This page was built for publication: Flipping the winner of a poset game
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q763499)
