计算广告竞价机制

本文整理了计算广告中常见的出价模式

单个广告位

一价计费简单说就是排名第一的广告出价多少钱，广告平台则计费多少钱；一价机制也是最早应用到搜索广告竞价计费的一种机制。非常简单直接，但是有一个最严重的问题：在一价机制下，广告主之间不存在一个出价策略均衡，而是广告主会根据其他广告主的行为不断调整，整个系统会不断变化，不会达到纳什均衡。

假设拍卖某一个广告位的流量，按 cpm 一价计费拍卖，也就是出价高的人拿走流量，计费完全等于出价。假设有两个广告主竞价，保留价是 10 元。那么一开始广告主 A 出 10.1 元买走了第一个的流量，广告主 B 出 10.2 元买走了第二个的，这个时候广告主 A 会调整出价到 10.3 元，广告主 B 又调到 10.4 元。。。直到当前价格是广告主 A 出 100 元，这个时候广告主 B 算了下再加价要亏本了，决定不再跟了，反正是第二名，出 99.9 元也是输，出 10 元也是输，不如把价格调回到 10 元，这样如果广告主 A 预算撞线了或者退出了，还能捡个漏。这个时候广告主 A 发现 B 已经把价格调到 10 元了（不能直接看到 B 的出价，但是可能会逐渐试探到），自己也不用花 100 元去买，直接出 10.1 元就可以了。广告主 B 又把价格提高到 10.2 元。。。于是，一个新的循环又开始了。排名第一的广告的价格呈现锯齿状，非常不稳定。这就是没有达到纳什均衡的现象，即没有达到：博弈的任何一方，只要改变当前的选择，双方各自的利益都不会增加。不管现在这个循环的哪个阶段，总有一方可以针对性地调整自己的出价，从而提高自己的收益。
二价计费即排名第一的广告赢得竞价，但是只计排名第二的广告的出价

在二价计费机制下，当广告主 B 把价格调整到 10 元后，广告主 A 不需要再把价格调到 10.1 元。因为计费按第二名 + 最小货币单位，也是按 10 元 + 0.001 元计费。不管是保持 100 元出价还是修改到 10.1 元，都是按 10.001 元计费。这个时候循环就被打破了。在这个阶段，广告主 A 是没有办法再通过调整自己的出价，来提高自己的收益。广告主 B 也没有办法再调整出价，来提高自己的收益。这个时候就达到了所谓的纳什均衡。

一价下广告主会不断通过调整出价来尝试降低成本，这样会造成整个系统及其不稳定（平台收益一直处于波动中），在二价机制下广告主没有调价的动力了，按照期望价值出价即可，可以使系统更加稳定。由于二价机制原理简单，易于理解，很快二价便取代一价成为主流竞价机制。
对于竞价点和计费点不一致的广告，二价需要进行转化。比如均按 CPC 或 oCPC 计费，排名第一的广告点击率 0.05，出价 2 元每次点击，eCPM 为 100 块，排名第二的广告点击率 0.01，出价 5 元每次点击，eCPM 为 50 块；在二价下，此时对排名第一的广告按 50 / 1000 / 0.05 = 1 元，再加上 0.001 元 = 1.001 元每次点击收费。按照这个出价排名第一的广告 eCPM 为 1000 * 1.001 * 0.05 = 50.05 元刚好大于排名第二的 50 块。即二价机制对排名第一广告的实际扣费为让这条广告保持在第一位的最低出价。
一价和二价的反作弊
- 理想情况下的拍卖，广告主之间是无信息沟通的，每个广告主独立出价。但实际中并不一定如此，在特定的机制下广告主之间可以通过「约定」来进行作弊，损害平台利益。
- 二价机制中，假设只有 A、B 两个广告主，若 A、B 之间相互独立，出价分别为 100 和 60，则按照二价广告平台计费 60，A 获得竞价；但若 A 和 B 事先进行约定，此次竞价让 A 胜出，B 只出价 10，这时候 A 依然能胜出，但只需付给广告平台 10。因此二价下广告主之间有动力通过同谋的方式进行作弊，让广告平台利益受损。
- 一价机制中，还是上面的例子，如果 A、B 之间约定 A 出 10，B 出 5，这时候 B 只要不按约定出一个稍高于 10 的出价，即可以竞价获胜，因此 B 有动力去背叛 A 而获得收益。因此一价下广告主之间同谋的动力减少，反而相互背叛的动力会增强。
- 实际中尽管二价机制存在广告主结盟作弊的可能性，但只要参与竞价的广告主数量增多，同谋作弊的难度就会增高，客观上缓解了这个问题。

