The Myerson value is a solution concept in cooperative game theory. It is a generalization of the Shapley value to communication games on networks. The solution concept and the class of cooperative communication games it applies to was introduced by Roger Myerson in 1977.
Preliminaries
Cooperative games A (transferable utility) cooperative game is defined as a pair ( N , v ) {\displaystyle (N,v)} , where N {\displaystyle N} is a set of players and v : 2 N → R {\displaystyle v:2^{N}\rightarrow \mathbb {R} } is a characteristic function, and 2 N {\displaystyle 2^{N}} is the power set of N {\displaystyle N} . Intuitively, v ( S ) {\displaystyle v(S)} gives the "value" or "worth" of coalition S ⊆ N {\displaystyle S\subseteq N} , and we have the normalization restriction v ( ∅ ) = 0 {\displaystyle v(\varnothing )=0} . The set of all such games v {\displaystyle v} for a fixed N {\displaystyle N} is denoted as W ( N ) {\displaystyle W(N)} .
Solution concepts and the Shapley value A solution concept – or imputation – in cooperative game theory is an allocation rule φ : W ( N ) → R | N | {\displaystyle \varphi :W(N)\rightarrow \mathbb {R} ^{|N|}} , with its i {\displaystyle i} -th component φ i ( v ) {\displaystyle \varphi _{i}(v)} giving the value that player i {\displaystyle i} receives.A common solution concept is the Shapley value φ S {\displaystyle \varphi ^{S}} , defined component-wise as
φ i S ( v ) = ∑ S ⊆ N ∖ { i } | S | ! ( | N | − | S | − 1 ) ! | N | ! ( v ( S ∪ { i } ) − v ( S ) ) {\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 i ∈ N {\displaystyle i\in N} how much they contribute in value (defined via the characteristic function v {\displaystyle v} ) to every possible coalition S ⊆ N {\displaystyle S\subseteq N} .
Communication games Given a cooperative game ( N , v ) {\displaystyle (N,v)} , suppose the players in N {\displaystyle N} are connected via a graph – or network – ( N , g ) {\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 ( N , g , v ) {\displaystyle (N,g,v)} . The graph ( N , g ) {\displaystyle (N,g)} can be partitioned into its components, which in turn induces a unique partition on any subset S ⊆ N {\displaystyle S\subseteq N} given by
Π ( S , g | S ) = { { i : i j ∈ g } : j ∈ S } {\displaystyle \Pi (S,g|_{S})=\{\{i:ij\in g\}:j\in S\}}
… excerpt ends here. Continue reading the full article.
