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


CSE 516A: Multi-Agent Systems

Spring 2017

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: Jolley 512
Office hours: Thursdays 1:30-2:30, and by appointment.

TAs: There are several (fantastic!) TAs for the class: Patrick Chao (pengningchao at wustl), Yuan Gao (gao.yuan at wustl), Anna Gautier (annagautier at wustl), Renee Mirka (mirkare at wustl), and Yao Yuan (yyuan25 at wustl). The TAs will hold regular office hours, grade homeworks, and answer questions on Piazza.

The office hour schedule is as follows:
Mondays 2:30-4:00 (Renee, Jolley 517)
Tuesdays 1:00-2:30 (Anna, Jolley 517)
Wednesdays 3:00-4:30 (Patrick, Jolley 431 (except Feb 22))
Thursdays 1:30-2:30 (Sanmay, Jolley 512)
3:00-4:30 (Yuan, Urbauer 116)
Fridays 11:30-1:00 (Yao, Jolley 408)

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 247, ESE 326 (or Math 3200), and Math 233 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 17 Introduction. Course policies. Course overview. Lecture notes
Jan 19 The assignment problem. The auction algorithm. SLB Section 2.3.2
Jan 24 (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 26 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
Jan 31 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 HW1 out
Feb 2 Preferences and von Neumann-Morgenstern utilities. SLB Section 3.1
Feb 7 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 9 Game theory, contd.: Nash equilibrium. SLB Sections 3.3 and 4.5 (excluding 4.5.2)
Feb 14 Mixed strategy Nash equilibria contd. Congestion games. NRTV Section 1.3. SLB Sections 3.3.2, 6.4.1
Feb 16 Congestion games and potential games. Correlated equilibrium. SLB Sections 6.4.2-6.4.3, NRTV Sections 1.3.6
Feb 21 Sequential games and subgame perfection. SLB 5.1, NRTV 1.5 HW2 out
Feb 23 Games of imperfect information. Sequential equilibrium. SLB 5.2.1, 5.2.2, 5.2.4. Game trees from lecture (from David Kreps' book)
Feb 28 Games of incomplete information. Bayes-Nash equilibrium. SLB 6.3.
Mar 2 Analyzing auctions as Bayesian games. Easley and Kleinberg, Chapter 9 (especially 9.7)
Mar 7 Ex-post BNE. Computing equilibria in 2-player zero-sum games. SLB 6.3.4, 3.4.1, 4.1
Mar 9 Ben-Gurion's Tri-Lemma Paper by James Stodder
Mar 21 Midterm review
Mar 23 Midterm
Mar 28 Linear complementarity problems and computing solutions to non-zero-sum games. Intro to social choice theory SLB 4.1, 4.2.1, 4.2.2. NRTV 9.1 and 9.2.
Mar 30 Midterm discussion. Arrow's impossibility theorem. Third proof in Geanakoplos' paper
Apr 4 The median voter theorem. The Gibbard-Satterthwaite theorem. NRTV 10.1 and 10.2; SLB 9.1-9.4. HW3 out
Apr 6 No class. Sanmay at SGB meeting.
Apr 11 Mechanism design and VCG mechanisms. NRTV 9.3
Apr 13 Mechanism design, contd. Sponsored search. Edelman, Ostrovsky, and Schwartz (2007)
Apr 18 Scoring rules and markets 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 20 Financial markets and prediction markets Wolfers and Zitzewitz, JEP 2004.
Apr 25 Market microstructure, and problems with mechanisms
Apr 27