Vitting Andersen
email: jorgen-vitting.andersen@univ-paris1.fr

From Minority Games to $-Games

In this chapter we will first argue for the use of game theory/agent-based modeling, to go beyond the standard methods used in traditional approach of Finance. First will be introduced some very general thoughts of elements needed in a new framework for Finance. Then some few concrete examples of heterogeneous agent-based models will be introduced and several of their main results will be discussed. Finally applications and methods to real market data will be introduced, notably the idea of "decoupling" to explain the short-lasting synchronization of investors.

Rejecting the the main building block in financial models, the rational expectation hypothesis, as unrealistic, the undeniable question is then how can you do better? The lack of established and convincing alternatives, is probably one of the main reasons why macroeconomists keep on using rational expectations in their models, for the simply fear of the "wilderness" of alternatives. If not to use the sharply defined hypothesis of rational expectations, then what exactly to use?

1 CHAOS THEORY AND FINANCIAL MARKETS

One of the main issues with rational expectation theory is the assumption that all investors act alike, analyzing in a cool and pervasive manner the market by using all available information relevant for future cash flows of a given asset. This description sounds far from the reality, and is far from reality as probably most economists also would agree on. Let us instead for one moment take the extreme opposite view. Assume for a moment, in a thought experiment, that we knew all investors, their wealth, and their investment strategies independent of the conditions of the markets. Let us also assume that we were somehow able to classify all this huge amount of information into a fast supercomputer. Would we then be in place to understand and predict future market movements? This line of thinking goes back to the tradition from Pierre Simon de Laplace, a French scientist born in the 18th century, who in his book "A Philosophical Essay on Probabilities" (1814) wroteμ "We may regard the present state of the universe as the effect of the past and cause of the future.

An intellect which at any given moment knew all the forces that animate nature and the mutual positions of the beings that compose it, if this intellect was vast enough to submit the data to analysis, could condense into a single formula the movement of the greatest bodies of the

INTRODUCTION

It is probably not an exaggeration to say that the theory of rational expectations really is at the very core, hiding basically deep down in the framework of most theories used in Finance since the mid 1λ70's. The idea is very simple, very elegant, and with very deep implications.

Unfortunately it is also very unrealistic. This chapter aims to go beyond such a traditional view of Finance, but also beyond the more recent Behavioral Finance view, which as its starting point takes the case in individual investor psychology. Instead the attention and the main theme of this chapter will be on price formation in financial markets but seen as a sociological phenomenon.

For a background on the ideas presented here, see also [START_REF] Andersen | An Introductory to Quantitative Behavioral Finance[END_REF].

ABSTRACT

universe and that of the lightest atom; for such an intellect nothing could be uncertain and the future just like the past would be present before its eyes" One century later a compatriot of Laplace, Henri Poincaré, would however discover that having just the equations is not enough since we also need to know the initial conditions of a system in exact detail: even the slightest change in initial conditions and the same equations could give completely different results. With the invention of computers and the sufficient computing power they obtained in the 1λ70's, this point became possible to formalize further and now goes under the name "Chaos Theory". Most readers probably will recognize "Chaos Theory" from the meteorologist Edward Lorenz, who coined the phrase that the "flap of a butterfly's wings in Brazil sets off a tornado in Texas".

Let us then step back and reconsider the question posed two paragraphs above concerning the predictability of future market movements. We can then summarize the situation as following: according to rational expectation theory used in the traditional Finance view, financial market movements are random and consequently impossible to predict -full stop!... Laplace on the other hand opens up for the exact opposite scenario with everything in this universe described by determinism, from the movement at the smallest scale of an atom, up to the largest scale of a galaxy, and of course in between these two extremes, all other activity including the movement of prices in a stock market. Even though Laplace's considerations are more philosophical in nature than of practical relevance, the idea suggested is that everything ultimately could be understood deterministically if we just were able to grasp the right underlying variables governing all forces in nature and analyze the positions of beings composed of it. Poincaré agrees with the determinism in the equations, but points out that in practice understanding the world deterministically is forever beyond our reach since changing the initial conditions of the equations changes the outcome of the equations, and we will never be able to grasp the initial conditions of how our universe started out. This however has not held people back in trying to understanding market movements using chaos theory, assuming some underlying variables governing cycles of price formation in financial markets much like business cycles governing the economy. The goal in that case is to determine a so-called strange attractor, which dimensions give the number of relevant variables in question. The principle of a parsimonious description of a system in terms of some few underlying relevant variables is the hallmark of most theories coming from the field of Physics, and has proven successful when imported to other domains like e.g. Bio-Physics and Geo-Physics. It is probably fair to say that the jury is still out when it comes to the possibility of getting insight by describing financial markets or economic developments in terms of chaos theory. The complexity approach to be presented in the following, rather than looking for some few equations of relevant variables, stresses the impact that each constituent can have on a system. By treating each constituent of a system, complexity theory in a sense appears more "chaotic" compared to chaos theory which instead of considering all the constituents, only considers a few relevant variables of a given system. If we return to the question of price formation in a financial market, each constituent is someone who takes part in making the price by trading -be it a computer or a human. The question is then is how to find order in this seemingly "cacophony" of "voices" of the constituents?

2 COMPLEXITY THEORY AND THE "SYMPHONY" OF THE MARKET

In order to visualize the complexity models to be introduced in the following, let us for a moment try to make the analogy between the way that prices are formed in a financial market, and the creation of a symphony by an orchestra. One can think of each market participant as the "musician" in such an orchestra, playing different tunes (trading frequency and direction of trade) with different volume (amount of cash behind a trade). The "maestros" that the market participants watch would then be played by the central bankers worldwide. The question is then whether we are somehow able to decode the "symphony" of price movements played by such an orchestra?

Even though the analogy might sound a bit far-fetched, it does illustrate the collective behavior of a system where humans have to perform an act which depends on the outcome of what other people do. Just like different traders use different trading strategies, so do different musicians in an orchestra have different music sheets that they use in their act of playing. A music sheet tells the musician how to play, but he/she has to wait for the outcome of his/her colleagues to play the instrument in the right manner. Similarly for trading decisions from a trading strategy "played" by a trader. A trader never acts in complete isolation, but takes his/her decisions depending on the "tunes" played by the market. Trend following strategies depends on the momentum of the market whereas fundamental value strategies are used depending of the price level of the market, buying when the price has become under-valued and selling when the price has become overvalued. In addition anticipation of how future tunes will be played matters, because of new policy making by central bankers or new economic statistics.

The complex, but also fascinating, way the "market" symphony is created, becomes clearer when we consider its hierarchical structure. At the first level of the hierarchy, we can imagine each given stock and its price movements being played by a local orchestra of individual traders. This local tune (i.e. price movements of the stock) is not made in complete isolation, but depends (partly) on the how other local orchestras (other stocks) play their melodies. Going one level up, we can then consider the tune of a stock created by the aggregate action of traders, now itself as a created by a single instrument, but playing in a national orchestra composed of all stocks in an index. Adding up the contributions of the local orchestras creates what one could call a "national" hymn, illustrated by a given country's stock index. As discussed in [START_REF] Andersen | An Introductory to Quantitative Behavioral Finance[END_REF] the hierarchical structure does not stop at the level of a given country, but goes into a super-hierarchical structure where a global "symphony" is played by a worldwide orchestra of all nationalities. As illustrated by [START_REF] Andersen | Price-Quakes" Shaking the World's Stock Exchanges[END_REF], each national orchestra does not play its hymn in isolation, but have to wait for the outcome of the other orchestras in order to know how the play their national hymn properly.

AGENT-BASED MODELING: SEARCH FOR UNIVERSALITY CLASSES IN FINANCE?

Having discussed the picture where the diversity in human decision making, collectively somehow creates a "symphony" of price movements, the question is how one can formalize such scenery? One first step in this direction is to use agent-based models which are build, so to speak, to allow for diversity when it comes to decision making.

The concept of agent-based models goes back to the 1λ40's from ideas of John von Neumann and Stanislaw Ulam who were interested in self-replicating machines and came up with the idea of the cellular automata. Similar to cellular automata agent-based models cover a very broad range of models, mostly computational models, that simulates the actions and interactions of some set of autonomous entities called agents. With this description the link to complex systems should be clear. In the context of finance and economics the great advantage using agent-based models is that it gives a handle to introduce behavioral traits at the micro level of each agent, and then study how such traits and rules of interaction among the agents generate complex behavior at the system level.

Originating from the domain of Physics, several types of agent-based models have been proposed to describe the dynamics of pricing in financial markets. Typically these kinds of models consider a financial market as composed of agents that use strategies to buy/sell shares.

The decision of the strategies could e.g. be based on estimation of fundamental values and/or, in order to encompass technical analysis, based on the last price movements of the market. The agents are adaptive since they adapt to the price movements of the market choosing the most successful strategy at each time step. In this perspective such models offer a ground breaking view of financial markets since the agents are bounded rational with, in some cases, exact solutions obtained via techniques borrowed from physics.

