IA168 Algorithmic Game Theory

Author

Štěpán Zapadlo

Published

March 2, 2024

Preface

This book follows the course IA168 Algorithmic Game Theory taught by assoc. prof. Brázdil on FI MUNI as it appeared in Fall 2023. All of this course is almost 1-to-1 based on his materials and I only typesetted it into a (in my opinion) more readable format.

In recent years, huge amount of research has been done at the borderline between game theory and computer science, largely motivated by the emergence of the Internet. The aim of the course is to provide students with basic knowledge of fundamental game theoretic notions and results relevant to applications in computer science. The course will cover classical topics, such as general equilibrium theory and mechanism design, together with modern applications to network routing, scheduling, online auctions etc. We will mostly concentrate on computational aspects of game theory such as complexity of computing equilibria and connections with machine learning.

Some notes:

  • more mathematically oriented than typically FI course
  • lectures should be enough to pass the course

All slides will be available.

Evaluation

Homework is mandatory and there are 3 homework assignments. Also there is a threshold for pass/not pass of the homework.

There are public homeworks from last years

Afterwards follows an oral exam:

  • there will be at least 3 or 4 exam dates every week
    • there are as many tries as we want
  • we need to know everything (and it’s not a joke :))
  • at least 1h for the exam (but very possibly more)
  • precise mathematical communication needed for the exam

Overview of the course

This is a theoretical course aimed at some fundamental results of game theory, often related to computer science

  • We start with strategic form games (such as the Prisoner’s dilemma), investigate several solution concepts (dominance, equilibria) and related algorithms.
  • Then we consider repeated games which allow players to learn from history and/or to react to deviations of the other players.
  • Subsequently, we move on to incomplete information games and auctions.
  • Finally, we consider (in)efficiency of equilibria (such as the Price of Anarchy) and its properties on important classes of routing and network formation games.
  • Remaining time will be devoted to selected topics from extensive form games, games on graphs etc.