5D Library › 机制设计、维克里—克拉克—格罗夫斯(VCG)拍卖与数字社群激励相容工程 · English
第四章 迈尔森最优拍卖:虚拟估值、保留价与熨平
问题
前两章的 VCG 与 GSP 追求的是效率:把物品给最看重它的人。卖家关心的往往是收入。迈尔森 1981 年的论文回答了一个看似无从下手的问题:在所有可能的拍卖规则中,哪一个使卖家的期望收入最高 (Myerson 1981)?借助显示原理(第一章),只需在激励相容的直接机制中寻找;本章给出完整的推导,用程序验证正则分布的结论,并讨论非正则分布的「熨平」。同一时期赖利与萨缪尔森在对称情形下得到了等价的结果 (Riley and Samuelson 1981)。
推导
设 名出价者的估值独立同分布,分布函数 、密度 ,支撑为 。直接机制规定:报告组合为 时, 获得物品的概率 与支付 。记 、,类型 如实报告的期望效用为 。
引理(迈尔森)。 机制是贝叶斯激励相容的,当且仅当 (a) 单调不减,且 (b) 。
证明要点。 激励相容意味着 ,它是一族关于 的线性函数的上包络,所以是凸函数,几乎处处可导且导数为 (包络定理);凸函数的导数单调不减,得到 (a),积分得到 (b)。反过来,若 (a)(b) 成立,则类型 报告 的损失 。
收入公式。 由 与 (b),交换积分次序得
所以卖家的期望收入为
称为虚拟估值。期望收入等于「期望虚拟剩余」减去最低类型的效用。个体理性要求 ,最优时取零。于是收入最大化化为:对每一个报告组合,把物品给虚拟估值最高的人,前提是这个虚拟估值为正,否则不卖。
正则情形。 若 单调递增(称分布正则),上述分配规则是单调的,满足引理的条件 (a),因而可以实施;它就是带保留价 的二价拍卖。保留价只取决于 ,与出价者人数无关。均匀分布 上 ,;参数为 的指数分布上 ,。布洛与罗伯茨指出,在分位数空间中 正是垄断定价理论中的边际收入,最优拍卖就是「按边际收入从高到低卖,边际收入为负则不卖」(Bulow and Roberts 1989)。
下面的程序对三种正则分布计算 、最优保留价,以及 时无保留价与带最优保留价的二价拍卖收入(数值积分 ),并用蒙特卡洛核对一个值。表的最后两列与布洛—克伦佩雷尔定理有关,下一节讨论。
推导
# Chapter 4. Myerson (1981) for regular distributions. Virtual value
# psi(v) = v - (1 - F(v)) / f(v); expected revenue = expected virtual surplus; with
# i.i.d. regular bidders the optimal auction is a second-price auction with reserve
# r* = psi^-1(0), whatever the number of bidders. Revenue of a second-price auction with
# reserve r and n bidders: R_n(r) = integral_r^inf psi(v) n F(v)^(n-1) f(v) dv.
# Bulow-Klemperer (1996): R_{n+1}(0) >= R_n(r*) for regular distributions.
import math, random, statistics
LN = statistics.NormalDist(0.0, 0.5) # log-value of the lognormal
DISTS = {
"uniform[0,1]": (lambda v: v, lambda v: 1.0, 0.0, 1.0),
"exponential(1)": (lambda v: 1 - math.exp(-v), lambda v: math.exp(-v), 0.0, 25.0),
"lognormal(0,.5)": (lambda v: LN.cdf(math.log(v)),
lambda v: LN.pdf(math.log(v)) / v, 1e-6, math.exp(4.0)),
}
def psi(F, f, v):
return v - (1 - F(v)) / f(v)
def simpson(g, a, b, m=4000):
h = (b - a) / m
s = g(a) + g(b) + math.fsum((4 if k % 2 else 2) * g(a + k * h)
for k in range(1, m))
return s * h / 3
def revenue(F, f, hi, n, r, lo):
return simpson(lambda v: psi(F, f, v) * n * F(v) ** (n - 1) * f(v), max(r, lo), hi)
def reserve(F, f, lo, hi):
a, b = lo + 1e-9, hi
for _ in range(100): # bisection on psi(v) = 0
m = (a + b) / 2
a, b = (m, b) if psi(F, f, m) < 0 else (a, m)
return (a + b) / 2
if __name__ == "__main__":
for name, (F, f, lo, hi) in DISTS.items():
xs = [lo + (hi - lo) * k / 400 for k in range(1, 400)]
xs = [x for x in xs if F(x) < 0.999999]
mono = all(psi(F, f, a) <= psi(F, f, b) + 1e-12 for a, b in zip(xs, xs[1:]))
r = reserve(F, f, lo, hi)
print(f"{name}: psi increasing on the grid: {mono}; optimal reserve {r:.4f}")
print(" n R_n(0) R_n(r*) gain R_n+1(0) Bulow-Klemperer holds")
for n in range(1, 6):
r0, rs = revenue(F, f, hi, n, 0.0, lo), revenue(F, f, hi, n, r, lo)
r1 = revenue(F, f, hi, n + 1, 0.0, lo)
g = f"{rs / r0 - 1:6.1%}" if r0 > 1e-6 else " n/a"
print(f" {n} {abs(r0):7.4f} {rs:8.4f} {g} {r1:8.4f} {r1 >= rs - 1e-9}")
rng = random.Random(1981); tot = 0.0; N = 200000
for _ in range(N):
a, b = sorted((rng.random(), rng.random()))
tot += max(a, 0.5) if b >= 0.5 else 0.0
print(f"Monte Carlo, uniform, n = 2, reserve 0.5: {tot / N:.4f} (exact 5/12 ="
f" {5 / 12:.4f})")
# uniform[0,1]: psi increasing on the grid: True; optimal reserve 0.5000
# n R_n(0) R_n(r*) gain R_n+1(0) Bulow-Klemperer holds
# 1 0.0000 0.2500 n/a 0.3333 True
# 2 0.3333 0.4167 25.0% 0.5000 True
# 3 0.5000 0.5312 6.2% 0.6000 True
# 4 0.6000 0.6125 2.1% 0.6667 True
# 5 0.6667 0.6719 0.8% 0.7143 True
# exponential(1): psi increasing on the grid: True; optimal reserve 1.0000
# n R_n(0) R_n(r*) gain R_n+1(0) Bulow-Klemperer holds
# 1 0.0000 0.3679 n/a 0.5000 True
# 2 0.5000 0.6681 33.6% 0.8333 True
# 3 0.8333 0.9172 10.1% 1.0833 True
# 4 1.0833 1.1273 4.1% 1.2833 True
# 5 1.2833 1.3071 1.9% 1.4500 True
# lognormal(0,.5): psi increasing on the grid: True; optimal reserve 0.7719
# n R_n(0) R_n(r*) gain R_n+1(0) Bulow-Klemperer holds
# 1 0.0000 0.5386 n/a 0.8200 True
# 2 0.8200 0.8554 4.3% 1.0577 True
# 3 1.0577 1.0643 0.6% 1.2139 True
# 4 1.2139 1.2154 0.1% 1.3322 True
# 5 1.3322 1.3326 0.0% 1.4280 True
# Monte Carlo, uniform, n = 2, reserve 0.5: 0.4166 (exact 5/12 = 0.4167)均匀分布下保留价为 0.5000,两名出价者时收入从 1/3 增到 5/12 = 0.4167(蒙特卡洛 0.4166),增加 25.0%;指数分布下保留价为 1,两人时增加 33.6%;对数正态分布 时保留价为 0.7719,两人时只增加 4.3%。三种分布中,保留价带来的增益都随人数迅速变小:五人时分别只有 0.8%、1.9% 与 0.0%。
布洛—克伦佩雷尔定理
定理 (Bulow and Klemperer 1996)。若估值独立同分布且分布正则,则 名出价者、无保留价的英式(或二价)拍卖的期望收入,不低于 名出价者时任何机制(包括迈尔森的最优拍卖)的期望收入。
证明思路。 考虑 名出价者、「必须卖出」的机制。其中一个是:对前 人运行最优拍卖,若流拍就把物品免费送给第 人。它激励相容、总能卖出,收入恰好是 。另一方面,在必须卖出的机制中,期望收入等于期望虚拟剩余,而虚拟剩余最大的是把物品给虚拟估值最高的人;正则时就是给估值最高的人,即无保留价的拍卖。所以 。
程序表中最后一列在三种分布、 的所有情形下都成立。它的实际含义是:多吸引一名同类的出价者,比精心计算保留价更有价值。但定理需要两个条件:出价者同分布,且分布正则。
非正则分布与熨平
若 不单调,「把物品给虚拟估值最高者」就不是单调的分配规则,违反引理条件 (a),不能实施。迈尔森的办法是熨平:在分位数空间 中定义收入曲线 (以价格 卖给一个人、成交概率为 时的收入), 就是 。分布正则当且仅当 是凹函数。若 不凹,就用它的凹包(最小的凹的上界) 代替,用 作为熨平的虚拟估值 :在 与 不重合的区间上, 是常数,这个区间内的所有类型被同等对待(同在区间内的出价者之间随机分配)。最优机制按 分配,期望收入为 。
下面的程序构造了一个非正则分布:估值以 0.78 的概率在 [0,3] 上均匀,以 0.02 的概率在 [3,4] 上均匀,以 0.20 的概率在 [4,5] 上均匀。中间那一段很薄,所以那里的 很大, 突然下跌。
推导
# Chapter 4. A non-regular distribution and Myerson's ironing. Values are piecewise
# uniform: weight 0.78 on [0,3], 0.02 on [3,4], 0.20 on [4,5] (a thin middle band). In
# quantile space (q = 1 - F(v)) the revenue curve is R(q) = q v(q) and psi = R'(q).
# Where R is not concave psi is not monotone; ironing replaces R by its concave hull,
# whose slope is the ironed virtual value psi_bar. With n i.i.d. bidders the optimal
# revenue is integral psi_bar(q)^+ n (1 - q)^(n-1) dq (ties inside an ironed interval
# are broken at random); any monotone allocation earns its expected unironed virtual
# surplus, so a second-price auction with reserve r earns the integral of psi over v >= r.
import math, random
PIECES = [(0.20, 4.0, 5.0), (0.02, 3.0, 4.0), (0.78, 0.0, 3.0)] # from the top down
M = 20000
def v_of_q(q):
acc = 0.0
for w, lo, hi in PIECES:
if q <= acc + w:
return hi - (hi - lo) * (q - acc) / w
acc += w
return 0.0
def psi_v(v):
acc = 0.0 # acc = 1 - F at the top of piece
for w, lo, hi in PIECES:
if v >= lo:
f = w / (hi - lo); tail = acc + w * (hi - v) / (hi - lo)
return v - tail / f
acc += w
return -1e9
Q = [k / M for k in range(M + 1)]
R = [q * v_of_q(q) for q in Q]
def hull(xs, ys): # upper concave hull
h = []
for p in zip(xs, ys):
while len(h) >= 2 and ((h[-1][0] - h[-2][0]) * (p[1] - h[-2][1]) -
(h[-1][1] - h[-2][1]) * (p[0] - h[-2][0])) >= 0:
h.pop()
h.append(p)
return h
H = hull(Q, R); BAR = [0.0] * M; j = 0
for k in range(M): # slope of the hull on cell k
qm = (Q[k] + Q[k + 1]) / 2
while H[j + 1][0] < qm:
j += 1
BAR[k] = (H[j + 1][1] - H[j][1]) / (H[j + 1][0] - H[j][0])
RAW = [(R[k + 1] - R[k]) * M for k in range(M)]
def weight(k, n):
return n * (1 - (k + 0.5) / M) ** (n - 1) / M
def optimal(n):
return math.fsum(max(BAR[k], 0.0) * weight(k, n) for k in range(M))
def spa_table(n): # cumulative revenue by reserve cell
out, s = [], 0.0
for k in range(M):
s += RAW[k] * weight(k, n); out.append(s)
return out
if __name__ == "__main__":
print(f"psi at 2.99: {psi_v(2.99):+.3f}; at 3.01: {psi_v(3.01):+.3f}; at 4.01:"
f" {psi_v(4.01):+.3f} -> not monotone")
flat = [k for k in range(M) if abs(RAW[k] - BAR[k]) > 1e-6]
qa, qb = flat[0] / M, (flat[-1] + 1) / M
print(f"ironed interval: values {v_of_q(qb):.3f} .. {v_of_q(qa):.3f}"
f" (quantiles {qa:.4f} .. {qb:.4f}), ironed psi {BAR[flat[0]]:+.4f}")
kstar = max(range(M + 1), key=lambda k: R[k])
print(f"monopoly (n = 1) price {v_of_q(kstar / M):.3f}, revenue {R[kstar]:.4f}")
for n in (2, 3, 5):
tab = spa_table(n); kb = max(range(M), key=lambda k: tab[k])
print(f"n = {n}: optimal (ironed) {optimal(n):.4f}; second price with best"
f" reserve {v_of_q((kb + 1) / M):.3f}: {tab[kb]:.4f}"
f" ({optimal(n) / tab[kb] - 1:+.2%})")
rng = random.Random(81); N = 200000; naive = 0.0
def draw():
u = rng.random()
for w, lo, hi in PIECES:
if u < w:
return rng.uniform(lo, hi)
u -= w
return 0.0
for _ in range(N):
naive += max(0.0, psi_v(draw()), psi_v(draw()))
print(f"n = 2: 'allocate by raw psi' virtual surplus {naive / N:.4f}"
f" > optimum {optimal(2):.4f}, not implementable:")
print(f" value 2.9 (psi {psi_v(2.9):+.2f}) can win, value 3.5 (psi"
f" {psi_v(3.5):+.2f}) never wins: not monotone")
# psi at 2.99: +2.134; at 3.01: -7.980; at 4.01: +3.020 -> not monotone
# ironed interval: values 2.234 .. 4.000 (quantiles 0.2000 .. 0.4191), ironed psi +0.6224
# monopoly (n = 1) price 1.923, revenue 0.9615
# n = 2: optimal (ironed) 1.6695; second price with best reserve 1.923: 1.6464 (+1.41%)
# n = 3: optimal (ironed) 2.2079; second price with best reserve 1.923: 2.1567 (+2.37%)
# n = 5: optimal (ironed) 2.9619; second price with best reserve 1.923: 2.8683 (+3.26%)
# n = 2: 'allocate by raw psi' virtual surplus 1.8757 > optimum 1.6695, not implementable:
# value 2.9 (psi +1.95) can win, value 3.5 (psi -7.00) never wins: not monotone在 2.99 处为 +2.134,在 3.01 处跌到 −7.980,到 4.01 又回到 +3.020:不单调。熨平区间为估值 2.234 到 4.000,区间内的熨平虚拟估值为 +0.6224(为正,所以这一段类型都会得到物品,只是彼此之间不分高下)。单个买家时最优标价为 1.923,收入 0.9615。两名出价者时,最优(熨平)拍卖的期望收入为 1.6695,最好的「二价拍卖加保留价」为 1.6464,前者高 1.41%;三人与五人时分别高 2.37% 与 3.26%。如果忽视单调性、直接按原始 分配,「虚拟剩余」会是 1.8757,高于最优值,但这个规则不能实施:估值 2.9()的人可能赢,估值 3.5()的人永远赢不了,估值高的人反而得不到物品,任何支付规则都无法让他说真话。
适用范围
迈尔森的结论是本书最干净的「最优」结论之一,但它的每一个假设都有分量。同分布:出价者分布不同时,最优拍卖按各自的虚拟估值分配,会对某些人「歧视」,物品不一定给出价最高的人,也不是带保留价的二价拍卖。独立私人价值:估值相关时,克雷默与麦克莱恩构造的机制可以榨取全部剩余 (Crémer and McLean 1988),那是另一类结论。卖家能承诺保留价:第一章的科斯问题说明,流拍之后若卖家会重新拍卖,保留价就不可信。风险中性:出价者风险厌恶时,收益等价定理(第 27 本)不再成立。
迈尔森—萨特思韦特定理(第 27 本已讨论)是同一套工具在双边交易中的应用:买卖双方都有私人信息、估值区间重叠时,不存在同时满足有效、激励相容、个体理性与不需补贴的机制 (Myerson and Satterthwaite 1983);第 27 本的程序给出均匀分布下最好的机制只能实现 84.375% 的交易收益,这里不再重复。
假说 · 尚未验证 · 社群奖励的保留价
作者的假说(尚未确立): 在用积分竞拍稀缺奖励(例如一对一辅导时段)的线上社群中,参与竞拍人数每增加一人带来的积分收入增量,大于把保留价从零调到按历史出价估计的最优水平带来的增量(布洛—克伦佩雷尔定理的社群版本)。什么样的结果能证明它是错的: 在独立社群事先登记的随机化比较中,「保留价组」的平均成交积分显著高于「多一名竞拍者组」。估值分布若明显非正则或参与者异质,定理不适用,这一检验也就不能说明定理的对错。
本章小结
迈尔森引理把激励相容化为「分配单调 + 效用由包络公式决定」,由此得到「期望收入 = 期望虚拟剩余」。分布正则时,最优拍卖是保留价为 的二价拍卖,保留价与人数无关(均匀分布 0.5、指数分布 1);保留价的增益随人数迅速变小,而布洛—克伦佩雷尔定理说多一名出价者胜过最优保留价。分布非正则时要熨平:程序中的例子里,最优拍卖比最佳保留价的二价拍卖多收 1.4%—3.3%,而按原始虚拟估值分配的规则不单调、不可实施。
参考文献
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).