Approximate and Simple Mechanisms

Why VCG Is Rare in Practice is the demolition; this is the reconstruction. The optimal mechanism — the one that squeezes out every last cent or every last unit of welfare — is, in almost every setting past the textbook cases, complicated, fragile, and dependent on distributional knowledge nobody has. The response of the last two decades has been to give up optimality on purpose and ask for a provable constant factor instead, in exchange for mechanisms that are simple enough to explain, robust enough to survive being wrong about the prior, and often computable in polynomial time. Three results anchor the field. The prophet inequality (Samuel-Cahn 1984) says a single fixed threshold captures half of what a clairvoyant could get. Bulow–Klemperer (1996) says the plain Vickrey auction with one extra bidder beats the revenue-optimal auction with the original bidders — recruiting beats optimizing. And Hartline–Roughgarden’s Simple versus Optimal Mechanisms (EC’09) generalizes both to a large class of environments with small constants. The engineering thesis running underneath is Robert Wilson’s: mechanisms that depend less on the details of the environment are more likely to be relevant — and this note measures that claim rather than asserting it.

Everything numeric below was computed for this note

Bulow–Klemperer is verified in exact rational arithmetic (fractions.Fraction) for n = 1…12; the prophet inequality’s tightness is computed in closed form; the robustness claim is measured by simulating a misspecified optimal auction against a plain Vickrey auction over 400,000 trials per point. Code and outputs are reproduced inline. No external numerical library was used (none is installable here — no pip, no numpy).

---

1. Mental Model: three separate things “simple” can mean

“Simple” is doing a lot of work in this literature and it is worth separating the senses, because the three failure modes of optimal mechanisms are distinct and the fixes are distinct.

flowchart TB
    OPT["<b>The optimal mechanism</b><br/>Myerson: maximize virtual welfare<br/>φᵢ(vᵢ) = vᵢ − (1−Fᵢ(vᵢ))/fᵢ(vᵢ)"]
    OPT --> P1["<b>Descriptive complexity</b><br/>Someone other than the highest<br/>bidder may win. The payment is<br/>unexplainable without a lecture<br/>on virtual valuations."]
    OPT --> P2["<b>Computational complexity</b><br/>Welfare maximization is NP-hard<br/>in combinatorial and knapsack<br/>environments."]
    OPT --> P3["<b>Informational complexity</b><br/>Every parameter of the mechanism<br/>is read off the prior F₁…Fₙ.<br/>Wrong prior ⇒ wrong mechanism."]
    P1 --> F1["<b>Posted prices</b><br/>take-it-or-leave-it offers.<br/>Prophet inequality: 2-approx"]
    P2 --> F2["<b>Greedy allocation</b><br/>monotone + critical payments.<br/>Knapsack: 2-approx; single-minded<br/>CA: √m-approx (tight)"]
    P3 --> F3["<b>Prior-independent designs</b><br/>Bulow–Klemperer: recruit one<br/>more bidder, run Vickrey"]

What it shows: the three ways an optimal mechanism is hard to live with, and the specific simple-mechanism family that answers each. Insight to take: these are not three views of one problem. A posted price fixes explicability and gains collusion-resistance but does nothing about NP-hardness; a greedy allocation rule fixes tractability but is still parameterized by a prior if you put reserve prices on it; Bulow–Klemperer fixes the prior dependence but assumes you can solve the allocation problem. Real designs stack all three.

The measurement discipline throughout is the approximation ratio: mechanism M is a c-approximation if E[OPT] ≤ c · E[M] for every instance in the class. Hartline’s Mechanism Design and Approximation argues the right threshold is a constant: “for mechanism design super-constant approximations tend to be indicative of (a) a bad mechanism, (b) failure to appropriately characterize optimal mechanisms, or (c) an imposition of incompatible modeling assumptions.”

---

2. Posted prices

A posted price mechanism offers each agent a take-it-or-leave-it price. In an order-oblivious posted pricing (OPM) the agents arrive in an arbitrary — even adversarial — order and the first one whose value clears its offered price buys, while supplies last. In a sequential posted pricing (SPM) the mechanism also chooses the order.

Chawla, Hartline, Malec and Sivan enumerate four properties that make these the right primitive (CHMS 2010), and each is an engineering property rather than an economic one:

1. Trivial game dynamics. Truthful responding is a dominant strategy, and it is dominant for a reason a non-economist can state: you are being offered a price, and you should take it if it is below your value.
2. Group strategyproofness. “The only way in which an agent can ‘help’ another agent is to decline an offer that he could have accepted, thereby hurting his own utility.” Contrast §5 of Why VCG Is Rare in Practice, where losing bidders have profitable joint deviations that cost them nothing.
3. Minimal information exposure. An agent never states its value, only accepts or declines a number. This directly answers Rothkopf’s privacy objection to VCG — the winner of a Vickrey procurement reveals exactly how much surplus it holds, to every counterparty it must later negotiate with.
4. Immediate resolution. An agent learns at once whether it is served. No rounds, no waiting for a clearing computation.

Hartline adds a fifth, systems-flavoured argument: auctions “require multiple rounds of communication (i.e., they are slow) and … require all agents to be present at the time of the auction. Often both of these requirements are prohibitive. In routing in computer networks a packet needs to be routed, or not, quickly and, if the network is like the Internet, without state in the routers.” A posted price is a stateless admission decision, which is why the pattern recurs in congestion control and in Rate Limiting as a Mechanism far from any auction house.

The cost of the simplification, measured

