5D Library › Mechanism Design, Vickrey–Clarke–Groves Auctions and Incentive-Compatible Community Engineering · 中文

Chapter 2 Multi-Item VCG: Pricing Externalities, the Core and False-Name Bids

From the second-price auction to VCG

In Vickrey’s second-price auction for one object the highest bidder wins and pays the second-highest bid (Vickrey 1961). Book 27 verified by program that truthful bidding is weakly dominant. Its generalisation is the Vickrey–Clarke–Groves (VCG) mechanism (Clarke 1971; Groves 1973): participants report valuation functions v̂i\hat v_i; the mechanism chooses an outcome maximising reported total welfare,

x*∈arg⁡maxx∑jv̂j(x),x^* \in \arg\max_x \sum_j \hat v_j(x),

and charges each participant the externality he imposes on the others:

ti=maxx∑j≠iv̂j(x)−∑j≠iv̂j(x*).t_i = \max_x \sum_{j \ne i} \hat v_j(x) \;-\; \sum_{j \ne i} \hat v_j(x^*).

The first term is “the best the others could do if ii were absent”, the second “what the others actually get when ii is present”. The second-price auction is a special case: if the winner were absent, the second-highest bidder would get the object, so the winner pays the second-highest bid.

Why truth-telling is dominant. Participant ii’s utility is vi(x*)−ti=[vi(x*)+∑j≠iv̂j(x*)]−max⁡x∑j≠iv̂j(x)v_i(x^*) – t_i = \big[v_i(x^*) + \sum_{j\ne i}\hat v_j(x^*)\big] – \max_x \sum_{j\ne i}\hat v_j(x). The last term does not depend on his report; the bracket is “total welfare evaluated at his true valuation”, while the mechanism maximises total welfare at his report. So whatever the others report, truthful reporting makes the mechanism maximise the bracket on his behalf, and any misreport can only lead it to an outcome that is worse (at best equal) for the bracket. This is Groves’ argument; any payment of the form ti=hi(v̂−i)−∑j≠iv̂j(x*)t_i = h_i(\hat v_{-i}) – \sum_{j\ne i}\hat v_j(x^*) has the same property. Taking hih_i to be “maximal welfare without ii”, as above, is the Clarke pivot rule; it makes payments non-negative and ensures that no participant loses by taking part (when values are non-negative).

Book 27 treated three weaknesses of VCG, which are only recapped here: revenue can be zero (when two objects go to two bidders who each want one, even if someone else bids substantially for the pair: revenue is zero whenever the bid for the pair is no higher than either single bid); adding bidders can lower revenue; and losers can collude: several bidders who would otherwise lose each raise their single-item bids, become the winners themselves and each pay very little or nothing. This chapter treats two further problems: the VCG outcome may lie outside the core, and VCG cannot withstand false-name bidding.

A package auction

The program below has three items A, B, C and five bidders bidding in “exclusive-or” form (each wins at most one of the packages he names): bidder 1 bids 6 for A and 10 for AB; bidder 2 bids 5 for B and 9 for BC; bidder 3 bids 4 for C; bidder 4 bids 13 for ABC; bidder 5 bids 8 for AC. It enumerates all feasible allocations to find the efficient allocation and the VCG payments, then generates 20,000 random misreports (scaling someone’s bids up or down, or replacing them with random packages and amounts) to see whether anyone can gain; finally it checks the core constraints.

Calculation

# 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])))
# 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

The efficient allocation gives A, B and C to bidders 1, 2 and 3, with total welfare 15 (above bidder 4’s 13 and the 14 of “bidder 1 takes AB, bidder 3 takes C”). Each VCG payment is 4: for example, without bidder 1 the best allocation is “bidder 5 takes AC, bidder 2 takes B” or “bidder 4 takes ABC”, worth 13; with him present the others get 5 + 4 = 9, so his externality is 13 − 9 = 4. The three surpluses are 2, 1 and 0. The largest gain among the 20,000 misreports is 0: in this example misreporting does not pay, in line with the argument above.

The core: can the seller and a loser strike a separate deal?

