Information Science 4220/Computer Science 4852/Economics 3825
Cornell University, Spring 2014
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, college admissions, online reputations systems, peer-to-peer filesharing, and airport security design that illustrate these phenomena.
Important Note: CMS
If you are not already on CMS, please email the course staff list INFO4220-STAFF-L@cornell.edu with subject line "CMS add: NetID *" (replace * with your NetID) to be added to CMS.
All lecture notes, homework assignments and announcements will be posted only on CMS, so do make sure you are on CMS if you are taking the course!
Instructor: Arpita Ghosh, 207 Gates Hall
Course staff email list: INFO4220-STAFF-L@cornell.edu
- Wei Dong <email@example.com>
- Rebecca Coombes <firstname.lastname@example.org>
- Matthew Oey <email@example.com>
- Jeffrey Wai <firstname.lastname@example.org>
Please make sure to use the course staff email list rather than individually emailing the instructor or individual teaching assistants---this list reaches all of us, making it more likely you will get an answer sooner.
Course Piazza page: http://piazza.com/cornell/spring2014/info4220
Please use the course Piazza forum, rather than email, for all questions and comments regarding course logistics, course material and content. Please also help answer other students' questions and participate in discussions, and contribute to an active forum! For any personal issues, not related to course logistics or content, you can send an email to the course staff list.
- Arpita Ghosh:
- Wednesday 3-4pm, 207 Gates Hall
- Wei Dong:
- Monday: 3-5pm, Upson 328B Bay D
- Wednesday: 130-3pm, Upson 328B Bay D
- Thursday: 2-5pm, Upson 328B Bay D
- Friday: 11am-12pm, Upson 328B Bay D
- Networks (INFO2040)
- Familiarity with logical reasoning (at the level of CS 2800 or equivalent),
and basic probability and statistics.
- I haven't taken Networks. Can I still take Networks II?
If you have adequate background in game theory (and have the second prerequisite), you should be able to handle Networks II with the following preparatory self-study: Chapters 6, 10, 22 in Networks, Crowds and Markets. That being said, you will definitely benefit more from this class if you take it after taking Networks, so you should do that if at all possible.
- I don't have the second prerequisite. Can I still take this class?
You can legally take this class, of course, but you might not enjoy it: some familiarity with (or at least aptitude for) simple logical reasoning and basic probability, although not associated with any particular class, is essential for Networks II.
Outline of Topics
Information and behavior on networks
- Why matching markets without money?
- Kidney exchange, college admissions, school choice
- Matching markets with versus without money
- One-sided matching markets without money
- Binary preferences
- Perfect matching; Hall's theorem
- 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
- Application: Kidney exchange
- Markets with two-sided preferences
- The marriage model; stable matchings
- The Gale-Shapley algorithm and its properties
- Many-to-one matching
- Incentives and preference reporting
- Application: College admissions (NRMP hospital-intern match)
- Quality uncertainty on the Web
- Asymmetric information: Adverse selection and moral hazard
- Online ratings and reputation systems
- A game-theoretic framework for moral hazard: Repeated prisoner's dilemma
- Application: An empirical study and redesign of the eBay reputation system
- Online public-goods games
- Free-riding and equilibrium behavior
- Application: P2P file-sharing
- Game theory and airport security
- A model for security: Stackelberg games
- Application: LAX airport security design
There is no textbook for this class, as there is no single book containing all the topics we will cover in this class. However, readings for each topic will be posted on CMS as they become relevant through the semester.
Note that these 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: the readings should be used as a supplement to, rather than a substitute for, the lectures.
To supplement reading material, the lecture slides will also be made available on CMS from after each lecture. Note, however, that some examples will be worked on the whiteboard in class and these will not make their way into the lecture slides. This means that again, the posted lecture slides are not a substitute for attending class.
- In-class midterm: 25%
- Final project (due May 13): 35%
- Homeworks: 30%
- Roughly 1 homework every 2 weeks (for 6-8 homeworks total); will be posted on CMS.
- Due Friday 5 PM (unless otherwise noted), by electronic upload on CMS.
- Blog post: 5%
- Class participation: 5%
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.