多个广告位

在同时有多个广告位进行竞价时，通常见于搜索广告场景，二价机制泛化为 GSP (Generized Second Price，广义第二价格拍卖)，即所有广告主按照排名下一位的广告主的出价计费。虽然二价在单个广告位时是 truth-telling 的，但在多个广告位时并不是。VCG（Vickrey–Clarke–Groves）机制则让广告主在多个竞标物下也保持 truth telling。VCG 机制核心是：每个广告的计费为：因为他们获得这个位置造成的社会总效用的下降，这个社会总效用通常使用 eCPM 进行衡量。

以下面具体例子进行分析

广告位	点击率
1	0.1
2	0.07

广告主	CPC
A	10
B	8
C	5

总共有两个广告位，点击率分别为 0.1 和 0.07，ABC 三个广告主分别按点击出价 10、8、5 块。

GSP 机制下，广告系统总收费为 800 （广告位 1）、350（广告位 2）。

	点击率	CPC	eCPM
A - 广告位1	0.1	10	1000
B - 广告位1	0.1	8	800
C - 广告位1	0.1	5	500
A - 广告位2	0.07	10	750
B - 广告位2	0.07	8	560
C - 广告位2	0.07	5	350

VCG 机制下

假设 A 参与竞价，A 获得广告位 1，我们对 A 获得广告位 1 进行计费，计算 B 和 C 因为 A 获得广告位 1 的损失。在 A 参与竞价赢得广告位时，B 的 eCPM 为 560，C 的 eCPM 为 0（没有赢得任何广告位），BC 总 eCPM 为 560；当 A 不参与竞价时，B 赢得广告位 1， eCPM 为 800，C 赢得广告位 2， eCPM 为 350，BC 总 eCPM 为 800 + 350 = 1150。因此因为 A 获得广告位 1 而对 BC 产生的 eCPM 损失为 1150 - 560 = 590 即为 A 为广告位 1 应付的钱。

同样的方法可以为 B 获得广告位 2 计费，计算 A 和 C 因 B 获得广告位 2 的损失。在 B 参与广告位 2 竞价时，AC 总 eCPM 为 1000 + 0，不参与时，AC 总 eCPM 为 1000 + 350，因此 B 应付 350。

在只有一个广告位时，VCG 中总效用的下降其实正好就好第二位的 eCPM（因为排名第二的广告主的收益由 eCPM 变为 0，其他排名第二位之后的广告主收益没变化）。因此在只有一个广告位时 VCG 和二价机制是等价的。在多个广告位下，GSP 并不是 truth-telling 的，还是按照上面的例子分析。假设 10、8、5 是广告主 ABC 按照真实价值出价，这时 A 的收益是 1000 - 800 = 200，其中 1000 是收入，800 是成本。如果此时 A 将出价调为 7.9，那么 B 将获得广告位 1，A 能够获得广告位 2，A 的收益为 553 - 350 = 203 > 200，高于在 truth-telling 下的收益，因此 GSP 机制下所有广告主 truth-telling 并不是占优策略，广告主仍有动力去通过调价获利。

	点击率	CPC	eCPM
A - 广告位1	0.1	7.9	790
B - 广告位1	0.1	8	800
C - 广告位1	0.1	5	500
A - 广告位2	0.07	7.9	553
B - 广告位2	0.07	8	560
C - 广告位2	0.07	5	350

GSP 博弈性质

假设有 N 个广告位，K 个广告主，为了简化模型，假设

每个广告位的点击率是一定的，与放置在该广告位上的广告无关；
广告主从每次点击中获取的价值也是一定的，与广告放置的位置无关；

按照排列位置，广告位的点击率依次为 $a_1 > a_2 > \dots > a_N$ ，广告主出价为 $b_1 \ge b_2 \ge \dots \ge b_K$ ，广告位对应广告每次点击收益依次为 $v_1, v_2, \dots, v_K$ ，每次点击计费为 $p_1, p_2, \dots, p_K$ 。

