Washington University in St. Louis
Department of Computer Science and Engineering


CSE 516A: Multi-Agent Systems

Spring 2016

ANNOUNCEMENTS

OVERVIEW

This course introduces the fundamental techniques and concepts needed to study multi-agent systems, in which multiple autonomous entities with different information sets and goals interact. We will study algorithmic, mathematical, and game-theoretic foundations, and how these foundations can help us understand and design systems ranging from robot teams to online markets to social computing platforms. Topics covered may include game theory, distributed optimization, multi-agent learning and decision-making, preference elicitation and aggregation, mechanism design, and incentives in social computing systems.

STAFF

Instructor: Sanmay Das
Office: Bryan 307E
Office hours: Thursdays 2-3 PM, and by appointment.

TAs: There are several TAs for the class. Zhuoshu Li (zhuoshuli at wustl) will be the head TA and will conduct various recitation sessions as needed. Tony Ginart (tony.ginart at wustl), Robert Miller (millerrt at wustl), and Alicia Sun (sun.yi at wustl) will also serve as TAs. The TAs will hold regular office hours starting in the second week of class, grade homeworks, and answer questions on Piazza.

TA office hours will be held in Urbauer 114, the ACM Lounge. The complete office hour schedule is as follows (Sanmay's office hours will be in Bryan 307E):
Mondays 2:30 - 4:00 (Alicia)
Tuesdays 4:00 - 5:30 (Zhuoshu)
Wednesdays 2:30 - 4:00 (Tony), 4:00 - 5:30 (Robert)
Thursdays 2:00 - 3:00 (Sanmay)

POLICIES

Detailed policies are in the official syllabus. However, a couple of things are worth stressing. This will be taught as a graduate / upper level undergraduate class. I expect regular attendance and participation. I consider these essential parts of this class, and will grade accordingly.

TEXTBOOKS

There are two primary textbooks for this class. They will be supplemented with other readings that will be posted. They are both available free for on-screen use, or you can purchase copies.

PREREQUISITES

Prerequisites: CSE 240 and 241 and ESE 326 (or Math 320) or equivalents, or permission of instructor. Some prior exposure to artificial intelligence, machine learning, game theory, and microeconomics may be helpful, but is not required. Basically, I expect some mathematical maturity. If you are not comfortable with calculus and probability, you will have a hard time in this class.

CLASS

Class meets on Tuesdays and Thursdays from 11:30AM to 1:00PM in Louderman 458.
Date Topics Readings Extras
Jan 19 Introduction. Course policies. Course overview. Lecture notes
Jan 21 The assignment problem. The auction algorithm. SLB Section 2.3.2
Jan 26 (Brief) introduction to linear programming and duality. SLB Appendix B. Chapter 7 of Algorithms (Dasgupta et al). GNU Linear Programming Kit. We'll post some installation tips on Piazza.
Jan 28 LP form of the assignment problem. Two-sided matching. SLB Section 10.6.4 (through Theorem 10.6.13). The original Gale and Shapley paper HW1 out
Feb 2 Two-sided matching, contd. Proposer optimality. LP formulation of stable matching. SLB Section 10.6.4 (through Theorem 10.6.13). The first two pages of this paper
Feb 4 Preferences and von Neumann-Morgenstern utilities. SLB Section 3.1
Feb 9 Risk-aversion and log utilities. Intro to game theory: Pareto-optimality and strict dominance. NRTV Sections 1.1-1.3. SLB Section 3.3.1
Feb 11 Game theory, contd.: Nash equilibrium. SLB Sections 3.3 and 4.5 (excluding 4.5.2)
Feb 16 Mixed strategy Nash equilibria contd. Congestion and potential games. NRTV Section 1.3. SLB Sections 3.3.2, 6.4.1-6.4.3
Feb 18 Correlated equilibrium. Subgame perfection. SLB Sections 3.4.5, 5.1. NRTV Sections 1.3.6, 1.5.
Feb 23 Sequential games and subgame perfection, contd. Same as prior lecture. HW2 out
Feb 25 Games of imperfect information. Sequential equilibrium. SLB 5.2.1, 5.2.2, 5.2.4. Game trees from lecture (from David Kreps' book)
Mar 1 Games of incomplete information. Bayes-Nash equilibrium. SLB 6.3.
Mar 3 Analyzing auctions as Bayesian games. Easley and Kleinberg, Chapter 9 (especially 9.7)
Mar 8 Ex-post BNE. Computing equilibria in 2-player zero-sum games. SLB 6.3.4, 3.4.1, 4.1
Mar 10 More on computing equilibria in games. SLB 4.1, 4.2.1, 4.2.2
Mar 22 Ben-Gurion's Tri-Lemma and Intro to Social Choice. Paper by James Stodder
Mar 24 Midterm
Mar 29 Social choice and Arrow's impossibility theorem. NRTV 9.1 and 9.2.
Mar 31 Midterm debriefing. Arrow's theorem, contd. Single-peaked preferences. NRTV 9.2, 10.1, 10.2; SLB 9.1-9.4
Apr 5 Single-peaked preferences (contd). The Gibbard-Satterthwaite theorem. NRTV 9.2, 9.3; SLB 9.4
Apr 7 The Gibbard-Satterthwaite theorem (contd.) VCG mechanisms NRTV 9.2, 9.3.
Apr 12 The Clarke Pivot Rule. Examples of VCG Mechanisms. NRTV 9.3. HW3 out
Apr 14 Sponsored search. Paper on GSP by Edelman, Ostrovsky, and Schwartz (2007)
Apr 19 Financial and prediction markets. Wolfers and Zitzewitz, JEP 2004. Sections 1 and 2 of Das, 2008, plus Parsons et al, 2006 (particularly Sections 1 and 2).
Apr 21 Automated market-making and scoring rules. Hanson, J. Pred. Markets 2007 (version from 2002), Sections 5.1 and 5.3 of Chen and Pennock, UAI 2007, NRTV 26.4.1
Apr 26 Prediction markets wrap-up. Slides
Apr 28 Final Jeopardy!