vault

The Revelation Principle

34 min read

The Revelation Principle

The revelation principle says that if some mechanism — an ascending auction, a haggle, a multi-round negotiation, anything at all — produces a particular outcome in equilibrium, then there is a direct mechanism producing exactly the same outcome in which every participant simply announces their private information and announcing it truthfully is an equilibrium. The proof is a construction: wrap the original mechanism in an interface layer that takes each agent’s report and plays, on that agent’s behalf, the strategy the agent would have chosen anyway. Lying to the interface is pointless because the interface is already lying for you, optimally. The Nobel committee’s scientific background for the 2007 prize puts the consequence plainly: “although the set of all possible mechanisms is huge, the revelation principle implies that an optimal mechanism can always be found within the well-structured subclass consisting of direct mechanisms” (Nobel 2007 scientific background, §2.1). That is why every textbook derivation of an optimal auction begins by assuming the auction is a sealed-bid form in which nobody lies — not because real auctions look like that, but because the theorem says nothing is lost by pretending they do. The caveats are where the engineering lives, and they are the longer half of this note.

This note is the third rung of P7 — Mechanism Design in Games and Strategic Systems in C MOC. It sits between Incentive Compatibility (what “truthful” means, and in which equilibrium concept) and The VCG Mechanism (the one direct mechanism you should memorize). If you have not met the vocabulary, read Mechanism Design first; the words direct, truthful, dominant strategy, and Bayes–Nash are used here in their technical senses throughout, and each is defined below on first use.

Mental Model — the Interface Layer

The whole theorem is one picture. On the left, agents facing a complicated mechanism, each running a strategy that translates private information into actions. On the right, the same picture with a box drawn around the strategies and the mechanism, and the box relabelled “the mechanism.”

flowchart LR
    subgraph ORIG["BEFORE — indirect mechanism M"]
        direction LR
        v1["agent 1<br/>type v₁"] -->|"plays s₁(v₁)"| M1["M<br/>(ascending auction,<br/>negotiation, ...)"]
        v2["agent 2<br/>type v₂"] -->|"plays s₂(v₂)"| M1
        vn["agent n<br/>type vₙ"] -->|"plays sₙ(vₙ)"| M1
        M1 --> O1["outcome ω<br/>payments p"]
    end
    subgraph NEW["AFTER — direct mechanism M′"]
        direction LR
        w1["agent 1<br/>type v₁"] -->|"reports b₁"| I["interface layer<br/>computes sᵢ(bᵢ)"]
        w2["agent 2<br/>type v₂"] -->|"reports b₂"| I
        wn["agent n<br/>type vₙ"] -->|"reports bₙ"| I
        I -->|"submits s₁(b₁)…sₙ(bₙ)"| M2["the SAME M,<br/>untouched"]
        M2 --> O2["outcome ω<br/>payments p<br/>(identical)"]
    end

What it shows: the transformation moves the dashed line between “agent” and “mechanism” one step to the left, so that the strategising that used to happen inside each agent’s head now happens inside the mechanism. The insight to take: nothing about the machine changes. M is untouched; the only new object is a lookup table sᵢ per agent. Truthfulness is manufactured by absorbing the lie, not by eliminating it. Shoham and Leyton-Brown put the intuition in one line: “if i could gain by lying to the new mechanism, he could likewise gain by lying to himself in the original mechanism” (Multiagent Systems, Theorem 10.2.5).

The Objects, Defined Precisely

A mechanism in the general (indirect) sense has six parts (Nisan, Algorithmic Game Theory, Definition 9.24):

SymbolNameMeaning
Tᵢtype spacethe private information agent i might hold — a value, a cost, a valuation function
Xᵢaction spacewhat i is allowed to say or do in the mechanism — a bid, a drop-out decision, a sequence of clicks
Aalternativesthe outcomes the designer can select — who wins what
vᵢ(tᵢ, a)valuationhow much i values outcome a when its type is tᵢ
a(x₁ … xₙ)outcome rulemaps action profiles to alternatives
pᵢ(x₁ … xₙ)payment rulehow much i pays, as a function of everyone’s actions

Utility is quasi-linear: uᵢ = vᵢ(tᵢ, a(x)) − pᵢ(x) — value of what you got, minus money paid. (Quasi-linear means money enters utility linearly and separably; The VCG Mechanism leans on this hard, and Roughgarden’s Lecture 9 surveys what breaks when it fails — budget constraints, risk aversion, non-transferable utility.)

A strategy is a function sᵢ : Tᵢ → Xᵢ: what you do for each thing you might privately know. A mechanism is direct when Xᵢ = Tᵢ — the only action available is to name a type. A direct mechanism is truthful (equivalently incentive compatible, equivalently strategyproof) when the identity strategy sᵢ(tᵢ) = tᵢ is an equilibrium.

The crucial split, which the revelation principle exists to collapse, is between two separate demands that the phrase “dominant-strategy incentive compatible” (DSIC) silently welds together (Roughgarden, CS364A Lecture 4, §3.1):

  1. every participant has a dominant strategy, whatever its private information; and
  2. that dominant strategy is direct revelation — telling the truth.

