CaltechAUTHORS
  A Caltech Library Service

On the Complexity of Succinct Zero-Sum Games

Fortnow, Lance and Impagliazzo, Russell and Kabanets, Valentine and Umans, Christopher (2008) On the Complexity of Succinct Zero-Sum Games. Computational Complexity, 17 (3). pp. 353-376. ISSN 1016-3328. https://resolver.caltech.edu/CaltechAUTHORS:FORcc08

[img] PDF
Restricted to Caltech community only
See Usage Policy.

556Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:FORcc08

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 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} ⊆ 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.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1007/s00037-008-0252-2DOIUNSPECIFIED
Additional Information:© 2008 Springer. Manuscript received 11 October 2005. Published online: 1 October 2008. We want to thank Joe Kilian for bringing Feigenbaum et al. (1995) to our attention, and Christos Papadimitriou for answering our questions on linear programming and zero-sum games. We also thank David Zuckerman for helpful discussions, and the anonymous referees for their comments. Lance Fortnow acknowledges NEC Laboratories America where he did the research reported in this paper. Russell Impagliazzo’s research was supported by NSF Award CCR-0098197 and USA-Israel BSF Grant 97-00188. Valentine Kabanets did most of this research while at the University of California, San Diego, supported by an NSERC postdoctoral fellowship. Chris Umans’s research was supported in part by NSF grant CCF-0346991.
Funders:
Funding AgencyGrant Number
NEC Laboratories AmericaUNSPECIFIED
National Science FoundationCCR-0098197
U.S.–Israel Binational Science Foundation (BSF)97-00188
Natural Sciences and Engineering Research Council of Canada (NSERCC)UNSPECIFIED
National Science FoundationCCF-0346991
Subject Keywords:Succinct zero-sum games - approximating the value of a zero-sum game - completeness - $$S^{p}_{2}$$ - ZPP NP
Issue or Number:3
Record Number:CaltechAUTHORS:FORcc08
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:FORcc08
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:12735
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:22 Dec 2008 16:55
Last Modified:03 Oct 2019 00:31

Repository Staff Only: item control page