Asymptotic properties of level-regular decision trees with randomly evaluated leaves (Q1099794)

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.