FI:IA168 Algorithmic game theory - Informace o předmětu

IA168 Algorithmic game theory

Rozsah

2/0/1. 3 kr. (plus ukončení). Ukončení: zk.
Vyučováno kontaktně

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

Po 23. 9. až Po 16. 12. Po 8:00–9:50 A319

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á 29 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í

Mandatory homework assignments and oral exam

Vyučovací jazyk

Angličtina

Další komentáře

Studijní materiály
Předmět je vyučován každoročně.

• Statistika zápisu (nejnovější)
  
• Permalink: https://is.muni.cz/predmet/fi/podzim2024/IA168