Vickrey’s second-price auction

In 1961 the economist William Vickrey published a long paper on auctions and sealed tenders in the Journal of Finance. He analysed several auction formats, the best known of which is the sealed-bid second-price auction: everyone writes down a bid, the highest bidder wins, but pays only the second-highest bid (Vickrey 1961).

The rule looks odd: why let the winner pay less? Vickrey’s answer was that, precisely because the price the winner pays does not depend on her own bid, nobody needs to guess what others will bid; each bidder need only write down her true value.

# Second-price auction: highest bid wins, pays the best rival bid r (ties split).
# Check on a grid: bidding one's value v is never worse than any other bid b, for any r.
GRID = [round(k * 0.01, 2) for k in range(101)]

def payoff(v, b, r):
    return v - r if b > r else (v - r) / 2 if b == r else 0.0

worse, strict = 0, 0
for v in GRID:
    for b in GRID:
        d = [payoff(v, v, r) - payoff(v, b, r) for r in GRID]
        worse += sum(x < -1e-12 for x in d)
        strict += b != v and any(x > 1e-12 for x in d)
print(f"{len(GRID) ** 3:,} (value, bid, rival) cases; truthful bid worse: {worse} times")
print(f"untruthful (value, bid) pairs that lose strictly to some rival bid: {strict:,}")
print("v = 0.60; payoff when the best rival bid is 0.30 / 0.50 / 0.70 / 0.90:")
for b in (0.40, 0.60, 0.80):
    row = "  ".join(f"{payoff(0.6, b, r):+.2f}" for r in (.3, .5, .7, .9))
    print(f"  bid {b:.2f}: {row}")
# 1,030,301 (value, bid, rival) cases; truthful bid worse: 0 times
# untruthful (value, bid) pairs that lose strictly to some rival bid: 10,100
# v = 0.60; payoff when the best rival bid is 0.30 / 0.50 / 0.70 / 0.90:
#   bid 0.40: +0.30  +0.00  +0.00  +0.00
#   bid 0.60: +0.30  +0.10  +0.00  +0.00
#   bid 0.80: +0.30  +0.10  -0.10  +0.00

Across 101 × 101 × 101 = 1,030,301 combinations of value, bid and best rival bid, the truthful bid is never worse than another bid, and every one of the 10,100 untruthful (value, bid) pairs loses strictly against at least one rival bid. The example with value 0.6 shows the cost of both mistakes: bidding 0.4 (shading) misses a gain of 0.1 when the rival bids 0.5; bidding 0.8 (overbidding) wins a deal that loses 0.1 when the rival bids 0.7.

First-price auctions: shading is an equilibrium, not a gamble

In a first-price auction the winner pays her own bid. Bidding one’s value is then no longer sensible: winning at a bid equal to one’s value yields nothing. So people “shade”, bidding below their value.

Shading is often described as “betting that rivals will bid lower”. It is more accurate to say that, in the standard model, shading is an equilibrium strategy that can be calculated exactly.

The revenue equivalence theorem says that in this class of models, as long as the object always goes to the bidder with the highest value and the lowest type expects zero payoff, every auction format gives the seller the same expected revenue (Myerson 1981; Riley and Samuelson 1981). Here that expected revenue is the expected second-highest value, $(n-1)/(n+1)$.

# First-price auction, n risk-neutral bidders, values i.i.d. uniform on [0, 1].
# If rivals bid (n-1)v/n, a bid b wins with probability (n b / (n-1))^(n-1).
# Find the best b on a grid.
import random

def best_bid(v, n, steps=20000):
    bids = [(n - 1) / n * k / steps for k in range(steps + 1)]
    return max(bids, key=lambda b: (v - b) * (n * b / (n - 1)) ** (n - 1))

print("best reply / formula (n-1)v/n")
for n in (2, 3, 5, 10):
    row = "  ".join(f"v={v}: {best_bid(v, n):.3f}/{(n - 1) * v / n:.3f}"
                    for v in (.3, .6, .9))
    print(f"  n = {n:2d}: {row}")
