The component-wise egalitarian Myerson value for Network Games

We introduce the notion of a component-wise egalitarian Myerson value for network games under cooperative game-theoretic set-up due to [15]. The component-wise egalitarian Myerson value takes care of both marginalism and egalitarianism in allocating the total resource generated by a network to the players. Marginalism accounts for players’ individual productivities, while egalitarianism does not distinguish between the relative efficiency of players in generating a resource. Over the past few years, network games under cooperative set-up (network games in short) have been effectively used to study various socio-economic issues related to trading and exchange, collaboration among acquaintances, security in the cyber world, sharing of natural resources among stack-holders, multi-graph problems pre-dominant in the field of information and system sciences, etc., to name a few. In a network game, the players/agents link themselves under some binding agreements and generate a worth. The problem then lies in finding a suitable allocation rule that distributes the total worth generated among the players. The study of network games has its origin in the seminal work of [19] on graph restricted games in 1977. In graph-restricted games, later known as communication situations  [16], coalitions in which players are connected through a network are the ones who can generate non-zero worth. The structure of the network is not important in a communication situation. However, when the cost of network formation matters which may be the case, for example, of establishing physical networks among nodes, it becomes important to consider the direct and indirect links among players in the generation of the worth. Consequently, [15] proposes the network games as an extension to the communication situations where the worth of a coalition depends on the network structure through which the players in that coalition are connected. Consequently, the Myerson value first proposed as an allocation rule in [19] for communication situations is further extended to network games in [15, 16]. The position value as an alternative allocation rule is proposed by [18] and characterized by  [3, 21, 22, 25] for communication situations and later extended to network games  [15, 16, 23]. While the position value emphasizes the links among the players more, the Myerson value concerns more on the players. Both these values are based on the productivity of the links and players, respectively; we call this: the marginalistic approach, see [17]. A third allocation rule is the equal division rule which assigns equal pay-off to all the players in a network. The component-wise equal division rule assigns equal pay-offs to the players in a component. Both the equal division rule and the component-wise equal division rule are attributed to the notion of egalitarianism. For a comprehensive study on these allocation rules, we recommend [4, 5, 11, 14, 16]. The marginalistic allocation rules are insensitive to non-productive players. They do not provide incentives to players who are not currently productive but have possibilities of being productive in future collaborations. On the other hand, egalitarianism does not distinguish the players based on their productivity. It encourages free-riding activities in a game [7]. Therefore, in many practical situations, none of these extreme approaches can be deemed suitable for designing an allocation rule. Rules that exhibit solidarity⁵⁵5By solidarity we mean the mutual support or compensation among the players in a network. to non-productive players on the one hand, and encourage the productive players to generate more worth, on the other hand, should ideally combine both these marginal and egalitarian approaches. We call them solidarity values. Take, for example, the International North-South Transport Corridor (INSTC) that connects India with Iran and other parts of Central Asia, Russia and has the scope of expansion up to the Baltic, Nordic, and Arctic regions. The trade between India and the landlocked Central Asian Region is not encouraging. The absence of an efficient transportation network with a facility for storage hubs at key nodes is identified to be the main reason for this shortfall. However, with the opening of Iran’s Chabahar Port, India is expected to do well with its exports.⁶⁶6India’s Export Opportunities Along the International North-South Transport Corridor–Naina Bhardwaj, India Briefing, June 25, 2021 Countries like Afghanistan, Turkmenistan, Bulgaria, etc., can allow their territories for establishing storage hubs and thus, contribute to increasing trades through the INSTC without being directly involved in the worth generation process. Thus, for sustaining the network among the worth generating countries, those non-productive countries should also be given a share of the total worth for their service. This we call their solidarity share. Allocation rules based on marginalism only cannot explain such solidarity-based models. Take another example involving the universal basic income proposed and piloted in many Scandinavian countries and parts of the United Kingdom.⁷⁷7Is Finland’s basic universal income a solution to automation, fewer jobs, and lower wages?– Sonia Sodha, The Guardian, February 19, 2017. The universal basic income is an unconditional income paid by the government to all the citizens, irrespective of whether they produce some worth or not. This is an example of solidarity shown to the non-productive players by the state. The supporters consider this as an answer to the fragmented welfare state that led to growing wage inequality, unemployment, an increasing number of temporary and part-time jobs. However, the critiques argue that such a guaranteed level of income already exists in most of the welfare schemes. The non-contributory nature of the welfare state, the subsidies to those in work, the children allowance and housing benefits, higher taxation slabs for the high waged strata are some of these measures already in place which exhibits solidarity to the non-productive and less productive players. They feel that a separate universal basic income as an egalitarian measure will overload the state’s expenditure and burden to the productive and worth-generating sectors. On the other hand, a flat basic income may also lead to free-riding activities, which is again not desirable. Therefore, a quantified and simplistic approach having sound theoretical background is necessary to highlight how much solidarity the players want to show to the non-productive players. Moreover, it is also not desirable to exhibit solidarity to players when they are at par in terms of their per capita productivity. A suitable allocation rule should adhere to such intuitive considerations while allocating the worth among the players. In section 2, this idea is illustrated with a numerical example. More examples can be found in [12], where the authors introduce the Generalized egalitarian Shapley value in the cooperative framework that reflects the flexibility in choosing the level of marginality based on the coalition size.
In this paper, we study the $\alpha$-component-wise egalitarian Myerson value or simply the $\alpha$-CEM value, which is a convex combination of the Myerson value and the component-wise equal division rule based on the convexity parameter $\alpha\in[0,1]$. The $\alpha$-component-wise egalitarian Myerson value provides a trade-off between marginalism and egalitarianism. The designer can adjust the solidarity to the players by a choice of $\alpha$ between $0$ and $1$. We provide three characterizations of the $\alpha$-component-wise egalitarian Myerson value. Our characterizations follow their counterparts in cooperative games due to [8, 9, 20, 26]. We also propose a non-cooperative bidding mechanism to show that the bidding process results in the $\alpha$-component-wise egalitarian Myerson value under subgame perfect Nash equilibrium. This approach highlights the bargaining framework of the proposed allocation rule and justifies its existence. Each stage of the bidding mechanism analyzes the players’ strategic and solidarity concerns under a cooperative environment. We develop our mechanism based on similar works by [24, 25].
The rest of the paper proceeds as follows. In section 2 we briefly discuss the preliminary concepts required to develop our model. Section 3 includes four characterizations of the component-wise egalitarian Myerson value. Section 4 describes the bidding mechanism for the component-wise egalitarian Myerson value and finally section 5 concludes.

