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 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 |
Key formula
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
- Chapter 1 · The Revelation Principle, Incentive Compatibility and Commitment
- Chapter 3 · Position Auctions: Equilibria of the Generalized Second-Price Auction and VCG
- Chapter 4 · Myerson's Optimal Auction: Virtual Values, Reserve Prices and Ironing
- Chapter 5 · Impossibility: Hurwicz, Green–Laffont and Roberts
- Chapter 6 · Community Incentives: Points Inflation, Badges and Sybil Attacks
- Chapter 7 · Reading the Classics: One Reward, Settled Shares and "Rewards Reliable, Punishments Certain"
- Chapter 8 · Practice and Pre-Registered Testing