Special Topics in Algorithmic Game Theory (MA5226)
TUM, Department of Mathematics, SS 2018
Lecturer: Yiannis Giannakopoulos
Teaching Assistant: Diogo Poças
Weekly hours: 2+1 (4+2 over 7 weeks)
ECTS credits: 5
- There will be a revision, “Q&A” class on Friday, June 8, 10:00-12:00 (in our regular room).
- The exam’s location has been changed! See below for the updated info.
- The date/time of the (regular) final exam has been announced (see the below). The registration period is between May 14 – June 8, 2018. Make sure to register for the exam in time!
- We have updated exercise 2.2; make sure to work on the latest version of Exercise Sheet 2.
- There will be no class on Wed 25.04, due to the Fachschaftsvollversammlung. Hand in your solutions to Exercise Sheet 2 during that day’s office hours (or via email).
- The first exercise sheet has been posted. Exercises are going to be published in this web page every Wednesday; make sure to check it regularly!
- Registration for the course is now open at TUMonline.
Duration: April 11, 2018 – May 25, 2018 (Tutorials start on April 20)
|Lecture||Wednesday||10:15 – 11.45||MI 02.04.011||Υ. Giannakopoulos|
|Friday||10:15 – 11.45||MI 02.04.011||Υ. Giannakopoulos|
|Tutorial||Friday||12:15 – 13.45||MI 02.04.011||D. Poças|
Office hours: Wednesdays & Fridays, 13:00–15:00, Room 02.04.061 (for the duration of the course); or after email appointment.
Exam: Friday, June 15, 2018. 16:15 – 17:45. Physics Department, Hörsaal 2.
The main goal of this course is to highlight the intriguing interplay between optimality, simplicity, efficiency and robustness in the design and analysis of systems involving many different selfish strategic players, with an emphasis in the intersection between Economics and Theoretical Computer Science. Can we predict the possible outcomes of such dynamic situations? Can we motivate the players and design specific rules, so that those outcomes are stable and desirable? How well and how efficiently can we approximate the above objectives? These questions are very important and relevant in many modern, real-life applications, where the Internet has been established as the main platform for agent-interaction and computing.
We will demonstrate the above by focusing in some of the prototypical topics in the field of Algorithmic Game Theory, such as Optimal (Revenue-Maximizing) Auctions, Scheduling Unrelated Machines, the Price of Anarchy, Selfish Routing, Congestion and Potential Games, and Learning in Games such as Best-Response and No-Regret Dynamics.
The ambition of this class is to provide a crash course for beginning graduate or advanced-undergraduate students interested in getting a glimpse into the toolbox and the necessary fundamentals of some of the most important research areas within the field of Algorithmic Game Theory, after which they should feel comfortable to start following the related work on their own.
- Fundamentals of Design & Analysis of Algorithms and Computational Complexity, e.g. MA2501 or similar
- Basics of Game Theory, e.g. IN2239 or similar (recommended, but not essential)
The overlap in the material of this course with that of other AGT courses offered at TUM, most notably IN2239 or IN2211, is minimal. In particular, this course is a natural follow-up to more fundamental Game Theory classes like IN2239, and can also complement nicely combinatorial Mechanism Design course like IN2211; if you have taken any of those courses in the past and enjoyed them, then this might be the right class for you! Also, as stated in the prerequisites above, some prior knowledge on the basics of Game Theory (as given, e.g., by IN2239), though not absolutely necessary (see below), will be an advantage.
Disclaimer: Prior knowledge of Game Theory is not essential for being able to follow this class. For example, game-theoretic primitives such as the notion of Nash equilibrium, are going to be introduced and used on-the-fly, on a need-to-know basis as part of the various topics described above. Nevertheless, this is still a theory course. As such, emphasis will be given in rigorousness and mathematical proofs, and the language and feel of algorithmic analysis and optimization will have a dominant presence throughout the lectures. So, mathematical maturity is essential and prior exposure or familiarity with the basic notions of subjects like the Design and Analysis of Algorithms, Discrete Mathematics and Optimization, Computational Complexity, Randomized/Approximation Algorithms, Probability and (Real) Analysis is highly recommended.
Please feel free to contact the lecturer beforehand to discuss any doubts you may have about your background.
The main textbook for our course will be:
- T. Roughgarden, “Twenty Lectures on Algorithmic Game Theory”, Cambridge University Press, 2016.
TUM students can get free electronic access to the book here (from within the Library’s network or via eAccess)
The following, known as “the AGT Book”, is the standard reference text in the field. It might be slightly outdated at some specific topics by now, and mostly aimed towards researchers (rather than students), but it is still a classic, covers way more material and we will repeatedly point to it throughout this class.
- Nisan, Roughgarden, Tardos & Vazirani (Eds), “Algorithmic Game Theory”, Cambridge University Press, 2007.
The AGT book is available online here (under the “Resources” tab), free of charge.
For convenience, we will use the shorthands [20LAGT] and [AGT], respectively, to cite the two main references mentioned above.
Further references to additional texts and specific research papers will be given during the class, and supplementary lecture notes will be uploaded here when needed (see the detailed outline below after each lecture).
Outline of Lectures & References
- Lecture 1 (Wed 11.04) Introduction: Mechanism Design, Price of Anarchy, computation of equilibria.
Reading: Supplementary notes, [20LAGT, Lecture 1]
- Video of the 2012 Olympics first controversial badminton match; related blog post; Wikipedia’s entry.
- Short-and-sweet overview articles about AGT: here and here.
- Three interesting blog posts about Equilibria and Computational Complexity: here, here and here.
- Play Rock-Paper-Scissors online, against an adaptive AI computer.
- Quanta article on Nash equilibria (and Rock-Paper-Scissors)
- Have you ever though about the interplay between Game Theory, Evolution and sex? Read here.
- Lecture 2 (Fri 13.04) Basics of Mechanism Design: First- and second-price auctions, DSIC truthfulness. Sponsored search auctions.
Reading: [20LAGT, Lecture 2]
- Lecture 3 (Wed 18.04) Single-Parameter environments. Characterization of DSIC implementability: Myerson’s Lemma and the payment formula.
Reading: Supplementary notes, [20LAGT, Lecture 3], [AGT, Theorem 9.39]
- Theorem 14.6.1 and its proof, from Anna Karlin’s and Yuval Peres’s book (highly recommended as an additional Game Theory reference textbook as well!).
- An interesting discussion about the GSP mechanism for sponsored search auctions and its (non)truthfulness, a short blog post and a related presentation. You can also have a look at Wikipedia’s entry.
- [AGT, Sections 9.4.1,9.4.2 and 9.5.4–9.5.6]
- Lecture 4 (Fri 20.04) Introduction to Bayesian Mechanism Design. The revenue-maximization objective. Regular distributions and virtual valuations. Equivalence between (expected) revenue maximization and virtual welfare maximization. Optimal Mechanisms; optimality of second-price with reserve for iid bidders.
Reading: Supplementary notes, [20LAGT, Sections 5.1–5.2], [AGT, Sections 13.1–13.2]
- Lecture 5 (Fri 27.04) Simplicity vs optimality in auction design. The prophet inequality and second-price auctions with bidder-specific reserves. Prior-independent mechanisms and the Bulow-Klemperer theorem.
Reading: [20LAGT, Lecture 6]
- Lecture 6 (Wed 02.05) (Non-atomic) selfish routing: Price of Anarchy and the Pigou bound.
Reading: [20LAGT, Lecture 11]
- An nice web article from the American Mathematical Society on the Price of Anarchy, and a blog post.
- The seminal paper of Roughgarden & Tardos on the PoA of nonatomic selfish routing.
- The original papers on the Pigou bound, here and here.
- The classic paper of J. G. Wardrop on selfish routing and “equilibria”.
- Lecture 7 (Fri 04.05) Atomic selfish routing: Price of Anarchy, upper and lower bounds for affine cost functions.
Reading: Supplementary notes, [20LAGT, Sections 12.4–12.5]
- The seminal paper of Koutsoupias & Papadimitriou, that introduced the Price of Anarchy notion.
- The classic paper of Christodoulou & Koutsoupias for the PoA on atomic congestion games with affine costs. For the \(5/2\) lower bound example we saw in class, see also this paper.
- As we briefly mentioned in class, the PoA of atomic games with polynomial cost functions, grows exponentially with respect to the maximum degree \(d\) of the polynomial. For exact PoA bound analysis with respect to \(d\) see this paper.
- Lecture 8 (Wed 09.05) Potential games. Congestion games and existence of pure Nash equilibria. Equilibrium refinement and Price of Stability bounds. Weighted congestion games and nonexistence of equilibria. Existence and uniqueness of equilibrium in nonatomic routing games.
Reading: Supplementary notes, [20LAGT, Sections 13.2–13.3], [AGT, Sections 18.3, 19.3.2–19.3.3]
- The seminal papers of Rosenthal and Monderer & Shapley for potential games.
- The study of the Price of Stability in atomic and nonatomic selfish routing games was initiated, respectively, by the works of Anshelevich et al. and Schulz & Moses.
- The classic reference for nonatomic routing, including the existence/uniqueness of equilibria in such games, is the work of Beckmann et al.. For a more modern exposition, see Chapter 2 of Roughgarden’s “routing” book.
- Lecture 9 (Fri 11.05) Hierarchy of solution concepts; pure Nash equilibria (PNE), (mixed) Nash equilibria (MNE), correlated equilibria (CE), coarse correlated equilibria (CCE). CE and Linear Programming. PoA and PoS for different equilibrium concepts. Approximate pure Nash equilibria (\(\varepsilon\)-PNE).
Reading: [20LAGT, Section 13.1 and Definition 16.2], [AGT, Sections 1.3 and 2.7]
- The seminal papers of John Nash on mixed equilibria, here and here.
- Aumann’s paper on correlated equilibria.
- The original paper on coarse correlated equilibria (although the actual term was coined later by Peyton Young).
- For the computational complexity of finding (and optimizing over) CE see the paper by Papadimitriou and Roughgarden.
- A blog post about CE.
- Lecture 10 (Wed 16.05) Best-response dynamics; convergence in potential games. \(\varepsilon\)-Best-response dynamics; fast convergence to approximate PNE of congestion games.
Reading: [20LAGT, Sections 16.1–16.3]
- Lectures 11-12 (Fri 18.05 & Wed 23.05) Online decision making, regret minimization. No-regret algorithms; multiplicative-weights. No-regret dynamics: fast convergence to (approximate) CCE; convergence to MNE for 2-player, zero-sum games. Swap-regret; convergence to CE.
Reading: [20LAGT, Sections 17.1 (except Example 17.5), 17.2, 17.4.1, 17.4.2 and 18.1–18.3]
- For an extensive overview of online learning (and its interplay with game equilibria), see the book of Cesa-Bianchi & Lugosi and Chapter 4 of [AGT] by Blum & Mansour.
- Classic references for learning dynamics that converge to MNE (in 2-player, zero-sum games) are the papers of Hannan and Blackwell.
- For more on the (swap-regret) dynamics that converge to CE, see the original papers of Foster & Vohra and Hart & Mas-Colell.
- The Minimax Theorem is due to the great John von Neumann: if you know German, you can read his seminal paper; alternative, see his book with O. Morgenstern that essentially founded the field of Game Theory.
- Lecture 13 (Fri 25.05) Overview of complexity classes related to computing PNE and MNE; FNP and TFNP. PLS and local search problems; local optima of MAX-CUT; (local) potential function minimization in congestion games and PLS-completeness. PPAD and MNE.
Reading: [20LAGT, Chapter 19 (except the proofs of Theorems 19.4 and 19.6) and Sections 20.1,20.2,20.6]
- The standard reference of the theory of NP-completeness and reductions is Garey and Johnson. You should also be aware of the seminal paper of Karp with its 21 NP-complete problems.
- Revisit the “further reading” list of Lecture 1 for complexity-related references.
- Class TFNP was first defined by Megiddo & Papadimitriou, PLS by Johnson, Papadimitriou & Yannakakis, and PPAD by Papadimitriou.
- The original paper on the PLS-completeness of computing PNE in congestion games is by Fabrikant, Papadimitriou & Talwar.
- The original papers on the PPAD-completeness of computing MNE is by Daskalakis, Goldberg and Papadimitriou Chen, Deng & Teng. For a more compact version see this article.
- To dig deeper into the theme of Complexity and Game Theory, have a look at these notes by Roughgarden.
Instructions for handing-in your solutions: either bring them, in person, by the end of Wednesday’s lecture (to Yiannis), or send them via email (to Diogo); in the latter case, make sure to submit your work as a single file.