Section 2: Analyzing Coalitional Games

Key Learning Points

• Discuss a series of refinements to the coalitional model.
• Discuss the main solution concepts, the Shapley value, the core, and the nucleolus.

Activities

1. Read Section 12.2 of the text;
2. Watch the following videos:
   1. The Shapley Value
   2. The Core
   3. Comparing the Core and the Shapley Value in an Example
3. Do the following exercises:
   1. Give the following characteristic form game with transferable utility for three agents: 1, 2, and 3 (i.e., N = {1, 2, 3}, |N | = 3). The table below shows the values of each coalition.

      S	v(S)
      (1)	2
      (2)	2
      (3)	4
      (12)	5
      (13)	7
      (23)	8
      (123)	9

      1. Is the game superadditive? Additive? Convex?
      2. Is payoff division x = (5, 5, 5) ∈ ℝ³ feasible? (Hints: here x₁ = 5, x₂ = 5, x₃ = 5, ∑_i∈N x_i = ∑³_i=1x_i = 15)
      3. Is payoff division x = (2, 4, 3) ∈ ℝ³ feasible? Efficient? A pre-imputation? Imputation?
      4. Are there any agents that are interchangeable?
      5. Are there any dummy players in the game?

   2. Consider the following example of characteristic function game: Charlie (C), Marcie (M), and Pattie (P) want to pool their savings to buy ice cream. Charlie has c dollars, Marcie has m dollars, and Pattie has p dollars. The ice cream packs come in three different sizes: (1) 500g, which costs $7, (2) 750g, which costs $9, and (3) 1000g, which costs $11. The children value ice cream and assign no utility to money. Thus, the value of each coalition is determined by how much ice cream it can buy. This situation corresponds to a characteristic game with the set of players N = {C, M, P}. For c = 3, m = 4, p = 5, its characteristic function, v, is given by v(Φ) = 0, v({C}) = v({M}) = v({P}) = 0, v({C, M}) = v({C, P}) = 500, v({M, P}) = 750, v({C, M, P}) = 1000. For c = 8, m = 8, p = 1, its characteristic function, v, is given by v(Φ) = 0, v({C}) = v({M}) = 500, v({P}) = 0, v({C, P}) = v({M, P}) = 750, v({C, M}) = 1250, v({C, M, P}) = 1250.

      Compute the Shapley values of all players in the two variants of the ice cream game. Do these games have non-empty cores?

   3. Consider a coalitional game (N = {1, 2, 3}):

      S	(1)	(2)	(3)	(1, 2)	(1, 3)	(2, 3)	(1, 2, 3)
      v(S)	2	6	12	10	15	21	24

      1. Is payoff vector (5, 6, 13) a core?
      2. Is payoff vector (2, 7, 15) a core?
      3. Is payoff vector (2, 4, 12) a core?
4. Discuss the following questions in the discussion forum:
   1. We can define that a payoff vector, x, for a coalition game (N, v) is feasible if there exists a set of coalitions, T = S₁, ..., S_k where ⋃_S∈T S = N such that ∑_S∈T v(S) ≥ ∑_i∈N x_i. The set of disjoint coalition, T, defined above, is often referred to as a coalition structure. What are the algorithms for finding the optimal coalition structure?