Laurent Devineau
email: laurent.devineau@isfaserveur.univ-lyon1.fr

Stéphane Loisel
email: stephane.loisel@univ-lyon1.fr

Risk aggregation in Solvency II: How to converge the approaches of the internal models and those of the standard formula?

Keywords: Economic capital, Solvency II, nested simulations, standard formula, risk aggregation, equity, risk factors, diversification

Two approaches may be considered in order to determine the Solvency II economic capital: the use of a standard formula or the use of an internal model (global or partial). However, the results produced by these two methods are rarely similar, since the underlying hypothesis of marginal capital aggregation is not verified by the projection models used by companies. We demonstrate that the standard formula can be considered as a first order approximation of the result of the internal model. We therefore propose an alternative method of aggregation that enables to satisfactorily capture the diversification among the various risks that are considered, and to converge the internal models and the standard formula.

Introduction

For the purpose of the new solvency repository of the European Union for the insurance industry, Solvency II, insurance companies are now required to determine the amount of their equity, adjusted to the risks that they incur. Two types of approach are possible for this calculation: the use of a standard formula or the use of an internal model1 . The "standard formula" method consists in determining a capital for each elementary risk and to aggregate these elements using correlation parameters. However, the internal model enables to measure the effects of diversification by creating a simultaneous projection of all of the risks incurred by the company. Since these two methods lead in practice to different results (see [START_REF] Derien | Construction d'un algorithme d'accélération de la méthode des « simulations dans les simulations » pour le calcul du capital économique Solvabilité II[END_REF] for an analysis for classical loss distributions and copulas), it seems crucial to explain the nature of the observed deviations. This is essential, not only in terms of certification of the internal model (in relation to the regulator), but also at an internal level in the Company's Risk Management strategy, as the calculation of the standard formula must in any case be carried out, independently of the use of a partial internal model. One must therefore be able to explain to the management the reason for these differences, in a manner that is understood by all, including the top ranks of the management and the shareholders.

In this paper, we shall be analysing the validity conditions of a "standard formula" approach for both the calculation of the marginal capital and the calculation of the global capital. We shall demonstrate that under certain hypotheses that are often satisfied in models used by companies, the marginal capitals according to the standard formula are very close, and sometimes identical, to those obtained with the internal model. However, we shall also demonstrate that the standard formula generally fails in terms of elementary capital aggregations and shows deviations in relation to the global capital calculated with the internal model that can be significant. These differences observed in the results are mainly caused by two phenomena: the level of equity is not adjusted in terms of underlying risk factors, the "standard formula" method does not take into account the "cross-effects" of the different risks that are being considered. In the event of the hypotheses inherent to the "standard formula" approach not being satisfied, we present an alternative aggregation technique that will enable to adequately comprehend the diversification among risks. The advantage of this method is that risk aggregation with the standard formula may be regarded as the first-order term of a multivariate McLaurin expansion series of the "equity" with respect to the risk factors. In some instances, risk aggregation with internal models may be approximated by using higher order terms in addition in the expansion series.

In any case, this way of considering things enables to explain to the management the main reasons of the difference between the result of the standard formula and the result obtained with the internal model.

3

In the first part we shall discuss the issues surrounding the calculation of economic capital in the Solvency II environment. We shall then formalise the "standard formula" and "internal model" approaches and explain the differences on the base of projections of a savings type portfolio. In the last section, we shall offer a description of our alternative aggregation method and apply it to the portfolio being considered. Finally, we shall examine the field of application and limitations of this approach by using another portfolio with a risk profile that makes it more complex to apply our method.

The calculation of the Solvency II economic capital

In this Section we offer some reminders concerning the notion of Solvency Economic Capital II and we describe the "standard formula" approaches and the technique of "nested simulations" implemented for the purposes of an internal model.

General Information

For a detailed presentation of the Solvency II economic capital calculation problematic, the reader may consult [START_REF] Derien | Construction d'un algorithme d'accélération de la méthode des « simulations dans les simulations » pour le calcul du capital économique Solvabilité II[END_REF]. It is useful to remember that the Solvency II economic capital corresponds to the amount in equity available to a company facing financial bankruptcy with a one year horizon and a confidence level of 99.5%. This definition of the capital rests on three notions: -Financial bankruptcy : situation where the market value of the Company's assets is inferior to the economic value of the liabilities (negative equity), -One year horizon: necessity of being able to carry out the distribution of the equity within one year, -

The 99.5% threshold: the required level of Solvency.

The Solvency II capital is based on the economic balance sheet of the company as from date t=0 and as of date t=1.

We offer here an explanation of the following notations: -A t the market value of the asset at t, -L t the fair value of liabilities at t, -E t the equity at t.

The balance sheet at takes on the following form:

Economic balance sheet at t

A t E t L t
At the initial date of the assets' value, the liabilities and the equity of the company are determinist figures, whereas at t=1, they are random variables that depend on random (financial, demographic...) factors that took place during the first year.

The value of each item in the balance sheet corresponds to the expected value under the risk-neutral probability Q of discounted future cash-flows.

Denote :

the filtration that permits to characterise the available information for each date, -the discount factor that is expressed with the instantaneous risk free interest rate r u : , -P t the cash-flows of the liabilities (claims, commissions, expenses) for the period t, -R t the profit of the company for period t. Equity and the fair value of the liabilities at the start date, , are calculated in the following manner: and In order to determine the equity and the fair value of the liabilities at t=1, a "real-world" conditioning must be introduced for the first period. The and variables are calculated with the expected value under the risk-neutral probability of the discounted future cash-flows, dependent of the "real-world" information of the first year (designated as

). This leads to the following calculations: , and .

The economic capital is then evaluated with the following relation: where P(0,1) is the price at time 0 of a zero-coupon bond with maturity 1 year. The quantity appears as a (mathematical) surplus that needs to be added to the initial equity in order to guarantee the following condition:

The standard formula

In this paper, we shall use the term "standard formula" to describe any method that aims to calculate the economic capital at the level of each "elementary risk" (stock, interest rate, mortality rate,...) and then to aggregate these capitals with correlation matrices.

A "standard formula" method may either rest on a single level of aggregation or implement successive aggregations, as is the case for the QIS (see: CEIOPS QIS 4 Technical Specifications 2008). In fact, this method consists in aggregating, in a first stage, the elementary capitals within different risk modules ("market" module, "life" module, "non-life" module,...) This phase corresponds to an intra-modular aggregation. The capitals of each module are then aggregated, so as to obtain the global economic capital (inter-modular aggregation). It should be noted that both the GCAE (2005) and [START_REF] Filipovic | Multi-Level Risk Aggregation[END_REF] underline the limits of such an approach 2 . A "standard formula" type method corresponds to a bottom-up approach (i.e. starting with the elementary risks and ending with the calculation of the global capital). The calculation of the elementary capitals implies the use of an ALM model that provides a financial balance sheet as from the start date. This model enables, amongst other things, to calculate the amount of "central" equity, i.e. the equity according to the conditions on the calculation date, as well as the equity resulting from an instantaneous shock of these conditions.