Total VCG revenue is 12. But bidder 4 bid 13 for the whole set: the seller and bidder 4 could bypass the auction and trade at any price between 12 and 13, both doing better than in the auction. Such an outcome is said to lie outside the core. Formally, for every subset SS of the winners, what they pay in total must be at least “the most the bidders other than SS could pay” minus “the bids of the winners outside SS”; otherwise the seller and the others can form a better coalition. The program lists 13 constraints; the VCG payments violate them by at most 1.0; the lowest revenue satisfying all core constraints is 13, exactly the losing bidder 4’s bid; and the core point nearest the VCG payments is (4.5, 4.5, 4.0).

Evidence

Ausubel and Milgrom called VCG the “lovely but lonely” auction: beautiful in theory, almost never used in practice (Ausubel and Milgrom 2006). They show that when the bidders are substitutes from the seller’s point of view (for instance when all bidders regard the items as substitutes), the VCG outcome lies in the core; with complements, VCG revenue can be unreasonably low and the auction can be manipulated by collusion among losers or by false-name bids. Day and Milgrom proposed “core-selecting package auctions”, which choose payments in the core so as to minimise bidders’ incentives to deviate from truthful bidding (Day and Milgrom 2008). The price is giving up dominant-strategy incentive compatibility: a core-selecting auction is strategy-proof only when the VCG outcome itself is in the core. Rothkopf’s thirteen reasons (among them low revenue, collusion, privacy and computational difficulty) explain from the practical side why VCG is rarely adopted (Rothkopf 2007); earlier, Rothkopf, Teisberg and Kahn asked “why are Vickrey auctions rare?” (Rothkopf et al. 1990).

Lucking-Reiley collected the few real uses of Vickrey auctions: nineteenth-century stamp auctions by mail, and the “proxy bidding” of online auctions (bidders give a ceiling and the system raises their bid by the minimum increment, close in effect to a second-price auction) (Lucking-Reiley 2000). Varian and Harris discussed VCG in the theory and practice of online advertising (Varian and Harris 2014). These are single-item or simply structured settings; full package VCG remains rare.

False-name bids: the Sybil attack of auctions

In an online auction one person can register several identities with several e-mail addresses. Yokoo, Sakurai and Matsubara called bidding under several identities false-name bidding and proved three results (Yokoo et al. 2004): first, VCG, strategy-proof and efficient without false names, is not false-name-proof; second, no package-auction rule is both Pareto efficient and false-name-proof; third, VCG is false-name-proof if the surplus function (the maximal welfare W(⋅)W(\cdot) achievable by any group of bidders) is “concave” over bidders, that is, for any S⊆TS \subseteq T and ii not in TT,

W(S∪{i})−W(S)≥W(T∪{i})−W(T).W(S \cup \{i\}) – W(S) \;\ge\; W(T \cup \{i\}) – W(T).

Concavity means “a bidder’s marginal contribution shrinks as there are more others”, which is the case when bidders are substitutes for one another.

The program first computes the classic example: two items A and B; I value the pair AB at 10, a rival values AB at 8. Bidding truthfully I win AB and pay 8, a surplus of 2. If I register two fake identities, one bidding only for A and the other only for B, 8 each, the mechanism finds that giving A and B to “two people” yields welfare 16, above the rival’s 8; without either fake identity, the other still gets its item and the rival still gets nothing, so each fake identity’s externality is 0. I get AB for a total payment of 0, and my surplus rises from 2 to 10.

The program then repeats the test in two classes of random markets: each market has one potential manipulator and three rivals, and the fake identities search a grid from 0 to 15 for the most profitable single-item bids.

Calculation

# Chapter 2. False-name (shill / Sybil) bids against VCG, two items A and B. Each bidder
# has XOR values (a, b, ab): for A alone, B alone, both. A manipulator may replace his
# one identity by two fake ones: X bids x for A only, Y bids y for B only. Yokoo,
# Sakurai and Matsubara (2004) show VCG is not false-name-proof and give a sufficient
# condition for it to be: concavity of the surplus function over bidders,
# W(S + i) - W(S) >= W(T + i) - W(T) for all S subset of T, i not in T.
import itertools, random

def welfare(bidders):
    """max over: one bidder takes AB, or A and B go to two different bidders."""
    w = max([0.0] + [t[2] for t in bidders])
    for i, s in enumerate(bidders):
        for j, t in enumerate(bidders):
            if i != j:
                w = max(w, s[0] + t[1])
        w = max(w, s[0], s[1])
    return w