Requirement (1) is a real constraint on the mechanism. Requirement (2), the theorem says, “comes for free.” Roughgarden’s silly-but-clarifying example of a mechanism satisfying (1) but not (2): run a second-price auction on twice each submitted bid. Every bidder’s dominant strategy is then to bid half its value. The mechanism is perfectly well behaved; it just is not phrased in truth.

The Construction Is the Proof

Fix a mechanism M = (X, a, p) and a dominant-strategy equilibrium s = (s₁ … sₙ) of it. Dominance means: for every agent i, every type tᵢ, every action xᵢ it might play instead, and every action profile x₋ᵢ of everyone else — not merely equilibrium ones —

    uᵢ(tᵢ, sᵢ(tᵢ), x₋ᵢ)  ≥  uᵢ(tᵢ, xᵢ, x₋ᵢ)

Now define the direct mechanism M′ on reports t = (t₁ … tₙ):

    f(t₁ … tₙ)   =  a( s₁(t₁), …, sₙ(tₙ) )
    p′ᵢ(t₁ … tₙ) =  pᵢ( s₁(t₁), …, sₙ(tₙ) )

That is the entire construction. Nisan’s proof that M′ is incentive compatible is four lines and worth reading symbol by symbol (AGT Proposition 9.25). Since sᵢ is dominant in M, for every tᵢ, every x₋ᵢ, and every alternative action xᵢ:

    vᵢ(tᵢ, a(sᵢ(tᵢ), x₋ᵢ)) − pᵢ(sᵢ(tᵢ), x₋ᵢ)  ≥  vᵢ(tᵢ, a(xᵢ, x₋ᵢ)) − pᵢ(xᵢ, x₋ᵢ)

This holds for all x₋ᵢ, so in particular it holds when x₋ᵢ happens to be s₋ᵢ(t₋ᵢ) — the actions the others’ strategies would generate from some reported types. And it holds for all xᵢ, so in particular for xᵢ = sᵢ(t′ᵢ) — the action agent i’s own strategy would generate from a lie t′ᵢ. Substituting both:

    vᵢ(tᵢ, f(tᵢ, t₋ᵢ)) − p′ᵢ(tᵢ, t₋ᵢ)  ≥  vᵢ(tᵢ, f(t′ᵢ, t₋ᵢ)) − p′ᵢ(t′ᵢ, t₋ᵢ)

which is exactly the definition of incentive compatibility for M′.

flowchart TB
    A["sᵢ is DOMINANT in M:<br/>uᵢ(tᵢ, sᵢ(tᵢ), x₋ᵢ) ≥ uᵢ(tᵢ, xᵢ, x₋ᵢ)<br/>for ALL x₋ᵢ and ALL xᵢ"]
    B["restrict x₋ᵢ to the image of s₋ᵢ<br/>(a subset of all profiles)"]
    C["restrict xᵢ to the image of sᵢ<br/>(a subset of all actions)"]
    D["uᵢ(tᵢ, sᵢ(tᵢ), s₋ᵢ(t₋ᵢ)) ≥ uᵢ(tᵢ, sᵢ(t′ᵢ), s₋ᵢ(t₋ᵢ))<br/>= M′ is incentive compatible"]
    A --> B --> D
    A --> C --> D
    E["note the direction:<br/>we only ever THREW AWAY constraints"] -.-> D

What it shows: the proof is a double specialisation of a universally quantified inequality. The insight: because the dominance hypothesis quantifies over all opponent actions, the transformed inequality falls out by restriction — we never need a new argument, only a narrower one. This is also exactly why the converse fails: an equilibrium concept that quantifies over fewer opponent behaviours (Bayes–Nash) yields a correspondingly weaker conclusion, and no amount of wrapping upgrades it.

The same argument works verbatim for Bayes–Nash equilibrium (BNE), where each agent best-responds only in expectation over a commonly known prior on others’ types, and only against the others’ equilibrium strategies (AGT Proposition 9.44; Hartline, Mechanism Design and Approximation, Theorem 2.10.1). Myerson’s own statement of it, in the paper that made it a working tool, is worth having in the original. He calls it Lemma 1 and it reads:

“(THE REVELATION PRINCIPLE.) Given any feasible auction mechanism, there exists an equivalent feasible direct revelation mechanism which gives to the seller and all bidders the same expected utilities as in the given mechanism.” — Myerson, Optimal Auction Design, Mathematics of Operations Research 6(1), p. 62

and his sketch of why, in the same paragraph, is the interface-layer picture in prose: “in the direct revelation mechanism (p, x), the seller first asks each bidder to announce his type, and then computes the strategy which the bidder would have used according to the strategic plans in the given auction mechanism, and finally implements the outcomes prescribed in the given auction game for these strategies… And (p, x) must satisfy the incentive-compatibility constraints, because the strategic plans formed an equilibrium in the given feasible mechanism. (If any bidder could gain by lying to the seller in the revelation game, then he could have gained by ‘lying to himself’ or revising his strategic plan in the given mechanism.)” That parenthesis is the origin of the phrase every textbook now uses. Note also what Myerson says immediately afterwards, because it is the theorem’s actual job description: “Using the revelation principle, we may assume, without loss of generality, that the seller only considers auction mechanisms in the class of feasible direct revelation mechanisms” — the point is to shrink a search space, not to describe an institution.

