Algorithmic game theory

ToC\r......Page 5
Foreword......Page 13
Preface......Page 17
Contributors......Page 19
I Computing in Games......Page 22
1.1 Games, Old and New......Page 24
1.2 Games, Strategies, Costs, and Payoffs......Page 30
1.3 Basic Solution Concepts......Page 31
1.4 Finding Equilibria and Learning in Games......Page 37
1.5 Refinement of Nash: Games with Turns and Subgame Perfect Equilibrium......Page 39
1.7 Cooperative Games......Page 41
1.8 Markets and Their Algorithmic Issues......Page 43
Exercises......Page 47
2.1 Introduction......Page 50
2.2 Is the Nash Equilibrium Problem NP-Complete......Page 52
2.3 The Lemke-Howson Algorithm......Page 54
2.4 The Class PPAD......Page 57
2.5 Succinct Representations of Games......Page 60
2.6 The Reduction......Page 62
2.7 Correlated Equilibria......Page 66
2.8 Concluding Remarks......Page 70
Bibliography......Page 71
3.1 Introduction......Page 74
3.2 Bimatrix Games and the Best Response Condition......Page 75
3.3 Equilibria via Labeled Polytopes......Page 78
3.4 The Lemke-Howson Algorithm......Page 82
3.5 Integer Pivoting......Page 84
3.6 Degenerate Games......Page 86
3.7 Extensive Games and Their Strategic Form......Page 87
3.8 Subgame Perfect Equilibria......Page 89
3.9 Reduced Strategic Form......Page 90
3.10 The Sequence Form......Page 91
3.11 Computing Equilibria with the Sequence Form......Page 94
3.13 Discussion and Open Problems......Page 96
Bibliography......Page 97
Exercises......Page 98
4.1 Introduction......Page 100
4.2 Model and Preliminaries......Page 102
4.3 External Regret Minimization......Page 103
4.4 Regret Minimization and Game Theory......Page 109
4.5 Generic Reduction from External to Swap Regret......Page 113
4.6 The Partial Information Model......Page 115
4.7 On Convergence of Regret-Minimizing Strategies to Nash Equilibrium in Routing Games......Page 117
Bibliography......Page 120
Exercises......Page 122
5.1 Introduction......Page 124
5.2 Fisher-s Linear Case and the Eisenberg-Gale Convex Program......Page 126
5.3 Checking If Given Prices Are Equilibrium Prices......Page 129
5.5 The Primal-Dual Schema in the Enhanced Setting......Page 130
5.7 Balanced Flows......Page 132
5.8 The Main Algorithm......Page 136
5.9 Finding Tight Sets......Page 138
5.10 Running Time of the Algorithm......Page 139
5.11 The Linear Case of the Arrow-Debreu Model......Page 142
5.12 An Auction-Based Algorithm......Page 143
5.13 Resource Allocation Markets......Page 145
5.14 Algorithm for Single-Source Multiple-Sink Markets......Page 147
5.15 Discussion and Open Problems......Page 152
Bibliography......Page 153
Exercises......Page 154
6.1 Introduction......Page 156
6.2 Fisher Model with Homogeneous Consumers......Page 162
6.3 Exchange Economies Satisfying WGS......Page 163
6.4 Specific Utility Functions......Page 169
6.5 Limitations......Page 171
6.6 Models with Production......Page 173
6.7 Bibliographic Notes......Page 176
Bibliography......Page 177
Exercises......Page 179
7.1 Introduction......Page 180
7.2 Preliminaries......Page 182
7.3 Computing Nash Equilibria in Tree Graphical Games......Page 185
7.4 Graphical Games and Correlated Equilibria......Page 190
7.5 Graphical Exchange Economies......Page 197
7.7 Bibliographic Notes......Page 198
Bibliography......Page 200
8.1 Cryptographic Notions and Settings......Page 202
8.2 Game Theory Notions and Settings......Page 208
8.3 Contrasting MPC and Games......Page 210
8.4 Cryptographic Influences on Game Theory......Page 212
8.5 Game Theoretic Influences on Cryptography......Page 218
8.6 Conclusions......Page 223
8.7 Notes......Page 224
Bibliography......Page 225
II Algorithmic Mechanism Design......Page 228
9.1 Introduction......Page 230
9.2 Social Choice......Page 232
9.3 Mechanisms with Money......Page 237
9.4 Implementation in Dominant Strategies......Page 243
9.5 Characterizations of Incentive Compatible Mechanisms......Page 246
9.6 Bayesian-Nash Implementation......Page 254
9.7 Further Models......Page 259
9.8 Notes......Page 260
Acknowledgments......Page 261
Bibliography......Page 262
10.1 Introduction......Page 264
10.2 Single-Peaked Preferences over Policies......Page 265
10.3 House Allocation Problem......Page 274
10.4 Stable Matchings......Page 276
10.5 Future Directions......Page 283
10.6 Notes and References......Page 284
Exercises......Page 285
11.1 Introduction......Page 288
11.2 The Single-Minded Case......Page 291
11.3 Walrasian Equilibrium and the LP Relaxation......Page 296
11.4 Bidding Languages......Page 300
11.5 Iterative Auctions: The Query Model......Page 304
11.6 Communication Complexity......Page 308
11.7 Ascending Auctions......Page 310
11.8 Bibliographic Notes......Page 316
Bibliography......Page 317
Exercises......Page 319
12.1 Introduction......Page 322
12.2 Single-Dimensional Domains: Job Scheduling......Page 324
12.3 Multidimensional Domains: Combinatorial Auctions......Page 331
12.4 Impossibilities of Dominant Strategy Implementability......Page 338
12.5 Alternative Solution Concepts......Page 342
Bibliography......Page 348
Exercises......Page 349
13.1 Introduction......Page 352
13.2 Bayesian Optimal Mechanism Design......Page 356
13.3 Prior-Free Approximations to the Optimal Mechanism......Page 360
13.4 Prior-Free Optimal Mechanism Design......Page 365
13.5 Frugality......Page 371
13.6 Conclusions and Other Research Directions......Page 375
13.7 Notes......Page 378
Bibliography......Page 379
Exercises......Page 381
14.1 Introduction......Page 384
14.2 Two Examples of DAMD......Page 387
14.3 Interdomain Routing......Page 391
14.4 Conclusion and Open Problems......Page 400
14.5 Notes......Page 401
Bibliography......Page 402
Exercises......Page 404
15.1 Cooperative Games and Cost Sharing......Page 406
15.2 Core of Cost-Sharing Games......Page 408
15.3 Group-Strategyproof Mechanisms and Cross-Monotonic Cost-Sharing Schemes......Page 412
15.4 Cost Sharing via the Primal-Dual Schema......Page 415
15.5 Limitations of Cross-Monotonic Cost-Sharing Schemes......Page 421
15.6 The Shapley Value and the Nash Bargaining Solution......Page 423
15.7 Conclusion......Page 426
15.8 Notes......Page 427
Bibliography......Page 429
Exercises......Page 431
16.1 Introduction......Page 432
16.2 Dynamic Environments and Online MD......Page 434
16.3 Single-Valued Online Domains......Page 438
16.4 Bayesian Implementation in Online Domains......Page 452
16.5 Conclusions......Page 456
16.6 Notes......Page 457
Bibliography......Page 458
Exercises......Page 460
III Quantifying the Inefficiency of Equilibria......Page 462
17.1 Introduction......Page 464
17.2 Fundamental Network Examples......Page 467
17.3 Inefficiency of Equilibria as a Design Metric......Page 475
17.4 Notes......Page 477
Bibliography......Page 478
Exercises......Page 480
18.1 Introduction......Page 482
18.2 Models and Examples......Page 483
18.3 Existence, Uniqueness, and Potential Functions......Page 489
18.4 The Price of Anarchy of Selfish Routing......Page 493
18.5 Reducing the Price of Anarchy......Page 499
18.6 Notes......Page 501
Bibliography......Page 504
Exercises......Page 505
19.1 Introduction......Page 508
19.2 The Local Connection Game......Page 510
19.3 Potential Games and a Global Connection Game......Page 515
19.4 Facility Location......Page 523
19.5 Notes......Page 527
Bibliography......Page 532
Exercises......Page 534
20.1 Introduction......Page 538
20.2 Pure Equilibria for Identical Machines......Page 543
20.3 Pure Equilibria for Uniformly Related Machines......Page 545
20.4 Mixed Equilibria on Identical Machines......Page 550
20.5 Mixed Equilibria on Uniformly Related Machines......Page 554
20.6 Summary and Discussion......Page 558
20.7 Bibliographic Notes......Page 559
Bibliography......Page 561
Exercises......Page 563
21.1 Introduction......Page 564
21.2 The Proportional Allocation Mechanism......Page 565
21.3 A Characterization Theorem......Page 572
21.4 The Vickrey-Clarke-Groves Approach......Page 580
21.5 Chapter Summary and Further Directions......Page 585
21.6 Notes......Page 586
Bibliography......Page 587
Exercises......Page 588
IV Additional Topics......Page 590
22 Incentives and Pricing in Communications Networks......Page 592
22.1 Large Networks - Competitive Models......Page 593
22.2 Pricing and Resource Allocation - Game Theoretic Models......Page 599
22.3 Alternative Pricing and Incentive Approaches......Page 608
Bibliography......Page 611
23.1 Introduction......Page 614
23.2 The p2p File-Sharing Game......Page 615
23.3 Reputation......Page 617
23.4 A Barter-Based System: BitTorrent......Page 621
23.5 Currency......Page 622
23.6 Hidden Actions in p2p Systems......Page 623
23.8 Bibliographic Notes......Page 629
Bibliography......Page 630
Exercises......Page 631
24.1 Introduction......Page 634
24.2 A First Model: Networked Coordination Games......Page 635
24.3 More General Models of Social Contagion......Page 639
24.4 Finding Influential Sets of Nodes......Page 643
24.5 Empirical Studies of Cascades in Online Data......Page 648
24.6 Notes and Further Reading......Page 651
Bibliography......Page 652
Exercises......Page 653
25.1 Introduction......Page 654
25.2 Misaligned Incentives......Page 655
25.3 Informational Asymmetries......Page 657
25.4 The Economics of Censorship Resistance......Page 661
25.5 Complex Networks and Topology......Page 664
25.6 Conclusion......Page 667
25.7 Notes......Page 668
Bibliography......Page 669
26.1 Introduction: What Is a Prediction Market......Page 672
26.2 Background......Page 673
26.3 Combinatorial Prediction Markets......Page 678
26.4 Automated Market Makers......Page 683
26.5 Distributed Computation through Markets......Page 686
26.6 Open Questions......Page 691
26.7 Bibliographic Notes......Page 692
Bibliography......Page 693
Exercises......Page 695
27.1 Introduction: Why Are Reputation Systems Important......Page 698
27.2 The Effect of Reputations......Page 701
27.3 Whitewashing......Page 703
27.4 Eliciting Effort and Honest Feedback......Page 704
27.5 Reputations Based on Transitive Trust......Page 710
27.6 Conclusion and Extensions......Page 714
27.7 Bibliographic Notes......Page 715
Bibliography......Page 716
Exercises......Page 717
28.1 Introduction......Page 720
28.2 Existing Models and Mechanisms......Page 722
28.3 A Static Model......Page 723
28.4 Dynamic Aspects......Page 728
28.5 Open Questions......Page 732
28.6 Bibliographic Notes......Page 733
Bibliography......Page 734
Exercises......Page 736
29.1 Evolutionary Game Theory......Page 738
29.2 The Computational Complexity of Evolutionarily Stable Strategies......Page 741
29.3 Evolutionary Dynamics Applied to Selfish Routing......Page 744
29.4 Evolutionary Game Theory over Graphs......Page 749
29.6 Notes......Page 754
Bibliography......Page 755
Exercises......Page 756
Index......Page 758