在 GSP 下，排名 i 的广告主获得第 i 个广告位，出价为 $b_i$ ，实际每次点击计费为下一名的出价，总计费 $P_i^G=a_i b_{i+1}$ ，总收益为 $a_i (v_i - b_{i+1})$
在 VCG 下，排名 i 的广告主仍获得第 i 个广告位，但其计费与 GSP 不同：
- 对于排名第 $i=\min\{N, K\}$ 位广告主，如果 $K > N$ ，则其总计费为 $P_i^V = a_N b_{N+1}$ ，如果 $K \le N$ ，则其计费为 0
- 对于排名第 $i < \min\{N,K\}$ 位广告主，其计费为 $P_i^V = (a_i - a_{i+1}) b_{i+1} + P_{i+1}^V$
以上面的例子代入计算， $P_2^V=a_2 b_3 = 350$ ， $P_1^V=(a_1 - a_2) b_2 + P_2^V = 240 + 350 = 590$ ，与我们上面的结果是一致的。

这里可以证明，在广告主出价相同的情况下，使用 GSP 机制对任意广告主的扣费大于等于使用 VCG 机制的扣费，反过来 GSP 机制下广告平台的收益也大于等于 VCG 机制下的收益。证明如下：

对于排名第 $i=\min\{N, K\}$ 位广告主，GSP 和 VCG 计费是一样的。如果 $K > N$ ，则其总计费为 $P_i^V = a_N b_{N+1}$ ，如果 $K \le N$ ，则其计费为 0
对于排名第 $i < \min\{N,K\}$ 位广告主， $P_i^V - P_{i+1}^V = (a_i - a_{i+1}) b_{i+1} \le a_i b_{i+1} - a_{i+1} b_{i+2} = P_{i}^G - P_{i+1}^G$ 。

由上述两点可得 $P_i^G \ge P_i^V$ 对于任意 $i \in [1, \min\{N, K\}]$ 成立，GSP 机制下广告平台的收益大于等于 VCG 机制下的收益。

Nash Enquilibrium

在 GSP 机制下能够达到纳什均衡，即任一广告主竞价位置确定下来之后都没有动力单方面去改变他们当前的竞价位置，一个例子：假设只有一个位置，AB 两个广告主参与竞价，AB 的点击价值分别是 20 和 10，出价集合 $\{11, 10\}$ 就构成了一个纳什均衡点，此时 A 赢得竞价，B 没有动力去提高报价获得这个位置（B 要赢报价需超过 11，此时是亏损的），A 也没有动力去放弃这个位置（A 此时是盈利的）。

对 GSP 下纳什均衡的数学化描述，假设 GSP 的一个纳什均衡点 $E(b)=\{b_1, b_2, \dots, b_K\}$ ，其中任意 $b_i$ 满足：

对于任意 $m \in [1, i)$ ， $(v_i - b_{i+1}) a_i \ge (v_i - b_{m}) a_m$
对于任意 $n \in (i, \min\{N, K\}]$ ， $(v_i - b_{i+1}) a_i \ge (v_i - b_{n+1}) a_n$

即所有广告主都没有动力通过提高竞价去抢占一个更靠前的位置，也没有动力通过调低竞价去获得一个更靠后的位置，竞价位置达到均衡态。

Locally Envy Free enquilibrium

此时虽然达到纳什均衡点，但此时的报价序列并不是稳定的。根据上面的定义 GSP 下的纳什均衡实际上是竞价位置的均衡，而不是竞价序列的均衡；在满足纳什均衡（不改变竞价排位）下广告主仍有调整 bid 出价的空间，通过调整竞价进而损失竞争对手利益。比如一个位置，AB 两个广告主参与竞价，AB 的点击价值分别是 20 和 10，出价集合 $\{100, 1\}$ 构成一个纳什均衡点，A 赢得竞价，此时 B 会有动力通过调高自己的出价，不是为了赢下竞价，而是为了提高 A 的计费进而损害 A 的利益。此时 A 看到 B 调高出价，会害怕 B 调到 20 以上（超过 A 的点击价值），会将自己的出价调低。在这个例子中，竞价位置是稳定的，但竞价序列却是不稳定的。

