CPSC 532A - Multiagent Systems
[
Overview | Grades | Final ProjectTexts | Schedule | Handouts]
 
2004-2005:  CPSC 532A - Multiagent Systems
 
     Term: 2
     Meeting Times: Tuesday and Thursday, 3:30 - 5:00 PM
     First class: Tuesday, January 11
     Location: Dempster 201
     Instructor: Kevin Leyton-Brown
     Instructor's Office Location: CICSR 185
     Office Hours: Mondays, 3:00 - 4:30 PM
 
  Overview

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: Overall, problems at the interface of economic theory and computer science.  (No prior experience in economics is assumed.) Specific topic include: Distributed problem solving. Games: normal-form; extensive-form; repeated; stochastic; Bayesian.  Computation of game-theoretic solution concepts. Mechanism design: key positive and negative results.  Single-good auctions. Combinatorial auctions: bidding; mechanisms; computational issues.

 

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.

 

Academic Honesty: Plagiarism is a serious offense and will be dealt with harshly.  I consider plagiarism to be the unattributed use of an external source (e.g., another student, a web site, a book) in work for which a student takes credit. The seriousness of the offence depends on the extent to which the student relied upon the external source.  Assignments and midterms will include an "honour code" statement which you will be required to sign, specifying forms of collaboration and reference to non-course materials that are acceptable.


  Grades

Overall Grading Scheme
Warning: I reserve the right to make changes to the exact percentage breakdowns shown here.  However, the following grading scheme should be approximately accurate, and indicates the components of the class upon which you will be graded.


Assignments 20 %
Midterm 15 %
Final Project 50 %
Peer Review of Other Students' Final Project Papers 5 %
Participation in Discussions; Peer Review for Presentations; Attendance 10 %

Final Project Grading Scheme (showing percentages of overall grade)

Literature Review 8 %
Outline 5 %
Paper 25 %
Presentation 12 %  (7% instructor; 5% peer)
Possible Bonus Marks on Paper (for including original research content) 2 %

 

Working in Pairs: Depending on the size of the class, students may or may not be allowed to work in pairs on the final assignment.  Stay tuned for details.

 

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, a grading scheme has been constructed 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.

 

Assignments:  The course will include four assignments.  Dates on which assignments will become available and due dates are given in the schedule below; assignments are always due at the beginning of class.  Assignments will probably not be weighted equally: weighting will be proportional to the total number of available points.  In particular, the last assignment may be weighted substantially more heavily since it will cover material not reviewed on the midterm exam. Students will be given three late days for use on the assignments.  These are intended to help avoid scheduling conflicts with other courses, personal commitments, and emergencies.  Therefore, no additional late days will be granted except under truly exceptional circumstances.  Late assignments will be penalized at 20% per day.


  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)
  • write a literature review - a 2-3 page summary of four or more papers from the literature on your chosen topic.  You will be evaluated on selecting appropriate references, demonstrating a good understanding of the papers, and communicating clearly.
  • 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

The topic of the final project should either be a survey of a subarea in Multiagent Systems, a compare-and-contrast study of two or more influential papers, or an effort to develop 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.  Please note that assignment late days cannot be applied to the final project.


  Texts
 
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. Please do not distribute this file.  Also, please note that this book will be updated throughout the year; thus, I recommend printing individual chapters as we come to them, or simply using the book electronically, rather than printing the whole book at the beginning of the year.
 
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

Good coverage of linear programming is given by:

J. Nocedal and S. Wright, Numerical Optimization
Springer, 1984, ISBN: 0387987932

  Schedule


Here is the tentative schedule for CPSC 532A. These dates may change throughout the term, but I'll try to keep this schedule up to date.  Blank dates are slack in case some of the topics covered here go long, and/or time for coverage of new topics. Assignment due dates will be added later.  The (tentative) deadline to hand in projects is Thursday, April 21.  The project outline deadline is now rather late; however, you're welcome to discuss your projects earlier during office hours or after class.

 

Date Lecture Topic Milestones
Tuesday, January 11 Introduction  
Thursday, January 13 Distributed problem solving  
Tuesday, January 18 Distributed problem solving  
Thursday, January 20 Games in normal form  
Tuesday, January 25 Games in normal form  
Thursday, January 27 Games in normal form Assignment 1 available
Tuesday, February 01 Games in extensive form  
Thursday, February 03 Imperfect information games  
Tuesday, February 08 Repeated games and the folk theorem  
Thursday, February 10 Bayesian games Assignment 1 due
Tuesday, February 15 Break  
Thursday, February 17 Break  
Tuesday, February 22 Social choice  
Thursday, February 24 Social choice  
Tuesday, March 01 Mechanism design  
Thursday, March 03 Quasilinear utility and risk attitudes  
Tuesday, March 08 Groves mechanism  
Thursday, March 10 Clarke tax Submit literature review.  Assignment 2 available
Tuesday, March 15 Groves uniqueness  
Thursday, March 17 Auctions  
Tuesday, March 22 Auctions  
Thursday, March 24 Midterm Exam  
Tuesday, March 29 Auctions Assignment 2 due
Thursday, March 31 Multi-good Auctions  
Tuesday, April 05 Combinatorial Auctions Submit project outline, and present it in class
Thursday, April 07 Combinatorial Auctions  
Tuesday, April 26 Student presentations Read and evaluate papers to be presented today
Thursday, April 28 Student presentations Read and evaluate papers to be presented today.

 

  Handouts
  • Slideshow from Jan 18 lecture on distributed problem solving [PPT | PDF]
  • Assignment 1 [PDF]
  • Proofs of Arrow's Impossibility Theorem
    • Three Brief Proofs of Arrow's Impossibility Theorem, John Geanakoplos: the proof in class followed the first proof in this paper [PDF]
    • Arrow and Gibbard-Satterthwaite - a unified approach, Phil Reny [PDF]
  • Possible project topics [PDF]
  • Proof that truthfulness is a dominant strategy in Groves mechanisms [PDF]
  • Assignment 2 [PDF]
  • Proof that Groves mechanisms are the unique dominant strategy eficient mechanisms for agents with general quasilinear preferences [PDF]
  • Assignment 3 [PDF].  Early due date (for 10% bonus to your grade): April 19.  Actual due date: May 5.  Late days may be used for both deadlines.
  • Final course projects
  • Grading schemes:
    • Written projects [PDF]
    • Presentations [PDF]