An Introduction to the Theory of Mechanism Design  Tilman Borgers

Preface v
1 Introduction 1
2 Screening 6
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Pricing a Single Indivisible Good . . . . . . . . . . . . . . . . 6
2.3 Nonlinear Pricing . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4 Bundling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.5 Comments on the Literature . . . . . . . . . . . . . . . . . . . 29
2.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3 Bayesian Mechanism Design 31
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 Single Unit Auctions . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.1 Set-Up . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.2 Mechanisms, Direct Mechanisms, and the Revelation
Principle . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.3 Characterizing Incentive Compatibility and Individual
Rationality . . . . . . . . . . . . . . . . . . . . . . 37
3.2.4 Expected Revenue Maximization . . . . . . . . . . . . 39
3.2.5 Maximizing Welfare . . . . . . . . . . . . . . . . . . . 42
3.2.6 Numerical Examples . . . . . . . . . . . . . . . . . . . 43
3.3 Public Goods . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3.1 Set-Up . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3.2 Incentive-Compatible and Individually Rational Direct
Mechanisms . . . . . . . . . . . . . . . . . . . . . 47
3.3.3 Ex ante and Ex post Budget Balance . . . . . . . . . 48
3.3.4 Welfare Maximization . . . . . . . . . . . . . . . . . . 51
i
CONTENTS ii
3.3.5 Prot Maximization . . . . . . . . . . . . . . . . . . . 58
3.3.6 A Numerical Example . . . . . . . . . . . . . . . . . . 59
3.4 Bilateral Trade . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.4.1 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.4.2 Direct Mechanisms . . . . . . . . . . . . . . . . . . . . 66
3.4.3 Welfare Maximization . . . . . . . . . . . . . . . . . . 68
3.4.4 Prot Maximization . . . . . . . . . . . . . . . . . . . 75
3.4.5 A Numerical Example . . . . . . . . . . . . . . . . . . 76
3.5 Comments on the Literature . . . . . . . . . . . . . . . . . . . 77
3.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4 Dominant Strategy Mechanisms 79
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.2 Single Unit Auctions . . . . . . . . . . . . . . . . . . . . . . . 82
4.2.1 Set-Up . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.2.2 Mechanisms, Direct Mechanisms, and the Revelation
Principle . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.2.3 Characterizing Dominant Strategy Incentive Compatibility
and Ex Post Individual Rationality . . . . . . . 84
4.2.4 Canonical Auctions . . . . . . . . . . . . . . . . . . . . 85
4.3 Public Goods . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
4.3.1 Set-Up . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
4.3.2 Direct Mechanisms . . . . . . . . . . . . . . . . . . . . 88
4.3.3 Characterizing Dominant Strategy Incentive Compatibility
and Ex Post Individual Rationality . . . . . . . 89
4.3.4 Canonical Mechanisms . . . . . . . . . . . . . . . . . . 91
4.3.5 Ex Post Budget Balance . . . . . . . . . . . . . . . . . 92
4.4 Bilateral Trade . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4.4.1 Set-Up . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4.4.2 Dominant Strategy Incentive Compatible and Ex Post
Individually Rational Direct Mechanisms . . . . . . . 94
4.4.3 Canonical Mechanisms . . . . . . . . . . . . . . . . . . 95
4.4.4 Ex Post Budget Balance . . . . . . . . . . . . . . . . . 96
4.5 Comments on the Literature . . . . . . . . . . . . . . . . . . . 97
4.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5 Dominance: General Theory 98
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.2 Set-Up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.3 Ex Post Revenue Equivalence . . . . . . . . . . . . . . . . . . 100
CONTENTS iii
5.4 Implementing Ecient Decision Rules . . . . . . . . . . . . . 101
5.5 Characterizing All Incentive Compatible Decision Rules . . . 102
5.6 All Incentive Compatible Decision Rules When Outcomes are
Lotteries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5.7 Single Dimensional Type Spaces . . . . . . . . . . . . . . . . 109
5.8 Suciency of Weak Monotonicity . . . . . . . . . . . . . . . . 113
5.9 Positive Association of Dierences . . . . . . . . . . . . . . . 114
5.10 Individual Rationality and Budget Balance . . . . . . . . . . 117
5.11 Remarks on the Literature . . . . . . . . . . . . . . . . . . . . 121
5.12 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
6 Bayesian Design: General Theory 122
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
6.2 Set-Up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
6.3 Independent Types . . . . . . . . . . . . . . . . . . . . . . . . 124
6.4 Correlated Types . . . . . . . . . . . . . . . . . . . . . . . . . 127
6.4.1 Framework . . . . . . . . . . . . . . . . . . . . . . . . 127
6.4.2 Failure of Revenue Equivalence . . . . . . . . . . . . . 127
6.4.3 Characterizing Bayesian Incentive Compatibility . . . 129
6.4.4 A Numerical Example . . . . . . . . . . . . . . . . . . 133
6.4.5 Individual Rationality and Budget Balance . . . . . . 135
6.4.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . 137
6.5 Complete Information . . . . . . . . . . . . . . . . . . . . . . 138
6.6 Eciency and Utilitarianism . . . . . . . . . . . . . . . . . . 138
6.7 Remarks on the Literature . . . . . . . . . . . . . . . . . . . . 138
6.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
7 Non-Transferrable Utility 140
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
7.2 The Gibbard Satterthwaite Theorem . . . . . . . . . . . . . . 141
7.2.1 Set Up . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
7.2.2 Statement of the Result and Outline of the Proof . . . 142
7.2.3 Every monotone direct mechanism is dictatorial . . . . 145
7.3 Dominant Strategy Incentive Compatibility On Restricted
Domains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
7.4 Bayesian Incentive Compatibility . . . . . . . . . . . . . . . . 151
7.5 Remarks on the Literature . . . . . . . . . . . . . . . . . . . . 153
7.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
CONTENTS iv
8 Interdependent Types 154
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
8.2 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
8.3 Impossibility of Implementing Welfare Maximizing Decision
Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
8.4 Characterizing All Incentive Compatible Mechanisms . . . . . 161
8.5 Remarks on the Literature . . . . . . . . . . . . . . . . . . . . 163
8.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
9 Robust Mechanism Design 164
10 Multiple Equilibria and Implementation 165
11 Dynamic Mechanism Design 166
12 Conclusion 167