21 07 2022 E TS

Page 1

GAME THEORY - July 21, 2022 Last name: First name: SOLVE THE EXERCISES AND ANSWER THE QUESTIONS ON THESE SHEETS Exercise 1 5 points Given the zero-sum game described by the following matrix: A =   3 4 4 2 4 5 5 4 1   find a pair of optimal strategies for the players and the value of the game. Answer of exercise 1 First of all, notice that 3 = vI ̸= vII = 4, therefore there are no optimal pure strategies. Then we observe that the second column is strictly dominated by a convex combination of the first one and the third one. Thus the game can be reduced to A =   3 4 2 5 5 1   If Pl2 plays (q, 0, 1 − q), then the utilities of the three rows are respectively (4 − q, 5 − 3q, 4q + 1). Then Pl2 plays q = 3/5 and Pl1 plays (p, 0, 1 − p). By the indifference principle, p = 4/5 and then the value is 17/5. 1 Exercise 2 5 points Let W ={Alessia, Barbara } and M ={Charlie, David, Ethan }. Suppose that Alessia prefers David to Charlie and Charlie to Ethan, while Barbara prefers David to Ethan and Ethan to Charlie. Men better prefer to be paired than to be alone. 1. If the ”women visiting men” algorithm is followed, what is the stable matching? Do we need to know the preferences of the men? 2. Choose a preference profile for the men such that there exists a unique stable sets. 3. Do the preferences of Charlie and Ethan matter? Why? Answer of exercise 2 1. Both women go to David at the first step. We need to know David’s preferences to proceed. 2. All men’s preference profiles lead to a unique stable matching, see below. 3. If David prefers Alessia, then he is going to be paired to her, since when men choose, he goes to her, and is accepted. When women choose, they both go to David at the first step, and then he chooses Alessia. Then Barbara can choose her second preference,…