Jalan, Chakrabarti, and Sarkar

Incentive-Aware Models of Dynamic Financial Networks

Incentive-Aware Models of Dynamic Financial Networks

Akhil Jalan Department of Computer Science, University of Texas at Austin,
Austin, TX 78712<EMAIL_ADDRESS>Deepayan Chakrabarti McCombs School of
Business, University of Texas at Austin, Austin, TX 78712<EMAIL_ADDRESS>Purnamrita Sarkar Department of Statistics and Data Science, University of
Texas at Austin, Austin, TX 78712<EMAIL_ADDRESS>
Financial networks help firms manage risk but also enable financial shocks to
spread. Despite their importance, existing models of financial networks have
several limitations. Prior works often consider a static network with a simple
structure (e.g., a ring) or a model that assumes conditional independence
between edges. We propose a new model where the network emerges from
interactions between heterogeneous utility-maximizing firms. Edges correspond
to contract agreements between pairs of firms, with the contract size being
the edge weight. We show that, almost always, there is a unique “stable
network.” All edge weights in this stable network depend on all firms’
beliefs. Furthermore, firms can find the stable network via iterative pairwise
negotiations. When beliefs change, the stable network changes. We show that
under realistic settings, a regulator cannot pin down the changed beliefs that
caused the network changes. Also, each firm can use its view of the network to
inform its beliefs. For instance, it can detect outlier firms whose beliefs
deviate from their peers. But it cannot identify the deviant belief: increased
risk-seeking is indistinguishable from increased expected profits. Seemingly
minor news may settle the dilemma, triggering significant changes in the
network.

financial networks; utility maximization; heterogeneous agents; dynamic games

##  1 Introduction

The financial crisis of $2008$ showed the need for mitigating systemic risks
in the financial system. There has been much recent work on categorizing such
risks (Glasserman and Young 2015, 2016, Birge 2021). While the causes of
systemic risk are varied, they often share one feature. This shared feature is
the network of interconnections between firms via which problems at one firm
spread to others. One example is the weighted directed network of debt between
firms. If one firm defaults on its debt, its creditor firms suffer losses.
Some creditors may be forced into default, triggering a default cascade
(Eisenberg and Noe 2001). Another example is the network implicitly formed by
firms holding similar assets. Here, sales by one firm can lead to mark-to-
market valuation losses at other firms. This can lead to fire sales of assets
(Caballero and Simsek 2013, Cont and Minca 2016, Feinstein 2020, Feinstein and
Søjmark 2021).

The structure of inter-firm networks plays a vital role in the financial
system. Small changes in network structure can lead to jumps in credit spreads
in Over-The-Counter (OTC) markets (Eisfeldt et al. 2021). Network density and
diversification affect how robust the networks are to shocks and how such
shocks propagate (Elliott et al. 2014, Acemoglu et al. 2015). The network
structure also affects the design of regulatory interventions (Papachristou
and Kleinberg 2022, Calafiore et al. 2022).

Despite its importance, many prior works use simplistic descriptions of the
network structure. For instance, they often assume that the network is fixed
and observable. But only regulators may have access to the full network.
Furthermore, shocks or regulatory interventions can change the network. Others
assume that the network belongs to a general class, such as ring networks or
core-periphery networks (Caballero and Simsek 2013, Amini et al. 2015). But
financial networks exhibit complex structure (Peltonen et al. 2014, Eisfeldt
et al. 2021). Leverage levels, size heterogeneity, and other factors can
affect the network topology (Glasserman and Young 2016). Hence, there is a
need for models to help reason about financial networks.

In this paper, we design a model for a weighted network of contracts between
agents, such as firms, countries, or individuals. The contracts can be
arbitrary, and the edge weights denote contract sizes. In designing the model,
we have two main desiderata. First, the model must account for heterogeneity
between firms. This follows from empirical observations that differences in
dealer characteristics lead to different trade risk exposures in OTC markets
(Eisfeldt et al. 2021). Second, each firm seeks to maximize its utility and
selects its contract sizes accordingly. In effect, each firm tries to optimize
its portfolio of contracts (Markowitz 1952). The model must reflect this
behavior. From this starting point, we ask the following questions:

  1. 1.

How does a network emerge from interactions between heterogeneous utility-
maximizing firms?

  2. 2.

How does the network respond to regulatory interventions?

  3. 3.

How can the network structure inform the beliefs that firms hold about each
other?

Next, we review the relevant literature.

Imputing financial networks. We often have only partial information about the
structure of a financial network. For example, we may know the total liability
of each bank in a network. From this, we want to reconstruct all the inter-
bank liabilities (Squartini et al. 2018). One approach is to pick the network
that minimizes KL divergence from a given input matrix (Upper and Worms 2004).
Mastromatteo et al. (2012) use message-passing algorithms, while Gandy and
Veraart (2017) use a Bayesian approach. But such random graph models often do
not reflect the sparsity and power-law degree distributions of financial
networks (Upper 2011). Furthermore, these models do not account for the
utility-maximizing behavior of firms.

General-purpose network models. The simplest and most well-explored network
model is the random graph model (Gilbert 1959, Erdös and Rényi 1959). Here,
every pair of nodes is linked independently with probability $p$.
Generalizations of this model allow for different degree distributions and
edge directionality (Aiello et al. 2000, Duijn et al. 2004). Exponential
random graph models remove the need for independence, but parameter estimation
is costly (Frank and Strauss 1986, Wasserman and Pattison 1996, Hunter and
Handcock 2006, Caimo and Friel 2011). Several models add node-specific latent
variables to model the heterogeneity of nodes. For example, in the Stochastic
Blockmodel and its variants, nodes are members of various latent communities.
The community affiliations of two nodes determine their probability of linkage
(Holland et al. 1983, Wang and Wong 1987, Chakrabarti et al. 2004, Airoldi et
al. 2008, Mao et al. 2018). Instead of latent communities, Hoff et al. (2002)
assign a latent location to each node. Here, the probability of an edge
depends on the distance between their locations.

All the latent variable models assume conditional independence of edges given
the latent variables. But in financial networks, contracts between firms are
not independent. Two firms will sign a contract only if the marginal benefit
of the new contract is higher than the cost. This cost/benefit tradeoff
depends on all other contracts signed with other firms. Unlike our model,
existing general-purpose models do not account for such utility-maximization
behavior.

Network games. Games have been widely studied for dynamic routing, path
planning, and so on (Wu et al. 2021, 2022, Peters et al. 2021). In network
games, the payoffs of nodes are dependent on the actions of their neighbors
(Tardos 2004). One well-studied class of network games is linear-quadratic
games. Such games have linear dynamics and quadratic payoff functions. Prior
work has explored the stability of Nash equilibria (Guo and De Persis 2021)
and algorithms to learn the agents’ payoff functions (Leng et al. 2020). But
our model does not yield a linear-quadratic game except in exceptional cases.
Instead, our process involves non-linear rational functions of the beliefs of
firms. Thus, our setting differs from linear-quadratic games. Recently,
network games have been extended to settings where the number of players tends
to infinity (Carmona et al. 2022). However, we only consider finite networks.

Strategic network formation. There is recent work on games designed to build
networks. Prior works prove variants of Nash stability for such games (Calvó-
Armengol and Ilkılıç 2009, Hellmann 2021). We also show that our model
achieves a strong form of Nash stability. But prior works typically consider
unweighted networks. In contrast, we model weighted networks, with weights
denoting contract sizes. Also, we analyze how the network adapts to changing
beliefs of the participant firms. The linkage between firms’ utilities and
their beliefs, and its effect on stability, is not considered in prior work.

There is also work combining network formation processes with network-based
games (Sadler and Golub 2021). The authors seek a Nash equilibrium over the
network and the agents’ actions. In other words, no agent wants to modify the
network or change her actions given the network. We show similar results for
our model. However, our work has several differences. Ours is for a weighted
network, while they only consider unweighted networks. Also, they primarily
focus on the case of “separable games.” In our setting, this corresponds to
the case where all firms are uncorrelated. This is an unrealistic assumption
since firms often face correlated counterparties. The presence of correlations
also lets firms diversify their contracts.

###  1.1 Our Contributions

We develop a new network model of contracts between heterogeneous agents, such
as firms, countries, or individuals. Each agent aims to maximize a mean-
variance utility parametrized by its beliefs. But for two agents to sign a
contract, both must agree to the contract size. For a stable network, all
agents must agree to all their contracts. We show that such constraints are
solvable by allowing agents to pay each other. By choosing prices
appropriately, every agent maximizes its utility in a stable network.

Characterization of stable networks (Section 2): We show that unique stable
networks exist for almost all choices of agents’ beliefs. These networks are
robust against actions by cartels, a condition that we call Higher-Order Nash
Stability. The agents can also converge to the stable network via iterative
pairwise negotiations. The convergence is exponential in the number of
iterations. Hence, the stable network can be found quickly. Finally, we show
how to infer the agents’ beliefs by observing network snapshots over time,
under certain conditions.

The limits of regulation (Section 3): A financial regulator can observe the
entire network but not the agents’ beliefs. Suppose firm $i$ changes its
beliefs about firm $j$. Then the contract size between $i$ and $j$ will
change. Indirectly, other contracts will change too. We show empirically that
in realistic settings, the indirect effects can be as significant as the
direct effects. In such cases, the regulator cannot infer the underlying cause
of changes in the network. Similarly, suppose the regulator intervenes with
one firm, affecting its beliefs. The resulting network changes need not be
localized to that firm’s neighborhood in the network. Thus, targeted
interventions can have strong ripple effects. Broad-based interventions aimed
at increasing stability can also have adverse effects. For instance,
increasing margin requirements may make stable networks impossible.

Outlier detection by firms (Section 4): A firm $i$ can observe its contracts
with counterparties but not the entire network. Suppose another firm $j$ (say,
a real-estate firm) has beliefs that are very different from its peers. Then,
we prove that under certain conditions, $j$’s contract size with $i$ is also
an outlier compared to other real-estate firms. So, firm $i$ can use the
network to detect outliers and update its beliefs. But suppose all real-estate
firms change their beliefs. This changes all their contract sizes without
creating outliers. We show that $i$ cannot determine the cause of this change.
For example, firm $i$ would observe the same change whether all real-estate
firms had become more risk-seeking or profitable. However, firm $i$ may want
to increase its exposure if they are more profitable but reduce exposure if
they are more risk-seeking. Since the data cannot identify the proper action,
firm $i$ remains uncertain. Exogenous, seemingly insignificant information may
persuade firm $i$ one way or another. Thus, minor news may trigger drastic
changes in the network.

Notation. We use lowercase letters, with or without subscripts, to denote
scalars (e.g., $c,\gamma_{i}$). Lowercase bold letters denote vectors
($\bm{\mu}_{i},\bm{w}$), and uppercase letters denote matrices
($W,P,\Sigma_{i}$). We use $\bm{\mu}_{i;j}$ to refer to the $j^{th}$ component
of the vector $\bm{\mu}_{i}$, and $\Sigma_{i;jk}$ for the $(j,k)$ cell of
matrix $\Sigma_{i}$. We use $\bm{v}^{T}$ to denote the transpose of a vector
$\bm{v}$, and $\|\cdot\|_{p}$ to denote the $\ell_{p}$ norm of a vector or
matrix. We say $A\succeq 0$ if $A$ is positive semidefinite, $A\succ 0$ if it
is positive definite, and $A\succeq B$ if $A-B\succeq 0$. The vectors
$\bm{e}_{1},\ldots,\bm{e}_{n}$ denote the standard basis in $\mathbb{R}^{n}$,
and $I_{n}$ is the $n\times n$ identity matrix. If $A\in\mathbb{R}^{m\times
n},B\in\mathbb{R}^{p\times q}$ then $A\otimes B\in\mathbb{R}^{mp\times nq}$
denotes their tensor product: $(A\otimes B)_{ij,k\ell}=A_{ik}B_{j\ell}$. For
an appropriate matrix $M$, $\textrm{tr}(M)$ calculates its trace,
$\textrm{vec}(M)$ vectorizes $M$ by stacking its columns into a single vector,
and $\textrm{uvec}(M)$ vectorizes the upper-triangular off-diagonal entries of
$M$. For an integer $r\geq 1$, we use $[r]$ to denote the set of integers
$[r]\vcentcolon=\\{1,2,\dots,r\\}$.

##  2 The Proposed Model

We consider a weighted network $W\in\mathbb{R}^{n\times n}$ between $n$ agents
(such as firms, countries, or individuals). The element $W_{ij}$ represents
the size of a contract between agents $i$ and $j$. We make no assumptions
about the content of the contract. For instance, the contract could be a
credit default swap, a stock swap, or an insurance contract. Since contracts
need mutual agreement, $W_{ij}=W_{ji}$. We take $W_{ii}$ to represent $i$’s
investment in itself. Note that a negative contract ($W_{ij}=W_{ji}<0$) is a
valid contract that reverses the content of a positive contract. For example,
if a positive contract is a derivative trade between two firms, the negative
contract swaps the roles of the two firms.

Let $\bm{w}_{i}$ denote the $i^{th}$ column of $W$ (i.e.,
$\bm{w}_{i;j}=W_{ji}$ for all $j$). Each agent $i$ would prefer to set its
contract sizes $\bm{w}_{i}$ to maximize its utility. But other agents will
typically have different preferences. So, to achieve an agreement about the
contract size, agents can pay each other. We denote by $P_{ji}$ the price per
unit contract that $i$ pays to $j$, for a total payment of $P_{ji}\cdot
W_{ji}$. If $P_{ji}<0$, then $j$ pays $i$. Since payments are zero-sum and
$W_{ji}=W_{ij}$, we must have $P_{ji}=-P_{ij}$.

Each contract yields a stochastic payout, and agents have beliefs about these
payouts. We represent agent $i$’s beliefs by a vector ${\bm{\mu}}_{i}$ of
expected returns and a covariance matrix $\Sigma_{i}\succ 0$. Specifically,
let $X_{ij}$ be a random variable representing the payout obtained by agent
$i$ from a unit-sized contract with agent $j$. Then, agent $i$ believes that
$E[X_{ij}]={\bm{\mu}}_{i;j}$ and $Cov(X_{ij},X_{ik})=\Sigma_{i;jk}$. Note that
we do not assume that the contracts are zero-sum or that the beliefs are
correct, even approximately. Thus, the overall expected return from all
contracts of $i$ is $\bm{w}_{i}^{T}(\bm{\mu}_{i}-P\bm{e}_{i})$, and the
variance of the overall return is $\bm{w}_{i}^{T}\Sigma_{i}\bm{w}_{i}$. We
assume that each agent has a mean-variance utility (Markowitz 1952):

