Lecture
122
Game Theory :introduction and
Solving Two Person and Zero - Sum Game
22.1 IntroductiontoGameTheory
Gametheoryisatypeofdecisiontheoryinwhichone’schoiceofactionisdeterminedaftertakingintoaccountallpossiblealternativesavailabletoanopponentplayingthesamegame,ratherthanjustbythepossibilitiesofseveraloutcomeresults.Gametheorydoesnotinsistonhowagameshouldbeplayedbuttellstheprocedureandprinciplesbywhichactionshouldbeselected.Thus itisadecisiontheoryusefulincompetitivesituations.
Gameisdefined as anactivitybetweentwoormorepersonsaccordingtoasetofrulesattheendofwhicheachpersonreceivessomebenefitorsuffersloss.Thesetofrulesdefinesthegame.Goingthroughthesetofrulesoncebytheparticipantsdefinesa play.
22.2 PropertiesofaGame
1.Therearefinite numbersofcompetitorscalled‘players’
2.Eachplayerhasa finitenumberofpossiblecoursesofactioncalled‘strategies’
3.Allthestrategiesandtheireffectsareknowntotheplayersbutplayerdoesnotknowwhichstrategyistobechosen.
4.Agameisplayedwheneachplayerchoosesoneofhisstrategies.Thestrategiesareassumedtobemadesimultaneouslywithanoutcomesuchthatnoplayerknowshisopponentsstrategyuntilhedecideshisownstrategy.
5.Thegameisacombinationofthestrategiesandincertainunitswhichdeterminesthegainorloss.
6.Thefiguresshownastheoutcomesofstrategiesinamatrixformarecalled‘pay-offmatrix’.
7.Theplayerplayingthegamealwaystriestochoosethebestcourseofactionwhichresults inoptimalpayoffcalled‘optimalstrategy’.
8.Theexpectedpayoffwhenalltheplayersofthegamefollowtheiroptimalstrategiesisknownas‘valueofthegame’.Themainobjectiveofaproblemofagameistofindthevalueofthegame.
9.Thegameis saidtobe‘fair’gameifthevalueofthegameis zerootherwiseitsknownas‘unfair’.
22.3 CharacteristicsofGameTehory
1.Competitivegame
Acompetitivesituation iscalledacompetitivegameif ithasthe followingfourproperties
1.Therearefinitenumberofcompetitorssuchthatn≥2.Incasen=2,itiscalledatwo-person gameandincasen2, itisreferredasn-person game.
2.Eachplayerhasalistoffinitenumberofpossibleactivities.
3.Aplayissaidtooccurwheneachplayerchoosesoneofhisactivities.Thechoicesareassumedtobemadesimultaneouslyi.e.noplayerknowsthechoiceof theotheruntilhehasdecidedonhisown.
1
4.Everycombination ofactivitiesdeterminesanoutcomewhich resultsinagain ofpaymentstoeachplayer,providedeachplayerisplayinguncompromisinglytogetasmuchaspossible.Negativegainimpliesthe lossofsameamount.
2.Strategy
Thestrategyofaplayeristhepredeterminedrulebywhichplayerdecideshiscourseofactionfromhisown listduringthegame. Thetwotypesofstrategyare
1.Purestrategy
2.Mixedstrategy
PureStrategy
Ifaplayerknowsexactlywhattheotherplayerisgoingtodo,adeterministicsituationisobtainedandobjectivefunctionistomaximizethegain.Therefore,thepurestrategyisadecisionrulealwaystoselectaparticular courseofaction.
MixedStrategy
Ifaplayerisguessingas towhichactivityistobeselectedbytheother onany particularoccasion,aprobabilisticsituationisobtainedandobjectivefunctionistomaximizetheexpectedgain.Thusthemixedstrategyisaselectionamongpurestrategieswithfixedprobabilities.
3.Numberofpersons
Agameiscalled‘n’persongameifthenumberofpersonsplayingis‘n’.Thepersonmeansanindividualoragroupaimingataparticularobjective.
Two-person,zero-sumgame
Agamewithonlytwoplayers(playerAandplayerB)iscalleda‘two-person,zero-sumgame’,ifthelossesofoneplayerareequivalenttothegainsoftheothersothatthesumoftheirnetgainsiszero.
Two-person,zero-sumgamesarealsocalledrectangulargamesastheseareusuallyrepresentedbyapayoffmatrixinarectangularform.
4.Numberofactivities
Theactivities may befiniteorinfinite.
5.Payoff
Thequantitativemeasureofsatisfactionapersongetsattheendofeachplay iscalledapayoff
6.Payoffmatrix
SupposetheplayerAhas‘m’activitiesandtheplayerBhas‘n’activities.Thenapayoffmatrixcanbeformedbyadoptingthe followingrules
- Rowdesignations foreachmatrixaretheactivities availableto player A
- Columndesignations foreachmatrixaretheactivitiesavailabletoplayerB
- CellentryVij isthepaymenttoplayerAinA’spayoffmatrixwhenAchoosestheactivityiandBchoosestheactivityj.
- Withazero-sum,two-persongame,thecellentryintheplayerB’spayoffmatrixwillbenegativeofthecorrespondingcellentryVijintheplayerA’spayoff matrixsothatsumofpayoffmatrices for playerAandplayer Bisultimatelyzero.
7.Valueofthegame
Valueofthegameis themaximum guaranteedgameto playerA(maximizingplayer)ifboththeplayersusestheirbeststrategies. It isgenerallydenotedby‘V’anditisunique.
22.4 ClassificationofGames
Allgamesareclassifiedinto
- Purestrategygames
- Mixedstrategygames
Themethodforsolvingthesetwotypesvaries.Bysolvingagame,weneedtofindbeststrategiesfor boththeplayersandalsotofind thevalueofthegame.
Purestrategygamescanbesolvedbysaddlepointmethod.
Thedifferentmethodsfor solvinga mixedstrategygameare
- Analyticalmethod
- Graphicalmethod
- Dominancerule
- Simplexmethod
22.5 SolvingTwo-PersonandZero-SumGame
Two-personzero-sumgamesmaybedeterministicorprobabilistic.Thedeterministic games willhavesaddlepointsandpurestrategiesexistinsuchgames.Incontrast,theprobabilisticgameswillhavenosaddlepointsandmixedstrategiesaretakenwiththehelpofprobabilities.
Definitionofsaddlepoint
Asaddlepointofamatrixisthepositionofsuchanelementinthepayoffmatrix,whichisminimumin itsrowandthemaximum in itscolumn.
Proceduretofindthesaddlepoint
- Selecttheminimumelementofeachrowofthepayoffmatrixandmarkthemwithcircles.
- Selectthemaximumelementofeachcolumnofthepayoffmatrixandmarkthemwithsquares.
- Iftheirappearsanelementinthepayoffmatrixwithacircleandasquaretogetherthenthatpositioniscalledsaddlepointand theelementisthevalueofthegame.
Solutionofgameswithsaddlepoint
Toobtainasolutionofagamewithasaddlepoint,itisfeasible tofindout
- Beststrategyfor playerA
- Beststrategyfor playerB
- Thevalueofthegame
ThebeststrategiesforplayerAandBwillbethosewhichcorrespondtotherowandcolumnrespectivelythroughthesaddlepoint.
Examples
Solvethepayoffmatrix
Example-1
PlayerA
IIIIIIIV
PlayerB
IIIIIIIVV
Solution
StrategyofplayerA–IIStrategyofplayerB- IIIValueofthe game=1
Example-2
B1B2B3B4
A1A2
A3
Solution
StrategyofplayerA–A2StrategyofplayerB– B3Valueofthe game=4