Correlated Equilibrium Strategies with Multiple Independent Randomization Devices

A primitive assumption underlying Aumann (1974,1987) is that all players of a game may correlate their strategies by agreeing on a common single ’public roulette’. A natural extension of this idea is the study of strategies when the assumption of a single randomdevice common to all the players (public roulette) is dropped and (arbitrary) disjoint subsets of players forming a coalition structure are allowed to use independent randomdevices (private roulette) a la Aumann. Undermultiple independent randomdevices, the coalitionsmixed strategies forman equilibrium of the induced non-cooperative game played across the coalitions–the ’partitioned game’–when the profile of such coalitions’ strategies is a profile of correlated equilibria. These correlated equilibria which are themutual joint best responses of the coalitions are called the Nash coalitional correlated equilibria (NCCEs) of the game. The paper identifies various classes of finite and infinite games where there exists a non-empty set of NCCEs lying outside the regular correlated equilibrium distributions of the game. We notably relate the class of NCCEs to the ’coalitional equilibria’ introduced in Ray and Vohra (1997) to construct their ’Equilibrium Binding Agreements’. In a ’coalitional equilibrium’, coalitions’ best responses are defined by Pareto dominance and their existence are not guaranteed in arbitrary games without the use of correlated mixed strategies. We characterize a family of games where the existence of a non-empty set of non-trivial NCCEs is guaranteed to coincide with a subset of coalitional equilibria. Most of our results are based on the characterization of the induced non-cooperative ’partitioned game’ played across the coalitions.