Hamed Amini
email: h.amini@math.miami.edu

Andreea Minca

Agnès Sulem
email: agnes.sulem@inria.fr

Optimal equity infusions in interbank networks

Keywords: Systemic risk, Markov decision process, Liquidity risk, Rollover risk, Financial contagion

We study optimal equity infusions into a financial network prone to the risk of contagious failures, which may be due to insolvency or to bank runs by short term creditors. Bank runs can be triggered by failures of connected banks.

Under complete information on interbank linkages, we show that the problem reduces to a combinatorial optimization problem. Subject to budget constraints, the government chooses the set of minimal cost whose survival induces the maximum network stability. Our results demonstrate that the optimal equity infusion might significantly mitigate failure contagion risk and stabilize the system. In the case of partial information on the network, the controllers' focus swiftly changes from preventing insolvencies to preventing runs by short term creditors.

Introduction

During the financial crisis, systemic risk has emerged as a major concern for governments, financial regulators and risk managers. By contrast with the traditional approach in risk management, the focus is no longer on modeling and managing the risks faced by a single financial institution, but on taking into account the interrelations between financial institutions and the complex mechanisms of distress propagation.

Limiting systemic risk requires new analytical and computational tools. Most research in this area focuses on systemic risk measurement and attribution. Recent works propose systemic risk measures within the framework of network models for insolvency risk in banking systems, see e.g. Amini et al. (2016), [START_REF] Battiston | Liaisons dangereuses: Increasing connectivity, risk sharing, and systemic risk[END_REF], [START_REF] Cont | Fear of fire sales, illiquidity seeking, and credit freezes[END_REF], [START_REF] Lehar | Measuring systemic risk: A risk management approach[END_REF]. The related issue of systemic risk attribution is addressed in [START_REF] Liu | Systemic risk components in a network model of contagion[END_REF].

Avram and [START_REF] Minca | On the central management of risk networks[END_REF], [START_REF] Blanchet | Stochastic Risk Networks: Modeling, Analysis and Efficient Monte Carlo[END_REF], [START_REF] Kley | Systemic risk in a large claims insurance market with bipartite graph structure[END_REF] extend the application field of the network framework to insurance-reinsurance markets. Network models for systemic risk have the advantage of being both structural (they integrate explicitly the details of banks' balance sheets and the interbank exposures) and tractable. Such features are crucial for determining best responses to systemic crisis. An example in this sense is [START_REF] Rogers | Failure and rescue in an interbank network[END_REF], who use networks as decision tools for the establishment of rescue consortia.

Our contribution is within the area of systemic risk management. We use network models to investigate a government's problem of optimal intervention in the form of equity infusions. This problem is motivated by the government interventions during the recent crisis, which took forms of recapitalizations, see e.g. [START_REF] Swagel | The financial crisis: An inside view[END_REF], [START_REF] Veronesi | Paulson's gift[END_REF]. The rationale and the net gain from these equity infusion programs is an important topic in the finance literature, both empirical and theoretical, see [START_REF] Bayazitova | Assessing TARP[END_REF], [START_REF] Philippon | Efficient recapitalization[END_REF], [START_REF] Philippon | Optimal interventions in markets with adverse selection[END_REF], [START_REF] Veronesi | Paulson's gift[END_REF]. Several possible reasons for equity infusion programs have been advanced in this literature (see [START_REF] Veronesi | Paulson's gift[END_REF]). One theory is that government recapitalized a banking sector that restricted lending because of debt overhang. The resulting optimization program has been investigated in [START_REF] Philippon | Efficient recapitalization[END_REF].

The second possible reason is that government intervened in order to prevent runs by short term creditors, since runs destroy value and are inefficient. Runs by short term creditors played a central role during the crisis, see Gorton and Metrick (2012a). In this paper we investigate this rationale.

Some of the questions we ask are: Is an equity infusion program such as the British equity infusion program or the US CPP (Capital Purchase Program) of 2008 justified in terms of the net gains when we take into account the runs of short term creditors? How does the optimal decision depend on the percentage of banks that use short term funding? Is the intervention budget constraint saturated at the optimal solution?1 To answer these questions, we build a model in which runs by short term creditors can be triggered by failures of connected banks. We set up an optimal equity infusion program by a government with constrained budget who aims at minimizing the total loss in the system. The loss is defined as the total capital of the failed banks, plus the write-downs recorded by surviving banks. The general model of failure propagation incorporates a bank run component on top of an insolvency component. The bank run component lowers the contagion threshold. The underlying network of exposures transmits losses among financial institutions, which then see their capital depleted and consequently may face bank runs even if they are solvent. The failure due to bank runs of some participants prompts more write-downs to their counterparties, leading to more contagion. Importantly, our model features a channel of indirect contagion. Increases in the cost of funding and possible runs can happen even in absence of exposures to failed banks, as short-term lenders may become skeptical to all short-term borrowers. Our perspective on the relation between insolvency risk and liquidity risk differs and thus complements the recent literature on funding liquidity. While, similarly to the recent singlebank funding liquidity risk models as [START_REF] He | Dynamic debt runs[END_REF], [START_REF] Liang | A multiperiod bank run model for liquidity risk[END_REF], [START_REF] Minca | Dynamics of debt capacity[END_REF], [START_REF] Morris | Illiquidity component of credit risk[END_REF], the risk of insolvency prompts creditors to withdraw funding, in our paper the insolvency risk is carried through the network. Previous models are single-bank models in which the focus is on the interaction of the short term creditors and in which the illiquidity barrier as a function of the capital is endogenous. Here, this function is exogenous, while insolvency risk comes from "far-away" in the network.

We assume that banks cannot refuse the decision of the government2 . We analyze two information settings. The first setting provides computational tools for the choice of a set of banks of minimal intervention cost and which can stabilize the network. The partial information case is highly stylized and intended to provide qualitative answers to the questions we stated above.

First, in the complete information setting, the controller observes the entire interbank exposure network. We show in Proposition 1 that the optimal equity infusion problem becomes a combinatorial optimization problem. This problem is tractable for networks of realistic sizes, several dozens of nodes, and with arbitrary structure. The idea is that complete information on the network reveals the causal structure of failures, that is, which banks fail because of bankruptcies of others. Therefore, we explore the intervention cost of insuring subsets of nodes, with the understanding that this leads to a modified causal structure of failures.

In our numerical examples, we find that the solution does not saturate the budget constraint. This result indicates that there is a tipping point, beyond which intervention is no longer optimal. it would, in effect, transfer the losses from the existing creditors and shareholders of failed banks to the taxpayer. The results in the complete information setting are given in the case of zero recovery rates, but can be extended to other recovery rate models such as [START_REF] Eisenberg | Systemic Risk in Financial Systems[END_REF], [START_REF] Rogers | Failure and rescue in an interbank network[END_REF]. The combinatorial aspect becomes relevant when the continuum of losses of the seminal paper by [START_REF] Eisenberg | Systemic Risk in Financial Systems[END_REF] is lost. This continuum is lost as soon as there are fixed and important bankruptcy costs, see e.g. Amini et al. (2016), [START_REF] Rogers | Failure and rescue in an interbank network[END_REF]. This aspect is highly relevant to systemic crisis which have an illiquidity component (such as the crisis of 2007 -2009).

In the second part of the paper we propose a partial information setting, where the controller observes the interbank exposure network in continuous time. Information about balance sheets is revealed progressively, when banks record their exposures to failed banks. We stylize the network model to obtain numerical tractability. The network is regular in structure, all nodes having the same degrees. The inhomogeneity in the model stems from the stability of the funding across banks. When intervention is adapted to the information given by the partial observation of the contagion cluster and, under certain assumptions on the distribution of the timing of when new information is learned, the cascade model is shown to become a search model. The recording of an exposure to a failed bank appears to a partial network observer as the result of a search process: A failed bank (belonging to the observed set of failed banks) will "search" for a counterparty, with a probability depending on banks' connectivities and their number of already recorded exposures. The search process is a Markov process, which consists of bilateral interactions between a failed bank and one of its counterparties. The successive interaction times correspond to the times when writedowns are recorded. To prove the equivalence in law of the cascade and the search process, we need to make an extension of the coupling argument in Amini et al. (2016) to the case of continuous time and adapted control. Our result in this setting, Theorem 1, allows us to study the cascade dynamics using a Markov Decision Process. Our results point to a strong dependence of the optimal intervention policy on the proportion of banks that use unstable short-term funding. The main takeaway message within the partial information setting is that, the presence of even a small proportion of banks using unstable funding will prompt the optimizing government to inject equity in banks that are otherwise solvent, in order to prevent a run by short term creditors.

We define the net gain from intervention as the difference between the magnitude of losses due to financial contagion with and without intervention, net of the cost to the government. We find that optimal intervention significantly mitigates financial contagion, both in the complete and partial information setting. We finally assess the value of information, namely the difference in the net gain from intervention between the complete and the partial information case. We find that the value of information is limited, as the net gain under partial information compares well with the net gain under complete information.

We show the net gain under partial information is due to a large extent to the availability of an adapted intervention strategy. Indeed, we further compare the net gain from intervention in two cases: First, the government observes the spread of distress continuously and adapts their strategy to the flow of information. Second, we restrict the government to optimally injecting equity only once after the exogenous shock applied to the system. We find that, the net gain is significantly larger in the first case, thereby justifying multiple infusions in the same bank, as it was the case in 2008.

