Game Theory 1

GAMETHEORYThomasS.FergusonPartI.ImpartialCombinatorialGames1.Take-AwayGames.1.1ASimpleTake-AwayGame.1.2WhatisaCombinatorialGame?1.3P-positions,N-positions.1.4SubtractionGames.1.5Exercises.2.TheGameofNim.2.1PreliminaryAnalysis.2.2Nim-Sum.2.3NimWithaLargerNumberofPiles.2.4ProofofBouton’sTheorem.2.5Mis`ereNim.2.6Exercises.3.GraphGames.3.1GamesPlayedonDirectedGraphs.3.2TheSprague-GrundyFunction.3.3Examples.3.4TheSprague-GrundyFunctiononMoreGeneralGraphs.3.5Exercises.4.SumsofCombinatorialGames.4.1TheSumofnGraphGames.4.2TheSpragueGrundyTheorem.4.3Applications.I–14.4Take-and-BreakGames.4.5Exercises.5.CoinTurningGames.5.1Examples.5.2Two-dimensionalCoinTurningGames.5.3NimMultiplication.5.4TartanGames.5.5Exercises.6.GreenHackenbush.6.1BambooStalks.6.2GreenHackenbushonTrees.6.3GreenHackenbushonGeneralRootedGraphs.6.4Exercises.References.I–2PartI.ImpartialCombinatorialGames1.Take-AwayGames.Combinatorialgamesaretwo-persongameswithperfectinformationandnochancemoves,andwithawin-or-loseoutcome.Suchagameisdeterminedbyasetofpositions,includinganinitialposition,andtheplayerwhoseturnitistomove.Playmovesfromonepositiontoanother,withtheplayersusuallyalternatingmoves,untilaterminalpositionisreached.Aterminalpositionisonefromwhichnomovesarepossible.Thenoneoftheplayersisdeclaredthewinnerandtheothertheloser.Therearetwomainreferencesforthematerialoncombinatorialgames.Oneistheresearchbook,OnNumbersandGamesbyJ.H.Conway,AcademicPress,1976.Thisbookintroducedmanyofthebasicideasofthesubjectandledtoarapidgrowthoftheareathatcontinuestoday.Theotherreference,moreappropriateforthisclass,isthetwo-volumebook,WinningWaysforyourmathematicalplaysbyBerlekamp,ConwayandGuy,AcademicPress,1982,inpaperback.Therearemanyinterestinggamesdescribedinthisbookandmuchofitisaccessibletotheundergraduatemathematicsstudent.Thistheorymaybedividedintotwoparts,impartialgamesinwhichthesetofmovesavailablefromanygivenpositionisthesameforbothplayers,andpartizangamesinwhicheachplayerhasadifferentsetofpossiblemovesfromagivenposition.Gameslikechessorcheckersinwhichoneplayermovesthewhitepiecesandtheothermovestheblackpiecesarepartizan.InPartI,wetreatonlythetheoryofimpartialgames.AnelementaryintroductiontoimpartialcombinatorialgamesisgiveninthebookFairGamebyRichardK.Guy,publishedintheCOMAPMathematicalExplorationSeries,1989.Westartwithasimpleexample.1.1ASimpleTake-AwayGame.Herearetherulesofaverysimpleimpartialcombinatorialgameofremovingchipsfromapileofchips.(1)Therearetwoplayers.WelabelthemIandII.(2)Thereisapileof21chipsinthecenterofatable.(3)Amoveconsistsofremovingone,two,orthreechipsfromthepile.Atleastonechipmustberemoved,butnomorethanthreemayberemoved.(4)PlayersalternatemoveswithPlayerIstarting.(5)Theplayerthatremovesthelastchipwins.(Thelastplayertomovewins.Ifyoucan’tmove,youlose.)Howcanweanalyzethisgame?Canoneoftheplayersforceawininthisgame?Whichplayerwouldyouratherbe,theplayerwhostartsortheplayerwhogoessecond?Whatisagoodstrategy?Weanalyzethisgamefromtheendbacktothebeginning.Thismethodissometimescalledbackwardinduction.I–3Iftherearejustone,two,orthreechipsleft,theplayerwhomovesnextwinssimplybytakingallthechips.Supposetherearefourchipsleft.Thentheplayerwhomovesnextmustleaveeitherone,twoorthreechipsinthepileandhisopponentwillbeabletowin.Sofourchipsleftisalossforthenextplayertomoveandawinforthepreviousplayer,i.e.theonewhojustmoved.With5,6,or7chipsleft,theplayerwhomovesnextcanwinbymovingtothepositionwithfourchipsleft.With8chipsleft,thenextplayertomovemustleave5,6,or7chips,andsothepreviousplayercanwin.Weseethatpositionswith0,4,8,12,16,...chipsaretargetpositions;wewouldliketomoveintothem.Wemaynowanalyzethegamewith21chips.Since21isnotdivisibleby4,thefirstplayertomovecanwin.Theuniqueoptimalmoveistotakeonechipandleave20chipswhichisatargetposition.1.2WhatisaCombinatorialGame?Wenowdefinethenotionofacombinatorialgamemoreprecisely.Itisagamethatsatisfiesthefollowingconditions.(1)Therearetwoplayers.(2)Thereisaset,usuallyfinite,ofpossiblepositionsofthegame.(3)Therulesofthegamespecifyforbothplayersandeachpositionwhichmovestootherpositionsarelegalmoves.Iftherulesmakenodistinctionbetweentheplayers,thatisifbothplayershavethesameoptionsofmovingfromeachposition,thegameiscalledimpartial;otherwise,thegameiscalledpartizan.(4)Theplayersalternatemoving.(5)Thegameendswhenapositionisreachedfromwhichnomovesarepossiblefortheplayerwhoseturnitistomove.Underthenormalplayrule,thelastplayertomovewins.Underthemis`ereplayrulethelastplayertomoveloses.Ifthegameneverends,itisdeclaredadraw.However,weshallnearlyalwaysaddthefollowingcondition,calledtheEndingCondition.Thiseliminatesthepossibilityofadraw.(6)Thegameendsinafinitenumberofmovesnomatterhowitisplayed.Itisimportanttonotewhatisomittedinthisdefinition.Norandommovessuchastherollingofdiceorthedealingofcardsareallowed.Thisrulesoutgameslikebackgammonandpoker.Acombinatorialgameisagameofperfectinformation:simultaneousmovesandhiddenmovesarenotallowed.Thisrulesoutbattleshipandscissors-paper-rock.Nodrawsinafinitenumberofmovesarepossible.Thisrulesouttic-tac-toe.Inthesenotes,werestr