IA168 Algorithmic game theory

Faculty of Informatics
Autumn 2020
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
Teacher(s)
doc. RNDr. Tomáš Brázdil, Ph.D. (lecturer)
RNDr. David Klaška (assistant)
Bc. Tomáš Lamser (assistant)
RNDr. Bc. Dominik Velan, Ph.D. (assistant)
Guaranteed by
doc. RNDr. Tomáš Brázdil, Ph.D.
Department of Machine Learning and Data Processing – Faculty of Informatics
Supplier department: Department of Machine Learning and Data Processing – Faculty of Informatics
Timetable
Tue 8:00–9:50 B204
Prerequisites
basic linear algebra, basic probability theory (mostly discrete probability), elementary complexity theory, some calculus
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
Course objectives
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.
Learning outcomes
Student knows the basics types of models of games and algorithms for searching winning strategies.
Syllabus
  • Basic definitions: Games in normal form, dominant strategies, Nash equilibria in pure and mixed strategies, existence of Nash equilibria, basic examples
  • Computing Nash equilibria: Lemke-Howson algorithm, support enumeration, sampling methods, PPAD-completeness of Nash equilibria,
  • Quantifying the inefficiency of equilibria and related games: Congestion and potential games, price of anarchy and price of stability, routing games, network formation games, load balancing games
  • Learning in games: Regret minimization algorithms, correlated equilibria and connection to learning in games, regret minimization in routing games
  • Auctions and mechanism design: First price auctions, Vickrey auctions, truthfulness, Vickrey-Clark-Groves mechanism, Bayesian games, Bayesian Nash equilibria, formal framework for mechanism design, revelation principle, auctions on Google
  • Games with multiple moves: Games in extensive form, games on graphs, Markov decision processes, stochastic games
Literature
  • Algorithmic game theory. Edited by Noam Nisan. Cambridge: Cambridge University Press, 2007, xxi, 754. ISBN 9780521872829. info
  • FILAR, Jerzy A. and Koos VRIEZE. Competitive Markov decision processes : with 57 illustrations. New York: Springer, 1997, xii, 393. ISBN 0387948058. info
Teaching methods
Standard lecture
Assessment methods
Oral exam
Language of instruction
English
Further Comments
Study Materials
The course is taught annually.
The course is also listed under the following terms Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.
  • Enrolment Statistics (Autumn 2020, recent)
  • Permalink: https://is.muni.cz/course/fi/autumn2020/IA168