# Winning strategy using Dynamic Programing

Let $$G=(V,E)$$ be a DAG and let $$v_0\in V$$. Alice and Bob are playing a game in which every player has his own turn and Bob is starting. In every turn $$i$$, the player is picking an edge $$e=(v_i,x)$$, then $$x$$ become $$v_{i+1}$$ and then it becomes the other player's turn. The player which doesn't have an edge to choose (the vertex $$v_i$$ has no out edges) is losing.

Propose an algorithm which determines if Bob has a winning strategy.

• What do you think? What have you tried? Where did you get stuck? – Yuval Filmus Jun 30 at 11:04

For a vertex $$v \in V$$, let $$W(v)$$ be the following predicate: "a player starting at $$v$$ wins". If $$N(v)$$ is the set of outward neighbors of $$v$$, then $$W(v) = \bigvee_{u \in N(v)} \lnot W(u),$$ where the empty disjunction is simply false.
This suggests a strategy to compute $$W(v_0)$$ using dynamic programming.