0
$\begingroup$

Any node can be the starting node and the game is finite (i.e no possible infinite loop). I need to show that for such game there exists a winning strategy for either verifier or the falsifier for every starting node.

$\endgroup$
  • $\begingroup$ Think about using induction on the depth of the graph. $\endgroup$ – mjqxxxx Jan 25 '17 at 18:12
  • $\begingroup$ My idea is to do it recursively. For every leaf nodes, either Verifier and falsifier has the winning strategy. Now for the nodes in n-1 level, we can say the node leading to winning node(in leaf) respective winner from leaf has the winning strategy. But I don't to how to formulate it or even if it is complete. $\endgroup$ – MessitÖzil Jan 25 '17 at 18:26
  • $\begingroup$ Can we be sure that draws are impossible ? $\endgroup$ – Peter Jan 25 '17 at 18:33
  • $\begingroup$ That's what I need to prove, and yes because the game is finite one has to win after n moves. $\endgroup$ – MessitÖzil Jan 25 '17 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.