Sensitivity and computational complexity in financial networks

1Introduction

The recent financial crisis and subsequent bailout have highlighted the need for a better understanding of the dynamics of financial networks. Indeed, the complexity of modern financial networks has been blamed for our collective failure to recognize the presence of serious risks in these systems. In this work, we show that even in extremely simple financialnetworks understanding the risk present in the system is computationally intractable in general – even in the presence of perfect information about all participants in the system. We hope that these insights will help regulators and policymakers to better understand the dynamics of financial networks.

Understanding an individual’s risk in a financial network is a difficult task, because an institution’s ability to fulfill its outgoing financial obligations is not a local property, i.e., it cannot be understood by examining a single individual in isolation. An institution’s ability to make its outgoing payments may depend on whether its incoming payments are made by its debtors, which in turn may depend on whether the incoming obligations are made to those institutions, etc. Thus each institution, acting without a global view of the network, cannot effectivelyunderstand its risk. Nevertheless, one might hope that a regulator, with a global view of the network could better understand the opportunities and risks inherent in the system. Even with a global view, the situation remains relatively complex. One complicating factor is the existence of cycles in the financial network, for example institution A may have obligations to institution B which has obligations to institution C, which in turn has obligations to institution A. The existence of these cyclical interdependencies has been put forward as one of the primary sources of complexity in financial networks. In this work, we will examine network dynamics in both cyclic (Theorem 1) and acyclic networks (Theorem 3). One of the driving forces in the study of financial networks is their ability to magnify risk: if an institution, A, defaults on its obligations to institution B, this may cause institution B to default on its obligations to institution C etc. The spread of risk through a financial network is known as financial contagion and has been carefully modeled and studied (Allen and Gale, 2000; Eisenberg and Noe, 2001; Gouriéroux, Héam, and Monfort, 2012; Acemoglu, Ozdaglar, and Tahbaz-Salehi, 2013; Glasserman and Young, 2014; Elliott, Golub, and Jackson, 2014). This work focuses on quantifying the ability of financial networks to amplify and conceal risk.

2Our contributions

In this work, we study two questions related to the stability of financial networks. First, we look at how sensitive market valuations can be to small changes in network structure. Second, we examine the computational complexity of determining how far a given network is from a massive failure. Throughout this work we use the network model put forward by Elliott (Golub, and Jackson, 2014). In this model, financial institutions own shares of underlying assets, and the institutions are connected by cross-holdings, which are modeled as linear dependencies. If an institution’s market value drops below a certain critical threshold, its value suffers a further discontinuous shock, modeling the effects of a loss of investor confidence, or the failure to pay everyday operating costs. See (Elliott, Golub, and Jackson, 2014) for an in-depth discussion of the interpretation and real-world validity of this model. The formal mathematical model is described in detail in Section 4.

