| This thesis consists of two chapters.;The first chapter is about the new version of NIM recently introduced by Gurvich together with a generalization of the minimal excludant function (mex). This game NIM(a, b) is played with two piles of matches. Two players alternate turns. By one move, each player can take either "almost the same" number of matches from each pile (the difference of the two numbers is strictly less than a) or any number of matches from one pile and strictly less than b from the other. This game further extends Fraenkel's NIM = NIM(a, 1), which, in its turn, is a generalization of the classic Wythoff NIM = NIM(1, 1).;Gurvich introduced a generalization mexb of the standard minimum excludant mex = mex1 defining mex b(S ⊂ Z+ ) = min{n : ∀s ∈ S s ≤ n ⇒ s + b ≤ n}. He also showed that P-positions (the kernel) of NIM(a, b) are given by the following recursion: xn=mexb xi,yi&vbm0; 0≤i 1 is the Perron root of the polynomial Pz=zb+1-z-1 -i=1a-1z ib/a, whenever a and b are coprime; furthermore, it is known that ℓ(ka, kb) = kℓ(a, b).;In particular, ℓ(a, 1) = alphaa = ½(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 = &fll0;aan&flr0; , yn = xn + an = &fll0;aa+a n&flr0; . 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.;The second chapter of the thesis is about the existence of Nash equilibria (NE) in pure stationary strategies in n-person positional games with no moves of chance, with perfect information, and with the mean or total effective cost function.;We construct a NE-free three-person game with positive local costs, disproving the conjecture suggested by Boros and Gurvich in Math. Soc. Sci. 46 (2003) 207-241.;Still, the following four problems remain open:;Whether NE exist in all two-person games with total effective costs such that (I) all local costs are strictly positive or (II) without directed cycles of the cost zero?;If NE exist in all n-person games with the terminal (transition-free) cost functions, provided all directed cycles form a unique outcome c and (III) assuming that c is worse than any terminal outcome or (IV) without this assumption?;For n = 3 cases (I) and (II) are answered in the negative, while for n = 2 cases (III) and (IV) are proven. We briefly survey other negative and positive results on Nash-solvability in pure stationary strategies for the games under consideration. |
