key: cord-0597692-0vyc95nh
authors: Klages-Mundt, Ariah; Minca, Andreea
title: Optimal Intervention in Economic Networks using Influence Maximization Methods
date: 2021-02-02
journal: nan
DOI: nan
sha: 944a51c11bf644f8e9cbe80347479ffae649bf62
doc_id: 597692
cord_uid: 0vyc95nh

We consider optimal intervention in the Elliott-Golub-Jackson network model and show that it can be transformed into an influence maximization problem, interpreted as the reverse of a default cascade. Our analysis of the optimal intervention problem extends well-established targeting results to the economic network setting, which requires additional theoretical steps. We prove several results about optimal intervention: it is NP-hard and additionally hard to approximate to a constant factor in polynomial time. In turn, we show that randomizing failure thresholds leads to a version of the problem which is monotone submodular, for which existing powerful approximations in polynomial time can be applied. In addition to optimal intervention, we also show practical consequences of our analysis to other economic network problems: (1) it is computationally hard to calculate expected values in the economic network, and (2) influence maximization algorithms can enable efficient importance sampling and stress testing of large failure scenarios. We illustrate our results on a network of firms connected through input-output linkages inferred from the World Input Output Database.

Following the global crisis due to the Covid-19 medical and economic contagion, governments have unleashed unprecedented macroeconomic stimulus. The variety of proposed stimulus, both in government financing and in monetary policy form, aims to support value in a shocked global economy. The tools to support value following a systemic shock are there since the financial crisis, and new ones are being proposed. One difference to the financial crisis is that the shock originated then from within the financial system and the main intervention target were systemically important institutions, i.e. those whose failure would lead to a large impact on the economy. In this crisis the shock was external and created disruptions to many economic sectors worldwide. Consequently, intervention is much wider.

One lesson learned from the financial crisis is that network effects underpin systemic importance, which can be measured based on the size of loss cascades, see e.g, [2, 14] or centrality measures, see [7] and the references therein. Work on systemic risk measures, e.g., [11, 9, 18, 5] , led to different axiomatic frameworks for capital requirements such that aggregate risk is acceptable. Notably, aggregation functions underlying these systemic risk measures can account for interconnections. In [3, 4, 10] , authors explore optimal capital and liquidity intervention, and derive insights into the intervention target in stylized coreperiphery banking networks subject to the risk of bank runs. Their methods are applied for small banking systems. In [1] , authors cast the intervention problem in the context of the Eisenberg-Noe model [16] as a mixed integer-programming problem, and propose a notion of of -optimality to solve it approximately. They apply their methods to the Korean banking system. In contrast to these past works, our paper focuses on the computational aspect of optimal intervention problems, which becomes critical when the number of eligible firms is large. When entire sectors are hit by shocks rather than a few large institutions, one needs to understand the systemic impact of groups of firms and optimally decide on where to intervene. Such problem quickly becomes computationally hard. The government's criterion is to maximize the overall value in the system under a budget constraint.

Our model abstracts away from the details of interventions, and relies on the notion of value of an organization -firm, sector, country-introduced in [17] in the context of crossholdings. Without intervention, if the value of the organization drops below a failure threshold, there are failure losses and the values of the connected organizations drop as well and so on. This is also in the spirit of the distress notion in [26] , which allows for contagion before the point of default. The failure threshold is interpreted as the value below which the organization ceases operations. Intervention can be seen as a way to increase an organization's value or alternatively lower its failure threshold. Several types of interventions can be modeled by a decrease in the failure threshold of an organization. Government bailouts could take the form of equity infusions, as they did in the financial crisis. Central banks are injecting liquidity in the economy via various asset purchase programs, including more recently corporate debt purchases.

It is clear that direct government financing allows firms to survive by directly lowering the failure threshold. The effect of asset purchase programs(APP) is more subtle. A point of contention is whether asset purchase programs involve liquidity injection, or whether it involves value injection. When central banks can purchase corporate debt they change the outcome in debt markets. 1 An unavoidable fact of APP is that, whenever the central bank purchases illiquid assets to intervene in liquidity, it must price those assets in some way. Models are usually used to calculate a 'fundamental value'. When acting as a lender of last resort, central banks may essentially accomplish bailout functions.

When designing and implementing interventions, it is critical to consider long-term moral hazard effects. Firm default is an important long-term filter that incentivizes strong and competent management. The prospect of intervention can disincentivize proper risk management, enabling additional short-term profits to management and equity holders while transferring tail risks to government. Note, however, that interventions can be shaped to reduce moral hazard (e.g. by organizing bail-ins by the creditors and thereby diluting equity holders). In [8] , authors endogenize intervention for a network of banks. In their paper, a bail-in can be organized in equilibrium if and only if the regulator's no-intervention threat is credible, namely in the last stage of the game she could optimally abandon intervention. Our work is complementary and could be used for the last stage of such a game, as we seek to find who will receive intervention.