The principle also works for ex-post Nash by way of a small lemma: restricting each action space to the range of the equilibrium strategy turns an ex-post-Nash equilibrium into a dominant-strategy one, after which the dominant-strategy version applies (AGT Proposition 9.23 and Corollary 9.26).

flowchart LR
    subgraph IN["what you feed in"]
        D1["dominant-strategy<br/>equilibrium"]
        D2["ex-post Nash<br/>equilibrium"]
        D3["Bayes-Nash<br/>equilibrium"]
    end
    subgraph OUT["what you get out"]
        O1["DSIC direct<br/>mechanism"]
        O2["DSIC after restricting<br/>action spaces to<br/>the strategy ranges"]
        O3["BIC direct mechanism<br/>(truth is a BNE,<br/>NOT dominant)"]
    end
    D1 --> O1
    D2 --> O2
    D3 --> O3
    X["there is no arrow<br/>from D3 to O1"]:::warn
    classDef warn fill:#442,stroke:#c93

What it shows: the transform is equilibrium-concept preserving, not equilibrium-concept improving. The insight: the single most common misreading of the revelation principle is that it turns any mechanism into a strategyproof one. It does not. Feed it a Bayes–Nash equilibrium and you get a mechanism where truth-telling is merely a Bayes–Nash equilibrium — an agent who doubts the prior, or doubts that others are playing along, has no reason to be honest. The implementation below verifies this failure by exhaustive enumeration.

Implementing the Transform

Talking about a construction is cheap; running it is not. The following is a complete, dependency-free implementation. Every number is a fractions.Fraction, so no comparison in the equilibrium checks is ever decided by floating-point noise — this matters because dominance is an inequality between utilities, and a spurious 1e-17 flips a verdict. Nothing here uses numpy, nashpy, or gambit; none of them is installed on this machine, and none is needed, because the type and action spaces are finite and small enough to enumerate exhaustively.

The core: three functions and two checkers

class Mechanism:
    """types[i], actions[i] are lists; outcome(a) and pay(i,a) take an action
    profile; val(i, t, o) is agent i's value for outcome o at type t."""
    def utility(self, i, t_i, a):
        return self.val(i, t_i, self.outcome(a)) - self.pay(i, a)
 
 
def is_dominant(mech, s):
    """Exhaustive check. Dominance quantifies over EVERY action profile of
    the others -- not only the ones the equilibrium would produce."""
    bad = []
    for i in range(mech.n):
        others = [mech.actions[j] for j in range(mech.n) if j != i]
        for t_i in mech.types[i]:
            a_i = s[i][t_i]
            for a_minus in product(*others):                 # ALL of them
                base = list(a_minus)
                u_star = mech.utility(i, t_i, tuple(base[:i] + [a_i] + base[i:]))
                for alt in mech.actions[i]:                   # ALL deviations
                    if mech.utility(i, t_i,
                                    tuple(base[:i] + [alt] + base[i:])) > u_star:
                        bad.append((i, t_i, a_i, alt, a_minus))
    return (not bad), bad
 
 
def revelation_transform(mech, s):
    """THE construction. Wrap `mech` in an interface layer that plays s."""
    def outcome(t):                      # t is a profile of REPORTED types
        return mech.outcome(tuple(s[i][t[i]] for i in range(mech.n)))
 
    def pay(i, t):
        return mech.pay(i, tuple(s[j][t[j]] for j in range(mech.n)))
 
    return Mechanism(mech.types, mech.types,      # action space := type space
                     outcome, pay, mech.val)

Line by line, the transform is six lines and does exactly what the picture says: outcome(t) composes the strategies with the original outcome rule; pay(i, t) composes them with the original payment rule; the constructor sets actions = types, which is the formal content of the word “direct.” There are two independent things to verify afterwards, and keeping them separate turns out to matter:

def is_incentive_compatible(direct):
    """Truth is dominant in the direct mechanism: for every agent, every true
    type, every profile of others' REPORTS, no lie beats the truth."""
    ...
 
def outcomes_match(mech, s, direct):
    """Equivalence: same alternative AND same payments on every type profile."""
    ...

Case A — an ascending clock auction becomes the Vickrey auction

The indirect mechanism is a genuine simulation, not a formula. The clock ticks 0, 1, 2, …; bidder i is still in at price p if and only if its chosen drop-out price dᵢ ≥ p; the auction stops the first time at most one bidder remains; the winner pays the previous tick.

def clock_run(d):
    active, price = list(range(len(d))), F(0)
    while True:
        still = [i for i in active if d[i] >= price]
        if len(still) <= 1:
            return (still[0] if still else min(active)), max(price - 1, F(0))
        active = still
        price += 1
