Centre for Discrete and Applicable Mathematics
	CDAM Research Report, LSE-CDAM-2001-03 August 2001

Abstract

Correlated equilibria are more general than Nash equilibria. For games in strategic form, they are also easier to compute. This no longer holds when the game is given in extensive form. We show that for an extensive two-player game with perfect recall, even without chance moves, it is computationally difficult (NP-hard) to find a correlated equilibrium with maximum payoff sum. Even with a modified definition of correlated equilibria for extensive games, NP-hardness applies to any such concept that amounts to a distribution on pure strategy profiles.

A PDF file (82 kB) with the full contents of this report can be downloaded by clicking here.

Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSE-CDAM-2001-03, together with your name and postal address to:

		CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K.
		Phone: +44(0)-20-7955 7732. Fax: +44(0)-20-7955 6877. Email: info@maths.lse.ac.uk

		Introduction to the CDAM Research Report Series.
		CDAM Homepage.

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html