Algoritmy moderní teorie her - NOPT021

• Anglický název: Modern Algoritmic Game Theory
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2022
• Semestr: zimní
• E-Kredity: 5
• Rozsah, examinace: zimní s.:2/2, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština, angličtina
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Další informace: http://Ústní zkouška. Požadavky k ústní zkoušce odvovídají sylabu.
• Garant: prof. RNDr. Martin Loebl, CSc.
• Vyučující: Mgr. Radovan Haluška; Mgr. Martin Schmid, Ph.D.
• Třída: Informatika Mgr. - Diskrétní modely a algoritmy
• Kategorizace předmětu: Informatika > Optimalizace

Anotace

čeština

Výklad základních matematických modelů a pojmů souvisejících s racionalním řešením konfliktních situací.

Poslední úprava: ()

angličtina

In this course, the students will learn the core concepts, models, theory and algorithms of modern and practical algorithmic game theory. During the practical part, they will gradually build the tools and codebase for implementing them in real games. At the end of the course, the students will have a working agent that converges to an optimal policy in Leduc poker and many other small games.

Poslední úprava: Hubička Jan, doc. Mgr., Ph.D. (14.02.2022)

Podmínky zakončení předmětu

čeština

Ústní zkouška.

Poslední úprava: Kynčl Jan, doc. Mgr., Ph.D. (31.05.2019)

angličtina

Oral exam.

Poslední úprava: Kynčl Jan, doc. Mgr., Ph.D. (31.05.2019)

Literatura

G. Owen: Game Theory, London 1971 nebo kterékoliv pozdější vydání (or any later edition).

E. Mendelson: Introducing Game Theory and Its Applications,CRC Press LLC,ISBN 1-58488-300-6, 2004

M. Chobot, F. Turnovec, V. Ulašin: Teória hier a rozhodovania, Alfa Bratislava, 1991.

M. Maňas: Teorie her a její ekonomické aplikace, SPN Praha 1983 nebo pozdější vydání.

Poslední úprava: T_KAM (20.04.2007)

Požadavky ke zkoušce

Oral exam, requirements according to the sylabus of the lecture.

Poslední úprava: Kynčl Jan, doc. Mgr., Ph.D. (31.05.2019)

Sylabus

Week 1

Course

• Matrix games formalism

• Best response

• Minimax policy, Nash equilibrium

• Zero sum games

Practice

• OpenSpiel

• Exploitability computation (i.e policy evaluation)

Week 2

Course

• Minimax theorem

• Minimax policy = Nash equilibrium

• Linear/convex optimization problem

Practice

• Linear programming for solving matrix games

Week 3 - Regret

Course

• Regret

• Folk’s theorem - connecting regret to exploitability

Practice

• Regret minimization in matrix games

• Average/current policy convergence

Week 4 - Sequential Decision Making

Course

• Extensive form games

• Factored observation games

Practice

• Small poker game

• Exploitability computation in extensive form games

Week 5 - Sequence Form

Course

• Sequence -> matrix = exponential explosion

• Sequence form

• Sequence LP

Practice

• Sequence LP

Week 6 - Counterfactual Regret Minimization

Course

• Counterfactual regret minimization

• CFR-BR

Practice

• CFR

Week 7 - Monte Carlo Methods

Course

• MCCFR

• Control variates

Practice

• MCCFR

• VR-MCCFR

Poslední úprava: Hubička Jan, doc. Mgr., Ph.D. (14.02.2022)