Games on Graphs (Lecture 1,2)

 

Lecture 1

We will try to have a look at the bigger picture on which we will be primarily focused. 

Consider the following directed graph.

Suppose we have two players (P0 and P1). Consider a game where we have a token, which we need to move from one vertex to another. If we are currently on the red circular vertex, it's the turn of P0 and it's of P1 otherwise. 

In simple words, a play is a sequence of vertices (which we represent by $V^{\omega}$). (They are just the sequence of the vertices which are visited by the token.) But a question that we might ask now, is, who will win the game?  To determine the same, we need a function, which we call, the Playoff function ($\pi : V^{\omega}\to \mathbb{R}$ ). 

We call P0, the Minimizer, and P1, the Maximizer. P0 wants to give away the playoff value as less as possible and P1 wants to gain as much as possible. Now let's talk about strategies.

Strategies

Consider the following graph for instance.

Let's say that if one of the purple vertices is visited, P1 wins and P0 otherwise. This can be expressed in the form of the Playoff function. Like the following.

$\pi(\bar{v})=1 \text{ if 8,9 or 10 is reached}$ and $0$ otherwise. Here $\bar{v}$ refers to the play. P0 wants not to reach those vertices (Hence minimizing the playoff) where as P1 wants to (Hence maximizing the playoff function). Strategy of a player (Say P0) is a function $\mu : V^{*}\times V_0\to V$. Similarly we define $\chi$ for P1. If both the players continue to follow their strategies, they will end up in the outcome$(\mu,\chi)$. We are concerned about $\pi(\text{outcome}(\mu,\chi))$. The target of P0 is to get $\inf_{\mu}\sup_{\chi} \pi(\text{outcome}(\mu,\chi))$ and P1 wants $\inf_{\chi}\sup_{\mu} \pi(\text{outcome}(\mu,\chi))$. If both entities are equal, we call the play determined. There are a few kinds of strategies, which include positional strategy which is dependent only on the current position of the token on the graph, and Finite memory strategy which requires the memory of past moves. 

Theorem: If the play is bounded and Borel Measurable, it is determined.

Lecture 2

Reachability

Consider the following graph. 

We say P1 wins if the violet squares are reached and P0 wins otherwise. 

We will classify the vertices in a special way. At Level 0, the purple vertices will be included. At Level 1, we will include those square vertices, from which we can directly reach the Level 0 vertices. At the $n$th level, we will include those square vertices which can directly reach the square vertices of level $n-1$. Apart from the square vertices, we will include the circular vertices,  which only have vertices to the lower levels. In formal language,

$\text{reach}_{1}^{n+1}=\text{reach}_{1}^{n} \cup \{v\in V_1 |\exists v\to w , w\in \text{reach}_1^{n}\} \cup \{v\in V_0 |\forall v\to w , w\in \text{reach}_1^{n}\}$ 

Here $V_1$ refers to the squares and $V_0$ refers to the circular vertices.

We will continue this formula until $\text{reach}_1^{n+1}=\text{reach}_1^{n}$. The remaining vertices are the winning vertices for P0 and all the levels contain vertices that are winning for P1.

Buchi Game

This game is about visiting a vertex infinitely often. P1 wins if the token visits specific vertices infinitely often and P0 wins otherwise. 

 The above diagram shows us the classification of the vertices in a certain manner. The purple region contains the vertices which P1 wants to visit infinitely often. The red region contains the vertices from which P1 can never go to the purple vertices. The transparent orange region is an interesting one. This region becomes a smaller game. P0 wins here if it can force the game to the red region.  

So what are the winning vertices for the players? We will use a recursive algorithm for that.

Buchi_Win(G):

    if reach_1(T)==V:

      (W_0,W_1)=(nil,V)

  else:

      G'=V'\reach_0(V\reach_1(T))

      (W_0',W_1')=Buchi_Win(G')

      (W_0,W_1)=(V\W_1',W_1')

  return(W_0,W_1)   

Running Time: We note that the running time of reach_1(T)is $O(m)$ where $m$ is the number of vertices. This brings us to the recursive relation 

$T(n+1)=T(n)+O(m)$

Which results in the running time of $O(mn)$.