$\displaystyle\text{agent $i$'s utility }g_{i}(W,P)$
$\displaystyle:=\bm{w}_{i}^{T}(\bm{\mu}_{i}-P\bm{e}_{i})-\gamma_{i}\cdot\bm{w}_{i}^{T}\Sigma_{i}\bm{w}_{i},$
(1)

where $\gamma_{i}>0$ is a risk-aversion parameter. Homogeneity of risk
aversion has been observed in game settings (Metrick 1995), surveys (Kimball
et al. 2008), and investment portfolios (Paravisini et al. 2017) (see also Ang
(2014)). Hence, we expect all $(\gamma_{i})_{i\in[n]}$ to be similar. Note
that Eq. 1 ignores costs for contract formation; we will consider these in
Section 3.1.

The model above allows contracts between all pairs of agents. But some edges
may be prohibited due to logistical or legal reasons. For each agent $i$, let
$J_{i}\subseteq[n]$ denote the ordered set of agents with whom $i$ can form an
edge. So, if $k\notin J_{i}$ (and hence $i\notin J_{k}$), we have
$W_{ik}=W_{ki}=P_{ik}=P_{ki}=0$. Similarly, if $i\notin J_{i}$, then self-
loops are prohibited ($W_{ii}=P_{ii}=0$).

We will encode these constraints in the binary matrix
$\Psi_{i}\in\mathbb{R}^{|J_{i}|\times n}$ where $\Psi_{i;jk}=1$ if $k$ is the
$j^{th}$ element of $J_{i}$, and $\Psi_{i;jk}=0$ otherwise. In other words,
$\Psi_{i}$ is obtained from $I_{n}$ by deleting the rows corresponding to the
prohibited counterparties of $i$. Thus, for any $\bm{v}\in\mathbb{R}^{n}$,
$\Psi_{i}\bm{v}$ selects the elements of $\bm{v}$ corresponding to $J_{i}$. If
all edges are allowed, we have $\Psi_{i}=I_{n}$ for all $i$.

######  Definition 2.1 (Network Setting)

A network setting $(\bm{\mu}_{i},\gamma_{i},\Sigma_{i},\Psi_{i})_{i\in[n]}$
captures the beliefs and constraints of $n$ agents. When there are no
constraints (i.e., all edges are allowed), we drop the $\Psi_{i}=I_{n}$ terms
to simplify the exposition. Finally, we will use $M\in\mathbb{R}^{n\times n}$
to denote a matrix whose $i^{th}$ column is $\bm{\mu}_{i}$, and $\Gamma$ to
denote a diagonal matrix with $\Gamma_{ii}=\gamma_{i}$.

###  2.1 Characterizing Stable Points

In the above model, every agent tries to optimize its own utility (Eq. 1). We
now characterize the conditions under which selfish utility-maximization leads
to a stable network.

######  Definition 2.2 (Feasibility)

A tuple $(W,P)$ is feasible if $W=W^{T}$, $P=-P^{T}$, and $W$ and $P$ obey the
constraints encoded in $(\Psi_{i})_{i\in[n]}$.

######  Definition 2.3 (Stable point)

A feasible $(W,P)$ is stable if each agent achieves its maximum possible
utility given prices $P$:

$\displaystyle g_{i}(W,P)=\max_{\text{feasible}(W^{\prime},P)\text{ under
}\\{\Psi_{i}\\}}g_{i}(W^{\prime},P)\quad\forall i\in[n].$

(a) No price payments allowed

(b) Firm $2$ pays $5/3$ per contract

(c) Network

Figure 1: Example of a stable point for two firms: (a) When firms are not
allowed to pay each other, they may be unable to agree to a contract, even if
trading improves their utilities. (b) By allowing for prices, both firms can
agree on a contract size. In effect, firm $2$ shares its utility with firm $1$
to achieve agreement. (c) The stable network is shown.

###### Example 2.4

Suppose we only have two firms with the following setting:

$\displaystyle\text{mean beliefs }M$ $\displaystyle=\begin{bmatrix}0&3\\\
1&4\end{bmatrix}$ $\displaystyle\text{covariance }\Sigma_{1}=\Sigma_{2}$
$\displaystyle=\begin{bmatrix}1&0\\\ 0&2\end{bmatrix}$
$\displaystyle\text{risk aversion }\gamma_{1}=\gamma_{2}$ $\displaystyle=1.$

So, both firms perceive a benefit from trading ($M_{12}>0,M_{21}>0$). If
trading is disallowed, the optimum $W$ is diagonal with $W_{11}=0$ and
$W_{22}=1$ (and $P$ is the zero matrix). The corresponding utilities are $0$
for firm $1$ and $2$ for firm $2$. Suppose we allow trading but do not allow
pricing (Figure 1(a)). Then, the two firms can each improve their utility by
trading, but achieve their optimum utilities at different contract sizes.
Hence, they may be unable to agree to a contract. In Figure 1(b), firm $2$
pays firm $1$ a specially chosen price of $5/3$ per unit contract. At this
price, both firms achieve their optimum utilities at the same contract size
$W_{12}=W_{21}=2/3$. Hence, they can agree to a contract. By paying the price,
firm $2$ shares some of its utility with firm $1$ to achieve agreement on the
contract. This choice of $W$ and $P$ is a stable point (Figure 1(c)). The
following results show that this is the only stable point.$\hfill\Box$

Define
$Q_{i}=\Psi_{i}^{T}(2\gamma_{i}\Psi_{i}\Sigma_{i}\Psi_{i}^{T})^{-1}\Psi_{i}$.
When all edges are allowed, $\Psi_{i}=I_{n}$ and
$Q_{i}=(2\gamma_{i}\Sigma_{i})^{-1}$. Let $F=\\{(i,j):1\leq i<j\leq
n,\Psi_{i}\bm{e}_{j}\neq\bm{0}\\}$ denote the ordered pairs $i<j$ where
$P_{ij}$ is allowed to be non-zero. Note that $|F|\leq n(n-1)/2$. For any
$n\times n$ matrix $X$, let $\textrm{uvec}(X)_{F}\in\mathbb{R}^{|F|}$ be a
vector whose entries are the ordered set $\\{X_{ij}\mid(i,j)\in F\\}$.

######  Theorem 2.5 (Existence and Uniqueness of Stable Point)

Define $n\times n$ matrices $A$, $B_{(i,j)}$, and $C_{(i,j)}$ as follows:

$\displaystyle A_{ij}$ $\displaystyle=\bm{e}_{i}^{T}Q_{j}M\bm{e}_{j},$
$\displaystyle B_{(i,j)}$ $\displaystyle=\bm{e}_{i}\bm{e}_{j}^{T}Q_{i},$
$\displaystyle C_{(i,j)}$
$\displaystyle=(B_{(i,j)}-B_{(j,i)})-(B_{(i,j)}-B_{(j,i)})^{T}.$

Let $Z_{F}$ be the $|F|\times|F|$ matrix whose rows are the ordered sets
$\\{\textrm{uvec}(C_{(i,j)})_{F}\mid(i,j)\in F\\}$. Then, we have the
following:

  1. 1.

A stable point $(W,P)$ under $\\{\Psi_{i}\\}$ exists if
$\textrm{uvec}(A-A^{T})_{F}$ lies in the column space of $Z_{F}$.

  2. 2.

A unique stable point always exists if $Z_{F}$ is full rank.

A special case of the above is when all agents have the same covariance
($\Sigma_{i}=\Sigma$ for all $i\in[n]$). One example is when the risk of a
contract is primarily counterparty risk (so $\Sigma_{i;jk}$ depends on $j$ and
$k$, not $i$) and there is reliable public data on such risks (say, via credit
rating agencies). We can then characterize the stable network as follows.

######  Corollary 2.6 (Shared $\Sigma$, all edges allowed)

Suppose $\Sigma_{i}=\Sigma$ and $\Psi_{i}=I_{n}$ for all $i\in[n]$. Let
$(\lambda_{i},\bm{v}_{i})$ denote the $i^{th}$ eigenvalue and eigenvector of
$\Gamma^{-1/2}\Sigma\Gamma^{-1/2}$. Then, the network $W$ can be written in
two equivalent ways:

$\displaystyle\textrm{vec}(W)$
$\displaystyle=\frac{1}{2}(\Gamma\otimes\Sigma+\Sigma\otimes\Gamma)^{-1}\textrm{vec}(M+M^{T}),$
$\displaystyle W$
$\displaystyle=\Gamma^{-1/2}\left(\sum_{i=1}^{n}\sum_{j=1}^{n}\frac{\bm{v}_{i}^{T}\Gamma^{-1/2}(M+M^{T})\Gamma^{-1/2}\bm{v}_{j}}{2(\lambda_{i}+\lambda_{j})}\bm{v}_{i}\bm{v}_{j}^{T}\right)\Gamma^{-1/2}.$

Next, we show that most settings have unique stable points, and such stable
networks are robust.

######  Theorem 2.7 (Unique Stable Points are Common)

For any network setting
$S=(\bm{\mu}_{i},\gamma_{i},\Sigma_{i},\Psi_{i})_{i\in[n]}$ and any
$\epsilon>0$, there exist uncountably many network settings
$S^{\prime}=(\bm{\mu}_{i},\gamma_{i},\Sigma_{i}^{\prime},\Psi_{i})_{i\in[n]}$
such that $\|\Sigma_{i}^{\prime}-\Sigma_{i}\|<\epsilon$ for all $i\in[n]$, and
$S^{\prime}$ has a unique stable point.

For two feasible tuples $(W_{1},P_{1})$ and $(W_{2},P_{2})$, let
$(W_{2},P_{2})$ dominate $(W_{1},P_{1})$ if for all
$i\in[n],g_{i}(W_{1},P_{1})\leq g_{i}(W_{2},P_{2})$, with at least one
inequality being strict.

######  Theorem 2.8 (Stable points cannot be dominated)

Suppose a stable point $(W,P)$ exists. Then, there is no feasible
$(W^{\prime},P^{\prime})$ that dominates $(W,P)$.

The stable point obeys a strong form of robustness that we call Higher-Order
Nash Stability. This strengthens the notions of pairwise stability (Hellmann
2013) and pairwise Nash (Calvó-Armengol and Ilkılıç 2009, Sadler and Golub
2021) by allowing for agent coalitions, instead of just considering pairs of
agents. It is also closely related to the concept of Strong Nash equilibrium,
which strengthens Nash equilibrium by requiring that no subset of agents can
deviate at equilibrium without at least one agent being worse off (Mazalov and
Chirkova 2019).

######  Definition 2.9 (Agent Action)

At a given feasible point $(W,P)$, an “action” by agent $i$ is the ordered set
$(w_{i,j}^{\prime},p_{i,j}^{\prime})_{j\in J_{i}}$, where $J_{i}\subseteq[n]$
is the set of permissible edges for agent $i$. The action represents a set of
proposed changes to $i$’s existing contracts. Each agent $j\in J_{i}$ responds
as follows:

  1. 1.

If the new $(w_{ij}^{\prime},p_{ij}^{\prime})$ raises $j$’s utility, then $j$
agrees to the revised contract and price.

  2. 2.

Otherwise, $i$ must either keep the existing contract or cancel it
($w_{ij}=p_{ij}=0$). We assume that $i$ cancels the contract if and only if
this strictly increases $i$’s utility.

We call the shifted $(W^{\prime},P^{\prime})$ the resulting network.

######  Definition 2.10 (Higher-Order Nash Stability)

A feasible $(W,P)$ is Higher-Order Nash Stable if:

  1. 1.

Nash equilibrium: No agent $i$ has an action such that the resulting network
$(W^{\prime},P^{\prime})$ is strictly better for $i$.

  2. 2.

Cartel robustness: For any proper subset $S\subset[n]$ of agents, there is no
feasible point $(W^{\prime},P^{\prime})$ that differs from $(W,P)$ only for
indices $\\{i,j\\}$ with $i\in S,j\in S$ such that all agents in $S$ have
higher utility under $(W^{\prime},P^{\prime})$ than $(W,P)$.

######  Theorem 2.11 (Higher-Order Nash Stability)

Any stable point $(W,P)$ is Higher-Order Nash Stable.

###  2.2 Finding the Stable Point via Pairwise Negotiations

To compute the stable point in Theorem 2.5, we must know the beliefs of all
agents. But in practice, contracts are set iteratively by negotiations among
pairs of agents. We will now formalize the process of pairwise negotiations
and characterize the conditions under which such negotiations can converge to
the stable point.

We propose a multi-round pairwise negotiation process. In round $t+1$, every
pair of agents $i$ and $j$ update the price $P_{ij}(t)$ to $P_{ij}(t+1)$ (and
hence $P_{ji}(t)$ to $P_{ji}(t+1)$) as follows. First, they agree to a price
$P^{\prime}_{ij}$ between themselves, assuming optimal contract sizes with all
other agents at the current prices $P(t)$. In other words, we assume that the
other agents will accept the prices in $P(t)$ and the contract sizes preferred
by $i$ and $j$. Under this condition, $P^{\prime}_{ij}$ is the price at which
$i$’s optimal contract size with $j$ is also $j$’s optimal size with $i$. All
pairs of agents calculate these prices simultaneously. We create a new price
matrix $P^{\prime}$ from these prices. Then, we set $P(t+1)=(1-\eta)P(t)+\eta
P^{\prime}$, where $\eta\in(0,1)$ is a dampening factor chosen to achieve
convergence. Algorithm 1 shows the details.

Next, we show how the price $P^{\prime}_{ij}$ can be computed. Slightly
abusing notation, we use $P^{\prime}$ in the next proposition to denote a
matrix that is identical to $P(t)$ except for the pair $(i,j)$.

######  Proposition 2.12 (Price after Pairwise Negotiation)

Consider a network setting
$(\bm{\mu}_{i},\gamma_{i},\Sigma_{i},\Psi_{i})_{i\in[n]}$. Let $Q_{i}$ be as
in Theorem 2.5. Given a price matrix $P=-P^{T}$ and a pair of firms $(i,j)$
that are permitted to trade, let $P^{\prime}$ be another skew-symmetric price
matrix such that (a) $P^{\prime}$ differs from $P$ only in the cells $(i,j)$
and $(j,i)$, (b) $i$ and $j$ both maximize their utility at the same contract
size under $P^{\prime}$, and (c) $i$ and $j$ can choose their optimal contract
sizes with all other agents given these prices. Then,

$\displaystyle P^{\prime}_{ij}$
$\displaystyle=\frac{1}{Q_{i;j,j}+Q_{j;i,i}}\Big{(}\bm{e}_{i}^{T}Q_{j}(M-P)\bm{e}_{j}-\bm{e}_{j}^{T}Q_{i}(M-P)\bm{e}_{i}\Big{)}+P_{ij}$

Algorithm 1 Pairwise Negotiations

1:procedure Pairwise($\eta\in(0,1)$)

2: $t\leftarrow 0$

3: $P(0)\leftarrow\text{ any skew-symmetric matrix}$

4: while $P(t)$ has not converged do

5: $\forall i,j\in[n],P^{\prime}_{ij}\leftarrow$ pairwise-negotiated price for
$(i,j)$ (Prop. 2.12)

6: $P(t+1)\leftarrow(1-\eta)P(t)+\eta P^{\prime}$

7: $t\leftarrow t+1$

8: end while

9:end procedure

Now, we will show that Algorithm 1 converges. First, we define global
asymptotic stability (following Callier and Desoer (1994)).

######  Definition 2.13 (Global Asymptotic Stability)

The pairwise negotiation process is globally asymptotically stable for a given
network setting and dampening factor $\eta$ if, for any initial price matrix
$P(0)$, there exists a matrix $P^{\star}$ such that the sequence of price
matrices $P(t)$ converges to $P^{\star}$ in Frobenius norm:
$\lim\limits_{t\to\infty}\|P(t)-P^{\star}\|_{F}=0$.

When pairwise negotiations are globally asymptotically stable, the limiting
matrix $P^{\star}$ must be skew-symmetric since each $P(t)$ is skew-symmetric.
Also, since prices are updated whenever two agents disagree on the size of the
contract between them, all agents agree on their contract sizes at
$P^{\star}$. Hence, $P^{\star}$ must be a stable point for the given network
setting. Most network settings have a unique stable point (Theorem 2.7).
Hence, we typically expect a single $P^{\star}$ for all starting points
$P(0)$. Now, we show that for a range of $\eta$, pairwise negotiations are
globally asymptotically stable.

######  Theorem 2.14 (Convergence Conditions and Rate)

Let $Q_{i}$ be defined as in Theorem 2.5. Define the following $n^{2}\times
n^{2}$ matrices:

$\displaystyle K$
$\displaystyle\vcentcolon=\sum\limits_{r=1}^{n}\bm{e}_{r}\bm{e}_{r}^{T}\otimes
Q_{r}+Q_{r}\otimes\bm{e}_{r}\bm{e}_{r}^{T}$ $\displaystyle
L_{(i-1)n+j,(i-1)n+j}$ $\displaystyle=Q_{i;j,j}+Q_{j;i,i}\quad\forall
i,j\in[n]$ ($L$ is diagonal).

Let $(L^{\dagger}K)\mid_{R}$ denote the principal submatrix of $L^{\dagger}K$
containing the rows/columns $(i-1)n+j$ such that the edge $(i,j)$ is not
prohibited. Let $\lambda_{\textrm{max}},\lambda_{\textrm{min}}$ be the largest
and smallest eigenvalues of the matrix $(L^{\dagger}K)\mid_{R}$ respectively.
Let $\eta^{*}=\frac{2}{\lambda_{\textrm{max}}}$. Then, we have:

  1. 1.

For all $\eta\in(0,\eta^{*})$, pairwise negotiations with $\eta$ are globally
asymptotically stable.

  2. 2.

For such an $\eta$, the convergence is exponential in the number of rounds
$t$:

$\displaystyle\|P(t)-P^{\star}\|_{F}$
$\displaystyle\leq\frac{\alpha^{t}}{1-\alpha}\cdot\|P(1)-P(0)\|_{F},$
$\displaystyle\text{where }\alpha=\max\\{\lvert
1-\eta\lambda_{\textrm{min}}\rvert,\lvert
1-\eta\lambda_{\textrm{max}}\rvert\\}.$

Here, $P^{\star}$ is the stable point to which the negotiation converges.

###  2.3 Pairwise Negotiations under Random Covariances

So far we have made no assumptions about agents’ beliefs. In this section, we
analyze the convergence of pairwise negotiations for “data-driven” agents.
Specifically, each agent $i$ now estimates its covariance matrix. For this
section only, we will call the covariance matrix $\hat{\Sigma}_{i}$ instead of
$\Sigma_{i}$ to emphasize that it is an estimated quantity.

Suppose each agent $i$ observes $m$ independent data samples. Each sample is a
vector of the returns of unit contracts with all $n$ agents. The samples for
agent $i$ are collected in a matrix $X_{i}\in\mathbb{R}^{n\times m}$, with one
column per sample. The sample covariance of this data is $\hat{\Sigma}_{i}$.

We assume that all agents observe samples from the same return distribution,
which has covariance $\Sigma$. Under a wide range of conditions,
$\|\hat{\Sigma}_{i}-\Sigma\|\to 0$ in probability (Vershynin 2018). Hence, at
convergence, the maximum allowed dampening rate $\eta^{\star}$ in Theorem 2.14
would be a function of $\Sigma$. But for finite sample sizes, each agent’s
$\hat{\Sigma}_{i}$ can be different. Hence, the maximum dampening
$\hat{\eta}^{\star}$ may be less than $\eta^{\star}$. The smaller the
$\hat{\eta}^{\star}$, the worse the rate of convergence of pairwise
negotiations. However, even with a few samples, $\hat{\eta}^{\star}$ is close
to $\eta^{\star}$, as the next theorem shows.

######  Theorem 2.15 (Small Sample Sizes are Sufficient for Fast Convergence)

Suppose that $\|\Sigma\|,\|\Sigma^{-1}\|,\|\Gamma\|,$ and $\|\Gamma^{-1}\|$
are $O(1)$ and all edges are allowed. Also, suppose that each sample column of
$X_{i}$ is drawn independently from a $\mathcal{N}(\bm{0},\Sigma)$
distribution, and ${\hat{\Sigma}_{i}\vcentcolon=(1/m)X_{i}X_{i}^{T}}$. Let
$\hat{\eta}^{\star}$ be the maximum dampening factor using
$(\hat{\Sigma}_{i})_{i\in[n]}$ as defined in Theorem 2.14. Let $\eta^{\star}$
be the dampening factor if $\hat{\Sigma}_{i}$ were replaced by $\Sigma$ for
all $i$. If $m=\left\lceil n\log n\right\rceil$, then for large enough $n$,
${\hat{\eta}^{\star}\geq(1-o(1))\eta^{\star}}$ with probability at least
$1-\exp(-\Omega(n))$.

Theorem 2.15 shows that data-driven agents using a broad range of dampening
factors are still likely to find the stable point via pairwise negotiations.
Furthermore, the amount of data they need is comparable to the number of
agents (up to a logarithmic factor).

###  2.4 Inferring Beliefs from the Network Structure

Suppose we are given a network that lies at a unique stable point as defined
in Theorem 2.5. How can we infer the beliefs of the agents?

#### Non-identifiability of beliefs.

Suppose we are given a network $W$ that is generated using a single covariance
$\Sigma_{i}=\Sigma\succ 0$. We want to infer the agents’ beliefs
$(M,\Gamma,\Sigma)$. By Corollary 2.6,

$\displaystyle\frac{1}{2}\textrm{vec}(M+M^{T})$
$\displaystyle=(\Gamma\otimes\Sigma+\Sigma\otimes\Gamma)\textrm{vec}(W).$

Clearly, the agents’ beliefs can only be specified up to an appropriate
scaling of $M$, $\Gamma$, and $\Sigma$. But even if we specify a scale (e.g.,
$\textrm{tr}[\Gamma]=\textrm{tr}[\Sigma]=1$), for any valid choice of $\Gamma$
and $\Sigma$ we can find a corresponding $M$. Thus, even in the simple setting
of identical covariance and fixed scale, the network $W$ cannot be used to
select a unique combination of the parameters $(M,\Gamma,\Sigma)$. By a
similar argument, we cannot identify the underlying beliefs even if we observe
multiple networks generated using the same $\Sigma$ and $\Gamma$ (but
different $M$). Thus, we need further assumptions in order to infer beliefs.

We consider a sequence of networks $W(t)$ generated over successive timesteps
$t=1,\ldots,T$. We assume that (a) $\Gamma(t)=I$ and $\Sigma_{i}(t)=\Sigma$
for all timesteps, (b) for all $i,j\in[n]$, $M_{ij}(t)$ varies independently
according to a Brownian motion with the same parameters for all $(i,j)$, and
(c) $\textrm{tr}\Sigma=1$. The first assumption is motivated by the
observations in portfolio theory that errors in mean estimation are far more
significant than covariance estimation errors (Chopra and Ziemba 2013). So,
accounting for variations in $\Sigma$ may be less important than variations in
$M$ (but see Remark 2.17 below). The homogeneity of risk aversion was noted in
Section 2, and this justifies setting $\Gamma=I$.

The second assumption is common in the literature on pricing models (Geman et
al. 2001, Bianchi et al. 2013). The third assumption fixes the scale, as
discussed above. Under these assumptions, we can infer $\Sigma$ (and hence
$M(t)$) via a computationally tractable Semidefinite Program (SDP), as shown
next.

###### Proposition 2.16

Finding the maximum likelihood estimator of $\Sigma$ under Assumption 2.4 is
equivalent to the following SDP:

$\displaystyle\min\limits_{\Sigma}\sum\limits_{t=1}^{T-1}\|\Sigma(W(t+1)-W(t))+(W(t+1)-W(t))\Sigma\|_{F}^{2}\text{$\quad\text{
s. t. }\Sigma\succeq 0,\textrm{tr}(\Sigma)=1.$}$

######  Remark 2.17 (Generalization to time-varying $\Sigma$)

We can extend our formulation from a constant covariance $\Sigma$ to one where
the covariance updates at times $0<T_{1}<T_{2}<\ldots<T_{m}<T$. Denote the
covariance in each interval $j$ as $\Sigma_{(j)}$. Then, we can modify the
objective of the SDP above with an additional term that penalizes differences
between successive covariances:
$\nu\cdot\sum_{j}\|\Sigma_{(j+1)}-\Sigma_{(j)}\|$, for some chosen matrix norm
$\|.\|$ and regularization parameter $\nu>0$. This allows the covariance to
change over time while penalizing abrupt changes. Note that the objective
function remains convex. The choice of update times $T_{1},\ldots,T_{m}$ can
be tuned based on heuristics or prior information.

##  3 Insights for Regulators

A financial regulator can observe the network but does not know the firms’
beliefs. The regulator may ask: what changes in beliefs caused recently
observed changes in the network? What are the side effects of different
regulatory interventions? To answer these questions, we need to know how
changes in firms’ beliefs or utility functions affect the network. That is the
subject of this section.

###  3.1 Effect of Friction in Contract Formation

Our model imposes no costs for contract formation. This is reasonable for
large firms where the fixed costs associated with contract negotiations may be
small relative to the contract sizes. But in an overheating market, a
regulator may impose frictions by penalizing large contracts, for example by
increasing margin requirements. We show next that such frictions may backfire,
by ruling out all stable equilibria.

Specifically, we model frictions via an additional $\ell_{1}$ penalty to the
utility of Eq. 1:

$\displaystyle
g_{i}(\bm{w})=\bm{w}^{T}(\bm{\mu}_{i}-P\bm{e}_{i})-\gamma_{i}\bm{w}^{T}\Sigma_{i}\bm{w}-\lambda\|\bm{w}\|_{1},$
(2)

where $\lambda$ is a parameter chosen by the regulator. Larger contract-
related costs correspond to higher values of $\lambda$.

######  Theorem 3.1 (Friction Can Lead to Loss of Equilibrium)

Consider the simple setting where $\Sigma_{i}=I_{n}$, $\Gamma=I$, and there
exists a pair of firms $(i,j)$ such that $\mu_{ij}\neq-\mu_{ji}$. Suppose that
all firms use Eq. 2 as their utility function. Then, if
$\lambda>\min\limits_{k,\ell\in[n]}\frac{\mu_{k\ell}+\mu_{\ell k}}{2}$, there
is no stable equilibrium.

Thus, the addition of frictions may destabilize the system, which is the very
result a regulator aims to prevent by adding such frictions. Furthermore, the
destabilizing level of friction is not known a priori to the regulator, since
it depends on the (hidden) beliefs of firms.

###  3.2 Effect of Changes in the Perceived Risk

Regulatory actions can change the risk perceptions of firms, who then update
their covariances accordingly. If the risk scales upwards, we find smaller
contract sizes, as expected.

######  Theorem 3.2 (Stable Point Scales Inversely with Risk)

Consider a network setting with $\Sigma_{i}=\Sigma$ for all firms. Let $W$ be
the corresponding stable network. If the covariance changes from $\Sigma$ to
$c\Sigma$ for some $c>0$, the stable point changes from $W$ to $(1/c)W$.

But this does not generalize to non-uniform increases in $\Sigma$, as we show
next.

######  Theorem 3.3 (Non-uniform Increases in Risk)

Consider a network setting with $\Sigma_{i}=\Sigma$ and $\gamma_{i}=\gamma$
for all $i$. Suppose the covariance changes as
$\Sigma\mapsto\Sigma^{\prime}\succ\Sigma$. Let $W$ and $W^{\prime}$ be the
stable points under $\Sigma$ and $\Sigma^{\prime}$ respectively. Then,

$\displaystyle\textrm{tr}(M^{T}(W^{\prime}-W))<0,$

where $M$ is the matrix of expected returns.

This shows that an increase in risk leads to a decrease in the weighted
average of the contract sizes. The weights are given by the expected return
beliefs of the firms. However, individual contracts between firms can
increase, as can the norm $\|W\|_{F}$. This is because increases in the
covariance $\Sigma$ may also increase correlations, which can offer better
hedging opportunities. By hedging some risks, larger contract sizes can be
supported.

###  3.3 Effect of Changes in Perceived Expected Returns

Now, we consider shifts in perceived rewards of contracts, as measured by the
matrix $M$ of expected returns from unit contracts. We find that contract
sizes increase if the perceived reward increases, as expected.

######  Theorem 3.4 ($W$ is monotonic with $M$)

Suppose $\Sigma_{i}=\Sigma$ for all firms. Then, for any $i,j\in[n]$, the
value of $W_{ij}$ is monotonic with respect to $M_{ij}$ (the $i^{th}$
component of $\bm{\mu}_{j}$).

Now, a change in $M_{ij}$ may affect not only $W_{ij}$ but also all other
contracts. Can we trace the changes in $W$ back to the underlying changes in
$M$?

######  Definition 3.5 (Source Detection Problem)

Suppose that a financial regulator observes two networks $W$ and $W^{\prime}$,
with the only difference being a small change in a single entry of $M$ (say,
$M_{ij}$). Can the regulator identify the pair $(i,j)$?

One approach is to try to infer all beliefs of all firms, and then identify
the changed belief. But, as discussed in Section 2.4, the beliefs are only
identifiable under extra assumptions and more data. An alternative approach
for the source detection problem is to find the entry $(i,j)$ with the largest
change $|W_{ij}-W^{\prime}_{ij}|$. The intuition is that a change in $M_{ij}$
has a direct effect on $W_{ij}$ and (hopefully weaker) indirect effects on
other contracts. Thus, the source detection problem is closely tied to the
following:

######  Definition 3.6 (Targeted Intervention Problem)

Can a regulator induce a small change in a single entry of $M$ (say, $M_{ij}$)
such that the change in $W_{ij}$ is significantly larger than changes in other
entries of $W$?

######  Proposition 3.7 (Network gradient over expected returns)

Let $\Gamma=I_{n}$, $\Sigma_{i}=\Sigma$ for all $i$, and let $\Sigma$ have the
eigendecomposition $\Sigma=V\Lambda V^{T}$. Then for $i,j,k,\ell\in[n]$,

$\displaystyle\frac{\partial W_{ij}}{\partial
M_{k\ell}}=\frac{1}{2}\sum\limits_{s,t\in[n]}\frac{V_{is}V_{ks}V_{jt}V_{\ell
t}+V_{is}V_{\ell s}V_{jt}V_{kt}}{\lambda_{s}+\lambda_{t}}.$ (3)

Proposition 3.7 shows how the network $W$ changes in response to a change in
the $(k,\ell)$ entry of the expected returns matrix $M$. When all eigenvalues
of $\Sigma$ are equal (that is, $\Sigma\propto I_{n}$), a change in
$M_{k\ell}$ only affects $W_{k\ell}(=-W_{\ell k})$, as can be seen from
Corollary 2.6. But when the eigenvalues are skewed, the terms in Eq. 3
corresponding to the smallest eigenvalues have greater weight. In such
circumstances, the indirect effect of a change in $M_{k\ell}$ on other
$W_{ij}$ can be significant. The following empirical results show that this is
indeed the case.

Figure 2: The success rate for the Source Detection Problem goes to zero as
$\alpha$ and $\epsilon$ increase in a noisy scaled equi-correlation model of
$\Sigma$. We set $n=50$ and $\rho=0.1$.

Empirical Results for the Source Detection Problem (Simulated Data). Here, we
set the covariance $\Sigma=D^{1/2}(R+\mathcal{E})D^{1/2}$, where $D$ is a
diagonal matrix, $R$ a correlation matrix, and $\mathcal{E}$ a noise matrix.
If $\mathcal{E}=0$, then $D_{ii}$ would be the variance of firm $i$. We set
$D_{ii}$ according to a power law: $D_{ii}=i^{-\alpha}$ for an $\alpha>0$.
Larger values of $\alpha$ correspond to greater skew in the variances. We
choose $R$ to be an equi-correlation matrix with $1$ along the diagonal and
$\rho\in(0,1)$ everywhere else. We draw the error matrix $\mathcal{E}$ from a
scaled Wishart distribution:
$\mathcal{E}=\|R\|_{2}\cdot\mathcal{W}(\sqrt{\epsilon}\cdot I_{n},n)/n$ for
some chosen the noise level $\epsilon$. As $\epsilon$ increases, the noise
$\mathcal{E}$ dominates $R$.

Figure 2 shows the success rate of source detection over $1000$ experiments
for various values of $(\epsilon,\alpha)$ for $\rho=0.1$. As $\alpha$
increases, the variances become more skewed and the source detection can fail
even with $\epsilon=0$ noise. When $\epsilon$ grows, the success rate for the
source detection problem goes to zero. This suggests that skew combined with
noise makes source detection difficult. We observe similar results for real-
world choices of $\Sigma$, as we show next.

Empirical Results for the Source Detection Problem (Real-World Data). We
consider two datasets: (a) a trade network between $46$ large economies (OECD
2022), and (b) a simulated network between $96$ portfolio managers following
various Fama-French strategies Fama and French (2015). For each dataset, we
construct a “ground-truth” covariance $\Sigma$ using all available data (the
details are in in Appendix 8). Then, using $m$ independent samples
$\bm{x}_{i}\sim\mathcal{N}(0,\Sigma)$, we build a “data-driven” covariance
$\hat{\Sigma}=(1/m)\sum_{i=1}^{m}\bm{x}_{i}\bm{x}_{i}^{T}$. We use this
$\hat{\Sigma}$ to construct the financial network.

(a) Simulated network of $96$ portfolio managers.

(b) $46$-country (OECD) trade network.

Figure 3: The success rate for the Source Detection Problem scales
monotonically with the number of samples used to construct the data-driven
covariance matrix $\hat{\Sigma}$.

Figure 3 shows the success rate over $500$ experiments for various choices of
the sample size $m$. The success rate increases monotonically with $m$. The
reason for this behavior lies in the spectra of $\Sigma$ and $\hat{\Sigma}$.
We find that in both datasets, the largest and smallest eigenvalues of
$\Sigma$ are separated by several orders of magnitude. This gap becomes even
more extreme in the data-driven $\hat{\Sigma}$; the fewer the samples $m$, the
greater the gap (see Figure 4). In fact, we observe that the smallest
eigenvalue of $\hat{\Sigma}$ is much smaller than the second-smallest
eigenvalue: $\lambda_{n}\ll\lambda_{n-1}$. Zhao et al. (2019) make similar
observations.

(a) Simulated network of $96$ portfolio managers

(b) $46$-country (OECD) trade network

Figure 4:  The eigenvalues of estimated covariance matrices are skewed, and
the degree of skew depends on the number of samples. As the sample size
decreases, so does the smallest eigenvalue $\lambda_{n}$ and the ratio
$\lambda_{n}/\lambda_{n-1}$.

In summary, the experiments on both simulated and real-world datasets
highlight the difficulty of source detection and targeted intervention in
realistic networks. The reason is the skew in the eigenvalues coupled with
noise, which affects the eigenvectors. Skewed eigenvalues correspond to trade
combinations (eigenvectors) that are seemingly low-risk. Hence, firms use such
trades to diversify. This implies that these eigenvectors have an outsized
effect on the network, and how it responds to local changes. Intuitively, if
these eigenvectors are “random,” the effect of a changed belief $M_{k\ell}$
affects the rest of the network randomly. Hence, the direct effects on
$W_{k\ell}$ may be less than the indirect effects on other $W_{ij}$. We
explore this theoretically in Appendix 7.15.

##  4 Insights for Firms

Until now, we have treated the beliefs of firms as fixed and exogenous. In
this section, we consider how a firm can use its contracts to gain insights
into other firms and update its beliefs.

For instance, suppose a firm $j$ faces a crisis, e.g., a looming debt payment
that may make it insolvent. The firm may then become risk-seeking (i.e., lower
its $\gamma_{j}$), hoping that the risks pay off. Another firm $i$ may be
unaware of the crisis, so $i$’s risk perceptions (perhaps based on historical
data) would be outdated. Can firm $i$ infer the lower $\gamma_{j}$, solely
from $i$’s contracts $\bm{w}_{i}$ with all firms? What if a group of firms
become risk-seeking, and not just one firm?

###  4.1 Detecting Outlier Firms

Intuitively, firm $i$ will try to answer these questions by comparing the
behavior of firm $j$ against other similar firms. We formalize this by
assuming that each firm $j$ belongs to a community $\theta_{j}$, e.g.,
banking, or real-estate, or insurance, etc. The community of each firm is
publicly known. Firms in the same community are perceived to have similar
return distributions:

$\displaystyle M_{ij}$
$\displaystyle=f(\theta_{i},\theta_{j})+\epsilon^{\prime}_{\theta_{i},j},$
$\displaystyle\Sigma_{ij}$ $\displaystyle=g(\theta_{i},\theta_{j}),$
$\displaystyle\gamma_{i}$ $\displaystyle=h(\theta_{i})+\epsilon_{i}$ (4)

for some unknown deterministic functions $f(.)$, $g(.)$, and $h(.)$ and random
error terms $\epsilon_{i}$ and $\epsilon^{\prime}_{\theta_{i},j}$. We also
assume that all firms use the same covariance $\Sigma$.

Now, suppose one firm $j$ is an outlier, with very different beliefs from
other firms in its community. For firm $i$ to detect the outlier firm $j$, the
contract size $W_{ij}$ should deviate from a cluster of contracts
$\\{W_{ij^{\prime}}\mid\theta_{j^{\prime}}=\theta_{j}\\}$ of other firms from
the same community as firm $j$. Now, outlier detection methods often assume
independent datapoints. In our model, all contracts are dependent. But we can
still do outlier detection if the contracts are appropriately exchangeable. We
prove below this is the case.

###### Definition 4.1

An intra-community permutation is a permutation $\pi:[n]\to[n]$ such that
$\pi(i)=j$ implies that $\theta_{i}=\theta_{j}$.

###### Proposition 4.2

Suppose $M,\Sigma,\Gamma$ exhibit community structure (Eq. 4), and all the
error terms $(\epsilon_{i})_{i\in[n]}$ and
$(\epsilon^{\prime}_{\theta_{i},j})_{i,j\in[n]}$ are independent and
identically distributed. Let $\pi:[n]\to[n]$ be any intra-community
permutation, and let $\Pi:\mathbb{R}^{n}\to\mathbb{R}^{n}$ be the
corresponding column-permutation matrix: $\Pi(\bm{e}_{i})=\bm{e}_{\pi(i)}$.
Then, $W$ and $\Pi^{T}W\Pi$ are identically distributed.

###### Corollary 4.3

Let $j_{1},\dots,j_{m}\in[n]$ belong to the same community:
$\theta_{j_{1}}=\dots=\theta_{j_{m}}$. Suppose the conditions of Proposition
4.2 hold. Then, for any $i\in[n]$, the joint distribution of
$(W_{i,j_{1}},\ldots,W_{i,j_{m}})$ is exchangeable.

Figure 5:  Success rate for detecting outlier risk-seeking firms. Detection is
more successful when there are fewer firms and when the risk-seeking firm’s
$\gamma_{\textrm{outlier}}$ is more standard deviations away from the $\gamma$
of the normal firms.

Empirical Results for Outlier Detection. We generate community-based networks
(Eq. 4) such that $\gamma_{i}\sim N(1,\sigma^{2})$ truncated to $[0.5,1.5]$.
The smaller the $\sigma$, the more closely the $\gamma_{i}$ values cluster
around $1$. For the outlier risk-seeking firm, we set
$\gamma_{\textrm{outlier}}=0.5$. For clarity of exposition, we do not add
heterogeneity in expected returns: $\epsilon^{\prime}=0$ everywhere.

To detect outliers under exchangeability (Corollary 4.3), we can use methods
based on conformal prediction (Guan and Tibshirani 2022). Here, we use a
simpler approach: pick the firm $j$ with the largest contract size as the
outlier;
$\hat{j}\vcentcolon=\arg\max\limits_{j\in\\{j_{1},\dots,j_{m}\\}}\lvert
W_{i,j}\rvert$. We run $500$ experiments for each choice of $\sigma$, and
count the frequency with which the outlier firm is detected via its contract
size. Further details are presented in Appendix 8.3.

Figure 5 shows the results. We characterize the degree of outlierness by how
many standard deviations away $\gamma_{\textrm{outlier}}$ is from the baseline
of $1$. The smaller the $\sigma$, the more the outlierness. The success rate
increases with increasing outlierness, as expected. It also increases when the
number of firms $n$ is reduced. This is because contract sizes depend on the
$\gamma$ values of all firms; fewer firms reduces the chances of any one firm
attaining large contract sizes due to randomness.

###  4.2 Risk-Aversion versus Expected Returns

The discussion above showed that a firm can detect outlier counterparties.
However, the firm cannot determine why the counterparty is an outlier, as the
following theorem shows.

######  Theorem 4.4 (Non-identifiability of risk-aversion versus expected
returns)

