CSE 516A: Spring 2014

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

CSE 516A: Multi-Agent Systems

Spring 2014

ANNOUNCEMENTS

Homework 4 and support code are posted.

Homework 3 is posted.

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 Cupples II L015 (note: not Green, as originally assigned). The first meeting will be on the 14th 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 2-3:30, and by appointment.

TAs:
Mithun Chakraborty (mithunchakraborty at wustl dot edu)
Allen Lavoie (allenlavoie at wustl dot edu)

Recitations: Fridays from ~~10-11~~ 9-10 AM and 1:30-2:30 PM.
Office hours: Mondays from 1-2 PM and Wednesdays from 2-3 PM (Jolley 507)

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 readings from the academic literature. 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.

A third book that we may use on occasion (and that has much of the material we will study presented at a more elementary level), is Networks, Crowds, and Markets, D. Easley and J. Kleinberg. Cambridge University Press. The pre-publication draft is perfectly usable.

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 Cupples II, Room L015.

Date	Topics	Readings	Extras
Jan 14	Introduction. Course policies. Course overview.	Lecture notes
Jan 16	The assignment problem. The auction algorithm.	SLB Section 2.3.2
Jan 21	Brief intro to linear programming and duality. LP formulation of the assignment problem.	SLB Appendix B. Chapter 7 of Algorithms (Dasgupta et al)	GNU Linear Programming Kit. Some installation tips are on the Piazza site.
Jan 23	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 28	Preferences and von Neumann--Morgenstern utilities	SLB Section 3.1
Jan 30	Intro to game theory	Chapter 2 of Parkes & Seuken (see Piazza); NRTV Sections 1.1-1.3	Chapter 1 of Parkes and Seuken
Feb 4	Dominance solvability and mixed strategies.	Same as above
Feb 6	Potential and congestion games. Correlated equilibrium.	Same as above + SLB 3.4.5
Feb 11	Sequential games and subgame perfect equilibrium.	NRTV 1.5, SLB 5.1
Feb 13	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.
Feb 18	Bayesian games (incomplete information).	SLB 6.3, EK Chapter 9 (especially 9.7).
Feb 20	Auctions as incomplete information games.	Same as above.
Feb 25	Ex-post equilibria; Maxmin and minmax strategies and solving 2-player zero-sum games; Ben-Gurion's tri-lemma. Extras: Perfect Bayesian equilibria and brief discussion of the complexity of computing Nash equilibria in general.	SLB 6.3.4, 3.4.1, 4.1.	Paper for the Ben-Gurion's "tri-lemma" experiment
Feb 27	Intro to social choice. Arrow's impossibility theorem.	NRTV 9.1 and 9.2.
Mar 4	Midterm
Mar 6	Midterm discussion and feedback.
Mar 18	Social choice continued: single-peaked preferences and the Gibbard-Satterthwaite theorem.	NRTV 9.2, 10.1, 10.2; SLB 9.1-9.4.	Conitzer's CACM Paper: Making Decisions Based on the Preferences of Multiple Agents
Mar 20	Finish up Gibbard-Satterthwaite. VCG Mechanisms.	NRTV 9.2, 9.3
Mar 25	VCG Mechanisms, continued.	NRTV 9.2, 9.3
Mar 27	VCG mechanisms for public goods, sponsored search.	NRTV 9.3, Edelman, Ostrovsky, and Schwartz, AER 2007	HW3 out
Apr 1	Prediction markets, continuous double auctions, and market-making.	Wolfers and Zitzewitz, JEP 2004, Sections 1 and 2 of Das, AAMAS 2008
Apr 3	Scoring rules and market scoring rules (Mithun).	Hanson, J. Pred. Markets 2007 (version from 2002), Sections 5.1 and 5.3 of Chen and Pennock, UAI 2007, NRTV 26.4.1	Savage, JASA 1971 (the original paper on scoring rules)
Apr 8	Market scoring rules, contd. The market for lemons.	Readings from previous lecture + EK 22.4-22.6.
Apr 10	No class.		HW4 and support code out
Apr 15	Behavioral economics 1 (Allen)	Rabin, J. Econ. Lit., 1998
Apr 17	Behavioral economics 2 (Allen): Hyperbolic discounting; badges	Laibson, QJE 1997; Anderson et al, WWW 2013
Apr 22	Novel uses of prediction markets	Cowgill et al, Working paper; Chakraborty et al, AAAI 2013
Apr 24	Final jeopardy!		Final exam out (on Piazza)