## Abstract

For any positive integer parameters a and b, Gurvich recently introduced a generalization mex_{b} of the standard minimum excludant mex = mex_{1}, along with a game NIM(a, b) that extends further Fraenkel's NIM = NIM(a, 1), which in its turn is a generalization of the classical Wythoff NIM = NIM(1, 1). It was shown that P-positions (the kernel) of NIM(a, b) are given by the following recursion: (Formula presented.), and conjectured that for all a, b the limits ℓ(a, b) = x _{n}(a, b)/n exist and are irrational algebraic numbers. In this paper we prove that showing that ℓ(a,b) = a/r-1, where r > 1 is the Perron root of the polynomial(Formula presented.) whenever a and b are coprime; furthermore, it is known that ℓ(ka, kb) = kℓ(a, b). In particular, ℓ(a, 1) = α_{a} = 1/2 (2 - a + √a^{2} + 4). In 1982, Fraenkel introduced the game NIM(a) = NIM(a, 1), obtained the above recursion and solved it explicitly getting x_{n} = ⌊ α_{a} n⌊, y_{n} = x_{n} + an = ⌊ (α_{a} + a) n ⌊. Here we provide a polynomial time algorithm based on the Perron-Frobenius theory solving game NIM(a, b), although we have no explicit formula for its kernel.

Original language | English (US) |
---|---|

Pages (from-to) | 891-915 |

Number of pages | 25 |

Journal | International Journal of Game Theory |

Volume | 42 |

Issue number | 4 |

DOIs | |

State | Published - Nov 2013 |

## All Science Journal Classification (ASJC) codes

- Statistics and Probability
- Mathematics (miscellaneous)
- Social Sciences (miscellaneous)
- Economics and Econometrics
- Statistics, Probability and Uncertainty

## Keywords

- Algebraic number
- Asymptotic
- Combinatorial and impartial games
- Fraenkel's NIM
- Kernel
- Minimum excludant
- NIM
- Wythoff's NIM