This paper explores equilibrium concepts for Bayesian games, which are fundamental models of games with incomplete information. We aim at three desirable properties of equilibria. First, equilibria can be naturally realized by introducing a mediator into games. Second, an equilibrium can be computed efficiently in a distributed fashion. Third, any equilibrium in that class approximately maximizes social welfare, as measured by the price of anarchy, for a broad class of games. These three properties allow players to compute an equilibrium and realize it via a mediator, thereby settling into a stable state with approximately optimal social welfare. Our main result is the existence of an equilibrium concept that satisfies these three properties. Toward this goal, we characterize various (non-equivalent) extensions of correlated equilibria, collectively known as Bayes correlated equilibria. In particular, we focus on communication equilibria (also known as coordination mechanisms), which can be realized by a mediator who gathers each player's private information and then sends correlated recommendations to the players. We show that if each player minimizes a variant of regret called untruthful swap regret in repeated play of Bayesian games, the empirical distribution of these dynamics converges to a communication equilibrium. We present an efficient algorithm for minimizing untruthful swap regret with a sublinear upper bound, which we prove to be tight up to a multiplicative constant. As a result, by simulating the dynamics with our algorithm, we can efficiently compute an approximate communication equilibrium. Furthermore, we extend existing lower bounds on the price of anarchy based on the smoothness arguments from Bayes Nash equilibria to equilibria obtained by the proposed dynamics.


翻译:本文探讨贝叶斯博弈的均衡概念,这是不完全信息博弈的基本模型。我们旨在实现三个期望的均衡特性。首先,均衡自然可以通过引入协调者实现。其次,均衡可以被分布式地高效地计算。第三,在一个广泛的游戏类别中,任何均衡大致上都最大化社会福利,作为公理收益率的衡量标准。这三个属性允许玩家计算均衡并通过协调者实现它,从而进入一个稳定状态,具有近似最优的社会福利。我们的主要结果是存在一种均衡概念,满足这三个属性。为此,我们刻画了各种(不等价的)相关均衡扩展,统称为贝叶斯相关均衡。特别是,我们关注通信均衡(也称为协调机制),可以通过收集每个玩家的个人信息,然后向玩家发送相关的建议,使之实现。我们表明,如果每个玩家在重复博弈时最小化一种称为不诚实交换后悔的遗憾变化,这些动态的经验分布趋向于通信均衡。我们提出了一种最小化不诚实交换后悔的有效算法,其上限是次线性的,我们证明了其上限是紧凑的,到乘法常数。因此,通过使用我们的算法模拟这些动态,我们可以有效地计算近似的通信均衡。此外,我们将现有的关于基于贝叶斯-纳什均衡的光滑性论据的公理收益率下限扩展到了该文提出的动态的均衡。

0
下载
关闭预览

相关内容

【MIT Sam Hopkins】如何读论文?How to Read a Paper
专知会员服务
105+阅读 · 2022年3月20日
专知会员服务
50+阅读 · 2020年12月14日
100+篇《自监督学习(Self-Supervised Learning)》论文最新合集
专知会员服务
164+阅读 · 2020年3月18日
因果效应估计组合拳:Reweighting和Representation
PaperWeekly
0+阅读 · 2022年9月2日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
LibRec 精选:推荐系统的常用数据集
LibRec智能推荐
17+阅读 · 2019年2月15日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
LibRec 精选:推荐系统的论文与源码
LibRec智能推荐
14+阅读 · 2018年11月29日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2023年5月27日
Arxiv
0+阅读 · 2023年5月26日
Arxiv
13+阅读 · 2021年10月22日
VIP会员
相关VIP内容
【MIT Sam Hopkins】如何读论文?How to Read a Paper
专知会员服务
105+阅读 · 2022年3月20日
专知会员服务
50+阅读 · 2020年12月14日
100+篇《自监督学习(Self-Supervised Learning)》论文最新合集
专知会员服务
164+阅读 · 2020年3月18日
相关资讯
因果效应估计组合拳:Reweighting和Representation
PaperWeekly
0+阅读 · 2022年9月2日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
LibRec 精选:推荐系统的常用数据集
LibRec智能推荐
17+阅读 · 2019年2月15日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
LibRec 精选:推荐系统的论文与源码
LibRec智能推荐
14+阅读 · 2018年11月29日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
相关基金
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员