Polynomial games and determinacy (Q1919550)

Extensive-form, two-player games with incomplete information are considered. Information about past moves is stored in a database and each player has access to the database. A polynomial game is a game in which, at each step, all players withdraw at most a polynomial amount of information from the database. Resource-bounded determinacy is proved for some kinds of finite, zero-sum, polynomial games whose payoff sets are computable by non-deterministic polynomial-time function-oracle Turing machines.