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

第四章 迈尔森最优拍卖:虚拟估值、保留价与熨平

问题

前两章的 VCG 与 GSP 追求的是效率:把物品给最看重它的人。卖家关心的往往是收入。迈尔森 1981 年的论文回答了一个看似无从下手的问题:在所有可能的拍卖规则中,哪一个使卖家的期望收入最高 (Myerson 1981)?借助显示原理(第一章),只需在激励相容的直接机制中寻找;本章给出完整的推导,用程序验证正则分布的结论,并讨论非正则分布的「熨平」。同一时期赖利与萨缪尔森在对称情形下得到了等价的结果 (Riley and Samuelson 1981)。

推导

设 nn 名出价者的估值独立同分布,分布函数 FF、密度 f>0f > 0,支撑为 [v_,v‾][\underline v, \bar v]。直接机制规定:报告组合为 vv 时,ii 获得物品的概率 qi(v)q_i(v) 与支付 ti(v)t_i(v)。记 Qi(vi)=Ev−i[qi(v)]Q_i(v_i) = E_{v_{-i}}[q_i(v)]、Ti(vi)=Ev−i[ti(v)]T_i(v_i) = E_{v_{-i}}[t_i(v)],类型 viv_i 如实报告的期望效用为 Ui(vi)=viQi(vi)−Ti(vi)U_i(v_i) = v_i Q_i(v_i) – T_i(v_i)。

引理(迈尔森)。 机制是贝叶斯激励相容的,当且仅当 (a) QiQ_i 单调不减,且 (b) Ui(vi)=Ui(v_)+∫v_viQi(s)dsU_i(v_i) = U_i(\underline v) + \int_{\underline v}^{v_i} Q_i(s)\,ds。

证明要点。 激励相容意味着 Ui(v)=max⁡r[vQi(r)−Ti(r)]U_i(v) = \max_r\,[v Q_i(r) – T_i(r)],它是一族关于 vv 的线性函数的上包络,所以是凸函数,几乎处处可导且导数为 Qi(v)Q_i(v)(包络定理);凸函数的导数单调不减,得到 (a),积分得到 (b)。反过来,若 (a)(b) 成立,则类型 vv 报告 rr 的损失 Ui(v)−[vQi(r)−Ti(r)]=∫rv[Qi(s)−Qi(r)]ds≥0U_i(v) – [vQ_i(r) – T_i(r)] = \int_r^v [Q_i(s) – Q_i(r)]\,ds \ge 0。

收入公式。 由 Ti=vQi−UiT_i = v Q_i – U_i 与 (b),交换积分次序得

E[Ui(vi)]=Ui(v_)+∫v_v‾(1−F(s))Qi(s)ds=Ui(v_)+E[1−F(vi)f(vi)Qi(vi)],E[U_i(v_i)] = U_i(\underline v) + \int_{\underline v}^{\bar v} (1 – F(s))\,Q_i(s)\,ds = U_i(\underline v) + E\Big[\tfrac{1-F(v_i)}{f(v_i)}\,Q_i(v_i)\Big],

所以卖家的期望收入为

∑iE[Ti(vi)]=E[∑iψ(vi)qi(v)]−∑iUi(v_),ψ(v)=v−1−F(v)f(v).\sum_i E[T_i(v_i)] = E\Big[\sum_i \psi(v_i)\,q_i(v)\Big] – \sum_i U_i(\underline v), \qquad \psi(v) = v – \frac{1 – F(v)}{f(v)} .

ψ\psi 称为虚拟估值。期望收入等于「期望虚拟剩余」减去最低类型的效用。个体理性要求 Ui(v_)≥0U_i(\underline v) \ge 0,最优时取零。于是收入最大化化为:对每一个报告组合,把物品给虚拟估值最高的人,前提是这个虚拟估值为正,否则不卖。