Consider two network settings $S=(\bm{\mu}_{i},\Sigma,\gamma_{i})_{i\in[n]}$
and $S^{\prime}=(\bm{\mu}_{i},\Sigma,\gamma_{i}^{\prime})_{i\in[n]}$ which
differ only in the risk-aversions of firms
$J=\\{j\mid\gamma_{j}\neq\gamma^{\prime}_{j}\\}\subseteq[n]$. Then, there
exists a setting
$S^{\dagger}=(\bm{\mu}_{i}^{\dagger},\Sigma,\gamma_{i})_{i\in[n]}$ such that
$\bm{\mu}_{i}=\bm{\mu}^{\dagger}_{i}$ for all $i\notin J$ and the stable
networks under $S^{\dagger}$ and $S^{\prime}$ are identical.

Thus, one cannot determine if an outlier is more risk-seeking than its
community or expects higher profits. But risk-seeking behavior may be
indicative of stress, while higher profits than similar firms are unlikely.
Hence, in either case, the firm detecting the outlier may choose to reduce its
exposure to the outlier. However, this approach fails if an entire community
shifts its behavior. The following example illustrates the problem.

###### Example 4.5

Consider two communities numbered $1$ and $2$, with $n_{1}$ and $n_{2}$ firms
respectively. Let the setting $S$ of Theorem 4.4 correspond to

