本文是对 AAAI 2024 会议上发表的论文 Dynamic Budget Throttling in Repeated Second-Price Auctions 的论文解读。本论文由北京大学前沿计算研究中心邓小铁、孔雨晴课题组与腾讯广告等合作完成，邓小铁课题组博士生陈炤桦、西北大学博士生王畅与孔雨晴课题组博士生王骞为共同第一作者。论文探讨了重复二价拍卖中利用节流方法控制买家预算所能达到的表现。

　　论文地址：https://arxiv.org/abs/2207.04690

01 背 景

　　由于当前的广告拍卖市场的巨大体量、广告拍卖发生的极高频率以及广告商的优化目标和所受约束较为复杂等多方面的因素，在现在的广告拍卖市场中，广告平台往往引入自动出价代理（auto-bidder）帮助广告商进行实时报价，并在广告商所指定的约束（如预算、回报投入比等）下优化整体目标。进一步，于实际场景中，广告位的具体价值等详细信息往往由自动出价代理或其背后的广告平台预测算法直接估计；广告商由于已知信息远少于广告平台，故对广告位价值的预估往往较为粗糙。

　　在这一背景下，我们考虑当广告商受到长期预算限制时自动出价代理在重复二价拍卖中的出价算法。受到实际业务的启发，我们特别考虑节流（throttling）算法，即自动出价代理仅能选择是否参加一场拍卖；如果参加，则其出价必须为广告位的真实预估价值。这一业务需求来源于多种原因：如，广告商不允许自动出价代理更改出价；节流策略更有利于广告商了解市场全貌等。我们主要研究节流策略所能达到的表现。

02 模 型

　　我们假设市场中共发生T次二价拍卖（second-price auction），其中广告商的预算为B = \rho T，\rho为与T无关的常数。在第t次拍卖中，广告位的预估价值为v_t，这里，v_t可能是随机的或是对抗性的；市场中的最高竞价为p_t，我们假设其独立服从于某个未知分布G。我们假设v_t,p_t \in [0, \bar{v}]。自动出价代理在第t次拍卖中的决策为x_t \in \{0, 1\}；其中1代表参与拍卖，0代表不参与。我们令r_t = (v_t - p_t)^+，c_t = p_t 1[v_t \ge p_t]，则广告商在第t次拍卖中的效益（utility）为x_t r_t，开销为x_t c_t。

　　则在这一建模下，自动出价代理的优化问题为

　　在这一问题下，对于v_t是随机的或是对抗性的，我们考虑不同的评价指标。在前者情况下，我们将节流算法的效益与“流动最优”（fluid optimal）进行比较：

　　这里，流动最优代表着当期望意义上开销不超出预算时最优随机策略的期望效益。在后者情况下，我们则考虑“远视最优”（hindsight optimal）的期望：

　　关于这两个评价指标，我们可以得到一些最优可能界和不可能结果。首先，在v_t随机时，存在一些实例使得任何算法的期望效益与流动最优的差（即“悔”）都是\Omega(\sqrt{T})的；其次，在v_t是对抗性的时，任何算法在T \to \infty时的渐近竞争比（asymptotic competitive ratio）都是不超过\rho / \bar{v}的。最后，我们证明了任何节流算法在面对对抗性的最高竞价p 时都是无意义的；这说明了假设p随机的必要性。

03 算法结果

　　我们下面考虑较优的节流算法。由于最高竞价p所服从的分布G是未知的，如何获得关于G的信息尤为关键。我们这里考虑两种信息反馈模型：在全信息反馈下，自动出价代理在每一轮结束后都可以看到该轮的最高竞价；在部分信息反馈下，自动出价代理仅当参加了一轮拍卖后才能在该轮结束后看到相应的最高竞价。显然，部分信息反馈是更难处理的。

　　我们的工作提出了 OGD-CB 算法，其受到 [Balseiro, Lu, Mirrokni; 2023] 这一工作的启发。这一算法的关键点是动态维护一个非负标价系数\lambda_t。直观地讲，由于受到预算限制，自动出价代理希望赢得那些回报投入比（即r_t / c_t）较高的拍卖；而\lambda_t即代表了在第t轮中期望回报r(v_t)和期望开销c(v_t)比值的最低阈值。当这一比值高于\lambda_t时，选择参加此次拍卖；否则不参加。维护\lambda_t的方法与期望开销有关：当期望开销高于\rho时，说明花销过大，阈值过松，故提高\lambda_t；否则说明花销过小，阈值过紧，故降低\lambda_t。算法中具体更新\lambda_t的方式采用了在线优化中常用的在线梯度下降（online gradient descent, OGD）方法。

　　当知道期望回报r(v_t)和期望开销c(v_t)的精确值时，上述算法当然有很好的保障。然而，由于分布G是未知的，我们只能得到这两个期望的估计值。我们的算法在这里的估计采用了置信界（confidence bound, CB）的技术。直觉上，当获得p的样本越多时，对G的估计就越准，算法效果就越好。在全信息反馈下，获取样本的频率已经达到了100%；而在部分信息反馈下，我们仍然可以证明获取样本的频率是一个常数，从而算法也能达到很好的效果。结果上，在两种信息反馈模型下，当v_t随机时，OGD-CB 算法的期望悔是近似最优的O(\sqrt{T \log T})；当v_t对抗时，算法的渐近竞争比是最优的\rho / \bar{v}。

04 节流算法与配速算法的比较

　　最后，我们将节流算法与配速（pacing）算法的表现进行了比较。后者是在实际业务中广泛应用的预算控制方法，其核心是将每次拍卖中的出价设置为实际价值的某一动态比值；这类算法的最优能力是不弱于节流算法的，因为节流算法是其的一个特例。

　　在此之上，我们证明了，当价值v_t随机时，在一般情况下，最优配速的期望效益是线性优于最优节流的。此外，最优配速可以应对最高竞价p_t对抗的情况，而最优节流不行。然而，当v_t 对抗而p_t随机时，最优节流在全信息反馈或部分信息反馈下则是渐近最优的出价算法。

05 总结与展望

　　我们的工作提供了一个在重复二价拍卖中动态节流策略的理论全景：我们给出了最优可能界和不可能结果，给出了（近似）最优算法，同时比较了节流和配速的性能。我们还有一些尚未能解决的问题，包括证明 OGD-CB 算法是否已是最优算法，以及在老虎机（bandits）信息反馈，即仅能看到效益和花费而看不到最高竞价时分析节流算法。

参考文献：

Santiago Balseiro, Haihao Lu, Vahab Mirrokni. The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems. Operations Research, 2023.