Formation of Circular Directed Networks with Shared Link Costs
Juan M. C. Larrosa, Fernando A. Tohmé · 2026
Read Formation of Circular Directed Networks with Shared Link Costs by Juan M. C. Larrosa, Fernando A. Tohmé (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-28382.txt.
Introduction
Juan M. C. Larrosa and Fernando A. Tohmé model how self-interested agents wire themselves into an information network. Each agent holds some information and chooses whom to contact. A link lets the initiator reach the contact's information and everything beyond it. But every step along the path costs, and path costs are shared.
Larrosa and Tohmé characterize the networks that arise when everyone plays a best response. Their central result says strict Nash equilibria must be circular: agents arrange in a directed ring. Circular networks are exactly the equilibria using the fewest links while still giving everyone access to all information, and they are both Pareto optimal and best for total welfare. Non-circular weak equilibria can exist but waste links. Shared path costs set their model apart from the classic Bala-Goyal framework.
Catalog record
| CREATOR | Juan M. C. Larrosa, Fernando A. Tohmé |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 40 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.28382
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Formation of Circular Directed Networks with Shared Link Costs Juan M. C. Larrosa, Fernando A. Tohmé 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