Decision Theory

Mechanism Design

Inverse game theory: designing rules so that self-interested agents produce desired outcomes. The revelation principle, VCG mechanisms, Myerson's optimal auction, and applications to ML marketplaces and data economics.

AdvancedTier 2Stable~45 min

Prerequisites

Game Theory Nash Equilibrium

Why This Matters

Game theory takes the rules of a game as given and asks what rational agents will do. Mechanism design inverts this: given the outcome you want, design the rules so that self-interested agents produce that outcome in equilibrium.

This matters for ML in concrete ways. Ad auctions (Google, Meta) are mechanisms that extract billions in revenue. Federated learning requires incentive-compatible protocols so that data providers contribute truthfully. Data marketplaces must price data fairly. Crowdsourcing platforms must elicit honest labels. Whenever you design a system where strategic agents interact, you are doing mechanism design.

Core Concepts

Definition

Social Choice Function

A social choice function (SCF) maps the agents' private types $\theta = (\theta_1, \ldots, \theta_n) \in \Theta = \Theta_1 \times \cdots \times \Theta_n$ to an outcome $x \in X$ . Each agent $i$ has a type $\theta_i \in \Theta_i$ representing their private information (valuation, preference, signal).

Agent $i$ 's utility for outcome $x$ when their type is $\theta_i$ is $u_i(x, \theta_i)$ .

The social welfare is $W(\theta) = \sum_{i=1}^n u_i(f(\theta), \theta_i)$ . An SCF is efficient (or welfare-maximizing) if $f(\theta) \in \arg\max_{x \in X} \sum_i u_i(x, \theta_i)$ for all $\theta$ .

Definition

Mechanism

A mechanism is a pair $(\Sigma, g)$ where $\Sigma = \Sigma_1 \times \cdots \times \Sigma_n$ is the message (action) space and $g: \Sigma \to X$ is the outcome function. Each agent $i$ sends a message $\sigma_i \in \Sigma_i$ , and the mechanism selects outcome $g(\sigma_1, \ldots, \sigma_n)$ .

A direct mechanism has $\Sigma_i = \Theta_i$ for all $i$ : agents report their types. An indirect mechanism allows arbitrary messages (e.g., bids in an auction).

Definition

Incentive Compatibility

A direct mechanism $(\Theta, g)$ is:

Dominant-Strategy Incentive Compatible (DSIC): Truth-telling is a dominant strategy for every agent, regardless of what others report:

