|M.Sc Student||Itai Ashlagi|
|Subject||On the Value of Correlation|
|Department||Department of Industrial Engineering and Management||Supervisors||Full Professor Tennenholtz Moshe|
|Professor Emeritus Monderer Dov|
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:
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.