Our first result (Theorem 2), shows that financial networks can be highly sensitive to small changes in their link structure. Concretely, we show that if a single institution changes a single cross-holding by ε, the market values of institutions in the system can change by as much as ε/2r, where r ≤ 1 is the minimum amount of self-holdings of the institutions in the network. The minimum self-holdings, r, is a measure of integration of the network, where r = 0 corresponds to a fully integrated network, and r = 1 corresponds to a network with no integration. This result shows that if each institution retains only, say, 5% self-ownership, a change in a single holding by ε can result in a 20ε change in an institution’s market value. This amplification is directly caused by cycles in the network, and in acyclic networks this type of magnification cannot occur (see Lemma 1). Our bounds are essentially tight, and Theorems 1 and 2, show that the true sensitivity is in fact Θ (ε/r). This sensitivity magnification has many consequences. First, it means that in order to estimate market values of institutions within the system, all cross-holdings need to be known to an extremely high degree of precision. Investors or regulators who wish to calculate market values can be extremely far off if even a single cross-holding in the network remains unknown to them. Second, because small changes in a single institution’s investments can have large effects on market values throughout the system, this indicates a potential for extreme instability in the system as a whole; the small portfolio changes in one institution can have a drastically magnified effect market values of other institutions, and so small changes by a myopic institution could topple even seemingly stable institutions. Third, this extreme sensitivity means that calculating market values in a privacy-preserving manner can be extremely difficult (Narayan, Papadimitriou, and Haeberlen, 2014). This is the flip-side of the first point, in order to calculate market values for institutions in the system, all the interbank holdings need to be known with high precision, which means that revealing market prices has the potential to reveal extremely detailed information about each institution’s interbank holdings. Our second result addresses the question of how well a regulator can assess the stability of a network. Suppose a regulator or oversight agency is presented with a network in which every bank is solvent, and suppose the regulator believes that the underlying assets cannot drop in value by more than some fixed amount d. What is the maximum number of failures that can be caused by a drop of this size in asset values? We emphasize that in this scenario, the regulator has complete information about the entire structure of the financial network, and the only uncertainty is in which specific assets may decline in value. We show calculating the number of institutions that can fail in a network is NP-Hard. In particular, we show that is as hard as calculating the maximum balanced clique in a bipartite graph (Theorem 3). The maximum balanced bipartite subgraph (BCBS) problem is NP-hard (Gary and Johnson, 1979; D.S. Johnson, 1987), and there is evidence that it is even hard to It is known that if 3-SAT is not in DTIME (2^n3/4+ε) for some ε, then there is no polynomial time algorithm for calculating the maximum balanced clique to within a factor of 2^(logn)δ for some δ > 0. Feige and Kogan (2004) go further, conjecturing that there is no polynomial time algorithm to approximate the maximum balanced bipartite clique to within a factor of n^δ for some δ > 0. This would imply that there is no polynomial time algorithm that can even estimate the maximum number of failures caused by a drop in asset values of a given magnitude to within a factor of n^δ in a network with 2n institutions. In particular, this means that there are financial networks where stress testing (which is inherently computationally feasible) cannot hope to even approximate the magnitude of collapse that could be caused by some bounded drop in assetvalues. Unlike our first result, which crucially relies on cycles in the network, this result holds even in acyclic networks: even when there are no cycles it is computationally intractable to estimate the maximum number of failures that could be caused by a bounded drop in asset values. This complexity arises not from cycles, but from the nonlinear dynamics that occur when a bank drops below its critical threshold value.

3Previous work

Many different models have been proposed to study financial networks, and specifically models of stability and contagion.

Allen and Gale (1998) considered a model consisting of depositors and banks. Depositors deposit their money in the banks, and the banks must choose between making short-term investments or long-term investments. This model has three time periods, t = 0, 1, 2. At t = 0, investments are made, at t = 1 short-term investments pay off, and depositors choose whether to withdraw their money, and at time t = 2 long-term investments pay off. The banks’ investment strategies then depend on the probability that depositors withdraw their money at time t = 1. In a follow-up work Allen and Gale (2000) introduced a network component, where banks can exchange deposits with each other in an effort to mitigate risk, and they showed simple contagion effects in this model.

Acemoglu, Ozdaglar, and Tahbaz-Salehi (2013) build on Allen and Gale’s 3 time-step model. At time t = 0 banks can make a short-term investment, a long-term investment or loan money to other banks. Long term investments yield a fixed return at t = 2. Long term investments that are liquidated at t = 1 receive a return that is randomly distributed between two values. Banks whose investments returned the lower of the two values were said to have received a shock. Acemoglu, Ozdaglar and Tahbaz-Salehi considered how two extremal types of networks serve to propagate these shocks. They considered the ring (where each bank only has debts to its two neighbors) and the complete network where each bank’s debts are spread to all other banks, as well as all convex combinations of these two. They showed that if the magnitude of the shocks are small then the complete network is more stable and resilient than the ring, and if the magnitudes of the shock are large enough then both the ring and complete networks are the least stable networks, thus the complete network exhibits a phase transition, moving from the most stable to the least stable network as the magnitude of the shocks increase.

Eisenberg and Noe (2001) developed a very simple and appealing network model where each bank has cash reserves and fixed debts to other banks. Eisenberg and Noe’s work focused on showing that (under some basic restrictions on the network) there is always a unique clearing vector (indicating how much of its debts each bank pays to its creditors), and they gave a linear program and simple iterative algorithm for calculating this clearing vector and hence the equilibrium valuation of each bank.

Gai and Kapadia (2010) considered a modification of Eisenberg and Noe’s network model, forcing all incoming edges to have the same weight, but allowed banks to have additional illiquid assets. Gai and Kapadia then considered the question of how a single bank failure propagates through a network. For this analysis, they considered different models for generating the underlying graph topology, and plotted contagion effects for different network models characterized by their degree distribution. They found that a single large shock could have devastating effects on the network, but that this was highly dependent on where in the network the shock hit.

