Master Course
Algorithmic Game Theory (AGT)

Background

Algorithmic Game Theory (AGT) is an interdisciplinary research area that lies in the intersection of Theoretical Computer Science, Discrete Mathematics and Economic Theory. The area builds upon game-theoretic foundations to study situations of strategic decision making, with a particular focus on computational and algorithmic aspects. It combines methodologies and techniques from several disciplines such as complexity theory, algorithm design, discrete and continuous optimization, online decision making and learning, auction and mechanism design, etc.

Course Contents

In this course, we study the existence, computation and inefficiency of equilibria (ranging from pure Nash equilibria to coarse correlated equilibria and learning outcomes) for various classes of games. We also consider the problem of designing coordination mechanisms to reduce the inefficiency. Further, we touch upon the computational limitations that arise in classic auction theory and learn about techniques to develop simple and efficient algorithms for fundamental mechanism design problems.

Objectives 

The overall aim of the course is to get acquainted with fundamental methodologies, techniques and results in AGT. Throughout the course, we will build up a toolbox of models and techniques to study the impact of strategic decision making in various settings and to develop efficient algorithms for such environments. 

The expected learning outcomes of the course are listed below: 

• Learn how to use game-theoretic models to study situations of strategic decision making.

• Understand and identify the computational limitations and algorithmic challenges that arise.

• Study and learn fundamental results on the existence, computation and inefficiency of equilibria.

• Build up a toolbox of models and techniques to study the impact of strategic decision making.

• Learn how to design simple and efficient algorithms for computationally hard mechanism design settings.

Topics

The main topics that will be covered in this course are: 

• selfish routing games and the price of anarchy

• Braess paradox, Stackelberg routing, network tolls

• best-response dynamics and potential games

• existence, computation and inefficiency of equilibria 

• equilibrium hierarchy and no-regret learning 

• smoothness and extension theorems

• auctions (single-item, single-parameter, combinatorial, generalized second price) 

• simple vs. optimal mechanism design 

• matching markets and envy-freeness

(see below for a more detailed overview of the different modules of the course) 

Course Organization 

This course is part of the Master of Logic and the Master of Artificial Intelligence and will be given at the University of Amsterdam (Science Park). 

The course starts on Monday, September 4, 2023 and ends on Thursday, October 19, 2023. 

There will be two lectures and one tutorial session offered each week. 

Lectures:

Monday: 15:00–17:00
Thursday: 15:00–17:00

Tutorials:

Wednesday: 15:00–17:00

Lecturer and Teaching Assistant

The course will be given by Guido Schäfer.

Prof. Dr. Guido Schäfer
Networks and Optimization Group, Centrum Wiskunde & Informatica
Institute for Logic, Language and Computation, University of Amsterdam
Email: g.schaefer@cwi.nl

Please feel free to approach me if you have any questions, comments or remarks related to the course.

Danish Kashaev will be the teaching assistant of the course. 

Assignments

Assignments will be issued throughout the course and graded. 

We will probably allow for a mix of individual and group assignments (exact setup to be determined).

We will also ask you to study some material on your own. 

Prerequisites

• Solid background knowledge of the following topics:

  • complexity theory: worst-case analysis, P vs NP, NP-completeness

  • algorithms: basic algorithms (e.g., shortest path, matching, min-cost flow), knowledge of approximation algorithms is advantageous

  • optimization: linear programming, duality, basic knowledge of convex optimization is advantageous 

• Basic knowledge of game theory

• Mathematical maturity: students are are expected to have prior experience with working out and writing up mathematical proofs.

References to standard textbooks to read up on relevant background (if needed) can be provided upon request.

Literature

Lecture Notes covering most of the material covered throughout the course will be provided. 

The following books contain most of the material covered in class and are good references if you want to learn more.

Main references: 

[NRTV07]
N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani (Editors), Algorithmic Game Theory, Cambridge University Press, 2007.
Note: The full-text of the book (pdf) seems to be available online.

[Rou16]
T. Roughgarden, Twenty Lectures on Algorithmic Game Theory, Cambridge University Press, 2016.
Note: The full-text of the book (pdf) seems to be available online.

Additional background reading: 

[SLB16]
Y. Shoham and K. Leyton-Brown, Multiagent Systems, Cambridge University Press, 2009.
Note: The full-text of the book (pdf) is available here.

[KP16]
A. R. Karlin and Y. Peres, Game Theory, Alive, American Mathematical Society, 2016.
Note: The full-text of the book (pdf) is available here.

Modules

The course is subdivided into four main modules. An outline is given below (might still be adapted throughout the course).

Introduction: Some Highlights and Pheomena in AGT

Module 1: Potential Games and their Connections to Congestion Games 

• Strategic games and existence of pure Nash equilibria (PNE)

  • improving moves algorithms, better and best response dynamics

  • finite improvement property (FIP)

• Potential games

  • exact, ordinal, generalized potential games

  • equivalence generalized potential games and the FIP 

  • relation to congestion games

  • examples: connection games, congestion games, load balancing games, scheduling games 

• Computing PNE in potential games

  • Polynomially local search problems (PLS)

  • PLS-reduciblibility, PLS-completeness

  • computing PNE in congestion games is PLS-complete

• Techniques to bound the inefficiency

  • POS: potential function method

  • POA: outlook: smoothness framework

• Strong equilibria
  
  

Module 2: Non-Atomic Selfish Routing Games

• Wardrop model and selfish routing

  • existence and computation of Nash flows

  • Karush Kuhn Tucker optimality conditions for convex programming

  • characterization of Nash flows and social optima

• Inefficiency of equilibria and the price of anarchy

  • price of anarchy is independent of network topology

  • proof template for upper bound 

  • tight lower bounds 

• Coping with selfishness:

  • Braess paradox

  • network tolls

  • Stackelberg routing
    
    

Module 3: Equilibrium Hierarchy

• equilibrium notions: 

  • Mixed Nash equilibria

  • Correlated equilibria 

  • Coarse correlated equilibria

• online decision making and learning outcomes

• approximate equilibria

• existence and computational issues

• smoothness of games and extension theorems
  
  

Module 4: Auctions and Mechanism Design

• Warm-up: Vickrey auction 

  • single-item auction and objectives

  • second-price auction

  • strategyproofness

• VCG mechanism for combinatorial auctions 

  • combinatorial auction model

  • VCG mechanism and extensions

  • truthfulness and pitfalls 

• Generalized second-price auctions (GSP)

  • GSP and sponsored search

  • model and deficiencies of GSP

  • detour: existence of pure Nash equilibria

  • matching markets

    • existence of market clearing prices

    • ascending price algorithm and its termination

  • price of anarchy of GSP

• Single-parameter setting

  • Myerson's Lemma: characterization of truthful mechanisms

  • mechanism design and approximation algorithms 

  • procurement auctions: knapsack auction, shortest-path auction 

  • extension: single-minded bidders

• Mechanism Design without Payments