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šší.
Seznam odborné literatury
Martin J. Osborne and Ariel Rubinstein, A course in game theory, (MIT Press, 1994).
Ch. Papadimitiou, Computational Complexity, Addison-Wesley Publishing Company, 1994.
- zadáno a potvrzeno stud. odd.