Moral hazard is outside the scope of our model, but it is perhaps less relevant to a crisis like the Covid-19 where the shock was exogenous and global than it was to the mostly endogenous financial crisis. Given the widespread need to preserve value in this crisis, we focus on the specific question of how to design targeted interventions that exploit network effects while leaving the precise micro structure of those interventions as a separate problem.

Our work is also part of the broader literature on targeting in networks, see e.g., [6, 19] , and in particular the literature on optimal diffusions of products or innovations or influence maximization, [15, 21, 22] . Our contributions are summarized below. This paper. We construct an economic network intervention model and show how it can be solved via influence maximization (Section 2). Our analysis extends well-established targeting results to the economic network setting, which requires additional theoretical steps over the classical setting. For instance, the 'influence matrix' is more complex (∼ the Neumann series of the matrix in a linear influence setting that is column-substochastic with zero diagonals) and the structure of 'activations' is more nuanced. We contribute the following results, which provide the legwork for adapting powerful targeting algorithms to solve several economic network problems:

1. We prove that it is NP-hard to optimize the economic network intervention and additionally hard to approximate to a constant factor in polynomial time (Theorem 1 and Corollary 1).

2. We prove that, when modified to consider expected values under random thresholds, the intervention problem is monotone submodular (Theorem 2) and thus admits a greedy polynomial time (1 − 1/e − )-approximation (Corollary 2).

3. We show that similar results extend to a related problem: identifying large failure cascade scenarios. We prove that it is NP-hard to find the worst case failure scenarios given a maximum sized aggregate shock to asset values (Theorem 3). Under randomized thresholds, a similar greedy approximation is applicable.

4. We show two practical consequences of Theorem 3 in Section 3.3. (1) It is computationally hard to calculate expected values in the economic network. (2) Influence maximization algorithms can allow us to find approximate worst case failures, which we suggest can enable efficient importance sampling and stress testing.

We demonstrate a proof-of-concept of optimal intervention approximation applied to economic networks constructed from the World Input-Output Database (Section 4).

In this section, we supplement the Elliot-Golub-Jackson network contagion model [17] to incorporate targeted interventions. We then provide an overview and definition of influence maximization problems and relate the intervention problem in economic networks to an influence maximization problem.

We define an economic network (C, D, β, θ, p) based on the Elliot-Golub-Jackson network contagion model as follows:

• n firm nodes The matrix C describes the linear cross-holding relationships between firms. If a firm i's market value (defined next) falls below its threshold θ i , it incurs an extra failure cost β ii . We assume C is column sub-stochastic as otherwiseĈ −1 is not well-defined. Notice that this also means that I − C is invertible because the spectral radius ρ(C) < 1.

The network propagates asset values and defaults across firms in the network. We illustrate this conceptually in Figure 1 . D describes the mapping of underlying assets (blue nodes) to firms (orange nodes). C describes cross-holdings between firms. The breach of a threshold triggers failure costs, which propagate to other firms through C.

Firm book values are given by In [17] , they show that the matrixĈ(I − C) −1 is column-stochastic.

Node value = linear function of assets, connected nodes If node value < threshold, nonlinear default cost incurred Default costs propagate through holdings Figure 1 : Financial network propagation mechanism.

Lattice of solutions. As defined, there is always a solution for v. The set of solutions forms a complete lattice via Tarski's fixed point theorem. Further, supremum and infimum exist (best and worst cases). The analysis in [17] focuses on the best case solution as other solutions in the lattice are due to self-fulfilling failures.

Intervention lowers thresholds. Beyond the core model from [17] , we add a vector of intervention payments γ ≥ 0, which affect the default status of firms. Given an intervention profile γ, firm i now defaults if

An intervention via this mechanism effectively lowers the failure threshold of firms. This is consistent with real-world intervention mechanisms as discussed in the introduction.

Our analysis builds on influence propagation research in social networks. This work has historically studied processes like diffusion of technological innovation, beliefs, product adoption, and viral content. A natural question is how to engineer such a viral cascade given information about the network.

A model for this problem is specified as follows:

• U is the set of nodes in the network.

• f (S) a set function that outputs the vector of influence exerted by the activation of node set S ⊆ U on each node in U (i.e., f u (S) = influence exerted on node u). We assume f (∅) = 0.

• w(S) outputs an importance weighting of node set S. In the simplest setting, each node is weighted by 1.

•θ is the vector of thresholds for each node. A node u becomes activated if the influence exerted on it is ≥θ u .

• b is the budget for influencing nodes.

Integral Influence Maximization, studied in [21], focuses on maximizing the weighted number of activated nodes by finding an optimal seed set S 0 to activate with payments of sizeθ u for each u ∈ U subject to budget b. An influence cascade is calculated in stages.

Given an initial set of activated nodes S 0 , we construct the set of nodes S i (for i ≥ 1) activated by the set S i−1 by adding the nodes u such that

