Mechanism Design, Auctions, and the Revelation Principle¶
Job: develop the revelation principle / direct mechanisms (IC), the auction theory (first-price / second-price / Vickrey / Myerson optimal), the VCG / Groves mechanisms, and the implementation / social choice — with the Myerson optimal auction / VCG as the worked example.
Core¶
The revelation principle and the direct mechanism¶
The revelation principle: any Bayes–Nash equilibrium outcome achievable by any mechanism is achievable by a direct truth-telling mechanism (the Myerson). The incentive compatibility (IC): the truth-telling is the equilibrium.
| Revelation / direct / IC | Description |
|---|---|
| Revelation principle | any BNE outcome achievable by a direct truth-telling mechanism (the Myerson) |
| Direct mechanism | the players report types directly; the mechanism maps reports to outcomes |
| Incentive compatibility (IC) | truth-telling is the BNE (the \(u_i(\theta_i, s_i=\theta_i)\ge u_i(\theta_i, s_i)\) for all \(s_i\), the optimization) |
The auction theory and the Myerson¶
| Auction / Myerson | Description |
|---|---|
| First-price | the highest bid wins, pays own bid (the shading, the BNE the shading) |
| Second-price / Vickrey | the highest bid wins, pays second-highest (the truthful, the dominant strategy) |
| Myerson optimal | the Myerson 1981: the virtual valuation, the optimal the highest virtual (the optimization) |
| Virtual valuation | \(\varphi_i(v_i)=v_i-\frac{1-F_i(v_i)}{f_i(v_i)}\) (the virtual, the Myerson) |
The VCG and the Groves¶
| VCG / Groves | Description |
|---|---|
| VCG (Vickrey–Clarke–Groves) | the truthful, the social welfare maximizing (the each pays the externality, the optimization) |
| Groves | the Groves class (the VCG the special, the optimization) |
The implementation and the social choice¶
| Implementation / social choice | Description |
|---|---|
| Implementation (Maskin) | the Maskin monotonicity (the social choice rule implementable, the optimization) |
| Social choice / Arrow | the Arrow impossibility (the no universal social welfare, the optimization) |
See it¶
Myerson optimal auction and the VCG / Vickrey. The Myerson: the virtual valuation \(\varphi_i(v_i)=v_i-\frac{1-F_i(v_i)}{f_i(v_i)}\), the optimal the highest virtual (the Myerson 1981, the optimization). The VCG: the Vickrey–Clarke–Groves (the second-price, the truthful, the social welfare, the optimization). The key point: the Myerson the virtual (the optimal the revenue-maximizing), the VCG the truthful (the welfare-maximizing).
Check¶
Show that the second-price auction is truthful (the dominant strategy), and explain the VCG.
The second-price (Vickrey): the highest bid wins, pays the second-highest. The truthful: for the bidder \(i\) with value \(v_i\), the bidding \(b_i=v_i\) the dominant strategy (the \(u_i(v_i,b_i,b_{-i})\): if \(b_i>v_i\) the risk of overpaying, if \(b_i<v_i\) the risk of losing, the \(b_i=v_i\) the optimal). The proof: the \(u_i=(v_i-b_{(2)})\mathbf{1}_{b_i>b_{(2)}}\) (the \(b_{(2)}\) the second-highest), the \(b_i=v_i\) the dominant (the overbidding the risk, the underbidding the loss). The VCG: the generalization (the each pays the externality, the \(p_i=\sum_{j\ne i}v_j(s_{-i})-\sum_{j\ne i}v_j(s)\), the social welfare the maximizing, the truthful). So the Vickrey the truthful, the VCG the generalization.
Explain the Myerson optimal auction and the virtual valuation, and the revenue equivalence.
The Myerson: the optimal auction the revenue-maximizing (the Myerson 1981). The virtual valuation \(\varphi_i(v_i)=v_i-\frac{1-F_i(v_i)}{f_i(v_i)}\) (the virtual, the \(v_i\) the value minus the information rent \(\frac{1-F}{f}\)). The optimal: the highest virtual (the allocate to the highest \(\varphi_i(v_i)\ge0\), the reserve the \(\varphi^{-1}(0)\), the Myerson). The revenue equivalence: the any auction with the same allocation rule + the same payment (the expected revenue the same, the Myerson — the revenue determined by the allocation, not the payment rule). So the Myerson the virtual (the optimal), the revenue equivalence the allocation.
Pitfalls¶
- The revelation principle the BNE (the any BNE the direct — the dominant-strategy the different, the VCG the dominant, the Myerson the BNE).
- The Myerson the virtual (the revenue-maximizing, not the welfare — the VCG the welfare, the Myerson the revenue).
- The VCG / Groves the truthful (the dominant strategy, the social welfare — but the VCG the budget issues, the Myerson the revenue).
- The Arrow impossibility (the no universal social welfare — the dictatorship, the IIA, the Pareto the incompatible).
Refs¶
- Myerson, "Optimal auction design" (Math. OR 1981); the Myerson optimal / the virtual
- Vickrey, "Counterspeculation, auctions" (1961); Clarke (1971), Groves (1973) — the VCG
- Maskin, "Nash equilibrium and welfare optimality" (1999); the implementation
- Arrow, "A difficulty in the concept of social welfare" (1950); the impossibility
Next¶
GT index · Foundations · Repeated & Folk · Learning & No-Regret · Cooperative & Combinatorial · Optimization · Information theory