$\displaystyle M_{ij}$ $\displaystyle=\left\\{\begin{array}[]{cl}a&\text{if
$\theta_{i}=\theta_{j}=1$}\\\ b&\text{if $\theta_{i}=\theta_{j}=2$}\\\
c/2&\text{otherwise}\end{array}\right.$ $\displaystyle\Sigma_{ij}$
$\displaystyle=\left\\{\begin{array}[]{cl}1&\text{if
$\theta_{i}=\theta_{j}=1$}\\\ 1&\text{if $\theta_{i}=\theta_{j}=2$}\\\
0&\text{otherwise}\end{array}\right.$ $\displaystyle\gamma_{i}$
$\displaystyle=1.$

Now, suppose that under setting $S^{\prime}$,
$\gamma_{i}\mapsto\gamma_{i}+\delta$ for some small $\delta$ for all nodes $i$
in community $1$. The change in the network would be the same if we had
updated the columns corresponding to community $1$ in the $M$ matrix instead
(setting $S^{\dagger}$):

$\displaystyle M^{\dagger}_{ij}$
$\displaystyle=M_{ij}+\Delta(\theta_{i},\theta_{j})$
$\displaystyle\Delta(\theta_{i},\theta_{j})+O(\delta^{2})$
$\displaystyle=\left\\{\begin{array}[]{cl}-\delta a/2&\text{if
$\theta_{i}=\theta_{j}=1$}\\\ -\delta b\cdot n_{2}/(n_{1}+n_{2})&\text{if
$\theta_{i}=2,\theta_{j}=1$}\\\ 0&\text{if $\theta_{j}=2$}\end{array}\right.$

Thus, a firm from community $2$ cannot determine if the network change was due
to a change in $(\gamma_{i})_{\theta_{i}=1}$ or
$(\bm{\mu}_{i})_{\theta_{i}=1}$. For instance, when $b>0$, an increase in
risk-seeking ($\delta<0$) looks the same as an increase in trading benefits
($\Delta(1,2)>0$). In the former case, firms in community $2$ should reduce
their exposure to community $1$ firms. But in the latter case, they should
increase exposure. Since the data cannot be used to choose the appropriate
action, the behaviors of firms may be guided by their prior beliefs or
inertia. When such beliefs change due to external events (e.g., due to news
about one firm in community $1$), the resulting change in the network may be
drastic.$\hfill\Box$

##  5 Conclusions

We have proposed a model of a weighted undirected financial network of
contracts. The network emerges from the beliefs of the participant firms. The
link between the two is utility maximization coupled with pricing. For almost
all belief settings, our approach yields a unique network. This network
satisfies a strong Higher-Order Nash Stability property. Furthermore, the
firms can converge to this stable network via iterative pairwise negotiations.

The model yields two insights. First, a regulator is unable to reliably
identify the causes of a change in network structure, or engage in targeted
interventions. The reason is that firms seek to diversify risk by exploiting
correlations. We find that in realistic settings, there are often combinations
of trades that offer seemingly low risk. Hence, all firms aim to use such
trades. The over-dependence on a few such combinations leads to a pattern of
connections between firms that thwarts targeted regulatory interventions.

The second insight is that firms can use the network to update their beliefs.
For instance, they can identify counterparties that behave very differently
from their peers. However, the cause of the outlierness remains hidden. If all
firms in one line of business become more risk-seeking, the result is
indistinguishable from that business becoming more profitable. Innocuous
events (such as a news story) may cause beliefs to change suddenly, leading to
drastic changes in the network.

While our work focuses on mean-variance utility, many of our results hold more
generally. This is because the mean-variance utility is a good approximation
of a perturbation of other utility functions around the stable point. Some of
our results for pairwise negotiations and targeted interventions are based on
such perturbation arguments. Hence, these generalize to other choices of
utility functions.

##  6 Acknowledgments

The authors thank Stathis Tompaidis, Marios Papachristou, Kshitij Kulkarni,
and David Fridovich-Keil for valuable discussions and suggestions. This work
was supported by NSF grant 2217069 and a Dell Faculty Award.

## References

  * Acemoglu et al. (2015) Acemoglu D, Ozdaglar A, Tahbaz-Salehi A (2015) Systemic risk and stability in financial networks. _American Economic Review_ 105(2):564–608.
  * Aiello et al. (2000) Aiello W, Chung F, Lu L (2000) A random graph model for massive graphs. _Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC ’00)_ , 171–180.
  * Airoldi et al. (2008) Airoldi EM, Blei DM, Fienberg SE, Xing EP (2008) Mixed membership stochastic blockmodels. _Journal of Machine Learning Research_ 9:1981–2014.
  * Amini et al. (2015) Amini H, Minca A, Sulem A (2015) Control of interbank contagion under partial information. _SIAM Journal on Financial Mathematics_ 6(1):1195–1219.
  * Ang (2014) Ang A (2014) _Asset management: A systematic approach to factor investing_.
  * Bianchi et al. (2013) Bianchi S, Pantanella A, Pianese A (2013) Modeling stock prices by multifractional brownian motion: an improved estimation of the pointwise regularity. _Quantitative finance_ 13(8):1317–1330.
  * Birge (2021) Birge JR (2021) Modeling investment behavior and risk propagation in financial networks. _Available at SSRN 3847443_ .
  * Caballero and Simsek (2013) Caballero RJ, Simsek A (2013) Fire sales in a model of complexity. _The Journal of Finance_ 68(6):2549–2587.
  * Caimo and Friel (2011) Caimo A, Friel N (2011) Bayesian inference for exponential random graph models. _Social Networks_ 33(1):41–55.
  * Calafiore et al. (2022) Calafiore GC, Fracastoro G, Proskurnikov AV (2022) Control of dynamic financial networks. _IEEE Control Systems Letters_ .
  * Callier and Desoer (1994) Callier FM, Desoer CA (1994) _Linear System Theory_ (Springer Verlag).
  * Calvó-Armengol and Ilkılıç (2009) Calvó-Armengol A, Ilkılıç R (2009) Pairwise-stability and nash equilibria in network formation. _International Journal of Game Theory_ 38(1):51–79.
  * Carmona et al. (2022) Carmona R, Cooney DB, Graves CV, Lauriere M (2022) Stochastic graphon games: I. the static case. _Mathematics of Operations Research_ 47(1):750–778.
  * Chakrabarti et al. (2004) Chakrabarti D, Zhan Y, Faloutsos C (2004) R-MAT: A recursive model for graph mining. _Proceedings of the 4th SIAM International Conference on Data Mining (SDM ’04)_ , 442–446.
  * Chopra and Ziemba (2013) Chopra VK, Ziemba WT (2013) The effect of errors in means, variances, and covariances on optimal portfolio choice. _Handbook of the fundamentals of financial decision making: Part I_ , 365–373.
  * Cont and Minca (2016) Cont R, Minca A (2016) Credit default swaps and systemic risk. _Annals of Operations Research_ 247(7):523–547.
  * Duijn et al. (2004) Duijn MA, Snijders TA, Zijlstra BJ (2004) p2: a random effects model with covariates for directed graphs. _Statistica Neerlandica_ 58(2):234–254.
  * Eisenberg and Noe (2001) Eisenberg L, Noe TH (2001) Systemic risk in financial systems. _Management Science_ 47(2):236–249.
  * Eisfeldt et al. (2021) Eisfeldt AL, Herskovic B, Rajan S, Siriwardane E (2021) OTC intermediaries. Research Paper 18-05, Office of Financial Research.
  * Elliott et al. (2014) Elliott M, Golub B, Jackson MO (2014) Financial networks and contagion. _American Economic Review_ 104(10):3115–53.
  * Erdös and Rényi (1959) Erdös P, Rényi A (1959) On random graphs I. _Publicationes Mathematicae_ 6:290–297.
  * Fama and French (2015) Fama EF, French KR (2015) A five-factor asset pricing model. _Journal of financial economics_ 116(1):1–22.
  * Feinstein (2020) Feinstein Z (2020) Capital regulation under price impacts and dynamic financial contagion. _European Journal of Operational Research_ 281(2):449–463.
  * Feinstein and Søjmark (2021) Feinstein Z, Søjmark A (2021) Dynamic default contagion in heterogeneous interbank systems. _SIAM Journal on Financial Mathematics_ 12(4):SC83–SC97.
  * Frank and Strauss (1986) Frank O, Strauss D (1986) Markov Graphs. _Journal of the American Statistical Association_ 81(395):832–842.
  * Gandy and Veraart (2017) Gandy A, Veraart LA (2017) A bayesian methodology for systemic risk assessment in financial networks. _Management Science_ 63(12):4428–4446.
  * Geman et al. (2001) Geman H, Madan DB, Yor M (2001) Asset prices are brownian motion: only in business time. _Quantitative Analysis In Financial Markets: Collected Papers of the New York University Mathematical Finance Seminar (Volume II)_ , 103–146.
  * Gilbert (1959) Gilbert EN (1959) Random Graphs. _The Annals of Mathematical Statistics_ 30(4):1141–1144.
  * Glasserman and Young (2015) Glasserman P, Young HP (2015) How likely is contagion in financial networks? _Journal of Banking & Finance_ 50:383–399.
  * Glasserman and Young (2016) Glasserman P, Young HP (2016) Contagion in financial networks. _Journal of Economic Literature_ 54(3):779–831.
  * Guan and Tibshirani (2022) Guan L, Tibshirani R (2022) Prediction and outlier detection in classification problems. _Journal of the Royal Statistical Society. Series B, Statistical Methodology_ 84(2):524.
  * Guo and De Persis (2021) Guo M, De Persis C (2021) Linear quadratic network games with dynamic players: Stabilization and output convergence to nash equilibrium. _Automatica_ 130:109711.
  * Hellmann (2013) Hellmann T (2013) On the existence and uniqueness of pairwise stable networks. _International Journal of Game Theory_ 42(1):211–237.
  * Hellmann (2021) Hellmann T (2021) Pairwise stable networks in homogeneous societies with weak link externalities. _European Journal of Operational Research_ 291(3):1164–1179.
  * Hoff et al. (2002) Hoff PD, Raftery AE, Handcock MS (2002) Latent space approaches to social network analysis. _Journal of the American Statistical Association_ 97(460):1090–1098.
  * Holland et al. (1983) Holland PW, Laskey KB, Leinhardt S (1983) Stochastic blockmodels: First steps. _Social Networks_ 5(2):109–137.
  * Horn and Johnson (2008) Horn R, Johnson C (2008) _Topics in matrix analysis_ (Cambridge University Press).
  * Hunter and Handcock (2006) Hunter DR, Handcock MS (2006) Inference in Curved Exponential Family Models for Networks. _Journal of Computational and Graphical Statistics_ 15(3):565–583.
  * Kimball et al. (2008) Kimball MS, Sahm CR, Shapiro MD (2008) Imputing risk tolerance from survey responses. _Journal of the American statistical Association_ 103(483):1028–1038.
  * Leng et al. (2020) Leng Y, Dong X, Wu J, Pentland A (2020) Learning quadratic games on networks. _International Conference on Machine Learning_ , 5820–5830.
  * Mao et al. (2018) Mao X, Sarkar P, Chakrabarti D (2018) Overlapping Clustering Models, and One (class) SVM to Bind Them All. _Advances in Neural Information Processing Systems_ , volume 31.
  * Markowitz (1952) Markowitz H (1952) Portfolio selection. _Journal of Finance_ 7(1):77–91.
  * Mastromatteo et al. (2012) Mastromatteo I, Zarinelli E, Marsili M (2012) Reconstruction of financial networks for robust estimation of systemic risk. _Journal of Statistical Mechanics: Theory and Experiment_ .
  * Mazalov and Chirkova (2019) Mazalov V, Chirkova JV (2019) _Networking games: network forming games and games on networks_ (Academic Press).
  * Metrick (1995) Metrick A (1995) A natural experiment in “jeopardy!”. _The American Economic Review_ 240–253.
  * OECD (2022) OECD (2022) Oecd statistics. URL https://stats.oecd.org/.
  * Papachristou and Kleinberg (2022) Papachristou M, Kleinberg J (2022) Allocating stimulus checks in times of crisis. _Proceedings of the ACM Web Conference 2022_ , 16–26.
  * Paravisini et al. (2017) Paravisini D, Rappoport V, Ravina E (2017) Risk aversion and wealth: Evidence from person-to-person lending portfolios. _Management Science_ 63(2):279–297.
  * Peltonen et al. (2014) Peltonen TA, Scheicher M, Vuillemey G (2014) The network structure of the cds market and its determinants. _Journal of Financial Stability_ 13:118–133.
  * Peters et al. (2021) Peters L, Fridovich-Keil D, Royo VR, Tomlin CJ, Stachniss C (2021) Inferring objectives in continuous dynamic games from noise-corrupted partial state observations. _Robotics: Science and Systems XVII, 2021_.
  * Sadler and Golub (2021) Sadler E, Golub B (2021) Games on endogenous networks. _arXiv preprint arXiv:2102.01587_ .
  * Squartini et al. (2018) Squartini T, Caldarelli G, Cimini G, Gabrielli A, Garlaschelli D (2018) Reconstruction methods for networks: the case of economic and financial systems. _Physics Reports_ 757:1–47.
  * Tardos (2004) Tardos E (2004) Network games. _Proceedings of the thirty-sixth annual ACM symposium on Theory of computing_ , 341–342.
  * Upper (2011) Upper C (2011) Simulation methods to assess the danger of contagion in interbank markets. _Journal of financial stability_ 7(3):111–125.
  * Upper and Worms (2004) Upper C, Worms A (2004) Estimating bilateral exposures in the german interbank market: Is there a danger of contagion? _European Economic Review_ 48:827–849.
  * Vershynin (2018) Vershynin R (2018) _High-dimensional probability: An introduction with applications in data science_ , volume 47 (Cambridge university press).
  * Wang and Wong (1987) Wang YJ, Wong GY (1987) Stochastic blockmodels for directed graphs. _Journal of the American Statistical Association_ 82(397):8–19.
  * Wasserman and Pattison (1996) Wasserman S, Pattison P (1996) Logit models and logistic regressions for social networks: I. An introduction to Markov graphs and p${}^{\textrm{*}}$. _Psychometrika_ 61(3):401–425.
  * Wu et al. (2022) Wu M, Amin S, Ozdaglar A (2022) Convergence and stability of coupled belief–strategy learning dynamics in continuous games. _arXiv preprint arXiv:2206.05637_ .
  * Wu et al. (2021) Wu M, Amin S, Ozdaglar AE (2021) Value of information in bayesian routing games. _Operations Research_ 69(1):148–163.
  * Zhao et al. (2019) Zhao L, Chakrabarti D, Muthuraman K (2019) Portfolio construction by mitigating error amplification: The bounded-noise portfolio. _Operations Research_ 67(4):965–983.

##  7 Proofs

###  7.1 Proof of Theorem 2.5

Recall that
$Q_{i}=\Psi_{i}^{T}(2\gamma_{i}\Psi_{i}\Sigma_{i}\Psi_{i}^{T})^{-1}\Psi_{i}$,
$F=\\{(i,j):1\leq i<j\leq n,\Psi_{i}\bm{e}_{j}\neq\bm{0}\\}$, and
$\textrm{uvec}(X)_{F}\in\mathbb{R}^{|F|}$ is a vector whose entries are the
ordered set $\\{X_{ij}\mid(i,j)\in F\\}$. Note that
$\Psi_{i}\Sigma_{i}\Psi_{i}^{T}$ is positive definite, since it is a principal
submatrix of the positive definite matrix $\Sigma_{i}$.

[Restatement of Theorem 2.5]. Define $n\times n$ matrices $A$, $B_{(i,j)}$,
and $C_{(i,j)}$ as follows:

$\displaystyle A_{ij}$ $\displaystyle=\bm{e}_{i}^{T}Q_{j}M\bm{e}_{j},$
$\displaystyle B_{(i,j)}$ $\displaystyle=\bm{e}_{i}\bm{e}_{j}^{T}Q_{i},$
$\displaystyle C_{(i,j)}$
$\displaystyle=(B_{(i,j)}-B_{(j,i)})-(B_{(i,j)}-B_{(j,i)})^{T}.$

Let $Z_{F}$ be the $|F|\times|F|$ matrix whose rows are the ordered sets
$\\{\textrm{uvec}(C_{(i,j)})_{F}\mid(i,j)\in F\\}$. Then, we have the
following:

  1. 1.

A stable point $(W,P)$ under $\\{\Psi_{i}\\}$ exists if
$\textrm{uvec}(A-A^{T})_{F}$ lies in the column space of $Z_{F}$.

  2. 2.

A unique stable point always exists if $Z_{F}$ is full rank.

###### Proof 7.1

Proof. For clarity of exposition, we first prove the result when all edges are
allowed, and then consider the case of disallowed edges.

(1) All edges allowed. Here, $E=\\{i,j\mid 1\leq i<j\leq n\\}$, and we use
$\textrm{uvec}(.)$ and $Z$ to refer to $\textrm{uvec}(.)_{E}$ and $Z_{E}$ in
the theorem statement. For any price matrix $P$ with $P=-P^{T}$, consider the
matrix $W$ whose $j^{th}$ column has the utility-maximizing contract sizes for
agent $j$:

$\displaystyle W_{ij}$
$\displaystyle=\bm{e}_{i}^{T}\Psi_{j}^{T}(2\gamma_{j}\Psi_{j}\Sigma_{j}\Psi_{j}^{T})^{-1}\Psi_{j}(M-P)\bm{e}_{j}=\bm{e}_{i}^{T}Q_{j}(M-P)\bm{e}_{j}.$

The tuple $(W,P$) is stable if $W=W^{T}$. So, for all $i<j$, we require

$\displaystyle W_{ij}$ $\displaystyle=W_{ji}$ (5)
$\displaystyle\Leftrightarrow\bm{e}_{i}^{T}Q_{j}(M-P)\bm{e}_{j}$
$\displaystyle=\bm{e}_{j}^{T}Q_{i}(M-P)\bm{e}_{i}$
$\displaystyle\Leftrightarrow\bm{e}_{i}^{T}Q_{j}M\bm{e}_{j}-\bm{e}_{j}^{T}Q_{i}M\bm{e}_{i}$
$\displaystyle=\bm{e}_{i}^{T}Q_{j}P\bm{e}_{j}-\bm{e}_{j}^{T}Q_{i}P\bm{e}_{i}$
$\displaystyle\Leftrightarrow\bm{e}_{i}^{T}(A-A^{T})\bm{e}_{j}$
$\displaystyle=\bm{e}_{i}^{T}(Q_{j}P-(Q_{i}P)^{T})\bm{e}_{j}.$ (6)

Since $P=-P^{T}$, we must have $P=R-R^{T}$, where $R$ is upper-triangular with
zero on the diagonal. Hence, using $Q_{i}=Q_{i}^{T}$, we have

$\displaystyle\bm{e}_{i}^{T}(Q_{j}P-(Q_{i}P)^{T})\bm{e}_{j}$
$\displaystyle=\bm{e}_{i}^{T}(Q_{j}P+PQ_{i})\bm{e}_{j}$
$\displaystyle=trP(\bm{e}_{j}\bm{e}_{i}^{T}Q_{j}+Q_{i}\bm{e}_{j}\bm{e}_{i}^{T})$
$\displaystyle=tr(R-R^{T})(B_{(j,i)}+B_{(i,j)}^{T})$
$\displaystyle=trR^{T}C_{(i,j)}$
$\displaystyle=\textrm{uvec}(R)^{T}\textrm{uvec}(C_{(i,j)}),$

where we used the upper-triangular nature of $R$ in the last step. Plugging
into Eq. 6, a stable point exists if there is an appropriate vector
$\bm{p}:=\textrm{uvec}(R)\in\mathbb{R}^{n(n-1)/2}$ such that for all $1\leq
i<j\leq n$,
$\bm{e}_{i}^{T}(A-A^{T})\bm{e}_{j}=\textrm{uvec}(C_{(i,j)})^{T}\bm{p}$. This
is equivalent to $\textrm{uvec}(A-A^{T})=Z\bm{p}$.

(2) Disallowed edges.  If $\\{i,j\\}$ is a prohibited edge then
$\Psi_{i}\bm{e}_{j}=\Psi_{j}\bm{e}_{i}=\bm{0}$, so $B_{(i,j)}=B_{(j,i)}=0$, so
$\bm{e}_{ij}^{T}Z=\bm{0}^{T}$. Also, $A_{ij}=A_{ji}=0$ so
$\textrm{uvec}(A-A^{T})_{ij}=0$. Therefore, the equality
$\bm{e}_{i}^{T}(A-A^{T})\bm{e}_{j}=\textrm{uvec}(C_{(i,j)})^{T}\bm{x}$ is
achieved for any solution vector $\bm{x}$ if $\\{i,j\\}$ is a prohibited edge.
We can therefore reduce the linear system $Z\bm{p}=\textrm{uvec}(A-A^{T})$
from part (1) by deleting rows of $Z$ corresponding to prohibited edges.

Similarly, since the system is constrained by $\bm{p}_{ij}=0$ for prohibited
edges $\\{i,j\\}$, the columns of $Z$ corresponding to such edges have no
effect on the solution set.

We conclude that the linear system in (1) is equivalent to the (unconstrained)
reduced system $Z_{F}\bm{p}_{F}=\textrm{uvec}(A-A^{T})_{F}$. If $Z_{F}$ has
full rank then the unique reduced solution is
$\bm{p}_{F}=Z_{F}^{-1}\textrm{uvec}(A-A^{T})_{F}$.

###  7.2 Proof of Theorem 2.7

We begin with a perturbation lemma.

###### Lemma 7.2

Let $E$ and $Z_{F}$ be defined as in Theorem 2.5. Let
$\underline{\lambda}(A)\vcentcolon=\min\\{\lvert\lambda\rvert:\lambda\in\sigma(Z_{F})\setminus\\{0\\}\\}$.
Then for all $\epsilon\in(0,\underline{\lambda}(Z_{F}))$, the perturbed matrix
$Z_{F}+\epsilon I_{|F|}$ is full rank.

###### Proof 7.3

Proof of Lemma 7.2. The eigenvalues of $(Z_{F}+\epsilon I)$ are given by
$\\{\lambda+\epsilon:\lambda\in\sigma(Z_{F})\\}$. So, any zero eigenvalues are
shifted to $\epsilon>0$. For all other eigenvalues
$\lambda\in\sigma(Z_{F})\setminus\\{0\\}$, we have $\lambda+\epsilon\neq 0$
since $\epsilon<\underline{\lambda}(Z_{F})$. Hence, $Z_{F}+\epsilon I_{|F|}$
is full rank.

[Restatement of Theorem 2.7]. For any network setting
$S=(\bm{\mu}_{i},\gamma_{i},\Sigma_{i},\Psi_{i})_{i\in[n]}$ and any
$\epsilon>0$, there exist uncountably many network settings
$S^{\prime}=(\bm{\mu}_{i},\gamma_{i},\Sigma_{i}^{\prime},\Psi_{i})_{i\in[n]}$
such that $\|\Sigma_{i}^{\prime}-\Sigma_{i}\|<\epsilon$ for all $i\in[n]$, and
$S^{\prime}$ has a unique stable point.

###### Proof 7.4

Proof of Theorem 2.7. Define $F$, $Z_{F}$ and $Q$ as in Theorem 2.5. Let
$Z_{F}^{\prime}=Z_{F}+\beta I_{\lvert F\rvert}$ for some $\beta>0$. For
$\beta$ small enough, Lemma 7.2 and Theorem 2.5 show that if $Z_{F}^{\prime}$
arises according to a network setting $S^{\prime}$, then that setting
$S^{\prime}$ has a unique stable point. Therefore, it remains to show that
there exists an $S^{\prime}$ such that the matrix of the corresponding system
is $Z_{F}^{\prime}$.

For $i\in[n]$ let $X_{i}\in\mathbb{R}^{n\times n}$ be diagonal matrix such
that for $j\in[n]$,

$\displaystyle(X_{i})_{j,j}=\begin{cases}1&(i,j)\in F\\\
0&\text{otherwise}\end{cases}$

We claim that $S^{\prime}$ results in the system $Z_{F}^{\prime}$ if for all
$i\in[n]$, we define $\Sigma_{i}^{\prime}$ such that
$\Psi_{i}\Sigma_{i}^{\prime}\Psi_{i}^{T}=\frac{1}{2\gamma_{i}}(\Psi_{i}(Q_{i}+\beta
X_{i})\Psi_{i}^{T})^{-1}$. The entries of $\Sigma_{i}^{\prime}$ and
$\Sigma_{i}$ are kept the same outside of the submatrix selected by
$\Psi_{i}\Sigma_{i}\Psi_{i}^{T}$.

To see that this choice of $S^{\prime}$ results in $Z^{\prime}$, notice that
$Q_{i}^{\prime}=\Psi_{i}^{T}(2\gamma_{i}\Psi_{i}\Sigma_{i}^{\prime}\Psi_{i}^{T})^{-1}\Psi_{i}=\Psi_{i}^{T}\Psi_{i}(Q_{i}+\beta
X_{i})\Psi_{i}^{T}\Psi_{i}$.

This has the effect of shifting the diagonal of $Q_{i}$:

$\displaystyle(Q_{i}^{\prime})_{j,k}=\begin{cases}(Q_{i})_{j,k}+\beta&j=k,(i,j)\in
F\\\ (Q_{i})_{j,k}&\text{otherwise}\end{cases}$

Working through the matrices $B_{(i,j)}$ and $C_{(i,j)}$ in the statement of
Theorem 2.5, we find that $Z_{F}^{\prime}=Z_{F}+\beta I_{\lvert F\rvert}$
under network setting $S^{\prime}$.

Next, we want to bound $\|\Sigma_{i}^{\prime}-\Sigma_{i}\|$. Since
$\Sigma_{i}^{\prime}$ has entries equal to that of $\Sigma_{i}$ outside of the
submatrix selected by $\Psi_{i}\Sigma_{i}\Psi_{i}^{T}$, and since both
matrices are positive definite symmetric, a permutation argument implies that
to bound the spectral norm it suffices to analyze the principal submatrix that
is changed. That is,
$\|\Sigma_{i}-\Sigma_{i}^{\prime}\|_{2}=\|\Psi_{i}(\Sigma_{i}-\Sigma_{i}^{\prime})\Psi_{i}^{T}\|_{2}$.

Let
$r_{i}\vcentcolon=\|\beta(\Psi_{i}Q_{i}\Psi_{i}^{T})^{-1}(\Psi_{i}X_{i}\Psi_{i}^{T})\|$.
We choose $\beta$ small enough that $r_{i}<1$ for all $i\in[n]$. Then, using
the power series identity $(I-X)^{-1}=\sum_{k=0}^{\infty}X^{k}$ for $\|X\|<1$,
we have:

$\displaystyle\|\Psi_{i}(\Sigma_{i}-\Sigma_{i}^{\prime})\Psi_{i}^{T}\|$
$\displaystyle=\frac{1}{2\gamma_{i}}\|(\Psi_{i}(Q_{i}+\beta
X_{i})\Psi_{i}^{T})^{-1}-(\Psi_{i}Q_{i}\Psi_{i}^{T})^{-1}\|$
$\displaystyle=\frac{1}{2\gamma_{i}}\bigg{\|}\bigg{(}(\Psi_{i}Q_{i}\Psi_{i}^{T})(I+\beta(\Psi_{i}Q_{i}\Psi_{i}^{T})^{-1}(\Psi_{i}X_{i}\Psi_{i}^{T}))\bigg{)}^{-1}-(\Psi_{i}Q_{i}\Psi_{i}^{T})^{-1}\bigg{\|}$
$\displaystyle=\frac{1}{2\gamma_{i}}\bigg{\|}\bigg{(}\big{(}(I+\beta(\Psi_{i}Q_{i}\Psi_{i}^{T})^{-1}(\Psi_{i}X_{i}\Psi_{i}^{T})\big{)}^{-1}-I\bigg{)}(\Psi_{i}Q_{i}\Psi_{i}^{T})^{-1}\bigg{\|}$
$\displaystyle\leq\frac{\|(\Psi_{i}Q_{i}\Psi_{i}^{T})^{-1}\|}{2\gamma_{i}}\sum\limits_{k=1}^{\infty}\bigg{\|}\bigg{(}-\beta(\Psi_{i}Q_{i}\Psi_{i}^{T})^{-1}(\Psi_{i}X_{i}\Psi_{i}^{T})\bigg{)}^{k}\bigg{\|}$
$\displaystyle=\frac{\|(\Psi_{i}Q_{i}\Psi_{i}^{T})^{-1}\|}{2\gamma_{i}}\frac{r_{i}}{1-r_{i}}.$

Thus, for $\beta$ small enough (and hence $\\{r_{i}\\}_{i\in[n]}$ small
enough), $\|\Sigma_{i}-\Sigma^{\prime}_{i}\|<\epsilon$ for all $i\in[n]$.

###  7.3 Proof of Corollary 2.6

[Restatement of Corollary 2.6.] Suppose $\Sigma_{i}=\Sigma$ and
$\Psi_{i}=I_{n}$ for all $i\in[n]$. Let $(\lambda_{i},\bm{v}_{i})$ denote the
$i^{th}$ eigenvalue and eigenvector of $\Gamma^{-1/2}\Sigma\Gamma^{-1/2}$.
Then, the network $W$ can be written in two equivalent ways:

$\displaystyle\textrm{vec}(W)$
$\displaystyle=\frac{1}{2}(\Gamma\otimes\Sigma+\Sigma\otimes\Gamma)^{-1}\textrm{vec}(M+M^{T}),$
$\displaystyle W$
$\displaystyle=\Gamma^{-1/2}\left(\sum_{i=1}^{n}\sum_{j=1}^{n}\frac{\bm{v}_{i}^{T}\Gamma^{-1/2}(M+M^{T})\Gamma^{-1/2}\bm{v}_{j}}{2(\lambda_{i}+\lambda_{j})}\bm{v}_{i}\bm{v}_{j}^{T}\right)\Gamma^{-1/2}.$

###### Proof 7.5

Proof. We first prove the identity with $\textrm{vec}(W)$.

For each agent $i$ the optimal set of contracts is given as
$\bm{w}_{i}=(2\gamma_{i}\Sigma_{i})^{-1}(M-P)\bm{e}_{i}$. Since
$\Sigma_{i}=\Sigma$ for all $i$, we obtain
$W=\frac{1}{2}\Sigma^{-1}(M-P)\Gamma^{-1}$. Hence $M-P=2\Sigma W\Gamma$. Using
$W=W^{T}$ and $P^{T}=-P$ for a stable feasible point $(W,P)$, we obtain
$\Sigma W\Gamma+\Gamma W\Sigma=\frac{1}{2}(M+M^{T})$.

Vectorization implies
$(\Gamma\otimes\Sigma+\Sigma\otimes\Gamma)\textrm{vec}(W)=\frac{1}{2}\textrm{vec}(M+M^{T})$.
It remains to show that $(\Gamma\otimes\Sigma+\Sigma\otimes\Gamma)$ is
invertible.

Let $K\vcentcolon=(\Gamma\otimes\Sigma+\Sigma\otimes\Gamma)$ for shorthand.
Notice
$K=(\Gamma^{1/2}\otimes\Gamma^{1/2})(I\otimes\Gamma^{-1/2}\Sigma\Gamma^{-1/2}+\Gamma^{-1/2}\Sigma\Gamma^{-1/2}\otimes
I)(\Gamma^{1/2}\otimes\Gamma^{1/2})$. Let
$K^{\prime}=(I\otimes\Gamma^{-1/2}\Sigma\Gamma^{-1/2}+\Gamma^{-1/2}\Sigma\Gamma^{-1/2}\otimes
I)$. Since $(\Gamma^{1/2}\otimes\Gamma^{1/2})$ is invertible it suffices to
show $K^{\prime}$ is invertible.

Properties of Kronecker products imply that if a matrix
$A\in\mathbb{R}^{n\times n}$ has strictly positive eigenvalues then
$\sigma(I\otimes A+A\otimes I)=\\{\lambda+\mu:\lambda,\mu\in\sigma(A)\\}$
counting mutiplicities (Horn and Johnson 2008). Let $\bm{v}\neq\bm{0}$. Then,
since $\Sigma\succ 0$ and $\Gamma^{-1/2}\succ 0$ we obtain
$\bm{v}^{T}\Gamma^{-1/2}\Sigma\Gamma^{-1/2}\bm{v}=(\Gamma^{-1/2}\bm{v})^{T}\Sigma(\Gamma^{-1/2}\bm{v})>0$.
Hence $\Gamma^{-1/2}\Sigma\Gamma^{-1/2}\succ 0$, so $K^{\prime}$ is invertible
and hence $K$ is invertible. This proves the first identity.

Next, we prove the second identity. Properties of Kronecker products imply
that $(K^{\prime})^{-1}$ has eigendecomposition
$(K^{\prime})^{-1}=\sum_{i=1}^{n}\sum_{j=1}^{n}\frac{1}{\lambda_{i}+\lambda_{j}}(\bm{v}_{i}\otimes\bm{v}_{j})(\bm{v}_{i}\otimes\bm{v}_{j})^{T}$.

Therefore, since
$(\Gamma^{1/2}\otimes\Gamma^{1/2})^{-1}=(\Gamma^{-1/2}\otimes\Gamma^{-1/2})$
we obtain:

$\displaystyle\textrm{vec}(W)$
$\displaystyle=(\Gamma^{-1/2}\otimes\Gamma^{-1/2})\sum_{i=1}^{n}\sum_{j=1}^{n}\frac{1}{\lambda_{i}+\lambda_{j}}(\bm{v}_{i}\otimes\bm{v}_{j})(\bm{v}_{i}\otimes\bm{v}_{j})^{T}(\Gamma^{-1/2}\otimes\Gamma^{-1/2})\textrm{vec}\big{(}\frac{M+M^{T}}{2}\big{)}$
$\displaystyle=(\Gamma^{-1/2}\otimes\Gamma^{-1/2})\sum_{i=1}^{n}\sum_{j=1}^{n}\frac{1}{2(\lambda_{i}+\lambda_{j})}(\bm{v}_{i}\bm{v}_{i}^{T}\otimes\bm{v}_{j}\bm{v}_{j}^{T})\textrm{vec}\big{(}\Gamma^{-1/2}(M+M^{T})\Gamma^{-1/2}\big{)}$
$\displaystyle=(\Gamma^{-1/2}\otimes\Gamma^{-1/2})\textrm{vec}\left(\sum_{i=1}^{n}\sum_{j=1}^{n}\frac{\bm{v}_{i}^{T}\Gamma^{-1/2}(M+M^{T})\Gamma^{-1/2}\bm{v}_{j}}{2(\lambda_{i}+\lambda_{j})}\bm{v}_{i}\bm{v}_{j}^{T}\right)$
$\displaystyle W$
$\displaystyle=\Gamma^{-1/2}\left(\sum_{i=1}^{n}\sum_{j=1}^{n}\frac{\bm{v}_{i}^{T}\Gamma^{-1/2}(M+M^{T})\Gamma^{-1/2}\bm{v}_{j}}{2(\lambda_{i}+\lambda_{j})}\bm{v}_{i}\bm{v}_{j}^{T}\right)\Gamma^{-1/2}$

###  7.4 Proof of Theorem 2.8

[Restatement of Theorem 2.8]. Let $(W^{*},P^{*})$ be a stable feasible point.
Then there is no feasible $(W,P)$ such that $(W,P)\succ(W^{*},P*)$.

###### Proof 7.6

Proof of Theorem 2.8. Case 1: $P=P^{*}$. First, consider a feasible $(W,P)$
such that $P=P^{*}$. Then $W\neq W^{*}$. Since $W^{*}$ is stable, by
definition each agent optimizes contracts with respect to $P^{*}$, so no agent
is worse off under $(W^{*},P^{*})$ then $(W,P^{*})$. Hence
$(W,P)\not\succ(W^{*},P^{*})$.

Case 2: $P\neq P^{*}$. Second, suppose that $P\neq P^{*}$. Let
$\Delta_{i}\vcentcolon=g_{i}(W,P)-g_{i}(W,P^{*})$. It follows that
$\Delta_{i}=(W\bm{e}_{i})^{T}((P^{*}-P)\bm{e}_{i})$. Let
$A\in\mathbb{R}^{n\times n}$ be defined as $A_{ij}=W_{ij}(P_{ij}^{*}-P_{ij})$.
Then $\Delta_{i}=\bm{e}_{i}^{T}A\bm{1}$.

Next, notice that $A_{ji}=-A_{ij}$. Therefore,
$\sum_{i}\Delta_{i}=\bm{1}^{T}A\bm{1}=0$. Hence, either $\Delta_{i}=0$ for all
$i$, or there exists $k$ such that $\Delta_{k}<0$.

Case 2(i). Suppose there exists $k$ such that $\Delta_{k}<0$. Then
$g_{k}(W,P)<g_{k}(W,P^{*})$. By case $1$, we have $g_{k}(W,P^{*})\leq
g_{k}(W^{*},P^{*})$. Therefore agent $k$ is strictly worse off, so
$(W,P)\not\succ(W^{*},P^{*})$.

Case 2(ii). Suppose $\Delta_{i}=0$ for all $i$. Then
$g_{i}(W,P)=g_{i}(W,P^{*})$ for all $i$. And by case $1$, we have
$g_{i}(W,P^{*})\leq g_{i}(W^{*},P^{*})$. Therefore no agent is better off, so
$(W,P)\not\succ(W^{*},P^{*})$.

###  7.5 Proof of Theorem 2.11

[Restatement of Theorem 2.11] Any stable point $(W,P)$ is Higher-Order Nash
Stable.

###### Proof 7.7

Proof of Theorem 2.11. First, we argue $(W,P)$ is a Nash equilibrium. Suppose
that agent $i$ wants to shift some of their contracts at the stable feasible
point $(W,P)$. Suppose they propose
$(w_{i,j_{1}}^{\prime},p_{i,j_{1}}^{\prime}),\dots,(w_{i,j_{m}}^{\prime},p_{i,j_{m}}^{\prime})$
for $j_{1},\dots,j_{m}\in[n]$. Let $(W^{\prime},P^{\prime})$ denote the new
feasible point that occurs if all changes are accepted. By Theorem 2.8 we know
that $(W^{\prime},P^{\prime})\not\succ(W,P)$, so at least one agent does not
prefer $(W^{\prime},P^{\prime})$. Since the only changes are to edges
$\\{i,j_{1}\\},\dots,\\{i,j_{m}\\}$, there must exist a
$j\in\\{j_{1},\dots,j_{m}\\}$ who does not prefer $(W^{\prime},P^{\prime})$.
Therefore, they will reject the proposal of agent $i$ to shift to
$(w_{ij}^{\prime},p_{ij}^{\prime})$.

Then, agent $i$ can choose to either maintain the existing contract
$(w_{ij},p_{ij})$ or delete the edge $\\{i,j\\}$. We claim that agent $i$
prefers to keep the edge, since they could have chosen to set $w_{ij}=0$
during the network formation process, no matter what price was offered. But
$w_{ij}\neq 0$ at equilibrium $(W,P)$. By stability of $(W,P)$ we know
$w_{ij}$ is the optimal choice for agent $i$ at prices $P$. Therefore, after
agent $j$ rejects $(w_{ij}^{\prime},p_{ij}^{\prime})$, it follows that the
edge remains at $(w_{ij},p_{ij})$.

Since $(W^{\prime},P^{\prime})$ was arbitrary, we conclude that at
equilibrium, agent $i$ cannot propose any set of changes that result in a
strictly better network for them. Therefore, their optimal action at $(W,P)$
is to not deviate from the equilibrium.

Next, we show cartel robustness. Suppose $S\subset[n]$ is a strict subset and
$(W^{\prime},P^{\prime})\neq(W,P)$ is a feasible point differing only at
indices $\\{i,j\\}$ such that $i,j\in S$. By Theorem 2.8, we know
$(W^{\prime},P^{\prime})$ cannot dominate $(W,P)$, so there is some agent
$i\in[n]$ that does not prefer $(W^{\prime},P^{\prime})$ to $(W,P)$. Since
$(W^{\prime},P^{\prime})$ only changes contracts where both members are in
$S$, the utility of agents in $[n]\setminus S$ must be unchanged. Therefore
$i\in S$, and hence not all members of the cartel have higher utility under
$(W^{\prime},P^{\prime})$.

###  7.6 Proof of Proposition 2.12

[Restatement of Proposition 2.12] Consider a network setting
$(\bm{\mu}_{i},\gamma_{i},\Sigma_{i},\Psi_{i})_{i\in[n]}$. Let $Q_{i}$ be as
in Theorem 2.5. Given a price matrix $P=-P^{T}$ and a pair of firms $(i,j)$
that are permitted to trade, let $P^{\prime}$ be another skew-symmetric price
matrix such that (a) $P^{\prime}$ differs from $P$ only in the cells $(i,j)$
and $(j,i)$, (b) $i$ and $j$ both maximize their utility at the same contract
size under $P^{\prime}$, and (c) $i$ and $j$ can choose their optimal contract
sizes with all other agents given these prices. Then,

$\displaystyle P^{\prime}_{ij}$
$\displaystyle=\frac{1}{Q_{i;j,j}+Q_{j;i,i}}\Big{(}\bm{e}_{i}^{T}Q_{j}(M-P)\bm{e}_{j}-\bm{e}_{j}^{T}Q_{i}(M-P)\bm{e}_{i}\Big{)}+P_{ij}$

###### Proof 7.8

Proof. Let $A_{i}\vcentcolon=\gamma_{i}Q_{i}$ for $i\in[n]$. Since
$\Sigma_{i}\succ 0$ and $\Psi_{i}\Sigma_{i}\Psi_{i}^{T}$ is a principal
submatrix, we know $\Psi_{i}\Sigma_{i}\Psi_{i}^{T}$ is real symmetric and
positive definite, and hence its inverse is as well. Therefore $A_{i}$ is real
symmetric and PSD. (It is not full rank in general, unless $\Psi_{i}=I$).
Since $\\{i,j\\}$ is a permitted edge, $\Psi_{i}\bm{e}_{j}\neq\bm{0}$ and
$\Psi_{j}\bm{e}_{i}\neq\bm{0}$. Therefore
$A_{i;j,j}=\bm{e}_{j}^{T}A_{i}\bm{e}_{j}=(\Psi_{i}\bm{e}_{j})^{T}(2\Psi_{i}\Sigma_{i}\Psi_{i}^{T})^{-1}(\Psi_{i}\bm{e}_{j})>0$
since $(2\Psi_{i}\Sigma_{i}\Psi_{i}^{T})^{-1}$ is positive definite. So,
$A_{i;j,j}>0$ and similarly $A_{j;i,i}>0$.

Now, the optimal contracts for agent $i$ under prices $P^{\prime}$ are given
by $\bm{w}_{i}=A_{i}(M-P^{\prime})\Gamma^{-1}\bm{e}_{i}$. Note that
$P^{\prime}=P+(P^{\prime}_{ij}-P_{ij})(\bm{e}_{i}\bm{e}_{j}^{T}-\bm{e}_{j}\bm{e}_{i}^{T})$.
Since both $i$ and $j$ maximize their utility at the same contract size, we
have:

$\displaystyle\bm{w}_{i;j}$ $\displaystyle=\bm{w}_{j;i}$
$\displaystyle\Rightarrow\bm{e}_{j}^{T}\bm{w}_{i}$
$\displaystyle=\bm{e}_{i}^{T}\bm{w}_{j}$
$\displaystyle\Rightarrow\bm{e}_{j}^{T}(A_{i}(M-P^{\prime})\Gamma^{-1})\bm{e}_{i}$
$\displaystyle=\bm{e}_{i}^{T}(A_{j}(M-P^{\prime})\Gamma^{-1})\bm{e}_{j}$
$\displaystyle\Rightarrow\gamma_{j}\bm{e}_{j}^{T}A_{i}M\bm{e}_{i}-\gamma_{i}\bm{e}_{i}^{T}A_{j}M\bm{e}_{j}$
$\displaystyle=\gamma_{j}\bm{e}_{j}^{T}A_{i}P^{\prime}\bm{e}_{i}-\gamma_{i}\bm{e}_{i}^{T}A_{j}P^{\prime}\bm{e}_{j}$
$\displaystyle=\gamma_{j}\bm{e}_{j}^{T}A_{i}P\bm{e}_{i}-\gamma_{i}\bm{e}_{i}^{T}A_{j}P\bm{e}_{j}-(P^{\prime}_{ij}-P_{ij})\left(\gamma_{j}\bm{e}_{j}^{T}A_{i}\bm{e}_{j}+\gamma_{i}\bm{e}_{i}^{T}A_{j}\bm{e}_{i}\right)$
$\displaystyle\Rightarrow P^{\prime}_{ij}-P_{ij}$
$\displaystyle=\frac{1}{\gamma_{j}A_{i;j,j}+\gamma_{i}A_{j;i,i}}\Big{(}\bm{e}_{i}^{T}\Gamma
A_{j}(M-P)\bm{e}_{j}-\bm{e}_{j}^{T}\Gamma A_{i}(M-P)\bm{e}_{i}\Big{)}$
$\displaystyle=\frac{1}{Q_{i;j,j}+Q_{j;i,i}}\Big{(}\bm{e}_{i}^{T}Q_{j}(M-P)\bm{e}_{j}-\bm{e}_{j}^{T}Q_{i}(M-P)\bm{e}_{i}\Big{)}$

###  7.7 Proof of Theorem 2.14

First, we characterize pairwise negotiation dynamics as linear in the price
updates.

###### Theorem 7.9

Consider a network setting
$(\bm{\mu}_{i},\gamma_{i},\Sigma_{i},\Psi_{i})_{i\in[n]}$. Define $Q_{i}$ as
in Theorem 2.5. Let $s_{ij}=1$ if $\\{i,j\\}$ is a permitted edge and $0$
otherwise. Let $L,R\in\mathbb{R}^{n^{2}\times n^{2}}$ be diagonal matrices
such that $L_{(i-1)n+j,(i-1)n+j}=Q_{i;jj}+Q_{j;ii}$ and
$R_{(i-1)n+j,(i-1)n+j}=s_{ij}$, and $L^{\dagger}$ be the pseudoinverse of $L$.
Let $\Delta_{(t+1)}=P(t+1)-P(t)$, where $P(t)$ is the price matrix at time
step $t$ of pairwise negotiations. Then,

$\displaystyle\textrm{vec}(\Delta_{(t+1)})$
$\displaystyle=R\Big{(}I_{n^{2}}-\eta
L^{\dagger}K\Big{)}\textrm{vec}(\Delta_{(t)}),$ $\displaystyle\text{where }K$
$\displaystyle=\sum\limits_{r=1}^{n}\big{(}\bm{e}_{r}\bm{e}_{r}^{T}\otimes
Q_{r}+Q_{r}\otimes\bm{e}_{r}\bm{e}_{r}^{T}\big{)}.$

###### Proof 7.10

Proof. Let $\\{i,j\\}$ be a permitted edge. From Proposition 2.12, we obtain:

$\displaystyle(\Delta_{(t+1)})_{ij}$
$\displaystyle=\frac{\eta}{Q_{i;j,j}+Q_{j;i,i}}\Big{(}\bm{e}_{i}^{T}Q_{j}(M-P(t))\bm{e}_{j}-\bm{e}_{j}^{T}Q_{i}(M-P(t))\bm{e}_{i}\Big{)}$
$\displaystyle\Rightarrow(\Delta_{(t+1)})_{ij}-(\Delta_{(t)})_{ij}$
$\displaystyle=\frac{\eta}{Q_{i;j,j}+Q_{j;i,i}}\Big{(}\bm{e}_{i}^{T}Q_{j}(-\Delta_{(t)})\bm{e}_{j}-\bm{e}_{j}^{T}Q_{i}(-\Delta_{(t)})\bm{e}_{i}\Big{)}$
$\displaystyle=\frac{-\eta}{Q_{i;j,j}+Q_{j;i,i}}\Big{(}\bm{e}_{i}^{T}Q_{j}\Delta_{(t)}\bm{e}_{j}-\bm{e}_{j}^{T}Q_{i}\Delta_{(t)}\bm{e}_{i}\Big{)}$
$\displaystyle=\frac{-\eta}{Q_{i;j,j}+Q_{j;i,i}}\bm{e}_{i}^{T}\Big{(}Q_{j}\Delta_{(t)}-(Q_{i}\Delta_{(t)})^{T}\Big{)}\bm{e}_{j}$
$\displaystyle\Rightarrow(Q_{i;j,j}+Q_{j;i,i})\Big{(}(\Delta_{(t+1)})_{ij}-(\Delta_{(t)})_{ij}\Big{)}$
$\displaystyle=-\eta
s_{ij}\bm{e}_{i}^{T}\Big{(}Q_{j}\Delta_{(t)}+\Delta_{(t)}Q_{i}\Big{)}\bm{e}_{j},$

We assumed that $\\{i,j\\}$ was a permitted edge above, but notice the
identity is also true for prohibited $\\{i,j\\}$ since both the numerator and
denominator become $0$, and we can define their ratio to be $0$. Defining
$Y_{ij}=\bm{e}_{i}^{T}\Big{(}Q_{j}\Delta_{(t)}+\Delta_{(t)}Q_{i}\Big{)}\bm{e}_{j}$,
and recalling the definitions of $L$ and $R$ from the theorem statement, the
above formula becomes

$\displaystyle L\textrm{vec}(\Delta_{(t+1)}-\Delta_{(t)})$
$\displaystyle=-\eta R\textrm{vec}(Y).$ (7)

We show next that $\textrm{vec}(Y)=K\textrm{vec}(\Delta_{(t)})$, where $K$ is
defined in the theorem statement. Let $tr$ denote the trace operator. Then,

$\displaystyle(\bm{e}_{j}^{T}\otimes\bm{e}_{i}^{T})\textrm{vec}(Y)=Y_{ij}$
$\displaystyle=\bm{e}_{i}^{T}\Big{(}Q_{j}\Delta_{(t)}+\Delta_{(t)}Q_{i}\Big{)}\bm{e}_{j}$
$\displaystyle=tr\Big{(}\bm{e}_{i}^{T}Q_{j}\Delta_{(t)}\bm{e}_{j}\Big{)}+tr\Big{(}\bm{e}_{i}^{T}\Delta_{(t)}Q_{i}\bm{e}_{j}\Big{)}$
$\displaystyle=tr\Big{(}\bm{e}_{j}^{T}\Delta_{(t)}^{T}Q_{j}^{T}\bm{e}_{i}\Big{)}+tr\Big{(}\bm{e}_{i}^{T}\Delta_{(t)}Q_{i}\bm{e}_{j}\Big{)}$
$\displaystyle=tr\Big{(}\Delta_{(t)}^{T}Q_{j}^{T}\bm{e}_{i}\bm{e}_{j}^{T}\Big{)}+tr\Big{(}Q_{i}\bm{e}_{j}\bm{e}_{i}^{T}\Delta_{(t)}\Big{)}$
$\displaystyle=\textrm{vec}(\Delta_{(t)})^{T}\textrm{vec}(Q_{j}^{T}\bm{e}_{i}\bm{e}_{j}^{T}+(Q_{i}\bm{e}_{j}\bm{e}_{i}^{T})^{T})$
$\displaystyle=\textrm{vec}(Q_{j}\bm{e}_{i}\bm{e}_{j}^{T}+\bm{e}_{i}\bm{e}_{j}^{T}Q_{i})^{T}\textrm{vec}(\Delta_{(t)}),$

where we used $Q_{i}=Q_{i}^{T}$.

Hence we need to show
$(\bm{e}_{j}^{T}\otimes\bm{e}_{i}^{T})K=\textrm{vec}(Q_{j}\bm{e}_{i}\bm{e}_{j}^{T}+\bm{e}_{i}\bm{e}_{j}^{T}Q_{i})^{T}$.
Now,

$\displaystyle(\bm{e}_{j}^{T}\otimes\bm{e}_{i}^{T})K$
$\displaystyle=(\bm{e}_{j}^{T}\otimes\bm{e}_{i}^{T})(\sum\limits_{r=1}^{n}\bm{e}_{r}\bm{e}_{r}^{T}\otimes
Q_{r}+Q_{r}\otimes\bm{e}_{r}\bm{e}_{r}^{T})$
$\displaystyle=\sum\limits_{r=1}^{n}\delta_{jr}(\bm{e}_{j}^{T}\otimes\bm{e}_{i}^{T}Q_{r})+\delta_{ir}(\bm{e}_{j}^{T}Q_{r}\otimes\bm{e}_{i}^{T})$
$\displaystyle=(\bm{e}_{j}^{T}\otimes\bm{e}_{i}^{T}Q_{j})+(\bm{e}_{j}^{T}Q_{i}\otimes\bm{e}_{i}^{T})$
$\displaystyle=\left(\bm{e}_{j}\otimes
Q_{j}\bm{e}_{i}+Q_{i}\bm{e}_{j}\otimes\bm{e}_{i}\right)^{T}.$ (8)

Now, we observe that $\bm{e}_{j}\otimes Q_{j}\bm{e}_{i}$ is the vectorization
of a matrix whose $j^{th}$ column is $Q_{j}\bm{e}_{i}$, i.e., the matrix
$Q_{j}\bm{e}_{i}\bm{e}_{j}^{T}$. Similarly, $Q_{i}\bm{e}_{j}\otimes\bm{e}_{i}$
is the vectorization of a matrix whose $i^{th}$ row is
$(Q_{i}\bm{e}_{j})^{T}$, i.e., the matrix $\bm{e}_{i}\bm{e}_{j}^{T}Q_{i}$.
Hence,
$(\bm{e}_{j}^{T}\otimes\bm{e}_{i}^{T})K=\textrm{vec}(Q_{j}\bm{e}_{i}\bm{e}_{j}^{T}+\bm{e}_{i}\bm{e}_{j}^{T}Q_{i})^{T}$,
as desired.

Plugging into Eq. 7,

$\displaystyle L\textrm{vec}(\Delta_{(t+1)}-\Delta_{(t)})$
$\displaystyle=-\eta RK\textrm{vec}(\Delta_{(t)})$ $\displaystyle\Rightarrow
L\textrm{vec}(\Delta_{(t+1)})$ $\displaystyle=L\textrm{vec}(\Delta_{(t)})-\eta
RK\textrm{vec}(\Delta_{(t)})$
$\displaystyle\Rightarrow\textrm{vec}(\Delta_{(t+1)})$
$\displaystyle=\Big{(}L^{\dagger}L-\eta
L^{\dagger}RK\Big{)}\textrm{vec}(\Delta_{(t)})$
$\displaystyle\Rightarrow\textrm{vec}(\Delta_{(t+1)})$
$\displaystyle=\Big{(}R-\eta RL^{\dagger}K\Big{)}\textrm{vec}(\Delta_{(t)})$
$\displaystyle=R\Big{(}I_{n^{2}}-\eta
L^{\dagger}K\Big{)}\textrm{vec}(\Delta_{(t)}),$

where we used the facts that $(\Delta_{t})_{ij}=(\Delta_{(t+1)})_{ij}=0$ for
disallowed edges, and $L^{\dagger}L=R$ and $LR=RL=L$, which can be easily
confirmed by inspection of these diagonal matrices.

We use Lyapunov theory to analyze the convergence of pairwise negotiation
dynamics. In particular, we need the the discrete Lyapunov equation, also
called the Stein equation.

######  Theorem 7.11 (Callier and Desoer (1994) 7.d)

For the discrete-time dynamical system $\bm{x}_{t+1}=A\bm{x}_{t}$, with
$\bm{x}_{t}\in\mathbb{R}^{n}$, the following are equivalent:

  1. 1.

The system is globally asymptotically stable towards $\bm{0}$.

  2. 2.

For any positive definite $R\in\mathbb{R}^{n\times n}$, there exists a unique
solution $X\succ 0$ to the equation

$AXA^{T}-X=-R$

  3. 3.

For any eigenvalue $\lambda$ of $A$, $\lvert\lambda\rvert<1$.

Pairwise negotiation dynamics can be described as a discrete-time linear
system in $\textrm{vec}(\Delta_{t})$, where $\Delta_{t}$ is the price
difference at time $t$. Clearly, the system converges iff $\Delta_{t}$
approaches zero. Therefore, we can use the Stein equation to prove global
asymptotic stability conditions.

We will also need the commutation matrix.

######  Lemma 7.12 (Horn and Johnson (2008))

Let $\Pi^{(n,n)}:\mathbb{R}^{n^{2}}\to\mathbb{R}^{n^{2}}$ be a permutation
matrix (called the $(n,n)$ commutation matrix) defined as
$\Pi^{(n,n)}=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\bm{e}_{i}\bm{e}_{j}^{T}\otimes\bm{e}_{j}\bm{e}_{i}^{T}$.
Then for any $A,B\in\mathbb{R}^{n\times n}$, we have

$\displaystyle A\otimes B=\Pi^{(n,n)}(B\otimes A)(\Pi^{(n,n)})^{T}$

Recall that for a linear operator $T$ that $\sigma(T)$ denotes the eigenvalues
of $T$. We are ready to prove Part 1 of Theorem 2.14.

######  Proposition 7.13 (Part 1 of Theorem 2.14)

Let $L,R,K$ be defined as in Theorem 7.9. For a matrix
$X\in\mathbb{R}^{n^{2}\times n^{2}}$ let $X\mid_{R}$ denote the principal
submatrix of $X$ corresponding to the nonzero rows/columns of $R$. Define
$\eta^{\star}=2/\left\|(L^{\dagger}K)\mid_{R}\right\|$. Then, for any
$\eta\in(0,\eta^{\star})$, $\textrm{vec}(\Delta_{(t)})$ is globally
asymptotically stable towards $\bm{0}$.

###### Proof 7.14

Proof of Proposition 7.13. Let $T=R(I-\eta L^{\dagger}K)$. By Theorem 7.11,
the dynamics are globally asymptotically stable towards $\bm{0}$ iff for all
$\lambda\in\sigma(T)$, we have $\lvert\lambda\rvert<1$.

From Eq. 8 for a prohibited edge $(i,j)$, we see that
$(\bm{e}_{j}^{T}\otimes\bm{e}_{i}^{T})K=\bm{0}^{T}$, since
$Q_{i}\bm{e}_{j}=\bm{0}=Q_{j}\bm{e}_{i}$. Hence, $K=RK$. Taking transposes and
noting that both $K$ and $R$ are symmetric, we find $KR=K$. Hence, $T=R(I-\eta
L^{\dagger}K)=R(I-\eta L^{\dagger}K)R$, where we used $R^{2}=R$. Thus, $T$ is
zero except for the principal submatrix corresponding to the nonzero columns
of $R$. So, to apply Theorem 7.11, we only require $\lvert\lambda\rvert<1$ for
$\lambda\in\sigma(T\mid_{R})$.

For clarity of exposition we will first consider the case where $R=I$ (no
prohibited edges). Then, the eigenvalues of $T\mid_{R}=T$ equal
$1-\eta\lambda$, where $\lambda\in\sigma(L^{-1}K)=\sigma(L^{-1/2}KL^{-1/2})$
by a similarity transformation. Also, $K=U_{1}+U_{2}$, where
$U_{1}=\sum\limits_{r=1}^{n}\big{(}\bm{e}_{r}\bm{e}_{r}^{T}\otimes
Q_{r}\big{)}$ and
$U_{2}\vcentcolon=\sum\limits_{r=1}^{n}\big{(}Q_{r}\otimes\bm{e}_{r}\bm{e}_{r}^{T}\big{)}$.
The matrix $U_{1}$ is block diagonal with positive-definite blocks $Q_{r}\succ
0$, so $U_{1}\succ 0$. By Lemma 7.12, $U_{2}$ is similar to $U_{1}$ via a
permutation matrix, so $U_{2}\succ 0$. Hence, $K\succ 0$, and
$L^{-1/2}KL^{-1/2}\succ 0$. So, the eigenvalues of $L^{-1}K$ are real and
positive. Hence, we have convergence iff for all $\lambda\in\sigma(L^{-1}K)$,
we have $1>(1-\eta\lambda)^{2}=1-2\eta\lambda+\eta^{2}\lambda^{2}$, i.e.,
$\lambda<2/\eta$. Hence, $\eta^{\star}=2/\|L^{-1}K\|$ as required.

Now we consider the prohibited edges setting ($R\neq I$). Here, convergence
occurs iff $|1-\eta\lambda|<1$ for all
$\lambda\in\sigma((L^{\dagger}K)\mid_{R})$. Since $RL^{\dagger}R=L^{\dagger}$
and $RKR=K$, we have
$(L^{\dagger}K)\mid_{R}=L^{\dagger}\mid_{R}K\mid_{R}=(L\mid_{R})^{-1}K\mid_{R}$.
Arguing as above, it suffices to show that $K\mid_{R}\succ 0$. We claim
$K\mid_{R}=V_{1}+V_{2}$ where $V_{1}$ is a block diagonal matrix with $i^{th}$
block equal to $(2\gamma_{i}\Psi_{i}\Sigma_{i}\Psi_{i}^{T})^{-1}\succ 0$, and
$V_{2}$ is similar to $V_{1}$ via Lemma 7.12. Hence $K\mid_{R}\succ 0$ and the
expression for $\eta^{\star}$ follows.

######  Proposition 7.15 (Part 2 of Theorem 2.14)

We define $\eta^{\star}$ as in Proposition 7.13, and $L,R,K,\alpha$ as in
Theorem 7.9. Let $\eta\in(0,\eta^{\star})$. Then,

$\displaystyle\|P(t)-P^{\star}\|_{F}$
$\displaystyle\leq\frac{\alpha^{t}}{1-\alpha}\cdot\|P(1)-P(0)\|_{F}$

Here, $P^{\star}$ is the stable point to which the negotiation converges.

###### Proof 7.16

Proof. Let $\beta$ denote the greatest eigenvalue in absolute value of
$R(I_{n^{2}}-\eta L^{\dagger}K)$. From Theorem 7.9, we have
$\|\Delta_{t+1}\|_{F}\leq\lvert\beta\rvert\|\Delta_{t}\|_{F}$. Recall that
$\lambda_{\textrm{max}},\lambda_{\textrm{min}}$ denote largest and smallest
eigenvalues of the matrix $(L^{\dagger}K)\mid_{R}$ respectively. Since
$\|R\|=1$, it follows that $\lvert\beta\rvert=\max\\{\lvert
1-\eta\lambda_{\textrm{min}}\rvert,\lvert
1-\eta\lambda_{\textrm{max}}\rvert\\}=\alpha$.

Then,

$\displaystyle\|P^{\star}-P(t)\|_{F}$
$\displaystyle\leq\sum_{i>t}\|\Delta_{i}\|_{F}$
$\displaystyle\leq\|\Delta_{t}\|_{F}(\alpha+\alpha^{2}+\ldots)$
$\displaystyle\leq\|\Delta_{t}\|_{F}\frac{\alpha}{1-\alpha}$
$\displaystyle\leq(\alpha^{t-1}\|\Delta_{1}\|_{F})\frac{\alpha}{1-\alpha}$
$\displaystyle=\|\Delta_{1}\|_{F}\frac{\alpha^{t}}{1-\alpha}$

Since $\|\Delta_{1}\|_{F}=\|P(1)-P(0)\|_{F}$ we are done.

###  7.8 Proof of Theorem 2.15

We will use a series of Lemmas to reduce the result of Theorem 2.15 to a
matrix concentration inequality in each of the $\hat{\Sigma}_{i}$.

###### Lemma 7.17

Let $\widehat{\eta^{*}},\eta^{*}$ be as in Theorem 2.15. Suppose all edges are
permitted.

Suppose that for all $i\in[n]$, we have
$\|\hat{\Sigma}_{i}^{-1}-\Sigma^{-1}\|=o(1)$. Then,
$\hat{\eta}^{\star}>\eta^{\star}(1-o(1))$.

###### Proof 7.18

Proof. Let $\hat{L},\hat{K}\in\mathbb{R}^{n^{2}\times n^{2}}$ be as in Theorem
2.15, but built using $\hat{\Sigma}_{1},\dots,\hat{\Sigma}_{n}$ instead of
$\Sigma,\dots,\Sigma$. Let $L,K$ be defined similarly to $\hat{L},\hat{K}$ but
using $\Sigma$ in place of all $\hat{\Sigma}_{i}$.

Then $\widehat{\eta^{*}}\vcentcolon=\frac{2}{\max\sigma(\hat{L}^{-1}\hat{K})}$
and $\eta^{*}\vcentcolon=\frac{2}{\max\sigma(L^{-1}K)}$.

Let $\epsilon_{L},\epsilon_{K}\in\mathbb{R}^{n^{2}\times n^{2}}$ be such that
$\hat{L}^{-1}=L^{-1}+\epsilon_{L}$ and $\hat{K}=K+\epsilon_{K}$. We will bound
$\|\epsilon_{L}\|,\|\epsilon_{K}\|$.

Let $Q_{i},\hat{Q}_{i}$ be defined as in Theorem 2.5, so
$Q_{i}\vcentcolon=(2\gamma_{i}\Sigma)^{-1}$ and
$\hat{Q}_{i}\vcentcolon=(2\gamma_{i}\hat{\Sigma}_{i})^{-1}$. Let
$\alpha=\max\limits_{i\in[n]}\|\hat{Q}_{i}-Q_{i}\|$. Notice
$\|\Gamma^{-1}\|=O(1)$, so $\alpha=o(1)$.

First, since $L$ is diagonal,
$\|\epsilon_{L}\|\leq\max\limits_{i,j\in[n]}\big{(}(\hat{Q}_{i;jj}-Q_{i;jj})+(\hat{Q}_{j;ii}-Q_{j;ii})\big{)}\leq
2\max\limits_{i,j\in[n]}\big{(}\hat{Q}_{i;jj}-Q_{i;jj}\big{)}\leq
2\max\limits_{i\in[n]}\|\hat{Q}_{i}-Q_{i}\|=2a$.

Second, let $\hat{K}\vcentcolon=\hat{U}_{1}+\hat{U}_{2}$ where
$\hat{U}_{1},\hat{U}_{2}$ are defined analogously to $U_{1},U_{2}$ in the
proof of Theorem 2.14. Letting $\Pi$ be the $(n,n)$ commutation matrix of
Lemma 7.12, we know $\hat{U}_{2}=\Pi\hat{U}_{1}\Pi^{T}$, so
$\|\epsilon_{K}\|\leq 2\|\hat{U}_{1}-U_{1}\|$. Since $U_{1},\hat{U}_{1}$ are
block diagonal with $i^{th}$ blocks $Q_{i},\hat{Q}_{i}$ respectively, it
follows
$\|\hat{U}_{1}-U_{1}\|=\max\limits_{i\in[n]}\|\hat{Q}_{i}-Q_{i}\|=\alpha$.
Hence $\|\epsilon_{K}\|\leq 2\alpha$.

Third, notice that since $\|\Sigma\|$ and $\|\Gamma\|$ are assumed to be
$O(1)$ that $\|L^{-1}\|=O(\max_{i}\|Q_{i}\|)=O(1)$ and
$\|K\|=O(\max_{i}\|Q_{i}\|)=O(1)$. So,

$\displaystyle\|\hat{L}^{-1}\hat{K}-L^{-1}K\|_{2}$
$\displaystyle\leq\|\epsilon_{L}\|\|K\|+\|L^{-1}\|\|\epsilon_{K}\|+\|\epsilon_{L}\|\|\epsilon_{K}\|$
$\displaystyle\leq 2\alpha(\|K\|+2\alpha)+4\alpha(\|L^{-1}\|+\alpha)$
$\displaystyle=4\alpha(\|K\|+\|L^{-1}\|)+8\alpha^{2}$ $\displaystyle\leq o(1)$

We conclude that $\|\hat{L}^{-1}\hat{K}\|_{2}\leq\|L^{-1}K\|_{2}+o(1)$, so
$\widehat{\eta^{*}}\geq\frac{\eta^{*}}{1+(o(1)/\|L^{-1}K\|)}\geq(1-o(1))\eta^{*}$.

###### Lemma 7.19

Suppose for $i\in[n]$, we have
$\delta_{i}\vcentcolon=\|\hat{\Sigma}_{i}-\Sigma\|=o(1)$. Then
$\|\hat{\Sigma}_{i}^{-1}-\Sigma_{i}^{-1}\|=o(1)$.

###### Proof 7.20

Proof. Weyl’s inequality implies that
$\lambda_{min}(\hat{\Sigma}_{i})\geq\lambda_{min}(\Sigma)-\|\hat{\Sigma}_{i}-\Sigma\|$.
Therefore,

$\displaystyle\|\hat{\Sigma}_{i}^{-1}\|$
$\displaystyle=\frac{1}{\lambda_{min}(\hat{\Sigma}_{i})}$
$\displaystyle\leq\frac{1}{\lambda_{min}(\Sigma)-\delta_{i}}$
$\displaystyle=\frac{1}{\lambda_{min}(\Sigma)}\Big{(}1+\frac{\delta_{i}}{\lambda_{min}(\Sigma)}+O\Big{(}\Big{(}\frac{\delta_{i}}{\lambda_{min}(\Sigma)}\Big{)}^{2}\Big{)}\Big{)}$
$\displaystyle=\|\Sigma^{-1}\|(1+o(1))$
$\displaystyle\Rightarrow\|\hat{\Sigma}_{i}^{-1}-\Sigma^{-1}\|$
$\displaystyle=\|\Sigma^{-1}(\Sigma_{i}-\hat{\Sigma}_{i})\hat{\Sigma}_{i}^{-1}\|$
$\displaystyle\leq(1+o(1))\|\Sigma^{-1}\|^{2}\delta_{i}$ $\displaystyle\leq
o(1)$

The last step follows from the fact $\|\Sigma^{-1}\|=O(1)$.

The hypothesis of Lemma 7.19 follows from standard concentration bounds for
random covariance matrices.

######  Theorem 7.21 (Vershynin (2018), 4.7.3)

Suppose $\Sigma\in\mathbb{R}^{n\times n}$ is positive definite and
$\hat{\Sigma}\in\mathbb{R}^{n\times n}$ is a covariance estimate generated via
$m$ samples from a $\mathcal{N}(\bm{0},\Sigma)$ distribution, as in Theorem
2.15. There exists an absolute constant $c>0$ such that for all $u>0$, with
probability $\geq 1-2e^{-u}$,

$\displaystyle\|\Sigma-\hat{\Sigma}\|_{2}\leq
c\|\Sigma\|_{2}\bigg{(}\sqrt{\frac{n+u}{m}}+\frac{n+u}{m}\bigg{)}$

Theorem 2.15 follows easily.

###### Proof 7.22

Proof of Theorem 2.15 Suppose $m=\left\lceil n\log n\right\rceil$. We will
first consider the case of all edges permitted; the proof for prohibited edges
is almost identical.

Applying Theorem 7.21 to each $\hat{\Sigma}_{i}$, a union bound gives
$\|\Sigma-\hat{\Sigma}_{i}\|\leq 2\sqrt{2}c\|\Sigma\|\sqrt{\frac{n}{m}}$ for
all $i\in[n]$ with probability at least $(1-2e^{-n})^{n}\geq 1-e^{-n+O(\log
n)}\geq e^{-\Omega(n)}$. Since $\|\Sigma\|=O(1)$ and $\frac{n}{m}=o(1)$, this
simplifies to $\|\Sigma-\hat{\Sigma}_{i}\|=o(1)$ for all $i$. By Lemmas 7.17
and 7.19, we have $\hat{\eta}^{*}\geq\eta^{*}(1-o(1))$ with probability at
least $1-e^{-\Omega(n)}$.

If there are prohibited edges, then we must use matrix concentration to bound
$\max\sigma(\hat{L}^{\dagger}\hat{K})$ instead of
$\max\sigma(\hat{L}^{-1}\hat{K})$. Notice that prohibited edges have the
effect of simply zeroing out certain rows and columns of $Q_{i}$, so that
$Q_{i}\vcentcolon=\Psi_{i}(2\gamma_{i}\Psi_{i}^{T}\Sigma_{i}\Psi_{i})^{-1}\Psi_{i}^{T}$,
rather than $(2\gamma_{i}\Sigma_{i})^{-1}$. Therefore, we can use Theorem 7.21
to bound $\|\Psi_{i}^{T}\hat{\Sigma}_{i}\Psi_{i}-\Psi_{i}^{T}\Sigma\Psi_{i}\|$
for all $i$, and then prove the appropriate analogue of Lemma 7.17. In
particular, the sample size requirement remains the same.

###  7.9 Proof of Proposition 2.16

[Restatement of Proposition 2.16.] Finding the maximum likelihood estimator of
$\Sigma$ under Assumption 2.4 is equivalent to the following SDP:

$\displaystyle\min\limits_{\Sigma}\sum\limits_{t=1}^{T-1}\|\Sigma(W(t+1)-W(t))+(W(t+1)-W(t))\Sigma\|_{F}^{2}$
$\displaystyle\Sigma\succeq 0$ $\displaystyle\textrm{tr}(\Sigma)=1$

Recall that in Assumption 2.4 we assumed that $M_{ij}(t)$ varies independently
according to a Brownian motion with the same parameters for all $(i,j)$. To
avoid ambiguity, we recall the definition of a standard Brownian motion as
follows.

######  Definition 7.23 (Brownian Motion)

For $d\geq 1$, a $d$-dimensional Brownian motion with scale parameter
$\sigma>0$ is a stochastic process $\\{\bm{X_{t}}:t\geq 0\\}$ such that
$\bm{X_{t}}\in\mathbb{R}^{d}$ for all $t$, the components of $\bm{X_{t}}$ are
independent, and for all $j\in[d]$,

i) The process $\\{(\bm{X_{t}})_{j}:t\geq 0\\}$ has independent increments

ii) For $r>0$, the increment $(\bm{X_{t+r}})_{j}-(\bm{X_{t}})_{j}$ is
distributed as $N(0,r\sigma^{2})$.

iii) With probability $1$, the function $t\mapsto\bm{X_{t}}$ is continuous on
$[0,\infty)$.