The cascade process converges to a final set of activated nodes S. The optimization problem is max

Fractional Influence Maximization, studied in [13] , is a generalization of the integral case. In this problem, we choose a payment vector x subject to budget b to exert influence on seed nodes. An influence cascade is again calculated in stages. An initial set of activated nodes S 0 is composed of nodes u for which x u ≥θ u . We construct the subsequent sets of nodes S i (for i ≥ 1) activated by the set S i−1 by adding the nodes u such that

Note that this assumes that direct influence is additive with influence from other vertices in the network, in the sense that node activated in next stage if and only if this condition satisfied. The cascade process converges to a final set of activated nodes S. The optimization problem is max

where 1 is the all-ones vector. The amounts can be a fraction of the thresholds of the nodes. This allows more efficient use of budget b to influence an effective seed set S. In particular, this takes advantage of the fact that we don't have to spend as much to influence a node that already has partial influence exerted from other influenced nodes. For simple influence models, like the Linear Threshold Model and Triggering Set Model, these problems are NP-hard, as shown in [21] and [13] . Further, they are also hard to approximate within any general nontrivial factor.

However, when we consider a modified problem with randomized thresholds-e.g., if activation thresholds for influence are uniform random variables-then the problem changes enough in expectation to lower complexity. In particular, the expected cascade size σ(S 0 ) := E[w(S)|S 0 ] from a given seed set S 0 (with similar definition for σ(x)) is monotone submodular and allows a greedy approximation that is provably within (1 − 1/e) ≈ 63% of optimal ([21], [13] ).

[23] proved this for more general threshold models and distributions forθ. In particular, letting F u be the distribution function ofθ u , σ(S 0 ) is monotone submodular given that the following functions are monotone submodular: f , w, and F u • f u for all u ∈ U .

We define these greedy algorithms formally in Appendix B and discuss influence maximization algorithms further with regard to applications in Section 4.

We can interpret the intervention problem in the economic network model as the following: given an impending default cascade, how do we find an optimal intervention to limit defaults to an acceptable level.

To do this, suppose that the set of nodes that would default without intervention is T . Now reduce the system to only look at effects on the nodes in T , while preserving the entire network structure. In particular, define the following • I T = diagonal matrix with I uu = 1 for u ∈ T and 0 otherwise.

• Ψ(T ) maps to a system on the non-zero diagonal coordinates of I T . Essentially, Ψ(T )

is the |T | × |U | matrix obtained by dropping zero rows of I T .

We can apply the above map to transform the system to look at

This transformation removes firms that don't fail without intervention, while preserving the networked connections through such nodes. The idea is that among the firms who would fail without intervention, some of them will be saved by direct intervention. Their value would then go above the failure threshold and in particular the failure costs are reversed. In a reverse causal relation of failure, other firms would be indirectly saved because their value would also increase. As we demonstrate in this section, the economic network intervention problem becomes an influence maximization problem on this transformed system. To simplify notation, we will proceed where applicable without the bar notation, but assuming we're working in the transformed problem. The direct influence function under the influence maximization version of the problem is

This accounts for the effect on book values across the network of reversing default costs in the S nodes (the first term), which pushes other nodes closer to their influence (or failure reversal) thresholds. In the typical influence maximization problem, a node in S does not exert influence on itself. This is complicated in the economic network intervention problem because the reversal of a node's default has an effect on itself through cross-holdings. However, notice that the intervention γ does not need to cover the cost of β because this cost disappears when the market value would otherwise be evaluated above threshold. The second term in f (S) removes this self-influencing effect from the influence function as it is instead represented in reduced influence thresholds.

for initial defaulting set T and node u ∈ T . This represents how much book values would need to change in order for the failure of u to be reversed. This can also be thought of as the slack below threshold in the economic network. We can obtain this from taking

the divergence of book value from the failure threshold (measured in book value), and subtracting the self-influencing effect described above. An intervention γ in the economic network setting is then analogous to a vector x in the fractional influence setting, and can be defined similarly for integral influence.

In the previous section, we set up an economic network intervention model that transforms into an instance of an influence maximization problem. We now prove theoretical properties of the intervention model. We prove that it is NP-hard to optimize the economic network intervention and additionally hard to approximate to a constant factor in polynomial time. Additionally, we prove that the influence maximization instance of the problem, when modified to consider expected values under random thresholds, is monotone submodular, and thus drawing from results in [23] and [13] , admits a (1 − 1/e − )-approximation in polynomial time.

In our first result, we show that the optimal economic network intervention problem is NPhard. Note that this result is not a consequence of influence maximization hardness results in, e.g., [21] , [13] , [20] . While we can transform the economic network intervention model into an instance of influence maximization, that does not mean that the general hardness of influence maximization extends to this case. Theorem 1. Let (C, D, β, θ, p) be a financial system with n firms and deterministic thresholds θ, and let 0 ≤ < α ≤ 1. Suppose αn firms fail in the financial system equilibrium. Then it is NP-hard to determine whether there exists an intervention γ i ≥ 0 with γ 1 ≤ b such that at most n nodes fail after the intervention.

