More Web Proxy on the site http://driver.im/

Article

Free access

Universal games of incomplete information

Author:

John H. ReifAuthors Info & Claims

STOC '79: Proceedings of the eleventh annual ACM symposium on Theory of computing

Pages 288 - 308

https://doi.org/10.1145/800135.804422

Published: 30 April 1979 Publication History

Abstract

We consider two-person games of incomplete information in which certain portions of positions are private to each player and cannot be viewed by the opponent. We present various games of incomplete information which are universal for all reasonable games. The problem of determining the outcome of these universal games from a given initial position is shown to be complete in doubly-exponential time. We also define “private alternating Turing machines” which are alternating Turing machines with certain tapes and portions of states private to universal states. The time and space complexity of these machines is characterized in terms of the time complexity of deterministic Turing machines, with single and double exponential jumps.

We also consider blindfold games, which are restricted games in which the second player is not allowed to modify the common position. We show various blindfold games to have exponential space complete outcome problems and to be universal for reasonable blindfold games.

We define “blind alternating Turing machines” which are private alternating Turing machines with the restriction that the universal states cannot modify the public tapes and public portion of states. A single exponential jump characterizes the relation between the space complexity of deterministic Turing machines.

References

[1]

Blaquiere, A., Ed. Topics in Differential Games, North-Holland Publishing Company, The Netherlands, 1973.

[2]

Chandra, A.K. and Stockmeyer, L.J., "Alternation," Proc. 17th IEEE Symp. on Foundations of Computer Science, 1976, pp. 98-108.

[3]

Even, S. and Tarjan, R.E., "A combinatorial problem which is complete in polynomial space", 7th Annual ACM Symp. on Theory of Computing, May, 1976, Hershey, pp. 41-49.

Digital Library

[4]

Fraenkel, A.S., Garey, M.R., Johnson, D.S., Schaefer, T. and Yesha, Y., "The complexity of checkers on an N×N board-preliminary report," Proc. 19th IEEE Symp. on Foundations of Computer Science, Oct. 1978, pp. 55-64.

[5]

Isaacs, R., Differential Games, John Wiley and Sons, Inc., New York, 1965.

[6]

Jones, N.D., "Blindfold games are harder than games with perfect information," Bulletin of the European Assoc. for Theoretical Comp. Sci., No. 6, Oct., 1978, pp. 4-7.

[7]

Jones, N.D., "Space-bounded reducibility among combinatorial problems," J. Comput. System Sci., 11 (1975), pp. 68-85.

Digital Library

[8]

Lichtenstein, D. and Sipser, M., "GO is Pspace Hard," Proc. 19th IEEE Symp. on Foundations of Computer Science, Oct. 1978, pp. 48-54.

Digital Library

[9]

von Neumann, J. and O. Morgenstern, Theory of Games and Economic Behavior, 3rd ed., Princeton University Press, 1953.

[10]

Reif, J.H., "Private and blind alternating automata," to appear.

[11]

Savitch, W.J., "Relationships between nondeterministic and deterministic tape complexities," J. Comput. Sci., 4 (1970), pp. 177-192.

Digital Library

[12]

Schaefer, T.J., "Complexity of decision problems based on finite two-person perfect-information games," Proc. 8th ACM Symp. on Theory of Computing, 1976, pp. 41-49.

Digital Library

[13]

Stockmeyer, L.J., "The polynomial-time hierarchy, IBM Research Report RC5379, 1975;" Theoretical Computer Science, to appear.

[14]

Stockmeyer, L.J. and Meyer, A.R., "Word problems requiring exponential time: preliminary report," Proc. 5th ACM Symp. on Theory of Computing, 1973, pp. 1-9.

Digital Library

[15]

Stockmeyer, L.J. and Chandra, A.K., "Provably difficult combinatorial games," IBM T.J. Watson Res. Ctr. Research Report, Yorktown Heights, Jan. 1978.

Cited By

Yan RSantos GNorman GParker DKwiatkowska M(2024)Strategy Synthesis for Zero-Sum Neuro-Symbolic Concurrent Stochastic GamesInformation and Computation10.1016/j.ic.2024.105193(105193)Online publication date: Jul-2024
https://doi.org/10.1016/j.ic.2024.105193
Raju DBakirtzis GTopcu UAgmon NAn BRicci AYeoh W(2023)Memoryless Adversaries in Imperfect Information GamesProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598940(2379-2381)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598940
Hazra TAnjaria K(2021)Analysis and applications of a bridge gameJournal of Ambient Intelligence and Humanized Computing10.1007/s12652-021-03557-314:6(7033-7045)Online publication date: 1-Nov-2021
https://doi.org/10.1007/s12652-021-03557-3
Show More Cited By

