Cooperative Games Basics

Cooperative Games, a core branch of Game Theory, focus on scenarios where players form coalitions to achieve shared goals, maximizing collective outcomes through collaboration. Unlike non-cooperative games, cooperative games emphasize teamwork, negotiation, and fair payoff distribution. This guide from MathMultiverse, inspired by the foundational work of John von Neumann and Oskar Morgenstern, explores coalition formation, solution concepts like the Shapley Value and Core, and their applications in economics, politics, and beyond.

\[ (N, v): \text{ Cooperative game with players } N \text{ and characteristic function } v \]

Definition and Key Concepts

Cooperative games are defined by their structure, focusing on group dynamics and payoff allocation.

Basic Definition

A cooperative game is a pair \( (N, v) \), where \( N = \{1, 2, \ldots, n\} \) is the player set, and \( v: 2^N \to \mathbb{R} \) assigns a value \( v(S) \) to each coalition \( S \subseteq N \), with \( v(\emptyset) = 0 \).

\[ v(S): \text{ Payoff achievable by coalition } S \]

Superadditivity

A game is superadditive if merging coalitions increases value:

\[ v(S \cup T) \geq v(S) + v(T), \quad S \cap T = \emptyset \]

Monotonicity

Larger coalitions yield at least as much value:

\[ S \subseteq T \implies v(S) \leq v(T) \]

Convex Games

A game is convex if:

\[ v(S \cup T) + v(S \cap T) \geq v(S) + v(T) \]

The Core

An allocation \( x = (x_1, \ldots, x_n) \) is in the core if:

\[ \sum_{i \in N} x_i = v(N), \quad \sum_{i \in S} x_i \geq v(S) \text{ for all } S \subseteq N \]

Examples of Cooperative Games

Real-world scenarios illustrate cooperative game dynamics.

Delivery Truck Sharing

Companies A, B, C share a truck. Costs: A=50, B=60, C=70; AB=90, AC=100, BC=110, ABC=120. Savings as values:

\[ v(\{A,B\}) = 50 + 60 - 90 = 20, \quad v(\{A,B,C\}) = 50 + 60 + 70 - 120 = 60 \]

Voting Power

Players A(3 votes), B(2 votes), C(1 vote); need 4 to win:

\[ v(\{A,B\}) = 1, \quad v(\{A,C\}) = 1, \quad v(\{A,B,C\}) = 1 \]

Airport Cost Sharing

Planes need runways of lengths 1, 2, 3; cost = max length:

\[ v(\{1,2\}) = 2, \quad v(\{1,3\}) = 3, \quad v(\{1,2,3\}) = 3 \]

Resource Pooling

Firms pool resources: \( v(\{1,2\}) = 5 \), \( v(\{1,2,3\}) = 8 \).

Production Alliance

Values: \( v(\{A,B\}) = 10 \), \( v(\{A,B,C\}) = 15 \).

Coalitions and Payoff Allocation

Solution concepts ensure fair payoff distribution.

Shapley Value

Fair allocation for player \( i \):

\[ \phi_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|! (n - |S| - 1)!}{n!} [v(S \cup \{i\}) - v(S)] \]

Core Stability

For truck sharing, \( x = (20, 20, 20) \):

\[ x_A + x_B \geq 20, \quad x_A + x_B + x_C = 60 \]

Nucleolus

Minimizes maximum dissatisfaction:

\[ \min \max_{S} [v(S) - \sum_{i \in S} x_i] \]

Banzhaf Index

Voting power for player \( i \):

\[ B_i = \frac{\text{Number of swings}}{2^{n-1}} \]

TU Games Stability

Ensures total payoff allocation:

\[ \sum_{i \in N} x_i = v(N) \]