The proof is a reduction from independent set. A consequence of this is the following corollary describing hardness of approximation.

Optimal economic network intervention cannot be approximated to within a constant factor in polynomial time.

The economic network setting is different from the typical influence maximization setting because the aim is to reverse defaults that occur. In particular, there is a cascade of defaults, and we try to construct a reverse cascade that counteracts this. This also means that we can identify the hierarchy of defaults in initial economic network model. It's interesting to note that this hierarchy information doesn't guarantee us a good approximation to optimal intervention-a result of the previous corollary. While intervening on a given layer of the hierarchy necessarily prevents all failures in layers after, there are cases where only intervening on a hierarchy layer is far from optimal. Intuitively, this is because the initial default hierarchy doesn't describe all possible sequences of default; for instance, making some intervention payments in turn alters the effective hierarchy sequence.

Additionally, note that it may be much harder to approximate the optimal intervention problem than proven in Corollary 1. For example, similar influence maximization problems have approximation difficulties that scale in the dimensions of the system [13, 20] .

We now establish that a modified form of the optimal intervention problem can be wellapproximated in polynomial time. The modification incorporates randomized thresholds and reframes the problem to optimize in expectation. For instance, this can be done by treating thresholds as random variables uniformly distributed over any given uncertainty range. This can be done more generally with different threshold distributions, as we will discuss. In essence, the combinatorial complexity problems disappear in expectation. 2 We first show that the intervention problem with random thresholds is monotone submodular, connecting with results from [23] and [13] . As a result, a greedy hill-climbing algorithm provides a (1 − 1/e − )-approximation using results from [12, 24] .

Our next result establishes that the influence function in the intervention problem is monotone submodular.

Prop. 1. The function f from Eq. 1 is monotone increasing and submodular.

We need a few assumptions to prove that the objective σ for intervention problem under random thresholds is monotone submodular. The first assumption describes the randomization of thresholds and is necessary for the results of [23] to apply. It allows very general distributions of thresholds, an example of which is uniform distributions.

For u ∈ U , random thresholds θ u are independent with distribution function F u such that F u • f u is monotone increasing submodular.

The next assumption is that the influence function f is normalized-no nodes are initially activated/exert influence (i.e., have defaults reversed) if the seed set is empty. This is an easy assumption to make with fixed thresholds, as we can simply reshape the problem if there are initial non-seed activations. If we make thresholds θ random in the economic network setting, this is more complicated because the corresponding influence thresholdsθ in (2) could be 0 or negative depending on the realization of thresholds, and, if this occurs, the resultingθ distributions are not independent. This can be solved in two ways that keep the initially defaulting nodes technically fixed: (1) the randomization in thresholds can be associated withθ ≥ 0 instead of with θ, or (2) the problem can be reformulated:θ becomes the positive part in (2), initial defaults are fixed, f (∅) := 0, and whenθ u = 0, u can be added to the seed set with cost 0 (and so will be added first).

The influence function f is normalized, i.e. f (∅) = 0.

The final assumption concerns the function describing node weighting in the objective. The weight function describes how valuable it is to reverse the defaults of a given set of nodes.

In particular, the cardinality function, which weights each node equally, obeys this assumption and is consistent with aiming to minimize the number of defaults. A different fixed weighting of nodes would also obey the assumption. Assumption 3. The weight function w : 2 U → R + is normalized, monotone, and submodular.

Under these assumptions, the intervention objective function-e.g., the expected number of defaults under a given intervention-is monotone submodular based on results from [23], as formalized in the next result. Theorem 2. Given assumptions 1-3 and an instance of the economic network intervention problem with random thresholds, the σ(S 0 ) and σ(x) functions of the associated integral and fractional influence maximization problems are normalized, monotone, and submodular.

Then following the application of results in [21], there is a greedy (1 − 1/e − 1/poly(n))approximation algorithm for optimizing the expectation, as formalized in the next corollary. [Link to Proof]

We now show how these results translate to related economic network problems. We start by showing that it is additionally NP-hard to identify the worst case failure scenarios given a maximum sized aggregate shock to asset values p. Like the intervention problem, there is a (1 − 1/e − )-approximation under random thresholds. Theorem 3. Suppose (C, D, β, θ, p 0 ) is an instance of an economic network and asset prices evolve to p 1 such that p 0 1 − p 1 1 ≤ b for some maximum aggregate shock b > 0. Let 0 < < 1. Then it is NP-hard to determine if a failure cascade of size |U | is possible in (C, D, β, θ, p 1 ).

The reduction from independent set again implies a corollary result that the optimum is hard to approximate up to a constant factor in polynomial time. As in the intervention case, when reframed in terms of expectations under random thresholds, a greedy (1 − 1/e − )approximation again applies.

