5D Library › 机制设计、维克里—克拉克—格罗夫斯(VCG)拍卖与数字社群激励相容工程 · English

第三章 广告位拍卖:广义二价拍卖的均衡与 VCG

广告位拍卖

搜索结果页旁边有 KK 个广告位,位置越靠上,被点击的次数越多。标准模型假设位置 kk 每期带来 αk\alpha_k 次点击(α1>α2>⋯>αK\alpha_1 > \alpha_2 > \cdots > \alpha_K),与是谁的广告无关;广告主 ii 每次点击的价值为 viv_i,是他的私人信息。每个广告主只要一个位置。

广义二价拍卖(GSP):每人报一个每次点击的出价 bib_i,按出价从高到低排位;排在第 kk 位的人每次点击支付排在第 k+1k+1 位的人的出价。只有一个位置时,它就是维克里二价拍卖;多个位置时,它看起来像二价拍卖的自然推广,因此常被误认为也让说真话成为占优策略。实际使用中,排名与价格还要乘以广告质量或预估点击率;在点击率可分离(位置 kk 上广告 ii 的点击为 αkei\alpha_k e_i)的假设下,这不改变下面的结论,只改变记号 (Varian 2007)。

广告位的 VCG:按出价排位(与 GSP 相同),但第 kk 位的人支付他给下面所有人造成的点击损失:他若不在,第 k+1k+1 位以下的每个人都上移一位。按出价者估值从高到低编号,第 kk 位的总支付为

TkVCG=∑j≥kvj+1(αj−αj+1),αK+1=0.T_k^{\text{VCG}} = \sum_{j \ge k} v_{j+1}\,(\alpha_j – \alpha_{j+1}), \qquad \alpha_{K+1} = 0 .

说真话不是均衡

下面的程序取两个位置(每期 100 与 60 次点击)与三名出价者(每次点击价值 10、8、5)。VCG 下第 2 位的人每次点击付 5(他挤掉了出价者 3 的 60 次点击),第 1 位的人每次点击付 (8×40+5×60)/100=6.2(8 \times 40 + 5 \times 60)/100 = 6.2,总收入 920。在 GSP 中,若人人按估值出价,出价者 1 每次点击付 8,得 100×(10−8)=200100 \times (10 – 8) = 200;若他把出价降到 5 与 8 之间(例如 6),落到第 2 位,每次点击只付 5,得 60×(10−5)=30060 \times (10 – 5) = 300。所以说真话在 GSP 中不是占优策略,在这里连纳什均衡都不是。

程序随后在 0 到 12、步长 0.25 的出价网格上穷举所有纯策略纳什均衡(493=117,64949^3 = 117{,}649 种出价组合),并按爱德曼、奥斯特罗夫斯基与施瓦茨 (Edelman et al. 2007) 与瓦里安 (Varian 2007) 的定义筛出局部无嫉妒(瓦里安称为对称纳什)均衡:没有人愿意与排在自己上面一位的人以对方现在支付的价格互换位置。在这个例子中,这等价于

αk(vk−pk)≥αk−1(vk−pk−1),\alpha_k (v_k – p_k) \ge \alpha_{k-1}(v_k – p_{k-1}),

其中 pkp_k 是第 kk 位每次点击的价格;对落选者也要求他不愿以第 2 位的价格挤进去。

推导

# Chapter 3. Position auction with 2 slots (clicks 100 and 60) and 3 bidders with
# values per click 10, 8, 5. GSP: rank by bid, the slot-k winner pays the (k+1)-th bid
# per click. VCG: each winner pays the click-externality he imposes. We enumerate all
# pure Nash equilibria of GSP on a bid grid 0..12 (step 0.25; ties go to the lower
# index), check truthful bidding, and compare revenues with the locally envy-free
# ("symmetric") equilibria of Edelman-Ostrovsky-Schwarz and Varian.
import itertools

ALPHA, V = (100.0, 60.0), (10.0, 8.0, 5.0)
GRID = [x / 4 for x in range(49)]

