 |
 |
DIVISION OF ENGINEERING AND APPLIED SCIENCES
HARVARD UNIVERSITY
schedule | announcements | assignments | projects | comments| CPLEX
|
|
Example domains are drawn from e-commerce (Internet auctions, electronic markets for supply chain, automated bidding agents) and from computational applications such as resource allocation in computational grids and routing across peer-to-peer wireless networks. Many complex resource allocation problems fall under the rubric of computational mechanism design. For instance, the Federal Aviation Administration might consider the use of auctions to allocate takeoff and landing slot rights at congested airports. Strategic and economic issues in any proposed design are important. But so are computational issues, such as can the winner-determination problem in an auction be cleared quickly enough and what is the design for a suitable bidding language, that is both expressive and compact?
This course was last taught in Spring 2002 and we will focus almost exclusively on papers written since then. A lot of progress has been made in understanding requirements for strategyproof mechanisms that are nonmanipulable, and research is now pushing into online auction settings in which temporal dynamics must be considered. We'll keep broad though and will not focus exclusively on auction problems but also read papers on cryptographic approaches that remove the need for a trusted center, and on distributed approaches and adaptive approaches that bring in ideas from machine learning and distributed problem solving and optimization.
The tools used are drawn from discrete algorithms, artificial intelligence, linear programming and duality, game theory, discrete optimization, and mathematical economics. Official prerequisites are listed on the main class web page.
Many related papers can be found at the Harvard econcs web page.
Prerequisites: This course draws on a broad set of ideas, from CS theory, to AI, to economics. Formal requirements include a basic course in linear algebra (such as M 21b, AM 21b, or equivalent), CS 121 (complexity theory) and CS 124 (algorithms), and a course in AI, such as CS 181 or CS 182. Students can petition to substitute an economic theory course for an AI course. A course in advanced algorithms, such as CS 223, Probabilistic algorithms, or CS 226r, Efficient algorithms is preferred but not required. Similarly, knowledge of game theory, microeconomics, and auction theory, is very helpful but not required. Mathematics 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 for the course read a couple of papers from the reading list, and attend my office hours during the first week.
Time/Location: The course meets on Mondays and Wednesdays, 1-2.30pm, in Maxwell-Dworkin 319.
Limited Enrollment: Enrollment will be restricted to 20 students to facilitate seminar-style discussion of papers. A form 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.
Office Hours: Regular hours: TR 2-3pm, Maxwell-Dworkin 229. Additional early-term office hours: Mon 2/7 2:30-3:30pm.
Missed Course Materials: Laura Kang (kang@eecs), Maxwell-Dworkin 217.
Course Structure: This is primarily a seminar course, and we will spend most of the term reading and discussing research papers. However, I will take the first few lectures of the term to lecture around some important background material that will help with understanding the non-CS related material in the papers that we read. Students will be required to complete a few homework sets during this part of the course. Later, when we move to reading papers, students will be expected to read the papers in advance, participate in class discussion, present one of the papers to the class, and complete a project. Good projects can form a foundation for a research paper, or a senior thesis for undergraduates.
| Problem Sets | 25% | 3-4 Short Problem Sets on Introductory Material |
| Participation | 20% | Reading papers, submitting short summaries and Qs ahead of class, participation in discussion. |
| Presentation of a research paper. | 15% | A short survey and critique. |
| Project. | 40% | Proposal, class presentation, and final report. |
There will be 3 short homework sets during the first four weeks of the term on game theory, mechanism design, and auction theory. The problem sets are designed to help with understanding of the background material that is covered in the introductory lectures.
Readings: There is no set text for this course. Readings will be made available electronically, and also distributed in class.
Submitting comments on papers: When we start reading and discussing research papers, please send comments to cs286r@fas.harvard.edu by midnight before class, with the subject line indicating the paper discussed. Things to think about include (you don't need to hit all of these...):
Presenting papers: Students will present papers in pairs, and should prepare a 30 minute presentation on the paper. We will then break into a discussion of the paper. Students presenting papers must come by to office hours and talk with me about the paper(s) before their presentation.
Course Staff:
| Name | Phone | Office Hours | |
| David Parkes | parkes@eecs.harvard.edu | 384-8130 | TR 2-3pm, MD 229 |
| Laura Kang | kang@eecs.harvard.edu | 384-8123 | Tue 6:30-8:30pm, MD 217 |
Class Project: The goal of the final project is to develop a deep understanding of an important research area, and, to the extent possible, to work on an open research problem. Students may also review an existing area of literature. Although project areas must be approved, the choice is left largely up to the student. Projects may be theoretical or experimental. A list of suggested topics for projects is available. Students are also encouraged to propose a topic of their own for approval. Project proposals are due Wednesday, April 13. Project presentations will be on Tuesday, May 17 (9:30am - noon), with project reports due on the last day of reading week (Wednesday, May 18) to Arthur Cram in MD 133.
Related Courses: