Nash and correlated equilibria: Some complexity considerations. (English) Zbl 0755.90093
Summary: This paper deals with the complexity of computing Nash and correlated equilibria for a finite game in normal form. We examine the problems of checking the existence of equilibria satisfying a certain condition, such as “Given a game \(G\) and a number \(r\), is there a Nash (correlated) equilibrium of \(G\) in which all players obtain an expected payoff of at least \(r\)?” or “Is there a unique Nash (correlated) equilibrium in \(G\)?” etc. We show that such problems are typically “hard” (NP-hard) for Nash equilibria but “easy” (polynomial) for correlated equilibria.
MSC:
| 91A10 | Noncooperative games |
| 90C60 | Abstract computational complexity for mathematical programming problems |
References:
| [1] | Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0286.68029 |
| [2] | Aumann, R. J., Subjectivity and Correlation in Randomized Strategies, J. Math Econ., 1, 67-95 (1974) · Zbl 0297.90106 |
| [3] | Ben, Porath E., The Complexity of Computing Best Response Automata in Repeated Games with Mixed Strategies (1988), mimeo |
| [4] | Garey, N. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Will, Freeman and Company: Will, Freeman and Company New York · Zbl 0411.68039 |
| [5] | Gilboa, I., The Complexity of Computing Best Response Automata in Repeated Games, J. Econ. Theory, 45, 342-352 (1988) · Zbl 0649.90105 |
| [6] | Hart, S.; Schmeidler, D., Correlated Equilibria: An Elementary Proof of Existence (1986), mimeo |
| [7] | Megiddo, N., A Note on Complexity of P-Matrix L ⊂ P and Computing an Equilibrium (May 1988), IBM Almaden Research Center |
| [8] | Nash, J. F., Non-cooperative Games, Ann. Math., 54, 86-295 (1951) · Zbl 0045.08202 |
| [9] | Samuelson, L., Evolutionary Foundations of Solution Concepts for Finite, TwoPlayer, Normal-Form Games, (Vardi, M., Proceedings of the Second Conference on the Theoretical Aspects of Reasoning About Knowledge (1988), Morgan-Kaufman: Morgan-Kaufman Los Altos, CA), 211-225 · Zbl 0706.90104 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
