最近恶补了一波广告相关文章，本文是预算控制平滑方面很经典的文章之一，由LinkedIn团队发表在KDD2014上。

摘要

Targeted online advertising is a prime source of revenue for many Internet companies. It is a common industry practice to use a generalized second price auction mechanism to rank advertisements at every opportunity of an impression. This greedy algorithm is suboptimal for both advertisers and pub- lishers when advertisers have a finite budget. In a greedy mechanism high performing advertisers tend to drop out of the auction marketplace fast and that adversely affects both the advertiser experience and the publisher revenue. We describe a method for improving such ad serving systems by including a budget pacing component that serves ads by being aware of global supply patterns. Such a system is ben- eficial for both advertisers and publishers. We demonstrate the benefits of this component using experiments we con- ducted on advertising at LinkedIn.

在线广告是许多互联网公司的主要收入来源，目前业界的普遍做法是，针对每个曝光采用二价拍卖机制对广告进行排名。但是当广告商拥有有限的预算时，这种贪婪的算法对广告商和发布者来说都是次优的。

因为高消耗（High Performing）广告主往往会迅速退出拍卖市场，这对广告主的体验和平台的收入都有负向影响。

我们描述了一种改进此类广告服务系统的方法，它包括一个通过感知全局的消耗模式来控制预算消耗的模块。这样的系统对广告商和出版商都是有益的，我们用我们在LinkedIn的广告实验来证明这个模块的收益。

问题背景

一个广告计划会参与每一次有资格的（此处指广告计划覆盖人群的曝光）竞价，直到预算用完。当一个广告计划的预算用完了之后，就会在剩下的时间里退出交易市场。二价拍卖机制的目标是贪婪优化每一次曝光的价值。具体表现为：

消耗高的（perform well ）广告计划快速用完预算并很早地退出
平台往往只能得到一小部分目标用户的数据
随着部分广告计划退出，市场竞争减弱，二价机制导致收益下降
广告服务的基建会导致花费存在延迟，如果广告消耗非常快，很容易超过预算

解决方案

此处简单扩展一下，一般控制预算有两种方式：

修改竞价（Modified Biding），通过修改竞价来提升广告的消耗，这种方式优点在于可以增加整体消耗，当所有流量都参竞仍然无法消耗完预算，那么必然需要提高出价来竞争得到更多的流量，消耗上限更高，缺点在于如果想通过降低出价提升广告计划时间长度，那么大家出价都会降低，整体消耗会非常低，平台收入受损。
概率截流（Probabilistic Throttling），通过参竞的概率来控制预算的消耗情况，这种方法优势在于并不会影响竞争度，平台整体收入不会受损，缺点在于上限有限，无法从高出价、高预算的广告主身上赚到更多的钱。

本文的做法是预估未来的流量分布，并采用概率截流（Probabilistic Throttling）的方式动态控制预算。

将全天分成\(T\)个时间段，预估广告\(i\)从0点到时间段\(t\)的流量记为\(f_{i,t}\)，将累积应消耗预算\(d_i\)按照分配到每个时间段\(a_{i,t}=\frac{f_{i,t}}{f_{i,T}}d_i\)，然后我们根据累积应消耗预算来动态调整节流概率\(p_{i,t}\)： \[ p_{i,t}=\begin{cases} \min(p_{i,t-1} \cdot (1+r_t), 1) && s_{i,t} \leq a_{i,t} \\ \max(p_{i,t-1} \cdot (1-r_t), 0) && s_{i,t} > a_{i,t} \\ \end{cases} \]

其中\(s_{i,t}\)是截止\(t\)时刻后实际使用预算，\(r_t\)为\(t\)时刻的调整幅度。

实现细节：

更新频率，1min一次更新（工程实现方式后面有提到）
预测，预测每个广告目前用户群体的访问量（PV），具体使用方法没细说，大概率是时间序列类的方法
调整率，\(r_t=10\%\)，理论上应该根据消耗率\(\partial s_{i,t}/\partial t\)来调整，但是噪声比较大，未来可能会做
慢启动，\(p_{i,0}=10\%\)，这样做是为了让系统可以学习广告的消耗情况，有更长的时间可以调整，另一方面即使速率比较慢，25min也可以将节流概率调整到1
快速完成，因为流量是预估的，所以每日会留出一定时间buffer避免预算消耗不完，每天22点之后，没有消耗完的预算会被快速消耗。

工程实现：

流量预测是离线的，消耗数据的实时流是LinkedIn的内部工具，每分钟更新是采用每次随机更新部分广告，大概7秒更新12%的广告，这样可以减轻服务器压力。

实验

实验我觉得值得关注：

因为消耗的预算是同一个池子，所以在做AB的时候会有预算争抢的问题（即不满足STUVA假设），存在“网络效应”，所以实验方式为天轮转AB实验，一共15天，1个实验7天一个实验8天覆盖周一到周日，8天的实验对两个重复日期取平均
另一个就是关注的实验指标
- 广告主：
  - 广告计划的生命周期，耗完95%预算的时间
  - 单位消耗的曝光用户，即广告覆盖用户数
  - 实际开展的广告计划数量，此处我理解应该是所有
- 平台：
  - 每次请求消耗，平台收入指标
  - 超出预算消耗，资损类指标
- 用户：
  - 每个用户看过的广告数，类似浏览深度的感觉，但如果只做预算控制，应该跟广告生命周期相关

评价总结

文章是很早年的文章，14年KDD，当时NN可能都没有被大规模使用，提出的预算调节方法简单好用。

多BB两句，我在滴滴的三年中，其中我觉得有两部分代码价值百万，其中一部分就是我们在2019年初做我们的算法迭代系统时，就做了对预算进行分桶的考虑，在不同流量桶（即AB测试版本）上进行预算的平分，这样可以杜绝不同策略消耗预算速率差异所导致的在预算池内的争抢问题，目前很多大厂的广告系统都没有做到这一步。感叹一句CGNB！（CG是当时团队中设计系统的主要负责人）