We now develop two practical consequences of these results: (1) it is computationally hard to calculate expected values in the economic network, and (2) approximation methods can be applied to identify adverse scenarios for the purpose of stress testing.

Hardness of calculating expected values. We next demonstrate a consequence of Theorem 3: it can be computationally hard to calculate expected values of firms in an economic network even if we have perfect information about the underlying setup. Consider a simple setting in which the prices of underlying assets p are i.i.d. Bernoulli distributed 0-1 with probability q. The probability that a specific set of b assets fail is (1 − q) b , which is nonvanishing in the scale of the network and so non-negligible for the calculation of expected value of firms when the problem is large (and potentially computationally complex). Since it is NP-hard to determine whether a large failure cascade can occur with that probability, it is in turn NP-hard to determine if the expected value is above some given level. Further, the ability to approximate will depend on the failure costs β in the network, which could be arbitrarily large in the general case, suggesting that approximation is also difficult in general under fixed thresholds.

This compares to what is typically done in financial models in practice. Firms are typically treated in isolation, i.e., not part of a network model. In this case, firm defaults are treated as independent or perhaps correlated through a simple copula. Such distributions of credit risk, such as produced by a Gaussian copula, fail to capture clustering of defaults. The resulting probability that a given fraction of firms default is exponentially unlikely as the number of firms grows, and so this computational problem does not arise in those simple models. Naturally, the assumption that firm defaults are independent is flawed, and so the complexity problems that we describe in calculating expected values may apply in realistic settings.

Identifying extreme default scenarios. While it is NP-hard to identify the worst case failure scenarios given a maximum sized aggregate shock in an economic network, it is possible to identify scenarios that approximate this up to a (1 − 1/e − ) factor with random thresholds. As a result, we can apply influence maximization approximation methods to identify shocks that produce large default cascades of similar size to the worst scenarios. A common task in finance is to stress test a financial system subject to aggregate shocks up to a particular size. It is well-known that the straightforward Monte Carlo approach to this will underestimate risks because random samples are unlikely to contain many of the extreme default scenarios (e.g., the relevance of importance sampling). Thus these approximation methods can allow us to sample more large default scenarios for inclusion in stress tests.

To demonstrate the use of our results, we consider an application of influence maximization algorithms to an economic network. We construct instances of the economic network intervention problem based on the World Input Output Database (WIOD). The data is openly available at http://www.wiod.org/home. We simulate a number of possible shocks to the resulting network and demonstrate that influence maximization algorithms can derive effective interventions using relatively modest budgets. As we might expect, we see decreasing returns to scale in the size of the budget.

The simulations we perform are intended as a proof of concept of a realistic-looking setup based on real underlying data. We stress that many parts of the setup for which data is not available remain stylized: in particular underlying assets, thresholds, failure costs, and distribution of shocks to underlying asset values. Additionally, there is naturally uncertainty about economic network structure as described by the dataset and aggregation effects from grouping entire industries of firms into single nodes.

The WIOD dataset (see, e.g., [25] ) describes the flow of resources in dollar value between different economic sectors within different nations (intermediate demand) and national final demand (e.g., GDP components, such as consumption, investment, government expenditure). The dataset includes this information for 2464 distinct economic sectors spread between 28 EU countries and 15 other major countries for the years 2000-2014.

We construct an economic network from the 2014 dataset in the following way:

• Nodes = n columns in the dataset that refer to economic sectors or final demand components • n × n array of flows between nodes from dataset, with zero rows for final demand components

• Transpose components of any negative entries in the array • Scale columns to sum to 1 (inclusive of value added, a row in the dataset that is not included in the array) or 0 if a zero column

• Zero the diagonals in the array to get C

• Fix unnecessarily bad conditioning in C by removing nodes with near zero value added (columns referring to households)

• Vector Dp = output of each node at basic prices (this is the TOT GO row in the dataset)

• Vector θ =Ĉ(I − C) −1 Dp − value added, which gives the market value assuming no defaults − value added.

• Diagonal matrix β with diagonal entries 0.1 · value added.

The vector Dp above represents initial asset values. We sample shocks to these asset values by sampling a return vector r such that the shocked asset prices are given by the component-wise multiplication Dp · (1 + r). The return vector r is sampled from a mdimensional normal distribution with the following specifications intended to sample a range of large deviations:

• Common correlation factor ρ = 0.6, Recall that Dp are underlying asset prices, and market values will have additional interrelation and correlation from the network process.