Gouri'eroux, H'eam, and Monfort (2012) considered a model that allows interbank investment via shares (like (Elliott, Golub, and Jackson, 2014)) and lending or insurance (like (Eisenberg and Noe, 2001)). Unlike (Eisenberg and Noe, 2001)). Unlike (Elliott, Golub, and Jackson, 2014), they do not introduce discontinuous failure costs. Gourieroux, Héam and Monfort extend Eisenberg and Noe’s uniqueness results to show that (under mild constraints on the network) this extended model has a unique equilibrium value for all institutions. They then examined the effects of exogenous shocks on the network (i.e., drops in asset values) using synthetic data and data obtained from the French banking sector.

Morris (2000) studied contagion in local interaction systems. In that model, each node represents a player, and each player engages in a local game with each of its neighbors. Morris focused on the case where each player has a binary strategy space, {0, 1}, and there is a global 2 × 2 payoff matrix, such that for each edge in the graph, the two neigboring players receive a payoff according to this global payoff matrix. In that model, a strategy is said to be “contagious,” if it can spread from a finite set of players to an infinite set of players by the best-response dynamics of the underlying local game.

The notion of failure cascades and contagion have also been studied in the computer science literature by Blume et al. (2011), Blume et al. considered general cascades in graphs where the edges were unweighted and a node was said to fail if some critical threshold of its neighbors failed. By choosing all edges to have equal weight, and choosing each institution’s failure threshold carefully, the failure model of (Elliott, Golub, and Jackson, 2014) can be made to overlap with this general network failure model.

In this work, we use the model of Elliott (Golub, and Jackson, 2014). In this model, institutions can own shares in each other, or in “primitive assets” that have intrinsic value outside of the network. The model is explained in detail in the next section. Elliott, Golub and Jackson introduced this model to help analyze and understand contagion effects in networks. Because a cascade of collapse requires an initial failure, Elliott, Golub and Jackson began by showing that the weakest institution can never be made strictly more stable by any fair trade between the institutions. Next they examined the contagion dynamics in a wide class of networks parametrized by “integration” and “diversification.” Integration increases as institutions in the network increase their inter-network holdings, i.e., integration increases as the percentage of each institution owned by shareholders external to the network decreases. As integration increases, the institutions’ fates are more closely tied together. Diversification measures how risk is spread within the network. Diversification increases as institutions increase their number of cross-holdings. Neither integration nor diversification have strictly positive or negative effects on network stability, but instead have slightly more complex non-monotonic effects.

The notion of computational complexity has been studied in the context of financial products by Arora et al. who showed that banks can create derivatives that are computational intractable to price accurately (Arora et al., 2010, 2011). The result of Arora et al. crucially relies on the information asymmetry between the institution the seller (who creates the derivatives) and the buyer who only sees their resulting composition. Braverman and Pasricha (2014) show that even in the full information setting pricing compound options is PSPACE complete.

4Model

We use the model put forward by Elliott (Golub, and Jackson, 2014). In this model there are n financial institutions, these can be viewed as countries, banks or private firms, and m underlying assets, that can be viewed as any object or project with intrinsic value. The financial institutions own shares of the underlying assets which impart value into the system. The values of the institutions themselves are interconnected via a network (modeled as a weighted, directed graph). The interdependencies (cross-holdings) between the institutions are modeled as simple linear dependencies. These linear cross-holdings can model simple equity stakes (one institution owning shares in another) or they can be viewed as an approximation of more complicated debt contracts between the institutions (see (Elliott, Golub, and Jackson, 2014, Section 2.5) for a more thorough discussion of the validity and generality of this model).

Although institutions invest in one another, all value in the system originates from the underlying assets. The price of asset k is denoted by p_k, and we use D_ik ≥ 0 to denote the percentage of asset k owned by institution i. The n × m matrix of ownership is denoted by D = (D_ik).

