9.1 Cooperative games and characteristic functions

Cooperative games focus on players working together to maximize collective payoffs. They form coalitions, sharing strategies and rewards. The characteristic function assigns values to coalitions, showing what they can achieve independently.

Transferable and non-transferable utility games differ in how payoffs are divided. Imputations distribute payoffs fairly. Superadditivity and convexity are key properties that influence coalition formation and stability in cooperative games.

Cooperative Game Fundamentals

Definition and Components of Cooperative Games

Top images from around the web for Definition and Components of Cooperative Games

• 

  Frontiers | Public Goods Games on Coevolving Social Network Models View original

  Is this image relevant?

• 

  “Procedural” values for cooperative games | SpringerLink View original

  Is this image relevant?

• 

  Frontiers | Public Goods Games on Coevolving Social Network Models View original

  Is this image relevant?

• 

  “Procedural” values for cooperative games | SpringerLink View original

  Is this image relevant?

1 of 2

Top images from around the web for Definition and Components of Cooperative Games

• 

  Frontiers | Public Goods Games on Coevolving Social Network Models View original

  Is this image relevant?

• 

  “Procedural” values for cooperative games | SpringerLink View original

  Is this image relevant?

• 

  Frontiers | Public Goods Games on Coevolving Social Network Models View original

  Is this image relevant?

• 

  “Procedural” values for cooperative games | SpringerLink View original

  Is this image relevant?

1 of 2

• Cooperative games involve players working together to achieve a common goal or maximize their collective payoff
• Players in cooperative games are allowed to form coalitions, which are subsets of players who agree to coordinate their strategies and share the resulting payoff
• The characteristic function, denoted as $v(S)$, assigns a real number to each possible coalition $S$, representing the total payoff that the coalition can guarantee for itself without help from players outside the coalition
• The grand coalition refers to the coalition consisting of all players in the game, often denoted as $N$, and the characteristic function value of the grand coalition, $v(N)$, represents the maximum total payoff that can be achieved through cooperation among all players

Coalitions and their Roles

• Coalitions are formed when players realize that they can achieve better outcomes by working together rather than acting independently
• The formation of coalitions allows players to pool their resources, coordinate their strategies, and share the resulting payoffs
• Different coalitions may have different levels of power or influence in the game, depending on their size, composition, and the characteristic function values associated with them
• The concept of coalitions is central to cooperative game theory, as it enables the analysis of how players might cooperate, negotiate, and distribute payoffs among themselves

Utility in Cooperative Games

Transferable and Non-Transferable Utility

• Transferable utility (TU) games are cooperative games in which the total payoff of a coalition can be freely divided among its members in any way they agree upon
• In TU games, the characteristic function assigns a single real number to each coalition, representing the total payoff that the coalition can achieve
• Non-transferable utility (NTU) games, on the other hand, are cooperative games in which the payoffs to individual players within a coalition are not freely transferable or divisible
• In NTU games, the characteristic function assigns a set of payoff vectors to each coalition, representing the possible payoff allocations among the coalition members

Imputation and Payoff Distribution

• An imputation is a payoff vector that represents a possible distribution of the total payoff among the players in a cooperative game
• For an imputation to be valid, it must satisfy two conditions:
  1. Individual rationality: Each player receives at least as much as they could obtain by acting alone, i.e., $x_i \geq v(\{i\})$ for all players $i$
  2. Efficiency: The sum of the payoffs to all players equals the value of the grand coalition, i.e., $\sum_{i=1}^n x_i = v(N)$
• The set of all valid imputations in a cooperative game is called the imputation set, and it represents the possible ways in which the total payoff can be distributed among the players while satisfying individual rationality and efficiency

Properties of Cooperative Games

Superadditivity

• A cooperative game is said to be superadditive if the value of any coalition is at least as large as the sum of the values of any partition of that coalition into smaller coalitions
• Mathematically, a game is superadditive if $v(S \cup T) \geq v(S) + v(T)$ for any disjoint coalitions $S$ and $T$
• Superadditivity implies that players have an incentive to form larger coalitions, as cooperation always leads to a payoff that is at least as large as the sum of the payoffs that could be obtained by acting separately
• Examples of superadditive games include cost-sharing scenarios (e.g., carpooling, where larger groups can share the cost of transportation more efficiently) and resource pooling situations (e.g., fishing quotas, where larger coalitions can exploit economies of scale)

Convexity

• A cooperative game is said to be convex if it satisfies the following condition: $v(S \cup \{i\}) - v(S) \leq v(T \cup \{i\}) - v(T)$ for any coalitions $S \subseteq T$ and any player $i$ not in $T$
• Convexity implies that the marginal contribution of a player to a coalition increases as the coalition grows larger
• In other words, a player's incentive to join a coalition increases as the coalition size increases, making convex games more stable and easier to form large coalitions
• Examples of convex games include situations with increasing returns to scale (e.g., production processes where larger coalitions can achieve higher efficiency) and scenarios with positive externalities (e.g., vaccination campaigns, where the benefits of vaccination increase as more people participate)