The Strength of Local Structures in Decentralized Network Formation

Basic Information

• Paper ID: 2510.10997
• Title: The Strength of Local Structures in Decentralized Network Formation
• Author: Jose M. Betancourt (Yale University)
• Classification: econ.TH (Economic Theory)
• Publication Date: October 2025
• Paper Link: https://arxiv.org/abs/2510.10997

Abstract

This paper investigates dynamic network formation games where agents assign arbitrary values to network structures. Any such game can be equivalently represented through agents' valuations of its substructures, linking local valuations to equilibrium behavior. A game is a potential game if and only if all participants in a structure assign it the same value, yielding a closed-form stationary distribution. When valuations are restricted to a finite set of repeated substructures (or motifs), the model exhibits phase transition phenomena: small changes in motif values lead to discontinuous jumps in network density.

Research Background and Motivation

Problem Context

Economic outcomes often depend on who interacts with whom—whether through trade, information exchange, or cooperation. These structures themselves evolve over time, responding to agents' incentives to form or sever connections. Understanding the forces driving these dynamics is central to characterizing any economic system with complex interactions.

Research Challenges

The primary challenge lies in the enormous number of possible structures through which agents might interact. For example, approximately 10^7 possible networks exist for 5 agents, while the number of networks for 20 agents exceeds the number of atoms in the universe.

Limitations of Existing Approaches

Existing network formation models typically face the following issues:

1. Lack of tractable characterizations for general utility functions
2. Difficulty analyzing asymptotic behavior in large networks
3. Absence of microeconomic foundations for exponential random graph models (ERGMs)

Research Motivation

This paper aims to address these issues by:

1. Providing a structural value representation for network formation games
2. Characterizing necessary and sufficient conditions for potential games
3. Analyzing phase transition phenomena in large networks

Core Contributions

1. Structural Value Representation Theorem: Proves that any network formation game has an equivalent structural value representation where agents derive value from the substructures in which they participate
2. Characterization of Potential Games: Establishes necessary and sufficient conditions for a game to be a potential game—all agents participating in a structure must assign it the same value
3. Reversibility of Dynamic Processes: Proves that a dynamic network formation process is reversible if and only if the static game is a potential game, providing explicit expressions for the stationary distribution
4. Motif Models and Phase Transitions: Discovers phase transition phenomena in motif utility models, where continuous changes in motif values lead to discontinuous jumps in network density
5. Application of Graph Limit Theory: Connects the model to Erdős-Rényi random graphs and stochastic block models, providing asymptotic analysis for large networks

Methodology

Task Definition

Studies network formation games with N agents where:

• Agent strategy: choosing a subset of other agents to connect with
• Network: the realization of all agents' strategies
• Utility function: $U_i: J_N \times G_N \to \mathbb{R}$, where $G_N$ is the set of all possible networks

Static Game Analysis

Structural Value Representation

For any utility function $U_i(g)$, there exists a unique structural value $V_i(g')$ such that: $U_i(g) = \sum_{g' \subseteq g} V_i(g')$

where $V_i(g')$ represents agent $i$'s value assessment of structure $g'$.

Potential Game Conditions

Theorem 1 (Conservativity Condition): A network formation game is a potential game if and only if the utility function is conservative, i.e., for all networks $g$ and links $ij, i'j'$:

$[U_i(\tau_{ij}(g)) - U_i(g)] + [U_{i'}(\tau_{i'j'}(\tau_{ij}(g))) - U_{i'}(\tau_{ij}(g))] = [U_{i'}(\tau_{i'j'}(g)) - U_{i'}(g)] + [U_i(\tau_{ij}(\tau_{i'j'}(g))) - U_i(\tau_{i'j'}(g))]$

Theorem 2 (Structural Value Condition): A game is a potential game if and only if for all structures $g'$ and agents $i,j$ participating in that structure: $V_i(g') = V_j(g') = V_0(g')$

Dynamic Network Formation

Stochastic Meeting Model

• Agents meet at Poisson rate $\lambda_{ij}(g)$
• After meeting, decide whether to change connection status according to logistic choice rule: $p_{ij}(g) = F_1\left[\left(\frac{1-\sigma}{\sigma}\right)(U_i(\tau_{ij}(g)) - U_i(g))\right]$

Reversibility and Stationary Distribution

Theorem 3: The dynamic process is reversible if and only if the static game is a potential game. The stationary distribution is then a Gibbs measure: $\pi(g) = \frac{\exp\left[\left(\frac{1-\sigma}{\sigma}\right)\Phi(g)\right]}{\sum_{g' \in G_N} \exp\left[\left(\frac{1-\sigma}{\sigma}\right)\Phi(g')\right]}$

Motif Models and Large Network Analysis

Motif Definition

A motif $m$ is a fixed network structure; agents receive value $a_m/N^{n_m-2}$ each time they participate in that structure, where $n_m$ is the number of nodes in the motif.

Phase Transition Phenomena

Theorem 4: In the large network limit, the model is equivalent to an Erdős-Rényi random graph with parameter $\rho^*$ solving: $\rho^* = \arg\max_{\rho \in [0,1]} \left[\left(\frac{1-\sigma}{\sigma}\right)\sum_{m \in M} \frac{a_m}{h_m}\rho^{e_m} + H(\rho)\right]$

where $H(\rho) = -\rho\log\rho - (1-\rho)\log(1-\rho)$ is the entropy function.

Since $\rho^*$ solves an optimization problem, it may be discontinuous even when the objective function is continuous, thereby generating phase transitions.

Extension to Heterogeneous Agents