CHMS give a hotel-room example with a clean closed form, which I recomputed exactly. One room, two attendees, values independent and identically distributed uniform on [100, 200]. For U[a,b] the virtual value is φ(v) = v − (b − v) = 2v − b, so the monopoly price φ⁻¹(0) = b/2 = 100 sits at the bottom of the support and the reserve does not bind: the optimal mechanism is the plain Vickrey auction. Its revenue is E[min of two draws] = a + (b−a)/3 = 100 + 100/3.

== (a) CHMS hotel-room example, EXACT
   optimal (= Vickrey, reserve does not bind): E[min] = 100 + 100/3 = 400/3 = 133.3333
   best sequential posted pricing over integer prices: p1=150, p2=100, revenue = 125 = 125.0000
   CHMS state $150 then $100 giving $125:  spm(150,100) = 125
   ratio SPM/OPT = 0.9375   (loss 6.25%)

Brute-forcing over all integer price pairs confirms CHMS’s stated optimum — offer $150 first, then $100 — and the exact revenue 125. The mechanism gives up 6.25% of revenue and in exchange never requires the two attendees to be in the room at the same time, never reveals anyone’s valuation, and cannot be gamed by a coalition. That is the trade in miniature.

---

3. The prophet inequality

The theorem that makes posted pricing provable comes from optimal stopping theory, and it is charming in its own right.

The game. A gambler faces n stages. At stage i a prize π_i is drawn from a distribution G_i; the distributions are independent and known in advance, but each realization is revealed only when its stage arrives. On seeing π_i the gambler may accept it and stop, or discard it forever and continue. Against her stands a prophet who sees all realizations up front and simply takes max_i π_i.

Theorem (Samuel-Cahn 1984). For every sequence G_1, …, G_n of independent distributions there is a strategy guaranteeing expected reward at least ½ · E[max_i π_i]. Moreover such a strategy can be a single fixed threshold t: accept the first prize with π_i ≥ t.

Uncertain

Verify: the exact statement and constant in Samuel-Cahn’s original paper. Reason: the primary source could not be retrieved — projecteuclid.org returned a 1,161-byte non-PDF for the article (Annals of Probability 12(4):1213–1216, 1984). The statement above is taken from two independent secondary treatments that were fetched and read in full: Roughgarden’s CS364A Lecture 6 (Theorem 2.1, with proof) and Hartline’s book (Theorem 4.7, with a different proof). They agree on the constant, the threshold form, and the median-threshold construction. To resolve: obtain the Annals of Probability paper. uncertain

Walking the proof

The proof is a two-sided sandwich and is worth doing symbol by symbol, because it explains why the constant is a half rather than something distribution-dependent. Write z⁺ = max{z, 0} and let q(t) = Pr[no prize is accepted] = Pr[π_j < t for all j].

Lower bound on the gambler. With probability 1 − q(t) she accepts something, worth at least t. Now credit her the excess above t, but only in realizations where exactly one prize clears the threshold — this is deliberately lazy, discarding value in the multi-clearing case:

E[gambler]  ≥  (1 − q(t))·t  +  Σᵢ E[(πᵢ − t)⁺] · Pr[πⱼ < t for all j ≠ i]
            ≥  (1 − q(t))·t  +  q(t) · Σᵢ E[(πᵢ − t)⁺]

The second line uses Pr[π_j < t ∀ j ≠ i] ≥ Pr[π_j < t ∀ j] = q(t) — dropping the constraint on coordinate i can only raise the probability. Independence is what licenses factoring the two probability terms apart.

Upper bound on the prophet. Add and subtract t:

E[maxᵢ πᵢ]  =  E[t + maxᵢ(πᵢ − t)]  ≤  t + E[maxᵢ(πᵢ − t)⁺]  ≤  t + Σᵢ E[(πᵢ − t)⁺]

— replacing a max of non-negative terms by their sum.

Choosing t. Set t so that q(t) = ½. Then the gambler’s bound reads ½t + ½ Σᵢ E[(πᵢ − t)⁺], which is exactly half the prophet’s bound t + Σᵢ E[(πᵢ − t)⁺]. Done.

flowchart LR
    subgraph LB["Gambler's payoff, bounded BELOW"]
        L1["(1−q)·t<br/><i>she accepts something<br/>worth at least t</i>"]
        L2["+ q · Σᵢ E[(πᵢ−t)⁺]<br/><i>credit the excess only when<br/>exactly one prize clears</i>"]
    end
    subgraph UB["Prophet's payoff, bounded ABOVE"]
        U1["t"]
        U2["+ Σᵢ E[(πᵢ−t)⁺]<br/><i>max of positives<br/>≤ sum of positives</i>"]
    end
    LB -->|"set q(t) = ½"| M["LB = ½ · UB<br/><b>ratio ≥ 1/2</b>"]
    UB --> M
    M --> T["<b>Two knobs, one dial.</b><br/>Raising t increases the risk q of<br/>getting nothing but raises the value<br/>of what is accepted. q = ½ balances them."]

What it shows: the two bounds and the single algebraic coincidence that makes them differ by a factor of two. Insight: the “extra credit only when exactly one prize clears” step is where the factor of 2 is spent. The gambler really does often get more than the bound — the bound throws away all the multi-clearing realizations — which is why measured ratios beat 1/2 comfortably on well-behaved instances.

Hartline’s proof takes a different route to a different threshold: the balanced threshold t̂ satisfying t̂ = Σᵢ E[(v_i − t̂)⁺], i.e. the threshold at which the value of the threshold equals the total expected excess above it. Both work; both give 2. Hartline additionally proves the bound is invariant to the tie-breaking rule when several prizes clear — including breaking ties by picking the worst clearing prize — which is exactly the property needed to carry the theorem over to adversarial arrival orders in a posted pricing.

