About ICSI Groups Projects Publications Events Partnerships Visitor Programs News Search
Previous Years 2010 2009 2008 2007 2006 2005 2004 2003

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



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


Copyright © 2011 International Computer Science Institute. All Rights Reserved.