COMPSCI 236R: Topics at the Interface between Computer Science and Economics

CS 236r Topics at the Interface between Computer Science and Economics

Spring 2016: Prediction, Learning and Games

Meeting: Mondays and Wednesdays 1:00-2:30pm, Maxwell Dworkin 323 
Instructor: Yiling Chen, yiling@seas.harvard.edu 
Teaching fellow: Bo Waggoner, bwaggoner@fas.harvard.edu 
Office Hours: 
     Yiling: Wednesdays 2:30-3:30 or by appointment, Maxwell Dworkin 233. 
     Bo: Mondays 2:30-4:00 or by appointment, Maxwell Dworkin 115. 

General Information

This is a rotating topics course that studies the interplay between computation and economics. Topics covered include but are not limited to 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. If necessary, we'll use a survey to help with the selection of students, with preference given to graduate students and students with the strongest background.

Prologue

Crucial to decision making is the fundamental problem of prediction. In the presence of uncertainty, a prerequisite for good decision making is being able to make accurate forecasts for relevant uncertain factors or unknown relationships. Researchers in different disciplines have developed a wide range of methods and techniques for this problem. For example, one natural idea for obtaining accurate predictions is to ask experts or people who have relevant information to share their beliefs. Proper scoring rules are developed, mostly in economics and statistics, to incentivize the experts to honestly reveal their information. Built upon proper scoring rules, prediction markets further integrate the aggregation of private information with the elicitation of it---they provide incentives for participants to incorporate what has been revealed with their private information when making a prediction. Another widely adopted approach to prediction is to use historical data. Machine learning and statistical methods fall into this category. Classification algorithms and regression methods attempt to approximately learn the underlying relationship between inputs and outputs from available data with the goal to make accurate predictions on future, unseen inputs.  

The above two examples approach the problem of prediction from different perspectives. The "asking the expert" approach emphasizes economic incentives for elicitation, while the "using historical data" approach concerns statistical learning. Each approach has independently blossomed into elegant theory and successful applications, by focusing on its own consideration and largely ignoring the other approach. In recent years, with our increasing abilities to reach and engage a large number of people via the Internet, it has become clear that the interplay between economic incentives and statistical learning can affect the prediction outcomes significantly. After all, statistical learning can be performed on elicited data and if data are provided by people, they may have incentives to withhold or misreport their data to affect learning outcomes.  

In Spring 2016, we consider the very recent research directions at the interface between economics and machine learning. We'll discuss a few topics that have developed initial connections between incentives design and statistical learning. 

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, decision theory, mechanism design and machine learning, 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 calculus (AM 21a or equivalent), a linear algebra course (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.) The informal requirement is a reasonable level of mathematical maturity. 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.

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 for each topic will include lectures on some important background material that will help with understanding the material in the papers that we will read. There will be 2 problem sets.

The final grade in the class will breakdown roughly as: participation and comments 25%, problem sets 25%, presentation of research papers 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 more sets of 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 problem sets and are encouraged to work in pairs for final projects other than exposition papers.

Collaboration Policy: Discussion and the exchange of ideas are essential to academic work. If you work in a team for problem sets and final project, collaboration within the team is essential and strongly encouraged. However, it is expected that each member of a team makes roughly equal contributions. For final projects, you are encouraged to consult with your classmates outside of your team on the choice of topics and to share sources. You may find it useful to discuss your chosen topic with your peers, particularly if you are working on the same topic as another team. However, you should ensure that any written work your team submit for evaluation is the result of your team's research and writing and that it reflects your team's approach to the topic. You must also adhere to standard citation practices in this discipline and properly cite any books, articles, websites, lectures, etc. that have helped you with your work. If you received any help with your writing (feedback on drafts, etc), you must also acknowledge this assistance.

Submitting Comments and Presenting Papers

You are required to read papers and other listed reading materials before each class. (Materials listed under Extra Readings on the Schedule page are optional.) You MUST submit comments on the readings by midnight before class. Your comments should include good-faith answers to posted reading questions (if any) and general comments. For research papers, things to think about for general comments 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.

You won't be graded on the correctness or the rigorousness of your answers to reading questions. These questions are designed to assist in understanding the material and to encourage discussion.

Presenting papers: Students will present papers (likely with a partner) and, in addition to the presentation, be ready to lead a discussion in class. Students presenting papers must come by to office hours 1.5 week before their presentation and talk with me about the paper(s) before their presentation. Students are also asked to propose reading questions for the papers they present. Please read the Presentation Notes for expectations on student presentations.

Course Reading

There is no required text. All readings will be distributed electronically and sometimes in class. Additional references include:

• Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, by Y. Shoham and K. Leyton-Brown. Cambridge University Press (2009). (Available for free through this website.)
• 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.)
• 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 (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 at least two related technical papers of their choice that are related to the course material. Such a paper MUST include an exposition of 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.