Název:

Teorie her

Zkratka:THE
Ak.rok:2011/2012
Semestr:zimní
Studijní plán:
ProgramOborRočníkPovinnost
IT-MGR-2MBI2.povinný
IT-MGR-2MBS-volitelný
IT-MGR-2MGM-volitelný
IT-MGR-2MGM.-volitelný
IT-MGR-2MIN-povinně volitelný - skupina S
IT-MGR-2MIN.-volitelný
IT-MGR-2MIS-volitelný
IT-MGR-2MIS.-volitelný
IT-MGR-2MMI-volitelný
IT-MGR-2MMM2.povinný
IT-MGR-2MPS-volitelný
IT-MGR-2MPV-volitelný
IT-MGR-2MSK1.povinně volitelný - skupina M
Vyučovací jazyk:čeština
Informace pro zapsané:http://www.fit.vutbr.cz/study/courses/THE/private/
Kredity:4 kredity
Ukončení:zápočet+zkouška (kombinovaná)
Výuka:
hod./sempřednáškasem./cvičenílab. cvičenípoč. cvičeníjiná
Rozsah:2600013
 zkouškatestycvičenílaboratořeostatní
Body:6000040
Garant:Hrubý Martin, Ing., Ph.D., UITS
Přednášející:Hrubý Martin, Ing., Ph.D., UITS
Fakulta:Fakulta informačních technologií VUT v Brně
Pracoviště:Ústav inteligentních systémů FIT VUT v Brně
 
Cíle předmětu:
  Cílem předmětu je poskytnout studentům vzdělání v oblasti racionálního strategického rozhodování v konfliktních situacích, naučit je vytvářet modely těchto situací, na základě modelů situace analyzovat a případně predikovat jejich vývoj a následky. Předmět doplňuje výuku umělé inteligence o oblast strategického rozhodování. Aplikace a použití budou směřovány do informatiky (řízení, rozhodování, bezpečnost, hraní her, sítě) a také do společenských věd jako jsou ekonomie, sociologie a mezinárodní vztahy.
Anotace:
  Předmět se zabývá Matematickou teorií her, která někdy také bývá nazývána jako Teorie interaktivního rozhodování. Teorie her se stala vyhledávaným nástrojem pro analýzu chování inteligentních jedinců v mnoha situacích soupeření nebo spolupráce. Tradičně bývá tato matematická teorie aplikována v oblastech řízení, ekonomických modelech, psychologii, sociologii, mezinárodních vztazích, evoluční biologii, ale taky v informatice (například v sítových protokolech). Z pohledu informatiky je teorie her rozšířením oboru umělé inteligence o algoritmy rozhodování, soupeření a vyjednávání. Souvisí částečně s multi-agentními přístupy. Hry budou považovány za modely reálných či imaginárních situací s prvky inteligence a soupeření. Studenti se v rámci tohoto předmětu seznámí se základním dělením her podle mechanismu provádění hry (sekvenční, strategické), rozložení zisků ve hře (s nulovým/nenulovým součtem), možnosti případné spolupráce (kooperativní, nekooperativní) a dále dle stavu informace ve hře (s neúplnou/úplnou informací). Po úvodním pochopení základních principů bude zaveden prvek opakování do hry (repeated games) a jeho vliv na chování hráčů. V druhé polovině předmětu budou rozebírány aplikace teorie her, mechanism design a jeho aplikace v aukcích nebo veřejných volbách, ekonomické modely trhu a další.
Požadované prerekvizitní znalosti a dovednosti:
  Studenti by měli mít základní znalosti diskrétní matematiky, algebry a matematické analýzy jako základních prostředků pro popis řešených problémů. Z ryze informatických prerekvizit je vyžadována znalost základů modelování a simulace, a dále pak základů umělé inteligence.
Získané dovednosti, znalosti a kompetence z předmětu:
  Základní získanou znalostí bude přehledová znalost teorie her a množství jejích návazných aplikací v technice a společenských vědách. Studenti by měli být po absolvování předmětu schopni vytvořit jednoduchý model zadané herní situace a predikovat její pravděpodobný vývoj.
Dovednosti, znalosti a kompetence obecné:
  V obecnější rovině dává studium racionálního rozhodování jistou průpravu ve schopnosti problémy analyzovat, hledat možné strategie v jejich řešení, strategiím přisuzovat možný užitek a v rámci toho se pak správně rozhodovat. Matematické modely v teorii her také ukazují jasná řešení mnoha problémů v běžném životě. Navíc předmět přináší řadu aplikací informatiky v přírodních a společenských vědách.
