Nodewise Decay in Two-Way Flow Nash Network: A Study of Network Congestion

Banchongsan Charoensook

Department of International Business, Keimyung University, Daegu, South Korea.

DOI: 10.4236/tel.[phone]                

Abstract

This paper studies a noncooperative model of network formation. Built upon the two-way flow model of, it assumes that information decay as it flows through each agent, and the decay is increasing and concave in the number of his links. This assumption results in the fact that a large set of Nash networks are disconnected and consist of components of different sizes, a feature that resembles that of real-world networks. Discussions on this insight are provided.

Keywords

Nash Networks, Network Congestion, Noncooperative Games

1. Introduction

This paper presents a model of network formation game that is built upon the two-way flow model with imperfect information transmission of (Bala & Goyal, 2000a) , It envisages a situation in which information decays due to the agents’ imperfect ability to communicate as opposed to the imperfect connection/link, which is an assumption in most of the existing literature. It thus assumes that information decays as it traverses through each agent, hence the term nodewise decay. Moreover, aiming to shed light on the realism that agent’s effort to communicate tends to be limited, it assumes that nodewise decay level is strictly concave in the amount of agent’s links. Each agent thus knows that whenever he establishes a link with another agent both of them transmit information less efficiently, causing a decline in the value of information that flows through them. This paper aims to understand how this assumption may affect link-formation decision of agents and hence the shape of equilibrium networks. To this end, it identifies the shapes of equilibrium networks and analyzes why they differ from those of other models in the literature. Finally, the paper discusses how the results of the analyses may explain some features of real-world networks.

We argue that this paper’s assumption is worth studying. Consider a firm in which employees’ task is to communicate with each other. In this network, there may be a center-like agent whose role is to collect and distribute information of other agents. Such an agent is important because the degree to which the information is lost depends on his ability to communicate. This is likely to decline as there are more contacts between him and other agents. This fact has two consequences. First, each agent has to take into account that contacting the center damages the information flow. Second, the value of information that he receives in turn may not worth the efforts to contact. Consequently, he may avoid contacting the center by contacting another agent or choosing to be completely disconnected. The fact that the center finds more difficulties in transmitting information as he has more links may be considered as a form of network congestion, and the fact that other agents may avoid contacting the center may be considered as a form of congestion avoidance. However, how this realism affects agents’ linking decision has not been investigated in the literature of game-theoretic network formation to our knowledge. This paper’s attempt to address this issue is therefore the central contribution to the literature.

With this situation in mind, this paper modifies the two-way flow model of BG as follows. In a network g we let the decay factor be nodewise: as information is transmitted through agent i, a fraction of information equal to 1 − σ (i; g) is lost. Moreover, σ (i; g) is decreasing and strictly concave on the amount of i’s links. The strict concavity is assumed for two reasons. First, it reduces mathematical difficulties. The strict concavity assumption implies that information decays completely if an agent possesses a sufficiently large number of links. Second, nodewise decay can be considered as a productivity of an agent in transmitting information. While there is no theoretical support, the following examples show that the difficulties that an agent face in transmitting information tend to increase at an increasing rate. Suppose that an agent stores all pieces of information in one place, then due to the limitedness of space, the chance that multiple pieces of information get mixed up, and hence cause more difficulties in communicating accurately, is arguably likely to increase at an increasing rate. Another example is when the pieces of information are very similar to one another. Then, the chance that an agent does not know which is which, as he has more pieces of information to transmit, is also arguably likely to increase at an increasing rate.

Besides these two assumptions, this paper retains all assumptions of two-way flow of BG, which are briefly described here for unfamiliar readers. Each agent possesses a piece of information that is nonrival. He can choose to sponsor costly links to any agents without their agreements. All links together form the network. If there is a link or a series of links between two agents, they are obliged to share their private information. Thus, the decision of agent to form a link represents his decision to make his private information available to other agents in exchange for receiving their information, and concurrently his willingness to be an information transmitting device. In BG, the decay factor is assumed to be geometric and linkwise: each link causes a fraction of information loss equal to 1 − σ, where σ is constant.

Since this paper models network congestion in a stylized way, we provide two justifications. First, this model makes observing the effects of congestion avoidance easier. The original model of BG and this model permit each agent to access others without their agreements. This implies that each agent decides on his own as to how to avoid the congestion he finds in the network, hence easing the observation. This advantage is also facilitated by the assumption that agents’ information is nonrival. If it is assumed otherwise, it may be difficult to distinguish whether an agent decides not to access another as a result of the congestion or the rival nature of information. Second, because links are formed in a noncooperative way, Nash equilibrium in pure strategies can be applied as the solution concept. This eases the analysis.

Admittedly, the assumption of unilateral link formation has a disadvantage. It entails that agent cannot defend against an access by another agent, even when the access lowers his payoffs. This implication is not realistic in many cases. For example, in a file sharing network, one agent may decline an access by another agent if the access lowers his internet speed. Hence, our model does not provide an insight to this side of reality. We believe, however, that there are some situations in which this model can be applied. These are such as workplace environment in which agent is obliged to disseminate all information he receives even when his productivity is declining, or friendship and kindred networks in which agents voluntarily feel obliged to welcome link formation due to psychological and peer pressure.

Based on the observation from the main results, two insights on the structure of real-world networks can be learned. First, through nodewise decay assumption equilibrium network tends to be fragmented, consisting of disconnected components. The intuition is that agent in one component may avoid entering another in order to avoid the network congestion. This may explain why empirical literature finds that disconnected networks are common in the real world. Second, moving from a smaller network to a larger one (a network with more agents) does not imply that the moving agent will improve his payoffs. The intuition is that agents in a larger network may be more congested (having more links), causing information to flow better in a smaller network. This may explain why real-world networks often consist of fragmented communities of notably different sizes. For example, in a friendship network, some students may prefer to keep their friendship within a small group rather than joining the crowd because they enjoy a stronger friendship that provides a better flow of benefits. These insights can be observed in our first proposition, which finds that no Nash network is connected if information decays at least by half whenever it is transmitted through an agent that has two links. This disconnectedness stands in contrast to the result in the original model of BG that all nonempty Nash networks are connected.

Beside the above disconnectedness, two results are also different from BG’s. First, Nash Network (in pure strategy) does not always exist. This result is shown by an example. Second, no stars are Nash except a centersponsored star if the network has more than three agents¹.

This paper contributes to the literature in game-theoretic network formation, which is pioneered by the work of Jackson & Wolinsky (1996) ². Their model assumes that two agents must share a mutual consent in order that a link is established. A seminal work that contrasts to this model is that of BG in which one-sided link formation is assumed. Since it assumes several simple assumptions such as agent homogeneity and linkwise decay, it has spawned a vast literature that questions how certain realisms, when incorporated as assumptions, influence the shape of equilibrium networks.

