Misplaced Pages

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 ${\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)}$.

Solution concepts and the Shapley value

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.A common solution concept is the Shapley value ${\displaystyle \varphi ^{S}}$, defined component-wise as

${\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 coallition ${\displaystyle S\subseteq N}$.

Communication games

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 coalliations can be formed. Such overall structure can be represented by a communication game ${\displaystyle (N,g,v)}$.

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

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

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

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)}$

Definition

Main definition

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})}$

Extensions

Beyond the main defintion 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 coallition ${\displaystyle N}$ is distributed among all the players:

${\displaystyle \sum _{i\in N}\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 ${\displaystyle (N,g)}$ is connected.

(Component) efficiency

For every coalition ${\displaystyle C\in \Pi (S,g|_{S})}$, the Myerson value allocates the total worth of the coallition to its members:

${\displaystyle \sum _{i\in C}\varphi _{i}^{M}(v,g)=v(C)\ \ \ \ \ \ \forall C\in \Pi (S,g|_{S})}$

Fairness

For any pair of agents ${\displaystyle i,j\in N}$ such that ${\displaystyle ij\in g}$ – 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:

${\displaystyle \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}$

where ${\displaystyle g-ij}$ represents the graph ${\displaystyle g}$ with the link ${\displaystyle ij}$ removed.

Axiomatic characterization

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

Notes

1. Some authors also impose an efficiency condition into the definition, and require that ${\displaystyle \sum _{i\in N}\varphi _{i}(v)=v(N)}$, while others do not.

References

1. ^ Myerson, Roger (1977). "Graphs and Cooperation in Games". Mathematics of Operations Research. 2 (3): 225–229. doi:10.1007/978-3-540-24790-6_2.
2. ^ Jackson, Matthew (2008). Social and Economic Networks. Princeton University Press. p. 411. ISBN 978-0-691-13440-6.
3. Selçuk, Özer; Suzuki, Takamasa (2014). "An Axiomatization of the Myerson Value". Contributions to Game Theory and Management. 7.
4. Shapley, Lloyd S. (1953). "A Value for n-person Games". In Kuhn, H. W.; Tucker, A. W. (eds.). Contributions to the Theory of Games. Annals of Mathematical Studies. Vol. 28. Princeton University Press. pp. 307–317. doi:10.1515/9781400881970-018. ISBN 9781400881970.
5. Li, Daniel Li; Shan, Erfang (2020). "The Myerson value for directed graph games". Operations Research Letters. 48 (2): 142–146. doi:10.1016/j.orl.2020.01.005.
6. ^ van den Brink, René; Khmelnitskaya, Anna; van der Laan, Gerard (2012). "An efficient and fair solution for communication graph games". Economics Letters. 117 (3): 786–789. doi:10.1016/j.econlet.2012.08.026.
7. ^ Béal, Sylvain; Casajus, André; Huettner, Frank (2015). "Efficient extensions of the Myerson value". Social Choice and Welfare. 45: 819–827. doi:10.1007/s00355-015-0885-4.

• Cooperative games
• Network theory