Before we in the following sections go into the specifics of the different agent-based models, let us begin with a word of caution. It is easy to fall into the trap of considering narrowly each model as a complete description of a given financial market. Clearly no model will ever do the full task of explaining in all detail price dynamics of a financial market, just like no map ever can tell all details of a location. Still maps are useful to get oversight, and our claim in the following is similarly that we need models to guide us through the "wilderness" of the price dynamics of financial markets. We would rather emphasize a view in which the models serve as probes and handles used to get a successively better description of what one could call "generic" behavior of financial markets. "Generic" behavior could for example be the point of identifying certain moments where the markets are framed as will be elaborated on later in this chapter. Let us stress "realism" as the main advantage of the complexity models compared to the traditional rational expectation models. We know from psychology that people do not behave rational [START_REF] Kahneman | Thinking, fast and slow[END_REF]. Incorporating non-rationality via complexity models therefore appears as an appealing alternative to models based on the rational expectation hypothesis.

At the lowest level of description, a complexity model of a financial market could for example be:

"A financial market is a place where a number of actors trade, using different strategies".

Even though this statement does not say a lot, it is hard to dispute, and can serve as foundation to build on as will be explained in the next section. The fear of traditional economist is however that this will never bring us very far, since the next refinement in such a description can be taking in an infinite number of different directions.

Interestingly, Physics faced what at a first look appear to be somewhat similar concerns back in the 1950-70's. The question then was how much detail is really needed to describe a given system properly? This question is relevant also in the present context, since if a detailed description of the price dynamics of a financial market is needed with all its interwoven facets, then there will not be much hope to get insight on financial markets, using the rather simple models which we will introduce in the following sections. It is however notable that the problems encountered in Physics at that time, eventually led to the development of tools now used in different areas of Physics, and which go under the general name of "renormalization group theory". Back then there were concerns in the domain of particle physics (atomic physics) that in order to understand the interactions of the forces in nature one needed a detailed description of the forces described at a certain scale (distance). It turns out that e.g. an electron which looks like a singular solid object when looked upon from afar, looks differently as one zoom in, and go to smaller and smaller distances. As one decrease the distance (go to higher energies) an electron appears composed of self-similar copies of yet other electrons, positrons and photons, somewhat similar to a stock index isn't just a stock index but has its own life in terms of the stocks that constitutes it. Also the forces which acts between different stock indices appear different compared to the forces acting between the individual stocks.

The development of the renormalization group theory happened through successive contributions. First by Stueckelberg and Petermann (1953), followed by M. Gell-Mann and F. E. [START_REF] Gell-Mann | [END_REF] then R. Feynman, J. Schwinger and S.-I Tomonaga (who won the Nobel Prize in Physics in 1965 for their contribution) showed how details depending on a given scale were irrelevant. A deeper understanding of this problem came from a different branch of Physics, Condensed Matter Physics, [START_REF] Kadanoff | Scaling Laws for Ising Models Near Tc[END_REF], [START_REF] Wilson | The renormalization group: critical phenomena and the Kondo problem[END_REF], where the technique was used to understand the general nature of phase transitions. This led to yet another Nobel Prize in Physics, illustrating how important the technique has become in modern Physics.

The lesson from Physics then tell us that insight can be gained as one study how forces change when varying the typical scale of a phenomenon. The question is whether similar insight could be used in an understanding of how market "forces" change, when instead of looking at correlations between different stocks in an index, one goes to a different scale and consider the forces acting now between different stock indices, with currency and commodity indices adding additional complexity in such an understanding. In similar vein it would be interesting having a theoretical understanding of how market forces change as one change the time scale in question, relating events at the time scale of seconds and minutes to what happens at the hourly, daily and monthly time scale. We mention this partly because we find the use of an analogy to get insight on market forces by looking at what happens when changing the "scale" appealing, but more importantly because the renormalization group theory explains the concept of "universality" seen in physical systems. It turns out that phase transitions seen in e.g. magnetic systems, alloy materials, superfluid and superconducting transitions, despite their apparent different nature, have similar critical exponents, meaning their behavior near the phase transition are identical.

The phase transitions of these very different systems can therefore all be described by the same set of relevant variables, leaving out (as mentioned in the paragraph above) a detailed description for each system as irrelevant to understand the physics governing the phase transitions of the systems. It should be mentioned that the notion of universality classes extends also to systems that are out of equilibrium. In that case it has been shown how domain growth of e.g. growing crystals, or growth of domains of oxygen in high temperature superconductors, again are determined by some few relevant variables (like the dimension of the system, and whether the so-called order parameter is conserved or not). Given the success coming from renormalization group theory, physicists are therefore brought up looking for the relevant variables of a system knowing details ultimately should not matter. It is through such glasses that the models introduced in the next sections should be seen: as primitive models of financial markets, but despite their simplicity, meant as probes to search for what could be the equivalent of "relevant" variables in financial markets.

METHODOLOGY: DEFINING THE AGENT-BASED MODELS AND EXPLORING THEIR PROPERTIES

THE EL FAROL BAR GAME AND THE MINORITY GAME

The El Farol Bar Game was invented by the economist Brian Arthur (Arthur 1994) and first published in 1994. In the game N people have to decide independently each week whether to show up at their favorite bar which once a week have some very popular live folk music. The problem however is that the bar only has L < N/2 chairs. Now since each person will only be happy if seated, the people try to use the last weeks attendance to predict future attendance. If a person predicts that the number of people that will attend the bar is larger than L, that person will stay home. The relevant remark is to notice that the El Farol Game describes adaptive behavior since the audience in the bar uses past data to predict future attendance.

One reason to discuss this model is that it gives a clear example of a situation in which rational expectations theory cannot be used to solve the problem. Suppose a rational expectations prediction machine existed and that all the agents possessed a copy of it. If e.g. the machine predicted that a number larger than L would attend the bar, nobody would show up, thereby negating the prediction of the rational expectations prediction machine.

Inspired by the El Farol Bar Game the Minority Game (MG) was introduced in 1997 by Ye-Cheng Zhang and Damien Challet [START_REF] Damien | [END_REF]) as an agent-based model proposed to study market price dynamics. The model was introduced following a leading principle in physics, that in order to solve a complex problem one should first identify essential factors at the expense of trying to describe all aspects in detail. The MG therefore should be considered as a "minimal" model of a financial market.

Specifically the Minority Game is described by just three parameters:

• N -Number of a agents (market participants)

•

-"Memory" of agent i

• -Number of strategies available by agent i in the case where all agents use same memory ≡ m and same number of strategies ≡ s (to be assumed in the following). The MG has its name since inspired by the El Farol Bar Game the agents are rewarded whenever their decision is in the minority. We will explain this point in detail further below where we define the payoff function.

In order to quantify technical analysis the MG agents use lookup tables representing the last m directional moves of the market. Representing an up move of the market as a 1 and a down movement of the market as a 0, a strategy can be represented via look up tables of which an example for m = 3 is shown in the table below.

[

HERE TABLE 2.1]

A strategy therefore tells you what to do whatever was the market behavior in the past. If the market went down over the last three days, the strategy represented in table 2.1 tells you that now is a good moment to buy (000 → 1 in table 2.1). If instead the market went down over the last two days and then up today, the same strategy tells you that now is a good moment to sell

(001 → -1 in table 2.1).
Despite the apparent simplicity of the model, the complexity of it is revealed when you consider the total number of possible strategies. Representing just the up and down movements there are possible price histories when you look at the time period of the last m days. Since for each possible price history (i.e. for each entry on the left side of the table 2.1) a strategy gives a recommendation of what to do (i.e. buy: 1 or sell: -1) the total number of strategies S are given by S = . Even for relatively short time period of say 2 weeks, that is 10 trading days, S =

. This number exceeds . To grasp the magnitude of such a number, notice that the total number of elementary particles in the universe is "only" supposed to be around . So in a "toy" financial market where traders only needed to make decisions based on the directional moves of the market over the last two weeks, without taking into account their magnitude, they would have by far more choices than there are particles in the universe! If nothing else this little exercise shows that it is no wonder then that people gets overwhelmed in making decision choices of when to invest. (1,-1,-1, 1,-1,-1, 1,-1) respectively, and ⃗⃗⃗⃗ = (1,-1,-1, 1,-1,-1, 1, 1). Clearly these two vectors, or trading strategies, are highly correlated. This remark can be elaborated upon and it can be shown [START_REF] Challet | On the minority game: analytical and numerical studies[END_REF]) that a qualitative understanding of the model can be obtained from, instead of the total set of S = strategies, a much smaller sets of just independent vectors (/strategies). i So to get a qualitative description of the MG one only needs a small subset out of the total number of strategies.

It turns out that a qualitative understanding of the MG for a given fixed value of S can be obtained from just one parameter [START_REF] Savit | Adaptive Competition, Market Efficiency, and Phase Transitions[END_REF], α, given by the ratio of the size of the set of uncorrelated strategies over the total number of N agents, α ≡ . For a general value of S it is however more natural to define the control parameter instead as α' ≡ [START_REF] Challet | On the minority game: analytical and numerical studies[END_REF]; [START_REF] Zhang | Modeling Market Mechanism with Evolutionary Games[END_REF]) since this parameter gives the ratio of the size of the set of uncorrelated strategies to the total number of strategies at play for any value of S. The distinction between the two definitions is not important for the results discussed in the following since S is taken constant, so we will stick to the notation used in the literature α ≡ .

We will limit ourselves to a very brief introduction to the MG, but for readers interested in the model more information on the MG can be found in [START_REF] Challet Damien | Minority Gamesμ Interacting Agents In Financial Markets[END_REF]) which is specifically dedicated to the research on the MG.

