DON and Shapley Value for Allocation among Cooperating Agents in a Network: Conditions for Equivalence

Abstract

In a paper appearing in a recent issue of this journal (Studies in Microeconomics), the authors explored a new method to allocate a divisible resource efficiently among cooperating agents located at the vertices of a connected undirected network. It was shown in that article that maximizing social welfare of the agents produces Pareto optimal allocations, referred to as dominance over neighbourhood (DON), capturing the notion of dominance over neighbourhood in terms of network degree. In this article, we show that the allocation suggested by the method competes well with current cooperative game-theoretic power centrality measures. We discuss the conditions under which DON turns exactly equivalent to a recent ‘fringe-based’ Shapley Value formulation for fixed networks, raising the possibility of such solutions being both Pareto optimal in a utilitarian social welfare maximization sense as well as fair in the Shapley value sense.

Keywords

Network centrality neighbourhood dominance Pareto optimal allocation Shapley value

Introduction

In an article appearing recently in this journal (Sridhar & Mandyam, 2016), the authors explored a new method for the allocation of a divisible resource among a group of cooperating network-connected agents on the basis of a measure of connectedness. Cooperation among agents in this setting implied an agreement among the agents to share the available resource on the basis of a principle of common benefit that is acceptable to all the agents. In a large class of problems of this nature, how well connected an agent is in its neighbourhood serves as one of the critical criteria for the allocation.

In that article, the authors described a utilitarian welfare maximizing solution which is grounded in traditional microeconomic theory, and yet accommodated the notion of networks in a natural way. The extensions proposed were employed to explore loan allocation in a microfinance application, and were shown to result in a network power centrality measure which was referred to as ‘Dominance over Neighbourhood’, or DON.

This class of allocation problems has long been traditionally viewed as a fair division problem in Cooperative Game Theory (CGT). In such a framework, the well-known Shapley Value (SV) solution concept for evaluating individual allocations on the basis of the agent’s marginal contributions to all possible coalitions that may be formed has been extended to networks in many alternative ways (Gilles, 2010). The central argument for the use of SV in many practical problems is that it conforms to a set of axioms relating to efficiency, nullity, symmetry and additivity, endowing the allocation with desirable properties of fairness. The SV has found applicability in many network scenarios ranging from engineering to biology (Bass, Diallo, Nelson, Soto, Myers, & Walhout, 2013; Kötter, Reid, Krumnack, Wanke, & Sporns, 2007; Moretti, Fragnelli, Patrone, Bonassi, 2010; Saad, Han, Debbah, & Bessar, 2009; Sajitz-Hermsteina & Nikoloskia, 2012).

Among the interesting recent contributions towards efficient allocation in networks of cooperating agents is the notion of the ‘fringe’ neighbourhood set suggested by Suri and Narahari (2008), which permits formulation of a characteristic function that extends the concept of individual node degree to neighbourhood connectivity. We shall refer to this characterization of SV as ‘fringe-SV’, or FSV. In a more recent paper, Michalak, Aadithya, Szczepanski, Ravindran and Jennings (2013) showed that FSV for this class of allocation problems can in fact be calculated in linear time with an analytical formula under the assumption that all possible coalitions were feasible.

In this article, we shall demonstrate that under certain network conditions and rate parameter settings, DON and FSV, as defined above turn numerically equivalent. This is a surprising result since they originate in different traditions of microeconomics. We also draw attention to the fact that while FSV produces allocations as a dominance-based centrality measure determined by node degree, DON produces both dominance-based optimal allocations as well as optimal flows of the shared resource among the agents that are required to achieve such an allocation. Additionally, both allocations offer conceptually similar link fairness.

The central theme of this article is to establish the conditions under which this equivalence occurs, and to highlight the fact that DON can play the role of FSV as a network centrality measure in a richer application context where agents are risk-averse and payoffs may be exponential.

In order to bring out the equivalence properties and conditions, we shall briefly summarize the notational and conceptual framework of both DON and FSV in the following two sections, the second and third sections. In the fourth section, we present results with network examples, demonstrating a variety of conditions under which DON and FSV are identical, and those under which DON approximates FSV with facilities for tuning. We discuss some implications of the equivalence in the fifth section.

DON Summary

In this section, we shall summarize the DON model set-up and solution. More details are in the cited paper (Sridhar & Mandyam, 2016), where the methodology was placed in a microfinance context. We have restated the essential core of the formulation here in a more general network context so that the results may be conveniently compared with the FSV allocations.

We assume that a community of agents has dyadic reciprocal relationships among themselves which can be represented as an un-weighted, undirected network, represented as a graph G(N,E), where the agents are located at the vertices of the graph and E denotes the set of links between vertices.

