Decision Algorithms for Multiplayer Games of Incomplete Information.

Abstract

This paper provides algorithms for deciding the outcome for various classes of multilayer games of incomplete information. The classes of games which our algorithms are applicable include games not previously known decidable; furthermore, many of our algorithms have asymptotically optimal complexity. We apply our algorithms to provide alternative proofs of upper bounds, and new time-space tradeoffs on the complexity of multilayer alternating machines.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1981
Accession Number
ADA114334

Entities

People

  • Gary Peterson
  • John Reif

Organizations

  • Harvard University

Tags

Communities of Interest

  • Human Systems

DTIC Thesaurus Topics

  • Algorithms
  • Automata
  • Computational Complexity
  • Computations
  • Computer Science
  • Computers
  • Construction
  • Contracts
  • Finite Alphabet
  • Language
  • Machines
  • Military Research
  • Natural Languages
  • Probability
  • Sequences
  • Theoretical Computer Science
  • Universities

Fields of Study

  • Computer science

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Game Theory.
  • Mathematical Modeling and Probability Theory.

Technology Areas

  • Space