Foundations of Multiagent Systems**
(CPSC 532L, Term 2,
Session 201, 2013-14)**

Overview | Grades | Presentations | Text | Schedule |

**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. It will use a "flipped classroom" model in which lectures will be delivered online. Classes will emphasize student participation. The first class of a week will focus on reinforcing and applying material covered in the videos. The second class of a week will consist of student presentations on enrichment topics, which will be peer evaluated and discussed afterwards.

**Term:** 2

**Meeting Times: **Tuesday, Thursday, 2:00 - 3:30 PM

**First Class: **Tuesday, January 7, 2014

**Location:** ICCS 206

**Instructor:** Kevin Leyton-Brown

**Instructor's Office Location:** ICCS X565

**Office Hours: **Tuesday, Thursday, 3:30 - 4:00 PM, or by appointment

**Video Lectures Available From:** Youtube; Coursera
(I);
Coursera (II)

**
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- and multi-good
auctions.

**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 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 presentations, you must
cite all external sources that you use, and the vast majority of the
slides 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
weekly structure.

Before first class |
Watch the week's videos. Hand in the previous week's assignment electronically. |

First class |
We'll begin with a quiz on the material covered in videos. We'll swap quizzes and peer-grade, discussing concepts as we go. We'll have an opportunity for open discussion of the lecture material. Then I'll cover related material and we'll have a chance to apply what we've learned with challenge problems and games. |

Second class |
Student presentations on enrichment topics. Each student has about 20 minutes to present, followed by discussion of both the material and the presentation itself. Remaining time will be devoted to discussion of the previous week's assignment and help with/group work on the current week's assignment. |

We'll start out with the first class being a Tuesday and the second being a Thursday. The midterm will be on a Tuesday. After that, the first class of a week will be a Thursday and the second will be a Tuesday. The term ends on a Tuesday.

**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.*

Quizzes (weekly; we'll keep your 10 best grades) | 10 % |

Assignments (weekly) | 20 % |

Midterm | 15 % (or 7 %) |

Final | 20 % (or 28 %, if better and final >= 80%) |

Presentation | 20 % (10% instructor; 10% peer) |

Peer Review of Other Students' Presentations | 5 % |

Participation in Discussions; Attendance | 10 % |

**Curving Grades and Peer Review: **Final grades may be curved to
give the overall distribution of grades a desired mean and standard
deviation. Peer
review is an important component of the class, and will be taken into
account when evaluating presentations. 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 reviews of other students.

**Assignments:** The course will include weekly assignments,
given out at the second class of the week (e.g., Thursday) and due an hour before
the following week's first class (e.g., Tuesday).
Assignments must be prepared using LATEX and submitted electronically.
Assignments will not be weighted equally: weighting will be
proportional to the total number of available points. Students will be
given five 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 1:00 PM on the second class of the week it was due.

**The list of candidate topics is available here.**In the second class of the term, we'll have an auction to assign students to topics from the first few weeks; we'll assign the rest of the topics after the drop date.

Presentations should be about 20 minutes long. Topics must be chosen from the assigned list or negotiated with me. The goal is to give you the chance to research and dig deeper into a topic that interests you. Each presentation should include at least one interactive activity or puzzle for students to solve.

Presentations will be peer evaluated. After each presentation is complete, we'll have a discussion about the presentation itself (what worked, what didn't) and the subject matter it covered (clarifications, elaborations).

The grading form used for (peer/) evaluation of presentations is available here.

- 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, Second Edition*, Elsevier, 2009.

Week |
Dates |
Topic
(click for videos) |
Presentations |
Links |

0 | Jan 7, 9 | Course overview | Giving effective presentations | |

1 | Jan 14, 16 | Normal-form games | Utility theory; Congestion games (tex) | Assg1 |

2 | Jan 21, 23 | Mixed Nash equilibrium | Price of Anarchy; Equilib'm Refinements | Assg2 |

3 | Jan 28, 30 | Alternate solution concepts | Solution Concepts; Behavioral GT | Assg3 |

4 | Feb 4, 6 | Extensive-form games | Sequence Form | Assg4 |

5 | Feb 11, 13 | Repeated games | Backward Induction; Multiagent RL | Assg5 |

Feb 25 | Midterm |
|||

6 | Feb 27, Mar 4 | Coalitional games | Compact Representations | Assg6 |

7 | Mar 6, 11 | Social choice | Ranking Systems | Assg7 |

8 | Mar 13, 18 | Bayesian games | Predicting Human Behavior | Assg8 |

9 | Mar 20, 25 | Mechanism design | (no Tuesday class this week) | Assg9 |

10 | Mar 27, Apr 1 | Efficient mechanisms | Bipartite Matching; Bandwidth Allocation | Assg10 |

11 | Apr 3, 8 | Auctions | Incentive Auctions | |

Apr 15 | Final exam (1 PM - 4 PM) |