Abstract
The work reported here is our first attempt to investigate the equilibria of independent distributions (ID) on unbalanced game trees, after a long series of studies on balanced AND-OR trees, e.g., Liu and Tanaka (Inform Process Lett 104(2):73–77, 2007; Liu and Tanaka (The computational complexity of game trees by eigen-distribution. In: Proceeding 436 of the 1st International Conference on COCOA, pp. 323–334, 2007; Suzuki and Niida (Ann Pure Appl Log 166(11):1150–1164, 2015; Peng et al. (Inform Process Lett 125:41–45, 2017; Suzuki (Ann Jpn Assoc Philos Sci 25:79–88, 2017; Inform Process Lett 139:13–17, 2018); Peng et al. (Methodol Comput Appl Probab 24:277–287, 2022). To handle an unbalanced tree, we decompose the tree into subtrees with different weights (= costs). The present research not only generalizes our previous results on balanced trees to unbalanced weighted trees, but also gives simpler inductive proofs and new perspectives for some old results. Our primary objective is to characterize the “eigen-distribution" \(d \in \) ID(r) for a weighted game tree (with a fixed probability for the root having value 0 as \(0<r<1\)), which achieves the distributional complexity. In this paper, we introduce two new concepts on independent distributions: “proportional" ID (PID for short) and “decent" ID. For \(0<r<1\), a PID (r) on a weighted tree is uniquely constructed by a technique “Super-RAT" which is inspired by the reverse assigning technique (RAT) for the CD case in Liu and Tanaka (Inform Process Lett 104(2):73–77, 2007). As a main theorem, we show that if the eigen-distribution \(d \in \) ID(r) is decent then it is a PID, from which we can deduce our previous theorem in Peng et al. (Inform Process Lett 125:41–45, 2017) that for a balanced AND-OR tree (without weights), the eigen-distribution \(d \in \) ID(r) is an IID.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Data Availibility Statement
The data used to support the findings of this study are included within the article.
Notes
Although the term “game tree” is often used in a broader sense Baudet (1978), in this paper we refer to game trees as above.
References
Baudet GM (1978) On the branching factor of the alpha-beta pruning algorithm. Artif Intell 10(2):173–199
Ben-Dov Y (1981) Optimal testing procedures for special structures of coherent systems. Manage Sci 27:1410–1420
Liu CG, Tanaka K (2007) Eigen-distribution on random assignments for game trees. Inform Process Lett 104(2):73–77
Liu CG, Tanaka K (2007) The computational complexity of game trees by eigen-distribution. In: Proceeding of the 1st International Conference on COCOA, 323–334
Okisaka S, Peng W, Li W, Tanaka K (2017) The eigen-distribution of weighted game trees. In: The 11th Annual International Conference on COCOA, 286–297
Pearl J (1980) Asymptotic properties of minimax trees and game-searching procedures. Artif Intell 14(2):113–138
Peng W, Okisaka S, Li W, Tanaka K (2016) The uniqueness of eigen-distribution under non-directional algorithms. IAENG Int J Comput Sci 43(3):318–325
Peng W, Peng N, Ng K, Tanaka K, Yang Y (2017) Optimal depth-first algorithms and equilibria of independent distributions on multi-branching trees. Inform Process Lett 125:41–45
Peng W, Peng N, Tanaka K (2022) The eigen-distribution for multi-branching weighted trees on independent distributions. Methodol Comput Appl Probab 24:277–287
Saks A (1986) Wigderson, probabilistic boolean decision trees and the complexity of evaluating game trees. In: Proceeding of 27th Annual IEEE Symposium on FOCS, 29–38
Suzuki T, Nakamura R (2012) The eigen distribution of an AND-OR tree under directional algorithms. IAENG Int J Appl Math 42(2):122–128
Suzuki T, Niida Y (2015) Equilibrium points of an AND-OR tree: under constraints on probability. Ann Pure Appl Logic 166(11):1150–1164
Suzuki T (2017) Kazuyuki Tanaka’s work on AND-OR trees and subsequent developments. Ann Jpn Assoc Philos Sci 25:79–88
Suzuki T (2018) Non-depth-first search against independent distributions on an AND-OR tree. Inform Process Lett 139:13–17
Tarsi M (1983) Optimal search on some game trees. J ACM 30(3):389–396
Yao ACC (1977) Probabilistic computations: toward a unified measure of complexity. In: Proceeding 18th Annual IEEE Symposium on FOCS, 222–227
Acknowledgements
The work was supported by the Natural Science Foundation of Beijing, China (Grant No. IS23001), the JSPS KAKENHI (Grant No. 21H03392), and the National Natural Science Foundation of China (Grant No. 11701438). We thank the anonymous referees for their valuable comments in improving the this paper.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare no Conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Tanaka, K., Peng, N.N., Peng, W. et al. The equilibria of independent distributions on unbalanced game trees. Comp. Appl. Math. 43, 267 (2024). https://doi.org/10.1007/s40314-024-02784-6
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s40314-024-02784-6