The price dynamics of the model enters in quite a special way and a word of caution is necessary since the details given in the following turn out to be absolutely crucial in the understanding of the model. Figure 2.1 gives a schematic representation of how the model works.

[

HERE FIGURE 2.1]
At each time step the agents update the score of their strategies according to the MG payoff function see eq.( 1) below. Based on actual history of the market each agent chooses the best performing strategy from a set of s available strategies which is then used to make the decision of whether to buy or sell an asset. The performance of the i'th agents j'th strategy is determined via its payoff function (t) which in the MG is updated according to:

∑ (t) (1)
(t) denotes the action of the i'th agents j'th strategy. It can be found in the strategy's lookup table as the right hand side corresponding to the price history that occurred at time t. Let us take the example where the market over the last 3 days went first up, then up and today finally down (i.e. the price history was (110) ). If the i'th agents, j'th strategy was given by the strategy shown in table 2.1, then = 1 as can be seen from that table. (t) represents the best performing (optimal) strategy of agent k at time t. In other words, is the strategy (out of s) actually used to trade with for agent k.

The name of the model should now be clear since (1) says that every time a given strategy takes the opposite position as taken by the majority (given by the sum in (1)) it gains, whereas if it took the same position as the majority it loses. The gain/loss is in the representation (1) is proportional to cumulative action of the agents.

It's important to remark the nonlinearity that enters (1) because of the "*" notation on (t). The nonlinearity is created since the agents try to cope with market changes by using their optimal strategy (out of the available pool of s strategies) at each time step. Therefore as the market changes, the optimal strategies of the agents change, which in turn (see figure 2.1) leads to changes of the market. This illustrates a highly nonlinear and non-trivial temporal feedback loop in the model; something which is argued takes place in the way people trade in real markets with people try out optimal strategies depending on the present market behavior.

SOME RESULTS FOR THE MINORITY GAME

In the "basic" version of the MG the agents can either buy or sell a unit of stock at each time step and they are assumed to have an unlimited amount of money and stock. The dynamics of the return of the market at time t, r(t), is a function of the difference between the number of market participants who buy, and those who sell. Specifically: r(t) = log [P(t)/P(t -1)] ( 2)

∑ (3)
with a constant describing the liquidity or market depth. Eq.3 expresses the fact that the return is proportional to the order imbalance given by ∑ The "t-1/2" notation in (t-1/2) is meant to stress that the decisions of actions made by the agents take place between the announcement of the price at the two moments t -1 and t, see figure 2.1. In the MG literature however this fact is usually little stressed and an "abuse" of notation writes r and taken at the same time t, but what is meant is that the action is taken first and then the price is announced.

The sequence of how the events take place is clearly illustrated in figure 2.1. Having made this point clear we will for simplicity stick to same "abuse" of notation and take r and at same instant of time. The small α case can be understood in terms of "crowd-anti-crowd theory" of Johnson et al.

[FIGURE 2.2 HERE] [FIGURE 2.3 HERE]
( [START_REF] Neil | Crowd Effects and Volatility in Markets with Competing Agents[END_REF]; [START_REF] Hart | Crowd-Anti-Crowd Theory of the Minority Game[END_REF]). It turns out in that case two groups of agents form, holding strategies with opposite predictions. This gives rise to huge fluctuations seen by the large value of σ in figure 2.2 for small values of α. On the other hand for large values of α, it becomes more and more unlikely that any two agents will hold the same optimal strategy. In this case the MG becomes a random game and the variance per agent approaches asymptotically the value 1 as would be the case in a game where the agents sold/bought randomly at each time step. Most interesting is the fact that for α ≈ 0.34 the agents, somehow, organize into a state where the market has lower volatility compared to the case where the agents trade completely randomly.

The minimum separates the state of the system into two different phases: 1) the crowded symmetric phase for small values of α where the market is unpredictable as seen by the predictability parameter H ∑ , where < denotes the conditional average of given the price history and the mean <> is calculated over all P price histories. H = 0 in figure 2.3. 2) the un-crowded phase where on the contrary the actions of the agents leaves information which can be traded on. This is seem by the predictability parameter H > 0.

Finally the study by [START_REF] Cavagna | Irrelevance of Memory in the minority game[END_REF] should be mentioned, since it was shown the maybe a priori surprising result, that it is not the feedback that is the important in the MG but rather the fact that the agents react to the same information. This is seen from the fact that the results in figure 2.2-3 remain almost unchanged (though there are some minor modifications in the asymmetric phase) if the agents instead of their own generated price history (see figure 2.1) use a randomly generated sequence of price moves (in the MG literature this is called exogenous games). The interpretation of this is, that is the fact that the agents share the same information that matters,

and not the feedback they generate in the formation of the price history (in the MG literature this is called the endogenous game case). This is an important result for analytical approaches to understand the MG, since analytical results can be obtained for exogenous games but not in general for endogenous games. It should however be noted that this is not a general result for agent-based models, the best counter example will be presented in the next section, where feedback will prove all important in the so called $-Game.

THE $-GAME

The main problem with the Minority Game described in the last section is of course that it is hard to imagine people trading in real markets just because they would like to be in the minority! People trade either because they try to make profit or because they need to hedge their positions, but even when trying just to hedge a position traders will of course try to do so at the best possible price. This elementary fact is not taken into account in the Minority Game, and was the main criticism that lead to another agent-based model, called the $-Game ($G), introduced to stress the fact that people trade to make profit [START_REF] Andersen | The $-game[END_REF]). This point will be explained in the following.

Actually, sometimes it is advantageous to be on the minority side of trades, especially when you enter a new position since opening a position you want to be opposite to the rest of the market in order to get a favorable price: if most people buy but few people (including you) sell, the imbalance will push up the price ensuring you sold at a favorable price and vice versa entering instead a position by buying an asset. However in the time that follows after entering a position, whether long or short, you no longer want your bet to be a minority bet. Let's say you bought some gold today, you then want this bet to be on the majority side following your purchase since then the imbalance created by the majority of trades pushes up the price in your favor. The best strategy in terms of profiting is therefore not always targeting the minority but shifting opportunistically between the minority and the majority. Specifically the payoff function taking into account these considerations was proposed in [START_REF] Andersen | The $-game[END_REF] to be given by:

∑ (t) (4) = (5)
Notice that the payoff function now is depending on two different times. To understand this point imagine you have only access to the daily close of a given market and decide to invest in this market at time t -1 and enter a position determined by how the market closes at that instant.

Then it is not until the day after knowing how the market closed (i.e. time t) that you will know if the decision you made the day before was a wise decision or not. This is especially clear from ( 5)

where one can see the link between the decision made at day t -1 (given by (t -1)) and the return of the market between day t -1 and day t (given by r(t)). So a strategy gains (losses) the return of the market over the following time step, depending if it was right (wrong) in predicting the market movement. Therefore in the $G agents correspond to speculators trying to profit from predicting the direction of price change.

One should note that the payoff for both the MG (1) and the $G (4) assign to strategies that are not active. This means all strategies except the optimal at a given time t) counts a "virtual" return since its contribution is not counted in the term ∑ . The lack of this "self-impact" has been shown to have important theoretical consequences, but here we note that from a practical point of view it makes very much sense that agents assign a "virtual" return to their strategies. This is the reality in practice when investors try out new arbitrage ideas in a financial marketthey first use price data as information in the search for arbitrage possibilities without actually entering the market.

[FIGURE 2.4 HERE]

As will be seen the emergent properties of the price dynamics and the wealth of agents are strikingly different from those found in the MG. Most remarkable it is seen from figure 2.4 that the wealth (lower graph dashed line) of the best performing MG-agent (i.e. optimal as described by ( 1)) perform consistently bad whereas reciprocally the relatively good performance in terms of wealth for the worst MG-agent (lower graph solid line) is a clear illustration of the fact that a minority strategy will perform poorly in a market where agents compete to make money. In contrast $G agents as defined in terms of ( 5), match by definition the performance of the wealth of the agents. This does however not exclude the potential usefulness of MG strategies in certain situations, in particular for identifying extrema, as will be illustrated in the next section.

Like the MG, dynamics of the $G contains nonlinear feedback, which is thought to be an essential factor in real markets, because each agent uses his/her best strategy at every time step.

This attribute makes agent-based models highly nonlinear and, in general, unsolvable. As the market changes, best strategies of the agents change, and as the strategies of the agents change, they thereby change the market. As shown in Roszczynska et al. (2011) the Nash equilibrium for the $G without constraints is given by Keyne's "Beauty Contest" where it becomes profitable for the subjects to guess the actions of the other participants, and the optimal state is one for which all subjects cooperate and take the same decision (either buy/sell). A plain way of saying the same thing is that in the $G without any constraints in the amount of money/stocks that the agents can hold, bubbles are generated spontaneous. This intrinsic "spontaneous bubble generating" property is specific to the $G and completely absent in the MG since agents seeking the minority generates mean-reverting behavior, so bubble generation is an impossibility in the MG. As will be shown we can use this intrinsic tendency to generate bubbles of the $G to actually detect bubble generation in real markets. For the moment, notice just that the price in the bubble state deviates exponentially in time from the fundamental value of an asset which is assumed constant. All subjects profit from further price increases/decreases in the bubble state, but it requires coordination among the subjects to enter and stay in such a state.

A SCIENTIFIC APPROACH TO FINANCE

