Fakulta informačních technologií VUT v Brně

Detail předmětu

Teorie her

THE Ak. rok 2013/2014 zimní semestr 4 kredity

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

Garant předmětu

Jazyk výuky

česky

Zakončení

zápočet+zkouška (kombinovaná)

Rozsah

26 hod. přednášky, 13 hod. projekty

Bodové hodnocení

60 zkouška, 40 projekty

Zajišťuje ústav

Přednášející

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.

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.

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.

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

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

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.

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

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

  • Program IT-MGR-2, obor MBI, 2. ročník, povinný
  • Program IT-MGR-2, obor MBS, MGM, MIS, MMI, MPV, libovolný ročník, volitelný
  • Program IT-MGR-2, obor MIN, libovolný ročník, povinně volitelný skupina S
  • Program IT-MGR-2, obor MMM, libovolný ročník, povinný
  • Program IT-MGR-2, obor MSK, 1. ročník, povinně volitelný skupina M
Nahoru