Search Results

Documents authored by Monderer, Dov


Document
The Value of Correlation in Strategic Form Games

Authors: Itai Ashlagi, Dov Monderer, and Moshe Tennenholtz

Published in: Dagstuhl Seminar Proceedings, Volume 5011, Computing and Markets (2005)


Abstract
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.

Cite as

Itai Ashlagi, Dov Monderer, and Moshe Tennenholtz. The Value of Correlation in Strategic Form Games. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{ashlagi_et_al:DagSemProc.05011.20,
  author =	{Ashlagi, Itai and Monderer, Dov and Tennenholtz, Moshe},
  title =	{{The Value of Correlation in Strategic Form Games}},
  booktitle =	{Computing and Markets},
  pages =	{1--29},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5011},
  editor =	{Daniel Lehmann and Rudolf M\"{u}ller and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.20},
  URN =		{urn:nbn:de:0030-drops-2317},
  doi =		{10.4230/DagSemProc.05011.20},
  annote =	{Keywords: Correlation, mediation, enforcement, equilibrium, mediator}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail