Games with uniqueness properties

DOI10.1007/S00224-003-1105-7MaRDI QIDQ705062zbMATH OpenOpenAlexFDO

Authors Shin Aida, Marcel Crasmaru, Osamu Watanabe, Kenneth W. Regan

Publication date 25 January 2005

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-003-1105-7

computational complexity game in extensive form game on graph perfect information in game position uniqueness property in game winning strategy

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Games involving graphs (91A43)

Review text

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.

Recommendations

Cited in

(3)

This page was built for publication: Games with uniqueness properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q705062)