Cahiers du CEREMADE 

Unité
Mixte de Recherche du C.N.R.S. N°7534 

Abstract : This paper defines the extensive form correlated equilibrium (EFCE) for extensive games with perfect recall. The EFCE concept extends the strategicform correlated equilibrium of Aumann. Before the game starts, a correlation device generates a move for each information set. This move is recommended to the player only at the time of reaching the information set. The condition of perfect recall in twoplayer extensive games without chance moves leads to strong restrictions on the playersâ€™ information sets, which are of some interest on their own. These are used to characterize the set of EFCE by means of a polynomial number of consistency and incentive constraints for correlating sequences of moves. In contrast, strategicform correlated equilibria for twoplayer games without chance moves give rise to NPhard optimization problems. Similarly, maximizing the payoff of an EFCE, or of a strategicform correlated equilibrium, is NPhard for twoplayer games with chance moves. 





200621 

22032006 

Université
de PARIS  DAUPHINE Place du Maréchal de Lattre De Tassigny  75775 PARIS CEDEX 16  FRANCE Téléphone : +33 (0)1 44054923  fax : +33 (0)1 44054599 