CS194-21: 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: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/.

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 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

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