More precisely, to calculate the elementary capital for the purpose of risk R, an instantaneous shock is delivered to the R factor, and the equity is determined after the shock. This amount is then subtracted from the central equity in order to obtain the economic capital for the purpose of R. In order to determine , the calculations must be reconditioned with a new filtration in mind, which derives from the instantaneous shock on the R factor. The ALM model is used to estimate the following quantity:

where corresponds to the risk-neutral probability that is applied to filtration .

The elementary capital is then represented as .

The following diagram illustrates the calculation method of the elementary capital in terms of Risk R: Note that (resp. ) represents the market value of the assets (resp. the fair value of the liabilities) at 0 after the shock on the R factor.

2 [START_REF] Filipovic | Multi-Level Risk Aggregation[END_REF] demonstrates that the correlation factors that enable to carry out the inter-modular aggregation are entity specific. Therefore, since it is impossible to use a "benchmark" correlation matrix, this approach loses its universal characteristic.

Stressed balance sheet

Central balance sheet

In order to estimate quantities and , Monte-Carlo simulations are carried out. The following notation should be introduced at this point, in order to formalise the calculations performed according to the ALM method. Write: -(resp.

) the result of date for the simulation according to Q (resp. under ), -(resp. ) the discount factor of the date for the s simulation under Q (resp. under ).

The amounts of and are then estimated in the following manner:

and Comment: for the purpose of coherence with the definition of the Solvency II economic capital, the instantaneous shocks delivered to the various elementary risks are homogeneous in terms of extreme deviations (i.e. the 0.5% or 99.5% threshold depending on the "sense" of risk) according to the physical probability.

The elementary capitals are then aggregated with correlation matrices. Let us define: -the set of risks of module m, -the capital for the purpose of risk i, -the correlation coefficient that enables to aggregate the capitals of risks i and j belonging to module m, -the economic capital (designated as Solvency Capital Requirement) of module m, -M the set of modules, -the correlation coefficient that enables to aggregate the capitals of modules i and j, -the global economic capital (designated as Basic Solvency Capital Requirement) before operational risks and adjustments.

A QIS type aggregation is based on two main stages:

-An intra-modular aggregation: for each risk module m, the economic capital SCR m is calculated in the following manner :

-An inter-modular aggregation: the BSCR global capital is obtained by aggregating the capitals of the different modules.

Hereunder is the mapping that was chosen for the calculation of the economic capital QIS 4: Comment: in a "standard formula" approach, the calculations are often carried out at the initial date. Therefore, the economic capital does not rest on the distribution of equity at the end of the first year but rather on the elementary capitals determined at t=0.

On the other hand, an internal model that performs NS projections (Nested Simulations) enables to calculate the economic capital by complying with all the Solvency II criteria.

The Nested Simulations (NS) method

As we have seen above, the Solvency II economic capital is described in relation to the 0.5% percentile of the distribution of equity at the end of the first year and of the amount of equity at the start date. The link between these various elements is provided by the following relationship:

There are generally no operational issues in the determination of the amount; all that is needed to obtain this quantity is an ALM model that enables to carry out "market consistent" calculations at t=0. However, it is more delicate to obtain the distribution of the variable, and the calculation of the equity at t=1 is required, conditional on the hazards of the "real-world". The "Nested simulations" technique (NS) enables to address this problematic. To this date, this application is one of the most compliant methods with the Solvency II criteria for annuity products. Devineau and Loisel (2009) offer a detailed description.

This method consists in carrying out, through an internal model, "real-world" simulations on the first period (called primary simulations) and launching, at the end of each one of these simulations, a set of new simulations (called secondary simulations), in order to determine the distribution of the equity of the company at . The secondary simulations have to be "market consistent"; in most cases these are risk-neutral simulations.

Intra-modular aggregation

Inter-modular aggregation

Bottom-up aggregation

In order to formalise the calculations carried out in a NS approach, let us define the profit of the date for the primary simulation, , and for the secondary simulation the result of the first period for the primary simulation , -the discount factor of the date for the primary simulation , and for the secondary simulation , -the discount factor of the first period for the primary simulation , -the information of the first year contained in the primary simulation , -the equity at the end of the first period for the primary simulation , -the fair value of liabilities at the end of the first period for the primary simulation , -the market value of the assets at the end of the first period for the primary simulation .

This application may be seen in the following diagram: The equity at t=1, for the primary simulation p, satisfies:

For the calculation of , the following estimator is considered:

Balance sheet at t=1 -simulation i Balance sheet at t=1 -simulation P

Simulation i

Simulation P

Simulation 1

E 1 1 L 1 1 t = 0 t =1
Secondary simulations "market consistent" Primary simulations "real world"

A 1 i E 1 i L 1 i
Balance sheet at t=1 -simulation 1

A 1 1 A 1 P E 1 P L 1 P … … Balance sheet at t=0 A 0 E 0 L 0

Balance sheet at t=1 -simulation i

Balance sheet at t=1 -simulation P

The determination of the , quantity is generally based on the estimator. In other words, the "worst value" of the sample is taken as estimator of

The economic capital is then evaluated with the estimator: .

Formalising the "standard formula" and "NS" approaches

In this section, we propose a formalisation of the "standard formula" and NS approaches. First we shall introduce the notion of risk factors, which we associate with "standard formula" shocks and with the primary simulations of a NS projection. Then we shall adapt the definition of the economic capital calculation so as to return to an analysis over a single period, which enables to compare the results of the "standard formula" and those of the internal model. Finally, we shall establish the theoretical framework that legitimises the marginal and global capitals obtained with the "standard formula" method. The partial internal models presented herein are of the same type as those used by companies. We are aware of the limits of these models. It would be a good idea to perfect them, but that is not the object of this paper: our aim is to study the risk aggregation issues in partial internal models typically used by insurance companies.

Risk factors

Risk factors are elements that enable to summarise the intensity of the risk for each primary simulation in an NS projection. For example, let us suppose that the stock price is modelled according to a geometric Brownian motion; in this case, the risk factor that one can consider is that of an increase of the Brownian motion of the diffusion over the period in question. Very low values for these increases correspond to cases where the stock price may undergo very strong downward shocks (adverse situations in terms of solvency).

It is possible to extract the risk factors from a table of economic scenarios for the first period by specifying an underlying model for each risk and by evaluating the parameters of each model. We shall describe this approach as an "a posteriori determination method"3 .

In the example that we offer as part of the fourth section "Application: comparison of the standard formula and NS approaches", we follow an "a posteriori" approach based on the first year "real-world" table used for NS projections.

From now on in this Section, write:

the stock price at time t, -a random variable distributed according to Normal-Inverse Gaussian distribution , -a standard normal random variable, -the price at of a zero-coupon bond with maturity , -the real-world return of the zero-coupon bond with maturity , -the real-world volatility of the zero-coupon bond with maturity , -the Pearson's correlation coefficient of variables and .

We shall suppose that the evolution of the value of stock price and of the price of zero-coupon bonds in a "real-world" environment for the first year is described by

(1) and

(2)

Relation (1) corresponds to a modelling of the stock price according to an exponential NIG-Levy process. For a detailed description of this type of model, see [START_REF] Papapantoleon | An introduction to Levy processes with applications in finance[END_REF]. Relation ( 2) is derived from a linear volatility HJM (Heath-Jarrow-Morton) type model4 .

