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 strategic-form 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 two-player 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, strategic-form correlated equilibria for two-player games without chance moves give rise to NP-hard optimization problems. Similarly, maximizing the payoff of an EFCE, or of a strategic-form correlated equilibrium, is NP-hard for two-player games with chance moves.
Extensive Form Correlated Equilibrium: Definition and Computational Complexity
VON STENGEL Bernhard, FORGES Francoise
Université de PARIS - DAUPHINE
Place du Maréchal de Lattre De Tassigny - 75775 PARIS CEDEX 16 - FRANCE
Téléphone : +33 (0)1 44-05-49-23 - fax : +33 (0)1 44-05-45-99