Jose Betancourt[Email<EMAIL_ADDRESS>
I would like to thank Tomás Rodríguez-Barraquer, Aniko Öry, Kevin Williams, Angelo Mele, Kevin Yin, and Eric Solomon for helpful comments.

Yale University

Tractable Aggregation in Endogenous Network Formation Models

This paper presents new conditions under which the stationary distribution of a stochastic network formation process can be characterized in terms of a generating function. These conditions are given in terms of a transforming function between networks: if the total transformation between two networks is independent of how these networks transform into each other (by adding or deleting links), then the process is reversible and a generating function can be constructed. When the network formation process is given by discrete choices of link formation, this procedure is equivalent to proving that the game with the associated utilities is a potential game. This implies that the potential game characterization is related to reversibility and tractability of network formation processes. I then use the characterized stationary distribution to study long-run properties of simple models of homophilic dynamics and international trade. The effects of adding forward-looking agents and switching costs are also discussed.

JEL Classification: C73, D85, F10

Keywords: Random Networks, Dynamic Models, Graph Limits, Homophily, International Trade.

§ INTRODUCTION

Economic networks play a central role in the dynamics and outcomes associated to various economic phenomena, ranging from the social aspects of individual interactions, such as homophily, employment dynamics and information transfers, to various macroeconomic behaviors such as international trade and credit relations. Understanding how individual interactions couple together to generate aggregate outcomes gives us richer insight both into the micro behaviors and their corresponding macro phenomena.

There has been extensive work on the dynamics of network formation, both on deterministic <cit.> and stochastic settings <cit.>. Previous work has shown that when a potential can be associated to the network formation process, the stationary distribution of the system can be given explicitly in terms of this potential <cit.>. I contribute to this literature by presenting novel conditions, similar to the ones in <cit.>, under which such a potential can be constructed for a wide class of network formation processes. These conditions correspond to the difference in potential between two networks being independent of how these transform into each other. Additionally, I use this framework to generate tractable aggregate models of homophilic dynamics and international trade starting from individual behaviors. As such, this paper contributes to the understanding of the long-run dynamics of a rich set of social structures.

I study a model of stochastic network formation in which individuals randomly evaluate the relationship they have with another individual, deciding whether to sever a link if one is present or to create a link if it is absent. These dynamics can be generated from various network dynamic processes, both at an individual and at a global level. For example, at an individual level, these processes can be obtained from stochastic deviations from deterministic solutions <cit.> or from stochasticity in the utility function itself <cit.>, while global-level dynamics can be generated by a social planner making these decisions. Convergence of the distribution of networks in this setting can be guaranteed under relatively weak conditions. I show that this distribution can be characterized in closed form if the stochastic process satisfies certain conditions, generalizing the results in <cit.>. These results follow from considering the formation process as being generated by Glauber dynamics <cit.> and matching the stationary distribution to the one being sampled in the Glauber process. In these processes, links are directed, but the analyses can be extended to undirected networks. In the undirected case, however, the calculation of the limiting probability distribution proves to be significantly more complex than in the directed case.

Using the characterization of the equilibrium dustribution, I use methods from statistical mechanics <cit.> to generate simple aggregate models of homophily and international trade that arise from stochastic network formation. In these models, I obtain aggregate statistics from the distribution over networks in equilibrium, providing a dynamic networks foundation for relations between macroeconomic outcomes.

The characterization of aggregate models using equilibrium statistics proves useful for structural estimation of the dynamic parameters in network generation. Structural estimation using the equilibrium outcomes of the network using Markov chain Monte Carlo (MCMC) is explored in a general setting in <cit.>. I show that maximum likelihood estimation in this setting is equivalent to matching of moments when the equilibrium statistics can be related to derivatives of the utility functions.

§ GENERAL PROPERTIES OF NETWORK FORMATION PROCESSES

§.§ Preliminaries

The general model consists of a set ${\cal N} = \{1,\ldots,N\}$ of $N$ individuals who can interact with each other on a directed unweighted graph. I will use the notation $ij$ to refer to the tuple $(i,j)$. Since I do not consider self-interactions, the set of possible dyads associated to these individuals is given by ${\cal D}=\{ij \in {\cal N}^2 \, | \, i \ne j\}$. A network $g$ on ${\cal N}$ is defined as a subset of ${\cal D}$, corresponding to the diads for which there is a link. Let ${\cal G} = {\cal P}({\cal D})$, where ${\cal P}$ denotes the power set, be the set of all possible networks on ${\cal N}$.

I will consider dynamics of stochastic network formation given by a Markov chain over the space of networks. I begin by considering discrete time, which will be indexed by $t=0,1,\ldots$, and will later extend the results to continuous time. Define the marginal probability measure at time $t$ as $\pi_t(g) \equiv \mathbb{P}\{G_t=g\}$. Agents undergo a meeting process where, at each point in time, they have the possibility of altering the structure of the network. Agent $i$ will meet with agent $j$ with probability $q_{ij} > 0$, which we will assume to be exogenous and independent of time and the network state. During this meeting, bank $i$ will be able to evaluate whether it will have a link to agent $j$ in the future or not. I assume that any ordered pair of agents has a positive probability of meeting and that only one of these pairs can meet in one period, such that the potential meeting events are mutually exclusive. Additionally, we assume that there is a positive probability of no meetings ocurring. Define the total meeting probability as

\begin{align}
q = \sum_{ij \in {\cal D}} q_{ij}.
\end{align}

My assumptions on the meeting process imply that $q \in (0,1)$. The structure of the meeting process is encoded in the vector ${\bf q} \equiv (q_{ij})_{ij\in{\cal D}}$.

In order to describe the process of link updating, it will be useful to define a set of “switching” functions. Consider the family of functions $(\sigma_{ij})_{ij \in {\cal D}}$, where for every $ij \in {\cal D}$, $\sigma_{ij}:{\cal G}\to{\cal G}$ is defined by

\begin{align}
\sigma_{ij}(g) =
\begin{cases}
g \cup \{ij\} & \textrm{if } ij \not \in g \\
g \backslash \{ij\} & \textrm{if } ij \in g.
\end{cases}
\end{align}

Intuitively, $\sigma_{ij}$ creates the link $ij$ if it is not present in a network and severs it if it is. Note that these functions satisfy the following properties for all $ij, i'j' \in {\cal D}$:

\begin{gather}
\sigma_{ij} \circ \sigma_{i'j'} = \sigma_{i'j'} \circ \sigma_{ij}, \nonumber \\
\sigma_{ij} \circ \sigma_{ij} = \mathbbm{1},
\end{gather}

where $\mathbbm{1}$ is the identity operator in ${\cal G}$. Additionally, we can define the composition of $M$ of these operators for a sequence $i_1 j_1, \ldots, i_M j_M$ of dyads as

\begin{align}
\prod_{m=1}^M \sigma_{i_m j_m} \equiv \sigma_{i_1 j_1} \circ \ldots \circ \sigma_{i_M j_M}.
\end{align}

For a given network state $g$, once a meeting occurs for the dyad $ij$, the state of the associated link will switch with probability $p_{ij}(g)$. The evolution of the probability measure is given by

\begin{align}
\pi_{t+1}(g) = \underbrace{(1-q) \pi_t(g)}_{\textrm{No meetings}} + \sum_{ij \in {\cal G}} q_{ij} (\underbrace{p_{ij}(\sigma_{ij}(g)) \pi_t(\sigma_{ij}(g))}_{\textrm{Link } ij \textrm{ is changed}} + \underbrace{(1-p_{ij}(g)) \pi_t(g)}_{\textrm{Link } ij \textrm{ is not changed}}).
\end{align}

We can re-write this as

\begin{align}
\pi_{t+1}(g) = \pi_t(g) + q \sum_{ij \in {\cal G}} \left( \frac{q_{ij}}{q} \right) (p_{ij}(\sigma_{ij}(g)) \pi_t(\sigma_{ij}(g)) - p_{ij}(g) \pi_t(g)).
\end{align}

Note that we can interpret ${\bf q}/q$ as the vector of meeting probabilities conditional on there being a meeting, and that this corresponds to a probability distribution with full support over ${\cal D}$. Now, we can enumerate the space of networks through a bijection $h: \{1, \ldots, |{\cal G}|\}  \to {\cal G}$ and re-cast this evolution equation to a vector equation. First, define $\boldsymbol{\pi}_t \equiv (\pi_t(h(k))_{k \in \{1, \ldots, |{\cal G}|\}})$. Define the matrix ${\bf A}({\bf q}/q)$ by

\begin{align}
A_{kl}({\bf q}/q) =
\begin{cases}
- \sum_{ij \in {\cal D}} \left( \frac{q_{ij}}{q} \right) p_{ij}(h(k)) & \textrm{if } k = l \\
\left( \frac{q_{ij}}{q} \right) p_{ij}(h(l)) & \textrm{if } h(l) = \sigma_{ij}(h(k))  \\
0 & \textrm{if } h(l) \ne \sigma_{ij}(h(k)) \textrm{ for every } ij \in {\cal D}.
\end{cases}
\end{align}

The probability measure $\boldsymbol{\pi}_t$ evolves as $\boldsymbol{\pi}_{t+1} = {\bf P}({\bf q}/q) \boldsymbol{\pi}_t$, where ${\bf P}({\bf q}/q)$ is the transition matrix of the Markov chain.[Note that this corresponds to $\boldsymbol{\pi}_t$ being a column vector and ${\bf P}({\bf q}/q)$ being column-stochastic. The convention can sometimes be the opposite (row vectors and row-stochastic matrices) in the literature.] This matrix will be given by ${\bf P}({\bf q}/q) = {\bf I} + q {\bf A}({\bf q}/q)$, where ${\bf I}$ is the identity matrix of dimension $|{\cal G}|$.

§.§ Convergence

I begin the analysis of the properties of the model by showing sufficient conditions under which the probability distribution converges point-wise to a stationary distribution.

If $p_{ij}(g) \in (0,1)$ for all $ij \in {\cal D}$ and all $g \in \mathcal{G}$, then there is a unique stationary distribution over the network states. Furthermore, the marginal distributions $\pi_t$ will converge point-wise to the unique stationary distribution. That is, $\pi_t(g) \to \pi(g)$ as $t \to \infty$ for all $g \in \mathcal{G}$.

The conditions for convergence stated in Lemma <ref> are relatively weak, implying that any stochastic network formation process where the switching probabilities are non-degenerate will converge to a stationary measure. It is of general interest to study the properties of the stationary distribution of the process, since it can give insights on the long-term dynamics of the system. However, characterizing this distribution is, in general, a more complicated process than proving convergence. Throughout this section I give sufficient conditions under which the stationary distribution of a network formation process can be characterized in terms of a “generating function”, and will give a way to construct it.

A function $\phi:{\cal G} \times {\cal D} \to \mathbb{R}$ is said to be conservative if for any $g \in {\cal G}$, and any two sequences of dyads $i_1 j_1, \ldots, i_M j_M$ and $i'_1 j'_1, \ldots, i'_{M'} j'_{M'}$ such that