We define C = (C_ij) to be the n × n matrix indicating the cross-holdings of institutions. Thus institution i owns a C_ij fraction of institution j. It will be be useful to view the network of cross-holdings as a directed graph with n nodes representing the financial institutions, and an edge from institution j to i of weight C_ij whenever C_ij > 0. Following (Elliott, Golub, and Jackson, 2014), we set C_ii = 0 for all i. Now, ∑_iC_ij is the fraction of institution j that is owned by institutions external to j. The remainder, the amount of self-ownership, is denoted by Cˆjj=def1-∑iCij. The matrix Cˆ will be a diagonal matrix with Cˆii on the diagonal.

As noted by Brioschi (Buzzacchi), this type of model introduces two types of valuations, the equity valuation (V→) and the market valuation (v→). The equity valuation of institution i is denoted by

In matrix notation, this becomes V→=Dp→+CV→ which implies V→=(I-C)-1Dp→. The matrix I - C is guaranteed to be invertible because we assume that Cˆjj>0, so the column sums of C are all strictly less than one (see Lemma 2). In fact, the matrix I - C, is an M-Matrix (Poole and Boullion, 1974), and so (I - C) ^-1 is an inverse M-Matrix, about which many properties are known (Willoughby, 1977; Johnson, 1982).

This equity valuation significantly overvalues the institutions. In particular, we can see that ∥V→∥1≥∥p→∥1, so the total value of the institutions in the system will (in general) be much larger than the total value of the underlying assets. This occurs because each asset counts towards the equity value of the institution that owns it and also to the institutions that have an equity stake in the asset’s owner. The network’s inflation of equity values is well-known and validated both theoretically and empirically (French and Poterba, 1991; Fedenia, Hodder, and Triantis, 1994).

To find an institution’s market value, we must scale the institution’s equity value by the percent stake it has in itself, thus the market value of institution i is vi=CˆiiVi, so the market values are the solution to the system

The matrix C is column sub-stochastic because column i sums to 1-Cˆii. The system can also be viewed as a flow, where at each time step money flows between banks according to the link structure of the network (see Appendix A).

5Sensitivity

Our first result concerns concerns the sensitivity of valuations to small changes in the structure of the network. Suppose a single institution shifts its holdings by a small quantity, ε, how much can this small change affect the market valuations in the network? This question is motivated by questions about network stability, and the possibility of privacy-preserving oversight. If small changes in network holdings can lead to large changes in the market values of the institutions, this indicates a fundamental instability in the financial network. Additionally, if small changes in interbank holdings can lead to large changes in market values, then any attempt at financial oversight must incorporate all the interbank holdings to a high degree of accuracy in order to predict market values.

A high sensitivity also has implications towards privately computing network statistics. Flood et al. (2013) proposed using tools from differential privacy (Dwork, 2006; Dwork et al., 2006) to provide a means of computing global network characteristics while preserving the privacy of each individual institution’s holdings. A high sensitivity implies a worse trade-off between privacy and accuracy when calculating network statistics.

We begin our sensitivity analysis with a simple observation: if the total value of the underlying assets is ∥p→∥, then an ε change in holdings can easily change the market valuations by ε∥p→∥ (see Fig.1). We show that if the network is acyclic, then this is the largest change possible, but if there are cycles in the network, the sensitivity can be much larger.

Fig.1

An ε change results in an ε∥p→∥ change in market values. Banks are in blue, external shareholders are in green, and the asset is shown in red. In this example Dp→=[10], and C = 0. Thus v→=[10]. Changing C to C˜=[0ε00] leads to a valuation of v→˜=[1−εε] , thus the market valuation of B₂ changes by ε∥p→∥.

Throughout this section, we use r (for “reserve”) to measure the fraction of each institution held by investors outside the system.¹ We define r=miniCˆii. Using the terminology of (Elliott, Golub, and Jackson, 2014), r is just a concrete metric of the integration of the network, and integration increases as r → 0. Another interpretation of reserve is the discrepancy between equity valuation (V→) and market valuation (v→). Since v→=CˆV→, we have that r=miniviVi.

5.2Sensitivity in general networks

In this section, we explore how much the market valuations can change when one bank changes its holdings by a small amount in the presence of cycles in the network graph. We begin by showing an upper bound on the change in market valuations that depends on the minimum self-ownership (Cˆii) of the institutions. For our upper bound, we do not require changes to occur in the holdings of a single bank. Instead, we allow any change in network structure, as long as the total (ℓ₁) change is bounded by ε. Formally, this means that we have two network matrices C and C˜ such that ∥C-C˜∥≤ε, and we would like to bound how much the market valuations can change between these two situations. Because we are showing an upper bound, allowing more general perturbations only strengthens our result.