那么在 GSP 中存不存在竞价序列稳定的均衡呢？答案是存在的，在 GSP 一个纳什均衡点中，如果所有人无法通过和他的前一名交换 bid 而获得更多收益，此时竞价序列处于稳定的均衡，我们将这种竞价序列稳定的均衡称为局部无嫉妒均衡（Locally Envy Free enquilibrium, LEF）。对 LEF 进行数学化描述，假设 GSP 的一个纳什均衡点 $E(b)=\{b_1, b_2, \dots, b_K\}$ ,对于任意 $i \in [1,\min\{N,K\}]$ ，满足

(v_{i} - b_{i + 1}) a_{i} \geq (v_{i} - b_{i}) a_{i - 1}

$(v_i - b_{i+1}) a_i \ge (v_i - b_i)a_{i-1}$

由于 LEF 是一个纳什均衡，由上面对纳什均衡的描述可得对于任意 $n \in (i, \min\{N, K\}]$ ， $(v_i - b_{i+1}) a_i \ge (v_i - b_{n+1}) a_n$ ，另 $n = i + 1$ 代入可得

(v_{i} - b_{i + 1}) a_{i} \geq (v_{i} - b_{i + 2}) a_{i + 1}

$(v_i - b_{i+1}) a_i \ge (v_i - b_{i+2}) a_{i+1}$

由上面两式可得对于任意 $i,j \in [1, \min\{N,K\}]$ ，满足 $(v_i - b_{i+1})a_i \ge (v_i - b_{j+1})a_j$ ，以 $p_i$ 表示广告主 i 的付费即

(v_{i} - p_{i}) a_{i} \geq (v_{i} - p_{j}) a_{j}

$(v_i - p_i)a_i \ge (v_i - p_j)a_j$

上式表示，任一广告主 i 与任一广告主 j 交换 bid，都不会获得比他当前位置 i 更好的收益，i 和 j 反过来也是成立的，因此 LEF 也称为对称纳什均衡（symmetric Nash Equilibrium, SNE）[TODO]。

LEF 的性质

对于所有 $i$ ， $v_{i-1} \ge v_i$

由 LEF 性质可知：

$(a_i - a_j)v_i \ge p_i a_i - p_j a_j$ $(a_j - a_i)v_j \ge p_j a_j - p_i a_i$

两式两边分别相加得到：

$(a_i - a_j)(v_i - v_j) \ge 0$

上式可得 $a_i - a_j$ 和 $v_i - v_j$ 同号，由 $a_{i-1} \ge a_i$ 可得 $v_{i-1} \ge v_i$ 。这里也可以看出在 LEF 下，具有更高价值的广告会被分配到点击率更高的位置，是一种高效的分配方式。
LEF 下 bid 的上下界

由于在 LEF 下位于 $i$ 的广告主没有动力通过降低出价拿到 $i+1$ 的名次 $(v_i - p_i) a_i \ge (v_i - p_{i+1}) a_{i+1}$ ，位于 $i+1$ 的广告主同样没有动力通过提高出价拿到 $i$ 名次， $(v_{i+1} - p_{i+1}) a_{i+1} \ge (v_{i+1} - p_i) a_i$ ，综合两个式子可得

$v_i(a_{i} - a_{i+1}) + p_{i+1}a_{i+1} \ge p_i a_i \ge v_{i+1}(a_i - a_{i+1}) + p_{i+1} a_{i+1}$

将 $p_i = b_{i+1}$ 代入得

$v_i(a_{i} - a_{i+1}) + b_{i+2}a_{i+1} \ge b_{i+1} a_i \ge v_{i+1}(a_i - a_{i+1}) + b_{i+2} a_{i+1}$

等同于

$v_{i-1}(a_{i-1} - a_{i}) + b_{i+1}a_{i} \ge b_{i} a_{i-1} \ge v_{i}(a_{i-1} - a_{i}) + b_{i+1} a_{i}$

可以定义 $\lambda_i = \frac{a_{i}}{a_{i-1}} < 1$ ，得

$(1 - \lambda_i) v_{i-1} + \lambda_i b_{i+1} \ge b_{i} \ge (1-\lambda_i)v_{i} + \lambda_i b_{i+1}$

