CS285: Multi-Agent Systems
Instructor:
Prof. David C. Parkes
last-name - at - eecs.harvard.edu
Teaching Fellow:
Dimitrios
Antos
last-name - at - fas.harvard.edu
Meeting time:
Tuesdays & Thursdays 11:30-1:00 PM ( first class Thursday, September 2
)
Location:
MD 221 (Maxwell Dworkin, 33 Oxford St.)
Office Hours:
David Parkes: Maxwell
Dworkin 229, 1-2pm on Tuesdays
Dimitrios: Maxwell Dworkin 217, 3-5 PM on Mondays
Announcements
- Prof. Parkes has extra office hours, 1-2pm, on Thursday 9/2
- Survey for the first-class (9/2): download here.
- Handouts for the first class: [1] and [2].
- Submit your comments (starting 9/7) here.
- First homework is out! Download it here.
- Sections will take place every Wednesday between 4 and 5 PM. Location is Pierce Hall 320.
- Queens example (corrected): download.
- Second homework is out: here.
- NOVEMBER 18: Please send a 1-page (max) paper outlining your ideas for the expositional paper. The deadline is hard! (And please bring a printed copy to class.)
- Third homework is out: here.
- Examples from last year's final papers (thanks to the authors!): [1], [2] and [3].
General Information
Algorithmic, game-theoretic and logical foundations of multi-agent systems, including distributed optimization and problem solving, non-cooperative game theory, learning and teaching, communication, social choice, mechanism design, auctions, negotiation, coalitional game theory, logics of knowledge and belief, collaborative plans and social systems.
Course Goals
A multi-agent system is composed of multiple autonomous entities, with distributed information, computational ability, and possibly divergent interests. Multi-agent systems may be cooperative, as in those of sensor networks and mobile robots in a warehouse, or competitive, as in those of electronic commerce, or for resource or task allocation to competing firms. Some systems are somewhere inbetween, for example Wikipedia and Yahoo! Question and Answers. The agents in a multi-agent system may be both artificial and human (and often humans are present at least on the "edges" to provide preference information, and on whose behalf the artificial agents act.)
The goal of this class is to provide a broad and rigorous introduction to
the theory, methods and algorithms of multi-agent systems.
The material spans disciplines as diverse as computer science
(including artificial intelligence, theory and distributed systems),
microeconomic
theory, operations research, and linguistics and belief systems.
We will
seek to emphasize computational perspectives where appropriate.
The class is designed to provide a survey of this exciting area
for students of computer science, applied mathematics and microeconomics,
and will also provide an excellent basis for continued research in this area.
Prerequisites
The stated requirement is Computer Science 181 or 182. A level of comfort
with mathematical formalisms and proofs is required.
Students should
also have familiarity with basic computer science (algorithms, complexity;
e.g., CS 121 and CS 124), and basic probability theory (e.g. Stat 110 or ES 101). Some familiarity with game theory (EC 1051, EC 1052) is helpful but not required. Definitely talk to the
instructor after class on September 2 if you have any questions. Students with a
background in mathematical economics (e.g. EC 1011a), and an interest in computational issues, should be able to appreciate the class materials.
Course Reading
Required text: Multiagent Systems: Algorithmic, Game-Theoretic
and Logical Foundations, by Yoav Shoham and Kevin Leyton-Brown, Cambridge
University Press 2008. This book is required, and available at the COOP.
Course Structure
This class is an interactive, but lecture-based class. Students must submit comments and on the reading before each class, in particular to stress questions that they have about the material and possible areas of discussion. Moreover, there will be two classes dedicated soley to discussion and reflection on the material covered in the class. There are three "pencil and paper" problem sets that do not require any programming and are designed to help with understanding of the course material. In lieu of a final exam there is an expositional paper, to be written on a topic of the student's choice (see below.)
To get the most out of the class, students should do the readings, note questions in the readings, and compare prepared to ask the questions in the classroom.
Students may work in pairs on the problem sets. There are no late days.
| Problem Sets: Topic | Available | Due Date |
| Cooperation and Competition | 9/3 | 10/7 |
| Game Theory and Social Choice | 10/26 | 11/10 |
| Mechanism Design and Logic | 11/16 | 11/30, 23:59 |
Expositional paper
In place of a final exam, students will write a short (maximum 10 page) expositional paper on two related technical papers of their choice that are related to the course material. This structure is a strict requirement. The survey must include an exposition of two formal results in these papers, and must also provide a critical discussion of assumptions made by the authors along with some suggestions about future work. Final papers are to be written individually. The final paper is due at 2pm to Maxwell Dworkin 133 on Friday 12/10.
Grading
To recognize the importance of class room participation, the final grade in the class will breakdown as: participation and comments 20%, homeworks 60%, and exposition paper 20%.