Abstract:
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 \emph{exact} value of a succinct zero-sum game by several results on \emph{approximating} the value. (1) We prove that approximating the value of a succinct zero-sum game to within an \emph{additive} factor is \emph{complete} for the class $\promise\text{-}S_2^p$, the ``promise'' version of $S_2^p$. 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~\cite{BCGKT96} and a recent result by Cai~\cite{Cai01} that $S_2^p\subseteq\ZPP^{\NP}$. (3) We observe that approximating the value of a succinct zero-sum game to within a \emph{multiplicative} factor is in $\PSPACE$, and that it \emph{cannot} be in $\promise\text{-}S_2^p$ 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-factor approximation.