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:
-
If x is any node, then the empty path starting and ending at
x is a member of P.
-
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.
-
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