Game Theory
Mechanism Design
How does the FCC sell radio spectrum for $45 billion? How does Google decide which ad to show and at what price? How are scarce vaccines allocated across regions? All of these are mechanism design problems: the 'engineering' side of game theory. Not analyzing games, but designing them. The 2007 and 2020 Nobels prove this is one of the most practically important areas of mathematics.
- **Google Ads (GSP):** every time someone searches Google, an auction determines who shows up and at what price. This is mechanism design in real time, billions of times a day
- **FCC spectrum auctions:** selling frequencies to telecom companies, an auction designed from scratch by game theorists. Milgrom and Wilson received the 2020 Nobel for this design
- **Matching markets:** the Gale-Shapley algorithm allocates residents to hospitals, children to schools, donor organs to recipients: an IC mechanism that changed medicine
Предварительные знания
Incentive Compatibility
The tax authority wants to know citizens' real income to collect taxes fairly. A hospital wants to know how urgently a patient needs surgery, to prioritize correctly. The problem: people lie when it's in their interest to do so. Mechanism design is 'game theory in reverse': instead of analyzing a given game, we design the rules so that rational agents find it in their interest to tell the truth and act as desired.
A mechanism (d, t) maps agents' reports to a decision d and transfers t. Dominant IC: it is in each agent's interest to report their true type θᵢ regardless of others' actions: uᵢ(d(θᵢ, θ₋ᵢ), tᵢ(θᵢ, θ₋ᵢ), θᵢ) ≥ uᵢ(d(θᵢ', θ₋ᵢ), tᵢ(θᵢ', θ₋ᵢ), θᵢ) for all θᵢ', θ₋ᵢ Bayesian IC: truthfulness is optimal in expectation.
Incentive compatibility is the central principle of mechanism design. The designer's goal: create rules where honest behavior is the best strategy for every agent. This eliminates the need for monitoring and coercion: agents themselves want to tell the truth.
Nobel Prizes for mechanism design
In 2007 Leonid Hurwicz, Eric Maskin, and Roger Myerson received the Nobel Prize for the foundations of mechanism design theory. Hurwicz introduced IC in the 1970s. Myerson proved the optimal auction theorem (1981). Maskin developed implementation theory. In 2020, Paul Milgrom and Robert Wilson received the Nobel for auction design, the practical application of these ideas.
A good mechanism is one that punishes lying
The best mechanism is one where lying is simply not in anyone's interest. An IC mechanism needs no monitoring; agents choose truthfulness on their own.
Monitoring is costly and incomplete. An IC mechanism (like the Vickrey auction) makes honesty a dominant strategy, economically more efficient and more robust to manipulation.
An incentive-compatible mechanism means that:
The Revelation Principle
Suppose a mechanism is being designed. Agents can make complex strategic reports, imitate different types, bluff. The task seems impossible: every possible private type must be accounted for, along with all possible strategies. The Revelation Principle cuts through this complexity: it suffices to consider only direct mechanisms, where each agent directly reports their type.
For any mechanism M with equilibrium σ*, there exists a direct IC mechanism M' that produces the same outcome: • Agents report their types θᵢ directly • The mechanism computes what they would have gotten in M's equilibrium Corollary: when searching for optimal mechanisms, it suffices to consider the class of direct IC mechanisms.
The Revelation Principle is a powerful analytical tool. It says there is no need to study every possible complex mechanism; finding the optimal direct IC mechanism is enough. This radically narrows the search space, and it is exactly what let Myerson derive optimal auction design.
The Revelation Principle means direct mechanisms are better than indirect ones
The Revelation Principle is an analytical tool: for every indirect mechanism there exists an equivalent direct one. This simplifies analysis but does not claim that direct is better in practice.
In practice, indirect mechanisms (auctions, negotiations) are often easier to implement. The Revelation Principle helps find lower bounds for indirect mechanisms by analyzing direct ones.
What does the Revelation Principle state?
The VCG Mechanism
A city wants to build a public park. Different residents value it differently. How would you determine total value and fairly share costs? The VCG mechanism (Vickrey-Clarke-Groves) is an elegant solution: each agent pays exactly the external harm their participation causes to others. This makes truthful reporting a strictly dominant strategy.
Choose decision d* maximizing total reported value: d* = argmax_d Σᵢ vᵢ(d, θᵢ) Transfer for agent i: tᵢ = Σⱼ≠ᵢ vⱼ(d*, θⱼ) - max_d Σⱼ≠ᵢ vⱼ(d, θⱼ) = (others' payoff with i) - (their max payoff without i) Agent i pays the Clarke tax, the external harm their presence causes others.
VCG is theoretically elegant: IC + efficiency. But in practice it has problems: budget deficit (total payments can be negative), vulnerability to collusion between agents, computational complexity with many alternatives. That's why simplified versions, such as Vickrey auctions, are more commonly used in practice.
VCG is perfect and is used everywhere in practice
VCG is theoretically optimal but has practical problems: budget deficit, vulnerability to collusion, computational complexity. Simplified versions are used in practice.
Google and Microsoft use modified VCG for ad auctions (GSP: Generalized Second Price), not pure VCG, because of its practical limitations.
What is the Clarke tax (an agent's payment) in the VCG mechanism?
Auction Design as Mechanism Design
Auction design is the most practical application of mechanism design. The seller wants to maximize revenue. Buyers know their own values; the seller does not. How do you set bidding rules so that agents honestly reveal information and the seller maximizes revenue? Myerson (1981) answered this completely.
With independent symmetric value distributions, the optimal auction: 1. Computes 'virtual values': ψ(v) = v - (1-F(v))/f(v) 2. Allocates to the bidder with max ψ(v) > 0 (if such a bidder exists) 3. Sets a reserve price r*: ψ(r*) = 0 Can be implemented as a second-price auction with an optimal reserve price.
| Mechanism | IC | Efficiency | Optimal revenue | Application |
|---|---|---|---|---|
| First-price auction | Bayesian | No | No (without reserve) | Real estate, procurement |
| Second-price (Vickrey) | Dominant | Yes | No (without reserve) | Google/Bing ads |
| Myerson's optimal auction | Dominant | No | Yes | Telecom licenses |
| VCG | Dominant | Yes | No | Spectrum auctions |
Google uses a pure Vickrey auction to sell ads
Google uses GSP (Generalized Second Price), a simplification of VCG for multiple positions. It is not strictly IC, but works well in practice.
Pure VCG for multiple ad positions is complex and has a budget deficit problem. GSP is simpler and more robust to practical manipulation, though theoretically inferior to VCG.
What is the 'virtual value' ψ(v) in Myerson's optimal auction theory?
Key ideas
- **Mechanism design is 'game theory in reverse':** design rules so that rational agents find it optimal to act as desired
- **Incentive compatibility:** honesty is a dominant strategy. No monitoring needed; agents want to reveal their type
- **Revelation Principle:** analyzing direct IC mechanisms is sufficient; simplifies design
- **VCG:** the only mechanism that is simultaneously IC and efficient. In practice: GSP and Vickrey with a reserve price
Related topics
Mechanism design is the applied branch of game theory, connected to auctions and platforms:
- Auction Theory — Auctions are the main application of mechanism design; Myerson's optimal auction theorem
- Extensive Form Games — Mechanisms are often sequential; the revelation principle works via backward induction
- Game Theory in Tech: pricing, markets — Google Ads, Uber surge pricing, marketplace design: mechanism design in products
Вопросы для размышления
- Facebook and Google know user preferences better than the user does. How does this change incentive compatibility: can mechanisms be designed when the agent doesn't know their own type?
- What happens if several agents collude in a VCG mechanism, reporting coordinated false types? How do designers try to protect against collusion?
- Uber uses surge pricing, raising prices during peak demand. Is this mechanism design? What are the incentives for drivers? For passengers? Is this mechanism fair?