Polynomial games and determinacy (Q1919550)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Polynomial games and determinacy |
scientific article |
Statements
Polynomial games and determinacy (English)
0 references
23 July 1996
0 references
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.
0 references
extensive-form game
0 references
zero-sum game
0 references
resource-bounded determinacy
0 references
two-player games with incomplete information
0 references
polynomial game
0 references
Turing machines
0 references