In this section, we compile the preliminary notations, definitions, and results from [1, 2, 4, 11, 16] required for the development of our model.

• •

  Players
  Let $N=\{1,2,...,n\}$ be the set of players. A coalition $S$ is a subset of $N$. We use the corresponding lower case letter $s$ to denote the cardinality of coalition $S$, thus $\#S=s$.

• •

  Networks
  Given the player set $N$ and distinct players $i,j\in N$, a link $ij$ is the pair $\{i,j\}$ which represents an undirected relationship between $i$ and $j$. Clearly, $ij$ is equivalent to $ji$.

  The set of all possible links with the player set $N$ denoted by $g_{N}=\{ij$ $|$ $i,j\in N$ and $i\neq j\}$ is called the complete network.

  A network $g$ is a subset of $g_{N}$. The set of all possible networks on $N$ is $\mathbb{G}^{N}=\{g\mid g\subseteq g_{N}\}$.

  The network $g_{0}=\emptyset$ is the network without any links, which we refer as the empty network.

  Let the number of links in a network $g$ be denoted by $l(g)$. Obviously, $l(g_{N})=\binom{n}{2}=\tfrac{1}{2}n(n-1)$ and $l(g_{0})=0$.

  For every network $g\in\mathbb{G}^{N}$ and every player $i\in N$ we denote $i$’s neighbourhood in $g$ by $N_{i}(g)=\{j\in N\mid j\neq i$ and $ij\in g\}$ as the set of players with whom $i$ is directly linked in $g$.

  The set of players in the network $g$ is denoted by $N(g)$. Also, denote by $n_{i}(g)=\#N_{i}(g)$, and $n(g)=\#N(g)$.

  Denote by $L_{i}(g)=\{ij\in g\mid j\in N_{i}(g)\}\subseteq g$ the set of links of player $i$ in $g$.

