On the Value of Correlation
On the Value of Correlation
复制标题
论相关性的价值
DOI：
10.1613/jair.2588
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Moshe Tennenholtz
中科院分区：
文献类型：
--
作者：
I. Ashlagi;Dov Monderer;Moshe Tennenholtz
相关平衡（Aumann，1974）概括了NASH平衡以允许相关装置。 Aumann展示了一个游戏的示例，并且在此游戏中相关的平衡，其中代理商的盈余（预期的收益之和）在所有混合策略均衡中都大于其盈余。遵循无政府状态文献的价格发起的想法（Koutsoupias＆Papadimitriou，1999; Papadimitriou，2001），这表明研究了两项主要的措施，以实现与非阴性回报的游戏中相关性价值的研究：
1。在混合策略平衡中获得的相关平衡与最大盈余获得的最大盈余之间的比率。我们将此比率称为中介值。
2。在相关平衡中获得的最大盈余与最大盈余之间的比率。我们将该比率称为执行价值。
在这项工作中，我们启动了调解和执法值的研究，为这些概念所捕获的相关价值提供了几个一般结果。我们还为更专业的拥堵游戏案（Rosenthal，1973）展示了一系列结果，这是一类游戏，在最近的文献中受到了很多关注。
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 payoffs) 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.