We would like to advocate for what could be best be called a scientific approach to Finance.

Scientific, because we propose experiments to go hand in hand with theory, a tradition that comes from the hard sciences, but which is a rare approach in traditional Finance. It has been argued that the reason for the success of the hard sciences is precisely the link between proposing theories/models against which one can test via experiments. This lies at the heart of the philosophy of science suggested by the Austro-British philosopher Karl Popper . He

introduced the idea that a scientific theory can never be completely verified no matter how many times experimental testing confirm the assumptions of the theory, but one single case in which the theory is shown not to hold experimentally, can falsify the theory.

AGENT-BASED MODEL USED AS A "THERMOMETER": TAKING THE "TEMPERATURE" OF THE MARKET TO PREDICT BIG SWINGS

Just as one can get information about the internal state of water by inserting a thermometer into the liquid, the idea of applying models of agent-based simulations on real financial market data and look at how agents react via their decision making, would be a way to probe the internal "state" of the market. The hope would be to get a new way of characterizing markets getting general information of e.g. whether the market would be in a "hot" or "cold" state. How to implement this idea in practice will be discussed in the following and it will be illustrated how sudden large swings in markets seem to have precursors which can be used in attempts to predict such swings.

As mentioned in the last section, before making any claims that agent-based models should be applicable to extract information on real market data, it is clear that a first minimal requirement needs to be met. Imagine therefore given a "black-box" time series generated by a multi-agent game for a fixed unknown parameter set of the three parameters (N,m, s) as well as an unknown specific realization of initial strategy choices assigned to the agents in the game. A minimum requirement doing reverse engineering would be that using the "black-box" time series as a

"blind test" one should be able to extract what were the parameters used to create this time series. If one cannot possible estimate the parameters of a theoretical defined model it would be useless spending time on real market data, which needless to say, are not created according some theoretical framework.

A reverse engineering test for the MG was proposed by Lamper et al. (2000). A priori it seems as an almost impossible task trying to estimate parameters in a model which has an astronomical large number of different initial conditions given by the different strategies. Nonetheless it was shown by Lamper et al. (2000) how this task is possible to perform for a moderate number of strategies, meaning for a sufficient small memory (say m=2-5) used by the agents in the MG. This is indeed very good news since as shown it is possible, at least in the case of the MG, to reverse engineer and find the parameters of a "black box" generated time series without knowing in detail the theoretical setup of the model! Similarly the possibility of reverse engineering was later found to hold for moderate values of m (m=2-5) also in the case of the $G [START_REF] Andersen | A Mechanism for Pockets of Predictability in Complex Adaptive Systems[END_REF]).

Let us finally end this section with an appetizer to the discussion in the next section. Lamper et al. (2000) give an example of how large changes can be predicted in a multi-agent population described by the MG. The remarkable fact is that the predictability actually increases prior to a large change. It was shown how predictable corridors appear at certain time periods, a typical example of which is shown in Figure 2.5. In the next section we will identify the mechanism which gives rise to such large market swings.

[FIGURE 2.5 HERE]

RESULTS

THE IDEA OF DECOUPLING

We start by presenting a method by which soft human decision heuristics can be precisely formalized as rules in the agent's decision making in agent-based models of financial markets.

The agent-based models that we have in mind are games of the types like e.g. the Minority Game or the $-Game as were introduced in last section. In this formalism, cognitive closure is defined as the decoupling of an agent's strategies from the market feedback.

[HERE TABLE 3.

1]

In what follows we will describe decoupling in the context of the $G but it should be noted that this is a general property related to agent-based games which use look-up tables like table 3.1.

It is important for the understanding of the following to note that the optimal state of the $G is the solution in which the price deviates exponentially in time from the fundamental value of the asset, enabling all agents to profit from constant price increases/decreases in the bubble/antibubble states. However finding the optimal solution in the $G requires coordination among the agents to enter and stay in such states. Coordination, however, is not driven by an intentionally coordinated behavior of all agents; rather, it emerges from independent decisions of the majority of agents who choose the optimal strategies from the entire set of strategies. These optimal strategies presented in the reference tables happen to lead to the same action, which on an aggregate level is seen as synchronization. The question is whether this mathematical formalism can adequately describe the process of human decision-making.

Agents' strategies, at the first glance, are very different from what we know about decision heuristic of humans [START_REF] Tversky | Judgment Under Uncertaintyμ Heuristics and Biasis[END_REF]). Decision heuristics provide rules for human decision making. Heuristics are formed in terms of verbally (or rather propositionally) formulated conditional rules. Clearly, humans are cognitively incapable of precisely representing many vectors and exact sequences of market dynamics, needed to represent and valuate the strategies. However, the reverse formalization of human decision heuristics by lookup tables is simple. Any conditional rule of human reasoning can be represented by a lookup table. To accept the notion that agent's strategies represent human decision heuristics we just need to assume that each agents' strategy depicts in a algorithmic way implementation of a decision heurist that for humans would be specified in a higher level language.

In this vein, cognitive closure in market players may be interpreted as setting up the mind as to what will happen in more distant future, regardless of what happens in the near future. In terms of decision heuristics after observing certain patterns of market dynamics investors may come to the conclusion that the market trend is set and, further, the temporary market reversals are not indicative of the real market trend. For example if the market player judges that the market trend is up, then the increase in price serves as a confirmation of the expected trend so the decision is to buy. If the price drops, it may be perceived as a momentary deviation from the governing trend, which indicates immediate correction, so the decision also is to buy. In terms of agent's strategies this may be translated as decoupling of agents' strategies, something which will be crucial in the understanding of how speculative bubbles are formed.

As long, as the majority of investors are reacting to incoming information the market dynamics is unpredictable. If, however, large enough proportion of investors makes the decision about the direction the market will evolve regardless of what happens next, the market may become temporarily predictable since investors are in fact locked in their decision and decisions are temporarily decoupled from information concerning the market. The prolonged locked decision of investors on the buy decision results in bubbles, and locking the decision on selling will result in market crashes.

Some strategies represented by reference tables have a unique property: i.e., the actions that they recommend are decoupled from the incoming information. A decoupling of the strategy means that the different patterns of market history lead to the same decision (e.g., buy), regardless of whether the market went up or down at the previous time moment. The main interest in the mechanism of decoupling is, as we will show, it gives a handle to predict formation of speculative bubbles before they are seen in the price data.

THE FORMALISM OF DECOUPLING

The simplest example of decoupling in agent-based models is the case in which an agent uses a strategy like the one presented in Table 3.1, but with the action column consisting only of 1s. In this case, the strategy is trivially decoupled because, no matter what the price history is, this strategy will always recommend buying. In the notation used in [START_REF] Andersen | A Mechanism for Pockets of Predictability in Complex Adaptive Systems[END_REF], such a strategy would be referred to as an infinite number of time steps decoupled, conditioned on any price history. In plain words: if somebody ends up holding a strategy having only 1s in the decision part, such a strategy would always make the same decision to buy at every time step, independently of what goes on in the price history of the market. It should be noted that the probability of an agent possessing such a strategy is very small and is given by because is the total number of strategies. The strategy presented in Table 3.1 is one time step decoupled, conditioned on the price history was = (01) at time t because in cases where the market at time t + 1 went up ((01) → (11)) or down ((01) → (10)), the strategy in both cases recommend buying at time t + 2 (i.e., for both ( 10) and ( 11), buying is recommended). In plain words: every time we see an occurrence of the price history where the market first went down (0), then up (1) we know for sure what action this strategy will recommend in two time steps. To see this imagine that the market following the down-up movement would go say down (0). Then the updated price history to be used by the strategy at the next time step would be up-down, i.e.

(10), and here the strategy recommends to buy. If instead however the market following the down-up movement would go up (1) the updated price history at the next time step would be upup, i.e. ( 11), in which case the strategy also recommends to buy. So this means that whatever happens in the time step after the up-down movement of the market, we can tell for sure that following this time step the strategy will always recommend to buy. Likewise, the same strategy is seen to be one time step decoupled conditioned on the price history (11), since, independently of the next market movement at time t+1, the strategy will always recommend buying at time t + 2.

In a game with only one agent and only one strategy, such as the one in Table 3.1, we could therefore know with certainty what the agent would do at time t + 2 if the price history at time t was either (01) or (11), independent of the price movement at time t + 1.

A priori, it is highly nontrivial whether one should ever find the condition for decoupling to be fulfilled at any instant of time, even in the computer simulations of the agent-based models. As shown in [START_REF] Andersen | A Mechanism for Pockets of Predictability in Complex Adaptive Systems[END_REF] if the agents in the MG and $G play their strategies randomly, the condition (given the parameters used in the simulations) was never fulfilled. When the agents choose their strategies randomly there is no feedback between the price movements of the market and the decision making of the agents, so it's important to note that in this case we cannot use decoupling to predict what the agents will do next. The way decoupling arises therefore has to be related to feedback and dynamics of the pricing, which somehow imposes that the optimal strategies of agents will be attracted to regions in the phase space of strategies which contains decoupled strategies. In the $G the natural candidates for attractors are the two most trivial strategies with actions either all +1 or all -1. However, because it is very unlikely for an agent to possess these two strategies, an attractor would necessarily have to consist of regions in the phase space of strategies which are highly correlated to such strategies. In the MG it seems even less obvious that decoupling should ever take place, since there seem to be no natural attractors for decoupling in that game.

