Schedule
Assignments
Additional Resources
Submit Comments
Project Ideas
CS286r in Previous Years
| Meeting | Monday, Wednesday 1:00– 2:30PM | ||
| Location: MD 319.
|
|||
| Instructor | Yiling Chen (please call me Yiling) | Teaching Fellow | Mike Ruberry |
| yiling – at– eecs.harvard.edu | mruberry – at – seas.harvard.edu | ||
| OH @ MD 319: Monday 2:30 – 3:30 or by appointment. |
OH Wednesday 11 – 12, MD second floor lounge |
Project presentations will be from 1 to 2:40PM on Monday 12/5 in MD 319.
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. 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.
Many problems of central interest within computer science and economics are fundamentally about preferences. In elections, the voters express their preference over the candidates and a voting rule is used to elect the winning candidate. In World Wide Web, a link to a webpage can be viewed as a favorable vote for the webpage. In resource allocation among either human or computer agents, agents have preferences over some resource and a mechanism is used to decide how to allocate the resource to the agents. In a reputation system for electronic marketplaces, how to present the past ratings for a seller may change the behavior of the seller.
In fall 2011, we consider research directions related to computational social choice, covering topics of computational voting theory, ranking and reputation, fair division, and preference elicitation. Research in this area often focuses on achieving one or more of the following desirable properties: social efficiency, strategyproofness, fairness, and computational tractability. Social efficiency aims to obtain an outcome or decision that is optimal for the agents as a group. Strategyproofness reduces agents' attempts to game a system. We'll find that sometimes it is difficult or even impossible to achieve strategyproofness with rational, economic agents. While computational tractability for operating a system is important, computational intractibility for agents to game the system can act as a good barrier to manipulation and help to achieve strategyproofness with computationally bounded agents. Fairness is an essential requirement for reaching stable resource allocation. Computational social choice brings together ideas from computer science, AI, economic theory, CS theory, political science, and logic, among others. This seminar-style course will discuss papers in this exciting interdisciplinary field.
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.
Formal requirements include a
basic course in linear algebra (AM 21b 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.
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 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
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 upload comments on the readings by midnight before class. For research papers, things to think about include (you don't need to hit all of these...):
I also recommend you read the blog post by Prof. Michael Mitzenmacher on How to Read a Research Paper.
I will post reading questions related to the reading materilas. Your comments should include good faith answers to these questions. You won't be graded on the correctness or the rigorousness of your answers. These reading questions are designed to assist in understanding the material and to encourage discussion.
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.
There is no required text. All readings will be distributed electronically and sometimes in class. Additional references include:
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 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
Thanks to Lirong Xia and Ariel Procaccia for reviewing and recommending papers for this course!