A strand of this literature which this paper belongs studies various forms of inefficiency in information flow. Interestingly, most models in this literature focus on link, which is a connection between agents, as a source of inefficiency in information flow rather than agents themselves. For example, Bala & Goyal (2000b) , Haller & Sarangi (2005) and Billand et al. (2011) extend the two-way flow model of BG by assuming that link formation may fail with a positive probability. Also, Billand et al. (2010) studies the insider-outsider model of Galeotti et al. (2006) , which is an extension of BG, by varying the level of linkwise decay. Among this group of literature, noteworthy is that of Bloch & Dutta (2009) and Deroian (2009) , which assume that the decay level of each link varies based upon the extent to which the agents are willing to spend their limited resources. These models share a similarity to the model of this paper in the sense that in this paper each agent is also assumed to have limited ability to communicate. However, a major difference does exist. Unlike the model of Bloch & Dutta (2009) and Deroian (2009) , this model assumes that the decay is nodewise in the sense that the decay occurs each time information traverses through an agent. Thus, it perceives agent, rather than link, as a direct and primary cause of inefficiency in information flow. This difference entails a major interpretation of realism. If the decay is assumed to be linkwise, as most papers do, then the major cause of the decay is the connection or the relationship between agents. On the other hand, if the decay is nodewise, then what causes the decay is the inability of agent to communicate perfectly.

Another paper that shares a certain extent of similarity to this paper is Feri (2011) , which also assumes that the decay is nodewise. Indeed, to our knowledge, apart from this paper Feri (2011) is the only paper that assumes nodewise decay. However, a major difference exists in terms of how the nodewise decay is modeled. In Feri (2011) , the decay level is an outcome of the coordination game played between two agents who share the same link. Thus, it can be interpreted that the decay depends on the compatibility of technology adopted by the two agents. On the other hand, this paper assumes that the decay level depends on the quantity of links that each agent possesses. Thus, our concern is on the limitedness of the efforts of agent to communicate, rather than the technology that he adopts.

The paper proceeds as follows. In Section 2, the model and all assumptions are introduced. Subsequently Section 3 introduces the main results. It consists of two propositions. The first proposition fully characterizes Nash networks under the restriction that information decays at least by half if it traverses through an agent that has more than two links. Admittedly, due to the mathematical difficulties full characterization of Nash network is not achieved when this restriction is removed. The second proposition, instead, discusses certain properties of Nash networks given the removal of this restriction. We also provide some examples of Nash network and their supporting parameters. Subsequently Section 4 uses the analysis from these results to provide some insights to certain features of real-world networks. Finally, Section 5 concludes.

2. The Model

$N=\left\{1,\cdots ,n\right\}$ is a set of agents. i and j are typical members of this set. Each agent possesses a nonrival piece of information that is valuable both to himself and any other agent who has an entry to it. Information flow in this model is two-way in the following sense. If i has an entry to j information, then j also has an entry to i’s information. An entry to information is made possible through the existence of a link or a path, a series of multiple links, between two agents.

Link establishment is costly and one-sided. i can choose to form a link with any other agent without his consent so long as he bears the link formation cost c. A strategy of i is a set $g_i=\left(g_{i,1},\cdots ,g_{i,i-1},g_{i,i+1},\cdots ,g_{i,n}\right)$ where $g_{i,j}\in \left\{0,1\right\}$ and $g_{i,j}=1$ if and only if i forms a link with j. In this case, it is said that i accesses j. Throughout the entire paper the our analysis is restricted to pure strategies. Let $g=\left(g_1,\cdots ,g_n\right)$ be a strategy profile. The strategy space of i is $G_i$ and the set of all pure strategy profiles is $G={\left\{\times G_i\right\}}_{i=1}^n$ .

To visualize how information flows among agents, a strategy profile g can be represented by a network. Pictorially, a network consists of a set of nodes, each represents an agent, and a set of arrows pointing from one node to another. There exists an arrow from node i to node j if and only if i accesses j in a strategy profile g. As a consequence of this symbolization the term network g and strategy profile g are used interchangeably onwards. Figure 1 depicts an example of a network.

Because a link between i and j can be sponsored by either i or j, to distinguish

Figure 1. A network with five agents. $n=5$ , $g_1=\left\{1,0,0,0\right\}$ , $g_2=\left\{0,1,0,0\right\}$ , $g_3=\left\{0,0,1,0\right\}$ , $g_4=\left\{0,0,0,1\right\}$ , $g_5=\left\{0,0,0,0\right\}$ .

the link sponsorship let $D\left(i;g\right)=\left\{k\in N|g_{i,k}=1\right\}$ be the set of all agents whom i accesses and $\mu \left(i;g\right)=\left|D\left(i;g\right)\right|$ be the number of links that i establishes. To indicate whether there is a link between i and j, let ${\bar{g}}_{ij}=\max \left\{g_{i,j},g_{j,i}\right\}$ so that ${\bar{g}}_{i,j}=1$ if and only if there is a link between i and j. Similarly, let $\bar{D}\left(i;g\right)=\left\{k\in N|{\bar{g}}_{i,k}=1\right\}$ and $\bar{\mu }\left(i;g\right)=\left|\bar{D}\left(i;g\right)\right|$ so that $\bar{\mu }\left(i;g\right)$ represents the number of I’s links.

Based upon these notations, information flow is formalized as follows. i’s information flows to j if there exists an ij-path. Formally, an ij-path, $P_{i,j}\left(g\right)$ , is a sequence ${\bar{g}}_{i,j_1},{\bar{g}}_{j_1,j_2},\cdots ,{\bar{g}}_{j_m,j}$ whose each element is 1. If $P_{i,j}\left(g\right)$ exists, it is said that i observes j. The set of all agents observed by i is $1-N\left(i;g\right)=\left\{j\in N|P_{i,j}\text{exists}\right\}$ . Note that if i observes j then j also observes i.

To maintain a comparison with the original two-way flow model with linear payoff in BG, the value of each piece of information that is perfectly transmitted and received is 1. However, in the process of transmitting and receiving this value may decay. In this paper, the decay is incurred nodewise. That is, for each agent k a decay factor $\sigma \left(k;g\right)$ is assigned. As information traverses through k, a fraction of information equal to $1-\sigma \left(k;g\right)$ is lost. That is, $\sigma \left(k;g\right)$ , is the percentage rate at which the value of information is preserved. Therefore, if the information of j is transmitted to i through a path $P_{i,j}$ , the value of j’s information

that i receives is $V\left(P_{i,j}\left(g\right)\right)={\displaystyle {\prod }_{k\in N\left(P_{i,j}\left(g\right)\right)}\sigma \left(k;g\right)}$ , where $N\left(P_{i,j}\left(g\right)\right)$ is the set

of all agents in $P_{i,j}\left(g\right)$ . Figure 2 illustrates how the values of information of other agents flow to agent 1 in a network.

Naturally, if multiple ij-paths exist the value of j’s information received by i is given by the optimal path(s). Formally, let $P_{i,j}\left(g\right)=\left\{P_{i,j}^1\left(g\right),P_{i,j}^2\left(g\right),\cdots ,P_{i,j}^L\left(g\right)\right\}$ be the set of all paths, each enumerated by the superscript, through which i observes j in a network g. The value of the information of j that i obtains in this network is ${\bar{V}}_{i,j}\left(g\right)={\max }_{k\in 1,\cdots ,L}V\left(P_{i,j}^k;g\right)$ . An optimal ij-path, ${\bar{P}}_{i,j}$ , is thus a path that solves ${\max }_{k\in 1,\cdots ,L}V\left(P_{i,j}^k;g\right)$ . The set of all optimal paths is ${\bar{P}}_{i,j}\left(g\right)$ . Similarly, the value of i’s own information is $V_{i,i}=\sigma \left(i;g\right)$ if i has a link and $V_{i,i}=1$ if i has no link. This assumption is justified as follows. As the amount of i’s links increases, so is the amount of information that arrives to him. This decreases his ability to correctly process each piece information before he transmits it to other agents. This in turn affects his ability to process his own information. Alternatively, if he has no link, then he can consume his own information with no decay. That is, $V_{i,i}=1$ if i has no link.