Calibration of the parameters Let:

be the stock price at date 1 in primary simulation , -be the price at of a zero-coupon bond with maturity T in simulation .

The interest rate parameters are evaluated from the economic scenarios' table of the first period.

In order to estimate the parameters of the stock price model, we present hereunder a reminder of the properties of a distribution. With we obtain:

---

12

and where (resp.

) represents the skewness coefficient (resp. Kurtosis excess coefficient) of the distribution.

Let

(resp. ) be the empirical estimator of the expected value (resp. the variance, the skewness, the excess of kurtosis excess) calculated for the sample.

The density of is expressed as follows:

where K 1 is a Bessel function of the third kind with parameter 1.

First, an estimation of the moments of parameters α,β,δ,μ is to be carried out by minimisation of the criteria .

We shall then determine the estimator of maximum likelihood for α,β,δ,μ by initialising the optimization algorithm with the moments' estimator obtained above.

Extraction of stock and zero-coupon bond related risk factors

For each primary simulation p, we shall establish the pair of centred and reduced random events, using the estimators presented above: and

The global and marginal NS projections

The NS method described above enables us to determine the global economic capital of the company.

However, in order to compare the NS and "standard formula" approaches, it might be useful to know, in addition to the global capitals, the value of the elementary capitals. This will enable to determine if the differences noted between the two methods are due to elementary capitals or to the aggregation method (or both).

Definitions: -We shall use the term marginal scenarios for risk R to describe a set of primary simulations, for which all the hazards are cancelled out, except for the hazards pertaining to R.

-

We shall use the term marginal NS in terms of risk R to describe any NS projection for which the primary scenarios are the marginal scenarios of risk R.

It is thus possible to determine the 0.5% level percentile of the equity distribution at t=1 conditional on risk R, by performing a marginal NS. Where is the estimator of the said percentile. It is then easy to obtain the marginal economic capital in terms of risk R from the following relation:

"Standard formula" vs internal model

The results of the standard formula and the internal model can be analysed on two levels: -Marginal level: comparison of the "standard formula" capital determined by stress test and the capital calculated according a marginal NS, -Global level: in the case where the marginal capitals obtained with the "standard formula" are very close or identical to those obtained with the internal model, comparison of the "standard formula" aggregation method and the NS method.

Hereunder is a recall of the diagram showing the marginal capital calculation in terms of R using the standard formula: Hereunder we also present a figure showing the calculation of the capital in terms of risk R using a marginal NS:

Where the primary simulation p is the simulation associated with the 0.5% level percentile of the variable that represents the distribution of equity at t=1, conditional only on risk R.

Two fundamental differences are observed in terms of marginal capitals between the "standard formula" and internal model approaches: -Calculation timing: the "standard formula" approach consists in comparing the value of the equity before and after the shock at t=0, whereas the calculation using the marginal NS is based on the discounted percentile of the equity at then end of the first period. -

The "standard formula" method uses a valorisation after shock (notion of percentile on the R risk factor), whereas the "Marginal NS" method rests on marginal simulations of equity (notion of percentile on the distribution of equity).

In order to compare the results of the "internal model" and those obtained with the single period "standard formula" approach, we shall slightly amend the latter by modifying our definition of economic capital:

-We shall then place ourselves in a single period context and we shall describe the following value as economic capital:

where represents the value of equity at , when all the hazards of the first period have been cancelled out. This relation enables to define the global capital and the marginal capital, the calculation of which can be carried out using a "NS (global or marginal)" method.

-Rather than performing an instantaneous stress test for the determination of the marginal capital in terms of risk R with the standard formula, we shall apply the corresponding shock to the first period by cancelling out all the other sources of randomness. The marginal capital will thus be the difference between the central value and the level of equity at , conditional on the "standard formula" shock (noted ):

The following diagram illustrates the change of shock timing in the "standard formula" method: On the basis of these adjustments, we shall propose in the following section a theoretical analysis of the "standard formula" approach.

4.

Theoretical analysis of the "standard formula" approach

In this section we describe the theoretical framework required to calculate the economic capital with the "standard formula" method.

Case of an elementary capital

In this Section, we shall assume that risk R may be entirely characterised by a risk factor that we shall denote as . Note that in a marginal NS projection in terms of R, the value of equity at t=1 is a function of the risk factor .

In other words, if designates the value of the risk factor in the primary situation p, then:

By taking α=0.5% or α=99.5% depending on the "sense" of risk R, then the calculation of the economic capital can be described as whereas an approach of the marginal NS type would give the following capital: . In the above expression, the percentile is considered on the "equity" function of the factor and not on the factor itself.

The analysis of the "standard formula" vs the internal model therefore consists in comparing elements and

In order to compare these elements, let us introduce the following H0 hypothesis:

H0 : the amount of equity at t=1 is a monotonic function of the risk factor .

According to H0, there are two scenarios. These are as follows:

A 1 R E 1 R L 1 R t=0 t=1 E 0 L 0 A 0 « standard formula » shock Balance sheet at t=0 Balance sheet at t=1
f is a decreasing function 5 :

f is an increasing function:

H0 is a very strong hypothesis. In some cases, equity may be penalised for both very low and very high values of the risk factor .

As an example of this, consider an annuity product with a significant guaranteed interest rate and with a dynamic lapses' rule. The equity will be degraded for both low and high values of the "interest rate" risk factor and its monotonic nature will not be verified. It is possible to relax the H0 hypothesis by considering the H0 bis hypothesis, which we shall designate as hypothesis of predominance.

H0 bis : hypothesis of predominance If one assumes that the "equity" function:

is decreasing (resp. increasing) beyond the q-percentile, where , say, (resp. before q-percentile with , say) of the risk factor, -and takes on higher values when the factor is below (resp. above) the q-percentile, Then:

The hypothesis of predominance consists in considering that the situations of bad solvency are explained by extreme values taken on by the risk factor "in any direction" (upwards or downwards). Statistical issues about tests of Hypothesis H0 bis are left for future research.

The monotonic hypothesis, also called the hypothesis of the predominance of the "equity" function in terms of the risk factor, justifies the fact that the percentile approach on equity is equivalent to the percentile approach on risk factor.

5 With Where R f( R ) q 99,5% ( R )

Analysis of the risk aggregation method

The technique of risk aggregation using a correlation matrix rests on a Markowitz mean-variance type approach. This method of aggregation is described, amongst other authors, by [START_REF] Saita | Risk Capital Aggregation: the Risk Manager's Perspective[END_REF] and by [START_REF] Rosenberg | A General Approach to Integrated Risk Management with Skewed, Fat-tailed Risks[END_REF]. The latter describe in their paper the case of the VaR of a portfolio containing three assets; the approach can be broadened to the calculation of the VaR of equity, depending on the different risk factors.

Aggregation techniques are often based on the notion of an economic capital that corresponds to the difference between the percentile and the expected value of a reference distribution (value of the portfolio, amount of losses, equity level,...). In our case, and using, for the purpose of simplifying the notations, E to describe the end of period equity, this definition leads to the following amount C of economic capital: , where is the expected value of variable E.

We shall use this hypothesis to demonstrate the "standard formula" aggregation method under certain hypotheses.

