scientific article; zbMATH DE number 3900780

From MaRDI portal
Publication:3679207





[For the entire collection see Zbl 0547.00011.] The authors consider the following game, played on a finite rooted tree by two players who take alternating turns: the first player occupies a node adjacent to the root; on succeeding turns a player occupies a previously-unoccupied node adjacent to the one last occupied, if such a node exists. The winner is the player who first occupies an end-node. A tree is winning if the first player has a winning strategy; if not, then the second player has a winning strategy and the tree is called losing. In the first part of the paper the authors show that for a certain kind of family of trees called simply-generated (a condition on the generating function for the number of n-node trees in the family, implying that if the root is removed from a tree in the family, all the remaining components are members of the family), the ratio of winning n-trees to all n-trees in the family approaches a limit. This limit is at least one- half for any simply-generated family; its value is given for certain common families such as the family of binary trees. In the remainder of the paper the authors restrict the strategies allowed the players to a certain class (the admissible strategies), and consider the probability that the first player wins if an n-node tree is chosen at random from a simply-generated family of trees and the players adopt a fixed pair of admissible strategies. An expression for the limiting value of this probability is obtained, and is evaluated for certain families of trees and certain pairs of simple strategies.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3679207)