Asymptotic properties of level-regular decision trees with randomly evaluated leaves (Q1099794)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Asymptotic properties of level-regular decision trees with randomly evaluated leaves |
scientific article |
Statements
Asymptotic properties of level-regular decision trees with randomly evaluated leaves (English)
0 references
1989
0 references
Game trees are an important model of decision-making situations, both in artificial intelligence and decision analysis. The model most frequently investigated in theoretical research consists of a uniform tree of height h and a constant branching factor b, where the terminal positions are assigned the values of independent, identically distributed random variables. Our paper investigates two generalizations: (1) Different levels of the tree may have different branching factors; (2) The preferences of the two players may no longer be totally opposite. Our result concerns evaluation functions with a finite range of values. We prove that the induced (minimax) value of the tree's root is with high probability one of only two ``neighbouring'' values. Such a result does not hold for decision trees with three players.
0 references
asymptotic properties
0 references
level-regular decision trees
0 references
randomly evaluated leaves
0 references
game trees
0 references
decision-making
0 references
evaluation functions
0 references
0 references