来自公众号：Gopher指北
在线广告，也称网络广告、互联网广告，顾名思义，指的是在线媒体上投放的广告。平时我们在刷信息流、短视频、新闻和微博均可以看见它的影子。对于比较大的广告平台，用户定向后依旧会有大量的广告可以下发，而从大量的广告中选择合适的广告展现给用户就是本篇要讨论的主题——在线广告分配策略。
名词描述
为了更好的理解本文，先提前做一些名词描述。
eCPM(Effective Cost Per Mille): 指的是每一千次展示可以获得的广告收入。此指标反映盈利能力，不代表实际收入。不同的广告主会选择CPC、CPM等不同出价方式，因此广告分配时无法以纯粹的出价进行比较，所以才有了ecpm这一指标用于评估不同出价方式的广告可以给广告平台带来的收益。
定向广告：所谓"定向"实际上是对受众的筛选，即广告的显示是根据访问者来决定的，先进的广告管理系统 能够提供多种多样的定向方式。
最好的一定合适嘛
对于广告平台而言收益最大化是优先事项。为了保证收益最大化，对于每一次广告请求我们都选择ecpm最高的广告下发。这个逻辑从理论上来看是正确的，但在实际中就不一定了，那么它到底会有什么问题呢？
- ⼴告消耗超预算限额。
- 广告预算消耗不尽。
- 空结果问题。
- 部分广告消耗过快影响广告主投放体验和用户产品体验。
问题分析
问题1
对问题1进行分析时，我们需要先有这样一个共识，广告的点击、曝光等数据上报有一定的延时。
由于广告分配策略未考虑预算消耗信息，当消耗接近预算限额时未能及时减缓曝光速度，导致本应分配给其他广告主的流量依旧分配给了预算受限的广告主，这是对广告平台流量的浪费（流量越大的平台浪费会愈加严重）。
问题2
部分中小广告主竞争力弱(出价低)，很难获取足够的曝光量，这种情形当广告充裕时尤为明显。
问题3
一方面可能是因为广告资源不足，另外一方面也有可能是定向广告消耗过快(详见下面的例子)。
问题4
广告按照ecpm排序，会导致广告消耗速度差异较大直接影响广告主的投放体验，甚至于用户反复看到重复的广告直接影响用户产品体验，再反过来影响到广告的CVR。
为了进一步说明纯按价高者得这一算法的不足之处，请看下面的特殊例子。
| 广告 | 出价($) | 预算($) | 定向 |
|---|---|---|---|
| A | 0.5 | 100 | 男,游戏 |
| B | 1 | 100 | 男,游戏,运动 |
以上述广告为例，现有男,游戏和男,运动请求各100。理想最大收益为150$，但是按照上述策略分配广告时，会出现男,游戏这100请求先到达时优先消耗B广告，男,运动这100请求达到时无广告可消耗。按照ecpm排序的算法又称为Greedy算法，该算法会让高价值广告快速消耗。
合适的才是最好的
Balance算法
与Greedy算法不同的是，Kalyanasundaram和Pruhs提出的Balance算法忽略单个bidder的出价，尽可能平衡所有bidder的预算消耗，使得其在线时间尽可能⻓，即尽量使得所有⼴告都保持匀速投放。其算法描述如下：
当一个满足一些定向广告的请求到达时：
if 广告预算消耗完 {
continue
} else {
选择一个（消耗/预算）值最小的一个广告
}
相比贪心算法，Balance算法平衡所有广告的消耗速度，能够有效解决贪心算法广告快速消耗的问题，但在广告消耗不尽的问题上依旧不是最佳解决方案。我们看下面特殊例子：
| 广告 | 出价($) | 预算($) | 定向 |
|---|---|---|---|
| A | 1 | 100 | 男,游戏 |
| B | 0.01 | 100 | 男,游戏,运动 |
以上述广告为例，现有男,游戏和男,运动请求各100。理想对最大收益为110$，根据balance算法其总的预算消耗仅为几美元。当男,游戏这100请求先到达时，B广告一定会先消耗完，当男,运动100请求到达时依旧会无广告可消耗。
那Balance算法适用场景到底是什么，下面我们以极限法来考虑这个问题。
假设一：如果广告A和广告B的出价分别为1000$和1$(CPC)
很明显，广告A具有更大的优势理应优先展示。根据前面的例子，Balance算法是无法解决这种极值场景的，而Greedy算法则充分兼顾了平台的利益以及广告主急切花钱的心情。
假设二：如果所有广告出价分别为10$(CPC)
Greedy算法是和出价有关的，而Balance算法仅和预算有关。根据控制变量法很容易知道Balance算法正是为了这种场景而生。
小结：根据前面的假设以及论文中的描述我们总结如下结论：
- Balance算法更适用于广告出价比较接近的场景
- Greedy算法则比较适用于广告出价差异比较大的场景
MSVV算法
只有小孩子才做选做题，我们成年人全都要。Balance算法和Greedy算法各有优劣且适用场景不同，那有没有算法能够融合两者的优点呢？这正式MSVV算法的思路。
为了更清楚描述新算法，先给出一些基本定义：
- 消耗比例：
'消耗/总预算'并记作$\upsilon$。总预算由广告主设置，并且可动态调整。 - 权衡函数：
$\Psi(\upsilon) = 1 - e^{(\upsilon-1)}$ - 缩放出价：
$出价 * \Psi(\upsilon)$
算法描述如下：
当一个满足一些定向广告的请求到达时：
if 广告预算消耗完 {
continue
} else {
选择一个`缩放出价`值最大的广告
}
上述的权衡函数为一个单调下降的函数，且$\upsilon$取值范围为[0,1]。权衡函数分布图如下：
当所有广告出价相等时，由于权衡函数是一个单调下降的函数，因此MSVV算法就正好退化成Balance算法。另一方面，如果出价差异非常大时，MSVV算法在大多数情况都不会改变出价的顺序，此时MSVV表现更接近Greedy算法。考虑更极端的情况，当所有广告预算都是无限时，MSVV算法直接退化为Greedy算法，因为此时权衡函数为常量$1 - {\frac 1 e}$。
为了验证MSVV算法的适应性，我们看下面的代码：
type ad struct {
cost float64
total float64
price float64
}
func scaled(price, cost, total float64) float64 {
return price * (1.0 - math.Pow(math.E, cost/total-1))
}
func main() {
a := &ad{0, 100, 1}
b := &ad{0, 100, 0.01}
// 模拟`男,游戏`到达时，a和b同时消耗
for i := 0; i < 100; i++ {
aCp := scaled(a.price, a.cost, a.total)
bCp := scaled(b.price, b.cost, b.total)
if a.cost >= a.total || b.cost >= b.total {
break
}
if aCp >= bCp {
a.cost += a.price
} else {
b.cost += b.price
}
}
// 模拟`男,运动`到达时，仅b可消耗
for i := 0; i < 100; i++ {
if b.cost >= b.total {
break
}
b.cost += b.price
}
fmt.Println(a.cost + b.cost)
}
MSVV算法在前面的极值例子中收益分别为116.5和101，其整体表现基本符合预期。
总结
现在回顾前面的问题，消耗过快以及减缓曝光速度都在Balance算法的射程内（广告资源不足只有通过其他手段解决了）。从广告平台的收益角度考虑Greedy算法更佳。那么结合两者优点的MSVV算法可谓是每个广告平台居家旅行之必备利器。
在线广告老许也是初次接触，而且正在努力储备知识，以期日后可持续发展。如果文中有不正确的地方欢迎各位读者指正和交流。
