Orenations (@) Onlytwo players participate in the game: (0) Each player has a finite number of strategies to use, (©) Each specific strategy results in & pay-off. (a) Total pay-off to the two players at the end ofeach play is zero. 19.4 THE MAXIMIN-MINIMAX PRINCIPLE bytwo players. Consider tv players 4, This principle is used for the selection ‘of optimal strategies| oe Aisa player who wishes to maximize his gains. while player B wishes tominimize his esses, sin ban for player 4. the value called matimin yanee 4 ue ar like to maximize his minimum gain, we corresponding strategy 1s called the matimin strategy: ‘On the other hand. since player B wishes tomiimize his losses, a value called the minimax vay {the minimum of the maximum losses is found. The corresponding strategy is called the7rinimaras, When these to are equal (maximin value= minimax value), the corresponding strategies are called serategies and the game is said to have a saddle point. The value ofthe game is given by the saddle, ‘The selecuon of maximin and minimax strategies by 4 and B is based upon the so-called am minimax principle, which guarantees the best of the worst results. J Saddle point A saddle point is a position in the pay-off matrix where, the maximum of row mi aencide with the minimum of column maxima. The pay-off atthe saddle point is called the value gane : ‘We shall denote the maximin value by ¥ , the minimax value ofthe game by ¥ and the value ofthe, by. Notes: (i) A game is said to be fair if, ‘maximin value= minimax value =0, i. (i A game is said to be strictly determinable if, maximin value=minimax value#0. 1 =1= 7. Example 19.1 Solve the game whose pay-offfatrix is given by, Player 3B Bh B i ATT 34 Played 4! -4 -3 ALT Seed ‘Solution Player B B, By By Rowminima meopayi sy} wes [0 4 -3]-4 ALi 5-1} -1 Coumnmaxima | 5on et” or Maxims i, Mini(marmg, M2, 4.- Het Maxininvate = Min 5 he 1 * Minimax value 7 ie dle point exists Thevahcethy yore ., om of the saddle point and gpg, 5 the saddle pont, which posto jon PA), 8) Ali 6 Player A,| -1 Al -2 4 4 puion Sener the value ofl. the pay-of matrix is given by, : Player B 8 By By Rowminima 4 Player Ay} -1 9, -7 |-7 Al-2 4 a ]2 Cohmnmaxims ==} § 2 “The gameis strictly determinable if, 2 Example 19.3 Determine which ofthe following two-person zero-sum games are strictly determumable and fair. Given the optimum strategy for each player in the case of strictly determinable games. 0 Player B (i) Player B a B a B A[-5 2]. aie Player 4 ae “I Player 4 a -| Maxi(minimum) = ¥ = Max(-5,~7)=-5 Mini (maximum) = 7 = Min -$,2)=—$ Solution @ Player B B, By Rowminima Af-5 2]-5 Pl 1 wea 4S IE 1 4] Column maxima -5 2 Since y = F =—5 #0, the gameisstrctly determinable. There exists a saddle point = ~S. Hence, the Value of the game is 5, The optimal strategy isthe position of the saddle point given by, (4, B,).ast Orunations Ry ry Player 5,8; Row minimum Pye 4ft i]t 43 4 a Colm manna 4. Maxi (minivan) = y =Max(1,-3)=1. ‘Mini (maximum) = ¥ = Min (4, 1 Since } = ¥ =11#(0,thegameisstrictly determinable. Value of the gameis 1. The is 4,3). ‘optimal strategy Example 19.4 Solve the game whose pay-off matrix is given below. 200 5 3 Spa HAD 4302 6 5 3-4 2 6 Solution B, B, By By Bs Rowminima Af-2 0 0 5 3)-2 4/3 2 12 2/1 Ral oa 23 oe 6 [=a Al S 34 2 6 ]-6 (Column maxima $3 15.6 Man (minimum) = ¥ = Max (-2,1,-4,-6)=1. ‘Mami(maxamum) = 7 = Min (5,3, 1,5, 6)=1. Since, ¥ = ¥ = 1, there exists a saddle point. Value of the game is 1. The position of'the saddle point is the optimal strategy and is given by, [4,, By]. EXERCISES 1. For & peme with the following pay-off matrix, Player A 12-2 PuyrB |e 4 6 ‘determine the best strategies as well es the value of the game fc A end B. Is this game ()) fair, (i) 4; game for players {Ans. Value of game is = 2, Game is not fair, but strictly determinable] 2 Deterrine the optimal minmas strategies for each player In the folowing game, BBB, B A[S 207 Al 564 8 AL 402-9 TAns. g = 4, (Az, B,) Is tho optimum strategy)0" ps WITHOUT oat SADDLE POINTS (MIXED STRATEGIES? 95 out saddle point can be ! rg within Solved by various solution methods A 0 ee x 2 Games without Srddie point 1s two-person 704 ya 2 r Mm game without any saddle poet hmv Se nyo maser player cans fe & B, ae a a az: } me optimum mixed strategies, apt ps2 =P"! Fi wheres te __9+q,51> elm aireleeai cae % 4 9 = 42 (a4) + a2) ~ (42 + 221) ‘The value of the game (j) = 5 Solve the following pay-off matrix. Also determine the optimal stravegres and vale of Example 19. ‘the game- B ee 34 B 51), Lec this be, 34 Solution ae 4{ a, a2 ] “The optimum mixed straseBies, Alay, an (& 3) s-(4 8) iss ( a “la La : ayy - Oy 4-3 1 i tc} at z ss PL” Tay, Pay) (0g 220 *a-aed poten 2 Pl3H Oremmnons 4 SR Sy 22-4, ae = sete; 1” Gy Fax) ~(Oi2+@y O¥4) 09 75 3_2 a7 n2t- 525 x= Usa) TD value of game. . (5+4)-+3) 5 The optimum mixed strategies. Example 19.6 Solve the following game and determine its value. B [<<] 4 44 Solution Wis clear that the pay-ofT matrix does not possess any saddle point. The players will use mixe strategies. The optimum mixed strategy for the players are, 4 *) Se sp, +py=1 ‘ . my B, ) Sp= nth?! i Fe Gide =a 4 Bt PL Gay + ayy) (aj 4a) 4+4-(-4-4) 16 2 a. pytl-py > 71-575 eee ce N” Gran) (q, ay) 444-(-4-4) 162 ee =1-9,=l--=2-. a7 1 7-2 memmiens( f)-($ 9 The value of the game is, y= —229u~ 12421 (agg + 4)~ (a2 + a1) (44)=[-44(-a)A ie oe 19.7, 93 ea fa os A ga wins nothing we ee hha cere Spree aa Seg to te aa aslo Pun oftaewhen tee rend ow rae player and the value of the 104 ye pay-off matrix forthe On aye A ispivenby patthis be pee optimum mined StateBis, —a- 4 (ayo 1.3 gr h-qr ary ‘Value of the game = 0-4-5) +0- \ 8436 Orererny Me The optimum mixed strategy is given by, _ hind the value of game is -1/8. EXERCISES 1 For a game wan the folowing payff mats, determine the Optimal stretagy and the value o hy o OB B45 Sane. 6-3 43 3) By One mw 8 i 4) 2. Two players, A and B match coins. Ifthe coins match, then A wins two units of value. Wf CONS do ret mg then B wins two units of value. Determine the optimum strategies for the players and the value of the game. [ane SaSp 3. Consider a ‘modified form’ of matching-based coins game problem. The matching player is pad © 600 1 the coins tum heads and € 1 if both the coins tum tails. The non-matching player is paid & 300 when te ‘coins do not match. Given the choice of being the matching or non-matching player, which one was choose and what would be your strategy? [Anns Snaen*( 75} Sterna “| 2 ¥) Value of game = ~+,Non - matching pin Hint: Pay-off matrix for matching player is, Non-matching (B) HT uf 8 -3 Matching player (A) 7] _y 19.5.2. Graphical Method for 2 n or mx 2 Games Consider the following 2 games. Strategy for player B By B, Strategy forplayer A |» Dt Br Fe . Pier Aan a2 On Ay Lay) 422 + Faq Let the mixed strategy for player A be given by, A S,> ‘) such that, p, +p," 1,p), p20 PL Pz :eo eat of the PUFE HHERCS ite 1g p oa 0 wo prspuremon® been pay-off for player A would be as follows- B, é Pected pay-off Elp) By Berea 20)™ 012, + ay>Py B aie i n(P)~ 249, + dayPy ike to m8 wos haces cui See! is a minimum for of player isto eiepech (Efoh=1.2.- the straight lines, and pin sucha way that, 7a large as possible. This may PF Bie) = 0,0," 0,"(0, 4) Py * i225" jective tions of P; ‘avon the lower boundary/ofthes ns wil gi i Il give the maxim in the lower boundary (lower envelope) as well asthe optimum: neat ; ehighest Oa um valueamong the minimum peed pay-ofls value of probability P; of player B corresponding tothe lines th ee 2 the can a theps in reducing thesize ofthe game 2) at pss tah he main PN sntreat m *2 games in thesame way and get the mii we cal pper poundary (upper envelope). oP Now the two strategics ecerrit max point, which will bethe lowest 4g Solve the following 23 game graphically. Player B 1,3 Player A vet [hs a Solution Since the problem does not possess any saddle point, let player 4 play by the mixed strategy (* 4) sitio t-P A Pa sainst player B. are etd pay-off gains B's puremove Sve B's pure move arsexpected pay-off Elp)) B, gyp)prvs-0)— 78 By gyppr snes -Pd 57 By ego iee PnP