INSEAD Library

Includes bibliographical references and index

Digitized

Networks, Crowds, and Markets
Reasoning about a
Highly Connected World
Contents
Preface page xi
1 Overview 1
1.1 Aspects of Networks 2
1.2 Central Themes and Topics 7
Part I Graph Theory and Social Networks
2 Graphs 21
2.1 Basic Definitions 21
2.2 Paths and Connectivity 23
2.3 Distance and Breadth-First Search 29
2.4 Network Data Sets: An Overview 35
2.5 Exercises 39
3 Strong and Weak Ties 43
3.1 Triadic Closure 44
3.2 The Strength of Weak Ties 46
3.3 Tie Strength and Network Structure in Large-Scale Data 51
3.4 Tie Strength, Social Media, and Passive Engagement 54
3.5 Closure, Structural Holes, and Social Capital 58
3.6 Advanced Material: Betweenness Measures and Graph Partitioning 62
3.7 Exercises 74
4 Networks in Their Surrounding Contexts 77
4.1 Homophily 77
4.2 Mechanisms Underlying Homophily: Selection and Social Influence 81
4.3 Affiliation 83
4.4 Tracking Link Formation in Online Data 88
4.5 A Spatial Model of Segregation 96
4.6 Exercises 103
5 Positive and Negative Relationships 107
5.1 Structural Balance 107
5.2 Characterizing the Structure of Balanced Networks 110
5.3 Applications of Structural Balance 113
5.4 A Weaker Form of Structural Balance 115
5.5 Advanced Material: Generalizing the Definition of Structural Balance 118
5.6 Exercises 132
Part II Game Theory
6 Games 139
6.1 What Is a Game? 140
6.2 Reasoning about Behavior in a Game 142
6.3 Best Responses and Dominant Strategies 146
6.4 Nash Equilibrium 149
6.5 Multiple Equilibria: Coordination Games 151
6.6 Multiple Equilibria: The Hawk-Dove Game 154
6.7 Mixed Strategies 156
6.8 Mixed Strategies: Examples and Empirical Analysis 161
6.9 Pareto Optimality and Social Optimality 165
6.10 Advanced Material: Dominated Strategies and Dynamic Games 167
6.11 Exercises 179
7 Evolutionary Game Theory 189
7.1 Fitness as a Result of Interaction 190
7.2 Evolutionarily Stable Strategies 191
7.3 A General Description of Evolutionarily Stable Strategies 196
7.4 Relationship between Evolutionary and Nash Equilibria 197
7.5 Evolutionarily Stable Mixed Strategies 199
7.6 Exercises 204
8 Modeling Network Traffic Using Game Theory 207
8.1 Traffic at Equilibrium 207
8.2 Braess's Paradox 209
8.3 Advanced Material: The Social Cost of Traffic at Equilibrium 211
8.4 Exercises 219
9 Auctions 225
9.1 Types of Auctions 225
9.2 When Are Auctions Appropriate? 226
9.3 Relationships between Different Auction Formats 228
9.4 Second-Price Auctions 229
9.5 First-Price Auctions and Other Formats 232
9.6 Common Values and the Winner's Curse 233
9.7 Advanced Material: Bidding Strategies in First-Price and All-Pay
Auctions 234
9.8 Exercises 242
Part III Markets and Strategic Interaction in Networks
10 Matching Markets 249
10.1 Bipartite Graphs and Perfect Matchings 249
10.2 Valuations and Optimal Assignments 253
10.3 Prices and the Market-Clearing Property 255
10.4 Constructing a Set of Market-Clearing Prices 258
10.5 How Does This Relate to Single-Item Auctions? 261
10.6 Advanced Material: A Proof of the Matching Theorem 262
10.7 Exercises 270
11 Network Models of Markets with Intermediaries 277
11.1 Price Setting in Markets 277
11.2 A Model of Trade on Networks 280
11.3 Equilibria in Trading Networks 286
11.4 Further Equilibrium Phenomena: Auctions and Ripple Effects 290
11.5 Social Welfare in Trading Networks 294
11.6 Trader Profits 295
11.7 Reflections on Trade with Intermediaries 297
11.8 Exercises 297
12 Bargaining and Power in Networks 301
12.1 Power in Social Networks 301
12.2 Experimental Studies of Power and Exchange 304
12.3 Results of Network Exchange Experiments 305
12.4 A Connection to Buyer-Seller Networks 309
12.5 Modeling Two-Person Interaction: The Nash Bargaining Solution 310
12.6 Modeling Two-Person Interaction: The Ultimatum Game 312
12.7 Modeling Network Exchange: Stable Outcomes 314
12.8 Modeling Network Exchange: Balanced Outcomes 317
12.9 Advanced Material: A Game-Theoretic Approach to Bargaining 320
12.10 Exercises 327
Part IV Information Networks and the World Wide Web
13 The Structure of the Web 333
13.1 The World Wide Web 333
13.2 Information Networks, Hypertext, and Associative Memory 335
13.3 The Web as a Directed Graph 340
13.4 The Bow-Tie Structure of the Web 344
13.5 The Emergence of Web 2.0 347
13.6 Exercises 349
14 Link Analysis and Web Search 351
14.1 Searching the Web: The Problem of Ranking 351
14.2 Link Analysis Using Hubs and Authorities 353
14.3 PageRank 358
14.4 Applying Link Analysis in Modem Web Search 363
14.5 Applications beyond the Web 366
14.6 Advanced Material: Spectral Analysis, Random Walks, and Web
Search 368
14.7 Exercises 378
15 Sponsored Search Markets 385
15.1 Advertising Tied to Search Behavior 385
15.2 Advertising as a Matching Market 388
15.3 Encouraging Truthful Bidding in Matching Markets: The VCG
Principle 391 15.4 Analyzing the VCG Mechanism: Truth-Telling as a Dominant
Strategy 395
15.5 The Generalized Second-Price Auction 398
15.6 Equilibria of the Generalized Second-Price Auction 401
15.7 Ad Quality 404
15.8 Complex Queries and Interactions among Keywords 406
15.9 Advanced Material: VCG Prices and the Market-Clearing Property 407
15.10 Exercises 420
Part V Network Dynamics: Population Models
16 Information Cascades 425
16.1 Following the Crowd 425
16.2 A Simple Herding Experiment 427
16.3 Bayes' Rule: A Model of Decision Making under Uncertainty 430
16.4 Bayes' Rule in the Herding Experiment 434
16.5 A Simple, General Cascade Model 436
16.6 Sequential Decision Making and Cascades 440
16.7 Lessons from Cascades 442
16.8 Exercises 444
17 Network Effects 449
17.1 The Economy without Network Effects 450
17.2 The Economy with Network Effects 453
17.3 Stability, Instability, and Tipping Points 456
17.4 A Dynamic View of the Market 457
17.5 Industries with Network Goods 462
17.6 Mixing Individual Effects with Population-Level Effects 465
17.7 Advanced Material: Negative Externalities and the El Farol Bar
Problem 470
17.8 Exercises 476
18 Power Laws and Rich-Get-Richer Phenomena 479
18.1 Popularity as a Network Phenomenon 479
18.2 Power Laws 481
18.3 Rich-Get-Richer Models 482
18.4 The Unpredictability of Rich-Get-Richer Effects 484
18.5 The Long Tail 486
18.6 The Effect of Search Tools and Recommendation Systems 489
18.7 Advanced Material: Analysis of Rich-Get-Richer Processes 490
18.8 Exercises 493
Part VI Network Dynamics: Structural Models
19 Cascading Behavior in Networks 497
19.1 Diffusion in Networks 497
19.2 Modeling Diffusion through a Network 499
19.3 Cascades and Clusters 506
19.4 Diffusion, Thresholds, and the Role of Weak Ties 509
19.5 Extensions of the Basic Cascade Model 512
19.6 Knowledge, Thresholds, and Collective Action 514
19.7 Advanced Material: The Cascade Capacity 517
19.8 Exercises 532
20 The Small-World Phenomenon 537
20.1 Six Degrees of Separation 537
20.2 Structure and Randomness 538
20.3 Decentralized Search 541
20.4 Modeling the Process of Decentralized Search 543
20.5 Empirical Analysis and Generalized Models 546
20.6 Core-Periphery Structures and Difficulties in Decentralized Search 552
20.7 Advanced Material: Analysis of Decentralized Search 554
20.8 Exercises 564
21 Epidemics 567
21.1 Diseases and the Networks That Transmit Them 567
21.2 Branching Processes 569
21.3 The SIR Epidemic Model 572
21.4 The SIS Epidemic Model 576
21.5 Synchronization 578
21.6 Transient Contacts and the Dangers of Concurrency 582
21.7 Genealogy, Genetic Inheritance, and Mitochondrial Eve 585
21.8 Advanced Material: Analysis of Branching and Coalescent Processes 590
21.9 Exercises 602
Part VII Institutions and Aggregate Behavior
22 Markets and Information 607
22.1 Markets with Exogenous Events 608
22.2 Horse Races, Betting, and Beliefs 609
22.3 Aggregate Beliefs and the "Wisdom of Crowds" 615
22.4 Prediction Markets and Stock Markets 618
22.5 Markets with Endogenous Events 622
22.6 The Market for Lemons 623
22.7 Asymmetric Information in Other Markets 627
22.8 Signaling Quality 631
22.9 Quality Uncertainty Online: Reputation Systems and Other
Mechanisms 632
22.10 Advanced Material: Wealth Dynamics in Markets 635
22.11 Exercises 641
23 Voting 645
23.1 Voting for Group Decision Making 645
23.2 Individual Preferences 646
23.3 Voting Systems: Majority Rule 649
23.4 Voting Systems: Positional Voting 654
23.5 Arrow's Impossibility Theorem 657
23.6 Single-Peaked Preferences and the Median Voter Theorem 658
23.7 Voting as a Form of Information Aggregation 663
23.8 Insincere Voting for Information Aggregation 665
23.9 Jury Decisions and the Unanimity Rule 668
23.10 Sequential Voting and the Relation to Information Cascades 672
23.11 Advanced Material: A Proof of Arrow's Impossibility Theorem 673
23.12 Exercises 678
24 Property Rights 681
24.1 Externalities and the Coase Theorem 681
24.2 The Tragedy of the Commons 685
24.3 Intellectual Property 688
24.4 Exercises 691
Bibliography 693
Index 711