We can derive the SDP of Proposition 2.16 as follows.

###### Proposition 7.24

Under Assumption 2.4, the maximum likelihood estimator for $\Sigma$ is the
unique $\Sigma\succ 0$ such that $tr\Sigma=1$ and

  * •

Consistency: For all $t\in[T]$,

$\displaystyle W(t)\Sigma+\Sigma W(t)$
$\displaystyle=\frac{1}{2}(M(t)+M(t)^{T})\quad\text{for some $M(1),M(2),\ldots
M(t)$}$

  * •

Minimum mean shift: The resulting $M(1),\dots,M(T)$ minimize the objective

$\displaystyle\sum\limits_{t=1}^{T-1}\|M(t+1)-M(t)\|_{F}^{2}$

###### Proof 7.25

Proof of Proposition 7.24.

$\displaystyle P(M(1),\ldots,M(T)$ $\displaystyle\mid
W(1),\ldots,W(T),\Sigma)$ $\displaystyle\propto P(W(1),\ldots W(T)\mid
M(1),\ldots,M(T),\Sigma)\cdot P(M(1),\ldots,M(T)\mid\Sigma)$
$\displaystyle=\left(\prod_{t=1}^{T}\mathds{1}_{W(t)\Sigma+\Sigma
W(t)=0.5(M(t)+M(t)^{T})}\right)\left(\prod_{t=1}^{T-1}P(M(t+1)-M(t))\right)$
$\displaystyle=\left(\prod_{t=1}^{T}\mathds{1}_{\textrm{vec}(W(t))=0.5(\Sigma\otimes
I+I\otimes\Sigma)\textrm{vec}(M(t)+M(t)^{T})}\right)\left(\prod_{t=1}^{T-1}\exp(-\frac{\|\textrm{vec}(M(t+1)-M(t))\|^{2}}{2\sigma^{2}})\right),$

