关于「广告位拍卖:广义二价拍卖的均衡与 VCG」,《VCG 拍卖与社群激励》给出的定量结论是什么?

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

数据口径:书中以标注框区分已发表的证据、可运行的 Python 计算(16 段程序)、原典与作者的模型和假说;书中所有数据都是虚构或模拟的。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 1000, 1355, 200, 300, 605, 920

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 grid4,307; truthful profile among them: False
all equilibria4,307 revenue 605 .. 1355
efficient ranking3,106 revenue 605 .. 1355
efficient, no overbidding1,162 revenue 605 .. 1000
locally envy-free (SNE), no overbidding58 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

核心公式

\[T_k^{\text{VCG}} = \sum_{j \ge k} v_{j+1}\,(\alpha_j - \alpha_{j+1}), \qquad \alpha_{K+1} = 0 .\]
查看完整验算程序
# 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}")

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《机制设计、维克里—克拉克—格罗夫斯(VCG)拍卖与数字社群激励相容工程》第 3 章「广告位拍卖:广义二价拍卖的均衡与 VCG」(版本 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23836274

DOI: 10.5281/zenodo.23836274 · 阅读本章所在专著 · 5DL-B-050 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026050,
  author    = {Fan, Yafu},
  title     = {Mechanism Design, Vickrey–Clarke–Groves Auctions and Incentive-Compatible Community Engineering},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  doi       = {10.5281/zenodo.23836274},
  url       = {https://doi.org/10.5281/zenodo.23836274}
}

本书其他章节结论