Tomáš Valla - Combinatorial Games Theory

In this thesis we study the complexity that appears when we consider the competitive version of a certain environment or process, using mainly the tools of algorithmic game theory, complexity theory, and others. For example, in the Internet environment, one cannot apply any classical graph algorithm on the graph of connected computers, because it usually requires existence of a central authority, that manipulates with the graph.

We describe a local and distributed game, that in a competitive environment without a central authority simulates the computation of the weighted vertex cover, together with generalisation to hitting set and submodular weight function. We prove that this game always has a Nash equilibrium and each equilibrium yields the same approximation of optimal cover, that is achieved by the best known approximation algorithms. More precisely, the Price of Anarchy of our game is the same as the best known approximation ratio for this problem. All previous results in this field do not have the Price of Anarchy bounded by a constant.

Moreover, we include the results in two more fields, related to the complexity of competitive environments. In positional games, we establish the game size of game variants of several Ramsey-type theorems, and we show that the game sizes are tremendously smaller than the Ramsey sizes. In the field of the cops and robber games, we solve an open question regarding the computational complexity of the so-called guarding game problem - we show that the problem is E-complete for general graphs.

Tématem dizertační práce je studium složitosti, která vzniká, pokud k určitému prostředí či procesu uvážíme jeho kompetitivní variantu, a to především pomocí metod algoritmické teorie her, teorie složitosti, a dalších nástrojů. Například v prostředí Internetu je vyloučeno aplikovat na graf propojených počítačů libovolný klasický grafový algoritmus, protože ten zpravidla vyžaduje existenci centrální autority, která s grafem manipuluje.

V této práci popisujeme distribuovanou a lokálně definovanou hru, která v kompetitivním prostředí bez centrální autority simuluje výpočet váženého vrcholového pokrytí grafu, včetně zobecnění na tzv. hitting set a submodulární váhovací funkci. Dokážeme, že tato hra má vždy Nashovo ekvilibrium a každé toto ekvilibrium dá stejně dobrou aproximaci optimálního pokrytí, jakou lze dosáhnout nejlepšími známými aproximačními algoritmy. Přesněji, tzv. cena anarchie naší hry je stejná jako faktor u nejlepšího známého aproximačního algoritmu. Dosavadní výsledky v této oblasti neměly cenu anarchie omezenu ani konstantou.

Kromě toho v práci předkládáme i výsledky z oblasti her tzv. grafových prohledávacích her a pozičních her, které se týkají složitosti kompetitivního prostředí. V oblasti pozičních her určíme herní velikost (velikost hracího plánu potřebnou pro existenci vítězné strategie prvního hráče) několika herních variant ramseyovských vět, která vyjde podstatně menší než příslušná ramseyovská velikost. Dále vyřešíme otevřenou otázku u varianty prohledávacích her zvané guarding game, u níž dokážeme, že tento problém je v obecnosti E-úplný.