As shown in the previous section, there are greedy algorithms with (1−1/e− )-approximations. The general structure of these greedy algorithms is to start with an empty seed set S 0 and, iteratively, add the node u to S 0 that gives the maximum marginal gain. Since the thresholds are random, determining the maximum marginal gain in each step involves estimating the expected size of resulting cascades σ(S 0 ∪ {u}) for a number of nodes u. This is typically done through Monte Carlo estimation of the expectation. For large networks, these Monte Carlo approximations become prohibitively slow, although still within polynomial time. 3 In practice, heuristic algorithms are used in influence maximization to try to estimate the greedy algorithm in faster time. For instance DiscountFrac used in [13] starts with an empty seed set S 0 and iteratively adds the node u to S 0 that would exert the most total influence on the remaining unactivated nodes. In particular, given the initial activation set S at the beginning of a step, DiscountFrac picks the node u that maximizes f ({u}) 1 A\{u} 1 for remaining uninfluenced set A. We define these influence maximization algorithms formally in Appendix B.

In our simulations, we adapt DiscountFrac to choose the node u that maximizes

where S is the currently influenced set. This accounts for the cost to influence node u in the current step, given that economic network thresholds can vary significantly in size.

We simulate 5000 shocks and apply the adaptation of DiscountFrac to approximate the resulting optimal intervention problems. In this setting, we explore the effectiveness of a range of targeted intervention sizes. The results of our simulations are represented in a 2-D histogram in Figure 2 depicting the percentage of firms defaulting under a range of intervention budget sizes. In this plot, density of (x, y)-pairs is represented in the third dimension (color: light=high density, dark=low density). Additional contour lines are added to better illustrate the densities. As perhaps expected, the highest density region is near the x-axis, with density increasing with intervention budget size. Figure 3 depicts slices of the above data that show effects more concretely. In particular, we restrict to comparing the effects of a 1% targeted intervention to no intervention. Figure 3a shows histogram densities of firm defaults under the sampled shocks, illustrating that the 1% intervention effectively reduces the tails of this distribution. Note that 1-D histograms in Figure 3a are the leftmost and rightmost verticals of Figure 2 (no intervention and 1% intervention respectively). Figure 3b shows histogram densities of defaults averted under the 1% intervention relative to no intervention, which also illustrates the effectiveness. An interesting feature is the bimodal distribution of defaults averted from targeted intervention. One hypothesis to consider is that this is a result of the network cluster structure itself: there are several clusters in the network, and firms within the same cluster are more likely to default (or avert default from a nearby intervention) together. Figure 4 depicts the experimental Tail Value at Risk (TVaR) of default cascade size for different quantiles 0 < q ≤ 1. TVaR(q) is a conditional expectation, conditioned on events falling in the q-th quantile of outcomes: where |A|(b) outputs the number of defaulting firms given budget b, |U | is the number of total firms, and VaR(X; q) is the q-quantile of random variable X. Note that in our case q is a quantile of a distribution that is already modeling negative outcomes in these simulations. Also recall that q = 1 gives the unconditional expectation. Figure 4 demonstrates that relatively small budgets effectively reduce systemic risks as measured by TVaR. Experimental numbers for the percentage reduction in TVaR using an intervention budget of 1% of initial assets is presented in Table 1 .

We have shown that the optimal intervention problem is NP-hard under fixed failure thresholds. Given a network, one essentially needs to choose a set of firms among those who would otherwise default and reverse their defaults. The choice of such firms saves the max-q % Reduction in TVaR(q) 0.1 23% 0.2 29% 0.4 36% 0.6 40% 1.0 42% Table 1 : Percentage change in TVaR with quantile q of default cascade size resulting from targeted intervention with budget 1% of total initial assets.

imum value. Other related problems are also shown to be computationally hard, even if we have perfect information about the underlying setup. In particular, given a maximum aggregate shock, it is computationally hard to determine if there is a distribution of this shock across firms leading to a given fraction of the network to fail. In turn, when thresholds are random, these problems allow (1 − 1/e − )-approximations. Failure thresholds represent the points where shareholders of the firm decide to cease the operations and liquidate the asset.

In reality thresholds could be based on the expectations of large cascades and large scale liquidations. Given the complexity issues in assessing which shocks lead to such extreme scenarios, it would be interesting to explore further how strategic shareholders would make their threshold choices.

Using the approximation algorithms, we evaluate the performance of intervention under a large number of shocks. We remark a significant reduction of Tail Value at Risk of the default cascade size, even under a small intervention budget relative to total assets. This can be explained by the fact that the solution to the optimal intervention problem unveils a hierarchical or causal structure of defaults, and in practice it selects a relatively small set to directly intervene on. Most of the default cascade is then averted indirectly, by reversing failure costs and network effects. 

Proof. We will reduce from independent set to an instance of the economic network intervention problem. Our reduction follows closely that used in [20] for the linear influence model, but we note it requires additional steps to reduce independent set to the economic network intervention setting, which is a class of instances of more general influence maximization problems.

In the independent set problem, we are given an undirected graph G = (U, E) with nodes U and edges E. Given a number k, we ask if there is an independent set in G of size k.

Reduction gadget. For the reduction, construct a bipartite graph G = (U 1 ∪ U 2 , E ) as follows:

• Add each node in G to U 1 . Attach thresholds 1 |U | to these nodes.

