Exercise 6 solution

Page 1

GAME THEORY 2017-2018 5 cfu 6 Cooperative games Exercise 73. Given the game (N,v ) with N ={1, 2, 3} and v({i}) = 0 , v({1, 2}) = v({1, 3}) = 1 , v({2, 3}) = 0, v(N) = 2, represent the core of the game. Solution C(v) = convex hull of the set of vectors {(1, 0, 1), (0, 1, 1), (2, 0, 0), (1, 1, 0)} and it is represented in Figure 1. (0,2,0) (0,0,2) (1,1,0) (0,1,1) (2,0,0) (1,0,1) x3 = 1 x2 = 1 Figure 1: Exercise 73 Exercise 74. Given the TU game: N ={1, 2, 3},v({i}) = 0,v({1, 2}) =a,v({1, 3}) =v({2, 3}) = 1, v(N) = 2, find a such that the core of the game is a singleton. In such a case find the nucleolus. Solution The core is the singleton (1, 1, 0) fora = 2. In such a case, the nucleolus coincides with the core. Exercise 75. Consider the graph in Figure 2a where O is a power plant that provides electricity to the houses in N ={1, 2, 3}. The numbers on the edges are the costs of connecting two different houses or one house with O. How can we represent the cost of each coalition of houses? Write the characteristic function and find the core of the cost game. Solution The situation is depicted in Figure 2a. A way to define a cooperative game that represents such situation is the minimum cost spanning tree game (Bird 1976). In the mcst game the value of 1 each coalition is the minimum cost of connecting all the elements in the coalition to O. In this case the game v is defined by v({1}) = 24 , v({2}) = 24 , v({3}) = 26 , v({1, 2}) = 42 , v({1, 3}) = 34 , v({2, 3}) = 44 , v({1, 2, 3}) = 52. The core of the game is co{(24, 18, 10), (18, 24, 10), (8, 24, 20), (8, 18, 26)} and it is drawn in Figure 2b. O 1 2 3 24 24 26 18 10 20 (a) The mcst game (2,24,26) (24,24,4) (8,18,26) (8,24,20) (18,24,10) (24,2,26) (24,18,10) x2= 18 x3= 10 x1= 8 (b) The core of the game Figure 2: Exercise 75…