• •

  Networks on subsets of players
  For any $g\in\mathbb{G}^{N}$ and $S\subseteq N$, the restriction of $g$ on the coalition $S$ is denoted by $g|_{S}$ and is given by $g|_{S}=\{ij\in g\mid i,j\in S\}$. For $g\subseteq g_{N}$ and $g^{\prime}\subseteq g$, let $g-g^{\prime}$ denote the network $g\setminus g^{\prime}$. Similarly, for $g^{\prime}\subseteq g_{N}\setminus g$, let $g+g^{\prime}$ denote the network $g\cup g^{\prime}$.

• •

  Paths
  A path in $g$ connecting $i$ and $j$ is a set of distinct players $\{i_{1},i_{2},\ldots,i_{p}\}\subseteq N(g)$ with $p\geqslant 2$ such that $i_{1}=i$, $i_{p}=j$, and $\{i_{1}i_{2},i_{2}i_{3},\ldots,i_{p-1}i_{p}\}\subseteq g$.

  We say $i$ and $j$ are connected to each other if a path exists between them and they are disconnected otherwise.

• •

  Components
  The network $h\subseteq g$ is a component of $g$ if for all $i\in N(h)$ and $j\in N(h)$, $i\neq j$, there exists a path in $h$ connecting $i$ and $j$ and for any $i\in N(h)$ and $j\in N(g)$, $ij\in g$ implies $ij\in h$.

  In other words, a component is simply a maximally connected subnetwork of $g$. We denote the set of network components of the network $g$ by $C(g)$.

• •

  Isolated players
  The set of players that are not connected in the network $g$ are collected in the set of isolated players in $g$ denoted by $N_{0}(g)=N\setminus N(g)=\{i\in N\mid N_{i}(g)=\emptyset\}$.

  Clearly, $N_{0}(g_{0})=N$.

• •

  Network games and value functions
  A network game is the pair $(N,v)$ where $N$ is the player set and $v\colon\mathbb{G}^{N}\to\mathbb{R}$ is a function called the characteristic function that satisfies $v(g_{0})=0$.

  The space of all network games with player set $N$ is denoted by $\mathbb{V}^{N}$, which is a $2^{l(g)}-1$ dimensional vector space. If no ambiguity arises on the player set $N$, we denote a network game simply by its characteristic function $v$.

• •

  component additive network games
  A network game $v$ is called component additive if for every network $g\in\mathbb{G}^{N}$, $v(g)=\sum_{h\in C(g)}v(h)$. Component additivity ensures that there is no externality across different components in a network.

  The class of component additive games is denoted by $\mathbb{H}^{N}$, which is a $\sum_{h\in C(g)}2^{l(h)}-1$ dimensional subspace of $\mathbb{V}^{N}$.

  Unless stated explicitly, throughout this paper, we only consider the component additive network games.

• •

  Basis for value functions
  Two important subclasses of games in $\mathbb{V}^{N}$ are the class of unanimity games and the class of identity games which are defined as follows.

  • –

    For any network $g\in\mathbb{G}^{N}$, the unanimity game $(N,u_{g})$ is defined as:

    $$u_{g}(g^{\prime})=\begin{cases}1&\text{if}\leavevmode\nobreak\ g\subseteq g^{\prime}\\ 0&\leavevmode\nobreak\ \text{otherwise}.\end{cases}$$

  • –

    For any network $g\in\mathbb{G}^{N}$, the identity game $(N,e_{g})$ is defined as:

    $$e_{g}(g^{\prime})=\begin{cases}1&\text{if}\leavevmode\nobreak\ g^{\prime}=g\\ 0&\leavevmode\nobreak\ \text{otherwise}.\end{cases}$$

  These two classes of network games are standard bases for $\mathbb{V}^{N}$.

• •

  Allocation rules
  A network allocation rule is a function $Y\colon\mathbb{G}^{N}\times\mathbb{V}^{N}\to\mathbb{R}^{N}$ such that for every $g\in\mathbb{G}^{N}$ and every $v\in\mathbb{V}^{N}$, $Y_{i}(g,v)=0$ whenever $i\in N_{0}(g)$.

• •

  Efficiency
  An allocation rule $Y$ is efficient if for each $g\in\mathbb{G}^{N}$ and $v\in\mathbb{V}^{N}$ it holds that

  $$\sum_{i\in N(g)}Y_{i}(g,v)=v(g).$$

  Thus, an efficient network allocation rule determines how the collective worth generated by a given network $g\in\mathbb{G}^{N}$ with respect to the network game $v\in\mathbb{V}^{N}$ is allocated to the players.

