Mechanism Design: Engineering the Rules of the Game

The "Engineering" Branch of Game Theory

Classical game theory analyzes existing rules: what is the equilibrium outcome? Mechanism design solves the reverse problem: which rules should be introduced so that rational behavior of players leads to the desired social outcome?

Analogy: classical game theory is physics (describes the world), mechanism design is engineering (designs the world). Leonid Hurwicz, Eric Maskin, and Roger Myerson won the 2007 Nobel Prize for foundational contributions.

Examples of mechanism design problems: how to sell government television frequencies for maximum revenue? How to organize trading on the electricity market to minimize costs? How to allocate healthcare resources "fairly" when patients have private information?

The Problem: Private Information

The key barrier is that agents have private information (type θᵢ), which the planner does not observe: willingness to pay, production function, risk attitude. Agents may lie about their type for personal gain.

A mechanism M = (S, g): message space S = S₁ × ... × Sₙ and outcome function g: S → X × ℝⁿ (decision + payments). The agent strategically chooses message sᵢ, which does not have to be truthful.

Revelation Principle

Direct mechanism: Each agent reports their type θ̂ᵢ (possibly falsely). The outcome function is g(θ̂) = (x(θ̂), t(θ̂)).

Incentive compatibility (DSIC): Truth-telling θ̂ᵢ = θᵢ is a dominant strategy for each agent for any types of opponents. Formally: uᵢ(θᵢ, g(θᵢ, θ₋ᵢ)) ≥ uᵢ(θᵢ, g(θ̂ᵢ, θ₋ᵢ)) for all θᵢ, θ̂ᵢ ≠ θᵢ, θ₋ᵢ.

Revelation theorem: For any mechanism M that implements outcome f in (Bayesian or dominant) equilibrium, there exists an equivalent direct mechanism that implements the same outcome under truthful strategies.

Corollary: without loss of generality, it suffices to consider only direct DSIC mechanisms. This is a colossal simplification: instead of all possible rules, it is enough to analyze truthful direct mechanisms.

The VCG Mechanism

VCG (Vickrey–Clarke–Groves) is a canonical example of a DSIC mechanism for the efficient allocation problem.

Selection rule: x*(θ) = argmax_x Σᵢ vᵢ(x, θᵢ) — the choice maximizing total value.

Clarke payment: tᵢ(θ) = Σⱼ≠ᵢ vⱼ(x*(θ), θⱼ) − Σⱼ≠ᵢ vⱼ(x*₋ᵢ(θ₋ᵢ), θⱼ)

Where x*₋ᵢ is the optimal outcome without agent i. Payment = "how much others gained from the presence of i".

Numerical example — two-slot auction: Slots with click-through rates α₁ = 1.0 and α₂ = 0.5. Three advertisers with valuations θ₁ = 10, θ₂ = 7, θ₃ = 4.

VCG allocation: slot 1 → agent 1 (valuation 10), slot 2 → agent 2 (valuation 7).

Payment of agent 1: Σⱼ≠₁ vⱼ for x* = 7×0.5+4×0 = 3.5. Without agent 1, optimal: slot 1 → 2 (7), slot 2 → 3 (4×0.5=2) → Σⱼ≠₁ = 9. t₁ = 3.5 − 9 = −5.5 (agent 1 pays 5.5).

Payment of agent 2: vⱼ≠₂ for x* = 10×1 = 10. Without agent 2: slot 1 → 1, slot 2 → 3 → vⱼ≠₂ = 10+4×0.5=12. t₂ = 10 − 12 = −2 (pays 2).

Properties of VCG: DSIC (truth-telling is optimal), efficiency. Drawback: not always budget-balanced (sum of payments can be negative — the planner needs additional funds).

The Myerson–Satterthwaite Theorem

Theorem (1983): In a bilateral market with private valuations of the seller (s) and buyer (b), s ~ Fₛ, b ~ F_b, there does not exist a mechanism that is simultaneously IC, IR (individually rational), EF (efficient), and BB (budget-balanced).

Meaning: a fundamental inevitability of losses — some mutually beneficial deals are not realized under private information. This is a normative "law" of information asymmetry.

Application: merger negotiations, land sales, healthcare contracts — everywhere some "blurred" value is lost due to information asymmetry.

Spectrum Auctions — Theory in Action

In 1994, the FCC (USA) first conducted spectrum frequency auctions instead of administrative allocation. Milgrom, Wilson, and McAfee developed the Simultaneous Ascending Auction (SAA): all lots are auctioned in parallel, round by round. This allows participants to purchase complementary lots and avoid the "exposure problem" (when the value of a package is higher than the sum of the separate lots). The US government raised over $100 billion in spectrum auctions — a direct result of applying mechanism design theory.

The VCG Mechanism in Internet Advertising and Spectrum Auctions

The VCG mechanism is at the foundation of the world's largest auction markets. Spectrum auctions held by the US Federal Communications Commission (FCC) since 1994 allocate radio frequency usage rights among telecommunications companies via combinatorial auctions, theoretically based on VCG. From 1994 to 2015, the US raised over $100 billion in such auctions. Google AdWords uses a variant of VCG — the Generalized Second-Price Auction (GSP) — to assign ad positions: advertisers bid for positions and pay the price of the next player, not their own bid. Although GSP is not strictly VCG, its stable equilibria coincide with VCG outcomes under certain conditions. Facebook Ads similarly uses a second price auction mechanism. Combinatorial auctions for sale of packages of flight routes, gas extraction rights, and electricity supply contracts require the VCG mechanism to achieve efficient allocation in the presence of complementarity or substitutability of lots. A billion-dollar replicator: correct design of the auction mechanism brings the state and society substantially more revenue and efficiency than suboptimal alternatives.

Assignment: (a) Design a VCG mechanism for a single object auction (agents have valuations θᵢ ~ U[0,1]). Show equivalence to a second-price auction. (b) Why is truth-telling a dominant strategy in the VCG mechanism (formally, via the IC-condition)? (c) Name a real-world example where VCG is applied in practice.