Networks, Crowds, and Markets: Reasoning About a Highly Connected World (Draft 2010-06-10)

Half-title......Page 3
Title......Page 5
Copyright......Page 6
Contents......Page 7
Preface......Page 13
CHAPTER 1 Overview......Page 19
1.1 Aspects of Networks......Page 20
1.2 Central Themes and Topics......Page 25
2.1 Basic Definitions......Page 39
2.2 Paths and Connectivity......Page 41
2.3 Distance and Breadth-First Search......Page 47
2.4 Network Data Sets: An Overview......Page 53
2.5 Exercises......Page 57
CHAPTER 3 Strong and Weak Ties......Page 61
3.1 Triadic Closure......Page 62
3.2 The Strength of Weak Ties......Page 64
3.3 Tie Strength and Network Structure in Large-Scale Data......Page 69
3.4 Tie Strength, Social Media, and Passive Engagement......Page 72
3.5 Closure, Structural Holes, and Social Capital......Page 76
3.6 Advanced Material: Betweenness Measures and Graph Partitioning......Page 80
A. A Method for Graph Partitioning......Page 82
B. Computing Betweenness Values......Page 89
3.7 Exercises......Page 92
4.1 Homophily......Page 95
4.2 Mechanisms Underlying Homophily: Selection and Social Influence......Page 99
4.3 Affiliation......Page 101
4.4 Tracking Link Formation in Online Data......Page 106
4.5 A Spatial Model of Segregation......Page 114
4.6 Exercises......Page 121
5.1 Structural Balance......Page 125
5.2 Characterizing the Structure of Balanced Networks......Page 128
5.3 Applications of Structural Balance......Page 131
5.4 AWeaker Form of Structural Balance......Page 133
5.5 Advanced Material: Generalizing the Definition of Structural Balance......Page 136
A. Structural Balance in Arbitrary (Noncomplete) Networks......Page 137
B. Approximately Balanced Networks......Page 145
5.6 Exercises......Page 150
CHAPTER 6 Games......Page 157
6.1 What Is a Game?......Page 158
6.2 Reasoning about Behavior in a Game......Page 160
6.3 Best Responses and Dominant Strategies......Page 164
6.4 Nash Equilibrium......Page 167
6.5 Multiple Equilibria: Coordination Games......Page 169
6.6 Multiple Equilibria: The Hawk–Dove Game......Page 172
6.7 Mixed Strategies......Page 174
6.8 Mixed Strategies: Examples and Empirical Analysis......Page 179
6.9 Pareto Optimality and Social Optimality......Page 183
B. Dominated Strategies and Their Role in Strategic Reasoning......Page 185
C. Dynamic Games......Page 191
6.11 Exercises......Page 197
CHAPTER 7 Evolutionary Game Theory......Page 207
7.1 Fitness as a Result of Interaction......Page 208
7.2 Evolutionarily Stable Strategies......Page 209
7.3 A General Description of Evolutionarily Stable Strategies......Page 214
7.4 Relationship between Evolutionary and Nash Equilibria......Page 215
7.5 Evolutionarily Stable Mixed Strategies......Page 217
7.6 Exercises......Page 222
8.1 Traffic at Equilibrium......Page 225
8.2 Braess’s Paradox......Page 227
8.3 Advanced Material: The Social Cost of Traffic at Equilibrium......Page 229
A. How to Find a Traffic Pattern at Equilibrium......Page 230
B. Comparing Equilibrium Traffic to the Social Optimum......Page 235
8.4 Exercises......Page 237
9.1 Types of Auctions......Page 243
9.2 When Are Auctions Appropriate?......Page 244
9.3 Relationships between Different Auction Formats......Page 246
9.4 Second-Price Auctions......Page 247
9.5 First-Price Auctions and Other Formats......Page 250
9.6 Common Values and theWinner’s Curse......Page 251
A. Equilibrium Bidding in First-Price Auctions......Page 252
B. Seller Revenue......Page 256
C. Equilibrium Bidding in All-Pay Auctions......Page 259
9.8 Exercises......Page 260
10.1 Bipartite Graphs and Perfect Matchings......Page 267
10.2 Valuations and Optimal Assignments......Page 271
10.3 Prices and the Market-Clearing Property......Page 273
10.4 Constructing a Set of Market-Clearing Prices......Page 276
10.5 How Does This Relate to Single-Item Auctions?......Page 279
10.6 Advanced Material: A Proof of the Matching Theorem......Page 280
10.7 Exercises......Page 288
11.1 Price Setting in Markets......Page 295
11.2 A Model of Trade on Networks......Page 298
11.3 Equilibria in Trading Networks......Page 304
11.4 Further Equilibrium Phenomena: Auctions and Ripple Effects......Page 308
11.5 SocialWelfare in Trading Networks......Page 312
11.6 Trader Profits......Page 313
11.8 Exercises......Page 315
12.1 Power in Social Networks......Page 319
12.2 Experimental Studies of Power and Exchange......Page 322
12.3 Results of Network Exchange Experiments......Page 323
12.4 A Connection to Buyer–Seller Networks......Page 327
12.5 Modeling Two-Person Interaction: The Nash Bargaining Solution......Page 328
12.6 Modeling Two-Person Interaction: The Ultimatum Game......Page 330
12.7 Modeling Network Exchange: Stable Outcomes......Page 332
12.8 Modeling Network Exchange: Balanced Outcomes......Page 335
12.9 Advanced Material: A Game-Theoretic Approach to Bargaining......Page 338
12.10 Exercises......Page 345
13.1 The World Wide Web......Page 351
13.2 Information Networks, Hypertext, and Associative Memory......Page 353
13.3 The Web as a Directed Graph......Page 358
13.4 The Bow-Tie Structure of the Web......Page 362
13.5 The Emergence of Web 2.0......Page 365
13.6 Exercises......Page 367
14.1 Searching the Web: The Problem of Ranking......Page 369
14.2 Link Analysis Using Hubs and Authorities......Page 371
14.3 PageRank......Page 376
14.4 Applying Link Analysis in ModernWeb Search......Page 381
14.5 Applications beyond theWeb......Page 384
A. Spectral Analysis of Hubs and Authorities......Page 386
B. Spectral Analysis of PageRank......Page 392
C. Formulation of PageRank Using RandomWalks......Page 394
14.7 Exercises......Page 396
15.1 Advertising Tied to Search Behavior......Page 403
15.2 Advertising as a Matching Market......Page 406
15.3 Encouraging Truthful Bidding in Matching Markets: The VCG Principle......Page 409
15.4 Analyzing the VCG Mechanism: Truth-Telling as a Dominant Strategy......Page 413
15.5 The Generalized Second-Price Auction......Page 416
15.6 Equilibria of the Generalized Second-Price Auction......Page 419
15.7 Ad Quality......Page 422
15.8 Complex Queries and Interactions among Keywords......Page 424
15.9 Advanced Material: VCG Prices and the Market-Clearing Property......Page 425
A. High-Level Overview of the Proof......Page 427
B. Details of the Proof......Page 433
15.10 Exercises......Page 438
16.1 Following the Crowd......Page 443
16.2 A Simple Herding Experiment......Page 445
16.3 Bayes’s Rule: A Model of Decision Making under Uncertainty......Page 448
16.4 Bayes’s Rule in the Herding Experiment......Page 452
16.5 A Simple, General Cascade Model......Page 454
16.6 Sequential Decision Making and Cascades......Page 458
16.7 Lessons from Cascades......Page 460
16.8 Exercises......Page 462
CHAPTER 17 Network Effects......Page 467
17.1 The Economy without Network Effects......Page 468
17.2 The Economy with Network Effects......Page 471
17.3 Stability, Instability, and Tipping Points......Page 474
17.4 A Dynamic View of the Market......Page 475
17.5 Industries with Network Goods......Page 480
17.6 Mixing Individual Effects with Population-Level Effects......Page 483
17.7 Advanced Material: Negative Externalities and the El Farol Bar Problem......Page 488
17.8 Exercises......Page 494
18.1 Popularity as a Network Phenomenon......Page 497
18.2 Power Laws......Page 499
18.3 Rich-Get-Richer Models......Page 500
18.4 The Unpredictability of Rich-Get-Richer Effects......Page 502
18.5 The Long Tail......Page 504
18.6 The Effect of Search Tools and Recommendation Systems......Page 507
18.7 Advanced Material: Analysis of Rich-Get-Richer Processes......Page 508
18.8 Exercises......Page 511
19.1 Diffusion in Networks......Page 515
19.2 Modeling Diffusion through a Network......Page 517
19.3 Cascades and Clusters......Page 524
19.4 Diffusion, Thresholds, and the Role of Weak Ties......Page 527
19.5 Extensions of the Basic Cascade Model......Page 530
19.6 Knowledge, Thresholds, and Collective Action......Page 532
19.7 Advanced Material: The Cascade Capacity......Page 535
A. Cascades on Infinite Networks......Page 536
B. How Large Can the Cascade Capacity Be?......Page 538
C. Compatibility and Its Role in Cascades......Page 540
19.8 Exercises......Page 550
20.1 Six Degrees of Separation......Page 555
20.2 Structure and Randomness......Page 556
20.3 Decentralized Search......Page 559
20.4 Modeling the Process of Decentralized Search......Page 561
20.5 Empirical Analysis and Generalized Models......Page 564
20.6 Core–Periphery Structures and Difficulties in Decentralized Search......Page 570
A. The Optimal Exponent in One Dimension......Page 572
B. Higher Dimensions and Other Exponents......Page 579
20.8 Exercises......Page 582
21.1 Diseases and the Networks That Transmit Them......Page 585
21.2 Branching Processes......Page 587
21.3 The SIR Epidemic Model......Page 590
21.4 The SIS Epidemic Model......Page 594
21.5 Synchronization......Page 596
21.6 Transient Contacts and the Dangers of Concurrency......Page 600
21.7 Genealogy, Genetic Inheritance, and Mitochondrial Eve......Page 603
21.8 Advanced Material: Analysis of Branching and Coalescent Processes......Page 608
A. Analysis of Branching Processes......Page 609
B. Analysis of Coalescent Processes......Page 614
21.9 Exercises......Page 620
CHAPTER 22 Markets and Information......Page 625
22.1 Markets with Exogenous Events......Page 626
22.2 Horse Races, Betting, and Beliefs......Page 627
22.3 Aggregate Beliefs and the “Wisdom of Crowds”......Page 633
22.4 Prediction Markets and Stock Markets......Page 636
22.5 Markets with Endogenous Events......Page 640
22.6 The Market for Lemons......Page 641
22.7 Asymmetric Information in Other Markets......Page 645
22.8 Signaling Quality......Page 649
22.9 Quality Uncertainty Online: Reputation Systems and Other Mechanisms......Page 650
A. Bayesian Learning in a Market......Page 653
B. Wealth Dynamics......Page 657
22.11 Exercises......Page 659
23.1 Voting for Group Decision Making......Page 663
23.2 Individual Preferences......Page 664
23.3 Voting Systems: Majority Rule......Page 667
23.4 Voting Systems: Positional Voting......Page 672
23.5 Arrow’s Impossibility Theorem......Page 675
23.6 Single-Peaked Preferences and the Median Voter Theorem......Page 676
23.7 Voting as a Form of Information Aggregation......Page 681
23.8 Insincere Voting for Information Aggregation......Page 683
23.9 Jury Decisions and the Unanimity Rule......Page 686
23.10 Sequential Voting and the Relation to Information Cascades......Page 690
23.11 Advanced Material: A Proof of Arrow’s Impossibility Theorem......Page 691
23.12 Exercises......Page 696
24.1 Externalities and the Coase Theorem......Page 699
24.2 The Tragedy of the Commons......Page 703
24.3 Intellectual Property......Page 706
24.4 Exercises......Page 709
Bibliography......Page 711
Index......Page 729