BBC Russian

Hardness of Approximation Between P and NPMay 2019

May 2019

Author:
Aviad Rubinstein
Stanford University

Publisher:

Association for Computing Machinery and Morgan & Claypool

ISBN:978-1-947487-23-9

DOI:https://doi.org/10.1145/3241304

Published:30 May 2019

Pages:

320

Appears In:

ACM Books

Purchase this Book Recommend ACM DL

ALREADY A SUBSCRIBER?SIGN IN

Bibliometrics

Abstract

Nash equilibrium is the central solution concept in Game Theory. Since Nash's original paper in 1951, it has found countless applications in modeling strategic behavior of traders in markets, (human) drivers and (electronic) routers in congested networks, nations in nuclear disarmament negotiations, and more. A decade ago, the relevance of this solution concept was called into question by computer scientists, who proved (under appropriate complexity assumptions) that computing a Nash equilibrium is an intractable problem. And if centralized, specially designed algorithms cannot find Nash equilibria, why should we expect distributed, selfish agents to converge to one? The remaining hope was that at least approximate Nash equilibria can be efficiently computed.

Understanding whether there is an efficient algorithm for approximate Nash equilibrium has been the central open problem in this field for the past decade. In this book, we provide strong evidence that even finding an approximate Nash equilibrium is intractable. We prove several intractability theorems for different settings (two-player games and many-player games) and models (computational complexity, query complexity, and communication complexity). In particular, our main result is that under a plausible and natural complexity assumption ("Exponential Time Hypothesis for PPAD"), there is no polynomial-time algorithm for finding an approximate Nash equilibrium in two-player games.

The problem of approximate Nash equilibrium in a two-player game poses a unique technical challenge: it is a member of the class PPAD, which captures the complexity of several fundamental total problems, i.e., problems that always have a solution; and it also admits a quasipolynomial time algorithm. Either property alone is believed to place this problem far below NP-hard problems in the complexity hierarchy; having both simultaneously places it just above P, at what can be called the frontier of intractability. Indeed, the tools we develop in this book to advance on this frontier are useful for proving hardness of approximation of several other important problems whose complexity lies between P and NP: Brouwer's fixed point, market equilibrium, CourseMatch (A-CEEI), densest k-subgraph, community detection, VC dimension and Littlestone dimension, and signaling in zero-sum games.

Chapters

Preface

The Frontier of Intractability

Preliminaries

Communication complexity of approximate Nash equilibrium

Brouwer's fixed point

PPAD-hardness of approximation

The generalized circuit problem

Many-player games

Bayesian Nash equilibrium

VC and Littlestone's dimensions

Signaling

2-player approximate Nash equilibrium

References

