Polynomial games and determinacy

DOI10.1016/0168-0072(95)00043-7MaRDI QIDQ1919550zbMATH OpenOpenAlexFDO

Authors Tomoyuki Yamakami

Publication date 23 July 1996

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0168-0072(95)00043-7

zbMATH Keywords

extensive-form gamepolynomial gameresource-bounded determinacyTuring machinestwo-player games with incomplete informationzero-sum game

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Determinacy principles (03E60) 2-person games (91A05) Games involving topology, set theory, or logic (91A44)

Review text

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.

Recommendations

• Computational complexity of winning strategies in two player polynomial games
• The determinacy of Blackwell games
• scientific article; zbMATH DE number 29719
• The complexity of two-player games of incomplete information
• The complexity of two-person zero-sum games in extensive form

Cites work

• A Proof of Projective Determinacy
• Category and Measure in Complexity Classes
• Complexity for type-2 relations
• Descriptive set theory
• Feasible computability and resource bounded topology
• Generic separations
• scientific article; zbMATH DE number 1555957 (Why is no real title available?)
• scientific article; zbMATH DE number 3215740 (Why is no real title available?)
• scientific article; zbMATH DE number 3078993 (Why is no real title available?)
• scientific article; zbMATH DE number 3106184 (Why is no real title available?)
• INFINITE GAMES AND ANALYTIC SETS
• P-uniform circuit complexity
• Structural properties for feasibly computable classes of type two
• The axiom of determinateness and reduction principles in the analytical hierarchy
• The complexity of two-player games of incomplete information

Cited in

(11)

• Computational complexity of winning strategies in two-person polynomial games
• Polyhedral end games for polynomial continuation
• The Shapley functional and polar forms of homogeneous polynomial games
• scientific article; zbMATH DE number 6500356 (Why is no real title available?)
• Computational complexity of winning strategies in two player polynomial games
• scientific article; zbMATH DE number 29719 (Why is no real title available?)
• The Cost of Derandomization: Computability or Competitiveness
• scientific article; zbMATH DE number 1559566 (Why is no real title available?)
• A tutorial for computer scientists on finite extensive games with perfect information
• scientific article; zbMATH DE number 6296052 (Why is no real title available?)
• The complexity of two-player games of incomplete information

This page was built for publication: Polynomial games and determinacy

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