- Office hours: Tuesdays, 2pm-3pm, 212 CS
- Office Hours: Tuesdays, 1pm-2pm, 001A CS| Instructors: | Xi Chen
-
- Office hours: Tuesdays, 2pm-3pm, 212 CS
|
| Alex Fabrikant
-
- Office Hours: Tuesdays, 1pm-2pm, 001A CS |
Please note: this is an informal course; those taking the course will not receive course credit. The course is open to all.
Prerequisites: general mathematical maturity appropriate for CS grad students; 1 semester of undergraduate algorithms & 1 semester of undergraduate complexity; please contact the instructors if you are not sure whether you are ready to take this course
Recommended textbook: Algorithmic Game Theory, ed. by Nisan, Roughgarden, Tardos, and Vazirani, ISBN 978-0-521-87282-9. A hard copy is available in the Theory Lab (but may not be removed from that room). An online version of the book is also publicly accessible, thanks to the publisher, Cambridge Press. The directions are on Tim Roughgarden's homepage
Scribe notes: As long as there are volunteers to write scribe notes, we will edit them and post them below. Use this LaTeX template to write scribe notes. It assumes that you have the AMS packages and algorithm/algorithmic installed (if it compiles, you're set). If you want, you can use it with the TeX installation on penguins.cs.princeton.edu, which has all the relevant packages.
| Date | Topics | Reading (by default, in the AGT book) | Exercises |
| Thu 02/05 | Intro, pure Nash equilibria, Price of Anarchy and Price of Stability, a global network connection game [ PS ] [ PDF ] | Recommended: 1.1-1.3.3; 17.1; 19.3.1
Further reading:
|
Problem set 1 |
| Fri 02/06 | Selfish source routing, congestion games, potential functions [ PS ] [ PDF ] | Recommended:
|
|
| Thu 02/12 | Games and TFNP; Complexity of finding pure Nash equilibria, PLS; mixed and correlated equilibria | Recommended:
|
|
| Fri 02/13 | PPAD and complexity of finding mixed Nash equilibria | Recommended:
Further reading:
|
|
| Thu 02/19 | Introduction to Mechanism Design | Recommended: Ch. 9.1-9.3 Further reading: Rest of Ch. 9 |
|
| Fri 02/20 | Distributed Algorithmic Mechanism Design | Recommended:
|
|
| Thu 02/26 | Combinatorial suctions and profit maximization | Roughly, Ch. 11 and 13 | |
| Fri 02/27 | Guest lecture by Umar Syed on Game Theory and Learning |
Recommended: Freund and Schapire, Game Theory, Online Prediction, and Boosting, in COLT 1996 | |
| Thu 03/05 | Cost sharing mechanisms | Roughly, Ch. 15 |
We will introduce the main concepts in most major sub-areas of algorithmic game theory, both theoretical and applied: standard equilibrium concepts, Price of Anarchy and similar metrics, several well-established game-theoretic models of networks, computational complexity of finding equilibria, algorithmic mechanism design, combinatorial auctions, sponsored search auctions, and cost sharing. Our mission is to present the research landscape of AGT, and have those taking the course be able, by the end, to read and understand the bulk of current papers in AGT (e.g. in the EC conference), which should be sufficient for getting involved in current AGT research.
The target audience is grad students both in theory and in networking, with the prerequisites being general mathematical maturity appropriate for CS grad students, and the equivalent of roughly 1 undergrad-level course in algorithms and 1 in complexity.
The topics will essentially not overlap with COS 444, Ken Steiglitz's undergraduate-targeted course on Internet Auctions, which is also being taught this semester.