可以得到 LEF 下第 $i$ 位置的 bid 上界为 $(1 - \lambda_i) v_{i-1} + \lambda_i b_{i+1}$ ，下界为 $(1-\lambda_i)v_{i} + \lambda_i b_{i+1}$ 。上界是上个位置广告 value 和下个位置 bid 的线性组合，下界是本位置广告 value 和下个位置 bid 的线性组合，线性组合权重由本位置和前个位置的点击率决定。

当取下界时， $b_i^* a_{i-1} = v_{i}(a_{i-1} - a_{i}) + b_{i+1} a_{i}$ 时，转化可得 $(v_i - b_i^*) a_{i-1} = (v_i - b_{i+1}) a_i$ ，等式右边表示 $i$ 位置广告主此时的收益，等式左边表示 $i$ 位置广告主调高 bid 刚刚好超过上一名 $i-1$ ，拿到 $i-1$ 位置时的收益，左右相等表示：位于 i 位置的广告主刚刚好超过上一名，且利益仍保持不变时 $i$ 的 bid 即为 $b_i$ 下界。

当取上界时， $b_i^*a_{i-1} = v_{i-1}(a_{i-1} - a_{i}) + b_{i+1}a_{i}$ ，转化可得 $(v_{i-1} - b_{i+1}) a_i = (v_{i-1} - b_i) a_{i-1}$ ，等式右边表示上一名 $i-1$ 广告主此时的收益，等式左边表示上一名 $i-1$ 广告主下探 bid 刚刚好低于 $i$ 广告，拿到 $i$ 位置时的收益，左右相等表示：位于 $i-1$ 位置的广告主刚刚好下降一名，且其利益仍保持不变时 $i$ 的 bid 即为 $b_i$ 的上界。

LEF 的构造

对于一个 GSP 博弈，我们可以直接构造出一个特殊的 LEF。假设所有广告主按照各自广告价值（每点击收益）进行排序，即如果 $i < j$ ，则 $v_i > v_j$ 。第一个广告主 bid 设为 $b_1^* = v_1$ ，对于广告主 $i \in [2, \dots, \min\{N+1, K\}]$ ， $bid_i^* = \frac{P^V_{i-1}}{a_{i-1}}$ ，其中 $P^V_{i-1}$ 是在 VCG 机制下，所有广告主采用占优策略时第 $i - 1$ 个广告主的总扣费。

这样构造出来的序列首先出价序列是递增的，即 $b_1 > b_2 > \dots > b_K$ ，同时对于任意位置的广告主，他在当前位置的收益刚好等于与上一名互换 bid 时的收益，根据 LEF 定义可知这个出价序列刚好构成一个 LEF。这个出价序列中每个广告主的收费与在 VCG 机制下所有广告主采用占优策略下的收费是一致的，因此广告平台的收益也与 VCG 机制下占优策略均衡是一致的。同时上面构造的 LEF 均衡，是 GSP 所有 LEF 均衡中广告主整体收益最佳（广告平台收益最差的）的均衡。因此即便是最差的 LEF 均衡，也至少达到了 VCS 占优策略均衡下的收益。

竞价机制总结

互联网广告竞价机制经历了从 GFP 到 GSP/VCG 的演变，相较而言目前 GSP 更为主流（谷歌、雅虎、微软、百度、腾讯等），VCG 在 Facebook 有被应用。
GFP 机制依赖广告主自己的出价，广告主没有最佳的出价策略，会不断试探价格以最大化收益，会造成广告系统不稳定，损害广告系统收益。
二价拍卖和 VCG 机制均不依赖广告主自己的出价，在密封出价、只有一个竞标物（广告位）时，两者是等价的。在多个广告位时 GSP 和 VCG 有所差异：
- 在 VCG 下，truth-telling 是所有人的占优策略，所有人 truth-telling 构成 VCG 一个纳什均衡点；在 GSP 中所有人 truth-telling 并不是占优策略
- GSP 尽管不存在 truth-telling 的平衡，但是存在非常强条件的均衡，GSP 通常也能够达到稳定的状态
- GSP 对于广告系统的收益在最差情况下也比 VCG 机制所有人 truth-telling 下的收益要更好
- VCG 机制复杂，对于广告主来说较难理解，相比之下 GSP 规则较容易被广告主理解接受

Guibo Wang