5D Library › Mechanism Design, Vickrey–Clarke–Groves Auctions and Incentive-Compatible Community Engineering · 中文
Chapter 4 Myerson’s Optimal Auction: Virtual Values, Reserve Prices and Ironing
The question
The VCG and GSP auctions of the previous chapters aim at efficiency: giving the object to whoever values it most. Sellers often care about revenue. Myerson’s 1981 paper answered a question that seems impossible to approach: among all possible auction rules, which maximises the seller’s expected revenue (Myerson 1981)? Thanks to the revelation principle (Chapter 1), one need only search among incentive-compatible direct mechanisms. This chapter gives the full derivation, verifies the results for regular distributions by program and treats “ironing” for non-regular ones. Riley and Samuelson obtained equivalent results in the symmetric case at the same time (Riley and Samuelson 1981).
Derivation
Let the values of bidders be independent and identically distributed with distribution function and density on . A direct mechanism specifies, for each report profile , the probability that gets the object and his payment . Write and ; the expected utility of type reporting truthfully is .
Lemma (Myerson). The mechanism is Bayesian incentive compatible if and only if (a) is non-decreasing and (b) .
Sketch of proof. Incentive compatibility means , the upper envelope of a family of functions linear in , hence convex, differentiable almost everywhere with derivative (the envelope theorem); the derivative of a convex function is non-decreasing, which gives (a), and integrating gives (b). Conversely, if (a) and (b) hold, the loss of type from reporting is .
The revenue formula. From and (b), exchanging the order of integration gives
so the seller’s expected revenue is
is the virtual value. Expected revenue equals “expected virtual surplus” minus the utility of the lowest types. Individual rationality requires , which is zero at the optimum. Revenue maximisation therefore reduces to: for each report profile, give the object to the bidder with the highest virtual value, provided it is positive; otherwise do not sell.
The regular case. If is increasing (the distribution is regular), this allocation rule is monotone, satisfies condition (a) of the lemma and can be implemented; it is a second-price auction with reserve . The reserve depends only on and not on the number of bidders. For the uniform distribution on , and ; for the exponential distribution with parameter , and . Bulow and Roberts pointed out that, in quantile space, is exactly the marginal revenue of monopoly pricing theory, and the optimal auction “sells in order of marginal revenue and does not sell at negative marginal revenue” (Bulow and Roberts 1989).
The program below computes, for three regular distributions, , the optimal reserve and the revenue of a second-price auction with no reserve and with the optimal reserve for (numerical integration of ), and checks one value by Monte Carlo. The last two columns of each table concern the Bulow–Klemperer theorem, discussed in the next section.
Calculation
# Chapter 4. Myerson (1981) for regular distributions. Virtual value
# psi(v) = v - (1 - F(v)) / f(v); expected revenue = expected virtual surplus; with
# i.i.d. regular bidders the optimal auction is a second-price auction with reserve
# r* = psi^-1(0), whatever the number of bidders. Revenue of a second-price auction with
# reserve r and n bidders: R_n(r) = integral_r^inf psi(v) n F(v)^(n-1) f(v) dv.
# Bulow-Klemperer (1996): R_{n+1}(0) >= R_n(r*) for regular distributions.
import math, random, statistics
LN = statistics.NormalDist(0.0, 0.5) # log-value of the lognormal
DISTS = {
"uniform[0,1]": (lambda v: v, lambda v: 1.0, 0.0, 1.0),
"exponential(1)": (lambda v: 1 - math.exp(-v), lambda v: math.exp(-v), 0.0, 25.0),
"lognormal(0,.5)": (lambda v: LN.cdf(math.log(v)),
lambda v: LN.pdf(math.log(v)) / v, 1e-6, math.exp(4.0)),
}
def psi(F, f, v):
return v - (1 - F(v)) / f(v)
def simpson(g, a, b, m=4000):
h = (b - a) / m
s = g(a) + g(b) + math.fsum((4 if k % 2 else 2) * g(a + k * h)
for k in range(1, m))
return s * h / 3
def revenue(F, f, hi, n, r, lo):
return simpson(lambda v: psi(F, f, v) * n * F(v) ** (n - 1) * f(v), max(r, lo), hi)
def reserve(F, f, lo, hi):
a, b = lo + 1e-9, hi
for _ in range(100): # bisection on psi(v) = 0
m = (a + b) / 2
a, b = (m, b) if psi(F, f, m) < 0 else (a, m)
return (a + b) / 2
if __name__ == "__main__":
for name, (F, f, lo, hi) in DISTS.items():
xs = [lo + (hi - lo) * k / 400 for k in range(1, 400)]
xs = [x for x in xs if F(x) < 0.999999]
mono = all(psi(F, f, a) <= psi(F, f, b) + 1e-12 for a, b in zip(xs, xs[1:]))
r = reserve(F, f, lo, hi)
print(f"{name}: psi increasing on the grid: {mono}; optimal reserve {r:.4f}")
print(" n R_n(0) R_n(r*) gain R_n+1(0) Bulow-Klemperer holds")
for n in range(1, 6):
r0, rs = revenue(F, f, hi, n, 0.0, lo), revenue(F, f, hi, n, r, lo)
r1 = revenue(F, f, hi, n + 1, 0.0, lo)
g = f"{rs / r0 - 1:6.1%}" if r0 > 1e-6 else " n/a"
print(f" {n} {abs(r0):7.4f} {rs:8.4f} {g} {r1:8.4f} {r1 >= rs - 1e-9}")
rng = random.Random(1981); tot = 0.0; N = 200000
for _ in range(N):
a, b = sorted((rng.random(), rng.random()))
tot += max(a, 0.5) if b >= 0.5 else 0.0
print(f"Monte Carlo, uniform, n = 2, reserve 0.5: {tot / N:.4f} (exact 5/12 ="
f" {5 / 12:.4f})")
# uniform[0,1]: psi increasing on the grid: True; optimal reserve 0.5000
# n R_n(0) R_n(r*) gain R_n+1(0) Bulow-Klemperer holds
# 1 0.0000 0.2500 n/a 0.3333 True
# 2 0.3333 0.4167 25.0% 0.5000 True
# 3 0.5000 0.5312 6.2% 0.6000 True
# 4 0.6000 0.6125 2.1% 0.6667 True
# 5 0.6667 0.6719 0.8% 0.7143 True
# exponential(1): psi increasing on the grid: True; optimal reserve 1.0000
# n R_n(0) R_n(r*) gain R_n+1(0) Bulow-Klemperer holds
# 1 0.0000 0.3679 n/a 0.5000 True
# 2 0.5000 0.6681 33.6% 0.8333 True
# 3 0.8333 0.9172 10.1% 1.0833 True
# 4 1.0833 1.1273 4.1% 1.2833 True
# 5 1.2833 1.3071 1.9% 1.4500 True
# lognormal(0,.5): psi increasing on the grid: True; optimal reserve 0.7719
# n R_n(0) R_n(r*) gain R_n+1(0) Bulow-Klemperer holds
# 1 0.0000 0.5386 n/a 0.8200 True
# 2 0.8200 0.8554 4.3% 1.0577 True
# 3 1.0577 1.0643 0.6% 1.2139 True
# 4 1.2139 1.2154 0.1% 1.3322 True
# 5 1.3322 1.3326 0.0% 1.4280 True
# Monte Carlo, uniform, n = 2, reserve 0.5: 0.4166 (exact 5/12 = 0.4167)For the uniform distribution the reserve is 0.5000, and with two bidders revenue rises from 1/3 to 5/12 = 0.4167 (Monte Carlo 0.4166), an increase of 25.0 %; for the exponential distribution the reserve is 1 and the increase with two bidders 33.6 %; for the lognormal distribution the reserve is 0.7719 and the increase with two bidders only 4.3 %. For all three distributions the gain from the reserve shrinks quickly with the number of bidders: with five it is only 0.8 %, 1.9 % and 0.0 %.
The Bulow–Klemperer theorem
Theorem (Bulow and Klemperer 1996). If values are independent and identically distributed and the distribution is regular, the expected revenue of an English (or second-price) auction with bidders and no reserve is at least the expected revenue of any mechanism, including Myerson’s optimal auction, with bidders.
Idea of proof. Consider mechanisms with bidders that “must sell”. One of them is: run the optimal auction among the first bidders and, if the object is not sold, give it free to bidder . It is incentive compatible, always sells, and earns exactly . On the other hand, among mechanisms that must sell, expected revenue equals expected virtual surplus, which is maximised by giving the object to the bidder with the highest virtual value; under regularity that is the bidder with the highest value, i.e. the auction without reserve. Hence .
The last column of the program’s tables holds for all three distributions and all . Its practical meaning is that attracting one more similar bidder is worth more than carefully computing a reserve. But the theorem needs two conditions: bidders are identically distributed, and the distribution is regular.
Non-regular distributions and ironing
If is not monotone, “give the object to the highest virtual value” is not a monotone allocation rule, violates condition (a) and cannot be implemented. Myerson’s remedy is ironing. In quantile space , define the revenue curve (the revenue from selling to one person at price , which is accepted with probability ); is . The distribution is regular if and only if is concave. If it is not, replace by its concave hull (the smallest concave function above it) and use as the ironed virtual value : on intervals where and differ, is constant and all types in the interval are treated alike (bidders within the same interval share the object at random). The optimal mechanism allocates by , with expected revenue .
The program below builds a non-regular distribution: the value is uniform on [0,3] with probability 0.78, uniform on [3,4] with probability 0.02 and uniform on [4,5] with probability 0.20. The middle band is thin, so is large there and drops abruptly.
Calculation
# Chapter 4. A non-regular distribution and Myerson's ironing. Values are piecewise
# uniform: weight 0.78 on [0,3], 0.02 on [3,4], 0.20 on [4,5] (a thin middle band). In
# quantile space (q = 1 - F(v)) the revenue curve is R(q) = q v(q) and psi = R'(q).
# Where R is not concave psi is not monotone; ironing replaces R by its concave hull,
# whose slope is the ironed virtual value psi_bar. With n i.i.d. bidders the optimal
# revenue is integral psi_bar(q)^+ n (1 - q)^(n-1) dq (ties inside an ironed interval
# are broken at random); any monotone allocation earns its expected unironed virtual
# surplus, so a second-price auction with reserve r earns the integral of psi over v >= r.
import math, random
PIECES = [(0.20, 4.0, 5.0), (0.02, 3.0, 4.0), (0.78, 0.0, 3.0)] # from the top down
M = 20000
def v_of_q(q):
acc = 0.0
for w, lo, hi in PIECES:
if q <= acc + w:
return hi - (hi - lo) * (q - acc) / w
acc += w
return 0.0
def psi_v(v):
acc = 0.0 # acc = 1 - F at the top of piece
for w, lo, hi in PIECES:
if v >= lo:
f = w / (hi - lo); tail = acc + w * (hi - v) / (hi - lo)
return v - tail / f
acc += w
return -1e9
Q = [k / M for k in range(M + 1)]
R = [q * v_of_q(q) for q in Q]
def hull(xs, ys): # upper concave hull
h = []
for p in zip(xs, ys):
while len(h) >= 2 and ((h[-1][0] - h[-2][0]) * (p[1] - h[-2][1]) -
(h[-1][1] - h[-2][1]) * (p[0] - h[-2][0])) >= 0:
h.pop()
h.append(p)
return h
H = hull(Q, R); BAR = [0.0] * M; j = 0
for k in range(M): # slope of the hull on cell k
qm = (Q[k] + Q[k + 1]) / 2
while H[j + 1][0] < qm:
j += 1
BAR[k] = (H[j + 1][1] - H[j][1]) / (H[j + 1][0] - H[j][0])
RAW = [(R[k + 1] - R[k]) * M for k in range(M)]
def weight(k, n):
return n * (1 - (k + 0.5) / M) ** (n - 1) / M
def optimal(n):
return math.fsum(max(BAR[k], 0.0) * weight(k, n) for k in range(M))
def spa_table(n): # cumulative revenue by reserve cell
out, s = [], 0.0
for k in range(M):
s += RAW[k] * weight(k, n); out.append(s)
return out
if __name__ == "__main__":
print(f"psi at 2.99: {psi_v(2.99):+.3f}; at 3.01: {psi_v(3.01):+.3f}; at 4.01:"
f" {psi_v(4.01):+.3f} -> not monotone")
flat = [k for k in range(M) if abs(RAW[k] - BAR[k]) > 1e-6]
qa, qb = flat[0] / M, (flat[-1] + 1) / M
print(f"ironed interval: values {v_of_q(qb):.3f} .. {v_of_q(qa):.3f}"
f" (quantiles {qa:.4f} .. {qb:.4f}), ironed psi {BAR[flat[0]]:+.4f}")
kstar = max(range(M + 1), key=lambda k: R[k])
print(f"monopoly (n = 1) price {v_of_q(kstar / M):.3f}, revenue {R[kstar]:.4f}")
for n in (2, 3, 5):
tab = spa_table(n); kb = max(range(M), key=lambda k: tab[k])
print(f"n = {n}: optimal (ironed) {optimal(n):.4f}; second price with best"
f" reserve {v_of_q((kb + 1) / M):.3f}: {tab[kb]:.4f}"
f" ({optimal(n) / tab[kb] - 1:+.2%})")
rng = random.Random(81); N = 200000; naive = 0.0
def draw():
u = rng.random()
for w, lo, hi in PIECES:
if u < w:
return rng.uniform(lo, hi)
u -= w
return 0.0
for _ in range(N):
naive += max(0.0, psi_v(draw()), psi_v(draw()))
print(f"n = 2: 'allocate by raw psi' virtual surplus {naive / N:.4f}"
f" > optimum {optimal(2):.4f}, not implementable:")
print(f" value 2.9 (psi {psi_v(2.9):+.2f}) can win, value 3.5 (psi"
f" {psi_v(3.5):+.2f}) never wins: not monotone")
# psi at 2.99: +2.134; at 3.01: -7.980; at 4.01: +3.020 -> not monotone
# ironed interval: values 2.234 .. 4.000 (quantiles 0.2000 .. 0.4191), ironed psi +0.6224
# monopoly (n = 1) price 1.923, revenue 0.9615
# n = 2: optimal (ironed) 1.6695; second price with best reserve 1.923: 1.6464 (+1.41%)
# n = 3: optimal (ironed) 2.2079; second price with best reserve 1.923: 2.1567 (+2.37%)
# n = 5: optimal (ironed) 2.9619; second price with best reserve 1.923: 2.8683 (+3.26%)
# n = 2: 'allocate by raw psi' virtual surplus 1.8757 > optimum 1.6695, not implementable:
# value 2.9 (psi +1.95) can win, value 3.5 (psi -7.00) never wins: not monotoneis +2.134 at 2.99, falls to −7.980 at 3.01 and returns to +3.020 at 4.01: not monotone. The ironed interval runs from values 2.234 to 4.000, and the ironed virtual value there is +0.6224 (positive, so these types do get the object, but without being ranked among themselves). With a single buyer the optimal posted price is 1.923, for revenue 0.9615. With two bidders the optimal (ironed) auction earns 1.6695 in expectation and the best “second-price auction with a reserve” 1.6464, 1.41 % less; with three and five bidders the optimal auction earns 2.37 % and 3.26 % more. Ignoring monotonicity and allocating by the raw would give a “virtual surplus” of 1.8757, above the optimum, but that rule cannot be implemented: a bidder with value 2.9 () can win while one with value 3.5 () never can; a higher value gets the object less often, and no payment rule can make him tell the truth.
Scope
Myerson’s result is one of the cleanest “optimality” results in this book, but every assumption carries weight. Identical distributions: when bidders differ, the optimal auction allocates by each bidder’s own virtual value, “discriminates” against some, does not always give the object to the highest bidder and is not a second-price auction with a reserve. Independent private values: with correlated values, the mechanisms constructed by Crémer and McLean can extract the full surplus (Crémer and McLean 1988), a different kind of result. A seller who can commit to the reserve: Chapter 1’s Coase problem shows that if the seller will re-auction after a failed sale, the reserve is not credible. Risk neutrality: with risk-averse bidders, revenue equivalence (Book 27) no longer holds.
The Myerson–Satterthwaite theorem (treated in Book 27) applies the same tools to bilateral trade: when buyer and seller both have private information and their value ranges overlap, no mechanism is efficient, incentive compatible, individually rational and free of subsidy at once (Myerson and Satterthwaite 1983); Book 27’s program showed that with uniform distributions the best mechanism realises only 84.375 % of the gains from trade, which is not repeated here.
Hypothesis · not established · Reserve prices for community rewards
The author’s hypothesis (not established): in online communities that auction scarce rewards for points (such as one-to-one mentoring slots), the increase in points revenue from one more bidder exceeds the increase from moving the reserve from zero to the level estimated as optimal from past bids (a community version of the Bulow–Klemperer theorem). What would show it wrong: in a pre-registered randomised comparison in independent communities, a mean clearing price in the “reserve” arm significantly higher than in the “one more bidder” arm. If the value distribution is clearly non-regular or participants are heterogeneous the theorem does not apply, and the test says nothing about it.
Chapter summary
Myerson’s lemma reduces incentive compatibility to “monotone allocation plus utility given by the envelope formula”, which yields “expected revenue = expected virtual surplus”. For regular distributions the optimal auction is a second-price auction with reserve , independent of the number of bidders (0.5 for the uniform, 1 for the exponential); the gain from the reserve shrinks quickly with more bidders, and the Bulow–Klemperer theorem says one more bidder beats the optimal reserve. Non-regular distributions require ironing: in the program’s example the optimal auction earns 1.4–3.3 % more than a second-price auction with the best reserve, and allocating by raw virtual values is not monotone and cannot be implemented.
References
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).