On the Complexity of Succinct Zero-Sum Games

We study the complexity of solving succinct zero-sum games, i.e., the games whose payoff matrix M is given implicitly by a Boolean circuit C such that M(i,j) = C(i,j). We complement the known EXP-hardness of computing the exact value of a succinct zero-sum game by several results on approximating the value. (1) We prove that approximating the value of a succinct zero-sum game to within an additive error is complete for the class promise-\(S^{p}_{2}\), the “promise” version of \(S^{p}_{2}\). To the best of our knowledge, it is the first natural problem shown complete for this class. (2) We describe a ZPP ^NP algorithm for constructing approximately optimal strategies, and hence for approximating the value, of a given succinct zero-sum game. As a corollary, we obtain, in a uniform fashion, several complexity-theoretic results, e.g., a ZPP ^NP algorithm for learning circuits for SAT (Bshouty et al., JCSS, 1996) and a recent result by Cai (JCSS, 2007) that \(S^{p}_{2} \subseteq\) ZPP ^NP. (3) We observe that approximating the value of a succinct zero-sum game to within a multiplicative factor is in PSPACE, and that it cannot be in promise-\(S^{p}_{2}\) unless the polynomial-time hierarchy collapses. Thus, under a reasonable complexity-theoretic assumption, multiplicative-factor approximation of succinct zero-sum games is strictly harder than additive-error approximation.

Authors and Affiliations

1. Department of Computer Science, University of Chicago, Chicago, IL, USA

   Lance Fortnow

2. Department of Computer Science, University of California – San Diego, La Jolla, CA, USA

   Russell Impagliazzo

3. School of Computing Science, Simon Fraser University, Vancouver, BC, Canada

   Valentine Kabanets

4. Department of Computer Science, California Institute of Technology, Pasadena, CA, USA

   Christopher Umans

Corresponding author

Correspondence to Lance Fortnow.

Manuscript received 11 October 2005

Reprints and permissions