A safety game. A 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 and :

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 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 can force a victory in a finite number of positions. Define to be the empty set, and define to be plus those positions such that either:
• is owned by player , and all outgoing edges from go into ; or
• is owned by player , and some outgoing edge from goes into .

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

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 by natural numbers, one can index them by ordinal numbers. For ordinal numbers, instead of one talks about the union of ranging over ordinal numbers . The set is guaranteed to stabilize for some ordinal.

 

COMMENTS