• •

  Component Balanced
  An allocation rule $Y$ is Component Balanced if for every $v\in\mathbb{H}^{N}$ and $g\in\mathbb{G}^{N}$ it holds that

  $$\sum_{i\in N(h)}Y_{i}(g,v)=v(h),\;\textrm{for every component $h\in C(g)$.}$$

• •

  Equal Bargaining Power
  The allocation rule $Y$ satisfies Equal Bargaining Power if for every network $g\in\mathbb{G}^{N}$, component additive network game $v\in\mathbb{H}^{N}$, and for all $i,j\in N(g)$, we have

  $$Y_{i}(g,v)-Y_{i}(g-ij,v)=Y_{j}(g,v)-Y_{j}(g-ij,v).$$

  (1)

• •

  Balanced Contributions Property
  The allocation rule $Y$ satisfies the Balanced Contributions Property if for every network $g\in\mathbb{G}^{N}$, every $v\in\mathbb{H}^{N}$, and for all players $i,j\in N(g)$, we have

  $$Y_{i}(g,v)-Y_{i}\left(g-L_{j}(g),v\right)=Y_{j}(g,v)-Y_{j}\left(g-L_{i}(g),v\right).$$

  (2)

• •

  Balanced Component Contributions Property
  Denote by $h_{i}^{g}$ the component of $g\in\mathbb{G}^{N}$ containing player $i\in N$ ⁸⁸8 $h_{i}^{g}$ is empty when $i$ is an isolated player.. The allocation rule $Y$ satisfies the Balanced Component Contributions Property if for every network $g\in\mathbb{G}^{N}$, every $v\in\mathbb{H}^{N}$, and for all players $i,j\in N(g)$, we have

  $$Y_{i}(g,v)-Y_{i}\left(g-h_{j}^{g},v\right)=Y_{j}(g,v)-Y_{j}\left(g-h_{i}^{g},v\right),$$

  (3)

• •

  The Myerson value
  In the following we define the Myerson value due to  [19] which is extended to network games by [15].

  The Myerson value is the network allocation rule $Y^{MV}\colon\mathbb{G}^{N}\times\mathbb{V}^{N}\to\mathbb{R}^{N}$ given by

  $$Y_{i}^{MV}(g,v)={\sum_{S\subseteq N\setminus i}}\left(v(g|_{S\cup i})-v(g|_{S})\right)\left(\frac{s!(n(g)-s-1)!}{n(g)!}\right).$$

  (4)

  for every $g\in\mathbb{G}^{N}$ and $v\in\mathbb{V}^{N}$.

• •

  The component-wise equal division rule
  The component-wise equal division rule is studied in [15, 25] and is the network allocation rule $Y^{CE}\colon\mathbb{G}^{N}\times\mathbb{V}^{N}\to\mathbb{R}^{N}$ defined by

  $$Y_{i}^{CE}(g,v)=\left\{\begin{array}[]{ll}&\dfrac{v(h_{i}^{g})}{n(h_{i}^{g})}\;\;\;\textrm{if there exists $h_{i}^{g}\in C(g)$ such that $i\in h_{i}^{g}$,}\\ &0\;\;\;\textrm{otherwise.}\end{array}\right.$$

  (5)

  for every $g\in\mathbb{G}^{N}$ and $v\in\mathbb{V}^{N}$.

• •

  The component-wise egalitarian Myerson value
  For $\alpha\in[0,1]$, let the $\alpha$-component-wise egalitarian Myerson value be denoted by $Y^{\alpha-CEM}\colon\mathbb{G}^{N}\times\mathbb{V}^{N}\to\mathbb{R}^{N}$ and defined for every $g\in\mathbb{G}^{N}$ and $v\in\mathbb{V}^{N}$ by

  $$Y^{\alpha-CEM}(g,v)=\alpha Y^{MV}(g,v)+(1-\alpha)Y^{CE}(g,v).$$

  (6)

Next, consider the following example.

In the next section, we characterize the component-wise egalitarian Myerson value.

Before the main results, we list the following axioms, some of which are standard in cooperative game theory and are trivial extensions to their network counterparts, and some are specific to network games. We assume that there are no externalities in worth generation across components in a network and, therefore, from now onwards, unless otherwise specified, we consider only the class $\mathbb{H}^{N}$ of component additive games.