Game Theoretic Problems in Network Economics and Mechanism Design Solutions Book

1 Introduction 1

1.1 Motivating Problems in Network Economics 1

1.1.1 Sponsored Web Search Auctions 1

1.1.2 Resource Allocation in Grid Computing 3

1.1.3 Protocol Design in Wireless Ad Hoc Networks 4

1.1.4 Supply Chain Network Formation 5

1.1.5 Nature of the Problems 6

1.2 Mechanism Design 7

1.2.1 Mechanisms: Some Simple Examples 8

1.2.2 Mechanism Design: A Brief History 8

1.3 Outline of the Monograph 9

References 12

2 Foundations of Mechanism Design 13

2.1 Strategic Form Games 13

2.1.1 Key Notions 14

2.1.2 Examples of Strategic Form Games 17

2.2 Dominant Strategy Equilibria 23

2.2.1 Strong Dominance 23

2.2.2 Weak Dominance 24

2.3 Pure Strategy Nash Equilibrium 26

2.3.1 Pure Strategy Nash Equilibria: Examples 28

2.3.2 Interpretations of Nash Equilibrium 32

2.3.3 Existence of a Pure Strategy Nash Equilibrium 33

2.3.4 Existence of Multiple Nash Equilibria 33

2.4 Mixed Strategy Nash Equilibrium 34

2.4.1 Randomized Strategies or Mixed Strategies 34

2.4.2 Mixed Strategy Nash Equilibrium 36

2.4.3 Existence of Mixed Strategy Nash Equilibrium 39

2.4.4 Computation of Nash Equilibria 39

2.5 Bayesian Games 40

2.5.1 Examples of Bayesian Games 42

2.5.2 Type Agent Representation and the Selten Game 44

2.5.3 Equilibria in Bayesian Games 48

2.5.4 Dominant Strategy Equilibria 50

2.6 The Mechanism Design Environment 51

2.7 Examples of Social Choice Functions 55

2.8 Implementation of Social Choice Functions 62

2.8.1 Implementation Through Direct Mechanisms 62

2.8.2 Implementation Through Indirect Mechanisms 65

2.8.3 Bayesian Game Induced by a Mechanism 68

2.8.4 Implementation of a Social Choice Function by aMechanism 70

2.9 Incentive Compatibility and the Revelation Theorem 71

2.9.1 Incentive Compatibility (IC) 73

2.9.2 The Revelation Principle for Dominant Strategy Equilibrium 75

2.9.3 The Revelation Principle for Bayesian Nash Equilibrium 76

2.10 Properties of Social Choice Functions 78

2.10.1 Ex-Post Efficiency 79

2.10.2 Dictatorship in SCFs 79

2.10.3 Individual Rationality 80

2.10.4 Efficiency 81

2.11 The Gibbard-Satterthwaite Impossibility Theorem 82

2.11.1 The G-S Theorem 84

2.11.2 Implications of the G-S Theorem 87

2.12 Arrow's Impossibility Theorem 87

2.13 The Quasilinear Environment 93

2.14 Groves Mechanisms 97

2.14.1 VCG Mechanisms 98

2.14.2 The Groves' Theorem 99

2.14.3 Groves Mechanisms and Budget Balance 101

2.15 Clarke (Pivotal) Mechanisms 102

2.15.1 Clarke Mechanisms and Weak Budget Balance 103

2.15.2 Clarke Mechanisms and Individual Rationality 105

2.16 Examples of VCG Mechanisms 106

2.17 Bayesian Implementation: The dAGVA Mechanism 113

2.17.1 The dAGVA Mechanism 114

2.17.2 The dAGVA Mechanism and Budget Balance 115

2.17.3 The Myerson-Satterthwaite Theorem 117

2.17.4 Mechanism Design Space in Quasilinear Environment 118

2.18 Bayesian Incentive Compatibility in Linear Environment 119

2.19 Revenue Equivalence Theorem 121

2.19.1 Revenue Equivalence of Two Auctions 122

2.19.2 Revenue Equivalence of Four Classical Auctions 124

2.20 Myerson Optimal Auction 129

2.20.1 Optimal Mechanism Design Problem 130

2.20.2 Myerson's Optimal Reverse Auction 131

2.21 Further Topics in Mechanism Design 136

2.21.1 Characterization of DSIC Mechanisms 136

2.21.2 Dominant Strategy Implementation of BIC Rules 137

2.21.3 Implementation in Ex-Post Nash Equilibrium 137

2.21.4 Interdependent Values 138

2.21.5 Implementation Theory 139

2.21.6 Computational Issues in Mechanism Design 140

2.22 To Probe Further 141

References 141

3 Mechanism Design for Sponsored Search Auctions 145

3.1 Internet Advertising 145

3.1.1 Internet Advertising Formats 146

3.1.2 Pricing Models for Internet Advertising 147

3.1.3 An Analysis of Internet Advertising 148

3.2 Sponsored Search Auction 150

3.3 Sponsored Search Auction as a Mechanism Design Problem 151

3.3.1 Outcome Set X 153

3.3.2 Utility Function of Advertisers ui(.) 153

3.3.3 Social Choice Function f(.) (Allocation and Payment Rules) 153

3.3.4 Linear Environment 153

3.4 Generalized First Price (GFP) Mechanism 154