In recent work, [START_REF] Amini | Control of interbank contagion under partial information[END_REF] have investigated other types of interventions, namely those by a lender of last resort. The results in [START_REF] Amini | Control of interbank contagion under partial information[END_REF] clearly point to the relation between the value of the financial system (defined there the sum of all external projects), connectivity and optimal intervention. Up to a certain connectivity, the value of the financial system increases with connectivity. This implies that a connected system prone to contagion and thus depending on intervention is preferable to a disconnected system. However, this is no longer the case if connectivity becomes too large and even in the case there is intervention, the value of the system may fall below the value of the disconnected system. In [START_REF] Minca | Optimal control of interbank contagion under complete information[END_REF] the problem of optimal intervention is treated in the context of [START_REF] Eisenberg | Systemic Risk in Financial Systems[END_REF], and the authors show that it may be optimal to restrict intervention to a subset of the banks.

In contrast, here we compare the two settings -partial and complete, and the main driver of the equity infusions is the existence of inefficient bank runs. It is the probability of bank runs that plays an important role in the case of incomplete information and leads the controller to have preventive infusions on otherwise well capitalized banks.

Our paper is organized as follows. In the next section we present a model for distress propagation in a network of financial institutions that are prone both to bank runs and to insolvency. The cascade dynamics in presence of the two channels of distress propagation and under intervention of a government is defined in Section 2.2. In Section 3, we study the complete information setting. We study the partial information setting in Section 4. 2 Distress propagation in a financial network

Interlinked balance sheets

At a fixed time, say time 0, a financial system is represented as a network (N , e), with N := {1, . . . , n} the set of financial institutions (banks). For any two financial institutions i and j, e(i, j) represents the exposure of i to j, i.e., the write-down of i's capital if j were to failure. The exposures e(i, j) may encompass several types of liabilities and contracts, including interbank loans or financial derivatives. Taking into account all possible liabilities between the two counterparties i and j would involve a multi-layer analysis of the financial network, see e.g. [START_REF] Bookstaber | Looking deeper, seeing more: a multilayer map of the financial system[END_REF]. This is not the aim of the present paper and we focus on one representative layer. The asset of one party is the liability of another party. If e(i, j) > 0, we also say that j has a liability to i. The total interbank assets of i are given by j e(i, j), while the total interbank liabilities of i are given by j e(j, i). We denote by s(i) the total short term debt on the balance sheet, net of the banks' liquid reserves. If s(i) is positive, then the bank depends on refinancing this net short term debt, and consequently it is prone to bank runs. In this case we let f (i) the short term funding capacity of bank i, i.e., the amount of short term debt that it can refinance on the market. If s(i) is negative, then the bank does not need to refinance this short term debt, and consequently it is not prone to bank runs. It can only failure due to insolvency.

We assume that the bank's external assets are illiquid. It is for simplicity and without loss of generality that we assume zero external debt, and such debt could easily be added to the liability side of a banks' balance sheet. We let c(i) the capital of bank i, defined as the total value of assets minus the total value of liabilities. Table 1 represents a snapshot of the balance sheet of bank i. Definition 1. A bank i is said to fail if the either one of following two conditions holds:

(i) Balance-sheet insolvency: The total value of its assets is smaller than the total value of its liabilities, i.e. c(i) < 0;

(ii) Illiquidity: The net short term debt cannot be refinanced, i.e., f (i) < s(i).

When setting the above illiquidity condition, we assume that the cannot liquidate the asset to repay this debt. We stress that s(i) is short term debt net of the liquid assets of the bank. Therefore, having more liquid assets amounts to lower net short term debt, and thus lower chances that the inequality f (i) < s(i) holds.

Assumption 1. We make the following assumptions:

(i) The bank does not sell the illiquid assets;

(ii) The bank cannot claim back its long-term interbank assets;

(iii) The bank is not acting at the same time a short term lender and a short term borrower.

The first assumption states that there is no market for the illiquid asset.3 This is a conservative setting in which banks avoid fire sales in order to avoid further asset declines and, therefore, equity depletion. In times of distress many institutions do not sell at firesale prices to avoid the obligation to record a loss, even if they are close to failure, see e.g. Diamond and Rajan (2011).

The second assumption states that long-term debtors do not repay their debt prior to maturity. Indeed, during a crisis, banks have been shown to hoard on liquidity, see e.g. [START_REF] Acharya | A model of liquidity hoarding and term premia in inter-bank markets[END_REF], [START_REF] Gale | Liquidity hoarding[END_REF], so it is reasonable to assume that they have no incentive to pay back debt before it is due.

The third assumption is a tractability assumption. If banks acted at the same time as both short term lenders and short term borrowers, then, if unable to refinance the short term debt they could withdraw funding from their own short term borrowers. Our assumption insulates our analysis from modeling the decision of each short term lender whether or not to withdraw funding. The assumption that short term borrowers and lenders are disjoint is in line with e.g, [START_REF] Geanakoplos | The leverage cycle[END_REF], [START_REF] Simsek | Belief disagreements and collateral constraints[END_REF] where short term debt is taken on by firms with limited wealth but who are optimistic about the future prospects of the illiquid asset, while it is provided by firms who are pessimistic about the value of the illiquid asset.

Distress propagation with intervention

We consider that there exists a government that makes equity infusions in the form of cash. The government has a constrained budget M and their objective is to minimize the magnitude of contagion (expressed as total loss) in the financial system.

Our model is of a short term contagion, in which case recovery rates are low because assets cannot be liquidated fast. For simplicity, we set recovery rates to zero. The cascade of failures is to be interpreted as a causal structure of failures. Under complete information on exposures, the cascade is understood as instantaneous, whereas under incomplete information the causal structure will be revealed over time.

Distress propagation begins with an exogenous set of banks D 0 , called fundamental failures, that are either insolvent or illiquid following a shock.

D 0 = {i ∈ N | c(i) < 0 or f (i) < s(i)}.
(1)

We consider that, after the exogenous shock, the government injects equity ξ(i) ∈ [0, M ] in all banks which have not failed after the exogenous shock, i.e., i ∈ D c 0 , where c denotes set complement. In this section it is helpful to think of as a deterministic quantity ξ(i) ≥ 0 that is injected instantaneously. 4After intervention, bank i ∈ D c 0 holds capital c(i) + ξ(i). We now describe the cascading failures triggered by the set D 0 of fundamentally failed banks. Let us first describe the contagion mechanism. There are three sources of contagion in the model. First, a creditor of failed bank is affected by the direct balance-sheet loss (write-down). The failure of an institution j leads to a loss equal to e(i, j) to its counterparty i. If the new capital of i reaches the failure barrier, then i fails. Second, any creditor of a failed bank will be also affected by the changes in funding conditions: A fraction of its own short-term creditors that concerned by bank i's decreased capital withdraw funds. Third, all banks depending on short term borrowing, irrespective of being a creditor of the failed bank or not, are affected by changes in the funding conditions, due to the depletion of the risk bearing capital of the financial system.

We capture the bank run component of the contagion mechanism by assuming that the short term funding capacity is a function of the bank's capital and of the number of failed banks: f (i) = f (c(i), |D|) gives the short term funding capacity of bank i when the set of failed banks is D ⊆ N . This assumption is consistent with structural models of bank runs [START_REF] He | Dynamic debt runs[END_REF], [START_REF] Liang | A multiperiod bank run model for liquidity risk[END_REF], [START_REF] Minca | Dynamics of debt capacity[END_REF], [START_REF] Morris | Illiquidity component of credit risk[END_REF] where liquidity is a function of capital and bank runs happen when the capital (usually assumed a stochastic process) reaches a barrier.

We assume that the function f is non-negative, increasing in the first argument (the capital), and decreasing in the second argument (the number of failures in the system). The condition of illiquidity (given a failure set D) in Definition 1 writes as

c(i) < f -1 (s(i), |D|),
where f -1 represents the inverse (in the first argument) of the debt capacity function f . The parallel of the insolvency condition and the illiquidity condition is now apparent: insolvency happens when capital drops below zero, while illiquidity happens when capital drops below a barrier f -1 (s(i), |D|) (given a failure set D). The higher the barrier, the more likely it is to fail. The larger the size of the failure set, the higher is the barrier. Equity infusions, in turn, decrease the failure barrier, because the function f -1 is increasing in its first argument.

If s(i) ≤ 0, i.e, the liquid reserves are larger than the short term debt, then the bank cannot fail due to illiquidity, and thus f -1 (s(i), |D|) = 0, for any failure set D. Otherwise if s(i) > 0 , the illiquidity barrier is higher than the insolvency barrier, i.e, f -1 (s(i), |D|) > 0. We generically call f -1 the failure barrier, which is either an insolvency barrier if s(i) ≤ 0 or an illiquidity barrier if s(i) > 0, in which case the failure barrier increases with the number of failures in the system.

Because the bank fails when its capital reaches the failure barrier, its loss absorbing capacity is c -f -1 . This quantity is related to the well known distance to default in [START_REF] Merton | On the pricing of corporate debt: The risk structure of interest rates[END_REF]. There it denotes the probability of bankruptcy. Since assets are deterministic, here we can think of the remaining loss absorbing capacity as a threshold to contagion.

For a bank i ∈ N and a set of failed banks D ⊆ N , the remaining capital of bank i by θ(i, D) := c(i) -j∈D e(i, j).

(2)

We are now able to specify the first round of contagious failures:

D 1 (ξ) =    i ∈ N | c(i) + ξ(i) - j∈D 0 e(i, j) < f -1 (s(i), |D 0 |)    , (3)
represents the set of banks whose failure is triggered by fundamentally failed banks, either due to direct balance sheet exposures or because of the changes in funding conditions. Their remaining capital reaches the failure barrier following the fundamental failures.

We have the following definition of cascading failures:

Definition 2 (Cascading failures). Starting from the set of fundamental failures D 0 , define D k (ξ) for k = 1, . . . , n -1 as the set of institutions whose remaining capital reaches the failure barrier following the failures in D k-1 (ξ) :

D k (ξ) =    i ∈ N | c(i) + ξ(i) - j∈D k-1 (ξ) e(i, j) < f -1 (s(i), |D k-1 (ξ)|)    , (4)
We note that this is a joint cascade of insolvencies and bank runs. We expect that under realistic scenarios the cascade will not pick up in absence of the bank run component. This is in line with [START_REF] Glasserman | How likely is contagion in financial networks[END_REF], who find that that cascades of insolvencies do not pick up in absence of an additional channel of contagion. On the other hand, in presence of an additional source of contagion they are likely to pick up. Other works that analyze multiple channels of contagion, in general cross-exposures in a network context and fire sale externalities, include [START_REF] Aldasoro | Bank networks: Contagion, systemic risk and prudential policy[END_REF], [START_REF] Battiston | Leveraging the network: a stress-test framework based on debtrank[END_REF], [START_REF] Cifuentes | Liquidity risk and contagion[END_REF], see also [START_REF] Laux | Did fair-value accounting contribute to the financial crisis?[END_REF]. The focus of our work is quite different from these works, as we study the control of this cascade.

Example 1. Suppose that the initial failure set is comprised of two banks and one bank has an exposure of 2 (units of numéraire) to these banks. If its capital is initially equal to 3, then after the write-down it becomes 1. If the bank does not depend on short term funding, then the bank does not fail. However, if the bank depends on short term funding, there may be a bank run following the write-downs, in which case the bank fails and there is contagion.

The previous example shows that a cascade can pick up if some of the banks have small initial distances to failure, which is equivalent to them having low contagion thresholds. In particular, inhomogeneous networks may have phase transitions when sufficiently many nodes have low contagion thresholds, see Amini and Minca (2016). A cascade as defined above is may pick up in particular if the exposures aggregate several sources (loans, derivatives). More importantly, thresholds for contagion decrease with the number of failures in the system is a very powerful source of indirect contagion on top of the direct cascade.

Final set of failures. It is easy to see that the cascade is monotonic, i.e. D k-1 (ξ) ⊆ D k (ξ). Moreover, if the size of the network is n, the cascade finishes in at most n-1 rounds. The final set of failures is given by

D(ξ) := D n-1 (ξ).
The final set of failures in absence of intervention is D(0) and we clearly have for all ξ ≥ 0, D(ξ) ⊆ D(0).

If a bank i belongs to the final set of failures, i.e. i ∈ D(ξ), we identify the following losses:

(i) Loss absorbed by shareholders : c(i) + ξ(i);

(ii) Loss absorbed by counterparties: j∈D(ξ) c e(j, i).

Since the loss is absorbed by the capital cushion after infusions, it is understood that it includes the government cost.

Definition 3. We define the loss in the system

L(ξ) := i∈D(ξ) c(i) + i∈D(ξ) ξ(i) + i∈D(ξ) j∈D(ξ) c e(j, i).
(5)

It is reasonable to assume that the government recapitalizes only banks that have not failed after the initial shock, i.e., ξ(i) = 0 for all i ∈ D 0 (ξ). In the next section we will see that if the government has complete information on balance sheets, then their optimization program will yield that ξ(i) = 0, for all i ∈ D(ξ). It is important to note that the loss we expressed above includes any loss that is absorbed by the government cushion of capital injected in the banks.

In the sequel, we refer to time 0 the time after the fundamental failures, and we consider that the controller knows the set of fundamental failures at time 0.

We will analyze two specifications for the equity infusion problem. In the complete information case the controller minimizes the loss in the system, when the network structure is know (this is a deterministic optimization). In the partial information case, the controller minimizes the expected loss, when the network structure is only partially observed (this is a stochastic control problem). The expected value in the latter case is over the linkages in the network, revealed over time.

Optimal intervention with complete network information

We consider a deterministic and static setting for the equity infusion problem in which the complete information of the interbank structure is available to the government at time 0. In this case, the cascade (under any equity infusion) can be seen as instantaneous and the idea is to transform the optimization over the equity infusions into an optimization over sets of banks that are insured against contagion by equity infusions. The government has the following optimization problem.

Problem 1 (Optimal equity infusion). We define the problem of optimal equity infusion with maximum budget

M Minimize ξ L(ξ) s.t. n i=1 ξ(i) ≤ M. (6)
The controller will seek a set of banks that maximize stability in the network, in the sense that insuring these banks removes most causal chains of failures. Figure 1 illustrates the idea. On the left, a set of fundamental failures leads by causal failure chains to a final set of failures. On the right, some banks are "insured" and the final set of failures is smaller. Not only the "insured" banks are removed from the final set of failures, but also some indirectly saved banks, that would have failed due to causal chains. The "insured" banks act as buffers and cut the causal failure chains that pass through them.

The equity infusion problem may have multiple solutions. We make the following assumption.

Assumption 2. If there are multiple solutions to the above problem, the government prefers the solution(s) with minimal total equity infusion.

The rationale of this assumption is apparent in the following example.

Example 2. We assume a causal chain of failures: the initial failure of 0 leads to the failure of 1 which leads to the failure of 2. The solution of minimal cost that ensures the survival of both 1 and 2 is to make an equity infusion in 1 equal to the exposure of 1 to 0. This infusion will automatically save 2. Any solution that would make higher equity infusions would achieve the same gain, namely the capital of banks 1 and 2. This gain is the maximum that can be achieved in this network. This example demonstrates why beyond a certain point, equity infusions may not be efficient. All banks survive here following the intervention on a smaller subset of banks. We conclude that even under infinite budget, it is in general not optimal to make equity infusions in all banks.

A more subtle point is that it may also be optimal to let a bank fail, even if there is infinite budget. The idea is that it may be better to let a bank fail (and have the loss bounded to the capital of this bank), than save the bank and absorb (with taxpayer money) the exposures of this bank to the failed banks.

Example 3. Assume that bank 0 is the initial failure, with c(0) = 3. We let c(1) = 3 the capital of bank 1 and e(1, 0) = 5 the exposure of bank 1 to the failed bank. Further down the chain, bank 2 has a capital c(2) = 3 and e(2, 1) = 2, the exposure of bank 2 to bank 1. In absence of intervention, the failure of 0 leads to the failure of 1, while bank 2 survives. From (5), the total loss in the system is c(0) + c(1) + e(2, 1) = 8, i.e, the capital of the failed banks plus the exposure of the surviving bank to the failed banks. To save bank 1, the government needs to inject sufficient funds so that it survives the write-down of e(1, 0). If needs thus to inject (e(1, 0) -c(1)) + = 2. The loss in the system is now c(0) + e(1, 0) = 8, i.e, the capital of the failed bank plus the exposure of surviving banks to the failed banks. The loss is the same as in the case without intervention, but at a cost for the government. Because we give preference to the minimal equity infusion, the optimal solution is to let 1 fail and 2 absorb the write-down.

If there are multiple solutions of minimal equity infusion, we may add criteria to distinguish between the solutions. Such criteria may include in particular the quality and riskiness of the external assets. Preference towards saving banks with less risky assets can reduce moral hazard. However, we expect multiple solutions only in presence of rather unnatural symmetries in the network, for example in presence of banks with an indistinguishable path of exposures to the initial set of failures. As we will see, in the partial information setting with linkages revealed over time the problem will have a unique solution because infusions are made sequentially.

We now show how to choose the set of minimal cost that reduces contagion loss by the most. We start by the following lemma, which states that either a node is left to fail, in which case no equity is injected in it, or, if a node is saved, then the equity infusion the minimal amount needed such that any node is above the failure barrier f -1 .

Lemma 1. Suppose that ξ is a solution to Problem 1. Then the following properties hold (i) If node i does not fail during the cascade, i.e., i ∈ D( ξ) c , we have

