Games with Uniqueness Properties

For two-player games of perfect information such as Checkers, Chess, and Go we introduce "uniqueness" properties. A game position has a uniqueness property if a winning strategy - should one exist - is forced to be unique. Depending on the way that winning strategy is forced, a uniqueness property is classified as weak, strong, or global. We prove that any reasonable two-player game G is extendable to a game G* with the strong uniqueness property for both players, so that, e.g., QBF remains PSPACE-complete under this reduction. For global uniqueness, we introduce a simple game over Boolean formulas with this property, and prove that any reasonable two-player game with the global uniqueness property is reducible to it. We show that the class of languages that reduce to globally unique games equals Niedermeier and Rossmanith's unambiguous alternation class UAP [NR], which is in an interesting region between FewP and SPP.