Having defined the value of information, we are now ready to define the payoff of player i from the strategy profile g in a game with n players. It is:

Figure 2. In the above network, ${\bar{V}}_{1,2}\left(g\right)=\sigma \left(1;g\right)\sigma \left(2;g\right)$ , ${\bar{V}}_{1,3}\left(g\right)=\sigma \left(1;g\right)\sigma \left(2;g\right)\sigma \left(3;g\right)$ , ${\bar{V}}_{1,4}\left(g\right)=\sigma \left(1;g\right)\sigma \left(2;g\right)\sigma \left(3;g\right)\sigma \left(4;g\right)$ , ${\bar{V}}_{1,5}\left(g\right)=\sigma \left(1;g\right)\sigma \left(2;g\right)\sigma \left(3;g\right)\sigma \left(4;g\right)\sigma \left(5;g\right)$ .

$U\left(i;g\right)={\bar{V}}_{i,i}\left(g\right)+{\displaystyle \underset{j\in N\left(i;g\right)}{\sum }{\bar{V}}_{i,j}\left(g\right)}-c\cdot {\mu }_i(\; g\; )$

To adjourn this section a major difference between our model and BG’s is pointed out. This difference is in how information decays. In BG, the decay is assumed to be linkwise and geometric. For example, let λ be this decay. If an ij-path consists of m links, then the information of j decays to ${\lambda }^m$ when it arrives to i. Hence, the aggregated decay of a path depends solely on its length. In contrast, the decay in our model is defined nodewise, σ(), which depends on the amount of links of each agent who lies on the path. Consequently, two ij-paths with the same length may not provide the same value of information to i. We remark that this is a major cause of mathematical difficulties in the analysis of equilibrium characterization.

2.1. Nash Networks and Strict Nash Networks

In a network, a point of view of an agent i can be considered as the set of all links formed by all agents in the network except himself. Let this set be $g_{-i}$ . That is, an agent i takes a look at this set and then decides with whom he wishes to form links for the best of his interest. This is his strategy $g_i$ . A set that is a union of $g_i$ and $g_{-i}$ of course form the network g. We denote this set by $g_i\oplus g_{-i}$ and use these notations to define the term Nash network and Strict Nash network below.

Definition 1 (Best response). A strategy $g_i$ is a best response of i to $g_{-i}$ if

$U_i\left(i;g_i\oplus g_{-i}\right)\ge U_i\left(i;{g^{\prime }}_i\oplus g_{-i}\right)\forall {g^{\prime }}_i\in G_i$

Definition 2 (Nash network). A network g is a Nash network if $g_i$ is a best response to $g_{-i}$ for every agent $i\in N$ .

Moreover, if the inequality is strict for all $i\in N$ , Nash network is a Strict Nash Network. We abbreviate the term Strict Nash Network by SNN.

2.2. Assumptions on Decay

Our key assumption is that the decay factor $\sigma \left(i;g\right)$ depends solely on the number of i’s links. This is formalized as follows.

Assumption 1 (Concave Decreasing Nodewise Decay). Let $\varsigma :\mathbb{N}\to \left[0,1\right]$ be a function such that:

1) ${\varsigma }_x$ be the value at x.

2) ${\varsigma }_1=1$ .

3) there exists $K>1$ such that ${\sigma }_x=0$ for all $x>K$ . Moreover, for $x\le K$ , $\varsigma$ is decreasing and strictly concave.

Throughout this paper we assume that $\sigma \left(i;g\right)={\varsigma }_{\bar{\mu }\left(i;g\right)}$ for all $i\in N$ .

Certain remarks on these assumptions are worth elaborating. First, $\sigma \left(i;g\right)={\varsigma }_{\bar{\mu }\left(i;g\right)}$ implies that an agent’s decay factor depends solely on the number of links. Moreover, two agents have the same decay factor if they have the same amount of links. That is, agent homogeneity is assumed. Second, ${\varsigma }_1=1$ entails that perfect information transmission occurs if an agent has exactly one link. Finally, the existence of K in the last part warrants that the nodewise decay factor becomes zero, rather than being negative, once the amount of agent’s link reaches a certain extent.

2.3. Network-Related Definitions

This subsection introduces some properties of networks and definitions of some particular patterns of network that are used in the analysis. A network is minimal if every ij-path is unique. If an ij-path exists for any $i,j\in N;i\ne j$ , a network is said to be connected. Let $g^1$ and $g^2$ be networks and $N^1$ and $N^2$ be their set of agents, $g^1$ is a subnetwork of $g_2$ if $N^1\subset N^2$ and $g^1\subset g^2$ . $g^1$ is said to be a component of $g^2$ if $g^1$ is a maximally connected subgraph of $g^2$ .

The particular patterns of network that are used in the equilibrium analysis are introduced as follows. A network is a line if there are exactly two agents that have one link and every other agent has two links. A network is a wheel if every agent has exactly two links. Note that if a link is removed from a wheel the resulted network is a line. A network is empty if every agent has no link. In such a network, each agent is said to be a singleton. A network is a star if it is a minimally connected network such that there is a unique agent $i^{\text{*}}$ that has exactly one link with every other agent. A star is a center-sponsored star if $i^{\text{*}}$ sponsors all links. A star is a periphery-sponsored star if $i^{\text{*}}$ sponsors no links.

3. Main Results

The goal of this section is to identify Nash networks and their properties. I

summarize main results as follows. For ${\varsigma }_2\le \frac{1}{2}$ , Proposition 1 guarantees the

existence of Nash network regardless of the values of ς₂ and c. It also provides an expansive equilibrium characterization.

Proposition 1. 1) If ${\varsigma }_2\le \frac{1}{2}$ , Nash network exists for any cost c and number

of players n. Moreover, each component of a Nash network is one of the following three types.

a) A three-agent periphery-sponsored star, ie., network (a) in Figure 3.

b) A pair, i.e., network (b) in Figure 3.

c) A singleton, i.e., network (c) in Figure 3.

Figure 3. Three types of components in a Nash network, given that ${\varsigma }_2\le \frac{1}{2}$ .

2) Using the network (a), (b) and (c) in Figure 3, the set of Nash networks for each set of parameters c and ${\varsigma }_2$ is given below.

a) If $c>1$ and ${\varsigma }_2\le \frac{1}{2}$ , then the empty network is a unique Nash network.

b) If $c\le 1$ and ${\varsigma }_2=\frac{1}{2}$ , then Nash network is either the empty network or

the network that contains at most one component that is a singleton, and every other component is either a three-agent peripherysponsored star or a pair.

c) If $c=1$ and ${\varsigma }_2<\frac{1}{2}$ , then the set of Nash networks consists of all networks

that have the following architectures:

· the empty network.