ξ(i) =   j∈D( ξ) e(i, j) -c(i) + f -1 s(i), |D( ξ)|   + . ( 7
) (ii) If bank i fails under infusion ξ, i.e., i ∈ D( ξ), then ξ(i) = 0.
It is is immediate to check the proof, by considering the basic tradeoff in the loss function in (5): higher equity infusion ξ may decrease the set of failures D( ξ), but increases the exposure of the government. Therefore, for fixed D( ξ), a bank i ∈ D( ξ) c receives the minimum infusion that guarantees that it does not fail, i.e. it "insures" it. If a bank i ∈ D( ξ) c fails under infusion ξ, then ξ(i) = 0 (otherwise ξ would not be an optimum: by setting ξ(i) = 0, the exposure of the government to i's failure can be decreased to zero, while D( ξ) would be unchanged.)

We now further characterize those infusions ξ (not necessarily solutions of Problem 1) which satisfy conditions (i) and (ii) of Lemma 1. Let V ⊆ N and consider the following algorithm, which gives the minimal infusions that insures the set V when only nodes in V may receive infusions.

Algorithm 1 (Insurance of a set of banks). (i) Let D V the final set of failures, as in Definition 2, when all banks in V receive infinite equity infusions, and all other banks do not receive any equity infusions;

(ii) Let now ξ V (i) := j∈D V e(i, j) -c(i) + f -1 s(i), D V + .
In step one of the algorithm we compute the failure set when banks in V receive infinite equity infusions. The causal chains of failure are modified, since insured nodes act as stabilizers, see Figure 1. The fictitious infinite equity infusions serve only to determine the modified final set of failures D V after we remove the causal chains of failures going through insured banks. The actual amount of equity infusions needed to insure V is of course not infinite. This amount is computed in step two of the algorithm, such that the capital of insured banks survives the exposures to the modified final set of failures.

We will thus use the failure set D V to compute the actual equity infusions in V. The critical observation is that D V is equal to D(ξ V ), i.e., the cascade with infinite equity infusions in V is the same as the cascade with equity infusions ξ V . We also have that ξ V is the minimal infusion that insures the set V when only nodes in V receive infusions.

We now can recast the optimal equity infusion problem as a combinatorial optimization problem.

Proposition 1. Problem 1 can be stated as the following combinatorial optimization problem, over the set V ⊆ N \ D 0 of banks to receive equity infusions:

Minimize V i∈D(ξ V ) c(i) + i∈D c (ξ V ) j∈D(ξ V ) e(i, j) subject to i∈V ξ V (i) ≤ M.
The proof of Proposition 1 is given in the appendix. Since the set of banks is finite, the combinatorial optimization problem has a solution. Finding the optimal solution requires however exploring all possible sets V that satisfy the budget constraint.

Figure 2 Concerning the uniqueness of the solution, we can construct an example where there are multiple solutions to the optimization problem. We expect that such examples feature symmetries in the network structure. In the next example, banks 1 and 2 have an indistinguishable path to the initial failure, node 0.

Example 4. Consider the network in Figure 2. Node 0 is the initial failure. It causes the failure of nodes 1 and 2, because each of these node's exposure to 0 is 1, equal to their capital. These two nodes, in turn, cause the failure of node 3. Finally, node 3 causes the failure of node 4. One can note there are two solutions with minimal cost: one can inject 1 in node 1 and save all nodes except for 2, or symmetrically one can inject 1 in node 2 and save all nodes except for 1. The cost in both case is equal to 1. According to the criteria we considered so far, nodes 1 and 2 are exchangeable from the point of view of the controller. In practice, this poses a fairness problem and additional criteria need to be added. For example, the government can have a preference on the type of assets of the banks. In the case of multiple solutions, the government could inject equity in banks with the preferred type of assets. Additional criteria on the quality and riskiness of the assets of banks that have access to equity infusions will also mitigate the moral hazard problem associated with equity infusions.

Full information on the network structure allows the government to select the solution of minimal cost. Because the objective is to minimize losses, then the banks that receive equity infusions are those that would otherwise lead to the most failures. This in turn creates an obvious moral hazard problem. Banks would seek to position themselves high in the causal failure chains, by borrowing from several large counterparties, particularly those with small distances to failure, e.g., those who fund themselves through short term debt. This in turn creates fragile networks. We expect that the existence of multiple solutions to the equity infusion problem would actually lead to less moral hazard, since there could be ambiguity about the preferred solution.

Data collection on exposures has thus important tradeoffs. In time of distress, it allows the government to achieve the minimal loss possible given the network. However, because of the structure of the solution, data collection could turn out to be detrimental to financial stability, because banks may create fragile network structures. It is thus imperative that data collection and the availability of equity infusion programs is accompanied by capital requirements and charges that disincentivize banks from creating network structures with potentially large causal default chains. In the next section, we consider the intervention in presence of partial information. Partial information makes the equity infusions less predictable for the banks and thus mitigates moral hazard.

Optimal intervention with partial network information

In this section, we consider that the complete interbank network is unknown to the controller from the beginning, but it is revealed over time. At each time t, the controller can decide (subject to budget constraints) to inject equity in any bank so as to minimize the total expected loss in the system until the cascade ends.

Contagion begins with the set of fundamental failures D 0 , which are assumed to be recorded. Contrary to the full information case when all the write-downs are instantaneous, there is now a span between a bank's failure and the time when an exposed counterparty will record its write-down.

The government observes all failures and the recorded exposures to failed banks. The providers of short term debt learn the same information as the government, but with a delay that would allow intervention before a bank run. To motivate this assumption, consider that bank i is about to reach the illiquidity barrier f -1 = 1 after a write-down. If the market observed the write-down before the government, then the run ensues and the bank fails. It cannot be then saved by intervention, even if the government increases its capital to 2 (above the failure barrier). However, if the government observes the write-down before the market, then it can make the capital infusion and the bank run does not occur because the providers of short term debt integrate the information that the government already made equity infusions, and that the new capital is 2, which is above the failure barrier.

A random network model

We assume now a regular network, in which all nodes have the same number of linkages. Heterogeneity in degrees can be introduced and all theoretical results in this section would still hold under some mild conditions on the degrees. At the same time, heterogeneity in degrees would increase the dimension of the Markov processes. The problem would remain tractable for more realistic two-tiered network structures, such as core periphery-networks. We illustrate the theory on the regular case, and differ the discussion of these extensions to the end of Section 5. Thus we present the regular case from the outset. We will retain heterogeneity in the funding stability, and thus the model has the important feature that the failure barrier is uncertain: zero for banks that do not depend on short term funding and thus can only fail due to insolvency, and equal to one for banks that do depend on short term funding. As we will see, this heterogeneity will drive the results.

We endow each node with a number of λ incoming half-links and λ outgoing half-links. Each link represents one unit of exposure (in terms of the numéraire). The network results form the uniform matching of all incoming half links and all outgoing half-links. We allow for parallel links, with the meaning that the exposures between the same pair of nodes add up.

We further simplify the problem by setting the failure barrier f -1 constant and equal to 1 for those banks prone to bank runs. We let α the fraction of banks that are prone to bank runs. The other banks (representing a fraction 1 -α) have a failure barrier equal to 0. We thus have

f -1 =
1 with probability α 0 with probability 1 -α.

Maximum capital. From now on, we assume that the initial capital is constant across banks, c(i) = c for all i ∈ N , for c ≤ λ (the capital is smaller than the interbank assets). Throughout contagion, the remaining capital decreases, so c also represents the maximum remaining capital.

We consider that, after a recorded failure i, any node j exposed to i will record the write-down related to its exposure after a random time span, independent of everything else, and distributed as an exponential random variable with mean 1 (time unit) Exp(1).5 Contagion stops at a random time T , which is finite almost surely (a.s.). Indeed, there will be at most m (the total number of edges) recorded write-downs due to exposures to failed banks, and therefore T will be smaller than a sum of m i.i.d. exponentials Exp(1).

We denote by T k , for k ≤ m, the arrival times of the superposed recorded write-downs (we take by convention T 0 = 0). We denote (i k , j k ) the pair of banks whose exposure is recorded at time T k , with the usual direction that j k is exposed to i k .

Optimal intervention

Unlike in the complete information case where all intervention happened at once, here we assume that the cascading failures and the intervention occur over time.

We let ξ t (i) the cumulative equity infusion in bank i up to time t, with ξ T the cumulative equity infusion up to the end of the cascade. We let D(ξ) the final failure set under the equity infusion ξ t , t ≤ T . The optimal equity infusion problem 1 becomes now Problem 2 (Optimal equity infusion under partial information).

Minimize

ξ E i∈D(ξ) c(i) + i∈D(ξ) ξ T (i) + i∈D(ξ) c j∈D(ξ) e(i, j) , ( 8
) subject to n i=1 ξ T (i) ≤ M. (9)
Note that, contrary to the complete information setting, the second term is not necessarily zero, since it is possible that the government injects equity in a bank that afterwards could record additional write-downs and fail. In the numerical results, we consider the difference between the loss without intervention and the loss under the optimal intervention, which is our criterion for the assessment of the equity infusion program. The "wasted government money" term E i∈D(ξ) ξ T (i) is part of our criterion, allowing us to capture the tradeoff associated with intervention: potentially wasted money versus less capital depletion.

The solution to this problem can be given in terms of a Markov Decision Process for the embedded Markov chain, i.e., it is sufficient to determine the optimal intervention only at the times when the write-downs are recorded. The Markov Decision Process is based on partitioning the set of banks according their remaining capital.

The next proposition states that intervention only occurs at the random times T k when write-downs are recorded. A bank i may receives infusions only when it records an exposure to a failed bank and when the government decides to reinforce the capital of the exposed bank.

Proposition 2. The optimal solution to the Problem 2 is for all i ∈ N ,

ξt (i) = k, T k ≤t, i k =i u k ,
where u k ∈ {0, 1} represents the equity infusion at time T k in the exposed bank i k . We have the budget constraint k, T k ≤T u k ≤ M .

The proof of this proposition is given as part of the proof of a technical Lemma 2 in the Appendix.

We can describe contagion in our model using a Markov Decision Process. What determines whether a bank fails, is whether either its distance to the illiquidity barrier is zero (if the bank uses unstable sources of funding) or its distance to insolvency is zero (if the bank does not use unstable sources of funding).

Recall that contagion starts from fundamental failures and that the counterparties of failed nodes record their exposures after random exponential times. Thanks to the uniform matching, a recorded exposure belongs to a counterparty of a failed node with probability proportional to the number of unrecorded exposures of that counterparty. A node with an exposure to a recorded failure, will have its remaining capital decrease.

Finally, remark that, from point of view of the government, nodes that have the same connectivity and remaining capital represent the same type. Therefore, we only need to keep track of their number during the cascade, rather than their individual state, which is a significant reduction in the dimension of the Markov process.

We make now this intuition mathematically precise. At time t ≤ T , the state variables are • X t (θ), θ = 1, . . . , c: the number of banks with remaining capital equal to θ at time t,

• N t (θ), θ = 1, . . . , c: the number of interventions up to time t on banks with remaining capital θ (at the time of intervention).

Thanks to Proposition 2, the control variables are

u k := (u k (θ)),
giving the 0/1 infusion decision corresponding to intervention at k-th event (at time T k ) on banks with remaining capital θ.

We let X t := (X t (θ)) θ=1,...,c and N t := (N t (θ)) θ=1,...,c . By abuse of notation, we will use from now on the embedded controlled Markov chain (as a function not of time but of the recorded exposure)

X k := X T k , and

N k := N T k .
The transition probabilities of this embedded Markov chain are given in Appendix A.2.2. Note that by Proposition 2, the optimal strategy consists in injecting liquidity at the random times T k , i.e., as soon as exposures are recorded, and, moreover, the amount of these interventions are either 0 or 1.

By virtue of the theorem 1 below, the optimal intervention problem in continuous time (Problem 2) reduces to the following optimization problem in discrete time 0, 1, . . . , m.

Problem 3 (Optimization program in discrete time).

V k (x, ) := min u k (θ)∈{0,1} L k (x, ) subject to c θ=1 N m (θ) ≤ M, with L k (x, ) := E c(n - c θ=1 X m (θ)) + c-1 θ=1 (c -θ)X m (θ) + c-1 θ=1 N m (θ) | X k = x, N k = .
The quantity L k (x, ) represents the expected loss at the end of the cascade, assuming that at step k there have been j interventions and the system is in state x, i.e., X k (θ) = x(θ), for all θ = 1, . . . , c. Just as in Equation ( 5) the loss consists of the capital of the failed banks c(n -c θ=1 X m (θ)), as well as the loss absorbed by surviving banks (including the loss absorbed by the new equity) c-1 θ=1 (c -θ)X m (θ) + c-1 θ=1 N m (θ). For example, each bank at distance c -1 at the end of the cascade absorbed one unit of loss from their own capital.

A solution exists for Problem 3, since the state space is discrete and finite, as well as the time horizon. Uniqueness follows due to the uniqueness of the solution to the associated dynamic programming equation, given in section A.2.4. Formally, we have: Proposition 3. There exists an unique solution to the stochastic control Problem 3, given by a Markovian optimal control ũ:

V k (x, ) := min u k (θ)∈{0,1} L k (x, ), = L (ũ) k (x, ).
We now state the main technical result of this section, which links the Markovian optimal control ũ and the equity infusion problem 1.

Theorem 1. The optimal solution to Problem 2 is given by V 0 (X 0 , 0) and the optimal strategy is determined by the Markovian optimal control (ũ) as

ξt (i) = k, T k ≤t, i k =i ũk (θ k (i)),
for i ∈ N , where θ k (i) is the remaining capital of node i at step k.

The proof is given in Appendix A.2.3. This result will allow us to study the optimal solution numerically, using dynamic programming.

The value of adapted intervention in the partial information setting

We end this section by a technical result, that allows to compute the optimal intervention in the case when the corresponding budget is used at time 0 to increase the capital of certain banks. We denote by V0 the value function when we restrict intervention to be made at time 0. As before, the objective is to minimize the expected loss during the cascade. The value of adapted intervention is defined as the difference V 0 (X 0 , 0) -V0 .

It is easy to see that the value V0 results as an optimization problem in dimension c, over the increases in the initial distances to insolvency, under budget constraints. Let us denote by ∆X the increase in the initial number of banks at different distances to insolvency. Remark that the risk bearing capacity of the system is given by the total capitalization of the financial system: c θ=1 X(θ)θ. The capital infusion will increase the risk bearing capacity of the system. After intervention, individual banks will have increased their capital, therefore the increase in the initial number of banks at different distances to insolvency verify k≥1 ∆X(k) = 0, since the number of fundamentally failed banks does not change. Moreover, banks can only increase their distances to failure after intervention: for all 2 ≤ θ ≤ c, k>θ ∆X(k) ≥ 0. Thus, we have the following technical result, which allows us to study numerically the value of adapted control.

Proposition 4. The solution of the optimization Problem 2 when we restrict intervention to be made at time 0, i.e, ξ T (i) = ξ 0 (i), for all i, is given by

V0 = min ∆X E(L | X 0 + ∆X) subject to: c θ=1 ∆X(θ) • d ≤ M, k≥1 ∆X(k) = 0, and k≥θ ∆X(k) ≥ 0 for all 2 ≤ θ ≤ c.

Numerical results

In this section we will compare the net gain from intervention in various settings, where the net gain is understood as the difference between loss without intervention and loss with intervention. The net gain from intervention will be expressed as a percentage of total value of the financial system, where we define the total value of the financial system as the sum over all banks of their capital, i.e., i∈N c(i). We are particularly interested in comparing the gain from intervention in the partial information and complete information case. The difference in the net gain is the value of information. A cautionary point is that this value of information does not integrate moral hazard, which we expect to be higher in the case of complete information. In the complete information case, we choose uniformly 2 banks as initial failures. We check robustness of the results by generating a regular network and an inhomogeneous network. By means of the configuration model, see e.g. [START_REF] Molloy | A critical point for random graphs with a given degree sequence[END_REF], we obtain sample networks in which the nodes have prescribed degrees. Nodes are assigned in-coming and out-going "half-linkages" and the sample graph results from a uniform matching model of the in-coming half linkages and out-going half linkage, as shown in Figure 3. The regular network is a network in which all nodes have the same degree λ = 12.

λ • • • 2 1 λ .. 2 1 λ • • • 2 1 λ ..
Likewise, an inhomogeneous sample network is obtained by the configuration model, but the degrees are not all equal to λ. They are instead chosen randomly, equal to λ min = 6 or λ max = 18 each with probability .5, such that the average degree remains λ = 12. In a regular network, each bank can be reached from other λ banks and can reach other λ banks. When λ is large by comparison the n, we can expect that the graph is strongly connected and that it contains cycles (with sufficiently high probability). The same holds in the case of the inhomogeneous graph when λ min is sufficiently large by comparison the n. The numerical results of this section depend on the strong connectivity property of the networks we consider.

In the partial information setting we do not need to choose the banks that fail initially, but only their number. We will consider the cases of 1 and 2 initial failures (out of 20 banks).

The partition of non-failed banks according to the remaining capital can be interpreted in the following way:

• θ = 3: Banks which are not prone to bank runs in case they record a write-down;

• θ = 2: Banks that recorded one write-down. Among these banks, those who depend on short term funding will face a bank run as soon as they record a new write-down;

• θ = 1: Banks that recorded two write-downs. They do not depend on short term debt (A non-failed bank that depends on short term debt cannot have remaining capital θ = 1, since it fails due to illiquidity as soon as its remaining capital reaches the failure barrier f -1 = 1).

Before contagion (after the initial shock), non-failed banks have remaining capital θ = 3. If there is additional depletion of capital beyond the initial failures, we will allow non-failed banks to start with θ = 2 in order to illustrate the effect of contagion.

Optimal intervention in the complete information setting

We generate several samples from our random network model with the parameters in Table 2. Figure 4 plots the net gain from intervention versus the total equity infusion. Each point represents one of the sets of "insured" banks. We plot the cost versus the net gain for all possible choices of insured sets of banks, for which the infusion is smaller than M .

More precisely, we are in the context of Proposition 1 and we plot for each set of "insured" banks

V ⊆ N \ D 0 with i∈V ξ V (i) ≤ M the cost i∈V ξ V (i) versus the net gain i∈D(ξ V ) c(i) + i∈D c (ξ V ) j∈D(ξ V ) e(i, j) - i∈D(0) c(i) + i∈D c (0) j∈D(0) e(i, j) ,
where D(0) represents the final set of failed banks under no intervention (0 equity infusions).

If the net gain from insuring a set of banks is positive, then it is efficient to intervene on that set. However, the government will chose to insure the set with the maximal net gain. If there are multiple optimal solutions, we choose the one of minimal cost.

We make three plots, for the same network, but for different α (the probability that a node depends on short term funding). For each of these plots, we note that the net gain is in general decreasing with the cost of insurance. To understand this unintuitive result, consider the example of a long chain of causal defaults: 1 leads to the default of 2, which leads to the default of 3, and so on, until the default of last bank 20. In absence of intervention all 20 banks default. However, the causal structure of defaults is particularly simple here, and its complete knowledge will let the controller identify that there is only one bank, 1, that has a critical position in the network. Saving this bank will have the smallest intervention cost, 1 and lead to the maximum net gain equal to the capital of 20 banks. When the cost to insure a set of banks is small, this means that most causal chains would be removed if only a few critical banks receive infusions.

The second observation from Figure 4 is that the optimal solution is not very sensitive to the fraction of banks prone to bank runs. Only when the fraction of such banks increases significantly, the cost of the optimal solution increases from 4 to 5. The net gain is the same. Clearly, because in the complete information the controller can identify the critical nodes in the network that need to be insured, then the default chains are cut "early" before an illiquidity crisis can unfold. Third, as expected, the general cost to insure sets of nodes increases with the fraction α of banks prone to bank runs. This is explained by the fact that there are less choices of insurable sets that can satisfy the budget constraint. However, because the optimal solution is interior and not very sensitive to the fraction α of banks prone to bank runs, then increasing the intervention budget will not lead to a better solution.

Further, we let α = 0.2 and plot the cases when there is a dependence of the illiquidity barrier and the number of defaults in the system. The first plot is the case when there is no dependence, the second one is when the illiquidity barrier increases by 1 with every 5 defaults in the system, and the last case when the illiquidity barrier increases by 1 with every 2 defaults in the system. The optimal solution has now a higher cost 6. As the indirect contagion channel becomes more powerful, much fewer sets are "insurable". The sensitivity is much larger to the indirect contagion channel than to the increase in the fraction α of banks prone to bank runs.

In all considered cases, beyond a certain value for the total capital infusion, it is not optimal for the government to inject more equity in the system. The budget constraint is not saturated in general. This suggests that injecting equity beyond a certain limit would, in effect, not serve to mitigate the contagious losses, but to transfer losses from the creditors and existing shareholders of failed banks to the taxpayers. We now check the robustness of these results with respect to the network structure. We have so far considered a regular network. We now consider intervention in an inhomogeneous network in Figure 6. The network is obtained by the configuration model, but the degrees are not all equal to λ. They are instead chosen randomly, equal to λ min = 6 or λ max = 18 each with probability .5, such that the average degree remains λ = 12.

The same results hold qualitatively, with two important distinctions. Unlike in homogenous networks, in heterogeneous networks there is no contagion in absence of the bank run component. The maximal gain that can be achieved is 0.4 (compared to 0.5) of the value of the financial system. This is because there is less contagion in the first place. The second distinction is that in heterogeneous networks there are more cases in which the net gain from intervention is negative. This is because in such networks, exposures are heterogeneous. Or, as seen in Example 3, in presence of large exposures the government will not save a bank and absorb a large exposure with taxpayer money, according to our optimization criterion.

Given that the networks we consider here have n = 20 nodes, it is reasonable to interpret these nodes as core banks. While the entire financial system is highly heterogeneous, the subset of core banks is more homogenous in term of connectivities. In the sequel, we consider the partial information setting, in which the network is homogenous and in fact regular.

Optimal intervention in the partial information setting

We compare in Figure 7 the net gain from intervention in the complete and partial information setting. Given complete information on the network, the loss mitigation will be more effective. Here we study numerically the value of information, defined the difference between the value function in the complete versus the incomplete information case. Policymakers would need to balance the value of information against the costs associated with the complete information case: the costs of data collection and the moral hazard costs.

The complete information case is shown as before, and the optimal solution is easy to identify on the plots as the maximum net gain. In the incomplete information case we plot the expected net gain as a function of α and the number of banks with remaining capital θ = 2. Because we consider that non-failed banks have either θ = 3 or θ = 2 remaining capital, it is understood that the larger the number of banks with remaining capital θ = 2, the smaller the initial capitalization of the non-failed banks.

We note that optimal intervention reduces significantly the magnitude of contagion, in both the complete and partial information settings whenever α is small and there are few banks with remaining capital θ = 2. The resulting net gain in the partial information setting compares well to the case when the government observes the whole network. In both the complete information and the partial information the gain is close to .5 of the value of the system. Importantly however, for the partial information case, this large gain holds only for small values of α, whereas in the previous section the dependence on α of the optimal solution was not as significant.

This points to the fact that an optimal intervention of a government "one step ahead" of the market yields good results in terms of mitigating contagion when the fraction of banks prone to bank runs is small and most non-failed banks are well capitalized initially. The fact that the value of information is small is particularly important from the perspective that the government needs to put into balance the value of information with the increase in moral hazard when the network structure is known (full information on who would receive infusions). Moreover, data collection is costly, see e.g. [START_REF] Abad | Shedding light on dark markets: First insights from the new eu-wide otc derivatives dataset[END_REF] for details on the amount of data availability and the costs this data collection entails.

We further compare the optimal solution under partial information with the solution when we constrain equity infusions to take place only once. The difference is the value of an adaptive strategy. Figure 8 shows that the adapted intervention strategy performs significantly better than an infusion constrained to take place at time 0.

Short term debt and interbank contagion

In this section we assess the intervention policy in presence of banks which depend on unstable sources of funding. We vary the proportion α of banks that fund themselves via short term debt. In figure 9 we plot the net gain from intervention as a function of the number of banks at remaining capital θ = 2 and as a function of α. The more banks at remaining capital 2 (as opposed to 3) the less capital of non-failed banks. We consider two cases, with one initial failure and with two initial failures. For each of these cases, we compare the net gain under two intervention budgets, M = 10 and M = 4.

Consider the case of one initial default and M = 4. For low α, the net gain increases with the number of banks at remaining capital θ = 2; this is because contagion can be For each plot, we consider the intervention budget M = 10 (surface above) vs. M = 4 (surface below).

contained with the allocated budget. When α is large, the net gain quickly decreases with the number of banks at remaining capital θ = 2; when there is a large number of such banks, the net gain is close to zero; this means that contagion under intervention is almost the same as without intervention.

For M = 10, contagion can be better contained, so the expected net gain remains large even for a large α and a large number of banks with remaining capital θ = 2. This is no longer true in the case of two initial defaults. Then the expected net gain is sharply decreasing with α and the number of banks at remaining capital θ = 2 even under the larger budget M = 10.

In Figure 10 we plot the difference between the expected number of interventions on banks with remaining capital θ = 2 and interventions on banks with remaining capital θ = 1, as a function of α and time. More interventions on banks with remaining capital θ = 2 means that the focus is on avoiding runs. More interventions on banks with remaining capital θ = 1 means that the focus is on avoiding insolvencies. Whenever banks are not prone to illiquidity (α = 0) the government has no incentive to inject equity before the bank is in actual danger of insolvency.

All plots in Figure 10 have a jump at α = 0. This means that as soon as there is even a small fraction of banks that depend on short term funding, there is a threat that short term creditors can withdraw funding and the banks could fail due to illiquidity. In this case the government cannot wait for the banks to reach θ = 1 to make equity infusions, because it fears failures due to bank runs on banks that are still solvent. The government chooses instead to make equity infusions in banks that have θ = 2. These are banks that are adequately capitalized but which can fail due to runs, and not insolvency.

When there is one initial default, the strategies are indistinguishable for M = 10 and M = 6. When there are two initial defaults, the switch (the aforementioned jump at α = 0) towards interventions to prevent bank runs are much swifter when the intervention budget is larger. We conclude that under partial information, and in contrast with the complete information case, a larger intervention budget allows the government to take better decisions and avoid illiquidity crises. Whenever there are banks which depend on short term funding, the primary reason for equity infusions is to eliminate the frictions associated to inefficient bank runs, and not to prevent insolvency. An important observation is that it suffices to have an arbitrarily small α to observe this sharp jump in the rationale of the intervention policy. With one initial default (left), the strategies are indistinguishable for M = 10 and M = 6. The negative region of each surface represents the case when the controller's focus is on preventing insolvencies, and the positive region of each surface represents the case when the controller's focus is on preventing runs. All results of this section have been given in the regular network case, in which all banks have the same connectivity. The regular network is to be thought of as a network of core banks, which have access to repo funding and are prone to bank runs. We expect that our results would go through qualitatively if we considered a tiered system, the core and the periphery, as long as the core is strongly connected with sufficiently high probability. In such an extended model, the peripheral banks may have a smaller connectivity than the core banks and only core-peripheral directed paths.

The dimension of the problem would double, because the value function in 3 would depend, in addition to the state of the core banks and the number of interventions on the core banks, on the state of the peripheral banks and the number of interventions on the peripheral banks. Let us compute the size of the state space in the homogenous and tiered case, for the working example in 2. Consider the homogenous case. There are n = 20 banks, and the solvent banks have remaining capital θ = 1, . . . , c (c = 3), in total n+c c=1771 . There are M +2 2=28 possible ways to intervene on core banks at levels 1 and 2, for M = 6. For our example, the size of the state space is 1771 × 28. Suppose now that we introduce a periphery of n = 20 peripheral banks, and suppose that the interventions budget is M = 12. Then there are M +3 3=455 possible ways to intervene on core banks at levels 1 and 2 and on peripheral banks at level 1 (assuming that peripheral banks are not prone to repo runs). The size of the state space becomes the 1771 × 1771 × 455 ∼ 10 9 . Computing the optimal solution for a two tiered system under partial information remains tractable (and also for some three-tiered system, using today's computational power). By comparison, note that keeping tract of the state of each bank, would yield in the case n = 40 a state space of size 3 4 0. It is thus remarkable that the solution for systems with dozens of banks can become tractable and yield insights on the role of solvency vs. runs. It is clear that such tractability comes at the expense of imposing a tiered structures with a small number of levels, within each level banks having the same connectivity.

The dependence of the government strategy on funding capacity has implications on data collection. From data, one must estimate the probability of bank runs. A large fraction of the short term lending is done through repo markets. However, because of a lack of data on bilateral repos in the United States, "the full picture on repo is yet to be assembled" [START_REF] Gorton | Who ran on repo? Technical report[END_REF], [START_REF] Krishnamurthy | Sizing up repo[END_REF]. This is in contrast to European markets, where repo lending is much more transparent as it goes through a CCP (Eurex) [START_REF] Mancini | The euro interbank repo market[END_REF]. Currently, for US markets only data on money market funds lending is available see e.g. [START_REF] Gorton | Who ran on repo? Technical report[END_REF], [START_REF] Krishnamurthy | Sizing up repo[END_REF]. It is critical to estimate the cost of funding across a variety of types of repo lenders, e.g., money market funds, securities lender, insurance companies. This would lead to better estimation of bank run probabilities, which we have shown are central in intervention programs.

Conclusions

We analyzed the optimal equity infusions of a government with constrained budget, in two different information settings. The optimal strategy depends on the government's information and is highly sensitive to the presence of banks that are susceptible to bank runs. From this perspective, to minimize loss it is critical to estimate the banks' funding capacity and to acknowledge the role of indirect contagion from capital loss to funding withdrawal across the system. Collecting data that would allow to estimate funding capacity is equally (if not more important) than collecting data on exposures.

In presence of banks that are susceptible to bank runs, the intervention must be swifter and in banks that are otherwise not close to insolvency. The threshold to contagion is smaller when banks are prone to illiquidity. Under incomplete information, the government does not know the threshold to contagion. Even for a small fraction of banks that depend on unstable short term funding, there is discontinuity in the optimal strategy from "patient" intervention only on banks with low capital to "immediate" reinforcing of banks with medium capital (that could be in danger of illiquidity).

We have further compared the reduction in the magnitude of contagion in the partial and complete information settings. We found that even in the case of partial information, contagion is significantly mitigated by intervention, provided the government uses an adapted strategy. The mitigating effect of intervention is in this case comparable to the case when government has complete information. This has significant implications for moral hazard. Under complete information, the government will inject in banks that are higher in the causal chain of failures. This in turn creates incentives for banks to have many creditors, and can potentially turn them into "super"-spreaders of contagion or "toointerconnected to fail". In the incomplete information case, the creditors of the initially failed banks will receive infusions more equitably since there is no information as to which of them is higher in the causal chain of failure. Less information may decrease moral hazard

Step 1: An algorithm for sequential construction of the failure cluster. We describe the construction of the failure cluster in the random financial network, as introduced in Section 4.1, in the form of the following algorithm.

Algorithm 2. (i) Choose randomly a network from the Configuration Model.

(ii) Let Q the set of unrecorded exposures to failed banks. The set Q initially contains exposures to nodes in D 0 . All exposures in Q are assigned a clock which rings after a random time with law Exp(1), independent of everything else.

(iii) While the queue Q is non-empty, let (i k , j k ) the exposure whose clock rings first.

Remove k from Q: Q ← Q \ {k} and record the exposure. The government may intervene by injecting equity in the node i k (according to their optimization program under partial information). We denote by u 1 k the optimal decision. If i k is left to fail, the exposures of other nodes to i k are added to the queue Q and assigned a clock of law Exp(1), independent of everything else.

(iv) Repeat until Q = ∅. We denote by C 1 = (D 1 , E 1 ) the failure cluster observed by the government at the end of the contagion process, with D 1 the set of failures, and E 1 the set of recorded exposures.

We now introduce a second algorithm, which has the advantage of being sequential, and which will construct a failure cluster with the same conditional law as Algorithm 2.

Algorithm 3. Let Q the queue of unexplored in-coming half edges belonging to failed banks.

(i) Assign to each node i ∈ N , λ out-coming half edges and λ in-coming half edges.

(ii) Add the set of in-coming half edges of fundamentally failed banks to the queue Q and assign them a clock of law Exp(1), independent of everything else.

(iii) While Q = ∅, let k be the half edge whose clock rings first. Remove k from its queue: Q ← Q \ {k}. Choose uniformly a matching out-going half edge among all unmatched out-going half edges and form an edge. Let i k be the node to which the chosen out-going half-edge belongs and record the exposure.

The government may intervene by injecting equity in node i k (according to their optimization program under partial information). We denote by u 2 k the optimal decision. If i k is left to fail, then the λ in-coming half edges of i k are added to the queue Q and assigned a clock of law Exp(1), independent of everything else.

(iv) Repeat until Q = ∅. We denote by C 2 = (D 2 , E 2 ) the failure cluster observed by the government at the end of the contagion process.

Note that the difference between Algorithms 2 and 3 is that, in the first case, the network is drawn from the configuration model in the first step of the algorithm and then the failure cluster is generated using a supplementary queue which is unobserved by the government, whereas, in the second case, the network is generated at the same time as the failure cluster.

Step 2. We now need to show that, at any time t, the law of the failure cluster is the same for the two algorithms, conditional on observing at time t the same partial failure cluster and number of interventions.

We let the failure cluster observed at time t, C 1 t := (D Proof. We prove this claim by backward induction on the number of links in the observed failure cluster. Let t such that |E 1 t | = m, i.e., we have recorded m write-downs. Thus, we must be after the end of the cascade. So C 1 = C 1 t , and therefore

E(F (C 1 )|H 1 t ) = F (C 1 t , N 1 t ).
Likewise, for t such that |E 2 t | = m, E(F (C 1 )|H 2 t ) = F (C 2 t , N 2 t ).

Suppose now that the two claims hold for observed failure clusters with a number of links greater than k. We now show that the two claims hold when the observed failure clusters have k links. Let us consider first the case when a clock rings precisely at time t. In this case, the history H 1 t+ is strictly larger than H 1 t , since it contains the information about the newly recorded exposure and the controller's decision. More importantly, because at time t+ there is an additional exposure added to the observed cluster, we are under the induction hypothesis. Using iterated conditioning, we have

E(F (C 1 )|H 1 t ) = E(E(F (C 1 )|H 1 t+ )|H 1 t ) = E(G 1 t+ (C 1 t+ , N 1 t+ ))|H 1 t ) =: G 1 t (C 1 t , N 1 t ),
where in the second equality, we have used the induction step. The last equality (and implicit definition) holds because, conditional on a clock ringing, C 1 t+ results from C 1 t in two steps: (i) First, the newly recorded exposure must have been formed at Step (i) of Algorithm 2 by matching an in-coming half-edge belonging to a recorded failure with an out-going half edge. Due to the independence of the clock on everything else and the memoryless property of exponential distribution, this matching is conditionally uniform over all such matchings of unexplored half-edges entering the failure cluster C 1 t .

(ii) The induction step can be applied for the total loss L. There exists a function G L t+ such that the optimization in (iii) of Algorithm 2

min u E(G L t+ (C 1 t+ , N 1 t+ )|H t ),
with the understanding that C 1 t+ and N 1 t+ depend on the decision u 1 t . Since u 1 t is decided after the exposure is recorded, and since nodes of same remaining capital θ are indistinguishable, we have that u 1 t depends on the new information (the new exposure) only through the exposed node's remaining capital θ. Moreover, because the loss criterion depends on the history of the default cluster only through the current state C 1 t and N 1 t It follows that u 1 t = u 1 t (d, C 1 t , N 1 t ).

Take now a time t when no clock rings, and let T 1 the next time a clock rings. In this case

E(F (C 1 )|H 1 t ) = E(E(F (C 1 )|H 1 T 1 )|H 1 t ) = E(G 1 T 1 (C 1 T 1 , N 1 T 1 )|H 1 t ) = G 1 t (C 1 t , N 1 t ),
where the second equality holds since there is a jump at time T 1 . We have that C 1 T 1 = C 1 t , the failure cluster does not change between t and T 1 . Moreover, because the loss criterion depends only on the failure cluster and is time independent, it also holds that there are no interventions between t and T 1 , so N 1 T 1 = N 1 t and we obtain the last equality with G 1 t = G 1 T 1 . Note that this point concludes the proof of the statement of Proposition 2, that interventions only occur when a clock rings.

For the second algorithm, we consider a time t when a clock rings (The case when no clock rings is treated similarly as in the first algorithm).

E(F (C 2 )|H 2 t ) = E(E(F (C 2 )|H 2 t+ )|H 2 t ) = E(G 2 t+ (C 2 t+ , N 2 t+ ))|H 2 t ) =: G 2 t (C 2 t , N 2 t ),
where C 2 t+ denotes the failure cluster resulting from C 2 t using the procedure at Step (iii) of Algorithm 3. We obtain that the control used by the government at this point is Markovian and depends on the new information only through the remaining capital of the exposed node u 2 t = u 2 θ (C 2 t , N 2 t ) ∈ {0, 1}. We are only left to show that, G 1 t = G 2 t , for which it is enough to show that the conditional laws of C 2 t+ are the same as the conditional laws of C 2 t+ , for any control choice u ∈ {0, 1}. For this, remark that in Algorithm 3, the out-going half edge is chosen uniformly among all unmatched half edges and the in-coming half-edge belongs to a recorded failure.

Figure 1 :

 1 Figure 1: Left: Causal structure of failures without intervention (the arrow represents the sense of causality). Right: Structure of failures after "insuring" a set of nodes. Chains of causal failures that pass through insured nodes are removed, and banks are indirectly saved.

2 1 Figure 3 :

 13 Figure 3: Configuration model: Links of are formed by uniformly matching half edges.

Figure 4 :

 4 Figure4: Net gain from intervention vs. total equity infusion, α = 0, 0.2, 0.4 and no indirect contagion. Each point represents a set V that are insured. The net gain is represented as a percentage of total value of the financial system.

Figure 5 :Figure 6 :

 56 Figure5: Net gain from intervention vs. total equity infusion; α = 0.2: In the first plot there is no indirect contagion, in the second and third plot there is indirect contagion: the barrier increases by 1 every 5 and respectively 2 defaults. Each point represents a set V that are insured. The net gain is represented as a percentage of total value of the financial system.

  Net gain from intervention vs. total equity infusion. Each point represents a set of banks that receive equity infusions. The total equity infusion is represented as a multiple of M , and the net gain as a percentage of total value of the financial system. Expected net gain from intervention as percentage of the total capitalization in the system.

Figure 7 :

 7 Figure 7: Net gain from intervention: complete vs. partial information.

Figure 8 :Figure 9 :

 89 Figure 8: Difference between value functions in the case with all equity infusions at time 0 and the case with adaptive intervention. M = 10 and there is one initial failure.

Figure 10 :

 10 Figure10: Difference between the expected number of interventions on banks with remaining capital θ = 2 and θ = 1 for budget M = 10 (surface above), M = 6 (surface in the middle) and M = 4 (surface below). With one initial default (left), the strategies are indistinguishable for M = 10 and M = 6. The negative region of each surface represents the case when the controller's focus is on preventing insolvencies, and the positive region of each surface represents the case when the controller's focus is on preventing runs.

Table 1 :

 1 Stylized balance sheet of a bank. numerical results in Section 5 compare the different information settings and the respective net gains from intervention of a government. Section 6 concludes. The paper finishes with a technical appendix providing the list of notations and the proofs.

	The

  1 t , E 1 t ) in Algorithm 2 and respectively C 2 t := (D 2 t , E 2 t ) in Algorithm 3. We denote by N 1 t and N 2 t the respective number of interventions. The respective failure clusters C 1 t and C 2 t are observed, in case we have a clock ringing, before the exposure is recorded and the intervention decision is made. We denote by H 1 t and respectively H 2 t the history of the cluster observation in the two algorithms. Lemma 2. For any network function F , and time t there exists a deterministic function (depending on F ) G t such that:

	E(F (C 1 )|H 1 t ) = G t (C 1 t , N 1 t ),
	and
	E(F (C 2 )|H 2 t ) = G t (C 2 t , N 2 t ).