S. Aaronson, R. Impagliazzo, and D. Moshkovitz. 2014. AM with multiple merlins. In Proceedings of the IEEE Twenty-Ninth Conference on Computational Complexity, June 2014, Vancouver, British Columbia, pp. 44--55. 13, 23, 149, 180, 184, 224Google Scholar
A. V. Aho, J. D. Ullman, and M. Yannakakis. 1983. On notions of information transfer in VLSI circuits. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, April 1983, Boston, Massachusetts, pp. 133--139. 37Google Scholar
N. Alon, L. Babai, and A. Itai. 1986. A fast and simple randomized parallel algorithm for the maximal independent set problem. Journal of Algorithms, 7(4): 567--583. 29Google ScholarDigital Library
N. Alon, O. Goldreich, J. Hastad, and R. Peralta. 1992. Simple construction of almost k-wise independent random variables. Random Structures and Algorithms, 3(3): 289--304. 28Google ScholarCross Ref
N. Alon, M. Krivelevich, and B. Sudakov. 1998. Finding a large hidden clique in a random graph. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, January 1998, San Francisco, California, pp. 594--598. <457::AID-RSA14>3.0.C0;2-W. 157Google Scholar
N. Alon, A. Andoni, T. Kaufman, K. Matulef, R. Rubinfeld, and N. Xie. 2007. Testing k-wise and almost k-wise independence. In Proceedings of the 39th Annual ACM Symposium on the Theory of Computing, June 2007, San Diego, California, pp. 496--505. 157Google Scholar
N. Alon, S. Arora, R. Manokaran, D. Moshkovitz, and O. Weinstein. 2011. In approximability of densest k-subgraph from average case hardness. Unpublished manuscript. http://www.cs.tau.ac.il/-nogaa/PDFS/dks8.pdf. 156, 157Google Scholar
N. Alon, T. Lee, A. Shraibman, and S. Vempala. 2013. The approximate rank of a matrix and its algorithmic applications: Approximate rank. In Proceedings of the Symposium on Theory of Computing Conference, June 2013, Palo Alto, California, pp. 675--684. 13, 17, 223, 224Google Scholar
I. Althofer. 1994. On sparse approximations to randomized strategies and convex combinations. Linear Algebra and Its Applications, 199: 339--355. 152, 216, 224, 230, 231, 270Google ScholarCross Ref
Y. Anbalagan, S. Norin, R. Savani, and A. Vetta. 2013. Polylogarithmic supports are required for approximate well-supported nash equilibria below 2/3. In Proceedings of the Ninth International Conference on Web and Internet Economics, December 2013, Cambridge, Massachusetts, pp. 15--23. 224Google ScholarDigital Library
Y. Anbalagan, H. Huang, S. Lovett, S. Norin, A. Vetta, and H. Wu. 2015. Large supports are required for well-supported Nash equilibria. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, August 2015, Princeton, New Jersey, pp. 78--84. 224Google Scholar
A. Anshu, N. B. Goud, R. Jain, S. Kundu, and P. Mukhopadhyay. 2017. Lifting randomized query complexity to randomized communication complexity. arXiv preprint arXiv:1703.07521. 37, 40Google Scholar
S. Arora and B. Barak. 2009. Computational Complexity---A Modern Approach. Cambridge University Press. 227Google Scholar
S. Arora and S. Safra. 1998. Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM, 45(1): 70--122. 14, 155, 231Google ScholarDigital Library
S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. 1998. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3): 501--555. 14, 155Google ScholarDigital Library
S. Arora, R. Ge, S. Sachdeva, and G. Schoenebeck. 2012. Finding overlapping communities in social networks: toward a rigorous approach. In Proceedings of the ACM Conference on Electronic Commerce, June 2012, Valencia, Spain, pp. 37--54. 12, 14, 15, 177, 178, 179Google Scholar
M. Asteris, D. S. Papailiopoulos, A. Kyrillidis, and A. G. Dimakis. 2015. Sparse PCA via bipartite matchings. In Proceedings of the Twenty-Eighth International Conference on Neural Information Processing Systems, December 2015, Montreal, Quebec, pp. 766--774. http://papers.nips.cc/paper/5901-sparse-pca-via-bipartite-matchings. 13Google Scholar
R. J. Aumann. 1987. Game theory. In J. Eatwell, M. Milgate, and P. Newman, eds., The New Palgrave: A Dictionary of Economics. Palgrave Macmillan. 3Google Scholar
P. Austrin, M. Braverman, and E. Chlamtac. 2013. Inapproximability of NP-complete variants of Nash equilibrium. Theory of Computing, 9: 117--142. 224Google ScholarCross Ref
Y. Azar, R. Motwani, and J. Naor. 1998. Approximating probability distributions using small sample spaces. Combinatorica, 18(2): 151--171. 27, 28Google ScholarCross Ref
L. Babai and L. Fortnow. 1991. Arithmetization: A new method in structural complexity theory. Computational Complexity, 1: 41--66. 229Google ScholarCross Ref
L. Babai, L. Fortnow, L. A. Levin, and M. Szegedy. 1991. Checking computations in polylogarithmic time. In Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, May1 991, New Orleans, Louisiana, pp. 21--31. 231Google Scholar
Y. Babichenko. 2012. Completely uncoupled dynamics and Nash equilibria. Games and Economic Behavior, 76(1): 1--14. 18, 33, 35Google ScholarCross Ref
Y. Babichenko. 2016. Query complexity of approximate Nash equilibria. Journal of the ACM, 63(4): 36:1--36:24. 18, 34, 37, 38, 41, 43Google ScholarDigital Library
Y. Babichenko and S. Barman. 2015. Query complexity of correlated equilibrium. ACM Transactions on Economics and Computation, 3(4): 22. 39Google ScholarDigital Library
Y. Babichenko and A. Rubinstein. 2017. Communication complexity of approximate Nash equilibria. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, June 2017, Montreal, Quebec, pp. 878--889. xivGoogle Scholar
Y. Babichenko, C. H. Papadimitriou, and A. Rubinstein. 2016. Can almost everybody be almost happy? In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, January 2016, Cambridge, Massachusetts, pp. 1--9. 13, 20, 22, 35, 224, 230, 231Google ScholarDigital Library
A. Badanidiyuru, C. H. Papadimitriou, A. Rubinstein, L. Seeman, and Y. Singer. 2016. Locally adaptive optimization: Adaptive seeding for monotone submodular functions. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, January 2016, Arlington, VA, pp. 414--429. 157Google ScholarCross Ref
M. Balcan, C. Borgs, M. Braverman, J. T. Chayes, and S. Teng. 2013. Finding endogenously formed communities. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, January 2013, New Orleans, Louisiana, pp. 767--783. 15, 157, 177, 178Google ScholarCross Ref
A. S. Bandeira, N. Boumal, and V. Voroninski. 2016. On the low-rank approach for semidefinite programs arising in synchronization and community detection. In Proceedings of the Twenty-Ninth Conference on Learning Theory, June 2016, New York, pp. 361--382. http://jmlr.org/proceedings/papers/v49/bandeira16.html. 179Google Scholar
J. Banks, C. Moore, J. Neeman, and P. Netrapalli. 2016. Information-theoretic thresholds for community detection in sparse networks. In Proceedings of the Twenty-Ninth Conference on Learning Theory, June 2016, New York, pp. 383--416. http://jmlr.org/proceedings/papers/v49/banks16.html. 179Google Scholar
B. Barak. 2004. Non-Black-Box Techniques in Cryptography. PhD thesis, Weizmann Institute of Science. 6Google Scholar
B. Barak, S. B. Hopkins, J. Kelner, P. K. Kothari, A. Moitra, and A. Potechin. 2016. A nearly tight sum-of-squares lower bound for the planted clique problem. In Proceedings of the IEEE Fifty-Seventh Annual Symposium on Foundations of Computer Science, October 2016, New Brunswick, New Jersey, pp. 428--437. 157Google Scholar
S. Barman. 2015. Approximating Nash equilibria and dense bipartite subgraphs via an approximate version of Caratheodory's theorem. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, June 2015, Portland, Oregon, pp. 361--369. 12, 17, 155, 156, 157, 223, 224Google ScholarDigital Library
S. Barman, K. Ligett, and G. Piliouras. 2015. Approximating Nash equilibria in tree polymatrix games. In Algorithmic Game Theory---Eighth International Symposium, September 2015, Saarbrücken, Germany, pp. 285--296. 101Google ScholarCross Ref
R. C. Battalio, J. H. Kagel, and C. A. Kogut. 1991. Experimental confirmation of the existence of a Giffen good. The American Economic Review, 81(4): 961--970. https://www.jstor.org/stable/2006656. 9Google Scholar
C. Bazgan, F. Foucaud, and F. Sikora. 2016. On the approximability of partial VC dimension. In Proceedings of the Tenth International Conference on Combinatorial Optimization and Applications, December 2016, Hong Kong, pp. 92--106. 190Google ScholarCross Ref
P. Beame, S. A. Cook, J. Edmonds, R. Impagliazzo, and T. Pitassi. 1998. The relative complexity of NP search problems. Journal of Computer System Sciences, 57(1): 3--19 223Google ScholarDigital Library
S. Ben-David and M. Ackerman. 2008. Measures of clustering quality: A working set of axioms for clustering. In Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems, December 2018, Vancouver, British Columbia, pp. 121--128. http://papers.nips.cc/paper/3491-measures-of-clustering-quality-a-working-set-of-axioms-for-clustering. 179Google Scholar
S. Ben-David, D. Pál, and S. Shalev-Shwartz. 2009. Agnostic online learning. In Proceedings of the Twenty-Second Conference on Learning Theory, June 2009, Montreal, Quebec. http://www.cs.mcgill.ca/~colt2009/papers/032.pdf#page=1. 25Google Scholar
E. Ben-Sasson, M. Sudan, S. P. Vadhan, and A. Wigderson. 2003. Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, June 2003, San Diego, California, pp. 612--621. 28, 228, 231Google Scholar
E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan, and S. P. Vadhan. 2006. Robust PCPs of proximity, shorter PCPs, and applications to coding. SIAM Journal on Computing, 36(4): 889--974. 229, 231Google ScholarDigital Library
Q. Berthet and P. Rigollet. 2013. Complexity theoretic lower bounds for sparse principal component detection. In Proceedings of the Twenty-Sixth Annual Conference on Learning Theory, June 2013, Princeton University, New Jersey, pp. 1046--1066. https://arxiv.org/abs/1304.0828. 157Google Scholar
U. Bhaskar, Y. Cheng, Y. K. Ko, and C. Swamy. 2016. Hardness results for signaling in Bayesian zero-sum and network routing games. In Proceedings of the 2016 ACM Conference on Economics and Computation, July 2016, Maastricht, The Netherlands, pp. 479--496. 214Google ScholarDigital Library
A. Bhaskara, M. Charikar, E. Chlamtac, U. Feige, and A. Vijayaraghavan. 2010. Detecting high log-densities: An O(n^1/4) approximation for densest k-subgraph. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, June 2010, Cambridge, Massachusetts, pp. 201--210. 156Google Scholar
A. Bhaskara, M. Charikar, A. Vijayaraghavan, V. Guruswami, and Y. Zhou. 2012. Polynomial integrality gaps for strong SDP relaxations of densest k-subgraph. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, January 2012, Kyoto, Japan, pp. 388--405. http://dl.acm.org/citation.cfm?id=2095116.2095150. 156Google ScholarCross Ref
B. E. Birnbaum, N. R. Devanur, and L. Xiao. 2011. Distributed algorithms via gradient descent for fisher markets. In Proceedings of the Twelfth ACM Conference on Electronic Commerce (EC-2011), June 2011, San Jose, California, pp. 127--136. 9Google Scholar
N. Bitansky, O. Paneth, and A. Rosen. 2015. On the cryptographic hardness of finding a nash equilibrium. In Proceedings of the IEEE Fifty-Sixth Annual Symposium on Foundations of Computer Science, October 2015, Berkeley, California, pp. 1480--1498. 6Google Scholar
A. Blum. 1994. Separating distribution-free and mistake-bound learning models over the Boolean domain. SIAM Journal on Computing, 23(5): 990--1000. 190Google ScholarDigital Library
C. Borgs, J. T. Chayes, A. Marple, and S. Teng. 2016. An axiomatic approach to community detection. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, January 2016, Cambridge, Massachusetts, pp. 135--146. 14, 177, 179Google ScholarDigital Library
H. Bosse, J. Byrka, and E. Markakis. 2010. New algorithms for approximate Nash equilibria in bimatrix games. Theoretical Computer Science, 411(1): 164--173. 17, 223Google ScholarDigital Library
W. C. Brainard and H. Scarf. 2000. How to compute equilibrium prices in 1891. Cowles Foundation Discussion Papers 1272, Cowles Foundation for Research in Economics, Yale University. http://cowles.yale.edu/sites/default/files/files/pub/d12/d1272.pdf. 4Google Scholar
M. Braverman, Y. Kun-Ko, and O. Weinstein. 2015. Approximating the best Nash equilibrium in n^{O(log n)}-time breaks the exponential time hypothesis. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, January 2015, San Diego, California, pp. 970--982. 17, 150, 151, 158, 213, 224Google ScholarCross Ref
M. Braverman, Y. Kun-Ko, A. Rubinstein, and O. Weinstein. 2017. ETH hardness for densest-k-subgraph with perfect completeness. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, January 2017, Barcelona, Spain, pp. 1326--1341. xiv, 15, 23Google Scholar
G. W. Brown. 1951. Iterative solutions of games by fictitious play. In Activity Analysis of Production and Allocation. T. C. Koopmans (ed.) New York: Wiley, pp. 374--376. 4Google Scholar
E. Budish. 2011. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6): 1061--1103. 11, 131, 132, 133, 139, 140, 142, 143, 144, 145Google ScholarCross Ref
E. Budish, G. P. Cachon, J. Kessler, and A. Othman, 2014. Course Match: A large-scale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation. Working paper. 11, 131Google Scholar
C. Calabro, R. Impagliazzo, and R. Paturi. 2009. The complexity of satisfiability of small depth circuits. In Parameterized and Exact Computation, 4th International Workshop, September 2009, Copenhagen, Denmark, pp. 75--85. 224Google Scholar
M. L. Carmosino, J. Gao, R. Impagliazzo, I. Mihajlin, R. Paturi, and S. Schneider. 2016. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, January 2016, Cambridge, Massachusetts, pp. 261--270. 224Google ScholarDigital Library
S. O. Chan, D. Papailliopoulos, and A. Rubinstein. 2016. On the approximability of sparse PCA. In Proceedings of the Twenty-Ninth Conference on Learning Theory, June 2016, New York, pp. 623--646. http://jmlr.org/proceedings/papers/v49/chan16.html. 13Google Scholar
W. Chen, F. Li, T. Lin, and A. Rubinstein. 2015. Combining traditional marketing and viral marketing with amphibious influence maximization. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, June 2015, Portland, Oregon, pp. 779--796. 157Google ScholarDigital Library
X. Chen and X. Deng. 2009. On the complexity of 2D discrete fixed point problem. Theoretical Computer Science, 410(44): 4448--4456. 8Google ScholarCross Ref
X. Chen, D. Dai, Y. Du, and S.-H. Teng. 2009a. Settling the complexity of Arrow-Debreu equilibria in markets with additively separable utilities. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, October 2009, Atlanta, Georgia, pp. 273--282. 9, 117, 125Google ScholarDigital Library
X. Chen, X. Deng, and S.-H. Teng. 2009b. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM, 56(3). 4, 7, 8, 80, 83, 84, 85, 86, 88, 223Google ScholarDigital Library
X. Chen, D. Paparas, and M. Yannakakis. 2013. The complexity of non-monotone markets. In Symposium on Theory of Computing Conference, June 2013, Palo Alto, California, pp. 181--190. 9, 10, 115, 116, 117, 118, 121, 125, 127Google Scholar
X. Chen, Y. Cheng, and B. Tang. 2017. Well-supported versus approximate Nash equilibria: Query complexity of large games. https://dblp.uni-trier.de/rec/bibtex/conf/innovations/ChenCT17 18, 34, 38Google Scholar
Y. Chen, G. M. Kamath, C. Suh, and D. Tse. 2016. Community recovery in graphs with locality. In Proceedings of the Thirty-Third International Conference on Machine Learning, June 2016, New York City, pp. 689--698. http://jmlr.org/proceedings/papers/v48/chena16.html. 179Google Scholar
Y. Cheng, H. Y. Cheung, S. Dughmi, E. Emamjomeh-Zadeh, L. Han, and S. Teng. 2015. Mixture selection, mechanism design, and signaling. In Proceedings of the IEEE Fifty-Sixth Annual Symposium on Foundations of Computer Science, October 2015, Berkeley, California, pp. 1426--1445. 16, 17, 213Google Scholar
B. Codenotti, B. McCune, and K. Varadarajan. 2005. Market equilibrium via the excess demand function. In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, May 2005, New York, pp. 74--83. 9, 116Google Scholar
R. Cole and L. Fleischer. 2008. Fast-converging tâtonnement algorithms for one-time and ongoing market problems. In Proceedings of the Fortieth Annual ACM Symposium on the Theory of Computing, May 2008, Victoria, British Columbia, pp. 315--324. 9Google Scholar
V. Conitzer and T. Sandholm. 2004. Communication complexity as a lower bound for learning in games. In Proceedings of the Twenty-First International Conference on Machine Learning, July 2004, Banff, Alberta, p. 24. 35, 38Google Scholar
T. M. Cover and J. A. Thomas. 2012. Elements of Information Theory. John Wiley & Sons. 25Google Scholar
M. Cygan, M. Pilipczuk, and M. Pilipczuk. 2016. Known algorithms for edge clique cover are probably optimal. SIAM Journal on Computing, 45(1): 67--83. 224Google ScholarDigital Library
A. Czumaj, A. Deligkas, M. Fasoulakis, J. Fearnley, M. Jurdzinski, and R. Savani. 2015. Distributed methods for computing approximate equilibria. CoRR, abs/1512.03315. https://dblp.uni-trier.de/rec/bibtex/journals/algorithmica/CzumajDFFJS19. 38Google Scholar
A. Daniely. 2016. Complexity theoretic limitations on learning halfspaces. In Proceedings of the Forty-Eighth Annual ACM SIGACT Symposium on Theory of Computing, June 2016, Cambridge, Massachusetts, pp. 105--117. 190Google ScholarDigital Library
A. Daniely and S. Shalev-Shwartz. 2016. Complexity theoretic limitations on learning DNF's. In Proceedings of the Twenty-Ninth Conference on Learning Theory, June 2016, New York, pp. 815--830. http://jmlr.org/proceedings/papers/v49/daniely16.html. 190Google Scholar
C. Daskalakis. 2008. The Complexity of Nash Equilibria. PhD thesis, University of California, Berkeley. http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-107.pdf 18Google Scholar
C. Daskalakis. 2013. On the complexity of approximating a Nash equilibrium. ACM Transactions on Algorithms, 9(3): 23. 224Google ScholarDigital Library
C. Daskalakis and C. H. Papadimitriou. 2009. On oblivious PTAS's for Nash equilibrium. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, May 31-June 2, 2009, Bethesda, Maryland, pp. 75--84. Full version available at http://arxiv.org/abs/1102.2280. 17, 29, 223, 224Google Scholar
C. Daskalakis and C. H. Papadimitriou. 2015. Approximate Nash equilibria in anonymous games. J. Economic Theory, 156: 207--245. 101Google ScholarCross Ref
C. Daskalakis, A. Mehta, and C. H. Papadimitriou. 2007. Progress in approximate nash equilibria. In Proceedings of the Eighth ACM Conference on Electronic Commerce, June 2007, San Diego, California, pp. 355--358. 17, 223Google Scholar
C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou. 2009a. The complexity of computing a Nash equilibrium. SIAM Journal on Computing, 39(1): 195--259. DOI: 10.1137/ 070699652. 4, 6, 7, 8, 33, 80, 84, 85, 86, 99, 101, 102, 106, 223, 230, 269Google ScholarDigital Library
C. Daskalakis, A. Mehta, and C. H. Papadimitriou. 2009b. A note on approximate Nash equilibria. Theoretical Computer Science, 410(17): 1581--1588. 17, 223Google ScholarDigital Library
G. Debreu and K. J. Arrow. 1954. Existence of an equilibrium for a competitive economy. Econometrica, 22(3): 265--90. 9Google ScholarCross Ref
Y. Dekel, O. Gurel-Gurevich, and Y. Peres. 2010. Finding hidden cliques in linear time with high probability. CoRR, abs/1010.2997. https://dblp.org/rec/bibtex/journals/cpc/DekelGP14. 157Google Scholar
A. Deligkas, J. Fearnley, R. Savani, and P. G. Spirakis. 2017. Computing approximate Nash equilibria in polymatrix games. Algorithmica, 77(2): 487--514. 224Google ScholarDigital Library
H. Dell, T. Husfeldt, D. Marx, N. Taslaman, and M. Wahlen. 2014. Exponential time complexity of the permanent and the Tutte polynomial. ACM Transactions on Algorithms, 10(4): 21:1--21:32. 22Google ScholarDigital Library
X. Deng and Y. Du. 2008. The computation of approximate competitive equilibrium is PPAD-hard. Information Processing Letters, 108(6): 369--373. 9Google ScholarDigital Library
Y. Deshpande and A. Montanari. 2015. Improved sum-of-squares lower bounds for hidden clique and hidden submatrix problems. CoRR, abs/1502.06590. https://dblp.org/rec/bibtex/conf/colt/DeshpandeM15. 157Google Scholar
N. R. Devanur, C. H. Papadimitriou, A. Saberi, and V. V. Vazirani. Nov. 2008. Market equilibrium via a primal-dual algorithm for a convex program. Journal of the ACM, 55(5): 22:1--22:18. 9, 11Google ScholarDigital Library
I. Dinur. 2007. The PCP theorem by gap amplification. Journal of the ACM, 54(3): 12. 23Google ScholarDigital Library
I. Dinur and P. Harsha. 2013. Composition of low-error 2-query PCPs using decodable PCPs. SIAM Journal on Computing, 42(6): 2452--2486. 228Google ScholarCross Ref
S. Dughmi. 2014. On the hardness of signaling. In Proceedings of the Figty-Fifth IEEE Annual Symposium on Foundations of Computer Science, October 2014, Philadelphia, Pennsylvania, pp. 354--363. 16, 17, 213, 215Google ScholarDigital Library
S. Dughmi, N. Immorlica, and A. Roth. 2013. Constrained signaling for welfare and revenue maximization. SIGecom Exchanges, 12(1): 53--56. 16, 213Google ScholarDigital Library
F. Y. Edgeworth. 1909. Review of free trade in being. Economic Journal, 19: 104--105. 9Google ScholarCross Ref
Y. Emek, M. Feldman, I. Gamzu, R. P. Leme, and M. Tennenholtz. 2014. Signaling schemes for revenue maximization. ACM Transactions on Economics and Computing, 2(2): 5. 16, 213Google ScholarDigital Library
K. Etessami and M. Yannakakis. 2010. On the complexity of Nash equilibria and other fixed points. SIAM Journal on Computing, 39(6): 2531--2597. 7Google ScholarCross Ref
J. Fearnley, M. Gairing, P. W. Goldberg, and R. Savani. 2013. Learning equilibria of games via payoff queries. In Proceedings of the Fourteenth ACM Conference on Electronic Commerce, June 2013, Philadelphia, Pennsylvania, pp. 397--414. 18, 34Google ScholarDigital Library
T. Feder, H. Nazerzadeh, and A. Saberi. 2007. Approximating Nash equilibria using small-support strategies. In Proceedings of the Eighth ACM Conference on Electronic Commerce, June 2007, San Diego, California, pp. 352--354. 224Google Scholar
U. Feige. 2002. Relations between average case complexity and approximation complexity. In Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, Montreal Quebec, May 2002, New York, pp. 534--543. 156Google ScholarDigital Library
U. Feige and R. Krauthgamer. 2000. Finding and certifying a large hidden clique in a semirandom graph. Random Structures and Algorithms, 16(2): 195--208. <195::AID-RSA5>3.0.C0;2-A. 157Google ScholarDigital Library
U. Feige and M. Seltser. 1997. On the densest k-subgraph problem. Citeseer. DOI: 10.1.1.37.9962. 14, 155, 156Google Scholar
U. Feige, S. Goldwasser, L. Lovász, S. Safra, and M. Szegedy. 1996. Interactive proofs and the hardness of approximating cliques. Journal of the ACM (JACM), 43(2): 268--292. 14, 155, 180, 184Google ScholarDigital Library
U. Feige, G. Kortsarz, and D. Peleg. 2001. The dense k-subgraph problem. Algorithmica, 29(3): 410--421. 156Google ScholarDigital Library
J. Feigenbaum, D. Koller, and P. W. Shor. 1995. A game-theoretic classification of interactive complexity classes. In Proceedings of the Structure in Complexity Theory Conference, June 1995, Minneapolis, Minnesota, pp. 227--237. 79Google Scholar
V. Feldman, P. Gopalan, S. Khot, and A. K. Ponnuswami. 2006. New results for learning noisy parities and halfspaces. In Proceedings of the Forty-Seventh Annual IEEE Symposium on Foundations of Computer Science, October 2006, Berkeley, California, pp. 563--574. 190Google Scholar
V. Feldman, E. Grigorescu, L. Reyzin, S. Vempala, and Y. Xiao. 2013. Statistical algorithms and a lower bound for detecting planted cliques. In Symposium on Theory of Computing Conference, June 2013, Palo Alto, California, pp. 655--664. 157Google Scholar
L. Florescu and W. Perkins. 2016. Spectral thresholds in the bipartite stochastic block model. In Proceedings of the 29th Conference on Learning Theory, June 2013, New York, pp. 943--959. http://jmlr.org/proceedings/papers/v49/florescu16.html. 179Google Scholar
D. Foley. 1967. Resource allocation and the public sector. Yale Economic Essays, 7(1): 45--98. 10Google Scholar
L. Fortnow, R. Impagliazzo, V. Kabanets, and C. Umans. 2008. On the complexity of succinct zero-sum games. Computational Complexity, 17(3): 353--376. 79Google ScholarDigital Library
S. Fortunato. 2010. Community detection in graphs. Physics Reports, 486: 75--174. 14, 177Google ScholarCross Ref
D. P. Foster and H. P. Young. Sept. 2006. Regret testing: learning to play Nash equilibrium without knowing you have an opponent. Theoretical Economics, 1(3): 341--367. http://econtheory.org/ojs/index.php/te/article/view/20060341. 4, 35Google Scholar
M. Frances and A. Litman. 1998. Optimal mistake bound learning is hard. Information and Computation, 144(1): 66--82. 16, 187, 190Google ScholarDigital Library
A. Ganor and Karthik. 2017. Communication complexity of correlated equilibrium in two-player games. arXiv preprint arXiv:1704.01104. 60Google Scholar
J. Garg, R. Mehta, M. A. Sohoni, and V. V. Vazirani. 2015. A complementary pivot algorithm for market equilibrium under separable, piecewise-linear concave utilities. SIAM Journal on Computing, 44(6): 1820--1847. 9Google ScholarDigital Library
J. Garg, R. Mehta, V. V. Vazirani, and S. Yazdanbod. 2017. Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria. In Proceedings of the Forty-Ninth Annual ACM SIGACT Symposium on Theory of Computing, June 2017, Montreal, Quebec, pp. 890--901. 9Google Scholar
R. Garg and S. Kapoor. 2006. Auction algorithms for market equilibrium. Math. Oper. Res., 31(4): 714--729. 9Google ScholarDigital Library
S. Garg, O. Pandey, and A. Srinivasan. 2016. Revisiting the cryptographic hardness of finding a nash equilibrium. In Advances in Cryptology: Proceedings of the Thirty-Sixth Annual International Cryptology Conference, August 2016, Santa Barbara, California, Part II, pp. 579--604. 6Google Scholar
F. Germano and G. Lugosi. 2007. Global Nash convergence of Foster and Young's regret testing. Games and Economic Behavior, 60(1): 135--154. 35Google ScholarCross Ref
A. Ghodsi, M. Zaharia, B. Hindman, A. Konwinski, S. Shenker, and I. Stoica. 2011. Dominant resource fairness: Fair allocation of multiple resource types. In Proceedings of the Eighth USENIX Conference on Networked Systems Design and Implementation, March 30-April 1, 2011, Boston, Massachusetts, pp. 323--336. http://dl.acm.org/citation.cfm?id=1972457.1972490. 11Google Scholar
I. Gilboa and E. Zemel. 1989. Nash and correlated equilibria: Some complexity considerations. https://www.sciencedirect.com/science/article/pii/0899825689900067 150Google Scholar
P. W. Goldberg and A. Pastink. 2014. On the communication complexity of approximate Nash equilibria. Games and Economic Behavior, 85: 19--31. 38Google ScholarCross Ref
P. W. Goldberg and A. Roth. 2016. Bounds for the query complexity of approximate equilibria. ACM Transactions on Economics and Computing, 4(4): 24:1--24:25. 38, 39, 101Google ScholarDigital Library
O. Goldreich, ed. 2010. Property Testing---Current Research and Surveys [outgrowth of a workshop at the Institute for Computer Science (ITCS) at Tsinghua University, January 2010], volume 6390 of Lecture Notes in Computer Science. Springer. 228Google Scholar
M. Göös, T. Pitassi, and T. Watson. 2017. Query-to-communication lifting for BPP. 30, 37, 40Google Scholar
V. Guruswami and A. Rudra. 2005. Tolerant locally testable codes. In Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, Proceedings of the Eighth International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, and Ninth International Workshop on Randomization and Computation, August 2005, Berkeley, California, pp. 306--317. 228Google Scholar
B. E. Hajek, Y. Wu, and J. Xu. 2016. Semidefinite programs for exact recovery of a hidden community. In Proceedings of the Twenty-Ninth Conference on Learning Theory, June 2016, New York, pp. 1051--1095. http://jmlr.org/proceedings/papers/v49/hajek16.html. 179Google Scholar
S. Hart and Y. Mansour. 2010. How long to equilibrium? The communication complexity of uncoupled equilibrium procedures. Games and Economic Behavior, 69(1): 107--126. 18, 33, 34, 38, 39, 60Google ScholarCross Ref
S. Hart and A. Mas-Colell. 2003. Uncoupled dynamics do not lead to nash equilibrium. American Economic Review, 93(5): 1830--1836. DOI: 10.12571000282803322655581. 4, 33, 35Google ScholarCross Ref
S. Hart and A. Mas-Colell. 2006. Stochastic uncoupled dynamics and Nash equilibrium. Games and Economic Behavior, 57(2): 286--303. 33, 35Google ScholarCross Ref
S. Hart and A. Mas-Colell. 2013. Simple adaptive strategies: From regret-matching to uncoupled dynamics, volume 4. World Scientific. 35Google Scholar
S. Hart and N. Nisan. 2013. The query complexity of correlated equilibria. CoRR, abs/1305.4874. https://dblp.uni-trier.de/rec/bibtex/journals/geb/HartN18. 18, 34, 38, 39Google Scholar
J. Håstad. 1999. Clique is hard to approximate within n^1-∈. Acta Mathematica, 182(1): 105--142. 14, 155Google ScholarCross Ref
E. Hazan and R. Krauthgamer. 2011. How hard is it to approximate the best Nash equilibrium? SIAM Journal on Computing, 40(1): 79--91. 224Google ScholarDigital Library
M. D. Hirsch, C. H. Papadimitriou, and S. A. Vavasis. 1989. Exponential lower bounds for finding Brouwer fix points. J. Complexity, 5(4): 379--416. 37, 38, 62, 63, 65, 69, 85, 223, 225Google ScholarDigital Library
P. W. Holland, K. B. Laskey, and S. Leinhardt. 1983. Stochastic blockmodels: First steps. Social Networks, 5: 109--137. 179Google ScholarCross Ref
S. B. Hopkins, P. Kothari, A. H. Potechin, P. Raghavendra, and T. Schramm. 2016. On the integrality gap of degree-4 sum of squares for planted clique. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, January 2016, Arlington, Virginia, pp. 1079--1095. 157Google ScholarCross Ref
P. Hubácek and E. Yogev. 2017. Hardness of continuous local search: Query complexity and cryptographic lower bounds. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, January 2017, Barcelona, Spain, pp. 1352--1371. 6Google Scholar
R. Iemhoff. 2016. Intuitionism in the philosophy of mathematics. In E. N. Zalta, ed., The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University, winter 2016. 7Google Scholar
R. Impagliazzo and R. Paturi. 2001. On the complexity of k-SAT. Journal of Computer System Sciences, 62(2): 367--375. 224Google ScholarDigital Library
R. Impagliazzo, R. Paturi, and F. Zane. 2001. Which problems have strongly exponential complexity? Journal of Computer System Sciences, 63(4): 512--530. 5, 13, 17, 22, 224Google ScholarDigital Library
K. Jain. 2004. A polynomial time algorithm for computing the Arrow-Debreu market equilibrium for linear utilities. In Proceedings of the Forty-Fifth Symposium on Foundations of Computer Science, October 2004, Rome, Italy, pp. 286--294. 9Google ScholarDigital Library
K. Jain and V. V. Vazirani. 2010. Eisenberg-Gale markets: Algorithms and game-theoretic properties. Games and Economic Behavior, 70(1): 84--106. 9Google ScholarCross Ref
M. Jerrum. 1992. Large cliques elude the metropolis process. Random Struct. Algorithms, 3(4): 347--360. 157Google ScholarCross Ref
W. S. Jevons. 1866. Brief account of a general mathematical theory of political economy. History of Economic Thought Articles, 29: 282--287. http://EconPapers.repec.org/RePEc:hay:hetart:jevons1866. 8Google Scholar
A. X. Jiang and K. Leyton-Brown. 2015. Polynomial-time computation of exact correlated equilibrium in compact games. Games and Economic Behavior, 91: 347--359. 39, 60Google ScholarCross Ref
A. T. Kalai, A. R. Klivans, Y. Mansour, and R. A. Servedio. 2008. Agnostically learning halfspaces. SIAM Journal on Computing, 37(6): 1777--1805. 190Google ScholarDigital Library
E. Kalai and E. Lehrer. 1993. Rational learning leads to Nash equilibrium. Econometrica, 61(5): 1019--1045. 4, 35Google ScholarCross Ref
R. Kannan and T. Theobald. 2007. Games of fixed rank: A hierarchy of bimatrix games. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 2007, New Orleans, Louisiana, pp. 1124--1132. http://dl.acm.org/citation.cfm?id=1283383.1283504. 17, 223, 224Google Scholar
M. Karchmer, R. Raz, and A. Wigderson. 1995. Super-logarithmic depth lower bounds via the direct sum in communication complexity. Computational Complexity, 5(3-4): 191--204. 37Google ScholarCross Ref
R. M. Karp. 1972. Reducibility among combinatorial problems. In Proceedings of a Symposium on the Complexity of Computer Computations, March 1972, Yorktown Heights, New York, pp. 85--103. http://www.cs.berkeley.edu/~luca/cs172/karp.pdf. 14, 155Google ScholarCross Ref
M. Karpinski and W. Schudy. 2010. Faster algorithms for feedback arc set tournament, kemeny rank aggregation and betweenness tournament. In Algorithms and Computation: Proceedings of the Twenty-First International Symposium, December 2010, Jeju Island, Korea, Part I, pp. 3--14. 224Google ScholarCross Ref
M. Kearns. 2007. Graphical games, chapter 7, pp. 159--180. Cambridge University Press. 79Google Scholar
M. J. Kearns and L. G. Valiant. 1994. Cryptographic limitations on learning Boolean formulae and finite automata. Journal of the ACM, 41(1): 67--95. 190Google ScholarDigital Library
M. Kharitonov. 1993. Cryptographic hardness of distribution-specific learning. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 1993, San Diego, California, pp. 372--381. 190Google ScholarDigital Library
M. Kharitonov. 1995. Cryptographic lower bounds for learnability of Boolean functions on the uniform distribution. Journal of Computer System Sciences, 50(3): 600--610. 190Google ScholarDigital Library
S. Khot. 2001. Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring. In Proceedings of the Forty-Second Annual Symposium on Foundations of Computer Science, October 2001, Las Vegas, Nevada, pp. 600--609. 14, 155Google ScholarCross Ref
S. Khot. 2006. Ruling out PTAs for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM Journal on Computing, 36(4): 1025--1071. 157Google ScholarDigital Library
J. M. Kleinberg. 2002. An impossibility theorem for clustering. In Proceedings of the Advances in Neural Information Processing Systems 15, December 2002, Vancouver, British Columbia, pp. 446--453. http://papers.nips.cc/paper/2340-an-impossibility-theorem-for-clustering. 179Google Scholar
A. R. Klivans. 2016. Cryptographic hardness of learning. In Encyclopedia of Algorithms, pp. 475--477. Springer. 190Google Scholar
A. R. Klivans and A. A. Sherstov. 2009. Cryptographic hardness for learning intersections of halfspaces. Journal of Computer System Sciences, 75(1): 2--12. 190Google ScholarDigital Library
P. Koiran and A. Zouzias. 2011. On the certification of the restricted isometry property. CoRR, abs/1103.4984. http://arxiv.org/abs/1103.4984. 157Google Scholar
S. C. Kontogiannis, P. N. Panagopoulou, and P. G. Spirakis. 2009. Polynomial algorithms for approximating Nash equilibria of bimatrix games. Theoretical Computer Science, 410(17): 1599--1606. 17, 223Google ScholarDigital Library
L. Kucera. 1995. Expected complexity of graph partitioning problems. Discrete Applied Mathematics, 57(2-3): 193--212. 157Google ScholarDigital Library
F. T. Leighton. 1992. Introduction to Parallel Algorithms and Architectures: Array, Trees, Hypercubes. Morgan Kaufmann Publishers Inc. 239Google Scholar
C. E. Lemke and J. T. Howson. 1964. Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics, 12(2): 413--423. 4, 223Google ScholarCross Ref
N. Linial, Y. Mansour, and R. L. Rivest. 1991. Results on learnability and the Vapnik-Chervonenkis dimension. Information and Computation, 90(1): 33--49. 190, 191Google ScholarDigital Library
R. J. Lipton, E. Markakis, and A. Mehta. 2003. Playing large games using simple strategies. In Proceedings of the Fourth ACM Conference on Electronic Commerce, June 2003, San Diego, California, pp. 36--41. 12, 17, 36, 39, 79, 150, 223, 224Google Scholar
N. Littlestone. 1987. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2(4): 285--318. 16, 24, 25, 187Google ScholarDigital Library
D. Lokshtanov, D. Marx, and S. Saurabh. 2011. Lower bounds based on the exponential time hypothesis. Bulletin of the EATCS, 105: 41--72. http://albcom.lsi.upc.edu/ojs/index.php/beatcs/article/view/96. 224Google Scholar
K. Makarychev, Y. Makarychev, and A. Vijayaraghavan. 2016. Learning communities in the presence of errors. In Proceedings of the Twenty-Ninth Conference on Learning Theory, June 2016, New York, pp. 1258--1291. http://jmlr.org/proceedings/papers/v49/makarychev16.html. 179Google Scholar
P. Manurangsi. 2017. Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph. In Proceedings of the Forty-Ninth Annual ACM Symposium on Theory of Computing. 158, 159, 189Google ScholarDigital Library
P. Manurangsi and P. Raghavendra. 2016. A birthday repetition theorem and complexity of approximating dense CSPs. CoRR, abs/1607.02986. https://dblp.org/rec/bibtex/conf/icalp/ManurangsiR17. 189Google Scholar
P. Manurangsi and A. Rubinstein. 2017. Inapproximability of VC dimension and Littlestone's dimension. In Proceedings of the Thirtieth Conference on Learning Theory, July 2017, Amsterdam, The Netherlands, pp. 1432--1460. http://proceedings.mlr.press/v65/manurangsi17a.html. xivGoogle Scholar
A. Marshall. 1895. Principles of Economics. Number III. Macmillan. 9Google Scholar
R. R. Maxfield. 1997. General equilibrium and the theory of directed graphs. Journal of Mathematical Economics, 27(1): 23--51. 123Google ScholarCross Ref
A. McLennan and R. Tourky. 2005. From imitation games to Kakutani. Manuscript, available at http://www.econ.umn.edu/mclennan/Papers/papers.html. 37, 41Google Scholar
N. Megiddo and C. H. Papadimitriou. 1991. On total functions, existence theorems and computational complexity. Theoretical Computer Science, 81(2): 317--324. 6Google ScholarDigital Library
R. Meka, A. Potechin, and A. Wigderson. 2015. Sum-of-squares lower bounds for planted clique. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, June 2015, Portland, Oregon, pp. 87--96. 157Google Scholar
C. Menger. 1871. Principles of Economics. Ludwig von Mises Institute. 8Google Scholar
P. B. Miltersen and O. Sheffet. 2012. Send mixed signals: earn more, work less. In ACM Conference on Electronic Commerce, June 2012, Valencia, Spain, pp. 234--247. 16, 213Google Scholar
N. Mishra, R. Schreiber, I. Stanton, and R. E. Tarjan. 2008. Finding strongly knit clusters in social networks. Volume 5, pp. 155--174. https://dblp.uni-trier.de/rec/bibtex/journals/im/MishraSST08 15, 177, 178Google Scholar
A. Moitra, W. Perry, and A. S. Wein. 2016. How robust are reconstruction thresholds for community detection? In Proceedings of the Forty-Eighth Annual ACM SIGACT Symposium on Theory of Computing, June 2016, Cambridge, Massachusetts, pp. 828--841. 179Google Scholar
T. Morioka. 2003. The relative complexity of local search heuristics and the iteration principle. Electronic Colloquium on Computational Complexity (ECCC), (051). http://eccc.hpi-web.de/eccc-reports/2003/TR03-051/index.html. 6Google Scholar
D. Moshkovitz and R. Raz. 2010. Two-query PCP with subconstant error. Journal of the ACM, 57(5): 29:1--29:29. 24, 228Google ScholarDigital Library
E. Mossel and C. Umans. 2002. On the complexity of approximating the VC dimension. Journal of Computer System Sciences, 65(4): 660--671. 190Google ScholarDigital Library
E. Mossel and J. Xu. 2016. Density evolution in the degree-correlated stochastic block model. In Proceedings of the Twenty-Ninth Conference on Learning Theory, June 2016, New York, pp. 1319--1356. http://jmlr.org/proceedings/papers/v49/mossel16.html. https://dblp.uni-trier.de/rec/bibtex/conf/colt/MosselX16. 179Google Scholar
J. Nash. 1951. Non-cooperative games. The Annals of Mathematics, 54: 286--295. 3, 35Google ScholarCross Ref
N. Nisan. 2009a. Communication complexity of mixed-Nash equilibria. https://agtb.wordpress.com/2009/09/28/communication-complexity-of-mixed-nash-equilibria/. 18, 34Google Scholar
N. Nisan. 2009b. Economists and complexity. https://agtb.wordpress.com/2009/11/27/economists-and-complexity/. 9, 33Google Scholar
A. Othman, T. Sandholm, and E. Budish. 2010. Finding approximate competitive equilibria: efficient and fair course allocation. In Ninth International Conference on Autonomous Agents and Multiagent Systems, May 2010, Toronto, Canada, Volume 1--3, pp. 873--880. 11Google Scholar
A. Othman, C. H. Papadimitriou, and A. Rubinstein. 2016. The complexity of fairness through equilibrium. ACM Transactions on Economics and Computing, 4(4): 20. xivGoogle ScholarDigital Library
C. H. Papadimitriou. 1994. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer System Sciences, 48(3): 498--532. 5, 6, 143, 223Google ScholarDigital Library
C. H. Papadimitriou and T. Roughgarden. 2008. Computing correlated equilibria in multiplayer games. Journal of the ACM, 55(3), Article 14. 39, 60Google Scholar
C. H. Papadimitriou and M. Yannakakis. 1986. A note on succinct representations of graphs. Information and Control, 71(3): 181--185. 16Google ScholarDigital Library
C. H. Papadimitriou and M. Yannakakis. 1996. On limited nondeterminism and the complexity of the V-C dimension. Journal of Computer System Sciences, 53(2): 161--170. 16, 187, 190Google ScholarDigital Library
M. Parnas, D. Ron, and R. Rubinfeld. 2006. Tolerant property testing and distance approximation. Journal of Computer System Sciences, 72(6): 1012--1042. 228Google ScholarDigital Library
A. Polishchuk and D. A. Spielman. 1994. Nearly linear size holographic proofs. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, May 1994, Montreal, Quebec, pp. 194--203. 229, 231Google Scholar
P. Raghavendra and D. Steurer. 2010. Graph expansion and the unique games conjecture. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, June 2010, Cambridge, Massachusetts, pp. 755--764. 156Google Scholar
R. Raz and P. McKenzie. 1999. Separation of the monotone NC hierarchy. Combinatorica, 19(3): 403--435. 37Google ScholarDigital Library
R. Raz and A. Wigderson. 1990. Monotone circuits for matching require linear depth. In Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, May 1990, Baltimore, Maryland, pp. 287--292. 37Google Scholar
J. Robinson. 1951. An iterative method of solvinga game. Annals of Mathematics, 54: 296--301. 4Google ScholarCross Ref
T. Roughgarden. 2014. Barriers to near-optimal equilibria. In Fifty-Fifth IEEE Annual Symposium on Foundations of Computer Science, October 2014, Philadelphia, Pennsylvania, pp. 71--80. 39Google ScholarDigital Library
T. Roughgarden and O. Weinstein. 2016. On the communication complexity of approximate fixed points. In Electronic Colloquium on Computational Complexity (ECCC), volume 23, p. 55. 7, 18, 39Google Scholar
A. Rubinstein. 2015. Inapproximability of Nash equilibrium. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, June 2015, Portland, Oregon, pp. 409--418. xiv, 224Google ScholarDigital Library
A. Rubinstein. 2016. Settling the complexity of computing approximate two-player Nash equilibria. In Proceedings of the IEEE Fifty-Seventh Annual Symposium on Foundations of Computer Science, October 2016, New Brunswick, NewJersey, pp. 258--265. xiv, 41, 44Google ScholarCross Ref
A. Rubinstein. 2017a. Detecting communities is hard and counting them is even harder. https://dblp.uni-trier.de/rec/bibtex/conf/innovations/Rubinstein17. xivGoogle Scholar
A. Rubinstein. 2017b. Honest signaling in zero-sum games is hard, and lying is even harder. In Forty-Fourth International Colloquium on Automata, Languages, and Programming, July 2017, Warsaw, Poland, pp. 77:1--77:13. xiv, 214Google Scholar
A. Rubinstein. 2017c. Hardness of Approximation Between P and NP. PhD thesis, University of California at Berkeley, USA. https://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-146.pdf. xivGoogle Scholar
H. Scarf. 1967. The approximation of fixed points of a continuous mapping. SIAM Journal of Applied Mathematics, 15: 1328--1343. 4, 8Google ScholarCross Ref
M. Schaefer. 1999. Deciding the Vapnik-Červonenkis dimension is Σ^p₃-complete. Journal of Computer System Sciences, 58(1): 177--182. 190Google ScholarDigital Library
M. Schaefer. 2000. Deciding the k-dimension is PSPACE-complete. In Proceedings of the Fifteenth Annual IEEE Conference on Computational Complexity, July 2000, Florence, Italy, pp. 198--203. 190Google ScholarCross Ref
J. P. Schmidt, A. Siegel, and A. Srinivasan. 1995. Chernoff-Hoeffding bounds for applications with limited independence. SIAM J. Discrete Math., 8(2): 223--250. 27Google ScholarDigital Library
G. Schoenebeck and S. P. Vadhan. 2012. The computational complexity of Nash equilibria in concisely represented games. ACM Transactions on Computation Theory, 4(2): 4. 79Google ScholarDigital Library
A. Shamir. 1992. IP = PSPACE. Journal of the ACM, 39(4): 869--877. 229Google ScholarDigital Library
L. S. Shapley. 1964. Some topics in two-person games. Annals of Mathematical Studies, 52: 1--28. https://apps.dtic.mil/dtic/tr/fulltext/u2/407345.pdf. 4Google Scholar
E. Shmaya. 2012. Brouwer implies Nash implies Brouwer. http://theoryclass.wordpress.com/2012/01/05/brouwer-implies-nash-implies-brouwer/. 37, 41Google Scholar
S. P. Singh, V. Soni, and M. P. Wellman. 2004. Computing approximate Bayes-Nash equilibria in tree-games of incomplete information. In Proceedings of the Fifth ACM Conference on Electronic Commerce, May 2004, New York, pp. 81--90. 111Google ScholarDigital Library
D. A. Spielman. 1995. Computationally Efficient Error-Correcting Codes and Holographic Proofs. PhD thesis, Massachusetts Institute of Technology. 229, 231Google Scholar
G. J. Stigler. 1947. Notes on the history of the Giffen paradox. Journal of Political Economy, 55(2): 152--156. https://www.jstor.org/stable/1825304. 9Google ScholarCross Ref
W. Thomson and H. Varian. 1985. Theories of justice based on symmetry. Social Goals and Social Organizations: Essays in Memory of Elisha Pazner. Cambridge University Press. 10Google Scholar
N. Tremblay, G. Puy, R. Gribonval, and P. Vandergheynst. 2016. Compressive spectral clustering. In Proceedings of the Thirty-Third International Conference on Machine Learning, June 2016, New York City, pp. 1002--1011. http://jmlr.org/proceedings/papers/v48/tremblay16.html. 179Google Scholar
H. Tsaknakis and P. G. Spirakis. 2008. An optimization approach for approximate Nash equilibria. Internet Mathematics, 5(4): 365--382. 17, 223, 224Google ScholarCross Ref
T. van Laarhoven and E. Marchiori. 2014. Axioms for graph clustering quality functions. Journal of Machine Learning Research, 15(1): 193--215. http://dl.acm.org/citation.cfm?id=2627441. 179Google ScholarDigital Library
V. N. Vapnik and A. Y. Chervonenkis. 1971. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2): 264--280. 16, 24Google ScholarCross Ref
H. Varian. 1974. Equity, envy, and efficiency. Journal of Economic Theory, 9(1): 63--91. 10, 11Google ScholarCross Ref
V. V. Vazirani and M. Yannakakis. 2011. Market equilibrium under separable, piecewise-linear, concave utilities. Journal of the ACM, 58(3): 10. 9, 10, 117, 125Google ScholarDigital Library
M. Viderman. 2015. A combination of testability and decodability by tensor products. Random Struct. Algorithms, 46(3): 572--598. 245Google ScholarDigital Library
L. Walras. 1874. Éléments d'économie politique pure, ou, Théorie de la richesse sociale. L. Corbaz Lausanne. 8Google Scholar
E. B. Yanovskaya. 1968. Equilibrium points in polymatrix games. Litovskii Matematicheskii Sbornik, 8: 381--384. 79Google Scholar
H. P. Young. 2004. Strategic learning and its limits. Oxford University Press. 35Google Scholar
H. P. Young. 2009. Learning by trial and error. Games and economic behavior, 65(2): 626--643. 35Google Scholar
D. Zuckerman. 2007. Linear degree extractors and the inapproximability of Max Clique and chromatic number. Theory of Computing, 3(1): 103--128. 14, 155Google ScholarCross Ref