sequenceDiagram
    participant C as clock
    participant B0 as bidder 0 (v=5)
    participant B1 as bidder 1 (v=3)
    participant B2 as bidder 2 (v=2)
    C->>B0: price 0..2 — still in?
    C->>B1: price 0..2 — still in?
    C->>B2: price 0..2 — still in?
    B2-->>C: drops at price 3 (3 > v=2)
    C->>B0: price 3 — still in?
    C->>B1: price 3 — still in?
    B1-->>C: drops at price 4 (4 > v=3)
    C-->>B0: only one left — you win, pay 3
    Note over C,B2: the direct image of this run is<br/>"report 5, 3, 2 → bidder 0 wins, pays 3"<br/>i.e. exactly the second-price auction

What it shows: an iterative, multi-round protocol and its one-shot direct image, side by side. The insight: the second-price auction is not an independent invention — it is what you get when you apply this transform to the English auction, a point Roughgarden makes explicitly (“the Vickrey auction is what you get when you apply the Revelation Principle to the English auction”, Lecture 7 §3.2) and Hartline makes twice (“the second-price auction is the revelation principle applied to the ascending-price auction”, §2.10).

Vickrey ran this transform by hand in 1961, twelve years before the theorem was stated

The primary text confirms the framing. Vickrey does not present the second-price rule as an invention; he presents it as the answer to a search for the sealed-bid image of the ascending auction: “Since it has been shown that the Dutch auction has certain characteristics in some circumstances that may be considered disadvantageous as compared with the more certainly Pareto-optimal results of the progressive auction, it is of interest to inquire whether there is not some sealed-bid procedure that would be logically isomorphic to the progressive auction. It is easily shown that the required procedure is to ask for bids on the understanding that the award will be made to the highest bidder, but on the basis of the price set by the second highest bidder” (Counterspeculation, Auctions, and Competitive Sealed Tenders, Journal of Finance 16(1), p. 20). “Logically isomorphic” is the revelation principle’s conclusion in 1961 vocabulary. Read here from the original — the JSTOR scan has zero extractable characters and no embedded fonts, so the pages were rendered with pdftoppm -png -r 120 and read as images from a Princeton course mirror.

Two details of that text are worth keeping. First, Vickrey never uses the word dominant; he hedges the argument twice with collusion aside (“could not, collusion aside, affect the price he would actually pay”), which is exactly the quantifier the revelation principle’s dominant-strategy version consumes and its coalition blind spot leaves open. Second, on the same page he pins down why one would want the direct form — not revenue, but cognitive cost: “It is one of the salient advantages of the second-price method that it makes any such general market appraisal entirely superfluous… Each bidder can confine his efforts and attention to an appraisal of the value the article would have in his own hands, at a considerable saving in mental strain” (p. 22). That is a claim about human beings playing the mechanism, not about its equilibria — and it is the claim the theorem cannot make, which is what §4 below is about.

Running the machinery on three bidders with values in {0,…,6}:

  s is a dominant-strategy equilibrium of the CLOCK auction : True   (0 violations)
  transformed direct mechanism is DSIC                      : True   (0 violations)
  outcomes+payments identical on all 343 type profiles      : True
  profiles where direct(clock) != textbook 2nd-price rule   : 0

The last line is the one that matters. It is checked against an independently written second-price rule (winner = argmax bid, price = max of the rest), not against the transform’s own output, so agreement on all 7³ = 343 type profiles is evidence about the construction, not a tautology.

Case B — undoing an arbitrary strategic re-encoding

Roughgarden’s “silly example”: the mechanism doubles every bid before running Vickrey, so sᵢ(v) = v/2. Here the transform does visible work — the direct mechanism’s report is not the original action.

  s dominant in the indirect mechanism : True   (0 violations)
  direct mechanism DSIC                : True
  equivalence on all type profiles     : True
  direct(doubled) != 2nd-price on      : 0 profiles

The interface layer halves your report before passing it on, and the composite is the plain second-price auction again. This is the theorem’s real content in miniature: the strategic encoding is not information, it is noise, and the transform is the decoder.

Case C — a Bayes–Nash equilibrium, and the four mechanisms it could have been

Now the honest case. Take a first-price sealed-bid auction with two bidders, values drawn uniformly from {0,1,2,3}, bids restricted to the same grid. First-price has no dominant strategy — how much to shade depends on what you think the other will bid — so only Bayes–Nash is available. Enumerating all 4⁴ × 4⁴ = 65,536 pure strategy profiles and checking the BNE condition exactly:

#agent 0’s bid functionagent 1’s bid functionE[revenue]E[welfare]efficient?
0v=0123 → 0001v=0123 → 00115/833/16no
1v=0123 → 0011v=0123 → 00113/42no
2v=0123 → 0011v=0123 → 01117/833/16no
3v=0123 → 0011v=0123 → 01129/817/8yes

