Detail předmětu

Teorie her

FIT-THEAk. rok: 2009/2010

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ší.

Jazyk výuky

čeština

Počet kreditů

4

Garant předmětu

Ing. Martin Hrubý, Ph.D.

Zajišťuje ústav

Ústav inteligentních systémů (UITS)

Výsledky učení 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.

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.

Prerekvizity

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.

Způsob a kritéria hodnocení

Vypracování individuálního projektu a získání alespoň poloviny bodů (20 ze 40).

Osnovy výuky

  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

Učební cíle

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.

Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky

Kontrolovanou výukou jsou projekt a závěrečná zkouška. Závěrečná zkouška má dva náhradní termíny.

Základní literatura

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

Doporučená literatura

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

Zařazení předmětu ve studijních plánech

  • Program IT-MGR-2 magisterský navazující

    obor MBI , 2 ročník, zimní semestr, povinný
    obor MBS , 0 ročník, zimní semestr, volitelný
    obor MGM , 0 ročník, zimní semestr, volitelný
    obor MGM , 0 ročník, zimní semestr, volitelný
    obor MIN , 0 ročník, zimní semestr, povinně volitelný
    obor MIN , 0 ročník, zimní semestr, volitelný
    obor MIS , 0 ročník, zimní semestr, volitelný
    obor MIS , 0 ročník, zimní semestr, volitelný
    obor MMI , 0 ročník, zimní semestr, volitelný
    obor MMM , 2 ročník, zimní semestr, povinný
    obor MPS , 0 ročník, zimní semestr, volitelný
    obor MPV , 0 ročník, zimní semestr, volitelný
    obor MSK , 2 ročník, zimní semestr, povinně volitelný

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

Ing. Martin Hrubý, Ph.D.

Osnova

  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

Projekt

13 hod., nepovinná

Vyučující / Lektor

Ing. Martin Hrubý, Ph.D.