The constant is tight, and my simulation initially said otherwise

The classic tight instance: prize 1 is the deterministic value 1; prize 2 is 1/ε with probability ε and 0 otherwise. Any single threshold either takes the guaranteed 1 or skips it, and skipping yields ε · (1/ε) = 1 in expectation — so the gambler gets exactly 1 either way. The prophet gets E[max] = (1−ε)·1 + ε·(1/ε) = 2 − ε.

== TIGHT INSTANCE, computed exactly (no simulation)
          eps  best single threshold     E[max]    ratio
          0.5               1.000000   1.500000   0.6667
          0.1               1.000000   1.900000   0.5263
         0.01               1.000000   1.990000   0.5025
        0.001               1.000000   1.999000   0.5003
        1e-06               1.000000   1.999999   0.5000
   -> ratio -> 1/2 from ABOVE as eps -> 0. The 1/2 in the Prophet Inequality is tight.

An earlier version of this measurement estimated E[max] by Monte Carlo on the ε = 0.001 instance and reported a ratio of 0.4802 — apparently violating the theorem. It does not: with 300,000 trials only ~300 hit the 1/1000 prize worth 1,000, so the estimator’s variance dwarfs the quantity being estimated. This is the standard trap of measuring heavy-tailed expectations by sampling, and the fix was to compute the two-point expectation in closed form. Recorded here because “my simulation contradicts the theorem” is almost always the simulation.

Which threshold rule to actually use

Two thresholds are natural: the median rule (Pr[accept nothing] = ½, which is the one the proof uses) and the half-of-max rule (t = ½ E[max_i π_i], which is the threshold used in Kleinberg and Weinberg’s matroid generalization). Both are 2-approximations in theory. In practice they are very different:

== Median-threshold rule on well-behaved instances (2,000,000 trials each)
              instance  t (median)       ALG    E[max]   ratio  t=E[max]/2      ALG2  ratio2
           10 x U[0,1]      0.9330    0.4826    0.9090  0.5310      0.4545    0.7269  0.7997
           10 x Exp(1)      2.7036    1.8493    2.9273  0.6317      1.4637    2.2850  0.7806
           50 x U[0,1]      0.9862    0.4967    0.9804  0.5067      0.4902    0.7451  0.7600
    10 x Pareto(a=1.5)      6.0640    9.0863   12.5429  0.7244      6.2714    9.0621  0.7225

The median rule sits barely above its worst-case guarantee on bounded distributions — 0.531 and 0.507 for 10 and 50 uniform prizes — because with many bounded prizes the median of the max is pushed right up against the top of the support (0.933 and 0.986), so the gambler is being very picky and frequently ends up with nothing. The half-of-max rule lands at 0.76–0.80 on the same instances. On the heavy-tailed Pareto instance the two coincide, which is the regime the median rule was designed for.

Engineering conclusion: the theorem tells you a threshold rule exists; it does not tell you which one to ship. Both rules have the same proof-derived constant, and one of them is 50% better on the instances you are likely to face. Simulate before choosing. Hartline makes the same point generically: “in specific environments the mechanism may perform better. It is easy, via simulation, to evaluate the mechanism performance on specific settings to see how close to optimal it actually is.”

From prophet to posted pricing

The bridge is one substitution. In the optimal auction the seller’s expected revenue equals expected virtual welfare (see Reserve Prices and Optimal Auctions), so for a single item the optimal revenue is E[max_i φ_i(v_i)⁺] — the prophet’s payoff, with prize i being bidder i’s clipped virtual value. Apply the prophet inequality in virtual-value space:

1. Pick t with Pr[max_i φ_i(v_i)⁺ ≥ t] = ½.
2. Set bidder-specific reserve prices r_i = φ_i⁻¹(t).
3. Award to the highest bidder clearing its own reserve.

Roughgarden’s Lecture 6 derives exactly this and observes the two ways it is qualitatively simpler than Myerson: virtual valuations now appear only in setting reserves, and the highest bidder wins as long as it clears its reserve — no more “someone other than the highest bidder might win.” Hartline’s Theorem 4.9 is the order-oblivious version: a uniform virtual price (equivalently, non-uniform posted prices in value space) yields at least half the optimal revenue under any arrival order.

The remaining wrinkle is that the reserves are bidder-specific and most real venues offer only one knob. eBay lets a seller set one opening bid. Roughgarden reports the state of the art for anonymous reserves as: at least 25% of optimal revenue is achievable, and no anonymous reserve always achieves more than 50%. Hartline–Roughgarden prove a 4-approximation for single-item settings with independent non-identical regular distributions, with a lower bound of 2 that they conjecture is tight.

Sequential posted pricing — where the mechanism also picks the order — improves the constant from 2 to e/(e−1) ≈ 1.58. CHMS obtain constants “range[ing] from 1.5 to 8” across multi-unit and matroid environments and, critically, extend them to multi-dimensional settings where no optimal mechanism is known at all.

---

4. Greedy allocation and the price of tractability

The second axis. When welfare maximization is NP-hard, an exact DSIC mechanism is unavailable at any price, so the question becomes: which approximation algorithms can be made truthful?

The answer for single-parameter environments is Myerson’s Lemma: an allocation rule is implementable in dominant strategies iff it is monotone (bidding higher never makes you lose), and the payments are then forced — the winner pays its critical value, the lowest bid at which it would still have won. So the design task is “find a monotone approximation algorithm,” and greedy algorithms are usually monotone because raising your bid moves you earlier in a greedy order.

