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

2022 年 2 月 2 日 专知

导读

本文是 WWW 2022入选论文《基于均值的学习算法在首价拍卖中的纳什均衡收敛性（Nash Convergence of Mean-Based Learning Algorithms in First Price Auctions）》的解读。该工作由北京大学前沿计算研究中心邓小铁教授课题组主导完成，根据理论计算领域惯例，作者按姓名首字母排序。

论文链接：

https://www.zhuanzhi.ai/paper/b664f83275fd22f5ba450b2eb1edb8f1

背景

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

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

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

模型

我们考虑一个重复首价拍卖的模型，一个卖家给固定的多个买家重复无穷多轮卖同一种商品。每个买家运行一个“基于均值的在线学习算法”来学习报价策略。每一轮，每个买家的算法给出其当轮的报价，根据首价拍卖结果，每个买家获得当轮收益，算法再根据当轮的拍卖信息更新未来的报价策略。Braverman et al (2009) 提出的“基于均值的在线学习算法”要求算法在每一轮仅以低概率选取历史平均收益低的报价。这类算法包括很多无悔学习算法（no-regret learning algorithm），例如 eps-greedy，MWU 和 Follow the Pertubed Leader。

我们假设每个买家对商品的估值是固定的，即不随轮数变化。这意味着我们并不采取贝叶斯模型（每一轮每个买家对商品的估值从某一个固定分布中采样）。研究表明首价拍卖的贝叶斯纳什均衡对于一般的非对称分布没有显示刻画，也没有已知的算法能高效计算，更别谈大家熟知的无悔算法。而现实中，很多在线广告拍卖场景，拍卖发生的频率很高，即拍卖在相当短的一段时间内发生很多次。所以，买家对商品的估值可能在短时间内还没有发生变化，买家行为就已经收敛到了均衡。事实上，我们将会看到，在这个假设下，买家的行为已经展现出了复杂的收敛性质。

结果

我们聚焦于两种纳什均衡收敛的概念：一是“时间平均（time-average）”意义下收敛，指当轮数趋于无穷时，采取纳什均衡策略的轮的频率将趋向于1；二是“末轮策略（last-iterate）”意义下收敛，指当轮数趋于无穷时，买家混合策略组合趋向于纳什均衡。

我们证明了在有至少两个最高估值买家的情形下，任意“基于均值的学习算法”将收敛到纳什均衡。特别的，如果有至少三个最高估值买家，我们证明了买家行为在两种意义下均收敛；如果仅有两个最高估值买家，我们证明了买家行为在“时间平均”意义下收敛，而在“末轮策略”意义下不一定收敛，同时，我们的试验显示 eps-greedy 算法可能收敛到此时的两个纳什均衡中的任意一个均衡。而如果仅有一个最高估值买家，我们构造了某个“基于均值的学习算法”在两个意义下均不收敛，同时，我们的实验表明 eps-greedy 和 MWU 算法均表现出不收敛的性质。

证明思路和技巧

我们证明的直觉来源于经济学博弈论中的“逐步剔除被占优策略（iterated elimination of dominated strategies）”的均衡解概念。事实上这个思路在 Hon-Snir et al (1998) 分析 fictitious play 在首价拍卖中收敛性的论文中已经用到。但该论文研究的 fictitious play 为确定性算法，我们证明的难点正是在于处理“基于均值的学习算法”中的很大一类随机算法，它们可能会以正的概率选取很差的被占优的策略。我们采用并拓展了 Feng et al (2021) 研究次价拍卖中学习算法收敛性工作所提出的“时间分割”技术（time-partitioning），来处理首价拍卖中学习算法的随机性难题。

总结

我们完整刻画了“基于均值的学习算法”在重复首价拍卖中两种纳什均衡收敛性，如下图所示。

项目简介视频

参考文献

[1] Feng, Z., Guruganesh, G., Liaw, C., Mehta, A., and Sethi, A. (2021). Convergence Analysis of No-Regret Bidding Algorithms in Repeated Auctions. In Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21).

[2] Hon-Snir, S., Monderer, D., and Sela, A. (1998). A Learning Approach to Auctions. Journal of Economic Theory, 82(1):65–88.

[3] Braverman, M., Mao, J., Schneider, J., and Weinberg, M. (2018). Selling to a No-Regret Buyer. In Proceedings of the 19th ACM Conference on Economics and Computation (EC'18).

[4] Kolumbus, Y. and Nisan, N. (2021). Auctions between regret-minimizing agents. arXiv preprint arXiv:2110.11855.

专知便捷查看