Andreea Minca

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

Optimal Control of Interbank Contagion Under Complete Information

Keywords: Systemic risk, Liquidity risk, Bank runs, Financial contagion, Financial Networks, Optimal Intervention, Bail-outs

We study a preferred equity infusion government program set to mitigate interbank contagion. Financial institutions are prone to insolvency risk channeled through the network of interbank debt and to the risk of bank runs. The government seeks to maximize, under budget constraints, the total net worth of the financial system or, equivalently, to minimize the dead-weight losses induced by bank runs. The government is assumed to have complete information on interbank debt. The problem of quantifying the optimal amount of infusions can be expressed as a convex combinatorial optimization problem, tractable when the set of banks eligible for intervention (core banks) is sufficiently, yet realistically, small. We find that no bank has an incentive to withdraw from the program, when the preferred dividend rate paid to the government is equal to the government's outside return on the intervention budget. On the other hand, it may be optimal for the government to make infusions in a strict subset of core banks.

Introduction

During the recent 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 building new analytical and computational tools for macro-prudential regulation. Most research in this area focuses on the important topic of systemic risk measurement and attribution. [START_REF] Giesecke | Systemic risk: What defaults are telling us[END_REF] propose such measures within the framework of reduced form models (in reduced form models, the ensemble of firms in the economy is represented as a portfolio in which failures arrive according to some exogenous process). Some works propose systemic risk measures within the framework of network models for insolvency risk in banking systems, see e.g. [START_REF] Lehar | Measuring systemic risk: A risk management approach[END_REF], Amini et al. (2013a), [START_REF] Cont | Fear of fire sales, illiquidity seeking, and credit freezes[END_REF]. [START_REF] Blanchet | Stochastic Risk Networks: Modeling, Analysis and Efficient Monte Carlo[END_REF] extend the application field of the network framework to insurance-reinsurance markets. [START_REF] Chen | An axiomatic approach to systemic risk[END_REF] propose an axiomatic approach to systemic risk measures.

Network models for systemic risk have the advantage of being both structural (they integrate explicitly the details of banks balance sheets and the interbank debt) and tractable.