What it shows: four distinct pure Bayes–Nash equilibria of the same auction, their transforms, and how much they differ. The insight: revenue ranges from 5/8 to 9/8 — a factor of 1.8 — and only one of the four is efficient. Feeding each to revelation_transform produces four distinct direct mechanisms (verified by comparing their full outcome-and-payment tables). All four are BIC — truth-telling is a Bayes–Nash equilibrium of each. None is DSIC. The theorem does not tell you which of the four you get; you told it, when you picked an equilibrium.

  pure Bayes-Nash equilibria found by exhaustive search : 4
  distinct direct mechanisms they induce                : 4
  of the 4 distinct direct mechanisms: BIC=4  DSIC=0

Case D — the negative control, and a genuine surprise

Every proof has a hypothesis, and the fastest way to see what a hypothesis is doing is to break it. Feed the transform a strategy profile that is not an equilibrium — “drop out one tick above your value” in the clock auction:

  overbid-by-1 is a dominant-strategy equilibrium : False
  transform of a non-equilibrium is DSIC          : False
  profitable lies found in it                     : 270
  e.g. agent 0 with value 1 reports 0 against (0, 1), gains 1
  ...yet outcome-equivalence STILL holds          : True

That last line was not what I expected, and it is instructive. The theorem’s conclusion has two halves with different hypotheses. Outcome-equivalence — that M′ reproduces whatever M would have done under s — is a definitional identity: it holds for any profile of functions s, equilibrium or not, because M′ is literally defined as “compose and run.” Incentive compatibility is the half that consumes the equilibrium hypothesis. If you find yourself in an argument about whether some system “is really a direct mechanism,” this is the fault line: the wrapping is always possible, the truthfulness is not.

What the Theorem Does Not Say

The revelation principle is true, its proof is three lines, and it is one of the most over-applied results in the field. Every practical mechanism I can name — the English auction, the FCC’s simultaneous multiple-round spectrum auctions, sponsored-search GSP, real estate, procurement — is indirect. That is not because practitioners have not heard of the theorem.

mindmap
  root((the theorem<br/>holds — but))
    computation
      simulating sᵢ may be NP-hard
      burden moves TO the centre
      approximation breaks DSIC
    communication
      full type revelation
      exponential in combinatorial settings
      multi-step can be exponentially cheaper
    equilibrium
      one must EXIST
      one must be KNOWN
      one must be SELECTED
      new equilibria may appear
    commitment
      designer must not renegotiate
      partial commitment ⇒ OSP
    coalitions
      DSIC is single-agent
      pairs and false names unconstrained
    message space
      restricted timing
      online arrival/departure
    privacy
      direct = tell the centre everything

What it shows: the seven independent escape hatches, grouped by what they attack. The insight: these are not quibbles about a fragile proof. Each one is a place where the modelling assumption behind the proof — free computation, free communication, common knowledge of an equilibrium, perfect commitment, unilateral deviations only, unrestricted messages, no privacy cost — fails in a system you would actually build.

1. Computation: the strategy you are simulating may be intractable

The transform’s cost is the cost of evaluating sᵢ. Shoham and Leyton-Brown state the consequence directly: “the general effect of constructing a revelation mechanism is to push an additional computational burden onto the mechanism… There are many settings in which agents’ equilibrium strategies are computationally difficult to determine. When this is the case, the additional burden absorbed by the mechanism may be considerable” (MAS §10.2.2).

How considerable? Conitzer and Sandholm’s motivating example is reverse auctions for trucking services: a bidder’s own valuation for a bundle of delivery tasks requires solving “an NP-hard vehicle routing and scheduling problem” (Computational Criticisms of the Revelation Principle, §1). To measure the shape of that burden I gave an agent a private 0/1 knapsack and made “name the bundle you want” its dominant strategy, so the interface layer has to solve the knapsack on the agent’s behalf:

items in the agent’s private knapsacksubsets to searchseconds for one agent’s sᵢ(tᵢ)
101,0240.0004
1416,3840.0052
18262,1440.101
201,048,5760.425
224,194,3041.687

The centre pays this once per agent, per invocation. At 22 items and 30 bidders the direct mechanism spends fifty seconds computing what, in the indirect mechanism, thirty separate parties would each have worked out for themselves in parallel — using domain knowledge and heuristics the centre does not have. The theorem is silent on all of this because its model has no notion of cost.

Worse, the natural fix breaks the theorem’s own premise. Replace exact welfare maximisation with an approximation and the resulting allocation rule generally stops being implementable at all — this is the founding problem of algorithmic mechanism design (Roughgarden, Lecture 4; Approximate and Simple Mechanisms develops it).

2. Communication: direct means everything, up front

Conitzer and Sandholm answer a question Papadimitriou posed at DIMACS in 2001 — can multi-step mechanisms save an exponential amount of communication relative to single-step? — in the affirmative, with a two-agent construction. Agent 1’s type is an n-bit string; agent 2’s type is a function from n-bit strings to one bit; welfare is maximised by the outcome (θ₁, θ₂(θ₁)). A single-step direct mechanism must learn agent 2’s whole truth table. A two-step mechanism asks agent 1 first and then asks agent 2 exactly one question (Theorem 1).

