Myerson value

A (transferable utility) cooperative game is defined as a pair $(N,\; v)$, where $N$ is a set of players and $v:\; 2^N\; \backslash rightarrow\; \backslash mathbb\; R$ is a characteristic function, and $2^N$ is the power set of $N$. Intuitively, $v(S)$ gives the "value" or "worth" of coalition $S\; \backslash subseteq\; N$, and we have the normalization restriction $v(\backslash varnothing)\; =\; 0$. The set of all such games $v$ for a fixed $N$ is denoted as $W(N)$.{{cite book |last1=Jackson |first1=Matthew |author1-link=Matthew O. Jackson |title=Social and Economic Networks |date=2008 |publisher=Princeton University Press |isbn=978-0-691-13440-6 |page=411}}

A solution concept – or imputation – in cooperative game theory is an allocation rule $\backslash varphi:\; W(N)\; \backslash rightarrow\; \backslash mathbb\; R^$

:$\backslash varphi\_i^S(v)\; =\; \backslash sum\_\{S\; \backslash subseteq\; N\; \backslash setminus$

\{i\}} \frac{|S|!\; (|N|-|S|-1)!}{|N|!}(v(S\cup\{i\})-v(S))

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

Given a cooperative game $(N,\; v)$, suppose the players in $N$ are connected via a graph – or network – $(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)$.

The graph $(N,\; g)$ can be partitioned into its components, which in turn induces a unique partition on any subset $S\; \backslash subseteq\; N$ given by

:$\backslash Pi(S,\; g\; |\_S)\; =\; \backslash \{\backslash \{\; i\; :\; ij\; \backslash in\; g\backslash \}\; :\; j\; \backslash in\; S\backslash \}$

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

The communication game $(N,\; g,\; v)$ induces a cooperative game $(N,\; v\_g)$ with characteristic function given by

:$v\_g(S)\; =\; \backslash sum\_\{C\; \backslash in\; \backslash Pi(S,\; g\; |\_S)\}\; v(C)$

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

:$\backslash varphi^M(v,\; g)\; =\; \backslash varphi^S\; (v\_g)$

Beyond the main definition above, it is possible to extend the Myerson value to networks with directed graps.{{cite journal |last1=Li |first1=Daniel Li |last2=Shan |first2=Erfang |title=The Myerson value for directed graph games |journal=Operations Research Letters |date=2020 |volume=48 |issue=2 |pages=142-146 |doi=10.1016/j.orl.2020.01.005}} It is also possible define allocation rules which are efficient (see below) and coincide with the Myerson value for communication games with connected graphs.{{cite journal |last1=van den Brink |first1=René |last2=Khmelnitskaya |first2=Anna |last3=van der Laan |first3=Gerard |title=An efficient and fair solution for communication graph games |journal=Economics Letters |date=2012 |volume=117 |issue=3 |pages=786-789 |doi=10.1016/j.econlet.2012.08.026|hdl=10419/86843 |hdl-access=free }}{{cite journal |last1=Béal |first1=Sylvain |last2=Casajus |first2=André |last3=Huettner |first3=Frank |title=Efficient extensions of the Myerson value |journal=Social Choice and Welfare |date=2015 |volume=45 |pages=819–827 |doi=10.1007/s00355-015-0885-4|url=https://crese.univ-fcomte.fr/uploads/wp/WP-2015-01.pdf }}

Being defined as the Shapley value of an induced cooperative game, the Myerson value inherits both existence and uniqueness from the Shapley value.

In general, the Myerson value is not efficient in the sense that the total worth of the grand coalition $N$ is distributed among all the players:

:$\backslash sum\_\{i\; \backslash in\; N\}\; \backslash varphi\_i^M(v,\; g)\; =\; v(N)$

The Myerson value will coincide with the Shapley value (and be an efficient allocation rule) if the network $(N,\; g)$ is connected.

For every coalition $C\; \backslash in\; \backslash Pi(S,\; g\; |\_S)$, the Myerson value allocates the total worth of the coalition to its members:

:$\backslash varphi\_i^M(v,\; g)\; -\; \backslash varphi\_i^M(v,\; g\; -\; ij)\; =\; \backslash varphi\_j^M(v,\; g)\; -\; \backslash varphi\_j^M(v,\; g\; -\; ij)\; \backslash \; \backslash \; \backslash \; \backslash \; \backslash \; \backslash \; \backslash forall\; ij\; \backslash in\; g$

where $g\; -\; ij$ represents the graph $g$ with the link $ij$ removed.

Indeed, the Myerson value is the unique allocation rule that satisfies both (component) efficiency and fairness.

{{reflist|group=nb}}

{{Reflist}}

{{game theory}}

Category:Cooperative games

Category:Network theory