• For each edge {i, j} ∈ E, add a node u to U 2 and add directed edges (i, u), (j, u) to E . Attach edge weights 1 |U | and thresholds 1 |U | .

• For each possible pair {i, j} / ∈ E, add two nodes u, w to U 2 and add directed edges (i, u), (j, w) to E . Attach influence weights 1 |U | and thresholds 1 |U | .

Notice the number of vertices and edges in G :

Set the desired penetration rate in G to ζ = k|U | |U | 2 −|E| (this is the fraction of nodes we want to 'activate' or 'reverse defaults' of in the economic network). Notice that

which will be the desired penetration in the reduction graph to correspond to the independent set (which we prove below).

We now show that the problem on G translates to an instance (C, β, θ, D, p) of the economic network intervention problem. Let A be the adjacency matrix of G . Since G is a 2-layer DAG, we have A t = 0 for integers t > 1. Then the Neumann series is

Notice that A is non-negative column-substochastic with zero diagonal. Thus we take C = A, andĈ is well-defined.

Claim: (β, θ, D, p) can be chosen such that, before intervention, all nodes fail with end values v = 0,θ u = 1 |U | for all u, and β ≥ 1.

To find such a (β, θ, D, p), we can setup the following system

The system has the same number of variables as dimensions. Because of the 2-layer DAG structure, it is simple to see that the system is solvable. Notice that in the equation forθ is valid. Taking failure set T , we havẽ

Claim: The effect of reversing defaults S propagates to other nodes through f (S) = Cβ 1 S .

First notice that for all nodes u,

This is a simple result because C has zero diagonal and the only nonzero entry of 1 u is the uth entry; thus there is 0 contribution from Cβ 1 u for the uth entry.

Then we have Claim: If we reverse the default of a node in U 1 , then its neighbors in U 2 are also saved from default.

Proof of claim: Suppose we reverse the default of u ∈ U 1 . Suppose w ∈ U 2 is a neighbor of u. Then w's value is affected by

Thus w's default is also reversed.

To complete the translation into the economic network intervention problem, define the following:

In intuitive terms, the corresponding economic network is a 2-layer DAG, in which the only cross-holdings are the shares in the first layer held by the second layer. In this case, the interactions are quite simple, described solely by C. In this network, every node starts in default. We can payθ = 1 |U | to reverse a node's default ("activate" a node). Our budget is b and we can choose at most k nodes to influence.

Reduction to integral case. We first consider the integral case and then extend to the fractional case. We want to select a subset S of k nodes from G such that, if we provide payments equal to theirθ, a cascade of reverse-defaults occurs of size at least ζ|U 1 ∪ U 2 | (i.e., at most |U 1 ∪ U 2 | nodes fail after intervention). This occurs if and only if G has an independent set of size k, as we prove next.

First, note that sets S ⊆ U 1 always dominate sets S ⊆ U 1 ∪ U 2 with S U 1 . This is because, by construction, activating any node in U 1 in turn activates its neighbors in U 2 whereas activating a node in U 2 does not activate its neighbors in U 1 . Since each node in U 2 has a neighbor in U 1 , it always makes sense to activate such a neighbor instead of the considered node in U 2 . Thus it is sufficient to consider only solutions in U 1 . Notice that this extends to the fractional case since threshold-crossing payments are of the same size for nodes in U 1 and U 2 .

Each node in U 1 has |U |−1 neighbors, and two nodes in V 1 share a neighbor if and only if they are neighbors in G. So if we pick the subset S ⊆ U 1 , the size of the default reverse cascade is #default reverses = |U ||S| − |{{i, j} ∈ E|i, j ∈ S}|.

E.g., if no nodes in S are connected in G, then the second term is 0 and each activated node activates itself and |U | − 1 unique nodes in U 2 for a total of |S| + (|U | − 1)|S| = |U ||S| nodes. The number of activations is ≥ |U 1 ∪ U 2 | = k|U | if and only if ∀u, v ∈ S, {u, v} / ∈ E, which is that case if and only if there is an independent set of size k in G.

Proof. Recall that the intervention problem is equivalent to an instance of an influence maximization problem. By assumption, w is normalized, monotone, and submodular, and f is normalized. And by Prop. 1, f is monotone and submodular. Notice that the intervention problem is easily normalized (in a different sense) so as to restrict each f i andθ i to the range [0, 1]. Then by Theorem 1 in [23], the integral influence problem has σ(S 0 ) normalized, monotone, and submodular. And by Theorems 2-3 in [13] , the fractional influence problem has σ(x) normalized, monotone, and submodular (note that these definitions are modified to describe non-set functions in the fractional case).

Proof. This follows using the same application of results as in [21] . In particular, the results of [12] , [24] show that a greedy hill-climbing algorithm approximates the optimum of monotone submodular problems to within a factor of (1 − 1/e). Given that σ has to be approximated, the result can be extended to show that for any > 0, there is δ > 0 such that by using (1 + δ)-approximate values for the σ function, we obtain a (1 − 1/e − )-approximation. For the fractional case, this uses Theorem 4 in [13] .