where the first step follows from Bayes’ Rule, the second step from Corollary
2.6, and the third from Assumption 2.4. The theorem follows from the
observation that for any matrix $X$, we have
$\|\textrm{vec}(X)\|^{2}=\|X\|_{F}^{2}$.

The proof of Proposition 2.16 follows easily.

###### Proof 7.26

Proof of Proposition 2.16. By Proposition 7.24, we obtain the SDP

$\displaystyle\min\limits_{\Sigma}\sum\limits_{t=1}^{T-1}\|M(t+1)-M(t)\|_{F}^{2}$
$\displaystyle\forall t\in[T]:W(t)\Sigma+\Sigma W(t)$
$\displaystyle=\frac{1}{2}(M(t)+M(t)^{T})$

under the assumptions of $\Sigma\succ 0$ and $\textrm{tr}(\Sigma)=1$. Since
the Frobenius norm is invariant under transposes, we have

$\sum\limits_{t=1}^{T-1}\|M(t+1)-M(t)\|_{F}^{2}\propto\sum\limits_{t=1}^{T-1}\|(M(t+1)+M(t+1)^{T})-(M(t)+M(t)^{T})\|_{F}^{2}.$

We can replace $M(t)+M(t)^{T}$ with $2W(t)\Sigma+2\Sigma W(t)$ for all
$t\in[T]$ to obtain the equivalent objective function
$\sum\limits_{t=1}^{T-1}\|(W(t+1)-W(t))\Sigma+\Sigma(W(t+1)-W(t))\|_{F}^{2}$
(up to a constant). This substitution enforces the fixed point equation
$W(t)\Sigma+\Sigma W(t)=\frac{1}{2}(M(t)+M(t)^{T})$ for all $t\in[T]$, so the
conclusion follows.

