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


CSE 516A: Multi-Agent Systems

Spring 2018

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: Mondays from 2-3 PM, and by appointment.

TAs: There are three (fantastic!) TAs for the class: Sirui Li (sirui.li), Gwyneth Pearson (gpearson), and Angelica Tao Zhu (angelica.tao). The TAs will hold regular office hours, grade homeworks, and answer questions on Piazza.

The office hour schedule is as follows:
Mondays 2:00-3:00 (Sanmay, Jolley 512)
Wednesdays 4:00-6:00 (Gwyneth, Jolley 224)
Thursdays 1:00-3:00 (Angelica, Jolley 224)
Fridays 4:15-6:15 (Sirui, Jolley 224)

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 Hillman 60.
Date Topics Readings Extras
Jan 16 Introduction. Course policies. Course overview. Lecture notes
Jan 18 The assignment problem. The auction algorithm. SLB Section 2.3.2
Jan 23 (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 25 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 30 Two-sided matching, contd. Proposer optimality. LP formulation of stable matching. SLB Section 10.6.4 (through Theorem 10.6.13).
Feb 1 LP formulation of stable matching, contd. Housing with endowments and the Top Trading Cycles algorithm. Intro to preferences. The first two pages of Stable matchings and linear programming (Vohra, 2012). Incentive compatibility in a market with indivisible goods (Roth, 1982)
Feb 6 No class. Sanmay at AAAI. HW1 out
Feb 8 Preferences and von Neumann-Morgenstern utilities. SLB Section 3.1
Feb 13 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 15 Game theory, contd.: Nash equilibrium. SLB Sections 3.3 and 4.5 (excluding 4.5.2)
Feb 20 Mixed strategy Nash equilibria contd. Congestion games. NRTV Section 1.3. SLB Sections 3.3.2, 6.4.1
Feb 22 Congestion games and potential games. Correlated equilibrium. SLB Sections 6.4.2-6.4.3, NRTV Sections 1.3.6
Feb 27 Sequential games and subgame perfection. SLB 5.1, NRTV 1.5
Mar 1 Games of imperfect information. Sequential equilibrium. SLB 5.2.1, 5.2.2, 5.2.4. Game trees from lecture (from David Kreps' book) HW2 out
Mar 6 Games of incomplete information. Bayes-Nash equilibrium. SLB 6.3.
Mar 8 Bayes Nash equilibrium continued. Analyzing first-price auctions as Bayesian games. Easley and Kleinberg, Chapter 9 (especially 9.7)
Mar 20 Computing equilibria in 2-player zero-sum games. General sum games and linear complementarity problems SLB 3.4.1, 4.1, 4.2.1, 4.2.2
Mar 22 Ben-Gurion's Tri-Lemma Paper by James Stodder
Mar 27 Midterm review
Mar 29 Midterm
Apr 3 Midterm discussion. Intro to social choice theory SLB 4.1, 4.2.1, 4.2.2. NRTV 9.1 and 9.2. SLB 9.1-9.3
Apr 5 Arrow's impossibility theorem. Single-peaked preferences and the median voter theorem. Third proof in Geanakoplos' paper. NRTV 10.1 and 10.2.
Apr 10 The Gibbard-Satterthwaite theorem. Mechanism design and VCG mechanisms. SLB 9.4. NRTV 9.2-9.3
Apr 12 VCG mechanisms. NRTV 9.3 HW3 out
Apr 17 Guest lecture by Peter Hovmand on Prevention and Systems See Piazza for link to slides
Apr 19 Mechanism design, contd. Sponsored search. Edelman, Ostrovsky, and Schwartz (2007)
Apr 26 Final Jeopardy!