DIVISION OF ENGINEERING AND APPLIED SCIENCES
HARVARD UNIVERSITY

CS 286r. Multi-Agent Learning and Implementation

Prof. David C. Parkes

Spring 2006 MW 1-2.30pm Maxwell Dworkin 319

schedule | announcements | assignments | projects | comments

List of Papers (Presentations start Mon Feb 27, 2006.)

Time and Location

Mon, Wed. 1-2.30pm. Maxwell-Dworkin 319.
Section: Thursdays, 5.10-6.30pm. Room MD 119

General Information

Learning in games is a subject that nicely spans between the fields of economics and computer science. There exists a large, rich and deep literature in game theory, artificial intelligence, and theoretical computer science. This course will adopt a unique perspective: that of implementation. Specifically, we will be reading the papers on the schedule with a view to thinking about the design of protocols for the coordination of multi-agent systems with adaptive agents. To those familiar with mechanism design, think about this as indirect mechanism design for repeated games and possibly with bounded-rational agents.

The course will begin with lectures that will provide a sometimes informal, sometimes technical, and necessarily rapid tour of: game theory (including repeated games and Folk theorems), mechanism design, implementation theory, and sequential decision theory (incl. MDPs and reinforcement learning.) The goal of this first phase of the course is to make everyone reasonably comfortable with the background, before we dive into reading papers.

The bulk of the course will be structured as a seminar. Students (typically in pairs) will present a paper and engage the class in a discussion. The guiding focus in these discussions will be that of implementation: is there a message to take away from the paper about how to design systems for coordinated action between adaptive agents. The papers are grouped, roughly into two main areas:

The tools used are drawn from discrete algorithms, artificial intelligence, linear programming and duality, game theory, discrete optimization, and mathematical economics.

Many related papers can also 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. Much of the material, especially this year, is quite technical. Students should be very comfortable with the methods of applied mathematics, and a strong background in both economics and artificial intelligence is recommended. 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 absolutely 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. This is a seminar class and attendance and participation is required.

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 then students with the strongest background.

Office Hours: Regular hours: Tues and Thursday 2-3pm, Maxwell-Dworkin 229.

Additional early-term office hours: Wed 2/1, 2.30-3pm; Mon 2/6 2.30-3pm.

Missed Course Materials: TBD

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 E-mail Phone Office Hours
David Parkes parkes@eecs.harvard.edu 384-8130 Tue, Thur 2-3pm, MD 229
Giro Cavallo cavallo@eecs.harvard.edu W 2:30-3:30pm (right after class), MD 219
Ben Lubin blubin@eecs.harvard.edu R 3-4pm, MD 215

Assignments:

Course Announcements:

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. Students working on an experimental paper my work in a pair. A list of suggested topics for projects are available . Students are also encouraged to propose a topic of their own for approval.

Project proposals are due Monday, April 17. Project presentations will be on Wednesday May 3rd (4-5.30pm), with project reports due on the last day of reading week (Wednesday, May 17) to Arthur Cram in MD 133.

Student Comments: None yet!

Related Courses:

parkes@eecs.harvard.edu