Mechanism Design: Revelation Principle, VCG & Auction Theory

Game theory asks what rational players do in a given game. Mechanism design asks the inverse question: given a desired outcome, what game should we design so that self-interested players produce it? This "reverse game theory" underlies spectrum auctions, ad auctions, and kidney exchange programs — anywhere a designer controls the rules and must account for players who will strategically exploit them.

Concepts

Imagine designing the rules for a spectrum auction: you decide who bids what, how allocations are determined, and what payments are required — but the bidders know their private values and will game whatever rules you set. Mechanism design asks: given that players are self-interested and strategic, what rule system produces the outcome you want? The Revelation Principle makes this tractable by collapsing the infinite space of possible rule systems down to a single question: can you design a "just tell me your type" game where truth-telling is the dominant strategy?

Direct Mechanisms: Types, Allocations, Payments

A mechanism design setting has:

• $n$ agents with private types $\theta_i \in \Theta_i$ (e.g., values for goods).
• A social choice function $f : \Theta \to X$ mapping type profiles to outcomes.
• A direct revelation mechanism $(x, p)$ consisting of an allocation rule $x : \Theta \to X$ and a payment rule $p : \Theta \to \mathbb{R}^n$.

Agent $i$'s utility is quasi-linear: $u_i(\theta_i, x, p_i) = v_i(\theta_i, x) - p_i$, where $v_i$ is the agent's value for outcome $x$ given type $\theta_i$.

Incentive Compatibility and Individual Rationality

A mechanism is dominant-strategy incentive compatible (DSIC) (also: strategyproof) if truthful reporting is a dominant strategy for every agent regardless of others' reports:

Bayesian incentive compatibility (BIC) weakens this: truthful reporting is optimal only in expectation over opponents' types. DSIC implies BIC.

A mechanism satisfies individual rationality (IR) if each agent weakly prefers participating: $v_i(\theta_i, x(\theta)) - p_i(\theta) \geq 0$ for all $\theta_i$ (ex-post IR), or in expectation (ex-ante IR).

The Revelation Principle

The Revelation Principle states: for any mechanism $M$ and any Bayesian Nash equilibrium $\sigma$ of $M$, there exists a DSIC direct mechanism that implements the same social choice function.

Proof by construction. Build a new mechanism where agents report types $\hat{\theta}_i$, and the mechanism internally simulates the equilibrium strategies $\sigma_i(\hat{\theta}_i)$ before running $M$ on the simulated actions. Truthful reporting in the new mechanism implements $\sigma$, and since $\sigma$ was an equilibrium of $M$, the new mechanism is DSIC.

The revelation principle collapses the design space: to find the best mechanism over all possible games and equilibria, it suffices to search over DSIC direct mechanisms — a constrained optimization problem rather than an infinite design space.

The proof-by-simulation argument is the key: any mechanism where players use a non-truthful equilibrium can be replaced by one that simulates those strategies internally, making truthful reporting reproduce the same outcome. This reduction is non-constructive — it says the DSIC mechanism exists without specifying how to find it. What it does is justify restricting the search space, turning an intractably large design problem into a feasibility-constrained optimization.

VCG Mechanism

The Vickrey-Clarke-Groves (VCG) mechanism implements the socially efficient allocation in dominant strategies.

Allocation: $x^*(\theta) = \arg\max_{x \in X} \sum_i v_i(\theta_i, x)$.

Clarke pivot payment for agent $i$:

where $x^*(\theta_{-i})$ is the efficient allocation without agent $i$.

Interpretation. Agent $i$ pays the externality they impose: the change in others' welfare caused by their participation. If agent $i$ shifts the allocation from $x^*(\theta_{-i})$ to $x^*(\theta)$, others' welfare changes by exactly $p_i(\theta)$.

DSIC proof. Agent $i$'s payoff is:

Maximizing this over reports is equivalent to maximizing total welfare $\sum_j v_j$, which is exactly what truthful reporting achieves.

Second-price auction as VCG. For a single item with $n$ bidders and values $v_1 > v_2 > \cdots > v_n$, VCG allocates to bidder 1 and sets $p_1 = v_2 - 0 = v_2$. The winner pays the second-highest bid — the Vickrey auction. The DSIC property follows directly: if value $v >$ highest competing bid $b$, bidding $v$ wins at price $b$ (surplus $v - b > 0$); underbidding below $b$ loses unnecessarily. If $v < b$, overbidding wins at price $b > v$ (negative surplus). Truth is dominant in both cases.

