共计 2968 个字符，预计需要花费 8 分钟才能阅读完成。
来自公众号：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 算法的思路。
为了更分明形容新算法，先给出一些根本定义：
算法形容如下：
当一个满足一些定向广告的申请达到时：if 广告估算耗费完 {continue} else {抉择一个 ` 缩放出价 ` 值最大的广告}
上述的衡量函数为一个枯燥降落的函数，且 \(v \)取值范畴为[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 算法堪称是每个广告平台居家旅行之必备利器。
在线广告老许也是首次接触，而且正在致力储备常识，以期日后可继续倒退。如果文中有不正确的中央欢送各位读者斧正和交换。
