Kombinatorická teorie her

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra teoretické informatiky

Anotace:

Klasická teorie her je oblastí matematiky, která má široké aplikace ve

společenských vědách, zejména ekonomii, biologii, politice a informatice. Tato

teorie se snaží podchytit chování účastníků (hráčů) určité kompetitivní

činnosti zavedením matematického modelu a studiem strategií hráčů. Tradiční

úkolem klasické teorie her je nalézání rovnovážných bodů, tzv. ekvilibrií. To

jsou stavy hry, ve kterých všichni hráči zaujali takovou strategii, kterou se

jim již nevyplatí měnit.

Vzhledem k současnému rozvoji výpočetní techniky, internetu, sociálních sítí, online

aukcí, reklamy, multiagentních systémů a dalších konceptů

se dostává do popředí zájmu algoritmická stránka věci.

Kromě otázek existenčního charakteru tedy studujeme i otázky efektivního nalezení

efektivních řešení různých konceptů v herně teoretických problémech.

V rámci tohoto předmětu vybudujeme základy teorie her mnoha hráčů,

koncepty řešení (tedy typicky rovnovážných stavů tzv. ekvilibrií) a metody jejich

efektivního výpočtu.

Předmět je zaměřen na teoretickou analýzu her a budováni jejich teorie, nikoli na praktické programování herních algoritmů, zabývá se tedy čistě matematickým aspektem věci. Předmět vyžaduje samostatnou práci studentů, jejich schopnost matematicky myslet, analyzovat a dokazovat.

Předmět je vhodný i pro bakalářské studenty ve třeťáku, kteří za sebou mají nějaký úvod do teorie grafů, i pro doktorské studenty, kteří z něj mohou čerpat výzkumná témata.

Požadavky:

* nebát se obtížné matematiky

* základy teorie grafů a kombinatoriky a algebry

Osnova přednášek:

1) úvod do teorie her 1

2) úvod do teorie her 2

3) problematika nalezení Nashova ekvilibria a třída PPAD 1

4) problematika nalezení Nashova ekvilibria a třída PPAD 2

5) problematika nalezení Nashova ekvilibria a třída PPAD 3

6) teorie voleb, impossibility theorems 1

7) teorie voleb, impossibility theorems 2

8) teorie voleb, impossibility theorems 3

9) gerry mandering

10) kombinatorické aukce

11) mechanism design

12) efektivita ekvilibrií

Osnova cvičení:

Tématické příklady zaměřené na hlubší pochopení látky probírané na přednáškách a na analýzu jednodušších her. Samostatná analýza her a dokazování tvrzení.

Cíle studia:

Cíle přednášky

* Seznámit se s základy klasické teorie her.

* Seznámit se s základy algoritmické teorie her.

* Získat přehled v dalších specializovaných partiích algoritmické teorie her.

Studijní materiály:

Nisan, Roughgarden, Tardos, Vazirani: Algorithmic Game Theory

Dresher: The mathematics of games of strategy

Cramton, Shoham, Steinberg: Combinatorial Auctions

Brandt, Conitzer, Endriss, Lang, Procaccia: Handbook of Computational Social Choice

Rothe: Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division

Poznámka:

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/MI-ATH/

Další informace:

https://courses.fit.cvut.cz/MI-ATH/

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Mgr. obor Znalostní inženýrství, 2016-2017 (volitelný předmět)
• Mgr. obor Počítačová bezpečnost, 2016-2019 (volitelný předmět)
• Mgr. obor Počítačové systémy a sítě, 2016-2019 (volitelný předmět)
• Mgr. obor Návrh a programování vestavných systémů, 2016-2019 (volitelný předmět)
• Mgr. obor Webové a softwarové inženýrství, zaměření Informační systémy a management, 2016-2019 (volitelný předmět)
• Mgr. obor Webové a softwarové inženýrství, zaměření Softwarové inženýrství, 2016-2019 (volitelný předmět)
• Mgr. obor Webové a softwarové inženýrství, zaměření Webové inženýrství, 2016-2019 (volitelný předmět)
• Mgr. program Informatika, pro fázi studia bez oboru, 2016-2019 (volitelný předmět)
• Mgr. obor Systémové programování, zaměření Systémové programování, 2016-2019 (volitelný předmět)
• Mgr. obor Systémové programování, zaměření Teoretická informatika, 2016-2017 (volitelný předmět)
• Mgr. specializace Teoretická informatika, 2018-2019 (volitelný předmět)
• Mgr. obor Znalostní inženýrství, 2018-2019 (volitelný předmět)