Knapsack auctions. Bidders have private values v_i and public sizes w_i; a set is feasible if Σ w_i ≤ W. Roughgarden’s Lecture 4 gives the rule: sort by bang-per-buck b_i / w_i, pack greedily until one does not fit, and return the better of that packing and the single highest bidder. This is a ½-approximation. The proof is a fractional-relaxation argument: the greedy fractional solution is exactly optimal for fractional knapsack; if the first k bidders win integrally and the (k+1)-th fractionally, then step 2 collects the first k and step 3 collects at least the (k+1)-th, so the better of the two is at least half the fractional optimum, which upper-bounds the integral optimum. The rule is monotone, so critical-value payments make it DSIC.

The step-3 fallback is not decoration: without it, one very large very valuable bidder ranks last by bang-per-buck and is never packed. And the guarantee improves to 1 − α if every w_i ≤ αW for α ≤ ½ — the pathological case is a single bidder consuming most of the capacity.

Combinatorial auctions with single-minded bidders. Each bidder wants one specific bundle S*_i at value v*_i. Nisan’s chapter in the Algorithmic Game Theory book gives the Lehmann–O’Callaghan–Shoham mechanism: sort by v*_i / √|S*_i|, greedily accept bidders whose bundles are still free, and charge each winner the critical value at which it would drop below the bidder that displaced it. Two lemmas do the work:

• Lemma 11.9 — a mechanism for single-minded bidders in which losers pay 0 is incentive compatible iff it is (i) monotone: a winner with (S*_i, v*_i) still wins with any higher v_i or any smaller S_i, and (ii) charges the critical payment. Note the two-dimensional monotonicity: bidding more, or asking for less, must both help. This is why the characterization is not literally Myerson’s — a single-minded bidder’s private data is a value and a bundle.
• Lemma 11.10 — the greedy rule is a √m-approximation. The Cauchy–Schwarz step: for each winner i, the set OPT_i of optimal-allocation bidders blocked by i all appear later in the greedy order, so v*_j ≤ v*_i √|S*_j| / √|S*_i|; summing and applying Cauchy–Schwarz with Σ_{j∈OPT_i} |S*_j| ≤ m and |OPT_i| ≤ |S*_i| gives Σ_{j∈OPT_i} v*_j ≤ √m · v*_i.

And √m is the best possible: approximating better than m^{1/2−ε} is NP-hard (Proposition 11.6). The greedy mechanism is simultaneously simple, truthful, and optimal among polynomial-time algorithms. That coincidence is the happiest result in the area and it is worth noticing that it does not generalize — a (1−ε) FPTAS for knapsack exists but its standard implementation is not monotone, so it must be tweaked before it can be used in a mechanism.

Deferred allocation. The FCC’s incentive-auction reverse phase uses the mirror image: start with all bidders feasible, and greedily remove bidders (by a score increasing in the bidder’s own bid and independent of others’) while feasibility is preserved. Feasibility checking is itself NP-hard — essentially graph colouring, since geographically overlapping TV stations cannot share or neighbour a channel — and is discharged by SAT and integer-programming solvers. Milgrom and Segal call these deferred acceptance heuristic auctions, and Roughgarden notes they enjoy “a number of good incentive properties above and beyond DSIC, which are not shared by their forward-greedy cousins.”

---

5. Bulow–Klemperer: recruit, don’t optimize

The third axis, and the cleanest simplicity result in auction theory.

Theorem (Bulow & Klemperer 1996). Let F be a regular distribution and n ≥ 1. Then

E[ revenue of the Vickrey auction with n+1 bidders drawn i.i.d. from F, NO reserve ]
        ≥
E[ revenue of the revenue-OPTIMAL auction for F with n bidders ]

Read that twice. The left-hand mechanism has no free parameters at all — it does not know F. The right-hand mechanism is tuned to F through its monopoly reserve φ⁻¹(0). And a single, fixed, parameter-free auction beats an entire infinite family of separately-tuned optimal auctions, one per distribution.

The proof, which is three lines and a trick

Define a fictitious auction A on the n+1 bidders: run the optimal auction OPT_F on bidders 1…n; if the item was not sold, hand it to bidder n+1 for free. A has two properties by construction: its expected revenue equals that of OPT_F on n bidders (the giveaway raises no money), and it always allocates the item.

Now: among all auctions that always allocate, which maximizes expected revenue? By revenue-equals-virtual-welfare, it is the one awarding the item to the highest virtual value, even when negative. Because the bidders are i.i.d. from a regular F, they share a single increasing φ, so the highest virtual value belongs to the highest value. That auction is the Vickrey auction. Hence Vickrey on n+1 bidders ≥ A on n+1 bidders = OPT_F on n bidders. ∎

flowchart TB
    V["<b>Vickrey, n+1 bidders, no reserve</b><br/>parameter-free"]
    A["<b>Fictitious auction A</b><br/>1. run OPT_F on bidders 1…n<br/>2. if unsold, give it to bidder n+1 free"]
    O["<b>OPT_F, n bidders</b><br/>Vickrey + monopoly reserve φ⁻¹(0)"]
    A ---|"same revenue<br/>(step 2 raises $0)"| O
    V -->|"≥"| A
    V2["<b>Why V ≥ A:</b> both always allocate.<br/>Among always-allocating auctions the<br/>revenue-maximizer awards to the highest<br/>virtual value. i.i.d. + regular ⇒ one<br/>shared increasing φ ⇒ highest virtual value<br/>= highest value = Vickrey."]
    V --- V2

What it shows: the fictitious-auction bridge. Insight: the whole proof turns on manufacturing an auction that (a) is revenue-equivalent to the target and (b) always allocates, so that the comparison can be made inside a class where Vickrey is provably optimal. The extra bidder is not “more competition” in a hand-wavy sense — it is the specific object that lets the giveaway step be free.