In the US, the intervention budget is imposed to the government by Congress vote, and therefore it is important to determine in a quantitative model whether this constraint is saturated.

During the 2008 crisis, amid the Capital Purchase Program, the US banks that received equity infusions did not have the option to refuse the government decision, see e.g.[START_REF] Landler | Drama behind a $250 billion banking deal[END_REF],[START_REF] Veronesi | Paulson's gift[END_REF]. The Capital Assistance Program (CAP) replaced the Capital Purchase Program in 2009, offering participating banks redemption options. CAP securities valuation is investigated in[START_REF] Glasserman | Valuing the treasury's capital assistance program[END_REF].

The Troubled Asset Relief Program, before becoming an equity infusion program, was set up as an asset purchase program to avoid fire-sales of illiquid assets.

In contrast to the complete information case, in the partial information setting of Section 4, ξ(i) will not represent an instantaneous investment, but the cumulative injection over an entire time horizon in which information is revealed.

The exponential distribution of the random time span is a tractability assumption.

anonymous referees for very helpful comments. Andreea Minca is partially funded under NSF grant CMMI 1638230. ments. Andreea Minca is partially funded under NSF grant CMMI 1638230.

and have comparable mitigation.

There exist, of course, other kinds of interventions for supporting liquidity which do not take the form of equity infusions, but that of loans or credit guarantees. These are important topics for future research. Equity infusions in 2008, on the other hand, constituted the largest ever U.S. government intervention in the financial sector, and our results are intended to be used as tools for the decision process in this type of interventions.