rng, R = random.Random(11), 100000
mean = lambda xs: sum(xs) / len(xs)
sd = lambda xs, m: (sum((x - m) ** 2 for x in xs) / len(xs)) ** 0.5
print("mean revenue in 100,000 auctions")
print("  n | first  | second | all-pay | (n-1)/(n+1) | sd first | sd second")
for n in (2, 3, 5):
    fp, sp, ap = [], [], []
    for _ in range(R):
        v = sorted(rng.random() for _ in range(n))
        fp.append((n - 1) / n * v[-1])                    # winner pays own bid
        sp.append(v[-2])                                  # winner pays 2nd value
        ap.append(sum((n - 1) / n * x ** n for x in v))   # all pay own bids
    m1, m2 = mean(fp), mean(sp)
    print(f"  {n} | {m1:.4f} | {m2:.4f} | {mean(ap):.4f}  |   {(n - 1) / (n + 1):.4f}"
          "    |"
          f"  {sd(fp, m1):.3f}   |  {sd(sp, m2):.3f}")
# best reply / formula (n-1)v/n
#   n =  2: v=0.3: 0.150/0.150  v=0.6: 0.300/0.300  v=0.9: 0.450/0.450
#   n =  3: v=0.3: 0.200/0.200  v=0.6: 0.400/0.400  v=0.9: 0.600/0.600
#   n =  5: v=0.3: 0.240/0.240  v=0.6: 0.480/0.480  v=0.9: 0.720/0.720
#   n = 10: v=0.3: 0.270/0.270  v=0.6: 0.540/0.540  v=0.9: 0.810/0.810
# mean revenue in 100,000 auctions
#   n | first  | second | all-pay | (n-1)/(n+1) | sd first | sd second
#   2 | 0.3333 | 0.3335 | 0.3333  |   0.3333    |  0.118   |  0.236
#   3 | 0.5004 | 0.4990 | 0.4995  |   0.5000    |  0.129   |  0.223
#   5 | 0.6670 | 0.6661 | 0.6661  |   0.6667    |  0.112   |  0.178

When rivals bid $(n-1)v/n$, the numerically computed best reply agrees with the formula in every case to three decimal places, confirming that it is an equilibrium. The average revenue of all three auctions is within 0.002 of the theoretical $(n-1)/(n+1)$: that is revenue equivalence. But only the expectation is equal. The standard deviation of revenue in the second-price auction is clearly larger than in the first-price auction (twice as large with two bidders, 0.236 against 0.118; about 1.6 times with five, 0.178 against 0.112), so for a risk-averse seller the two are not the same.

So shading is neither gambling nor something everyone does “just right”. Theory provides a risk-neutral benchmark; real people fear losing more and often bid above it.

VCG: lovely but lonely

Vickrey’s idea extends to many objects and to public decisions. The work of Clarke (1971) and Groves (1973), of which the pivot mechanism of the previous chapter is one example, gives a general construction: choose the option with the largest reported total value, and have each person pay the loss her presence imposes on everyone else (Clarke 1971; Groves 1973). This is the Vickrey–Clarke–Groves (VCG) mechanism. It makes truthful reporting a dominant strategy and achieves an efficient allocation.

Yet in a paper titled “The lovely but lonely Vickrey auction”, Ausubel and Milgrom pointed out that almost no one uses it in practice, and not only because it is computationally demanding (Ausubel and Milgrom 2006).

# VCG with items A, B and package bids (after a kind of example in Ausubel-Milgrom 2006):
# pick the allocation with the largest reported value; each winner pays the loss her
# presence imposes on the others. Bidder 1 wants only AB, 2 only A, 3 only B.
from itertools import product

