Computational Game Theory (CGT)

University of Glasgow, School of Computing Science — 2024/25, Semester 1

Lecturer: Yiannis Giannakopoulos
Weekly hours: 2+1
ECTS credits: 5 (Glasgow credits: 10)

Moodle page (accessible only to UofG students)

Official UofG course listing

News

• The Moodle page of the course is now online. All UofG students who want to take this course for credit, should make sure that they are properly enrolled and that they have access to that page. The Moodle page is the primary, official resource for all matters related to this course: important announcements, lecture video recordings and slides, tutorial problems, and assessed coursework, will only be posted there!

Schedule

Lectures & Tutorials: October 1, 2024 – December 3, 2024 (10 weeks)

Class Type	Day	Time	Room
Lecture	Tuesday	10:00 – 12:00	Rankine 107
Tutorials	Tuesday	15:00 – 16:00	James Watt 355 (J10)

Office hours: Tuesdays (on lecture weeks), 13:15 – 14:45, Room M101, Sir Alwyn Williams building; also online via Zoom (the link will be posted on the course’s Moodle 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 on some prototypical topics in the field of Algorithmic Game Theory, such as (the complexity of) computing equilibria, the price of anarchy, congestion games, zero-sum 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 (AGT), 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 required for being able to follow this class successfully.

Disclaimer: This is a theory course. As such, emphasis will be given in rigorousness and mathematical proofs. Furthermore, the language and feel of algorithmic analysis 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, Calculus, and Probability 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, for most of the material taught. 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 13, 2025)

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.

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

University of Glasgow students can get free electronic access to both books; see our course’s official reading list.

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 01 Oct) Introduction and motivation. Normal-form games and basic solution concepts. Reading: [20LAGT, Lecture 1], Chapter 1 from lecture notes.
  Further reading:
  • What is Computational Game Theory, according to ChatGPT, in the styles of T.S. Eliot, Pink Floyd, Oasis, and Taylor Swift.
  • 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 08 Oct) Potential games. Congestion games and existence of pure Nash equilibria. Price of Anarchy (PoA) and Stability (PoS).
  Reading: Sections 2.1 – 2.3 (up until the statement of Theorem 2.3) from lecture notes.
  Further reading:
  • The seminal paper of Rosenthal on congestion games.
  • The seminal paper of Monderer & Shapley for potential games.
  • 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.
• Lecture 3 (Tue 15 Oct) PoA upper and lower bounds for linear congestion games. Equilibrium refinement and PoS upper bounds for polynomial congestion games. Computation of equilibria in congestion games. Better-response dynamics.
  Reading: Sections 2.3 – 2.4.2 from lecture notes.
  Further reading:
  • 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 an exact PoA bound analysis with respect to d see this paper paper by Aland et al..
• Lecture 4 (Tue 22 Oct) Fast convergence of better-response dynamics in singleton games. Poly-time computation of PNE in symmetric network games. Approximate equilibria. FPTAS for approximate PNE in symmetric congestion games.
  Reading: Sections 2.4.3 – 2.4.5 from lecture notes.
  Further reading:
  • The fast-convergence result for singleton games we saw in class is from Ieong et al..
  • The reduction of symmetric network congestion games to a min-cost flow problem was done by Fabrikant, Papadimitriou & Talwar.
  • The fast-convergence result of (1+\varepsilon)-improving dynamics to approximate PNE we analyzed in class is due to Chien & Sinclair.
• Lecture 5 (Tue 29 Oct) 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 PLS-completeness of the Local-Max-Cut problem was established by Schäffer & 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.
  • For more on the topic of “decision vs search” in computational complexity see this blog post, and the classic paper of Bellare & Goldwasser.
• Lecture 6 (Tue 5 Nov) No new material: “Tutorial week”
  
• Lecture 7 (Tue 12 Nov) Mixed Nash equilibria in bimatrix games. Very quick introduction to linear programming. Von Neumann’s Minimax Theorem. Existence/computability of NE for zero-sum games.
  Reading: Sections 4.1-4.2 from lecture notes. For the linear programming intro, read from the lecture slides.
  Recommended reading:
  • We highly recommend the excellent textbook of Matoušek and Gärtner, for students interested in a more thorough introduction to linear programming fundamentals.
  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 8 (Tue 19 Nov) Fictitious play. Convergence of FP for zero-sum games and Karlin’s conjecture. (Coarse) correlated equilibria.
  Reading: Section 4.3 and Chapter 5 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. You can also find her paper on the traveling salesman problem 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 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.
  • For more on the interesting geometry of CE, see this paper.
  • A blog post about CE.
• Lecture 9 (Tue 26 Nov – Guest lecture by Aris Filos-Ratsikas!) Existence and complexity of computing mixed Nash equilibria in general games. The complexity class PPAD.
  Reading: Aris’s lecture slides.
  Further reading:
  • See Section 4.4 from the lecture notes, for an alternative proof of Nash’s theorem.
  • 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).
  • See Section 4.4 from the lecture notes, for an alternative proof of Nash’s theorem (but still via Brouwer’s fixed-point theorem), due to John Geanakoplos.
  • For a generalization of Nash’s theorem to infinite games, see the paper of Glicksberg.
  • The complexity class PPAD was introduced by Papadimitriou.
  • The PPAD-completeness of computing mixed Nash equilibria in general games with even only two players is due to Daskalakis, Goldberg & Papadimitriou and Chen, Deng & Teng.