静5前沿讲座回顾｜陆品燕教授介绍一价拍卖效率的确定
关键词：静5前沿讲座
编者按
2023年5月10日，上海财经大学的陆品燕教授访问北京大学前沿计算研究中心，在静园五院作了题为“Settling the Efficiency of First Price Auction”的报告，介绍了一价拍卖效率的完全确定。报告由中心讲席教授邓小铁老师主持。
陆品燕教授报告现场
陆老师介绍了他与哥伦比亚大学金耀楠同学合作发表于 FOCS 2022 的论文。论文精确确定了一价拍卖的效率。一价拍卖是一种最为基本的拍卖形式。假设有一个被拍卖的物品和若干个参与拍卖的买家。每个买家向拍卖方提交一个报价，报价最高的买家就得到此物品，并且按其报价支付给拍卖方。这是一种非常简单，且在现实中被广泛使用的拍卖形式。
虽然一价拍卖有简单的规则，却会导致复杂的出价策略。每个买家 对于物品有一个真实价值 ，独立地抽取自先验分布 。 是买家 的私有信息，而他使用一个出价策略 进行出价 ，他的出价形成分布 。此时一个买家的效用定义为他期望下的获利 ，其中 是出价 时其他买家的出价都低于 的概率，也就是买到物品的概率。如果每个买家的出价策略 都总是最大化他的效用，那么这组策略 就称为贝叶斯纳什均衡（BNE）。对于任意一组价值分布 ，可以证明贝叶斯纳什均衡总是存在，但不一定唯一。
一价拍卖的效率是一个长期以来悬而未决的重要问题。存在一些价值分布 （称为实例），在一价拍卖的贝叶斯纳什均衡下，物品并不总是被卖给真实价值最高的买家，这导致一价拍卖的社会福利（即买到物品的买家的真实价值的期望）会低于最优（即买家之中最高的真实价值的期望），这两者的比值称为一价拍卖的效率。具体地，由于贝叶斯纳什均衡可能不唯一，可以用 PoA（Price of Anarchy）和 PoS（Price of Stability）两个量作为效率的衡量。其中 PoA 定义为 ，而 PoS 定义为 ，分别代表一价拍卖中当买家采用最坏的均衡时的社会福利与最优社会福利之比的下确界，和当买家采用最好的均衡时社会福利与最优社会福利之比的下确界。
在先前的研究工作中，Syrgkanis 与 Tardos 证明了 PoA 的一个下界是 ，而 Hoy，Taggart 与 Wang 将下界改进到约 。Hartline，Hoy 和 Taggart 还构造了一个具体的例子，具有 的效率，这是 PoA 和 PoS 的一个上界。也就是说，先前的工作只能确定 PoA 的紧界位于 到 之间。先前的研究方法没有充分利用买家价值的独立性，并且面临着一价拍卖的贝叶斯纳什均衡十分复杂，难以刻画等困难，所以难以更进一步确定 PoA 的精确值。
陆老师与合作者在论文中提出了一套新的技术框架，证明了一价拍卖的 PoA 和 PoS 都等于 ，从而完全解决了这一难题。
为了分析和构造最坏情况的实例，重要的一步是改变视角。他们首先使用出价分布 代替价值分布与均衡策略的组合 来表达实例，根据均衡下的出价分布 即可反推确定唯一的价值分布 和均衡策略 ，从而避免了均衡难以刻画和均衡不唯一性带来的困难。但并非任何出价分布 都是有效的，有一些分布 不对应任何 和 。利用一价拍卖均衡出价分布的性质，他们进一步使用出价到价值的映射来表示实例。出价到价值的映射可以看作出价策略 的反函数，是一个单调递增函数，从一组出价到价值的映射可以反推得到出价分布。经过这一视角转换，实例的表示更加简洁清晰，并且可以利用离散化技巧将出价到价值的映射转化为分段常数函数，以方便进行分析。
利用这一视角变换，他们构造出达到最坏情况的实例，包含一个价值较高的买家和 个价值较低的买家。当 趋于无穷时，实例的效率达到 。而对于一般的实例，他们通过将实例逐步修改，每一步都保证效率不增大，最终达到最坏实例，从而说明任何实例的效率都不低于 ，也就是一价拍卖 PoA 的紧界为 。对于 PoS，他们通过修改最坏实例的构造使得均衡唯一，得出 PoS 也同样是 。
陆老师的研究成果不仅解决了一价拍卖的效率这一难题，而且为学术界带来了关于一价拍卖均衡更深刻的认识，以及研究更多相关问题的新视角、新工具。陆老师的报告得到了在场老师同学们的一致好评，报告在踊跃的交流互动中圆满结束。
合影留念
图文 | 李宁远
PKU daGAME
近期讲座回顾
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。