· the network that has at most one component that is a singleton, and every other component is a pair.

d) If $c<1$ and $c>2{\varsigma }_2$ , then Nash network has at most one component that is a singleton, and every other component is a pair.

e) If $c<1$ and $c\le 2{\varsigma }_2$ , then Nash network is.

· the network that has at most one component that is a singleton, and every other component is a pair.

· the network such that each component is either a three-agent periphery-sponsored star or a pair.

A particular feature of Nash networks in Proposition 1 is that none of them are connected, given that $n>3$ . This is a contrast to Proposition 5.3 in BG which shows that every non-empty Nash Network is connected. What drives this contrast? In BG, if i finds that the component that he accesses provides more benefits than the component that j accesses, then j always finds likewise. Since BG assumes that link formation cost is homogeneous, it follows that j has a positive deviation by removing his link with his component and access i’s component instead. However, under the concave decreasing nodewise decay assumption this reasoning is not valid. Whenever j enters the component of i, he reduces the decay factor at the agent with whom the link is formed. This entails that the value of information that j receive may be sufficiently low that it does not cover his link formation cost. Consequently there is no guarantee that his payoff will improve. The following example clarifies this intuition by showing what happens when the linkwise decay assumption in BG is replaced by our nodewise decay assumption.

Example 1. Consider the Nash network for $c=2{\varsigma }_2$ and $c<1$ in Figure 4. It is easy to check that i’s payoff does not improve if he removes his link with j

Figure 4. A Nash network with five agents for $c=2{\varsigma }_2$ and $c<1$ .

and imitate the strategy of k by forming the link with l. Indeed, his benefit from accessing l is 0 since ${\varsigma }_3=0$ .

On the other hand, suppose it is assume that the decay is geometric, linkwise, and the decay factor is $\lambda$ as in BG, then k’s benefit from accessing l is $\lambda +{\lambda }^2$ and i’s benefit from accessing j is merely $\lambda$ . As a result, i has a positive deviation by removing his link with j and accessing l instead.

Contrary to Proposition 1, for ${\varsigma }_2>\frac{1}{2}$ Nash network does not exist for some

parameters c and n. An example is given below.

Example 2. Let $\frac{1}{\sqrt{2}}>{\varsigma }_2>\frac{1}{2},{\varsigma }_3=0$ , and $c=0.98$ , no network with 5 agents

is Nash³.

Contrary to Proposition 1, for ${\varsigma }_2>\frac{1}{2}$ Nash network does not exist for some

parameters c and n. An example is given below.

Example 3. Let $\frac{1}{\sqrt{2}}>{\varsigma }_2>\frac{1}{2},{\varsigma }_3=0$ , and $c=0.98$ , no network with 5 agents

is Nash⁴.

A remark is that the nonexistence of equilibrium originates stems from the fact that nodewise decay assumption causes agents’s payoffs to change discretely. Indeed, due to this complication the provision of full equilibrium characterization

for ${\varsigma }_2>\frac{1}{2}$ is not attained. Instead, Proposition 2 below describes some properties of Nash network for ${\varsigma }_2>\frac{1}{2}$ . It states that no two agents who have exactly

one link want to access the same agent in Nash network. The intuition, which is a result of congestion avoidance, is straightforward. Let i and j have exactly one link with k, and i accesses k. Then i is better off avoiding the link formation with k and accessing j instead. Such avoidance is profitable because initially j has only one link. The link addition by i thus increases the amount of j’s links from one to

two. This fact and the fact that ${\varsigma }_2>\frac{1}{2}$ guarantee that information loss that is

incurred by j is sufficiently low. Formally, let an agent who has exactly one link be called end node and the agent who is his neighbor parent.

Proposition 2. Given that ${\varsigma }_2>\frac{1}{2}$ and $n>3$ ⁵. In a minimal Nash network

g, let j be an end node and i be his parent,

1) if j accesses i, j is the only end node of i;

2) if i accesses j, i accesses all his end nodes.

A corollary of Proposition 2 which is establish below is straightforward: no star is a candidate for Nash network, except center-sponsored star. A notable remark is that this result differs from Proposition 5.3 in BG which shows that all kinds of stars are Nash if decay falls within a certain range.

Corollary 1. Given that ${\varsigma }_2>\frac{1}{2}$ and $n>3$ , no star is a candidate for Nash

network, except center-sponsored star.

Beside center-sponsored star, line is also a candidate for Nash network. Figure 5 shows some Nash networks and their supporting parameters.

4. Discussions

This section points out two particular features of equilibrium networks in this model. It questions why they arise and provide intuitions as to what causes agents to make such link formation decision. Finally it discusses how these intuitions may explain some features of real-world networks.

4.1. Network Congestion May Lead Equilibrium Networks to Be Disconnected

The first observation comes from the fact that all Nash networks for ${\varsigma }_2\le \frac{1}{2}$ are

disconnected, as in Proposition 1. The intuition, which is made clear by Example 1, can be summarized as follows. While establishing a link to an agent is a way to reach a component, it also increases the congestion at the agent who receives the link. This congestion may cause much loss in the information transmitted via the agent. When such congestion, or inefficiency in information transmission, is sufficiently high, an agent may be better off avoiding the congestion altogether and staying disconnected from the component.

Figure 5. Two lines and a star that are Nash.

How does this observation help us understand real-world phenomena? This observation may serve as a hypothesis that explains why empirical evidence finds that real-world networks are often disconnected. If a community is considered as a network in which information is exchanged among agents, it is likely that it is fragmented into sub-communities if agents find that avoiding connection between each sub-community is a way to reduce inefficiency in information flow. For instance, sociologists have long observe that a common feature of friendship networks is that there are agents who are social isolates, disconnecting themselves from the principal component (Ennett & Bauman, 2009) . Also Kumar et al. (2010) give a surprising remark that several online social networks contain isolated communities and singletons.

4.2. Connecting to a Larger Component Does Not Imply Larger Benefits

Our second observation is that a smaller component may provide higher benefits to their members than a larger one. The is evident through the fact that many Nash networks in Proposition 1 consist of components whose sizes, or the numbers of agents, are not equal. Consider, for example, the equilibrium network in Example 1. Observe that i chooses to access an isolated agent j rather than an agent in the larger component. If i accesses j, j’s productivity is ${\varsigma }_1$ . If i accesses someone in the larger component, the productivity of the accessed agent is at most ${\varsigma }_2$ . Hence, if ${\varsigma }_2$ is sufficiently lower than ${\varsigma }_1$ , then his strategy to abandon the smaller component that contains j and enter a larger one gives i relatively lower benefits compared to his strategy to maintain the link with j.

This observation may explain why there are agents who prefer to reside in a relatively smaller component rather than a relatively larger one that contains most of agents. Consider the following hypothesis. While a larger component contains more agents, and hence more information, each agent may possess relatively more connections than his counterpart in a smaller component. If the increase in connections is further assumed to increase inefficiency in information flow, then an agent may prefer to stay in a smaller component rather than joining a larger one. Put differently, when choosing between joining a smaller component or a larger component, an agent faces a tradeoff between the quantity of information and quality of information that he receives. If the quality of information prevails, then he is better off being in a smaller component. A friendship network among adolescent students may serve as an example of this hypothesis. Some students may choose to be “social isolates,” defined as students who are alone or those who maintain their friendships within a smaller group and avoid contacting the major group (Ennett & Bauman, 2009) . This model thus hypothesizes that such behavior arises because by avoiding the crowd the social isolates enjoy higher benefits shared among one another.

