IA168 Algorithmic game theory

Fakulta informatiky
podzim 2023
Rozsah
2/0/1. 3 kr. (plus ukončení). Ukončení: zk.
Vyučující
doc. RNDr. Tomáš Brázdil, Ph.D. (přednášející)
Mgr. Jakub Balabán (pomocník)
RNDr. David Klaška (pomocník)
Mgr. Martin Kurečka (pomocník)
Mgr. Matěj Žáček (pomocník)
Garance
doc. RNDr. Tomáš Brázdil, Ph.D.
Katedra strojového učení a zpracování dat – Fakulta informatiky
Dodavatelské pracoviště: Katedra strojového učení a zpracování dat – Fakulta informatiky
Rozvrh
Čt 8:00–9:50 A218
Předpoklady
basic linear algebra, basic probability theory (mostly discrete probability), elementary complexity theory, some calculus
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
předmět má 30 mateřských oborů, zobrazit
Cíle předmětu
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.
Výstupy z učení
Student will understand basic game theoretic models and algorithms.
Osnova
  • 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
Literatura
  • Algorithmic game theory. Edited by Noam Nisan. Cambridge: Cambridge University Press, 2007, xxi, 754. ISBN 9780521872829. info
  • FILAR, Jerzy A. a Koos VRIEZE. Competitive Markov decision processes : with 57 illustrations. New York: Springer, 1997, xii, 393. ISBN 0387948058. info
Výukové metody
Standard lecture
Metody hodnocení
Oral exam
Vyučovací jazyk
Angličtina
Další komentáře
Studijní materiály
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018, podzim 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2024.