CSE 516A: Fall 2019

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

CSE 516A: Multi-Agent Systems

Fall 2019

ANNOUNCEMENTS

Homework 3 is posted. Due December 6. Gradescope instructions are available.

The final project handout is posted.

Welcome to Multi-Agent Systems! We will meet on Tuesdays and Thursdays at 2:30 PM in Cupples I, Room 207. The first meeting will be on the 27th of August.

We will be using Piazza for questions, discussions, and classroom participation.

We will be using Gradescope (linked directly to Canvas, so you should be able to use it if you are enrolled in the class) for homework submission and grading of homeworks and exams.

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 from 3:50-5:00 (right after class, starting in Cupples I and moving back to Jolley 512), and by appointment.

TAs: There are two (fantastic!) TAs for the class: Parvathi Narayan (pnarayan at wustl) and Alex DiChristofano (a.dichristofano). The TAs will hold regular office hours, grade, and answer questions on Piazza.

The TA office hours are Wednesdays from 2-4 in Urbauer 214 (Parvathi) and Fridays from 1-3 in Jolley 224 (Alex)

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.

Course Syllabus

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.

SLB: Multiagent Systems, Yoav Shoham and Kevin Leyton-Brown. Cambridge University Press.

NRTV: Algorithmic Game Theory (look under the "Resources" tab for a PDF download), N. Nisan, T. Roughgarden, E. Tardos and V.V. Vazirani, eds. Cambridge University Press.

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, and ability to reason algorithmically and code fluently. 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 2:30 PM to 3:50 PM in Cupples I Room 207.

Date	Topics	Readings	Extras
Aug 27	Introduction. Course policies. Course overview.	Lecture notes
Aug 29	The assignment problem. The auction algorithm.	SLB Section 2.3.2
Sep 3	(Brief) introduction to linear programming and duality.	SLB Appendix B. Chapter 7 of Algorithms (Dasgupta et al).	GNU Linear Programming Kit. We have posted some installation tips on Piazza.
Sep 5	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
Sep 10	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 Stable matchings and linear programming (Vohra, 2012)
Sep 12	LP formulation of stable matching, contd. Housing with endowments and the Top Trading Cycles algorithm. Intro to school choice and the Boston Mechanism	Incentive compatibility in a market with indivisible goods (Roth, 1982)	HW1 out Gradescope instructions
Sep 17	School choice continued. The Boston Mechanism, Deferred Acceptance, and Top Trading Cycles	The Boston Public School Match (Abdulkadiroglu et al, 2005)
Sep 19	Guest lecture by Sujoy Sikdar on fair division.	Slides
Sep 24	Preferences and von Neumann-Morgenstern utilities. Risk-aversion and log utilities.	SLB Section 3.1	See Piazza for link to MASeCoin spreadsheet
Sep 26	Intro to game theory: Pareto-optimality and strict dominance.	NRTV Sections 1.1-1.3. SLB Section 3.3.1
Oct 1	Game theory, contd.: Nash equilibrium.	SLB Sections 3.3 and 4.5 (excluding 4.5.2)
Oct 3	Mixed strategy Nash equilibria contd. Congestion games.	NRTV Section 1.3. SLB Sections 3.3.2, 6.4.1
Oct 8	Congestion games and potential games.	SLB Sections 6.4.2-6.4.3
Oct 10	Correlated equilibrium. Sequential games and subgame perfection.	SLB 5.1, NRTV 1.3.6, 1.5	HW2 out
Oct 17	Games of imperfect information. Sequential equilibrium.	SLB 5.2.1, 5.2.2, 5.2.4. Game trees from lecture (from David Kreps' book)
Oct 22	Games of incomplete information. Bayes-Nash equilibrium.	SLB 6.3.
Oct 24	Bayes Nash equilibrium continued. Analyzing first-price auctions as Bayesian games.	Easley and Kleinberg, Chapter 9 (especially 9.7)
Oct 29	More analysis of standard auctions (second-price, first-price, all-pay) as Bayesian games.	Easley and Kleinberg, Chapter 9 (especially 9.7). SLB 11.1.2-11.1.4
Oct 31	Standard auctions and revenue equivalence. Intro to computing equilibria in 2-player zero-sum games.	SLB 11.1.5, 3.4.1
Nov 5	Midterm review
Nov 7	Midterm
Nov 12	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
Nov 14	Ben-Gurion's Tri-Lemma	Paper by James Stodder
Nov 19	Intro to social choice theory and Arrow's impossibility theorem.	SLB 4.1, 4.2.1, 4.2.2. NRTV 9.1 and 9.2. SLB 9.1-9.3. Third proof in Geanakoplos' paper.
Nov 21	Single-peaked preferences and the median voter theorem. Manipulation and the Gibbard-Satterthwaite theorem.	NRTV 10.1 and 10.2. SLB 9.4.
Nov 26	Mechanism design and VCG mechanisms.	NRTV 9.2-9.3	HW3 out
Dec 3	VCG mechanisms contd. Sponsored search.	Edelman, Ostrovsky, and Schwartz (2007) Amazon bidding war blogpost
Dec 5	Final Jeopardy!