ndirect (single-step) bitstwo-step bitsratio
42054×
8264929×
1665,552173,900×
201,048,5962150,000×
301,073,741,854313.5 × 10⁷ ×

I verified the equivalence exhaustively at n = 3: over all 8 × 256 = 2,048 type profiles the two-step protocol selects the identical welfare-maximising outcome, having elicited 4 bits instead of 11. Both mechanisms are dominant-strategy truthful; they differ only in when the questions are asked.

This is not a contrived corner. Roughgarden’s assessment of the practical situation in combinatorial auctions is blunt: with m items each bidder has 2^m − 1 private parameters, “roughly a thousand when m = 10 and a million when m = 20. No bidder in their right mind would want to write down (or even figure out) that many bids. No seller would want to listen to that many bids. This exponential number of private parameters makes the VCG mechanism, and every other direct-revelation mechanism, a nonstarter for combinatorial auctions in practice” (Lecture 7 §3.2). The FCC does not run a direct mechanism because a direct mechanism for its problem cannot be written down.

3. Equilibrium: it must exist, be known, and be chosen

The theorem’s hypothesis is “there exists a mechanism that implements f in equilibrium.” Three separate things are being assumed.

  • Existence. Games with strict incomplete information often have no dominant-strategy equilibrium at all; Nisan notes that these solution concepts “seem too good to be true… in usual cases one does not expect games with strict incomplete information to have any of these equilibria” (AGT §9.4.1). Mechanism design escapes this only because the designer gets to choose the game.
  • Knowledge. To build the interface layer you must be able to compute sᵢ. For a Bayes–Nash equilibrium this requires knowing the prior distributions — Hartline lists “where the designer does not know the prior distribution (and hence cannot simulate the agent strategies)” as one of two named environments where “the revelation principle fails to hold” (MDnA §2.10); the other is where agents learn their values over time. A DSIC mechanism, by contrast, “requires fewer assumptions on the agents: each agent must only know her own value; while for a BIC mechanism, each agent must also know the distribution over other agent values.”
  • Selection. Case C above is this problem, measured: four equilibria, four different direct mechanisms, revenue spread 1.8×. The Nobel background flags the same gap and names the field that grew out of it: “The revelation principle is extremely useful. However, it does not address the issue of multiple equilibria… Can a mechanism be designed so that all its equilibria are optimal? The first general solution to this problem was given by Eric Maskin (1977). The resulting theory, known as implementation theory, is a key part of modern mechanism design” (§1).

There is a fourth, subtler version. Shoham and Leyton-Brown: “even if the original indirect mechanism had a unique equilibrium, there is no guarantee that the new revelation mechanism will not have additional equilibria” (MAS §10.2.2). The transform preserves the equilibrium you fed it; it does not promise not to create new ones.

4. Commitment: the designer must be unable to change its mind

The proof implicitly assumes the mechanism is a machine that will execute its published rules no matter what it learns. Real designers can renegotiate, and everyone knows it. Li’s Obviously Strategy-Proof Mechanisms gives this the sharpest formulation available: obviously dominant strategies (where “for any deviation, at any information set where both strategies first diverge, the best outcome under the deviation is no better than the worst outcome under the dominant strategy”) characterise exactly what “can be carried out by a social planner under a particular regime of partial commitment” (abstract, AER 107(11): 3257–87).

Uncertain

Verify: the precise statement of Li’s partial-commitment characterisation and its relation to the revelation principle. Reason: only the publisher’s abstract page was readable from this machine — scholar.harvard.edu returned HTTP 403 and pubs.aeaweb.org served a Cloudflare challenge, matching the known-blocked list in the vault conventions. The full text was not read. To resolve: obtain the AER PDF or the author’s working-paper version and check Theorem 1 and the OSP-implementability characterisation directly. #uncertain

The empirical shadow of this is measurable and was verified: Roughgarden reports that “empirical studies show that bidders are more likely to play their dominant strategy in an English auction than in a sealed-bid second-price auction, where some bidders inexplicably overbid,” citing Harstad’s Dominant Strategy Adoption and Bidders’ Experience with Pricing Rules (Lecture 7, footnote 4). The two mechanisms are revelation-principle images of each other and therefore theoretically identical — and people play them differently. The theorem is a statement about equilibria, not about whether humans find them.

5. Coalitions: the constraint is single-agent by construction

Incentive compatibility says no agent, unilaterally, gains by lying. A direct mechanism produced by the transform inherits exactly that and nothing more. Groups can still gain, and so can one agent pretending to be a group. The VCG Mechanism contains a measured demonstration: on a 3-item, 3-bidder combinatorial auction, an exhaustive search over 4.9 million single-agent misreports found zero profitable deviations, while a search over pairs of reports found jointly profitable collusion, and a single bidder splitting into two false identities turned a utility of 0 into a utility of 2 — beating every one of the 729 single-identity reports available to it. Every one of those attacks is outside what the revelation principle constrains. Why VCG Is Rare in Practice develops the consequences.

6. Restricted message spaces: online mechanisms

