**Lecturer**: Yiannis
Giannakopoulos

**Weekly hours**: 2+1

ECTS credits: 5 (Glasgow credits: 10)

**Moodle**
page (accessible only to UofG students)

Official UofG course listing

- 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!

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

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.

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,

*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, 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: November 11, 2024)*

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

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

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