CPSC 532L - Foundations of Multiagent Systems
(Term 2, Session 201, 2012-13)
Meeting Times: Tuesday, Thursday, 3:30 - 5:00 PM
First Class: Thursday, January 3, 2013
Location: DMP 101
Instructor: Kevin Leyton-Brown
Instructor's Office Location: CS X565
Office Hours: Tuesday, Thursday, 5:00 - 5:30 PM, or by appointment
Video Lectures Available From: Coursera
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; coalitional; 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 do need to be able to construct and follow formal proofs. Relevant mathematical/CS background includes 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. As a result, 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, or the inappropriate use of an external source whether or not attribution is made. 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. For projects, you must cite all external sources that you use, and the vast majority of the project must be written in your own words. Any text that you take verbatim from another source must be in quotation marks and followed by a citation.
Flipped Classroom Structure: The course will follow the following
|Before Tuesday class||Watch the week's videos, on Coursera or locally at UBC. Hand in the previous week's assignment electronically.|
|Tuesday class||A lecture with high-level review of concepts from the week's videos. Enrichment lectures about concepts not covered online. Discussion, interactive activities.|
|Thursday class||A "lab" focusing on group work. We'll review the solutions to the previous week's assignment. Then we'll give you the next assignment (usually 1 or 2 questions) and you'll work in groups. Kevin and Dave/James will be there to offer help, hints, and advice about how to improve answers.|
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 (weekly)||20 %|
|Midterm||14 % (or 7 %)|
|Final||25 % (or 32 %, if better and final >= 80%)|
|Project outline||4 %|
|Project writeup||18 % (9% instructor; 9% peer)
+ up to 2 bonus marks
|Peer Review of Other Students' Final Project Papers||4 %|
|Participation in Discussions; Attendance||15 %|
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 weekly assignments,
given out Thursdays in class and due Tuesdays an hour before class.
Assignments must be prepared using LATEX and submitted electronically.
not be weighted equally: weighting will be proportional to the total number of available points. Students will be given three late days for use on the assignments; at most two can be used for any one assignment. 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. Once late days are used up, late assignments will be penalized at 20% per day. No assignment will ever be accepted after 2:30 PM Thursday of the week it was due.
- submit a one-page outline of the paper you intend to write
- 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. (Note, however, that even if you perform a survey, your project must be written entirely in your own words, and must do more than simply reiterate content from the papers you survey.) 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.
Your project should be written using the LaTeX document preparation system, which is the standard for writing research papers in computer science. Please use the "article" class file with default margins, 10 pt font; in this style, your project should be between 6-10 pages, not including your bibliography.
- Y. Shoham and K. Leyton-Brown, Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, Cambridge University Press, 2009.
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.
|0||Jan 3||Course overview (slides)|
|1||Jan 8, 10||Normal-form games (slides, slides)||Assg1 (pdf, tex)|
|2||Jan 15, 17||Mixed Nash equilibrium (slides, slides)||Assg2 (pdf, tex)|
|3||Jan 22, 24||Alternate solution concepts (slides, slides)||Assg3 (pdf, tex)|
|4||Jan 29, 31||Extensive-form games (slides, slides)||Assg4 (pdf, tex)|
|5||Feb 5, 7||Repeated games (slides)||Assg5 (pdf, tex)|
|6||Feb 12, 14||Bayesian Games (slides)||Assg6 (pdf, tex)|
|7||Feb 26, 28||Midterm; Project Outlines (slides)|
|8||Mar 5, 7||Coalitional games (slides)||Assg7 (pdf, tex)|
|9||Mar 12, 14||Social choice (slides)||Assg8 (pdf, tex)|
|10||Mar 19, 21||Mechanism design (slides)||Assg9 (pdf, tex)|
|11||Mar 26, 28||Efficient mechanisms (slides)||Assg10 (pdf, tex)|
|12||Apr 2, 4||Auctions (slides)|
|Apr 11||Final exam (2 PM - 5 PM; location TBA)|
|Apr 24||Final projects due (11:59 PM)||1; 2; 3; 4; 5; 6; 7|
|Apr 30||Peer evaluations due (11:59 PM)||Peer revew form|