If agents physically cannot send a message at some times, the interface layer cannot always be built. Parkes’s chapter in Algorithmic Game Theory gives an explicit counterexample in the online setting, where agents have arrival and departure times and can only speak in [aᵢ, dᵢ]. With two periods, one item, and one agent whose type is (1,1,1) or (1,2,1), an indirect mechanism using messages {1,2} in period 1 implements a policy that “cannot be implemented as a DSIC direct-revelation mechanism because type (1,2,1) is allocated in period 1 for payment 0.99, and so type (1,1,1) (which is unallocated if truthful) will want to report type (1,2,1).” The diagnosis: “the revelation principle fails in this example because the indirect mechanism prevents the agent from claiming a later departure than its true departure” (AGT Example 16.7). A partial repair exists — a “revelation principle plus heartbeat” in which the agent makes one type report but must also emit a non-informative message every period it claims to be present.

7. Privacy: direct revelation is maximal disclosure

Shoham and Leyton-Brown, again: “the revelation mechanism forces the agents to reveal their types completely. There may be settings in which agents are not willing to compromise their privacy to this degree. (Observe that the original mechanism may require them to reveal much less information.)” Roughgarden makes the same observation from the seller’s side: “ascending auctions leak less valuation information to the auctioneer. In a Vickrey auction, the auctioneer learns the highest bid; in an English auction, the auctioneer only learns a lower bound on the highest bid” (Lecture 7, footnote 4). If the auctioneer is a repeat player — a search engine, an exchange, a cloud provider — that difference is worth money, and bidders know it.

Failure Modes and Gotchas

“The revelation principle means we can always make our mechanism truthful.” No. It means: if you already have an equilibrium of a mechanism you like, there is an equivalent mechanism in which truth is an equilibrium of the same kind. Case C measured the trap: a Bayes–Nash input yields a BIC output that is not DSIC, and 0 of 4 transformed first-price mechanisms were strategyproof. If your system has no equilibrium, or you cannot compute it, the theorem gives you nothing.

Conflating the two halves of the conclusion. Case D above: outcome-equivalence holds unconditionally (it is a definition), incentive compatibility requires the equilibrium hypothesis. Feeding a plausible-but-non-equilibrium heuristic into the transform produced 270 distinct profitable lies while still reproducing the original outcomes perfectly. If you validate only equivalence, you will conclude your mechanism is truthful when it is not.

Assuming truthfulness is the interesting property. Roughgarden titles the section “The Revelation Principle and the Irrelevance of Truthfulness” and concludes: “truthfulness per se is not important; what makes mechanism design hard is the requirement that a desired outcome (without loss of generality, truthful reporting) [be] in an equilibrium of some type” (Lecture 4 §3.3). Truthfulness is a normal form for the statement of a mechanism, not a property that buys you anything by itself.

Forgetting that the transform imports the original mechanism’s tie-breaking. M′ inherits M’s behaviour exactly, including its arbitrary tie-breaks. If M broke ties by a rule that depends on the actions (bid submission order, say) rather than the types, M′ inherits a rule that is now a function of reports — and reports are strategic. My clock simulation broke ties toward the lowest index deterministically; a first draft that broke them by comparing the running price against a stale variable produced a mechanism where s(v) = v was not dominant (201 violations), and the checker caught it. Write the equilibrium checker before you trust the mechanism.

Using floats in the equilibrium check. Dominance is uᵢ(truth) ≥ uᵢ(lie). On payments that are differences of computed optima, float error of order 1e-16 will occasionally answer that question wrongly, and you will get a mechanism reported as truthful that is not, or vice versa. Everything above uses fractions.Fraction. The VCG Mechanism contains the measurement: 17 out of 4,000 random instances get different payment vectors under float arithmetic, with a worst-case error of 2.7 on values in [0, 3].

Assuming the direct mechanism is simpler. It is simpler to analyse and often far worse to run: it absorbs every agent’s strategising, demands complete type revelation up front, and destroys the incremental structure that made the indirect version tractable. The tables in §1 and §2 above are that trade-off, measured.

Alternatives and When to Choose Them

ApproachWhat it gives upWhen to reach for it
Direct + DSIC (the transform’s output from a dominant-strategy input)communication, computation, privacysmall type spaces; you want the weakest possible behavioural assumption; you are proving a theorem
Direct + BIC (Bayes–Nash input)robustness — needs a common prior and coordination on one equilibriumwhen no DSIC mechanism achieves your objective; Hartline: “there will be some environments where we derive BIC mechanisms where no analogous DSIC mechanism is known”
Indirect, iterative (English, clock, SMR spectrum auctions)the theorem’s convenience; opens new manipulationslarge or combinatorial type spaces; preference elicitation cost dominates; privacy matters
Obviously strategyproof (OSP)expressiveness — strictly fewer rules are OSP-implementable than DSIC-implementablewhen participants are cognitively limited or the designer’s commitment is partial
Maskin implementationsimplicity; requires strong conditions on the social choice rulewhen all equilibria must be good, not just one — the gap the revelation principle leaves open
Approximate / simple mechanisms (posted prices, greedy)exact optimalitywhen welfare maximisation is NP-hard; see Approximate and Simple Mechanisms

