hidden - assigned and confirmed by the Study Dept.
Date of registration:
26.11.2013
Date of assignment:
03.12.2013
Administrator's approval:
not processed yet
Confirmed by Study dept. on:
11.12.2013
Date and time of defence:
08.09.2015 09:00
Date of electronic submission:
10.08.2015
Date of proceeded defence:
08.09.2015
Submitted/finalized:
committed by student and finalized
Opponents:
doc. Ing. Tomáš Kroupa, Ph.D.
Guidelines
Nashovo ekvilibrium (NE) je jedním ze základních pojmů teorie nekooperativních her. Je to soubor strategií hráčů představujících určitou strategickou rovnováhu - žádný z hráčů nemůže získat výhodu jednostranným odchýlením se od své rovnovážné strategie. Problém existence NE je pro konečné hry je klasickým výsledkem (Nash 1950), byl vyřešen i pro významnou třídu nekonečných her (Glicksberg 1952). Problém nalezení Nashova ekvilibria pro danou hru (NASH) je nejen důležitý z hlediska teorie her, ale i zajímavý z hlediska výpočtové složitosti. Pro hry s nulovým součtem je polynomiální, ale pro obecné nekooperativní hry spadá do speciální třídy PPAD, která spadá mezi P a NP. Kromě problému NASH nabízí tato oblast řadu dalších zajímavých problémů (např. maximální hodnota NE, hodnota NE větší než zadané x, existence dvou různých NE apod.), které jsou pro celou třídu nekooperativních her zpravidla NP úplné. Cílem práce je prozkoumat, zda některé z těchto problémů nebudou pro nějaké užší třídy algoritmicky jednodušší.
References
Martin J. Osborne and Ariel Rubinstein, A course in game theory, (MIT Press, 1994).
Ch. Papadimitiou, Computational Complexity, Addison-Wesley Publishing Company, 1994.
- assigned and confirmed by the Study Dept.