**Lecturer**: Yiannis
Giannakopoulos

**Weekly hours**: 2+1

ECTS credits: 5

- There will be a special
**kick-off meeting**on Thursday,**October 13, 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! - 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! Registration.**deadline: December 11, 2022** - The StudOn page of the course will be online soon. Stay tuned for updates! For now, you can have a look at previous instantiations of this course in FAU here: WS21/22

**Lectures:** October 18, 2022 – February 07, 2023

**Tutorials:** November 2, 2022 – February 10, 2023

Class Type | Day | Time | Room |
---|---|---|---|

Lecture |
Tuesday | 10:15 – 11:45 | Emmy-Noether-Hörsaal (H12) |

Tutorials |
Wednesday | 10:15 – 11:45 | Übung 5 (01.254-128) |

Friday | 12:15 – 13:45 | Übung 4 (01.253-128) |

**Office hours:** Tuesdays (on lecture weeks), 13:30 –
15:00, Room 03.384
(Felix-Klein building); also online via Zoom (the link will be posted on
the course’s StudOn page).

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.

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**:

*Please feel free to contact the lecturer beforehand to discuss
any doubts you may have about your background.*

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: January 24th, 2023)*

The following two textbooks include much of the material that we are going to cover in class and are highly recommended:

*T. Roughgarden, “Twenty Lectures on Algorithmic Game Theory”, Cambridge University Press, 2016.*

FAU students can get free electronic access to the book via the university’s network, through the Library.

- Nisan, Roughgarden, Tardos & Vazirani (Eds), “Algorithmic Game Theory”, Cambridge University Press, 2007.

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

**Lecture 1**(Tue 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.
- Rock-Paper-Scissors-Lizard-Spock video.
- Play Rock-Paper-Scissors online, against an adaptive AI computer.
- Here you can participate online in various Game-Theory-based experiments.
- 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.
- 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”

**Lecture 2**(Tue 25.10)*Potential games. Congestion games and existence of pure Nash equilibria.*

Reading: Sections 2.1, 2.2 from lecture notes

Further reading:- The seminal paper of Rosenthal on congestion games
- The seminal paper of Monderer & Shapley for potential games.

**Lecture 3**(Tue 8.11)*Price of Anarchy (PoA) and Stability (PoS). PoA upper and lower bounds for linear congestion games.*Reading: Section 2.3 (up to Theorem 2.4) from lecture notes

Further reading:**Lecture 4**(Tue 15.11)*Equilibrium refinement and PoS upper bounds for polynomial congestion games. Computation of equilibria in congestion games. Better-response dynamics.*

Reading: Sections 2.3 (starting from Theorem 2.5), 2.4.1 and 2.4.2 from lecture notes

Further reading:- 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.

**Lecture 5**(Tue 22.11)*Fast convergence of better-response dynamics in singleton games. Approximate equilibria. FPTAS for approximate PNE in symmetric congestion games.*

Reading: Sections 2.4.3 – 2.4.4 from lecture notes

Further reading:- The fast-convergence result for singleton games we saw in class is from Ieong et al..
- The fast-convergence result of (1+\varepsilon)-improving dynamics to approximate PNE we analyzed in class is due to Chien & Sinclair.

**Lecture 6**(Tue 29.11)*Poly-time computation of (exact) PNE in symmetric network games.*

Reading: Section 2.4.5 from lecture notes

Further reading:- The reduction of symmetric network congestion games to a min-cost flow problem was done by Fabrikant, Papadimitriou & Talwar.

**Lecture 7**(Tue 06.12)*Local search problems and the complexity class PLS. PLS-completeness of computing PNE.*Reading: Section 3 from lecture notes

Further reading:- For more about best-response graphs (and walks on them), see the papers here and here.
- The complexity class PLS was introduced by Johnson, Papadimitriou & Yannakakis.
- The original paper on the PLS-completeness of computing PNE in congestion games is by Fabrikant, Papadimitriou & Talwar. The proof we saw in class (Theorem 3.2 in the lecture notes) is from Roughgarden’s textbook [20LAGT].
- To dig deeper into the theory of local search and PLS, have a look at the books of Aarts & Lenstra and Michiels, Aarts & Korst.

**Lecture 8**(Tue 13.12)*Mixed Nash equilibria in bimatrix games. Von Neumann’s Minimax Theorem. Existence/computability of NE for zero-sum games.*Reading: Sections 4.1-4.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 9**(Tue 20.12)*Fictitious play. Convergence of FP for zero-sum games and Karlin’s conjecture. Proof of Nash’s theorem.*Reading: Section 4.3 – 4.4 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.
- 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.

**Lecture 10**(Tue 10.01)*(Coarse) correlated equilibria.*

Reading: Section 5.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**(Tue 17.01)*Online decision making, regret minimization. No-regret algorithms.*

Reading: Section 5.2, without Section 5.2.1, 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.

**Lecture 12**(Tue 24.01)*The multiplicative-weights-update (MWU) method.*

Reading: Section 5.2.1 from lecture notes

Further reading:- The development of the MWU method is attributed to the seminal “Weighted Majority” paper of Littlestone and Warmuth.