Paper deep dive
Formation of Circular Directed Networks with Shared Link Costs
Juan M. C. Larrosa, Fernando Tohmé
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 88%
Last extracted: 7/9/2026, 6:43:15 AM
Summary
This paper develops a noncooperative game-theoretic model of directed network formation where agents create links to access information while sharing path costs. It demonstrates that strict Nash equilibria result in circular directed networks, which are minimally connected, Pareto optimal, and efficient. The model contrasts with Bala and Goyal's framework by emphasizing shared path costs and heterogeneous information values.
Entities (7)
Relation Signals (6)
Noncooperative network formation model → predictsequilibriumstructureas → Circular directed networks
confidence 95% · The central result is that strict Nash equilibria must take the form of circular directed networks.
Strict Nash equilibrium → takestheformof → Circular directed networks
confidence 95% · The central result is that strict Nash equilibria must take the form of circular directed networks.
Noncooperative network formation model → compareswith → Bala and Goyal's model
confidence 90% · Finally, the paper compares this framework with Bala and Goyal's model...
Circular directed networks → exhibitsproperty → Pareto optimality
confidence 90% · The model also shows that strict Nash networks are both Pareto optimal and efficient in terms of aggregate welfare.
Circular directed networks → satisfiesproperty → Minimal connectivity
confidence 90% · circular networks are exactly the Nash networks that use the minimum number of links while allowing every agent to access all available information.
Shared link costs → generates → Different equilibrium implications
confidence 85% · shared path costs and heterogeneous information values generate different equilibrium implications.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:This paper develops a noncooperative model of directed network formation in which agents create links to access valuable information while sharing the costs generated along the paths through which information is obtained. Each agent is endowed with a positive amount of information and chooses, simultaneously, which other agents to contact. A directed link initiated by one agent allows her to access the information of the contacted agent and of the latter's reachable network, but each link in the resulting information path entails a unit cost. Payoffs therefore depend on the total value of accessible information net of the accumulated connection costs required to obtain it. The paper characterizes the relationship between strategy profiles and directed graphs, defines accessibility, paths, components, and minimal connectedness, and studies the Nash architectures induced by individual best responses. The central result is that strict Nash equilibria must take the form of circular directed networks. Moreover, circular networks are exactly the Nash networks that use the minimum number of links while allowing every agent to access all available information. Although noncircular weak Nash networks may exist, they are structurally redundant and do not satisfy the same minimality property. The model also shows that strict Nash networks are both Pareto optimal and efficient in terms of aggregate welfare. Finally, the paper compares this framework with Bala and Goyal's model, emphasizing that shared path costs and heterogeneous information values generate different equilibrium implications. The analysis supports the equivalence between strict stability and minimal connectivity in directed information networks.
Tags
Links
- Source: https://arxiv.org/abs/2606.28382v1
- Canonical: https://arxiv.org/abs/2606.28382v1
Trouble viewing inline? Open PDF directly →
Full Text
45,930 characters extracted from source content.
Expand or collapse full text
Formation of Circular Directed Networks with Shared Link Costs Juan M. C. Larrosa Department of Economics, Universidad Nacional del Sur; Instituto de Ciencias e Ingeniería de la Computación (ICIC). E-mail: jlarrosa@uns.edu.ar. Fernando A. Tohmé Department of Economics, Universidad Nacional del Sur; Instituto de Matemática de Bahía Blanca (INMABB). E-mail: ftohme@uns.edu.ar. Abstract This paper develops a noncooperative model of directed network formation in which agents create links to access valuable information while sharing the costs generated along the paths through which information is obtained. Each agent is endowed with a positive amount of information and chooses, simultaneously, which other agents to contact. A directed link initiated by one agent allows her to access the information of the contacted agent and of the latter’s reachable network, but each link in the resulting information path entails a unit cost. Payoffs therefore depend on the total value of accessible information net of the accumulated connection costs required to obtain it. The paper characterizes the relationship between strategy profiles and directed graphs, defines accessibility, paths, components, and minimal connectedness, and studies the Nash architectures induced by individual best responses. The central result is that strict Nash equilibria must take the form of circular directed networks. Moreover, circular networks are exactly the Nash networks that use the minimum number of links while allowing every agent to access all available information. Although noncircular weak Nash networks may exist, they are structurally redundant and do not satisfy the same minimality property. The model also shows that strict Nash networks are both Pareto optimal and efficient in terms of aggregate welfare. Finally, the paper compares this framework with Bala and Goyal’s model, emphasizing that shared path costs and heterogeneous information values generate different equilibrium implications. The analysis supports the equivalence between strict stability and minimal connectivity in directed information networks. JEL Classification: C72, L13, L20 Keywords: network formation games; one-way directional communication; line network Introduction Interaction among agents can be represented in several ways. One way of representing direct exchanges that has attracted considerable interest in recent years is through networks. Since it has a simple graphical representation, this analytical tool was first adopted in sociology and anthropology. For experts in those areas, it constitutes a graphical way of understanding the influence of agents’ environments on individual behavior. Based on the study of real social networks, sociologists and anthropologists have accumulated extensive evidence that helps explain how human behavior is conditioned by the behavior of other agents. In mathematical terms, a network is a graph, where nodes represent individual agents and arcs or links are interpreted as a “utility good”—for example, information, personal prestige, and so forth—that is exchanged; see Wasserman and Faust (1994). Economic literature has recently introduced tools from game theory into this analytical framework. Rather than being interested only in descriptive aspects, some economic theorists have addressed the study of how networks are formed in the first place, and then their conditions of stability and efficiency; see Jackson and Wolinsky (1996), Bala and Goyal (2000), and Dutta and Jackson (2000). The game-theoretic approach to networks has two main strands: one based on cooperative games and the other on strategies. The analysis based on cooperative games, as is usual in this approach, studies the problem of coalition formation among agents. The demanding assumption of utility transfer among agents is difficult to justify in many cases, in addition to being computationally costly; see Qin (1996), Dutta et al. (1998), and Slikker and van den Nouweland (2001). In turn, the strategic or noncooperative approach only requires the definition of the strategies available to agents, as well as the characterization of the corresponding payoff functions. Given a certain protocol or rule of interaction, agents decide whether or not to connect to the network, evaluating the benefits of connection or disconnection with other agents. The rational decisions of the agents lead to Nash equilibria, which give rise to the networks in this analysis. As mentioned, a network can be viewed as a graph. An important modeling decision is whether the graph is to be directed or undirected. This choice of primitives also has consequences for equilibrium results in noncooperative games of network formation. Undirected graphs are useful for representing situations in which the direction of flows of utility goods is less important or irrelevant; see Dutta and Mutuswami (1997). Directed graphs, on the other hand, reflect the importance of distinguishing which agent initiated the connection as well as the direction taken by the flow of information. A common convention is to draw directed links with arrows pointing toward the agent who decided to initiate the connection; see Bala and Goyal (2000) and Dutta and Jackson (2001). In this paper, networks are designed as graphs with directed flows. We call the utility good that circulates through networks “information,” in a rather generic use of the term. Each agent is assigned some amount of information, but has a payoff function that depends positively on the amount of information to which she has access. By establishing links with others, the agent can acquire information, but she has to share the payment of the cost of information. This is a way of representing the frequent fact that indirectly obtained information nevertheless requires a certain amount of cooperation with the source, in order to provide incentives for the source to continue supplying it. The shared-cost approach applied in this paper assumes that each agent pays a small fee for each link in the path that allows her to reach the desired information. The problem is to determine which structure can emerge as a strategic equilibrium among the agents and whether, in addition, it is optimal. It is shown here that strict Nash equilibria, or Nash equilibria with the minimum number of links, give rise to a circular network, which is stable and optimal. The problem of network formation studied here can be observed in different situations. For instance, consider the following scenario: suppose that Internet users are charged a small amount for each link through which a website is visited. If one of them follows a link, she has to pay for the new connection but obtains access to more information. If she then follows a link on that site, she accesses the new site by again paying the fee, but obtaining access to more information. The question is: what is the most efficient way to navigate through a series of sites under this cost structure? Closer to this framework, one might ask what kind of architecture for a local area network (LAN) increases the speed of flow while reducing losses. This is in fact analogous to our generic problem: a particular computer in the LAN might need to use the resources of another computer in the network. There should be an efficient protocol for choosing which machine to connect to. At the same time, a small “fee” must be paid—for example, in terms of processing time—in order to reach the machine that provides the largest amount of resources. Since this is true for all PCs in the network, the strategic outcome must allow all of them to reach the largest amount of available information while paying as little as possible. As in our result, although for technological reasons, the final outcome could be a circular network, as in the case of IBM’s Token Ring architecture; see Tanenbaum (1989). Such a situation appears in various social organizations, for example in multidisciplinary evaluation committees. These are made up of experts in different fields. Each one must rely on others to obtain information about areas in which she is not an expert. In this case, the circular network minimizes the number of questions while at the same time maximizing the information available to everyone. The remainder of the paper is organized as follows. Section 2 presents the model. Section 3 determines the equilibrium architecture, also showing how the equilibria satisfy certain stability and optimality criteria. Section 4 discusses the analogies and differences with the original work of Bala and Goyal. Finally, Section 5 offers a brief evaluation of the results reported here. The Model Let N=1,…,nN=\1,…,n\ be a set of agents. To avoid trivial results, assume that n≥3n≥ 3. If i and j are two typical members of N, a link between them, without intermediaries, originated in i and ending in j, will be represented as ijij. The interpretation of ijij is that i establishes contact with j, allowing i to access j’s information as well as her network of contacts. Each agent i∈Ni∈ N has some information of her own, Ii∈ℤ+I_i _+, that is, represented as a positive integer. As mentioned, i can access more information by forming links with other agents. Network formation is costly in time, resources, and effort, but for simplicity we shall assume that the link ijij has a cost of 1, measured in units of information utility. By convention, it is assumed that the information of each agent is sufficiently valuable for it to be worthwhile to establish a link with her, that is, Ii>1I_i>1. Agents will try to maximize the utility of the available information while minimizing the cost of connection with other agents. To achieve this, they will choose one strategy from a set of strategies. Each strategy for i∈Ni∈ N is an (n−1)(n-1)-dimensional vector gi=(gi,1,…,gi,i−1,gi,i+1,…,gi,n),g_i=(g_i,1,…,g_i,i-1,g_i,i+1,…,g_i,n), where each gi,jg_i,j, for j≠ij≠ i, takes the value 0 or 1. This is interpreted as follows: i establishes a direct link with j if gi,j=1g_i,j=1, whereas if gi,j=0g_i,j=0 such a link does not exist. The set of all strategies is denoted by GiG_i. The analysis is restricted to pure strategies, which implies that |Gi|=2n−1|G_i|=2^n-1. Finally, G=G1×⋯×GnG=G_1×·s× G_n denotes the set of strategy profiles in the interaction among the agents in N. The existence of a direct link ijij indicates asymmetric communication between i and j. That is, gi,j=1g_i,j=1 indicates that i has established communication with j, which allows i to access j’s information, but not vice versa. Symmetry between i and j is restored if gj,i=1g_j,i=1. Structures with this characteristic are called directed-flow networks. In these networks, the strategy profile can be represented as a directed graph g=(g1,…,gn)g=(g_1,…,g_n) on N. That is, in the directed graph the elements of N are the nodes, while each link established as gi,j=1g_i,j=1 is represented by an arrow beginning at j and directed toward i. This represents the idea that when i establishes a link with j, information flows from j to i. Thus, arrows are always oriented toward the agent who establishes the link. It follows immediately that: Proposition 1. There is a bijective relationship between directed graphs among n nodes and strategy profiles in G. Proof. A directed graph with n nodes is such that, for each node i, there is at most one incoming arrow from each j≠ij≠ i, and none from itself. Therefore, for each j, define gi,jg_i,j equal to 1 if there is an incoming arrow from j, and 0 otherwise. This defines gi=(gi,1,…,gi,i−1,gi,i+1,…,gi,n)g_i=(g_i,1,…,g_i,i-1,g_i,i+1,…,g_i,n) for each i∈Ni∈ N, and a g=(g1,…,gi,…,gn)∈G.g=(g_1,…,g_i,…,g_n)∈ G. Likewise, given a g, a directed graph can be obtained by adding an arrow from j to i if gi,j=1g_i,j=1. Since gi,ig_i,i is not defined, the graph has no self-loops, and since gi,jg_i,j has only two possible values, there is either one link between them or none. □ Example 1. Given a group of four agents, N=a,b,c,d,N=\a,b,c,d\, a joint strategy g=(ga,gb,gc,gd)g=(g_a,g_b,g_c,g_d) can be represented as a strategy profile, as in Table 1. Each row is the strategy chosen by one of the agents. The columns correspond to the agents. An entry 1 in row i and column j means that the strategy of agent i prescribes establishing a link with agent j. Entries on the main diagonal are marked with crosses, since agents cannot establish links with themselves. Figure 1 shows the directed graph corresponding to g. Table 1: Strategy profile Strategy a b c d gag_a X 1 0 0 gbg_b 0 X 1 0 gcg_c 0 0 X 1 gdg_d 0 0 0 X aabbccdd Figure 1: Network formed by the strategy profile Define Ngi=k∈N∣gi,k=1N^g_i=\k∈ N g_i,k=1\ as the set of agents with whom i establishes a direct link according to her strategy profile gig_i. There is a path from j to i according to g∈Gg∈ G if there is a sequence of different agents, to avoid cycles, j0,…,jm,j_0,…,j_m, with i=j0i=j_0 and j=jmj=j_m, such that gj0,j1=⋯=gjm−1,jm=1.g_j_0,j_1=·s=g_j_m-1,j_m=1. Given a joint strategy g, we have j1∈Ngj0,j2∈Ngj1,…,jm∈Ngjm−1.j_1∈ N^g_j_0, j_2∈ N^g_j_1, …, j_m∈ N^g_j_m-1. A path from j=jmj=j_m to i=j0i=j_0, denoted as j→ij→ i, has a length equal to the cardinality of the sequence j1,j2,…,jm−1,jm,j_1,j_2,…,j_m-1,j_m, that is, m, which indicates the number of intermediate links between j and i. Notice that a directed link is a path of length 1. Example 1, reformulated. Given the strategy g=(ga,gb,gc,gd),g=(g_a,g_b,g_c,g_d), with Nga=b,Ngb=c,Ngc=d,N^g_a=\b\, N^g_b=\c\, N^g_c=\d\, while Ngd=∅.N^g_d= . This sequence establishes a path from d to a of length 3. The set of agents accessed, directly or otherwise, by i is denoted as Ni;g=k∈N∣k→i∪i.N^i;g=\k∈ N k→ i\∪\i\. The agent i is included in Ni;gN^i;g to indicate that i knows her own valuation, despite the previously mentioned fact that i does not establish a direct link with herself. Let μi:G→0,…,n(n−1) _i:G→\0,…,n(n-1)\ be the number of links in all the paths that end in i, originated by agents in Ni;gN^i;g under any joint strategy: μi(g)=|(j,k)∈N×N:gj,k=1,and there exists l∈Ni;g with l→i and j,k∈l→i|. _i(g)= | \(j,k)∈ N× N:g_j,k=1,\ and there exists l∈ N^i;g with l→ i and j,k∈ l→ i \ |. Notice that there may be more than one path from j to i. Example 2. Suppose now that N=1,2,3,4,5N=\1,2,3,4,5\ and the strategy g=(g1,g2,g3,g4,g5)g=(g_1,g_2,g_3,g_4,g_5) is given by Table 2. Table 2: Strategy profile Strategy 1 2 3 4 5 g1g_1 X 1 0 0 1 g2g_2 0 X 1 0 0 g3g_3 0 0 X 1 1 g4g_4 0 0 0 X 0 g5g_5 0 0 0 0 X 12345 Figure 2: Network formed by the strategy profile Figure 2 shows the corresponding network. Here N1;g=1,2,3,4,5,N2;g=2,3,4,5,N^1;g=\1,2,3,4,5\, N^2;g=\2,3,4,5\, N3;g=3,4,5,N4;g=4,N5;g=5.N^3;g=\3,4,5\, N^4;g=\4\, N^5;g=\5\. That is, under g, agent 1 accesses the information of all agents, whereas agents 4 and 5 access only their own information. The numbers of links required to obtain the information are μ1(g)=5,μ2(g)=3,μ3(g)=2, _1(g)=5, _2(g)=3, _3(g)=2, while μ4(g)=μ5(g)=0. _4(g)= _5(g)=0. To turn this scheme into a game, the agents’ payoffs are defined. We shall assume that Πi:G→ℝ, _i:G , the payoff function for agent i, is: Πi(g)=∑j∈Ni;gIj−μi(g). _i(g)= _j∈ N^i;gI_j- _i(g). (1) That is, the payoffs of i are the sum of all the information to which she has access, minus the cost of the paths reaching her, established according to g, recalling that each link has unit cost. The intuition here is that i obtains a payoff from accessing more information, but at the same time she must pay a charge or fee for each of the links in the paths to the sources of information. Example 2, first reformulation. Suppose that the information obtained by the agents is: I1=2,I2=2,I3=4,I4=3,I5=3.I_1=2, I_2=2, I_3=4, I_4=3, I_5=3. Then, under the strategy g: Π1(g)=I1+⋯+I5−μ1(g)=2+2+4+3+3−5=9, _1(g)=I_1+·s+I_5- _1(g)=2+2+4+3+3-5=9, Π2(g)=I2+⋯+I5−μ2(g)=2+4+3+3−3=9, _2(g)=I_2+·s+I_5- _2(g)=2+4+3+3-3=9, Π3(g)=I3+⋯+I5−μ3(g)=4+3+3−2=8, _3(g)=I_3+·s+I_5- _3(g)=4+3+3-2=8, Π4(g)=I4−μ4(g)=3−0=3, _4(g)=I_4- _4(g)=3-0=3, Π5(g)=I5−μ5(g)=3−0=3. _5(g)=I_5- _5(g)=3-0=3. We can note that, for example, if g1,5=0g_1,5=0, agent 1 could improve her payoff, obtaining 10 rather than 9, since she would still have access to I5I_5 but using one less link. For each g∈Gg∈ G, agent i obtains a structure Ni;gN^i;g, and her payoff depends critically on the type of graph corresponding to Ni;gN^i;g, as summarized in the following proposition. Proposition 2. Given two joint strategies g and g′g , Πi(g)≥Πi(g′) _i(g)≥ _i(g ) if and only if the corresponding graphs Ni;gN^i;g and Ni;g′N^i;g are such that: ∑j∈Ni;gIj−∑j∈Ni;g′Ij≥μi(g)−μi(g′). _j∈ N^i;gI_j- _j∈ N^i;g I_j≥ _i(g)- _i(g ). Proof. Trivial. □ This result helps to understand the presumption that the objective of a rational agent is to obtain as much information as possible while crossing the smallest possible number of links. There are two cases of particular interest: ∑j∈Ni;gIj=∑j∈Ni;g′Ijandμi(g)≤μi(g′), _j∈ N^i;gI_j= _j∈ N^i;g I_j _i(g)≤ _i(g ), ∑j∈Ni;gIj≥∑j∈Ni;g′Ijandμi(g)=μi(g′). _j∈ N^i;gI_j≥ _j∈ N^i;g I_j _i(g)= _i(g ). The first condition shows that Πi(g)≥Πi(g′) _i(g)≥ _i(g ) if the information obtained through g is the same as that obtained through g′g , but the number of required links is smaller in g than in g′g . The second case shows that Πi(g)≥Πi(g′) _i(g)≥ _i(g ) if the number of links required to reach the information is the same in g as in g′g , but the amount of information obtained in g is greater than that reached in g′g . Equilibrium and Optimality Given a network g∈Gg∈ G, which according to Proposition 1 corresponds to a joint strategy g with its corresponding directed graph, let g−ig_-i be the directed graph obtained when all direct links of agent i are removed. Then g can be written as g=(gi,g−i),g=(g_i,g_-i), meaning that g is formed by the union of the links in gig_i and those in g−ig_-i. A strategy gig_i is said to be a best response of agent i to g−ig_-i if Πi(gi,g−i)≥Πi(gi′,g−i) _i(g_i,g_-i)≥ _i(g_i ,g_-i) (2) for every gi′∈Gig_i ∈ G_i. Example 3. Consider again the case N=1,2,3,4,5,N=\1,2,3,4,5\, where I1=2,I2=2,I3=4,I4=3,I5=3.I_1=2, I_2=2, I_3=4, I_4=3, I_5=3. Let g−1g_-1 be described by Table 3. Also see Figure 3 for the situation faced by agent 1. Table 3: Strategy profile Strategy 1 2 3 4 5 g2g_2 0 X 1 0 1 g3g_3 0 0 X 1 0 g4g_4 0 0 0 X 0 g5g_5 0 0 0 0 X 12345 Figure 3: Network formed by the strategy profile Agent 1 has to decide with whom to establish a connection. One possibility is to remain isolated, but that would give her only a payoff of 2. Alternatively, she could connect to as many agents as she wishes. But some connections might be redundant in terms of informational gains. Such redundancy, in turn, would imply a higher cost for the same information. Thus, for example, connecting to 3 and 4 would ensure that agent 1 has access to the information held by them. The number of required links would be 3. The payoff would therefore be 2+4+3−3=6.2+4+3-3=6. She could instead connect only to 3, since she would still receive the information of 3 and 4 but would require only 2 links; that is, her payoff would be 2+4+3−2=7.2+4+3-2=7. It can be deduced that the best response for 1 would be to connect only to the agent with the highest payoff under g−1g_-1. This is agent 2, who has a payoff of 2+4+3+3−3=9.2+4+3+3-3=9. Therefore, 1 will reach the information of 2, 3, 4, and 5, requiring 4 links. Thus, her payoff would be 10. Figure 4 shows the resulting network. 12345 Figure 4: Final network formed by agent 1 The set of best responses to g−ig_-i is BRi(g−i)BR_i(g_-i). A network g=(g1,…,gn)g=(g_1,…,g_n) is said to be a Nash network if, for each i, gi∈BRi(g−i),g_i∈ BR_i(g_-i), that is, if g, as a joint strategy, is a Nash equilibrium. To determine the structure of Nash networks, several definitions are introduced that will make it possible to describe additional properties of networks. Given a network g, a set C⊂NC⊂ N is called a component of g if, for every pair of agents i and j in C, with i≠ji≠ j, it holds that j∈Ni;gj∈ N^i;g, and there is no C′C , with C⊂C′C⊂ C , for which this is true. A component C is said to be minimal if C ceases to be a component once gi,j=1g_i,j=1 between two agents i and j in C is interrupted, that is, if gi,j=0g_i,j=0. Example 4. Given N=1,2,3,4,N=\1,2,3,4\, consider the following network, represented in Table 4 and Figure 5. Table 4: Strategy profile Strategy 1 2 3 4 g1g_1 X 1 0 0 g2g_2 0 X 1 0 g3g_3 0 0 X 1 g4g_4 0 1 0 X 1234 Figure 5: Network formed by the strategy profile Clearly, C=2,3,4C=\2,3,4\ is a component, since N2;g=N3;g=N4;g=2,3,4.N^2;g=N^3;g=N^4;g=\2,3,4\. If N=C∪1N=C∪\1\ is considered, N is not a component, since 1 does not belong to N2;gN^2;g, N3;gN^3;g, or N4;gN^4;g. On the other hand, C is minimal, since if any of the links 23, 34, or 42 is interrupted, one of the agents ceases to be reachable for at least one agent in C. Thus, for example, if 23 is cut, in the new network g′g , N2;g′=2.N^2;g =\2\. A network is said to be connected if it has a single component. If that single component is minimal, g is said to be minimally connected. A network that is not connected is said to be disconnected. A particular instance of minimally connected networks is the circular network, in which agents can be labeled, by means of a function ℓ:N→N :N→ N, as ℓ(1),…,ℓ(n)\ (1),…, (n)\ and gℓ(1),ℓ(2)=gℓ(2),ℓ(3)=⋯=gℓ(n−1),ℓ(n)=gℓ(n),ℓ(1)=1,g_ (1), (2)=g_ (2), (3)=·s=g_ (n-1), (n)=g_ (n), (1)=1, with no other links. With all these elements, the following result can be established. All results in this section correspond to the game (N,G,Π)(N,G, ), where Π=Π1×⋯×Πn. = _1×·s× _n. Lemma 1. If g∗g^* is a strict Nash network, then it is circular. Proof. Consider Πi:G→ℤ _i:G for each i∈Ni∈ N, and a strict Nash equilibrium g∗∈Gg^*∈ G. Then, for each i and each gi∈Gig_i∈ G_i, Πi(gi∗,g−i∗)>Πi(gi,g−i∗). _i(g_i^*,g_-i^*)> _i(g_i,g_-i^*). (3) Consider the payoff associated with a circular network. If g∗g^* defines such a network, then, by Proposition 2, it must hold for each i that: Πi(g∗)=∑j∈NIj−(n−1). _i(g^*)= _j∈ NI_j-(n-1). (4) In words: the maximum amount of information that can be reached in a circular network is the sum of the information held by all agents, while the number of links that make this information available to any one of them is n−1n-1. Notice that a structure in which there is only one path between any pair of agents has only n links. Suppose, by contradiction, that g∗g^* is not circular. This means that for at least one agent i, Πi(g∗)≠∑j∈NIj−(n−1). _i(g^*)≠ _j∈ NI_j-(n-1). (5) First consider the case in which: Πi(g∗)>∑j∈NIj−(n−1). _i(g^*)> _j∈ NI_j-(n-1). (6) Since ∑j∈NIj _j∈ NI_j cannot be improved, the only possibility is that the number of links is smaller, that is, Πi(g∗)=∑j∈NIj−k, _i(g^*)= _j∈ NI_j-k, where k<n−1k<n-1. But a contradiction appears from the fact that k≥n−1k≥ n-1, since otherwise i would not be able to access at least one agent j and therefore could not obtain the benefit from her information IjI_j. Now consider the case in which: Πi(g∗)<∑j∈NIj−(n−1). _i(g^*)< _j∈ NI_j-(n-1). (7) This can occur if i does not have access to at least one agent, say j, or if the number of links in the paths to the information acquired by i is greater than n−1n-1. Consider the first case, that is, that there exists a j who is not accessed by i. Then i can select a strategy gi∈Gig_i∈ G_i such that gi,j=1g_i,j=1. The number of links then increases by 1, while the accessed information increases by Ij>1I_j>1. Thus, Πi(gi,g−i∗)>Πi(g∗). _i(g_i,g_-i^*)> _i(g^*). This is absurd, since g∗g^* is a strict Nash equilibrium. On the other hand, if the number of links in the path that provides information to i is greater than n−1n-1, i receives the information of at least one agent j, IjI_j, in a redundant way. This implies that there is an agent k, which may be i itself, such that k receives information from j both through a direct link, gk,j=1g_k,j=1, and through a link to another agent, say l. Then k can switch to an alternative strategy g¯k∈Gk g_k∈ G_k, identical to gk∗g_k^* except for g¯k,j=0 g_k,j=0. This implies that the information accessed by k is the same as under g∗g^*, while the number of links is reduced by 1. Hence, Πk(g¯k,g−k∗)>Πk(g∗). _k( g_k,g_-k^*)> _k(g^*). This is absurd, since g∗g^* is a Nash equilibrium. □ Notice that not every Nash network is circular. Example 5. Let N=1,2,3N=\1,2,3\ with Ii=2I_i=2 for i=1,2,3i=1,2,3. Let g∗g^* be represented by Table 5. Table 5: Strategy profile Strategy 1 2 3 g1∗g_1^* X 1 1 g2∗g_2^* 1 X 0 g3∗g_3^* 1 0 X Of course, g∗g^* does not define a circular network; this type is called a star network. To verify that g∗g^* is a weak Nash equilibrium, consider, for example, the best responses of 2 to g−2∗g_-2^*; the analysis for 1 and 3 is analogous. Apart from g2∗g_2^*, there are three other possibilities: g21=(0,X,0),g22=(1,X,1),g23=(0,X,1).g_2^1=(0,X,0), g_2^2=(1,X,1), g_2^3=(0,X,1). Then, while Π2(g∗)=2+2+2−2=4, _2(g^*)=2+2+2-2=4, we have Π2(g21,g−2∗)=2, _2(g_2^1,g_-2^*)=2, Π2(g22,g−2∗)=2+2−1=3, _2(g_2^2,g_-2^*)=2+2-1=3, and Π2(g23,g−2∗)=2+2+2−2=4. _2(g_2^3,g_-2^*)=2+2+2-2=4. This example shows that there are noncircular Nash networks that can yield the same payoff as circular ones. But notice that while individuals obtain the same payoff, the global structure differs. In fact, the following holds. Proposition 3. g∗g^* is a circular network if and only if it is a Nash network with the minimum number of links. Proof. If g∗g^* is a circular network, then for each i the payoff is given by (4). Suppose that it is not a Nash network. That is, for at least one agent i, there exists a deviation gi′∈Gig_i ∈ G_i such that Πi(gi′,g−i∗)>∑j∈NIj−(n−1). _i(g_i ,g_-i^*)> _j∈ NI_j-(n-1). (8) However, the only way to reach this result is by reducing the number of links in the paths that carry information from the other agents to i. Since g∗g^* is circular, there is only one agent j such that gi,j∗=1g_i,j^*=1. There are three possible deviations for gi′g_i . First, for every j≠ij≠ i, let gi,j′=0g_i,j =0. Then i reduces the number of links by n−1n-1 and accesses only her own information, losing the information of all the other n−1n-1 agents. Since ∑j≠iIj>n−1, _j≠ iI_j>n-1, then Πi(gi′,g−i∗)<∑j∈NIj−(n−1). _i(g_i ,g_-i^*)< _j∈ NI_j-(n-1). This is a contradiction. Second, for a given k, let gi,k′=1g_i,k =1 while it is zero for every other agent. Then i cuts the entire path k→ik→ i that passes through j. If the length of this path is m, then m−1m-1 agents are no longer accessed. Since the information lost is greater than the reduction in links, the payoff cannot improve. This again contradicts (8). Third, for more than one k, let gi,k′=1g_i,k =1. Then, even if the number of accessed agents remains the same, the number of links increases. Thus, Πi(gi′,g−i∗)≤Πi(g∗), _i(g_i ,g_-i^*)≤ _i(g^*), which is again a contradiction. Now suppose that g∗g^* is a Nash equilibrium with the minimum number of links. Then it constitutes a single component that includes all agents in N; otherwise, the information of agents who are not accessed would be lost for at least one other agent, while the reduction in link costs would not be sufficient to compensate for that loss. Recall that each IiI_i is greater than the cost of one link. As shown above, the minimum number of links that allows all agents to be connected is n. To show that g∗g^* is circular, suppose that it is not. Then, for every labeling function ℓ:N→N :N→ N, at least one of gℓ(1),ℓ(2),gℓ(2),ℓ(3),…,gℓ(n−1),ℓ(n),gℓ(n),ℓ(1)g_ (1), (2),\,g_ (2), (3),\,…,\,g_ (n-1), (n),\,g_ (n), (1) has value 0, or else there exists another link. The latter possibility must be discarded, since g∗g^* has only n links. Therefore, it must not be possible to connect all agents in N in such a way that each agent is connected with only one agent. But since g∗g^* must include all agents and connect them with n links, it is possible to choose one of the agents in the structure, for example i, and assign to it the label ℓ(i)=1 (i)=1. Agent i is connected to only one agent j, since if i were connected to two different agents, only n−2n-2 links would remain to connect the other n−1n-1 agents. In that case, at least one of the agents would not have a direct link directed toward her and would therefore obtain a payoff lower than the maximum. Accordingly, label the agent connected to i as j, so that ℓ(j)=2 (j)=2. Consider the only agent to whom j is connected, say k. Label k as ℓ(k)=3 (k)=3. Proceed in the same way until the agent accessed by the path of connections, say r, is such that ℓ(r)=n (r)=n. Then, up to that point, n−1n-1 links will have been accessed. It remains to establish to whom r will connect. It cannot be any of the agents denoted as 2,…,n−12,…,n-1, since each of them has only one connection, toward the preceding agent. On the other hand, r cannot connect to herself, since her payoff would be only IrI_r. Therefore, she must connect with i, who has label 1. Hence, there exists a labeling function ℓ such that gℓ(1),ℓ(2)=gℓ(2),ℓ(3)=⋯=gℓ(n−1),ℓ(n)=gℓ(n),ℓ(1)=1.g_ (1), (2)=g_ (2), (3)=·s=g_ (n-1), (n)=g_ (n), (1)=1. This contradicts the assumption that the network is not circular. Therefore, g∗g^* is circular. Finally, it is accepted that many such g∗g^* may exist. The fact is that, since all of them are circular, the only difference among them lies in the names of the agents. Therefore, two different Nash networks on N are isomorphic. That is, if g∗g^* and g∗′g^* are two Nash networks on N, there exists a function f:N→Nf:N→ N such that, for every i and j, gi,j∗=gf(i),f(j)∗′.g_i,j^*=g_f(i),f(j)^* . □ Proposition 3 clearly indicates the close relationship between the strictness of Nash equilibria and the minimality of the number of links in the resulting structure. That is: Corollary. Given a component g, it is a strict Nash equilibrium if and only if the number of its links is minimal. Proof. Suppose that g is a strict Nash equilibrium, but the number of links is not minimal. Then there must be a redundant link, that is, a link that, if cut, would leave the payoff of at least one agent unchanged. Thus, there exists an agent i and a deviation gi′g_i such that Πi(gi′,g−i)=Πi(g). _i(g_i ,g_-i)= _i(g). This is a contradiction, since we assumed that g is a strict Nash equilibrium. Since g is a component, for every pair of agents i and j, i∈Nj;gandj∈Ni;g.i∈ N^j;g j∈ N^i;g. That is, all agents are connected. As discussed above, the minimum number of links that ensures this is n. The only structure with the property that all agents are connected by n links is the circular network, which, according to Proposition 3, is a strict Nash equilibrium. □ Even if circular networks can be identified with strict Nash equilibria, this does not mean that they are unique within the set of agents in N. However, they are certainly isomorphic, as shown in the following example. Example 6. Let N=1,2,3N=\1,2,3\ with I1=2,I2=3,I3=4.I_1=2, I_2=3, I_3=4. Let g∗g^* be represented by the strategy profile in Table 6. Table 6: Strategy profile Strategy 1 2 3 g1∗g_1^* X 1 0 g2∗g_2^* 0 X 1 g3∗g_3^* 1 0 X Establish that g∗g^* is a Nash equilibrium. Consider the best response of 1 to g−1∗g_-1^*. There are four options: g11=(X,0,0),g12=(X,1,0),g13=(X,0,1),g14=(X,1,1).g_1^1=(X,0,0), g_1^2=(X,1,0), g_1^3=(X,0,1), g_1^4=(X,1,1). It is found that Π1(g11,g−1∗)=I1=2, _1(g_1^1,g_-1^*)=I_1=2, Π1(g12,g−1∗)=I1+I2+I3−2=2+3+4−2=7, _1(g_1^2,g_-1^*)=I_1+I_2+I_3-2=2+3+4-2=7, Π1(g13,g−1∗)=I1+I3−2=2+4−2=4, _1(g_1^3,g_-1^*)=I_1+I_3-2=2+4-2=4, and Π1(g14,g−1∗)=I1+I2+I3−3=2+3+4−3=6. _1(g_1^4,g_-1^*)=I_1+I_2+I_3-3=2+3+4-3=6. It is clear that g12g_1^2 is the best response to g−1∗g_-1^*, and precisely g12=g1∗g_1^2=g_1^*. A similar argument is valid for g2∗g_2^* and g3∗g_3^*. This shows that g∗g^* is a Nash network. On the other hand, consider the following alternative network, g∗g^**, on N, represented in Table 7. Table 7: Strategy profile Strategy 1 2 3 g1∗g_1^** X 0 1 g2∗g_2^** 1 X 0 g3∗g_3^** 0 1 X A quick examination shows that g∗g^** is also a Nash network, which for every agent in N provides the same payoff: Π1(g∗)=Π2(g∗)=Π3(g∗)=I1+I2+I3−2=9−2=7. _1(g^**)= _2(g^**)= _3(g^**)=I_1+I_2+I_3-2=9-2=7. It is easy to establish an isomorphism f:N→Nf:N→ N between g∗g^* and g∗g^**: f(1)=2,f(2)=1,f(3)=3.f(1)=2, f(2)=1, f(3)=3. Then consider Table 8, obtained from the description of g∗g^* by a transposition of the rows and columns according to f. Table 8: Relabeled strategy profile Strategy f(1)f(1) f(2)f(2) f(3)f(3) gf1∗g_f1^** X 0 1 gf2∗g_f2^** 1 X 0 gf3∗g_f3^** 0 1 X Notice that the structure of entries in this table is identical to that corresponding to g∗g^**. This establishes the isomorphism between g∗g^* and g∗g^**. According to Lemma 1 and Proposition 3, a stable result in the strategic interaction of agents configures a circular network. We claim that it is stable because there are no incentives to cut or establish new links. Once the circular network structure has emerged, the new configuration may fail to give the same payoffs to the agents. This argument raises the question of the optimality of the result. That is, is there another configuration that can ensure better payoffs for the agents? Before answering this question negatively, two different notions of optimality must be introduced. One represents the notion of social welfare ensured by the network. Formally, let W:G→ℤW:G be defined as W(g)=∑i=1nΠi(g)W(g)= _i=1^n _i(g) for g∈Gg∈ G. A network is said to be efficient if W(g)≥W(g′)W(g)≥ W(g ) for every g′∈Gg ∈ G. On the other hand, we have the notion of Pareto optimality. A network g is said to be Pareto optimal if there is no other network g′g such that, for every i∈Ni∈ N, Πi(g′)≥Πi(g), _i(g )≥ _i(g), and for at least one i, Πi(g′)>Πi(g). _i(g )> _i(g). It then follows that: Proposition 4. A strict Nash network is both efficient and Pareto optimal. Proof. Recall that a strict Nash network g∗g^* sustains the maximum payoff for each agent: Πi(g∗)=∑j∈NIj−(n−1). _i(g^*)= _j∈ NI_j-(n-1). Therefore, Πi(g′)≤Πi(g∗) _i(g )≤ _i(g^*) for every i∈Ni∈ N and every g′∈Gg ∈ G. Thus, g∗g^* is optimal in the Pareto sense. By the same reasoning, W(g′)=∑i∈NΠi(g′)≤∑i∈NΠi(g∗)=W(g∗)W(g )= _i∈ N _i(g )≤ _i∈ N _i(g^*)=W(g^*) for every g′∈Gg ∈ G. That is, g∗g^* is efficient. □ Comparison with the Bala and Goyal Scheme As mentioned, the proposed model shares several characteristics with that of Bala and Goyal (2000), hereafter BG. But, as we shall see, the intuition is very different in one case and in the other. Moreover, the results that follow, even if there is some similarity among them, are reached on the basis of different concepts. To organize the discussion, we introduce the notion of payoffs used in BG. Consider two definitions already given: Ngi=k∈N∣gi,k=1N^g_i=\k∈ N g_i,k=1\ is the set of agents with whom i establishes a direct link according to her strategy gig_i, while the set of agents accessed, directly or otherwise, by i is Ni;g=k∈N∣k→i∪i.N^i;g=\k∈ N k→ i\∪\i\. On these two sets, BG define two functions: δid=|Ngi| _i^d=|N^g_i| and δi(g)=|Ni;g|, _i(g)=|N^i;g|, which indicate, respectively, the number of agents to whom i has a direct link and the number of agents to whom i is connected, directly or indirectly. In BG’s original presentation, δid _i^d is denoted as μid _i^d, while δi _i is μi _i. Here they have been reformulated to avoid confusion. BG consider the following payoff function: ΠiBG(g)=δi(g)−δid(g)c, _i^BG(g)= _i(g)- _i^d(g)c, (9) where c is the cost of establishing each link. That is, the payoffs of i are the number of agents whose information can be accessed by her, minus the cost of the direct links established according to g. Example 2, second reformulation. Suppose again that the information held by the agents is: I1=2,I2=2,I3=4,I4=3,I5=3.I_1=2, I_2=2, I_3=4, I_4=3, I_5=3. Then, under the strategy g, we have in BG, assuming c=1c=1: Π1BG(g)=δ1(g)−δ1d(g)=5−2=3, _1^BG(g)= _1(g)- _1^d(g)=5-2=3, Π2BG(g)=δ2(g)−δ2d(g)=4−1=3, _2^BG(g)= _2(g)- _2^d(g)=4-1=3, Π3BG(g)=δ3(g)−δ3d(g)=3−2=1, _3^BG(g)= _3(g)- _3^d(g)=3-2=1, Π4BG(g)=δ4(g)−δ4d(g)=1−0=1, _4^BG(g)= _4(g)- _4^d(g)=1-0=1, Π5BG(g)=δ5(g)−δ5d(g)=1−0=1. _5^BG(g)= _5(g)- _5^d(g)=1-0=1. It can be noted here that, for example, if g1,5=0g_1,5=0, agent 1 could improve her benefit, obtaining 10 instead of 9, because she could continue to have access to the information of agent 5 but using one less link. The same remains true in the BG case, which in this particular case would increase her benefit from 3 to 4. However, if, for example, agent 3 does not contact agent 5, agent 1 would improve her payoff under Π1 _1 from 9 to 10, whereas in the case of Π1BG _1^BG her payoff remains equal to 3. Moreover, note that while Π3BG(g)=1=Π4BG(g), _3^BG(g)=1= _4^BG(g), we have Π3(g)=8>3=Π4(g). _3(g)=8>3= _4(g). The differences in the payoffs shown in this example clearly display the different intuitions behind Πi(g) _i(g) and ΠiBG(g) _i^BG(g). While the former depends on the value of the information available to the agents, BG base it on the number of agents accessed. The costs are also different. BG only consider the costs of establishing direct links, whereas in our case the cost of a path is shared by all agents that make it up. To analyze the existence of equilibria, BG generalize ΠiBG _i^BG by means of the function Φ(δi(g),δid(g)), ( _i(g), _i^d(g)), (10) increasing in the first argument and decreasing in the second. With this function, BG prove the following statements: • A Nash network is either empty or minimally connected. Proposition 3.1, p. 1194. • A strict Nash network is either empty or circular. Proposition 3.2, p. 1195. Moreover: 1. If Φ(m+1,m)>Φ(1,0) (m+1,m)> (1,0) for some m∈1,…,n−1,m∈\1,…,n-1\, the unique strict Nash network is the circular network. 2. If Φ(m+1,m)≤Φ(1,0) (m+1,m)≤ (1,0) for all m, and Φ(n,1)>Φ(1,0), (n,1)> (1,0), both the circular network and the empty network are strict Nash networks. 3. If Φ(m+1,m)≤Φ(1,0) (m+1,m)≤ (1,0) for all m, and Φ(n,1)≤Φ(1,0), (n,1)≤ (1,0), the empty network is the unique strict Nash network. This last result can be evaluated when Φ(δi(g),δid(g))=δi(g)−δid(g)c. ( _i(g), _i^d(g))= _i(g)- _i^d(g)c. Thus, case 1 reduces to m+1−mc>1,m+1-mc>1, that is, 1−c>0,1-c>0, or c<1.c<1. Case 2 indicates that while c≥1,c≥ 1, it also holds that n−c>1,n-c>1, that is, c<n−1.c<n-1. Finally, case 3 occurs when c≥n−1.c≥ n-1. Thus, these results indicate that the only strict Nash networks are circular when c<1c<1, whereas empty networks are the only Nash networks when c>n−1c>n-1. For c∈[1,n−1],c∈[1,n-1], both the circular network and the empty network are strict Nash equilibria. To compare the results with those of BG, it is necessary to identify the respective payoff functions, that is: Πi(g)=∑j∈Ni;gIj−μi(g)=δi(g)−δid(g)c=ΠiBG(g). _i(g)= _j∈ N^i;gI_j- _i(g)= _i(g)- _i^d(g)c= _i^BG(g). (11) The simplest way in which this can occur is if Ij=1I_j=1 for each j∈Ni;g,j∈ N^i;g, and μi(g)=δid(g)c. _i(g)= _i^d(g)c. In particular, for circular networks it is the case that, for each i, Ni;g=N,μi(g)=n−1,δid(g)=1.N^i;g=N, _i(g)=n-1, _i^d(g)=1. To keep both payoff functions equal, the cost of each link must be c=n−1.c=n-1. But then, although the payoffs are the same, our approach identifies the circular network as the unique strict Nash network. In BG, by contrast, the unique strict Nash network is the empty network. In other words, the differences between the respective payoff functions lead to differences in equilibria. A Final Discussion This paper has presented a model of network formation in the form of a noncooperative game, where agents decide to whom to link by comparing the net benefits of their actions. Decisions are made simultaneously, and therefore no dynamic scheme is required, as appears in Bala and Goyal (2000). In any case, in a model in which agents are not myopic, that is, as in our scheme, and face higher costs of establishing initial links, dynamic processes that converge to the circular network can also be proposed; see Watts (2000). In this analytical framework, heterogeneity only means that each agent is endowed with some particular information that is valuable to other agents. This assumption leads to an increase in the benefit of entering the network, making participation in the network always more valuable than isolation. On the other hand, costs tend to be higher in our scheme because it is assumed that agents contribute to paying the costs of the links in the paths that carry information to them. An interesting result is that circular networks emerge here as Nash equilibria that sustain structures with a minimum number of links. This supports the intuition that strict Nash networks and the existence of a minimum number of connections are equivalent properties. References Bala, V., and Goyal, S. “A Noncooperative Model of Network Formation.” Econometrica, 68, 2000, p. 1181–1229. https://doi.org/10.1111/1468-0262.00155 Dutta, B., and Jackson, M. “The Stability and Efficiency of Directed Communication Networks.” Review of Economic Design, 5, 2000, p. 251–272. https://doi.org/10.1007/PL00013688 Dutta, B., and Jackson, M. On the Formation of Networks and Groups. In B. Dutta and M. Jackson, eds., Models of Strategic Formation of Networks and Groups. Springer-Verlag, New York, 2001. Dutta, B., van den Nouweland, A., and Tijs, S. “Link Formation in Cooperative Situations.” International Journal of Game Theory, 27, 1998, p. 245–255. https://doi.org/10.1007/s001820050070 Dutta, B., and Mutuswami, S. “Stable Networks.” Journal of Economic Theory, 76, 1997, p. 322–344. DOI: 10.1006/jeth.1997.2306 Jackson, M., and Wolinsky, A. “A Strategic Model of Social and Economic Networks.” Journal of Economic Theory, 71, 1996, p. 44–74. DOI: 10.1006/jeth.1996.0108 Qin, C. Z. “Endogenous Formation of Cooperative Structures.” Journal of Economic Theory, 69, 1996, p. 218–226. DOI: 10.1006/jeth.1996.0047 Slikker, M., and van den Nouweland, A. “A One-Stage Model of Link Formation and Payoff Division.” Games and Economic Behavior, 34, 2001, p. 153–175. DOI: 10.1006/game.1999.0785 Tanenbaum, A. Computer Networks. Prentice Hall, Englewood Cliffs, New Jersey, 1989. Wasserman, S., and Faust, K. Social Network Analysis. Cambridge University Press, New York, 1994. Watts, A. “Non-myopic Formation of Circle Networks.” Economic Letters, 74, 2002, p. 277–282. https://doi.org/10.1016/S0165-1765(01)00540-7