关于「多物品 VCG:外部性定价、核心与假名竞价」,《VCG 拍卖与社群激励》给出的定量结论是什么?

结论:VCG 让每个人支付自己给别人造成的外部性,由此使说真话成为占优策略;程序中的组合拍卖确认了这一点。但它的收入可能低于核心,使卖家与落败者有绕开拍卖的动机(示例中 12 对 13),选择核心的拍卖可以修补这一点,代价是放弃占优策略激励相容。更严重的是,VCG 不防假名竞价:一个人分身为两个身份可以把支付从 8 降到 0;横尾等人的凹性条件给出了 VCG 防假名的充分条件,但它必须对允许申报的整个类型域成立,只检查真实出价者是不够的。

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

English version

对照数据表

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

efficient welfare 15.0; allocation {1: 'A', 2: 'B', 3: 'C'}
bidder 1: wins A bid6.0, VCG payment 4.0, surplus 2.0
bidder 2: wins B bid5.0, VCG payment 4.0, surplus 1.0
bidder 3: wins C bid4.0, VCG payment 4.0, surplus 0.0
VCG revenue 12.0
misreport search20,000 misreports, largest gain +0.0000
core13 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

核心公式

\[x^* \in \arg\max_x \sum_j \hat v_j(x),\]
查看完整验算程序
# 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])))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《机制设计、维克里—克拉克—格罗夫斯(VCG)拍卖与数字社群激励相容工程》第 2 章「多物品 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}
}

本书其他章节结论