[FIGURE 3.

HERE]

Interestingly even the MG does indeed show predictable behavior as can be seen from figure 3.1.

Each dot in this figure shows the value of versus time. Given the parameter values of the MG used in the simulations, the condition of ( 7) means that whenever the value becomes larger than 50, or smaller than -50, we can predict for sure the direction of the market two time steps ahead independent of the market move one time step ahead. As can be seen from the figure most of the dots lie within the [-50:50] interval and for such events we have no prediction power. However the dots enclosed by a circle illustrate "prediction days" given from the condition (7), which means that standing at time t one can predict for sure the outcome of the market at time t + 2 independent of which direction the market takes at time t + 1. Crosses in the figure correspond to the events where two or more consecutive price movements can be predicted ahead of time.

At first it might seem like a somewhat theoretical exercise to be able to predict ahead of time how agents in a computer simulation will behave. One could argue that since the setup of the computer program is entirely determined by the parameters of the simulations, all information is already encoded in the program and the only thing needed to predict two time steps ahead would be to let the program run two additional steps and then see what happened. This remark however misses the point concerning the more interesting situations of practical applications where simulations of the agent-based models are "slaved" to real market data as explained in section 2.

This corresponds to considering real predictions in real time. In the case of applying real market data as input to the computer simulations of the agent-based models, one encounter the situation of knowing for example the closure of the markets today. Observing then a moment of decoupling in the computer simulations given the market closure of today means that we know

for sure what the agent-based model will predict , not for tomorrow, but for the day after tomorrow. In that case we don't need to wait and see how the markets close tomorrow to be able to make the prediction tomorrow -it can be made already today.

[FIGURE 3.

HERE]

The mechanism of decoupling can now be seen as a natural candidate to understand and define the process that lead to the observed "big swings" in the market defined in section 2. To see how the method of decoupling works when applied to real market data, consider figure 3.2 which shows as an example the Nasdaq Composite price history (thick dashed line) as a function of time in unit of days over a half year period. The shown sample period was chosen so as to have no apparent direction of the market over the first half of the period which was used as in-sample.

As described in section 2 when "slaving" a game to real market data, one uses the last m price directions of the real market data as input to the $G agents in the computer simulations. The agents therefore adjust their optimal strategies according to the real price history. The defined in (6) can in this way be calculated from the optimal strategies of the agents which are determined dynamically via the price history of the real data. The data of the in-sample period was first used to fix the parameters of the $-games which could best describe the Nasdaq Composite over the in-sample period. The $-games which fitted best the Nasdaq data in-sample were found using genetic algorithms that explored the 3 different parameters of the $-games as well different initial strategies attributed to the agents in the game. Having fixed the parameters of the $G that supposedly gives the best representation of the Nasdaq data in-sample, the remaining half of the data set was then used out-of-sample. The ten thin solid lines in figure 3.2

show third-party $-games obtained in this manner. The third-party $-games were constructed all with the same optimal parameters found in the genetic algorithm search, but each game had agents using different initial realizations of their strategies attributed to them in the beginning of the time period. Note the fact that the 10 thin solid lines all follow closely the real market data (thick dashed line) over the in-sample period. It illustrates the fact that different games with same parameters and all slaved to the same input data (here the Nasdaq Composite) perform similarly despite having agents with different pools of strategies assigned to them at the beginning of each game. Giving the size of the pool of the strategies ( ) this is maybe a priori a surprising result.

It lies at the core for the reason that one can do reverse engineering and find the parameters of a given time series generated by an agent-based model as shown by Lamper et al. (2000).

Of course the best way to try out a method is to test it on real data and see how it works. In order to see if prediction could be made using the idea of decoupling, the ten third-party games were then fed with the Nasdaq price history over the second half (the out-of-sample) period and predictions were issued at each close of a given day. The ten games would then issue a prediction when detecting a "prediction day".

[HERE TABLE 3.2] First it should be noted that it turns out that the using just the majority decision of the third-party games does a poor job at predicting the out-of-sample prices of the Nasdaq Composite index, while table 3.2 shows that they predict specific pockets of predictability associated with the forecasted "prediction days" As can be seen from the table below, the larger the threshold (measured by the parameter ) for predicting the larger the success rate in predicting the direction of the price movement of the Nasdaq Composite. The most important point to note is that the success rate increases with the amplitude of . The larger the value observed of the more confident one should be in the prediction. A large value however also comes at a "price", since there are fewer such events meaning worse statistics.

Having gotten a first idea of how to apply the idea behind decoupling to real data we now turn our attention to the detection of speculative financial bubbles. The following section will give additional insight into when decoupling could be a mechanism driving real price dynamics and in particular under which circumstances this mechanism could be used in the prediction of the onset of speculative bubbles.

DECOUPLING USED TO DETECT SPECULATIVE FINANCIAL BUBBLES

We will give a short introduction how to use the technique of decoupling in experiments with human subject trading in a market. The results shown are taken from Roszczynska et al. (2011) where a detailed description of the experiments is explained.

[FIGURE 3.3 HERE] Figure 3.3 gives an illustration of the price histories generated by the humans in three experiments. The circles illustrate the evolution of the price. In all three experiments the price was normalized to one at the beginning of the experiment. The two first plots give example of the creation of a bubble whereas the last plot illustrates an anti-bubble. The time ttb was chosen so that the onset of the bubble/anti-bubble (defined by tb) happened at time 0. The dashed vertical lines shows in all three case the time tb + m when the presence of a bubble/anti-bubble becomes evident from the price history itself. This is the time when the last m directions of the price movements had same sign (positive: up; negative: down). The solid lines illustrate the percentage of optimal decoupled strategies along the direction of the bubble (first two plots) or anti-bubble (last plot) whereas the dotted lines are the optimal decoupled strategies along the opposite direction. For experiments in which synchronization is due to decoupling, one can see a clear split of positive decoupled versus negative decoupled strategies happening before the onset of the bubble. As seen in figure 3.3a, even when a bubble is created very rapidly (with small m = 3), we see a split. However, as expected, this split becomes clearer over a longer time period for the larger memory length m = 6, as seen in figure 3.3c. In this case the subjects had a longer period over which they trade in a descending market before the final synchronization occurs.

Such a condition resembles features seen in real markets, with a typical run-up/-down before the first stages of a bubble/anti-bubble sets in, which gives confidence in applying our method to real market data. To further test the idea of decoupling, a manipulation of the price was done after over one time step after the subject had entered a decoupled state. This is seen by the spikes in the price figure 3.2.b-c. If truly decoupled the subjects should continue in a state of decoupling independent of the manipulation made of the price. This was indeed found to be the case as seen from the figures 3.2.b-c. These results reveal that decoupling can explain the synchronizations of people. Moreover, it appears that decoupling enables the prediction of the future market state, not only during the emergence of bubbles/anti-bubbles but also in a situation of a short-lasting (several time steps) synchronization of investors.

We have tried to argue for the use of game theory/agent-based modeling, that go beyond the standard methods used in traditional approaches of Finance. The idea is that we need models which more realistically describe the decision making of investors in financial markets. Two such models have been introduced, the Minority Game and the $-Game, and their main results have been discussed. It has been argued that a more scientific approach to Finance is needed, with theories and experiments done in trading floors needed to falsify and thereby select relevant properties of theoretical models. Some preliminary results in this direction has been shown by the introduction of the idea of "decoupling" of investor decision making. The hope is that the present article could help spark interest in such a scientific approach to Finance with the introduction of more models which can be tested by experiments done on trading floors.

i An example of independent strategies could be two strategies which does the opposite conditioned on a given realization of the price history. Such strategies are supposed to play a major role in the "crowded" phase where two almost equal size groups are formed with different mutually opposite view of the market behavior.

Figure 2

 2 Figure 2.2-3 illustrate the main results for the MG. It is taken from Yeung and Zhang (2009) and shows the behavior of the model for different values of the control parameter α = but for a

Figure 2 .

 2 Figure 2.2 shows the volatility of the model for a given fixed value of α plotted on the x-axis.The first thing to notice is the data "collapse" seen by the overlap of the 5 curves for the 5 different values of N. It tells you that α is indeed the relevant parameter to describe the model.

  What characterizes a strategy is therefore what it recommends to do given this constant set of different price histories. That is, what characterizes a strategy is just given by the right hand side of the table 2.1. Therefore formally a strategy can be seen as represented by a binary vector of length m. As mentioned above there are S = of such vectors. Many of these vectors are however very similar in the trading strategy they recommend. Take e.g. table2.1 and just change the last entry so that instead of recommending to sell if the last 3 days where up, it would then recommend to buy in this case. The two strategies are represented by the vectors ⃗⃗⃗⃗ =

Trading is complex!

The possible set of different price histories for a given fixed value of memory m of course always stays the same, i.e. the left hand side of the table 2.1 is the same for all possible strategies.

  Having stressed the need for experiments according to Popper, let us mention that experimental Finance took a big step forward by the attribution of the Nobel Prize in Economics to Vernon Smith in 2002. His most significant work was concerned with market mechanisms and tests of different auction forms. However by far the major part of the experimental work in Finance has considered (including Vernon Smith) human rationality and the ability of markets to find the proper price close to an equilibrium setting. Contrary to this approach Behavioral Finance takes a much more realistic description of how actual decision making takes place in financial markets.It would therefore seem like a very natural approach to bridge the insight gained from Behavioral Finance and apply it to experiments done on financial markets. Interestingly very little effort has been done in this direction. The main reason is maybe because the major part of research done in Behavioral Finance is concerned with how individual decision makes takes place (Prospect Theory included) and in a static setting, whereas price setting in financial market is clearly a collective and dynamic phenomenon.

