Mechanism Design

Overview

Mechanism Design Flow

Mechanism design is "reverse game theory": instead of analyzing existing games, we design games (mechanisms) to achieve desired outcomes when players act strategically. The designer controls the rules but not the players' private information or actions.

Formal Setting

Agents: N = {1, ..., n} with private types theta_i in Theta_i (valuations, preferences)
Outcomes: Set of possible outcomes O
Social choice function: f: Theta -> O mapping type profiles to desired outcomes
Mechanism: (M, g) where M = M_1 x ... x M_n is the message/action space and g: M -> O is the outcome function
Goal: Design (M, g) such that strategic agents' behavior implements f

A social choice function (SCF) selects a single outcome for each preference profile. A social choice correspondence selects a set of acceptable outcomes.

Preference Aggregation

Given individual preference orderings over alternatives, aggregate into a social ordering or choice.

Condorcet criterion: An alternative that beats every other in pairwise majority comparison should be chosen (Condorcet winner). A Condorcet winner need not exist (Condorcet paradox/cycle).

Pareto efficiency: Outcome x is Pareto efficient if no other outcome y makes everyone weakly better off and at least one player strictly better off. Minimal requirement for any reasonable SCF.

Strategyproofness

A mechanism is strategyproof (dominant-strategy incentive compatible, DSIC) if truthful reporting is a dominant strategy for every agent:

u_i(g(theta_i, m_{-i}), theta_i) >= u_i(g(m_i, m_{-i}), theta_i) for all m_i, m_{-i}, theta_i

Stronger than Bayesian incentive compatibility (BIC), which only requires truthfulness to be optimal in expectation over others' types.

Revelation Principle

Theorem: For any mechanism that implements a social choice function f in dominant strategies (or BNE), there exists a direct revelation mechanism where:

Each agent reports their type (M_i = Theta_i)
Truthful reporting is an equilibrium
The outcome is f(theta)

Implication: We can restrict attention to direct, truthful mechanisms without loss of generality when studying implementability. This dramatically simplifies mechanism design.

Limitations: The revelation principle does not address computational complexity, communication costs, or privacy. Indirect mechanisms may be preferable in practice for these reasons.

Gibbard-Satterthwaite Theorem

