  Suzuki and Niida (Ann. Pure. Appl. Logic, 2015) showed the following results
on independent distributions (IDs) on an AND-OR tree, where they took only
depth-first algorithms into consideration. (1) Among IDs such that probability
of the root having value 0 is fixed as a given r such that 0 < r < 1, if d is a
maximizer of cost of the best algorithm then d is an independent and identical
distribution (IID). (2) Among all IDs, if d is a maximizer of cost of the best
algorithm then d is an IID. In the case where non-depth-first algorithms are
taken into consideration, the counter parts of (1) and (2) are left open in the
above work. Peng et al. (Inform. Process. Lett., 2017) extended (1) and (2) to
multi-branching trees, where in (2) they put an additional hypothesis on IDs
that probability of the root having value 0 is neither 0 nor 1. We give
positive answers for the two questions of Suzuki-Niida. A key to the proof is
that if ID d achieves the equilibrium among IDs then we can chose an algorithm
of the best cost against d from depth-first algorithms. In addition, we extend
the result of Peng et al. to the case where non-depth-first algorithms are
taken into consideration.
