Probabilistic game automata

AbstractWe define a probabilistic game automaton, a general model of a two-person game. We show how this model includes as special cases the games against nature of Papadimitriou [13], the Arthur-Merlin games of Babai [1], and the interactive proof systems of Goldwasser, Micali, and Rackoff [7]. We prove a number of results about another special case, games against unknown nature, which is a generalization of games against nature. In our notation, we let UP, (UC) denote the class of two-person games with unbounded two-sided error where one player plays randomly, with partial information (complete information). Hence, the designation UC refers to games against known nature and UP refers to games against unknown nature. We show that UC-TIME(t(n))⊆ UP-TIME(t(n))⊆ UC-TIME(t2(n)), ASPACE(s(n))=UC-SPACE(s(n)) if s(n) =Ω(log n), UC-SPACE(s(n))⊆UP-SPACE(log(s(n))) if s(n) =Ω(n), where ASPACE(s(n)) is the class of languages accepted by s(n) space bounded alternating Turing machines. We assume that all the space and time bounds are deterministically constructible. All the inclusions above except one involve the simulation of one game by another. The exception is the result that UC-SPACE(s(n))⊆ASPACE(s(n)), which is shown by reducing a certain game theoretic problem to linear programming