Networks, crowds and markets: Foundations for formal analysis and design
Information Science 6260
Cornell University, Fall 2015
Mondays 1:25pm-4:25pm
Gates
Hall
Information science studies systems at the juncture of people and technologies---their behavior, analysis and design. This doctoral level mixed lecture-seminar course is an introduction to the formal analysis of social systems: we will introduce concepts from mathematics, computer science and economics that are fundamental to analyzing many settings---networks, crowds, markets---studied by information science, and see how formal reasoning using abstract mathematical models can help analyze and predict outcomes.
Throughout, we will draw on real-world examples such as social networks, Internet markets, and crowdsourcing to illustrate how formal analysis can inform the understanding and design of social systems.
Learning outcomes:
This is a core course for the Information Science PhD program. Students will learn the foundations of abstract mathematical modeling for the analysis of networks and information systems, and some basic techniques from mathematics, computer science and economics that are necessary to construct and utilize these models. The course will consist of a combination of lectures by the instructor, and seminar-style presentation of research papers by students. The seminar component of the course will expose students to the research literature in this area, as well as develop skills in critically evaluating and engaging with the literature.
Prerequisites: Graduate standing in Information Science PhD program.
Credits: 3.
Course Information
Instructor: Arpita Ghosh
Office: 207 Gates Hall
Email: arpitaghosh@cornell.edu
Note: I am typically unable to respond to email due to severe RSI. Asking questions in-class, after class, or in office hours (starting September) is the best way to communicate with me.
Office hours: 3-4pm Wednesdays, Gates 207.
Course outline and schedule
(Caveat: The schedule below is tentative, and may be modified somewhat through the duration of the semester.)
This course will use material from the text Networks, crowds and markets by Easley and Kleinberg; all chapter numbers below refer to this book.
- Introduction and overview (Week 1)
- Graphs: Information flow in networks (Week 2)
- Basic concepts: Connectivity and graph structure
- Weak ties, bridges, and social capital
We'll start with looking at information flow in networks as a means to learning about formally representing the underlying structure of a network: this will be an introduction to basic ideas and reasoning from graph theory (Chapters 2 and 3).
- Probability: Information cascades (Week 3)
- Inference and decision-making
- A model for herding
Next we'll introduce decision-making agents into the mix: we'll look at a mathematical model that allows studying the phenomenon of information cascades, which will help learn basic probability and reasoning with Bayes rule (Chapter 16).
- Strategic reasoning: Voting (Weeks 4,5,6)
- Voting for information aggregation
- Voting for group decision-making
So far, the payoffs to our decision-makers haven't depended on the decisions of other agents in the system. Now we'll study two kinds of voting applications to introduce strategic reasoning about other agents' behavior into the mix (Chapter 23): this will introduce game-theoretic reasoning.
- First, we'll start with voting when agents are in agreement about what outcome they'd ideally like---if they all had the same information, but, alas, don't (Sections 23.7-23.10). The basics of the model here are very similar to those in our previous topic, but differ in two important ways: first, in the information structure---here all decisions are made simultaneously---and second, in payoffs---here, your decision can indeed affect my payoff, whereas previously your decision only contributed to mine via the information it conveyed.
- Next we'll move to voting for preference aggregation, where agents might actually have different preferences over outcomes: again, my payoffs might now depend on your decision in addition to mine (Sections 23.2-23.6). We'll ask how to aggregate individual preferences into a common `good' outcome for the group---and what good means.
- Efficiency: Markets and information (Weeks 7,8)
- Fundamentals of matching markets: Prices and market clearing
- Information asymmetry and efficiency: How information structure can change market outcomes
Finally we'll study matching markets, and see how the information structure in the market can---quite dramatically---alter market outcomes (Chapters 10 and 22.6): in the process, we will introduce the notion of economic efficiency, and see how prices can serve as a mechanism to align agents’ preferences---even when differing across alternatives, as in our previous voting scenario---over outcomes.
This final topic will provide a particularly clear illustration of two themes running throughout the course: first, that formal analysis can help understand what might happen in an online system in a way that would be difficult without a mathematical model, and second, the idea of information as a design choice that can fundamentally alter system outcomes.
- Seminar-style presentations (Weeks 9, 10, 11)
Students will present research papers at the intersection of formal analysis and information systems; papers will be listed later in the term.
- Final class: Presentations of student research proposals (Week 12)
Coursework
The course will be evaluated on the basis of the following components (details and guidelines for each component will be described in class).
- Class presentations of chapter content: 25%
- Seminar-style presentations (paper summary, discussion of relation to formal analysis, and research critique): 25%
- Research proposal: 10%
- Homework assignments (2-4 problem sets): 25%
- Class participation (reaction notes and discussion): 15%
Note that class attendance is a critical component of the course since most learning will occur in class. While not explicitly assigned a percentage of total course credit, poor attendance will result in a penalty in the final grade.