No label defined (Q3679207)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3900780
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3900780

      Statements

      0 references
      0 references
      1984
      0 references
      games on trees
      0 references
      winning tree
      0 references
      losing tree
      0 references
      random tree
      0 references
      [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.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references