Algorithmic Game Theory (AGT)
FAU Erlangen-Nürnberg, Department of Mathematics, WS 2021/22
Lecturer: Yiannis Giannakopoulos
Weekly hours: 2+1
ECTS credits: 5
News
- There will be a special kick-off meeting on Thursday, October 14, 17:00, to discuss organizational aspects of the course (and answer any further questions that students may have). The Zoom link for this meeting can be found on StudOn. We encourage you all to attend!
- Registration for the course (for FAU students) is now open at StudOn. Make sure to sign up until November 11, 2021.
- Our StudOn page is now online. All FAU students should log in and join, in order to not miss important announcements and also be able to participate in the discussion forums!
Schedule
Lectures: October 18, 2021 – February 07, 2022
Tutorials: November 4, 2021 – February 11, 2022
Office hours: Tuesdays, 13:30 – 15:00, online via Zoom (the link will be posted on StudOn).
Description
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 Economic and Algorithmic Theory. 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 (the complexity of) computing equilibria, the price of anarchy, 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.
Prerequisites
Basic knowledge of: calculus, probability theory, and linear/combinatorial optimization and/or algorithms & complexity
In particular, 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.
Disclaimer: This is 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.
Lecture Notes & Textbooks
We will not make use of a single “official” textbook; instead, informal lecture notes will be provided by the instructor. These are going to be updated after each lecture and uploaded to the following document which will be gradually expanding:
Lecture Notes (last update: February 7th, 2022)
The following two textbooks include much of the material that we are going to cover in class and are highly recommended:
FAU students can get free electronic access to the book via the university’s network, through the Library.
The book is available online here, free of charge.
For convenience, we will use the shorthands [20LAGT] and [AGT], respectively, to cite these two books.
Further references to additional texts, resources, and specific research papers will be given during the semester (see the detailed outline below after each lecture).
Outline of Lectures and References
- Lecture 1 (Mon 18.10) Introduction and motivation. Normal-form games and basic solution concepts. Reading: [20LAGT, Lecture 1], Chapter 1 from lecture notes
Further reading:
- Video of the 2012 Olympics first controversial badminton match; related blog post; Wikipedia’s entry.
- Some “real life” examples demonstrating Braess’s paradox: here and here.
- The original paper of Dietrich Braess, in German. An English translation can be found here.
- 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 thought about the interplay between Game Theory, Evolution and sex? Read here.
- A talk by Tim Roughgarden on “Game Theory Through the Computational Lens”
- Lectures 2 & 3 (Mon 25.10, Mon 08.11) Potential games. Congestion games and existence of pure Nash equilibria.
Reading: Sections 2.1, 2.2 from lecture notes
Further reading:
- Lectures 3 & 4 (Mon 8.11, Mon 15.11) Price of Anarchy (PoA) and Stability (PoS). PoA upper and lower bounds for linear congestion games. Equilibrium refinement and PoS upper bounds for polynomial congestion games.
Reading: Section 2.3 from lecture notes
Further reading:
- A nice web article from the American Mathematical Society on the PoA, and a blog post.
- The seminal paper of Koutsoupias & Papadimitriou, that introduced the PoA notion.
- The classic paper of Christodoulou & Koutsoupias for the PoA on atomic congestion games with affine costs.
- The study of the PoS in congestion games was initiated by Anshelevich et al..
- 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.
- Lectures 4 & 5 (Mon 15.11, Mon 22.11) Computation of equilibria in congestion games. Better-response dynamics. Fast convergence in singleton games.
Reading: Sections 2.4.1 – 2.4.3 from lecture notes
Further reading:
- The fast-convergence result for singleton games we saw in class is from Ieong et al..
- Lectures 6 & 7 (Mon 29.11, Mon 06.12) Approximate equilibria. FPTAS for approximate PNE in symmetric congestion games. Poly-time computation of (exact) PNE in symmetric network games.
Reading: Section 2.4.4, 2.4.5 from lecture notes
Further reading:
- The fast-convergence result of \varepsilon-improving dynamics to approximate PNE we analyzed in class is due to Chien & Sinclair.
- The reduction of symmetric network congestion games to a min-cost flow problem was done by Fabrikant, Papadimitriou & Talwar.
- Lectures 7 & 8 (Mon 06.12, Mon 13.12) Local search problems and PLS-completeness of computing PNE Reading: Section 2.5 from lecture notes
Further reading:
- Lectures 9 & 10 (Mon 20.12, Mon 10.01) Mixed Nash equilibria in bimatrix games. Von Neumann’s Minimax Theorem. Existence/computability of NE for zero-sum games. Reading: Sections 3.1-3.2 from lecture notes
Further reading:
- The Minimax Theorem is due to the great John von Neumann: if you know German, you can read his original paper; see here for an english translation.
- A follow-up, alternative proof can be found in the seminal book of von Neumann & O. Morgenstern (which is considered the founding work of the entire field of Game Theory). This proof already has a strong duality/Farkas Lemma flavour.
- The proof we presented in class is essentially a “modern” interpretation of the aforementioned proof from the book of von Neumann & Morgenstern, through the lens of linear programming duality. This connection was made explicit by the works of Gale, Kuhn & Tucker and Dantzig; see Chapters XIX and XXX from these proceedings.
- For an interesting historical discussion of the technical aspects of von Neumann’s various proofs of the Minimax Theorem, see this paper.
- For an exciting, first-hand discussion about events related to the birth of linear programming theory and its connections with the developments of duality and the theory of zero-sum games, see this wonderful report from George Dantzig (of the Simplex method) himself.
- Lecture 10 (Mon 10.01) Fictitious play. Convergence of FP for zero-sum games and Karlin’s conjecture. Reading: Section 3.3 from lecture notes
Further reading:
- You can read more about the Julia Robinson here and here. She is well-known for her contributions to Hilbert’s tenth problem; a related documentary film can be found here.
- Although (the weak version of) Karlin’s conjecture is still open, it was recently proven to hold for the special case of diagonal matrices and lexicographic tie-breaking by Abernethy, Lai & Wibisono.
- Fictitious play converges for many other important classes of games, beyond zero-sum, including potential and general 2\times n bimatrix games.
- Interesting continuous and stochastic variants of FP exist. See, e.g., the textbook of Fudenberg & Levine.
- Lecture 11 (Mon 17.01) Correlated equilibria.
Reading: Section 4.1 from lecture notes
Further reading:
- The CE notion was introduced by Robert Aumann in these 1974 and 1987 papers.
- Coarse correlated equilibria where introduced by Moulin & Vial (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 & Roughgarden.
- A blog post about CE.
- Lectures 11, 12 & 13 (Mon 17.01, Thu 27.01, Mon 31.01) Online decision making, regret minimization. No-regret algorithms; multiplicative-weights. No-regret dynamics: fast convergence to CCE; convergence to MNE for 2-player, zero-sum games. Swap-regret; convergence to CE.
Reading: Sections 4.2-4.4 from lecture notes
Further reading:
- 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.
- For more on the (swap-regret) dynamics that converge to CE, see the original papers of Foster & Vohra and Hart & Mas-Colell.
- Lecture14 (Mon 07.02) Convergence of no-regret dynamics to MNE for 2-player zero-sum games. Proof of Nash’s theorem.
Reading: Sections 3.4 and 4.3 from lecture notes
Further reading:
- Classic references for learning dynamics that converge to MNE (in 2-player, zero-sum games) are the papers of Hannan and Blackwell.
- The conception of the mixed equilibrium notion (in general games) and the original proof of Nash’s Theorem is, of course, due to John Nash: he first published a (single-page!) proof (via Kakutani’s fixed-point theorem) and then a follow-up paper (where Brouwer’s fixed-point theorem is used).
- The proof of Nash’s theorem we showed in class (via Brouwer’s fixed-point theorem) is due to John Geanakoplos.
- For a generalization of Nash’s theorem to infinite games, see the paper of Glicksberg.