def rank(b):
    return sorted(range(3), key=lambda i: (-b[i], i))

def gsp(b):
    r = rank(b); u = [0.0] * 3; rev = 0.0
    for k in range(2):
        i, price = r[k], b[r[k + 1]]
        u[i] = ALPHA[k] * (V[i] - price); rev += ALPHA[k] * price
    return u, rev, r

def best_response_value(i, b):
    others = sorted(((b[j], j) for j in range(3) if j != i), key=lambda t: (-t[0], t[1]))
    best = 0.0                                           # option: lose (bid 0 loses
    for k in range(2):                                   # unless all bid 0; ignore)
        above = others[k - 1] if k > 0 else None         # need to beat others[k]
        target = others[k]
        bids = [g for g in GRID if (g > target[0] or (g == target[0] and i < target[1]))
                and (above is None or g < above[0] or (g == above[0] and i > above[1]))]
        if bids:
            best = max(best, ALPHA[k] * (V[i] - target[0]))
    return best

def vcg():
    p2 = V[2]                                            # slot 2 displaces bidder 3
    p1 = (V[1] * (ALPHA[0] - ALPHA[1]) + p2 * ALPHA[1]) / ALPHA[0]
    return p1, p2

if __name__ == "__main__":
    p1, p2 = vcg()
    print(f"VCG prices per click: slot 1 {p1:.2f}, slot 2 {p2:.2f};"
          f" revenue {ALPHA[0] * p1 + ALPHA[1] * p2:.0f}")
    u, rev, _ = gsp(V)
    print(f"GSP, all bid their values: revenue {rev:.0f}; bidder 1 earns {u[0]:.0f},"
          f" bidding 6 (slot 2) {ALPHA[1] * (V[0] - V[2]):.0f}")
    ne = []
    for b in itertools.product(GRID, repeat=3):
        u, rev, r = gsp(b)
        if all(u[i] >= best_response_value(i, b) - 1e-9 for i in range(3)):
            ne.append((b, rev, r))
    eff = [x for x in ne if x[2][:2] == [0, 1]]
    noover = [x for x in eff if all(x[0][i] <= V[i] for i in range(3))]
    def envy_free(b, r):
        price = [b[r[1]], b[r[2]]]                     # no one envies the slot above
        return (ALPHA[1] * (V[r[1]] - price[1]) >= ALPHA[0] * (V[r[1]] - price[0]) - 1e-9
                and 0.0 >= ALPHA[1] * (V[r[2]] - price[1]) - 1e-9)
    sne = [x for x in noover if envy_free(x[0], x[2])]
    print(f"pure Nash equilibria on the grid: {len(ne):,}; truthful profile among them:"
          f" {any(x[0] == V for x in ne)}")
    for lab, s in (("all equilibria", ne), ("efficient ranking", eff),
                   ("efficient, no overbidding", noover),
                   ("locally envy-free (SNE), no overbidding", sne)):
        rv = [x[1] for x in s]
        print(f"  {lab:40s} {len(s):6,d}   revenue {min(rv):6.0f} .. {max(rv):6.0f}")
    lo = min(sne, key=lambda x: x[1])
    print(f"  lowest grid SNE: bids {lo[0]}, revenue {lo[1]:.0f}"
          f" (VCG price {p1:.2f} is off the grid)")
    lo1 = (V[1] * (ALPHA[0] - ALPHA[1]) + V[2] * ALPHA[1]) / ALPHA[0]
    hi1 = (V[0] * (ALPHA[0] - ALPHA[1]) + V[2] * ALPHA[1]) / ALPHA[0]
    print(f"  SNE bounds (Varian), slot-2 price {V[2]:.0f}: slot-1 price {lo1:.2f} .."
          f" {hi1:.2f}, revenue {ALPHA[0] * lo1 + ALPHA[1] * V[2]:.0f} .."
          f" {ALPHA[0] * hi1 + ALPHA[1] * V[2]:.0f}")
