Game Theoretic Problems in Network Economics and Mechanism Design Solutions (eBook)

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