5D Library › 机制设计、维克里—克拉克—格罗夫斯(VCG)拍卖与数字社群激励相容工程 · English
第二章 多物品 VCG:外部性定价、核心与假名竞价
从二价拍卖到 VCG
单件物品的维克里二价拍卖中,最高出价者获胜,支付第二高的出价 (Vickrey 1961)。第 27 本已经用程序验证它使如实出价成为弱占优策略。它的推广是维克里—克拉克—格罗夫斯(VCG)机制 (Clarke 1971; Groves 1973):参与者报告估值函数 ,机制选择使报告的总福利最大的结果
并向每个参与者收取他给别人造成的外部性:
第一项是「如果 不在,其他人能得到的最大福利」,第二项是「 在场时其他人实际得到的福利」。二价拍卖是它的特例:获胜者不在时,第二高出价者会得到物品,所以获胜者支付的是第二高出价。
为什么说真话是占优策略。 参与者 的效用为 。最后一项与他的报告无关;第一项是「以他的真实估值计算的总福利」,而机制按他的报告最大化总福利。所以无论别人报告什么,他如实报告时机制恰好替他最大化了方括号中的量,任何误报只会让机制选到一个对方括号更差(至多相同)的结果。这就是格罗夫斯的论证;任何形如 的支付都有同样的性质,上式中的 取「 不在时的最大福利」,称为克拉克枢纽规则,它保证支付非负、参与者不会亏本(估值非负时)。
第 27 本已经讨论过 VCG 的三个弱点,这里只回顾:收入可能为零(两件物品分别给两个只要单件的人,即使另有人对整套出价不低:只要整套出价不高于任一单件出价,收入就是零);增加出价者可能使收入下降;落败者可以合谋:几个本来会落败的人各自抬高单件出价,自己变成胜者,而每人只付很低甚至为零的价格。本章讨论另外两个问题:VCG 的结果可能不在核心中,以及它不能抵抗假名竞价。
一个组合拍卖
下面的程序有三件物品 A、B、C 与五名出价者,出价为「异或」形式(每人最多赢得自己报出的一个组合):出价者 1 对 A 出 6、对 AB 出 10;出价者 2 对 B 出 5、对 BC 出 9;出价者 3 对 C 出 4;出价者 4 对 ABC 出 13;出价者 5 对 AC 出 8。程序穷举所有可行分配求出有效分配与 VCG 支付,然后随机生成 20,000 个误报(把某人的出价整体放大或缩小,或换成随机的组合与金额),检查有没有人能从误报中获利;最后检查核心约束。
推导
# Chapter 2. VCG in a small combinatorial (package) auction: items A, B, C; XOR bids
# (each bidder wins at most one of his packages). Efficient allocation by brute force,
# VCG payment = externality = W(others | i absent) - W(others | i present). Then:
# (1) a search for profitable misreports (random rescalings and random XOR bids);
# (2) the core: the seller and any coalition of losers must not be able to block, i.e.
# for every set S of winners, sum_{i in S} p_i >= W(N \ S) - sum_{j in W\S} b_j;
# we report the largest violation and the minimum-revenue core payments (vertex
# enumeration of the small linear programme, Day-Milgrom style).
import itertools, random
ITEMS = "ABC"
BIDS = {1: {"A": 6, "AB": 10}, 2: {"B": 5, "BC": 9}, 3: {"C": 4},
4: {"ABC": 13}, 5: {"AC": 8}}
def best(bids, who):
"""max welfare and allocation over bidders in `who` (XOR bids)."""
who = sorted(who); top = (0.0, {})
def rec(k, used, val, alloc):
nonlocal top
if k == len(who):
if val > top[0] + 1e-12:
top = (val, dict(alloc))
return
rec(k + 1, used, val, alloc) # bidder gets nothing
for pkg, b in bids[who[k]].items():
if not set(pkg) & used:
alloc[who[k]] = pkg
rec(k + 1, used | set(pkg), val + b, alloc)
del alloc[who[k]]
rec(0, set(), 0.0, {})
return top
def vcg(bids):
W, alloc = best(bids, bids)
pay = {}
for i in alloc:
others = W - bids[i][alloc[i]]
pay[i] = best(bids, [j for j in bids if j != i])[0] - others
return W, alloc, pay
def solve(M, y): # small Gauss-Jordan
n = len(y); A = [row[:] + [v] for row, v in zip(M, y)]
for c in range(n):
p = max(range(c, n), key=lambda r: abs(A[r][c]))
if abs(A[p][c]) < 1e-12:
return None
A[c], A[p] = A[p], A[c]
for r in range(n):
if r != c:
f = A[r][c] / A[c][c]; A[r] = [x - f * z for x, z in zip(A[r], A[c])]
return [A[i][n] / A[i][i] for i in range(n)]
def core(bids, alloc):
win = sorted(alloc); cons = [] # rows: (coefficients, rhs)
for r in range(1, len(win) + 1):
for S in itertools.combinations(win, r):
rest = sum(bids[j][alloc[j]] for j in win if j not in S)
rhs = best(bids, [j for j in bids if j not in S])[0] - rest
cons.append(([1.0 if i in S else 0.0 for i in win], rhs))
for k, i in enumerate(win): # 0 <= p_i <= bid
e = [0.0] * len(win); e[k] = 1.0
cons.append((e, 0.0)); cons.append(([-x for x in e], -bids[i][alloc[i]]))
top = None
for rows in itertools.combinations(cons, len(win)):
p = solve([r[0] for r in rows], [r[1] for r in rows])
if p and all(sum(a * x for a, x in zip(c, p)) >= b - 1e-9 for c, b in cons):
if top is None or sum(p) < sum(top) - 1e-9:
top = p
return win, cons, top
if __name__ == "__main__":
W, alloc, pay = vcg(BIDS)
print(f"efficient welfare {W:.1f}; allocation {alloc}")
for i in sorted(alloc):
print(f" bidder {i}: wins {alloc[i]:3s} bid {BIDS[i][alloc[i]]:4.1f},"
f" VCG payment {pay[i]:4.1f}, surplus {BIDS[i][alloc[i]] - pay[i]:4.1f}")
print(f" VCG revenue {sum(pay.values()):.1f}")
rng = random.Random(1); gain = -1e9; tries = 0
for i in BIDS:
for _ in range(4000):
fake = dict(BIDS)
if rng.random() < 0.5:
f = rng.uniform(0, 2); fake[i] = {k: v * f for k, v in BIDS[i].items()}
else:
pk = rng.sample(["A", "B", "C", "AB", "AC", "BC", "ABC"],
rng.randint(1, 3))
fake[i] = {k: rng.uniform(0, 15) for k in pk}
_, al, py = vcg(fake); tries += 1
true_val = BIDS[i].get(al.get(i, ""), 0.0) if i in al else 0.0
if i in al and al[i] not in BIDS[i]: # XOR: value of best sub-package
true_val = max([v for k, v in BIDS[i].items() if set(k) <= set(al[i])],
default=0.0)
u_true = (BIDS[i][alloc[i]] - pay[i]) if i in alloc else 0.0
gain = max(gain, (true_val - py.get(i, 0.0)) - u_true)
print(f"misreport search: {tries:,} misreports, largest gain {gain:+.4f}")
win, cons, low = core(BIDS, alloc)
viol = max(b - sum(a * pay[i] for a, i in zip(c, win)) for c, b in cons)
print(f"core: {len(cons)} constraints; largest violation by VCG payments {viol:.1f}")
R = sum(low); near = None
for a in range(0, 201): # VCG-nearest point, sum = R
for b in range(0, 201):
p = [a * 0.05, b * 0.05, R - a * 0.05 - b * 0.05]
if all(sum(x * y for x, y in zip(c, p)) >= r - 1e-9 for c, r in cons):
dist = sum((x - pay[i]) ** 2 for x, i in zip(p, win))
if near is None or dist < near[0] - 1e-12:
near = (dist, p)
print(f" minimum core revenue {R:.1f} (= losing bidder 4's bid for ABC);"
f" VCG revenue {sum(pay.values()):.1f}")
print(" VCG-nearest minimum-revenue core payments: " +
", ".join(f"bidder {i} {p:.2f}" for i, p in zip(win, near[1])))
# efficient welfare 15.0; allocation {1: 'A', 2: 'B', 3: 'C'}
# bidder 1: wins A bid 6.0, VCG payment 4.0, surplus 2.0
# bidder 2: wins B bid 5.0, VCG payment 4.0, surplus 1.0
# bidder 3: wins C bid 4.0, VCG payment 4.0, surplus 0.0
# VCG revenue 12.0
# misreport search: 20,000 misreports, largest gain +0.0000
# core: 13 constraints; largest violation by VCG payments 1.0
# minimum core revenue 13.0 (= losing bidder 4's bid for ABC); VCG revenue 12.0
# VCG-nearest minimum-revenue core payments: bidder 1 4.50, bidder 2 4.50, bidder 3 4.00有效分配是 A、B、C 分别给出价者 1、2、3,总福利 15(高于出价者 4 的 13 与「出价者 1 拿 AB、出价者 3 拿 C」的 14)。每人的 VCG 支付都是 4:例如出价者 1 不在时,最好的分配是「出价者 5 拿 AC、出价者 2 拿 B」或「出价者 4 拿 ABC」,福利 13;他在场时其他人得到 5 + 4 = 9,所以他造成的外部性是 13 − 9 = 4。三人的剩余分别为 2、1、0。20,000 次误报中最大的收益为 0:在这个例子里,误报无利可图,与上面的论证一致。
核心:卖家与落败者能否另做交易
VCG 的总收入是 12。可是出价者 4 对整套物品出了 13:卖家与出价者 4 可以撇开拍卖,以 12 到 13 之间的任何价格成交,双方都比拍卖结果更好。这样的结果称为不在核心中。形式地说,对于获胜者的任一子集 ,他们支付的总额必须不低于「把 排除后其余出价者能出的最高总额」减去「 以外的获胜者的出价」,否则卖家与 以外的人能结成一个更好的联盟。程序列出了 13 条约束,VCG 支付最多违反 1.0;满足所有核心约束的最低收入是 13,恰好等于落败者出价者 4 的出价;其中最接近 VCG 支付的点是 (4.5, 4.5, 4.0)。
证据
奥苏贝尔与米尔格罗姆把 VCG 称为「可爱但孤独」的拍卖:理论上漂亮,实践中极少使用 (Ausubel and Milgrom 2006)。他们说明,当出价者对拍卖方而言彼此是替代品(例如所有出价者都把物品看作替代品)时,VCG 的结果在核心中;有互补品时,VCG 的收入可能低得不合理,而且可能被落败者合谋或假名竞价操纵。戴与米尔格罗姆提出「选择核心的组合拍卖」:在核心中选择支付,以最小化出价者偏离如实出价的动机 (Day and Milgrom 2008)。代价是放弃占优策略激励相容:只有当 VCG 结果本身在核心中时,核心选择的拍卖才是防操纵的。罗特科普夫列举的十三条理由(含收入不足、合谋、隐私与计算难度)则从实践角度说明了为什么 VCG 很少被采用 (Rothkopf 2007);更早的罗特科普夫、泰斯伯格与卡恩讨论过「维克里拍卖为什么罕见」(Rothkopf et al. 1990)。
卢金—赖利整理过维克里拍卖在现实中的少数应用:十九世纪的邮票邮寄拍卖,以及网上拍卖中的「代理出价」(出价者给出上限,由系统按最小加价自动加价,效果近似二价拍卖)(Lucking-Reiley 2000)。瓦里安与哈里斯讨论了 VCG 在线上广告中的理论与实践 (Varian and Harris 2014)。这些都是单件物品或结构简单的情形;完整的组合 VCG 仍然罕见。
假名竞价:拍卖中的女巫攻击
在线上拍卖中,一个人可以用多个电子邮件地址注册多个身份。横尾、櫻井与松原把以多个身份出价称为假名竞价,并证明了三个结论 (Yokoo et al. 2004):第一,VCG 在没有假名时防操纵且有效,但它不防假名竞价;第二,不存在同时满足帕累托效率与防假名竞价的组合拍卖规则;第三,若剩余函数(任一组出价者能达到的最大福利 )对出价者满足「凹性」,即对任意 与不在 中的 ,有
则 VCG 是防假名竞价的。凹性的意思是「一个出价者的边际贡献在别人越多时越小」,这正是出价者之间互为替代品的情形。
下面的程序先算最经典的例子:两件物品 A、B,我对整套 AB 估值 10,对手对 AB 估值 8。如实出价时我赢得 AB,支付 8,剩余 2。若我注册两个假身份,一个只对 A 出价,一个只对 B 出价,各出 8:机制认为把 A、B 分给「两个人」的福利 16 高于对手的 8;每个假身份不在时,另一个假身份仍会拿到自己的物品,对手仍拿不到,于是每个假身份的外部性都是 0。我以 0 的总支付拿到了 AB,剩余从 2 升到 10。
随后程序在两类随机市场中重复这一检验:每个市场有一名可能作假的出价者与三名对手,假身份在 0 到 15 的网格上搜索最有利的单件出价。
推导
# Chapter 2. False-name (shill / Sybil) bids against VCG, two items A and B. Each bidder
# has XOR values (a, b, ab): for A alone, B alone, both. A manipulator may replace his
# one identity by two fake ones: X bids x for A only, Y bids y for B only. Yokoo,
# Sakurai and Matsubara (2004) show VCG is not false-name-proof and give a sufficient
# condition for it to be: concavity of the surplus function over bidders,
# W(S + i) - W(S) >= W(T + i) - W(T) for all S subset of T, i not in T.
import itertools, random
def welfare(bidders):
"""max over: one bidder takes AB, or A and B go to two different bidders."""
w = max([0.0] + [t[2] for t in bidders])
for i, s in enumerate(bidders):
for j, t in enumerate(bidders):
if i != j:
w = max(w, s[0] + t[1])
w = max(w, s[0], s[1])
return w
def outcome(bidders):
"""efficient allocation (labels per bidder) and VCG payments."""
W = welfare(bidders); best = None
for i, s in enumerate(bidders):
if abs(s[2] - W) < 1e-9: best = {i: "AB"}
for i, s in enumerate(bidders):
for j, t in enumerate(bidders):
if i != j and abs(s[0] + t[1] - W) < 1e-9 and best is None:
best = {i: "A", j: "B"}
if best is None and abs(max(s[0], s[1]) - W) < 1e-9:
best = {i: "A" if s[0] >= s[1] else "B"}
val = {"A": 0, "B": 1, "AB": 2}; pay = {}
for i, lab in best.items():
rest = bidders[:i] + bidders[i + 1:]
pay[i] = welfare(rest) - (W - bidders[i][val[lab]])
return best, pay
def gain_from_split(me, others, grid):
al, py = outcome([me] + others)
u0 = (me[{"A": 0, "B": 1, "AB": 2}[al[0]]] - py[0]) if 0 in al else 0.0
top = (0.0, None)
for x in grid:
for y in grid:
al, py = outcome([(x, 0.0, x), (0.0, y, y)] + others)
got = {al[k] for k in (0, 1) if k in al}
v = me[2] if got == {"A", "B"} else me[0] if got == {"A"} else \
me[1] if got == {"B"} else 0.0
u = v - py.get(0, 0.0) - py.get(1, 0.0)
if u - u0 > top[0] + 1e-9:
top = (u - u0, (x, y))
return top
def concave(bidders):
n = len(bidders); W = {}
for r in range(n + 1):
for S in itertools.combinations(range(n), r):
W[S] = welfare([bidders[k] for k in S])
for S, wS in W.items():
for T, wT in W.items():
if set(S) <= set(T):
for i in set(range(n)) - set(T):
if (W[tuple(sorted(S + (i,)))] - wS) < (W[tuple(sorted(T + (i,)))]
- wT) - 1e-9:
return False
return True
if __name__ == "__main__":
grid = [g * 1.0 for g in range(0, 16)]
me, rival = (0.0, 0.0, 10.0), (0.0, 0.0, 8.0)
al, py = outcome([me, rival])
g, xy = gain_from_split(me, [rival], grid)
print(f"classic case: I value AB at 10, a rival at 8. Truthful: I win AB, pay"
f" {py[0]:.1f}, utility {10 - py[0]:.1f}")
print(f" two fake identities bidding {xy[0]:.0f} for A and {xy[1]:.0f} for B:"
f" utility up {g:.1f} (fakes pay 0)")
rng = random.Random(2004)
print("600 random markets per domain (manipulator + 3 rivals), split bids 0..15:")
for dom in ("mixed: single-item, package and complementary bidders",
"substitutes: every bidder has ab between max(a, b) and a + b"):
n_conc = n_gain = n_both = 0; tot = 0.0
for _ in range(600):
def draw(manip):
a, b = rng.uniform(0, 10), rng.uniform(0, 10)
if dom.startswith("subs"):
return (a, b, max(a, b) + rng.random() * min(a, b))
if manip:
return (a, b, (a + b) * rng.uniform(0.6, 1.6))
k = rng.randrange(3)
return (a, 0.0, a) if k == 0 else (0.0, b, b) if k == 1 else \
(0.0, 0.0, rng.uniform(0, 15))
me = draw(True); others = [draw(False) for _ in range(3)]
g, _ = gain_from_split(me, others, grid)
c = concave([me] + others); n_conc += c; n_gain += g > 1e-9; tot += g
n_both += c and g > 1e-9
print(f" {dom}")
print(f" concave over the real bidders {n_conc}/600; profitable split"
f" {n_gain}/600; mean gain {tot / 600:.2f}")
print(f" concave over the real bidders AND profitable split:"
f" {n_both}/{n_conc}")
one, two = (7.0, 0.0, 7.0), [(5.0, 0.0, 5.0)]
al, py = outcome([one] + two)
print(f"single item (A only), value 7 vs a rival at 5: truthful pays {py[0]:.1f};"
f" best split gain {gain_from_split(one, two, grid)[0]:.1f}")
# classic case: I value AB at 10, a rival at 8. Truthful: I win AB, pay 8.0, utility 2.0
# two fake identities bidding 8 for A and 8 for B: utility up 8.0 (fakes pay 0)
# 600 random markets per domain (manipulator + 3 rivals), split bids 0..15:
# mixed: single-item, package and complementary bidders
# concave over the real bidders 406/600; profitable split 206/600; mean gain 1.70
# concave over the real bidders AND profitable split: 169/406
# substitutes: every bidder has ab between max(a, b) and a + b
# concave over the real bidders 600/600; profitable split 0/600; mean gain 0.00
# concave over the real bidders AND profitable split: 0/600
# single item (A only), value 7 vs a rival at 5: truthful pays 5.0; best split gain 0.0在含有单件出价者、整套出价者与互补估值的「混合」市场中,600 个市场里有 206 个存在有利的分身,平均收益 1.70;在所有出价者都是替代品的市场中(整套的估值介于两件中较高的一件与两件之和之间),600 个市场无一例外地没有有利的分身。有一个细节值得指出:混合市场中有 406 个市场的剩余函数对真实出价者是凹的,其中仍有 169 个存在有利的分身(程序倒数第二组输出的「169/406」)。原因是凹性条件要对整个类型域成立,包括作假者可以申报的类型:例如对手要整套、两个假身份各要一件时,两个假身份彼此是互补的,凹性就被破坏了。所以检查真实出价者是不够的,规则设计者需要限制的是允许申报的类型。单件物品的情形中,假身份只会抬高自己要付的第二价格,分身毫无收益,程序最后一行确认了这一点。
注
假名竞价与女巫攻击。 假名竞价正是拍卖中的女巫攻击(第六章):规则把每个身份当作独立的人,而身份的成本很低。它说明「激励相容」这一性质是相对于参与者集合而言的:VCG 对给定的出价者集合防操纵,但当参与者可以改变自己是几个人时,这一性质就不再成立。横尾等人与后续研究提出了专门防假名的拍卖规则,它们必须放弃一部分效率 (Yokoo et al. 2004)。
假说 · 尚未验证 · 组合投放中的分身
作者的假说(尚未确立): 在允许按「达人组合」打包报价的品牌投放竞价中,若平台按 VCG 式的外部性收费且不做身份核验,以多账号拆分报价的出价者比例会随组合报价的使用率上升。什么样的结果能证明它是错的: 在独立平台事先登记的观察研究中,经身份核验识别出的多账号报价比例与组合报价使用率之间没有正相关(相关系数的置信区间包含零或为负)。本书不使用作者企业的数据,也不做这项检验。
本章小结
VCG 让每个人支付自己给别人造成的外部性,由此使说真话成为占优策略;程序中的组合拍卖确认了这一点。但它的收入可能低于核心,使卖家与落败者有绕开拍卖的动机(示例中 12 对 13),选择核心的拍卖可以修补这一点,代价是放弃占优策略激励相容。更严重的是,VCG 不防假名竞价:一个人分身为两个身份可以把支付从 8 降到 0;横尾等人的凹性条件给出了 VCG 防假名的充分条件,但它必须对允许申报的整个类型域成立,只检查真实出价者是不够的。
参考文献
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).