$u_i(g(\theta_i, \theta_{-i}), \theta_i) \geq u_i(g(\theta_i', \theta_{-i}), \theta_i) \quad \forall \theta_i, \theta_i' \in \Theta_i, \; \forall \theta_{-i}$

Bayesian Incentive Compatible (BIC): Truth-telling is a Bayesian Nash equilibrium. Each agent's expected utility (over others' types, drawn from a common prior) is maximized by reporting truthfully:

$\mathbb{E}_{\theta_{-i}}[u_i(g(\theta_i, \theta_{-i}), \theta_i)] \geq \mathbb{E}_{\theta_{-i}}[u_i(g(\theta_i', \theta_{-i}), \theta_i)] \quad \forall \theta_i, \theta_i'$

DSIC is a stronger requirement than BIC. DSIC mechanisms work even if agents have wrong beliefs about others. BIC mechanisms require agents to have correct priors.

Definition

Individual Rationality (Participation Constraint)

A mechanism is (interim) individually rational if every agent's expected utility from participating is at least as good as their outside option (typically zero):

$\mathbb{E}_{\theta_{-i}}[u_i(g(\theta_i, \theta_{-i}), \theta_i)] \geq 0 \quad \forall \theta_i$

If agents can choose not to participate, the mechanism must satisfy this constraint or agents will opt out.

The Revelation Principle

Theorem

The Revelation Principle

Statement

For any mechanism $(\Sigma, g)$ and any equilibrium $\sigma^*: \Theta \to \Sigma$ of that mechanism, there exists a direct mechanism $(\Theta, g')$ in which truth-telling is an equilibrium and the outcome is the same:

$g'(\theta) = g(\sigma^*(\theta)) \quad \forall \theta \in \Theta$

If $\sigma^*$ is a dominant strategy equilibrium, then truth-telling is a dominant strategy in the direct mechanism. If $\sigma^*$ is a Bayesian Nash equilibrium, then truth-telling is a BNE in the direct mechanism.

Intuition

The mechanism designer can simulate any equilibrium behavior by asking agents to report their types and then computing what they would have done in the original mechanism. If lying in the original mechanism was suboptimal, then lying in the direct mechanism (which produces the same outcomes) is also suboptimal.

This is a powerful simplification. Instead of searching over all possible mechanisms with arbitrary message spaces, the designer can restrict attention to direct mechanisms where truth-telling is an equilibrium.

Proof Sketch

Define the direct mechanism $g'(\theta) = g(\sigma^*(\theta))$ .

Suppose agent $i$ considers misreporting $\theta_i'$ instead of $\theta_i$ in the direct mechanism. This gives outcome $g'(\theta_i', \theta_{-i}) = g(\sigma_i^*(\theta_i'), \sigma_{-i}^*(\theta_{-i}))$ .

But in the original mechanism, agent $i$ could have played $\sigma_i^*(\theta_i')$ instead of $\sigma_i^*(\theta_i)$ . Since $\sigma^*$ is an equilibrium, this deviation is not profitable:

$u_i(g(\sigma_i^*(\theta_i), \sigma_{-i}^*(\theta_{-i})), \theta_i) \geq u_i(g(\sigma_i^*(\theta_i'), \sigma_{-i}^*(\theta_{-i})), \theta_i)$

This translates directly to:

$u_i(g'(\theta_i, \theta_{-i}), \theta_i) \geq u_i(g'(\theta_i', \theta_{-i}), \theta_i)$

So truth-telling is an equilibrium of the direct mechanism.

Why It Matters

The revelation principle reduces mechanism design from an intractable search over all possible games to the tractable problem of finding a direct mechanism with truth-telling as equilibrium. This is why most of the literature studies direct revelation mechanisms: they are without loss of generality.

For ML applications: when designing data pricing, label elicitation, or federated learning protocols, you only need to consider mechanisms where agents report their true valuations or data quality, then verify that truth-telling is incentive compatible.

Failure Mode

The revelation principle is a theoretical tool, not a practical recommendation. Direct mechanisms may require agents to reveal all their private information, raising privacy concerns. Indirect mechanisms (like sealed-bid auctions) can be simpler and more robust in practice. The principle also assumes agents play the specified equilibrium, which may not hold with bounded rationality.

VCG Mechanisms

Definition

VCG Mechanism (Vickrey-Clarke-Groves)

The VCG mechanism selects the efficient outcome and charges each agent a payment that internalizes their externality on others. For type reports $\hat{\theta}$ :

Allocation: $x^*(\hat{\theta}) = \arg\max_{x \in X} \sum_{i=1}^n u_i(x, \hat{\theta}_i)$ (efficient outcome given reports).

Payment to agent $i$ :

$p_i(\hat{\theta}) = \sum_{j \neq i} u_j(x^*(\hat{\theta}), \hat{\theta}_j) - h_i(\hat{\theta}_{-i})$

where $h_i$ is an arbitrary function of others' reports.

Agent $i$ 's net utility is $u_i(x^*(\hat{\theta}), \theta_i) + p_i(\hat{\theta})$ .

Theorem

VCG is DSIC and Efficient

Statement

Under quasilinear preferences, the VCG mechanism is dominant-strategy incentive compatible (truth-telling is a dominant strategy) and efficient (the outcome maximizes social welfare).

Intuition

By reporting truthfully, agent $i$ 's reported utility aligns with their actual utility in the social welfare objective. Since the mechanism maximizes total reported welfare, truthful reporting causes the mechanism to also account for agent $i$ 's true preferences. The payment $h_i(\hat{\theta}_{-i})$ does not depend on $i$ 's report, so $i$ effectively maximizes $\sum_j u_j(x, \hat{\theta}_j)$ , which is the social welfare including $i$ 's own true utility when $\hat{\theta}_i = \theta_i$ .

Proof Sketch

Agent $i$ 's net utility when reporting $\hat{\theta}_i$ (others report $\hat{\theta}_{-i}$ ):

$u_i(x^*(\hat{\theta}_i, \hat{\theta}_{-i}), \theta_i) + \sum_{j \neq i} u_j(x^*(\hat{\theta}_i, \hat{\theta}_{-i}), \hat{\theta}_j) - h_i(\hat{\theta}_{-i})$

The last term $h_i(\hat{\theta}_{-i})$ does not depend on $\hat{\theta}_i$ , so agent $i$ maximizes:

$u_i(x^*(\hat{\theta}_i, \hat{\theta}_{-i}), \theta_i) + \sum_{j \neq i} u_j(x^*(\hat{\theta}_i, \hat{\theta}_{-i}), \hat{\theta}_j)$

When $\hat{\theta}_i = \theta_i$ , $x^*$ maximizes $\sum_j u_j(x, \hat{\theta}_j) = u_i(x, \theta_i) + \sum_{j \neq i} u_j(x, \hat{\theta}_j)$ , which is exactly what agent $i$ wants to maximize. So truth-telling is optimal regardless of $\hat{\theta}_{-i}$ .

Why It Matters

VCG is the canonical efficient mechanism. The Vickrey (second-price) auction is a VCG mechanism for single-item allocation. Google's Generalized Second Price (GSP) auction for ads is not VCG but was designed with similar goals. VCG provides the benchmark for what is achievable: efficiency with truthfulness.

Failure Mode

VCG has several practical problems. (1) Budget balance: VCG payments may not cover the mechanism's costs or may require subsidies. The Green-Laffont theorem shows that no mechanism is simultaneously efficient, DSIC, individually rational, and budget-balanced (except in trivial cases). (2) Computational complexity: Computing the efficient allocation $x^*$ is often NP-hard (e.g., combinatorial auctions). (3) Revenue: VCG maximizes welfare, not revenue. For revenue maximization, Myerson's optimal auction is needed.

The Vickrey (Second-Price) Auction

Example

Vickrey Auction as VCG

Single item, $n$ bidders. Bidder $i$ has private value $\theta_i$ for the item. The VCG mechanism:

Allocation: Give the item to the highest bidder: $i^* = \arg\max_i \hat{\theta}_i$ .

Payment: The winner pays the second-highest bid: $p_{i^*} = \max_{j \neq i^*} \hat{\theta}_j$ . All others pay 0.

Truth-telling is dominant. If you win at price $p$ , your surplus is $\theta_i - p$ . Bidding higher than $\theta_i$ risks winning at a price above your value. Bidding lower risks losing when you could have won profitably.

This is the VCG payment with $h_i(\hat{\theta}_{-i}) = \max_{j \neq i} \hat{\theta}_j$ (the welfare of others in the best allocation without $i$ ).

Myerson's Optimal Auction

Theorem

Myerson Optimal Auction Theorem (1981)

Statement

The revenue-maximizing auction allocates the item to the bidder with the highest virtual valuation $\psi_i(\theta_i)$ (provided it is nonneg), where:

$\psi_i(\theta_i) = \theta_i - \frac{1 - F_i(\theta_i)}{f_i(\theta_i)}$

and $F_i$ is the CDF and $f_i$ is the PDF of bidder $i$ 's value distribution. The payment is determined by the allocation rule via the payment identity.

For symmetric bidders (all $F_i = F$ ), the optimal auction is a second-price auction with reserve price $r^*$ satisfying $\psi(r^*) = 0$ , i.e., $r^* - (1 - F(r^*))/f(r^*) = 0$ .

Intuition

The virtual valuation adjusts for the information rent the seller must pay. A bidder with value $\theta_i$ can always pretend to have a lower value, and the mechanism must compensate for this temptation. The term $(1 - F_i(\theta_i))/f_i(\theta_i)$ is the information rent: the discount the seller gives to higher types to prevent mimicry by lower types. The optimal mechanism maximizes expected virtual welfare, not actual welfare.

Proof Sketch

By the revelation principle, restrict to BIC direct mechanisms. For a BIC mechanism, the allocation probability $q_i(\theta_i) = \Pr[\text{agent } i \text{ wins} \mid \theta_i]$ must be nondecreasing in $\theta_i$ .

The payment identity (from incentive compatibility) gives:

$p_i(\theta_i) = \theta_i q_i(\theta_i) - \int_{\underline{\theta}_i}^{\theta_i} q_i(t) \, dt - u_i(\underline{\theta}_i)$

Setting $u_i(\underline{\theta}_i) = 0$ (individual rationality binds at the lowest type), the expected revenue is:

$\text{Rev} = \sum_i \mathbb{E}_{\theta_i}\left[\psi_i(\theta_i) \cdot q_i(\theta_i)\right]$

Point-wise maximization of the integrand gives the result: allocate to $\arg\max_i \psi_i(\theta_i)$ when this maximum is nonneg.

Why It Matters

Myerson's theorem is the foundation of auction theory. It explains why eBay uses reserve prices, why Google's ad auctions have minimum bids, and why sellers should not always sell to the highest bidder (the reserve price screens out low-value bidders, extracting more revenue from high-value ones). The virtual valuation framework is also used in data pricing: the seller of data must account for the information rent when designing pricing schemes.

Failure Mode

The theorem assumes independent private values and known distributions $F_i$ . With correlated values, the optimal mechanism is different (Cremer-McLean can extract full surplus). With unknown distributions, the seller must learn the distributions from data, creating an explore-exploit tradeoff. The "increasing virtual valuation" (regularity) assumption fails for some distributions (e.g., certain bimodal distributions), requiring ironing.

Impossibility Results

Definition

Gibbard-Satterthwaite Impossibility Theorem

For social choice functions over three or more outcomes with unrestricted preferences: every SCF that is dominant-strategy incentive compatible and onto (every outcome is possible) must be dictatorial (one agent's preference determines the outcome).

This is the mechanism design analog of Arrow's impossibility theorem. It says that without restricting the domain (e.g., to quasilinear preferences), DSIC mechanisms are trivial.

The result explains why VCG requires quasilinear utilities: the quasilinear restriction is what enables non-dictatorial DSIC mechanisms.

Applications to ML

Ad auctions. Google's search ad auction is a mechanism that allocates ad slots to advertisers based on bids and quality scores. The Generalized Second Price (GSP) auction is not DSIC but has a Nash equilibrium that approximates VCG outcomes. Understanding mechanism design explains why Google charges the minimum bid needed to maintain position, not the actual bid.

Federated learning incentives. In federated learning, data providers train local models and share updates. Mechanism design addresses: how to compensate data providers fairly (Shapley value), how to prevent free-riding (agents who contribute little but benefit from the aggregate model), and how to ensure truthful contribution (agents do not corrupt their updates for strategic advantage).

Data markets. A data seller faces a mechanism design problem: buyers have private valuations for data, and the seller must design a pricing scheme that maximizes revenue or welfare. Myerson's framework applies: the optimal data pricing depends on the distribution of buyer valuations and the marginal value of additional data (often characterized by learning curves).

Crowdsourcing and label elicitation. When collecting labels from crowd workers, the mechanism must incentivize effort and accuracy. Peer prediction mechanisms use agreement between workers to incentivize truthful reporting without access to ground truth. Proper scoring rules are mechanisms that incentivize truthful probability reports.

Common Confusions

Watch Out

Efficiency and revenue maximization conflict

The VCG mechanism maximizes social welfare (efficiency) but does not maximize revenue. Myerson's optimal auction maximizes revenue but is not efficient (it withholds the item when the highest bid is below the reserve price, even though selling would increase total welfare). You cannot simultaneously maximize efficiency and revenue in general. This tension is central to auction design.

Watch Out

The revelation principle does not say direct mechanisms are best in practice

The revelation principle says that any outcome achievable by any mechanism can also be achieved by a direct mechanism with truth-telling. It does not say that direct mechanisms are simpler, more robust, or easier to implement. In practice, indirect mechanisms (auctions, markets) are preferred because they require less communication, are more robust to modeling errors, and are cognitively simpler for participants.

Watch Out

DSIC and BIC are very different in practice

DSIC mechanisms are robust: agents need no information about others and truth-telling is always optimal. BIC mechanisms require agents to have correct beliefs about others' type distributions. In ML applications where agent distributions are estimated from data, BIC mechanisms are fragile to estimation errors. When possible, prefer DSIC.

Exercises

ExerciseCore

Problem

In a second-price (Vickrey) auction with 3 bidders having true values $\theta_1 = 10$ , $\theta_2 = 7$ , $\theta_3 = 3$ , what is the outcome and revenue when all bid truthfully? What happens if bidder 1 bids $\hat{\theta}_1 = 15$ instead?

ExerciseCore

Problem

Consider a single-item auction with $n$ i.i.d. bidders, each with value drawn uniformly from $[0, 1]$ . Compute the virtual valuation $\psi(\theta) = \theta - (1 - F(\theta))/f(\theta)$ and find the optimal reserve price.

ExerciseAdvanced

Problem

Prove the payment identity for Bayesian incentive compatible mechanisms. If $q_i(\theta_i) = \mathbb{E}_{\theta_{-i}}[\mathbf{1}[\text{agent } i \text{ wins} \mid \theta_i]]$ is the interim allocation probability, show that BIC requires:

$p_i(\theta_i) = \theta_i q_i(\theta_i) - \int_{\underline{\theta}_i}^{\theta_i} q_i(t) \, dt + p_i(\underline{\theta}_i)$

where $p_i(\theta_i)$ is the expected payment of agent $i$ with type $\theta_i$ .

ExerciseResearch

Problem

The Cremer-McLean mechanism shows that with correlated values, a seller can extract the full surplus (every bidder's expected payment equals their expected value). Describe the key idea. Why does this not work with independent private values?

References

Canonical:

Myerson, "Optimal Auction Design" (1981), Mathematics of Operations Research
Vickrey, "Counterspeculation, Auctions, and Competitive Sealed Tenders" (1961), Journal of Finance
Clarke, "Multipart Pricing of Public Goods" (1971), Public Choice
Gibbard, "Manipulation of Voting Schemes" (1973), Econometrica

Textbook:

Nisan, Roughgarden, Tardos & Vazirani, Algorithmic Game Theory (2007), Chapters 9-13
Krishna, Auction Theory (2010), Chapters 3-5
Borgers, An Introduction to the Theory of Mechanism Design (2015), Chapters 1-4

ML Applications:

Jia et al., "Towards Efficient Data Valuation Based on the Shapley Value" (2019), AISTATS
Sim et al., "Collaborative Machine Learning Markets with Data-Replication-Robust Payments" (2020)

Next Topics

Mechanism design connects to many areas of ML theory. See game theory for the foundational framework and Nash equilibrium for the solution concept that mechanisms implement.

Last reviewed: April 2026

Prerequisites

Foundations this topic depends on.

Game Theory FoundationsLayer 2
Common Probability DistributionsLayer 0A
Sets, Functions, and RelationsLayer 0A
Basic Logic and Proof TechniquesLayer 0A
Convex Optimization BasicsLayer 1
Differentiation in RnLayer 0A
Matrix Operations and PropertiesLayer 0A
Nash EquilibriumLayer 2