A pre-requirement for the application of this method is that the global variable (annuity of the asset portfolio, equity of the company) is a linear function in terms of drivers (annuities of the portfolio's assets, risk factors,...). This is indeed the hypothesis that will enable to calculate de variance of the global variable in relation to the variance and covariance of the drivers.

We shall then assume that the company is exposed to three risks, X, Y, Z and that the distribution of equity at t=1 is linear for each one of these factors:

with and Hereunder we shall use notation (resp.

) to describe the expected value (resp. the standard deviation) of a random variable M. The coefficient will describe the linear correlation (Pearson's coefficient) between the two variables M and N.

We shall assume in this Section that variables E, X, Y and Z have finite one order and two order moments. First, let us calculate the variance of E :

Let M be a random variable with expected value and standard deviation . We shall use to describe the reduced and centred variable 20 In this study, are considered only the stock and interest rate related risks. The tables of economic scenarios that are used were updated on December 31, 2008. Let's note that the implicit "stock" and "interest rate" volatility parameters have been assumed as being identical for each set of "risk-neutral" secondary simulations. However, one should note that it is possible, in a NS application, to jointly project the risk factors and implicit volatilities on the first period, and to reprocess the market consistent secondary tables in relation, inter alia, to simulated volatilities. This approach would make it possible to take the implicit volatility risk into account, as suggested by the CRO Forum ( 2009).

The company's economic balance sheet at t=0 is as follows:

Asset market value -A 0 360 754

Fair value of the liabilities -L 0 353 394

Equity -E 0 7 360

Table: economic balance sheet of the company at t=0 (in M€)

The investment strategy at time 0 is as follows :

5% Stock 15% Bonds 80%

Results

Risk factors

The extraction of risk factors according to the method described above leads to the following cloud:

-Each point in the cloud corresponds to a primary simulation. In the graph hereunder, we present descriptive statistics pertaining to stock and zero-coupon bonds (noted ZC) related risk factors. Pearson's correlation coefficient for stock factors and zero-coupon bonds' factors is the following: . These two distributions are centred and reduced but the stock distribution shows kurtosis and skewness coefficients that are significantly different from those found in a normal distribution. This is due to the fact that the log-increase of the stock price follows a Normal-Inverse Gaussian distribution. The graph hereunder shows that the variable takes on more extreme negative values than the variable.

Indeed, the distribution is asymmetrical with a heavy tail, whereas the follows a normal standard distribution.

Distribution of equity and first calculations

The distribution of equity as provided by NS stochastic projections is as follows: The NS method enables to estimate the economic capital using the estimator hereunder:

where is an estimator of

The following value is obtained:

0% 1% 2% 3% 4% 5% 6% 7%
where (resp.

) is the economic capital in terms of "stock" risks (resp. "interest rates"). By definition we have:

These two quantities can be estimated using marginal NS projections with the following estimators: , and .

Hereunder are the results of the estimation: 567.0 737.7

Table 2 : calculations of the NS marginal capitals

Analysis of the deviations

Comparison of stand-alone capitals

As has been demonstrated above, the comparison of "standard formula" and internal model approaches means to compare respectively the elements and , where f is the "equity" function and α=0.5% or α=99.5% depend on the sense of risk R.

Since the "stock" related risk is a decreasing risk, elements and are compared hereunder.

For the purpose of our research, the following equality is used: Therefore, the "standard formula" approach (equity governed by the risk factor percentile) and the internal model approach (percentile on the distribution of equity) coincide.

Hereunder, we present the profile of in relation to the value of the risk factor : As this is an increasing function, Hypothesis H0 is verified and the "standard formula" and internal model approaches are equivalent.

The graph hereunder presents the marginal equity in terms of the value of the risk factor : One notes that it is the very low values for that lead to the most adverse situations in terms of solvency. One should remember that a low value corresponds to the case where the price of zerocoupons falls and therefore the interest rates increase. This corresponds to the product under consideration as it is exposed to an increase of the interest rate (triggering of a wave of dynamic lapses).

For the purpose of this study, we must therefore compare the elements and . 24

We find and .

There is a 0.4% difference between these two amounts.

Although these two values are very close, they are not identical since the extraction of zero-coupon bonds related risk factors induces a specification error. The deformation of the price of zero-coupon bonds is summarised independently from the maturities by a single random variable, whereas the underlying model is generally far more complex.

However, one may observe that the value of marginal equity rises globally along with the risk factor.

The linear nature of the variable in terms of the "stock" risk factor is acceptable with regard to graph 10. However, graph 11 contradicts the linear nature of in terms of risk factor . The H1 hypothesis (assuming a linear relation between equity and risk factors) is therefore not verified and the aggregation of the "standard formula" is compromised in such a context.

Comparison of global capitals

In this Section we compare the result obtained by aggregation of marginal capitals with the result provided by the internal model. One should remember that the "standard formula" global capital is calculated in the following manner:

, where (resp. ) corresponds to the formula" marginal capital in terms of stock related risk (resp. zero-coupon bonds) and ρ represents the correlation between variables and .

The table hereunder enables to compare the "standard formula" capitals with the internal model capitals:

567.0 743.1 1028.8 1209.7 The difference between and is of 15%.

This difference is due to the that the hypotheses H1 and H2 are not respected, a fact that justifies the aggregation by standard formula. We have insisted above the fact that the "equity" function is not linear in terms of risk factors. The is therefore not verified. Furthermore, in this study, the distributions of reduced and centred factors and are different. This contradicts the H2 hypothesis that assumes that the vector is elliptic in nature.

In the following section, we propose an analysis of the differences due to aggregation methods.

Parametric form and analysis of differences

a.

Introduction of a parametric form

We have underlined above the non-linearity of the function that links "equity" to the zero-coupon bonds' factor. To strengthen our analysis, we shall first refine our choice of regression variables.

To achieve this, the following linear regression is considered:

, where U is a centred distribution that is independent from the pair of risk factors .

Following an estimation of the one obtains a R² equal to 99.6%. Hereunder we restore the QQ-plot " vs expected values of " that adequately translates the distributions: The Kolmogorov-Smirnov test does not reject the goodness of fit of the distributions by giving a P-value equal to 76%.

The goodness of fit enables us to obtain an amount of economic capital based on the variable that is very close to the amount:

Relative error 1209.7 1201.6 0.7% The use of a parametric form will enable us to specify more accurately the deformations that occur during a "standard formula" type aggregation.

It should be noted that it is also possible to compare economic capitals that result from marginal equity distributions the results obtained with the parametric form. To achieve this, the parametric marginal equity is considered 8 :

, where is the stock's real-world return.

The QQ-plots hereunder for (resp.

) vs (resp.

) show a very good fit for the distributions: (abscissa) vs (ordinate) 8 The stock (resp. zero-coupon bonds) parametric marginal equity is obtained by cancelling out the zerocoupon bond random factor (resp. by substituting the real-world return for the risk factor ) in the parametric form presented above. The goodness of fit is also measured by the P-value of the KS-test, equal to 39% (resp. 19%) for "Stock equity" ("resp. zero-coupon bonds equity").

Let (resp. ) be the "stock" marginal capital (resp. zero-coupon bonds) calculated with the variable (resp.

). One obtains:

and

The parametric approach provides an estimation of the marginal capitals that is very close to the results obtained with marginal NS projections:

Difference 567,0 555,9 2,0% Since the results of the NS projections are very close to those obtained with the parametric form, we shall use the latter as basis in the rest of this section. The parametric structure will indeed enable us to explain the deviations noted between "standard formula" economic capitals and "internal model" economic capitals, based on cross-terms of the or type. The variable specifically integrates the cross-terms ou .

We shall designate the economic capital in terms of cross-effects as . It is defined by the following relation:

We obtain a linear relation between the variable and the marginal distributions of vector :

If the distribution of vector belongs to the same family of elliptic distributions, the global capital (noted ) may be calculated as follows:

Where:

is the linear correlation between variables and , -is the linear correlation between variables and , -is the linear correlation between variables and .

Comment: a "standard formula" type method fails to capture the cross-terms or , since isolating the risks implies cancelling out one of the two factors ( ou ).

A "standard formula" method therefore consists in performing the following calculation:

This approach therefore underestimates the risk when:

Hereunder are the obtained results:

29

Stand-alone capitals: The difference between the capital and the capital obtained by aggregation of risks is significant (16.5%). This is due to the fact that the risk inherent to cross-terms is not integrated in the calculation. By taking this risk into account in the C 2 calculation based on , the difference is reduced from 16.5% to 6.3% in relation to the reference capital .

However, as the linear hypothesis is verified ( is a linear function of variables , and

), the residual error is explained by the non-elliptic nature of the distribution.

Consider the QQ-plot of standard distributions (i.e. centred and reduced) of and : The above graph reveals that the reduced and centred marginal distributions of vector do not follow identical distributions. The latter's elliptic nature is therefore contradicted.

The following diagram offers a summary of the deviations between capitals obtained with the standard formula and those calculated with the internal model:

Alternative aggregation method

The principle behind this method is to infer the results obtained with the parametric model9 in the risk aggregation method. We have observed above that the calculation of the global capital by aggregation in a non-linear situation lead to a different amount than that found with the "internal model"

. This is essentially due to the or cross-terms that are not taken into account (as they are cancelled out in succession) in the "standard formula" approach. The sole use of marginal capitals is therefore not sufficient to satisfactorily measure the effects of diversification. In order to capture this phenomenon, without necessarily using an entirely integrated NS internal model (relatively complex modelling), we propose a method that is easily implemented and based on an ALM projection tool that enables to carry out valorisations only at t=0.

Description of the method

We shall detail here the principle stages of the alternative method:

Stage 0 -determination of the marginal capitals: Calculation of the stand-alone capitals of each risk factor (by variation of the equity at t=0 due to an immediate shock on a risk factor).

Stage 1 -obtaining an equity distribution:

Step 1 : establishment of risk factors' tuples (stock, interest rate, mortality,...) These tuples are not necessarily vectors created from simulations and they can be established "manually". Each tuple represents a deformation of the initial conditions.

Step 2: calculation of the amounts of the equity in relation to each tuple, using the projection model at t=0.

Step 3: calibration of a parametric form of the "equity" variable on the previous tuples.

Step 4: simulation of the risk factors (modelling of marginal distributions and of the copula that links them together).

Step 5: obtaining the equity "distribution" using the previous simulations and the parametric form calibrated in Step 3.

Stage 2 -adjustment of the correlations that reveal the "non-linear" diversification: Consider three risks, X, Y and Z to describe this point. The capital calculated on the basis of the distribution in step 5 is noted and the elementary capitals calculated from the parametric form (by cancelling out all the other risks) are noted The principle consists in calculating for each primary simulation the norm 11 that is associated with the underlying risk factors and then performing NS projections in a decreasing order until reaching the stability of the worst values of equity.

The NS accelerator converges after 300 primary simulations on the portfolio under consideration. In this section, we have taken the parametric structure introduced above and calibrated it on the basis of the 300 pairs of factors on the biggest norms. This enables to adjust the parametric form on the extreme percentiles of the equity distribution, as the calculation of the economic capital rests on these elements.

Hereunder is the point cloud used in the calibration process: After having estimated the coefficients in a parametric form, we determined its value for each of the pairs . Using the parametric distribution of equity, we then calculated the capital:

. We determined the parametric marginal capitals in the same manner: 555.7 729.5 Here is the "standard formula" capital, calculated with an adjustment factor that enables to integrate the non-linear diversification.

One observes that the difference between and capitals is only of 0.6% and that the differences between marginal capitals are inferior to 2%. By using in order to aggregate the standalone capital due to "standard formula" shocks, we obtain a global capital that is relatively close to the capital determined by NS projections (deviation of 2.8%).

Limits and points of attention

In some cases the alternative aggregation method can lead to disappointing results. Depending on the complexity of the modelled products, it can become difficult to adjust a parametric form to the "equity" function. For the purpose of illustrating this point, we carried out an additional study of an annuity product with a revalorisation of the guarantees indexed on inflation. This product was used in a projection with an internal model fed with economic scenarios calibrated as of the 31/12/2008. For this study, in addition to the risks and interest rates, we also factored in the inflation risk.

We describe as the inflation risk factor retrieved from the economic table according to an application similar to that used for the other risk factors. Consider the following profile of parametric form:

We estimated the coefficients of this function with the least squares method on over 500 simulations of the biggest standards12 and we then determined its value for each pair . The parametric equity distribution provided the following capital:

We obtained the following parametric marginal capitals:

559.8 149.9 Here, the difference between and capitals is 7.7%. This situation results from a bad match between the parametric distribution of equity and the distribution obtained with the NS calculation, as shown in the QQ-plot hereunder: The use of the determined with the imperfectly adjusted parametric form leads to a CSF* capital that is significantly lower than the reference capital (7.5% difference). In order to improve this result, the choice of regressors adapted to this type of product should be refined.

Conclusion

In this paper, we have presented a formalisation of the "standard formula method" and of the NS approach. Having established a theoretic context for the application of the "standard formula" method, we have demonstrated that the internal models used by companies do not generally guarantee the validity of the hypotheses required for this type of aggregation. Indeed, even if the profile of the equity variable in relation to risk factors leads to marginal capital values that are very close, and even similar, for these two methods, the levels of the global capital may differ greatly. We have shown that the aggregation error committed by the standard formula is essentially due to two phenomena:

the level of equity is not adjusted in terms of underlying risk factors, the "standard formula" method does not take into account the "cross-effects" of the different risks that are being considered.

To address this issue, we have developed an alternative technique of aggregation that uses very few simulations to satisfactorily capture the main part of the diversification among risks. This method aims to adjust the correlation coefficients, so as to obtain "standard formula" results and internal models that are as close as possible, and to explain the deviations. The quality of the adjustment depends in theory on the convergence rate of the McLaurin expansion series of the equity variable for a compact and convex set that includes all the values of risk factors that lead to net situations included within the best estimate and a percentile at a level greater than 99.5%. The analysis of this conversion rate and the associated estimation problems are to be analysed in future studies. We would also like to add that studies concerning the integration of other risks, such as mortality are currently under way and are to be published in the future. Finally, dynamic correlation models incorporating correlation crises (see [START_REF] Biard | Impact of correlation crises in risk theory: asymptotics of finite-time ruin probabilities for heavy-tailed claim amounts when some independence and stationarity assumptions are relaxed[END_REF][START_REF] Fisher | On some key research issues in Enterprise Risk Management related to economic capital and diversification effect at group level[END_REF] could be introduced to better capture diversification effect on longer time horizons.

Figure 1 :

 1 Figure 1 : calculation of the elementary capital in terms of risk R with the "standard formula" method.

Figure 2 :

 2 Figure 2 : mapping of the risks of the QIS 4

Figure 3 :

 3 Figure 3 : obtaining the distribution of equity with the NS method.

Figure 4 :

 4 Figure 4 : calculation of the elementary capital in terms of risk R with the "standard formula" method.

Figure 5 :

 5 Figure 5 : calculation of the NS marginal capital relating to risk R.

Figure 6 :

 6 Figure 6 : adapting of the shock timing in the "standard formula" method.

Figure 7 :

 7 Figure 7 : profile of the "equity" function according to the hypothesis of predominance.

Figure

  Figure 8 : risk factor pairs relating to stock (abscissa) and zerocoupon bonds (ordinate)

Figure

  Figure 9 : distribution of the variable (in M€)

Figure 10 :

 10 Figure 10 : value of in relation to the level of risk factor

Figure 11 :

 11 Figure 11 : Value of in relation to the level of risk factor

Figure

  Figure 12 : QQ-plot (abscissa) vs (ordinate)

Figure 13 :

 13 Figure 13 : QQ-plot (abscissa) vs (ordinate)

Figure

  Figure 14 : QQ-plot (abscissa) vs (ordinate)

Figure 15 :

 15 Figure 15 : QQ-plot of standard distributions of and

Figure 16 :

 16 Figure 16 : summary of the differences between "standard formula" capitals and internal model capitals

Figure 17 :

 17 Figure 17 : sample of the calibration process

Figure

  Figure 18 : QQ-plot (abscissa) vs (ordinate)

Table : distribution of the assets at market value at t=0

 :

Table 1 : statistical indicators of samples et

 1

Table 3 : of "standard formula" capitals and internal model capitals

 3

Table 4 : comparison of the NS capital and the capital obtained with the parametric form

 4

	8 200
	7 700
	7 200
	6 700
	6 200
	5 700
	5 700	6 200	6 700	7 200	7 700	8 200
	with	.

Table 5 : comparison of "NS" and "parametric" stock marginal capitals

 5

	Difference

Table 6 : comparison of "NS" and "parametric" zero-coupon bonds' marginal capitals

 6

Table 7 : marginal capitals associated to variables and

 7

	555.9	723.6	227.6
	Correlation matrix:
	1	21.5%	40.2%
	21.5%	1	32.5%
	40.2%	32.5%	1

Table 8 : correlation matrix of vector

 8

	Capital aggregated using the previous correlations
	Capital CSF « standard formula » on
	1002.9
	Capital on
	1225.4
	1201.6

Table 9 : capitals associated with risks and

 9

Table 10 : calculations of "parametric" marginal capitals

 10 The following table lists the results that were obtained:

	Finally, the following relation:
	11 The norm of a	pair corresponds to	, where is Pearson's coefficient of et

Table 11 : adjusted comparison of "standard formula" capitals and NS capitals

 11

Table 12 : calculations of "parametric" marginal capitals

 12 These values enabled us to calculate the adjustment factor: The following table lists the results that were obtained:

	Difference

Table 13 : adjusted comparison of "standard formula" capitals and NS capitals

 13

A combination of these methods may be envisaged in the case of partial internal models.

When the company has a precise knowledge of the underlying risks' modelling and simulates its own trajectories, it is sufficient to export all the simulated hazards when the primary trajectories are generated. Amongst other things, this enables to realise the increase of Brownian motions of the diffusions (interest rate, stock,...). In this case, the factors are known before the modelling.

See Devineau et Loisel (2009).

Gaussian and multivariate Student distributions are well known examples of elliptic distributions. For a detailed description of these distributions, see Appendix 1.

The linear correlation is not invariant by increasing transformations, contrary to a Kendall tau rank correlation coefficient.

On the basis of a calibration that requires few observations (see hereunder).

In some cases, they can be greater than 1 in absolute value.

The number of observations was increased to strengthen the estimation. This parametric form uses more regressors than in the case presented above.

Acknowledgment:

The authors acknowledge partial funding of this work by ANR project ANR-08-BLAN-0314-01 and by Milliman Paris.

We obtain the following relation: Consequentially, by using the expression of the variance of E in relation to the variance and correlation coefficient of each one of the 3 drivers X, Y and Z, one obtains:

In the case of an extreme percentile (α=0.5%), the value of the normalised distribution's percentile is therefore negative:

In Appendix 2 we recall that when the random vector is elliptic 6 , one obtains the following result: which leads to the C capital hereunder: Where (resp. , ) corresponds to the economic capital in terms of risk X (resp. Y, Z), and is the sign of .

In the event of all the coefficients all having the same sign, the QIS aggregation relation is found.

Comment: it is always possible to return to risk factor coefficients that have the same sign, even if this entails considering the opposites of the risk factors. However, in this instance, the correlations change sign.

It should be reminded that the establishment of this relation required the hypotheses hereunder.

H1

: the E variable is a linear function of variables X, Y and Z, H2 : the vector follows an elliptic distribution (e.g. normal or Student distribution).

Comments: -The H1 hypothesis ensures the standard nature of the correlation coefficient. Indeed, if the "equity" function is not linear in terms of risk factors, the linear correlations of the marginal distributions of equity are, generally speaking, different from those of the factors 7 . These parameters are no longer "market" values since they become "company" values (and therefore the "standard formula" approach loses its universal nature).

-

The H2 hypothesis imposes a constraint on both the marginal distributions and the copula that links them. In other words, all marginal distributions must be identical and belong to the same family as the copula. In practice, this means considering the two most standard cases: o marginal distributions and Gaussian copulas o marginal distributions and Student copulas

Application: comparing the "standard formula" and "NS" approaches

In this Section we shall present, for a savings type portfolio, a comparison of economic capitals obtained, on one hand with the "standard formula", and on the other with the internal model. To begin with, we shall restore the results obtained from global and marginal NS projections, and we shall compare these to aggregated and elementary capitals obtained with the "standard formula". We shall then propose a deviations' analysis that will enable to explain in large part the noted differences.

Description of the portfolio and of the model

The portfolio that we consider in this study is a savings' portfolio with no guaranteed interest rate. We have projected this portfolio using an internal model that performs ALM stochastic projections and the calculation of equity after one year. This projection tool enables the modelling of the profit sharing mechanism, as well as the modelling of behaviours in terms of dynamic lapses of the insured parties when the interest rates handed out by the company are deemed insufficient in relation to the reference interest rate offered by the competitors. -The coefficients of the matrix enable to "reproduce" the effects of the diversification that are due to the parametric form but they do not correspond, generally speaking, to the correlation coefficients. These adjustment factors are used in order to integrate the marginal capitals by using the standard formula, but in no case are these Pearson's correlation coefficients of underlying variables 10 .

Implementing the alternative method

In the section concerning the analysis of deviations, the calibration of the function linking equity and risk factors is based on all of the 5000 primary simulations. A comprehensive NS projection was therefore carried out to calibrate this function. However, it is often operationally difficult to carry out such a large number of simulations as these imply significant computation times. [START_REF] Derien | Construction d'un algorithme d'accélération de la méthode des « simulations dans les simulations » pour le calcul du capital économique Solvabilité II[END_REF] have developed an acceleration algorithm that enables to reduce the number of primary simulations in a NS calculation.

Appendix 1: Elliptic distributions

The family of elliptic distributions is a category of multivariate distributions that share the main properties of normal distributions while enabling to model extreme dependence and other forms of non Gaussian dependence. For a detailed presentation of these distributions, see [START_REF] Embrechts | Modelling Dependence with Copulas and Applications to Risk Management[END_REF].

Definition

If X is a random vector with a dimension n. If is a positive-definite matrix of dimensions for which the characteristic function of is a function of quadratic form , i.e. , then X is said to be an elliptic distribution.

The notation is then

The function is called the characteristic generator of the distribution.

Characterisation theorem

One obtains with only if there is a random variable R≥0 independent from the random vector U of dimension k uniformly distributed on the unit sphere and an A matrix of dimension with for which :

Consequence : in dimension 1, the family of elliptic distributions corresponds exactly to that of symmetrical distributions.

Theorem

Appendix 2: Proof of the aggregation formula

In this section we prove the aggregation formula presented in part 3.4.2.

Proposition : assuming that a random vector is elliptic and that the equity distribution is linear according to X, Y et Z, i.e. in the form where Then:

Proof

Under the hypotheses stated in the proposition, the standard distributions of the variables X, Y, Z and E are identical 13 .

It is easily demonstrated that for 14 any :

Let us examine the calculation of marginal capitals. Without loss of generality, let us consider the economic capital . There is the relation: As the X factor is centred, one obtains: Therefore: if : if :

Let Similarly, one obtains :

And,

Consider the expression presented in part 3.4.2 :

13 Refer to the previous appendix for a description of the properties of elliptic distributions. 14 It might be useful to remember that an elliptic random variable is symmetrical.

With the results presented above, one obtains:

. Therefore:


Arnaud Casteigts

Timothée Corsini

Writika Sarkar

Simple, strict, propre, happy : accessibilité et expressivité des graphes temporels †

Les graphes temporels sont des objets qui modélisent les réseaux dynamiques. L'accessibilité dans ces graphes se base sur la notion de chemin temporel (ou trajet). Contrairement au contexte des graphes statiques, la relation correspondante n'est ni symétrique, ni transitive, ce qui rend inopérant de nombreuses techniques connues. Pour ajouter à la confusion, les graphes temporels s'avèrent sensibles à de subtiles variations dans leur définition, telles que le fait que les trajets soient stricts ou non (c.à.d. peut-on emprunter deux arêtes consécutives à la même date ?), que le graphe soit propre ou non (les sommets peuvent-ils être incident à plus d'une arête à une même date ?), ou encore que le graphe soit simple ou non (une même arête peut-elle être présente à plusieurs dates ?).

Dans cet article, nous étudions l'impact de ces trois paramètres sur l'accessibilité. Nos résultats révèlent un paysage complexe, dans lequel différentes combinaisons de ces paramètres induisent différents niveaux d'expressivité en termes d'accessibilité. En particulier, nous montrons des séparations entre l'expressivité de certaines combinaisons (résultats négatifs) et des transformations préservant l'accessibilité entre d'autres combinaisons (résultats positifs). Ces résultats permettent de clarifier l'impact de ces paramètres et nous pensons qu'ils peuvent être utilisés pour comprendre la perte de généralité occasionnée (ou non) par différents choix d'hypothèses.

Mots-clefs : graphes temporels, expressivité, accessibilité, fermeture transitive

Définitions

Les graphes temporels se sont imposés ces dernières années pour modéliser de nombreux types de réseaux dynamiques, notamment dans le domaine des télécommunications. Ces objets sont connus sous différents noms, avec des nuances qui varient d'une communauté à l'autre. On parle ainsi de graphes dynamiques, de graphes évolutifs, de graphes variant dans le temps ou de flots de liens. Dans cet article, nous utilisons une version rudimentaire où un graphe temporel est défini par un graphe simple muni d'un étiquetage sur les arêtes, c'est à dire G = (V, E, λ), où V est un ensemble fini de sommets, E ⊆ V × V est un ensemble fini d'arêtes (non-orientées) et λ : E → 2 N associe à chaque arête un ensemble (non vide) d'entiers qui correspond aux temps où cette arête est présente. Étant donné un tel graphe G = (V, E, λ), le graphe G = (V, E) est appelé empreinte de G. Les graphes G t = (V, E t ) où E t = {e ∈ E | t ∈ λ(e)} sont appelés snapshots de G au temps t. L'empreinte et les snapshots sont des graphes statiques. Un couple (e, t) tel que t ∈ λ(e) est appelé contact. Enfin, la durée de vie de G correspond au temps maximum utilisé par G. La durée de vie sera toujours finie dans cet article, bien qu'elle puisse en général être infinie.

Un trajet (ou chemin temporel) est une suite de contacts ⟨(e i , t i )⟩ telle que ⟨e i ⟩ est un chemin dans l'empreinte de G et ⟨t i ⟩ est une suite croissante d'entiers (stricte ou non, nous distinguerons les deux plus tard). Les trajets définissent naturellement une relation d'accessibilité entre les sommets, que l'on peut représenter par un graphe statique orienté closure(G) = (V, E c ) où (u, v) ∈ E c si et seulement si u peut joindre v par un trajet. G est temporellement connexe si tous les sommets peuvent se joindre deux à deux.

1.1 Simple, Strict, Propre, Happy ? Plusieurs restrictions peuvent s'appliquer aux définitions précédentes. Dans la litérature, trois restrictions sont fréquemment utilisées :

• Les trajets doivent-ils être stricts ? Autrement dit, pour un trajet ⟨(e i , t i )⟩, faut-il que la suite ⟨t i ⟩ soit strictement croissante ou seulement croissante ? • Le graphe est-il propre ? À savoir que si deux arêtes e et e ′ sont incidentes, on a λ(e) ∩ λ(e ′ ) = ∅.

• Le graphe est-il simple ? À savoir que chaque arête de E n'est présente qu'un seul temps.

Certaines combinaisons de ces paramètres sont plus générales que d'autres. Cependant, elles ne sont pas toutes comparables, ce qui rend difficile la comparaison et le transfert de résultats dans le domaine des graphes temporels. Notre travail tente d'éclairer ces différences. Pour commencer, toutes les combinaisons ne sont pas distinctes. Par exemple, si l'on considère les graphes propres, il n'y a aucune conséquence à imposer des trajets stricts (ils sont stricts de toute façon), contrairement graphes non-propres où cette distinction est cruciale. En fait, nous pouvons distinguer six configurations, illustrées à la Figure 1 : • Non-propre, non-simple, strict (1)

• Non-propre, non-simple, non-strict (2)

• Non-propre, simple, strict (4)

• Non-propre, simple, non-strict (5)

• Propre, non-simple (3)

• Happy (= propre et simple) ( 6)

Happy (6) Simple (4) (5) Propre (3) Strict (1)
(2) Non-strict Une première subtilité apparaît : le fait d'être propre (ou non) et simple (ou non) est une propriété du graphe temporel, tandis que le fait d'être strict (ou non) est une propriété des trajets permis dans un tel graphe. Ainsi, les deux premiers choix peuvent être assimilés à des familles de graphes temporels, avec par exemple les graphes propres vus comme un cas particulier (sous-ensemble) des graphes non-propres, et similairement pour les graphes simples. Les options strict ou non-strict, quant à elles, sont plutôt vues comme une dimension supplémentaire venant compléter le choix d'une famille de graphes.

Expressivité en termes d'accessibilité

Nous nous intéressons à comparer l'expressivité des six configurations ci-dessus en fonction de l'accessibilité qu'elles permettent d'exprimer. Dans cette version courte du papier, nous dirons que deux graphes temporels ont la même accessibilité si la propriété suivante est satisfaite.

Définition 1 (Équivalence d'accessibilité). Deux graphes temporels G 1 et G 2 sont équivalents en termes d'accessibilité si closure(G 1 ) ≃ closure(G 2 ) (leurs graphes d'accessibilité sont isomorphes).

Étant donné deux configurations

C 1 et C 2 , on dira que C 1 ⪯ C 2 si et seulement si pour tout graphe temporel G interprété dans C 1 , il existe un graphe temporel H interprété dans C 2 tel que G et H ont la même accessibilité. Si cette inclusion est stricte, on notera C 1 ≺ C 2 . Si C 1 ⪯ C 2 et C 2 ⪯ C 1 ,
on dira que les deux configurations ont la même expressivité, noté C 1 ≈ C 2 . On pourrait déjà lister un certain nombre de relations entre configurations qui sont trivialement vraies, comme le fait que, tout autre paramètre étant égal, une configuration non-propre est au moins aussi expressive qu'une configuration propre (par inclusion). Mettant de côté ce type de relations, nous allons présenter quelques séparations entre configurations, ainsi que quelques transformations d'une configuration à une autre.

Pour séparer deux configurations, il suffit de trouver un graphe temporel dont l'accessibilité, interprétée dans la première configuration, ne peut être réalisée par aucun graphe dans la seconde. Voici les quatre séparations que nous avons obtenues dans [CCS22] :

1. "simple & strict" ne peut pas exprimer toutes les accessibilités de "non-simple & strict" ; 2. "non-strict" ne peut pas exprimer toutes les accessibilités de "simple & strict" ; 3. "simple & non-strict" ne peut pas exprimer toutes les accessibilités de "non-strict" ; dans la configuration "strict" ou "non-strict", constitue donc un exemple de graphe de la configuration "non-strict" dont l'accessibilité closure(H) ne peut être réalisée par aucun graphe dans "simple & nonstrict".

3 Transformations entre configurations À l'inverse des séparations, il est parfois possible de concevoir des transformations canoniques entre configurations qui préservent l'accessibilité, montrant ainsi qu'une configuration est "au moins aussi" expressive qu'une autre. Nous proposons plusieurs transformations dans [CCS22]. La plus simple est la technique de saturation, qui prend en entrée un graphe quelconque d'une configuration "non-strict" et qui produit en sortie un graphe ayant la même accessibilité lorsque seuls les trajets stricts sont autorisés. Cette transformation démontre que "strict" est au moins aussi expressif que "non-strict", ce qui combiné à l'une des séparations précédentes, implique que "strict" est strictement plus expressif que "non-strict". Une autre transformation est la technique de dilatation (dilation, en anglais), qui consiste à transformer n'importe quel graphe dans "non-strict" vers un graphe équivalent dans "propre". Si l'on réalise que "propre" est un cas particulier de "non-strict" (de même que de "strict", mais cela ne nous intéresse pas ici), il en résulte que les configurations "propre" et "non-strict" ont exactement la même expressivité, ce qui est inattendu. La troisième transformation, de portée différente, permet de reproduire dans une certaine mesure l'accessibilité de n'importe quel graphe temporel vers la configuration la moins expressive -celle des graphes "happy". Étant donné un graphe temporel G d'accessibilité closure(G), l'idée consiste à construire un graphe H plus grand que G, dans lequel un sous-ensemble bien défini de sommets auront, entre eux, exactement la même accessibilité que les sommets de G (on parle d'accessibilité induite). Techniquement, la transformation repose sur un gadget temporel appelé sémaphore, qui s'inspire d'une réduction de NP-difficulté issue de [BF03]. Cette troisième transformation montre que les graphes "happy", bien qu'étant les moins expressifs, peuvent néanmoins capturer, de manière induite, l'expressivité de toutes les autres configurations.

Synthèse et questions ouvertes

Si l'on combine les séparations mentionnées plus haut et les deux premières transformations, ainsi que plusieurs inclusions triviales, nous obtenons un paysage complexe qui démontre que les trois paramètres considérés dans ce travail ont une incidence réelle sur l'expressivité d'un graphe temporel. L'ensemble de nos résultats est présenté à la Figure 3. Dans ce paysage, le statut de certaines relations reste à déterminer. Notamment :

Question 1. Est-ce que "simple & strict" contient l'expressivité de "non-strict" ?

Question 2. Sinon, est-ce que "simple & strict" contient l'expressivité de "simple & non-strict" ?

Vus globalement, ces résultats définissent un ordre partiel sur l'expressivité des six configurations, illustré à la Figure 4. Comme déjà évoqué, l'une des surprises de cette étude est que les graphes propres sont aussi expressifs que n'importe quel graphe où les trajets non-stricts sont autorisés, ce qui légitimise leur étude. Au delà de cette classification, une question intéressante serait de caractériser les familles de graphes orientés qui correspondent à ces configurations.

Happy

Références

FIGURE 1 :

 1 FIGURE 1 : Configurations obtenues en combinant les paramètres.

FIGURE 2 :

 2 FIGURE 2 : G un graphe simple et strict, H un graphe non-strict et leurs fermetures.

FIGURE 3 :

 3 FIGURE 3 : Synthèse des résultats de la version complète [CCS22].

FIGURE 4 :

 4 FIGURE 4 : Relation d'ordre entre les configurations de graphes temporels selon leur expressivité.

[

  BF03] Sandeep Bhadra and Afonso Ferreira. Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks. In International Conference on Ad-Hoc Networks and Wireless, pages 259-270. Springer, 2003. [CCS22] Arnaud Casteigts, Timothée Corsini, and Writika Sarkar. Simple, strict, proper, happy : A study of reachability in temporal graphs. In Stabilization, Safety, and Security of Distributed Systems : 24th International Symposium, SSS 2022, Clermont-Ferrand, France, November 15-17, 2022, Proceedings, pages 3-18. Springer, 2022. arXiv :2208.01720.

† La version complète de cet article a été présentée à SSS 2022 et est également disponible sur arXiv [CCS22]. Ce travail a été en partie financé par le projet ANR TEMPOGRAL (ANR-22-CE48-0001).