On the Value of Correlation

DOI10.1613/JAIR.2588MaRDI QIDQ3624172zbMATH OpenOpenAlexFDO

Authors Itai Ashlagi, Dov Monderer, Moshe Tennenholtz

Publication date 28 April 2009

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1207.1362

Mathematics Subject Classification ID

Rationality and learning in game theory (91A26) Social choice (91B14) Models of societies, social and urban evolution (91D10)

Abstract: Correlated equilibrium (Aumann, 1974) 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 (expected sum of payo s) is greater than their surplus in all mixed-strategy equilibria. Following the idea initiated by the price of anarchy literature (Koutsoupias & 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 mixed-strategy 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. In this work we initiate the study of the mediation and enforcement values, 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 (Rosenthal,1973), a class of games that received a lot of attention in the recent literature.

Recommendations

• On the basic properties of correlations
• On Gebelein's correlation coefficient
• scientific article; zbMATH DE number 5558064
• On the Maximum Correlation Coefficient

Cited in

(13)

• Price of Pareto optimality in hedonic games
• Correlated equilibrium under costly disobedience
• Delegation and ambiguity in correlated equilibrium
• Exact enforcement value of soft correlated equilibrium for generalized chicken and prisoner's dilemma games
• The power of mediation in an extended El Farol game
• Computing Equilibria with Partial Commitment
• Measuring the power of soft correlated equilibrium in 2-facility simple non-increasing linear congestion games
• The last word in strong correlations
• The Earth Mover's Correlation
• On the enforcement value of soft correlated equilibrium for two-facility, non-increasing, simple linear congestion games
• scientific article; zbMATH DE number 5586156 (Why is no real title available?)
• The price of mediation
• Ranking games

This page was built for publication: On the Value of Correlation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3624172)