Cited By

Contributors

Aviad Rubinstein
Stanford University
- Publication Years2012 - 2023
- Publication counts48
- Citation count544
- Available for Download41
- Downloads (cumulative)12,330
- Downloads (12 months)1,774
- Downloads (6 weeks)172
- Average Downloads per Article301
- Average Citation per Article11
View Full Profile

Recommendations

Average-case hardness of NP from exponential worst-case hardness assumptions
STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing

A long-standing and central open question in the theory of average-case complexity is to base average-case hardness of NP on worst-case hardness of NP. A frontier question along this line is to prove that PH is hard on average if UP requires (sub-)...
Read More
On the (non) NP-hardness of computing circuit complexity
CCC '15: Proceedings of the 30th Conference on Computational Complexity

The Minimum Circuit Size Problem (MCSP) is: given the truth table of a Boolean function f and a size parameter k, is the circuit complexity of f at most k? This is the definitive problem of circuit synthesis, and it has been studied since the 1950s. ...
Read More
Hardness amplification within NP
Special issue on computational complexity 2002

In this paper we investigate the following question: if NP is slightly hard on average, is it very hard on average? We give a positive answer: if there is a function in NP which is infinitely often balanced and (1 - 1/poly(n))-hard for circuits of ...
Read More

Comments

Save to Binder

Sections

Chapters

References

Cited By

Save to Binder

Recommendations

Average-case hardness of NP from exponential worst-case hardness assumptions

On the (non) NP-hardness of computing circuit complexity

Hardness amplification within NP