Theorem 1. If ∥C-C˜∥<ε, then ∥v→-v→˜∥<εr∥Dp→∥, where r=mini(Cˆ˜ii,Cˆii) is the minimum reserve or “self-holdings” of the financial institutions. In addition, it is always true that ∥v→-v→˜∥≤2∥Dp→∥, thus

∥v→-v→˜∥∥Dp→∥≤min(εr,2)

Proof. Let C˜=C+E, and C˜ˆ=Cˆ+Eˆ. By hypothesis ∥E∥+∥Eˆ∥<ε. Then we have

C˜ˆ(I-C˜)-1-Cˆ(I-C)-1=[(Cˆ+Eˆ)-Cˆ(I-C)-1(I-C˜)](I-C˜)-1=[(Cˆ+Eˆ)-Cˆ(I-C)-1(I-C-E)](I-C˜)-1=[(Cˆ+Eˆ)-Cˆ(I-(I-C)-1E)](I-C˜)-1=[Eˆ+Cˆ(I-C)-1E](I-C˜)-1

Now, we notice that

∥(I-C˜)-1∥=∥∑k=0∞C˜k∥≤∑k=0∞∥C˜k∥≤∑k=0∞(1-r)k=1r

Because money is never created or destroyed, we have

∥Cˆ(I-C)-1v→∥1=∥v→∥1

Thus we have

∥C˜ˆ(I-C˜)-1-Cˆ(I-C)-1∥=∥[Eˆ+Cˆ(I-C)-1E](I-C˜)-1∥≤∥Eˆ∥·∥(I-C˜)-1∥+∥Cˆ(I-C)-1∥·∥E∥·∥(I-C˜)-1∥

Thus we immediately get the bound

∥C˜ˆ(I-C˜)-1-Cˆ(I-C)-1∥≤εr

Since ∥Cˆ(I-C)-1∥≤1, we also have the trivial bound

∥C˜ˆ(I-C˜)-1-Cˆ(I-C)-1∥≤2

The multiplicative bound of ε/r in Theorem 1 is much weaker than the bound of ε in the acyclic case (Corollary 1), as the minimum self-holdings approaches 0, this difference tends towards infinity. This discrepancy is not a limitation of our proof, but arises as an artifact of the effect that holdings cycles can have on the equity (and market) valuations of the institutions in the network. In Theorem 2 we show that there exist networks where changing a single institution’s holdings by ε results in a change of ε2r+1-r2ε∥Dp→∥ in one of the institution’s market values, where r is the minimum self-holdings in the network.

Theorem 2. There exist networks where ∥C-C˜∥≤ε, and ∥v→-v→˜∥≥ε2r+1-r2∥Dp→∥, where

v→=Cˆ(I-C)-1Dp→

and r=mini(Cˆ˜ii,Cˆii) is the minimum “self-holdings” of the financial institutions.

Proof. We exhibit an initial network in Fig. 2 and its perturbation in Fig. 3.

Fig.2

The initial configuration, banks are in blue, external shareholders are in green, and the asset is shown in red.

Fig.3

The perturbed configuration, where one link of weight ε has been moved from B₃ to B₄.

In Fig. 2, the equity values for the banks satisfy

B1=(1-r-ε)B2B2=v+(1-r)B1B3=εB2B4=0

So

B2=v+(1-r)B1=v+(1-r)(1-r-ε)B2=v+(1-r-ε-r+r2+rε)B2

Rearranging gives

B2=v+(1-r-ε-r+r2+rε)B2⇓v=(2r+ε-r2-rε)B2⇓B2=v2r+ε-r2-rε=vr(2-r)+(1-r)ε≥12(vr+1-r2ε)

Thus the market valuation of B₃ is εB₂ which is at least 12(εvr+1-r2ε).

If the link from B₂ → B₃ were moved to B₂ → B₄ (as in Fig. 3) then B₃’s value drops to zero and B₄’s value increases to εB₂.

Thus the change in ℓ₁ norm of the market valuations between the two situations is at least

εvr+1-r2ε

Writing this in matrix notation, we have

C=[01-r-ε001-r00    00ε0    0000    0]C˜=[01-r-ε001-r00000000ε00]

