Complexity Results about Nash Equilibria
Open accessThe DOI matches its OpenAlex record; 47 of the 47 references it cites were found in a registry or an index.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Equilibrium points in n -person games
Nash, J. F. (1950) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.36.1.48 · Cited by 7,560 · cited 3×
“The best known solution concept is that of Nash equilibrium [16], where the players’ strategies are such that no individual player can derive any benefit from deviating from its strategy.”
BackgroundInfluentialThe complexity of theorem-proving procedures
Cook, S. A. (1971) · Proceedings of the third annual ACM symposium on Theory of computing - STOC '71 · doi:10.1145/800157.805047 · Cited by 6,385 · cited 1×
“Satisfiability was the first problem shown to beNP-complete [10], but many other problems have been shownNP-complete since then (often by reducing satisfiability to them).”
(2015) · Adversarial Risk Analysis · doi:10.1201/b18653-3 · Cited by 3,632
The complexity of computing the permanent
Valiant, L. G. (1979) · Theoretical Computer Science · doi:10.1016/0304-3975(79)90044-6 · Cited by 2,705 · cited 1×
“Counting the number of satisfying assignments to a CNF formula is#P-hard[24].”
BackgroundShapley, L. S. (1953) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.39.10.1095 · Cited by 2,382 · cited 1×
“rategy equilibrium. A multi-stage game is typically represented as a stochastic (Markov) game, where there is an underlying set of states, and the game shifts between these states from stage to stage [45, 46, 12]. At every stage, each player’s payoff depends not only on the players’ actions, but also on the state. Furt…”
Polynomial algorithms in linear programming
Khachiyan, L. G. (1980) · USSR Computational Mathematics and Mathematical Physics · doi:10.1016/0041-5553(80)90061-0 · Cited by 1,992
Nisan, N., & Ronen, A. (2001) · Games and Economic Behavior · doi:10.1006/game.1999.0790 · Cited by 1,331
The Complexity of Markov Decision Processes
Papadimitriou, C. H., & Tsitsiklis, J. N. (1987) · Mathematics of Operations Research · doi:10.1287/moor.12.3.441 · Cited by 1,329 · cited 1×
“Papadimitriou and Tsitsiklis [41] show that computing the optimal policy (strategy) for a POMDP is PSPACE-hard even with a finite horizon.”
Equilibrium Points of Bimatrix Games
Lemke, C. E., & Howson, Jr. (1964) · Journal of the Society for Industrial and Applied Mathematics · doi:10.1137/0112033 · Cited by 1,231 · cited 1×
“The best-known algorithm for finding a Nash equilibrium, the Lemke-Howson algorithm [28], has been shown to indeed have exponential running time on some instances (and is therefore not a polynomial-time algorithm) [45].”
Algorithms, games, and the internet
Papadimitriou, C. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380883 · Cited by 1,085 · cited 1×
“rium has been dubbed “a most fundamental computational problem whose complexity is wide open” and “together with factoring, [...] the most important concrete open question on the boundary of P today” [38]. While this question remains open, important concrete advances have been made in determining the complexity of rel…”
Harsanyi, J. C. (1968) · Management Science · doi:10.1287/mnsc.14.7.486 · Cited by 1,059
Algorithm for optimal winner determination in combinatorial auctions
Sandholm, T. (2002) · Artificial Intelligence · doi:10.1016/s0004-3702(01)00159-x · Cited by 1,026
Self-citation16. Acceptable Points in General Cooperative n-Person Games
Aumann, R. J. (1959) · Contributions to the Theory of Games (AM-40), Volume IV · doi:10.1515/9781400882168-018 · Cited by 886
Word problems requiring exponential time(Preliminary Report)
Stockmeyer, L. J., & Meyer, A. R. (1973) · Proceedings of the fifth annual ACM symposium on Theory of computing - STOC '73 · doi:10.1145/800125.804029 · Cited by 871
Finite automata play the repeated prisoner's dilemma
Rubinstein, A. (1986) · Journal of Economic Theory · doi:10.1016/0022-0531(86)90021-9 · Cited by 594 · cited 1×
“formation to elicit from the players in various mechanisms [11]. Another avenue involves studying more sophisticated equilibrium notions which take into account that players have limited memory (e.g. [32, 41, 1, 14, 39]) or limited capability to solve optimization problems (e.g. [23, 24, 19, 34]). There are also open…”
Voting schemes for which it can be difficult to tell who won the election
Bartholdi, J., Tovey, C. A., & Trick, M. A. (1989) · Social Choice and Welfare · doi:10.1007/bf00303169 · Cited by 548
Graphical Models for Game Theory
Kearns, M. J., Littman, M. L., & Singh, S. P. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.2281 · Cited by 544
The computational difficulty of manipulating an election
Bartholdi, J. J., Tovey, C. A., & Trick, M. A. (1989) · Social Choice and Welfare · doi:10.1007/bf00295861 · Cited by 529 · cited 1×
“, [2, 3, 9, 44]), the complexity ofdesigningmechanisms (that lead to desirable outcomes) [10, 40], and the complexity of deciding what information toelicit from the players in various mechanisms [11].”
BackgroundPlaying large games using simple strategies
Lipton, R. J., Markakis, E., & Mehta, A. (2003) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/779928.779933 · Cited by 489 · cited 1×
“3It should be noted that this is different from the problem of computing an approximate equilibrium [12, 31], that is, a strategy profile from which individual players have only a small incentive to deviate.”
Algorithmic mechanism design (extended abstract)
Nisan, N., & Ronen, A. (1999) · Proceedings of the thirty-first annual ACM symposium on Theory of Computing · doi:10.1145/301250.301287 · Cited by 476 · cited 1×
“ch. For example, within the area of computational complexity, there are open questions regarding the complexity of executing various mechanism optimally (e.g., [4, 42, 43, 16]) or approximately (e.g. [33, 25]), the complexity of manipulating various mechanisms (e.g., [3, 2, 9, 44]), the complexity of designing mechani…”
Multi-agent influence diagrams for representing and solving games
Koller, D., & Milch, B. (2003) · Games and Economic Behavior · doi:10.1016/s0899-8256(02)00544-4 · Cited by 409
Nash and correlated equilibria: Some complexity considerations
Gilboa, I., & Zemel, E. (1989) · Games and Economic Behavior · doi:10.1016/0899-8256(89)90006-7 · Cited by 406 · cited 6×
“(Corollary 5 and weaker versions of Corollaries 2, 6 and 7 were first proven by Gilboa and Zemel [13].)”
BackgroundInfluentialSingle transferable vote resists strategic voting
Bartholdi, J. J., & Orlin, J. B. (1991) · Social Choice and Welfare · doi:10.1007/bf00183045 · Cited by 394
Bounded complexity justifies cooperation in the finitely repeated prisoners' dilemma
Neyman, A. (1985) · Economics Letters · doi:10.1016/0165-1765(85)90026-6 · Cited by 344 · cited 1×
“[1, 14, 32, 39, 41]) or limited capability to solve optimization problems (e.”
BackgroundComputationally feasible VCG mechanisms
Nisan, N., & Ronen, A. (2000) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/352871.352898 · Cited by 322
Complexity of Mechanism DesignPreprint
Conitzer, V., & Sandholm, T. (2002) · arXiv (Cornell University) · doi:10.1184/r1/6604286 · Cited by 278
Self-citationEfficient Computation of Equilibria for Extensive Two-Person Games
Koller, D., Megiddo, N., & von Stengel, B. (1996) · Games and Economic Behavior · doi:10.1006/game.1996.0051 · Cited by 228
Truth Revelation in Rapid, Approximately Efficient Combinatorial Auctions
Lehmann, D. J., O'Callaghan, L., & Shoham, Y. (n.d.) · Cited by 223
The complexity of two-person zero-sum games in extensive form
Koller, D., & Megiddo, N. (1992) · Games and Economic Behavior · doi:10.1016/0899-8256(92)90035-q · Cited by 207
Efficient Computation of Behavior Strategies
von Stengel, B. (1996) · Games and Economic Behavior · doi:10.1006/game.1996.0050 · Cited by 199 · cited 1×
“There is also a significant body of research on solving extensive-form games [18, 19, 25, 26, 34, 43, 51, 52].”
Computing equilibria for two-person gamesPreprint
von Stengel, B. (2002) · RePEc: Research Papers in Economics · Cited by 194
Designing networks for selfish users is hard
Roughgarden, T. (2001) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959923 · Cited by 123 · cited 1×
“[33, 25]), the complexity of manipulating various mechanisms (e.g., [3, 2, 9, 44]), the complexity of designing mechanisms (that lead to desirable outcomes) [10, 40 ], and the complexity of deciding what information to elicit from the players in various mechanisms [11].”
Vote Elicitation: Complexity and Strategy-ProofnessPreprint
Conitzer, V., & Sandholm, T. (2002) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0205073 · Cited by 114
Self-citationA polynomial-time nash equilibrium algorithm for repeated games
Littman, M. L., & Stone, P. (2003) · Proceedings of the 4th ACM conference on Electronic commerce · doi:10.1145/779928.779935 · Cited by 113 · cited 1×
“Finally, the complexity of best-responding, of guaranteeing payoffs, and of finding an equilibrium in repeated and sequential games has been studied in [1, 7, 11, 18, 25].”
BackgroundComplexity of Manipulating Elections with Few CandidatesPreprint
Conitzer, V., & Sandholm, T. (2002) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0205076 · Cited by 108 · cited 1×
“are open questions regarding the complexity of executing various mechanism optimally (e.g., [4, 42, 43, 16]) or approximately (e.g. [33, 25]), the complexity of manipulating various mechanisms (e.g., [3, 2, 9, 44]), the complexity of designing mechanisms (that lead to desirable outcomes) [10, 40], and the complexity o…”
Self-citationOn complexity as bounded rationality (extended abstract)
Papadimitriou, C. H., & Yannakakis, M. (1994) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/195058.195445 · Cited by 104
Leyton‐Brown, K., & Tennenholtz, M. (2003) · International Joint Conference on Artificial Intelligence · Cited by 81
A Program for Finding Nash Equilibria
Dickhaut, J. W., & Kaplan, T. R. (1993) · Springer eBooks · doi:10.1007/978-1-4757-2281-9_7 · Cited by 75 · cited 2×
“This has indirect implications for the problem of finding one Nash equilibrium: several recent algorithms for that problem operate by guessing the equilibrium supports and subsequently checking whether the guess is correct [14, 42, 44].”
Computing Nash equilibria of action-graph gamesPreprint
Bhat, N. A. R., & Leyton‐Brown, K. (2004) · arXiv (Cornell University) · doi:10.5555/1036843.1036848 · Cited by 75
The complexity of computing a best response automaton in repeated games with mixed strategies
Ben-Porath, E. (1990) · Games and Economic Behavior · doi:10.1016/0899-8256(90)90010-r · Cited by 68
Bargaining with limited computation: Deliberation equilibrium
Larson, K. S., & Sandholm, T. (2001) · Artificial Intelligence · doi:10.1016/s0004-3702(01)00132-1 · Cited by 63 · cited 1×
“[32, 41, 1, 14, 39]) or limited capability to solve optimization problems (e.g. [ 23 , 24, 19, 34]).”
Self-citationPure Nash equilibria: hard and easy games
Gottlob, G., Greco, G., & Scarcello, F. (2003) · Theoretical Aspects of Rationality and Knowledge · doi:10.1145/846241.846269 · Cited by 62 · cited 1×
“While changing the way the game is represented does not change it strategically,11 it does affect the computational complexity of solving the game [20, 46].”
On platers with a bounded number of states
Papadimitriou, C. H. (1992) · Games and Economic Behavior · doi:10.1016/0899-8256(92)90008-g · Cited by 56 · cited 2×
“Finally, the complexity of best-responding, of guaranteeing payoffs, and of finding an equilibrium in repeated and sequential games has been studied in [1, 7, 11, 18, 25].”
BackgroundThe complexity of dynamic languages and dynamic optimization problems
Orlin, J. B. (1981) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/800076.802475 · Cited by 54
The Complexity of Eliminating Dominated Strategies
Gilboa, I., Kalai, E., & Zemel, E. (1993) · Mathematics of Operations Research · doi:10.1287/moor.18.3.553 · Cited by 51 · cited 1×
“Solution concepts other than Nash equilibrium are also receiving attention: examples include CURB sets [4], (iterated) dominance [8, 16], other elimination criteria [9], and correlated equilibria [17, 40].”
Non-computable strategies and discounted repeated games
Nachbar, J. H., & Zame, W. R. (1996) · Economic Theory · doi:10.1007/bf01212014 · Cited by 47
Constructing Speculative Demand Functions in Equilibrium Markets
Sandholm, T. (1999) · Open Scholarship Institutional Repository (Washington University in St. Louis) · doi:10.7936/k7gt5kfm · Cited by 11 · cited 1×
“are open questions regarding the complexity of executing various mechanism optimally (e.g., [4, 42, 43, 16]) or approximately (e.g. [33, 25]), the complexity of manipulating various mechanisms (e.g., [3, 2, 9, 44]), the complexity of designing mechanisms (that lead to desirable outcomes) [10, 40], and the complexity o…”
Self-citation
Cited by
Multiagent systems: algorithmic, game-theoretic, and logical foundations
(2009) · Choice Reviews Online · doi:10.5860/choice.46-5662 · Cited by 1,756
The complexity of pure Nash equilibria
Fabrikant, A., Papadimitriou, C., & Talwar, K. (2004) · Proceedings of the thirty-sixth annual ACM symposium on Theory of computing · doi:10.1145/1007352.1007445 · Cited by 650
Settling the complexity of computing two-player Nash equilibria
Chen, X., Deng, X., & Teng, S.-H. (2009) · Journal of the ACM · doi:10.1145/1516512.1516516 · Cited by 560
Computing the optimal strategy to commit to
Conitzer, V., & Sandholm, T. (2006) · Proceedings of the 7th ACM conference on Electronic commerce · doi:10.1145/1134707.1134717 · Cited by 479
Self-citationThe complexity of computing a Nash equilibrium
Daskalakis, C., Goldberg, P. W., & Papadimitriou, C. H. (2006) · Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing · doi:10.1145/1132516.1132527 · Cited by 470
Metadata
- Authors
- Conitzer, V., & Sandholm, T.
- Venue
- arXiv (Cornell University)
- Publisher
- Cornell University
- Published
- 2002-05-28
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- cs/0205074
- OpenAlex
- W1807884544
- Cited by
- 223
- References
- 47
- Type
- posted content
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.