3.4.1 Allocation Rule 154

3.4.2 Payment Rule 155

3.5 Generalized Second Price (GSP) Mechanism 155

3.5.1 Allocation Rule 156

3.5.2 Relationship between Click Probability and CTR 156

3.5.3 Relationship Among Different Allocation Rules 158

3.5.4 Payment Rule 159

3.6 Vickrey-Clarke-Groves(VCG) Mechanism 160

3.6.1 Allocation Rule 160

3.6.2 Payment Rule 161

3.7 Optimal (OPT) Mechanism 162

3.7.1 Allocation Rule 163

3.7.2 Payment Rule 166

3.7.3 OPT Mechanism and Symmetric Advertisers 168

3.8 Comparison of GSP, VCG, and OPT Mechanisms 170

3.8.1 Incentive Compatibility 170

3.8.2 Revenue Equivalence of Mechanisms 176

3.8.3 Expected Revenue under GSP, VCG, and OPT 181

3.8.4 Expected Revenue under the VCG Mechanism 181

3.8.5 Expected Revenue under the OPT Mechanism 183

3.8.6 Expected Revenue under the GSP Mechanism 184

3.9 Individual Rationality 185

3.10 Computational Complexity 186

3.11 Summary and Future Work 188

3.12 Related Literature 189

References 193

4 Mechanism Design for Resource Procurement in Grid Computing 197

4.1 Grid Computing 197

4.1.1 Resource Procurement Problem in Grid Computing 198

4.1.2 Incentive Compatible Resource Procurement Mechanisms 199

4.1.3 Outline of the Chapter 200

4.2 The Model 201

4.3 The G-DSIC Mechanism 204

4.3.1 An Illustrative Example 205

4.3.2 The G-DSIC Mechanism: Allocation and Payment Rules 205

4.3.3 Properties of the G-DSIC Mechanism 206

4.3.4 The G-DSIC Algorithm 208

4.3.5 Limitations of G-DSIC 208

4.4 The G-BIC Mechanism 209

4.4.1 The G-BIC Mechanism: Allocation and Payment Rules 209

4.4.2 Properties of the G-BIC Mechanism 210

4.4.3 The G-BIC Algorithm 211

4.5 G-OPT: An Optimal Auction Mechanism 212

4.5.1 Preliminaries 212

4.5.2 Designing the G-OPT Mechanism 215

4.5.3 The G-OPT Mechanism: Allocation and Payment Rules 218

4.5.4 The G-OPT Algorithm 219

4.5.5 Properties of the G-OPT Mechanism 220

4.6 Current Art and Future Perspective 221

4.6.1 Current Art: The Field is Young but Rich 221

4.6.2 Avenues for Further Exploration 222

References 223

5 Incentive Compatible Broadcast Protocols for Ad hoc Networks 225

5.1 Introduction to Ad Hoc Wireless Networks 225

5.2 Ad Hoc Networks with Selfish Nodes 226

5.2.1 Modeling Ad Hoc Wireless Networks as Games 227

5.2.2 The Incentive Compatible Broadcast (ICB) Problem 229

5.2.3 Modeling the ICB Problem 229

5.3 Relevant Work on Incentive Compatible Protocols 231

5.3.1 Reputation-Based Solution Methods 231

5.3.2 Non-Cooperative Game Theoretic Solution Methods 231

5.3.3 Mechanism Design Based Solution Methods 232

5.4 A Dominant Strategy Incentive Compatible Broadcast Protocol 234

5.4.1 Construction of a Broadcast Tree 234

5.4.2 DSIC-B: The Idea 235

5.4.3 DSIC-B: Payment Rule 237

5.4.4 Properties of DSIC-B Mechanism 238

5.4.5 DISC-B: Protocol Implementation 239

5.4.6 DSIC-B: Performance Evaluation 241

5.4.7 Groves Mechanism Based Broadcast Protocol 244

5.5 A Bayesian Incentive Compatible Broadcast (BIC-B) Protocol 245

5.5.1 The BIC-B Protocol 246

5.5.2 BIC-B: An Example 247

5.5.3 BIC-B: Some Properties 248

5.5.4 BIC-B Protocol: An Implementation 252

5.5.5 BIC-B Protocol: Performance Evaluation 253

5.6 DSIC-B Protocol Versus BIC-B Protocol: A Discussion 255

5.7 Conclusions and Future Work 256

References 257

6 To Probe Further 261

6.1 Topics in Mechanism Design 261

6.1.1 Combinatorial Auctions 261

6.1.2 Optimal Mechanisms 262

6.1.3 Efficient Auctions 262

6.1.4 Cost Sharing Mechanisms 263

6.1.5 Iterative Mechanisms 263

6.1.6 Dynamic Mechanisms 263

6.1.7 Stochastic Mechanisms 265

6.1.8 Computationally Efficient Approximate Mechanisms 265

6.1.9 Mechanisms without Money 265

6.2 Key Application Areas 266

6.2.1 Procurement Auctions 266

6.2.2 Spectrum Auctions 266

6.2.3 Supply Chain Formation 267

6.2.4 Communication Networks 267

6.2.5 Peer-to-Peer Networks 267

6.2.6 Prediction Markets 268

6.2.7 Social Networks 268

6.3 In Conclusion 268

References 269

Index 271