Such features are required for quantifying best regulatory responses to systemic crisis. A recent 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 preferred equity infusions, i.e, the government earns a preferred fixed dividend on its share of the banks' capital. 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 gain from these equity infusion programs is an important topic of notable research in the finance literature, both empirical and theoretical, see [START_REF] Philippon | Optimal interventions in markets with adverse selection[END_REF], [START_REF] Veronesi | Paulson's gift[END_REF], [START_REF] Bayazitova | Assessing TARP[END_REF], [START_REF] Philippon | Efficient recapitalization[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 the government recapitalized a banking sector that restricted lending because of debt overhang. The resulting optimization program is investigated in [START_REF] Philippon | Efficient recapitalization[END_REF]. The second possible reason is that government intervened in order to avoid 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 [START_REF] Gorton | Securitized banking and the run on repo[END_REF]. 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 when we take into account the runs of short term creditors? Would it be preferable for the government to invest directly in the economy than invest in the banks' equity? How to optimally inject equity in each bank? Is the intervention budget constraint saturated at the optimal solution?1

To answer these questions, we build a model in which banks use a combination of short term debt and interbank debt to invest in an illiquid asset and a risk-free asset ("cash").

The banks are exposed to two interdependent sources of risk. First, they are exposed to insolvency risk channeled through the network of interbank debt. Second, they are exposed to funding liquidity risk due to the possibility of runs by external short term creditors (e.g., money market funds). In case a bank suffers a short term creditor outflow, it is forced to prematurely liquidate part of the illiquid asset realizing a value below the fundamental value of this asset. This creates dead-weight losses in the system.

Insolvency risk and funding liquidity risk are interdependent. The underlying network of interbank debt transmits losses among financial institutions, which then see their capital depleted and consequently may face withdrawals in the funding provided to them by short term creditors. If the withdrawals are severe (bank run) then the dead-weight losses may be so large that the bank becomes insolvent. Insolvency entails complete liquidation and, due to the dead weight losses, prompts writedowns and capital depletion to the counterparties. This leads to large feedback effects. The feature that dead-weight losses may drive firms into insolvency which largely drives these feedback effects, is discussed in the economics literature in Diamond and Rajan (2011). This is a new feature that this model adds to quantitative network-based contagion literature.

We set up an optimal preferred equity infusion program by a government with constrained budget who aims at maximizing the total net worth of the financial system. The financial system we consider is comprised by the banks, their external debt holders and the government who is a preferred equity investor in the banks. The key ingredient is the fact that this total net worth accounts for dead-weight losses induced by bank runs. Equally important, the government values the illiquid asset at its fundamental value, thereby taking a long-term perspective on this asset.

We capture the government's tradeoff between investing in the banks equity and directly funding projects in the economy by introducing an outside return rate for the government's investment. This creates an opportunity cost present in the government's optimization criterion.

The government problem is set under full information, by which we mean that the controller (the government) observes the entire interbank debt network. The corresponding problem under partial information is treated in the companion paper [START_REF] Amini | Optimal equity infusions in financial networks[END_REF]. We also consider that only an exogenously chosen set of banks are eligible to receive government equity infusions. Indeed, the network of financial institutions contains banks, mutual funds, hedge funds, etc. and it is reasonable to assume that not all financial institutions are eligible for equity infusions. We will call the subset of institutions that are eligible to receive such equity infusions core banks. They can be specified using an exogenous rule, e.g., the top US banks in terms of assets.

Our analysis (Theorem 16) shows that under the considered optimization program, all banks achieve a higher capital with intervention than without intervention after the preferred dividend of the government is detached. This means that banks are better off by receiving the equity infusion and paying the dividend and no bank can gain by withdrawing from the program. This is consistent with our model setting in which the decision of the government cannot be refused by the banks2 .

The increase in the net worth of the financial system is due the mitigation of deadweight losses and to a pooling of losses that occurs into the system. The intuition behind the pooling of losses is as follows. The banks that are solvent, yet would have become illiquid absent the intervention, are forced to transfer funds to the government in the form of the preferred dividend. The bigger their holdings in illiquid asset funded by unstable short term debt, the bigger the equity infusion they receive and the larger the dividend.

These funds are used to absorb losses stemming from banks that become insolvent and thus mitigate the amount of losses that eventually reach the taxpayer.

We show that under the proposed optimization program, the government does not make equity infusions if the system is not prone to dead-weight losses induced by bank runs (Proposition 7). Our results offer a methodology to test the theory that the US equity infusion was set up to avoid bank runs. The fact that a government may find it optimal to make equity infusions to avoid banks runs does not necessarily create moral hazard and incentives for banks to expose themselves to bank runs. Indeed, if the dividend is sufficiently large, banks that are fundamentally solvent in absence of bank runs and that receive equity infusions to avoid bank runs are effectively forced to participate with the government in the pooling of losses. Since the equity infusion is larger when the bank has both a large amount of illiquid asset and a large fraction of unstable short term debt to total debt, it is in this case precisely that the bank will have to pay a larger dividend.

Our main result (Theorem 8) shows that the optimal equity infusion problem becomes a convex optimization problem with a combinatorial aspect. The combinatorial aspect of the optimization problem becomes relevant when the continuum of losses of the 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. [START_REF] Rogers | Failure and rescue in an interbank network[END_REF], Amini et al. (2013a). This aspect is highly relevant to systemic crisis which have an illiquidity component (such as the crisis of 2007 -2009).

Specifically, for each subset of core banks, we can compute the optimal solution when we restrict intervention to that specific set. We then optimize over all such possible subsets of core banks. The solution to this problem gives for each banks the optimal amount of equity infusions.

Several insights come from our results. First, it may be optimal to make non-trivial equity infusions when the system is prone to dead-weight losses induced by bank runs. Since the government's criterion accounts for its return on the direct investment into the economy, non-trivial infusions imply that it is preferable to increase the risk bearing capacity of the financial system by avoiding premature asset liquidations. Second, it may not be optimal to make equity infusions in all core banks. Third, there exists a maximum budget beyond which the marginal cost from intervention surpasses its marginal gain. As a consequence, beyond a certain point, the budget constraint will not be saturated. This result indicates that if the government would make equity infusions beyond a certain limit, it would, in effect, transfer the losses from the existing creditors and shareholders of failed banks to the taxpayer.

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 insolvency risk and to bank runs. In Section 2.3 we introduce the fixed point equation that determines the equilibrium asset-to-debt ratio for all banks and the equilibrium dead-weight losses. In Section 3 we show that the government optimization problem can be stated as a convex combinatorial optimization problem. In Section 3.3 we perform numerical experiments. The paper finishes with a technical appendix. that makes instantaneous equity infusions in the form of cash at time 0. At time 0, banks come with capital, they have debt to each other which matures at time 1 (long-term debt) and they have short-term debt to the continuum of outside creditors.

The debt to the outside creditors is of two types, stable, i.e., it is not withdrawn at time 0, or unstable, i.e., the outside creditors may decide to withdraw funding, depending on the state of the financial system and the financial health of the bank in question.

On the asset side, bank hold investments in cash and an illiquid asset. The illiquid asset matures at time 1 and has a fundamental price normalized at 1 at time 0. However, if the asset needs to be prematurely liquidated at time 0, it is then valued at a fire-sale price 0 < p ≤ 1. The price of the asset at time 1 is unknown at time 0 and market participants may have different beliefs about a fundamental shock that may change the fundamental value of the illiquid asset from time 0 to time 1. The government expects that the price of the illiquid asset will be 1 at time 1, i.e., the government does not expect a shock in the fundamental value of the illiquid asset between times 0 and 1. This can be interpreted as the government being an investor less jittery about the valuation of the illiquid asset than the short term creditors. We do not model directly the beliefs of the outside creditors, but we assume an exogenous short term creditor outflow schedule that incorporates these beliefs.

We are interested in the equilibrium reached at time 0.

Market participants and their interrelations

We now describe the financial system at time 0. Debt. For a bank i ∈ [n], i denotes the sum of its long term debt and stable short term debt and s i its unstable short term debt. A proportion π ij of the debt i is toward bank j, with j∈[n] π ij ≤ 1. The remaining fraction 1 -j∈[n] π ij of i gives the proportion of stable short term debt.

Assets. We let γ i and y i denote the holdings in cash and respectively the holdings in illiquid asset of bank i. One bank's interbank debt is another bank's interbank asset. The total value of the interbank assets of i is therefore given by j∈[n] j π ji .

The capital of a bank is given by the value of its assets minus the value of its debt. A bank is said to be solvent if the value of its assets is larger than the value of its debt, i.e., if its capital is positive. Alternatively, the solvency condition can be expressed in terms of the the asset-to-debt ratio which must be greater than one. The capital and asset-todebt ratio determined under the assumption that no debtor banks are insolvent are called fundamental capital and asset-to-debt ratio.

The fundamental capital of bank i at time 0 is given by

c i := y i + γ i + j∈[n] j π ji -i -s i .
The fundamental asset-to-debt ratio of bank i at time 0 is given by

r i := y i + γ i + j∈[n] j π ji i + s i (1) = 1 + c i i + s i .
The fundamental solvency condition for a bank i can be expressed in term of the fundamental asset-to-debt ratio as r i ≥ 1.

Clearly, if there exists a bank that is insolvent, then its creditors cannot account the full value of their interbank assets and their asset-to debt ratio is no longer determined as above. The equilibrium asset-to-debt ratios for all banks will be determined from a fixed point equation, as we show in the next section.

Financial contagion

If r i < 1 bank i is fundamentally insolvent and all holdings of the illiquid asset are sold at the fire-sale price p ≤ 1. The proceeds are distributed to creditors proportionally to the outstanding debt as in [START_REF] Eisenberg | Systemic Risk in Financial Systems[END_REF]. The creditors of an insolvent bank will suffer a loss and, in turn, may become insolvent themselves.

Importantly, even if a bank is fundamentally solvent, i.e. r i ≥ 1, it may be forced to liquidate some of its illiquid asset holdings due to the outflow of short term creditors. We model the short term creditor outflow schedule by an exogenous function g(

•) : [1, ∞) → [0, 1]
of the asset-to-debt ratio, on which we make the following assumption.

Assumption 1. The short term creditor outflow schedule g has the following properties:

(i) There exists r ≥ 1 such that g(x) = 0, for x ≥ r;

(ii) x -→ g(x) is non-increasing, twice differentiable and convex;

(iii) g ≥ -1.

The first condition ensures that for sufficiently large asset-to-debt ratios there are no short term creditor outflows. The second condition states that the creditor outflow is decreasing with the asset-to-debt ratio. This assumption is reasonable, since banks with higher asset-to-debt ratios have lower future insolvency risk. The convexity assumption can be interpreted as an increase in the outflow rate as we approach the insolvency level (asset-to-debt ratio equal to 1). The last assumption is a tractability assumption that puts a lower bound on the withdrawal rate.

Importantly, the short term creditor outflow schedule is assumed to incorporate all the beliefs of the short-term creditors about the fundamental value of the illiquid asset at its maturity date 1.3

As a consequence of the short-term creditors behavior, captured by the short term creditor outflow schedule, a bank whose asset-to-debt ratio falls below r may be forced to liquidate part of its illiquid asset holdings at the fire-sale price p.

Consider now a bank with asset-to-debt ratio x, total short-term debt s, cash holdings γ and illiquid asset holdings y. The short term creditors will claim back an amount sg(x)

of the short term debt. If the cash available to the bank cannot cover the amount sg(x),

then the bank will have to liquidate a quantity (γ-sg(x)) - p ∧ y of the illiquid asset. In doing so, the bank will effectively have a loss in its' asset value, since the liquidated value will achieve a price p ≤ 1 instead of its fundamental price 1. The total loss on the asset side in

this case is (γ-sg(x)) - p ∧ y i (1 -p).
In our model, an insolvent bank is completely liquidated and its entire illiquid asset holdings are valued at the fire-sale price p and not at the fundamental value 1. In this case there will be a loss on the asset side equal to y(1 -p).

The losses arising on the asset side as a result of liquidations are called dead-weight losses and are defined as follows.

Definition 1. We define the dead-weight loss of a bank with asset-to-debt ratio x, total short-term debt s, cash holdings γ and illiquid asset holdings y as follows

δ(x, s, γ, y) :=    (γ-sg(x)) - p ∧ y (1 -p) if x ≥ 1, y(1 -p) if x < 1.
(2)

If g ≡ 0, dead-weight losses occur only when firms become insolvent. This is like in [START_REF] Rogers | Failure and rescue in an interbank network[END_REF], where there are fixed liquidation costs when firms become insolvent.

If g > 0, dead-weight losses can occur due to withdrawal of short term creditors (part of the illiquid asset is de facto valued at the fire-sale price p). Unlike [START_REF] Rogers | Failure and rescue in an interbank network[END_REF], these dead-weight losses may occur even if all banks are solvent.

Note that the dead-weight losses will decrease the asset-to-debt ratio of the bank, which will entail a larger short-term creator outflow and consequently more liquidations. It is possible that the asset-to-debt ratio reaches 1 as a result of this process, at which point the bank is insolvent. If p < 1 then the dead-weight loss has a jump when the asset-to-debt ratio reaches 1, since all the illiquid asset is then sold.

A bank i with asset-to-debt ratio x i < 1, i.e. a bank that is insolvent, will generate a loss on the asset side of its creditors, irrespective how it has reached insolvency. The creditors will then receive a percentage x i < 1 of their debt, and thus contagion ensues.

Note in particular that for an insolvent bank, under the proportionality assumption, the asset-to-debt ratio represent the recovery rate of the creditors.

Equilibrium with government intervention

We consider now that there exists a government that makes instantaneous equity infusions in the form of cash at time 0. We assume that only a subset C ⊆ [n] are eligible for intervention. This set represents the set of core banks in the financial system and are specified by an exogenous rule.

The intervention budget of the government is M . The government injects preferred

equity ξ i ∈ [0, M ] in bank i ∈ [n], with ξ i = 0 for i ∈ [n] \ C. After the (instantaneous) intervention, a bank i ∈ [n] holds γ i + ξ i of cash
Φ(R(ξ), ξ) = R(ξ), of the non-linear map Φ on [0, ∞) n × [0, ∞) n Φ(x, ξ) i := y i -δ(x i , s i , γ i + ξ i , y i ) + γ i + ξ i + j∈[n] j π ji (x j ∧ 1) i + s i . ( 3
)
Remark 2. Note that the dead-weight loss ) n and i = 1, . . . , n, we have that

