Complexity of question/answer games

Question/Answer games (Q/A games for short) are a generalization of the Rényi–Ulam game and they are a model for information extraction in parallel. A Q/A game, G=(D,s,(_q1,…,_qk))$G=(D,s,(q_1,\dots ,q_k))$, is played on a directed acyclic graph, D=(V,E)$D=(V,E)$, with a distinguished start vertex s$s$. In the i$i$th round, Paul selects a set, _Qi⊆V$Q_i\subseteq V$, of at most _qi$q_i$ non-terminal vertices. Carole responds by choosing an outgoing edge from each vertex in _Qi$Q_i$. At the end of k$k$ rounds, Paul wins if Carole’s answers define a unique path from the root to one of the terminal vertices in D$D$.