20052006: CPSC 532A  Multiagent
Systems
Term: 1
Meeting Times: Tuesday and
Thursday, 2:00  3:30 PM
First Class: Tuesday,
September 13
Location: FSC 1617
Instructor: Kevin
LeytonBrown
Instructor's Office Location:
CICSR 185
Office Hours: To be announced 



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 seminarstyle discussion as well as traditional lectures, and gives 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: 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.




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.
Final Project Grading Scheme (showing percentages of overall grade)
Working in Pairs: Depending on the size of the class, students may be allowed to work with one partner on the final project. Students working in pairs will be judged to a higher standard than students working alone. I recognize that students working in pairs do not always do an equal amount of work. Students in a pair must decide between themselves how to divide the 80 total possible marks between them, with the constraint that each partner must get at least 30 points. (For example, if partners agree that points will be divided 35/45 and their project is awarded 30 points, then one partner will receive 26.5 points and the other will receive 33.75.) If the final grade is such that one student would receive more than 100%, the division will be readjusted so that that student receives exactly 100%. If students are unable to agree on a division, they must meet with the instructor and settle the division through "arbitration". 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 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. 



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":
The topic of the final project should either be a survey of a subarea in Multiagent Systems, a compareandcontrast 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 some 532A projects will develop into publishable work, as has happened in previous years. Please note that assignment late days cannot be applied to the final project.




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:
Good coverage of linear programming is given by:
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! 