Verified exactly

For U[0,1]: f = 1, F(v) = v, so φ(v) = v − (1−v)/1 = 2v − 1, which is strictly increasing (regular), with monopoly reserve φ⁻¹(0) = ½. The optimal revenue with n bidders equals expected virtual welfare E[(2M − 1)⁺] where M = max of n uniforms with density n m^{n−1}:

OPT(n) = ∫_{1/2}^{1} (2m − 1) · n m^{n−1} dm  =  [ 2n/(n+1) · m^{n+1} − m^n ]_{1/2}^{1}

and the Vickrey revenue with N bidders is E[2nd highest of N] = (N−1)/(N+1). Both are rational, so the comparison can be exact:

BULOW-KLEMPERER, U[0,1], EXACT RATIONAL ARITHMETIC
  n     OPT(n) exact                VICKREY(n+1)             holds?  VICK(n)/OPT(n)  bound (n-1)/n
  1              1/4   0.250000              1/3   0.333333     YES        0.000000       0.000000
  2             5/12   0.416667              1/2   0.500000     YES        0.800000       0.500000
  3            17/32   0.531250              3/5   0.600000     YES        0.941176       0.666667
  4            49/80   0.612500              2/3   0.666667     YES        0.979592       0.750000
  5            43/64   0.671875              5/7   0.714286     YES        0.992248       0.800000
  6          321/448   0.716518              3/4   0.750000     YES        0.996885       0.833333
  7         769/1024   0.750977              7/9   0.777778     YES        0.998700       0.857143
  8        1793/2304   0.778212              4/5   0.800000     YES        0.999442       0.875000
  9        4097/5120   0.800195             9/11   0.818182     YES        0.999756       0.888889
 10       9217/11264   0.818271              5/6   0.833333     YES        0.999892       0.900000
 11        6827/8192   0.833374            11/13   0.846154     YES        0.999951       0.909091
 12      45057/53248   0.846173              6/7   0.857143     YES        0.999978       0.916667

The inequality holds at every n, and the sanity check at n = 1 is worth pausing on: OPT(1) = 1/4 — sell to one bidder at the monopoly price 1/2, which they accept half the time — versus 1/3 for a plain second-price auction with two bidders. Adding one bidder is worth more than the entire apparatus of optimal pricing.

The last two columns verify the corollary Roughgarden states: for n ≥ 2, the same-n Vickrey auction gets at least (n−1)/n of the optimal revenue. Measured, the true ratio is far better than the bound — 0.941 against a guarantee of 0.667 at n = 3, and 0.9998 against 0.917 at n = 12. By ten bidders the reserve price is worth about 0.01%.

A Monte Carlo cross-check on a second regular distribution (exponential, φ(v) = v − 1, monopoly reserve 1) confirms the margin is not an artifact of uniformity:

Monte Carlo cross-check (400k trials each) and a second regular distribution:
          dist   n   OPT(n) MC  VICKREY(n+1) MC    margin
        U[0,1]   1     0.24964          0.33341  +0.08377
        U[0,1]   3     0.53082          0.60015  +0.06933
        U[0,1]   5     0.67209          0.71402  +0.04192
        Exp(1)   1     0.36842          0.50063  +0.13222
        Exp(1)   3     0.91721          1.08293  +0.16572
        Exp(1)   5     1.30835          1.44977  +0.14142

Note that the margin shrinks with n for the uniform and stays roughly flat for the exponential. Bulow–Klemperer is strongest exactly where the marginal bidder matters most — thin markets. That matches the field evidence in §Production Notes.

The interpretation, and its limits

Roughgarden’s gloss: “extra competition is more important than getting the auction format just right. That is, invest your resources into getting more serious participants, rather than sharpening your knowledge of their preferences.” For a systems engineer the translation is that broadening the pool of requests you can serve beats tuning the admission policy, and that is usually the cheaper engineering project.

Two limits must be stated. The theorem assumes i.i.d. bidders and a regular distribution. Hartline and Rougharden’s generalization replaces “one extra bidder” with “duplicate every bidder” — each bidder and its duplicate are i.i.d., interchangeable, and cannot both be served — and obtains:

Environment	Distributional assumption	VCG with duplicates vs optimal	VCG with monopoly reserves vs optimal
Downward-closed set system	MHR (monotone hazard rate)	3-approximation, tight	2-approximation, tight
Matroid set system	Regular	2-approximation (lower bound 4/3)	2-approximation, tight
Single item, non-identical	Regular, anonymous reserve	—	4-approximation (lower bound 2)
Any of the above	Irregular	No constant-factor guarantee	No constant-factor guarantee

The last row is the fence. Regularity — v − 1/h(v) non-decreasing, where h = f/(1−F) is the hazard rate — is not a technicality; drop it and the simple mechanisms lose all guarantees. MHR (h non-decreasing) is strictly stronger and covers uniform, normal and exponential. The canonical regular-but-not-MHR distribution is the equal-revenue distribution F(z) = 1 − 1/z on [1, ∞), for which every posted price earns the same expected revenue — the distribution that makes pricing informationless.

Hartline and Roughgarden also note something that connects straight back to Why VCG Is Rare in Practice: they obtain the duplicate-bidder result “even though the VCG mechanism is not generally revenue monotone in downward-closed set systems, meaning that adding new agents can actually reduce the revenue of the VCG mechanism.” The approximation survives the very non-monotonicity that sinks exact VCG.

---

6. The engineering thesis, measured

