Games with uniqueness properties (Q705062)

The paper deals with computational complexity of the construction of the unique winning strategy (if there exists one) in two-players games in extensive form and with complete information. The uniqueness property, which is the crucial one for the problem formulation, is classified as weak, strong and global. The main results are proved for ``reasonable'' games, whose concept is based on the polynomial definability of the game, and the authors solve the general case of the problem. It is shown that any ``reasonable'' game is extendable to a game with strong uniqueness property, and that any ``reasonable'' game with global uniqueness property is reducible to a simple game over Boolean formulas with this type of uniqueness.