A Appendix

A.1 Preliminary list of notations

• n -the number of banks;

• N -the set of banks;

• D -generic set of failed banks;

• ξ(i) -arbitrary equity infusion;

• D(ξ) -the final set of defaults under equity infusion ξ • D V (i) -the final set of defaults when all banks in V receive infinite equity infusions, and all other banks do not receive any equity infusions;

• e(i, j) -the exposure matrix (bank i is exposed to bank j);

• c(i) -initial capital;

• c -initial capital, assumed constant across banks in the second part; it gives the maximum remaining capital throughout the contagion;

• s(i) -short term debt, net of liquid reserves;

• f (i) -the funding capacity; By abuse of notation, f denotes also the map that gives debt capacity as a function of capital and number of failed banks,

• f -1 (s(i), |D|) -the failure barrier for the capital (as a function of the net short term debt and number of failed banks), the inverse of the debt capacity function;

• θ(i, D) -reamaining capital (after recorded losses);

• θ k (i) -in the second part, remaining capital after there are k recorded losses in the system;

• α -fraction of banks depending on unstable short term debt;

• L -loss in the system, the optimization criterion;

• M -the intervention budget;

• ξ(i) -optimal equity infusion;

• ξ V -the minimal equity infusion that "insures" the set V;

• λ -the connectivity, assumed constant across banks in the second part; also the number of exposures;