# VCG prices per click: slot 1 6.20, slot 2 5.00; revenue 920
# GSP, all bid their values: revenue 1100; bidder 1 earns 200, bidding 6 (slot 2) 300
# pure Nash equilibria on the grid: 4,307; truthful profile among them: False
#   all equilibria                            4,307   revenue    605 ..   1355
#   efficient ranking                         3,106   revenue    605 ..   1355
#   efficient, no overbidding                 1,162   revenue    605 ..   1000
#   locally envy-free (SNE), no overbidding      58   revenue    925 ..   1000
#   lowest grid SNE: bids (6.25, 6.25, 5.0), revenue 925 (VCG price 6.20 is off the grid)
#   SNE bounds (Varian), slot-2 price 5: slot-1 price 6.20 .. 7.00, revenue 920 .. 1000

网格上有 4,307 个纯策略纳什均衡,其中 1,201 个的排位不是有效的(估值高的人排在了估值低的人后面),均衡收入从 605 到 1,355 不等;排除高于自己估值的出价后,有效均衡的收入从 605 到 1,000。再加上局部无嫉妒条件,只剩 58 个,收入从 925 到 1,000。理论上,局部无嫉妒均衡中第 2 位的价格为 5,第 1 位的价格在 6.20 与 7.00 之间,收入在 920 与 1,000 之间:下界恰好是 VCG 的收入,网格上 6.20 不可达,所以最低的网格均衡是 925。

证据

爱德曼、奥斯特罗夫斯基与施瓦茨证明 (Edelman et al. 2007):GSP 中说真话一般不是均衡;存在一个局部无嫉妒均衡,其位置分配与每人的支付恰好等于 VCG 的结果;在任何局部无嫉妒均衡中,拍卖方的收入都不低于 VCG。他们还证明,与之对应的「广义英式拍卖」(价格逐步上升、出价者选择退出时点)(在其限定的策略类中)有唯一的完美贝叶斯均衡,其结果与 VCG 相同。瓦里安独立给出了对称纳什均衡的不等式刻画与收入上下界 (Varian 2007)。福田等人在实验室中比较了 GSP 与 VCG,两种规则的收入与效率相近,与理论预测一致 (Fukuda et al. 2013)。

随机实例:收入比较

上面只是一个例子。下面的程序随机生成 20,000 个实例(6 名出价者、4 个位置、点击率按 dk−1d^{k-1} 递减、估值服从 [0,1] 均匀分布),分别计算 VCG 收入(即最低的局部无嫉妒均衡)、最高的局部无嫉妒均衡收入(落选者出价等于其估值,瓦里安的递推 pkαk=vk(αk−αk+1)+pk+1αk+1p_k\alpha_k = v_k(\alpha_k – \alpha_{k+1}) + p_{k+1}\alpha_{k+1})、以及人人说真话时的 GSP 收入,并检查说真话是否为均衡。程序还用上面的 VCG 公式独立核对了递推结果。

推导

# Chapter 3. Random position auctions: n = 6 bidders, K = 4 slots, click rates
# alpha_k = d^(k-1), values per click i.i.d. U[0,1]. Per instance we compute
#   VCG revenue  (= revenue of the lowest locally envy-free equilibrium of GSP, EOS 2007)
#   upper SNE    (Varian 2007: p_k a_k = v_k (a_k - a_k+1) + p_k+1 a_k+1, p_K = v_K+1)
#   GSP with everyone bidding his value, and whether that profile is a Nash equilibrium.
import math, random, statistics