Cˆ=C˜ˆ=[r0000r0000100001]

Note that increasing one link by ε and decreasing another by ε is actually a change in 2ε in the ∥C-Cˆ∥. Letting ε′=ε2, we have a change of ε in ∥C-Cˆ∥ yields a change of at most ε2r+1-r2ε. Notice that as r → 0, this is approaches 2, i.e., the resulting valuation is as far as possible in terms of the ℓ₁ norm of the market values of the institutions.

The type of equity amplification necessary for the lower bound in Theorem 2 cannot happen in an acyclic network (see Corollary 1).

Now, we compare the upper and lower bounds on sensitivity. We have an upper bound of max(2,εr) and a lower bound of ε2r+1-r2ε. The lower bound implies the following.

• • For any ε, δ > 0, there exists an r with0 < r < 1 and a network with minimum reserve r such that a change in edge weights of ε can lead to a change in market valuations of at least (1 - δ) 2. Thus the upper bound cannot be decreased below 2.

• • For any r, δ, with 0 < r < 1, and 0 < δ there exists an ε with 0 < ε < 1 and a network with minimum reserve r such that a change in edge weights of ε can lead to a change in market valuations of at least (1-δ)ε2r, thus the upper bound cannot be decreased below ε2r.

Together, these show that the upper bound cannot be decreased below max(2,ε2r), so our upper bound of max(2,εr) is essentially tight. Another interpretation of the lower bound is that for any n > 0, there exists an ε, r > 0 and a network such that an ε change in one edge weight can cause a multiplicative change of nε in market malues of the institutions.

6Bank failures

6.3Multiple equilibria

When discontinuous failure penalties (b→(v→)) are introduced into the system, then there may be multiple equilibrium values for the institutions in the system, i.e., the market values may not be uniquely defined (Elliott, Golub, and Jackson, 2014, Section 2.6 and Appendix A). As noted (Elliott, Golub, and Jackson, 2014), there are two distinctly different ways a network can have multiple equilibria. The first type falls into the standard theory of bank runs (Diamond and Dybvig, 1983), and this type of multiplicity can occur even in an acyclic network. For example suppose there is a network consisting of single institution holding a single asset of value p. Let v denote the value of the institution and v_ denote its failure threshold, and β its failure penalty. If p>v_>p-β, then a valuation of v = p, and v = p - β are both consistent with Equation 3. The second type of multiplicity is caused by cycles in the network. See Fig. 4 for a simple (cyclic) network that has multiple equilibria.

Fig.4

Banks are in blue, external shareholders are in green, and the asset is shown in red. In this example Dp→=[1001], and C=[012120]. If v_i=2, and b_i = 1, then two equilibria are: v→=[11], and v→=[00]

In a network with multiple equilibria, we can talk about the “best-case” equilibrium (the one with the fewest failures) and the “worst-case” equilibrium (the one with the most failures). As in (Elliott, Golub, and Jackson, 2014), we focus on the best-case equilibrium, thus when we refer to the “the number of failures” we mean the number of failures in the best-case equilibrium.

6.5The complexity of calculating the maximum number of failures

In this section, we give our main result concerning the computational complexity of estimating themaximum number of failures that can occur given a small drop in values of the underlying assets.

In particular, this hardness result applies finding the number of failures that occur at equilibrium when the institutional cross-holdings are fixed, and completely known, but there is some small uncertainty in the prices of the underlying assets.

In the situation that the cross-holdings and the assets are fixed, it is straightforward to calculate the market values of the institutions at equilibrium (Elliott, Golub, and Jackson, 2014, Section 3.2.3). Note that the network we construct is acyclic.

Theorem 3. For every bipartite graph G on 2n nodes, and every ε > 0, For every bipartite graph G on 2n nodes, and every ε > 0, there is a financial network with Ω (n) institutions, and a d > 0 such that computing the maximum number of institutions that could fail problem in G.

Proof. Let ℓ>0 be any integer.

Our starting point is the following hardness result for the BCBS problem. Given an n × n balanced bipartite graph G, it is hard to decide whether the largest balanced bipartite clique size in G is at least K × K or at most K/g × K/g for some gap function g. For instance, g = 2^(logn)δ under the assumption that 3-SAT ∉DTIME (2^n3/4+ε) for someε > 0.

