Networks II

Information Science 4220
Cornell University, Spring 2013
Tues-Thu 11:40-12:55

Thurston Hall 203

Arpita Ghosh

Networks II builds on its prerequisite course, continuing to examine how the computing, economic and sociological worlds are connected and how the structure of these connections affects these worlds. In this course, we will construct mathematical models for and analyze networked settings, allowing us to both make predictions about behavior in such systems, as well as reason about how to design such systems to exhibit some desirable behavior. Throughout, we will draw on real-world applications such as kidney exchange, online reputations systems, peer-to-peer filesharing, crowdsourcing and social networks that illustrate these phenomena.

Course Staff

 Course Piazza page:

 Course Blog page:

We encourage you to post all your questions and comments regarding the class and course material on Piazza, as well as help answer other students' questions and contribute to discussions. We will check Piazza regularly and answer the questions as soon as we can. For any personal issues, not related to course logistics or content, you can send an email to the course staff list so it will reach to both the instructor and the TA--- please use only the course staff address so it reaches both of us, making it more likely you will get an answer sooner.


Outline of Topics

  1. Matching markets
  2. (a) One-sided matching markets
    i. Binary (0-1) preferences:
    • Perfect matchings; the Matching theorem
    ii. Rank-order preferences:
    • Pareto efficiency and strategy proofness
    • No initial endowments ("House Allocation"): Serial dictatorship
    • Initial endowments: Core allocations; Gale's Top Trading Cycles (TTC) Algorithm

    (b) Markets with two-sided preferences
    i. The marriage model. Stable matchings.
    ii. The Gale-Shapley algorithm and its properties
    iii. Many-to-one matching
    iv. Incentives and preference reporting

    (c) Applications
    i. Kidney exchange
    ii. College admissions (NRMP hospital-intern match)
    iii. School choice

  3. Information and behavior on networks
  4. (a) Asymmetric information and quality uncertainty online: adverse selection and moral hazard; ratings and reputation
    i. Moral hazard and the EBay reputation system:
    • A game-theoretic framework using repeated prisoner's dilemma. Case-study: Empirical evidence, and redesign
    ii. Amazon ratings and adverse selection:
    • Eliciting opinions online; the peer-prediction method
    iii. Information asymmetry in human computation and crowdsourcing

    (b) Free-riding: Public-goods games
    Application: P2P file-sharing

    (c) Privacy: Information sharing and frameworks for privacy guarantees

  5. Diffusions, cascades and networks
  6. (a) Diffusion in networks and network effects:
    • How and when does network structure matter? Aggregate adoption versus social network adoption.

    (b) Modeling and analzying the effect of network structure on diffusion:
    • Cascade capacity

    (c) Applications:
    i. Adoption of new technologies--- Instant messenger adoption
    ii. Coordination and collective action: Revolutions and Twitter


This is a new course, and as such there is not a single book that will cover all the material in the course. There are two books that will contain much of the material.

In addition, the following book contains all the material we will cover on two-sided matching markets (but also much, much more):

There will also be several readings that will be posted to CMS as they become relevant. The books and readings will not substitute for attending class, though, since the material in the lectures will typically at a different level of detail than the readings. Readings should be used as a supplement and not a substitute for lectures.


Networks (InfoSci 2040) or permission of instructor; familiarity with elementary calculus (at the level of Math 1110 or equivalent), and basic probability and statistics.

Credit Components:

Academic Integrity

You are expected to maintain the utmost level of academic integrity in the course. Any violation of the code of academic integrity will be penalized severely.

You are allowed to collaborate on the homework to the extent of formulating ideas as a group. However, you must write up the solutions to each problem set completely on your own, using no memory aids whatsoever from your discussions, and understand what you are writing. You must also list the names of everyone that you discussed the problem set with.

Collaboration is not allowed on the other parts of the coursework.

Finally, plagiarism deserves special mention here. Including text from other sources in written assignments without quoting it and providing a proper citation constitutes plagiarism, and it is a serious form of academic misconduct. This includes cases in which no full sentence has been copied from the original source, but large amounts of text have been closely paraphrased without proper attribution. To get a better sense for what is allowed, it is highly recommended that you consult the guidelines maintained by Cornell on this topic. It is also worth noting that search engines have made plagiarism much easier to detect. This is a very serious issue; instances of plagiarism will very likely result in failing the course.