Networks, crowds and markets: Foundations for mathematical analysis and design

Information Science 6260
Cornell University, Fall 2017

Mondays 1:30pm-4pm

Gates Hall

Arpita Ghosh

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---relevant to information science, and see how formal reasoning using abstract mathematical models can help analyze and predict outcomes in 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 social 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, or other PhD program.

Note: This course is intended for, and suitable for, graduate students who are currently in a Phd program (in any department). Students not in a PhD program (such as MPS or M.Eng students) that are interested in the course are welcome to audit it, either formally or informally. Requirements for formal auditing are attendance in at least 7 of the first 8 weeks of the course, and at least one of the remaining weeks consisting of student presentations.

Credits: 3.

Course Information

Instructor: Arpita Ghosh

Office: 206 Gates Hall

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: Wednesdays 2-3pm.
Students in NYC: Please send me an email with your Skype ID (as well as whether you have any conflicts in the 2-3 range) and I will message you. (If Skype doesn't work well for you, please send me a phone number (and any conflicts) instead of a Skype ID, and I will call you instead!)

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, as well as several research papers. All chapter numbers below refer to this book.

Optional preparatory work : For students who are extremely unfamiliar with mathematical analysis and/or would like pointers for advance preparation, an accessible and helpful activity would be to read Chapter 6 (Games) in Easley-Kleinberg; you could also read Sections 2.1 and 2.2 in Chapter 2 . Again, this is not required reading; it is purely voluntary and meant to direct you if you are seeking additional resources prior to the start of classes. (Also, you are very welcome to read the chapters in the book that correspond to our syllabus below in advance of class, if you'd like further additional exposure; but again, this is not necessary reading.)

Schedule:

Introduction and overview (Week 1)

Information flow in networks (Week 2)

Basic concepts: Connectivity and graph structure
Diffusion in networks

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. (Chapter 19).

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

Voting for information aggregation (Week 4)

Voting for information aggregation
Voting for group decision-making

So far, our decision-makers haven't needed to account for the decisions of other agents in the system. Now we'll study voting as an application that brings in strategic reasoning about other agents' behavior into the mix (Chapter 23.7-10): this will introduce game-theoretic reasoning.

Voting for preference aggregation (Weeks 5, 6)

Individual preferences, voting rules, and pathologies
The impossibility of `good' preference aggregation: Arrow's theorem

In the previous voting scenario, agents are in agreement about what outcome they'd like---if they all had the same information---except they don't. Now we study a second kind of voting situation, where the issue isn't missing information, but differing preferences over outcomes (Chapter 23.1-6, 23.11).

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 show how prices can serve as a mechanism to align agents’ preferences 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, 12)

Students will present research papers at the intersection of formal analysis and information systems; papers will be listed later in the term.

Final classes: Presentations of student research proposals (Week 13)

Coursework

The course will be evaluated on the basis of the following components. Details and guidelines for each component will be announced in class, after the semester begins.

Class participation (in-class exercises, reaction notes)
Homework assignments
Seminar-style presentations (paper summary, discussion of relation to formal analysis, and research critique)
Research proposal

Note that being present in class is a critical component of the course, since most learning will occur in class. Class attendance is essential for class participation credit, and therefore poor attendance will directly affect the final grade.