def best(bids, out=None):
    top, alloc = 0.0, {}
    names = [n for n in bids if n != out]
    for pick in product(*[[None] + list(bids[n]) for n in names]):
        items = [i for p in pick if p for i in p]
        val = sum(bids[n][p] for n, p in zip(names, pick) if p)
        if len(items) == len(set(items)) and val > top + 1e-12:
            top, alloc = val, {n: p for n, p in zip(names, pick) if p}
    return top, alloc

def vcg(label, bids):
    total, alloc = best(bids)
    pay = {n: best(bids, n)[0] - (total - bids[n][p]) for n, p in alloc.items()}
    w = " ".join(f"{n}:{p}" for n, p in alloc.items())
    pays = " ".join(f"{n}:{x:.1f}" for n, x in pay.items())
    print(f"{label:34s}| wins {w:8s}| pays {pays:16s}| revenue {sum(pay.values()):.1f}")

vcg("AB=2 (1), A=2 (2), B=2 (3)", {"1": {"AB": 2}, "2": {"A": 2}, "3": {"B": 2}})
vcg("AB=2 (1), A=2 (2), 3 absent", {"1": {"AB": 2}, "2": {"A": 2}})
vcg("AB=2 (1), A=0.5 (2), B=0.5 (3)", {"1": {"AB": 2}, "2": {"A": .5}, "3": {"B": .5}})
# Weakness, not a method: if the two LOSING bidders both overstate, both win and pay 0.
# Such coordination is unlawful bid rigging in most jurisdictions.
vcg("same, but 2 and 3 each report 2", {"1": {"AB": 2}, "2": {"A": 2}, "3": {"B": 2}})
# AB=2 (1), A=2 (2), B=2 (3)        | wins 2:A 3:B | pays 2:0.0 3:0.0     | revenue 0.0
# AB=2 (1), A=2 (2), 3 absent       | wins 2:A     | pays 2:2.0           | revenue 2.0
# AB=2 (1), A=0.5 (2), B=0.5 (3)    | wins 1:AB    | pays 1:1.0           | revenue 1.0
# same, but 2 and 3 each report 2   | wins 2:A 3:B | pays 2:0.0 3:0.0     | revenue 0.0

The first two rows show that revenue is not monotonic. With all three present, A and B go to bidders 2 and 3 (total value 4 against bidder 1’s 2), but neither pays anything: the seller’s revenue is 0. If bidder 3 is absent, revenue is 2 (bidders 1 and 2 then tie; the program breaks the tie by order, which does not affect revenue). Adding a competitor cut revenue from 2 to 0.

The last two rows show another weakness. When bidders 2 and 3 truly value their items at only 0.5, bidder 1 should win the package and pay 1. But if two bidders who should lose both inflate their reports to 2, they both win and both pay nothing. In other words, VCG is especially fragile against coordination among losing bidders; a single bidder participating under several false identities may also gain (Ausubel and Milgrom 2006).

VCG has other practical difficulties. Reporting true values amounts to handing one’s commercial secrets to the auctioneer; the number of package values grows exponentially with the number of items; and the final prices may be far below what the seller considers “reasonable”, making the outcome politically hard to accept. The theoretically cleanest rule often has to give way in practice to more transparent and more robust ones.

Chapter summary

The second-price auction makes the winner pay the second-highest bid, so that one’s own bid determines only whether one wins, not the price; truthful bidding is therefore weakly dominant, as the program verified across more than a million combinations. Laboratory subjects nevertheless often overbid. In the first-price auction, shading is an equilibrium strategy that can be derived: with $n$ bidders and independent uniform private values, $b(v) = (n-1)v/n$; laboratory bids are often above this risk-neutral benchmark. Revenue equivalence means that first-price, second-price and all-pay auctions yield the same expected revenue, though with different risk. In theory VCG achieves truthful reporting and efficient allocation; in practice it can yield very low revenue, revenue that falls as bidders are added, and is fragile against coordination among losers and false identities. The next chapter asks how hard things become when both buyer and seller hold private information.