关于「广告位拍卖:广义二价拍卖的均衡与 VCG」,《VCG 拍卖与社群激励》给出的定量结论是什么?
结论:在广告位拍卖中,GSP 按下一名的出价收费,看起来像二价拍卖,但说真话一般不是均衡:示例中第 1 名下移到第 2 名可从 200 增到 300,随机实例中说真话为均衡的比例只有 0.0%—4.2%。局部无嫉妒均衡的收入介于 VCG 与一个上界之间(示例中 920 到 1,000),最低者恰好等于 VCG 的结果;「GSP 收入不低于 VCG」只在这类均衡中有保证;其他纳什均衡的收入可以低到 605,也可以高于 VCG(最高 1,355)。实验室证据显示两种规则的收入与效率相近。
数据口径:书中以标注框区分已发表的证据、可运行的 Python 计算(16 段程序)、原典与作者的模型和假说;书中所有数据都是虚构或模拟的。
对照数据表
下表数字由本章 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 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 |
核心公式
\[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}
}