本文是 ICML 2023 入选论文 Coordinated Dynamic Bidding in Repeated Second-Price Auctions with Budgets 的解读。该论文由北京大学计算经济学实验室和华为 TCS Lab 合作共同完成。本文提出了在有预算约束的重复二价拍卖中的在线协同竞价算法，从理论和实验的角度验证了协同竞价确实可以让每个玩家都拿到比单独竞价更好的收益，并分析了算法优良的博弈性质。

　　论文链接：https://proceedings.mlr.press/v202/chen23ac.html

01 引   言

　　在在线广告市场中，广告商通过参与在线广告位拍卖来赢得广告位及展示广告的机会。现实场景中，他们通常会参与多轮拍卖，有预算限制，并关心累积效益。参与这种重复拍卖的广告商所面临的是在线决策问题：他们无法获知即将到来的流量价值和可能的花费，必须根据历史信息决定出价，以最大化自己的累积效益。

　　最近，越来越多的广告商开始使用广告平台或第三方竞价机构提供的自动竞价服务。广告商告诉竞价代理他们的预算限制，代理设计满足预算约束的在线竞价算法，来最大化客户的累积效益。虽然大多数现有的在线竞价算法研究都集中在为一个竞价者设计竞价算法，但是，竞价代理通常同时拥有他所有客户的信息，从而有机会通过协同竞价来提高每个客户的效用。

　　本文的目标是回答在线拍卖场景中协同竞价的基本问题：我们是否可以设计一个协同的在线竞价策略，使得每个广告商客户的效用都高于他们在独立竞价下所能获得的最佳效用？

　　在本文中，我们研究了具有预算限制的重复二价拍卖中的竞价协同问题。具体的：

　　我们提出了满足预算约束的在线协同竞价算法，从理论和实验两方面保证了每个客户都能获得比其在独立竞价下所能获得的最佳效用更高的效用。此外，我们还对所提出的算法在对称情况下进行了均衡时博弈性质的分析：首先，我们证明了我们的算法是所有满足预算约束的协同竞价算法中最大化联盟福利的算法（即玩家效用和）。其次，我们证明了在我们的其中一个算法下，没有玩家可以通过谎报预算约束来获利。

02 难  点

　　为了获得有意义的理论结果，在线拍卖的协同竞价问题主要的难点在于竞价者在动态重复环境中的相互影响。因为拍卖是多人博弈，一个竞价者的效用受到其他人出价的影响。这样的多维动态分析是比较困难的。

　　此外，我们实际上是在比较每个竞价者的效用与其独立竞价时能获得的最佳效用，因此我们需要进行多基线而非单基线的比较。

　　或许有人会发现，允许竞价者之间进行货币转移可以简化问题，因为在这种情况下，算法设计只需要最大化联盟福利。但我们认为这是不合理的，因为竞价者参加拍卖，为的是扩大产品的影响力，赢得更多的广告位展示的机会，而非仅仅利用拍卖进行金融投资来直接获得金钱的利益。

03 基  线

　　考虑每个人都独立使用 Balseiro et al'19[1]提出的 adaptive pacing 算法的情况。作为一种协同竞价算法的特例，我们将其缩写为 IP（Individual Adaptive Pacing）。Balseiro et al'19[1]证明了该单人算法在随机和敌对环境下的最优性。并且，当玩家们的每轮期望花费满足强单调性时，可以证明每个玩家的平均策略及收益收敛到某个系统均衡。我们将其作为我们本论文的基线用于与我们自己提出的算法进行比较。同时，每轮期望花费函数的强单调性将是我们论文的主要假设。

04 技  术

　　为了克服这些困难，我们首先表明，存在一种最优的协同竞价算法，在每一轮中只选择一个代表进行竞价，其他成员竞价为0。这样可以降低获胜者的花费，从而提高她单轮的效用。因此，竞价算法设计问题就分解为了设计一个公平的规则来选择代表进行竞价以及一个良好的预算管理策略。我们将使用单人的 adaptive pacing 来作为预算管理策略。而如何设计代表选择的规则，使每个玩家都有足够的机会参与真实拍卖，是一个尤为重要的问题。

　　其次，强单调性假设确保了竞价者在使用协同竞价算法时的平均效用收敛，这进一步允许我们将对算法与基线的比较简化为在两个均衡下每个玩家效用的比较。更重要的是，这种均衡分析的简化使我们能够在对称情况下对算法的博弈性质进行一些理论分析。

05 两种算法的简介

　　一种最为自然简单的算法是对 IP 的直接延伸，注意到每个玩家在 IP 算法下的参数和策略更新只跟自己历史的花费和获得价值有关，我们直接将每次竞价最高的玩家选为代表参加真实的拍卖，将其他人的竞价抹平，并利用得到的花费和价值来更新参数。我们称该算法为 Coordinated Pacing（CP）。CP 的形式较为简洁，易于分析。可以证明在对称情况下，它能使得每个玩家的收益都比独立竞价时要高，同时当其他人都诚实报告自己的预算约束的时候，没有玩家能够通过报低自己的预算约束来获得更高的均衡收益。然而，这样简单的竞价代表选择规则在一般情况下并不是“公平”的。存在不对称的例子，使得一个玩家永远也没有机会赢得物品，而另一个玩家会一直赢的物品。

　　我们提出的第二种算法，Hybrid Coordinated Pacing（HP），将内部竞选和外部竞价分开来。通过模拟一个内部的拍卖来提高竞价代表选择的公平性。具体的，我们让内部拍卖的参数更新和拍卖结果模拟 IP 下的结果，让每个玩家都有足够的机会去参加外部的竞争。同时，因为每个人单轮的花费更少了，他们长期的平均收益就提升了。然而，因为该算法较为复杂，我们将玩家在该算法是否有动机谎报预算作为一个未来可探索的方向。

　　值得注意的是，我们找到了一个数值反例，其中的玩家在 IP 算法下有动机谎报自己的预算来提升效用。

06 总  结

　　本文提出了两个在有预算约束的重复二价拍卖中的在线协同竞价算法，并从理论和实验的角度验证了策略所具备的优良性质。同时，本文指出了很多可延伸拓展的方向，例如：

　　1. 如何更好地刻画和考虑联盟之外的人对于联盟的存在产生的反应；

　　2. 如何更合理地定义协同算法对联盟成员的公平性；

　　3. 如何将现在的在线竞价算法应用于实际广告拍卖，或是与机器学习结合设计基于学习的竞价算法。

参考文献：

[1] Balseiro, S. R. and Gur, Y. Learning in repeated auctions with budgets: Regret minimization and equilibrium. Management Science, 2019.