Cooperative Game Theory

Transferable Utility Cooperative Games

Input $G=(N,v)$

1. Set $N=\{1,\dots ,n\}$ of agents
   • A coalition is a subset of agents; $N$ is the grand coalition
2. Characteristic function: $v:2^N\to \mathbb{R}$ mapping coalitions $C\subseteq N$ to the utility $v(C)$ that the coalition members can generate by working together, satisfying
   • normalization: $v(\varnothing )=0$
   • non-negativity: $v(C)\ge N$ for $C\subseteq N$
   • monotonicity: $v(C)\le v(D)$ for $C\subseteq D$

Outcome $(\mathcal{C},\mathbf{x})$

• Coalition Structure: $\mathcal{C}=\{C_1,\dots ,C_k\}$ is partition of agents into coalitions ($k$ is not fixed)
• Payoff Vector: $\mathbf{x}=(x_1,\dots ,x_n)$ distributing utility generated by coalitions to agents, satisfying
  • $x_i\ge 0$ for all $i\in N$
  • ${\sum }_{i\in C}{x}_i=v(C)$ for each $C\in \mathcal{C}$

---

TU Cooperative Games: Solution Concepts

Core Stability

Core: The core of a TU game $G=(N,v)$, denoted $\mathrm{core}(G)$, is the set of all outcomes $(\mathcal{C},\mathbf{x})$ in which no coalition has an incentive to deviate, i.e.

${\sum }_{i\in C}{x}_i\ge v(C)\text{ for all }C\subseteq N$

For an outcome $(\mathcal{C},\mathbf{x})$, we call $C$ a deviating / blocking coalition if ${\sum }_{i\in C}{x}_i<v(C)$

Outcomes in the Core Maximize Total Generated Utility: Let $G=(N,v)$ be a TU game. For $(\mathcal{C},\mathbf{x})\in \mathrm{core}(G)$, we have

${\sum }_{i\in N}{x}_i={\sum }_{C\in \mathcal{C}}v(C)\ge {\sum }_{C^{\prime }\in {\mathcal{C}}^{\prime }}v(C^{\prime })$

for each coalition structure ${\mathcal{C}}^{\prime }$

• The core of a TU game might be empty!

$ϵ$-Core: An outcome $(\mathcal{C},\mathbf{x})$ of a TU game $G=(N,v)$ is in the $ϵ$-core if ${\sum }_{i\in C}{x}_i\ge v(C)-ϵ$ for all $C\subseteq N$.

• cost for moving / laziness

Power Indices

Idea: Distribute utility according to agents’ “influence” in the game

Naive Ideas: (Average) Marginal contributions, i.e. adding agents one by one to the coalition

• when we do not average, the ordering of the agents changes the result

Shapley Value: The Shapley value ${\phi }_i$ of agent $i$ is

${\phi }_i=\frac{1}{n!}{\sum }_{\pi \in {\Pi }_N}{\Delta }_{\pi }(i)$

• ${\Pi }_N$: set of all permutations of $N$ (i.e. bijective mappings from $N$ to $N$)
• For $\pi \in {\Pi }_N$ and $i\in N$, let ${\mathcal{S}}_{\pi }(i)$ be the set of all predecessors of $i$ in $\pi$
  • ${\mathcal{S}}_{\pi }(i)=\{j\in N|\pi (j)<\pi (i)\}$
• The marginal contribution of some agent $i$ with respect to permutation $\pi \in {\Pi }_N$ is
  • ${\Delta }_{\pi }(i):=v({\mathcal{S}}_{\pi }(i)\cup \{i\})-v({\mathcal{S}}_{\pi }(i))$
• Probabilistic Interpretation: Randomly choose an agent ordering. ${\phi }_i$ is the expected marginal contribution of $i$ to the coalition of their predecessors

Charaterization of the Shapley Value:

• Nullity: If $i\in N$ is a dummy agent, then ${\phi }_i=0$
  • Dummy Agent: An agent $i\in N$ is a dummy agent if $v(C)=v(C\cup \{i\})$ for each $C\subseteq N$
• Efficiency: ${\sum }_{i\in N}{\phi }_i=v(N)$
• Symmetry: For two symmetric agents $i,j\in N,{\phi }_i={\phi }_j$
  • Symmetric Agents: Two agents $i,j\in N$ are symmetric if $v(C\cup \{j\})=v(C\cup \{i\})$ for each $C\subseteq N\setminus \{i,j\}$
• Additivity: For two TU games $(N,v)$ and $(N,u)$ and agent $i\in N$, ${\phi }_i$ in $(N,v+u)$ is equal to ${\phi }_i$ in $(N,v)$ plus ${\phi }_i$ in $(N,u)$

Check for this properties before calculating Shapley values

---

Computing Shapley Value

Idea: All permutations $\pi$ with identical $S_{\pi }(i)$ have the same ${\Delta }_{\pi }(i)$ $\to$ iterate over preceding subsets instead of permutations

Algorithm: For some coalition $C\subseteq N\setminus \{i\}$, there are $|C|!(n-|C|-1)!$ permutations $\pi$ with $S_i(\pi )=C$

${\phi }_i=\frac{1}{n!}{\sum }_{C\subseteq N\setminus \{i\}}|C|!(n-|C|-1)![v(C\cup \{i\})-v(C)]$