def instance(rng, n=6, K=4, d=0.7):
    a = [d ** k for k in range(K)] + [0.0]
    v = sorted((rng.random() for _ in range(n)), reverse=True)
    lo = [0.0] * (K + 1); hi = [0.0] * (K + 1)
    lo[K - 1] = hi[K - 1] = v[K]                       # price per click of slot K
    for k in range(K - 2, -1, -1):
        lo[k] = (v[k + 1] * (a[k] - a[k + 1]) + lo[k + 1] * a[k + 1]) / a[k]
        hi[k] = (v[k] * (a[k] - a[k + 1]) + hi[k + 1] * a[k + 1]) / a[k]
    vcg = math.fsum(a[k] * lo[k] for k in range(K))
    up = math.fsum(a[k] * hi[k] for k in range(K))
    truth = math.fsum(a[k] * v[k + 1] for k in range(K))
    # truthful GSP: can bidder k (slot k) gain by moving to a lower slot j > k?
    dev = 0
    for k in range(K):
        u = a[k] * (v[k] - v[k + 1])
        if any(a[j] * (v[k] - v[j + 1]) > u + 1e-12 for j in range(k + 1, K)):
            dev += 1
    # direct VCG formula as a check: slot k pays sum_j>=k v_j+1 (a_j - a_j+1)
    chk = math.fsum(math.fsum(v[j + 1] * (a[j] - a[j + 1]) for j in range(k, K))
                    for k in range(K))
    return vcg, up, truth, dev, chk

if __name__ == "__main__":
    rng = random.Random(2007)
    for d in (0.9, 0.7, 0.5):
        R = [instance(rng, d=d) for _ in range(20000)]
        assert all(abs(r[0] - r[4]) < 1e-9 for r in R)
        print(f"click decay d = {d}: 20,000 instances")
        print(f"  mean revenue: VCG {statistics.fmean(r[0] for r in R):.4f},"
              f" upper SNE {statistics.fmean(r[1] for r in R):.4f},"
              f" GSP truthful {statistics.fmean(r[2] for r in R):.4f}")
        print(f"  upper SNE / VCG {statistics.fmean(r[1] / r[0] for r in R):.3f};"
              f" truthful GSP / VCG {statistics.fmean(r[2] / r[0] for r in R):.3f};"
              f" min truthful/VCG {min(r[2] / r[0] for r in R):.3f}")
        print(f"  truthful bidding is a GSP equilibrium in"
              f" {sum(r[3] == 0 for r in R) / len(R):.1%} of instances;"
              f" mean deviators {statistics.fmean(r[3] for r in R):.2f}")
# click decay d = 0.9: 20,000 instances
#   mean revenue: VCG 1.1116, upper SNE 1.1866, GSP truthful 1.7848
#   upper SNE / VCG 1.100; truthful GSP / VCG 1.857; min truthful/VCG 1.012
#   truthful bidding is a GSP equilibrium in 0.0% of instances; mean deviators 2.86
# click decay d = 0.7: 20,000 instances
#   mean revenue: VCG 1.0331, upper SNE 1.1993, GSP truthful 1.4195
#   upper SNE / VCG 1.201; truthful GSP / VCG 1.436; min truthful/VCG 1.007
#   truthful bidding is a GSP equilibrium in 0.2% of instances; mean deviators 2.33
# click decay d = 0.5: 20,000 instances
#   mean revenue: VCG 0.9478, upper SNE 1.1445, GSP truthful 1.1444
#   upper SNE / VCG 1.244; truthful GSP / VCG 1.225; min truthful/VCG 1.003
#   truthful bidding is a GSP equilibrium in 4.2% of instances; mean deviators 1.63

三点结论。第一,说真话几乎从不是 GSP 的均衡:点击率衰减较慢(d=0.9d = 0.9)时,20,000 个实例中没有一个;d=0.5d = 0.5 时也只有 4.2%;平均有 1.63—2.86 名出价者想往下挪。第二,局部无嫉妒均衡的收入区间相当宽:最高的那个平均比 VCG 高 10.0%—24.4%。第三,「人人说真话的 GSP」的收入总是高于 VCG(最低也高 0.3%),在 d=0.9d = 0.9 时平均高 85.7%,但这只是一个非均衡的参照点;它常被用来说明「GSP 比 VCG 赚得多」,这是一个不成立的比较。