Osnova přednášek:
 
  1. Úvod, historie vzniku TH, motivace pro studium TH, základní pojmy, teorie volby, základní dělení her, vliv informace na hru.
  2. Dvouhráčové hry s nulovým součtem: koncepce, sedlový bod, minimax theorem.
  3. Dvouhráčové hry s nenulovým součtem: koncepce, dominance strategií, Nashovo ekvilibrium, základní postupy nalezení Nashova ekvilibria.
  4. Matematické metody ve hrách s nenulovým součtem - rozbor důkazu Nashovy věty o existenci ekvilibria v konečných hrách, algoritmy výpočtu ekvilibria, grafické řešení her, lineární programování.
  5. Sekvenční hry s úplnou/neúplnou informací: aplikace sekvenčních her, Stackelbergovo ekvilibrium, zpětná indukce.
  6. Kooperativní hry a vyjednávání (bargaining): rozbor předpokladů pro kooperativní jednání hráčů, rozbor situace vyjednávání ve hrách s nenulovým součtem, Nash bargaining solution.
  7. Opakované hry: koncepce (konečný/nekonečný počet opakování), řešení. Aplikace opakovaných her. Vliv opakování na strategické chování.
  8. Mechanism design: základy podoboru Mechanism design. Volba v situaci neúplné informace.
  9. Veřejná volba, volební mechanismy: Arrowsův paradox, mechanismy voleb.
  10. Aukce: zkoumání racionality v aukčních mechanismech. Aplikace v obchodu.
  11. Korelované ekvilibrium: vliv korelovanosti na chování hráčů, definice korelovaného ekvilibria a jeho vztah k Nashově ekvilibriu, výpočet korelovaného ekvilibria, aplikace.
  12. Evoluční biologie: strategické chování v kolektivu mnoha jedinců, evolučně stabilní strategie, příklady z přírody.
  13. Aplikace v ekonomii, aplikace v technice" základní modely oligopolů v analytickém a simulačním řešení, rozbor netriviální případové studie ekonomického modelu. Aplikace TH v počítačových sítích. Aplikace v psychologii, sociologii a mezinárodních vztazích
Osnova ostatní - projekty, práce:
 V rámci předmětu studenti vypracují individuální projekt z jedné ze tří oblastí:
  • Studijní - detailní studium zadaného vědeckého článku a jeho rozbor.
  • Implementační - implementace zvoleného algoritmu.
  • Aplikační - případová studie zvoleného problému vedoucí k jeho modelu.
Literatura referenční:
 
  • různí autoři: Classics in Game Theory, edited by Harold W. Kuhn, Princetown University Press, 1997
  • Cesa-Bianci, N., Lugosi, G.: Prediction, Learning, and Games, Cambridge University Press, 2006
  • Shubik, M.: Game Theory in the Social Sciences: Concepts and Solutions, MIT Press, 1984
  • Dresher, M.: The Mathematics of Games of Strategy, Theory and Applications, Dover Publications, 1981
  • McCarty, N., Mierowitz, N.: Political Game Theory: An Introduction, Cambridge University Press, 2007
  • různí autoři: Algorithmic Game Theory, edited by Noam Nisan, Cambridge University Press, 2006
  • Osbourne, M.J., Rubinstein, A.: A Course in Game Theory, MIT Press, 1994
  • Fudenberg, D., Tirole, J.: Game Theory, MIT Press, 1991
  • Dorfman, R., Samuelson, P.A., Solow, R. M.: Linear Programming and Economic Analysis, Dover Publications, 1986
  • Schelling, T. S. : The Strategy of Conflict, Harvard Press, 1980
  • Dugatkin, L., Reeve, H.: Game Theory and Animal Behavior, Oxford University Press, 1988
  • Morrow, J.: Game Theory for Political Scientists, Princeton University Press, 1994
  • Kreps, D.: Game Theory and Economic Modelling, Oxford University Press, 1990
  • von Neumann, J.,  Morgenstern, O.: Theory of Games and Economic Behavior, Princeton University Press, 1944
  • Mailath, G., Samuelson, L.: Repeated Games and Reputations, Oxford University Press, 2006
  • Krishna, V.: Auction Theory, Elsevier, 2002
  • Gintis, H.: Game Theory Evolving, Princeton University Press, 2000
  • Miller, J.: Game Theory at Work, McGraw-Hill, 2003
  • Straffin, P.D.: Game Theory and Strategy, The Mathematical Association of America, 2003
  • Rasmunsen, E.: Games and Information, Blackwell Publishing, 2007
Literatura studijní:
 
  • Straffin, P.D.: Game Theory and Strategy, The Mathematical Association of America, 2003
  • Gibbons, R.: Game Theory for Applied Economists, Princeton University Press, 1992
  • Osbourne, M.J., Rubinstein, A.: A Course in Game Theory, MIT Press, 1994
Kontrolovaná výuka:
  Kontrolovanou výukou jsou projekt a závěrečná zkouška. Závěrečná zkouška má dva náhradní termíny. Pro získání bodů ze zkoušky je nutné zkoušku vypracovat tak, aby byla hodnocena nejméně 20 body. V opačném případě bude zkouška hodnocena 0 body.
Podmínky zápočtu:
  Vypracování individuálního projektu a získání alespoň poloviny bodů (20 ze 40).