正则情形。 若 ψ\psi 单调递增(称分布正则),上述分配规则是单调的,满足引理的条件 (a),因而可以实施;它就是带保留价 r*=ψ−1(0)r^* = \psi^{-1}(0) 的二价拍卖。保留价只取决于 FF,与出价者人数无关。均匀分布 [0,1][0,1] 上 ψ(v)=2v−1\psi(v) = 2v – 1,r*=1/2r^* = 1/2;参数为 λ\lambda 的指数分布上 ψ(v)=v−1/λ\psi(v) = v – 1/\lambda,r*=1/λr^* = 1/\lambda。布洛与罗伯茨指出,在分位数空间中 ψ\psi 正是垄断定价理论中的边际收入,最优拍卖就是「按边际收入从高到低卖,边际收入为负则不卖」(Bulow and Roberts 1989)。

下面的程序对三种正则分布计算 ψ\psi、最优保留价,以及 n=1,…,5n = 1, \dots, 5 时无保留价与带最优保留价的二价拍卖收入(数值积分 Rn(r)=∫rψ(v)nF(v)n−1f(v)dvR_n(r) = \int_r \psi(v)\,n F(v)^{n-1} f(v)\,dv),并用蒙特卡洛核对一个值。表的最后两列与布洛—克伦佩雷尔定理有关,下一节讨论。

推导

# 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%;对数正态分布 ln⁡v∼N(0,0.52)\ln v \sim N(0, 0.5^2) 时保留价为 0.7719,两人时只增加 4.3%。三种分布中,保留价带来的增益都随人数迅速变小:五人时分别只有 0.8%、1.9% 与 0.0%。

布洛—克伦佩雷尔定理

定理 (Bulow and Klemperer 1996)。若估值独立同分布且分布正则,则 n+1n+1 名出价者、无保留价的英式(或二价)拍卖的期望收入,不低于 nn 名出价者时任何机制(包括迈尔森的最优拍卖)的期望收入。

证明思路。 考虑 n+1n+1 名出价者、「必须卖出」的机制。其中一个是:对前 nn 人运行最优拍卖,若流拍就把物品免费送给第 n+1n+1 人。它激励相容、总能卖出,收入恰好是 Rn(r*)R_n(r^*)。另一方面,在必须卖出的机制中,期望收入等于期望虚拟剩余,而虚拟剩余最大的是把物品给虚拟估值最高的人;正则时就是给估值最高的人,即无保留价的拍卖。所以 Rn+1(0)≥Rn(r*)R_{n+1}(0) \ge R_n(r^*)。

程序表中最后一列在三种分布、n=1,…,5n = 1,\dots,5 的所有情形下都成立。它的实际含义是:多吸引一名同类的出价者,比精心计算保留价更有价值。但定理需要两个条件:出价者同分布,且分布正则。

非正则分布与熨平

若 ψ\psi 不单调,「把物品给虚拟估值最高者」就不是单调的分配规则,违反引理条件 (a),不能实施。迈尔森的办法是熨平:在分位数空间 q=1−F(v)q = 1 – F(v) 中定义收入曲线 R(q)=qv(q)R(q) = q\,v(q)(以价格 v(q)v(q) 卖给一个人、成交概率为 qq 时的收入),ψ\psi 就是 R′(q)R'(q)。分布正则当且仅当 RR 是凹函数。若 RR 不凹,就用它的凹包(最小的凹的上界)R‾\bar R 代替,用 R‾′\bar R' 作为熨平的虚拟估值 ψ‾\bar\psi:在 RR 与 R‾\bar R 不重合的区间上,ψ‾\bar\psi 是常数,这个区间内的所有类型被同等对待(同在区间内的出价者之间随机分配)。最优机制按 ψ‾\bar\psi 分配,期望收入为 ∫ψ‾(q)+n(1−q)n−1dq\int \bar\psi(q)^+\,n(1-q)^{n-1}\,dq。

下面的程序构造了一个非正则分布:估值以 0.78 的概率在 [0,3] 上均匀,以 0.02 的概率在 [3,4] 上均匀,以 0.20 的概率在 [4,5] 上均匀。中间那一段很薄,所以那里的 (1−F)/f(1-F)/f 很大,ψ\psi 突然下跌。