######  Remark 7.27 (The prohibited edges setting.)

Proposition 2.16 generalizes straightforwardly to the setting of prohibited
edges. Let $E$ denote the set of permitted edges. Then minimum mean shift
assumption is equivalent to minimizing
$\sum\limits_{t=1}^{T-1}\sum\limits_{\\{i,j\\}\in
E}\big{(}M(t+1)+M(t+1)^{T}-M(t)-M(t)^{T}\big{)}_{ij}^{2}$. In words, the
objective just zeroes out prohibited edges, since mean estimates for
prohibited edges have no effect on the network. For a network setting
$(\bm{\mu}_{j},\Sigma,\gamma_{j},\Psi_{j})_{j\in[n]}$, some algebra gives
$M(t)_{ij}=\bm{e}_{i}^{T}2\gamma_{j}(\Psi_{j}^{T}\Psi_{j})\Sigma(\Psi_{j}^{T}\Psi_{j})W(t)\bm{e}_{j}$.
Notice $\Psi_{j}^{T}\Psi_{j}\in\mathbb{R}^{n}$ is a diagonal matrix with
$(\Psi_{j}^{T}\Psi_{j})_{ii}=1$ if $\\{i,j\\}\in E$ and zero otherwise.
Therefore, it is clear that upon substitution, the objective is an SDP in
$\Sigma$ with the same constraints.

###  7.10 Proof of Theorem 3.1

[Restatement of Theorem 3.1.] Suppose that all firms use Eq. 2 as their
utility function. Consider the setting where $\Sigma_{i}=I_{n}$, $\Gamma=I$.
If there exists a pair of nodes $(k,\ell)$ such that
$\mu_{k\ell}\neq-\mu_{\ell k}$ and $|\mu_{k\ell}+\mu_{\ell k}|<2\lambda$, then
there is no stable equilibrium.

###### Proof 7.28

Proof of Theorem 3.1. First, we analyze equilibria under the modified utility
function $g_{i}(w)$. Notice that the Hessian of $g_{i}(\bm{w})$ behaves as
though $\lambda=0$, since the second derivatives of $\|w\|_{1}$ are zero. So
the Hessian is indeed negative definite, and so the optimal contracts of agent
$i$ are given by solving $\nabla_{\bm{w}}g_{i}(\bm{w})=\bm{0}$.

Let $sgn:\mathbb{R}\to\mathbb{R}$ be the sign function

$\displaystyle sgn(x)=\begin{cases}1&x>0\\\ 0&x=0\\\ -1&x<0\end{cases}$

Then $\nabla_{\bm{w}}g_{i}(\bm{w})=\bm{0}$ iff
$\bm{w}=\frac{1}{2}(M-P)\bm{e}_{i}-\lambda\cdot sgn(\bm{w})$, where we apply
$sgn(.)$ elementwise. Thus, $W=\frac{1}{2}(M-P)-\lambda\cdot sgn(W)$. Taking
transposes and noting that $W=W^{T}$ and $P=-P^{T}$, we have
$W=\frac{1}{2}(M+M^{T})-\lambda\cdot sgn(W)$. Let $H=\frac{M+M^{T}}{2}$. Then,
for all $k,\ell\in[n]$:

$\displaystyle H_{k\ell}$ $\displaystyle=W_{k\ell}+\lambda\cdot
sgn(W)_{k\ell}$

Observe that the absolute value of the right hand side is either $0$ (for
$W_{k\ell}=0$) or greater than $\lambda$. Hence, there is no stable network if
there exists $(k,\ell)$ such that $H_{k\ell}\neq 0$ and $|H_{k\ell}|<\lambda$.

###  7.11 Proof of Theorem 3.2.

[Restatement of Theorem 3.2.] Consider a network setting with
$\Sigma_{i}=\Sigma$ for all firms. Let $W$ be the corresponding stable
network. If the perceived covariance changes as $\Sigma\mapsto c\Sigma$ for
some $c>0$, the stable point changes to $W\mapsto(1/c)W$.

###### Proof 7.29

Proof of Theorem 3.2. The theorem follows from Corollary 2.6.

###  7.12 Proof of Theorem 3.3.

[Restatement of Theorem 3.3.] Consider a network setting with
$\Sigma_{i}=\Sigma$ and $\Gamma=\gamma I_{n}$. Suppose the covariance changes
as $\Sigma\mapsto\Sigma^{\prime}\succ\Sigma$. Let $W$ and $W^{\prime}$ be the
stable points under $\Sigma$ and $\Sigma^{\prime}$ respectively. Then,

$\displaystyle\textrm{tr}(M^{T}(W^{\prime}-W))<0,$

where $M$ is the matrix of expected returns.

###### Proof 7.30

Proof of Theorem 3.3. By Corollary 2.6,
$\textrm{vec}(W)=\gamma^{-1}(\Sigma\otimes
I+I\otimes\Sigma)^{-1}\textrm{vec}(\frac{M+M^{T}}{2})$. Let
$K=\gamma(\Sigma\otimes I+I\otimes\Sigma)$ and
$K^{\prime}=\gamma(\Sigma^{\prime}\otimes I+I\otimes\Sigma^{\prime})$. Since
$\Sigma^{\prime}\succ\Sigma$ it follows that $K^{\prime}\succ K$. Therefore
$K^{-1}\succ(K^{\prime})^{-1}$.

So, since
$\textrm{vec}(W^{\prime}-W)=((K^{\prime})^{-1}-K^{-1})\textrm{vec}(\frac{M+M^{T}}{2})$,
we immediately obtain
$\frac{1}{2}\textrm{vec}(M+M^{T})^{T}\textrm{vec}(W^{\prime}-W)<0$. Since
$W,W^{\prime}$ are symmetric it follows that
$\textrm{vec}(M^{T})^{T}\textrm{vec}(W^{\prime}-W)=\textrm{vec}(M)^{T}\textrm{vec}(W^{\prime}-W)$.
So we have $\textrm{vec}(M)^{T}\textrm{vec}(W^{\prime}-W)<0$.

Since
$\textrm{vec}(M)^{T}\textrm{vec}(W^{\prime}-W)=\textrm{tr}(M^{T}(W^{\prime}-W))$,
the conclusion follows.

###  7.13 Proof of Theorem 3.4

[Restatement of Theorem 3.4.] Suppose $\Sigma_{i}=\Sigma$ for all firms. Then,
for any $i,j\in[n]$, the value of $W_{ij}$ is monotonic with respect to
$M_{ij}$ (the $i^{th}$ component of $\bm{\mu}_{j}$).

###### Proof 7.31

