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

IA168 Algorithmic game theory

Rozsah

2/0. 2 kr. (plus ukončení). Ukončení: zk.

Vyučující

doc. RNDr. Tomáš Brázdil, Ph.D. (přednášející)
RNDr. David Klaška (pomocník)
Bc. Tomáš Lamser (pomocník)
RNDr. Bc. Dominik Velan, Ph.D. (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 B204

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

• Analýza a zpracování obrazu (program FI, N-VIZ)
• Bioinformatika a systémová biologie (program FI, N-UIZD)
• Computer Games Development (program FI, N-VIZ_A)
• Computer Graphics and Visualisation (program FI, N-VIZ_A)
• Computer Networks and Communications (program FI, N-PSKB_A)
• Cybersecurity Management (program FI, N-RSSS_A)
• Formální analýza počítačových systémů (program FI, N-TEI)
• Grafický design (program FI, N-VIZ)
• Graphic Design (program FI, N-VIZ_A)
• Hardware Systems (program FI, N-PSKB_A)
• Hardwarové systémy (program FI, N-PSKB)
• Image Processing and Analysis (program FI, N-VIZ_A)
• Informační bezpečnost (program FI, N-PSKB)
• Information Security (program FI, N-PSKB_A)
• Kvantové a jiné neklasické výpočetní modely (program FI, N-TEI)
• Počítačová grafika a vizualizace (program FI, N-VIZ)
• Počítačové sítě a komunikace (program FI, N-PSKB)
• Principy programovacích jazyků (program FI, N-TEI)
• Řízení kyberbezpečnosti (program FI, N-RSSS)
• Řízení vývoje služeb (program FI, N-RSSS)
• Řízení vývoje softwarových systémů (program FI, N-RSSS)
• Services Development Management (program FI, N-RSSS_A)
• Software Systems Development Management (program FI, N-RSSS_A)
• Software Systems (program FI, N-PSKB_A)
• Softwarové systémy (program FI, N-PSKB)
• Strojové učení a umělá inteligence (program FI, N-UIZD)
• Vývoj počítačových her (program FI, N-VIZ)
• Zpracování a analýza rozsáhlých dat (program FI, N-UIZD)
• Zpracování přirozeného jazyka (program FI, N-UIZD)

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 bude znát základnĂ­ modely her a algortimĹŻ pro hledánĂ­ strategiĂ­ k jejich Ĺ™ešenĂ­.

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ě.

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