CPSC 532A - Multiagent Systems
Overview | Grades | Final ProjectTexts | Schedule | Handouts]
Year: Winter 2003-2004, Term 2
Meeting Times: Monday and Wednesday, 12:30 - 2:00
Location: CICSR 104
Instructor: Kevin Leyton-Brown
Office Location: CICSR 185
Office Hours: Wednesday 2:00 - 3:00, or by appointment

Course Description:  This course examines the mathematical and computational foundations of modern multiagent systems, with a focus on game theoretic analysis of systems in which agents cannot be guaranteed to behave cooperatively.  The course emphasizes student participation, featuring seminar-style discussion as well as traditional lectures and giving students opportunities to make presentations. The course will culminate in a major research/writing project in which students survey existing literature and possibly explore open research questions.


Course Topics: Games: normal-form; extensive-form; repeated; stochastic; Bayesian.  Definition and computation of game-theoretic solution concepts. Mechanism design: key positive and negative results.  Single-good auctions. Combinatorial auctions: bidding; mechanisms; computational issues. Learning in games: repeated games; stochastic games; large populations.


Prerequisites:  There are no formal prerequisites, and it is assumed that most students in the class will be unfamiliar with Game Theory, Mechanism Design, Auction Theory, and the literature on Multiagent Systems.  Since some of the material to be covered is quite formal mathematically, students will need to be able to construct and follow formal proofs.  Relevant mathematical/CS background would include introductory knowledge of probability theory, computational complexity and combinatorial optimization. Much of the work associated with the course will revolve around reading papers from the Multiagent Systems literature, writing a survey or research paper, and presenting findings to the class.  Students who have trouble reading, speaking or writing comfortably in English will find themselves at a disadvantage.



Overall Grading Scheme

Literature Presentation 8 %  (5% instructor; 3% peer)
Midterm 15 %
Final Project 42 %
Take-Home Exam 20 %
Peer-Review of Papers 5 %
Participation in Discussions; Quality of Peer Review; Attendance 10 %


Final Project Grading Scheme (showing percentages of overall grade)

Proposal, references, outline 5 %
Paper 25 %
Presentation 12 %  (7% instructor; 5% peer)
Possible Bonus Marks on Paper 2 %


Working in Pairs: Due to the small size of the class, students will not be allowed to work in pairs. 


Curving Grades and Peer Review: Final grades will be curved to give the overall distribution of grades a desired mean and standard deviation. Bonus marks will be applied after grades are curved.  Peer review is an important component of the class, and will be taken into account when evaluating presentations and papers.  Since this is a Multiagent Systems course, we have endeavored to construct a grading scheme that does not provide students with any ability to influence their own grades by reviewing other students strategically.  The curve for a given student x will be calculated disregarding x's presentation and paper reviews of other students. To learn more, see mini-assignment 1.


  Final Project

The most important single component of CPSC 532A is the final project, which allows students to explore material that was not covered in class and to share that material with other students.  The project culminates in students writing and presenting a research paper, either alone or in pairs.  The idea is to emphasize the skills that students need for writing a conference paper: reading from the literature; outlining ideas; writing; peer review; delivering a presentation.  Here is the "pipeline":
  • submit a topic proposal (also to be used as the basis for forming pairs)
  • identify relevant references, and submit written one-paragraph summaries
  • present one of these references to the class and get feedback
  • submit an outline of the paper to the instructor
  • hand in the paper itself, which will be sent out to other students for peer review
  • present the paper in class; the presentation will also receive peer review
  • design several exam questions based on the paper, one of which will be used in the final

The topic of the final project should either be a survey of a subarea in Multiagent Systems, a compare-and-contrast of two or more influential papers, or your own research ideas.  In future weeks a list of possible topics will appear in this space.  Hopefully at least some of the 532A projects will develop into publishable work.


We will be using a new text under development, which is currently only available in electronic form.  In class an address has been provided from which this book can be downloaded.
If you'd like to do additional reading on Game Theory, I can recommend the following supplemental books:
M. Osborne and A. Rubinstein, A Course in Game Theory
MIT Press, 1994, ISBN: 0262650401
D. Fudenberg and Tirole, Game Theory
MIT Press, 1991, ISBN: 0262061414

Here is the tentative schedule for CPSC 532A. Note that lecture topics after the midterm are not filled in; they'll be determined later, depending on which topics students in the class find most interesting. The rest of the schedule is also subject to change, but it's probably a pretty accurate guideline.


Date Lecture topic Milestone
Mon, Jan 12 Introduction  
Wed, Jan 14 Games in normal form  
Mon, Jan 19 Games in normal form Mini-assignment due
Wed, Jan 21 Games in extensive form  
Mon, Jan 26 Imperfect information and repeated games  
Wed, Jan 28 Bayesian games  
Mon, Feb 02 Social choice  
Wed, Feb 04 Social choice  
Mon, Feb 09 Mechanism design  
Wed, Feb 11 Mechanism design  
Mon, Feb 16 - Reading Week
Wed, Feb 18 - Reading Week
Mon, Feb 23 Mechanism design  
Wed, Feb 25 Auctions Submit reference summaries, outline draft (Friday)
Mon, Mar 01 Midterm  
Wed, Mar 03 Auctions Submit reference summaries, outline final (Friday)
Mon, Mar 08 Auctions  
Wed, Mar 10 Multi-good Auctions  
Mon, Mar 15 Student presentations  
Wed, Mar 17 Student presentations  
Mon, Mar 22 Combinatorial Auctions  
Wed, Mar 24 Combinatorial Auctions Submit final project.
Mon, Mar 29 Student presentations? Submit final project (5 PM)
Wed, Mar 31 Student presentations Read and evaluate papers to be presented today.
Mon, Apr 05 Student presentations Read and evaluate papers to be presented today.
Wed, Apr 07 Student presentations. Read and evaluate all papers. Submit exam questions.
Wed, Apr 14 Review session 12:30 in our classroom; bring your own questions
Mon, Apr 19 Final exam 12:30 until 12:30 Wednesday the 21st (48 hours)
  Student Presentations

Wednesday, March 31

Monday, April 5

Wednesday, April 7

  • Mini-Assignment: Peer-Review Grading [pdf].
  • Mini-Assignment Solution [pdf].
  • Course Reader Errata [html].
  • Proof of the folk theorem [pdf]
  • A survey of Mechanism Design [ps]
  • Grading scheme for literature presentations [pdf]
  • AAAI Style file for the final project [link]
  • Grading scheme for final presentations [pdf]
  • Grading scheme for final papers [pdf]