The claim to test is: simple mechanisms are robust to distributional misspecification in a way optimal mechanisms are not. The optimal auction reads its reserve price off a prior. If the prior is wrong, the reserve is wrong, and — unlike a merely suboptimal mechanism — a wrong reserve can be actively destructive, because it refuses to sell.

Experiment. Designer believes values are U[0,1], hence sets reserve ½. Reality is a contaminated mixture: with probability c a bidder’s value is drawn from U[0,1]/5 (a low-value population the designer’s prior does not contain) and otherwise from U[0,1]. Three mechanisms compete with n = 3 bidders, 400,000 trials per cell: the misspecified optimal auction (Vickrey, reserve 0.5), plain Vickrey with no reserve, and Bulow–Klemperer’s Vickrey with n+1 = 4 bidders and no reserve.

   c (bad fraction)   MISSPEC r=0.5   plain Vickrey   BK: Vickrey n+1                 winner
             0.00         0.53135         0.50046           0.59995   misspecified optimal
             0.20         0.45612         0.40204           0.50904   misspecified optimal
             0.40         0.36677         0.30026           0.39761   misspecified optimal
             0.60         0.26217         0.20819           0.27942   misspecified optimal
             0.80         0.14036         0.13706           0.17601   misspecified optimal
             0.90         0.07254         0.11364           0.13975          PLAIN VICKREY
             1.00         0.00000         0.10009           0.11999          PLAIN VICKREY

Three readings.

1. The crossover is at roughly c ≈ 0.85. For contamination below that, the misspecified reserve still helps — it is a bad reserve, not a catastrophic one. So the naive claim “simple always beats misspecified optimal” is false, and it is worth saying so plainly.
2. Past the crossover, the optimal mechanism does not degrade gracefully; it falls off a cliff. At c = 1.0 every value lies in [0, 0.2], the reserve of 0.5 is above the entire support, and the auction earns exactly zero while a parameter-free Vickrey auction earns 0.100. That is not a 2× loss, it is total. A pure scale misspecification shows the same shape — with all values scaled to [0, 0.4] the misspecified optimal auction earns 0 against Vickrey’s 0.200.
3. Bulow–Klemperer’s mechanism wins in every single row, including c = 0 where the optimal auction is correctly specified. That is the theorem doing exactly what it advertises: one extra bidder, no parameters, uniformly better than a tuned mechanism whose tuning may be wrong. 0.600 vs 0.531 when the prior is right, and 0.140 vs 0.073 when it is 90% wrong.

The asymmetry of risk is the point. A simple mechanism’s downside when your model is wrong is that it is still simple and still collects something; the optimal mechanism’s downside is that its parameters are derived from the wrong model and can push it outside the feasible region entirely.

Uncertain

Verify: that the c ≈ 0.85 crossover generalizes. Reason: it depends entirely on my contamination family (a 1/5-scaled uniform) and on n = 3. A contamination that raises rather than lowers values would make the fixed reserve too low, degrading it gently rather than catastrophically. To resolve: sweep the contamination family and n. The robust claim — misspecification can drive optimal revenue to zero while a parameter-free mechanism keeps earning — does not depend on the particular family; the crossover point does. uncertain

Why this is a principle and not an anecdote

Two theoretical results say the observation is structural.

Wilson’s doctrine. Robert Wilson (1987) argued that mechanisms less dependent on the details of the environment are more likely to be relevant — cited by Hartline as the organizing philosophy of the whole approximation programme. The prior is a detail; the number of bidders is not.

Vincent and Manelli (2007). There exist mechanism design environments in which every “undominated” mechanism is optimal for some distribution of agent preferences. Hartline’s reading: “This result implies that optimality cannot be used to identify properties of good mechanisms.” If optimality does not discriminate, it cannot be the design criterion; approximation, which does discriminate, must be.

And Hartline’s practical defence of a factor of 2, which is the honest answer to a principal who objects that you are leaving half the money on the table: (i) the constant is a worst-case result and specific environments do better — simulate; (ii) the constant guides the design of better mechanisms for the specific environment; (iii) in most environments the optimal mechanism is not known at all, so the principal’s actual alternative is an ad-hoc mechanism with no guarantee whatsoever; and (iv) “mechanisms that are two approximations in theory arise in practice. In fact, that it is a two approximation explains why the mechanism arises.”

---

Failure Modes and Gotchas

The prior is not the only thing that can be wrong; regularity can be too. Every constant in the Hartline–Roughgarden table evaporates for irregular distributions. Before deploying a reserve-price mechanism, check that the empirical distribution has v − 1/h(v) non-decreasing — a heavy tail or a bimodal population can break it. Myerson’s own solution (ironing) restores optimality but reintroduces exactly the complexity the simple mechanism was meant to avoid.

“Simple” mechanisms can still need a prior. A posted price is a number, and a good posted price is computed from a distribution. CHMS are explicit that all the computational burden sits in the offline price-computation step, which “is based on a subroutine that repeatedly samples the distribution of agent values and simulates Myerson’s mechanism on the sample. This clearly requires more computation than just running Myerson’s mechanism on the real agents in the first place.” The gain is entirely in the online simplicity and robustness. If you were hoping approximation would spare you the statistics, it does not — that is what prior-independent designs like Bulow–Klemperer are for, and they are a separate technique.

Approximate allocation does not automatically preserve truthfulness. Substituting an approximation algorithm into VCG’s payment formula breaks the dominant-strategy property outright; Rothkopf’s blunt version is that approximate winner determination “will destroy the incentive for truth-revealing strategies that is a key purpose of the VCG process.” The fix is not “approximate carefully,” it is design for monotonicity and charge critical values. Note that natural algorithms are not always monotone: the standard knapsack FPTAS is not, and must be modified.

