CPSC 532L  Multiagent Systems
[ Overview  Grades  Final Project  Texts  Schedule  Handouts]Term: 1
Meeting Times: Tuesday and Thursday, 2:00  3:30 PM
First Class: Tuesday, January 15, 2008
Location: DMP 101
Instructor: Kevin LeytonBrown
Instructor's Office Location: CICSR 185
Office Hours: Tuesday and Thursday 3:30  4:00, or by appointment
Mailing List: in your UNIX account, type "
echo subscribe  mailx cpsc532arequest"
Course Topics: Overall, problems at the interface of economic theory and computer science. (No prior experience in economics is assumed.) Specific topic include: Games: normalform; extensiveform; repeated; stochastic; Bayesian. Computation of gametheoretic solution concepts. Mechanism design: key positive and negative results. Singlegood 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
noncourse materials that are acceptable.
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 inclass)  option 1: 20 %; option 2: 10% 
Test 2 (probably takehome)  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.
 submit a onepage 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 compareandcontrast 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.
 Y. Shoham and K. LeytonBrown, Multiagent Systems: Algorithmic, GameTheoretic, and Logical Foundations, Cambridge University Press, 2008
Another good general text for exploring more advanced material in the research area, written largely from a CS theory perspective, is the following edited volume:
 N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani (Eds.), Algorithmic Game Theory, Cambridge University Press, 2007
If you'd like to do additional reading on Game Theory, I recommend the following supplemental books:
 D. Fudenberg and Tirole, Game Theory, MIT Press, 1991
 M. Osborne and A. Rubinstein, A Course in Game Theory, MIT Press, 1994
 J. Nocedal and S. Wright, Numerical Optimization, Springer, 1984
 V. Krishna, Auction Theory, Elsevier, 2002
Slides from each lecture may be accessed by clicking on the links under "lecture topic"; applicable section numbers from the textbook are also given. Slides will not necessarily be available in advance; however, last year's slides can be accessed from last year's course webpage. Assignment and project due dates will be added throughout the term.
Date  Lecture Topic (textbook sections)  Milestones 
January 15  Introduction (§ Introduction)  
January 17  Utility Theory and Game Theory Intro (§ 3.1  3.2)  
January 22  From Optimality to Equilibrium (§ 3.2  3.3)  
January 24  Mixed Strategies; Maxmin (§ 3.3  3.4.1, )  
January 29  Computing Maxmin; Domination (§ 4.1, 4.4, 3.4.3, Appendix B)  Assg 1 released 
January 31  Computing Domination; Correlated Equilibrium (§ 4.5, 3.4.5)  
February 5 
Computing CE; PerfectInformation ExtensiveForm
games (§ 4.6, 5.1  5.1.3) 

February 7 
Backward Induction;
Imperfect
Information
Extensiveform games
(§ 5.1.4  5.2.2) 

February 12  Repeated Games and the Folk Theorem (§ 6.1  6.1.2)  Assg 1 due 
February 14  Stochastic Games; Bayesian games (§ 6.2, 6.3.1)  
February 26  Analyzing Bayesian Games; Social choice (§ 6.3.2, 9.1  9.3)  Assg 2 released 
February 28  Arrow's Impossibility Theorem (§ 9.4  9.5)  
March 4  Mechanism Design (§ 9.5  10.1)  
March 6  Revelation Principle; Quasilinear utility (§ 10.2  10.3.2)  
March 11  Quasilinear Mechanism Design; Groves (§ 10.3.2  10.4.1)  Assg 2 due 
March 13  The VCG Mechanism (§ 10.4.2  10.4.4)  
March 18  Midterm exam  
March 20  Advanced Mechanism Design (§ 10.4.5  10.7)  
March 25  SingleGood Auctions (§ 11.1  11.1.3)  Outline due 
March 27  Revenue Equivalence (§ 11.1.4  11.5)  Assg 3 released 
April 1  Advanced SingleGood; Multiunit Auctions (§ 11.1.6  11.2)  
April 3  Combinatorial Auctions (§ 11.3)  
April 8  Coalitional Game Theory Intro (§ 12.1)  
April 10  The Shapley Value and the Core (§ 12.2)  Assg 3 due 
Projects: use LaTeX article format, standard margins, 610 pages. Due date: April 24, 10:00 PM.
Peer reviews of projects: due April 29, 11:59 PM.
 Assignment 1
 Assignment 1 solutions
 Assignment 2
 Assignment 2 solutions
 Assignment 3
 Assignment 3 solutions
 Final exam: available from 4/15/08, 2:10 PM. Due 4/17/08, 2:10 PM.
 Final papers: as discussed in class, students had the
option of submitting their projects anonymously. Thus, some of
the projects below have names, and others are anonymized.
 Paper grading scheme. Please grade the projects using this scheme, and hand in your graded reviews by April 29, 11:59 PM either in person or electronically. (If you submit physical copies, you can bring them to the CS office the morning of April 30.)
 Anonymous 1
 Anonymous 2
 Anonymous 3
 Anonymous 4
 Anonymous 5
 Anonymous 6
 Brad
 Petcharat
 Guillaume
 Kevin
 Mahdi
 Jonatan