Department of Computer Science and Engineering

- The final project handout is available, as is the code base for Suggestion 1. Project writeups are due May 8.
- Homework 3 is now available. Due April 20.
- Welcome to Multi-Agent Systems! We will meet on Tuesdays and
Thursdays at 11:30 AM in
**Louderman 458**. The first meeting will be on the 17th of January. - We will be using a Piazza page for questions, discussions, and classroom participation.

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) |

- 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.

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 |