Mikołaj Bojańczyk

A safety game. safety game is a kind of game of infinite duration and perfect information, played by two players. The game is defined by an arena, which is a directed graph plus a function which says for each vertex (which is called a position of the game) which of the two players own this vertex. Here is a picture of an arena, with the players being called 0 and 1:

safety-game

Given an initial position, the game is played as follows: at each step the player who owns the current position chooses an outgoing edge, and so on until either an infinite path is created (in which case the player 0 wins), or a position is reached which does not have outgoing edges (in which the player who cannot make a move loses, i.e. the player who does not own the last position wins).

Theorem. Given a safety game with a finite arena and an initial position, one can decide in polynomial time which of the two players has a winning strategy. Furthermore, the player who has a winning strategy also has a memoryless winning strategy, which means that the choice of next position depends only on the current position and not on the history of the game before reaching that position.

Proof. We define a sequence of sets of positions where player 1 can force a victory in a finite number of positions. Define V_0 to be the empty set, and define V_{n} to be V_{n-1} plus those positions v such that either:
v is owned by player 0, and all outgoing edges from v go into V_{n-1}; or
v is owned by player 1, and some outgoing edge from v goes into V_{n-1}.

For example, V_1 consists of positions owned by player 0 which have no outgoing edges. It is easy to see that for positions in V_n, player 1 has a memoryless strategy which guarantees victory in at most n steps, i.e. in at most n steps player 0 will end up in a position without outgoing edges. If the arena is finite, the sequence V_n must stabilize at some set, call it V_*. As mentioned above, player 1 has a winning strategy that guarantees winning on all positions from V_*. We claim that player 0 has a memoryless winning strategy in positions outside V_*. This is because by definition, if a position is not in V_*, then either it belongs to player 0 and has at least one outgoing edge that stays outside V_*, or it belongs to player 1 and has all outgoing edges that stay outside V_*. The strategy of player 0 is to use the edge the stays outside V_*. \Box

In future lectures, we will also consider safety games with possibly infinite arenas. Of course the part of the above theorem about polynomial time no longer makes sense, but the part about memoryless strategies continues to be true. Consider the proof of the above theorem, and apply it to an infinite arena. Instead of indexing the sets V_n by natural numbers, one can index them by ordinal numbers. For ordinal numbers, instead of V_{n-1} one talks about the union of V_m ranging over ordinal numbers m < n. The set V_n is guaranteed to stabilize for some ordinal.

 

Leave a Reply

Your email address will not be published.