|
Preface |
6 |
|
|
Acknowledgments |
9 |
|
|
Contents |
12 |
|
|
Acronyms |
17 |
|
|
Introduction |
18 |
|
|
1.1 Motivating Problems in Network Economics |
18 |
|
|
1.1.1 Sponsored Web Search Auctions |
18 |
|
|
1.1.2 Resource Allocation in Grid Computing |
20 |
|
|
1.1.3 Protocol Design in Wireless Ad Hoc Networks |
21 |
|
|
1.1.4 Supply Chain Network Formation |
22 |
|
|
1.1.5 Nature of the Problems |
23 |
|
|
1.2 Mechanism Design |
24 |
|
|
1.2.1 Mechanisms: Some Simple Examples |
25 |
|
|
1.2.2 Mechanism Design: A Brief History |
25 |
|
|
1.3 Outline of the Monograph |
26 |
|
|
Chapter 2: Foundations of Mechanism Design |
27 |
|
|
Chapter 3: Mechanism Design for Sponsored Search Auctions |
27 |
|
|
Chapter 4: Resource Allocation in Computational Grids |
28 |
|
|
Chapter 5: Design of Incentive Compatible Broadcast Protocols in Ad Hoc Networks |
28 |
|
|
Chapter 6: To Probe Further |
29 |
|
|
References |
29 |
|
|
Foundations of Mechanism Design |
30 |
|
|
2.1 Strategic Form Games |
30 |
|
|
2.1.1 Key Notions |
31 |
|
|
2.1.2 Examples of Strategic Form Games |
34 |
|
|
2.2 Dominant Strategy Equilibria |
40 |
|
|
2.2.1 Strong Dominance |
40 |
|
|
2.2.2 Weak Dominance |
41 |
|
|
2.3 Pure Strategy Nash Equilibrium |
43 |
|
|
2.3.1 Pure Strategy Nash Equilibria: Examples |
45 |
|
|
2.3.2 Interpretations of Nash Equilibrium |
49 |
|
|
2.3.3 Existence of a Pure Strategy Nash Equilibrium |
50 |
|
|
2.3.4 Existence of Multiple Nash Equilibria |
50 |
|
|
2.4 Mixed Strategy Nash Equilibrium |
51 |
|
|
2.4.1 Randomized Strategies or Mixed Strategies |
51 |
|
|
2.4.2 Mixed Strategy Nash Equilibrium |
53 |
|
|
2.4.3 Existence of Mixed Strategy Nash Equilibrium |
56 |
|
|
2.4.4 Computation of Nash Equilibria |
56 |
|
|
2.5 Bayesian Games |
57 |
|
|
2.5.1 Examples of Bayesian Games |
59 |
|
|
2.5.2 Type Agent Representation and the Selten Game |
61 |
|
|
2.5.3 Equilibria in Bayesian Games |
65 |
|
|
2.5.4 Dominant Strategy Equilibria |
67 |
|
|
2.6 The Mechanism Design Environment |
68 |
|
|
2.7 Examples of Social Choice Functions |
72 |
|
|
2.8 Implementation of Social Choice Functions |
79 |
|
|
2.8.1 Implementation Through Direct Mechanisms |
79 |
|
|
2.8.2 Implementation Through Indirect Mechanisms |
82 |
|
|
2.8.3 Bayesian Game Induced by a Mechanism |
85 |
|
|
2.8.4 Implementation of a Social Choice Function by a Mechanism |
87 |
|
|
2.9 Incentive Compatibility and the Revelation Theorem |
88 |
|
|
2.9.1 Incentive Compatibility (IC) |
90 |
|
|
2.9.2 The Revelation Principle for Dominant Strategy Equilibrium |
92 |
|
|
2.9.3 The Revelation Principle for Bayesian Nash Equilibrium |
93 |
|
|
2.10 Properties of Social Choice Functions |
95 |
|
|
2.10.1 Ex-Post Efficiency |
96 |
|
|
2.10.2 Dictatorship in SCFs |
96 |
|
|
2.10.3 Individual Rationality |
97 |
|
|
2.10.4 Efficiency |
98 |
|
|
2.11 The Gibbard-Satterthwaite Impossibility Theorem |
99 |
|
|
2.11.1 The G-S Theorem |
101 |
|
|
2.11.2 Implications of the G-S Theorem |
104 |
|
|
2.12 Arrow's Impossibility Theorem |
104 |
|
|
2.13 The Quasilinear Environment |
110 |
|
|
2.14 Groves Mechanisms |
114 |
|
|
2.14.1 VCG Mechanisms |
115 |
|
|
2.14.2 The Groves' Theorem |
116 |
|
|
2.14.3 Groves Mechanisms and Budget Balance |
118 |
|
|
2.15 Clarke (Pivotal) Mechanisms |
119 |
|
|
2.15.1 Clarke Mechanisms and Weak Budget Balance |
120 |
|
|
2.15.2 Clarke Mechanisms and Individual Rationality |
122 |
|
|
2.16 Examples of VCG Mechanisms |
123 |
|
|
2.17 Bayesian Implementation: The dAGVA Mechanism |
130 |
|
|
2.17.1 The dAGVA Mechanism |
131 |
|
|
2.17.2 The dAGVA Mechanism and Budget Balance |
132 |
|
|
2.17.3 The Myerson-Satterthwaite Theorem |
134 |
|
|
2.17.4 Mechanism Design Space in Quasilinear Environment |
135 |
|
|
2.18 Bayesian Incentive Compatibility in Linear Environment |
136 |
|
|
2.19 Revenue Equivalence Theorem |
138 |
|
|
2.19.1 Revenue Equivalence of Two Auctions |
139 |
|
|
2.19.2 Revenue Equivalence of Four Classical Auctions |
141 |
|
|
2.20 Myerson Optimal Auction |
146 |
|
|
2.20.1 Optimal Mechanism Design Problem |
147 |
|
|
2.20.2 Myerson's Optimal Reverse Auction |
148 |
|
|
2.21 Further Topics in Mechanism Design |
153 |
|
|
2.21.1 Characterization of DSIC Mechanisms |
153 |
|
|
2.21.2 Dominant Strategy Implementation of BIC Rules |
154 |
|
|
2.21.3 Implementation in Ex-Post Nash Equilibrium |
154 |
|
|
2.21.4 Interdependent Values |
155 |
|
|
2.21.5 Implementation Theory |
156 |
|
|
2.21.6 Computational Issues in Mechanism Design |
157 |
|
|
2.22 To Probe Further |
158 |
|
|
References |
158 |
|
|
Mechanism Design for Sponsored Search Auctions |
161 |
|
|
3.1 Internet Advertising |
161 |
|
|
3.1.1 Internet Advertising Formats |
162 |
|
|
3.1.2 Pricing Models for Internet Advertising |
163 |
|
|
3.1.3 An Analysis of Internet Advertising |
164 |
|
|
3.2 Sponsored Search Auction |
166 |
|
|
3.3 Sponsored Search Auction as a Mechanism Design Problem |
167 |
|
|
3.3.1 Outcome Set X |
169 |
|
|
3.3.2 Utility Function of Advertisers ui(·) |
169 |
|
|
3.3.3 Social Choice Function f (·) (Allocation and Payment Rules) |
169 |
|
|
3.3.4 Linear Environment |
169 |
|
|
3.4 Generalized First Price (GFP) Mechanism |
170 |
|
|
3.4.1 Allocation Rule |
170 |
|
|
3.4.2 Payment Rule |
171 |
|
|
3.5 Generalized Second Price (GSP) Mechanism |
171 |
|
|
3.5.1 Allocation Rule |
172 |
|
|
3.5.2 Relationship between Click Probability and CTR |
172 |
|
|
3.5.3 Relationship Among Different Allocation Rules |
174 |
|
|
3.5.4 Payment Rule |
175 |
|
|
3.6 Vickrey-Clarke-Groves (VCG) Mechanism |
176 |
|
|
3.6.1 Allocation Rule |
176 |
|
|
3.6.2 Payment Rule |
177 |
|
|
3.7 Optimal (OPT) Mechanism |
178 |
|
|
3.7.1 Allocation Rule |
179 |
|
|
3.7.2 Payment Rule |
182 |
|
|
3.7.3 OPT Mechanism and Symmetric Advertisers |
184 |
|
|
3.8 Comparison of GSP, VCG, and OPT Mechanisms |
186 |
|
|
3.8.1 Incentive Compatibility |
186 |
|
|
3.8.2 Revenue Equivalence of Mechanisms |
192 |
|
|
3.8.3 Expected Revenue under GSP, VCG, and OPT |
197 |
|
|
3.8.4 Expected Revenue under the VCG Mechanism |
197 |
|
|
3.8.5 Expected Revenue under the OPT Mechanism |
199 |
|
|
3.8.6 Expected Revenue under the GSP Mechanism |
200 |
|
|
3.9 Individual Rationality |
201 |
|
|
3.10 Computational Complexity |
202 |
|
|
3.11 Summary and Future Work |
204 |
|
|
3.12 Related Literature |
205 |
|
|
References |
209 |
|
|
Mechanism Design for Resource Procurement in Grid Computing |
212 |
|
|
4.1 Grid Computing |
212 |
|
|
4.1.1 Resource Procurement Problem in Grid Computing |
213 |
|
|
4.1.2 Incentive Compatible Resource Procurement Mechanisms |
214 |
|
|
4.1.3 Outline of the Chapter |
215 |
|
|
4.2 The Model |
216 |
|
|
4.3 The G-DSIC Mechanism |
219 |
|
|
4.3.1 An Illustrative Example |
220 |
|
|
4.3.2 The G-DSIC Mechanism: Allocation and Payment Rules |
220 |
|
|
4.3.3 Properties of the G-DSIC Mechanism |
221 |
|
|
4.3.4 The G-DSIC Algorithm |
223 |
|
|
4.3.5 Limitations of G-DSIC |
223 |
|
|
4.4 The G-BIC Mechanism |
224 |
|
|
4.4.1 The G-BIC Mechanism: Allocation and Payment Rules |
224 |
|
|
4.4.2 Properties of the G-BIC Mechanism |
225 |
|
|
4.4.3 The G-BIC Algorithm |
226 |
|
|
4.5 G-OPT: An Optimal Auction Mechanism |
227 |
|
|
4.5.1 Preliminaries |
227 |
|
|
4.5.2 Designing the G-OPT Mechanism |
230 |
|
|
4.5.3 The G-OPT Mechanism: Allocation and Payment Rules |
233 |
|
|
4.5.4 The G-OPT Algorithm |
234 |
|
|
4.5.5 Properties of the G-OPT Mechanism |
235 |
|
|
4.6 Current Art and Future Perspective |
236 |
|
|
4.6.1 Current Art: The Field is Young but Rich |
236 |
|
|
4.6.2 Avenues for Further Exploration |
237 |
|
|
References |
238 |
|
|
Incentive Compatible Broadcast Protocols for Ad hoc Networks |
240 |
|
|
5.1 Introduction to Ad HocWireless Networks |
240 |
|
|
5.2 Ad Hoc Networks with Selfish Nodes |
241 |
|
|
5.2.1 Modeling Ad Hoc Wireless Networks as Games |
242 |
|
|
5.2.2 The Incentive Compatible Broadcast (ICB) Problem |
244 |
|
|
5.2.3 Modeling the ICB Problem |
244 |
|
|
5.3 RelevantWork on Incentive Compatible Protocols |
246 |
|
|
5.3.1 Reputation-Based Solution Methods |
246 |
|
|
5.3.2 Non-Cooperative Game Theoretic Solution Methods |
246 |
|
|
5.3.3 Mechanism Design Based Solution Methods |
247 |
|
|
5.4 A Dominant Strategy Incentive Compatible Broadcast Protocol |
249 |
|
|
5.4.1 Construction of a Broadcast Tree |
249 |
|
|
5.4.2 DSIC-B: The Idea |
250 |
|
|
5.4.3 DSIC-B: Payment Rule |
252 |
|
|
5.4.4 Properties of DSIC-B Mechanism |
253 |
|
|
5.4.5 DISC-B: Protocol Implementation |
254 |
|
|
5.4.6 DSIC-B: Performance Evaluation |
256 |
|
|
5.4.7 Groves Mechanism Based Broadcast Protocol |
259 |
|
|
5.5 A Bayesian Incentive Compatible Broadcast (BIC-B) Protocol |
260 |
|
|
5.5.1 The BIC-B Protocol |
261 |
|
|
5.5.2 BIC-B: An Example |
262 |
|
|
5.5.3 BIC-B: Some Properties |
263 |
|
|
5.5.4 BIC-B Protocol: An Implementation |
267 |
|
|
5.5.5 BIC-B Protocol: Performance Evaluation |
268 |
|
|
5.6 DSIC-B Protocol Versus BIC-B Protocol: A Discussion |
270 |
|
|
5.7 Conclusions and Future Work |
271 |
|
|
References |
272 |
|
|
To Probe Further |
275 |
|
|
6.1 Topics in Mechanism Design |
275 |
|
|
6.1.1 Combinatorial Auctions |
275 |
|
|
6.1.2 Optimal Mechanisms |
276 |
|
|
6.1.3 Efficient Auctions |
276 |
|
|
6.1.4 Cost Sharing Mechanisms |
277 |
|
|
6.1.5 Iterative Mechanisms |
277 |
|
|
6.1.6 Dynamic Mechanisms |
277 |
|
|
6.1.7 Stochastic Mechanisms |
279 |
|
|
6.1.8 Computationally Efficient Approximate Mechanisms |
279 |
|
|
6.1.9 Mechanisms without Money |
279 |
|
|
6.2 Key Application Areas |
280 |
|
|
6.2.1 Procurement Auctions |
280 |
|
|
6.2.2 Spectrum Auctions |
280 |
|
|
6.2.3 Supply Chain Formation |
281 |
|
|
6.2.4 Communication Networks |
281 |
|
|
6.2.5 Peer-to-Peer Networks |
281 |
|
|
6.2.6 Prediction Markets |
282 |
|
|
6.2.7 Social Networks |
282 |
|
|
6.3 In Conclusion |
282 |
|
|
References |
283 |
|
|
Index |
285 |
|