Index Terms

Universal games of incomplete information
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Models of computation
    1. Computability
      1. Turing machines

Recommendations

Repeated Games with Incomplete Information on One Side: The Case of Different Discount Factors

Two players engage in a repeated game with incomplete information on one side, where the underlying stage-games are zero-sum. In the case where players evaluate their stage-payoffs by using different discount factors, the payoffs of the infinitely ...
Solving Partial-Information Stochastic Parity Games
LICS '13: Proceedings of the 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science

We study one-sided partial-information 2-player concurrent stochastic games with parity objectives. In such a game, one of the players has only partial visibility of the state of the game, while the other player has complete knowledge. In general, such ...
Abstraction for solving large incomplete-information games
AAAI'15: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence

Most real-world games and many recreational games are games of incomplete information. Over the last dozen years, abstraction has emerged as a key enabler for solving large incomplete-information games. First, the game is abstracted to generate a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '79: Proceedings of the eleventh annual ACM symposium on Theory of computing

April 1979

364 pages

ISBN:9781450374385

DOI:10.1145/800135

Copyright © 1979 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 April 1979

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

STOC '79 Paper Acceptance Rate 37 of 111 submissions, 33%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

40
Total Citations
View Citations
203
Total Downloads

Downloads (Last 12 months)96
Downloads (Last 6 weeks)12

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yan RSantos GNorman GParker DKwiatkowska M(2024)Strategy Synthesis for Zero-Sum Neuro-Symbolic Concurrent Stochastic GamesInformation and Computation10.1016/j.ic.2024.105193(105193)Online publication date: Jul-2024
https://doi.org/10.1016/j.ic.2024.105193
Raju DBakirtzis GTopcu UAgmon NAn BRicci AYeoh W(2023)Memoryless Adversaries in Imperfect Information GamesProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598940(2379-2381)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598940
Hazra TAnjaria K(2021)Analysis and applications of a bridge gameJournal of Ambient Intelligence and Humanized Computing10.1007/s12652-021-03557-314:6(7033-7045)Online publication date: 1-Nov-2021
https://doi.org/10.1007/s12652-021-03557-3
Berthon RFijalkow NFiliot EGuha SMaubert BMurano APinault LPinchinat SRubin SSerre O(2020)Alternating Tree Automata with Qualitative SemanticsACM Transactions on Computational Logic10.1145/343186022:1(1-24)Online publication date: 17-Dec-2020
https://dl.acm.org/doi/10.1145/3431860
Coulombe MLynch J(2020)Cooperating in Video Games? Impossible! Undecidability of Team Multiplayer GamesTheoretical Computer Science10.1016/j.tcs.2020.05.028Online publication date: Jun-2020
https://doi.org/10.1016/j.tcs.2020.05.028
Hélouët LMarchand HRicker L(2018)Opacity with powerful attackersIFAC-PapersOnLine10.1016/j.ifacol.2018.06.34151:7(464-471)Online publication date: 2018
https://doi.org/10.1016/j.ifacol.2018.06.341
Bertrand NGenest BGimbert H(2017)Qualitative Determinacy and Decidability of Stochastic Games with SignalsJournal of the ACM10.1145/310792664:5(1-48)Online publication date: 15-Sep-2017
https://dl.acm.org/doi/10.1145/3107926
Ciolek DBraberman VDIppolito NPiterman NUchitel S(2017)Interaction Models and Automated Control under Partial Observable EnvironmentsIEEE Transactions on Software Engineering10.1109/TSE.2016.256495943:1(19-33)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1109/TSE.2016.2564959
Chatterjee KChmelík MTracol M(2016)What is decidable about partially observable Markov decision processes with ω-regular objectivesJournal of Computer and System Sciences10.1016/j.jcss.2016.02.00982:5(878-911)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1016/j.jcss.2016.02.009
Demirci HSay AYakaryılmaz A(2015)The Complexity of Debate CheckingTheory of Computing Systems10.1007/s00224-014-9547-757:1(36-80)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1007/s00224-014-9547-7
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents