 CS19421: Networks, Crowds, and Markets
Instructors: Richard M. Karp and Christos H. Papadimitriou
Office Hours: To Be Announced
Units: 3
Time and Place: Tu,Th 11:0012:30, 320 Soda
Text: David Easley and Jon Kleinberg, "Networks, Crowds and Markets," ISBN 9780=521195331, Cambridge University Press (2010).
A complete prepublication draft of the text is available at http://www.cs.cornell.edu/home/kleinber/.
Course Overview:
We live in a connected world in which information spreads virtually
instantaneously, and the Internet and the Web support new economic mechanisms and organizational structures and the operation of vast social and financial networks. This course will draw upon a range of scientific perspectives in its approach to understanding the interplay of technology, economics and sociology in networked settings. We will study: the structure and dynamics of networks; the phenomenon of six degrees of separation; the diffusion of ideas, behaviors, epidemics and computer viruses; the mechanisms of Web search; game theory and its applications to market behavior, auctions and resource allocation; the wisdom of crowds; and models of group decision making.
Prerequisites: There are no formal prerequisites. The mathematical models used in the course should be accessible to all participants.
Assignments:A reading assignment from the text will accompany each lecture. Every two weeks each student will be expected to submit a onepage report describing a recent news report related to the course material. There will also be three or four problem sets.
Exams: There will be a final exam.
We will aim to cover the following chapters of the text:
 1. Overview
Part I Graph Theory and Social Networks (2 weeks)
 2. Graphs
 3. Strong and Weak Ties
 4. Networks in Their Surrounding Contexts
 5. Positive and Negative Relationships
Part II Game Theory (3 weeks)
 6. Games
 8. Modeling Network Traffic Using Game Theory
 9. Auctions
Part III Markets and Strategic Interaction in Networks (2 weeks)
 10. Matching Markets
 11. Network Models of Markets with Intermediaries
 12. Bargaining and Power in Networks
Part IV Information Networks and the World Wide Web (3 weeks)
 13. The Structure of the Web
 14. Link Analysis and Web Search
 15. Sponsored Search Markets
Part V Network Dynamics: Population Models (2 weeks)
 16. Information Cascades
 17. Network Effects
 18. Power Laws and RichGetRicher Phenomena
Part VI Network Dynamics: Structural Models (1 week)
 19. Cascading Behavior in Networks
 20. The SmallWorld Phenomenon
 21. Epidemics
Part VII Institutions and Aggregate Behavior (1 week)
 22. Markets and Information
 23. Voting


Assignments
Assignment 4  April 5, 2012 Due: April 24, 2012
Solve problems 16.4, 17.2, 19.3, 20.2, and 21.3.
Assignment 3  March 8, 2012
Assignment 2  February 16, 2012
Assignment 1  February 2, 2012
