Teorie grafických her - Graphical game theory
v herní teorie, běžnými způsoby, jak hru popsat, jsou normální forma a rozsáhlá forma. Grafická forma je alternativní kompaktní reprezentace hry pomocí interakce mezi účastníky.
Zvažte hru s hráči s strategie každý. Budeme reprezentovat hráče jako uzly v grafu, ve kterém má každý hráč a užitková funkce to záleží jen na něm a jeho sousedech. Protože funkce obslužného programu závisí na menším počtu ostatních hráčů, grafické znázornění by bylo menší.
Formální definice
Grafickou hru představuje graf , ve kterém je každý hráč reprezentován uzlem a mezi dvěma uzly je hrana a pokud jsou jejich užitné funkce závislé na strategii, kterou si druhý hráč zvolí. Každý uzel v má funkci , kde je stupeň vrcholu . určuje užitečnost přehrávače v závislosti na jeho strategii i strategii jeho sousedů.
Velikost reprezentace hry
Pro generála hra hráčů, ve které má každý hráč možné strategie, velikost normální formy reprezentace by byla . Velikost grafického znázornění pro tuto hru je kde je maximální stupeň uzlu v grafu. Li , pak je grafické znázornění hry mnohem menší.
Příklad
V případě, že funkce nástroje každého hráče závisí pouze na jednom dalším hráči:
Grafická podoba popsané hry
Maximální stupeň grafu je 1 a hru lze popsat jako funkce (tabulky) velikosti . Celková velikost vstupu tedy bude .
Nashova rovnováha
Nalezení Nashovy rovnováhy ve hře vyžaduje exponenciální čas ve velikosti reprezentace. Pokud je grafickým znázorněním hry strom, můžeme najít rovnováhu v polynomiálním čase. V obecném případě, kde je maximální stupeň uzlu 3 nebo více, je problém NP-kompletní.
Další čtení
- Michael Kearns (2007) "Grafické hry ". V Vazirani, Vijay V.; Nisan, Noame; Roughgarden, Tim; Tardos, Éva (2007). Algoritmická teorie her (PDF). Cambridge, Velká Británie: Cambridge University Press. ISBN 0-521-87282-0.
- Michael Kearns, Michael L. Littman a Satinder Singh (2001) "Grafické modely pro teorii her ".