SCHOOL OF ENGINEERING AND APPLIED
SCIENCES
HARVARD UNIVERSITY
CS286r: Topics at the Interface between Computer Science and Economics
Information, Prediction, and Collective Intelligence
Instructor:
Prof. Yiling Chen
yiling - at -
eecs.harvard.edu
Teaching Fellow:
Alice Gao
xagao - at -
seas.harvard.edu
Meeting time:
Monday, Wednesday
1pm - 2:30pm
Location:
Maxwell
Dworkin 221, 33 Oxford Street
Office Hours:
Yiling: Maxwell
Dworkin 339, Monday, 4pm - 5pm, Friday, 2pm - 3pm
Alice: Maxwell Dworkin 242, Tuesday, 2:30pm - 4pm
Announcements
Tentative Presentation Schedule: Sergiy, John and Andrew, Dylan, Kevin, Mike and Victor, Jerry, Nitish, Rick, Karim and Benny, Sachin, Alex and Mikkel, David and Thomas, Scott, Wei, Pramod
Please email Yiling and Alice your presentation files by midnight of Sunday December 5.
Students will be giving brief project presentations at 1pm-3pm on Monday December 6 in MD221. Every project presentation will be 8 minutes long (7 minutes presentation + 1 minute Q&A). Students are required to attend the project presentations.
For Wednesday Dec 1, please submit comments on what you would like to discuss during class. The deadline is the midnight of Tuesday as usual.
Just a note about projects: Exposition papers are considered individual projects only. For non-exposition-paper projects, you may work in pairs if you prefer. Naturally, we have higher expectation for the quality of the projects if you work in pairs. Once we read through your project proposals, we will give feedback to each group and go from there.
We have posted a list of project ideas on the Project Ideas page. These should help you get started on your project proposal. You are encouraged to come up with your own project topics and come to talk to us about it. Note that project proposals are due on Friday 11/5 at noon to Ann Marie King in MD 133 and by email to Alice at xagao@seas.
General Information
This is a rotating topics course that studies the interplay between computation and economics. Topics covered include electronic commerce, computational social choice, computational mechanism design, peer production, prediction markets and reputation systems. The class is seminar style and readings are drawn from artificial intelligence, theoretical computer science, multi-agent systems, economic theory, and operations research.
Note: Enrollment of this course will be limited to facilitate seminar-style discussion of papers. A survey will be distributed in the first class to help with the selection of students, with preference given to graduate students and students with the strongest background.
Prologue
Many problems of interests are fundamentally about obtaining and aggregating information from the crowd. Think about influenza surveillance. Timely information on flu activities is highly desirable for influenza prevention and treatment, but is often possessed by different people, including doctors who meet patients, clinical microbiologists who perform respiratory culture tests, pharmacists who fill prescriptions, and even people who have acquired influenza. How to elicit, aggregate, and make use of such small pieces of information is crucial for informed decision making. Similarly, consider a machine learning system that has access to predictions of heterogeneous learners. A central problem is how the learning system combines the predictions of the learners to obtain a good prediction. The recent DARPA Network Challenge further pushes the idea of harnessing the collective intelligence by asking teams to provide coordinates of ten red weather balloons placed at different locations in the continental United States.
In fall 2010, we consider research directions related to information, prediction, and collective intelligence, covering topics of information theory (very briefly), peer prediction mechanisms, prediction markets, online learning, and collective task solving. Some example research challenges we will consider are: how to incentivize truthful report of information, especially when the information is subjective or about some uncertain event whose outcome is not verifiable in the future; how to combine information from different sources; and how to design mechanisms to allow people to express their information more freely.
Course Goals
The main goal of this course is to provide an introduction to the interdisciplinary literature for students looking to identify research directions in this area. Along the way, we will also develop some technical background in game theory and mechanism design, and hopefully also more general skills related to reading papers and thinking about research problems. This is a seminar course and students will be expected to participate in class discussion, present one or more papers, and write a final course paper. Students are expected to achieve a comfort level with both economic and computational thinking, become familiar with the status quo in the area, and, to the extent possible, work on an open research problem.
Prerequisites
Formal requirements include a basic course in linear algebra (AM 21b or equivalent), a probability and statistics course (STAT 110 or equivalent), an algorithms course (CS 124 or equivalent), and a background in either AI or microeconomic theory (CS 181, CS 182, EC 1011a, or equivalent.) Familiarity with economic theory is helpful but not required. Familiarity with AI and computer science theory is helpful but not required. Students with a background in theoretical microeconomics and an interest in computational issues should be able to appreciate the class materials. A background in optimization (e.g., AM 121) is useful but not necessary.
Mathematical analysis and formalism will be fundamental to the course, and students should expect to learn additional mathematics on their own as necessary. I recommend that students unsure about their background read a couple of papers from the reading list, and attend office hours during the first week.
Course
Structure and Grading Policy
This course is primarily a seminar course. We will spend most of
the term reading and discussing research papers. However, the first few
classes will include lectures on some important background material
that will help with
understanding the non-CS related material in the papers that we
will
read. There will be 2-3 problem sets.
The final grade in the class will breakdown roughly as: participation and comments 25%, problem sets 25%, presentation of a research paper 15%, project 35%.
Students are expected to read the papers in advance, submit short summaries and questions before class, participate in class discussion, and present and lead discussion on one or two papers (typically in a pair).
In lieu of a final exam there will be a final research paper, on a topic of the student's choice. Good papers can form a foundation for a research leading to a conference publication, or a senior thesis for undergraduates. Students may work in pairs on the problem sets and for final projects that involve computational work.
Submitting Comments and Presenting Papers
When we start reading and discussing research papers, you MUST upload comments on the papers by midnight before class. Things to think about include (you don't need to hit all of these...):- what is the main contribution of the paper?
- is this important, why?
- is this a comp sci contribution, an econ contribution, or both?
- what was the main insight in getting the result?
- what is not clear to you?
- what did the authors not do?
- what are the most important assumptions, are they limiting?
- what applications does this suggest?
- how does this relate to other things we have seen?
- what extensions does this suggest?
- can you suggest a two-sentence project idea based around the ideas in this paper?
I also recommend you read the blog post by Prof. Michael Mitzenmacher on How to Read a Research Paper.
Presenting papers: Students will likely present papers in pairs, and should prepare a 20-30 minute presentation on each paper and be ready to lead a discussion in class. Students presenting papers must come by to office hours and talk with me about the paper(s) before their presentation.
Course Reading
There is no required text. All readings will be distributed electronically and sometimes in class. Additional references include:
- Algorithmic Game Theory, Edited by N. Nisan, T. Roughgarden, E. Tardos and V. Vazirani, Cambridge University Press (2007). (Find information to download a non-printable copy of the book at here.)
- A course in game theory, by M. J. Osborne and A. Rubinstein, MIT Press (1994). (Available for free through this website.)
- Essentials of Game Theory: A Concise, Multidisciplinary Introduction, by K. Leyton-Brown and Y. Shoham, Morgan Claypool Publishers (2008).
- Elements of Information Theory, by T.M. Cover and J.A. Thomas, Wiley-Interscience (2005).
- Prediction, Learning, and Games, by N. Cesa-Bianchi and G. Lugosi, Cambridge University Press (2006).
Final Paper
The goal of the final paper is to develop a deep understanding of a specific research area related to the topic of the class, and to the extent possible to work on an open research problem. Although paper topics must be approved, students are free to pick a topic of interest in the general field related to information, prediction and collective intelligence. Students are required to submit a proposal, give a short presentation, and submit a final paper at the end of reading week (maximum 10 pages except for Appendix material). Papers may be computational, theoretical, experimental or empirical. Students may write an exposition paper (maximum 10 page) on two related technical papers of their choice that are related to the course material. Such a paper MUST include an exposition of (at least) two formal results in these papers, provide a critical discussion of assumptions made by the authors and suggestions about future work, and provide a new perspective.
Tentative project due dates:
Friday 11/5 Project proposals due at noon to Ann Marie King in MD 133, and by email to xagao@seas (2 pages, max.)
Monday 12/6 Brief project presentations.
Friday 12/10 Projects due at noon to Ann Marie King in MD 133, and by email to xagao@seas.