推导

# 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

ψ\psi 在 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%。如果忽视单调性、直接按原始 ψ\psi 分配,「虚拟剩余」会是 1.8757,高于最优值,但这个规则不能实施:估值 2.9(ψ=+1.95\psi = +1.95)的人可能赢,估值 3.5(ψ=−7.00\psi = -7.00)的人永远赢不了,估值高的人反而得不到物品,任何支付规则都无法让他说真话。

左:三种正则分布的虚拟估值,与零的交点即最优保留价(均匀 0.5、指数 1、对数正态 0.7719)。右:非正则分布的收入曲线 R(q)(实线)及其凹包(虚线);两者分离的一段就是熨平区间。

适用范围

迈尔森的结论是本书最干净的「最优」结论之一,但它的每一个假设都有分量。同分布:出价者分布不同时,最优拍卖按各自的虚拟估值分配,会对某些人「歧视」,物品不一定给出价最高的人,也不是带保留价的二价拍卖。独立私人价值:估值相关时,克雷默与麦克莱恩构造的机制可以榨取全部剩余 (Crémer and McLean 1988),那是另一类结论。卖家能承诺保留价:第一章的科斯问题说明,流拍之后若卖家会重新拍卖,保留价就不可信。风险中性:出价者风险厌恶时,收益等价定理(第 27 本)不再成立。

迈尔森—萨特思韦特定理(第 27 本已讨论)是同一套工具在双边交易中的应用:买卖双方都有私人信息、估值区间重叠时,不存在同时满足有效、激励相容、个体理性与不需补贴的机制 (Myerson and Satterthwaite 1983);第 27 本的程序给出均匀分布下最好的机制只能实现 84.375% 的交易收益,这里不再重复。

假说 · 尚未验证 · 社群奖励的保留价

作者的假说(尚未确立): 在用积分竞拍稀缺奖励(例如一对一辅导时段)的线上社群中,参与竞拍人数每增加一人带来的积分收入增量,大于把保留价从零调到按历史出价估计的最优水平带来的增量(布洛—克伦佩雷尔定理的社群版本)。什么样的结果能证明它是错的: 在独立社群事先登记的随机化比较中,「保留价组」的平均成交积分显著高于「多一名竞拍者组」。估值分布若明显非正则或参与者异质,定理不适用,这一检验也就不能说明定理的对错。

本章小结

迈尔森引理把激励相容化为「分配单调 + 效用由包络公式决定」,由此得到「期望收入 = 期望虚拟剩余」。分布正则时,最优拍卖是保留价为 ψ−1(0)\psi^{-1}(0) 的二价拍卖,保留价与人数无关(均匀分布 0.5、指数分布 1);保留价的增益随人数迅速变小,而布洛—克伦佩雷尔定理说多一名出价者胜过最优保留价。分布非正则时要熨平:程序中的例子里,最优拍卖比最佳保留价的二价拍卖多收 1.4%—3.3%,而按原始虚拟估值分配的规则不单调、不可实施。

参考文献

Bulow, Jeremy, and Paul Klemperer. 1996. “Auctions versus Negotiations.” American Economic Review 86 (1): 180–94.
Bulow, Jeremy, and John Roberts. 1989. “The Simple Economics of Optimal Auctions.” Journal of Political Economy 97 (5): 1060–90.
Crémer, Jacques, and Richard P. McLean. 1988. “Full Extraction of the Surplus in Bayesian and Dominant Strategy Auctions.” Econometrica 56 (6): 1247–57.
Myerson, Roger B. 1981. “Optimal Auction Design.” Mathematics of Operations Research 6 (1): 58–73.
Myerson, Roger B., and Mark A. Satterthwaite. 1983. “Efficient Mechanisms for Bilateral Trading.” Journal of Economic Theory 29 (2): 265–81.
Riley, John G., and William F. Samuelson. 1981. “Optimal Auctions.” American Economic Review 71 (3): 381–92.

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).