Computer Science 789 Online Algorithms

Hint 2 for the Proof of the Game Graph Lemma

To say that Red can win is to say that Red has a winning strategy. We can define a strategy to be a set P of paths in the graph, namely the set of all paths that might occur if Red plays that strategy. P must have the following properties:
  1. If x is any node, then the empty path starting and ending at x is a member of P.
  2. If alpha is a member of P and ends at a black node x and if (x,y) is an edge, then alpha(x,y) is a member of P.
  3. If alpha is a member of P and ends at a red node x then there exists a node y such that (x,y) is an edge and alpha(x,y) is a member of P.
Informally, condition 1 means that the start node is arbitrary, and that Black can stop the game before any moves are made. Condition 2 means that from a black node, Black can make any move. Condition 3 means that from a red node, Red can be forced to make some move.

Do you see how a behavioral strategy S gives rise to a path set strategy P? Do you see how a path set strategy P gives rise to a behavioral strategy S?

Back to Course Page

Back to Assignment Page

Back to Assignment 1