Computer Science 789 Online Algorithms

Hint 4 for the Proof of the Game Graph Lemma

Getting a behavioral strategy S from a path set strategy P.

If P is a path strategy, let S be the behavioral strategy defined as follows. If alpha is any path ending at a red node x, and if alpha is a member of P, then there must be some out-edge of x, say (x,y), such that alpha(x,y) is a member of P. If there is more than one such y, pick one, and define S(alpha)=y.

On the other hand, if alpha is not a member of P, define S(alpha)=y where y is an arbitrary node such that (x,y) is an edge. The choice is irrelevant because alpha will never be the path.

Back to Course Page

Back to Assignment Page

Back to Assignment 1