def outcome(bidders):
    """efficient allocation (labels per bidder) and VCG payments."""
    W = welfare(bidders); best = None
    for i, s in enumerate(bidders):
        if abs(s[2] - W) < 1e-9: best = {i: "AB"}
    for i, s in enumerate(bidders):
        for j, t in enumerate(bidders):
            if i != j and abs(s[0] + t[1] - W) < 1e-9 and best is None:
                best = {i: "A", j: "B"}
        if best is None and abs(max(s[0], s[1]) - W) < 1e-9:
            best = {i: "A" if s[0] >= s[1] else "B"}
    val = {"A": 0, "B": 1, "AB": 2}; pay = {}
    for i, lab in best.items():
        rest = bidders[:i] + bidders[i + 1:]
        pay[i] = welfare(rest) - (W - bidders[i][val[lab]])
    return best, pay

def gain_from_split(me, others, grid):
    al, py = outcome([me] + others)
    u0 = (me[{"A": 0, "B": 1, "AB": 2}[al[0]]] - py[0]) if 0 in al else 0.0
    top = (0.0, None)
    for x in grid:
        for y in grid:
            al, py = outcome([(x, 0.0, x), (0.0, y, y)] + others)
            got = {al[k] for k in (0, 1) if k in al}
            v = me[2] if got == {"A", "B"} else me[0] if got == {"A"} else \
                me[1] if got == {"B"} else 0.0
            u = v - py.get(0, 0.0) - py.get(1, 0.0)
            if u - u0 > top[0] + 1e-9:
                top = (u - u0, (x, y))
    return top

def concave(bidders):
    n = len(bidders); W = {}
    for r in range(n + 1):
        for S in itertools.combinations(range(n), r):
            W[S] = welfare([bidders[k] for k in S])
    for S, wS in W.items():
        for T, wT in W.items():
            if set(S) <= set(T):
                for i in set(range(n)) - set(T):
                    if (W[tuple(sorted(S + (i,)))] - wS) < (W[tuple(sorted(T + (i,)))]
                                                            - wT) - 1e-9:
                        return False
    return True

if __name__ == "__main__":
    grid = [g * 1.0 for g in range(0, 16)]
    me, rival = (0.0, 0.0, 10.0), (0.0, 0.0, 8.0)
    al, py = outcome([me, rival])
    g, xy = gain_from_split(me, [rival], grid)
    print(f"classic case: I value AB at 10, a rival at 8. Truthful: I win AB, pay"
          f" {py[0]:.1f}, utility {10 - py[0]:.1f}")
    print(f"  two fake identities bidding {xy[0]:.0f} for A and {xy[1]:.0f} for B:"
          f" utility up {g:.1f} (fakes pay 0)")
    rng = random.Random(2004)
    print("600 random markets per domain (manipulator + 3 rivals), split bids 0..15:")
    for dom in ("mixed: single-item, package and complementary bidders",
                "substitutes: every bidder has ab between max(a, b) and a + b"):
        n_conc = n_gain = n_both = 0; tot = 0.0
        for _ in range(600):
            def draw(manip):
                a, b = rng.uniform(0, 10), rng.uniform(0, 10)
                if dom.startswith("subs"):
                    return (a, b, max(a, b) + rng.random() * min(a, b))
                if manip:
                    return (a, b, (a + b) * rng.uniform(0.6, 1.6))
                k = rng.randrange(3)
                return (a, 0.0, a) if k == 0 else (0.0, b, b) if k == 1 else \
                       (0.0, 0.0, rng.uniform(0, 15))
            me = draw(True); others = [draw(False) for _ in range(3)]
            g, _ = gain_from_split(me, others, grid)
            c = concave([me] + others); n_conc += c; n_gain += g > 1e-9; tot += g
            n_both += c and g > 1e-9
        print(f"  {dom}")
        print(f"    concave over the real bidders {n_conc}/600; profitable split"
              f" {n_gain}/600; mean gain {tot / 600:.2f}")
        print(f"    concave over the real bidders AND profitable split:"
              f" {n_both}/{n_conc}")
    one, two = (7.0, 0.0, 7.0), [(5.0, 0.0, 5.0)]
    al, py = outcome([one] + two)
    print(f"single item (A only), value 7 vs a rival at 5: truthful pays {py[0]:.1f};"
          f" best split gain {gain_from_split(one, two, grid)[0]:.1f}")
