460-4116/02 – Teorie her (TEH)
Garantující katedra | Katedra informatiky | Kredity | 4 |
Garant předmětu | doc. Ing. Zdeněk Sawa, Ph.D. | Garant verze předmětu | doc. Ing. Zdeněk Sawa, Ph.D. |
Úroveň studia | pregraduální nebo graduální | Povinnost | povinně volitelný |
Ročník | 2 | Semestr | zimní |
| | Jazyk výuky | angličtina |
Rok zavedení | 2015/2016 | Rok zrušení | |
Určeno pro fakulty | FEI | Určeno pro typy studia | magisterské, navazující magisterské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
Porozumět základním pojmům a metodám matematické teorie her.
Naučit se používat tyto metody při řešení jednoduchých konfliktních a rozhodovacích situací standardního typu.
Osvojení si hlavních idejí teorie her a schopnost jejich intuitivního využívání ve složitých rozhodovacích situacích (konfliktních, s náhodnými vlivy, s neúplnou informací,...). Schopnost formalizovat rozhodovací situace a procesy pomocí standardních modelů teorie her. Schopnost řešit standardní úlohy teorie her (znalost příslušných algoritmů).
Vyučovací metody
Přednášky
Cvičení (v učebně)
Anotace
Předmět seznamuje studenty se základy matematické teorie her. Studenti se dozví o různých typech her a o tom, jak je možné různé typy her matematicky formalizovat a algoritmicky řešit. Nejprve jsou diskutovány kombinatorické hry, tj. hry dvou hráčů s dokonalou informací. Dále jsou pak studovány hry ve standardním a v rozvinutém tvaru, přičemž nejprve se zaměřujeme na hry dvou
hráčů s nulovým součtem (jejichž řešení se dá v případě konečných her převést na úlohu lineárního programování) a dále pak na hry s obecným součtem. U her s obecným součtem jsou pak zvlášť rozebírány nekooperativní hry, u kterých se zkoumá existence Nashových rovnovážných bodů, a dále pak kooperativní hry, u kterých navíc rozlišujeme varianty s přenosnou a nepřenosnou výhrou. Jak u her
s nulovým, tak u her s obecným součtem jsou studovány varianty her rozšířené o náhodné tahy a nedokonalou informaci.
Povinná literatura:
[1] Thomas S. Ferguson – Game Theory — výukové texty k předmětu Game Theory vyučovaném na UCLA (University of California, Los Angeles), http://www.math.ucla.edu/~tom/math167.html
Doporučená literatura:
[2] Kevin Leyton-Brown, Yoav Shoham: Essentials of Game Theory: A Concise, Multidisciplinary Introduction, Morgan and Claypool Publishers, 2008.
[3] Algorithmic Game Theory, edited by Noam Nisan, Tim Roughgarden, Eva Tardos and Vijay V. Vazirani, Cambridge University Press, 2007.
[4] Martin J. Osborne, Ariel Rubinstein: A Course in Game Theory, MIT Press, 1994.
[5] Drew Fudenberg, Jean Tirole: Game Theory, MIT Press, 1991.
[6] Robert Gibbons: A Primer in Game Theory, Financial Times Prentice Hall, 1992.
Forma způsobu ověření studijních výsledků a další požadavky na studenta
Průběžná kontrola studia:
Kontrolní písemka v polovině semestru.
Podmínky udělení zápočtu:
Kontrolní písemka v polovině semestru bude hodnocena maximálně 30 body, pro získání zápočtu je třeba získat z této písemky minimálně 10 bodů.
Zkouška:
Pro absolvování zkoušky je třeba ze 70 bodů získat alespoň 25.
E-learning
Další požadavky na studenta
Další požadavky na studenta nejsou kladeny.
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Přednášky:
1. Úvod.
2. Kombinatorické hry, grafové hry.
3. Hra NIM, Sprague-Grundyova funkce.
4. Sumy her a jejich řešení pomocí Sprague-Grundyovy funkce.
5. Hry dvou hráčů s nulovým součtem ve strategickém tvaru, maticové hry.
6. Dominované strategie, sedlový bod, smíšené strategie.
7. Řešení maticových her ve smíšených strategiích převodem na lineární programování.
8. Lineární programování (dokončení).
9. Hry dvou hráčů s nulovým součtem v rozvinutém tvaru, Kuhnův strom, náhodné tahy, hry s nedokonalou informací.
10. Hry dvou hráčů s obecným součtem ve strategickém tvaru, bimaticové hry, Nashovy rovnovážné body.
11. Kooperativní hry, hry s přenosnou výhrou.
12. Hry v koaličním tvaru.
Cvičení (u tabule):
1. Jednoduché odebírací hry.
2. Kombinatorické hry, grafové hry.
3. Hra NIM, Sprague-Grundyova funkce.
4. Sumy her a jejich řešení pomocí Sprague-Grundyovy funkce.
5. Hry dvou hráčů s nulovým součtem ve strategickém tvaru, maticové hry.
6. Dominované strategie, sedlový bod, smíšené strategie.
7. Řešení maticových her ve smíšených strategiích převodem na lineární programování.
8. Lineární programování (dokončení).
9. Hry dvou hráčů s nulovým součtem v rozvinutém tvaru, Kuhnův strom, náhodné tahy, hry s nedokonalou informací.
10. Hry dvou hráčů s obecným součtem ve strategickém tvaru, bimaticové hry, Nashovy rovnovážné body.
11. Kooperativní hry, hry s přenosnou výhrou.
12. Hry v koaličním tvaru.
Obsah cvičení podle osnovy přednášek.
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky
Předmět neobsahuje žádné hodnocení.