Monotonicity for single-minded bidders is two-dimensional. Lemma 11.9 requires that a winner keeps winning both when it raises its value and when it shrinks its bundle. It is easy to write a scoring rule that satisfies the first and violates the second, and the resulting mechanism is manipulable by over-requesting.

The threshold rule matters more than the theorem suggests. §3’s measurement: the median rule and the half-of-max rule both carry a proved 1/2 guarantee, and on ten uniform prizes they achieve 0.531 and 0.800. Selecting the rule by proof rather than by simulation leaves about 50% on the table.

Do not measure heavy-tailed expectations by naive sampling. My first prophet-inequality run reported a ratio of 0.4802 on an instance where the theorem guarantees ≥ 0.5. The instance had a 1/1000 probability of a prize worth 1,000; 300,000 trials gave ~300 hits and an E[max] estimate off by 4%. Compute the expectation in closed form, or use importance sampling, or report a confidence interval wide enough to be honest.

Bulow–Klemperer’s “one extra bidder” is not free. The theorem compares mechanisms, not budgets. Recruiting an additional serious bidder to a spectrum auction may cost more than a consultant’s estimate of the prior. What the theorem establishes is the exchange rate: it tells you that a marginal bidder is worth more than perfect distributional knowledge, so you can price the two efforts against each other.

i.i.d. is a real assumption. With asymmetric bidders the plain statement fails and you need the duplication form, which requires that a bidder and its duplicate be interchangeable within the feasibility structure — a condition that is natural in matroid environments and awkward elsewhere.

---

Alternatives and When to Choose Them

Approach	Gives up	Keeps	Approximation	Use when
Myerson optimal auction	Nothing	—	1 (exact)	Single-parameter, you genuinely know F, and complexity is affordable
Vickrey + monopoly reserve	Some revenue	DSIC, explicable	Exact for i.i.d. regular; 2 for MHR downward-closed	You know F well enough for one number per bidder
Vickrey + anonymous reserve	More revenue	One knob, eBay-compatible	4 (single item, regular)	The venue offers only one reserve; bidders are non-identical
Order-oblivious posted pricing	~half the revenue	Collusion-resistance, privacy, no rounds, arbitrary arrival order	2	Agents arrive over time; you cannot assemble them
Sequential posted pricing	~37%	All of the above plus you choose the order	e/(e−1) ≈ 1.58	You control arrival order; multi-dimensional settings
Greedy + critical payments	Exact welfare	DSIC, polynomial time	2 (knapsack), √m (single-minded CA, tight)	Welfare maximization is NP-hard
Deferred allocation	Exact welfare	DSIC + extra group incentive properties	Depends on scoring rule	Feasibility is a hard combinatorial predicate (FCC repacking)
Bulow–Klemperer / prior-independent	Nothing, given the extra bidder	Zero parameters	≥ optimal-with-n; (n−1)/n at same n	You do not trust your prior, and recruitment is cheap
Single-sample mechanisms	Some revenue	Needs one historical draw, not a distribution	Constant	You have data but not a fitted model
Core-selecting auctions	Strategyproofness	Core revenue, shill-resistance	n/a	Combinatorial, complements present — see Why VCG Is Rare in Practice

The decision is genuinely a decision tree rather than a ranking:

flowchart TB
    S["Choosing a mechanism"] --> Q1{"Is the welfare-maximizing<br/>allocation problem tractable?"}
    Q1 -->|No| G["<b>Greedy / deferred allocation</b><br/>+ critical-value payments.<br/>Design for MONOTONICITY first,<br/>approximation ratio second."]
    Q1 -->|Yes| Q2{"Do you trust a prior<br/>on bidder values?"}
    Q2 -->|No| BK["<b>Prior-independent</b><br/>Bulow–Klemperer: recruit one more<br/>bidder, run Vickrey with no reserve.<br/>Or a single-sample reserve."]
    Q2 -->|Yes| Q3{"Are all bidders present<br/>at the same time?"}
    Q3 -->|No| PP["<b>Posted pricing</b><br/>order-oblivious ⇒ 2-approx<br/>sequential ⇒ 1.58-approx<br/>Robust to arrival order and collusion."]
    Q3 -->|Yes| Q4{"Is the distribution<br/>REGULAR (v − 1/h(v) ↑)?"}
    Q4 -->|No| IRR["<b>No constant-factor guarantee.</b><br/>Iron the virtual values (back to<br/>complexity), or accept an<br/>unguaranteed heuristic knowingly."]
    Q4 -->|Yes| RES["<b>Vickrey with reserves</b><br/>bidder-specific monopoly reserves ⇒ 2<br/>anonymous reserve ⇒ 4"]

What it shows: the four questions whose answers determine which simple mechanism applies. Insight: tractability is asked first, because it is the only constraint that cannot be traded against revenue — an intractable exact mechanism is not slow, it is unavailable. Regularity is asked last, because it is the one that silently voids every guarantee if unchecked.

---

Production Notes

Yahoo!‘s 2008 reserve-price experiment

The best-documented field test of optimal-auction theory, reported in Roughgarden’s Lecture 6 from Ostrovsky and Schwarz’s study. Before 2008, Yahoo! used a single reserve price across all keywords — $0.01, later $0.05, then $0.10 in 2008 — which is obviously wrong the moment you compare the queries “divorce lawyer” and “pizza.”