Noteworthy is how the above insight relates to literature in Sociology. This model proposes that the existence of social isolates may be explained by a reason that is not agent heterogeneity, which appears to be the most natural reason. The insight from this model, therefore, stands in contrast with a vast literature in Sociology that places agent heterogeneity in terms of ethnics, attitude or physical appearance as a primary cause of social isolates. For example, Haas et al. (2010) assume that poor health in adolescent such as substantial physical handicap may be a cause of social isolation, and Kennedy & Kennedy (2004) suggest that individuals with anxious resistance have a higher risk of becoming social isolates. In addition, a recent work in game-theoretic network formation by Fershtman & Persitz (2021) also illustrates a similar tradeoff in the context of social clubs. In this paper, players face tradeoffs between “high quality links through a series of small clubs and…low quality links produced in large clubs”. Finally, I remark this insight and the aforementioned insight in Section 4.1 are closely related. Indeed, if agents find that joining a larger network does not lead to higher benefits as mentioned in this section, then a better alternative for them is to form another component that is disconnected from the main component, which is what is discussed in Section 4.1.

5. Conclusion

This paper provides a stylized model of network formation with two key assumptions. First, link can be formed without a mutual consent between agents. Second, link addition increases the congestion, or more information loss, at the agent who receives the link and the agent who forms the link. The model allows an ease of observation on how an agent may avoid forming links with other agents due to increasing congestion. As shown in Proposition 1, under a large set of parameters the two key assumptions lead to equilibrium networks that consist of disconnected components. In some cases, these components also have different sizes.

While it is difficult to make generalization from this simplified model, the link-formation behavior of agents in equilibrium networks may provide some insights to two common features of real-world networks. First, the fact that real world networks are often disconnected may be explained by the fact that agents choose to avoid forming a link that bridges two components since the link addition increases congestion, and hence increasing inefficiency in information flow. Second, an agent may prefer maintaining a link with an agent in a smaller component rather than with an agent in a larger component. This is because he takes into account the tradeoff between receiving less quantity of information with higher quality of transmission in a smaller component and more quantity of information with lower quality of information in a larger component and finds that the former prevails.

This model can be extended in several ways. First, to move closer to reality an extension may assume that an agent can choose to vary his nodewise decay for each link that he possesses. Second, since in this model agent homogeneity is assumed, an extension may be to assume a certain form of agent heterogeneity. For example, some agents may have nodewise decay that incurs less information loss than that of other agents. Third, it may be interesting to apply an equilibrium prediction criterion that assumes that link is formed under mutual consent (eg., pairwise stability of (Jackson & Wolinsky, 1996) ).

Appendix

1.1. The Concepts of Marginal Cost and Marginal Potential Benefit and a Useful Lemma

In this subsection, two useful definitions and a lemma for the proofs of Proposition 1 and 2 are introduced. The first two definitions, Marginal Potential Benefit and Marginal Cost, concern the (potential) gain and loss to an agent whenever he adds or removes exactly one link. Subsequently we introduce a lemma that states that an agent has an increasing (decreasing) payoff if the Marginal Potential Benefits are higher (lower) than the marginal cost. Naturally, in Propositions 1 and 2, this lemma is used to show whether a deviation of an agent by adding/removing a link is positive.

Consider an agent i in network g. Let $g+ij\left(g-ij\right)$ be the network that results from the addition (elimination) of the link $g_{i,j}$ by i. In $g+ij$ , the set of all agents that i observes can be partitioned into three sets. The first set contains all agents that i observes in g, and the addition of $g_{i,j}$ does not generate a new optimal path. On the other hand, the second set contains all agents that i observes in g, the addition of $g_{i,j}$ generates a new optimal path to these agents. The third set contains all agents that i observes in $g+ij$ but not in g. These three sets are formalized as follows.

$\begin{array}{l}{N}^1\left(i;g_{i,j}\to g\right)\\ =\left\{j\in N|j\in N(i;g)\wedge j\in N\left(i;g+ij\right)\wedge \left[P_{i,j}(g)=P_{i,j}\left(g+ij\right)\right]\right\}\end{array}$

$\begin{array}{l}{N}^2\left(i;g_{i,j}\to g\right)\\ =\left\{j\in N|j\in N\left(i;g\right)\wedge j\in N\left(i;g+ij\right)\wedge \left[P_{i,j}\left(g\right)\ne P_{i,j}\left(g+ij\right)\right]\right\}\end{array}$

$N^3\left(i;g_{i,j}\to g\right)=\left\{j\in N|j\notin N\left(i;g\right)\wedge j\in N\left(i;g+ij\right)\right\}$

Consider all agents in $N^1\left(i;g_{i,j}\to g\right)$ . Although i can use the same optimal paths to observe them, in $g+ij$ the value of information that he receives from these agents are lower than what he receives in g because $\sigma \left(i;g+ij\right)={\varsigma }_{\bar{\mu }\left(i;g\right)+1}$ . This decline in i’s benefits, and the link formation cost c, are together called Marginal Cost of i for adding $g_{i,j}$ to g.

Definition 3 (Marginal Cost). Let $N^1\left(i;g_{i,j}\to g\right)$ be defined as above, the marginal cost of i for adding $g_{i,j}$ to g is

$\begin{array}{c}MC\left(i;g_{i,j}\to g\right)=c+{{{\displaystyle \sum }}^{\text{}}}_{l\in N^1\left(i;g_{i,j}\to g\right)}\left({\bar{V}}_{il}\left(g\right)-{\bar{V}}_{il}\left(g+ij\right)\right)\\ =c+{{{\displaystyle \sum }}^{\text{}}}_{l\in N^1\left(i;g_{i,j}\to g\right)}\left({\bar{V}}_{il}\left(g\right)-{\bar{V}}_{il}\left(g\right)\frac{{\varsigma }_{\bar{\mu }\left(i;g\right)+1}}{{\varsigma }_{\bar{\mu }\left(i;g\right)}}\right)\end{array}$

The last inequality follows from the fact that the only difference between g and $g+ij$ is the addition of $g_{i,j}$ . As a result, $\sigma \left(i;g+ij\right)={\varsigma }_{\bar{\mu }}\left(i;g\right)+1$ , $\sigma \left(j;g+ij\right)={\varsigma }_{\bar{\mu }\left(j;g\right)+1}$ and $\sigma \left(k;g+ij\right)={\varsigma }_{\bar{\mu }\left(k;g\right)}$ for all $k\ne i,j$ .

Consider all agents in $N^3\left(i;g_{i,j}\to g\right)$ . Because i can observe in $g+ij$ but not in g, The value of information from these agents that i receives are considered as i’s benefit from the link $g_{i,j}$ . Moreover, consider all agents in $N^2\left(i;g_{i,j}\to g\right)$ . These are agents that i does observe in g. But by adding $g_{i,j}$ he is able to find new optimal paths to reach them. Observe, however, that these new paths in $g+ij$ may yield benefits to i that are higher, lower, or equal to the optimal paths in g due to the concave decreasing nodewise decay. The gain from being able to observe $N^3\left(i;g_{i,j}\to g\right)$ and the potential gain/loss from finding new paths to observe agents in $N^2\left(i;g_{i,j}\to g\right)$ are together called Marginal Potential benefit of i for adding $g_{i,j}$ to g.

