The Value of Correlation in Strategic Form Games

Every game in strategic form can be extended by adding a correlation device. Any Equilibrium in such an extended game is called a correlated equilibrium (Aumann 1974). Aumann showed that there exist games, where the agents surplus in a correlated equilibrium is greater than their surplus in every equilibrium. This suggests the study of two major measures for the value of correlation: 1. The ratio between the maximal surplus obtained in an correlated equilibrium to the maximal surplus obtained in equilibrium. We refer to this ratio as the mediation value. 2. The ratio between the optimal surplus to the maximal surplus obtained in correlated equilibrium. We refer to this ratio as the enforcement value. In this work we initiate the study of the mediation value and of the enforcement value, providing several general results on the value of correlation as captured by these concepts. We also present a set of results for the more specialized case of congestion games, a class of games that received a lot attention in the recent computer science and e-commerce communities. Indeed, while much work in computer science has been devoted to the study of the ratio between the surplus in optimal strategies to the surplus in the worst Nash equilibrium (the so called "price of anarchy") for congestion games, our work presents and initiates the study of two other complementary measures.