Given an n × n balanced bipartite graph G, we will construct a financial network with (2 + ℓ) n institutions such that if G has a balanced bipartite subgraph of size K, then a drop in asset prices by Kε can cause at least (2 + ℓ) K failures. On the other hand, if the largest balanced bipartite then a drop in asset prices by Kε can cause at least (2 + ℓ) K failures. Kg(ℓ+1) failures.

This shows that estimating the maximum number of failures induced by a fixed drop in asset prices is at least as hard as estimating the size of the maximum balanced bipartite clique. Without loss of generality, we assume that every vertex in G has degree at least K.

Let D denote the maximum degree of any vertex in G. Let 0 < ε < 1 be an arbitrary parameter, and let 0 < r < 1 denote the minimum amount of self-holdings of the institutions in the network we are constructing. (The reduction will hold for any choices of 0 < ε, r < 1.)

For each node in the graph G, we will associate a financial institution. Let institutions 1, …, n correspond to the left-hand nodes of G, and institutions n + 1, …, 2n correspond to the right-hand nodesof G.

We will also generate n underlying assets, labelled ai′,…,an′ and institution i will complete own asset ai′ for i = 1, …, n. Institutions n + 1, …, 2n will own none of the underlying assets. All assets will initially be valued at 1. Thus

D=[1⋱10⋱0]

Define N=D1-r (recall D is the maximum degree of G, and r is an arbitrary parameter that will determine the integration of the resulting financial network). We will use Γ (j) to denote the neighbors of vertex j in G. Notice that our definition of N ensures that

1-r=DN≥|Γ(j)|N

for all j = 1, …, 2n. This means that if institution j sells an equal 1N stake in itself to all of its neighbors, it will be left with at least an r fraction of self ownership. To operationalize this, we define

