Extensive-Form Correlated Equilibrium: Definition and Computational Complexity

References

• Aumann R. J. Subjectivity and correlation in randomized strategies. J. Math. Econom. (1974) 1:67–96Crossref, Google Scholar
• Aumann R. J. Correlated equilibrium as an expression of Bayesian rationality. Econometrica (1987) 55:1–18Crossref, Google Scholar
• Blair J. R. S., Mutchler D., van Lent M. Perfect recall and pruning in games with imperfect information. Comput. Intell. (1996) 12:131–154Crossref, Google Scholar
• Cho I.-K., Kreps D. M. Signaling games and stable equilibria. Quart. J. Econom. (1987) 102:179–221Crossref, Google Scholar
• Chu F., Halpern J. On the NP-completeness of finding an optimal strategy in games with common payoffs. Internat. J. Game Theory (2001) 30:99–106Crossref, Google Scholar
• Conitzer V., Sandholm T. Complexity results about Nash equilibria. Proc. 18th Internat. Joint Conf. Artificial Intelligence (IJCAI) (2003) 765–771Google Scholar
• Cotter K. D. Type correlated equilibria for games with payoff uncertainty. Econom. Theory (1994) 4:617–627Crossref, Google Scholar
• Dhillon A., Mertens J. F. Perfect correlated equilibria. J. Econom. Theory (1996) 68:279–302Crossref, Google Scholar
• Dodis Y., Halevi S., Rabin T. A cryptographic solution to a game theoretic problem. Advances in cryptology—CRYPTO 2000 (Santa Barbara, CA), Lecture Notes in Computer Science (2000) 1880(Springer-Verlag, Berlin) 112–130Crossref, Google Scholar
• Forges F. An approach to communication equilibria. Econometrica (1986) 54:1375–1385Crossref, Google Scholar
• Forges F. Correlated equilibria in repeated games with lack of information on one side: A model with verifiable types. Internat. J. Game Theory (1986) 15:65–82Crossref, Google Scholar
• Forges F. Five legitimate definitions of correlated equilibrium in games with incomplete information. Theory Decision (1993) 35:277–310Crossref, Google Scholar
• Forges F. Correlated equilibrium in games with incomplete information revisited. Theory and Decision (2006) 61:329–344Crossref, Google Scholar
• Garey M. R., Johnson D. S.Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) (W. H. Freeman, San Francisco, CA) Google Scholar
• Gerardi D. Unmediated communication in games with complete and incomplete information. J. Econom. Theory (2004) 114:104–131Crossref, Google Scholar
• Gibbons R.Game Theory for Applied Economists (1992) (Princeton University Press, Princeton, NJ) Google Scholar
• Gilboa I., Zemel E. Nash and correlated equilibria: Some complexity considerations. Games Econom. Behav. (1989) 1:80–93Crossref, Google Scholar
• Goldberg P. W., Papadimitriou C. H. Reducibility among equilibrium problems. Proc. 38th Annual ACM Sympos. Theory Comput. (STOC) (2006) 61–70Crossref, Google Scholar
• Grötschel M., Lovász L., Schrijver A.Geometric Algorithms and Combinatorial Optimization (1993) 2nd ed.(Springer-Verlag, Berlin) Crossref, Google Scholar
• Hansen K. A., Miltersen P. B., Sørensen T. B., Lin G. Finding equilibria in games of no chance. COCOON 2007. Lecture Notes in Computer Science (2007) 4598(Springer-Verlag, Berlin) 274–284Google Scholar
• Hart S., Schmeidler D. Existence of correlated equilibria. Math. Oper. Res. (1989) 14:18–25Link, Google Scholar
• Kamien M. I., Tauman Y., Zamir S. On the value of information in a strategic conflict. Games Econom. Behav. (1990) 2:129–153Crossref, Google Scholar
• Koller D., Megiddo N. The complexity of two-person zero-sum games in extensive form. Games Econom. Behav. (1992) 4:528–552Crossref, Google Scholar
• Koller D., Megiddo N., von Stengel B. Efficient computation of equilibria for extensive two-person games. Games Econom. Behav. (1996) 14:247–259Crossref, Google Scholar
• Kuhn H. W. Extensive games and the problem of information. Contributions to the Theory of Games, Vol. 2. Annals of Mathematics Studies, No. 28 (1953) (Princeton University Press, Princeton, NJ) 193–216Crossref, Google Scholar
• Lepinski M., Micali S., Peikert C., Shelat A. Completely fair SFE and coalition-safe cheap talk. Proc. 23rd Annual ACM Sympos. Principles of Distributed Comput. (2004) 1–10Crossref, Google Scholar
• Moulin H., Vial J.-P. Strategically zero-sum games: The class of games whose completely mixed equilibria cannot be improved upon. Internat. J. Game Theory (1978) 7:201–221Crossref, Google Scholar
• Myerson R. B. Multistage games with communication. Econometrica (1986) 54:323–358Crossref, Google Scholar
• Nau R. F., McCardle K. F. Coherent behavior in noncooperative games. J. Econom. Theory (1990) 50:424–444Crossref, Google Scholar
• Papadimitriou C. H.Computational Complexity (1994) (Addison-Wesley, Reading, MA) Google Scholar
• Papadimitriou C. H. Computing correlated equilibria in multi-player games. Proc. 37th Annual ACM Sympos. Theory Comput. (STOC) (2005) 49–56Crossref, Google Scholar
• Papadimitriou C. H., Roughgarden T. Computing equilibria in multi-player games. Proc. ACM-SIAM Sympos. Discrete Algorithms (SODA) (2005) 82–91Google Scholar
• Papadimitriou C. H., Roughgarden T. Computing equilibria in multi-player games. J. ACM (2008) 55Article 14Crossref, Google Scholar
• Romanovskiĭ I. V. Reduction of a game with complete memory to a matrix game. Dokl. Akad. Nauk SSSR (1962) 144:62–64English translation: Soviet Mathematics 3 678–681Google Scholar
• Samuelson L., Zhang J. Correlated equilibria and mediated equilibria in games with incomplete information. (1989) . Papers 8-89-5, Department of Economics, Pennsylvania State University, University Park, PAGoogle Scholar
• Selten R. Reexamination of the perfectness concept for equilibrium points in extensive games. Internat. J. Game Theory (1975) 4:25–55Crossref, Google Scholar
• Solan E. Characterization of correlated equilibria in stochastic games. Internat. J. Game Theory (2001) 30:259–277Crossref, Google Scholar
• Spence M. Job market signaling. Quart. J. Econom. (1973) 87:355–374Crossref, Google Scholar
• Urbano A., Vila J. E. Computational complexity and communication: Coordination in two-player games. Econometrica (2002) 70:1893–1927Crossref, Google Scholar
• von Stengel B. Efficient computation of behavior strategies. Games Econom. Behav. (1996) 14:220–246Crossref, Google Scholar
• von Stengel B. Computational complexity of correlated equilibria for extensive games. (2001) . Research Report LSE-CDAM-2001-03, London School of Economics, LondonGoogle Scholar
• von Stengel B., van den Elzen A., Talman D. Computing normal form perfect equilibria for extensive two-person games. Econometrica (2002) 70:693–715Crossref, Google Scholar
• Young H. P.Strategic Learning and Its Limits (2004) (Oxford University Press, Oxford, UK) Crossref, Google Scholar
• Zamir S., Kamien M. I., Tauman Y., Ichiishi T., Neyman A., Tauman Y. Information transmission. Game Theory and Applications (1990) (Academic Press, San Diego, CA) 273–281Crossref, Google Scholar