The term "falsifiable" introduced by Popper simply means that if a theory is wrong one should be able to show this by experiments. By the same logic this also means that if somebody introduces a theory that cannot be falsified this is not a scientific theory. Let us mention the Efficient Market Hypothesis as an example of a theory which can never be falsified by experiments, and therefore in the Popper's view, is not a scientific theory. Popper mentions falsifiable theories at the root of the apparent progress of scientific knowledge over time, and therefore also seems like the best candidates for a way forward of making progress in Finance.

Ultimately one should of course see the actual pricing taking place in a given financial market as one big experiment performed in real time! So if you have a model for a financial market, like e.g. the Minority Game or the $-Game, you should be able to falsify at least parts of your model against real market data. Most importantly however is the following minimal requirement, or test, for any models claiming to describe price dynamics in financial markets: assign randomly values to the parameters of the model, and generate a history of price time series according to the model with these given values of parameters. Imagine you didn't know the parameters used to generate the price time series and launch a search to try to determine their value. If this is not possible, then for sure you will never be able to estimate what would be the parameters describing any real time series of financial data.

ACKNOWLEDGMENTS

The author would like to thank the Collége Interdisciplinaire de la Finance for financial support.

CONCLUSIONS

As discussed above we have seen how sometimes the strategies of the agents can lead to momentarily "pockets of predictability" of what action a given agent will take in near future. But even knowing for sure what one or even several agents will do, does not mean that we necessarily know what will happen at the level of the market. To know for sure how the market will behave, we need to encounter the situation in which not only a majority of agents are decoupled, but we need to been in a situation in which such a majority of agents are decoupled in the same direction. To see how such a condition can arise we introduce the following formalism.

We call a strategy coupled to the price time series if conditioned on a given price history at time t we need to know the price movement at time t+1 in order to determine what the strategy will recommend at time t+2. Conditioned on having the price histories of either (00) or ( 10) at time t, the strategy in Table 3.1 is coupled to the price time series because we cannot know what it will recommend at time t+2 without first knowing the price history at time t+1. At any time t, one can therefore ascribe the actions of agents to two contributions, one from coupled strategies and one from decoupled strategies, as:

(6)

The condition for certain predictability one time step ahead is therefore

because in that case we know that, given the price history at time t, the sign of the price movement at time t + 2 will be determined by the sign of | |

DECOUPLING SEEN IN COMPUTER SIMULATIONS AND IN REAL MARKET DATA


Walter Nuninger
email: wnuninge@ensem.u-nancy.fr

Frédéric Kratz
email: fkratz@ensem.u-nancy.fr

José Ragot
email: jragot@ensem.u-nancy.fr

STRUCTURAL EQUIVALENCE BETWEEN DIRECT RESIDUALS BASED ON PARITY SPACE AND INDIRECT RESIDUALS BASED ON UNKNOWN INPUT OBSERVERS

Keywords: Redundancy, fault detection, fault isolation, observers, unknown input, parity space, robustness

In order to solve the fault detection and isolation problem, a diagnostic procedure is used. This procedure is composed of two steps: residuals generation followed by their evaluation within decision functions. Many ways have been developed to generate residuals. Among them, we quote the well known parity space approach and the observer based approach. These methods are known to produce structural equivalent residuals. As a consequence, one wonders which method to use in order to design a more robust on-line detection system. Besides, unknown input observers are known to be helpful, within Generalised Observer Schemes, to improve robustness with respect to systems uncertainties. Then, it is important to know if this equivalence is still true for residuals based on unknown input observers. So the goal of this paper is to give theorems so that answers to the previous interrogations could be given and discussed.

INTRODUCTION

Nowadays, fault diagnosis is an important field of research because of the increasing complexity of processes. Indeed, control systems require failures to be detected and isolated and further taken into account in order to maintain the performances required. Many surveys on design methods for the diagnostic procedure were done by Iserman (1976), [START_REF] Frank | Fault diagnosis in dynamic systems using analytical and knowledge base redundancy -A survey and some new results[END_REF]Frank ( , 1993)), [START_REF] Gertler | Analytical redundancy in fault detection and isolation[END_REF] and [START_REF] Patton | Robust model-based fault diagnosis: the state of art[END_REF]. In the past decade, the trend has been the development of analytical redundancy based methods rather than massive redundancy based approaches. These methods generate a signal significant of the fault. This signal that contains information about the failure, is called a residual. Such a residual is defined so that it is statistically close to zero when there is no failure and quite differs from this value otherwise. It is important to note that all these methods require a model of the system behaviour. Such a model is submitted to uncertainties like measurement noise and parameter (and even structure) variations. Depending on the assumptions supposed for the design of the detection system, these disturbances can lead to false alarms or no detection that degrade the performances. This problem is referred in the literature [START_REF] Frank | Fault diagnosis in dynamic systems using analytical and knowledge base redundancy -A survey and some new results[END_REF] as the robustness proprieties of the diagnostic procedure with respect to disturbances. Robustness is a degree of performance. It is then obvious that this degree is the result of a compromise between distinct performance criteria such as, for instance, both minimal no detection and false alarm rates. Among the techniques used for residual generation, two groups of techniques are presented: the direct generation based on parity space equation and W. NUNINGER, F. Kratz, J. Ragot, Structural equivalence between direct residuals based on parity space and indirect residuals based on unknown input observers, SAFEPROCESS'97, Symp. on Fault Detection, Supervision and Safety for Technical Processes, Vol. 1, pp. 462-467, Hull UK, august 26-28, 1997. the non direct generation that provides a residual based on state estimation. In that case, the simplest residual performed is the state estimation error, i.e. the comparison between the measured data and its estimation. In the literature, the reason to prefer one technique (direct) to the other (indirect) mostly depends on the habit rather than more scientific criteria. As presented previously, criteria considering the easier way to implement the method and/or the more robust residual generated should be worthwhile. The structural equivalence of the residual of both methods is well known. Indeed, [START_REF] Patton | A parity space approach to robust fault detection using eigenstruture assignment[END_REF] recall that parity space leads to reliable FDI scheme. They stress on the fact that even though their potential robustness was studied, less work has been done to show the powerful correspondence existing between both techniques. Nevertheless, [START_REF] Frank | Robust fault diagnosis using unknown input observer schemes[END_REF] and [START_REF] Frank | Fault diagnosis in dynamic systems using analytical and knowledge base redundancy -A survey and some new results[END_REF] pointed out that under certain conditions both residuals were equivalent within a choice of the observer gain to get the same proprieties on the estimation error. This result was proved afterwards by [START_REF] Magni | A generalized approach to observers for fault diagnosis[END_REF]. Several authors as, [START_REF] Frank | Robust fault diagnosis using unknown input observer schemes[END_REF], Wünnenberg (1990), [START_REF] Gertler | Analytical redundancy in fault detection and isolation[END_REF]), Staroswiesky (1991) and Frank (1993) evidenced that parity space approach leads to certain types of observer structures and is therefore structurally equivalent. Anyway, no results have been given with regard to unknown input observers, nor about the robust aspect.

Pari ty space projection matrix

Direct residual R(t)

UI Observer

Gain

Indirect residual E(t)

How can we get R(t) from E(t) and reciprocal ? Is E(t)=R(t) possible ?

Fig. 1: Problem illustration

The goal of this paper is illustrated in Fig. 1. Its relevance is first, to consider unknown input observer, and second, to present the results into the lemma and theorem format. Some attention to this case has already been made by [START_REF] Nuninger | Observers and redundancy equations generation for systems with unknown inputs[END_REF], but at that time only one theorem was proved, i.e. if an unknown input observer can be found to generate the residual as the estimation error, then one can construct the projection matrix for the direct approach and get the structure of the parity space based dual residual. Here, the reciprocal part of this theorem is proved and its implications are discussed. This paper is organised as follows. First, the problem formulation is presented. Second, from [START_REF] Nuninger | Observers and redundancy equations generation for systems with unknown inputs[END_REF], both the generation scheme of analytical redundancy equations and the indirect residual generation procedure, based on unknown input observer, are quickly recalled. In the third part, theorems and demonstrations are given to get one residual from another. Finally, the consequences implied by the previous theorems, for the design of a robust on-line diagnostic procedure, are discussed.

PROBLEM FORMULATION

Let us consider the linear time-invariant system subject to disturbances:

Ý x (t) = Ax(t ) + Bu(t) + Hv(t) (1.a) y(t) = Cx(t) + Du(t) + Fv(t ) (1.b)
where x ∈R n is the state vector, u ∈R r the control input, y ∈R p the measured output vector and v ∈R q the disturbance vector which components are unknown functions of the time. All the matrices are of appropriate dimensions and of real constant components. Note that this representation can describe a great number of systems such as uncertain parameter systems or singular systems for instance. Define the following assumptions:

