2023年7月4日，来自新加坡南洋理工大学的贝小辉老师访问北京大学前沿计算研究中心，在静园五院做了题为“Online Adwords Auction: From Theory to Practice”的报告。报告由中心助理教授孔雨晴老师主持。

贝小辉老师报告现场（报告视频：https://www.bilibili.com/video/BV1DF411R7m7/）

　　贝小辉老师首先介绍了拍卖设计（auction design）的一些背景。其中最成功的例子是在线广告词拍卖，这种拍卖的场景通常出现在搜索引擎的页面上，网站上有时候会有广告栏。公司自动化拍卖这些栏位给广告主。广告收益是互联网公司的重头，Google 2020年收入中最大头的就是广告。

　　拍卖在学界受到了非常广泛的关注，有很多重要且漂亮的结果。理想中，拍卖被抽象为了三方不同的交互，内容呈现者（publisher）展示广告，用户（user）看广告，广告主（advertiser）有想要展示的广告。然而在业界，这一系统还出现了别的角色：

　　- DSP（Demand Side Platform）：为广告主进行汇总和集中报价。

　　- SSP（Supply Side Platform）：帮助内容呈现者和不同的 DSP 联系。

　　- Ad exchange：在供求双方之间的角色。

　　贝老师从业界的实际情况和需求出发，提出了两个学界关注度不够高但是现实中却真实存在的问题。

　　第一个问题考虑的是竞价者子集选择问题。这一问题的出发点在于思考内容提供者的收入从哪里来。贝老师总结了一下三点：

　　- 选取良好的拍卖机制：比如二价拍卖机制中加入保留价格，就能得到更高的收益。

　　- 环境的先验信息：如果二价拍卖中我们能知道广告主的出价信息，就能更好地设计保留价格。

　　- 竞价者之间的竞争。

　　贝老师认为，第三点是更加重要的。首先，有一个非常漂亮的理论结果：二价单物品拍卖中，如果能够再吸引一个竞价者进来，那么拍卖方就能得到超过最好机制最好信息下的最优收益的收益。所以，从这个角度说，竞价者多是一个好事。

　　但从工业界来说，问题并没有结束。实践经验来看，如果竞价者的个数在1到10之间，那么确实越多越好。但是如果有100个竞价者呢？这就会引起新的问题。

　　- 延迟：太多竞价者拍卖机制的执行会被拖慢。在工业界的实际情况下，一次拍卖的竞价者被设定在20个左右。

　　- DSP：DSP 某种意义上解决了竞价者太多的问题，但是它引起了新的成本，比如吸引大的 DSP，维持与 DSP 的关系，这些行为都需要成本。

　　所以在真正运行拍卖之前，我们需要只能选择其中一部分竞价者来进行拍卖。

　　接下来，贝老师引入了这一问题所对应的模型。这里考虑的是单轮单物品的n个竞价者拍卖的经典模型，然后还要加上竞价者选择的环节。拍卖方首先固定一个简单的拍卖机制，从所有可能的竞价者中选取一个，来最大化自己的期望收益。这篇工作中考虑的简单机制包括：二价拍卖匿名保留价格（AR，工业界常见的），匿名价格（AP），顺序过帐定价（SPP），myerson 拍卖（Myerson）。

　　对上面的两个新问题的考虑也可以对应到模型中来：

　　- capacity constraints：只能选m个竞价者。

　　- invitation cost：选每个竞价者需要花费某个固定的价格。

　　这两个问题在学界也有一些非常相似的考虑。

　　- capacity constraint：与它非常相关的问题是k-MAX 问题。这一问题的表述是：从若干个随机的值中选出k个，最大化期望上最大的那个值，比如社会福利最大化就恰好是这个问题。如果是 Myerson 机制，收益最大化也基本上就是这个问题。k-MAX 有 PTAS，在同一篇工作中，他们也考虑了第二大的问题，这个时候就不太可能存在近似算法了，因为有 APX-hard 的结果。到此，似乎问题已经解决了，然而这一结果只适用于最基本情况，对于有保留价格的情况，这套方法就不再成立。

　　- Invitation costs：在线潘多拉魔盒问题和带 invitation costs 的 SPP 很相似。

　　贝老师的工作则是填补了更多的空白，这些空白的考虑更符合实际的使用：

　　AR 和 SPA 尽管只差一个保留价格，但是 AR 在两个问题中可以有O(1)近似或者O(1/δ)近似，而 SPA 却是不可近似的。此外，SPP 的 capacity constraint 问题有2-近似。

　　之后，贝老师简要介绍了一下这一系列新结果的证明思路和技术。对于 capacity constraint，AP(S)和Myerson(S)都可以写为次模优化问题，于是用次模优化的一般理论就可以做好的近似。另一方面，AR(S)和SPA(S)不是次模的。但是f(S)=max_{r}AR(S)是 XOS 类函数（分数次可加）。利用这一事实，也可以得到近似算法。此外，这个工作也给出了一个自然的优化问题，它属于 XOS 但不属于次模。对于 Invitation costs，带成本的次模最大化是很难的，在一般情况下是 APX-hard，所以不能直接做。相反，因为是 XOS 函数，所以可以用一种叫 demand oracle 的技术来实现近似算法。

　　对于这一个例子，贝老师也提出了一些未解决的问题。首先，表格中的其他空白如何去填补。其次，除了考虑收益最大化，也可以考虑社会福利的问题，还可以考虑其他的拍卖机制中的竞价者选择的问题，比如不诚实的拍卖机制（例如一价拍卖）。

　　此后，贝老师简要地介绍了第二个例子。这个例子关注 DSP。DSP 像是一个中介平台，它不仅作为帮助的媒介，而且还要牟利。从 DSP 的角度来说，它有两个任务，设计对下面广告商的拍卖机制以及对上面平台的报价机制。每个 DSP 有自己的目标，即最大化自己的收益。

　　这个问题并不是很容易的问题。现实中，最简单的机制就是把竞价者的报价原样报上去，但是这样是不能赚钱的。实际上，在文献中，这一问题的最优机制是有讨论的。在这种情况下，DSP 的最优策略应该是把下面的所有竞价者的虚拟价值算出来，找到最大的那个，如果它大于零，那么 DSP 往上报价的时候，就应该表现得仿佛它的真实报价是这个虚拟价值。在这种情况下，上面讨论的简单拍卖就不再是最优的，并且会有收益非单调的性质，市场结构上，选择人数比较少的 DSP 会对广告商更有利一点。

　　针对这一个例子，贝老师也提出了很多未解决的问题。首先，DSP 是有层级的，如何考虑这些层级之间的影响。其次，还有很多广告主宣传活动的设计的问题。最后，可能还需要考虑 DSP 之间的竞争关系。

　　作为总结，贝老师说，拍卖有很多漂亮的结果，但是从业界来说，会有很多新的问题和新的困难，这是一个非常好地理论与实际相结合的地方。

　　报告的过程中，听众与贝老师进行非常充分的互动，大家都很有热情，也有自己的想法。报告结束后，孔雨晴老师代表中心给贝老师送了纪念礼物并合影留念。