WWW 2022 | 基于均值的学习算法在首价拍卖中的纳什均衡收敛性

首价拍卖是在线广告拍卖的一个趋势，比如2019年谷歌在几乎所有广告平台完成了从次价拍卖到首价拍卖的转型。在首价拍卖中，出最高价的买家获得商品并支付自己的报价，获得的实际收益是自己对商品的估值减去其报价。据此，首价拍卖中的买家会策略性报价以获取更大收益。

比如在一个有两个买家一个商品的首价拍卖中，假设买家1对商品的估值为200元，而又同时知道买家2对商品的估值为100元，那么买家1知道买家2不会报比100元更高的价格，他只需报价101元就能拿到商品同时获得200-101=99元的效益，于是他不会诚实地报自己对商品的实际估值200元，而是会策略性报低价格。然而在实际的市场中，刚刚进入市场的买家往往并不了解其它买家对同一商品的估值，这时候他们会采用在线学习算法来学习如何报价以获取最大的效益。

那么大家自然会问：当买家采取这些在线学习算法在重复拍卖中自动报价时，买家的行为会怎样动态变化？是否会收敛到一个好的均衡？我们的工作研究了一大类被称为“基于均值的在线学习算法（mean-based learning algorithm）”，并完整地刻画了这类学习算法在重复首价拍卖中的两种纳什均衡收敛性。