Hypothesis 1: C is a full row rank matrix. Hypothesis 2: there is more measurements than unknown inputs (p > q). Hypothesis 3: H is a full column rank matrix Hypothesis 4: F is a full column rank matrix Assumption 1 implies that there is no more massive redundancy in (1.b). This assumption is not restrictive as a singular value decomposition of C can always be performed so that massive and analytical redundancy are driven apart. Assumption 2 is therefore a sufficient condition to provide analytical redundancy. Assumptions 3 and 4 are not restrictive either as it only means that the unknown inputs have independent influence on the state and the output respectively. If this is not the case, a simple basis transaction can transform the system so that hypothesis 3 or 4 are true.

Consider system (1) that only satisfies hypothesis 1 and 2. For such a system, reduced equations (3) can always be found thanks to a singular value decomposition (2) of F. Thanks to the formulation (3), the part independent of the unknown inputs has been driven apart in the measurement equation.

F = U R 0 0 0       V T (2)
where U and V are of dimension pxp and qxq respectively and m

= rank(R) ≤ inf(p, q ) = q (Hyp. 2), Ý x (t) = A 1 x(t) + B 1 u (t ) + H 1 y 1 (t ) + H 2 v 2 (t) (3.a) y 1 (t) = C 1 x(t) + D 1 u(t) + v 1 (t) (3.b) y 2 (t) = C 2 x(t) + D 2 u(t) (3.c)
where v 1 ∈R m , v 2 ∈R q-m , y 1 ∈R m , y 2 ∈R p-m and the following definition of the matrices an vectors:

Σ = R 0 0 I       , V T v = v 1 v 2       , Σ -1 U T y = y 1 y 2       , Σ -1 U T C = C 1 C 2       , Σ -1 U T D = D 1 D 2       , A 1 = A -H 1 C 1 , B 1 = B -H 1 D 1 and HV = H 1 H 2 ( ).
Remark 1. Within our hypothesis 1 and 2, propriety (4) can easily be proved, i.e. there is no direct redundancy in (3.c) as any matrix built from rows of C is also a full row rank matrix. Under hypothesis 3, ( 5) is also true. Finally, equation (3.b) can provide the estimation of some unknown inputs if the system state reconstructability is assumed.

rank C 1 C 2             = p (4) rank H 1 H 2 [ ] ( )= q (5)
It is important to note that hypothesis 1, 2 and 3 stand for the necessary and sufficient condition for the existence of an unknown input observer for system (1): rank(CH)=rank(H)=q [START_REF] Darouach | Full-order observers for linear systems with unknown inputs[END_REF].

Remark 2. Within assumption 4, the singular value decomposition of F leads to (6) with m=rank(R)=q. This implies that the dimension of v 2 is null. So, v is defined by V T v = v 1 and v 2 does not appear in the equations (3) anymore. As a consequence, the matrix H 2 does not appear either. Indeed, HV=H 1 .

F = U R 0 (n -q ),q       V T (6)
2. RESIDUALS GENERATIONS

Direct residual generation

Lemma 1. Consider system (1) of reduced form (3) that satisfies hypothesis 1 and 2. Then a parity space, defined by the projection matrix :

Ω(s) = Ω 3 (s)C 2 (sI n -A 1 ) -1 0 (n +q ),m Ω 3 (s) [ ] (7.a)
of dimension (n+q)x(n+p) exists if and only if :

(i) Ω 3 (s)C 2 (sI n -A 1 ) -1 H 2 = 0 [ ] (n +q ),( q-m) (7.b) ⇔ (ii) matrix sI n -A 1 -H 2 C 2 0       is full
Ω(s) B 1 H 1 0 -D 1 I m 0 -D 2 0 I p -m         u(s) y 1 (s) y 2 (s)         = 0 [ ] (n +q ),1 (8)
Note that Ω(s) satisfies:

Ω(s) sI n -A 1 0 -H 2 C 1 I m 0 C 2 0 0         = 0 [ ] (n +q ),( n+ q ) (9)
which is the constraint on the projection matrix.

n -A 1 -H 2 C 2 0       = n + q -m
Under hypothesis 4, a simpler form of ( 9) is given (cf. remark 2) so that constraint (7.b) has not to be satisfied anymore. As a consequence, the necessary and sufficient condition for the parity space is reduced to (iii). In this case any matrix Ω 3 (s) of dimension (n+q)x(p-m) can be chosen. ♦

In both cases, [START_REF] Nuninger | Observers and redundancy equations generation for systems with unknown inputs[END_REF] demonstrated that (8) leads to the simplified form of the direct residual r(s):

r(s) = -Ω 3 (s) C 2 (sI n -A 1 ) -1 B 1 + D 2 [ ] u(s) { +C 2 (sI n -A 1 ) -1 H 1 y 1 (s) -y 2 (s) } (10)
and that the search of Ω 3 (s) was reduced to the search of the kernel of a binomial matrix. Note that this matrix can be chosen of minimal degree. These results are based on Gantmacher's theory [START_REF] Gantmacher | The theory of matrices[END_REF]. In practice, Ω 3 (s) is obtained within the use of Maple. It should be noted that the residual ( 10) is sensitive to both sensor and actuator faults.

Indirect residual generation

On the other hand, implicit redundancy equations can be generated as the difference between the measured output and the estimated output based on an unknown input observer of the state defined by:

Ý z (t ) = Nz(t) + L 1 y 1 (t ) + L 2 y 2 (t) + Gu(t) (11.a) ˆ x (t) = z(t ) -V 1 y 1 (t ) -V 2 y 2 (t) + Mu(t) (11.b)
where z(t) is of dimension n and ˆ x (t) denotes the state estimation of size n.

Lemma 2. Consider system (1) of reduced form (3) that satisfies hypothesis 1 and 2. Then the estimation error, ε(t) = ˆ x (t)x(t ) , based on the unknown input observer (11) tends asymptotically to zero if and only if the following relations are satisfied: N stable (12.a)

V 1 = 0 [ ] n ,m (12.b) PH 2 = 0 [ ] n ,q -m (12.c) M = V 2 D 2 (12.d) L 1 = PH 1 (12.e) P = I n + V 2 C 2 (12.f) L 2 C 2 = PA 1 -NP (12.g) G = PB 1 -L 2 D 2
(12.h)♦ Proof. [START_REF] Nuninger | Observers and redundancy equations generation for systems with unknown inputs[END_REF] Note that the N stability problem (12.a) is reduced to an eigenvalue assignment problem for the observable pair (PA 1 ,C 2 ) within the use of a gain ♦ Lemma 3. Consider system (1) of reduced form (3) that satisfies hypothesis 1, 2 and 3. Then for a square matrix P of rank n-(q-m), the unknown input observer (11) exists if and only if:

(i) the pair (A 1 ,C 2 ) is detectable (observable) ⇔ (ii) rank sP -PA 1 C 2       = n ∀s ∈C, Re(s) > 0 ⇔ (iii) matrix sI n -A 1 -H 2 C 2 0       is full column rank ⇐ (iv) rank sI n -A H C 2 0       = n + q ∀s ∈C, Re(s) > 0 ♦
Proof. The necessary and sufficient condition for the unknown input observer has already been proved by several authors as [START_REF] Kudva | Observers for linear systems with unknown inputs[END_REF], Hou and Muller (1992). The equivalence between the three propositions was proved by [START_REF] Darouach | Full-order observers for linear systems with unknown inputs[END_REF]. The result is simply applied to our case and the complete proof is therefore omitted because of the number of pages required for this paper. Note that (iii) stands for the necessary and sufficient condition of existence for the parity space under Hyp. 1, 2, 3. ♦

The indirect residual is given by the output reconstruction error:

e(t ) = y 2 (t) -ˆ y 2 (t) = y 2 (t ) -C 2 ˆ x (t) -D 2 u(t) (13)
within the model (3.c) and can be expressed such as:

e(s) = -C 2 (sI n -N) -1 G + C 2 M + D 2 [ ] u(s) -C 2 (sI n -N) -1 L 1 y 1 (s) + I p -m + C 2 V 2 -C 2 (sI n -N) -1 L 2 [ ] y 2 (s) (14)

STRUCTURAL EQUIVALENCE

Theorem 1. Consider system (1) of reduced form (3) that satisfies hypothesis 1, 2 and 3. Consider the indirect residual ( 14) based on the unknown input observer (11).

Then, for any stable matrix T(s), the signal r(s) based on the expression:

r(s) = T(s)e(s) (15)
is the direct residual based on the parity space defined by the projection matrix Ω(s) (7.a) where Ω 3 (s) is:

Ω 3 (s) = T(s) I p -m + C 2 V 2 -C 2 (sI n -N) -1 L 2 [ ] (16)♦
Proof. First, lemma 3 ensure the existence of the UIO. Therefore, from lemma 1, the existence condition of the parity space is also satisfied. Second, let choose Ω(s) of form (7.a) with the special choice ( 16) of Ω 3 (s). This choice must respect constraint (7.b). This is simply proved using (12.f), (12.h) and (12.c). Finally, it is quite simple to rewrite r(s) as ( 15) basing our demonstration on relations (12). For more details, see the proof of the theorem in [START_REF] Nuninger | Observers and redundancy equations generation for systems with unknown inputs[END_REF]. ♦

This theorem proves that if one knows an UIO for system (1) then, within the choice of a stable matrix T(s), it is easy to generate a direct residual r(s) based on the indirect residual r(s). Besides, one knows how to construct the corresponding parity space. Such residuals are called : dual residuals. What about the reciprocal ?