# classic case: I value AB at 10, a rival at 8. Truthful: I win AB, pay 8.0, utility 2.0
#   two fake identities bidding 8 for A and 8 for B: utility up 8.0 (fakes pay 0)
# 600 random markets per domain (manipulator + 3 rivals), split bids 0..15:
#   mixed: single-item, package and complementary bidders
#     concave over the real bidders 406/600; profitable split 206/600; mean gain 1.70
#     concave over the real bidders AND profitable split: 169/406
#   substitutes: every bidder has ab between max(a, b) and a + b
#     concave over the real bidders 600/600; profitable split 0/600; mean gain 0.00
#     concave over the real bidders AND profitable split: 0/600
# single item (A only), value 7 vs a rival at 5: truthful pays 5.0; best split gain 0.0

In “mixed” markets with single-item bidders, package bidders and complementary values, 206 of 600 markets admit a profitable split, with mean gain 1.70; in markets where all bidders are substitutes (the value of the pair lies between the higher single value and the sum of the two), none of 600 does. One detail matters: in 406 of the mixed markets the surplus function is concave over the real bidders, yet 169 of them still admit a profitable split (the program’s “169/406”). The reason is that the concavity condition must hold over the whole domain of types, including the types a manipulator can declare. When a rival wants the pair and two fake identities want one item each, for example, the two fakes are complements of each other and concavity fails. Checking the real bidders is therefore not enough; what the rule-maker has to restrict is the set of types that may be declared. With a single item a fake identity only raises the second price one must pay, and splitting gains nothing, as the last line of the program confirms.

Note

False-name bids and Sybil attacks. False-name bidding is exactly the Sybil attack of auctions (Chapter 6): the rule treats each identity as a separate person, and identities are cheap. It shows that incentive compatibility is relative to the set of participants: VCG is strategy-proof for a given set of bidders, but not when participants can change how many people they are. Yokoo and co-authors and later work have proposed auction rules designed to be false-name-proof; they must give up some efficiency (Yokoo et al. 2004).

Hypothesis · not established · Split identities in bundled placements

The author’s hypothesis (not established): in brand-placement auctions that allow bundled bids for “sets of creators”, if the platform charges VCG-style externality prices without verifying identities, the share of bidders who split their bids over several accounts rises with the use of bundled bids. What would show it wrong: in a pre-registered observational study on an independent platform, no positive correlation between the share of multi-account bids identified by identity verification and the use of bundled bids (a confidence interval for the correlation that includes zero or is negative). The book uses no data from the author’s businesses and does not run this test.

Chapter summary

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.

References

Ausubel, Lawrence M., and Paul Milgrom. 2006. “The Lovely but Lonely Vickrey Auction.” In Combinatorial Auctions, edited by Peter Cramton, Yoav Shoham, and Richard Steinberg. MIT Press.
Clarke, Edward H. 1971. “Multipart Pricing of Public Goods.” Public Choice 11: 17–33.
Day, Robert, and Paul Milgrom. 2008. “Core-Selecting Package Auctions.” International Journal of Game Theory 36 (3–4): 393–407.
Groves, Theodore. 1973. “Incentives in Teams.” Econometrica 41 (4): 617–31.
Lucking-Reiley, David. 2000. “Vickrey Auctions in Practice: From Nineteenth-Century Philately to Twenty-First-Century e-Commerce.” Journal of Economic Perspectives 14 (3): 183–92.
Rothkopf, Michael H. 2007. “Thirteen Reasons Why the Vickrey–Clarke–Groves Process Is Not Practical.” Operations Research 55 (2): 191–97. https://doi.org/10.1287/opre.1070.0384.
Rothkopf, Michael H., Thomas J. Teisberg, and Edward P. Kahn. 1990. “Why Are Vickrey Auctions Rare?” Journal of Political Economy 98 (1): 94–109.
Varian, Hal R., and Christopher Harris. 2014. “The VCG Auction in Theory and Practice.” American Economic Review 104 (5): 442–45.
Vickrey, William. 1961. “Counterspeculation, Auctions, and Competitive Sealed Tenders.” Journal of Finance 16 (1): 8–37. https://doi.org/10.1111/j.1540-6261.1961.tb02789.x.
Yokoo, Makoto, Yuko Sakurai, and Shigeo Matsubara. 2004. “The Effect of False-Name Bids in Combinatorial Auctions: New Fraud in Internet Auctions.” Games and Economic Behavior 46 (1): 174–88. https://doi.org/10.1016/S0899-8256(03)00045-9.

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