cij={1Nifi>jand(i,j)anedgeofG0otherwise

For 1 = 1, …, n let v_i=1-|Γ(i)|N-ε, so if institution i’s asset drops in value by ε then institution i will fail. Let the failure penalty βi=1-|Γ(i)|N-ε for i = 1, …, n. Thus if asset i drops in price by ε, institution i fails and its value immediately drops to 0. For i = n + 1, …, 2n let rv_i=|Γ(i)|-dN. Notice that if all assets are initially valued at 1 then

vi={1-|Γ(i)|Nif1≤i≤n|Γ(i)|Nifn<i≤2n

This financial network has the following properties:

• 1 If j > n and d of bank j’s neighbors fail, i.e., d of the assets a_i (i ∈ Γ (j)) drop in value by ε, then bank j will fail.

• 2 If j > n and the total drop in value of bank j’s neighbors is less than dN then bank j will not fail.

Now, we examine the properties of this system when the assets are allowed to drop in price by total amount dε. A drop of dε can always cause d institutions on the left-hand side of the network to fail, simply by dropping the value of each of their assets by ε.

What happens if the price drop is not concentrated among exactly d assets? Let t denote the number of assets that drop in value by at least ε. If t < d, then at least tε from the “shock budget” of dε was used to lower the price of these t assets, which leaves a budget of (d - t) ε remaining. Now, consider how much this drop can affect one of a right-hand institutions, j. Even if this drop is concentrated entirely among the left-hand neighbors of j, the drop j feels is at most

1N(t+(d-t)ε)<1N(t+(d-t))=dN

Thus institution j cannot fail, since the failure of a right-hand institution requires a drop in value of at least dN. This means that in this case exactly t < d institutions fail. Since we are interested in the maximum number of failures that can arise from a drop in asset value of dε, we can, without loss of generality, assume that exactly d assets drop in value by ε, causing exactly d failures among the left-hand institutions.

Now, suppose there is a biclique of size K in G. If d = K, then causing d failures among the left-hand members of this biclique will cause d = K failures among the right-hand members.

On the other hand, suppose the largest biclique is of size Kg. If the failure of d left-hand institutions causes the failure of P right-hand institutions, then each of the P failed institutions on the right must be connected to each of the d failed institutions on the left. Thus there must be a biclique of sizemin(d, P) = P.

Thus in the “yes” case (G has a biclique of size K) we can cause at least K right hand failures with a failure budget of Kε. In the “no” case (the largest biclique in G is of size Kg) the maximum number of failures of right-hand institutions is bounded by Kg.

Now, to amplify this discrepancy, we add a chain of ℓ institutions connected to each right hand institution. Thus for every right-hand institution, b_i, it will have a chain of institutions bi(1),…,bi(ℓ) where bi(j) owns a 1 - r fraction of bi(j-1) and has no other holdings. Thus if b_i fails, then bi(1) through bi(ℓ) fail as well (see Fig. 5).

Fig.5

There are n assets, {ai′}, shown in red. Each asset ai′ is fully owned by institution a_i. Institutions {a_i}, {b_i} correspond to a hard instance of balanced bipartite clique. Institutions {bi(j)} serve to amplify the failures that occur in the first level.

This new network has (ℓ +2) n banks, and has the following properties. Given a failure budget of Kε, if the largest balanced clique in G is a K × K, a drop in value by Kε causes at most (2 + ℓ) K, but if the largest biclique is of size Kg, then a drop in asset values of at most Kε can cause at most K+(ℓ+1)Kg=(g+ℓ+1)Kg failures.

Note that when the gap, g = n^δ, choosing ℓ = poly (n), we obtain a gap of ((ℓ +2) n) ^δ′ for some δ′ < δ.

Applying a result of Feige and Kogan (2004), we obtain the following Corollary.

Corollary 2. If 3-SAT ∉DTIME (2^n3/4+ε) for some ε > 0, then there exists a δ > 0 such that there is no polynomial time algorithm that can calculate the maximum number of failures in a financial network caused by a drop in asset prices of dε to within a factor of 2^(logn)δ′ for some δ′ > 0.

7Conclusion

This work highlights two distinct sources of instability in financial networks, instability arising from fluctuations in cross-holdings and instability arising from fluctuations in asset prices. More specifically, we show that there are networks where small fluctuations in cross-holdings or asset prices can have striking consequences, and these consequences have numerous implications.

Our first result (Corollary 1, Theorems 1, 2) shows that the effect of small changes in cross-holdings is strongly tied to the integration of the network. In highly integrated networks small changes in cross-holdings can have potentially unbounded effects on market valuations, while in networks with low integration, changes in cross-holdings have more tightly bounded effects on the market values of the institutions in the network. These results can be interpreted in many ways. From a regulatory perspective, in a highly integrated network, any regulator must know the entire cross-holdings network to a very high degree of accuracy in order effectively understand the market values of the institutions. From an institution’s perspective, small changes in investment by individual institutions can have their effects greatly magnified throughout the network. From a predictivity perspective, if one wishes to forecast market values into the future, any small forecasting uncertainty in the cross-holdings can have enormous effects on the (predicted) market values of the institutions. From a privacy perspective, institutions cannot maintain any privacy in their investment portfolios without compromising the ability of outsiders (e.g. other institutions, outside investors or regulators) to calculate the market value of the institutions. These problems arise only in highly integrated networks (Theorem 1), and they can all be mitigated by imposing a cap on integration. If institutions are required to maintain some fixed percentage of their ownership outside of the network, the sensitivity to changes in cross-holdings can be drasticallyreduced.

Our second result shows that small changes in the prices of the underlying assets can have unpredictable effects on the number of failures in the system. Specifically, we show that there are networks where it is computationally intractable, even with perfect information about the cross-holdings, to estimate the number of failures that can occur after some small drop in asset prices. This result too can be interpreted from different perspectives. This result implies that a regulator (with perfect information about the network cross-holdings) who believes there may be some bounded fluctuation in asset prices cannot be expected to distinguish a network where these fluctuations cause a small number of failures, from a network where fluctuations of the same magnitude can cause a massive number of failures. Institutions face the same computational challenge. An institution may wonder whether its investment portfolio will protect it from a bounded shock in asset prices, and our results show that even with complete information about the investments of all other agents in the system, it may be infeasible to determine whether a specific portfolio is safe.

Previous works have imposed specific probabilistic models on fluctuations in asset prices, and for a given probabilistic model the number of failures can usually be estimated. But what if the model is incorrect (e.g. the asset prices do not fluctuate independently)? Our results show that there are situations where changes in the distribution of fluctuations (but not their overall magnitude) can have huge and unpredictable effects on the number of failures.

Moving forward, it is an important research question to understand what constraints on the network will allow institutions and regulators to perform these stability analyses.