License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-2317
URL: http://drops.dagstuhl.de/opus/volltexte/2005/231/

Ashlagi, Itai ; Monderer, Dov ; Tennenholtz, Moshe

The Value of Correlation in Strategic Form Games

pdf-format:
Dokument 1.pdf (318 KB)


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.

BibTeX - Entry

@InProceedings{ashlagi_et_al:DSP:2005:231,
  author =	{Itai Ashlagi and Dov Monderer and Moshe Tennenholtz},
  title =	{The Value of Correlation in Strategic Form Games},
  booktitle =	{Computing and Markets},
  year =	{2005},
  editor =	{Daniel Lehmann and Rudolf M{\"u}ller and Tuomas Sandholm},
  number =	{05011},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2005/231},
  annote =	{Keywords: Correlation, mediation, enforcement, equilibrium, mediator}
}

Keywords: Correlation, mediation, enforcement, equilibrium, mediator
Seminar: 05011 - Computing and Markets
Issue date: 2005
Date of publication: 29.07.2005


DROPS-Home | Fulltext Search | Imprint Published by LZI