The experiment: fit a lognormal valuation distribution to each of half a million keywords from bidding history, compute the theoretically optimal reserve per keyword (many came out at $0.30 or $0.40, i.e. 3–4× the uniform reserve), and then — because management was cautious — set the new reserve to the average of the old $0.10 and the theoretical optimum. Revenue rose several percent of a very large number, and better reserve prices were credited by Yahoo!‘s president as the biggest reason for higher search revenue in the 2008 Q3 report.

Two details make this more than a success story. First, the effect was concentrated in markets that were “valuable but thin” — fewer than six bidders. That is Bulow–Klemperer read backwards: reserves matter precisely where the marginal-bidder margin is largest, and my exact table shows the same shape (the reserve is worth 20% of revenue at n = 2 and 0.01% at n = 12). Second, Roughgarden’s footnote records that “both in theory and empirically, this initial change accounts for most of the revenue increase. Increasing the reserve price further does not have much effect on revenue.” The revenue curve is flat near its optimum. Getting roughly the right reserve captures nearly all the gain — which is the empirical face of every approximation result in this note.

eBay: posted prices displacing the auction

Hartline records that “eBay has found empirically that posted pricing via the ‘buy it now’ option is more appropriate than a slow (days or weeks) ascending auction,” citing Wang et al. (2008) and Reynolds and Wooders (2009) on why buy-it-now is replacing the second-price format. This is the field’s most consequential natural experiment and it went the way the theory predicts: for low-value, high-volume, asynchronously-arriving transactions, the ~2× worst-case revenue gap of a posted price is dominated by the fact that buyers do not have to show up at the same time. The prophet inequality is the statement that this gap has a worst case at all.

Google: the same lesson from the other side

Why VCG Is Rare in Practice records the detail; the relevant piece here is that Google shelved a working, truthful VCG auction in 2002 partly because “the VCG auction was harder to explain to advertisers” (Varian & Harris 2014). Explicability is not a soft criterion in a marketplace with millions of self-serve participants; it is the constraint that selects the mechanism. Simple mechanisms are not a concession made to theorists’ convenience — they are what the deployment environment demands, and the approximation results exist to tell you what the concession costs.

FCC incentive auction: greedy in production

The reverse phase’s deferred allocation rule (§4) is the largest deployment of an explicitly-approximate truthful mechanism. Two production-flavoured details from Roughgarden’s Lecture 8. It was implemented as a descending, bidder-specific clock auction rather than a sealed-bid direct mechanism, because “empirically, bidders find them easier to play” — the mechanism is theoretically direct-revelation and practically iterative, which is the standard pattern. And the choice among candidate greedy scoring rules “will likely be guided by the welfare achieved by different rules on synthetic data”: the constant in the theorem selects the class, and simulation selects the member. That is exactly the discipline §3’s threshold measurement argues for.

If you build one

For the P7 exercise in Games and Strategic Systems in C MOC — after implementing VCG and attacking it — the natural follow-ons, in increasing order of what they teach:

1. Verify Bulow–Klemperer exactly. U[0,1] gives closed forms for both sides (§5) so the check needs no simulation at all and no floating point. It took me twenty lines of Fraction arithmetic. Then re-derive it by Monte Carlo and watch the sampling error; the two together teach more than either.
2. Measure both prophet thresholds. Implement the median rule and the half-of-max rule, run them on uniform, exponential and Pareto instances, and observe the 0.53-vs-0.80 gap. The lesson — the proof picks a threshold that is legal, not one that is good — transfers to every approximation algorithm you will ever ship.
3. Build the misspecification harness. Fit the optimal mechanism to a prior, then draw from a different one. This is a ten-line change to an existing auction simulator and it is the single most informative experiment in the note, because it converts “robustness” from an adjective into a number with a crossover point.
4. Then break monotonicity on purpose. Implement the knapsack FPTAS, charge critical values as if it were monotone, and search for a bidder who profits by lowering its bid. Finding one is the fastest possible way to internalize why Myerson’s Lemma has the hypothesis it has.

---

See Also

• Why VCG Is Rare in Practice — the sibling note: the failure catalogue that motivates every approximation here
• The VCG Mechanism — the exact welfare-maximizing mechanism these approximate, and the payment rule the greedy mechanisms replace with critical values
• Reserve Prices and Optimal Auctions — Myerson’s characterization, virtual valuations, regularity and ironing; the “optimal” side of simple-versus-optimal
• Mechanism Design — the inverse problem, and the vocabulary of IC, IR, efficiency and budget balance
• Incentive Compatibility — dominant-strategy versus Bayes-Nash; Myerson’s Lemma and the monotonicity characterization used throughout §4
• The Revelation Principle — why direct truthful mechanisms are without loss of generality, and why iterative implementations are still preferred in the field
• Impossibility Results — the fences (Gibbard–Satterthwaite, Myerson–Satterthwaite) that make approximation necessary rather than merely convenient
• The Vickrey Auction — the parameter-free mechanism Bulow–Klemperer shows is nearly unimprovable
• Ad Auctions and GSP — a deployed non-truthful mechanism whose equilibrium lands on the VCG outcome; simplicity chosen over strategyproofness at scale
• Multi-Armed Bandit Algorithms — the other place where a simple threshold rule with a provable constant beats an intractable optimal policy
• The Price of Anarchy — the same “how much worse is the practical thing” question, asked about equilibria rather than mechanisms
• Rate Limiting as a Mechanism — posted pricing without money: admission thresholds as allocation rules with incentive properties
• Multi-Tenancy and Fairness in LLM Serving — where the online, stateless, order-oblivious character of posted pricing is the operative constraint
• Stock Exchange Order Matching System Design — a deployed allocation rule chosen for simplicity and explicability over optimality
• Games and Strategic Systems in C MOC — parent map; this note closes the P7 rung