Management Engineering - Game Theory

Full exam

GAME THEORY June 11, 2021Surname: Name: Matricola: Exercise 1 Given the following bimatrix game, depending on the parametersa; b2R, 0 @(12 ;6) (4;4) (3;5) (3;6) (8;5) (2;7) (a;3) (6;7) (3; b)1 A; 1. nd the pure Nash equilibria for everya; b; 2. nd the best reaction of the rst player to(13 ;13 ;13 ) ; 3. nda; bsuch that the game is a potential game (if any); 4. nda; bsuch that there is a Nash equilibrium with second player playing(13 ;13 ;13 ) ; 5.show that for everya; bthere is a Nash equilibrium with the rst player playing a pure strategy and the second one a mixed strategy where exactly two pure strategies are played with strictly positive probability. Answer of exercise 1 1.The pure Nash equilibria outcomes are(12;6)for everya; bsuch thata12and(3; b)ifb7; 2.The expected utilities form the three rows (multiplied by 3) are respectively19;13;9 +a. Thus the best reaction of the rst player to(13 ;13 ;13 ) is(1;0;0)ifa 10, and(p;0;1p),0p1if a= 10. 3.A candidate potential (up to a constant) should look like0 @6 4 5 3 81 A: However, looking at the second player, with second row xed for the rst one, we see that656 =38 thus for noa; bthe game is a potential game; 4.For no pure strategy of the rst player the best reaction of the second one is(13 ;13 ;13 ) . Thus, if such a strategy exists, it must bea= 10and such a strategy should be of the form(p;0;1p). If player one plays(p;0;1p), in order that the second mixes among the three columns, all of them must be optimal, thus providing the same expected value. Thus6p+ 33p= 4p+ 77p= 5p+bbp providingp=23 ; b = 5; 5.the only possible case is whenb= 7and rst player playing the last row, otherwise the best reaction of player II is a pure strategy. Ifb= 7and Player I plays the last row, Player II plays(0; q;1q). Thus we need to see if there existsqsuch that the best reaction of player I to(0; q;1q)is the last row. Thus it must be: 8q+ 22q6q+ 33q providing0q13 . 1 Exercise 2 Consider the following TU game with three players, with parametera2R: v(1) =v(2) =a; v(3) = 0; v(1;2) = 5; v(1;3) = 2; v(2;3) = 2; v(N) = 6 1. nd all values ofasuch that the game is superadditive; 2. nd the core fora >2; 3. nd the Shapley value for all values ofaand say when the Shapley value is an imputation. Answer of exercise 2 1.The superadditivity conditions to impose arev(1) +v(2)v(1;2)v(1) +v(3)2v(1) +v(2;3)v(N) providinga2; 2.First of all, ifa >3the core is empty, since in that case it is not possible to satisfy players 1 and 2 at the same time (their joint request is greater than v(N)). Then, suppose(x 1; x 2; x 3) 2C(v). The conditionx 1+ x 3 2 impliesx 2 4. However6a4fora >2, thus for an imputation it is alwaysx 2 4, and analogously for x1. Moreover, it must be x 3 1. This condition is automatically veri ed if62a1, i.e.a52 . Thus, if a52 the core does coincide with the imputation set, which is co f(6a; a;0);(a;6a;0);(a; a;62a)g. In casea52 we need to impose the further condition x 3 1, so that C(v) =f(6a; a;0);(5a; a;1);(a;6a;0);(a;5a;1);(a; a;62a)g: 3.Clearly players 1 and 2 are symmetric, thus only the value of one player must be calculated:3( v) =16 ( v(1;3)v(1) +v(2;3)v(2)) +13 ( v(N)v(1;2)) =6 2a6 thus(v) = (15 + a6 ; 15 + a6 ; 6 2a6 ) which is an imputation f and only ifa3. 2 Exercise 3 A guard is trying to catch a burglar in a museum with 5 rooms connected as in the map below. The guard will catch the burglar if they happen to be either in the same room or in contiguous room. In that case the guard gets a payo of 1 and the burglar -1. Otherwise the guard gets -1 and the burglar 1.12 345 1.Write the matrix form of the associated zero sum game; 2.Say which strategies can be eliminated by weak domination; 3.Find the value of the game and the optimal strategies of the players.Answer of exercise 3 1.The game is the following:12345 1111-1-1 211-111 31-11-1-1 4-11-11-1 5-11-1-11 2.From the point of view of the guard, 2 weakly dominates 4 and 5, while 1 dominates 3. Thus the game can be reduced to12345 1111-1-1 211-111 Now 1 and 2 are weakly dominated for the burglar, thus the game reduces to: 345 11-1-1 2-111 3.Observe that the burglar is indierent to enter either in room 4 or 5. Thus the optimal strategies are (12 ;12 ; 0;0;0)for the guard and(0;0;12 ;12 p; p)for the burglar, with0p12 . 3 Exercise 4 1.There arexcards on the table and each of the two players can take either 2 or 3 or 4 cards. Who leaves the other without available moves wins. Who wins ifx= 18andx= 295? 2.Given the following zero sum game in extensive form, nd all values ofasuch that the backward induction strategy pro le is(bh; df).g hc 1 =21 =2da e 1/32/3fbI IIII INN -12-231 a -1 Answer of exercise 4 1.Easy to check that the period sequence of P and N positions is PPNNNN. Thus positionsk+ 6nare P positions ifk= 0;1otherwise they are N positions. Both positions are P positions. 2.Between g and h I chooses h, between c and d II chooses d. If I takes B II must choose whether to pay 1 ora23 . Thus the pro le (bh,df ) is the BI strategy pro le if and only if12 a 23  1if and only if72  a5. 4