Myerson's Optimal Auction

For a single item with $n$ bidders having independent private values $v_i \sim F_i$ with density $f_i$, Myerson (1981) characterized the revenue-maximizing DSIC, IR mechanism via the virtual valuation:

The term $\frac{1 - F_i(v_i)}{f_i(v_i)}$ is the inverse hazard rate — the information rent the designer must concede to prevent type $v_i$ from mimicking lower types. Virtual valuation trades off the direct value $v_i$ against the rent cost.

Optimal mechanism: allocate the item to the bidder with the highest non-negative virtual valuation $\phi_i(v_i)$; charge the critical type (the value at which the winning bidder is just indifferent). For symmetric bidders with regular distributions ($\phi_i$ non-decreasing), this is a second-price auction with a reserve price $r$ satisfying $\phi(r) = 0$.

Revenue equivalence theorem. All DSIC, IR mechanisms that allocate identically in expectation and give zero utility to the lowest type generate the same expected revenue. The mechanism form shifts how revenue is extracted, not how much is extracted (holding fixed the allocation rule).

Impossibility: Myerson-Satterthwaite

For bilateral trade (one buyer, one seller, independent private values), no mechanism is simultaneously DSIC, ex-post IR, efficient, and budget-balanced. The four properties are jointly incompatible: efficient trade between privately informed parties requires either a subsidy or occasional failure to trade even when mutually beneficial.

Worked Example

Optimal Auction for Uniform Valuations

Single item, $n = 1$ bidder (monopoly pricing), value $v \sim \text{Uniform}[0, 1]$, so $F(v) = v$ and $f(v) = 1$.

Virtual valuation:

Reserve price: set $\phi(r) = 0 \implies 2r - 1 = 0 \implies r = 1/2$.

Optimal mechanism: post a take-it-or-leave-it price of $r = 1/2$. The item is sold iff $v \geq 1/2$.

Expected revenue:

Compare to second-price auction (no reserve). With one bidder and no reserve, the seller must post price 0 to always sell. Expected revenue $= \mathbb{E}[v] \cdot \mathbf{1}[\text{always sell at 0}] = 0$ (the bidder pays nothing since there is no competing bid). With a reserve of $r = 1/2$, revenue is $1/4 > 0$. The optimal mechanism strictly dominates the second-price auction without a reserve.

Extension to $n$ symmetric bidders. With $n$ bidders all with $v_i \sim \text{Uniform}[0,1]$, the virtual valuation is still $\phi(v) = 2v - 1$. The optimal mechanism is a second-price auction with reserve $r = 1/2$: allocate to the highest bidder if their value exceeds $1/2$, charge the maximum of the second-highest bid and $1/2$.

Revenue with $n = 2$:

where the payment is $\max(v_{(2)}, 1/2)$ conditional on selling. Working through: $\mathbb{E}[\text{revenue}] = 1/3$ for $n=2$ (standard calculation), compared to the second-price auction without reserve giving $\mathbb{E}[v_{(2)}] = 1/3$ for $n=2$ — the reserve only matters when both bids fall below $1/2$, which has probability $1/4$, adding $1/2 \cdot 1/4 = 1/8$ of revenue but losing the sale probability. The optimal reserve still yields strictly higher revenue than no reserve whenever the seller has market power.

Connections

Where Your Intuition Breaks

VCG achieves efficiency in dominant strategies — the mechanism theorem that seems too good to be true. The catch: efficiency and revenue are fundamentally in tension. The Myerson-Satterthwaite theorem proves that no mechanism can simultaneously achieve DSIC, ex-post IR, full efficiency, and budget-balance in bilateral trade. VCG gives up revenue-optimality (using a reserve price is not DSIC in general) and budget-balance (VCG payments go to a third party or are burned). The optimal Myerson auction gives up efficiency (excluding low types via the reserve). You cannot have all four properties at once, and every real mechanism is a tradeoff between them. Ad auction designers who want both strategyproofness and revenue must accept that some efficient allocations will not happen.