Branching processes with an adversary
We consider a game played by Bob (the protagonist) against Alice (the adversary), on a tree that is generated by a branching process. The game proceeds as follows. Alice starts at the root of the tree. She is permitted to delete a prespecified number of branches. If she is allowed to delete all the branches at the root, or if the root has no children to start with, Alice is declared a winner. Otherwise, Bob moves second. He chooses one of the branches that remain. The game then moves on to the corresponding node, and the procedure is repeated. Alice is permitted to remove a prespecified number of branches, and Bob chooses one of the branches that remain, if any. Alice's objective is to reach a childless node, or a node where she can remove all the branches. The number of children that a node has and the number of children that Alice is permitted to remove are drawn from the joint distribution independently across the nodes. Does Bob have a chance to win? We establish several sufficient conditions on the distribution of the game such that the probability for Bob to have a winning strategy is positive.
Area: CS31 - Random Games (Xavier Venel)
Keywords: random games; random trees; Galton-Watson trees; dynamic games; value
Please Login in order to download this file