The Price of Anarchy in Auctions
The Price of Anarchy in Auctions
复制标题
拍卖中无政府状态的代价
DOI：
10.1613/jair.5272
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
É. Tardos
中科院分区：
文献类型：
--
作者：
Tim Roughgarden;Vasilis Syrgkanis;É. Tardos
这项调查概述了一种通用的模块化理论，用于证明近似值保证了复杂环境中拍卖的平衡。该理论补充了传统的经济技术，这些技术通常集中在精确和最佳的解决方案上，因此仅限于相对风格化的设置。
我们重点介绍了三种用户友好的分析工具：平滑度类型的不平等现象，在完整信息和确定性策略的特殊情况下，立即为许多感兴趣的拍卖格式提供了近似保证；扩展定理将此类保证扩展到随机策略，无需重新学习成果和不完整的信息设置；和组成定理，将这种保证从更简单的拍卖扩展到更复杂的拍卖。结合这些工具可产生严格的最差近似值，可确保许多广泛使用的拍卖格式的平衡。
This survey outlines a general and modular theory for proving approximation guarantees for equilibria of auctions in complex settings. This theory complements traditional economic techniques, which generally focus on exact and optimal solutions and are accordingly limited to relatively stylized settings.
We highlight three user-friendly analytical tools: smoothness-type inequalities, which immediately yield approximation guarantees for many auction formats of interest in the special case of complete information and deterministic strategies; extension theorems, which extend such guarantees to randomized strategies, no-regret learning outcomes, and incomplete-information settings; and composition theorems, which extend such guarantees from simpler to more complex auctions. Combining these tools yields tight worst-case approximation guarantees for the equilibria of many widely-used auction formats.
DOI：
10.1145/2847520
发表时间：
2013-12
期刊：
ACM Trans. Economics and Comput.
影响因子：
--
作者：
G. Christodoulou;Annamária Kovács;A. Sgouritsa;Bo Tang
通讯作者：
G. Christodoulou;Annamária Kovács;A. Sgouritsa;Bo Tang
影响因子：
0.5
作者：
Christodoulou G
通讯作者：
Christodoulou G