Definition 4 (Marginal Potential benefit). the marginal potential benefit of i for adding $g_{i,j}$ to g is

$MPB\left(i;g_{i,j}\to g\right)={{{\displaystyle \sum }}^{\text{}}}_{l\in N^3\left(i;g_{i,j}\to g\right)}{\bar{V}}_{il}\left(g+ij\right)+{{{\displaystyle \sum }}^{\text{}}}_{l\in N^2\left(i;g_{i,j}\to g\right)}\left({\bar{V}}_{il}\left(g+ij\right)-{\bar{V}}_{il}\left(g\right)\right)$ .

Having defined the marginal cost and marginal potential benefit, we are ready to introduce the following Lemma.

Lemma 3. Let $MPB\left(i;g_{i,j}\to g\right)$ and $MC\left(i;g_{i,j}\to g\right)$ be defined as above. We have:

1) $U\left(i;g+ij\right)-U\left(i;g\right)=MPB\left(i;g_{i,j}\to g\right)-MC\left(i;g_{i,j}\to g\right)$

2) (link addition proofness) If $MPB\left(i;g_{i,j}\to g\right)>MC\left(i;g_{i,j}\to g\right)$ , then g is not Nash

3) (link deletion proofness) If $MPB\left(i;g_{i,j}\to g-ij\right)<MC\left(i;g_{i,j}\to g-ij\right)$ , then g is not Nash

Proof. The first part is a direct consequence of how $MPB\left(i;g_{i,j}\to g\right)$ and $MC\left(i;g_{i,j}\to g\right)$ are defined. The second part directly follows the first part, stating that has a positive deviation from his strategy in g by adding $g_{i,j}$ if his marginal potential benefit for adding $g_{i,j}$ is higher than the marginal cost. The third part is analogous to the second part, stating that i has a positive deviation from his strategy in g by eliminating $g_{i,j}$ , if his marginal potential benefit for adding $g_{i,j}$ to $g-ij$ is higher than the corresponding marginal cost. □

1.2. Proofs of the Propositions

Proof of Proposition 1. The proof consists of four steps. In the first three steps, we eliminate certain set of networks from being candidates for Nash networks. First, all networks that contains an agent that has more than two links are eliminated. This follows that a non-empty component of Nash network is either a wheel or a line. We subsequently eliminate the wheel in the second step. In the third step, all lines that contain an agent that receives one link and also establishes a link are eliminated. As a result of these three steps, a component in Nash network is a three-agent periphery sponsored star, a pair, or a singleton. Finally, in the fourth step we identify the exact combinations of these three types that are Nash for each pair of c and ${\varsigma }_2$ . This is achieved through direct substitution.

Step 1: A network that contains an agent that has more than two links is

not Nash. Let this agent be i. Observe that ${\varsigma }_3={\varsigma }_4=\cdots =0$ because ${\varsigma }_2\le \frac{1}{2}$

and $\varsigma$ is strictly concave. Therefore, $\sigma \left(i;g\right)={\varsigma }_{\bar{\mu }\left(i;g\right)}=0$ . It follows that if i accesses an agent in this network, he is strictly better off removing the link to save the cost c. Conversely, if i is accessed by an agent j, for the same reason j is better off removing the link. Due to these deviations this network is not Nash.

Step 2: A network that contains a component that is a wheel is not Nash. Consider an agent i who establishes a link in a wheel. Without loss of generality enumerate the agents in $g^{\text{wheel}}$ according to Figure A1. Let $i=1$ . Observe that his direct neighbors are 2 and $n^{\prime }$ . Observe further that if he removes the link $g_{1,n^{\prime }}$ this wheel becomes a line. Denote this wheel and line by $g^{\text{wheel}}$ and $g^{\text{line}}$ respectively. In what follows it is shown that he is strictly better off removing the link $g_{1,n^{\prime }}$ .

Consider an agent $k\ne 1$ . There are two 1k-paths through which 1 observes k. One contains $g_{1,n^{\prime }}$ and the other one does not. Observe that the latter coexists with 1k-path in $g^{\text{line}}$ but the former does not. Denote these two paths by $P_{1,k}^{\text{wheel}}$ and $P_{1,k}^{\text{line}}$ respectively. Observe further that:

· $V_{1,1}\left(g^{\text{wheel}}\right)={\varsigma }_2$ and $V_{1,1}\left(g^{\text{line}}\right)={\varsigma }_1=1$

· for $k\ne 1,n^{\prime }$ , $V\left(P_{1,k}^{\text{wheel}};g^{\text{wheel}}\right)={\varsigma }_2^{n^{\prime }-k+2}$ , $V\left(P_{1,k}^{\text{line}};g^{\text{wheel}}\right)={\varsigma }_2^k$ and, $V\left(P_{i,k}^{\text{line}};g^{\text{line}}\right)={\varsigma }_2^{k-1}$

· for $k=n^{\prime }$ , $V\left(P_{1,k}^{\text{wheel}};g^{\text{wheel}}\right)={\varsigma }_2^2$ , $V\left(P_{1,k}^{\text{line}};g^{\text{wheel}}\right)={\varsigma }^{n^{\prime }}$ and, $V\left(P_{1,n^{\prime }}^{\text{line}};g^{\text{line}}\right)={\varsigma }_2^{n^{\prime }-2}$

As a result, $V\left(P_{1,k}^{\text{wheel}};g^{\text{wheel}}\right)={\varsigma }_2^{n^{\prime }-k+2}>V\left(P_{1,k}^{\text{line}};g^{\text{wheel}}\right)={\varsigma }_2^k$ for $k>\frac{n+2}{2}$ .

This in turn entails that in this wheel $P_{1,k}^{\text{wheel}}$ is a unique optimal path for

$k>\frac{n+2}{2}$ . Based upon these observations, the marginal potential benefits and

marginal cost are expressed below:

Figure A1. A wheel with $n^{\prime }$ agents, enumerated from left to right.

Because ${\varsigma }_2<\frac{1}{2}$ , it holds true that

$MC\left(1;g_{1,n^{\prime }}\to g^{\text{wheel}}-1n^{\prime }\right)>MPB\left(1;g_{1,n^{\prime }}\to g^{\text{wheel}}-1n^{\prime }\right)$ . Consequently, through Lemma $1g^{\text{wheel}}$ is not Nash.

Step 3: if a component of a network is a line that is neither a three-agent periphery-sponsored star nor a pair⁶, then this network is not Nash. The proof is by contradiction. Suppose that the component is neither a three-agent periphery-sponsored star nor a pair, so that the component has at least three agents. It is straightforward to check that in such a component there exists an agent who has two links such that one of the links is formed by himself. Let this agent be i and the link be $g_{i,j}$ . In what follows it is shown that i is strictly better off deleting $g_{i,j}$ .

