Extended Sprague-Grundy theory for locally finite games, and applications to random game-trees. (English) Zbl 1490.91042
Summary: The Sprague-Grundy theory for finite games without cycles was extended to general finite games by Cedric Smith and by Aviezri Fraenkel and coauthors. We observe that the same framework used to classify finite games also covers the case of locally finite games (that is, games where any position has only finitely many options). In particular, any locally finite game is equivalent to some finite game. We then study cases where the directed graph of a game is chosen randomly, and is given by the tree of a Galton-Watson branching process. Natural families of offspring distributions display a surprisingly wide range of behavior. The setting shows a nice interplay between ideas from combinatorial game theory and ideas from probability.
MSC:
| 91A46 | Combinatorial games |
| 91A43 | Games involving graphs |
| 60J80 | Branching processes (Galton-Watson, birth-and-death, etc.) |
References:
| [1] | Proof. First we note that all finite Sprague-Grundy values have positive probability, up to the maximum out-degree d if there is one. This is easy by induction. We know that value 0 is possible since any terminal position has value 0. If values 0, 1, . . . , k − 1 are possible, and it is possible for the root to have degree k or larger, then there is positive probability that the set of values of the children of the root is precisely {0, 1, . . . , k − 1}, giving value k to the root as required. Now for part (a), since draws are possible, the value ∞(B) has positive probability for some B not containing 0. In that case, there is positive probability for all the children of the root to have value ∞(B), and then the root has value ∞(∅). So the value ∞(∅) has positive probability. Now if A is any finite set such that ∪ {∞(∅)}, and in that case the value of the root is ∞(A) as required. Finally, if |A| is greater than or equal to the maximum degree, then the value ∞(A) is impossible, since any vertex with such a value must have at least one child with value m for each m ∈ A, and additionally at least one child with infinite rank. We can derive the result for part (b) by applying part (a) to the Galton-Watson tree T (k) obtained by conditioning the root to have Sprague-Grundy value not in {0, 1, . . . , k − 1}, and removing all the vertices with values {0, 1, . . . , k − 1} from the graph, as described above. Theorem 3.1 tells us that if the resulting tree has positive probability to have a node with value ∞(A), then the original tree has positive probability to have a node with value ∞(B) where B = {b ≥ k : b − k ∈ A} ∪ {0, 1, . . . , k − 1}, and the desired results follow. |
| [2] | Remark 4.8. Suppose we have a Galton-Watson tree T with positive probability to be infinite, and a set C of Sprague-Grundy values with P(G(o) ∈ C) > 0. A straightforward extension of Lemma 4.1 says that conditional on T being infinite, with probability 1 there exists u ∈ T with G(u) ∈ C. Combining with Proposition 4.7, we get the following appealing property. If T has unbounded vertex degrees, and positive probability of draws, then conditional on Poisson(λ(1 − P ))-distributed, and the two are independent. If we condition the root to have at least one P-child, and then remove all its P-children, then because of the independence of the number of P-children and the number of N -children, we are simply left with a Poisson(λ(1 − P )) number of children. So we again have a Poisson Galton-Watson tree, but now with a new parameter |
| [3] | < λ. Since λ (1) < e, the new tree is still draw-free with probability 1. Hence, to adapt the terminology of the introduction, in the Poisson case we may see a “blatantly infinite” game once λ > e, but for λ ≤ e we are at worst “latently infinite”. There is no λ which gives “patently infinite” behavior whereby draws are p ∈ (0, 1). If p ≤ a 0 := 1/4 then the mean offspring size is less than or equal to 1, and the tree is finite with probability 1. One can show algebraically that there is positive probability of a draw if and only if p > a 2 := 5 3/4 ≈ 0.83593. Namely one can obtain that the function h defined in (4.2) has derivative less than 1 on [0, 1] for all p ≤ a 2 (except for a single point in the case p = a 2 ), and so r has just one fixed point for such p. Meanwhile for p > a 2 there is a fixed point s * of the function 1 − φ for which h (s * ) > 1, and this can be used to show that r has at least two further fixed points. Corollary 4.3 then gives the result. Between a 0 and a 2 there exist no draws, but the tree is infinite with positive probability, so we may ask whether there can exist positions with infinite rank. Numerically, we observe a phase transition around the point a 1 ≈ 0.52198. For p ≤ a 1 , we know that the tree T has zero probability of a draw, and we observe that the same is also true for the trees T (1) and T (2) (their maximum out-degrees are 3 and 2 respectively, so their generating functions φ (1) and φ (2) are cubic and quadratic respectively. The tree T (3) has vertices of out-degrees only 0 and 1, and will also be finite with probability 1, so we do not need to examine T (k) for any higher k.) Hence for p ∈ (a 0 , a 1 ], we have the “latently infinite” phase where all Sprague-Grundy values are finite with probability 1. However, for p ∈ (a 1 , a 2 ] we observe that the function h (1) (s) := 1 − φ (1) (1 − φ (1) (s)) has more than one fixed point. Consequently, there is positive probability of a draw in the tree T (1) . The tree T has positive probability not to be 1-stable, and so to have positions of infinite rank. The behavior of h, h (1) and h (2) around the phase transition point p = a 1 is shown in Figure 5.1. Although the precise nature and location of this phase transition is only found numerically, it is not hard to show rigorously that for p just above a 0 , the functions h (1) and h (2) have only one fixed point, while for p just below a 2 , the References |
| [4] | E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays, Volume 2, 2nd edition, CRC Press, 2003. · Zbl 1083.00003 |
| [5] | A. S. Fraenkel and Y. Perl, Constructions in combinatorial games with cycles, in Infinite and Finite Sets (to Paul Erdős on his 60th birthday), Volume 2, ed. A. Hajnal, R. Rado, and V. Sós, pp. 667-699, North-Holland, 1975. · Zbl 0332.90053 |
| [6] | A. S. Fraenkel and O. Rahat, Infinite cyclic impartial games, Theor. Comp. Sci. 252 (2001), 13-22. · Zbl 0976.91008 |
| [7] | A. S. Fraenkel and U. Tassa, Strategy for a class of games with dynamic ties, Comput. Math. Appl. 1 (1975), 237-254. · Zbl 0348.90177 |
| [8] | A. S. Fraenkel and Y. Yesha, The generalized Sprague-Grundy function and its invariance under certain mappings, J. Comb. Thy. A 43 (1986), 165-177. · Zbl 0622.05030 |
| [9] | G. Grimmett and D. Welsh, Probability: an Introduction, 2nd edition, Oxford University Press, Oxford, 2014. · Zbl 1302.60005 |
| [10] | R. K. Guy and C. A. B. Smith, The G-values of various games, Math. Proc. Camb. Phil. Soc. 52 (1956), 514-526. · Zbl 0074.34503 |
| [11] | A. E. Holroyd, Percolation Beyond Connectivity, PhD thesis, Univ. Cambridge, 2000. |
| [12] | A. E. Holroyd and J. B. Martin, Galton-Watson games, Random Structures & Algorithms, to appear, DOI 10.1002/rsa.21008. · Zbl 1541.91053 · doi:10.1002/rsa.21008 |
| [13] | R. M. Karp and M. Sipser, Maximum matching in sparse random graphs, in 22nd Annual Symposium on Foundations of Computer Science, pp. 364-375, IEEE, 1981. |
| [14] | J.-F. Le Gall, Random trees and applications, Probab. Surveys 2 (2005), 245-311. · Zbl 1189.60161 |
| [15] | A. N. Siegel, Combinatorial Game Theory, Amer. Math. Soc., Providence, Rhode Island, 2013. · Zbl 1288.91003 |
| [16] | C. A. Smith, Graphs and composite games, J. Comb. Thy. 1 (1966), 51-81. · Zbl 0141.36101 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