Theorem: If |O| >= 3 and f: Theta -> O is a surjective social choice function defined on the unrestricted domain of strict preference orderings, then f is strategyproof if and only if f is dictatorial (there exists a player i such that f always selects i's top choice).

Implications: Without domain restrictions or monetary transfers, no non-dictatorial voting scheme can be strategyproof for 3+ alternatives. This motivates:

Domain restrictions: Single-peaked preferences (median voter), quasi-linear utilities
Monetary transfers: VCG mechanisms
Relaxed solution concepts: Approximate strategyproofness, group strategyproofness

Comparison with Arrow's theorem: Arrow shows impossibility of a social welfare function (ranking) satisfying unanimity, IIA, and non-dictatorship. Gibbard-Satterthwaite shows impossibility for social choice functions under strategyproofness.

VCG Mechanism (Vickrey-Clarke-Groves)

The central positive result in mechanism design with money. Applies to settings with quasi-linear utilities: u_i(o, t_i) = v_i(o, theta_i) - t_i, where t_i is the payment by agent i.

Definition

The VCG mechanism:

Allocation: Choose the outcome maximizing social welfare: o* = argmax_o sum_i v_i(o, theta_i)
Payment: Each agent pays the externality they impose: t_i = max_o sum_{j != i} v_j(o, theta_j) - sum_{j != i} v_j(o*, theta_j)

Equivalently, t_i = h_i(theta_{-i}) - sum_{j != i} v_j(o*, theta_j) for any function h_i independent of theta_i (the Clarke pivot rule uses h_i = max_o sum_{j != i} v_j).

Properties

DSIC: Truthful reporting is a dominant strategy (each agent's payment is independent of their own report's effect on their utility; they internalize the social welfare maximization objective)
Efficient: Implements the welfare-maximizing outcome
Individually rational: With Clarke pivot payments, no agent pays more than their value
Weakly budget balanced: Total payments are non-negative (the mechanism does not inject money)

Limitations

Not strongly budget balanced: Payments need not sum to zero; surplus is "burned"
Computational: Finding o* may be NP-hard (e.g., combinatorial auctions). VCG with approximate welfare maximization is not generally truthful.
Not revenue-maximizing: VCG optimizes efficiency, not revenue
Collusion vulnerability: Groups of agents may benefit from coordinated misreporting
Uniqueness: VCG is essentially the only efficient DSIC mechanism (Green-Laffont theorem, with Roberts' theorem for general outcome spaces with sufficient richness)

Special Cases

Vickrey auction: VCG for single-item allocation; winner pays second-highest bid
Clarke pivot: The specific payment rule using h_i = optimal welfare without agent i

Myerson's Optimal Auction

Maximizes expected revenue (not welfare) for a single item.

Setup

n bidders with independent private values v_i drawn from distributions F_i with densities f_i. Regularity assumption: the virtual valuation phi_i(v_i) = v_i - (1 - F_i(v_i))/f_i(v_i) is non-decreasing.

Optimal Mechanism

Compute virtual valuations phi_i(v_i) for each bidder
Allocate the item to the bidder with the highest virtual valuation, provided it is positive
If all virtual valuations are negative, retain the item (reserve price)
Charge each winner their critical value (the minimum bid at which they would still win)

Payment identity: E[t_i(v_i)] = v_i * x_i(v_i) - integral_0^{v_i} x_i(z) dz, where x_i(v_i) is the probability of winning.

For symmetric bidders (identical distributions), the optimal auction reduces to a second-price auction with reserve price r* = phi^{-1}(0).

Revenue Equivalence Theorem

Any two mechanisms that allocate the item identically (same allocation rule as a function of types) and give zero expected payment to the lowest type yield the same expected revenue. This implies first-price, second-price, English, and Dutch auctions are revenue-equivalent under independent private values with risk-neutral bidders.

Proof sketch: By the payment identity, the payment is uniquely determined by the allocation rule and the boundary condition (payment at the lowest type).

Mechanism Design Without Money

When monetary transfers are infeasible (organ exchange, school choice, course allocation), different tools are needed.

Matching Mechanisms

Deferred acceptance (Gale-Shapley): Strategyproof for the proposing side; produces a stable matching. Used for residency matching (NRMP), school choice.

Top trading cycles (TTC): Strategyproof, Pareto-efficient, individually rational mechanism for house exchange problems. Each agent points to their top choice; cycles trade simultaneously; repeat.

Impossibility: No stable matching mechanism is strategyproof for both sides (Roth). No mechanism is simultaneously stable, strategyproof, and Pareto-efficient in many settings.

Random Assignment

Random serial dictatorship (RSD): Random priority ordering; agents choose sequentially. Strategyproof, ex-post efficient. Probabilistic serial (PS): Simultaneous "eating" of probability shares; ordinally efficient but not strategyproof.

Kidney Exchange

Pairwise and multi-way kidney exchange via cycle and chain detection in compatibility graphs. NP-hard for long cycles; practical mechanisms limit cycle length (2-3) and use long altruistic chains. Strategyproofness challenges: hospitals may withhold easy-to-match pairs.

Computational Mechanism Design

The intersection of mechanism design and computational complexity:

Automated mechanism design: Formulate mechanism design as an optimization problem; solve computationally for specific settings (Conitzer-Sandholm)
Approximation mechanisms: When optimal mechanisms are computationally intractable, design polynomial-time mechanisms with bounded approximation ratios
Communication complexity: How many bits must agents communicate? Revelation mechanisms may require exponential communication (e.g., combinatorial auctions)
Cryptographic mechanism design: Use cryptographic tools (secure computation, commitment schemes) to implement mechanisms without a trusted mediator

Key Impossibility Results Summary

| Result | Setting | Impossibility | |---|---|---| | Gibbard-Satterthwaite | Ordinal, >= 3 alternatives | SP implies dictatorial | | Arrow | Social welfare function | IIA + unanimity + non-dictatorship | | Myerson-Satterthwaite | Bilateral trade | No efficient, IR, BIC, BB mechanism | | Green-Laffont | Quasi-linear, DSIC, efficient | Must be VCG (affine maximizer) |

The Myerson-Satterthwaite theorem deserves emphasis: with bilateral trade (buyer and seller with private values, overlapping support), no mechanism simultaneously achieves efficiency, individual rationality, incentive compatibility, and budget balance. This is a deep impossibility that explains why markets cannot be perfectly designed.