0 ≤ δ(•, •, •, y) ≤ y(1 -p). Consequently, for (x, ξ) ∈ [0, ∞) n × [0, ∞
0 ≤ py i + γ i + ξ i + j∈[n] j π ji i + s i ≤ Φ(x, ξ) i ≤ y i + γ i + ξ i + j∈[n] j π ji i + s i .
The difference between the above map and the baseline specification in [START_REF] Eisenberg | Systemic Risk in Financial Systems[END_REF] is that only a fraction of the illiquid asset is valued at its fundamental price.

The liquidated quantity is evaluated at the fire-sale price. This means that, in equilibrium, there is a dependence between the value of the assets and the value and the stability of the debt. This dependence is induced by the behavior of the short term creditors captured by the short term creditor outflow schedule g and the network of interbank debt. Of course, if p = 1, then the equilibrium dead-weight losses are equal to zero and the fixed point of the map Φ is the same as in [START_REF] Eisenberg | Systemic Risk in Financial Systems[END_REF]. In this case, the short term creditor behavior does not matter.

We have the following lemma.

Lemma 3. For each ξ ∈ [0, ∞) n , the function x → Φ(x, ξ) is monotone and bounded.

Moreover, there exists a largest fixed point for this function.

The following proof mimics that of [START_REF] Rogers | Failure and rescue in an interbank network[END_REF].

Proof. Fix ξ ≥ 0. Since the dead-weight loss x → δ is a non-increasing function of x, we immediately have from Eq. ( 3) that for all i = 1, . . . , n, x → Φ(x, ξ) i is a non-decreasing function of x. By Remark 2, the map Φ is bounded.

We now define recursively the following sequence, using the upper bound of the map Φ: For all i = 1, . . . , n, we let q 0 i :=

y i +γ i +ξ i + j∈[n] j π ji i +s i
. We let q n+1 := Φ(q n , ξ). By the monotonicity of the map x → Φ(x, ξ) i , we have q n+1 ≤ q n . Since q n are non-negative, there exists a monotone limit q * :=↓ lim n→∞ q n . Since x → Φ(x, ξ) is continuous from above, it follows that q * is a fixed point. Since any fixed point is bounded from above by

y i +γ i +ξ i + j∈[n] j π ji i +s i
it follows from the monotonicity of Φ that any fixed point of the map Φ is bounded from above by q * , i.e., q * is the largest fixed point. This concludes the proof.

Lemma 3 proves the existence of a largest equilibrium asset-to-debt ratio. In the sequel we consider the largest fixed point of the map Φ.

The equilibrium dead-weight losses of bank i are given by

∆ i (ξ) := δ(R i (ξ), s i , γ i + ξ i , y i ).
The equilibrium capital of bank i, including the government share, is (R i (ξ) -1)( i + s i ).

The face value of the government share is ξ i (1 + d). The government investment is in the form of preferred equity, i.e., it absorbs losses after the ordinary shareholders and before the outside debt holders.

It follows that the equilibrium value of the government investment in bank i is

(R i (ξ) -1) + ( i + s i ) ∧ ξ i (1 + d) = ξ i (1 + d) -(R i (ξ) -1) + ( i + s i ) -ξ i (1 + d) -. (4)
The equilibrium capital of bank i, net of the face value of the government share, is then given by

C i (ξ) := (R i (ξ) -1)( i + s i ) -ξ i (1 + d) = y i + γ i + j∈[n] j π ji (R j (ξ) ∧ 1) -∆ i (ξ) -(s i + i ) -ξ i d. (5)
The equilibrium capital in absence of government intervention is given by

C i (0) = y i P + γ i + j∈[n] j π ji (R j (0) ∧ 1) -∆ i (0) -(s i + i ). ( 6
)
We obtain thus the difference in the capital with and without intervention

C i (ξ) -C i (0) = ∆ i (0) -∆ i (ξ) + j∈[n] j π ji (R j (ξ) ∧ 1 -R j (0) ∧ 1) -ξ i d. (7)
The first two terms are positive.

We now compute the total value of the government investment. We assume that the part of the budget non invested in the banks bears a return rate to which we refer as outside return rate.

Remark 4. The outside return rate can be interpreted not as a risk free rate but as the return on investment that the government would have by directly funding projects in the economy.

Assumption 2. We assume that the outside return rate is equal to the dividend rate d paid by the banks.

Since the problem setup gives the banks no option to refuse the government equity infusion, if the outside return rate were smaller that d, then the government would have an incentive to invest in a healthy bank in order to earn the preferred dividend. Also if the outside return rate were larger than d, then the government would provide capital "too cheaply" for the banks.

Using Eq. ( 4) and by the outside return rate d, we obtain the total value of the government investment

M (1 + d) - i∈[n] (R i (ξ) -1) + (s i + i ) -ξ i (1 + d) -. (8)
The total value of the investment of the outside creditors is given by

i∈[n] (R i (ξ) ∧ 1) s i + i (1 - j∈[n] π ij ) . (9)
3 Government optimization problem

Problem statement

The government has a constrained budget M and its objective is to maximize the overall net worth of the financial system. Recall that the government assigns probability one to the illiquid asset having the same fundamental value 1 at time 1. The net worth of the financial system (to the government) is thus deterministic and defined as the total equilibrium capital of the banks given in Eq. ( 5), plus the total value of the government investment as given in Eq. ( 8), plus the value of the outside creditors's investment given in Eq. ( 9).

The total net worth of the financial system is given by

V (ξ) := i∈[n] y i + γ i + j∈[n] j π ji (R j (ξ) ∧ 1) -∆ i (ξ) -( i + s i ) -ξ i d + i∈[n] (R i (ξ) ∧ 1) s i + i (1 - j∈[n] π ij ) + M (1 + d) - i∈[n] (R i (ξ) -1) + ( i + s i ) + ξ i (1 + d) - = i∈[n] (y i + γ i ) + M (1 + d) - i∈[n] ∆ i (ξ) - i∈[n] (R i (ξ) -1) -(s i + i ) - i∈[n] ξ i d + (R i (ξ) -1) + ( i + s i ) -ξ i (1 + d) -. (10)
Note that i∈[n] (y i +γ i )+M (1+d) represents the fundamental net worth of the financial system (including the government intervention funds valued at the outside return rate). We can further write the total ex-post value in the system

V (ξ) = i∈[n] (y i + γ i ) + M (1 + d) -L(ξ), (11)
where L(ξ) represents the total loss in the financial system:

L(ξ) := i∈[n] ∆ i (ξ) + i∈[n] (R i (ξ) -1) -(s i + i ) + i∈[n] ξ i d + i∈[n] (R i (ξ) -1) + ( i + s i ) + ξ i (1 + d) -. (12)
The total loss in the financial system has four components, that represent respectively the total dead-weight loss, the loss to the outside creditors, the opportunity cost of the government (who could have invested the intervention amount at the government's outside return rate) and the loss taken by the government on its investment in the banks. The government optimization problem will amount to minimizing this total loss.

We define the set of admissible intervention strategies as

A M := ξ ∈ R n + | ∀i ∈ [n] \ C, ξ i = 0; i∈C ξ i ≤ M . ( 13
)
We consider the following problem of optimal equity infusions with maximum budget M M aximize

ξ∈A M V (ξ)
or equivalently, using Eq. ( 11), Problem 5.

P M := M inimize ξ∈A M L(ξ).
We make the following assumption.

Assumption 3. If there are multiple solutions to the above problem, then the government prefers the one that maximizes the value of its investment in the banks as given in Eq. ( 8).

Problem solution

We begin by showing that the government never invests in an insolvent bank.

Proposition 6. Let ξ * a solution to the government optimization problem P M . Then,

R i (ξ * ) < 1 implies that ξ * i = 0.
Proof. For any i such that R i (ξ * ) < 1 we have that ∆ i (ξ * ) does not depend on ξ * i . If ξ * i > 0 we would have a direct transfer from the government to the outside creditors which would not increase the value of the system.

The following proposition is without surprise and can be immediately checked. There are no interventions if the fire-sale price of the illiquid asset is the same as the fundamental price since in this case there are no dead-weight losses to reduce. Also, there are no intervention if all banks are initially solvent and liquid. Proposition 7. If r i ≥ 1 and γ i ≥ s i g(r i ) for all i ∈ [n] or if p = 1, then there is no intervention, i.e., ξ * ≡ 0 is the unique solution to P M .

We now give the first main result of the paper, Theorem 8, in which we quantify the optimal intervention in the case with a fire-sale price below the fundamental value and when there is a bank that is fundamentally insolvent or illiquid.

In order to solve the optimal intervention problem, we split the problem and each subproblem represents the optimal equity infusion problem when a given subset of core banks is guaranteed to be collectively solvent. As we will see, each sub-problem will be decoupled from the network fixed point and is a simple convex optimization problem.

More formally, we define, for a subset of core banks S ⊆ C, the subset of admissible intervention strategies in which we allow only the banks in S to receive government intervention

∀S ⊆ C, A S M := {ξ ∈ A M , ∀i ∈ S, R i (ξ) ≥ 1, ∀i ∈ [n] \ S, ξ i = 0}.
The constraint R i (ξ) ≥ 1 is set since, by Proposition 6, the government does not invest in a bank that is insolvent in equilibrium.

We define the sub-problem

P S M := M inimize ξ∈A S M L(ξ) (14)
and let L * (S) the value of its solution. The next sub-section is dedicated to showing that P S M is a convex optimization problem and thus it has a unique solution, see Corollary 13. Moreover we will show that the solution to the sub-problem is decoupled from the network fixed point.

We can now state our first main result.

Theorem 8. Assume the illiquid asset has a fire-sale price p < 1 and assume that there exists a bank i fundamentally insolvent or illiquid, i.e., r i < 1 or γ i < s i g(r i ). Let S * the minimizer over 2 C of L * (S). Let ξ * the solution to P S * M . Then ξ * is the solution to the optimal equity infusion problem P M .

Proof. Thanks to Proposition 6, we can write

P M = M inimize ξ∈A M L(ξ) = M inimize S⊆C,ξ∈A S M L(ξ) = M inimize S⊆C L * (S).
The solution has a combinatorial aspect, requiring to assess for each set S ⊆ C of eligible banks the solution to the sub-problem P S M . In other words, we need to assess, for each set S ⊆ C the cost of guaranteeing all banks in that set to be solvent. The solution is tractable when the number of banks that are eligible for infusions is sufficiently small. In particular, it may be suboptimal to guarantee all core banks to be solvent. The decision however cannot be simply stated in terms of the balance sheets of these banks and requires to solve the convex combinatorial optimization problem above. In particular the complete network observation is required.

Optimal equity infusion sub-problem when all banks in a given set is guaranteed to be solvent. In this section, we show that the sub-problem P S M is a convex optimization problem. Fix now an intervention strategy ξ ∈ A S M .

Remark 9. For i ∈ [n] \ S, the recovery rate R i (ξ) can be computed as a fixed point of the following function

φ(x, S) i,i∈[n]\S := y i -δ(x i , s i , γ i , y i ) + j∈S j π ji + j / ∈S j π ji (x j ∧ 1) i + s i . ( 15
)
The above function is a modified version of the function Φ in which all banks in the set of banks S are guaranteed to be solvent, i.e., the asset-to-debt ratio is larger than 1 for any bank belonging to the set S. We denote its largest fixed point by (R S i ) i∈[n]\S .

In other words, we have determined the asset-to-debt ratios for the banks in [n] \ S, when all banks in the set of banks S are guaranteed to be solvent. This is the only point in the sub-problem when we need to compute a network fixed point, but note that this fixed point does not depend on the equity infusions, since no bank in [n] \ S receives equity infusions. This means that the asset-to-debt ratios for the banks in [n] \ S are constant on the set of intervention strategies A S M , i.e., for all i ∈ [n] \ S we have

R i (ξ) = R S i , ∀ξ ∈ A S M .
We now note that for all i ∈ S and for all ξ ∈ A S M the asset-to-debt ratio of bank i is given as the fixed point of the real-valued function f S (•, ξ i ) :

R + → R + , f S (x, ξ i ) := y i -δ(x, s i , γ i + ξ i , y i ) + γ i + ξ i + j∈S j π ji + j / ∈S j π ji (R S j ∧ 1) i + s i . (16)
We let the minimal government infusion that makes bank i ∈ S solvent

ξ S i := inf{ξ i | f S (1, ξ i ) ≥ 1}. ( 17
)
We have the following immediate result about the set of admissible strategies when we restrict intervention to the subset S ⊆ C of core banks.

Proposition 10. Fix i ∈ S. The set of admissible strategies in which we allow only the banks in S to receive government intervention is given by

A S M =    ∅ if i∈S ξ S i ≥ M, {ξ ∈ R n | ∀i ∈ [n] \ S, ξ i = 0, ∀i ∈ S, ξ i ≥ ξ S i , i∈S ξ i ≤ M } otherwise. (18)
If A S M = ∅, then for all ξ ∈ A S M there is a unique fixed point larger than 1 for the map f S (•, ξ i ). We denote this fixed point by R S i (ξ i ) and we have R i (ξ) = R S i (ξ i ).

Proof. Since g is decreasing in ξ i , we have that ∀x, ξ i → f S (x, ξ i ) is increasing with

lim ξ i →∞ f S (x, ξ i ) = ∞. For ξ i sufficiently large, f S (1, ξ i ) ≥ 1.
We now fix ξ ∈ A S M = ∅. We let

I S i (ξ i ) := 1 p -1 1 1 0<s i g(R S i (ξ i ))-γ i -ξ i <py i .
This quantity captures the ratio between the fundamental value and the fire-sale price for banks forced to liquidate. We have

∂f S (x, ξ i ) ∂x = - ∂δ ∂x δ(x, s i , γ i + ξ i , y i )/( i + s i ) = -s i g (x)I S i (ξ i )/( i + s i ) ≥ 0.
From the Assumption 1 (iii) it also follows that

∂f S (x, ξ i ) ∂x ≤ s i /( i + s i ) < 1.
We also have

∂ 2 f S (x, ξ i ) ∂x 2 = - ∂δ ∂x δ(x, s i , γ i + ξ i , y i ) ≤ 0,
where the inequality holds thanks to the convexity of the function g (Assumption 1 (ii)).

The function f S (•, ξ i ) is thus continuous, increasing, concave and is bounded. Its first derivative is bounded from above by 1. It follows that f S (•, ξ i ) has either no fixed point or one fixed point, depending on whether f S (1, ξ i ) is smaller or greater than 1. Since f S (1, ξ i ) > 1, by the assumption that ξ ∈ A S M = ∅, there is a unique fixed point.

The previous proposition shows in particular that for i ∈ S and ξ ∈ A S M , R i (ξ) depends on ξ only through ξ i . The intuition is simple. No bank outside the set S receives equity infusions and we are guaranteed that banks in S pay their debts in full. Therefore the equilibrium payments of the banks outside the set S do not depend on the actual amount of the equity infusions. For any bank in the set S its debt-to-asset ratio depends only on its own equity infusion.

For i ∈ S, the dead-weight losses are given by

∆ i (ξ) = ∆ S i (ξ i ) := δ(R S i (ξ i ), s i , γ i + ξ i , y i ). (19)
From Eq. ( 12) and noting that R S i (ξ i ) > 1 for i ∈ S, the total loss writes

L(ξ) = i∈S ∆ S i (ξ i ) + ξ i d + (R S i (ξ i ) -1)( i + s i ) -ξ i (1 + d) - + i∈[n]\S ∆ S i + i∈[n]\S (R S i -1) -(s i + i ). ( 20
)
We can immediately attribute the loss to each bank i ∈ S (the first summation above) and respectively to the set of banks [n] \ S (the last two summations above). Remark in particular that the loss attributed to the banks in [n] \ S is constant over A S M . Formally, for a bank i ∈ S, we define the contribution of bank i to the loss in system fundamental value as

L S i (ξ i ) := ∆ S i (ξ i ) + ξ i d + (R S i (ξ i ) -1)( i + s i ) -ξ i (1 + d) -. (21)
We have the following lemma.

Lemma 11. The map

ξ i → ∆ S i (ξ i ) + ξ i d is convex over A S M . The map ξ i → L S i (ξ i ) is convex over A S M .
The proof of this lemma is given in Appendix A.

Remark 12. If

d∆ S i (ξ i ) dξ i + d ≥ 0 then ξ i = ξ i , i.e.
, the equity infusion is equal to to the minimum equity infusion for which the bank is solvent. The gradient dL(ξ) dξ i ≤ 0 at the minimum equity infusion is decreasing with the ratio of unstable short term debt to total debt s i s i +l i whenever g (1) < 0. This shows that banks with larger fraction of unstable short term debt receive equity infusions in priority, in order to minimize dead-weight losses.

We obtain as an immediate consequence the following result, key in proving Theorem 8.

Corollary 13. Let S ⊆ C. Consider the problem

P S M = M inimize ξ∈A S M L(ξ) = M inimize ξ∈A S M i∈S L S i (ξ) + i∈[n]\S ∆ S i + i∈[n]\S (R S i -1) -(s i + i ),
where L(ξ i ) is defined in Eq. ( 20) and L S i (ξ) is defined in Eq. ( 21). It has a unique solution whose value is denoted L * (S).

Using Lemma 11, the problem P S M is a convex optimization problem and thus has a unique solution.

Note that this problem is decoupled from the network fixed point.

The case when all core banks is guaranteed to be solvent. Of particular interest the case when government equity infusions guarantees that all core banks are solvent. We set now S = C and use the definitions in the previous paragraph, with S = C.

We are intersted in the solution to the problem P C M . We assume that the budget is sufficiently large such that a nontrivial solution to P C M exists, i.e., i∈C ξ C i ≤ M . We denote by ξ * i the unconstrained minimum of the convex function

L C i (ξ i ) on the interval [ξ C
i , ∞). Thanks to Eq. ( 23) and ( 24) it is given by

ξ * i =      1+I C i (ξ i ) 1+ s i i +s i g (R C i (ξ i ))I C i (ξ i ) = 1 + d if 1+I C i (ξ C i ) 1+ s i i +s i g (1)I C i (ξ C i ) ≤ 1 + d, ξ C i otherwise.
Remark 14. Note that the optimal amount of equity infusions increases in the ratio of short to total debt s i i +s i , the short term creditors outflow rate g (R C i (ξ i )) and I C i (ξ C i ) that captures the ratio between the fundamental value and the fire-sale price for banks forced to liquidate.

Remark 15. Note that i∈C ξ * i is the value of the government infusion that minimizes the loss in the financial system under the constraint that all core banks are solvent. In particular, if M ≥ i∈C ξ * i then it immediately follows that the budget constraint is not saturated.

Otherwise it is given by the dual problem

M inimize λ∈R, ξ i ≥ξ C i i L C i (ξ i ) + λ( ξ i -M ).
and the solution to the problem P C M is given by

ξ * i (λ) :=      1+I C i (ξ i ) 1+ s i i +s i g (R C i (ξ i ))I C i (ξ i ) = 1 + d + λ if 1+I C i (ξ C i ) 1+ s i i +s i g (1)I C i (ξ C i ) ≤ 1 + d, ξ i otherwise,
with the Lagrange multiplier λ obtained from the equation

i∈C ξ * i (λ) = M. ( 22
)
Is it optimal for the banks to receive the government equity infusion? We now give the second main result of the paper. This states that, whatever the set of banks that are guaranteed not to fail, the government equity infusion is such that the capital of all banks increases after intervention and after the transfer of the dividend to the government. This means that banks are better off by receiving the equity infusion and paying the dividend than not joining the equity infusion program.

Theorem 16. Fix a subset S ⊆ C of banks that are all guaranteed to be solvent. Let ξ * be the solution to the problem P S M . Then, for all i ∈ [n] we have

C i (ξ * ) ≥ C i (0).
The proof is given in Appendix B.

Numerical experiments

In the numerical examples we illustrate our theoretical findings on a simulated network generated similarly as in Amini et al. (2013a).

Figure 1 illustrates the idea behind our solution to the optimal equity infusion problem.

Each point represents a set of banks that are guaranteed to be collectively solvent (in total 2 |C| such sets) and the value of the solution for the corresponding sub-problem. For each set we plot the total loss in the system versus the total equity infusion (when the respective set is guaranteed to be solvent).

We observe that the budget constraint is not saturated at the optimal solution, see

Remark 15. This result suggests that injecting equity beyond a certain limit would not serve to mitigate systemic risk. We next plot in Figure 2 the optimal value of the problem P M for varying M . We observe that the loss in the system is significantly mitigated as we increase M and that this effect decreases with the maximum budget M . We now fix M and vary the liquidation price p (we could vary alternatively the parameters for the creditor outflow schedule so as to increase the outflow). We plot, for each value of the liquidation price p, the optimal equity infusion and the value of the solution. The results are shown in Figure 3.

The numerical results corroborate the theoretical results, namely that in absence of dead- Figure 3: Optimal value and optimal total equity infusion for the problem P M for varying p. All quantities are expressed as a percentage of the fundamental value of the financial system, as weight losses, i.e., p = 1, there is no intervention, see Proposition 7. As the liquidation price decreases, the amount of equity infusions increases.

Conclusions

We have written an optimization program for a government with constrained budget seeking to maximize the net worth of a financial system comprising of banks and their outside creditors. The government makes preferred equity infusions in the form of cash. When banks are prone to bank runs and invest in an illiquid asset, there exists a non-trivial solution to this problem. In our setting, a non trivial solution to the problem implies in particular that it is preferable for the government to invest in the banks' equity than to invest directly in the economy (for example by directly funding projects).

We find that all banks are better off by participating in the program. The government may find it optimal to invest in a strict subset of the core banks. The decision however cannot be simply stated in terms of the balance sheets of these banks and requires to solve a convex optimization problem for every subset of banks, to which we restrict infusions and which are all guaranteed solvent. In particular the complete network observation is required.

We offer a methodology to test the theory that the rationale behind the large equity infusions in 2008 was to avoid runs by short term creditors, and implicitly to minimize the dead weight losses induced by creditor outflows. Given the precise interbank network and balance sheet composition for each bank, one can compute the optimal equity infusions in each of the core banks (which may be zero for some core banks, i.e, no equity infusions).

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, which can be studied with methods similar to the current paper. 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 Proof of Lemma 11

Proof. From the definition of R S i (ξ i ) as the unique fixed point in the interval [1, ∞) in Eq. ( 16) we have

( i + s i ) dR S i (ξ i ) dξ i = - ∂δ ∂x (R S i (ξ i ), s i , γ i + ξ i , y i ) dR S i (ξ i ) dξ i - ∂δ ∂γ (R S i (ξ i ), s i , γ i + ξ i , y i ) + 1 ( i + s i ) d 2 R S i (ξ i ) (dξ i ) 2 = - ∂δ ∂x (R S i (ξ i ), s i , γ i + ξ i , y i ) d 2 R S i (ξ i ) (dξ i ) 2 - ∂ 2 δ ∂x 2 (R S i (ξ i ), s i , γ i + ξ i , y i )( dR S i (ξ i ) dξ i ) 2 -2 ∂ 2 δ ∂x∂γ (R S i (ξ i ), s i , γ i + ξ i , y i ) dR S i (ξ i ) dξ i - ∂ 2 δ ∂γ 2 (R S i (ξ i ), s i , γ i + ξ i , y i ).
We let

I S i (ξ i ) := 1 p -1 1 1 0<s i g(R S i (ξ i ))-γ i -ξ i <py i .
We obtain, using Assumption 1 (iii), that

dR S i (ξ i ) dξ i = 1 -∂δ ∂γ (R S i (ξ i ), s i , γ i + ξ i , y i ) i + s i + ∂δ ∂x (R S i (ξ i ), s i , γ i + ξ i , y i ) = 1 + I S i (ξ i ) i + s i + s i g (R S i (ξ i ))I S i (ξ i ) ≥ 0, d 2 R S i (ξ i ) (dξ i ) 2 = -∂ 2 δ ∂x 2 (R S i (ξ i ), s i , γ i + ξ i , y i )( dR S i (ξ i ) dξ i ) 2 i + s i + ∂δ ∂x (R S i (ξ i ), s i , γ i + ξ i , y i ) = -s i g (R S i (ξ i ))I S i (ξ i )( dR S i (ξ i ) dξ i ) 2 i + s i + s i g (R S i (ξ i ))I S i (ξ i ) ≤ 0.
It then immediately follows

d∆ S i (ξ i ) dξ i = 1 -( i + s i ) dR S i (ξ i ) dξ i = 1 - 1 + I S i (ξ i ) 1 + s i i +s i g (R S i (ξ i ))I S i (ξ i ) = I S i (ξ i ) s i i +s i g (R S i (ξ i )) -1 1 + s i i +s i g (R S i (ξ i ))I S i (ξ i ) (23)
≤ 0;

d 2 ∆ S i (ξ i ) (dξ i ) 2 = -( i + s i ) d 2 R S i (ξ i ) (dξ i ) 2 ≥ 0.
We have obtained the first part of the lemma, namely that the map

ξ i → ∆ S i (ξ i ) + ξ i d
is convex. We now show the second part of the lemma. We have

dL S i (ξ) dξ i = d + d∆ S i (ξ i ) dξ i + 1 1 (R S i (ξ i )-1)( i +s i )<ξ i (1+d) -( i + s i ) dR S i (ξ i ) dξ i + 1 + d (24)
= d + d∆ S i (ξ i ) dξ i + 1 1 (R S i (ξ i )-1)( i +s i )<ξ i (1+d)

d∆ S i (ξ i ) dξ i + d = d∆ S i (ξ i ) dξ i + d (1 + 1 1 (R S i (ξ i )-1)( i +s i )<ξ i (1+d) ). d 2 L S i (ξ) (dξ i ) 2 = d 2 ∆ S i (ξ i ) (dξ i ) 2 (1 + 1 1 (R S i (ξ i )-1)( i +s i )<ξ i (1+d) )
≥ 0.

In the second line above we have used Eq. ( 23). In the last inequality we have used the first part of the lemma. This completes the proof of the lemma.

B Proof of Theorem 16

Proof. In light of Eq. ( 7), we can write the condition C i (ξ) ≥ C i (0) as

∆ i (ξ * ) + ξ * i d ≤ ∆ i (0) + j∈[n] j π ji R j (ξ * ) ∧ 1 -R j (0) ∧ 1 (25)
which becomes a simple constraint on ξ * i as follows ∀i ∈ S,

∆ S i (ξ * i ) + ξ * i d ≤ ∆ i (0) + j∈S j π ji 1 -R j (0) ∧ 1 + j∈[n]\S j π ji R S j ∧ 1 -R j (0) ∧ 1 .
Suppose now by way of contradiction that there exists i such that C i (ξ) < C i (0), i.e.,

∆ i (ξ * ) + ξ * i d > ∆ i (0) + j∈[n] j π ji R j (ξ * ) ∧ 1 -R j (0) ∧ 1 .
This inequality cannot hold for i ∈ [n] \ S, who receive no infusion but have indirect gains from equity infusions in their debtors.

Suppose that above inequality holds for i ∈ S. Thanks to Lemma 11, the map ξ i → ∆ i (ξ i ) + ξ i d is convex on A S M . Since ∆ i (ξ * ) + ξ * ≥ ∆ i (0), it follows that the map attains its minimum for a ξ i < ξ * i . But since ξ * i is a solution to P S M , it must be that

(R S i (ξ i ) -1)( i + s i ) -ξ i (1 + d) -≥ (R S i (ξ * i ) -1)( i + s i ) -ξ * i (1 + d) -.
This is equivalent to (R S i (ξ i ) -1)( i + s i ) -ξ i (1 + d) ≤ 0 and (R S i (ξ i ) -1)( i + s i ) -ξ i (1 + d) ≤ (R S i (ξ * i ) -1)( i + s i ) + ξ * i (1 + d),

i.e. ∆ S i (ξ i ) + ξ i d ≥ ∆ S i (ξ * i ) -ξ * i d. If ξ i is a strict minimum, then we directly obtain a contradiction. If with ξ i is not a strict minimum then we have a contradiction with Assumption 3.

  . The investment pays to the government a preferred dividend rate d at time 1. The equilibrium values of the asset-to-debt ratios of all banks in the system are jointly given by the fixed point of the following function, similar as in[START_REF] Eisenberg | Systemic Risk in Financial Systems[END_REF],[START_REF] Cifuentes | Liquidity risk and contagion[END_REF],[START_REF] Amini | Systemic risk with central counterparty clearing[END_REF]

Figure 1 :

 1 Figure1: Total loss in the system vs. total equity infusion. Each point represents a set of banks that are guaranteed to be collectively solvent. All quantities are expressed as a percentage of the fundamental net worth of the financial system.

Figure 2 :

 2 Figure 2: Optimal value for the problem P M for varying M .

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] Veronesi | Paulson's gift[END_REF],[START_REF] Landler | Drama behind a $250 billion banking deal[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 modelWe consider a one period network model for the cross-section of a financial system, t = 0, 1. The financial system is constituted of a set [n] := {1, . . . , n} of interrelated financial institutions ("Banks") and a continuum of outside creditors. There exists a government

Modeling the roll-over coordination game of the short term creditors is beyond the scope of this paper, and thus the short term creditor outflow schedule is exogenous. For models of insolvency and rollover risk we refer the reader to[START_REF] Morris | Illiquidity component of credit risk[END_REF],[START_REF] Lütkebohmert | A multi-period bank run model for liquidity risk[END_REF],[START_REF] He | Rollover risk and credit risk[END_REF],[START_REF] Krishenik | When do creditors with heterogeneous beliefs agree to run?[END_REF].

Acknowledgement We thank Hamed Amini for valuable discussions.


Daniel Delahaye
email: delahaye@cena.frpuechmor@recherche.enac.frrjhans@mit.edu

Stephane John Puechmorel

Jonathan Histon Hansman

Cena

Air Traffic Complexity based on Non Linear Dynamical Systems

Keywords: Complexity, Dynamic Systems, Topological Entropy, Control Workload. 1

This paper present a new air traffic complexity metric based on non-linear dynamical systems. The goal of this metric is to identify any trajectory organisation in the traffic pattern in order to quantify the associated control difficulty. Many others works have proposed metrics in the past, but they usually identify one feature of the complexity and were not able to address any pattern organization. A full vector field can be summarized by the equation of a dynamical system which describe and control the evolution of a given state vector ( X = [x, y, z] T ). The key idea of our work is to find a dynamical system which modelizes a vector field as close as posible to the observations given by the aircraft positions (and speeds). Two approaches are then presented. The first one is based on a linear dynamical system and produce an aggregate complexity metric. The second one, which is the main part of this paper, uses a non-linear dynamical system modeling which fits the observations without error. Such a modeling enable to identify high (low) complexity areas on a map and addresses trajectory segments instead of vector field which is more relevant for the air traffic management application (the air controller sees speed vectors on his screen but works on trajectory segments in his mind in order to produce resulution scenario (past and future)). A collocation techniques has been used to speed up the computation of the associated complexity metric in order to address large areas with many aircraft. Such a metric is very adapted to compare different traffic situations for any scale (sector or country).

Introduction

Air traffic control organizes air flows in order to ensure flight safety and to increase the capacity of the route network. Currently, about 7500 are registered everyday over France, which is a crossroad for the whole European airpsace. This traffic generates a huge amount of control workload and the airspace is then divided into elementary sectors which are managed by air navigation controllers. For several years, a constant increase of air traffic has induced more and more congestion in the control sectors. Two strategies can then be applied to reduce such a congestion. The first one consist in adapting the demand to the existing capacity (slot-route allocation, collabarative decision making etc...). The second one adapts the capacity to the demand (modification of the air network, of the sectorization, new airportsetc ...). For the two preceding approaches, the capacity of a sector is measured by the number of aircraft flying across the sector during a given period of time. The observation of controlled sectors shows that sometimes, controllers accept planes beyond the capacity threshold, while in other situations, they refuse traffic before the capacity is reached. This phenomenon clearly shows that the operational metric alone cannot account for controller's workload. The goal of this study is to synthesize a traffic complexity indicator in order to better quantify the congestion in air sector, which will be more relevant than a simple number of aircraft which is independent of the traffic configuration. More precisely, our objective is to build some metrics of the intrinsic complexity of the traffic distribution in the airspace. Those metrics must capture the level of disorder (or organization) of any traffic distribution. Usuallly, metrics are focused on the speed vector distribution and the associated disorder metric captures only some features of the traffic complexity. The real objective of our work is to build a metric which measures the disorder or the organization of a set of trajectories in a 4D space (3D for the space and 1D for the time).

Those metric are relevant for many applications in the air traffic management area. For instance, when a sectoring is designed [START_REF]Genetic algotithms for partitioning airspace[END_REF], the sectors have to be balanced from the congestion point of view and for the time being, only the number of aircraft is used to reach this objective. Another example where a congestion metric is needed is the traffic assignment [START_REF] Delahaye | Genetic algotithms for air traffic assignment[END_REF][START_REF] Delahaye | Aispace congestion smoothing by stochastic optimization[END_REF] for which an optimal time of departure and a route are searched for each aircraft in order to reduce the congestion in the airspace. Complexity metric may also be used to design new air networks, for dynamic sectoring concept, to define fu-ture ATM concepts (Free Flight) etc....Complexity metrics would enable to qualify and quantify the performance of the Air Traffic service providers and enable a more objective consultation between airlines and providers.

The work presented in this paper is based on the dynamical systems modeling of the air traffic. A dynamical system describes and controls the evolution of a given state vector. If such a vector is given by the position of aircraft X = [x, y, z] T , a dynamical system associates a speed vector ˙ X = [vx, vy, vy] T to each point in the airspace. So, a full vector field can be summarized by the equation of the dynamical system. The key idea is to find a dynamical system which modelize a vector field as close as possible to the observations given by the aircraft positions (and speeds). Based on this dynamical system modeling, a trajectory disorder metric can be easily computed.

In a first part, this paper will summarize the previous related works. The second part will present a linear dynamical system modeling for which the complexity metric can be represented into a complex coordinate system. In this system, it is very easy to identify any speed vector organization pattern. The third part introduces a non linear extension of the previous dynamical system modeling. Such a modeling is exact and can fit the observations without error. Such a non linear modeling can be used to produce maps of complexity by identifying areas with high(low) complexity. This extension can also address time extension of the model and can then work straightly on the trajectory segments instead of speed vectors. A collocation techiques has been used to speed up the computation of the associated complexity; mainly when such a computation is done on large areas like countries.

Previous related works

The airspace complexity is related with both the structure of the traffic and the geometry of the airspace. Different efforts are underway to measure the whole complexity of the airspace.

Significant research interest in the concept ot ATC complexity was generated by the "Free Flight" operational concept. Integral to Free Flight was the notion of dynamic density. Conceptually, dynamic density is a measure of ATC complexity that would be used to define situations that were so complex that centralized control was required [START_REF]Final report of rtca task force 3: Free flight implementation[END_REF].

Windemere inc [START_REF] Inc | An evaluation of air traffic control complexity[END_REF] proposed a measure of the perceived complexity of an air traffic situation.This measure is related with the cognitive workload of the controller with or without knowledge of the intents of the aircraft. The metric is human oriented and is then very subjective.

Laudeman et al from NASA [START_REF] Laudeman | Dynamic density : an air traffic management metric[END_REF] have developed a metric called "Dynamic Density" which is more quantitative than the previous one and is based on the flow characteristics of the airspace. The "Dynamic Density" is a weighted sum of the traffic density (number of aircraft), the number of heading changes (¿15), the number of speed changes (¿0.02 Mach), the number of altitude changes (¿750 ft), the number of aircraft with 3-D Euclidian distance between 0-25 nautical miles, the number of conflicts predicted in 25-40 nautical miles. The parameters of the sums have been adjusted by showing different situations of traffic to several controllers. Finally, B.Sridhar from NASA [START_REF] Sridhar | Airspace complexity and its application in air traffic management[END_REF], has developed a model to prodict the evolution of the metric in the near future. Efforts to define "Dynamic Density" have identified the importance of a wide range of potential complexity factors, including structural considerations.

The traffic itself is not enough to describe the complexity associated with an airspace. A few previous studies have attempted include structural consideration in complexity metrics, but have done so only to a restricted degree. For example, the Wyndemere Corporation proposed a metric that included a term based on the relationship between aircraft headings and dominant geometric axis in a sector [START_REF] Inc | An evaluation of air traffic control complexity[END_REF]. The importance of including structural consideration has been explicitly identified in recent work at Eurocontrol. In a study to identify complexity factors using judgment analysis, "Airspace Design" was identified as the second most important factor behind traffic volume [START_REF] Kirwan | Investigating complexity factors in u.k. air traffic management[END_REF].The impact of the structure on the controller workload can be found on the paper [START_REF] Histon | Introducing structural consideration into complexity metrics[END_REF][START_REF] Histon | Structural consideration and cognitive complexity in air traffic control, Proceedings of the 21 th Air Traffic Management for Commercial and Military Systems[END_REF]. Those papers show how strong the structure of the traffic (airways, sectors, etc...) is related with the control workload.

The previous models do not take into account the intrinsic traffic disorder which is related to the complexity. The first efforts related with disorder can be found in [START_REF] Delahaye | Air traffic complexity : Towards intrinsic metrics, Proceedings of the Second USA/EUROPE ATM R&D Seminar[END_REF]. This paper introduces two classes of metrics which measure the disorder of a traffic pattern. The first class is based on geometrical properties and proposed new metrics which are able to extract features on the traffic complexity such as proximity (measures the level of aggregation of aircraft in the airspace), convergence (for close aircraft, this metric measures how strongly aircraft are closer to each other) and sensitivity (this metric measure how the relative distance between aircraft is sensible to the control manouver). The second class is based on a dynamic system modeling of the air traffic and use the topological entropy as a measure of disorder of the traffic pattern.

G.Aigoin has extended and refined the geometrical class by using a cluster based analysis [START_REF] Aigoin | Air traffic complexity modeling[END_REF]. Two aircraft are said to be in the same cluster if the product of their relative speed and their proximity (a function of the inverse of the relative distance) is above a threshold. For each cluster, a metric of relative dependence between aircraft is computed and the whole complexity of the cluster is then given by a weighted sum of the matrix norm. Those norms give an aggregated measure of the level of proximity of aircraft in clusters and the associated convergence. From the cluster matrix, it is also possible to compute the difficulty of a cluster (it measures how hard it is to solve a cluster). Multiple clusters can exist within a sector, and their interactions must also be taken into account. A measure of this interaction has been proposed by G.Aigoin [START_REF] Aigoin | Air traffic complexity modeling[END_REF]. This technique allows multiple metrics of complexity to be developed such as average complexity, maximum and minimum cluster complexities, and complexity speeds.

Another approach based on fractal dimension has been proposed by S.Mondoloni and D, Liang in [START_REF] Mondoloni | Airspace fractal dimension and applications[END_REF]. Fractal dimension is a metric comparing traffic configurations resulting from various operational concepts. It allows in particular to separate the complexity due to sectorization from the complexity due to traffic flow features. The dimension of geometrical figures is well-known: a line is of dimension 1, a rectangle of dimension 2,etc.... Fractal dimension is simply the extension of this concept to more complecated figures, whose dimension may not be an integer. The block count approach is a practical way of computing fractal dimensions: it consists in describing a given geometrical entity in a volume divided into blocks of linear dimension d and counting the number of blocks contained in the entity N .The fractal dimension D 0 of the entity is thus :

D 0 = lim d→0 log N log d
The applicatin of this concept to air route analysis consists in computing the fractal dimension of the geometrical figure composed of existing air routes. An analogy of air traffic with gas dynamics then shows a relation between fractal dimension and conflict rate (number of conflicts per hour for a given aircraft). Fractal dimension also provides information on the number of degrees of freedom used in the aispace: a higher fractal dimension indicates more degrees of freedom. This information is independent of sectorization and does not scale with traffic volume. Therefore, fractal dimension is a measure of the geometrical complexity of a traffic pattern. Some new geometrical metrics have been developed in [START_REF] Delahaye | A new air traffic complexity metric based on dynamical system modelization[END_REF]which are able to capture the level of disorder or the level of aorgainization for some traffic patterns. For instance, in a curl moving, the speed vector are very different even if the global moving is full organized without any changes in the relatives distance between aircraft. To capture those features, the covariance and the Koenig metrics have been developed. The first one is able to identify disorder or organization of translation movings. The second one identify organized curl moving.

All the previous metrics capture only one feature of the complexity and are not able to produce an aggregate metric which can capture all the possible situations (high-low density, how-low convergence, translation organization, curl organization etc ...). The topological entropy (kolmogorov entropy) is the only metric which is able to capture most features of the complexity. The non-linear form is even able to identify any trajectories organizations (aircraft following the same path at the same speed). The next section will describe this metric in detail for the linear and the non-linear forms.

Linear Dynamical System Modeling

Principle

This metric is based on the modeling of the set of trajectories by a linear dynamic system. This enable to identify different structure of organization of the aircraft speed vectors such as translation, curl organizations or a mix of them.

The key idea of this metric is to model the set of aircraft trajectories by a linear dynamical system which is controlled by the following equation :

˙ X = A. X + B
where X is the state vector of the system :

X =   x y z  
The eigen values of the matrix A control the evolution of the system. The real part of those eigen values is related with the convergence or the divergence property of the system in the direction of the eigen vector. When such a eigen value has positive real part, the system is in expansion mode and when it is negative the system is in contraction mode. On the other end, the imaginary part of the eigen values are related with the level of curl organization of the system. Depending of those eigen values, a dynamical system can evolve in contraction, expension, rotation or a combination of those three modes.

✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂ ✂ ✁✂
The figure 1 shows examples of evolutions with different eigen values. The initial situation consist in two aircraft moving in parallel at the same speed and three possible evolutions are then drawn after a time period d. In the first case, the eigen value is real and negative; the system evolves in a contraction mode and the two aircraft are converging. The second situation represent a diverging evolution for which the eigen value is real and positive. It must be noticed that in the two previous situations, the distance between aircraft changes with time. The last evolution is associated with a full imaginary eigen value for which the aircraft stay a the same distance from each other in a curl moving. The evolution properties of the system related with the position of the eigen values can be summerized in the complex coordinate system (see figure 2). In this coordinate system, the vertical ellipse identifies the organized situations (in translation, curl or both).

A dynamical system can then be considered as a map T from the state space X to itself. Based on this mapping T , one can define the topological entropy (or Kolmogorov entropy) of the dynamical system which measure the level of mixing of X by T . This entropy is associated with the changes of the relative distances between points from X by T . The topological entropy of a dynamical system is then a disorder indicator of the distribution of the aircraft in the considered airspace. This entropy is not a statistical metric and is very adapted to the air traffic control system for which there are few aircraft in the sectors.

Kolmogorov Entropy Computation

The kolmogorov entropy is computed with the help of the eigen value decomposition of the matrix A :

A = L.S.U T
where S is the diagonal matrix of the eigen values. Based on the observations of the aircraft (positions and speed vectors), the dynamical system has to be adjusted with the minimum error. This fitting has been done with a Least Square Minimization method. For each considered aircraft i, it is supposed that position X i = [x i , y i , z i ] T and speed vector V i = [vx i , vy i , vz i ] T are given. An error criterium between the dynamical system model and the observation is computed :

E = i=N i=1 V i -A. X i + B
In order to use matrix forms the following matrices are introduced.

X =     x 1 x 2 x 3 ... x N y 1 y 2 y 3 ... y N z 1 z 2 z 3 ... z N 1 1 1 ... 1     V =   vx 1 vx 2 vx 3 ... vx

 

With such matrices, the error criterium E can be written :

E = V -C.X
To minimize E is the same as to minimize :

E 2 = V -C.X 2
The problem is to find the matrix C which minimize such a criterium. By using the matrix derivation properties, the gradient of E 2 is given by :

∇ C E 2 = -2.(V -C.X).X T
The optimum is given by ∇

C E 2 = 0 ⇔ C.X.X T = V X T
The optimum matrix C opt is then given by :

C opt = V.X T .(X.X T ) -1
The expression X T .(X.X T ) -1 is the pseudo inverse of the matrix X T and can be writen as :

X T .(X.X T ) -1 = L T .S -1 .R
where S is the diagonal matrix of the singular values of the matrix X T . This singular value decomposition is very helpful in order to avoid condition troubles. The matrix C is finally given by :

C = V.L T .S -1 .R
The matrix A is then extracted from the matrix C, and the associated eigen value decomposition is given by :

A = L.D.U T
The eigen values of the matrix D are complex numbers. In order to produce a scalar metric, the larger obsolute value of the real part of those complex eigen values is computed. The sign of this larger real part is related with the mode of the system (contraction or expansion). If those eigen values are drawn in the complex coordinates, it gives information about the level of contraction/expansion of the system and also its curl tendency. Such a metric can identify any speed vector organization (translation, curl or both) because it is sensitive to relative distances between aircraft. An example of computation of such a metric is given on figures 3,4,5. The traffic simulation consists in 41 aircraft involved in a fuzzy convergence 3. The evolution of real part of the larger eigen value is given on figure 4. As it can be noticed, the metric begins to be negative showing the situation is globally converging and after the crossing the metric becomes positive indicated the situation is now globally diverging. If such eigen value is represented in the complex coordinate system (see figure 5), the locus of the conjugate eigen value begins from the right side and move to the left side. The eigen value having an imaginary part means the system have a global curl moving during the crossing. Figure 5: Evolution of the larger eigen value in the complex coordinate system Linear system dynamical system modeling enable to produce an aggregate metric associated to any traffic situation and can recognize any global organization pattern. If detail metric is needed in order to indentify high (low) complexity areas, a non-linear dynamical system has to be used.

Non Linear extension

Interpolating splines are common tools in the field of numerical analysis. Those applications are optimal with respect to a cost functional that controls the smoothness of the solution and allows exact interpolation at given points [START_REF] Wahba | Spline models for observational data[END_REF]. One of the most elementary example of such family of applications is given by piecewise third order polynomials, named cubic splines, which give the smoothest interpolation with respect to the second derivative. Many generalizations of splines have been introduced, like vector splines [START_REF] Suter | Motion estimation and vector splines[END_REF] and splines on manifolds [START_REF] Crouch | Spline elements on spheres[END_REF]. All those spline models may be used for static data, but dynamical system modelling requires time to be taken into account. Dynamical splines may be constructed as solutions to a optimal linear control problem. More specifically, let a controlled system :

dx dt = Ax + bu (1)
y = C t x (2)
with A, b, C matrices, x the state vector and u the command. The dynamic interpolation problem is to find the command u 0 that realizes the minimum of the functional :

λ 2 T 0 u 2 (t)dt + 1 2 m i=1 (y(t i ) -y i ) t (y(t i ) -y i )
where the y i , i = 1 . . . m are the values to be taken by the system at times t i , i = 1 . . . m. The solution of this problem is known as smoothing spline and is computed as a linear combination of elementary kernel functions :

k ti (t) = C t exp(A(t i -t)) t ≤ t i 0 t > t i
This approach can be used to obtain smooth trajectories from samples.

Div-Curl Splines

Computing topological entropy for a given trafic situation requires interpolating a vector field given only samples (positions and speeds of aircraft at a given time). Vector spline interpolation seeks for the minimum of a functional of the form :

1 2 D LX(x) 2 dx + 1 2 m i=1 X(x i ) -V i 2
where X is a vector field defined on a domain D ⊂ R n , L is an elliptic differential operator and (x i , V i ) i=1...m are the interpolation data [7]. By introducing the adjoint operator L t , optimal vector field can be shown to be a linear combination of shifted version of the elementary solution kernel of the PDE L t L. A special case is the so-called "div-curl" splines with the criterion :

Topological entropy computation

Combining trajectory extrapolation based on dynamic splines with vector spline interpolation yields a dynamic vector field model of the trafic suitable for evaluating topological entropy.

Vector dynamic splines

Mixing the previous approach, we will seek for an optimal solution of a dynamic interpolation problem, namely find a time-dependent vector field X(t, x) defined on [0, T ]×D and continuously differentiable up to order 2 in time coordinate that minimize :

T 0 D ∂X(t, x) ∂t 2 + α LX(t, x) 2 dxdt
under the constraints :

X(t i , x i ) = V i , i = 1 . . . m
where α is a positive real. This value controls the relative importance of the vector field variation thru time over the discrepancy of X as measured by the differential operator L. Taking α = 0 will yield to a constant vector field over time, while α → +∞ will focus on the differential part.

Variational problem

Let L be an elliptic differential operator of order p with constant coefficients. L t will denote the adjoint operator of L. We will assume in the following that the vector field X has fixed value at 0 and T and that for all t ∈ [0, T ], X(t, .) belongs to the sobolev space H p . Furthermore, the mapping ttoX(t, .) must be a least two time continuously differentiable.

Let γ : [0, T ] → C p (R n , R n ) a variation of X (that is time-dependent H p vector field γ(0, .) = γ(T, .) = 0). Simple calculus of shows that the gradient of :

T 0 D ∂X(t, x) ∂t 2 + α LX(t, x) 2 dxdt
with respect to γ is the linear mapping :

γ → T 0 D γ, ∂ 2 X ∂t 2 -αL t LX dxdt
The constraints on X impose that :

γ(t i , .) = 0, i = 1 . . . m
One can find an elementary solution e of the PDE

∂ 2 X ∂t 2 -αL t LX
and use its translates e ti,xi to represent the evaluation operator at (t i , x i ). Combining this with the gradient previously obtained shows that the optimal solution is of the form :

X = m i=1
e ti,xi + X 0 with X 0 an element of the kernel of the operator :

∂ 2 X ∂t 2 -αL t LX

Results

The topological entropy computation based on thin plate splines (equal importance of constant div and curl) and dynamic interpolation has been applied to the french trafic of the 11 August 2001 on some sectors. To speed up computations, an approximation of the true solution has been made with the help of a quasi-interpolation approach. The method can be sketched as follows. Since spline kernel is an elementary solution, applying the operator L t L on it will yield to a delta distribution. By replacing in the differential operator all derivatives by finite differences approximations, the resulting operator applied on the kernel will yield a bell-shaped function that approximate the delta distribution. Those functions are used to produce an interpolating vector field without having to solve a linear system for coefficients. The following figures show examples of computation of such a metric for two sectors (Z1, JS). Two kind of simulation are presented : the first one with standard routes and the second one with direct routes. The absciss represents times samples (each ten second for a full day). Sector JS is more complicated than Z1. Based on those results it can be concluded that direct route assignment will decrease the complexity of JS, but will increase for Z1 (note however that complexity peaks are more concentrated in time for direct routes). The map of french sector is given at the end of the article.

Conclusion

We have presented in this paper a new air traffic complexity metric based on non-linear vector field model of air traffic. Extending previous results on topological entropy, this method allows identification of traffic pattern organization in its full generality while previous works were limited to specific aspects of the complexity. Furthermore, since we are processing trajectory segments instead of samples at a given time, the induce metric is more realistic from an operational point of view. The quasiinterpolation algorithm allows real-time processing on operational traffic even for large areas (Europe or US). Unlike linear models which produce mean complexity indicators, the non-linear one may give local information, thus providing a way of displaying maps of complexity. In a future work, such a tool will be applied to comparison of US and Europe airspace.

Figure 1 :

 1 Figure 1: Impact of the eigen values on the dynamic of a system

Figure 2 :

 2 Figure 2: Impact of the eigen values on the dynamic of a system

Figure 3 :Figure 4 :

 34 Figure 3: Fuzzy convergence of 41 aircraft

R 2 α

 2 ∇divX 2 + β ∇curlX with α, β positive reals. Relative values of these reals controls the smoothness of the approximation by focusing on constant divergence or constant curl.

Figure 6

 6 Figure 6: Z1 sector

Figure 7 Figure 8

 78 Figure 7: Z1 sector direct routes

Figure 9 :

 9 Figure 9: JS sector direct routes

  1980 and his Ph.D. in Physics, Meteorology, Aeronautics & Astronautics and Electrical Engineering from MIT in 1982. He is the Head of the Humans and Automation Division, the Director of the International Center for Air Transportation and of the Aeronautical Systems Laboratory at MIT. He conducts research in several areas related to flight vehicle operations and aviation safety. His current research activities focus on advanced cockpit information systems, including Flight Management Systems, air-ground datalink, electronic charting, advanced alerting systems, and flight crew situational awareness, cockpit human factors and information management. Jonathan Histon is a PhD student in the International Center for Air Transportation of the Department of Aeronautics & Astronautics at MIT. He obtained a B.Sc. (Honours Physics) in 2000 from Simon Fraser University, Canada. He did his Master thesis at the Aero Astro Department at MIT. His main research interests are metrics of complexity, human factors in ATC, and safety in ATC.

  N vy 1 vy 2 vy 3 ... vy N vz 1 vz 2 vz 3 ... vz N 12 a 13 b 1 a 21 a 22 a 23 b 2 a 31 a 32 a 33 b 3

			
			
			a 11 a
	C =	