Exercise 7 Text

Page 1

GAME THEORY 2017-2018 5 cfu 7 Matching problem Exercise 89. Given the matching problem M ={a, b, c, d}, W ={A, B, C, D}, with preferences D ≻a C ≻a B ≻a A b ≻A a ≻A c ≻A d B ≻b A ≻b C ≻b D c ≻B a ≻B d ≻B b B ≻c D ≻c C ≻c A d ≻C a ≻C c ≻C b A ≻d D ≻d C ≻d B d ≻D c ≻D b ≻D a Find a stable set and a non stable set. Verify that M =W. Solution A stable set is given by {(a, C), (b, A), (c, B), (d, D)}. A non stable set is given by {(a, A), (b, B), (c, C), (d, D)}, since a≻C c and C≻a A. M =W ={(a, C), (b, A), (c, B), (d, D)}. Exercise 90. Consider the matching problem M ={a, b, c} and W ={A, B, C}, with the following system of preferences: A ≻a B ≻a C b ≻A c ≻A a B ≻b C ≻b A c ≻B a ≻B b C ≻c A ≻c B a ≻C b ≻C c. - Find the stable set M provided by the men’s courtship algorithm. - Find the stable set W provided by the women’s courtship algorithm. - Is there any other stable set? SolutionM ={(a, A), (b, B), (c, C)} is the stable solution obtained when we suppose that men go to visit women, W ={(a, C), (b, A), (c, B)} is the stable solution obtained when we suppose that women go to visit men. A third stable solution is J ={(a, B), (b, C), (c, A)}. 1 Exercise 91. Consider the following matching problem with W ={Catwoman, W onderwoman} and M = {Superman, Batman, F lash}. Suppose that Catwoman prefers Batman to Superman and Superman to Flash, while Wonderwoman prefers Superman to Flash and Flash to Batman. 1. If the women are visiting men, what is the stable set? 2. Find a preference profile for the men such that there is another stable set. 3. If all the men prefer to be paired than to be alone, is there a man that will be alone in all the stable sets? (independently from the men’s preferences) Solution 1. The stable set is (Batman, Catwoman), (Superman, Wonderwoman), Flash alone.…