CPSC 532A - Multiagent Systems
[
Overview | Grades | Final ProjectTexts | Schedule | Handouts]
 
2006-2007: CPSC 532A - Multiagent Systems
 
     Term: 1
     Meeting Times: Tuesday and Thursday, 2:00 - 3:30 PM
     First Class: Tuesday, September 12
     Location: DMP 201
     Instructor: Kevin Leyton-Brown
     Instructor's Office Location: CICSR 185
     Office Hours: To be announced
     Mailing List: log in to your UNIX account and type "echo subscribe | mailx cpsc532a-request"
 
  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. The course will culminate in a small research 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: 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 offence 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 (three or four) 20 %
Test 1 (probably in-class) option 1: 20 %;  option 2: 10%
Test 2 (probably take-home) option 1: 20 %;  option 2: 30%
Project outline 7 %
Project writeup 20 %  (10% instructor; 10% peer)
+ up to 2 bonus marks
Peer Review of Other Students' Final Project Papers 3 %
Participation in Discussions; Attendance 10 %

 

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 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 three or 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

CPSC 532A will culminate with a final project that allows students to explore material that was not covered in class and to share that material with other students.  The project involves students writing a paper on a topic of interest within Multiagent Systems, and then reading and evaluating each other's papers.  Here is the "pipeline":
  • submit a one-page outline of the paper you intend to write to the instructor
  • hand in the paper itself, which will be sent out to other students for peer review
  • perform peer review of papers from other students in the class

The topic of the final project need not be too ambitious; it's fine to perform a survey of a subarea in Multiagent Systems or a compare-and-contrast study of two or more influential papers.  If you plan to do more work in the area, you can also use the project to develop your own research ideas.  In future weeks a list of possible topics will appear in this space.  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

Roughly a dozen texts covering multiagent systems, game theory and microeconomic theory have been purchased by the CS reading room.  They are available in a special section, under the heading "game theory reading group".  Just ask the librarian if you can't find them!
 

  Schedule


Here is the tentative schedule for CPSC 532A. I'll try to keep this schedule up to date.  Slides from each lecture may be accessed by clicking on the links under "lecture topic"; applicable section numbers from the textbook are also given. Assignment and project due dates will be added throughout the term. 

 

Date Lecture Topic  (textbook sections) Milestones
Tuesday, September 12 Introduction (Introduction)  
Thursday, September 14 Utility Theory ( 3.1, Appendix C)  
Tuesday, September 19 Game Theory Intro ( 3.2 - 3.2.3)  
Thursday, September 21 Pure-Strategy Nash Equilibria ( 3.2.3 - 3.2.4)  
Tuesday, September 26 Mixed Strategies and Nash Equilibria ( 3.2.1)  
Thursday, September 28 Maxmin, Dominance ( 3.3.2 - 3.3.3, 4.1, 4.6, App D)  
Tuesday, October 3 Domination and Computational Issues ( 3.3.3, 4.7)  
Thursday, October 5 Correlated Equilibrium ( 3.3.6, 4.8, 5.1 - 5.1.2) Homework 1 out.
Tuesday, October 10 PIEF Games and Subgame Perfection ( 5.1 - 5.1.3)  
Thursday, October 12 Backward Induction and IIEF games ( 5.1.4 - 5.2.2)  
Tuesday, October 17 Perfect Recall; Repeated games ( 5.2.2; 6.1 - 6.1.2)  
Thursday, October 19 The Folk Theorem ( 6.1.2) Hw 1 due; Hw 2 out
Tuesday, October 24 Stochastic Games; Bayesian games ( 6.2, 6.3.1)  
Thursday, October 26 Analyzing BGs; Social choice ( 6.3.2, 7.1 - 7.3)  
Tuesday, October 31 Social choice, Arrow's Theorem ( 7.4 - 7.5)  
Thursday, November 2 Arrow's Theorem; Mechanism design ( 7.5 - 8.2) Homework 2 due
Tuesday, November 7 Midterm exam  
Thursday, November 9 Mechanism design, Quasilinear utility ( 8.2 - 8.5)  
Tuesday, November 14 Risk attitudes; Groves mechanism ( 8.5 - 8.6) Project proposals due
Thursday, November 16 VCG ( 8.6 - 8.7)  
Tuesday, November 21 Auctions intro ( 9.1) Homework 3 out
Thursday, November 23 Auction theory I ( 9.2 - 9.2.3)  
Tuesday, November 28 Auction theory II ( 9.2.4 - 9.2.9)  
Thursday, November 30 Multiunit and Combinatorial Auctions ( 9.3 - 9.4)  
  • Homework 3 due: December 4, 3 PM (bring to main office and get it time-stamped, or else submit electronically)
  • Final exam: December 10, 4:00 PM until December 12, 4:00 PM (take-home exam; paper or electronic submission)
  • Projects due: December 27 11:59:59 PM (electronic submission)
  • Project reviews due: January 22, 5 PM (physical submission please!)
  Handouts