Myerson value
Myerson value
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 <math>(N, v)</math>, where <math>N</math> is a set of players and <math>v: 2^N \rightarrow \mathbb R</math> is a characteristic function, and <math>2^N</math> is the power set of <math>N</math>. Intuitively, <math>v(S)</math> gives the "value" or "worth" of coalition <math>S \subseteq N</math>, and we have the normalization restriction <math>v(\varnothing) = 0</math>. The set of all such games <math>v</math> for a fixed <math>N</math> is denoted as <math>W(N)</math>.
Solution concepts and the Shapley value A solution concept – or imputation – in cooperative game theory is an allocation rule <math>\varphi: W(N) \rightarrow \mathbb R^</math>, with its <math>i</math>-th component <math>\varphi_i(v)</math> giving the value that player <math>i</math> receives.{{r|g=nb|r= Some authors also impose an efficiency condition into the definition, and require that <math>\sum_{i \in N} \varphi_i (v) = v(N)</math>, while others do not.}}A common solution concept is the shapley-value <math>\varphi^S</math>, defined component-wise as
:<math>\varphi_i^S(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|!\; (|N|-|S|-1)!}{|N|!}(v(S\cup\{i\})-v(S))</math>
Intuitively, the Shapley value allocates to each <math>i \in N</math> how much they contribute in value (defined via the characteristic function <math>v</math>) to every possible coalition <math>S \subseteq N</math>.
Communication games Given a cooperative game <math>(N, v)</math>, suppose the players in <math>N</math> are connected via a graph – or network – <math>(N, g)</math>. 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 <math>(N, g, v)</math>.
The graph <math>(N, g)</math> can be partitioned into its components, which in turn induces a unique partition on any subset <math>S \subseteq N</math> given by
:<math>\Pi(S, g |_S) = \{\{ i : ij \in g\} : j \in S\}</math>
Intuitively, if the coalition <math>S</math> were to break up into smaller coalitions in which players could only communicate with each through the network <math>g</math>, then <math>\Pi(S, g |_S) </math> is the family of such coalitions.
The communication game <math>(N, g, v)</math> induces a cooperative game <math>(N, v_g)</math> with characteristic function given by
:<math>v_g(S) = \sum_{C \in \Pi(S, g |_S)} v(C)</math>
Definition ### Main definition Given a communication game <math>(N, g, v)</math>, its Myerson value <math>\varphi^M</math> is simply defined as the shapley-value of its induced cooperative game <math>(N, v_g)</math>:
:<math>\varphi^M(v, g) = \varphi^S (v_g) </math>
Extensions Beyond the main definition above, it is possible to extend the Myerson value to networks with directed graps. It is also possible define allocation rules which are efficient (see below) and coincide with the Myerson value for communication games with connected graphs.
Properties ### Existence and uniqueness Being defined as the Shapley value of an induced cooperative game, the Myerson value inherits both existence and uniqueness from the Shapley value.
Efficiency In general, the Myerson value is not efficient in the sense that the total worth of the grand coalition <math>N</math> is distributed among all the players:
:<math>\sum_{i \in N} \varphi_i^M(v, g) = v(N)</math>
The Myerson value will coincide with the Shapley value (and be an efficient allocation rule) if the network <math>(N, g)</math> is connected.
(Component) efficiency For every coalition <math>C \in \Pi(S, g |_S)</math>, the Myerson value allocates the total worth of the coalition to its members:
:<math>\sum_{i \in C} \varphi_i^M(v, g) = v(C) \ \ \ \ \ \ \forall C \in \Pi(S, g |_S) </math>
Fairness For any pair of agents <math>i, j \in N</math> such that <math>ij \in g</math> – i.e., they are able to communicate through the network–, the Myerson value ensures that they have equal gains from bilateral agreement to its allocation rule:
:<math> \varphi_i^M(v, g) - \varphi_i^M(v, g - ij) = \varphi_j^M(v, g) - \varphi_j^M(v, g - ij) \ \ \ \ \ \ \forall ij \in g </math>
where <math>g - ij</math> represents the graph <math>g</math> with the link <math>ij</math> removed.