Myerson value

A (transferable utility) cooperative game is defined as a pair ${\displaystyle (N,v)}$, where ${\displaystyle N}$ is a set of players and ${\displaystyle v:2^{N}\rightarrow \mathbb {R} }$ is a characteristic function, and ${\displaystyle 2^{N}}$ is the power set of ${\displaystyle N}$. Intuitively, ${\displaystyle v(S)}$ gives the "value" or "worth" of coalition ${\displaystyle S\subseteq N}$, and we have the normalization restriction ${\displaystyle v(\varnothing )=0}$. The set of all such games ${\displaystyle v}$ for a fixed ${\displaystyle N}$ is denoted as ${\displaystyle W(N)}$.^[2]

A solution concept – or imputation – in cooperative game theory is an allocation rule ${\displaystyle \varphi :W(N)\rightarrow \mathbb {R} ^{|N|}}$, with its ${\displaystyle i}$-th component ${\displaystyle \varphi _{i}(v)}$ giving the value that player ${\displaystyle i}$ receives.^{[nb 1]}A common solution concept is the Shapley value ${\displaystyle \varphi ^{S}}$, defined component-wise as^[4]

${\displaystyle \varphi _{i}^{S}(v)=\sum _{S\subseteq N\setminus \{i\}}{\frac {|S|!\;(|N|-|S|-1)!}{|N|!}}(v(S\cup \{i\})-v(S))}$

Intuitively, the Shapley value allocates to each ${\displaystyle i\in N}$ how much they contribute in value (defined via the characteristic function ${\displaystyle v}$) to every possible coalition ${\displaystyle S\subseteq N}$.

Given a cooperative game ${\displaystyle (N,v)}$, suppose the players in ${\displaystyle N}$ are connected via a graph – or network – ${\displaystyle (N,g)}$. This network represents the idea that some players can communicate and coordinate with each other (but not necessarily with all players), imposing a restriction on which coalitions can be formed. Such overall structure can be represented by a communication game ${\displaystyle (N,g,v)}$.^[2]

The graph ${\displaystyle (N,g)}$ can be partitioned into its components, which in turn induces a unique partition on any subset ${\displaystyle S\subseteq N}$ given by^[1]

${\displaystyle \Pi (S,g|_{S})=\{\{i:ij\in g\}:j\in S\}}$

Intuitively, if the coalition ${\displaystyle S}$ were to break up into smaller coalitions in which players could only communicate with each through the network ${\displaystyle g}$, then ${\displaystyle \Pi (S,g|_{S})}$ is the family of such coalitions.

The communication game ${\displaystyle (N,g,v)}$ induces a cooperative game ${\displaystyle (N,v_{g})}$ with characteristic function given by

${\displaystyle v_{g}(S)=\sum _{C\in \Pi (S,g|_{S})}v(C)}$

Given a communication game ${\displaystyle (N,g,v)}$, its Myerson value ${\displaystyle \varphi ^{M}}$ is simply defined as the Shapley value of its induced cooperative game ${\displaystyle (N,v_{g})}$:

${\displaystyle \varphi ^{M}(v,g)=\varphi ^{S}(v_{g})}$

Beyond the main definition above, it is possible to extend the Myerson value to networks with directed graps.^[5] It is also possible define allocation rules which are efficient (see below) and coincide with the Myerson value for communication games with connected graphs.^[6][7]