What does VCG Auctions and Community Incentives conclude, in numbers, about “Multi-Item VCG: Pricing Externalities, the Core and False-Name Bids”?

Answer: VCG makes each person pay the externality he imposes on the others and thereby makes truth-telling a dominant strategy; the package auction in the program confirms this. But its revenue can fall below the core, giving the seller and losers a reason to bypass the auction (12 against 13 in the example); core-selecting auctions repair this at the price of dominant-strategy incentive compatibility. More seriously, VCG is not false-name-proof: one person splitting into two identities can cut his payment from 8 to 0. The concavity condition of Yokoo and co-authors is sufficient for VCG to be false-name-proof, but it must hold over the whole domain of declarable types; checking the real bidders is not enough.

Scope of the numbers: Marked boxes separate published evidence, runnable Python calculations (16 programs), classical sources and the author's models and hypotheses; all data in the book are fictional or simulated.

中文版

Data table

The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 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

Key formula

\[x^* \in \arg\max_x \sum_j \hat v_j(x),\]
Show the full program
# 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])))

Single source and citation

Fan, Y. (2026). Mechanism Design, Vickrey–Clarke–Groves Auctions and Incentive-Compatible Community Engineering (Version 1.0.0), Chapter 2: Multi-Item VCG: Pricing Externalities, the Core and False-Name Bids. 5D Library. https://doi.org/10.5281/zenodo.23836274

DOI: 10.5281/zenodo.23836274 · Read the monograph · 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}
}

Other chapter answers in this book