First, observe that without $g_{i,j}$ i is disconnected from the line that contains j. $g-ij$ thus consists of two components, one contains j and the other one contains i. Denote these two components by $g^j$ and $g^i$ respectively. Suppose that there are $n^{\prime }$ agents in $g^j$ , i’s marginal potential benefits for adding $g_{i,j}$ to $g-ij$ are:

$MPB\left(i;g_{i,j}\to g^{\text{line}}-ij\right)=\sigma \left(i;g^{\text{line}}\right)\sigma \left(j;g^{\text{line}}\right)={\varsigma }_2$

if $n^{\prime }=1$ , and for $n^{\prime }>1$

To compare the marginal potential benefits with the marginal cost, in what follows we identify a lower bound of $MC\left(i;g_{i,j}\to g^{\text{line}}-ij\right)$ . Beside the cost c, i’s nodewise decay drops from ${\varsigma }_1$ to ${\varsigma }_2$ if he establishes $g_{i,j}$ . Therefore, the lower bound $MC\left(i;g_{i,j}\to g^{\text{line}}-ij\right)$ is $\underset{\_}{MC}=c+\left({\varsigma }_1-{\varsigma }_2\right)=c+\left(1-{\varsigma }_2\right)$ .

Because ${\varsigma }_2\le \frac{1}{2},\underset{\_}{MC}>\frac{1}{2}$ and $MB\left(i;g_{i,j}\to g^{\text{line}}-ij\right)\le \frac{1}{2}$ . Therefore,

$MC\left(i;g_{i,j}\to g^{\text{line}}-ij\right)>MPB\left(i;g_{i,j}\to g^{\text{line}}-ij\right)$ . Applying Lemma 3 to this inequality, it is concluded that i is strictly better off deleting $g_{i,j}$ .

Step 4: Equilibrium Characterization for each pair of c and ${\varsigma }_2$ . As a result of the three steps above, every Nash network is a combination of components that are a three-agent periphery sponsored star, a pair, or a singleton. Therefore, it is straightforward to identify which combination constitutes a Nash network. First, all deviations that arise from every combination are categorized. Each deviation is further coupled with the deviating agent’s payoff as a result of deviation and his payoff when he does not deviate. We then substitute the value of each pair of c and ${\varsigma }_2$ to identify whether the deviation is positive. The combinations that have no positive deviations are concluded to be Nash networks accordingly.

To minimize the tedium, Step 4.1 and 4.2 below eliminate some types of deviations by pointing out that they are never positive.

Step 4.1: In a network where each component is a three-agent periphery-sponsored star, a pair, or a singleton, a deviation that causes the deviating agent to have more than one link is never a positive deviation. This result is a direct consequence of Step 2 and 3. Let i be an agent that does this deviation. This entails that i forms a link with an agent j. If j is in the same component as i, then this component becomes a wheel. However, in Step 2 it is shown that i’s payoff in a line is higher than his payoff in a wheel. Consequently this deviation does not make i better off.

Step 4.2: if c < 1, then a network that contains more than one singleton is not Nash. Let i and j be singletons. If i accesses j, his payoff is $1+\left(1-c\right)$ . If i does not access j, he remains isolated and his payoff is 1. Therefore, if $c<1$ i has a strictly positive deviation by accessing j.

Step 4.3: Equilibrium Characterization for each pair of c and ${\varsigma }_2$ . Using Step 4.1 and 4.2, we classify all networks that remain candidates for Nash networks into seven classes as follows.

1) At least one A, at least one B, exactly one C

2) At least one A, at least one B, no C

3) At least one A, no B, exactly one C

4) No A, at least one B, exactly one C

5) All A

6) All B

7) All C (only for $c\ge 1$ )

Finally, identification of Nash network is achieved in the following manner. For each agent in each type of component, all deviations except those eliminated by Step 4.1 and 4.2 are listed and coupled with their deviationbased payoffs and no-deviation payoffs. Figures A2-A4 illustrate such. By substituting the value of c and ${\varsigma }_2$ into the payoffs and subsequently comparing them, we reach the result of Proposition 1.

□

Proof of Proposition 2. In a minimal network g, let $i^{\text{*}}$ be an agent that has a link with an end node. Let $j_1,\cdots ,j_{\hat{n}}$ be the end nodes that have a link with $i^{\text{*}}$ . Suppose that $i^{\text{*}}$ is accessed by $j_1$ . We partition the set of all neighbors of $j_1$ , $N\left(j_1;g\right)$ , into three subsets as follows: (i) $N^1\left(j_1;g\right)=\left\{i^{\text{*}}\right\}$ , (ii) $N^2\left(j_1;g\right)=\left\{j_2,\cdots ,j_{\hat{n}}\right\}$ , and (iii) $N^3\left(j_1;g\right)=\{k\in N\left(j_1;g\right)|k\ne i^{\text{*}}$ and

$k\ne j_2,\cdots ,j_{\hat{n}}\}$ . For each of these subsets, the value of information that $j_1$ receives in g is identified. Subsequently, it is again identified under the assumption that $j_1$ removes $g_{j_1,i^{\text{*}}}$ and accesses $j_2$ instead. We then compare the payoff of $j_1$ in g with his payoff in $g^{\prime }$ , where $g^{\prime }$ is the network resulted from the removal of the link $g_{j_1,i^{\text{*}}}$ and the addition of the link $g_{j_1,j_2}$ (See Figure A5 for an illustrated example). Finally, it is shown that his payoff in $g^{\prime }$ is higher than

Figure A2. Deviations by agents in a three-agent periphery-sponsored star.

Figure A3. Deviations by agents in a pair. Without loss of generality, it is supposed that deviations are caused by agent $b_1$ . Notice that deviations from $b_2$ are not listed as a result of Step 4.1.

Figure A4. Deviations by an agent that is a singleton. Without loss of generality, it is assumed that all deviations are from agent $c_1$ .

Figure A5. The networks g and $g^{\prime }$ in Proposition 2. Observe that in $g^{\prime }$ $j_1$ accesses $j_2$ instead of $i^{\text{*}}$ , unlike in g. Observe that in g, $\hat{n}=3$ , $N^1\left(j_1;g\right)=\left\{i^{\text{*}}\right\}$ , $N^2\left(j_1;g\right)=\left\{j_2,j_3\right\}$ , $N^3\left(j_1;g\right)=\left\{k_1,k_2\right\}$ .

his payoff in g. This is the strategy of this proof.

To identify the value of information that $j_1$ receives, the number of links that agents have in g and $g^{\prime }$ are identified as follows: since the only difference between g and $g^{\prime }$ is that in g $j_1$ accesses $i^{\text{*}}$ but in $g^{\prime }$ $j_1$ accesses $j_2$ , we have $\bar{\mu }\left(i^{\text{*}};g^{\prime }\right)=\bar{\mu }\left(i^{\text{*}};g\right)-1$ , $\bar{\mu }\left(j_2;g\right)=1$ but $\bar{\mu }\left(j_2;g^{\prime }\right)=2$ , and $\bar{\mu }\left(j_k;g\right)=\bar{\mu }\left(j_k;g^{\prime }\right)=1$ for $k\ne 2$ .

Using the above information, $j_1$ ’s payoff in g is:

Therefore,

(1)

