CSE 516A: Spring 2014

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

CSE 516A: Multi-Agent Systems

Spring 2015

ANNOUNCEMENTS

Homework 4 is posted, along with the code base. Due April 28.

We will use Piazza for discussions and questions. This will serve as a permanent announcement linking to the Piazza page.

Welcome to Multi-Agent Systems! We will meet on Tuesdays and Thursdays at 11:30 AM in Green Hall L0160. The first meeting will be on the 13th of January.

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 510
Office hours: Thursdays from 1:30-3:30, and by appointment.

TA:
Mark Heimann (mheimann at wustl dot edu)
Office hours: Mondays from 5:30-7:30 (ACM Lounge: Urbauer 114)

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 , N. Nisan, T. Roughgarden, E. Tardos and V.V. Vazirani, eds. Cambridge University Press.

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 Green Hall, Room L0160.

Date	Topics	Readings	Extras
Jan 13	Introduction. Course policies. Course overview.	Lecture notes
Jan 15	The assignment problem. The auction algorithm.	SLB Section 2.3.2
Jan 20	The assignment problem (contd.). Brief intro to linear programming and duality.	SLB Appendix B. Chapter 7 of Algorithms (Dasgupta et al)	GNU Linear Programming Kit. Some installation tips will be on the Piazza site.
Jan 23	LP formulation of the assignment problem. Stable matching	SLB Section 10.6.4 (through Theorem 10.6.13). The first two pages of this paper are also useful and concise.	HW1 out.
Jan 27	Proposer optimality in stable matching. LP formulation of stability. Preferences and von Neumann--Morgenstern utilities	Readings from previous lecture + SLB Section 3.1
Jan 29	Proof of the von Neumann--Morgenstern theorem. Risk-aversion and log utilities.	SLB Section 3.1
Feb 3	Intro to game theory	Chapter 2 of Parkes & Seuken (see Piazza); NRTV Sections 1.1-1.3	Chapter 1 of Parkes and Seuken
Feb 5	Nash equilibria and dominance solvability.	Same as above, plus SLB Sections 3.3 and 4.5 (excluding 4.5.2)
Feb 10	Mixed equilibrium. Congestion games.	Same as above.
Feb 12	Potential games. Correlated equilibrium.	Parkes and Seuken 2.8 + NRTV 1.3.6 + SLB 3.4.5
Feb 17	Sequential games and subgame perfect equilibrium.	NRTV 1.5, SLB 5.1	HW2 out.
Feb 19	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 24	Bayesian games (incomplete information).	SLB 6.3, Easley and Kleinberg Chapter 9 (especially 9.7).
Feb 26	Auctions as incomplete information games.	Same as above.
Mar 3	Wrapping up auctions; Ex-post equilibria; Maxmin and minmax strategies and solving 2-player zero-sum games	SLB 6.3.4, 3.4.1, 4.1.
Mar 5	Solving 2-player zero-sum games, contd. Ben-Gurion's Tri-Lemma.	Lecture notes Paper for the Ben-Gurion's "tri-lemma" experiment
Mar 17	Intro to social choice. Arrow's impossibility theorem.	NRTV 9.1 and 9.2.
Mar 19	Midterm
Mar 24	Midterm discussion. Single-peaked preferences.	NRTV 9.2, 10.1, 10.2; SLB 9.1-9.4.
Mar 26	The Gibbard-Satterthwaite theorem. VCG Mechanisms	NRTV 9.2; SLB 9.4. NRTV 9.3.	Conitzer's CACM Paper: Making Decisions Based on the Preferences of Multiple Agents
Mar 31	No class.
Apr 2	VCG Mechanisms, continued.	NRTV 9.2, 9.3	HW3 out
Apr 7	VCG mechanisms for public goods, sponsored search.	NRTV 9.3, Edelman, Ostrovsky, and Schwartz, AER 2007
Apr 9	Sponsored search, contd. Intro to prediction markets	Wolfers and Zitzewitz, JEP 2004
Apr 14	Scoring rules and market 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	HW4 out. Code base Savage, JASA 1971 (the original paper on scoring rules)
Apr 16	Combinatorial markets. Market-making more generally, and double auction markets.	Combinatorial markets: Background, plus Sections 1 and 2 of Chen et al, 2007 CDAs, call auctions and market making: Sections 1 and 2 of Das, 2008, plus Parsons et al, 2006 (particularly Sections 1 and 2).
Apr 21	Asymmetric information and the market for lemons. Application to market-making.	Easley and Kleinberg Sections 22.4-22.6. Section 3 of Das, 2008
Apr 23	Final jeopardy!