CS194-21: Networks, Crowds, and Markets
Instructors: Richard M. Karp and Christos H. Papadimitriou
Office Hours: To Be Announced
Time and Place: Tu,Th 11:00-12:30, 320 Soda
Text: David Easley and Jon Kleinberg, "Networks, Crowds and Markets," ISBN 978-0=521-19533-1, Cambridge University Press (2010).
A complete pre-publication draft of the text is available at http://www.cs.cornell.edu/home/kleinber/.
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 one-page 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 Rich-Get-Richer Phenomena
Part VI Network Dynamics: Structural Models (1 week)
- 19. Cascading Behavior in Networks
- 20. The Small-World Phenomenon
- 21. Epidemics
Part VII Institutions and Aggregate Behavior (1 week)
- 22. Markets and Information
- 23. Voting
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