Next, $j_1$ ’s payoff in $g^{\prime }$ is identified below. It makes use of the fact that information of $i^{\text{*}}$ flows to $j_1$ via $j_2$ . Moreover, for any agent $l\in N^2\left(j_1;g\right)\cup N^3\left(j_1;g\right)$ and $l\ne j_2$ , notice that l’s information flows to $i^{\text{*}}$ , $j_2$ and $j_1$ in sequential order. As a result, $j_1$ ’s payoff in $g^{\prime }$ is:

Therefore, applying the fact that $\bar{\mu }\left(i^{\text{*}};g^{\prime }\right)=\bar{\mu }\left(i^{\text{*}};g\right)-1$ , and $\bar{\mu }\left(j_2;g\right)=1$ but $\bar{\mu }\left(j_2;g^{\prime }\right)=2$ , we have:

(2)

To be able to compare Equation (1) with (2), in what follows, it is shown that:

$\underset{l\in N^3\left(l;g\right)}{{\displaystyle \sum }}{\bar{V}}_{j_1,l}\left(g\right){\left[{\varsigma }_{\bar{\mu }\left(j_k;g\right)}\right]}^{-1}=\underset{l\in N^3\left(l;g^{\prime }\right)}{{\displaystyle \sum }}{\bar{V}}_{j_1,l}\left(g^{\prime }\right){\left[{\varsigma }_2{\varsigma }_{\bar{\mu }\left(j_k;g\right)-1}\right]}^{-1}$

First, notice that $j_{1}l$ -path is unique for any $l\in N^3\left(l;g\right)$ because g and $g^{\prime }$ are minimal. This in turn necessitates that $i^{\text{*}}$ has at most one link with an agent that is not an end node. Let this agent be k. Thus, for any $l\in N^3\left(l;g^{\prime }\right)$ the sequence of agents in $P_{j_1,l}\left(g\right)$ and $P_{j_1,l}\left(g^{\prime }\right)$ are $l,\cdots ,k,i^{\text{*}},j_1$ and $l,\cdots ,k,i^{\text{*}},j_2,j_1$ respectively. Consequently,

(3)

(4)

Since the only difference between g and $g^{\prime }$ is the fact that $j_1$ removes his link with $i^{\text{*}}$ in g and accesses $j_2$ instead in $g^{\prime }$ , it holds true that ${\bar{V}}_{l,k}\left(g^{\prime }\right)={\bar{V}}_{l,k}\left(g\right)$ . Applying this fact to Equation (3) and (4) above, we have:

Finally, since σ() is strictly concave, ${\varsigma }_2{\varsigma }_{\bar{\mu }\left(j_k;g\right)}>{\varsigma }_{\bar{\mu }\left(j_k;g\right)-1}$ . This inequality, coupled with the Equation (3c) above, entail that $U\left(j_1;g^{\prime }\right)>U\left(j_1;g\right)$ when Equation (1b) is compared with (2b). This completes the proof. □

NOTES

¹A star is a network such that there is a unique center-like agent who connects to all other agents. But all other agents have no links with each other. A center-sponsored star is a star such that the center sponsors the link to every other agent.

² Jackson (2007) and Jackson (2008) provides an overview of network formation literature and an overview of network studies in economics respectively.

³The proof tediously consists of proving that in each possible network there is at least one agent that finds a positive deviation. It is thus omitted.

⁴The proof tediously consists of proving that in each possible network there is at least one agent that finds a positive deviation. It is thus omitted.

⁵If n ≤ 3, this proposition does not apply. Every component of Nash network is either a line or empty. The proof is trivial and is omitted.

⁶Three-agent periphery-sponsored star and pair are lines

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Bala, V., & Goyal, S. (2000a). A Noncooperative Model of Network Formation. Econometrica, 68, 1181-1229. https://doi.org/10.1111/1468-0262.00155
[2]	Bala, V., & Goyal, S. (2000b). A Strategic Analysis of Network Reliability. Review of Economic Design, 5, 205-228. https://doi.org/10.1007/s100580000019
[3]	Billand, P., Bravard, C., & Sarangi, S. (2010). The Insider-Outsider Model Reexamined. Games, 1, 422-437. https://doi.org/10.3390/g1040422
[4]	Billand, P., Bravard, C., & Sarangi, S. (2011). Nash Networks with Imperfect Reliability and Heterogeneous Players. International Game Theory Review, 13, 181-194. https://doi.org/10.1142/S0219198911002939
[5]	Bloch, F., & Dutta, B. (2009). Communication Networks with Endogenous Link Strength. Games and Economic Behavior, 66, 39-56. https://doi.org/10.1016/j.geb.2008.03.007
[6]	Deroian, F. (2009). Endogenous Link Strength in Directed Communication Networks. Mathematical Social Sciences, 57, 110-116. https://doi.org/10.1016/j.mathsocsci.2008.06.007
[7]	Ennett, F., & Bauman, K. E. (2009). Adolescent Social Networks: Friendship Cliques, Social Isolates, and Drug Use Risk. In W. B. Hansen, S. M. Giles, & M. D. Fearnow-Kenney (Eds.), Improving Prevention Effectiveness (pp. 47-58). Tanglewood Research.
[8]	Feri, F. (2011). Coordination in Evolving Networks with Endogenous Decay. Journal of Evolutionary Economics, 23, 955-1000. https://doi.org/10.1007/s00191-013-0313-9
[9]	Fershtman, C., & Persitz, D. (2021). Social Clubs and Social Networks. American Economic Journal: Microeconomics, 13, 224-251. https://doi.org/10.1257/mic.20180143
[10]	Galeotti, A., Goyal, S., & Kamphorst, J. (2006). Network Formation with Heterogeneous Players. Games and Economic Behavior, 54, 353-372. https://doi.org/10.1016/j.geb.2005.02.003
[11]	Haas, S., Schaefer, D., & Kornienko, O. (2010). Health and the Structure of Adolescent Social Networks. Journal of Health and Social Behavior, 51, 424-439. https://doi.org/10.1177/0022146510386791
[12]	Haller, H., & Sarangi, S. (2005). Nash Networks with Heterogeneous Links. Mathematical Social Sciences, 50, 181-201. https://doi.org/10.1016/j.mathsocsci.2005.02.003
[13]	Jackson, M. (2007). Literature Review: The Study of Social Networks in Economics. In J. E. Rauch (Ed.), The Missing Links: Formation and Decay of Economic Networks (pp. 19-43). Russell Sage Foundation.
[14]	Jackson, M. (2008). Social and Economic Networks. Princeton University Press. https://doi.org/10.1515/9781400833993
[15]	Jackson, M., & Wolinsky, S. (1996). A Strategic Model of Social and Economic Networks. Journal of Economic Theory, 171, 44-74. https://doi.org/10.1006/jeth.1996.0108
[16]	Kennedy, J., & Kennedy, C. (2004). Attachment Theory: Implications for School Psychology. Psychology in the Schools, 41, 247-269. https://doi.org/10.1002/pits.10153
[17]	Kumar, R., Novak, J., & Tomkins, A. (2010). Structure and Evolution of Online Social Networks. In P. S. Yu, J. W. Han, & C. Faloutsos (Eds.), Link Mining: Models, Algorithms, and Applications (pp. 337-357). Springer. https://doi.org/10.1007/978-1-4419-6515-8_13