左:示例中 GSP 的纯纳什均衡收入分布(灰色)、局部无嫉妒均衡的收入区间(阴影,920—1,000)、VCG 收入(实线)与人人说真话时的收入(虚线)。右:随机实例中最高局部无嫉妒均衡与「说真话的 GSP」的平均收入(以 VCG 为 1)随点击率衰减的变化。

为什么平台用 GSP

如果 GSP 在局部无嫉妒均衡中最多只是「VCG 或略高」,为什么平台长期使用它?常见的解释包括:它容易向广告主解释(「你付下一名的出价」);它在历史上先于 VCG 被采用,切换有成本;在均衡的选择偏向较高收入时,它可能比 VCG 收入更高 (Edelman et al. 2007; Varian and Harris 2014)。这些解释大多是关于历史与组织的,不是定理。2019 年 9 月,谷歌宣布把 Ad Manager 的程序化展示广告改为统一的一价拍卖 (Bigler 2019);这一变化涉及的是展示广告,公告没有说到搜索广告,本书只作注,不推断它对搜索广告的含义。

注

均衡选择问题。 局部无嫉妒是一种均衡精炼,不是参与者必然到达的状态。示例中有 4,307 个纳什均衡,其中只有 58 个局部无嫉妒;第 32 本讨论过学习与推荐中的动态,那里的结论提醒我们:反复竞价中的学习过程会停在哪里,取决于学习规则。说「GSP 的收入不低于 VCG」时,应当加上「在局部无嫉妒均衡中」。

假说 · 尚未验证 · 达人投放中的排位竞价

作者的假说(尚未确立): 在按「下一名出价」收费的达人排位推荐中,出价者的报价会随经验向局部无嫉妒均衡的下界(VCG 结果)收敛,而不是停在说真话的出价上。什么样的结果能证明它是错的: 在独立平台或实验室事先登记的重复竞价中,后半段轮次的出价与 VCG 下界的平均距离不小于前半段,或者如实出价的比例随轮次上升。第八章的实验可以检验后一种情形。

本章小结

在广告位拍卖中,GSP 按下一名的出价收费,看起来像二价拍卖,但说真话一般不是均衡:示例中第 1 名下移到第 2 名可从 200 增到 300,随机实例中说真话为均衡的比例只有 0.0%—4.2%。局部无嫉妒均衡的收入介于 VCG 与一个上界之间(示例中 920 到 1,000),最低者恰好等于 VCG 的结果;「GSP 收入不低于 VCG」只在这类均衡中有保证;其他纳什均衡的收入可以低到 605,也可以高于 VCG(最高 1,355)。实验室证据显示两种规则的收入与效率相近。

参考文献

Bigler, Jason. 2019. Rolling out First Price Auctions to Google Ad Manager Partners. Google, The Keyword (company blog), 5 September 2019.
Edelman, Benjamin, Michael Ostrovsky, and Michael Schwarz. 2007. “Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords.” American Economic Review 97 (1): 242–59.
Fukuda, Emiko, Yoshio Kamijo, Ai Takeuchi, Michiharu Masui, and Yukihiko Funaki. 2013. “Theoretical and Experimental Investigations of the Performance of Keyword Auction Mechanisms.” RAND Journal of Economics 44 (3): 438–61. https://doi.org/10.1111/1756-2171.12026.
Varian, Hal R. 2007. “Position Auctions.” International Journal of Industrial Organization 25 (6): 1163–78.
Varian, Hal R., and Christopher Harris. 2014. “The VCG Auction in Theory and Practice.” American Economic Review 104 (5): 442–45.

Fan, Y. (2026). Mechanism Design, Vickrey–Clarke–Groves Auctions and Incentive-Compatible Community Engineering: From Myerson's Optimal Auction and the Hurwicz Impossibility Theorem to Sybil-Resistant Reputation Games, Read Beside Classical Legalist Treatises on Rewards and Incentives [机制设计、维克里—克拉克—格罗夫斯(VCG)拍卖与数字社群激励相容工程] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23836274 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).