CS286r: Topics at the Interface between Computer Science and Economics

Fall 2011 ⋅ Computational Social Choice: Voting, Preferences and Fair Division

Meeting Monday, Wednesday 1:00– 2:30PM
Location: MD 319.

Instructor     Yiling Chen (please call me Yiling) Teaching Fellow     Mike Ruberry
yiling – at– mruberry – at –
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.

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

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.


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.

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

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.

Course Reading

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

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 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!