Two new computer based results in game theory related to combinatorial games and Nash equilibria
Citation & Export
Hide
Simple citation
Oudalov, Vladimir.
Two new computer based results in game theory related to combinatorial games and Nash equilibria. Retrieved from
https://doi.org/doi:10.7282/T33R0RKBExport
Description
TitleTwo new computer based results in game theory related to combinatorial games and Nash equilibria
Date Created2013
Other Date2013-01 (degree)
Extentvi, 58 p. : ill.
DescriptionThis thesis consists of two chapters.The first chapter is about the new version of NIM recently introduced by Gurvichtogether with a generalization of the minimal excludant function (mex). This gameNIM(a,b) is played with two piles of matches. Two players alternate turns. By onemove, each player can take either “almost the same” number of matches from each pile(the difference of the two numbers is strictly less thana) or any number of matches fromone pile and strictly less thanbfrom the other. This game further extends Fraenkel’sNIM = NIM(a,1), which, in its turn, is a generalization of the classic Wythoff NIM =NIM(1,1).Gurvich introduced a generalization mexbof the standard minimum excludant mex =mex1defining mexb(S⊂Z+) = min{n:∀s∈S s≤n⇒s+b≤n}. He also showedthat P-positions (the kernel) of NIM(a,b) are given by the following recursion:xn= mexb({xi,yi|0≤i < n}), yn=xn+an;n≥0,and conjectured that for alla,bthe limits`(a,b) =xn(a,b)/nexist and are irrationalalgebraic numbers. Here we prove it showing that`(a,b) =ar−1, wherer >1 is the Perron root of the polynomialP(z) =zb+1−z−1−a−1∑i=1zdib/ae,wheneveraandbare coprime; furthermore, it is known that`(ka,kb) =k`(a,b).In particular,`(a,1) =αa=12(2−a+√a2+ 4). In 1982, Fraenkel introducedthe game NIM(a) = NIM(a,1), obtained the above recursion and solved it explicitlygettingxn=bαanc, yn=xn+an=b(αa+a)nc. Here we provide a polynomial timealgorithm based on the Perron-Frobenius theory solving game NIM(a,b), although wehave no explicit formula for its kernel.The second chapter of the thesis is about the existence of Nash equilibria (NE) inpure stationary strategies inn-person positional games with no moves of chance, withperfect information, and with the mean or total effective cost function.We construct a NE-free three-person game with positive local costs, disproving theconjecture suggested by Boros and Gurvich in Math. Soc. Sci. 46 (2003) 207-241.Still, the following four problems remain open:Whether NE exist in alltwo-person games with total effective costs such that (I) alllocal costs are strictly positive or (II) without directed cycles of the cost zero?If NE exist in alln-person games with the terminal (transition-free) cost functions,provided all directed cycles form a unique outcomecand (III) assuming thatcis worsethan any terminal outcome or (IV) without this assumption?Forn= 3 cases (I) and (II) are answered in the negative, while forn= 2 cases(III) and (IV) are proven. We briefly survey other negative and positive results onNash-solvability in pure stationary strategies for the games under consideration.
NotePh.D.
NoteIncludes bibliographical references
NoteIncludes vita
Noteby Vladimir Oudalov
Genretheses, ETD doctoral
Languageeng
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.
Statistical Profile