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
1984
0 references
games on trees
0 references
winning tree
0 references
losing tree
0 references
random tree
0 references
0.7924264669418335
0 references
0.7845470905303955
0 references
0.7781105041503906
0 references
0.7761014699935913
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