Itai Ashlagi

One of the most fruitful contributions to game theory has been the introduction of correlated equilibrium by Aumann. Correlated equilibrium (Aumann 1974, 1987) generalizes Nash equilibrium to allow correlation devices. Aumann showed an example of a game, and of a correlated equilibrium in this game, in which the agents' surplus (sum of payoffs) is greater than their surplus in all Nash equilibria. Following the idea initiated by the price of anarchy literature (Koutsoupias and Papadimitriou 1999, Papadimitriou 2001) this suggests the study of two major measures for the value of correlation in a game with non-negative payoffs:

1. The ratio between the maximal surplus obtained in a correlated equilibrium to the maximal surplus obtained in a Nash equilibrium. We refer to this ratio as the mediation value.
2. The ratio between the maximal surplus to the maximal surplus obtained in a correlated equilibrium. We refer to this ratio as the enforcement value.

Notice that the higher the mediation value is, the more correlation helps.

In this work we initiate the study of the mediation and enforcement values, providing several general results on the value of correlation (mediation and enforcement values) as captured by these concepts. We also present a set of results for the more specialized case of congestion games (Rosenthal 1973, Monderer and Shapley 1996), a class of games that received a lot of attention in the recent computer science and e-commerce communities.