Proof. First consider a specific subclass of economic network instances. We will reduce independent set to an instance of this subclass. The subclass has the following properties:

• Asset prices p take values in {0, 1}.

• D is row-sub-stochastic, such that a firm's underlying assets can be valued at most 1.

• C = 0, in which caseĈ = I and (I − C) −1 = I.

• β = 0, in which case a firm's value is in [0, 1].

• b is an integer.

As a result, the shock to be chosen in our problem, if applied to asset i, can change it's price from 1 to 0. The problem at hand is now to find a set of b assets that, if set to 0, cause |U | firms to default.

Next consider a reformulation of the network process into a bipartite graph G as follows:

• Add nodes for each underlying asset. Denote these nodes U 1 .

• Add nodes for each firm. Denote these nodes U 2 .

• For each u ∈ U 1 , add a weighted directed edge from u to nodes in U 2 according to the matrix D. The weights here represent the effect of the asset on the book values of firms that own those assets in the simple setting with C = 0.

Assume the assets in U 1 are initially set to 1. If an asset is changed to 0, (negative) influence is exerted on its connections in U 2 via D, lowering those firms' values. If enough (negative) influence is exerted on a firm in U 2 , its value decreases below threshold, triggering default. The equivalent problem is to find a set of b nodes in U 1 such that, if set to 0, cause |U | firms to default. To reduce from independent set, we can follow essentially the same reduction as in Theorem 1 to a process on a bipartite graph like above. With appropriate definition of parameters, this is an instance of the subclass of economic networks above. And thus independent set reduces to economic network maximum shock problem.

The algorithms below use the following problem setting:

• f (S) outputs the vector of influence exerted by the activation of node set S on each node. In the analysis, we define f to give the linear threshold model.

• w(S) outputs a weight of node set S. In the analysis, we define w to weight each node by 1.

• Θ = uniform[0, 1] n is the distribution for node thresholds (n=number of nodes).

• b = budget.

CalcIntCascade(S; f, θ) Require: set S, set function f , thresholds θ

Optimal intervention under stress scenarios: A case of the korean financial system

Resilience to contagion in financial networks

Control of interbank contagion under partial information

Optimal equity infusions in interbank networks

Multivariate shortfall risk allocation and systemic risk

Who's who in networks. wanted: The key player

Riskdependent centrality in economic and financial networks

Bail-ins and bail-outs: Incentives, connectivity, and systemic stability

A unified approach to systemic risk measures via acceptance sets

Systemic risk mitigation in financial networks

An axiomatic approach to systemic risk

Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms

How to influence people with partial incentives

Managing default contagion in inhomogeneous financial networks

Mining the network value of customers

Systemic risk in financial systems

Financial networks and contagion

Measures of systemic risk

Influencing the influencers: a theory of strategic diffusion

Least-cost influence maximization on social networks

Reduction to fractional case. Notice that this easily extends to the fractional case. In this case, we want to find payments such that i γ i ≤ b = k |U | and we save ζ|U 1 ∪U 2 | nodes from failure (i.e., at most |U 1 ∪ U 2 | nodes fail after intervention). In G , all edges and thresholds have value 1 |U | . Given the structure of G , optimal node payments will obey γ i ∈ {0, 1 |U | }. This is because a payment to a node in U 1 is again always better than a payment to a node in U 2 (same argument as before), and any payment smaller than 1 |U | will result in no activation in U 1 , and hence no subsequent effect on U 2 . Thus there is one-to-one correspondence between optimal integral solutions and optimal fractional solutions. Thus the fractional case is NP-hard in general.

Proof. To simplify notation, define A := (I − C) −1 β.(Monotonicity) Let T ⊂ U and u ∈ U \ T . Then we haveSince A is non-negative, the second term is ≥ 0. The third term only affects the uth component, and then only cancels the contribution of the second term. Thus we have(Submodularity) Let S ⊆ T ⊆ U and u ∈ U \ T . From the above equations, we haveand similarly with S. Thus the submodularity condition

Require: set S, set function f , weight function w, thresholds distr. Θ, sample size k = 10, 000Algorithm 5σ(x) estimate of σ(x) for fractional influence Require: vector x, set function f , weight function w, thresholds distr. Θ, sample size k = 10, 000Initialize σ ← 0 for i ≤ k do Sample θ ∼ Θ T = CalcFracCascade x; f, θ σ ← σ + w(T ) end for return σ/k Algorithm 6 GreedyFracInfMax = Greedy algorithm for fractional influence maximization Require: set function f , weight function w, thresholds distr.Algorithm 8 Γ − (v, A) = total sum of weight of edges from node v to set A Require: set A, set function f , node v return 1 T A f ({v})

Require: set function f , weight function w, thresholds distr. Θ, budget b Initialize x 0 ← 0, i ← 0