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 nn bidders be independent and identically distributed with distribution function FF and density f>0f > 0 on [v_,v‾][\underline v, \bar v]. A direct mechanism specifies, for each report profile vv, the probability qi(v)q_i(v) that ii gets the object and his payment ti(v)t_i(v). Write Qi(vi)=Ev−i[qi(v)]Q_i(v_i) = E_{v_{-i}}[q_i(v)] and Ti(vi)=Ev−i[ti(v)]T_i(v_i) = E_{v_{-i}}[t_i(v)]; the expected utility of type viv_i reporting truthfully is Ui(vi)=viQi(vi)−Ti(vi)U_i(v_i) = v_i Q_i(v_i) – T_i(v_i).

Lemma (Myerson). The mechanism is Bayesian incentive compatible if and only if (a) QiQ_i is non-decreasing and (b) Ui(vi)=Ui(v_)+∫v_viQi(s)dsU_i(v_i) = U_i(\underline v) + \int_{\underline v}^{v_i} Q_i(s)\,ds.

Sketch of proof. Incentive compatibility means Ui(v)=max⁡r[vQi(r)−Ti(r)]U_i(v) = \max_r\,[v Q_i(r) – T_i(r)], the upper envelope of a family of functions linear in vv, hence convex, differentiable almost everywhere with derivative Qi(v)Q_i(v) (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 vv from reporting rr is Ui(v)−[vQi(r)−Ti(r)]=∫rv[Qi(s)−Qi(r)]ds≥0U_i(v) – [vQ_i(r) – T_i(r)] = \int_r^v [Q_i(s) – Q_i(r)]\,ds \ge 0.

The revenue formula. From Ti=vQi−UiT_i = v Q_i – U_i and (b), exchanging the order of integration gives

E[Ui(vi)]=Ui(v_)+∫v_v‾(1−F(s))Qi(s)ds=Ui(v_)+E[1−F(vi)f(vi)Qi(vi)],E[U_i(v_i)] = U_i(\underline v) + \int_{\underline v}^{\bar v} (1 – F(s))\,Q_i(s)\,ds = U_i(\underline v) + E\Big[\tfrac{1-F(v_i)}{f(v_i)}\,Q_i(v_i)\Big],

so the seller’s expected revenue is

∑iE[Ti(vi)]=E[∑iψ(vi)qi(v)]−∑iUi(v_),ψ(v)=v−1−F(v)f(v).\sum_i E[T_i(v_i)] = E\Big[\sum_i \psi(v_i)\,q_i(v)\Big] – \sum_i U_i(\underline v), \qquad \psi(v) = v – \frac{1 – F(v)}{f(v)} .

ψ\psi is the virtual value. Expected revenue equals “expected virtual surplus” minus the utility of the lowest types. Individual rationality requires Ui(v_)≥0U_i(\underline v) \ge 0, 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 ψ\psi 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 r*=ψ−1(0)r^* = \psi^{-1}(0). The reserve depends only on FF and not on the number of bidders. For the uniform distribution on [0,1][0,1], ψ(v)=2v−1\psi(v) = 2v – 1 and r*=1/2r^* = 1/2; for the exponential distribution with parameter λ\lambda, ψ(v)=v−1/λ\psi(v) = v – 1/\lambda and r*=1/λr^* = 1/\lambda. Bulow and Roberts pointed out that, in quantile space, ψ\psi 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, ψ\psi, the optimal reserve and the revenue of a second-price auction with no reserve and with the optimal reserve for n=1,…,5n = 1, \dots, 5 (numerical integration of Rn(r)=∫rψ(v)nF(v)n−1f(v)dvR_n(r) = \int_r \psi(v)\,n F(v)^{n-1} f(v)\,dv), 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 ln⁡v∼N(0,0.52)\ln v \sim N(0, 0.5^2) 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 n+1n+1 bidders and no reserve is at least the expected revenue of any mechanism, including Myerson’s optimal auction, with nn bidders.

Idea of proof. Consider mechanisms with n+1n+1 bidders that “must sell”. One of them is: run the optimal auction among the first nn bidders and, if the object is not sold, give it free to bidder n+1n+1. It is incentive compatible, always sells, and earns exactly Rn(r*)R_n(r^*). 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 Rn+1(0)≥Rn(r*)R_{n+1}(0) \ge R_n(r^*).

The last column of the program’s tables holds for all three distributions and all n=1,…,5n = 1,\dots,5. 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 ψ\psi 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 q=1−F(v)q = 1 – F(v), define the revenue curve R(q)=qv(q)R(q) = q\,v(q) (the revenue from selling to one person at price v(q)v(q), which is accepted with probability qq); ψ\psi is R′(q)R'(q). The distribution is regular if and only if RR is concave. If it is not, replace RR by its concave hull (the smallest concave function above it) R‾\bar R and use R‾′\bar R' as the ironed virtual value ψ‾\bar\psi: on intervals where RR and R‾\bar R differ, ψ‾\bar\psi 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 ψ‾\bar\psi, with expected revenue ∫ψ‾(q)+n(1−q)n−1dq\int \bar\psi(q)^+\,n(1-q)^{n-1}\,dq.

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 (1−F)/f(1-F)/f is large there and ψ\psi 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 monotone

ψ\psi is +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 ψ\psi would give a “virtual surplus” of 1.8757, above the optimum, but that rule cannot be implemented: a bidder with value 2.9 (ψ=+1.95\psi = +1.95) can win while one with value 3.5 (ψ=−7.00\psi = -7.00) never can; a higher value gets the object less often, and no payment rule can make him tell the truth.

Left: virtual values of three regular distributions; where they cross zero is the optimal reserve (uniform 0.5, exponential 1, lognormal 0.7719). Right: revenue curve R(q) of the non-regular distribution (solid) and its concave hull (dashed); where they separate is the ironed interval.

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 ψ−1(0)\psi^{-1}(0), 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

Bulow, Jeremy, and Paul Klemperer. 1996. “Auctions versus Negotiations.” American Economic Review 86 (1): 180–94.
Bulow, Jeremy, and John Roberts. 1989. “The Simple Economics of Optimal Auctions.” Journal of Political Economy 97 (5): 1060–90.
Crémer, Jacques, and Richard P. McLean. 1988. “Full Extraction of the Surplus in Bayesian and Dominant Strategy Auctions.” Econometrica 56 (6): 1247–57.
Myerson, Roger B. 1981. “Optimal Auction Design.” Mathematics of Operations Research 6 (1): 58–73.
Myerson, Roger B., and Mark A. Satterthwaite. 1983. “Efficient Mechanisms for Bilateral Trading.” Journal of Economic Theory 29 (2): 265–81.
Riley, John G., and William F. Samuelson. 1981. “Optimal Auctions.” American Economic Review 71 (3): 381–92.

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