Cops and Robbers on Graphs (C & R) is a vertex-to-vertex pursuit game played on graphs first introduced by Quilliot (in 1978) and Nowakowski (in 1983). The cop player starts the game by choosing a set of vertices which will be the cops’ starting positions. The robber player responds by choosing its own start vertex. On each player’s turn, the player may move its tokens to adjacent vertices. The cops win if the robber is captured (they occupy the same vertex). The robber wins if it can avoid capture indefinitely. The question, then, is to determine the smallest number of cops required to guarantee the robber will be captured. A variation of C & R called Zombies and Survivors (Z & S) was recently proposed and studied by Fitzpatrick. Z & S is the same as C & R with the added twist that the zombies are required to move closer to the survivor (by following a shortest path from the zombie to the survivor). Whenever multiple shortest paths exist, the zombies are free to choose which one to follow. As in C & R, we are interested in the minimum number of zombies required to guarantee the survivor will be caught. Chapter 1 summarizes important results in vertex-pursuit games. In Chapter 2 we give an example of a planar graph where 3 zombies always lose, whereas Aigner and Fromme showed in 1984 that three cops have a winning strategy on planar graphs. In Chapter 3 we show how two zombies can win on a cycle with one chord.

Title: Combinatorial Games Theory Author: Tomáš Valla Department / Institute: IUUK MFF UK Supervisor: Prof. RNDr. Jaroslav Nešetřil, DrSc., IUUK MFF UK Abstract: 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 al- gorithmic 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 manipu- lates 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 func- tion. 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 ap- proximation 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...