Coalitional games

• Payoffs


  A way of measuring (in terms of outcomes) the combined effect of strategies. They correspond to "utilities", but cardinal utilities, not ordinal utilities
• In game theory, the appropriate utility concept is that of expected utility, which preserves the preferences of individuals towards outcomes resulting from actions, but only up to a positive linear (affine) transformation
• Levels of abstraction in game theoretical analysis

  • Coalitional form: the highest level of abstraction, where strategies are completely ignored, and one only considers coalitions of players
  • Normal form: the possibility of communication and binding agreements is dropped, and players' strategies are included
  • Extensive form: the most detailed description of an interactive situation, fully describing the sequential decision making and informational structure
• In both normal- and extensive form games, the actual description of the interactive situation is part of the analysis, and different equilibrium concepts reflect different strategic considerations
• Coalitional form representation


  Used in co-operative game theory
• Normal form


  Possibility of communication and binding agreements (commitments) is dropped, and players' strategies are also included (albeit possibly still at a general level)
• Extensive form


  The most detailed description of an interactive situation. It fully describes the sequential decision making in strategic interaction. Strategies are presented in detail as a sequence of possible moves, so that timing of actions as well as informational structure (who can observe what and when) also become crucial. Communication and binding commitments are again assumed away.
• The normal- and extensive form representations, which exclude the possibility of binding contracts and commitment, are mainly used in strategic (non-cooperative) game theory
• Coalitional game


  Described by the pair (N; v), where N = {1, 2, ..n} is the (finite) set of players and v is a function that assigns to every coalition S the value (worth) of that coalition, v(S)
• Super-additive coalitional game


  v(S ∪ T) ≥ v(S) + v(T) for all S, T such that S ∩ T = ∅
• Essential coalitional game


  v(N) > v(1) + v(2) + ... + v(n)
• Allocation in the grand coalition


  A payoff vector (x1, ..., xn) such that xi ≥ v(i) for all i ∈ N and Σi∈N xi = v(N)
• With only two players, the situation is trivial - if v(1,2) ≥ v(1) + v(2), the two players can never be worse off if they form a partnership
• A coalitional game (N,v) is essential only if v(S ∪ T) > v(S) + v(T) for at least two coalitions S and T
• Barycentric coordinate system


  A geometric representation of a 3-player coalitional game, where the vertices of an equilateral triangle represent the scenarios where one player gets everything, and points inside the triangle represent allocations where all three players get something
• For 3-player coalitional games with v(i) = 0 for all i ∈ N, the vertices of the equilateral triangle have coordinates (v(N), 0, 0), (0, v(N), 0) and (0, 0, v(N))
• For 3-player coalitional games with v(i) ≠ 0 for at least one i ∈ N, the equilateral triangle is normalized to a unit simplex, where each point represents the actual shares (proportions) of the overall worth
• Coalitional game


  A game where players can form coalitions and the worth of each coalition is determined by the characteristic function v(S)
• In a 3-player coalitional game, the characteristic function v(i) must be 0 for at least one player i
• Representing 3-player coalitional games with v(i) ≠ 0 for at least one player

  1. Normalize v(i) to 0 for all players

  2. Normalize v(N) to 1

  3. Represent the game on a unit simplex (equilateral triangle)
• Unit simplex


  An equilateral triangle where each point represents an allocation, and the sum of the coordinates equals 1
• 1. player coalitional games


  • v(1) = 1, v(2) = 2, v(3) = 3, v(1,2) = 4, v(1,3) = 4, v(2,3) = 6, v(1,2,3) = 10
  • v(1) = v(2) = v(3) = 0, v(1,2) = 1, v(1,3) = 2, v(2,3) = 1, v(1,2,3) = 3
  • v(1) = v(2) = v(3) = 0, v(1,2) = v(2,3) = 1, v(1,3) = 1, v(1,2,3) = 3
  • v(1) = v(2) = v(3) = 0, v(1,2) = v(1,3) = v(2,3) = 2, v(1,2,3) = 3
  • v(1) = v(2) = v(3) = 0, v(1,2) = 3/4, v(1,3) = 3/4, v(2,3) = 1/4, v(1,2,3) = 1
  • v(1) = 1, v(2) = 2, v(3) = 3, v(1,2) = 4, v(1,3) = 4, v(2,3) = 6, v(1,2,3) = 10 (normalized to v(i) = 0, v(1,2) = 1/4, v(1,3) = 0, v(2,3) = 1/4, v(1,2,3) = 1)
• Core of a coalitional game


  The set of allocations where no coalition has an incentive to break away from the grand coalition
• Finding the core of a 3-player coalitional game

  1. Draw the unit simplex

  2. Divide the sides based on the characteristic function values

  3. Draw line segments parallel to the sides representing the minimum payout required for 2-player coalitions to join

  4. The core is the intersection of the half-spaces created by these line segments
• The core can be a single point, line segment, triangle, trapezoid, pentagon, or hexagon (or empty)
• The grand coalition will not form if the core is empty, but an empty core is only a necessary condition, not sufficient
• Even with a non-empty core, the grand coalition may still fail to form due to other reasons