. . , m -the recording of exposure k consists of a 4 -tuple: the time when this exposure is recorded T k , the pair of banks, with the convention that i k is exposed to j k .

• u k ∈ {0, 1} -decision to inject equity in the exposed bank at time T k ;

• u k (θ) ∈ {0, 1} -decision to inject equity in the exposed bank at time T k given that the bank with remaining capital θ;

• ũk (θ) -the optimal decision to inject equity in the exposed bank at time T k

• X k (θ) -state variables, the number of banks with remaining capital θ;

• N k (θ) -control variables, the number of interventions on banks at remaining capital θ;

• L k (x, ) -the expected loss, starting at step k from state x and a number of interventions ;

• V k (x, ) -the minimal expected loss; this is the value function in the dynamic programming equation;

• V 0 (X 0 , 0) -the optimal solution under partial information;

• V -the solution with partial information and one-time infusions;

A.2 Proofs

A.2.1 Proof of Proposition 1

The set of infusions ξ which satisfies conditions (i) and (ii) of Lemma 1 is equal to the set {ξ V | V ⊆ N }. The proof of the equality of the two sets is easy to check. Let ξ V defined as above for a set V. It is clear that V D(ξ V ) = ∅, so failed banks do not receive infusions. Therefore ξ V satisfies condition (ii) of Lemma 1. It satisfies condition (i) by construction. Conversely, for ξ which satisfies conditions (i) and (ii

Lemma (1) combined with the budget constraint states that solutions to Problem 1 are a subset of {ξ V | V ⊆ N , i ξ V (i) ≤ M }. Therefore, in Problem 1 it suffices to minimize loss over the restricted equity infusion set {ξ

We conclude that the optimal equity infusion problem can be recast as the combinatorial optimization problem in the statement of Proposition 1.

A.2.2 Transition probabilities of the controlled Markov chain (X, N )

We define the stopping time

with k ≤ m, representing the time the cascading failures stop, meaning that all exposures to defaulted banks (there are (n -c θ=1 X k (θ))λ such exposures) have been recorded (the number of recorded exposures is k). The transition probabilities of the Markov chain are as follows. For all θ ∈ [1, . . . , c], with probability

, the next state will be:

A.2.3 Proofs of Proposition 2 and Theorem 1

For the proofs of Proposition 2 and Theorem 1 we need the following steps:

(i) We introduce a sequential algorithm that generates a failure cluster with will be shown to have the same conditional law as the failure cluster in the random financial network.

(ii) We then show by a coupling argument the equivalence of the conditional laws of the failure clusters in the two algorithms.

In Amini et al. (2016) it has been shown that in the case without intervention, the cluster of failures on the random network at the end of the cascade process has the same law as a random graph constructed sequentially. The intuition is as follows. A random matching can be constructed sequentially: At any step, choose an in-coming half edge according to any rule based on the history of the matching, and then choose its pair uniformly among all unmatched out-going half edges.

We now show that this is also the case when the controller has partial information.

Since the past control (u s ) s<t is non-anticipative, the histrory H 2 t does not contain any information on the future matching, which has thus a conditionally uniform law as in the case of Algorithm 2. This completes the proof of the Lemma.

Thanks to Proposition 2, it is enough to study the solution in discrete time, with the time k given by the k-th time a clock rings. By Proposition 2, the transition probabilities of the auxiliary Markov chains follow directly from the law of the failure cluster resulting from C 2 t using the procedure at Step (iii) of Algorithm 3. One can immediately check that these transition probabilities are precisely those given in Section A.2.2. Therefore, the solution of the dynamic programming equations is the solution of the equity infusion problem, and this completes the proof of Theorem 1.

In the next subsection we give the dynamic programming equations verified by the value function.

A.2.4 The value function

We let

be the set of admissible values for the state variables. We define V k (X, ) the value function when, at time t ≥ 0, there have been made interventions (X, ) ∈ A.

We denote by X the next state, without intervention, when a half edge of a bank with remaining capital θ is chosen, and the bank depends on short term funding. When the bank does not depend on short term funding, the next state is denoted by X .

We have

m -k min{V k+1 (X, + e θ ), αV k+1 (X , )

+ (1 -α)V k+1 (X , )} with the following boundary conditions. For all (X, ) ∈ A, we have

• for all such that c θ=1 (θ) = M (the intervention budget is exhausted),

where p denotes the transition probabilities in Section A.2.2.