Game Theory and Strategy

GameTheoryandStrategyContentTwo-personsZero-SumGamesTwo-PersonsNon-Zero-SumGamesN-PersonsGamesIntroductionAtleast2playersStrategiesOutcomePayoffsTwo-personsZero-SumGamesPayoffsofeachoutcomeaddtozeroPureconflictbetween2playersTwo-personsZero-SumGamesColinABCDA7,-7-1,11,-10,0B5,-51,-16,-6-9,9C3,-32,-24,-43,-3RoseD-8,80,00,08,-8Two-personsZero-SumGamesColinABCDA7-110B516-9C3243RoseD-8008DominanceandDominancePrincipleDefinition:AstrategySdominatesastrategyTifeveryoutcomeinSisatleastasgoodasthecorrespondingoutcomeinT,andatleastoneoutcomeinSisstrictlybetterthanthecorrespondingoutcomeinT.DominancePrinciple:Arationalplayerwouldneverplayadominatedstrategy.SaddlePointsandSaddlePointsPrincipleDefinition:AnoutcomeinamatrixgameiscalledaSaddlePointiftheentryatthatoutcomeisbothlessthanorequaltoanyinitsrow,andgreaterthanorequaltoanyentryinitscolumn.SaddlePointPrinciple:Ifamatrixgamehasasaddlepoint,bothplayersshouldplayastrategywhichcontainsit.ValueDefinition:Foramatrixgame,ifthereisanumbersuchthatplayerAhasastrategywhichguaranteesthathewillwinatleastvandplayerBhasastrategywhichguaranteesplayerAwillwinnomorethanv,thenviscalledthevalueofthegame.Two-personsZero-SumGamesColinABCDA7-110B516-9C3243RoseD-8008SaddlePointsMinimaxColinABCDRowminimumA43252MaximinB-10201-10C75232MaximinRoseD08-4-5-5ColumnMaximum7825SaddlePoints0saddlepoint1saddlepointmorethan1saddlepointsMixedStrategyColinABA2-3RoseB03MixedStrategyColinplayswithprobabilityxforA,(1-x)forBRoseA:x(2)+(1-x)(-3)=-3+5xRoseB:x(0)+(1-x)(3)=3-3xif-3+5x=3-3x=x=0.75RoseA:0.75(2)+0.25(-3)=0.75RoseB:0.75(0)+0.25(3)=0.75MixedStrategyRoseplayswithprobabilityxforA,(1-x)forBColinA:x(2)+(1-x)(0)=2xColinB:x(-3)+(1-x)(3)=3-6xif2x=3-6x=x=0.375ColinA:0.375(2)+0.625(0)=0.75ColinB:0.375(-3)+0.625(3)=0.75MixedStrategy0.75asthevalueofthegame0.75A,0.25BasColin’soptimalstrategy0.375A.0.625BasRose’soptimalstrategyMixedStrategyColinABRowdifferenceRoseoddmentsRoseprobabilitiesA2-32-(-3)=533/8RoseB030–3=-355/8Columndifference2–0=2-3–3=-6Colinoddments62Colinprobabilities6/82/8MinimaxTheoremEverymxnmatrixgamehasasolution.Thereisauniquenumberv,calledthevalueofgame,andoptimalstrategyfortheplayerssuchthati)playerA’sexpectedpayoffisnolessthatv,nomatterwhatplayerBdoes,andii)playerB’sexpectedpayoffisnomorethatv,nomatterwhatplayerAdoesThesolutioncanalwaysbefoundinkxksubgameoftheoriginalgameMinimaxTheorem(example)ColinABCDEA11213910B1128145RoseC673415MinimaxTheorem(example)ThereisnodominanceintheaboveexampleFromarrowsinthegraph,ColinwillonlychooseA,BorC,butnotDorE.Sothegameisreducedintoa3x3subgameExample9-Police9-08-17-26-35-47-01/21/21/2116-111/21/21/215-2111/21/2½7-Guerrillas4-31111/20Example9-Police7-26-35-47-01/2116-11/21/215-21/21/2½7-Guerrillas4-311/20Example9-Police7-26-35-47-01/2117-Guerrillas4-311/20Example9-Police7-25-47-01/217-Guerrillas4-310MixedStrategy9-Police7-25-4RowdifferenceGuerrillasoddmentsGuerrillasprobabilities7-01/21-1/212/37-Guerrillas4-3101½1/3Columndifference1/21Policeoddments11/2Policeprobabilities2/31/3ColinABAUVBWXCYZRoseUtilityTheoryUtilityTheoryRose’sorderisu,w,x,z,y,vColin’sorderisv,y,z,x,w,uColinABA61B54C23RoseUtilityTheoryvwxui)020406080100ii)-101234iii)171921232527UtilityTheoryTransformationcanbedoneusingapositivelinearfunction,f(x)=ax+binthisexample,f(x)=0.5(x-17)--------ColinABA27,-517,0RoseB19,-123,-3ColinABA5,-50,0RoseB1,-13,-3Two-PersonsNon-Zero-SumGamesEquilibriumoutcomesinnon-zero-sumgames~saddlepointsinzero-sumgamesPrisoners’DilemmaColinConfessDon’tConfess10,100,20RoseDon’t20,01,1NashEquilibriumIfthereisasetofstrategieswiththepropertythatnoplayercanbenefitbychangingherstrategywhiletheotherplayerskeeptheirstrategiesunchanged,thenthatsetofstrategiesandthecorrespondingpayoffsconstitutetheNashEquilibriumDominantStrategyEquilibriumIfeveryplayerinthegamehasadominantstrategy,andeachplayerplaysthedominantstrategy,thenthatcombinationofstrategiesandthecorrespondingpayoffsaresaidtoconstitutethedominantstrategyequilibriumforthatgame.Pareto-optimalIfanoutcomecannotbeimprovedupon,ie.noonecanbemadebetteroffwithoutmakingsomebodyelseworseoff,thentheoutcomeisPareto-optimalParetoPrincipleTobeacceptableasasolutiontoagame,anoutcomeshouldbePareto-optimal.PrudentialStrategy,SecurityLevelandCounter-PrudentialStrategyInanon-zero-sumgame,playerA’soptimalstrategyinA’sgameiscalledA’sprudentialstrategy.ThevalueofA’sgameiscalledA’ssecuritylevelA’scounter-prudentialstrategyisA’soptimalresponsetohisopponent’sprudentialstrategy.ExampleColinABA2,41,0RoseB3,10,4ExampleconsideronlyRose’sstrategysaddlepointatABColinABA21RoseB30ExampleconsideronlyColin’sstrategyColinABA40RoseB14Columndifference4-1=30-4=-4Colinoddments43Colinprobabilities4/73/7ExampleRosestrategyColinstrategyRosepayoffColinpayoffprudentialprudential11/716/7prudentialCounter-prudential24Counter-prudentialPrudential12/716/7Counter-prudentialCounter-prudential31ExampleRoseprudentialAColinPrudential4/7A,3/7BRoseCounter-prudentialBColinCounter-prudentialAExampleBBAAEquilibriumBAABCo-oper