Let the square matrix A(n x n) denote the adjacency matrix associated with graph G, such that its elements a_ij = 1 if node (or vertex, or agent, synonymously) i has a link (or edge, synonymously) to node j, and 0, otherwise. We define a neighbourhood set, $N_{i}; i \in N$ , for every agent such that any other agent $j \in N_{i} i f f a_{i j} = 1; j \neq i$ . Neighbourhood defines the set of agents directly connected to an agent. The number of connections a node has in the graph is usually referred to as the degree of the node, and is denoted here by $α_{i} = \sum_{j \in N_{i}} a_{i j} = # N_{i}$ , the cardinality of set N_i.

Let X denote the total sum available for allocation among the set $N = {1, 2, .. n}$ of n agents. Suppose each agent derives utility $u_{i} (x_{i}); i \in N$ , from an allocation value $x_{i} > 0; i \in N$ , such that

\sum_{i e N} x_{i} = X .

(1)

The equality constraint states that the entire amount is efficiently allocated among the agents leaving no surpluses or balances.

We assume that the utility functions are concave and satisfy conditions ensuring that the agents exhibit resource utilization rate parameterized as $ρ_{i} = - \frac{u_{i}^{"}}{u_{i}^{'}}; i \in N .$ .

Given a network of agents, we seek to obtain allocations, ${\tilde{x}}_{i}; i \in N$ , as solutions to a constrained optimization problem whose objective is to maximize social welfare of the network of agents modelled as the following weighted sum of their individual utilities:

m a x i m i z e \sum_{i \in N} (1 + α_{i} σ_{i}) u_{i} (x_{i}),

(2)

subject to Equation (1), where we consider a (given) constant rate, $- 1 < σ_{i} \leq 1; \forall i \in N$ , at which individual agents contribute quantities, $σ_{i} u_{i} (x_{i})$ , as externalities in proportion to their network degree, $α_{i}; i \in N,$ to the sum, $\sum_{i e N} u_{i} (x_{i})$ . When this rate parameter is positive, the externality is positive; and the externality is negative appropriately, when the parameter is negative.

Optimal solutions, ${\tilde{x}}_{i}; i \in N,$ to this problem can be obtained by forming the Lagrangian, and finding first order conditions:

(1 + σ_{i} α_{i}) u^{'} (x_{i}) = λ; \forall i \in N,

(3)

where $λ$ is the Lagrangian multiplier.

Under the assumption of concavity of the utility functions, it is easy to show that a solution must exist, and it is in fact a Pareto optimal solution which satisfies the following criteria:

1. assign higher (lower) allocations to those agents that have higher (lower) degree connectivity;

2. allocations are Pareto efficient with no surpluses or balances in meeting the constraint (Equation [1]), ensuring that for any feasible alternative allocation, $u_{i} (x_{i}) \leq u_{i} ({\tilde{x}}_{i}); i \in N,$ with the inequality holding for at least one agent.

Given a graph whose adjacency matrix is A , individual node degrees are $α_{i}; i \in N,$ we solve Equations (1)–(2) in order to obtain the optimal solution ${\tilde{x}}_{i}; i \in N,$ by forming the Lagrangian and using the first order conditions. Using

u_{i} (x_{i}) = \frac{1}{ρ_{i}} (1 - e^{- ρ_{i} x_{i}}); i \in N,

(4)

in Equation (3), where the parameter $ρ_{i}; i \in N$ characterizes the utilization parameter of the i^th agent.

Pareto optimal solutions to Equations (1)–(2) may be obtained as

{\tilde{x}}_{i} = \frac{R}{ρ_{i}} X + q_{i}; \forall i \in N,

(5)

where

q_{i} = \frac{R}{ρ_{i}} \sum_{j \in N_{i}} \frac{1}{ρ_{j}} \ln (\frac{β_{i}}{β_{j}}); \forall i \in N,

(6)

and we have set $\frac{1}{R} = \sum_{j \in N} \frac{1}{ρ_{j}}$ and $β_{i} = 1 + σ_{i} α_{i}$ . We refer to the expression in Equation (5), as the formula for DON, which produces optimal allocations on the Pareto frontier.

In a matrix form, the allocation solution may be expressed as

\tilde{x} = X c^{T} + Q b^{T},

(7)

where the vector, $c = [\frac{R}{ρ_{1}} \frac{R}{ρ_{2}} \dots \frac{R}{ρ_{n}}]$ , and $b = [\ln β_{1} \ln β_{2} \dots \ln β_{n}]$ ;

Q = [\begin{array}{l} \frac{R}{ρ_{1}} \frac{R {N_{1}}}{ρ_{1}} - \frac{a_{12}}{ρ_{1}} \frac{R}{ρ_{2}} - \frac{a_{13}}{ρ_{1}} \frac{R}{ρ_{1}} .. - \frac{a_{1 n}}{ρ_{1}} \frac{R}{ρ_{n}} \\ - \frac{a_{21}}{ρ_{2}} \frac{R}{ρ_{1}} \frac{1}{ρ_{2}} \frac{R^{{N_{2}}}}{ρ_{2}} - \frac{a_{23}}{ρ_{2}} \frac{R}{ρ_{3}} .. - \frac{α_{2 n}}{ρ_{2}} \frac{R}{ρ_{n}} \\ : : : : \frac{1}{ρ_{n}} \frac{R {N_{n}}}{ρ_{n}} \end{array}],

(8)

where $\frac{1}{R^{{N_{i}}}} = \sum_{j \in N_{i}} \frac{1}{ρ_{j}}$ , and the elements $a_{i j}; i, j \in N; i \neq j$ belong to the adjacency matrix A, as defined earlier. Q holds the quantities $q_{i}; i \in N$ arranged in a matrix form. The off-diagonal elements of the square matrix Q (n x n) are either zero or non-zero depending upon the elements $a_{i j} = 1 o r 0; i, j \in N, i \neq j$ of the adjacency matrix A representing the network. The values of $q_{i}; \forall i \in N$ are such that $\sum_{i \in N} q_{i} = 0$ , rendering Q rank deficient. See Sridhar and Mandyam (2016) for more details on flow interpretations and balance properties of Q .

A ‘standardized’ version of DON is obtained under the condition X = n, and the agents are indistinguishable in terms of the rate parameter; that is, $ρ_{i} = ρ \forall i \in N$ , in a network characterized by the network degree and externality:

{\tilde{x}}_{i} = 1 + \frac{1}{n ρ} \sum_{j \in N_{i}} \ln (\frac{β_{i}}{β_{j}}) .

(9)

The dominance property of DON gives higher importance to nodes that not only have higher degree but also dominate over their neighbours in terms of degree, and thus agents who exhibit ‘power over powerless neighbours’ are rewarded with higher allocations. Hence, DON behaves as a power centrality index for networks (Bonacich, 1987).

Before proceeding to the discussion on the FSV formulation, let us illustrate the application of Equation (9) with an undirected network example. Consider the 10-node network depicted in Figure 1.

Figure 1.

10-node Example Network

Note that the network has nodes with a degree of 2, 3 or 5. The DON allocation is calculated using Equation (9) with a setting $σ_{i} = 1 \forall i \in N$ , and $ρ_{i} = ρ = 1 \forall i \in N .$ The allocation values are tabulated in the third row of Table 1.

Observe that nodes 5 and 8 have the same degree of 5, but node 8 receives a lower allocation because its neighbourhood has one node, that is, node 7, with a higher degree. Also note how node 6 with a degree of 2 has a higher allocation than node 1 which has a degree of 3 because node 6 has less dominant, even if fewer, neighbours than node 1.

DON not only admits rich agent-local characterization with additional parameterization via $σ$ and $ρ$ to produce Pareto optimal allocations, it also offers the means to obtain directions of flow of resources along the given links to accomplish the optimal allocation. Laying out the element level product terms of Qb ^T in a matrix E , the flow is obtained by calculating the differences in the off-diagonal terms, $f_{i j} = e_{i j} - e_{j i}; \forall i, j \in N, i \neq j$ , where the elements $e_{i j}; i, j \in N$ denote the elements of $E . f_{i j} > 0$ . implies a flow from node i to node j, and vice-versa when implies equal flows in either direction.

For the network of Figure 1, the flows that are associated with optimal allocation allow the specification of direction to the arrows linking the nodes, as in Figure 2. In the figure, blue links indicate zero-flows due to equal flows in both direction, while red arrows depict directions of resource flows required to achieve optimality of allocation.

Figure 2.

Resource Flow at Optimal Allocation with DON

Fringe-Shapley Value (FSV) for Network Agents

Among the popular and effective measures of power centrality in networks in the current literature are those founded on the CGT solution concept of SV (Shapley, 1953; Shapley & Shubik, 1954; Soham & Brown, 2010).

Table 1.

DON and FSV Allocations for 10-node Network of Figure 1

Node No.	1	2	3	4	5	6	7	8	9	10
Degree	3	3	2	2	5	2	3	5	3	2
DON Allocation	0.9189	0.9882	0.9019	0.9307	1.2197	0.9712	0.9882	1.191	0.9882	0.9019
FSVAllocation	0.8333	1	0.75	0.8333	1.5	0.9167	1	1.4167	1	0.75

Source: All data generated from synthetic network examples.

Considering the set of agents, $N = {1, 2, \dots, n}$ , assume that any agent can be identified by its index $i \in N$ , as before. CGT assumes that agents can form coalitions, $C \subseteq N$ , of ‘players’, and associates with every such coalition a characteristic function $v : \to R$ , a real number representing the value created by the members of the coalition through cooperation. The tuple (N, v) is referred to as a characteristic function game. It is assumed that $v (\emptyset) = 0$ , and that a ‘grand’ coalition of all n agents, v(N), which is formed, produces the highest value. The object of the game is to determine how much of the total value generated is to be assigned to each agent. Such an assignment, often also referred to as payoff, is the equivalent of an allocation to each agent out of a total value of X = n.

The SV assigns a value to each agent on the basis of the average marginal contribution made by the agent to all possible coalitions that may be formed with the participation of this agent. One of the convenient forms of the SV assignment expression is written as:

S V (i) = \sum_{C \in N \ {i}} \frac{| C |! (| N | - | C | - 1)!}{| N |!} [v (C \cup^{​} {i}) - v (C)]; i \in N

(10)

The expression involves the contribution of agent i calculated as the difference between the value of coalition C with agent i and without the participation of i. Such contributions are averaged over all combinatorial possibilities of forming coalition C.

The popularity of the SV stems from its ‘fairness’ characterized by its four desirable properties of the allocations: (i) Efficiency, in the sense that there are no balances or surpluses; (ii) Symmetry, in the sense that they do depend on identity; (iii) Nullity property that implies agents who make no marginal contributions do not receive any allocations and (iv) Additivity, in the sense that value created by two games add up to the sum of the values of the games (Gilles, 2010; Soham & Brown, 2010).

The SV was originally proposed only for unconnected groups of agents where all coalitional combinations were feasible. In order to apply this solution concept to fixed networks, broadly, two approaches have been proposed in the literature. One of the approaches considers the marginal contribution of each node to feasible coalitions formed by sub-graphs that this node can participate in (Borkotokey & Sarangi, 2011; Borm, Owen, & Tijs, 1992; Go´mez, Gonza´lez-Arangu¨ena, Manuel, Owen, del Pozo, & Tejada, 2003; Myerson, 1977; Slikker, 2005a; Slikker, 2005b).

A recent approach (Suri & Narahari, 2008) generalizes the notion of node degree to a set of neighbours one hop away, referred to as the ‘fringe’, that may be reached by a coalition, $C \subseteq N$ . The SV, referred to in this setting as FSV, is obtained by defining the characteristic function of the game as the cardinality of the ‘fringe’ set, $f r i n g e (C) = {i \in N : i \in C (o r) \exists j \in C s u c h t h a t (i, j) \in E}$ . Marginal contributions of individual agents are calculated under the assumption that all combinations of coalitions are feasible. However, since the number of ways in which such coalitions could be formed is exponential in the network size, the values were proposed to be calculated approximately.

Recently, it was shown (Michalak et al., 2013) that using probabilistic calculations for estimating the combinatorial possibilities of participation of every agent to different fringes that may form in an undirected network, the SV for this characteristic function game, denoted as $F S V (i); i \in N$ , to reflect its association with the FSV formulation, can be calculated exactly using the formula:

F S V (i) = \frac{1}{1 + α_{i}} + \sum_{j \in N_{i}} \frac{1}{1 + α_{j}}; \forall i \in N

(11)

Note that this formula for fixed networks has the following interesting properties.

1. Power Centrality Index: The allocation formula in Equation (11) is a power centrality index, which associates higher values to those agents which have higher node degrees and also have neighbours with lower degree (Bonacich, 1987). This is easy to see from the manner in which more additive terms appear in the summation over the neighbourhood, N_i for the ith node when the degree of node is larger, and each term turns larger when the degree of the corresponding neighbour is relatively smaller. This index has thus been described as a measure that captures the ‘power over powerless’ notion.

Let us illustrate this calculation with the same example of a 10-node network pictured in Figure 1. We can observe that the allocation pattern, tabulated in the fourth row of Table 1, closely follows that for DON. The observations made about the differences in nodes 5 and 8, and those between nodes 1 and 6 are valid here also.

2. Link Fairness: In general, fairness of allocations in collectives is a vast research area (Moulin, 2004). However, FSV-based allocation in the form (Equation [11]) exhibits the following link fairness property:

Given any two nodes with equal degree and a link between them, the FSV assigned to each of the nodes reduces by the same amount when the link is removed, irrespective of the degree structure of their neighbours.

Proof:

Consider two nodes $k, l \in N$ , in a given network with neighbourhoods, N_k and N_l , respectively, such that k ϵ N_l and l ϵ N_k, implying that there is a link between nodes k and l.

Let us define FSV on the basis of Equation (11) of the node k before and after removal of the link between nodes k and l as FSV (k), and FSV' (k), respectively. The changes in the allocation r_k and r_l, respectively, due to removal of the link is

r_{k} = F S V (k) - F S V^{'} (k) = [\frac{1}{1 + α_{k}} + (\frac{1}{1 + α_{l}} + \sum_{j \in {N_{k} \ l}} \frac{1}{1 + α_{j}})] - [\frac{1}{1 + (α_{k} - 1)} + \sum_{j \in {N_{k} \ l}} \frac{1}{1 + α_{j}}]

Similarly, for node l:

r_{l} = F S V (l) - F S V^{'} (l) = [\frac{1}{1 + α_{l}} + (\frac{1}{1 + α_{k}} + \sum_{j \in {N_{l} \ k}} \frac{1}{1 + α_{j}})] - [\frac{1}{1 + (α_{l} - 1)} + \sum_{j \in {N_{l} \ k}} \frac{1}{1 + α_{j}}]

With some minor simplification of the aforementioned expressions, we can see the difference between the changes in the allocations to the two nodes, that is,

r_{k} - r_{l} = \frac{1}{α_{l}} - \frac{1}{α_{k}}

(12)

Clearly, even though neighbourhood dominance essentially determines FSV, removal of the link between the nodes k and l can cause numerically asymmetric losses or gains in their respective allocations, depending on their degrees. However, relative differences are independent of neighbourhood structure and its functional form as in Equation (12) is symmetric to interchange of node degrees.

When the nodes k and l have the same degree, that is, $α_{k} = α_{l} = α$ , the right hand side of Equation (12) reduces to zero. In this case, the differences, r_k and rl in the FSV for both the nodes, before and after removing the link, are:

r_{k} = r_{l} = \frac{α - 1}{α (α + 1)} .

(13)

This is, of course, valid for any choice of $k, l \in N$ , where $α = α_{k} = α_{l}$ As expected, the expression in Equation (13) also captures the notion that the loss due to removal of single link from the node drops rapidly as the degree increases.

It may be noted that the FSV as in Equation (11) does not conform to the definition of link fairness in the framework of certain other graph-restricted cooperative games (Go´mez et al., 2003; Myerson, 1977). In the Myerson formulation, for instance, link fairness is referred to the property that the allocation to any two connected nodes reduces by the same amount when the link between them is removed, independent of their degree connectivity. In contrast, in the fringe-based characteristic function formulation of SV considered here, the differences are equal, that is, $r_{k} = r_{l}$ , only when the two nodes have the same degree, that is, $α_{k} = α_{l} .$

As an illustration, in the network of Figure 1, if the link between nodes 5 and 8 is removed, the allocations for both node 5 and node 8 reduce by an amount 0.133333, as seen in Table 2, demonstrating link fairness property.

Conditions for the Equivalence between DON and FSV

In this section, we shall make some observations on the conditions under which DON and FSV turn equivalent.

Table 2.

FSV for Network of Figure 1, with Link 5–8 Removed

Node No.	1	2	3	4	5	6	7	8	9	10
Degree	3	3	2	2	5	2	3	5	3	2
FSV Allocation	0.9	1.0333	0.7833	0.8667	1.3667	0.9167	1.0333	1.2833	1.0333	0.7833

Source: All data generated from synthetic network examples.

Since FSV as defined in the previous section is determined entirely by network degree alone and while DON accommodates additional parameterization through ρ and σ, we shall determine conditions on these parameters that make DON allocations equivalent to FSV by comparing them for the same fixed network.

The first important observation is that DON, like FSV, can also be calculated in time linear in the size of the network.

Another key observation is that DON satisfies the same type of link fairness condition as satisfied by FSV for fixed connected networks.

Observation 1

DON is link fair in the same sense as in the case of the FSV defined in the third section.

Link Fairness: Given any two nodes with equal degree and a link between them, the DON allocation assigned to each of the nodes reduces by the same amount when the link is removed, irrespective of the degree structure of their neighbours.

Proof:

As before, let us select any two nodes $k, l \in N$ , with neighbourhoods, $N_{k}$ and , such that $N_{l}$ and $k \in N_{l}$ . Let the nodes have a degree of $α_{k}$ and $α_{i}$ , respectively. Let us set $σ_{i} = 1 \forall i \in N$ and $ρ_{i} = ρ \forall i \in N$ . Let DON(k) and $D O N^{'} (k)$ denote the allocations for node k with the link between node k and node l present and removed, respectively. Similarly, let $D O N (l)$ and $D O N^{'} (l)$ denote the allocations for node l with the link between node k and node l present and removed, respectively. We can then calculate the differences, $t_{k} = D O N (k) - D O N^{'} (k); t_{l} = D O N (l) - D O N^{'} (l),$ in DON allocations for node k and node l, using Equation (9) exactly as we did with the SV.

It can be shown that (proof omitted)

t_{k} - t_{l} = \frac{1}{n ρ} \ln [\frac{{(\frac{α_{k} + 1}{α_{k}})}^{α_{k} + 1}}{{(\frac{α_{l} + 1}{α_{l}})}^{α_{l} + 1}} \frac{α_{k}^{2}}{α_{l}^{2}}],

(14)

assuring link asymmetric treatment of allocations. As in the case of the FSV, the functional form is symmetric to interchanges of node degrees.

For the setting , Equation (14) obviously produces a difference of zero, asserting that the DON allocation differences are identical. We also see that at this setting:

t_{k} = t_{l} = \frac{1}{n ρ} (α - 1) \ln (\frac{α + 1}{α}) .

(15)

This relationship is valid for any choice of $k, l \in N$ , where $α_{k} = α_{l}$ . It can be verified that the functional form of right hand side in Equation (15) is such that loss in allocation also reduces as the degree of node increases in proportion to the size of the network.

This establishes the fact that DON which is Pareto optimal in the social welfare maximization sense is also link fair in the FSV sense. For the case where the link between nodes 5 and 8 in the network of Figure 1 is removed, the difference is easily calculated to be 0.0729 for both nodes, with $ρ_{i} = ρ = 1 \forall i \in N$ .

Note, of course, that the above differences also admit additional parameterization with both $ρ$ and $σ$ values.

Observation 2

For a setting of $σ_{i} = σ = 1; ρ_{i} = ρ; \forall i \in N$ , there is a specific value of ρ at which DON and FSV turn exactly identical for the class of biregular networks, that is, for networks in which all nodes have one of any two distinct node degree values.

Proof:

Consider connected networks where nodes have either a degree of $α^{'}$ or $α^{″}$ . With a setting $σ = 1$ , and $δ_{1} = 1 + σ α^{'} = 1 + α^{'}$ and $δ_{2} = 1 + σ α^{″} = 1 + α^{″}$ , we can write down the allocations for DON and SV, respectively as

For all nodes with a degree $α^{'}$ :

DON (α^{'}) = 1 + \frac{1}{n ρ} \ln \frac{δ_{1}^{δ_{1} - 1}}{δ_{1}^{k} δ_{2}^{δ_{1} - k - 1}} = 1 + \frac{1}{n ρ} (δ_{1} - k - 1) \ln \frac{δ_{1}}{δ_{2}}; 0 \leq k \leq δ_{1} - 1;

and for all nodes with a degree $α^{″}$ :

DON (α^{″}) = 1 + \frac{1}{n ρ} \ln \frac{δ_{2}^{δ_{2} - 1}}{δ_{2}^{k} δ_{1}^{δ_{2} - k - 1}} = 1 + \frac{1}{n ρ} (δ_{2} - k - 1) \ln \frac{δ_{2}}{δ_{1}}; 0 \leq k \leq δ_{2} - 1;

where the values of integers, k, serve to enumerate all possible networks under the biregular degree constraint. The SV values may be written down similarly as

\begin{matrix} FSV (α^{'}) = (k + 1) \frac{1}{δ_{1}} + (δ_{1} - k - 1) \frac{1}{δ_{2}}; 0 \leq k \leq δ_{1} - 1; \\ FSV (α^{″}) = (k + 1) \frac{1}{δ_{2}} + (δ_{1} - k - 1) \frac{1}{δ_{1}}; 0 \leq k \leq δ_{2} - 1; \end{matrix}

respectively, for all nodes with a degree of $α^{'}$ and $α^{″}$ .

It is easily shown (proof omitted) that $DON (α^{'}) = FSV (α^{'})$ ; and $DON (α^{″}) = FSV (α^{″})$ over all k possible neighbourhood configurations only when

ρ = \frac{1}{n} - \frac{\ln \frac{δ_{2}}{δ 1}}{\frac{1}{δ_{1}} - \frac{1}{δ_{2}}} .

(16)

The class of biregular networks where the degree of every node is one of two distinct integers is non-trivial, characterizing some types of interesting practical neighbourhood types and includes many classical benchmark network structures, such as single and multi-star networks.

The numerical equivalence between DON and FSV for a particular setting of $ρ$ for this class of networks, a consequence of the relationship between logarithmic means of degrees characterizing flows in DON and harmonic means of degrees characterizing FSV, brings out an interesting scenario where the allocation has all the fairness and efficiency properties of FSV, while also offering the DON’s ability to characterize non-linear agent behaviour and determine flows for welfare maximization.

It should also be noted that this specific benchmark value of $ρ$ has a maximum value of $ρ_{\max} = 0.8109$ , which occurs for a basic star network with only three nodes—a classical minimal star benchmark. For all other networks in this class, over all sizes, the value of $ρ$ rapidly reduces, rendering the exponential utility functions increasingly closer to linearity.

For the purpose of illustration, consider the 10-node biregular network of Figure 3, where nodes have either a degree of 2 or of 5.

Figure 3.

10-node Biregular Network

The result we obtain when we set $σ_{i} = 1 \forall i \in N$ and $ρ_{i} = ρ = 0.4159; \forall i \in N$ , appears in Table 3. We find that $DON (i) = FSV (i); \forall i \in N$ for the example network.

Observation 3

In connected networks where nodes have arbitrary degree distributions, it is possible to determine a common value of $ρ$ for the agents, at which DON closely approximates the FSV in a minimum least-squares deviation sense.

We observe that for the 10-node network of Figure 1, the allocations for a setting of $ρ = 0.4385$ produces DON values that are closest (Correlation Coefficient = 0.9962) in a least-square sense to SV.

This approximate equivalence holds for large networks with more diverse degree distributions as well. Figure 4 shows a comparison between DON and FSV for a real electric power network with 4941 nodes and 6594 edges.

DON allocations were obtained with a

ρ = 0.001

(approx.), suggesting near linear utility function forms for the agents. The differences between DON and FSV values were found minimal at lower node degrees as seen in the chart, where the green and red dots representing DON and FSV, respectively, nearly overlap. The differences are more pronounced at higher node degree values. However, DON and FSV values were found to be strongly correlated (Correlation = 0.9666), and sum of squared difference between them was found to be small, at 0.1578 per cent of the total allocation of n = 4941.

Table 3.

DON = FSV for the Network of Figure 3, when ρ = 0.4159

Node No.	1	2	3	4	5	6	7	8	9	10
Degree	2	2	2	2	5	2	2	5	2	2
AllocationDON = FSV	0.6667	0.8333	0.8333	0.8333	1.6666	1	0.8333	1.6666	0.8333	0.8333

Source: All data generated from synthetic network examples.

We can further explore conditions for an exact equivalence between DON and SV in another manner, by asking what values the network externality rate parameters, $σ_{i}; i \in N$ , may be set to in order to make them equivalent in networks with arbitrary degree distributions. We have the following observation.

Figure 4.

Source: Retrieved from http://konect.uni-koblenz.de/networks/opsahl-powergrid

Observation 4

For scenarios where agents are indistinguishable in terms of , we may obtain values of network externality rate parameters at which DON values are exactly equivalent to SV for any network.

Consider a network in which we have $ρ_{i} = ρ; \forall i \in N$ . Let the SV values, $S V (i); i \in N$ , be denoted by the $(n x 1)$ vector, s. From Equation (7), we can solve for $b^{T}$ in $Q b^{T} = \tilde{s} - X c^{T}$ :

b^{T} = Q^{+} (\tilde{s} - X c^{T}),

(17)

where $Q^{+}$ is the Moore–Penrose generalized inverse of $Q$ (recall that has a rank of [n – 1]). From Equation (17), we can calculate values of $σ_{i}; i \in N$ using

σ_{i} = \frac{e^{b_{i}} - 1}{α_{i}}; i \in N .

We thus obtain balanced benchmark externality rates, $σ_{i}, i \in N$ , that characterize Pareto optimal allocations for fixed $ρ$ . As an illustration, the calculated sigma values are shown overlaid on the network in Figure 5.

Figure 5.

Calculated Externality Rates for DON = FSV Allocations

The calculated values of $σ$ show that nodes with higher degree (5 and 3) need to make positive externality contributions (shown in red) to the social welfare, in order to compensate for the negative contributions (shown in blue) of those agents with very low connectivity (degree of 2), across all neighbourhoods.

Concluding Remarks

DON was proposed recently as an optimal network allocation methodology, grounded in utilitarian microeconomic theory, but extended in a manner that makes in amenable to model network flows under certain assumptions on the form of the agent utility function. It was shown earlier that the Pareto optimal allocation methodology produced a class of power centrality measures that captures the notion of dominance over 1-hop neighbours.

This class of problems has been previously solved in the Cooperative Game Theoretic tradition by posing it in the framework of the SV solution concept, extended to accommodate the structure of networks. The concept of a ‘fringe’ set was used to develop an exact formula for the SV using the cardinality of the fringe as the characteristic function.

We have established that DON exhibits certain link fairness properties that are offered by the FSV. Additionally, we see that for a class of biregular networks, DON allocations are identical to FSV for certain specific parameterizations. We also show that the equivalence between DON and the FSV can be used to determine fair values of network externalities in the DON framework.

Principally, while the FSV as a link-fair centrality measure is built on the assumption of risk-neutrality of agents, we have demonstrated that DON offers a powerful methodology for Pareto optimal and link-fair network allocation when the agents are risk-averse and the payoffs are exponential. This represents the ability to characterize agent-local behaviour in richer, non-linear ways. Additionally, DON provides the means to obtain flow information, and model network externalities in meaningful ways, facilitating new ways to create benchmark cooperative behaviour for given networks.

Further work is aimed at exploring the application of DON as a power centrality measure in complex networks where risk-aversion and trust play central roles in determining sharing of resources.

The authors wish to thank Prof. Anjan Dasgupta, Department of Biochemistry, Calcutta University for insightful discussions on optimal network flows.

References

Bass

Diallo

Nelson

Soto

Myers

Walhout

(2013, December). Using networks to measure similarity between genes: Association index selection. Nature Methods , 10(12), 1169–1176.

Bonacich

(1987). Power and centrality: A family of measures. American Journal of Sociology , 92(5), 1170–1182.

Borkotokey

Sarangi

(2011). An interactive allocation rule for networks . Munich Personal RePEc Archive.

Borkotokey

Sarangi

(2011). Allocation rules for fixed and flexible networks: the role of players and their links (MPRA Paper No. 38340, posted 24 April 2012). Louisiana State University. Retrieved from https://mpra.ub.uni-muenchen.de/38340/

Borm

Owen

Tijs

(1992). On the position value for communication situations. Siam Journal of Discrete Mathematics , 5(3), 305–320.

Gilles

(2010). The cooperative game theory of networks and hierarchies . Heidelberg: Springer.

Go´mez

Gonza´lez-Arangu¨ena

Manuel

Owen

del Pozo

Tejada

(2003). Centrality and power in social networks: A game theoretic approach. Mathematical Social Sciences , 46(1), 27–54.

Kötter

Reid

Krumnack

Wanke

Sporns

(2007). Shapley ratings in brain networks. Frontiers in Neuroinformatics , 1(2). doi:10.3389/neuro.11.002.2007

Michalak

Aadithya

Szczepanski

Ravindran

Jennings

(2013). Efficient computation of the Shapley value for game-theoretic network centrality. Journal of Artificial Intelligence Research , 46, 607–650. doi:10.1613/jair.3806

10.

Moretti

Fragnelli

Patrone

Bonassi

(2010). Using coalitional games on biological networks to measure centrality and power of genes. Bioinformatics , 26(21), 2721–2730. https://doi.org/10.1093/bioinformatics/btq508

11.

Moulin

(2004). Fair division and collective welfare . Cambridge, MA: MIT Press.

12.

Myerson

(1977). Graphs and cooperation in games. Mathematics of Operations Research , 2(3), 225–229.

13.

Saad

Han

Debbah

Bessar

(2009). Coalitional game theory for communication networks: A tutorial. IEEE Signal Processing Magazine , 26(5), 77–97. DOI: 10.1109/MSP.2009.000000.

14.

Sajitz-Hermsteina

Nikoloskia

(2012). Restricted cooperative games on metabolic networks reveal functionally important reactions. Journal of Theoretical Biology , 314, 192–203.

15.

Shapley

L.S.

(1953). A value for n-person games. In Kuhn

Tucker

(Eds), Contributions to the theory of games (Vol. 2, pp. 307–317). Princeton, NJ: Princeton University Press.

16.

Shapley

L.S.

Shubik

(1954). A method for evaluating the distribution of power in a committee system. The American Political Science Review , 48(3), 787–792.

17.

Slikker

(2005a). A characterization of the position value. International Journal of Game Theory , 33(4), 505–514.

18.

Slikker

. (2005b). Link monotonic allocation schemes. International Game Theory Review , 7(4), 473–489.

19.

Soham

Brown

(2010). Multiagent systems: Algoritmic, game theoretic, logical foundations . Retrieved from www.masfoundations.org/mas.pdf

20.

Sridhar

Mandyam

(2016). Loan allocation and guarantee structure for group borrower networks in microfinance. Studies in Microeconomics , 4(2), 100–114. Doi:10.1177/2321022216661588

21.

Suri

Narahari

(2008). Determining the top-k nodes in social networks using the Shapley value . AAMAS ‘08: Proceedings of the 7th International Joint Conference on Autonomous Agents and Multi-Agent Systems, 1509–1512. Retrieved from http://dl.acm.org/citation.cfm?id=1402911