We consider the problem of computing a (pure) Bayes-Nash equilibrium in the first-price auction with continuous value distributions and discrete bidding space. We prove that when bidders have independent subjective prior beliefs about the value distributions of the other bidders, computing an $\varepsilon$-equilibrium of the auction is PPAD-complete, and computing an exact equilibrium is FIXP-complete.


翻译:我们考虑了在第一次价格拍卖中计算(纯)巴耶斯-纳什平衡的问题,第一次价格拍卖有连续的价值分配和离散的投标空间。 我们证明,当投标人对其他投标人的价值分配有独立主观的先入为主的信念时,计算拍卖的美元(varepsilon$-equiquiblium)是完整的PPAD,计算准确的平衡是完整的FIXP。

0
下载
关闭预览

相关内容

让 iOS 8 和 OS X Yosemite 无缝切换的一个新特性。 > Apple products have always been designed to work together beautifully. But now they may really surprise you. With iOS 8 and OS X Yosemite, you’ll be able to do more wonderful things than ever before.

Source: Apple - iOS 8
专知会员服务
52+阅读 · 2021年4月6日
专知会员服务
26+阅读 · 2021年4月2日
大数据白皮书(2020年), 72页pdf
专知会员服务
59+阅读 · 2020年12月31日
【干货书】机器学习速查手册,135页pdf
专知会员服务
126+阅读 · 2020年11月20日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
111+阅读 · 2020年5月15日
强化学习最新教程,17页pdf
专知会员服务
177+阅读 · 2019年10月11日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
16+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
多高的AUC才算高?
ResysChina
7+阅读 · 2016年12月7日
Arxiv
0+阅读 · 2021年4月25日
Arxiv
0+阅读 · 2021年4月25日
VIP会员
相关VIP内容
专知会员服务
52+阅读 · 2021年4月6日
专知会员服务
26+阅读 · 2021年4月2日
大数据白皮书(2020年), 72页pdf
专知会员服务
59+阅读 · 2020年12月31日
【干货书】机器学习速查手册,135页pdf
专知会员服务
126+阅读 · 2020年11月20日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
111+阅读 · 2020年5月15日
强化学习最新教程,17页pdf
专知会员服务
177+阅读 · 2019年10月11日
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
16+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
多高的AUC才算高?
ResysChina
7+阅读 · 2016年12月7日
Top
微信扫码咨询专知VIP会员