Mechanism Design & Auctions
Mechanism Design & Auctions
Mechanism design ('reverse game theory') asks: given a desired outcome, what rules of the game implement it? A mechanism $(M,g)$ specifies a message space $M_i$ for each player and an outcome function $g:M\to X$. The revelation principle reduces the design problem: any Bayes-Nash equilibrium of any mechanism can be replicated by a direct, incentive-compatible mechanism where truth-telling is optimal. This principle underlies optimal auction theory and the design of markets, voting rules, and matching algorithms.
Incentive Compatibility & Revelation Principle
A direct mechanism is incentive compatible (IC) if truth-telling is a dominant strategy (strategy-proof) or Bayes-Nash equilibrium (Bayesian IC). For single-dimensional private types $\theta_i\in[\underline{\theta},\bar{\theta}]$, Myerson's characterization: a direct mechanism $(q,t)$ (allocation $q_i(\theta)$, payment $t_i(\theta)$) is BIC and individually rational iff (i) $q_i(\theta_i,\cdot)$ is non-decreasing in $\theta_i$, and (ii) payments satisfy $t_i(\theta_i)=\theta_i q_i(\theta_i)-\int_{\underline\theta}^{\theta_i}q_i(s,\theta_{-i})\,ds - U_i(\underline\theta)$.
Myerson's Optimal Auction (Revenue Equivalence)
For $n$ buyers with i.i.d. types $\theta_i\sim F$ on $[0,1]$, all auction formats (first-price, second-price, Dutch, English) yield the same expected revenue when buyers follow symmetric equilibrium strategies (Revenue Equivalence Theorem). The revenue-maximizing auction uses virtual valuations $\psi(\theta_i)=\theta_i-\frac{1-F(\theta_i)}{f(\theta_i)}$: allocate to the buyer with the highest non-negative virtual valuation; set a reserve price at $\psi^{-1}(0)$.
Example 1
In a second-price sealed-bid auction with $n$ bidders having values $v_i\sim U[0,1]$ i.i.d., show that bidding $b_i=v_i$ is a dominant strategy and compute the seller's expected revenue.
Solution: Dominant strategy: suppose others bid $b_{-i}$. Bidding $v_i$: win iff $v_i>\max b_{-i}$, pay second-highest bid. Any bid $b_i>v_i$ wins more often but only in cases where the second-highest bid $>v_i$ (losing money). Any bid $b_i
Example 2
In a first-price auction with 2 bidders, $v_i\sim U[0,1]$, find the symmetric Bayes-Nash equilibrium bidding strategy.
Solution: In symmetric BNE, each bidder uses strategy $b(v)$. Bidder 1 with value $v$ maximizes $(v-b)\cdot P(b>b(v_2))=(v-b)\cdot b/b(\bar{v})$... assume $b(v)=\alpha v$ (linear equilibrium). Bidder 1's expected payoff: $(v-\alpha v_1^*)\cdot P(\alpha v_2<\alpha v_1^*)=(v-b)\cdot(b/\alpha)$ assuming $b=\alpha v$. Maximizing: $(v-b)/\alpha - b/\alpha=0$ is wrong approach. Better: maximize $(v-b)\cdot(b/(\alpha))$, $\partial/\partial b: -b/\alpha+(v-b)/\alpha=0\Rightarrow v=2b\Rightarrow b(v)=v/2$. So $\alpha=1/2$: bid half your value. Expected revenue: $E[\max(v_1/2,v_2/2)]=\frac{1}{2}E[\max(v_1,v_2)]=\frac{1}{2}\cdot\frac{2}{3}=\frac{1}{3}$. Revenue equivalent to second-price.
Practice
- Prove the Revenue Equivalence Theorem: any two standard auction formats with symmetric equilibria yield the same expected revenue when buyers have i.i.d. types.
- Describe the Vickrey-Clarke-Groves (VCG) mechanism and prove it is strategy-proof.
- For a single seller and buyer with $v\sim U[0,1]$, find the Myerson optimal mechanism (monopoly pricing with reserve price $r=1/2$) and compute expected revenue.
- Explain why the FCC spectrum auctions use simultaneous ascending-bid auctions rather than sealed-bid formats, connecting to exposure and complementarity problems.
Show Answer Key
1. Under the conditions (i.i.d. private values, symmetric bidders, same allocation rule), any two mechanisms allocating to the highest-value bidder have the same expected revenue. Proof: by the envelope theorem, $U_i(v_i)=U_i(0)+\int_0^{v_i}Q_i(t)dt$ where $Q_i$ is the prob of winning, which is the same for both mechanisms.
2. VCG: each agent reports their value, the mechanism chooses the allocation maximizing total value, and charges agent $i$ the externality they impose: $t_i=\sum_{j\neq i}v_j(a^{*-i})-\sum_{j\neq i}v_j(a^*)$ where $a^*$ is optimal with $i$ and $a^{*-i}$ without. Truth-telling is dominant because $i$'s payment doesn't depend on their own report (only on others' values), so maximizing $v_i(a)-t_i$ aligns with maximizing total welfare.
3. Myerson: for $v\sim U[0,1]$, the virtual value is $\psi(v)=2v-1$. Sell iff $\psi(v)\ge0$, i.e., $v\ge1/2$. So set reserve price $r=1/2$. Expected revenue $=\int_{1/2}^1 v\,dv=3/8... $ Actually: revenue $=$ E[payment] $=P(v\ge1/2)\cdot E[\text{payment}|\text{sale}]=1/2\cdot3/4=3/8$. Wait: for second-price with reserve $r$: $E[\text{rev}]=P(v>r)\cdot r=1/2\cdot1/2=1/4$? No, for a single buyer: revenue $=r\cdot P(v\ge r)=r(1-r)$, maximized at $r=1/2$, revenue $=1/4$.
4. Sealed-bid formats suffer from the winner's curse (common values), strategic demand reduction, and cannot reveal complementarities between items. Simultaneous ascending auctions allow price discovery, efficient aggregation of complementary licenses, and reduce the winner's curse by letting bidders observe prices. They handle exposure risk (paying for incomplete bundles) better through iterative bidding.