\begin{align}
\left(\prod_{m=1}^M \sigma_{i_mj_m} \right) (g) = \left(\prod_{m=1}^{M'} \sigma_{i'_mj'_m} \right) (g),
\end{align}

the following holds:

\begin{align}
\sum_{m=1}^M \phi_{i_mj_m}\left[ \left( \prod_{n=1}^{m-1} \sigma_{i_n j_n} \right) (g) \right] = \sum_{m=1}^{M'} \phi_{i'_mj'_m}\left[ \left( \prod_{n=1}^{m-1} \sigma_{i'_n j'_n} \right) (g) \right].
\end{align}

We can interpret $\phi_{ij}(g)$ as the contribution to some cumulative “change” quantity corresponding to switching the state of the dyad $ij$ given the network $g$. We can, then, think of the total change associated to a sequence of dyad switchings as the sum of the associated individual sequential changes. The conservative property intuitively states that the total change associated to transforming some network $g$ to another network $g'$ is independent of how this transformation is carried out. This is analogous to a conservative vector field, which satisfies that the integral between two points is path-independent.

It is useful to note that any function $\Psi: {\cal G} \to \mathbb{R}$ induces a conservative function given by $\psi_{ij}(g) \equiv \Psi(\sigma_{ij}(g)) - \Psi(g)$. Lemma <ref> states the inverse relation: that any conservative function $\psi$ induces a function $\Psi$ such that $\psi_{ij}(g) \equiv \Psi(\sigma_{ij}(g)) - \Psi(g)$, and gives a construction for this function. Additionally, it gives sufficient conditions to evaluate conservativeness.

A function $\phi:{\cal G} \times {\cal D} \to \mathbb{R}$ is conservative if and only if it satisfies the following two properties:

* For all $g \in {\cal G}$ and all $ij \in {\cal D}$,

\begin{align}
\phi_{ij}(g) = - \phi_{ij}(\sigma_{ij}(g)).
\end{align}

* For all $g \in {\cal G}$ and all $ij, i'j' \in {\cal D}$,

\begin{align}
\phi_{ij}(g) + \phi_{i'j'}(\sigma_{ij}(g)) = \phi_{i'j'}(g) + \phi_{ij}(\sigma_{i'j'}(g))
\end{align}

Furthermore, if $\phi$ is conservative, then there exists a function $\Phi:{\cal G}\to \mathbb{R}$ such that for every $g \in {\cal G}$ and every $ij \in {\cal D}$, it satisfies

\begin{align}
\Phi(\sigma_{ij}(g))-\Phi(g) = \phi_{ij}(g).
\end{align}

Fixing a value of $\Phi(\varnothing)$, this function is unique and can be constructed as

\begin{align}
\Phi(g) = \Phi(\varnothing) + \sum_{n=1}^{|g|} \phi_{i_n j_n} \left( \bigcup_{m=1}^{n-1} \{i_m j_m\} \right),
\end{align}

where $i_1 j_1, \ldots, i_{|g|} j_{|g|}$ is an arbitrary ordering of the links in $g$.

Illustration of a conservative function

Note: In order for $\phi$ to be conservative, the sum of the values corresponding to the top path must coincide with the sum of values corresponding to the bottom path.

Lemma <ref> gives properties that are sufficient to construct a network-dependent function that summarizes the properties of a function that depends both on dyads and networks. Proposition <ref> states that for a particular construction of $\phi$ from the transition probabilities in a network formation process, such a function characterizes the stationary distribution of the system.

Consider a network formation process parametrized by the non-degenerate probabilities $((p_{ij}(g))_{ij \in {\cal D}})_{g \in {\cal G}}$. Define the function $\phi:{\cal G} \times {\cal D} \to \mathbb{R}$ by

\begin{align}
\phi_{ij}(g) = \log \left( \frac{p_{ij}(g)}{p_{ij}(\sigma_{ij}(g))} \right).
\end{align}

Then the following are equivalent:

* The process has an associated generating function $\Phi(g)$ such that

\begin{align}
\frac{p_{ij}(g)}{p_{ij}(\sigma_{ij}(g))} = \exp(\Phi(\sigma_{ij}(g)) - \Phi(g)).
\end{align}

* $\phi$ is a conservative function.

* The network formation process is reversible.

Additionally, if these conditions are satisfied, then the process converges to the stationary distribution given by

\begin{align} \label{eq:eq_dist}
\pi(g) = \frac{\exp(\Phi(g))}{\sum_{g' \in {\cal G}} \exp(\Phi(g'))},
\end{align}

where $\Phi(g)$ is given by the construction in Lemma <ref> using $\phi$.

The relation between the existence of a generating function and conservativeness is given by Lemma <ref>. We can intuitively understand how reversibility is associated to these properties as follows: the revesibility property implies that, for any $g$ and $ij$, we have

\begin{align}
q_{ij} p_{ij}(g) \pi(g) = q_{ij} p_{ij}(\sigma_{ij}(g)) \pi(\sigma_{ij}(g)).
\end{align}

By taking logs, this yields

\begin{align}
\log(\pi(g)) - \log(\pi(\sigma_{ij}(g))) = - \log\left( \frac{p_{ij}(g)}{p_{ij}(\sigma_{ij}(g))} \right) = - \phi_{ij}(g).
\end{align}

Since $\log(\pi)$ is a network-function, we know that the difference must correspond to a conservative function. As such, it follows naturally that reversibility requires the conservativeness of $\phi$.

Proposition <ref> gives sufficient conditions under which a generating function can be constructed, as well as characterizing the stationary network distribution under these conditions. With this characterization, the long-run behavior of systems associated to the formation process can be studied. This is of particular interest in economic systems, since we can perform comparative statics on the network formation parameters to analyze their effects on long-run outcomes of interest. I will explore how this framework can be applied to study aggregate homophilic behavior and international trade in subsequent sections.

§.§ Continuous time model

I now consider a model of network formation that is analogous to the previous discrete time model. It is comprised of a Poisson arrival process with rates $\lambda_{ij}>0$ for every $ij \in {\cal D}$. This means that the probability of link $ij$ being evaluated between time $t$ and time $t + \Delta t$ is given by $\lambda_{ij} \Delta t + o(\Delta t)$. These arrival rates do not depend on the state of the network. This process has an analogous convergence property to the one discussed previously.

From this process, the probability measure $\pi_t$ follows the master equation

\begin{align}
\dot{\pi}_t(g) = \sum_{ij \in {\cal D}} \lambda_{ij} \left(p_{ij}(\sigma_{ij}(g)) \pi_t(\sigma_{ij}(g)) - p_{ij}(g) \pi_t(g) \right).
\end{align}

Note that by defining the vector of arrival rates $\boldsymbol{\lambda} \equiv (\lambda_{ij})_{ij \in {\cal D}}$ and the total arrival rate $\lambda \equiv \sum_{ij \in {\cal D}} \lambda_{ij}$, we can describe the evolution by

\begin{align}
\dot{\boldsymbol{\pi}}_t = \lambda {\bf A}\left(\frac{\boldsymbol{\lambda}}{\lambda}\right) \boldsymbol{\pi}_t.
\end{align}

The results in Proposition <ref> apply to the continuous time model.

§.§ Ensemble averages

The normalization factor in the equilibrium distribution given in Equation (<ref>) is of great interest in the field of statistical physics <cit.>. It is commonly referred to as the partition function and denoted with $Z$, and is used to analyze the statistical properties of physical systems. I will use similar techniques to the ones used in statistical physics to analyze the stationary properties of network formation processes that satisfy the properties in Proposition <ref>.

Since it is of interest to study the formation of networks on an arbitrary number of individuals, we focus on generating functions that depend on the size of the network and on some set of $n$ parameters $\omega = (\omega_i)_{1 \le i \le n}$ that are independent of $N$. ${\cal G}_N$ and ${\cal D}_N$ correspond to the sets of networks and dyads over $N$ nodes, respectively, and $\boldsymbol{\Omega}$ be the set of possible parameters. Consider a network formation process over $N$ nodes that satisfies the properties stated in Proposition <ref>. If the generating function for a network $g \in {\cal G}_N$ is given by $\Phi_N(g;\omega)$, the partition function of the system is defined as

\begin{align}
Z_N(\omega) = \sum_{g \in {\cal G}_N} \Phi_N(g;\omega).
\end{align}

Denote the associated stationary distribution for the system of size $N$ as $(\pi^N(g;\omega))_{g \in {\cal G}_N}$. I denote the ensemble average of a function $f_N:{\cal G}_N\times \boldsymbol{\Omega} \to \mathbb{R}$ under the stationary distribution as

\begin{align}
\langle f_N(\omega) \rangle &\equiv \sum_{g \in {\cal G}_N} \pi^N(g; \omega) f_N(g, \omega) \nonumber \\
&= \frac{1}{Z_N(\omega)} \sum_{g \in {\cal G}_N} \exp(\Phi_N(g ; \omega)) f_N(g, \omega).
\end{align}

The partition function is particularly useful to find ensemble averages of quantities related to the potential. Specifically, the ensemble average of a derivative of the potential with respect to a parameter can be obtained by

\begin{align}
\left \langle \frac{\partial \Phi_N(\omega)}{\partial \omega_i} \right \rangle = \frac{\partial \log(Z_N(\omega))}{\partial \omega_i}.
\end{align}

In cases where the logarithm of the partition function scales as $N^2$, we can define the “per-link” partition function

\begin{align}
\zeta(\omega) = \lim_{N \to \infty} \frac{\log(Z_N(\omega))}{N^2}.
\end{align}

Additionally, if we have

\begin{align}
\lim_{N \to \infty} \left \langle \frac{1}{N^2} \frac{\partial \Phi_N(\omega)}{\partial \omega_i} \right \rangle = -\frac{\partial \zeta(\omega)}{\partial \omega_i},
\end{align}

for some $\omega_i \in \omega$, with $\frac{\partial \zeta(\omega)}{\partial \omega_i}$ non-zero and finite, then the quantity associated to $\frac{\partial \Phi_N(\cdot;\omega)}{\partial \omega_i}$ will also scale as $N^2$. In particular, if there is an $\omega_i$ such that this quantity corresponds to the number of links in the network, the associated network formation process is said to generate dense networks. That is, the average number of links will converge to a non-zero fraction of the number of possible links. Dense network formation processes have been studied previously in <cit.>. In the following sections, I will study economic applications in which dense network formation processes emerge, and characterize aggregate quantities of interest for each case.

§ MYOPIC LINK FORMATION

Having established the general aspects of the network formation processes studied in this paper, I now focus on how economic incentives are integrated into these formation dynamics. This section studies myopic link formation, where individuals don't take into account the actions of others to make their decisions. Subsequent sections deal with agents that take into account others' actions and their effects on the network formation process.

§.§ Discrete choice in link formation

The network formation dynamics discussed in the previous section can be generated by a variety of microfounded models in which choices related to the network formation process are stochastic. An example of a model that captures this is a discrete choice model of link formation. Consider a case in which agent $i$ has an baseline utility $V_i(g)$ associated to network $g$, and that there are stochastic shocks to utility based on the idiosyncrasies of the meeting process. Conditional on link evaluation, the utility agent $i$ obtains from changing the state of their link to agent $j$ given a network $g$ is given by $u_{ij}^1(g)$, while the utility of not changing the state of the link is $u_{ij}^0(g)$. These utilities are given by

\begin{align} \label{eq:disc_choice}
u_{ij}^0(g) &= V_i(g) + \varepsilon_{ij}^0, \nonumber \\
u_{ij}^1(g) &= V_i(\sigma_{ij}(g)) + \varepsilon_{ij}^1,
\end{align}

where the shocks $\varepsilon_{ij}^k$ are i.i.d. and follow some distribution $F_0$. Let $F_1$ be the distribution followed by $\varepsilon^1_{ij} - \varepsilon^0_{ij}$. Note that this distribution satisfies $F_1(x) = 1-F_1(-x)$ since the shocks follow the same distribution. This implies that the switching probabilities are given by

\begin{align}
p_{ij}(g) &= \mathbb{P}\{V_i(\sigma_{ij}(g))-V_i(g) \ge \varepsilon_{ij}^0 - \varepsilon_{ij}^1 \} \nonumber \\
&= F_1(V_i(\sigma_{ij}(g)) - V_i(g)).
\end{align}

This implies that the associated $\phi$ function from Proposition <ref> is given by

\begin{align} \label{eq:disc_probs}
\phi_{ij}(g) = \log \left( \frac{F_1(V_i(\sigma_{ij}(g)) - V_i(g))}{F_1(V_i(g) - V_i(\sigma_{ij}(g)))} \right).
\end{align}

Note that these values satisfy the following relation:

\begin{align}
\phi_{ij}(g) > 0 \iff V_i(\sigma_{ij}(g)) > V_i(g).
\end{align}

This suggests that the log odds-ratio that characterizes the stationary distribution encodes some information about the incentives agents have to switch the state of a link. This can be studied under the framework of potential games <cit.>, in which information about the incentives to deviate of all the players in a game can be encoded into a single function.

The network formation game is said to be an ordinal potential game if there exists a function $Q:{\cal G} \to \mathbb{R}$ such that, for all $g \in {\cal G}$ and all $ij \in {\cal D}$,

\begin{align}
V_i(g) - V_i(\sigma_{ij}(g)) > 0 \iff Q(g) - Q(\sigma_{ij}(g)) > 0.
\end{align}

Furthermore, the game is called an exact potential game if there exists a function $Q:{\cal G} \to \mathbb{R}$ such that, for all $g \in {\cal G}$ and all $ij \in {\cal D}$,

\begin{align}
Q(g) - Q(\sigma_{ij}(g)) = V_i(g) - V_i(\sigma_{ij}(g)).
\end{align}

In either case, if such a function exists, it is called an associated potential of the game.

The previous analysis of the stationary distribution of the network formation process allows for aggregation of the individual link-formation decisions to obtain the generating function. Proposition <ref> connects this aggregation to the aggregation of the individual incentives when the network is formed via discrete choice, revealing a connection between stationariety and the existence of a potential function.

Let $V: {\cal N} \times {\cal G} \to \mathbb{R}$ be the utility functions agents assign to the networks. Then if the associated discrete-choice network formation process is reversible it implies that the associated game where strategies correspond to link-switching is an ordinal potential game. Under reversibility, the generating function of the network formation process is an associated potential of the game, and it is given by the construction in Lemma <ref> using $\phi$ from Equation (<ref>).

Furthermore, if the utility shocks follow a type 1 extreme value distribution (T1EV), then reversibility implies that the game is an exact potential game. Additionally, the existence of an exact potential implies reversibility. The generating function in this case reduces to

\begin{align}
\Phi(g) = \Phi(\varnothing) + \sum_{m=1}^N (V_{i_m}(g_{m}) - V_{i_m}(g_{m-1})),
\end{align}

where $i_1,\ldots,i_N$ is an arbitrary ordering of ${\cal N}$ and $g_n \equiv g_{n-1} \cup \left( \bigcup_{j \in {\cal N}_i(g)} \{i_n j\} \right)$, with $g_0 \equiv \varnothing$.

With the characterization of the potential/generating function in Proposition <ref>, we can link the individual incentives of players to dynamic observables in the network formation process. Specifically, this characterization will prove useful to calculate long-term averages of aggregate properties of the system.

§.§ Switching costs

The discrete choice framework can be extended to include the case where the switching probabilities depend on the current state. I analyze the case where this dependence is incorporated as an additional cost to changing the state. This can also be interpreted as a bias to staying in the current state. The utilities in this case are given by

\begin{align}
u_{ij}^0(g) &= V_i(g) + s + \varepsilon_{ij}^0, \nonumber \\
u_{ij}^1(g) &= V_i(\sigma_{ij}(g)) + \varepsilon_{ij}^1,
\end{align}

where $s > 0$. Focusing on the scenario where the shocks follow a T1EV distribution, we can study the conditions for conservativeness in detail. Define the function

\begin{align}
\zeta(x;s) \equiv x + \log \left( \frac{1 + e^{x+s}}{e^x + e^{s}} \right).
\end{align}

We can write the $\phi$ function in this case as

\begin{align}
\phi_{ij}(g) = \zeta(V_i(\sigma_{ij}(g)) - V_i(g);s).
\end{align}

Expanding to linear order in $s$, we can analyze the behavior of this function for small $s$.The first term in the expansion is given by

\begin{align}
\zeta(x;s) = x + s \left( \frac{e^x - 1}{e^x + 1} \right) + {\cal O}(s^2).
\end{align}

We can see that even small values of $s$ introduce non-linearities in the function's dependence on $x$. This implies that, even for very small switching costs, it is not sufficient to have conservativeness in the $s=0$ to have it when $s>0$.

§.§ Other models of myopic link formation

§.§.§ Stochastic deviations from optimality

An alternate decision process which results in stochastic network formation is the one studied in <cit.>. In this model, every time a link is evaluated, there is a known optimal decision that is not stochastic. However, with a probability $\epsilon \in (0,1)$, the opposite action is implemented. The information about the optimal decision process can be summarized in a function $s:{\cal D}\times{\cal G} \to \{0,1\}$, where $s_{ij}(g) = 1$ if it is optimal for the dyad $ij$ to be in the network given the current network $g$, and $s_{ij}(g) = 0$ otherwise. Note that this is the case where $s$ corresponds to pure strategies, which I have chosen for simplicity. I focus on the case where $s_{ij}(g) = s_{ij}(\sigma_{ij}(g))$ for all $ij$ and $g$, such that the optimal state of the dyad only depends on the rest of the network.

The switching probabilities in this model are given by

\begin{align}
p_{ij}(g) = (1-\epsilon) \mathbbm{1}\{s_{ij}(g) \ne g_{ij}\} + \epsilon \mathbbm{1}\{s_{ij}(g) = g_{ij}\},
\end{align}

where $g_{ij} = \mathbbm{1}\{ij \in g\}$. This means that the state of the dyad is changed with probability $\epsilon$ if the current state is optimal, and it is changed with probability $1-\epsilon$ if the current state is not optimal. We can define

\begin{align*}
m_{ij}(g) = \mathbbm{1}\{s_{ij}(g) = g_{ij}\},
\end{align*}

such that $m_{ij}(g) = 1$ means that the state of dyad $ij$ matches the optimal decision given $g$. Note that since $s_{ij}(g) = s_{ij}(\sigma_{ij}(g))$, we have that $m_{ij}(g) = 1-m_{ij}(\sigma_{ij}(g))$, and therefore $p_{ij}(g) = 1-p_{ij}(\sigma_{ij}(g))$. This implies that the associated $\phi$ is

\begin{align}
\phi_{ij}(g) = \Lambda(\epsilon) m_{ij}(g) + \Lambda(1-\epsilon) (1-m_{ij}(g)),
\end{align}

\begin{align}
\Lambda(p) = \log\left( \frac{p}{1-p} \right).
\end{align}

Since $\Lambda(1-\epsilon) = - \Lambda(\epsilon)$, we have that

\begin{align}
\phi_{ij}(g) &= \Lambda(\epsilon) [2 m_{ij}(g)-1].
\end{align}

Note that $\epsilon$ only enters $\phi$ in a multiplicative factor that is the same for all $ij \in {\cal D}$ and $g \in {\cal G}$. This means that the conservativeness of $\phi$ will depend only on the structure of $s$.

The conditions for conservativeness in Lemma <ref> are satisfied if and only if, for all $ij,i'j' \in {\cal D}$ and all $g \in {\cal G}$,

\begin{align}
m_{ij}(g) + m_{i'j'}(\sigma_{ij}(g)) = m_{i'j'}(g) + m_{ij}(\sigma_{ij}(g)).
\end{align}

Intuitively, this condition means that, for any two networks that can be transformed into each other by changing the state of two dyads, the number of optimal changes in the transformation is independent of the order in which the states of the dyads are changed. If the conditions for conservativeness are satisfied, the generating function of the system is

\begin{align*}
\Phi(g) = \Lambda(\epsilon) (2n_{\textrm{opt}}(g) - |g|),
\end{align*}

where $n_{\textrm{opt}}(g)$ is the number of optimal optimal dyad changes, starting from the empty network, needed to obtain $g$. This quantity is independent of the order in which the dyads are changed, which is a direct consequence of Proposition <ref>. Since the stationary probability associated to a network is increasing in $\Phi$, we have that networks generated from a greater number of optimal changes will be more likely if $\epsilon < 1/2$, while they will be less likely if $\epsilon > 1/2$. If $\epsilon = 1/2$, every evaluation will yield a completely random outcome, and all networks will be equally likely.

§.§.§ Central planner problem

We can also consider a network generation process in which a central planner can stochastically propose a dyad evaluation and choose whether to change the state of the dyad. The planner has a welfare function $W:{\cal G} \to \mathbb{R}$. If the utility associated to forming or severing a link is independent of the state of the dyad, the utilities in a dyad evaluation are given by

\begin{align*}
u_{ij}^0(g) &= W(g \cup \{ij\}) + \varepsilon^0_{ij}, \\
u_{ij}^1(g) &= W(g \backslash \{ij\}) + \varepsilon^1_{ij},
\end{align*}

such that the shocks follow a T1EV distribution. In this model, the conditions for conservativeness are automatically satisfied, meaning that a generating function can be associated to the process. The associated function, then, is given by

\begin{align*}
\Phi(g) = W(g).
\end{align*}

Since the function $W$ can be arbitrary, this model captures a much richer class of network formation processes than the previous models. This is, however, at the cost of not having heterogeneity in the incentives to form or sever links.

§ FORWARD-LOOKING AGENTS

The previous section analyzed the case of agents that made choices based only on utilities dependent on the state of the network, independent of their beliefs of the future. In this section I extend this framework to allow individuals to consider the future actions of others.

Consider the continuous-time network formation game. I study Markov-Perfect Equilibria (MPE), where the strategies of agents depend only on the state of the network. That is, at time $t$, an individual's strategy is measurable with respect to $G_t$. In this setting, I consider that agents discount the future at a rate $\beta$, and that there are stochastic shocks to their utility due to the idiosyncracies of the meeting process, as in Section <ref>.

Suppose agent $i$ derives a flow utility $v_i(g)$ if the state of the network is $g$. Then the present value associated to being in the network $g$ given a future stochastic network formation process is given by

\begin{align}
V_i(g) = \beta \int_0^\infty e^{-\beta t} \left[ \sum_{g' \in {\cal G}} v_i(g') \mathbb{P}\{G_t = g' \, | \, G_0 = g \} \right] dt,
\end{align}

where the factor $\beta$ is introduced in order to interpret this value function as an average of the flow utilities, as well as allowing the present value to be comparable to the idiosyncratic shocks regardless of the value of $\beta$. Individuals make their link formation/severing decisions based on this present value, where the utilities used when evaluating a link are as given in Equation (<ref>).

For a given network formation process, we can define ${\bf V} \equiv ((V_i(g))_{i \in {\cal N}})_{g \in {\cal G}}$ as the set of present values for all agents in all possible states. In equilibrium, the future probabilities of being in a given state will be a function of ${\bf V}$, since these present values determine the switching probabilities. Specifically, any equilibrium must satisfy

\begin{align}
V_i(g) = \sum_{g' \in {\cal G}} v_i(g') \Tilde{\mathbb{P}}(g',g \,|\, \beta, {\bf V}),
\end{align}

\begin{align}
\Tilde{\mathbb{P}}(g',g \,|\, \beta, {\bf V}) = \beta \int_0^\infty e^{-\beta t} \mathbb{P}\{G_t = g' \, | \, G_0 = g, \beta, {\bf V} \} \, dt.
\end{align}

The inter-dependence of the present values of different individuals makes this problem significantly more complex than in the myopic case. Proposition <ref> outlines some general properties about MPEs in this setting, as well as limiting behavior they must satisfy.

For every $\beta \in (0,1)$ and every set of flow-utilities $v:{\cal N} \times {\cal G} \to \mathbb{R}$, a Markov-Perfect Equilibrium exists. Additionally, let $(\beta_n)_{n \in \mathbb{N}}$ be a sequence of discount factors and let $V^n$ be a Markov-Perfect Equilibrium consistent with $\beta_n$. Then the following hold:

* If $\lim_{n \to \infty} \beta_n = 0$, then for every $i \in {\cal N}$ and all $g \in {\cal G}$,

\begin{align}
\lim_{n \to \infty} V^n_i(g) = \frac{1}{|{\cal G}|} \sum_{g' \in {\cal G}} v_i(g').
\end{align}

* If $\lim_{n \to \infty} \beta_n = \infty$, then for every $i \in {\cal N}$ and all $g \in {\cal G}$,

\begin{align}
\lim_{n \to \infty} V^n_i(g) = v_i(g).
\end{align}

Proposition <ref> implies that, in equilibrium, if individuals are infinitely impatient they are no different than in the myopic case. If they are infinitely patient, then only the long-term behavior of the network formation process is relevant. As such, the initial state of the process does not matter, as is evidenced in the limiting behavior of the value function.

Note that the results from Section <ref> can be applied to an equilibrium if the myopic utilities are replaced by the present values. However, establishing conservativeness is in general not possible if a characterization of the equilibrium valuations is not achievable.

§ APPLICATIONS OF THE FRAMEWORK

§.§ A homophilic process of network formation

Homophily is the tendency of individuals to disproportionately form connections with people similar to themselves. This is a well-documented phenomenon present in various social settings <cit.>. There has been extensive work done on the origins of homophily <cit.>, as well as its effects communication and learning <cit.>. I will apply the previously laid out framework to a simple model that generates homophilic dynamics, allowing for the characterization of the aggregate properties that emerge in large networks.

I will use the model of demand described in Section <ref> as a generator of the dynamics of the model. As a baseline, consider a utility function where the marginal utility of forming a link between individuals depends only on their characteristics, not on the rest of the network. Specifically, suppose that individuals have a baseline utility $v_0$ of forming a friendship link and they experience negative utility proportional to how distant they perceive the potential friend. By denoting the distance agent $i$ perceives agent $j$ as with $D_{ij} > 0$, the utility agent $i$ associates to network $g$ is

\begin{align}
V_i(g) = \sum_{j \in {\cal N}_i(g)} [v_0 - \gamma D_{ij}],
\end{align}

where ${\cal N}_i(g)$ is the set of outgoing neighbors of $i$ in $g$. That is, ${\cal N}_i(g) = \{j \, | \, ij \in g\}$. Let $\overline{D}$ be an upper bound on $D_{ij}$ that is independent of $N$. Note that this model satisfies the conditions for reversibility in Proposition <ref>, since there is no network dependence in the link formation probabilities. This implies that $\phi_{ij}(g) = \phi_{ij}(g')$ for all $ij \in {\cal D}$ and all $g,g' \in {\cal G}$, making it trivially satisfy conservativeness. I will later extend the model to include network dependence in the marginal utility. The associated generating function in this case is given by

\begin{align}
\Phi_N(g;\alpha, \gamma) = \sum_{ij \in g}(v_0 - \gamma D_{ij}).
\end{align}

In this model, the parameters $\gamma$ and $v_0$ have clear interpretations, not only in the individual utility, but in aggregate quantities. We see that, for a given $g$, $\frac{\partial \Phi_N(v_0,\gamma)}{\partial v_0}$ corresponds to the number of links in the network, while $-\frac{\partial \Phi_N(v_0,\gamma)}{\partial \gamma}$ is the sum of the distances corresponding to the links in $g$. These quantities allow us to study aggregate characteristics of the network formation process. For example, for a given non-empty network, the average distance between neighbors is given by

\begin{align}
\left( \frac{\partial \Phi_N(v_0, \gamma)}{\partial v_0} \right)^{-1} \left( \frac{\partial \Phi_N(v_0, \gamma)}{\partial \gamma} \right).
\end{align}

We can study how the behavior of these quantities scales as $N$ increases. In particular, it is useful to study the case where the process yields dense networks. An important concept in this scenario is that of extensive functions.

A function $q(N)$ is said to be extensive if

\begin{align}
\lim_{N \to \infty} \frac{q(N)}{N^2} = K
\end{align}

for some finite non-zero $K$.

Lemma <ref> characterizes the behavior of the average distance in terms of the limiting partition function.

Suppose that $\left \langle \frac{\partial \Phi_N(v_0,\gamma)}{\partial v_0} \right \rangle$ and $\left \langle \frac{\partial \Phi_N(v_0,\gamma)}{\partial \gamma} \right \rangle$ are extensive, and that they converge to $\frac{\partial \zeta(v_0,\gamma)}{\partial v_0}$ and $\frac{\partial \zeta(v_0,\gamma)}{\partial \gamma}$, respectively, when divided by $N^2$. Additionally, suppose that

\begin{align}
\lim_{N \to \infty} \frac{1}{N^2} \left[ \left \langle \left(\frac{\partial \Phi_N(v_0,\gamma)}{\partial v_0} \right)^2 \right \rangle - \left \langle \frac{\partial \Phi_N(v_0,\gamma)}{\partial v_0} \right \rangle^2 \right] = \frac{\partial^2 \zeta(v_0,\gamma)}{\partial v_0^2}, \\
\lim_{N \to \infty} \frac{1}{N^2} \left[ \left \langle \left(\frac{\partial \Phi_N(v_0,\gamma)}{\partial \gamma} \right)^2 \right \rangle - \left \langle \frac{\partial \Phi_N(v_0,\gamma)}{\partial \gamma} \right \rangle^2 \right] = \frac{\partial^2 \zeta(v_0,\gamma)}{\partial \gamma^2},
\end{align}

and that these quantities are finite, and that

\begin{align}
\lim_{N \to \infty} \pi^N(\varnothing) = 0,
\end{align}

converging faster than $1/N^m$ for all $m \in \mathbb{N}$. Then we have that

\begin{align}
\lim_{N \to \infty} \left \langle \left. \left( \frac{\partial \Phi_N(v_0, \gamma)}{\partial v_0} \right)^{-1} \left( \frac{\partial \Phi_N(v_0, \gamma)}{\partial \gamma} \right) \right | G \ne \varnothing \right \rangle = \left( \frac{\partial \zeta(v_0, \gamma)}{\partial v_0} \right)^{-1} \left( \frac{\partial \zeta(v_0, \gamma)}{\partial \gamma} \right),
\end{align}

where $\langle \cdot | G \ne \varnothing \rangle$ denotes the ensemble average conditional on networks having at least one link.

Using the result in Lemma <ref>, we can characterize both the average link density and the average distance between neighbors by analyzing the limiting partition function. Denote the average link density with $\mu$ and the average distance in the network with $\eta$. If the conditions in the lemma are satisfied, we have that

\begin{gather}
\mu(v_0,\gamma) = \frac{\partial \zeta(v_0,\gamma)}{\partial v_0}, \nonumber \\
\eta(v_0,\gamma) = -\left( \frac{\partial \zeta(v_0,\gamma)}{\partial v_0} \right)^{-1} \left( \frac{\partial \zeta(v_0,\gamma)}{\partial \gamma} \right).
\end{gather}

I will use these quantities to compare the behavior of the network formation process when agents have discrete types and when they have continuous types.

§.§.§ Discrete-type model

I first consider consider a model where there are $C$ distinct groups of people. Let $\Theta = \{1, \ldots, C\}$ denote the set of these groups and $({\cal M}_r)_{r \in {\cal C}}$ be a partition of ${\cal N}$, such that $i \in {\cal M}_r$ if and only if individual $i$ is in group $r$, and let $N_r \equiv |{\cal M}_r|$. Additionally, let $\theta_i$ denote the group to which individual $i$ belongs.

Let the distance between two individuals only depend on the group they are in, such that $D_{ij} = \Tilde{D}_{\theta_i,\theta_j}$. Additionally, I consider the case where the fractions of agents in group $r$ converges to $w_r$ as $N \to \infty$. Link formation probabilities here are independent. This corresponds to a stochastic block model with the probability associated to forming a link between individuals in groups $r$ and $s$ being given by a logit probability with argument $v_0 - \gamma \Tilde{D}_{r,s}$. This model will serve as a benchmark to compare to more complex network formation models.

For this case, the generating function of a network $g$ would be given by

\begin{align}
\Phi_N(g; v_0, \gamma) = \sum_{r \in \Theta} \sum_{s \in \Theta} (v_0 - \gamma \Tilde{D}_{r,s}) l_{rs}(g),
\end{align}

where $l_{rs}(g)$ is the number of links individuals of group $r$ have established with individuals of group $s$. The limiting partition function, then, is given by

\begin{align}
\zeta_{\textrm{disc}}(v_0, \gamma) = \sum_{r \in \Theta} \sum_{s \in \Theta} w_r w_s \log \left( 1 + e^{v_0 - \gamma \Tilde{D}_{r,s}} \right).
\end{align}

The partition function in this case has a simple closed form, and the model satisfies the conditions stated in Lemma <ref>. This will allow us to compare the aggregate behavior of this model to the one with continuous types.

§.§.§ Continuous-type model

Now I consider a model where $\Theta$ is continuous, which can correspond to a continuous characteristic such as income, such that $\Theta = \left[\underline{\theta}, \overline{\theta} \right]$, with $\overline{\theta} > \underline{\theta}$. The distance between two agents is now given by some bounded continuous function of their characteristics, such that $D_{ij} = D(\theta_i,\theta_j)$. Suppose agents characteristics are distributed with a density $\rho(\theta)$ in the limit $N \to \infty$, such that

\begin{align}
\lim_{\Delta \theta \to 0} \frac{1}{\Delta \theta} \lim_{N \to \infty} \frac{1}{N} M_N(\theta, \theta+\Delta \theta) = \rho(\theta),
\end{align}

where $M_N(x,y)$ is the number of individuals with types in $[x,y]$ when there are $N$ total individuals. The limiting partition function, then, is given by

\begin{align}
\zeta_{\textrm{cont}}(v_0, \gamma) = \left(\overline{\theta} - \underline{\theta} \right)^2 \int_{\Theta^2} \rho(\theta) \rho(\theta') \log \left( 1 + e^{v_0 - D(\theta, \theta')} \right) \, d \theta \, d \theta'
\end{align}

As an example, we can calculate the partition function for the uniform case. To guarantee symmetry between agents, characteristics will be located on a circle with circumference $L$, such that $\theta_j = jL/(N+1)$.  The distance between agents is

\begin{align*}
D_{ij} = \min \{ |\theta_i-\theta_j|, L - |\theta_i-\theta_j| \}.
\end{align*}

A visualization of this distance is given in Figure <ref>. The partition function in this case is

\begin{align*}
\zeta_{\textrm{cont}}(v_0, \gamma) =
\begin{cases}
\frac{2}{L \gamma} \left[ \textrm{Li}_2(-e^{v_0}) - \textrm{Li}_2(-e^{v_0-L\gamma/2}) \right] & \textrm{if } \gamma > 0 \\
\log(1 + e^{v_0}) & \textrm{if } \gamma = 0,
\end{cases}
\end{align*}

where $\textrm{Li}_2$ is the dilogarithm function.

Distance in the uniform continuous-type model

Note: The illustrated example holds for $N > 10$.

I now compare network link densities and average distances for a discrete-type and a continous-type model where the average distance between agents is the same. Specifically, I consider the case of two groups with $w_1 = w_2 = \frac{1}{2}$ and $\Tilde{D}_{r,s} = \mathbbm{1}\{r=s\}$ for the discrete-type model, and a uniform distribution with $L = 2$ for the continuous-type model. This yields an average distance of $1/2$ when considering all possible agent interactions. I calculate the average link density and distance between neighbors for various parameter values to analyze how individual sensitivities to others' characteristics reflect themselves on average. The results are shown in Figures <ref> and <ref>.

Average link density
[Discrete-type model]
[Continuous-type model]

Average distance between neighbors
[Discrete-type model]
[Continuous-type model]

These results show that the link density behaves similarly for both models when varying the model parameters. However, a significant difference emerges when considering the average distance between neighbors. For a given set of parameters for which $\gamma > 0$, we have that the discrete-type model has a lower distance between neighbors compared to the continuous-type model. This is because in the discrete-type setting, individuals have the choice of associating mostly with people of the same type, whereas in the continuous-type case, even if individuals form links with the people closest to them, they have to interact with people who are increasingly further away if they want to establish more links. This means that the variety in the continuous-type setting leads to more diverse groups of neighbors for individuals.

§.§.§ Group-size preferences

The previously analyzed models included preferences based only on agent types and disregarded the network structure. However, there are non-trivial examples of network formation processes where a generating function (or potential) can be constructed that can be analyzed under the same framework. While there is work considering more complex processes under which a potential can be associated to a network, as in <cit.>, I will analyze processes in which this non-triviality enters through the out-degree of the individuals. This will allow me to both expand the model to allow for a more realistic utility specification, as well as provide a framework to estimate effects of the dynamics of network formation using static network data.

To include some of these network formation preferences in this analysis, I will study the dynamics of a model with the following utility specification for a network over $N$ individuals:

\begin{align}
V_i(g) = \sum_{j \in {\cal N}_i(g)} [v_0 - \gamma D_{ij}] + B_N(|{\cal N}_i(g)|),
\end{align}

where $B_N: \mathbbm{N} \to \mathbbm{R}$ is an arbitrary function that is bounded for any $N$ (although this bound can depend on $N$). Without loss of generality, let us assume that $B_N(0) = 0$, so as to normalize the utility of the empty network to $0$. For any such function, the above utility specification corresponds to a model that satisfies the properties in Proposition <ref>, meaning that a generating function can be associated to it. An example of this type of model is one where there is a decreasing marginal utility in the number of neighbors, which would allow for the model to not generate dense networks, in contrast to the previous specification. This would be a more realistic model for friendship networks, since individuals tend to have a limited number of friends, regardless of how large their pool of potential friends grows.

Using the results in Proposition <ref>, the generating function for the utility specification above is given by

\begin{align}
\Phi_N(g;v_0, \gamma) = \sum_{ij \in g} \left[ v_0 - \gamma D_{ij} \right] + \sum_{i \in {\cal N}} B_N\left( |{\cal N}_i(g)| \right).
\end{align}

In the example with discrete types, both the generating function and the partition function can be simplified. The generating function is

\begin{align}
\Phi_N(g;v_0, \gamma) = \sum_{r \in \Theta} \sum_{i \in {\cal M}_r} \left\{ \sum_{s \in \Theta} [ v_0 - \gamma \tilde{D}_{r,s} ] n_{is}(g) + B_N \left( \sum_{s \in \Theta} n_{is}(g) \right) \right\},
\end{align}

where $n_{is}(g)$ is the number of links individual $i$ has established with individuals of group $s$. The corresponding finite-size partition function is

\begin{align}
Z_N(v_0, \gamma) = \prod_{r \in \Theta} \left[ \left( \sum_{l_{rs}=0}^{N_s-\delta_{rs}} \right)_{s \in \Theta} \left[ \prod_{s \in \Theta} {l_{rs} \choose N_s - \delta_{rs}} \right] \exp\left( \sum_{q \in \Theta} [ v_0 - \gamma \tilde{D}_{r,q} ] l_{rq} + B_N \left( \sum_{q \in \Theta} l_{rq} \right) \right) \right]^{N_r},
\end{align}

where $\delta_{rs}$ is the Kronecker delta, and I have used the following summation convention:

\begin{align}
\left( \sum_{l_{rs}=0}^{N_s-\delta_{rs}} \right)_{s \in \Theta} = \sum_{l_{r1} = 0}^{N_1 - \delta_{r1}} \cdots \sum_{l_{rC}=0}^{N_C - \delta_{rC}}.
\end{align}

While this model has an associated stationary distribution given by Proposition <ref>, it is more difficult to obtain a closed-form solution to the partition function than in the previous examples. However, calculating the partition function corresponds to calculating $N \prod_{r \in \Theta} (N_r+1)$ distinct terms, which is a significant improvement with respect to the original sum, which contained $2^{N(N-1)}$ terms. Given that even this calculation can become intractable for estimation, in the following application I explore a model which allows for a more simple characterization of the partition function and ensemble averages.

§.§ A simple international trade model

I will now consider a model of trade where some characteristics of large-scale trade networks can be inferred from individual preferences to trade. Similar to the model in the previous application, individuals will be classified into $C$ groups. Here, individuals are firms and the groups correspond to countries. The costs of forming links with firms in other countries will now correspond to actual transportation and coordination costs, such that the distance measure in this case corresponds to a more tangible attribute of the interaction.

I will consider the formation of trade routes as a unilateral decision. A richer model is obtained if bilateral decisions are taken into account, but it does not allow for an application of the framework described here. The model is an application of the class of models analyzed in Section <ref>, where the utilities include a convex cost to forming links:

\begin{align}
V_i(g) = \sum_{j \in {\cal N}_i(g)} [v_0 - \gamma D_{ij}] - \frac{c}{N} |{\cal N}_i(g)|^2.
\end{align}

Here, $\gamma$ captures the distance-dependent fixed costs of establishing a given route and $c>0$ indirectly captures the budget constraint of the firm. This cost reflects that a larger a firm's network is, the more costly it is to establish a connection with other firms. This model could potentially be accommodated to allow for benefits of networking, which would decrease the costs of adding routes the bigger a firm's network is.

Given that this model is of the form discussed in Section <ref>, it satisfies the conditions in Proposition <ref>. The associated generating function is given by

\begin{align}
\Phi_N(g ; v_0, \gamma, c) = \sum_{r \in \Theta} \sum_{s \in \Theta} \left[ v_0 - \gamma \Tilde{D}_{r,s} \right] l_{rs}(g) + \frac{c}{N} \sum_{i \in {\cal N}} |{\cal N}_i(g)|^2.
\end{align}

The structure of this generating function results in a partition function whose logarithm scales as $N^2$, meaning that the limiting partition function can be calculated. In particular, the model is a dense network formation process where the network structure does enter the utility of forming new links, in contrast to the simple homophily models discussed previously. Even though the calculation of the partition function cannot be done through direct methods, like in the previous examples, results from large deviations theory like the ones used in <cit.> can be used to obtain the limiting behavior of the stationary distribution. In particular, it is of interest to analyze the limiting behavior of the normalized trade from country $r$ toward country $s$, defined in the finite case as

\begin{align}
T_{rs,N}(g) = \frac{\sum_{ij \in g} \mathbbm{1}\{\theta_i = r\} \mathbbm{1}\{\theta_j = s\}}{N_r (N_s-\delta_{rs})}
\end{align}

Define $H(p) \equiv -p \log(p) - (1-p) \log(1-p)$. The limiting partition function in the trade model, then, is given by

\begin{align}
\zeta_{\mathrm{trade}}(v_0, \gamma, c) = \sum_{r \in \Theta} w_r \max_{{\bf x}_r \in (0,1)^{C}} \left\{ \sum_{s \in \Theta} w_s [ v_{rs} x_{rs} + H(x_{rs})] - c \left( \sum_{s' \in \Theta} w_{s'} x_{rs'} \right)^2 \right\},
\end{align}

\begin{align}
v_{rs} =  v_0 - \gamma \tilde{D}_{r,s}.
\end{align}

Furthermore, the average trade between countries $r$ and $s$ is given by

\begin{align}
T_{rs} \equiv \lim_{N \to \infty} \langle T_{rs,N} \rangle = \left[ 1 + A_r(c) e^{\gamma \tilde{D}_{r,s} - v_0} \right]^{-1},
\end{align}

where $A_r$ is a positive function that is increasing in $c$.

Proposition <ref> provides a non-trivial characterization of the aggregate long-run behavior of the trade model. Having characterized the limiting partition function, additional aggregate statistics such as the average distance between trading firms can be obtained, giving a rich description of the macroeconomic system. Additionally, note that the expression for $T_{rs}$ in Proposition <ref> resembles a gravity equation of trade, showing that such a relation can not only be obtained by complexity in the goods being traded, as in <cit.>, but can arise in a simple one-good economy from the dynamics of how trade routes are established.

§ USES FOR EMPIRICAL ESTIMATION

In the absence of dynamic data, estimations of the determinants of link formation in networks tend to focus on the static characteristics of individuals. While this approach allows researchers to analyze the dependence of network structure on individual characteristics, an inclusion of the dynamics of network formation in the analysis would provide both a cleaner estimation of static effects and reveal the relative importance of dynamic effects.

While there has been previous work in incorporating dynamics of networks into structural estimation, these methods tend to entail a large computational cost as noted in <cit.>. This implies that estimation is limited to networks over groups of size of the order of hundreds of individuals. Given the increasing availability of data on large networks, ranging between tens of thousands and millions of individuals, it is of interest to explore methods that allow for the use of the richness of such large data samples in structural estimation.

My previous analysis provides a closed-form expression for the stationary distribution of a stochastic network formation process. Specifically, for a process of homophilic friendship formation, the structure of the model is sufficiently compact to allow an explicit calculation of the probabilities without having to sum over all networks. If there are $C$ distinct groups, the resulting calculation of the probability of observing a given network scales as $N \prod_{r \in \Theta} N_r$, which is drastically slower than the size of the network space, given that it scales as $2^{N^2}$. Additionally, large deviations arguments such as the one used in Section <ref> allow for an additional reduction in computational costs. While this imposes restrictions on the complexity of the model, it allows for a tractable incorporation of dynamics into the structural estimation of determinants of network formation.

Estimation of parameters in such a model can be done via maximum likelihood. Letting $\omega$ be the parameters of the model, the log-likelihood function $\ell(\omega)$ is given by

\begin{align*}
\ell (\omega) = \Phi_N(g_0;\omega) - \log(Z_N(\omega)).
\end{align*}

Since the likelihood depends only on the generating function and the partition function, the results obtained in the previous sections can be used to calculate the likelihood function. Additionally, note that the form of the likelihood function implies that solving for a local extremum corresponds to a set of moment conditions. Specifically, we have that

\begin{align*}
\frac{\partial \ell(\omega)}{\partial \omega_i} &= \frac{\partial \Phi_N(g_0;\omega)}{\partial \omega_i} - \frac{\partial \log(Z_N(\omega))}{\partial \omega_i} \\
&= \frac{\partial \Phi_N(g_0;\omega)}{\partial \omega_i} - \left \langle \frac{\partial \Phi_N(\omega)}{\partial \omega_i} \right \rangle.
\end{align*}

As such, maximum likelihood estimation is equivalent to a type of method of moments estimation using the expectation of the derivatives of the generating function.

§ CONCLUSION

In this paper I have presented sufficient conditions to get a generating function for an arbitrary network formation process where links are individually evaluated. When these conditions are satisfied, I show how aggregate characteristics of the long-run behavior of the system can be obtained from a partition function associated to the process.

I applied this framework to simple models of homophily and international trade. In the case where networks are dense, I was able to find a close form of aggregate quantities, such as the average distance between neighbors and the density of trade routes between two countries, in terms of the parameters dictating the dynamic network formation process. In particular, in the homophily setting I find that people tend to form links with others if they are in a continuum of types than if they have a discrete set of types. I also find that a gravity-like equation is satisfied by the trade-route density in the international trade model, showing that it can arise even in settings where the economy is relatively simple.

§ PROOFS

§.§ Proof of Lemma <ref>

Since the switching probabilities are non-degenerate, there is always a positive probability to switch the state of a dyad. Given that any network can be reached from any other by switching the states of dyads, this implies that there is a positive probability of reaching any network in a finite set of steps and, therefore, the Markov chain is irreducible. Additionally, since the state space is finite, the chain is positive recurrent. Finally, states have a non-zero probability to transition to themselves, therefore the chain is aperiodic. Therefore, using Corollary 8.3.11 in <cit.>, we conclude that a stationary measure exists, is unique, and satisfies $\lim_{t \to \infty} \pi_t(g) = \pi(g)$ for all $g \in {\cal G}$.

§.§ Proof of Lemma <ref>

First note that one of the implications is easily obtained. If $\phi$ is conservative, the first property can be obtained by comparing the paths $g \to \sigma_{ij}(g) \to g$ and $g \to \sigma_{ij}(g) \to g \to \sigma_{ij}(g) \to g$. This yields

\begin{align}
&\phi_{ij}(g) + \phi_{ij}(\sigma_{ij}(g)) = \phi_{ij}(g) + \phi_{ij}(\sigma_{ij}(g)) + \phi_{ij}(g) + \phi_{ij}(\sigma_{ij}(g)) \nonumber \\
&\implies \quad \phi_{ij}(g) = - \phi_{ij}(\sigma_{ij}(g)).
\end{align}

The second property can be obtained by comparing the paths $g \to \sigma_{ij}(g) \to \sigma_{i'j'}\circ\sigma_{ij}(g)$ and $g \to \sigma_{i'j'}(g) \to \sigma_{ij}\circ\sigma_{i'j'}(g)$. Since $\sigma_{i'j'}\circ\sigma_{ij}(g) = \sigma_{ij}\circ\sigma_{i'j'}(g)$, conservativeness implies that

\begin{align}
\phi_{ij}(g) + \phi_{i'j'}(\sigma_{ij}(g)) = \phi_{i'j'}(g) + \phi_{ij}(\sigma_{i'j'}(g)).
\end{align}

Now I show that if $\phi$ satisfies the properties, then it is conservative. Let $g \in {\cal G}$ and $i_1 j_1, \ldots, i_M j_M$ be an arbitrary sequence of dyads. Define

\begin{align}
g_n \equiv \left( \prod_{m=1}^n \sigma_{i_m j_m} \right) (g).
\end{align}

Additionally, define $g_0 \equiv g$ and $\overline{g} \equiv g_M$. With these definitions, define the sum

\begin{align}
S = \sum_{m=1}^M \phi_{i_mj_m}\left[ \left( \prod_{n=1}^{m-1} \sigma_{i_n j_n} \right) (g) \right] &= \sum_{m=1}^M \phi_{i_m j_m}(g_{m-1}).
\end{align}

We can first prove that this sum is invariant under permutations of the order of the links. This is clearly true for $M=1$, so I will focus on the case $M \ge 2$. For $\tilde{m} < M$, define the modified sequence

\begin{align}
i_m'j_m' =
\begin{cases}
i_m j_m & \textrm{if } m \notin \{\tilde{m}, \tilde{m}+1\}, \\
i_{\tilde{m}+1} i_{\tilde{m}+1} & \textrm{if } m = \tilde{m}, \\
i_{\tilde{m}} i_{\tilde{m}} & \textrm{if } m = \tilde{m} + 1.
\end{cases}
\end{align}

This corresponds to the sequence where links in the positions $\tilde{m}$ and $\tilde{m+1}$ have been switched. Define the networks associated to this sequence of links in an analogous manner to the previous sequence:

\begin{align}
g_n' \equiv \left( \prod_{m=1}^n \sigma_{i_m' j_m'} \right) (g).
\end{align}

Note that, given the definition of the new sequence, we have that $g_n' = g_n$ for $n \le \Tilde{m}-1$. Additionally, we have that the switching operators commute, such that

\begin{align}
g_{\Tilde{m}+1}' &= \sigma_{i_{\Tilde{m}+1}' j_{\Tilde{m}+1}'} \circ \sigma_{i_{\Tilde{m}}' j_{\Tilde{m}}'} (g_{\Tilde{m}-1}') \nonumber \\
&= \sigma_{i_{\Tilde{m}}' j_{\Tilde{m}}'} \circ \sigma_{i_{\Tilde{m}+1}' j_{\Tilde{m}+1}'} (g_{\Tilde{m}-1}') \nonumber \\
&= \sigma_{i_{\Tilde{m}+1} j_{\Tilde{m}+1}} \circ \sigma_{i_{\Tilde{m}} j_{\Tilde{m}}} (g_{\Tilde{m}-1}') \nonumber \\
&= \sigma_{i_{\Tilde{m}+1} j_{\Tilde{m}+1}} \circ \sigma_{i_{\Tilde{m}} j_{\Tilde{m}}} (g_{\Tilde{m}-1}) \nonumber \\
&= g_{\tilde{m}+1}.
\end{align}

Given that the links sequences coincide for $n > \tilde{m}+1$, this implies that we also have $g_{n}' = g_n$ for $n \ge \tilde{m} + 1$. The networks, therefore, satisfy

\begin{align}
g_m' =
\begin{cases}
g_m & \textrm{if } m \ne \Tilde{m}, \\
\sigma_{i_{\tilde{m}+1} j_{\tilde{m}+1}}(g_{\tilde{m}-1}) & \textrm{if } m = \tilde{m}.
\end{cases}
\end{align}

This, then, implies that for $m \notin \{\Tilde{m}, \Tilde{m}+1\}$,

\begin{align}
\phi_{i_m' j_m'}(g_{m-1}') = \phi_{i_m j_m}(g_{m-1}).
\end{align}

This implies that

\begin{align}
&\sum_{m=1}^M \phi_{i_m j_m}(g_{m-1}) - \sum_{m=1}^M \phi_{i_m' j_m'}(g_{m-1}') \nonumber \\
&= \phi_{i_{\Tilde{m}} j_{\Tilde{m}}}(g_{\Tilde{m}-1}) + \phi_{i_{\Tilde{m}+1} j_{\Tilde{m}+1}}(g_{\Tilde{m}}) - \phi_{i_{\Tilde{m}}' j_{\Tilde{m}}'}(g_{\Tilde{m}-1}') - \phi_{i_{\Tilde{m}+1}' j_{\Tilde{m}+1}'}(g_{\Tilde{m}}')
\end{align}

Now, because of the second property, we have that the terms in the sum at positions $\tilde{m}$ and $\tilde{m}+1$ satisfy

\begin{align}
\phi_{i_{\tilde{m}} j_{\tilde{m}}}(g_{\tilde{m}-1}) + \phi_{i_{\tilde{m}+1} j_{\tilde{m}+1}}(g_{\tilde{m}}) &= \phi_{i_{\tilde{m}} j_{\tilde{m}}}(g_{\tilde{m}-1}) + \phi_{i_{\tilde{m}+1} j_{\tilde{m}+1}}(\sigma_{i_{\tilde{m}} j_{\tilde{m}}}(g_{\tilde{m}-1})) \nonumber \\
&= \phi_{i_{\tilde{m}+1} j_{\tilde{m}+1}}(g_{\tilde{m}-1}) + \phi_{i_{\tilde{m}} j_{\tilde{m}}}(\sigma_{i_{\tilde{m}+1} j_{\tilde{m}+1}}(g_{\tilde{m}-1})) \nonumber \\
&= \phi_{i_{\tilde{m}}' j_{\tilde{m}}'}(g_{\tilde{m}-1}) + \phi_{i_{\tilde{m}+1}' j_{\tilde{m}+1}'}(\sigma_{i_{\tilde{m}+1} j_{\tilde{m}+1}}(g_{\tilde{m}-1})) \nonumber \\
&= \phi_{i_{\tilde{m}}' j_{\tilde{m}}'}(g_{\tilde{m}-1}') + \phi_{i_{\tilde{m}+1}' j_{\tilde{m}+1}'}(g_{\Tilde{m}}').
\end{align}

We, therefore, conclude that

\begin{align}
\sum_{m=1}^M \phi_{i_m j_m}(g_{m-1}) = \sum_{m=1}^M \phi_{i_m' j_m'}(g_{m-1}').
\end{align}

This means that we can switch the order of two links in the sequence and the sum does not change. Since any permutation of the links can be achieved via a sequence of switches of adjacent links, this implies that $S$ is invariant under permutations of the sequence of dyads.

We can use the previous result to prove that, if a given link appears in the sequence twice, the sum $S$ remains the same if these two entries in the sequence are removed.  Suppose the first instance of the repeated link occurs at position $\hat{m}_1$ and the second one occurs at $\hat{m}_2$. If $\hat{m}_2 > \hat{m}_1$, we can repeatedly apply the previous result to show that $S$ remains the same if we switch the second instance of the repeated link with the previous link in the sequence until it is at position $\hat{m}_1+1$. Denote the sequence of links where the two instances of the links are adjacent with $\hat{i}_1 \hat{j}_1, \ldots, \hat{i}_M \hat{j}_M$ and denote the corresponding sequence of networks with $\{\hat{g}_m\}_{m=0}^M$. We have that

\begin{align}
S &= \sum_{m=1}^M \phi_{\hat{i}_m \hat{j}_m}(\hat{g}_{m-1}) \nonumber \\
&= \phi_{\hat{i}_{\hat{m}_1} \hat{j}_{\hat{m}_1}}(\hat{g}_{\hat{m}_1-1}) + \phi_{\hat{i}_{\hat{m}_1+1} \hat{j}_{\hat{m}_1 + 1}}(\hat{g}_{{\hat{m}_1}}) +  \sum_{m = 1}^{\hat{m}_1-1} \phi_{\hat{i}_m \hat{j}_m}(\hat{g}_{m-1}) + \sum_{m = \hat{m}_1+2}^{M} \phi_{\hat{i}_m \hat{j}_m}(\hat{g}_{m-1}).
\end{align}

Now, we have that $\hat{i}_{\hat{m}+1} \hat{j}_{\hat{m}+1} = \hat{i}_{\hat{m}} \hat{j}_{\hat{m}}$. Therefore, we have that

\begin{align}
\phi_{\hat{i}_{\hat{m}_1} \hat{j}_{\hat{m}_1}}(\hat{g}_{\hat{m}_1-1}) + \phi_{\hat{i}_{\hat{m}_1+1} \hat{j}_{\hat{m}_1 + 1}}(\hat{g}_{{\hat{m}_1}}) &= \phi_{\hat{i}_{\hat{m}_1} \hat{j}_{\hat{m}_1}}(\hat{g}_{\hat{m}_1-1}) + \phi_{\hat{i}_{\hat{m}_1} \hat{j}_{\hat{m}_1}}(\hat{g}_{{\hat{m}_1}}) \nonumber \\
&= \phi_{\hat{i}_{\hat{m}_1} \hat{j}_{\hat{m}_1}}(\hat{g}_{\hat{m}_1-1}) + \phi_{\hat{i}_{\hat{m}_1} \hat{j}_{\hat{m}_1}}(\sigma_{\hat{i}_{\hat{m}_1} \hat{j}_{\hat{m}_1}} (\hat{g}_{{\hat{m}_1-1}})) \nonumber \\
&= 0,
\end{align}

by the first property in the Lemma. This yields

\begin{align}
S = \sum_{m = 1}^{\hat{m}_1-1} \phi_{\hat{i}_m \hat{j}_m}(\hat{g}_{m-1}) + \sum_{m = \hat{m}_1+2}^{M} \phi_{\hat{i}_m \hat{j}_m}(\hat{g}_{m-1}).
\end{align}

Now, note that

\begin{align}
\hat{g}_{\hat{m}_1+1} &= \sigma_{\hat{i}_{\hat{m}_1+1} \hat{j}_{\hat{m}_1+1}} \circ \sigma_{\hat{i}_{\hat{m}_1} \hat{j}_{\hat{m}_1}}(\hat{g}_{\hat{m}_1-1}) \nonumber \\
&= \sigma_{\hat{i}_{\hat{m}_1} \hat{j}_{\hat{m}_1}} \circ \sigma_{\hat{i}_{\hat{m}_1} \hat{j}_{\hat{m}_1}}(\hat{g}_{\hat{m}_1-1}) \nonumber \\
&= \hat{g}_{\hat{m}_1-1}.
\end{align}

We can define a sequence $\Tilde{i}_1 \Tilde{j}_1, \ldots, \Tilde{i}_{M_2} \Tilde{j}_{M-2}$ of $M-2$ dyads given by

\begin{align}
\Tilde{i}_m \Tilde{j}_m =
\begin{cases}
\hat{i}_m \hat{j}_m & \textrm{if } m \le \hat{m}_1 - 1, \\
\hat{i}_{m+2} \hat{j}_{m+2} & \textrm{if } m \ge \hat{m}_1.
\end{cases}
\end{align}

Defining $\{\Tilde{g}_m\}_{m=0}^{M-2}$ analogously to the previous sequences of networks, we have that

\begin{align}
\Tilde{g}_m =
\begin{cases}
\hat{g}_m& \textrm{if } m \le \hat{m}_1 - 1, \\
\hat{g}_{m+2}& \textrm{if } m \ge \hat{m}_1.
\end{cases}
\end{align}

This implies that $S$ satisfies

\begin{align}
S = \sum_{m=1}^{M-2} \phi_{\Tilde{i}_m \Tilde{j}_m}(\Tilde{g}_{m-1}).
\end{align}

As such, we have that $S$ is invariant under the removal of repeated links.

With the above result we have that sums constructed from a sequence of dyads, like $S$, can be reduced to a sequence that includes the dyads that appear an odd number of times in the sequence, and only includes these dyads once. This is because if a dyad appears an even number of times, it can be removed from the sequence in pairs with the previous scheme, and an odd number of repeated dyads can be reduced to one dyad in the same manner. Let $\Delta(g,\overline{g})$ be the set of dyads by which $g$ and $\overline{g}$ differ. That is,

\begin{align}
\Delta(g,\overline{g}) = (g \backslash \overline{g}) \cup (\overline{g} \backslash g).
\end{align}

Since $S$ can be reduced to a sum constructed from a sequence $\overline{i}_1 \overline{j}_1, \ldots, \overline{i}_{\overline{M}} \overline{j}_{\overline{M}}$ where each dyad appears only once, and that $\overline{g}$ must satisfy

\begin{align}
\overline{g} = \left( \prod_{m=1}^{\overline{M}} \sigma_{\overline{i}_{m} \overline{j}_{m}} \right) (g),
\end{align}

it must be true that the sequence is an ordering of the set $\Delta(g,\overline{g})$. Given that $S$ is invariant under permutations of the sequence of dyads used to construct it, we conclude that any ordering of $\Delta(g,\overline{g})$ yields the same value of the sum. Since any sequence of dyads that transforms $g$ into $\overline{g}$ can be transformed into an ordering of $\Delta(g,\overline{g})$, we conclude that any of these sequences yield the same sum. This implies that $\phi$ is conservative.

To construct the $\Phi$ function, consider a non-empty network $g$ and an ordering $i_1 j_1, \ldots, i_{|g|} j_{|g|}$ of the dyads in $g$. From our previous results, we have that the sum

\begin{align}
\sum_{n=1}^{|g|} \phi_{i_n j_n} \left( \bigcup_{m=1}^{n-1} \{i_m j_m\} \right),
\end{align}

is invariant under permutations of the dyads. This means that the value of the sum depends only on the set of dyads, which is precisely $g$. Therefore, the sum above is only a function of $g$, not of the ordering of the links. To define this function for all networks, we can set an arbitrary value $\Tilde{\Phi}(\varnothing)$ and define the function for the non-empty networks by

\begin{align}
\Tilde{\Phi}(g) = \Tilde{\Phi}(\varnothing) + \sum_{n=1}^{|g|} \phi_{i_n j_n} \left( \bigcup_{m=1}^{n-1} \{i_m j_m\} \right).
\end{align}

We can now evaluate $\Tilde{\Phi}(\sigma_{ij}(g))$ for some $ij \in {\cal D}$. If $ij \notin g$, we can organize the sequence of dyads used to construct $\tilde{\Phi}(\sigma_{ij}(g))$ such that $ij$ is the last one and all the other dyads follow the previous ordering of $g$. We would, therefore, have that

\begin{align}
\tilde{\Phi}(\sigma_{ij}(g)) &= \Tilde{\Phi}(\varnothing) + \sum_{n=1}^{|g|} \phi_{i_n j_n} \left( \bigcup_{m=1}^{n-1} \{i_m j_m\} \right) + \phi_{ij}(g) \nonumber \\
&= \Tilde{\Phi}(g) + \phi_{ij}(g).
\end{align}

For the case $ij \in g$, we can use a new ordering $i_1'j_1', \ldots, i_{|g|}' j_{|g|}'$ such that $i_{|g|}' j_{|g|}' = ij$. We, therefore, have that

\begin{align}
\tilde{\Phi}(g) &= \Tilde{\Phi}(\varnothing) + \sum_{n=1}^{|g|} \phi_{i_n' j_n'} \left( \bigcup_{m=1}^{n-1} \{i_m' j_m'\} \right) \nonumber \\
&= \Tilde{\Phi}(\varnothing) + \sum_{n=1}^{|g|-1} \phi_{i_n' j_n'} \left( \bigcup_{m=1}^{n-1} \{i_m' j_m'\} \right) + \phi_{ij}(\sigma_{ij}(g)).
\end{align}

Note that the dyads in the first sum constitute an ordering of the dyads in $\sigma_{ij}(g)$. Using this and the first property $\phi$ stated in the Lemma, we have that

\begin{align}
\tilde{\Phi}(g) &= \tilde{\Phi}(\sigma_{ij}(g)) + \phi_{ij}(\sigma_{ij}(g)) \nonumber \\
&= \tilde{\Phi}(\sigma_{ij}(g)) - \phi_{ij}(g).
\end{align}

In both of these cases, we have that $\tilde{\Phi}$ satisfies

\begin{align} \label{eq:phi_difference}
\tilde{\Phi}(\sigma_{ij}(g)) - \tilde{\Phi}(g) = \phi_{ij}(g).
\end{align}

To show that this function is unique, consider another function $\hat{\Phi}$ that satisfies

\begin{align}
\hat{\Phi}(\sigma_{ij}(g)) - \hat{\Phi}(g) = \phi_{ij}(g)
\end{align}

for all $g \in {\cal G}$ and $ij \in {\cal D}$
Additionally, suppose $\Tilde{\Phi}(\varnothing) = \hat{\Phi}(\varnothing)$ and there exists a $g_0$ such that $\Tilde{\Phi}(g_0) \ne \hat{\Phi}(g_0)$. We have that, for all $g \in {\cal G}$ and $ij \in {\cal D}$

\begin{align}
\Tilde{\Phi}(g) - \hat{\Phi}(g) &= [\Tilde{\Phi}(g) + \phi_{ij}(g)] - [\hat{\Phi}(g) + \phi_{ij}(g)] \nonumber \\
&= \Tilde{\Phi}(\sigma_{ij}(g)) - \hat{\Phi}(\sigma_{ij}(g)).
\end{align}

Since this procedure can be repeated with any sequence of dyads to reach any network, we conclude that $\Tilde{\Phi}(g) - \hat{\Phi}(g)$ is the same for all networks. Specifically, $\Tilde{\Phi}(g_0) - \hat{\Phi}(g_0) = \Tilde{\Phi}(\varnothing) - \hat{\Phi}(\varnothing) = 0$, which is a contradiction. We, therefore, have that $\Tilde{\Phi}$ is the unique function satisfying Equation (<ref>) for a fixed value $\Tilde{\Phi}(\varnothing)$.

§.§ Proof of Proposition <ref>

I first prove the following 3 implications:

* Existence of $\Phi$ implies conservativeness of $\phi$: We have that the function $\Phi$ satisfies

\begin{align}
\Phi(\sigma_{ij}(g)) - \Phi(g) = \log \left( \frac{p_{ij}(g)}{p_{ij}(\sigma_{ij}(g))} \right) = \phi_{ij}(g).
\end{align}

This implies that, for any $g \in {\cal G}$ and $ij,i'j' \in {\cal D}$,

\begin{align}
\phi_{ij}(g) + \phi_{i'j'}(\sigma_{ij}(g)) &= [\Phi(\sigma_{ij}(g)) - \Phi(g)] + [\Phi(\sigma_{i'j'} \circ \sigma_{ij}(g)) - \Phi(\sigma_{ij}(g))] \nonumber \\
&= \Phi(\sigma_{i'j'} \circ \sigma_{ij}(g)) - \Phi(g) \nonumber \\
&= [\Phi(\sigma_{i'j'}(g)) - \Phi(g)] + [\Phi(\sigma_{i'j'} \circ \sigma_{ij}(g)) - \Phi(\sigma_{i'j'}(g))] \nonumber \\
&= [\Phi(\sigma_{i'j'}(g)) - \Phi(g)] + [\Phi(\sigma_{ij} \circ \sigma_{i'j'}(g)) - \Phi(\sigma_{i'j'}(g))] \nonumber \\
&= \phi_{i'j'}(g) + \phi_{ij}(\sigma_{i'j'}(g)),
\end{align}

where I used the fact that the switching operators commute: $\sigma_{ij} \circ \sigma_{i'j'}(g) = \sigma_{i'j'} \circ \sigma_{ij}(g)$. By Lemma <ref>, this implies that $\phi$ is conservative.

* Conservativeness of $\phi$ implies reversibility of the process: By Lemma <ref>, we have that conservativeness of $\phi$ implies the existence of a function $\Phi$, given by the construction in Lemma <ref>, that satisfies

\begin{align}
\Phi(\sigma_{ij}(g))-\Phi(g) = \phi_{ij}(g) = \log \left( \frac{p_{ij}(g)}{p_{ij}(\sigma_{ij}(g))} \right).
\end{align}

We, therefore, have that

\begin{align}
q_{ij} p_{ij}(g) e^{\Phi(g)} &= q_{ij} p_{ij}(\sigma_{ij}(g)) \left[ \frac{p_{ij}(g)}{p_{ij}(\sigma_{ij}(g))} \right] e^{\Phi(g)} \nonumber \\
&= q_{ij} p_{ij}(\sigma_{ij}(g)) e^{\Phi(\sigma_{ij}(g))-\Phi(g)} e^{\Phi(g)} \nonumber \\
&= q_{ij} p_{ij}(\sigma_{ij}(g)) e^{\Phi(\sigma_{ij}(g))}.
\end{align}

Define the following probability distribution over the space of networks:

\begin{align} \label{eq:stationary_dist}
\Tilde{\pi}(g) = \frac{e^{\Phi(g)}}{\sum_{g' \in {\cal G}} e^{\Phi(g')}}.
\end{align}

Dividing the previous expression by $\sum_{g' \in {\cal G}} e^{\Phi(g')}$, we have that

\begin{align}
q_{ij} p_{ij}(g) \tilde{\pi}(g) &= q_{ij} p_{ij}(\sigma_{ij}(g)) \tilde{\pi}(\sigma_{ij}(g)).
\end{align}

Note that this corresponds to the detailed balance condition for the network formation process, since the only non-zero transition probabilities correspond to pairs of networks that differ by only one link. Satisfying detailed balance implies that $\tilde{\pi}$ is a stationary distribution of the Markov chain. By Lemma <ref>, there is a unique stationary distribution of the process, which means that $\Tilde{\pi}$ is the unique stationary distribution. Since $\Tilde{\pi}$ satisfies the detailed balance condition, we conclude that the process is reversible.

* Reversibility of the process implies existence of $\Phi$: Since the switching probabilities are non-degenerate, by Lemma <ref>, there exists a unique non-degenerate stationary distribution $\pi$ to which the system converges. If the process is reversible, it satisfies the detailed balance condition:

\begin{align}
q_{ij} p_{ij}(g) \pi(g) &= q_{ij} p_{ij}(\sigma_{ij}(g)) \pi(\sigma_{ij}(g)).
\end{align}

Since the stationary distribution has full support, we have that

\begin{align}
\log(\pi(\sigma_{ij}(g))) - \log(\pi(g)) &= \log \left( \frac{p_{ij}(g)}{p_{ij}(\sigma_{ij}(g))} \right) = \phi_{ij}(g).
\end{align}

Since the stationary probabilities are a function of the network only, we have that any function

\begin{align}
\Phi(g) = C + \log(\pi(g)),
\end{align}

for $C \in \mathbb{R}$, will satisfy

\begin{align}
\frac{p_{ij}(g)}{p_{ij}(\sigma_{ij}(g))} = \exp(\Phi(\sigma_{ij}(g)) - \Phi(g)).
\end{align}

Using the proof of the second implication, we have that the function $\Phi$ constructed in Lemma <ref> characterizes the stationary distribution of the chain. Namely, the stationary distribution is given by Equation (<ref>).

§.§ Proof of Proposition <ref>

Suppose the network formation process is reversible. Using Proposition <ref>, we have that there exists a function $\Phi$ such that, for all networks and dyads,

\begin{align}
\log \left( \frac{p_{ij}(g)}{p_{ij}(\sigma_{ij}(g))} \right) = \Phi(\sigma_{ij}(g)) - \Phi(g).
\end{align}

If the probabilities are generated from a discrete choice process, we have that

\begin{align}
\Phi(\sigma_{ij}(g)) - \Phi(g) =\log \left( \frac{F_1(V_i(\sigma_{ij}(g)) - V_i(g))}{F_1(V_i(g) - V_i(\sigma_{ij}(g)))} \right).
\end{align}

Due to the symmetry in the definition of $F_1$, we have that

\begin{align}
F_1(-x) = 1 - F_1(x).
\end{align}

Additionally, since $F_0$ is non-negative, we have that $F_1$ satisfies

\begin{align}
F_1(0) &= \frac{1}{2}, \nonumber \\
F_1(x) &< \frac{1}{2} \quad \textrm{for } x < 0, \nonumber \\
F_1(x) &> \frac{1}{2} \quad \textrm{for } x > 0.
\end{align}

As such, we have that

\begin{align}
\log \left( \frac{F_1(V_i(\sigma_{ij}(g)) - V_i(g))}{F_1(V_i(g) - V_i(\sigma_{ij}(g)))} \right) > 0 \quad \iff \quad V_i(\sigma_{ij}(g)) > V_i(g).
\end{align}

This implies that

\begin{align}
\Phi(\sigma_{ij}(g)) - \Phi(g) > 0 \quad \iff \quad V_i(\sigma_{ij}(g)) > V_i(g).
\end{align}

We, therefore, conclude that $\Phi$ is an ordinal potential of the deterministic game.

If $F_0$ corresponds to a T1EV distribution, we have that,

\begin{align}
\log \left( \frac{F_1(x)}{F_1(-x)} \right) = x.
\end{align}

Therefore, we have that in the case of a reversible process, the following is satisfied for all networks and dyads:

\begin{align}
\Phi(\sigma_{ij}(g)) - \Phi(g) = V_i(\sigma_{ij}(g)) - V_i(g)).
\end{align}

We, therefore, conclude that $\Phi$ is an exact potential of the deterministic game. Conversely, if the deterministic game is an exact potential game, then there exists a function $Q$ such that

\begin{align}
Q(\sigma_{ij}(g)) - Q(g) &= V_i(\sigma_{ij}(g)) - V_i(g)).
\end{align}

Now, we have that

\begin{align}
V_i(\sigma_{ij}(g)) - V_i(g)) &= \log \left( \frac{F_1(V_i(\sigma_{ij}(g)) - V_i(g))}{F_1(V_i(g) - V_i(\sigma_{ij}(g)))} \right) \nonumber \\
&= \log \left( \frac{p_{ij}(g)}{p_{ij}(\sigma_{ij}(g))} \right).
\end{align}

As such, this means that $Q$ satisfies

\begin{align}
\frac{p_{ij}(g)}{p_{ij}(\sigma_{ij}(g))} = \exp(Q(\sigma_{ij}(g)) - Q(g)).
\end{align}

Following Proposition <ref>, this implies that the process is reversible, and that $Q$ is a generating function of the stationary distribution.

In the case where the schocks follow a T1EV distribution and the process is reversible, we have that the generating function can be constructed as

\begin{align}
\Phi(g) = \Phi(\varnothing) + \sum_{n=1}^{|g|} \phi_{i_n j_n} \left( \bigcup_{m=1}^{n-1} \{i_m j_m\} \right),
\end{align}

where $i_1 j_1, \ldots, i_{|g|} j_{|g|}$ is an arbitrary ordering of the dyads in $g$, and $\phi$ is given by

\begin{align}
\phi_{ij}(g) = V_i(\sigma_{ij}(g)) - V_i(g)).
\end{align}

The dyads in $g$ can be ordered such that the dyads originating from any given node are adjacent. Defining $i_1,\ldots,i_N$ as an arbitrary ordering of ${\cal N}$, $g_n \equiv g_{n-1} \cup \left( \bigcup_{j \in {\cal N}_i(g)} \{i_n j\} \right)$, with $g_0 \equiv \varnothing$, as the corresponding networks including the neighbors of each node, and $j^m_1, \ldots, j^m_{|{\cal N}_i(g)|}$ as an arbitrary ordering of the neighbors of $i$, $\Phi(g)$ can be written as

\begin{align}
\Phi(g) = \Phi(\varnothing) + \sum_{m=1}^N \sum_{l=1}^{|{\cal N}_i(g)|} \left[V_{i_m}\left(g_{m-1} \cup \left[ \bigcup_{k=1}^{l} \{i_m j^m_k\} \right]\right) - V_{i_m}\left(g_{m-1} \cup \left[ \bigcup_{k=1}^{l-1} \{i_m j^m_k\} \right]\right) \right].
\end{align}

Note that the inner sum is telescopic, which yields

\begin{align}
\Phi(g) &= \Phi(\varnothing) + \sum_{m=1}^N \left[V_{i_m}\left(g_{m-1} \cup \left[ \bigcup_{k=1}^{|{\cal N}_i(g)|} \{i_m j^m_k\} \right]\right) - V_{i_m}(g_{m-1}) \right] \nonumber \\
&= \Phi(\varnothing) + \sum_{m=1}^N (V_{i_m}(g_{m} ) - V_{i_m}(g_{m-1})).
\end{align}

§.§ Proof of Lemma <ref>

The equivalence of statements 1 and 2 in Proposition <ref> only depend on the set of switching probabilities, which is common to the discrete and continuous-time processes.

The irreducibility and aperiodicity properties of ${\bf P}({\bf q}/q)$ hold for ${\bf A}(\boldsymbol{\lambda}/\lambda)$, and these are sufficient to guarantee convergence of the process <cit.>. Now, note that a stationary distribution under the discrete-time evolution will be a stationary distribution under the continuous-time evolution by taking ${\bf q} = s \boldsymbol{\lambda}/\lambda$ for some $s \in (0,1)$. Note that in this case we have $q = s$ so ${\bf q}/q = \boldsymbol{\lambda}/\lambda$. We have that

\begin{align*}
\boldsymbol{\pi} = {\bf P}({\bf q}/q) \boldsymbol{\pi} &\iff \boldsymbol{\pi} = ({\bf I} + s {\bf A}(\boldsymbol{\lambda}/\lambda))\boldsymbol{\pi} \\
&\iff {\bf A}(\boldsymbol{\lambda}/\lambda)\boldsymbol{\pi} = {\bf 0},
\end{align*}

since $s > 0$. Additionally, we have that $\boldsymbol{\lambda}/\lambda$ constitutes a distribution with full support over ${\cal D}$. As such, the stationary distribution in Proposition <ref> will also be the stationary distribution for the continuous-time process, since it is the same for any distribution ${\bf q}$ with full support over ${\cal D}$.

§.§ Proof of Proposition <ref>

Consider the vector in ${\bf x} \equiv ((x_{i}(g))_{i \in {\cal N}})_{{\cal G}} \in \mathbb{R}^{N \times |{\cal G}|}$. Define the function $T: \mathbb{R}^{N \times |{\cal G}|} \to \mathbb{R}^{N \times |{\cal G}|}$ by

\begin{align}
[T({\bf x})]_i(g) &= \sum_{g' \in {\cal G}} v_i(g') \Tilde{\mathbb{P}}(g',g \,|\, \beta, {\bf x}),
\end{align}

\begin{align}
\Tilde{\mathbb{P}}(g',g \,|\, \beta, {\bf x}) = \beta \int_0^\infty e^{-\beta t} \mathbb{P}\{G_t = g' \, | \, G_0 = g, \beta, {\bf x} \} \, dt,
\end{align}

and $\mathbb{P}\{G_t = g' \, | \, G_0 = g, \beta, {\bf x} \}$ are the probabilities induced by the discrete choice dynamics. Note that these time-weighted probabilities satisfy

\begin{align}
\sum_{g' \in {\cal G}} \Tilde{\mathbb{P}}(g',g \,|\, \beta, {\bf x}) &= \beta \int_0^\infty e^{-\beta t} \left[ \sum_{g' \in {\cal G}} \mathbb{P}\{G_t = g' \, | \, G_0 = g, \beta, {\bf x} \} \right] \, dt \nonumber \\
&= \beta \int_0^\infty e^{-\beta t} \, dt \nonumber \\
&= 1.
\end{align}

As such, we have that $[T({\bf x})]_i(g)$ is a convex combination of the $v_i(g)$ across all networks, regardless of ${\bf x}$. Define

\begin{align}
\underline{v}_i &\equiv \min_{g \in {\cal G}} v_i(g), \nonumber \\
\overline{v}_i &\equiv \max_{g \in {\cal G}} v_i(g).
\end{align}

We, therefore, have that the image of $T$ is ${\cal V} \equiv (\prod_{i \in {\cal N}}[\underline{v}_i, \overline{v}_i])^{|{\cal G}|}$. Restricting $T$ to the domain ${\cal V} \subset \mathbb{R}^{N \times |{\cal G}|}$, we conclude that $T$ maps ${\cal V}$ to itself.

I now prove that $T$ is continuous in ${\bf x}$. We have that the switching probabilities associated to a given ${\bf x}$ are given by

\begin{align}
p_{ij}(g \, | \, {\bf x}) &= F_1(x_i(\sigma_{ij}(g)) - x_i(g)).
\end{align}

Since $F_1$ is differentiable, we have that the switching probabilities are differentiable in ${\bf x}$. The probability distribution on ${\cal G}$ satisfies the master equation

\begin{align}
\dot{\mathbb{P}}\{G_t = g' \, | \, G_0 = g, \beta, {\bf x} \} = \sum_{ij \in {\cal D}} \lambda_{ij} \Bigg[ & p_{ij}(\sigma_{ij}(g') | \, {\bf x}) \mathbb{P}\{G_t = \sigma_{ij}(g') \, | \, G_0 = g, \beta, {\bf x} \} \nonumber \\
& - p_{ij}(g' \, | \, {\bf x}) \mathbb{P}\{G_t = g' \, | \, G_0 = g, \beta, {\bf x} \} \Bigg],
\end{align}

with initial conditions

\begin{align}
\mathbb{P}\{G_0 = g \, | \, G_0 = g, \beta, {\bf x} \} &= \mathbbm{1}\{g'=g\}.
\end{align}

Define the function $S:{\cal G} \times [0,1]^{|{\cal G}|} \times {\cal V} \to \mathbb{R}$ by

\begin{align}
S(g,{\bf y} \, | \, {\bf x}) \equiv \sum_{ij \in {\cal D}} \lambda_{ij} [ p_{ij}(\sigma_{ij}(g) | \, {\bf x}) y(\sigma_{ij}(g))  - p_{ij}(g \, | \, {\bf x}) y(g) ].
\end{align}

Since the switching probabilities are differentiable in ${\bf x}$, we have that $H$ is differentiable in ${\bf x}$. Additionally, since the switching probabilities are bounded, we also have that $H$ is differentiable in ${\bf y}$. We, therefore, have that the function is Lipschitz. Using Theorem 8.3 in <cit.>, we conclude that the solution of the differential equation $\mathbb{P}\{G_t = g \, | \, G_0 = g, \beta, {\bf x} \}$ is continuous in ${\bf x}$. Using continuity of the solution, we have that the integral $\tilde{\mathbb{P}}\{g, g' \, | \, \beta, {\bf x} \}$ is continuous in ${\bf x}$, according to Theorem 5.6 in <cit.>. This implies that $T$ is continuous in ${\bf x}$.

Since $T$ is continuous and maps a convex compact subset of $\mathbb{R}^{N \times |{\cal G}|}$ to itself, by Brouwer's fixed-point theorem, $T$ must have a fixed point. That is, there exists an ${\bf x}^* \in {\cal V}$ such that

\begin{align}
{\bf x}^*_i(g) = \sum_{g' \in {\cal G}} v_i(g') \Tilde{\mathbb{P}}(g',g \,|\, \beta, {\bf x}^*).
\end{align}

As such, a Markov-Perfect Equilibrium exists.

§.§.§ $\beta_n \to \infty$ limit

For the $\beta_n \to \infty$ case, we can bound the values that $[T({\bf x})]_i(g)$ takes for any ${\bf x} \in {\cal V}$, which bounds the values the fixed point can take. Using the triangle inequality, we have that

\begin{align}
|\dot{\mathbb{P}}\{G_t = g' \, | \, G_0 = g, \beta, {\bf x} \}| \le \sum_{ij \in {\cal D}} \lambda_{ij} \Bigg[ & |p_{ij}(\sigma_{ij}(g') | \, {\bf x}) \mathbb{P}\{G_t = \sigma_{ij}(g') \, | \, G_0 = g, \beta, {\bf x} \}| \nonumber \\
& + |p_{ij}(g' \, | \, {\bf x}) \mathbb{P}\{G_t = g' \, | \, G_0 = g, \beta, {\bf x} \}| \Bigg].
\end{align}

Since the probabilities are positive and bounded by $1$, this yields

\begin{align}
|\dot{\mathbb{P}}\{G_t = g' \, | \, G_0 = g, \beta, {\bf x} \}| \le 2 \sum_{ij \in {\cal D}} \lambda_{ij}.
\end{align}

Integrating, this yields the following bound:

\begin{align}
|\mathbb{P}\{G_t = g' \, | \, G_0 = g, \beta, {\bf x} \} - \mathbb{P}\{G_0 = g' \, | \, G_0 = g, \beta, {\bf x} \}| &= \left| \int_{0}^t \mathbb{P}\{G_{t'} = g' \, | \, G_0 = g, \beta, {\bf x} \} \, dt' \right| \nonumber \\
&\le \int_{0}^t \left| \mathbb{P}\{G_{t'} = g' \, | \, G_0 = g, \beta, {\bf x} \}  \right| \, dt' \nonumber \\
&\le 2 \left[ \sum_{ij \in {\cal D}} \lambda_{ij} \right] t.
\end{align}

Additionally, since the probabilities lie in $[0,1]$, we have that

\begin{align}
|\mathbb{P}\{G_t = g' \, | \, G_0 = g, \beta, {\bf x} \} - \mathbb{P}\{G_0 = g' \, | \, G_0 = g, \beta, {\bf x} \}| \le 1.
\end{align}

Together, these imply that

\begin{align}
|\mathbb{P}\{G_t = g' \, | \, G_0 = g, \beta, {\bf x} \} - \mathbb{P}\{G_0 = g' \, | \, G_0 = g, \beta, {\bf x} \}| \le \min \left\{ 2 \left[ \sum_{ij \in {\cal D}} \lambda_{ij} \right] t, 1 \right\}
\end{align}

Now, we have that

\begin{align}
&\Tilde{\mathbb{P}}(g',g \,|\, \beta, {\bf x}) - \mathbb{P}\{G_0 = g' \, | \, G_0 = g, \beta, {\bf x} \} \nonumber \\
&= \Tilde{\mathbb{P}}(g',g \,|\, \beta, {\bf x}) - \beta \int_0^{\infty} e^{-\beta t} \mathbb{P}\{G_0 = g' \, | \, G_0 = g, \beta, {\bf x} \} \, dt \nonumber \\
&= \beta \int_0^{\infty} e^{-\beta t} (\mathbb{P}\{G_t = g' \, | \, G_0 = g, \beta, {\bf x} \} - \mathbb{P}\{G_0 = g' \, | \, G_0 = g, \beta, {\bf x} \}) \, dt
\end{align}

We, therefore, have that

\begin{align}
&|\Tilde{\mathbb{P}}(g',g \,|\, \beta, {\bf x}) - \mathbb{P}\{G_0 = g' \, | \, G_0 = g, \beta, {\bf x} \}| \nonumber \\
&\le \beta \int_0^{\infty} e^{-\beta t} |\mathbb{P}\{G_t = g' \, | \, G_0 = g, \beta, {\bf x} \} - \mathbb{P}\{G_0 = g' \, | \, G_0 = g, \beta, {\bf x} \}| \, dt \nonumber \\
&\le \beta \int_0^{\infty} e^{-\beta t} \min \left\{ 2 \left[ \sum_{ij \in {\cal D}} \lambda_{ij} \right] t, 1 \right\} \, dt.
\end{align}

\begin{align}
\tau \equiv \frac{1}{2} \left[ \sum_{ij \in {\cal D}} \lambda_{ij} \right]^{-1}.
\end{align}

We, then, have that

\begin{align}
&|\Tilde{\mathbb{P}}(g',g \,|\, \beta, {\bf x}) - \mathbb{P}\{G_0 = g' \, | \, G_0 = g, \beta, {\bf x} \}| \nonumber \\
&\le \beta \left( 2 \left[ \sum_{ij \in {\cal D}} \lambda_{ij} \right] \int_0^{\tau} e^{-\beta t} t \, dt + \int_{\tau}^{\infty} e^{-\beta t} \, dt  \right) \nonumber \\
&= \beta \left( 2 \left[ \sum_{ij \in {\cal D}} \lambda_{ij} \right] \left[ \frac{1 - e^{-\beta \tau}(\beta \tau + 1)}{\beta^2} \right] + \frac{e^{-\beta \tau}}{\beta}  \right) \nonumber \\
&= \frac{2}{\beta} \left[ \sum_{ij \in {\cal D}} \lambda_{ij} \right] (1- e^{-\beta \tau}) + e^{-\beta \tau} \left( 1 - 2 \tau \sum_{ij \in {\cal D}} \lambda_{ij} \right) \nonumber \\
&= \frac{2}{\beta} \left[ \sum_{ij \in {\cal D}} \lambda_{ij} \right] (1- e^{-\beta \tau}) \nonumber \\
&\le \frac{2}{\beta} \left[ \sum_{ij \in {\cal D}} \lambda_{ij} \right].
\end{align}

With this result, we obtain the following bound:

\begin{align}
|[T({\bf x})]_i(g) - v_i(g)| &=  \left|\left(\sum_{g' \in {\cal G}} v_i(g') \Tilde{\mathbb{P}}(g',g \,|\, \beta, {\bf x}) \right) - \left( \sum_{g' \in {\cal G}} v_i(g') \mathbbm{1}\{g'=g\} \right) \right| \nonumber \\
&= \left|\left(\sum_{g' \in {\cal G}} v_i(g') \Tilde{\mathbb{P}}(g',g \,|\, \beta, {\bf x}) \right) - \left( \sum_{g' \in {\cal G}} v_i(g') \mathbb{P}\{G_0 = g' \, | \, G_0 = g, \beta, {\bf x} \} \right) \right| \nonumber \\
&= \left|\sum_{g' \in {\cal G}} v_i(g') (\Tilde{\mathbb{P}}(g',g \,|\, \beta, {\bf x}) - \mathbb{P}\{G_0 = g' \, | \, G_0 = g, \beta, {\bf x} \}) \right| \nonumber \\
&\le \sum_{g' \in {\cal G}} |v_i(g')| |\Tilde{\mathbb{P}}(g',g \,|\, \beta, {\bf x}) - \mathbb{P}\{G_0 = g' \, | \, G_0 = g, \beta, {\bf x} \}| \nonumber \\
&\le \frac{2}{\beta} \left[ \sum_{ij \in {\cal D}} \lambda_{ij} \right] \sum_{g' \in {\cal G}} |v_i(g')|.
\end{align}

Since this bound is independent of ${\bf x}$, we have that any fixed point associated to $\beta_n$ must satisfy

\begin{align}
|V^n_i(g) - v_i(g)| \le \frac{2}{\beta_n} \left[ \sum_{ij \in {\cal D}} \lambda_{ij} \right] \sum_{g' \in {\cal G}} |v_i(g')|.
\end{align}

We, therefore, have that if $\beta_n \to \infty$ as $n \to \infty$, any fixed point must satisfy

\begin{align}
\lim_{n \to \infty} |V^n_i(g) - v_i(g)| = 0.
\end{align}

§.§.§ $\beta_n \to 0$ limit

Let $\pi(g \, | \, {\bf x})$ denote the stationary distribution for a given vector ${\bf x}$. Since the Markov chain is positive recurrent, as shown in the proof of Lemma <ref>, we have that every state in the chain (i.e. every network) is recurrent. As such, the expected time in each network is infinite. For sufficiently small $\beta$, the weighted time average converges to an average over the stationary distribution of the chain, regardless of the initial state. That is,

\begin{align}
\lim_{\beta \to 0} [T({\bf x})]_i(g) &= \sum_{g' \in {\cal G}} v_i(g') \pi(g \, | \, {\bf x}).
\end{align}

This average, however, is independent of $g$. In particular, this applies to the fixed points of $T$. We must, therefore, have that any limit of the fixed points associated to a sequence $\{\beta_n\}$, with $\beta_n \to 0$, must satisfy

\begin{align}
\lim_{n \to \infty} V_i^n(g) = \lim_{n \to \infty} V_i^n(g')
\end{align}

for all $i \in {\cal N}$ and $g, g' \in {\cal G}$. If this is satisfied, we must have that all the switching probabilities converge to $1/2$, since

\begin{align}
\lim_{n \to \infty} p_{ij}(g \, | \, {\bf V}^n) &= \lim_{n \to \infty} F_1(V_i^n(\sigma_{ij}(g)) - V_i^n(g)) \nonumber \\
&= F_1(0) \nonumber \\
&= \frac{1}{2}.
\end{align}

This yields

\begin{align}
\lim_{n \to \infty} \log\left( \frac{p_{ij}(\sigma_{ij}(g) \, | \, {\bf V}^n)}{p_{ij}(g \, | \, {\bf V}^n)} \right) = 0.
\end{align}

Following Proposition <ref>, this corresponds to a conservative function $\phi$ with a constant generating function $\Phi$. A constant generating function corresponds to a constant stationary distribution, which is given by

\begin{align}
\lim_{n \to \infty} \pi(g \, | \, {\bf V}^n) = \frac{1}{|{\cal G}|}.
\end{align}

We, therefore, have that

\begin{align}
\lim_{n \to \infty} V^n_i(g) = \frac{1}{|{\cal G}|} \sum_{g' \in {\cal G}} v_i(g').
\end{align}

§.§ Proof of Lemma <ref>

For a given $N$, define the random variables

\begin{align}
X_N(G) &\equiv \left(\frac{\partial \Phi_N(G;v_0,\gamma)}{\partial v_0} \right), \nonumber \\
Y_N(G) &\equiv \left(\frac{\partial \Phi_N(G;v_0,\gamma)}{\partial \gamma} \right).
\end{align}

We want to study the behavior of

\begin{align}
\left \langle \left. \frac{Y_N}{X_N} \right| G \ne \varnothing \right \rangle = \sum_{g \in {\cal G} \backslash \{\varnothing\}} \left( \frac{\pi^N(g)}{1-\pi^N(\varnothing)} \right) \frac{Y_N(g)}{X_N(g)}.
\end{align}

Now, note that convergence of the mean implies convergence in the means conditional on $G \ne \varnothing$. We have that

\begin{align}
\langle X_N | G \ne \varnothing \rangle &= \sum_{g \in {\cal G} \backslash \{\varnothing\}} \left( \frac{\pi^N(g)}{1-\pi^N(\varnothing)} \right) X_N(g) \nonumber \\
&= \frac{1}{1 - \pi^N(\varnothing)} [\langle X_N \rangle - \pi^N(\varnothing) X_N(\varnothing)],
\end{align}

and similarly for $Y_N$. Since in our case $X_N(\varnothing) = Y_N(\varnothing) = 0$ for all $N$, we have that

\begin{align}
\lim_{N \to \infty} \frac{1}{N^2} \langle X_N | G \ne \varnothing \rangle &= \lim_{N \to \infty} \left(\frac{1}{1 - \pi^N(\varnothing)} \frac{\langle X_N \rangle}{N^2} - \frac{\pi^N(\varnothing) X_N(\varnothing)}{N^2 (1 - \pi^N(\varnothing))} \right) \nonumber \\
&= \frac{\partial \zeta(v_0,\gamma)}{\partial v_0},
\end{align}

and similarly for $Y_N$.

I now establish that $X_N$ converges in probability to $\frac{\partial \zeta(v_0,\gamma)}{\partial v_0}$, conditional on $G \ne \varnothing$. We have that, for all $\epsilon > 0$,

\begin{align}
&\mathbb{P}\left\{ \left. \left|\frac{X_N}{N^2} - \frac{\partial \zeta(v_0,\gamma)}{\partial v_0} \right| \le \epsilon \right| G \ne \varnothing  \right\} \nonumber \\
&= 1 - \mathbb{P}\left\{ \left. \left|\frac{X_N}{N^2} - \frac{\partial \zeta(v_0,\gamma)}{\partial v_0} \right| > \epsilon \right| G \ne \varnothing  \right\} \nonumber \\
&= 1 - \mathbb{P}\left\{ \left. \left|\left(\frac{X_N}{N^2} - \frac{1}{N^2} \langle X_N | G \ne \varnothing \rangle \right) - \left( \frac{\partial \zeta(v_0,\gamma)}{\partial v_0} - \frac{1}{N^2} \langle X_N | G \ne \varnothing \rangle \right) \right| > \epsilon \right| G \ne \varnothing  \right\} \nonumber \\
&\ge 1 - \mathbb{P}\left\{ \left. \left|\frac{X_N}{N^2} - \frac{1}{N^2} \langle X_N | G \ne \varnothing \rangle \right | + \left| \frac{\partial \zeta(v_0,\gamma)}{\partial v_0} - \frac{1}{N^2} \langle X_N | G \ne \varnothing \rangle \right| > \epsilon \right| G \ne \varnothing  \right\}.
\end{align}

Since $\frac{1}{N^2} \langle X_N | G \ne \varnothing \rangle$ converges to $\frac{\partial \zeta(v_0,\gamma)}{\partial v_0}$, we have that there exists an $N_0$ such that, for all $N > N_0$,

\begin{align}
\left| \frac{\partial \zeta(v_0,\gamma)}{\partial v_0} - \frac{1}{N^2} \langle X_N | G \ne \varnothing \rangle \right| \le \epsilon/2.
\end{align}

Suppose that $N > N_0$. We, then, have that

\begin{align}
&\mathbb{P}\left\{ \left. \left|\frac{X_N}{N^2} - \frac{\partial \zeta(v_0,\gamma)}{\partial v_0} \right| \le \epsilon \right| G \ne \varnothing  \right\} \nonumber \\
&\ge 1 - \mathbb{P}\left\{ \left. \left|\frac{X_N}{N^2} - \frac{1}{N^2} \langle X_N | G \ne \varnothing \rangle \right | > \epsilon - \left| \frac{\partial \zeta(v_0,\gamma)}{\partial v_0} - \frac{1}{N^2} \langle X_N | G \ne \varnothing \rangle \right| \right| G \ne \varnothing  \right\} \nonumber \\
&\ge 1 - \mathbb{P}\left\{ \left. \left|\frac{X_N}{N^2} - \frac{1}{N^2} \langle X_N | G \ne \varnothing \rangle \right | > \frac{\epsilon}{2} \right| G \ne \varnothing  \right\}
\end{align}

Using Chebyshev's inequality, this implies that

\begin{align}
\mathbb{P}\left\{ \left. \left|\frac{X_N}{N^2} - \frac{\partial \zeta(v_0,\gamma)}{\partial v_0} \right| \le \epsilon \right| G \ne \varnothing  \right\} \ge 1 - \frac{4 \mathbb{V}(X_N/N^2|G \ne \varnothing)}{\epsilon^2},
\end{align}

where $\mathbb{V}$ denotes the variance. Now, we have that

\begin{align}
\lim_{N \to \infty} \frac{1}{N^2} [\langle X_N^2 \rangle - \langle X_N \rangle^2] = \frac{\partial^2 \zeta(v_0, \gamma)}{\partial v_0^2}.
\end{align}

Note that we can write

\begin{align}
\langle X_N^2 | G \ne \varnothing \rangle &= \sum_{g \in {\cal G} \backslash \{\varnothing\}} \left( \frac{\pi^N(g)}{1-\pi^N(\varnothing)} \right) X_N^2(g) \nonumber \\
&= \frac{1}{1 - \pi^N(\varnothing)} [\langle X_N^2 \rangle - \pi^N(\varnothing) X_N^2(\varnothing)] \nonumber \\
&= \frac{\langle X_N^2 \rangle}{1 - \pi^N(\varnothing)}.
\end{align}

This implies that

\begin{align}
\langle X_N^2 | G \ne \varnothing \rangle - \langle X_N | G \ne \varnothing \rangle^2 &= \frac{\langle X_N^2 \rangle}{1 - \pi^N(\varnothing)} - \frac{\langle X_N \rangle^2}{[1 - \pi^N(\varnothing)]^2} \nonumber \\
&= \frac{\langle X_N^2 \rangle - \langle X_N \rangle^2}{[1 - \pi^N(\varnothing)]^2} - \frac{\pi^N(\varnothing) \langle X_N^2 \rangle}{[1 - \pi^N(\varnothing)]^2}.
\end{align}

Now, since $\pi^N(\varnothing)$ converges to $0$ faster than $N^m$ for all $m \in \mathbb{N}$, we have that

\begin{align}
\lim_{N \to \infty} \pi^N(\varnothing) \langle X_N^2 \rangle &= \lim_{N \to \infty} \pi^N(\varnothing) [\langle X_N^2 \rangle - \langle X_N \rangle^2] + \pi^N(\varnothing) \langle X_N \rangle^2 \nonumber \\
&= 0.
\end{align}

The first term vanishes because of the convergence of the variance divided by $N^2$, and the second term vanishes because of the convergence of the mean divided by $N^2$ (or of the mean squared divided by $N^4$, which is implied by the convergence of the mean). We, therefore, conclude that

\begin{align}
\lim_{N \to \infty} \frac{1}{N^2} [\langle X_N^2 | G \ne \varnothing \rangle - \langle X_N | G \ne \varnothing \rangle^2] &= \lim_{N \to \infty} \frac{1}{N^2} \frac{\langle X_N^2 \rangle - \langle X_N \rangle^2}{[1 - \pi^N(\varnothing)]^2} \nonumber \\
&= \frac{\partial^2 \zeta(v_0, \gamma)}{\partial v_0^2}.
\end{align}

Therefore, there exists an $N_1$ such that $N > N_1$ implies

\begin{align}
\left|\frac{1}{N^2} [\langle X_N^2 | G \ne \varnothing \rangle - \langle X_N | G \ne \varnothing \rangle^2] - \frac{\partial^2 \zeta(v_0, \gamma)}{\partial v_0^2} \right| < \epsilon^2.
\end{align}

Let us now assume that $N > \max\{N_0,N_1\}$. Dividing by $N^2$, we obtain a bound for the variance of $X_N/N^2$:

\begin{align}
&\left| \mathbb{V}(X_N/N^2|G \ne \varnothing) - \frac{1}{N^2} \frac{\partial^2 \zeta(v_0, \gamma)}{\partial v_0^2} \right| < \frac{\epsilon^2}{N^2}, \nonumber \\
&\implies \quad \mathbb{V}(X_N/N^2|G \ne \varnothing) < \frac{1}{N^2} \left(\frac{\partial^2 \zeta(v_0, \gamma)}{\partial v_0^2} + \epsilon^2 \right).
\end{align}

Going back to Chebyshev's inequality, we obtain that

\begin{align}
\mathbb{P}\left\{ \left. \left|\frac{X_N}{N^2} - \frac{\partial \zeta(v_0,\gamma)}{\partial v_0} \right| \le \epsilon \right| G \ne \varnothing  \right\} &\ge 1 - \frac{4}{N^2} \left( 1 + \frac{1}{\epsilon^2} \frac{\partial^2 \zeta(v_0, \gamma)}{\partial v_0^2} \right).
\end{align}

This implies that

\begin{align}
\lim_{N \to \infty} \mathbb{P}\left\{ \left. \left|\frac{X_N}{N^2} - \frac{\partial \zeta(v_0,\gamma)}{\partial v_0} \right| \le \epsilon \right| G \ne \varnothing  \right\} = 1.
\end{align}

We, therefore, conclude that $\frac{X_N}{N^2}$ converges in probability to $\frac{\partial \zeta(v_0,\gamma)}{\partial v_0}$, conditional on $G \ne \varnothing$. A completely analogous argument shows that $\frac{Y_N}{N^2}$ converges in probability to $\frac{\partial \zeta(v_0,\gamma)}{\partial \gamma}$.

By conditioning on $G \ne \varnothing$, $\frac{X_N}{N^2}$ is a strictly positive random variable. Applying Slutsky's theorem, we have that

\begin{align}
\left( \frac{X_N}{N^2} \right)^{-1} \left( \frac{Y_N}{N^2} \right) \xrightarrow[]{p} \left( \frac{\partial \zeta(v_0,\gamma)}{\partial v_0} \right)^{-1} \left( \frac{\partial \zeta(v_0,\gamma)}{\partial \gamma} \right),
\end{align}

where $\xrightarrow[]{p}$ denotes convergence in probability. Now, note that in our case we have that $X_N(g)$ corresponds to the number of dyads in $g$ and $Y_N(g)$ corresponds to the negative of the sum of the distances corresponding to each dyad. Therefore, we have that $-Y_N/X_N$ is the average distance between neighbors. Since the distance is bounded by $\overline{D}$, we have that

\begin{align}
\left| \frac{Y_N}{X_N} \right| < \overline{D}.
\end{align}

As such, the random variable $\frac{X_N}{Y_N}$ has bounded support and is, therefore, uniformly integrable (Lemma 2.31 in <cit.>). Since uniform integrability and convergence in probability are sufficient to have convergence in mean, we conclude that

\begin{align}
\lim_{N \to \infty} \left \langle \left. \left( \frac{\partial \Phi_N(v_0, \gamma)}{\partial v_0} \right)^{-1} \left( \frac{\partial \Phi_N(v_0, \gamma)}{\partial \gamma} \right) \right | G \ne \varnothing \right \rangle = \left( \frac{\partial \zeta(v_0, \gamma)}{\partial v_0} \right)^{-1} \left( \frac{\partial \zeta(v_0, \gamma)}{\partial \gamma} \right).
\end{align}

§.§ Proof of Proposition <ref>

Note that the trade model can be written in terms of the group-size preferences model. We have that for utilities of the form

\begin{align}
V_i(g) = \sum_{j \in {\cal N}_i(g)} [v_0 - \gamma D_{ij}] + B_N(|{\cal N}_i(g)|),
\end{align}

the partition function is given by

\begin{align}
Z_N(v_0, \gamma) = \prod_{r \in \Theta} \left[ \left( \sum_{l_{rs}=0}^{N_s-\delta_{rs}} \right)_{s \in \Theta} \left[ \prod_{s \in \Theta} {l_{rs} \choose N_s - \delta_{rs}} \right] \exp\left( \sum_{q \in \Theta} [ v_0 - \gamma \tilde{D}_{r,q} ] l_{rq} + B_N \left( \sum_{q \in \Theta} l_{rq} \right) \right) \right]^{N_r}.
\end{align}

For the case of the trade model, we have that

\begin{align}
B_N(l) = - \frac{c}{N} l^2.
\end{align}

The partition function for the trade model, then, is given by

\begin{align}
Z_N(v_0, \gamma, c) = \prod_{r \in \Theta} \left[ \left( \sum_{l_{rs}=0}^{N_s-\delta_{rs}} \right)_{s \in \Theta} \left[ \prod_{s \in \Theta} {l_{rs} \choose N_s - \delta_{rs}} \right] \exp\left( \sum_{q \in \Theta} [ v_0 - \gamma \tilde{D}_{r,q} ] l_{rq} - \frac{c}{N} \left( \sum_{q \in \Theta} l_{rq} \right)^2 \right) \right]^{N_r}.
\end{align}

This can be re-written as

\begin{align}
&Z_N(v_0, \gamma, c) \nonumber \\
&= \prod_{r \in \Theta} \left[ \left( \sum_{l_{rs}=0}^{N_s-\delta_{rs}} \right)_{s \in \Theta} \exp \left( \sum_{s \in \Theta} \left( \log \left[ {l_{rs} \choose N_s - \delta_{rs}} \right] + [ v_0 - \gamma \tilde{D}_{r,s} ] l_{rs} \right) - \frac{c}{N} \left( \sum_{q \in \Theta} l_{rq} \right)^2 \right) \right]^{N_r}.
\end{align}

Taking logs, we obtain

\begin{align}
&\log(Z_N(v_0, \gamma, c)) \nonumber \\
&= \sum_{r \in \Theta} N_r \log \left[ \left( \sum_{l_{rs}=0}^{N_s-\delta_{rs}} \right)_{s \in \Theta} \exp \left( \sum_{s \in \Theta} \left( \log \left[ {l_{rs} \choose N_s - \delta_{rs}} \right] + [ v_0 - \gamma \tilde{D}_{r,s} ] l_{rs} \right) - \frac{c}{N} \left( \sum_{q \in \Theta} l_{rq} \right)^2 \right) \right].
\end{align}

To asymptotically evaluate this expression, we can use the Stirling bounds on the factorial:

\begin{align}
\sqrt{2 \pi n} \left( \frac{n}{e} \right)^n e^{\frac{1}{12 n + 1}} < n! < \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n e^{\frac{1}{12 n}},
\end{align}

for $n > 0$. This implies that, if $\frac{k_n}{n} \to x \in (0,1)$ as $n \to \infty$, the following holds:

\begin{align}
\lim_{n \to \infty} \frac{1}{n} \log \left[ {n \choose k_n} \right] &= - [x \log(x) + (1-x) \log(1-x)].
\end{align}

Now, for a sequence $l_{rs}^N$ that satisfies $\lim_{N \to \infty} l_{rs}^N/N_s = x_{rs} \in (0,1)$, we have that

\begin{align}
&\lim_{N \to \infty} \frac{1}{N} \left[ \sum_{s \in \Theta} \left( \log \left[ {l_{rs} \choose N_s - \delta_{rs}} \right] + [ v_0 - \gamma \tilde{D}_{r,s} ] l_{rs} \right) - \frac{c}{N} \left( \sum_{q \in \Theta} l_{rq} \right)^2 \right] \nonumber \\
&= \lim_{N \to \infty} \sum_{s \in \Theta} \left( \frac{N_s - \delta_{rs}}{N} \frac{1}{N_s - \delta_{rs}} \log \left[ {l_{rs} \choose N_s - \delta_{rs}} \right] + [ v_0 - \gamma \tilde{D}_{r,s} ] \frac{N_s}{N} \frac{l_{rs}}{N_s} \right) - c \left( \sum_{q \in \Theta} \frac{N_q}{N} \frac{l_{rq}}{N_q} \right)^2 \nonumber \\
&= \sum_{s \in \Theta} w_s \left( - [x_{rs} \log(x_{rs}) + (1-x_{rs}) \log(1-x_{rs})] + [ v_0 - \gamma \tilde{D}_{r,s} ] x_{rs} \right) - c \left( \sum_{q \in \Theta} w_q x_{rq} \right)^2,
\end{align}

since we have that $N_s/N \to w_s$ as $N \to \infty$. For ${\bf x}_r \equiv (x_{rs})_s$, define the function

\begin{align}
Y_r({\bf x}_r) \equiv \sum_{s \in \Theta} w_s \left( - [x_{rs} \log(x_{rs}) + (1-x_{rs}) \log(1-x_{rs})] + [ v_0 - \gamma \tilde{D}_{r,s} ] x_{rs} \right) - c \left( \sum_{q \in \Theta} w_q x_{rq} \right)^2.
\end{align}

The partial derivatives of $Y_r$ are

\begin{align} \label{eq:trade_derivative}
\frac{\partial Y_r}{\partial x_{rs}} = w_s [\log(1-x_{rs}) - \log(x_{rs})] + w_s [ v_0 - \gamma \tilde{D}_{r,s} ] - 2 c w_s \sum_{q \in \Theta} w_q x_{rq}.
\end{align}

The second partial derivatives are

\begin{align}
\frac{\partial^2 Y_r}{\partial x_{rq} \partial x_{rs}} = - \frac{w_s}{x_{rs}(1-x_{rs})} \delta_{sq} - 2 c w_s w_q.
\end{align}

Take an arbitrary vector $(z_s)_{s \in \Theta}$. We have that

\begin{align}
\sum_{s,q \in \Theta} z_s \left( \frac{\partial^2 Y_r}{\partial x_{rq} \partial x_{rs}} \right) z_q &= - \left[ \sum_{s,q \in \Theta} \left(  \frac{w_s}{x_{rs}(1-x_{rs})} \delta_{sq} z_s z_q + 2 c w_s w_q z_s z_q \right) \right] \nonumber \\
&= - \left[ \sum_{s \in \Theta}  \frac{w_s}{x_{rs}(1-x_{rs})} z_s^2 + 2 c \left( \sum_{s \in \Theta} w_s z_s \right)^2 \right].
\end{align}

This quantity is strictly negative if ${\bf z} \ne {\bf 0}$. As such, we have that the Hessian is negative definite, meaning that $Y_r$ has a unique maximum in $[0,1]^{|\Theta|} = [0,1]^C$.

For a finite set ${\cal A}$, define $\overline{a} \equiv \max\{{\cal A}\}$. We have that

\begin{align}
e^{\overline{a}} \le \sum_{a \in {\cal A}} e^a \le |{\cal A}| e^{\overline{a}}.
\end{align}

Taking logs, this yields

\begin{align}
\overline{a} \le \log \left( \sum_{a \in {\cal A}} e^a \right) \le \overline{a} + \log(|{\cal A}|).
\end{align}

For a given $r \in \Theta$, the sum we wish to evaluate runs over the set that is indexed by ${\cal A}_r = \{(n_s)_{s} | 0 \le n_s \le N_s - \delta_{rs} \}$. This set satisfies

\begin{align}
|{\cal A}_r| \le \prod_{s \in \Theta} N_s \quad \implies \quad \log(|{\cal A}_r|) \le \sum_{s \in \Theta} \log(N_s).
\end{align}

Since $N_s \le N$, we this implies

\begin{align}
\log(|{\cal A}_r|) \le C \log(N).
\end{align}

Dividing by $N$ yields

\begin{align}
\frac{\overline{a}}{N} \le \frac{1}{N} \log \left( \sum_{a \in {\cal A}} e^a \right) \le \frac{\overline{a}}{N} + C \frac{N}{\log(N)}.
\end{align}

From the previous analysis, we have that the maximum of our sum is the unique maximizer of $Y_r$:

\begin{align}
\lim_{N \to \infty} \frac{\overline{a}}{N} = \max_{{\bf x}_r \in [0,1]^C} Y_r({\bf x}_r).
\end{align}

Since $\lim_{N \to \infty} \log(N)/N = 0$, we conclude that

\begin{align}
\lim_{N \to \infty} \frac{1}{N} \log \left( \sum_{a \in {\cal A}_r} e^a \right) = \max_{{\bf x}_r \in [0,1]^C} Y_r({\bf x}_r).
\end{align}

Note that the partition function can be written in terms of the sum over ${\cal A}$ as

\begin{align}
\log(Z_N(v_0, \gamma, c)) = \sum_{r \in \Theta} N_r \log \left( \sum_{a \in {\cal A}_r} e^a \right).
\end{align}

We, therefore, have that

\begin{align} \label{eq:trade_appendix}
\zeta_{\mathrm{trade}}(v_0, \gamma, c) &= \lim_{N \to \infty} \frac{Z_N(v_0, \gamma, c)}{N^2} \nonumber \\
&= \lim_{N \to \infty} \sum_{r \in \Theta} \frac{N_r}{N} \frac{1}{N} \log \left( \sum_{a \in {\cal A}_r} e^a \right) \nonumber \\
&= \sum_{r \in \Theta} w_r \max_{{\bf x}_r \in [0,1]^C} Y_r({\bf x}_r) \nonumber \\
&= \sum_{r \in \Theta} w_r \max_{{\bf x}_r \in [0,1]^C} \sum_{s \in \Theta} w_s \left( H(x_{rs}) + [ v_0 - \gamma \tilde{D}_{r,s} ] x_{rs} \right) - c \left( \sum_{q \in \Theta} w_q x_{rq} \right)^2.
\end{align}

To evaluate the average trade between countries $r$ and $s$, note that the generating function for this problem is

\begin{align}
\Phi_N(g ; v_0, \gamma, c) = \sum_{r \in \Theta} \sum_{s \in \Theta} \left[ v_0 - \gamma \Tilde{D}_{r,s} \right] l_{rs}(g) + \frac{c}{N} \sum_{i \in {\cal N}} |{\cal N}_i(g)|^2.
\end{align}

For a given network $g$, the normalized trade is given by

\begin{align}
T_{rs,N}(g) = \frac{l_{rs}(g)}{N_r(N_s - \delta_{rs})}.
\end{align}

Note that this can be obtained as

\begin{align}
T_{rs,N}(g) = \frac{1}{N_r(N_s - \delta_{rs})} \left( - \frac{1}{\gamma} \frac{\partial \Phi_N(g ; v_0, \gamma, c)}{\partial \Tilde{D}_{r,s}} \right).
\end{align}

The limiting behavior, then, can be obtained from

\begin{align}
\lim_{N \to \infty} \langle T_{rs,N} \rangle &= - \frac{1}{\gamma} \lim_{N \to \infty} \frac{N^2}{N_r(N_s - \delta_{rs})} \left\langle  \frac{1}{N^2} \frac{\partial \Phi_N(v_0, \gamma, c)}{\partial \Tilde{D}_{r,s}} \right\rangle \nonumber \\
&= - \frac{1}{\gamma} \frac{1}{w_r w_s} \frac{\partial \zeta_{\textrm{trade}}(v_0, \gamma, c)}{\partial \Tilde{D}_{r,s}}.
\end{align}

Applying the envelope theorem to the expression in Equation (<ref>) yields

\begin{align}
\frac{\partial \zeta_{\textrm{trade}}(v_0, \gamma, c)}{\partial \Tilde{D}_{r,s}} = -\gamma w_r w_s x_{rs}^*,
\end{align}

where $x_{rs}^*$ is the maximizer in the expression for $\zeta$. We, therefore, have that

\begin{align}
\lim_{N \to \infty} \langle T_{rs,N} \rangle = x_{rs}^*.
\end{align}

To obtain $x_{rs}^*$, we can use the expressions for the first derivatives in Equation (<ref>) to obtain the first-order conditions of the optimization problem. The condition associated to $x_{rq}$ is

\begin{align}
&w_q [\log(1-x_{rq}^*) - \log(x_{rq}^*)] + w_q [ v_0 - \gamma \tilde{D}_{r,q} ] - 2 c w_q \sum_{q' \in \Theta} w_{q'} x_{rq'}^* = 0, \nonumber \\
&\implies \log\left( \frac{1-x_{rq}^*}{x_{rq}^*} \right) + v_0 - \gamma \tilde{D}_{r,q} - 2 c \sum_{q' \in \Theta} w_{q'} x_{rq'}^* = 0.
\end{align}

Note that this implies that the quantity

\begin{align}
\log\left( \frac{1-x_{rq}^*}{x_{rq}^*} \right) + v_0 - \gamma \tilde{D}_{r,q}
\end{align}

is the same for all $q$, given $r$. Denoting this quantity with $B_r$, we have that

\begin{align}
&\log\left( \frac{1-x_{rq}^*}{x_{rq}^*} \right) + v_0 - \gamma \tilde{D}_{r,q} = B_r, \nonumber \\
&\implies \quad x_{rq}^* = [1 + e^{B_r} e^{\gamma \Tilde{D}_{r,q} - v_0}]^{-1}.
\end{align}

Additionally, note that $B_r$ must satisfy

\begin{align}
B_r &= 2 c \sum_{q' \in \Theta} w_{q'} x_{rq'}^* \nonumber \\
&= 2 c \sum_{q' \in \Theta} w_{q'} [1 + e^{B_r} e^{\gamma \Tilde{D}_{r,q'} - v_0}]^{-1}.
\end{align}

We have that the $x_{rq'}^*$ are strictly decreasing functions of $B_r$, that $\lim_{B_r \to 0} x_{rq'}^* > 0$ and that $\lim_{B_r \to \infty} x_{rq'}^* = 0$. This implies that there is a unique root of the above equation. Using the implicit function theorem, we have that

\begin{align}
&\frac{\partial B_r}{\partial c} = 2 \sum_{q' \in \Theta} w_{q'} x_{rq'}^* + 2 c \left(\sum_{q' \in \Theta} w_{q'} \frac{\partial x_{rq'}^*}{\partial B_r} \right) \frac{\partial B_r}{\partial c}, \nonumber \\
&\implies \quad \frac{\partial B_r}{\partial c} \left[ 1 - 2 c \sum_{q' \in \Theta} w_{q'} \frac{\partial x_{rq'}^*}{\partial B_r} \right] = 2 \sum_{q' \in \Theta} w_{q'} x_{rq'}^*.
\end{align}

Since $\frac{\partial x_{rq'}^*}{\partial B_r} < 0$, we conclude that $B_r$ is increasing in $c$. Writing $A_r(c) \equiv e^{B_r}$, we can express the limiting behavior of the normalized trade as

\begin{align}
\lim_{N \to \infty} \langle T_{rs,N} \rangle = [1 + A_r(c) e^{\gamma \Tilde{D}_{r,s} - v_0}]^{-1}.
\end{align}

§.§ Exactly solvable partition functions

§.§.§ Constant marginal utility of links

Consider the utility function

\begin{align}
V_i(g) = \alpha |{\cal N}_i(g)|.
\end{align}

§.§.§ Distance-dependent marginal utility

§.§.§ Matching pairs utility

Define the set of symmetric neighbors of $i$ as

\begin{align}
{\cal N}_i^{\textrm{sym}}(g) = \{j \in {\cal N} \, | \, ij \in g, ji \in g \}.
\end{align}

The utility is given by

\begin{align}
V_i(g) = \sum_{j \in {\cal N}_i^{\textrm{sym}}(g)} m_{ij}.
\end{align}

Proof of conservativeness when $m_{ij} = m_{ji}$ given by Mele. The $\Phi$ function, then, is given by

\begin{align}
\Phi(g) = \sum_{i \in {\cal N}} \sum_{j \in {\cal N}_i^{\textrm{sym}}(g)} m_{ij}.
\end{align}

We can calculate the partition function exactly in the case $m_{ij} = \beta$ for all $ij \in {\cal D}$. In this case the potential is given by

\begin{align}
\Phi(g) = \beta L_{\textrm{sym}}(g),
\end{align}

where $L_{\textrm{sym}}(g)$ is the number of $(ij, ji)$ pairs such that both are present in $g$, which I call the “symmetric links”. Let $L_N \equiv \frac{N(N-1)}{2}$ denote the number of possible links in an undirected network over $N$ nodes.

The partition function is, then

\begin{align}
Z &= \sum_{g \in {\cal G}} e^{\Phi(g)} \nonumber \\
&= \sum_{g \in {\cal G}} e^{\beta L_{\textrm{sym}}(g)}.
\end{align}

Partitioning ${\cal G}$ into subsets with a constant number of symmetric links, we obtain

\begin{align}
Z &= \sum_{L=0}^{L_N} {L_N \choose L} 3^{L_N - L} e^{\beta L} \nonumber \\
&= (3 + e^\beta)^L_N \nonumber \\
&= (3 + e^\beta)^{\frac{N(N-1)}{2}}.
\end{align}

With this partition function we can calculate the average number of observed symmetric links. Note that by differentiating the $\Phi$ function with respect to $\beta$, we obtain

\begin{align}
\frac{\partial \Phi(g)}{\partial \beta} = L_{\textrm{sym}}(g).
\end{align}

The long-run average, then, is given by

\begin{align}
\langle L_{\textrm{sym}}(g) \rangle &= \frac{\partial \log(Z)}{\partial \alpha} \nonumber \\
&= \frac{N(N-1)}{2} \frac{e^\alpha}{3 + e^{\alpha}}.
\end{align}

That is, the average fraction of possible symmetric links in the network will be given by $\frac{e^\alpha}{3 + e^{\alpha}}$. This will range from $1/4$ when $\alpha = 0$, which corresponds to an Erdös-Rényi model with $p=1/2$, to $1$ when $\alpha \to \infty$, which corresponds to the case where the value of a symmetric connection is higher than the idiosyncratic differences with probability $1$.

§.§ Asymptotic partition functions

§.§.§ Group-size preferences

§.§ Discrete-type model

I begin by calculating the partition function for $N$ agents. Let $N_A(N)$ and $N_B(N)$ be the number of agents of types $A$ and $B$, respectively. The condition that the fraction of agents of type $j$ must converge to $\rho_j$ can be written as

\begin{align*}
\lim_{N \to \infty} \frac{N_j(N)}{N} = \rho_j, \, j \in \{A,B\}.
\end{align*}

Let $L_s(N)$ and $L_c(N)$ be the number of possible links of agents of the same type (self-links) and between agents of different types (cross-links), respectively. These are given by

\begin{align*}
L_s(N) &= N_A(N)(N_A(N)-1) + N_B(N)(N_B(N)-1), \\
L_c(N) &= 2 N_A(N)N_B(N).
\end{align*}

Recall that the Hamiltonian of this system can be written as

\begin{align*}
H_N(g) = -\alpha l_s(g) + (\gamma - \alpha) l_c(g),
\end{align*}

such that it is fully characterized by the number of self-links and cross-links in $g$. We have that the number of networks in ${\cal G}_N$ that have $k_s \le L_S(N)$ self-links and $k_c \le N_C(N)$ cross-links is given by ${L_s(N) \choose k_s} {L_c(N) \choose k_c}$. The partition function, then, can be calculated as

\begin{align*}
Z_N(\alpha, \gamma) &= \sum_{g \in {\cal G}_N} e^{-H(g)} \\
&= \sum_{k_s = 0}^{L_s(N)} \sum_{k_c = 0}^{L_c(N)} {L_s(N) \choose k_s} {L_c(N) \choose k_c} e^{\alpha k_s + (\alpha - \gamma) k_c} \\
&= \left( 1 + e^\alpha \right)^{L_s(N)} \left( 1 + e^{\alpha - \gamma} \right)^{L_c(N)}.
\end{align*}

Given this simple expression for the finite-size partition function, calculating $\zeta$ is straightforward. We have that

\begin{align*}
\frac{1}{N^2} \log(Z_N(\alpha, \gamma)) \, =& \, \left( \frac{L_s(N)}{N^2} \right) \log \left( 1 + e^\alpha \right) + \left( \frac{L_c(N)}{N^2} \right) \log \left( 1 + e^{\alpha - \gamma} \right) \\
\, =& \, \left[ \left( \frac{N_A(N)}{N} \right) \left( \frac{N_A(N) - 1}{N} \right) + \left( \frac{N_B(N)}{N} \right) \left( \frac{N_B(N) - 1}{N} \right)  \right] \log \left( 1 + e^\alpha \right) \\
& \, + 2 \left( \frac{N_A(N)}{N} \right) \left( \frac{N_B(N)}{N} \right) \log \left( 1 + e^{\alpha - \gamma} \right).
\end{align*}

Since the limits as $N \to \infty$ of all these factors exist, we obtain the desired result:

\begin{align*}
\zeta_{\textrm{disc}}(\alpha, \gamma) &= \lim_{N \to \infty} \frac{1}{N^2} \log(Z_N(\alpha, \gamma)) \\
&= (\rho_A^2 + \rho_B^2) \log \left( 1 + e^\alpha \right) + 2 \rho_A \rho_B \log \left( 1 + e^{\alpha - \gamma} \right).
\end{align*}

The average link density and distance between neighbors are given by

\begin{align*}
\mu_{\textrm{disc}}(\alpha, \gamma) &= (\rho_A^2 + \rho_B^2) \left( \frac{e^\alpha}{1 + e^\alpha} \right) + 2 \rho_A \rho_B \left( \frac{e^{\alpha-\gamma}}{1 + e^{\alpha-\gamma}} \right), \\
\eta_{\textrm{disc}}(\alpha, \gamma) &= \frac{2 \rho_A \rho_B \left( \frac{e^{\alpha-\gamma}}{1 + e^{\alpha-\gamma}} \right) }{ (\rho_A^2 + \rho_B^2) \left( \frac{e^\alpha}{1 + e^\alpha} \right) + 2 \rho_A \rho_B \left( \frac{e^{\alpha-\gamma}}{1 + e^{\alpha-\gamma}} \right) }.
\end{align*}

§.§ Continuous-type model

For the calculation of the $N$-individual partition function, it is convenient to re-write the Hamiltonian as

\begin{align*}
H_N(g) &= \sum_{ij \in {\cal L}_N} (-\alpha + \gamma D(\theta_i, \theta_j)) g_{ij}. \\
&= \sum_{i \in {\cal N}} \sum_{j \in {\cal N} \backslash \{i\}} (-\alpha + \gamma D(\theta_i, \theta_j)) g_{ij}.
\end{align*}

The partition function can be calculated as

\begin{align*}
Z_N(\alpha, \gamma) &= \sum_{s_{i_1j_1} \in \{0,1\}} \cdots \sum_{s_{i_{L_N}j_{L_N}} \in \{0,1\}} \prod_{ij \in {\cal L}_N} \exp \left( (-\alpha + \gamma D(\theta_i, \theta_j)) s_{ij} \right) \\
&= \prod_{ij \in {\cal L}_N} \sum_{s_{ij} \in \{0,1\}} \exp \left( (\alpha - \gamma D(\theta_i, \theta_j)) s_{ij} \right) \\
&= \prod_{ij \in {\cal L}_N} \left[ 1 + \exp \left( \alpha - \gamma D(\theta_i, \theta_j) \right) \right].
\end{align*}

We can split this product into factors corresponding to each individual, such that

\begin{align*}
Z_N(\alpha, \gamma) = \prod_{i \in {\cal N}} \prod_{j \in {\cal N} \backslash \{i\}} \left[ 1 + \exp \left( \alpha - \gamma D(\theta_i, \theta_j) \right) \right].
\end{align*}

Explain why it is the same for everyone

\begin{align*}
Z_N(\alpha, \gamma) = \left( \prod_{j \in {\cal N} \backslash \{1\}} \left[ 1 + \exp \left( \alpha - \gamma D(\theta_1, \theta_j) \right) \right] \right)^N.
\end{align*}

We, therefore, have that

\begin{align*}
\log(Z_N(\alpha, \gamma)) = N \sum_{j \in {\cal N} \backslash \{1\}} \log \left[ 1 + \exp \left( \alpha - \gamma D(\theta_1, \theta_j) \right) \right].
\end{align*}

By analyzing the number of individuals at different distances, we can turn

\begin{align*}
\sum_{j \in {\cal N} \backslash \{1\}}& \log \left[ 1 + \exp \left( \alpha - \gamma D(\theta_1, \theta_j) \right) \right] = \\
\begin{cases}
2 \sum_{k=1}^{\frac{N-1}{2}} \log \left[ 1 + \exp \left( \alpha - \gamma \frac{Ck}{N+1} \right) \right] & \textrm{if } N \textrm{ is odd} \\
\log \left[ 1 + \exp \left( \alpha - 2 \gamma \right) \right] + 2 \sum_{k=1}^{\frac{N-2}{2}} \log \left[ 1 + \exp \left( \alpha - \gamma \frac{Ck}{N+1} \right) \right] & \textrm{if } N \textrm{ is even}.
\end{cases}
\end{align*}

These expressions yield the following limit:

\begin{align*}
\lim_{N \to \infty} \frac{1}{N} \sum_{j \in {\cal N} \backslash \{1\}}& \log \left[ 1 + \exp \left( \alpha - \gamma D(\theta_1, \theta_j) \right) \right] = \int_0^1 \log \left[ 1 + \exp \left( \alpha - \frac{C \gamma}{2} x \right) \right] \, dx.
\end{align*}

The previous integral can be calculated using the identity

\begin{align*}
\int_0^1 \log[1 + c r^x] = \frac{\textrm{Li}_2(-cr) - \textrm{Li}_2(-c)}{\log(r)}, \, r, c > 0,
\end{align*}

where $\textrm{Li}_2$ is the dilogarithmic function. We, therefore, have that

\begin{align*}
\int_0^1 \log \left[ 1 + \exp \left( \alpha - \frac{C \gamma}{2} x \right) \right] \, dx = \frac{2}{C \gamma} \left[ \textrm{Li}_2(-e^{\alpha}) - \textrm{Li}_2(-e^{\alpha-C\gamma/2}) \right].
\end{align*}

Returning to the partition function, we conclude that

\begin{align*}
\zeta_{\textrm{cont}}(\alpha, \gamma) &= \lim_{N \to \infty} \frac{1}{N^2} \log(Z_N(\alpha, \gamma)) \\
&= \lim_{N \to \infty} \frac{1}{N} \sum_{j \in {\cal N} \backslash \{1\}} \log \left[ 1 + \exp \left( \alpha - \gamma D(\theta_1, \theta_j) \right) \right] \\
&= \frac{2}{C \gamma} \left[ \textrm{Li}_2(-e^{\alpha}) - \textrm{Li}_2(-e^{\alpha-C\gamma/2}) \right].
\end{align*}

The average link density and distance between neighbors are given by

\begin{align*}
\mu_{\textrm{cont}}(\alpha, \gamma) &= \frac{2}{C \gamma} \left[ \log(1 + e^{\alpha}) - \log(1+e^{\alpha-C\gamma/2}) \right], \\
\eta_{\textrm{cont}}(\alpha, \gamma) &= \frac{ \frac{2}{C \gamma^2} \left[ \textrm{Li}_2(-e^{\alpha}) - \textrm{Li}_2(-e^{\alpha-C\gamma/2}) \right] - \frac{1}{\gamma} \log(1+e^{\alpha - C \gamma/2})}{ \frac{2}{C \gamma} \left[ \log(1 + e^{\alpha}) - \log(1+e^{\alpha-C\gamma/2}) \right] }.
\end{align*}

§.§ Network size preferences

The Hamiltonian for the trade model is calculated in similar way to the one in Section <ref>. In particular, it is given by

\begin{align*}
H_N(g; v_0, \gamma, \alpha, {\bf y}, p) = \sum_{r \in {\cal C}} \sum_{i \in {\cal N}_r} \Bigg\{ & \sum_{s \in {\cal C}} \underbrace{\frac{1}{2} \left[- v_0 + \gamma D(r,s) - \alpha (y_r + y_s) + \frac{\alpha p}{2 N} \right]}_{-h_N(r,s)} l_i^s(g) \\
&+ \frac{\alpha p}{2 N} \left( \sum_{s \in {\cal C}} l_i^s(g) \right)^2 \Bigg\}.
\end{align*}

The log-likelihood function in this case is

\begin{align*}
\ell(\Omega) = \sum_{r \in {\cal C}} \sum_{s \in {\cal C}} \left\{ (v_0-D_{rs}(\Omega)) \left( \sum_{i \in {\cal N}_r} l_{is}(g) \right) - N_r(N_s - \delta_{rs}) \log\left(1+e^{v_0-D_{rs}(\Omega)}\right) \right\}
\end{align*}