A polynomial algorithm for a two parameter extension of Wythoff NIM based on the Perron-Frobenius theory

Endre Boros, Vladimir Gurvich, Vladimir Oudalov

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

For any positive integer parameters a and b, Gurvich recently introduced a generalization mexb of the standard minimum excludant mex = mex1, 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 + √a2 + 4). In 1982, Fraenkel introduced the game NIM(a) = NIM(a, 1), obtained the above recursion and solved it explicitly getting xn = ⌊ αa n⌊, yn = xn + 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 languageEnglish (US)
Pages (from-to)891-915
Number of pages25
JournalInternational Journal of Game Theory
Volume42
Issue number4
DOIs
StatePublished - 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

Fingerprint Dive into the research topics of 'A polynomial algorithm for a two parameter extension of Wythoff NIM based on the Perron-Frobenius theory'. Together they form a unique fingerprint.

Cite this