Theorem 2. Consider system (1) of reduced form (3) that satisfies hypothesis 1 and 2. Consider the direct residual (10) based on the parity space (7) where matrix Ω 3 (s) is given of dimension (n+q)x(n+p).

Choose two matrices : -a square stable matrix N of dimension nxn, -a constant matrix V 20 of dimension nx(q-m).

Then an UIO of form (11) defined by:

V 2 = -H 2 C 2 H 2 ( ) + + V 20 I -C 2 H 2 ( ) + C 2 H 2 ( ) [ ] (17)
P defined by (12.f) and L 2 by : L 2 = K -NV 2 (18) where K satisfies the pole placement of (PA 1 ,C 2 ): PA 1 -KC 2 = N (19) and the defined matrices M (12.d), G (12.h), L 1 (12.e) and V 1 (12.b) exists if and only if hypothesis 3 is true.

Besides, the signal e(t) generated by: e(s) = ϕ(s)r(s) (20.a)

ϕ(s) = C 2 sI n -N ( ) -1 P sI -A 1 ( )C 2 - [ ] T(s) (20.b)
is the indirect residual based on the previously defined unknown input observer if and only if T(s) is a stable matrix such that:

T(s)Ω 3 (s) = I n + p (21)♦
Proof. Note that (.) + = (.) T [(.)(.) T ] -1 stands for the right inverse of the given matrix and (.) -= [(.) T (.)] -1 (.) T for the left inverse. The proof is made in two steps. First, the existence of the UIO is proved. Second, the comparison of both residuals leads to (20) within constraint (21).

Step 1: From lemma 1, the UIO exists if and only if assumption 3 is true. Under these assumptions, the choice of P (12.f) where V 2 is imposed by the choice of V 20 like (17) ensure, from lemma 3, the existence of the UIO. Therefore, the observability of the pair (PA 1 ,C 2 ) is satisfied. K can then be found within the choice of N. L 2 satisfies (18) and the remaining matrices M , G , L 1 a n d V 1 a r e t h e n g i v e n b y t h e expressions (12.d), (12.h), (12.e) and (12.b).

Step 2: Let us now rewrite e(s) so that expression (10) of r(s) appears in ( 14). Replace M, L 1 and G by their expressions in equation ( 14) to get:

e(s) = -α(s)u(s) -β(s)y 1 (s) + γ(s)y 2 (s) (22)
where:

α(s) = C 2 (sI n -N) -1 PB 1 -L 2 D 2 [ ]+ C 2 V 2 D 2 + D 2 β(s) = C 2 (sI n -N) -1 PH 1 γ (s) = I p-m + C 2 V 2 -C 2 (sI n -N) -1 L 2 [ ] Let us now introduce I = C 2 C 2 - w h e r e C 2 -= C 2 T C 2 C 2 T ( ) -1
w h i c h e x i s t s a n d f u r t h e r r e p l a c e V 2 C 2 by its expression (12.f). Within factorisation of the term C 2 (sI n -N) -1 , α(s) and γ(s) are expressed by:

α(s) = C 2 (sI n -N) -1 PB 1 -L 2 D 2 + (sI n -N)PC 2 -D 2 [ ] γ (s) = C 2 (sI n -N) -1 (sI n -N)PC 2 --L 2 [ ]
The product NP is then replaced by (12.g). After factorisation by P(sI n -A 1 ) the following expressions are obtained:

α(s) = C 2 (sI n -N) -1 P(sI n -A 1 ) (sI n -A 1 ) -1 B 1 + C 2 -D 2 [ ] β(s) = C 2 (sI n -N) -1 P(sI n -A 1 )P (sI n -A 1 ) -1 H 1 [ ] γ (s) = C 2 (sI n -N) -1 P(sI n -A 1 ) C 2 - [ ]
Finally, define ζ(s) so that ( 23) is true. Therefore α(s), β(s) and γ(s) are given by (24) :

ζ(s)C 2 = C 2 (sI n -N) -1 P sI n -A 1 ( ) (23)
α(s) = ζ(s) (sI n -A 1 ) -1 B 1 + D 2 [ ] (24.a) β(s) = ζ(s) C 2 (sI n -A 1 ) -1 H 1 [ ] (24.b) γ (s) = ζ(s) (24.c)
It is obvious, from the comparison of ( 22) and ( 10) that:

e(s) = ζ(s)T(s)r(s) (25)
is true if and only if the stable matrix T(s) satisfies condition (21). Definition (23) of ζ(s), implies: Thanks to this theorem, the knowledge of a direct residual and the projection matrix that defines the corresponding parity space allows, for a special design of the UIO, to generate the dual indirect residual quite easily. This theorem is the reciprocal of theorem 1 but it is important to note that the UIO observer only exists if assumption 3 is true. Besides, in that case, T(s) must satisfies the stronger constraint (21).

ζ(s) = C 2 (sI n -N) -1 P sI n -A 1 ( )C 2 -. ( 26

DISCUSSION

From theorems 1 and 2, it is always possible to get a dual direct residual of an indirect one but the contrary is not always true. Besides, when it is possible, a stronger constraint ( 21) must be satisfied by T(s). The reciprocal does not require such a condition as the design of the observer is already imposed and a total freedom for the choice of Ω 3 (s) is allowed. Therefore, it is simpler to get the direct residual. These results are illustrated in Fig. 2 where O stands for a set of solutions within the indicated hypothesis and the transfer law '→' are given with the constraints. So one may think that detection systems based on both approaches are strictly equivalent under some hypothesis. In fact, one can not conclude so easily. Indeed, robustness performance of both residuals has to be considered, even though the residuals are structurally equivalent. First, it is necessary to make a proper choice of the observer gain. Indeed, this gain should further allow detection and isolation of the faults within the residual. From theorem 1, any stable matrix T(s) can a priori be chosen. As a consequence the residual e(s) generated from (15) can not be a priori influenced by certain faults. Therefore, good performances of the fault detection and isolation system could not a priori be achieved. Nevertheless, from theorem 1, it is possible to improve the robustness of the indirect residual if a good choice for T(s) is made.

As a consequence, it seems simpler to directly design the fault detection system by the parity space approach in order to get a good degree of robustness. This result has also been advanced by [START_REF] Frank | Fault diagnosis in dynamic systems using analytical and knowledge base redundancy -A survey and some new results[END_REF]. From theorem 2, it is obvious that the design of the UIO is more constrained if one wants to apply equation (20.a) because of the constraint (21). Anyway, theorem 2 allows us to design quite easily the observer and get the residual however it can be useless for fault detection and isolation. These theorems also show that the direct approach is a better one, as it is easier to construct the parity space taking into account the robustness constraints with respect to systems uncertainties. Indeed, it is simpler to get structured or fixed direction residuals that will increase the degree of robustness. Nevertheless, it is important to note that however there exists a minimal degree for the projection matrix (Nuninger, et al., 1 9 9 6 ) , i n p r a c t i c e t h e n u m e r i c implementation is not always possible. Indeed, because of inconsistencies, the exact solution Ω 3 (s) might not be found that satisfies the constraint (9). Therefore, suboptimal solutions should be performed in order to satisfy the independence of some state and unknown input components. Of course, this implies a degradation of the performance. On the contrary, the observer based method can be interesting using a generalised observer scheme.

Finally, both theorems can be applied to find, for a given residual based on parity space (observer) the corresponding design of the unknown input observer (parity space) that leads to the same residual: i.e. e(s)=r(s). Considering theorem 1, the special choice of T(s) equal to the identity matrix is obvious. On the contrary, the constraint on N and V 20 i s h a r d e r t o satisfy. Indeed, theses matrices are defined so that: C 2 (sI n -N)

-1 P sI n -A 1 ( )C 2 -= Ω 3 (s) (27)
With respect to the diagnostic procedure, the given theorems prove that an optimal solution does not always exists based on UIO whereas a solution can always be given based on parity space approach (Hyp. 4 true but not Hyp. 3). Therefore, parity space approach seems more convenient to achieve a higher degree of robustness. Note that this remark does not mean that this solution can not be found within UIO when such an observer exists.

CONCLUSION

This paper has focused the structural equivalence of residuals based on two a priori different methods using analytical redundancy: parity space and observers. This equivalence is well known in the literature but this paper considers the case of unknown input observer based residuals. This paper is the following of [START_REF] Nuninger | Observers and redundancy equations generation for systems with unknown inputs[END_REF] as the reciprocal theorem is given, proving that both residuals can be obtained from the other one, within little assumptions, thanks to their structural equivalence through a transfer function. The relevance of this work is that one can now conclude that the parity space approach seems to be the simplest way to take into account robustness constraints with respect to systems disturbances. Moreover, it is simpler to get the direct residual from the one based on the UIO (theorem 1) than the reciprocal that requires a more restrictive assumption on T(s) (theorem 2). In the future, the effect of model uncertainties on the two dual residuals should be discussed and compared within the structure of T(s), which is in fact a filter between both residuals. The aim is to stress on the statistical proprieties in order to emphasise which one of the dual residuals is the more valuable with respect to robustness. It is then obvious that the choice of the matrix T(s) is quite important in that matter.

  ) From (25), (20.a) is true with ϕ(s) = ζ(s)T(s) ♦

Fig. 2 :

 2 Fig. 2: Transfer law between direct and indirect residuals.