Stochastic Block Model

For heterogeneous agents with types $\Theta$, the model converges to a directed stochastic block model where the connection probability between types $\theta$ and $\theta'$ is determined by kernel $\psi^*_{\theta\theta'}$.

Theorem 5: The kernel $\psi^*$ solves: $\max_{\psi \in K_\Theta} \left[\left(\frac{1-\sigma}{\sigma}\right)\sum_{m \in M} a_m b[m,\psi;w] + \sum_{\theta \in \Theta} w_\theta\left[\sum_{\theta' \in \Theta} w_{\theta'}H(\psi_{\theta\theta'}) + \left(\frac{1-\sigma}{\sigma}\right)u_\theta[(w_{\theta'}\psi_{\theta\theta'})_{\theta' \in \Theta}]\right]\right]$

Experimental Setup

Trade Model Example

Consider a simple trade model with $N$ firms:

• Cost of forming trade links: $c > 0$
• Benefit from mutual trade: $v > 0$
• Utility function: $U_i(g) = v\sum_{j \in J_N} \mathbf{1}\{ij \in g, ji \in g\} - c\sum_{j \in J_N} \mathbf{1}\{ij \in g\}$

Spatial Trade Model

Firms distributed on a unit circle with distance $D(\theta, \theta') = \min\{|\theta - \theta'|, 1 - |\theta - \theta'|\}$:

• Cost of establishing trade intent: $\gamma D(\theta_i, \theta_j)$
• Benefit from mutual trade: $v$

Experimental Results

Phase Transitions in Simple Trade Model

• When $v < 2c$: typical density approaches 0 (low-density phase)
• When $v > 2c$: typical density approaches 1 (high-density phase)
• Discontinuous jump occurs at $v = 2c$

Supply Chain Model

For $\ell$-node chain models:

• $\ell = 5$: density changes continuously
• $\ell = 7, 9$: significant discontinuous jumps appear
• Structural complexity is key to generating phase transitions

Spatial Heterogeneity Effects

In the spatial trade model:

• Total network density changes smoothly
• Local density kernels exhibit sharp phase transitions
• High-density trading neighborhoods form with sharp density decline outside

Related Work

Network Formation Models

• Deterministic Models: Jackson and Wolinsky (1996), Bala and Goyal (2000)
• Stochastic Models: Jackson and Watts (2002), Mele (2017, 2022)
• Forward-Looking Agents: Dutta et al. (2005)

Exponential Random Graph Models (ERGMs)

• This paper provides microeconomic foundations for ERGMs
• Extends results from Chandrasekhar and Jackson (2012), Mele (2017)

Graph Limit Theory

• Based on Chatterjee and Varadhan (2011), Chatterjee and Diaconis (2013)
• Applied to phase transition analysis in network formation

Conclusions and Discussion

Main Conclusions

1. Importance of Structural Value: Network formation can be understood through agents' valuations of local structures
2. Necessary and Sufficient Conditions for Potential Games: Consistency in agents' value assessments of structures is key
3. Universality of Phase Transitions: Phase transitions are universal phenomena in models with complex motifs
4. Micro-Macro Linkage: Clear connections exist between individual incentives and macroscopic network properties

Limitations

1. Restriction to Positive-Valued Motifs: Analysis primarily focuses on positive-value motifs ($a_m > 0$ for $e_m > 1$)
2. Myopic Assumption: Agents employ myopic decision-making without considering future payoffs
3. Dense Network Assumption: Analysis concentrates on dense networks; sparse networks require different approaches

Future Directions

1. Forward-Looking Agents: Extension to agents considering future payoffs
2. Non-Potential Games: Study of general games approximating potential games
3. Sparse Networks: Development of analytical frameworks for sparse networks
4. Empirical Applications: Application of theory to real network data

In-Depth Evaluation

Strengths

1. Theoretical Innovation: Provides a novel theoretical framework for network formation games
2. Mathematical Rigor: Complete proofs with solid theoretical foundations
3. Unification: Integrates static games, dynamic processes, and large network analysis
4. Practical Value: Provides microeconomic foundations for ERGMs with important econometric implications

Weaknesses

1. Computational Complexity: Partition functions for large networks remain difficult to compute
2. Insufficient Empirical Validation: Lacks verification with real data
3. Restrictive Assumptions: Some assumptions (e.g., sign restrictions on motif values) are quite stringent

Impact

1. Theoretical Contribution: Provides important theoretical tools for network economics
2. Methodological Value: Successful application of graph limit theory in economics
3. Interdisciplinary Significance: Connects game theory, statistical physics, and graph theory

Applicable Scenarios

1. International Trade Networks: Analysis of trade relationship formation and evolution
2. Financial Networks: Stability analysis of interbank lending networks
3. Social Networks: Mechanisms of social relationship formation
4. Supply Chain Networks: Industrial chain structure analysis

References

1. Jackson, M. O., & Wolinsky, A. (1996). A strategic model of social and economic networks. Journal of Economic Theory, 71(1), 44-74.
2. Mele, A. (2017). A structural model of dense network formation. Econometrica, 85(3), 825-850.
3. Chatterjee, S., & Diaconis, P. (2013). Estimating and understanding exponential random graph models. The Annals of Statistics, 41(5).
4. Chandrasekhar, A. G., & Jackson, M. O. (2012). Tractable and consistent random graph models.

Note: This paper makes important theoretical contributions to network economics, particularly in understanding how local structures influence global network properties. The discovery of phase transition phenomena provides new perspectives for policy intervention, suggesting that small parameter changes may lead to dramatic shifts in network structure.