Proof of Theorem 3.4. Let $(\lambda_{i},\bm{v}_{i})$ denote the $i^{th}$
eigenvalue and eigenvector of $\Gamma^{-1/2}\Sigma\Gamma^{-1/2}$, and let
$V_{ij}=\bm{e}_{i}^{T}\bm{v}_{j}$. By Corollary 2.6,

$\displaystyle W$
$\displaystyle=\Gamma^{-1/2}\left(\sum_{r=1}^{n}\sum_{s=1}^{n}\frac{\bm{v}_{r}^{T}\Gamma^{-1/2}(M+M^{T})\Gamma^{-1/2}\bm{v}_{s}}{2(\lambda_{r}+\lambda_{s})}\bm{v}_{r}\bm{v}_{s}^{T}\right)\Gamma^{-1/2}$
$\displaystyle\Rightarrow\frac{\partial W_{ij}}{\partial M_{ij}}$
$\displaystyle=\bm{e}_{i}^{T}\Gamma^{-1/2}\left(\sum_{r=1}^{n}\sum_{s=1}^{n}\frac{\bm{v}_{r}^{T}\Gamma^{-1/2}(\bm{e}_{i}\bm{e}_{j}^{T}+\bm{e}_{j}\bm{e}_{i}^{T})\Gamma^{-1/2}\bm{v}_{s}}{2(\lambda_{r}+\lambda_{s})}\bm{v}_{r}\bm{v}_{s}^{T}\right)\Gamma^{-1/2}\bm{e}_{j}$
$\displaystyle=(\gamma_{i}\gamma_{j})^{-1}\left(\sum_{r=1}^{n}\sum_{s=1}^{n}\frac{\bm{v}_{r}^{T}(\bm{e}_{i}\bm{e}_{j}^{T}+\bm{e}_{j}\bm{e}_{i}^{T})\bm{v}_{s}}{2(\lambda_{r}+\lambda_{s})}(\bm{e}_{i}^{T}\bm{v}_{r})(\bm{v}_{s}^{T}\bm{e}_{j})\right)$
$\displaystyle=(\gamma_{i}\gamma_{j})^{-1}\left(\sum_{r=1}^{n}\sum_{s=1}^{n}\underbrace{\frac{V_{ir}V_{js}+V_{jr}V_{is}}{2(\lambda_{r}+\lambda_{s})}(V_{ir}V_{js})}_{Z_{rs}}\right)$
$\displaystyle=(2\gamma_{i}\gamma_{j})^{-1}\left(\sum_{r=1}^{n}\sum_{s=1}^{n}Z_{rs}+\sum_{s=1}^{n}\sum_{r=1}^{n}Z_{sr}\right)$
$\displaystyle=(2\gamma_{i}\gamma_{j})^{-1}\sum_{r=1}^{n}\sum_{s=1}^{n}\left(Z_{rs}+Z_{sr}\right)$
$\displaystyle=(2\gamma_{i}\gamma_{j})^{-1}\sum_{r=1}^{n}\sum_{s=1}^{n}\frac{\left(V_{ir}V_{js}+V_{jr}V_{is}\right)^{2}}{2(\lambda_{r}+\lambda_{s})}>0.\Halmos$

###  7.14 Proof of Proposition 3.7

[Restatement of Proposition 3.7] Let $\Sigma$ have the eigendecomposition
$\Sigma=V\Lambda V^{T}$. Then for $i,j,k,\ell\in[n]$,

$\displaystyle\frac{\partial W_{ij}}{\partial
M_{k\ell}}=\frac{1}{2}\sum\limits_{s,t\in[n]}\frac{V_{is}V_{ks}V_{jt}V_{\ell
t}+V_{is}V_{\ell s}V_{jt}V_{kt}}{\lambda_{s}+\lambda_{t}}.$ (9)

###### Proof 7.32

Proof. This can be proved using the same steps as in the proof of Theorem 3.4.

###  7.15 Hardness of Source Detection

We begin by defining

$\displaystyle\left|\frac{\partial W_{ij}}{\partial
M_{k\ell}}\right|_{approx}$
$\displaystyle\vcentcolon=\frac{\left|V_{in}V_{kn}V_{jn}V_{\ell
n}\right|}{2\lambda_{n}}.$ (10)

This approximates the right hand side of Eq. 3 when the term corresponding to
the smallest eigenvalue $\lambda_{n}$ dominates the sum. We now show that if
the corresponding eigenvector $\bm{v}_{n}$ is random, source detection becomes
impossible.

######  Proposition 7.33 (Hardness of Source Detection)

Suppose $\bm{v}_{n}$ is Haar-distributed, that is, $\bm{v}_{n}$ is distributed
uniformly on the unit sphere $S^{n-1}$. Then, if $\Sigma=V\Lambda V^{T}$ and
$\Gamma=I$,

$\displaystyle\mathop{\mathbb{P}}\left[\max\limits_{i,j\in[n]:(i,j)\neq(k,\ell)}\left|\frac{\partial
W_{ij}}{M_{k\ell}}\right|_{approx}<\left|\frac{\partial
W_{k\ell}}{M_{k\ell}}\right|_{approx}\right]\leq O\left(\frac{1}{n}\right).$

###### Proof 7.34

Proof of Proposition 7.33. Without loss of generality we can set $k=1,\ell=2$
(the analysis of $k=\ell$ is identical). Notice that $\left|\frac{\partial
W_{ij}}{M_{k\ell}}\right|_{approx}$ is maximized at the $(i,j)$ that maximizes
$\lvert V_{in}V_{jn}\rvert$.

Now, consider $(i,j)\in\\{(1,2),(3,4),\dots,(n-1,n)\\}$. Notice the
distribution of $\bm{v}_{n}$ is permutation-invariant by assumption. Hence the
joint distribution of $(V_{in},V_{jn})$ is the same for all such pairs
$(i,j)$. Hence the distribution of $\lvert V_{in}V_{jn}\rvert$ is also the
same for all such $(i,j)$. Therefore,

$\displaystyle\mathop{\mathbb{P}}\left[\arg\max\limits_{(i,j)\in\\{(1,2),(3,4),\dots,(n-1,n)\\}}\left|\frac{\partial
W_{ij}}{M_{12}}\right|_{approx}=(1,2)\right]\leq O(1/n)\qquad\Halmos$

###  7.16 Proofs of Proposition 4.2

[Restatement of Proposition 4.2] Suppose $M,\Sigma,\Gamma$ exhibit community
structure (Eq. 4), and all the error terms $(\epsilon_{i})_{i\in[n]}$ and
$(\epsilon^{\prime}_{\theta_{i},j})_{i,j\in[n]}$ are independent and
identically distributed. Let $\pi:[n]\to[n]$ be any intra-community
permutation, and let $\Pi:\mathbb{R}^{n}\to\mathbb{R}^{n}$ be the
corresponding column-permutation matrix: $\Pi(\bm{e}_{i})=\bm{e}_{\pi(i)}$.
Then, $W$ and $\Pi^{T}W\Pi$ are identically distributed.

###### Proof 7.35

Proof. Let $H=\frac{1}{2}(M+M^{T})$. The fixed point equation for $W$ is given
by Corollary 2.6 as $\Sigma W\Gamma+\Gamma W\Sigma=H$. Vectorization implies
$(\Gamma\otimes\Sigma+\Sigma\otimes\Gamma)\textrm{vec}(W)=\textrm{vec}(H)$.
Let $X\sim Y$ denote that a pair of random variables $X,Y$ are identically
distributed. We want to show $\Pi^{T}W\Pi\sim W$. Vectorization gives
$\textrm{vec}(\Pi^{T}W\Pi)=(\Pi^{T}\otimes\Pi^{T})\textrm{vec}(W)$. Let
$P=(\Pi^{T}\otimes\Pi^{T})$ and $K=(\Gamma\otimes\Sigma+\Sigma\otimes\Gamma)$
for shorthand.

In this notation, we want to show that $PK^{-1}\textrm{vec}(H)\sim
K^{-1}\textrm{vec}(H)$. Since $P$ is a permutation, we have
$PK^{-1}\textrm{vec}(H)=PK^{-1}P^{T}P\textrm{vec}(H)=(PKP^{T})^{-1}P\textrm{vec}(H)$.
Since the collections of random variables $\\{\epsilon_{i}\\}_{i}$ and
$\\{\epsilon_{\theta_{i},j}^{\prime}\\}_{i,j}$ are independent, we know
$\textrm{vec}(H)$ and $K$ are independent. So to show
$(PKP^{T})^{-1}P\textrm{vec}(H)\sim K^{-1}\textrm{vec}(H)$ it suffices to show
that $P\textrm{vec}(H)\sim\textrm{vec}(H)$ and $PKP^{T}\sim K$.

Notice $P\textrm{vec}(H)=\textrm{vec}(\Pi^{T}H\Pi)$. Hence, we want to show
$\Pi^{T}H\Pi\sim H$, which holds iff $\Pi^{T}(M+M^{T})\Pi\sim M+M^{T}$. Notice
that $\Pi^{T}M^{T}\Pi=(\Pi^{T}M\Pi)^{T}$, so if $\Pi^{T}M\Pi\sim M$ then we
obtain $\Pi^{T}M^{T}\Pi\sim M^{T}$ as well. It suffices to show
$\Pi^{T}M\Pi\sim M$.

Similarly, we can simplify
$PKP^{T}=\Pi^{T}\Sigma\Pi\otimes\Pi^{T}\Gamma\Pi+\Pi^{T}\Gamma\Pi\otimes\Pi^{T}\Sigma\Pi$.
It suffices to show $\Pi^{T}\Gamma\Pi\sim\Gamma$ and
$\Pi^{T}\Sigma\Pi=\Sigma$.

We are left to show that $\Pi^{T}\Sigma\Pi=\Sigma$ and $\Pi^{T}A\Pi\sim A$ for
$A\in\\{\Gamma,M\\}$.

Proof of $\Pi^{T}\Sigma\Pi=\Sigma$. Let $i,j\in[n]$. Then
$(\Pi^{T}\Sigma\Pi)_{ij}=\Sigma_{\pi(i),\pi(j)}=g(\theta_{\pi(i)},\theta_{\pi(j)})$.
Since $\pi$ only commutes members within communities,
$g(\theta_{\pi(i)},\theta_{\pi(j)})=g(\theta_{i},\theta_{j})=\Sigma_{ij}$. So
$\Pi^{T}\Sigma\Pi=\Sigma$.

Proof of $\Pi^{T}\Gamma\Pi\sim\Gamma$. Notice $\Pi^{T}\Gamma\Pi$ and $\Gamma$
are both diagonal. Let $i\in[n]$. Then
$(\Pi^{T}\Gamma\Pi)_{ii}=\Gamma_{\pi(i),\pi(i)}=h(\theta_{\pi(i)})+\epsilon_{\pi(i)}=h(\theta_{i})+\epsilon_{\pi(i)}$.
Since $\theta_{i}=\theta_{\pi(i)}$, we know
$\epsilon_{i}\sim\epsilon_{\pi(i)}$. The conclusion follows.

Proof of $\Pi^{T}M\Pi\sim M$. Let $i,j\in[n]$. Then
$(\Pi^{T}M\Pi)_{ij}=M_{\pi(i),\pi(j)}=f(\theta_{\pi(i)},\theta_{\pi(j)})+\epsilon_{\theta_{\pi(i)},\pi(j)}^{\prime}=f(\theta_{i},\theta_{j})+\epsilon_{\theta_{i},\pi(j)}^{\prime}$.
Since $\theta_{j}=\theta_{\pi(j)}$, we know that
$\epsilon_{\theta_{i},\pi(j)}^{\prime}\sim\epsilon_{\theta_{i},j}^{\prime}$,
and the conclusion follows.

###  7.17 Proof of Theorem 4.4

[Restatement of Theorem 4.4] Consider two network settings
$S=(\bm{\mu}_{i},\Sigma,\gamma_{i})_{i\in[n]}$ and
$S^{\prime}=(\bm{\mu}_{i},\Sigma,\gamma_{i}^{\prime})_{i\in[n]}$ which differ
only in the risk-aversions of firms
$J=\\{j\mid\gamma_{j}\neq\gamma^{\prime}_{j}\\}\subseteq[n]$. Then, there
exists a setting
$S^{\dagger}=(\bm{\mu}_{i}^{\dagger},\Sigma,\gamma_{i})_{i\in[n]}$ such that
$\bm{\mu}_{i}=\bm{\mu}^{\dagger}_{i}$ for all $i\notin J$ and the stable
networks under $S^{\dagger}$ and $S^{\prime}$ are identical.

###### Proof 7.36

Proof of Theorem 4.4. First, consider the network settings $S$ and
$S^{\prime}$. Let $\Gamma\in\mathbb{R}^{n\times n}$ be a diagonal matrix with
$\Gamma_{i,i}=\gamma_{i}$; define $\Gamma^{\prime}$ similarly under
$S^{\prime}$. Let the corresponding networks be $W$ and $W^{\prime}$, and let
$\Delta_{W}=W^{\prime}-W$ and $\Delta_{\Gamma}=\Gamma^{\prime}-\Gamma$. By
Corollary 2.6, we have

$\displaystyle\Sigma W\Gamma+\Gamma W\Sigma$
$\displaystyle=\frac{M+M^{T}}{2}=\Sigma
W^{\prime}\Gamma^{\prime}+\Gamma^{\prime}W^{\prime}\Sigma$
$\displaystyle\Rightarrow\frac{M+M^{T}}{2}$
$\displaystyle=\Sigma(W+\Delta_{W})(\Gamma+\Delta_{\Gamma})+(\Gamma+\Delta_{\Gamma})(W+\Delta_{W})\Sigma$
$\displaystyle=\Sigma W\Gamma+\Gamma
W\Sigma+\Sigma\Delta_{W}\Gamma+\Gamma\Delta_{W}\Sigma+\Sigma
W\Delta_{\Gamma}+\Delta_{\Gamma}W\Sigma+\Sigma\Delta_{W}\Delta_{\Gamma}+\Delta_{\Gamma}\Delta_{W}\Sigma$
$\displaystyle\Rightarrow\Sigma\Delta_{W}\Gamma+\Gamma\Delta_{W}\Sigma$
$\displaystyle=-(\Sigma
W\Delta_{\Gamma}+\Delta_{\Gamma}W\Sigma+\Sigma\Delta_{W}\Delta_{\Gamma}+\Delta_{\Gamma}\Delta_{W}\Sigma)$
$\displaystyle=-(\Sigma
W^{\prime}\Delta_{\Gamma}+\Delta_{\Gamma}W^{\prime}\Sigma)$ (11)

Next, consider $S$ versus $S^{\dagger}$. Suppose that $M^{\dagger}$ has
columns $\bm{\mu}_{1}^{\dagger},\dots,\bm{\mu}_{n}^{\dagger}$ and let
$\Delta_{M}=M^{\dagger}-M$. Let $W^{\dagger}$ be the fixed point network under
$S^{\dagger}$, given by $\Sigma W^{\dagger}\Gamma+\Gamma
W^{\dagger}\Sigma=\frac{M^{\dagger}+(M^{\dagger})^{T}}{2}$. Let
$\Delta_{W}^{\dagger}=W^{\dagger}-W$. Then a similar argument gives:

$\displaystyle\frac{\Delta_{M}+\Delta_{M}^{T}}{2}=\Sigma\Delta_{W}^{\dagger}\Gamma+\Gamma\Delta_{W}^{\dagger}\Sigma$
(12)

Therefore, from Eq 11 and 12, it follows that $W^{\prime}=W^{\dagger}$ if

$\frac{\Delta_{M}+\Delta_{M}^{T}}{2}=-(\Sigma
W^{\prime}\Delta_{\Gamma}+\Delta_{\Gamma}W^{\prime}\Sigma).$

Hence, $W^{\prime}=W^{\dagger}$ if we set $\Delta_{M}=-\Sigma
W^{\prime}\Delta_{\Gamma}$.

It remains to show that $M^{\dagger}$ differs from $M$ only in columns
corresponding to $J$. Suppose that $i\not\in J$. Then
$\gamma_{i}=\gamma_{i}^{\prime}$, so $\Delta_{\Gamma}\bm{e}_{i}=\bm{0}$. We
conclude that $\Delta_{M}\bm{e}_{i}=\bm{0}$ and hence
$M\bm{e}_{i}=M^{\dagger}\bm{e}_{i}$.

##  8 Experimental Details

###  8.1 Fama-French Stock Market Data

We use the Fama-French value-weighted asset returns dataset, for 96 assets
over 625 months (Fama and French 2015).

###  8.2 OECD International Trade Data

We use international trade statistics from the OECD to get quarterly
measurements of bilateral trade between 46 large economies, including the top
15 world nations by GDP OECD (2022). The data are available at the OECD
Statistics webpage (https://stats.oecd.org/). The data are measured quarterly
from Q1 2010 to Q2 2022. We take the sum of trade flows $i\to j$ and $j\to i$
to measure the weight of an edge $\\{i,j\\}$.

To obtain the corresponding $\Sigma$, we run our inference procedure (Section
2.4). Since there is no data for within-country trade, the network has no
self-loops ($W_{ii}=0$). So we modify the inference according to Remark 7.27
in Appendix 7.9.

###  8.3 Outlier Detection Simulation

The experiments in Figure 5 proceed as follows. Fix a number of communities
$k$ and number of firms $n$. Fix a value of $\sigma>0$. For us, $k=2$,
$n\in\\{20,100,300\\}$, and $\sigma\in\\{\sigma_{1},\dots,\sigma_{10}\\}$,
where the $\sigma_{i}$ are logarithmically spaced on the interval $[0.1,1]$,
so that

$\displaystyle\sigma\in\\{0.1,0.12915497,0.16681005,0.21544347,0.27825594,$
$\displaystyle 0.35938137,0.46415888,0.59948425,0.77426368,1.0\\}$

For a setting of $n,k,\sigma$, we perform the following simulation $m=500$
times.

Generate communities. Generate the community membership matrix
$\Theta\in\\{0,1\\}^{n\times k}$ with rows independently and uniformly at
random from $\\{\bm{e_{1}},\dots,\bm{e_{k}}\\}$.

Generate the network setting. The deterministic functions $f,g,h$ for
$M,\Sigma,\Gamma$ respectively are as follows. First
$f(\theta_{1},\theta_{2})=f(\theta_{2},\theta_{1})=1$ and $f=0$ otherwise.
Next, let $G\in\mathbb{R}^{k\times k}$ be the matrix
$G_{ij}=g(\theta_{i},\theta_{j})$. Then $G$ is generated from a normalized
Wishart distribution centered at $I_{k}$ and with $5$ degrees of freedom.
Finally, $h(\theta_{i})=1$ for all $i$.

The noise variables for agent beliefs are as follows. Sample i.i.d.
$\epsilon_{i}$ according to a $N(0,\sigma^{2})$ distribution truncated to
$[-0.5,0.5]$ for all $i$. Sample
$\epsilon_{\theta_{i},j}^{\prime}\overset{\mathrm{iid}}{\sim}N(0,\sigma^{2})$
for all $i,j$.

Designate an outlier. Set the the noise parameter $\epsilon_{1}=-0.5$ for firm
$1$ (the risk-seeker), so as $\sigma\to 0$, $\gamma_{1}$ gets further
separated from all other $\gamma_{i}$.

Outlier detection simulation. Then for a random firm $i$ such that
$\theta_{i}\neq\theta_{1}$, we test whether the outlier
$\hat{j}\vcentcolon=\arg\max\limits_{j:\theta_{j}=\theta_{1}}\lvert
W_{i,j}\rvert$ is equal to the true outlier firm $1$.

Collate results. Once the $m=500$ runs are completed for a single setting of
$n,k,\sigma$, we obtain an estimate $\hat{p}$ for the probability of
successful deviator detection at this setting of parameters. We plot a
confidence interval
$[p-2\sqrt{\frac{\hat{p}(1-\hat{p})}{m}},p+2\sqrt{\frac{\hat{p}(1-\hat{p})}{m}}]$.
This is plotted on the $y$-axis. The $x$-axis quantifies how much $\gamma_{1}$
deviates from the mean, in terms of the number of standard deviations of the
truncated normal distribution $\epsilon_{i}$.