The honest summary from Roughgarden: “for sufficiently simple problems… DSIC mechanisms can do anything non-DSIC mechanisms can. In more complex problems… weakening the DSIC constraint often allows you [to] accomplish things that are provably impossible for DSIC mechanisms (assuming participants figure out and coordinate on the desired equilibrium). DSIC and non-DSIC mechanisms are incomparable in such settings — the former enjoy stronger incentive guarantees, the latter better performance guarantees” (Lecture 4 §3.2).

Production Notes

Wireless spectrum. The FCC has never run a direct mechanism for spectrum, and the reasons are exactly items 1 and 2 above. Roughgarden: “indirect auctions are unavoidable for all but the smallest combinatorial auctions” (Lecture 7 §3.2). His Lecture 8 opens by conceding the point at the level of theory: “for the first time in the course, we have no choice but to design and analyze indirect mechanisms, and especially iterative mechanisms that query bidders for relevant valuation information on a ‘need-to-know’ basis. This entails relaxing both the DSIC guarantee and full welfare maximization — we will miss these properties, but have no alternative” (Lecture 8 §1).

What indirect costs you. Iterative mechanisms open manipulations a direct mechanism forecloses. Cramton and Schwartz documented signalling in an early FCC auction: bidding for licence #378 (Rochester, MN), USWest retaliated against McLeod by bidding up licences elsewhere, and “to make sure its message came through loud and clear, all of USWest’s retaliatory bids were a multiple of 1000 plus 378” (recounted in Roughgarden Lecture 7 §3.2, citing Collusive Bidding: Lessons from the FCC Spectrum Auctions, J. Regulatory Economics 17(3), 2000). The countermeasure — forcing bids to be multiples of a large number — kills that channel and not the general problem. This is the price of leaving the direct world, and it is a real, documented price.

Elicitation in practice is far better than the worst case. Conitzer and Sandholm note that in explicit preference-elicitation approaches to combinatorial auctions, “in practice only a vanishingly small fraction of the bidders’ valuation information needs to be revealed before the optimal allocation can be determined for certain,” despite the worst case requiring exponential communication. That gap — worst case exponential, typical case tiny — is why indirect mechanisms ship.

Where the transform genuinely is used. As an analytical device, constantly and correctly: every derivation of an optimal auction, of Revenue Equivalence, and of the impossibility theorems runs through it. Nisan’s proof of revenue equivalence begins “Using the revelation principle, we can first limit ourselves to mechanisms that are truthful in the Bayesian–Nash sense”; the Gibbard–Satterthwaite theorem is stated for direct mechanisms and applies to all mechanisms only because of it (MAS Theorem 10.2.6). The Nobel background describes the intended workflow exactly: “once an optimal direct mechanism has been found, the researcher can ‘translate back’ that mechanism to a more realistic mechanism. By this seemingly roundabout method, researchers have been able to solve problems of institutional design that would otherwise have been effectively intractable.”

Uncertain

Verify: the attribution of the revelation principle’s first statement. Reason: Gibbard (1973) and Myerson (1979) could not be obtained from this machine — Econometrica and Journal of Mathematical Economics are paywalled and no institutional mirror was found for either. Two primary sources were read in full and are cited above rather than paraphrased: Vickrey 1961 (as a rendered image scan — jstor.org/stable/2977633 returns HTTP 200 with a Content-Security-Policy challenge shell, but a Princeton course mirror served the PDF, whose 31 pages carry zero extractable characters and no embedded fonts, so pdftoppm -png -r 120 and direct image reading were used) and Myerson 1981, Optimal Auction Design, whose identity was checked against its masthead: Mathematics of Operations Research 6(1), Feb 1981, pp. 58–73 — not Econometrica, which several secondary summaries imply. Myerson’s Lemma 1 there defers the general proof to his own earlier reference, which is the 1979 paper that could not be read. “Could not extract text” and “could not read” are different failures; only the first applied to Vickrey. Note that Myerson 1981’s PDF is an OCR’d JSTOR scan whose mathematics is mangled (arrows render as +, equation numbers as ( 3 3), so only its prose is quoted here and no formula is taken from it. Attribution of first statement rests on the Nobel committee’s scientific background document and on the history sections of Nisan et al. and Shoham & Leyton-Brown, all of which were fetched and read in full. These secondary sources disagree in emphasis: Shoham & Leyton-Brown say “the revelation principle was first articulated by Gibbard [1973] and was developed in the greatest generality by Myerson [1979; 1982; 1986]”, while the Nobel document adds that “several researchers independently extended it to the general notion of Bayesian Nash equilibrium (Dasgupta, Hammond and Maskin, 1979, Harris and Townsend, 1981, Holmstrom, 1977, Myerson, 1979, Rosenthal, 1978)”. To resolve: locate course-page or institutional mirrors (the */courses/*/papers/*.pdf pattern that worked for Vickrey) for Gibbard 1973 and Myerson 1979 and check their statements directly. #uncertain

See Also

Graph View

Backlinks