Algorithmic Game Theory (AGT)
FAU
Erlangen-Nürnberg, Departments of Mathematics & Data Science, WS
2022/23
Lecturer: Yiannis
Giannakopoulos
Weekly hours: 2+1
ECTS credits: 5
News
- 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
Schedule
Lectures: October 18, 2022 – February 07, 2023
Tutorials: November 2, 2022 – February 10, 2023
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).
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: March 6th, 2023)
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 (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:
- 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:
- 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.
- 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:
- 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:
- 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.
- Lecture 13 (Tue 31.01) No-regret dynamics: fast
convergence to CCE; convergence to MNE for 2-player, zero-sum
games.
Reading: Section 5.3 from lecture
notes
Further reading:
- The application of the MWU method in regret analysis of games can be
traced to the work of Freund and
Schapire
- Classic references for learning dynamics that converge to MNE (in
2-player, zero-sum games) are the papers of Hannan
and Blackwell.
- Lecture 14 (Tue 07.02) Swap-regret; convergence
to CE. Q&A for entire course material.
Reading: Section 5.4 from lecture
notes
Further reading: