Arnaud Simon
email: arnaud.simon@dauphine.fr

Arbitrage models and mortgage options pricing

Keywords: real estate finance, arbitrage theory, pricing error, real options

In this paper we examine the applicability of arbitrage theory to real estate. Arbitrage theory has been applied to the valuation of mortgages using partial differential equations, however the implicit assumptions made are problematic when applied to real estate. The latter is a very complex financial asset, and for instance, for the case of default options, one could produce very large errors (even up to 100%) by applying -unwisely -conventional arbitrage theory techniques. The consequences of real estate appraisal are in this paper studied in particular.

Because one has encountered similar problems in real options theory as in real estate, the tools developed in that field could probably well adapt to real estate; we provide here an example. Finally the possibility of pricing contingent claims written on properties is discussed.

Introduction

For some years now, real estate and financial theory have become more and more interlinked.

The approach of applying the powerful tools developed in finance to real estate seems promising; mortgage valuation methods developed by [START_REF] Kau | A generalized valuation model for fixed-rate residential mortgages[END_REF] is a major example. That article applied arbitrage theory with two state variables (interest rate and a house process) to price a mortgage, which constitutes of a loan, a prepayment option and a default option. Some well-known arguments lead to a valuation PDE (partial differential equation) which is solved numerically.

The underlying assumptions of financial theory (for instance the absence of arbitrage opportunities) are clearly based on market reality. They are not purely formal or only useful to solve the mathematical problems that arise, they are leaning on the distinctive characteristics of the studied object. The purpose of this article is to re-examine the financial arbitrage models from the point of view of the specific features of real estate, in order to see if the requirements of arbitrage theory are entirely satisfied within this particular asset. This specific question can be aided by considering the case of real options theory, in which the utilisation of financial models was not initially straightforward.

The remainder of this paper is organized as follows. In the first section, the optional model for mortgage is presented in a detailed manner. After a literature review, the demonstration leading to the fundamental valuation PDE is reviewed, trying to be as explicit as possible whenever a market assumption is necessary. Section 2 goes back to the demonstration and examines the relevance of assumptions pointed out in Section 1. Does the riskless portfolio exist when dealing with real estate? Can real arbitrage activities exist and which assets could be chosen to build an actual arbitrage portfolio? These practical questions have direct consequences to the correct use of theory and to the validity of the PDE. Section 3 studies more specifically and more empirically one of the difficulties relating to the pricing of contingent claims on real estate, and tries to estimate the distribution of error. To this end a simplified reverse mortgage is presented and the impact of the appraisal accuracy (for the house associated to this contract) on the put option embedded in the mortgage is estimated.

Data provided by IPD-France are used for this purpose. The conclusion presents briefly other possibilities for a financial modelisation of real estate, more connected to the reality of real estate assets, and discusses the overall possibility of pricing contingent claims on properties.

Applying financial theory to real estate : Optional models for mortgage

2.1. Literature review MBS markets are an important field of investment in the United States. Mortgages entitled to individuals are grouped together, and representative bonds backed on this pool are sold to investors. This configuration gave rise to a lot of research on mortgage valuation because of the associated risks in the mortgage, namely the prepayment and default risks. Indeed, when mortgage rates drop, a wave of repayments arises, changing the financial characteristics of the MBS (mortgage proceeds are directly passed to bondholders, shortening the duration of their portfolios). This sensitivity to the rates led to a development of models using stochastic techniques 1 . We can mention among the first major contributions [START_REF] Dunn | Valuation of GNMA Mortgage-Backed Securities[END_REF], who chose to work with one state variable (a CIR process), whereas [START_REF] Schwartz | Prepayment and the valuation of Mortgage-Backed Securities[END_REF] chose two processes for the short and long term rates. In both cases the models gave a partial differential equation (PDE) which must be solved numerically, its complexity preventing a closed formula. Prepayment was described by using exogenous functions (a Poisson process in the first article, a proportional-hazard model in the second), which were calibrated on historical data and then incorporated into the PDE before its numerical implementation. Prepayment was not thought of as structural, it is not endogenous to the model. There was neither a house process in these first models which can be probably viewed as a gap as suggested by [START_REF] Downing | An empirical test of a two-factor mortgage valuation model : How much do house prices matter?[END_REF].

There exist two levels of analysis for mortgages, so called loan level and pool level; the articles mentioned previously were focused on the second one. The behavior of the MBS is probably harder to study because of the portfolio structure and the interactions between loans gathered in the pool. For the loan level, [START_REF] Titman | Valuing commercial mortgages: an empirical investigation of the contingent-claims approach to pricing risky debt[END_REF] is one of the first attempts.

But the numerous papers written by Kau, Keenan et al. are the reference for the valuation of mortgages considered as such and not as a part of a pool. We can mention their 1992 article for fixed-rate, and their 1993 for floating rate, while their 1995 survey is also a very interesting. The aim is to reach a sufficiently precise and flexible procedure for the numerical valuation of mortgages and of its components (prepayment and default options). To this end two processes are used, a CIR for the interest rate r and a geometric Brownian motion for the real estate value H. The mortgage is seen as a time-varying contingent claim relying on r and H, V(t, r, H) -the latter being the value of the mortgage -, and usual arbitrage theory is applied resulting to a PDE satisfied by V. Numerical results are obtained with a backward procedure, imposed by the forward looking behavior of borrowers in their exercise of the options. Calculations are made discretizing time and applying a finite difference algorithm on each interval with boundary conditions. [START_REF] Azevedo-Pereira | Numerical solution of a two state variable contingent claims mortgage valuation model[END_REF] provide a good presentation for the numerical details of this method. A crucial point in this model is the endogenous aspect of the option exercise, contrary to the first articles mentioned above.

Roughly speaking a prepayment occurs when refinancing mortgage rates are sufficiently low, and a default takes place when the borrower is in a situation of negative equity. It's no longer an exogenous treatment; the choice is analyzed into the structure of the model.

Thereafter, some improvements have been developed within this framework. Hilliard, Kau and Slawson (1998) produced a less cumbersome numerical procedure working with a bivariate binomial lattice. The default option had been split in two by [START_REF] Ambrose | Embedded options in the mortgage contract[END_REF] in order to analyze the behavior of deficient loans (default is not a one step process; it comprises two options, a right to stop making payments temporarily and a right to give up the property). [START_REF] Kelly | Time-varying mortgage prepayment penalties[END_REF] introduced the effect of prepayment penalties in the borrower decisions when they exercise. [START_REF] Stanton | Rational prepayment and the valuation of mortgage-backed securities[END_REF] improved the realism in the description of the borrowers' choices, assuming that they do not constantly reexamine their options but only at random moments, producing in the same time a convincing explanation for the burnout phenomenon. Option models had also been used as tools for pricing CMOs. For example [START_REF] Mcconnell | Rational prepayments and the valuation of collateralized mortgage obligations[END_REF], incorporating Stanton's ideas, have been able to find a price. [START_REF] Ambrose | A new spin on the Jumbo/Conforming loan rate differential[END_REF] explained a part of the spread between Jumbo loans and conforming loan, using these theoretical models and the higher volatility observed on high-priced houses. Azevedo-Pereira, Newton and[START_REF] Azevedo-Pereira | UK fixed rate repayment mortgage and mortgage indemnity valuation[END_REF]2003) fit this theory to specific mortgage products used in the UK. All these developments and adaptations have been integrated into the options framework without great difficulties, bringing to the fore the power and the applicability of this approach. See [START_REF] Kau | Frictions, heterogeneity and optimality in mortgage modeling[END_REF] for one of the latest version of these models.

The purpose of what follows is to present the standard no-arbitrage argument producing the well-known valuation PDE, for the specific situation studied here, with one rate process and one real estate process 2 . The financial assumptions needed to establish this PDE will be pointed out as explicitly as possible, and their validity will be re-examined in the next section, which relies on this theoretical and quite classical first part.

Market and notations

Economy is described by two state variables: a spot rate r and a value of real estate H. Usually r follows a CIR process, H is a geometric Brownian motion, however we won't specify here explicitly the dynamics, calculations will be done using general diffusion processes.

Under the objective probability we have: dr = µ r (t, r, H) dt + σ r (t, r, H) dz r = µ r dt + σ r dz r

(1)

dH = µ H (t, r, H) dt + σ H (t, r, H) dz H = µ H dt + σ H dz H (2) dz r dz H = ρ(t, r, H) dt = ρ dt
The drift for H doesn't include the service flow resulting from the possession of the house over time; it only describes the capital appreciation of the real estate.

A prepayment option, a default option or a mortgage taken in its whole (i.e. a loan with the two options) are contingent claims relying on time, r and H, denote it by V(t, r, H). We will assume, as is required by arbitrage theory, that V is perfectly tradable in a frictionless market.

That hypothesis is very strong but essential to get the PDE valuation.

V(t,r,H) depends on the two state variables and is a diffusion process too, and Itô lemma gives its dynamics :

dV = [ V t + µ r V r + µ H V H + ½ V rr σ r ² + ½ V HH σ H ² + V rH ρ σ r σ H ] dt + σ r V r dz r + σ H V H dz H
For simplicity we denote the drift DV (D for Dynkin)

Therefore dV = DV dt + σ r V r dz r + σ H V H dz H
Dividing by V dV /V = a dt + s r dz r + s H dz H Where a = DV / V s r = ( σ r V r ) / V and s H = ( σ H V H ) / V

In order to establish the PDE we have to select two particular assets V 1 (r,H,t) and V 2 (r,H,t), perfectly tradable in a frictionless market as well. They will serve as primary assets, allowing the construction of a riskless portfolio. With the same notation we have:

dV i /V i = a i dt + s i r dz r + s i H dz H i = 1, 2 (3)

2.3.Riskless portfolio and PDE

An investor chooses to build a portfolio, buying the securities V, V 1 and V 2 in quantities N, N 1 and N 2 . This idea is not purely formal; the portfolio must be practically possible.

We denote W his total wealth, W

= N V + N 1 V 1 + N 2 V 2 Differentiating dW = N dV + N 1 dV 1 + N 2 dV 2 = N V (a dt + s r dz r + s H dz H ) + N 1 V 1 (a 1 dt + s 1 r dz r + s 1 H dz H ) + N 2 V 2 (a 2 dt + s 2 r dz r + s 2 H dz H ) = ( NV a + N 1 V 1 a 1 + N 2 V 2 a 2 ) dt + ( NVs r + N 1 V 1 s 1 r + N 2 V 2 s 2 r ) dz r + ( NVs H + N 1 V 1 s 1 H + N 2 V 2 s 2 H ) dz H
If we can find N, N 1 , N 2 verifying:

NVs r + N 1 V 1 s 1 r + N 2 V 2 s 2 r = 0 (4) NVs H + N 1 V 1 s 1 H + N 2 V 2 s 2 H = 0
the corresponding portfolio will be riskless and its drift, using the no-arbitrage assumption, will be : r W.

For example if s 1 r s 2 H -s 1 H s 2 r is different from zero, for each value of N we can find N 1 and N 2 solving this system. As this portfolio is riskless we can then assert that ( N, N 1 , N 2 ) is also a solution for the following system :

NV a + N 1 V 1 a 1 + N 2 V 2 a 2 = r W NVs r + N 1 V 1 s 1 r + N 2 V 2 s 2 r = 0 (5) NVs H + N 1 V 1 s 1 H + N 2 V 2 s 2 H = 0 Writing W = N V + N 1 V 1 + N 2 V 2 , we get: NV(a -r) + N 1 V 1 (a 1 -r) + N 2 V 2 (a 2 -r) = 0 NV s r + N 1 V 1 s 1 r + N 2 V 2 s 2 r = 0 NV s H + N 1 V 1 s 1 H + N 2 V 2 s 2 H = 0
The initial wealth W not being zero ( N, N 1 , N 2 ) cannot be the null vector. As the above system admits a non trivial solution its determinant must be zero. Transposing it, it gives:

a-r s r s H a 1 -r s 1 r s 1 H = 0 a 2 -r s 2 r s 2 H
The rules of linear algebra imply, then, a linear dependence relation between the columns. For instance the first one can be written as a combination of the second and the third.

In others words, there exist λ 1 = λ 1 (t, r, H) , λ 2 = λ 2 (t, r, H) such that :

a -r = λ 1 s r + λ 2 s H a 1 -r = λ 1 s 1 r + λ 2 s 1 H (6) a 2 -r = λ 1 s 2 r + λ 2 s 2 H
The two last equations are not depending on the features of V, therefore by requiring that s 1 r s 2 H -s 1 H s 2 r is different from zero we can express λ 1 , λ 2 independently of V. The fact that these quantities are the same for all assets V(t,r,H) is a major result and will lead directly to the notion of market price of the two sources of risk, as reviewed in appendix.

Regarding the first equation, it gives the PDE:

a -r = λ 1 s r + λ 2 s H DV -rV = λ 1 σ r V r + λ 2 σ H V H
Replacing DV with its expression:

V t + µ r V r +µ H V H + ½V rr σ r ² + ½V HH σ H ² + V rH ρσ r σ H -rV = λ 1 σ r V r + λ 2 σ H V H
Rearranging it, V(t, r, H) is thus a solution of the following PDE :

V t + (µ r -λ 1 σ r ) V r + (µ H -λ 2 σ H ) V H + ½ V rr σ r ² + ½ V HH σ H ² + V rH ρ σ r σ H = rV (7)
Thereafter, the usual arguments of financial theory give the interpretation of λ 1 and λ 2 (market prices for the rate risk and the house risk), Girsanov theorem and the Q-measure provide the final formulation of the PDE. The rest of the procedure can be found in the appendix.

2.4.Summing-up

For a contingent claim V( t, r ,H ), depending on state variables r and H we can calculate the no-arbitrage price solving the following PDE :

V t + (µ r -λ 1 σ r ) V r + ( rH -δ(H)H ) V H + ½ V rr σ r ² + ½ V HH σ H ² + V rH ρ σ r σ H = rV (8)
Where:

µ r -λ 1 σ r equals the drift of r under the risk neutral measure Q. Usually the dynamic of r under Q is described using a CIR process ( dr = γ ( θ -r ) dt + σ r r 1/2 dž r ), so µ r -λ 1 σ r must be replaced with γ ( θ -r ) in the equation δ(H) is the service flow coming from the house, usually assumed constant σ r , σ H , ρ are the volatilities and the correlation for r and H under both measure Very often V is a prepayment or a default option. Numerical solutions are calculated using backward procedure and finite difference methods specifying some boundary conditions (see [START_REF] Azevedo-Pereira | Numerical solution of a two state variable contingent claims mortgage valuation model[END_REF] for more details).

From practice to theory

The previous demonstration ends up to equation ( 8). It is of course a mathematical object but the strong assumptions made during the process are primarily financial. After this technical step we are going to question these hypotheses in the light of the real estate markets. If they are not empirically verified, the mathematical demonstration, as sophisticated as it may be, will only produce an abstract and biased formula.

3.1.The no-arbitrage assumption

The main result established above is the possibility of valuing an option embedded in a loan, secured by a real estate, using numerical methods for PDE. This fair price is a consequence of a market mechanism, formalised by the no-arbitrage assumption. Indeed, at any moment, if V(t, r, H) moves away from the theoretical value, it would imply the existence of an arbitrage opportunity. Arbitrageurs would then take advantage of the situation and the attempts to realize the potential benefits would bring back V to its theoretical level.

In the real world, bankers are not spending all their time solving PDEs and the job of traders is not the application of finite difference methods. The no-arbitrage assumption must be understood as an indirect result of the market activity. If someone detects a local inefficiency, he will act to take advantage of it, but in the majority of times this will be done without the use of mathematics. For example if the exchange rate is 0.6$ for 1€ in a market and at the same time 1€ is valued 1.4$ on another market, one does not need to solve a PDE to earn a lot of money. On the total market scale the actions of all participants lead to the noarbitrage assumption; this hypothesis is supported by an actual and concrete activity. It allows us to assert that a riskless portfolio will have a return equal to the riskless rate, and it produces the valuation equation 3 . The PDE is then an indirect consequence of the local arbitrages realised by the market participants and for it to be valid some precise and important conditions must be fulfilled.

3.2.Real estate markets

Certainly the stock market operates in a way that is much closer to the assumptions of arbitrage theory than the real estate market. Usually, when studying a problem, the first approach takes an ideal situation in order to establish closed and quite simple formulas, while further approaches refine -and possibly change -the initial hypotheses in order to achieve a more realistic description. For instance the Black-Scholes formula had been initially established assuming constant volatility, thereafter this assumption had been relaxed (for example [START_REF] Heston | A closed-form solution for options with stochastic volatility with applications to bond and currency options[END_REF]. Nevertheless the foundations of the arguments were maintained and the situation remained to a great extent unchanged.

For real estate this stage of improving on the initial simple assumptions is not at all straightforward. Problems can arise and a blind application of conventional techniques can produce misleading results. For example we saw previously that the PDE relies on taking action of the opportunities of arbitrage, and that it is not just an abstract hypothesis. Consider the case of a prepayment option, the previous argument would mean that there actually exist people that are realising the arbitrage opportunities between V 1 , V 2 and the prepayment option. These traders should buy or sell houses, lend or borrow, in order to make money with the small inefficiencies in the mortgage contracts. Of course it is an unrealistic situation and this kind of actions does not take place. Options embedded in mortgage contracts have prices which depend more on competition between lenders rather than on hypothetical arbitrages.

The arbitrage activity required in theory is thus absent for a prepayment option.

The arbitrage based modelling also assumes implicitly that assets can be isolated and priced separately. However for residential loans it is not always as easy as it seems because of the cross-selling problem. For investors this matter does not exist when the mortgages are securitized in an SPV, since the only proceeds they will receive will be the passed monthly payments, and the pool will be in a "situation of isolation". But when a bank chooses to keep the loans in its balance sheet this assumption of isolation becomes questionable. In France for example, residential loans are essentially loss makers; expected earnings for lenders are not only coming from the contract. They also come from other financial products that the bank can sell to its customers, as for example a current account or a consumer credit, taking advantage of the privileged relationship established between lender and borrower during the loan process. Thus if a bank tries to value a mortgage using the PDE, cash flows should be modified in order to take into account the other indirect earnings 4 . The problem will then be to find a precise valuation method for these "blurred" expected proceeds.

The use of SPV or other isolation techniques such as covered bonds makes easier the financial study of the mortgage; interferences with other asset classes are low or even nonexisting in the perfectly isolated cases. But in both cases, the portfolio structure must also be examined for the mortgages class. The interactions between the mortgages inside the SPV or inside the balance sheet and their possible correlations are also a matter of importance.

Summing up, prepayment option can sometimes be a commercial problem rather than a financial one, assets are never isolated and real arbitrages are non-existent. This questions the validity of the arbitrage pricing. In the following three paragraphs we will see precisely where the difficulties are in the actions (required by theory) of taking advantage of the arbitrage opportunities, for the benchmark assets V 1 and V 2 as for the contingent claim V.

3.3.Asset associated with the rate risk

In the first section, V 1 indicated a time-varying asset relying only on r; it was the money market account. Interest rate products are sufficiently standardised, negotiated and liquid.

Thus we can reasonably consider V 1 as a perfectly tradable asset in a frictionless market; it can be bought or sold without any limitations. Building an arbitrage strategy based on lending or borrowing money is not a problem. Of course one needs to make a choice on the specific model for the risk neutral process for r. Which should be used between Vasicek, CIR or Hull-White? However this question is not specific to the problem examined here. Since there already exists an established theory for the pricing of interest rate products; we are going here to utilise its results, not questioning further its validity.

3.4.Housing benchmark

In the arguing made in the previous section, V 2 was not specified explicitly and mathematically we could choose a quite complex asset depending on t, r and H : V 2 = V 2 (t, r, H). The only thing we needed to ensure to solve system (4) was that s 1 r s 2 H -s 1 H s 2 r was different from zero, and that condition is not a very demanding one. Among all possible choices, there are some that are better than others in the sense of them providing better intuition. Since V 1 is a benchmark for r, V 2 should also be a benchmark for H. Interpretation would be greatly facilitated by V 2 = V 2 (t, H)

The most natural choice for V 2 is H * itself (the value of the house securing the loan), and as H * is a tradable asset, we could apply the theoretical results easily. Indeed, in arbitrage theory when a state variable is not traded, problems can arise. For example models with stochastic volatility introduce difficulties because of the impossibility of trading directly the volatility for hedging a portfolio. Thus V 2 = H * should be preferable for modelling. However, in this case also, one can have objections stemming from the feasibility of financial operations. The latter should be possible practically and not only in a perfect world (as described by arbitrage theory).

A first difference with the theoretic situation comes from the uniqueness of the house. If someone tries to build an arbitrage, on a prepayment option, he cannot own the specific house associated to the mortgage because it is already the borrower's ownership. He can only try to build his riskless portfolio with a similar real estate, adding, unfortunately, a risk of imperfect replication. Houses cannot be substituted one with another as two stocks can. A second problem may occur if the strategy implies the sell of a house. If our hypothetical trader does not have it already in his portfolio, it can be difficult to take a short position on a house. And last but not least, H * is unknown until the sale completion. Property prices are not quoted as stocks, the price of a real estate is only revealed in a transaction. It is very far from the "prefect" financial situation assumed by arbitrage theory, making the construction of a riskless portfolio practically impossible. Several articles written by [START_REF] Childs | Valuation and information acquisition policy for claims written on noisy real assets[END_REF]Childs et al. ( -2002Childs et al. ( -2002[START_REF] Childs | Effects of noise on optimal exercise decisions: the case of risky debt secured by renewable lease income[END_REF] deal with this problem, analysing H * as a noisy asset, as for example in real options theory. Considering H * as financial asset would bring out the appraisal problem. As the right price cannot be known without a transaction, the only means to carry out a financial analysis is by forming an estimation; its quality becoming then a central point. Usually estimation is considered correct when the spread between the real price and the estimated price is less than 10%. We will see later what can the consequences be of the appraisal problem on a pricing example. Therefore a rather natural choice for V 2 is strongly rejected for purely practical reasons.

Another possibility for V 2 could be a REIT stock. This provides an important improvement compared to the previous choice, namely the liquidity. These assets can be bought or sold very easily and prices are known at every time. Nevertheless there are always important difficulties. For example which REIT is the more appropriate? In addition, REITs are usually correlated with other stocks in the market, resulting to the introduction of additional (market) risk. In terms of the model developed here, it means the introduction of a third Brownian motion, complicating the building of riskless portfolio. Theoretically two benchmark assets with three random sources do not allow the building of a risk-neutral portfolio whatever the combination of V 1 and V 2. In other words, an interesting and practical choice for V 2 leads to a mathematical problem.

Finally the last possibility we are going to consider for V 2 is an index (for instance a price/m² on a determined area for residential property). The liquidity problem appears here also because an index is not a directly tradable asset. If the requirements for hedging or for building a risk-neutral portfolio include a purchase of only 3m² (three times the index) of residential property in Paris, they could be hard to realise. However a natural and interesting way to achieve this could be the use of an index derivative. It would suppose a quite mature and liquid market for such products, but at the present time it is not a reality. A possible future development of the market for index derivatives could lead to a greater use of arbitrage theory in real estate, which is certainly a promising possibility.

In conclusion, the choice of V 2 is not obvious. The financial features of a house are not in good agreement with the requirements of arbitrage theory, REIT stocks bring another random source and the indexes are not enough developed. It seems rather inappropriate not to take this reality into account when using theoretical models.

3.5.Contingent claim V

PDEs are essentially applied to prepayment and default options. Once more it means that these assets are perfectly tradable in a frictionless market and unfortunately, in this case too, reality is far from this. We saw before that traders cannot take advantage of possible arbitrage opportunities on these options, resulting in their prices being defined more by bank policies than by market actions. Nevertheless, if someone wanted to take advantage of a hypothetic arbitrage opportunity, s/he will be faced with another practical difficulty coming from the insufficient financial features of these options. To be specific, these options are embedded in the mortgages. It is therefore impossible to own or to sell an option separately from the loan.

The consequences of this concern system (4). A riskless portfolio requires the finding of integers N, N 1 , N 2 making the random contributions of the two Brownian motions zero. A mathematical solution could perfectly be N 1 = N 2 = 1 and N = 4; one unit of the two benchmarks assets and four units of a prepayment option. Who could sell separately these four options? If one tries to buy them indirectly, by signing into four mortgages, s/he would result in adding others risks linked to the loans; consequently it would no longer be a riskless portfolio. A mathematical arbitrage opportunity is not always a financial one since the options are not isolated securities.

3.6.Validity of the PDE

Real estate is not as smooth a financial product as stocks. Its peculiarity is illustrated by the inability of traders to take advantage of possible arbitrage opportunities. However the problem is not actually produced by this inability, it is really the reasons behind the inability that are responsible. The reason why arbitrage activity in real estate is scarce, is mostly because it is practically very problematic to construct a riskless portfolio. Among the reasons for such practical problems one can mention the uniqueness of house, the impossibility of being short on a real estate, the price uncertainty until a real transaction is made, the introduction of market risk by the use of REIT, the underdevelopment of index derivative markets and the implicit nature of options that cannot be traded on their own.

The modelisation developed in section 1 ends up with a valuation PDE which can be implemented using numerical procedures. It is a very powerful result but fundamentally it assumes some very strong conditions on the securities under study. In a sufficiently well developed, mature, liquid and frictionless market (in other words in a "perfect" financial market) the no-arbitrage assumption is acceptable. This assumption is the core of the model and it allows us to assert that a riskless portfolio must give a return of r ( 5), producing finally the equation ( 7). In this section we have just seen the situation in the real estate market is far from this. The imperfections involved are not secondary difficulties which could be resolved by slightly changing the assumptions, as it was done with stochastic volatility models. The imperfections here question the model on the whole, and ultimately, the accuracy and validity of the final PDE. The modelling is not sufficiently linked to real estate particularities, and a direct application of arbitrage theory, originally built for "perfect" financial products such as stocks, can produce misleading valuations.

Example of a misleading pricing

Among the difficulties previously mentioned, we are going to elaborate on one of them;

namely the difference between the right price and the estimated price. The aim is to arrive at having an idea on the error of pricing for contingent claims written on real estates. In particular we will examine a simplified version, namely the put option embedded in a reverse mortgage.

4.1.Asset description

Recently a report [START_REF] Jachiet | Rapport sur le prêt viager hypothécaire et la mobilisation de l'actif résidentiel des personnes âgées[END_REF]) ordered by the French government has studied the possibility to create, in France, products that make easier the availability of residential equity that has accumulated in elderly persons' houses. These assets are already known in UK as lifetime mortgages and in the US as reverse mortgages; they are examples of the home equity loans family (loans granted for consumption and warranted by real estate). In France this type of product, named "crédit hypothécaire", is scarce, but there exist governmental projects aiming at creating and developing this possibility (the "prêt viager hypothécaire", which translates to "reverse mortgage").

The principle of the contract is as follows: At the origination the lender provides the borrower with certain amount. During the following years interests are added to the initial amount lent, without any repayments required from the borrower. At the event of death of the borrower, the house warranting the loan is sold and the bank is repaid. Two situations can then occur: the sale price is higher or lower than the accumulated debt. In the former situation the difference goes to the heirs of the borrower, and in the latter, a clause included in the initial contact limits the bank's rights to repayment up to the house's sale price. This creates a situation where the bank has effectively shorted a put option on the value of the house. The major risks concern the life expectancy and the final house price, it is a contingent claim depending on r and H 5 : V(t, r, H). The purpose here will not be to examine rigorously all the features of this loan and to calculate the right price of such a contract 6 . We are going to work on a simplified version, in order to understand the consequences for the pricing of the put option and the mortgage, of the fact that the value of the real estate is not explicitly known.

Indeed, at the beginning, H * is not known directly as long as the house is not sold, giving rise to an error in the estimation of the house value, which leads directly to a mispricing for the assets relying on H * . Accurate estimations are always have always been and continue to be important for real estate finance.

4.2.Simplified contract and environment

Let us assume that at t = 0, the lender pays K to the householder. Interest is accruing continuously at a fixed annual rate r, and, for simplification, let us assume that the rates curve is flat and does not change with time. We assume further that the contract is executed at a fixed date T corresponding to the life expectancy of the borrower (for example ten years).

Notice here that this view is not very realistic, but it avoids the complications of working with what is called a stopping time, associated with the random time of death of the borrower.

Moreover a fixed maturity allows the use of a closed formula for the price of a European put option.

At t = T, the lent capital has produced a debt of Ke rT = K' , however this amount is capped at H(T), so the final payoff for the bank is :

Min ( K' ; H(T) ) = K' -max ( 0, K' -H(T) )
In other words, the bank's portfolio contains a loan and a short position on a put. This option is European, written on H, with maturity T and strike of K'.

We assume that the dynamics of H are given by a geometric Brownian motion :

dH = µH dt + σH dz
Hence we can use the Black-Scholes formula to value this position. At t = 0, as e -rT K' = K the worth of the portfolio is:

K -( e -rT K' N(-d 2 ) -H(0) N(-d1) ) = K -Put(0)
Where :

d 1 = { ln( H(0) / K' ) + (r + σ²/2) T } / σ T 1/2 and d 2 = d 1 -σ T 1/2
(N being the standard normal distribution function)

Uncertainty in this formula enters with the term H(0), since the real value cannot be observed exactly without a sales transaction. The next calculation is made assuming that H(0) is known, hance we can get the true prices of the contingent claims.

Choice of parameters:

-H(0) = 100 000 (real price of the house) -K' = Ke rT = 115410,49 -T = 10 years 7 -µ = 2% 8 -K = 70 000 -σ = 15% 9 -r = 5%

At T, the final debt will be K' = 115410,49 and if σ = 0, the final value of the house will be H(0) e µT = 122140,28. In the absence of uncertainty the debt would not exceed the value of the sale, and the heirs of the borrower would receive the difference. If σ ≠ 0, the Black-Scholes formula is applied, and in this situation of full information the true put value is Put(0)

= 5101,92. The mortgage price is 70 000 -Put(0) = 64898,08.

It must be noticed that the calculation of Put(0) implicitly assumes that the arbitrage assumptions made in the Black-Scholes formula are valid in the case of a real estate derivative. In particular that the riskless portfolio exists and traders are able to take advantage of arbitrage opportunities (we saw previously what the problems are in making such assertions). Here, the aim being to examine the consequences of one of these problems, namely the price uncertainty on H(0), the options will be priced assuming that real estates are perfectly tradable in a frictionless market. We will work as if the difficulty with the appraisal was the only remaining imperfection. We could hope that with such a nearly "perfect" context things would go quite well, but unfortunately this uncertainty on H(0) makes, on its own, the pricing very problematical.

4.3.Incomplete information

For an appraiser, the estimation of H(0) can be considered correct if the error stays within a 10% interval of the real price. This accuracy is very reasonable when valuing such a complicated asset as a house, but unfortunately even such a good appraisal is going to produce a bad pricing for the put option. For example, if the house is valued at the origination with H (0) = 95 000, the price calculated for P(0) will be Put (0) = 5975,75. The option price will be overestimated by 17% and the mortgage value will be underestimated by 1,3%

(estimated price = 64024,25). If the estimation gives H(0) = 110 000, we will have P(0) = 3722,78 (-27%) and a mortgage value of 66277,22 ( +2,1%).

Let us now do a more detail analysis in order to reach a better understanding of the phenomenon of such large percentage errors. The method developed thereafter does not aim at producing perfect estimations, it is rather rough and can admit a lot of improvements . The purpose is only to measure the size of the error when valuing the put. Let us assume that the percentage error on the estimated price is distributed according to a normal law N(m,s). The actual mean m is not necessarily 0 since there can exist a positive or negative bias. Drawing a sample {e i } distributed as described, we can then build a sample of estimated prices { h i = H(0) ( 1+ e i ) } 10 . For each h i , the estimated option and mortgage prices can be calculated using a basic pricer. The differences between these values and the real ones provide two series, which we name put_error and mortgage_error, whose density can be represented using a kernel method. 11 For example, with m = 0 and s = 0,1 we obtain the empirical distributions of the Figures 1,2 and 3.

For this choice of parameters, the probability of having an error between -15% and +15%

on the estimated house price is around 0,87. This type of situation is not at all unrealistic.

However the probability of the event { |put_error| ≥ 40%} is near 20%, which means that on average every five estimations the put option is completely mispriced (the error is more than 40%). The noise on P(0) is an amplification of the noise on the pricing of H(0).

The mortgage comprises a put option whose real price is around 5000 and a loan valued 70000. Uncertainty exists only on the first part, and considering the relative sizes of these two components, the distribution of error becomes necessarily tighter. For instance, the event {|mortgage_error| ≥ 5%} has a probability of around 6%. However this -not bad -pricing is more a consequence of a size effect rather than a well performing valuation methodology. The noise shrinks with the inclusion of the non-random component.

With a choice of m = 0 and s = 0.01, we have P( |put_error| ≥ 5% ) ≈ 11%. It could be considered as a reasonable pricing, but in order to achieve it, the accuracy of the house estimation should be very high, since the same parameters imply that P( |house error| ≤ 2% ) = 95 %. In other words the appraisal in this case is quite always very effective; needless to say that such a situation hardly occurs in reality.

4.4.Error on P(0) when using real data

IPD-France publishes annually a property index, based on a set of real estate portfolios, highly representative of the total market. Appraisal is a central point for the reliability of this index since the majority of the assets are not sold each year. The quality of the assessments made by the experts becomes a matter of importance and it is studied in particular. Figure 4 shows the improvements in the appraisal quality, by showing the distribution of the spreads between valued and real prices when a sale is effectively realized soon afterwards the estimation.

Means and standard deviations can be roughly estimated with this histogram. For illustration the 27% that appears on the left axis and corresponds to the [0%;10%] interval for the year 1998, can be assigned the meaning of a 27% of the appraisals having been underestimated by 5% on that year. We use the value of the mid of each interval (in our example the [0%;10%] interval), hence the 5%. Results are in Table 1 where we can see that there exists a slight trend to overestimate (negative mean). But the most important and notable characteristic is that the variance of the estimation is decreasing year by year, implying that estimations have greatly improved.

Assuming that the distributions are normal 12 with the parameters stated on table 1, we can use the same methodology as in the previous section. A sample is drawn from each year's distribution, and subsequently one can obtain the estimation for the house {h i }, from which the put price is calculated with the Black-Scholes formula. Error on P(0) is measured for each house value and the shape of its distribution is obtained with a kernel density method. Summing up, a financial approach of real estates brings the quality of appraisal at a central place. However for some claims as options the noise effect prevents a traditional pricing. This difficulty seems to be rather important, since P( |put_error| ≥ 5% ) ≈ 11% is associated as mentioned earlier with P( |house error| ≤ 2% ) = 95 %. In other words, the put price is correctly determined only if there is almost no appraisal error. Good quality of appraisal is not a guarantee for precise pricing, particularly for leveraged assets as options.

More generally, the usage of very sophisticated methods such as PDEs does not guarantee an equal standard of pricing accuracy, in this case the sophistication of methodology is rather disproportional to the quality of results. A rough estimation of the prepayment option, for example 3% of the remaining capital balance, is of course inexact, but it is not obvious that the PDE estimation is better. What's more, the former price is very simply obtained (because it is determined by experience), while the latter is not at all, and that is obvious. In a costs / benefits analysis, the PDE estimation is not fully convincing.

Synthesis and conclusion

We saw that arbitrage assumptions are not satisfied when dealing with real estates; the most salient of difficulties being the assumption of the existence of a riskless portfolio, and the possibility of taking advantage of the theoretical arbitrage opportunities. The reality seems to be far from the arbitrage paradigm when dealing with that kind of assets. Consequently the validity of the valuations based on a PDE is not obvious; in section 3 we saw that the error could easily be very significant for a put option. A rough estimation of the options prices is maybe as good as the very complicated and not fully convincing method in a costs/benefits view.

This paper could be seen as a part of a more general topic, concerning the validity of real options. Options are a very powerful tool for the stock and the interest rates markets. This success has led numerous attempts to expand the concepts to other asset classes, however the transposition is not always straightforward and without risks. All the implicit assumptions must be re-examined rigorously before being applied to a less "pure" financial field. Because a blind application of the concepts could result in biased pricings, the extension must be conducted carefully and step by step. Examples of these problems can be found in Lautier (2002a and2002b) or [START_REF]New Boundaries to Real Options Valuation? Exploratory Research Based on a Case Study[END_REF]. [START_REF] Childs | Valuation and information acquisition policy for claims written on noisy real assets[END_REF]Childs et al. ( -2002Childs et al. ( -2002[START_REF] Childs | Effects of noise on optimal exercise decisions: the case of risky debt secured by renewable lease income[END_REF] Once this is done Childs et al price an option on a noisy asset x(t) with a version of Black-Scholes formula but using m(t) as underlying. Unfortunately, the same concerns discussed above for the PDE could be raised for this pricing methodology. m(t) is not a tradable asset contrary to the stock in the Black-Scholes world. Moreover, at maturity the payoff is not m(T), but x(T), making the construction of a riskless portfolio difficult, which puts the validity of the pricing formula under question. Similarly, for t < T, m(t) is an optimal appraisal price, it is not the real price needed to build an actual arbitrage portfolio. In Childs et al, a pricing formula is not really the aim, the analysis rather stresses the importance of information, comparing the costs and the benefits. Indeed, as the acquisition of information is costly, it is necessary to estimate its usefulness. This framework is more intended to be an analysis of economical choices rather than a financial pricing, and this shifting is not really surprising. Investors will decide exogenously for the premium associated to the risk generated by the noise around the valuation. In other words, if they think that it can be sufficiently valuable to acquire information they will proceed for it. But this decision relies on their appetite for risk, and on their personal valuation of the costs associated with this uncertainty.

It is an economical choice. The problem of valuation of real options can be dealt with financial theory, but the issue of the usefulness of information cannot be ignored.

Fundamentally real estate markets are incomplete, in the sense that all possible portfolio positions are not attainable. For example if someone owns a specific house with a specific service flow, a hypothetical trader wishing to arbitrate on a prepayment option could not include exactly this particular house in his portfolio, because of its uniqueness. In addition to this physical incompleteness, there exists an informational incompleteness coming from the appraisal problem. How could be constituted a portfolio relying on H(t) if this value in unknown? Theory says that in incomplete markets it does not exist a single no-arbitrage price but only an interval of prices compatible with this no-arbitrage assumption. As far as it concerns the noise issue things can be understood heuristically. If there exist noise on H it would be surprising to obtain an exact formula for V(t, r, H); dispersion in figure 1 for H(0) leads to a dispersion in figure 3 for P(0). This price interval represents the economical freedom associated with the noise risk and the possibility for each agent to price this uncertainty according to his own preferences.

The specific features of real estates make the pricing of contingent claims uneasy.

Properties are strongly segmented and this lack of a global and uniform market prevents a purely financial approach. Real estate is not a partitive asset, in the sense that you cannot buy "some" real estate as you can buy some sugar. In a financial market one can buy some IBM (stock), some oil, or some bond treasury, nearly perfectly assimilated with another stock, another barrel or another bond. The uniqueness of houses hinders this financial view and, in a way, real estate markets do not exist; we can only speak of multiple local markets each one with its particularities. This situation is very far from the assumptions used in the financial models and the lack of a product globally traded, linked to the real estates, is probably one of the major obstacles to a purely financial approach. A solution could be in a reversal of this situation. Instead of viewing the real estate as the underlying asset, the primary asset could be a property index or a derivative on this index. If such a market becomes sufficiently well developed it could provide a price for "some" real estate, making easier a financial pricing for contingent claims. .000

.002

.004

.006

.008

.010

-100 0 100 200 300 400 500 600

.000

.002

.004

.006

.008

.010

-100 0 100 200 300 400 500 600

Figure 7: distribution of put_error_2000 (%) Figure 8: distribution of put_error_2001 (%)

.000

.002

.004

.006

.008

.010

-100 0 100 200 300 400 500 600

.000

.002

.004

.006

.008

.010

-100 0 100 200 300 400 500 600 .000

.002

.004

.006

.008

.010

-100 0 100 200 300 400 500 600

.000

.002

.004

.006

.008

.010

-100 0 100 200 300 400 500 600

  10 present the results for the years 1998 to 2003.13 The increase of the accuracy relating to the estimation of H(0) produces a tightening of the distribution around 0, in other words the put price is valued more accurately. This improvement is very significant when comparing for example figure 5 and figure9; in the first case the error could sometimes be as large as 500%, and in the second it stays mostly under 100%. Having said that, even if in 1998 the situation was as bad as not being able to reasonably determine the put value, in 2002 and 2003 it still remains a difficult task. The noise on P(0) is always amplified compared to the noise on H(0); the usual leverage effect of the option brings about a very unpleasant consequence, acting as a noise amplifier. If we had studied directly a pool of mortgages, the global appraisal noise would have been lower, but unfortunately what we could have got on one side would have been lost on another. Indeed, a modelisation of the correlations is required when analysing a portfolio, and the choice of a geometric Brownian motion for H becomes then much more problematic.

Figure 4 :

 4 Figure 4: difference between sale price and estimation 1998-2003, Source IPD-France 13

Figure 9 :

 9 Figure 9: distribution of put_error_2002 (%) Figure 10: distribution of put_error_2003 (%)

  have provided interesting concepts, well adapted to the real estate specificities, and allowing to handle the uncertainty on H(0) (they employ the term "noisy asset", coming from real options theory in this situation). The tools they have developed can be used in the management of research and development projects, for the exploitation of corporate assets as mines, and for real estates. A common point between these fields is the ignorance of the exact prices unless an irreversible action is undertaken (beginning of the production or the exploitation, or sale completion). The principles of the modelisation are as follows: The real price process x(t) is unknown for investors because of a noise process y(t). The only thing that can be observed is a noisy estimation z(t) of the true

value x(t) , the relation can be for instance z(t) = x(t) + y(t) or z(t) = x(t) y(t). At any time t, the available information is represented by a filtration {I(t)}, and investors estimate x(t) given this filtration, by m(t) = E [x(t) | I(t)] . This value m(t) is an appraisal value conditional on all the relevant information (for instance sale prices for similar real estate), and is named the time-filtered asset value. Subsequently using Lipster and Shiryayev differential equations, the dynamic of m(t) can be expressed with the parameters present in the dynamics of x(t) and y(t).

Table 1 :

 1 Estimation of mean and standard deviation for the distributions of Figure4

		1998	1999	2000	2001	2002	2003
	Mean	-0.070 -0.010 -0.028 -0.018	0.009	-0.005
	Standard deviation 0.354	0.232	0.247	0.201	0.151	0.148

Interpretation of λ 1

There are choices more natural than others for the two benchmark assets; namely V 1 which only depends on r, and V 2 which only depends on H (for example V 1 could be the money market account, H could be V 2 , but subject to the inclusion of the service flow produced by the real estate during its holding period). With such a choice, the mathematical formula becomes simpler and the interpretation easier.

As we have V 1 H = s 1 H = 0 and V 2 r = s 2 r = 0 system (4) becomes:

And the last two equations in (6) are now:

Which means that :

For any asset only relying on t and r, the first equation in (6) gives :

a -r = λ 1 s r hence :

These two quotients represent the market price, per unit of volatility, for the risks associated with the assets V(t, r) and V 1 . The dynamics of V(t, r) and V 1 (t, r) are dV/V = a dt + s r dz r and dV 1 /V 1 = a 1 dt + s 1 r dz r ; (a -r) and (a 1 -r) are the risk premiums and s r , s 1 r the corresponding volatilities. This equation establishes that the risk price is always the same, whatever the asset (if the latter relies only on t and r); it is a relation of internal coherence following from the no-arbitrage assumption. λ 1 is an exogenous process, it is determined by the market, and once its price is known the drift of any asset V (t, r) is a = r + λ 1 s r (the riskless rate increased by the risk contribution coming from the volatility).

Risk neutrality

Dynamic of r is : dr = µ r dt + σ r dz r

Introducing λ 1 : dr = ( µ r -λ 1 σ r ) dt + σ r ( dz r + λ 1 dt )

The same for H :

Assuming that λ 1 and λ 2 are known, we can use multidimensional Girsanov theorem. There exists a measure Q under which dynamics of r and H are:

And, since V is a solution of the PDE:

in which the terms in front of V r and V H are, this time, the same as the drift for the dynamics of r and H under Q. We can then apply Feynman-Kac theorem obtaining the fundamental formula:

for t ≤ T, integral between t and T Actualised price of perfectly tradable assets are martingales under Q.

H is a tradable asset, interpretation of λ 2

The real estate (physical house and service flow) can be bought and sold. If we consider it can be traded in a perfect and frictionless market, its value is then determined by a PDE solution.

Let us note H * the house process including these "dividends", we have: The left hand side is the instantaneous return under the objective measure, associated with the owning of H * , the equality splits this quantity in a riskless part, rH, and λ 2 σ H . λ 2 is then the risk premium per unit of volatility for H and more generally for all the assets only relying on H. It's the market price for the house risk.

1 Stochastic calculus and arbitrage theory are, since the 70's, a very powerful tool to deal with uncertainty in finance. Pioneers were Black and Scholes (1973) and [START_REF] Merton | Optimum consumption and portfolio rules in a continuous time model[END_REF][START_REF] Merton | Theory of rational option pricing[END_REF] with their works on options pricing and optimal rules for consumption and investment. Diffusion processes allow handling easily expected returns and risk premiums in a continuous way, giving a rigorous framework for uncertainty.

2 There exist numerous books dealing with arbitrage theory, we can refer for instance the Björk's, published by Oxford University Press: "Arbitrage theory in continuous time". 3 This assumption is used when we get (5) from ( 4) 4 Securitization is strongly developed in Anglo-Saxon countries, partly explaining the greater success and the greater use of the models presented above since the isolation hypothesis is quite realistic. 5 Here, H represents the real house price process 6 It would require the use of an American option and the modelisation of the death of the borrower as a stopping time. The tools coming from life insurance would be relevant to this end. 7 Coherent with what is observed in the countries where the reverse mortgages exists. People subscribing are around 70 years old, a life expectation of 10 years is reasonable particularly for women 8 µ isn't useful in the calculations of P(0). It's well known that options prices are independent of the drift; the only thing that matters in the dynamic of H for P(0) is the volatility.

9 Coherent with the volatility estimated by [START_REF] Ambrose | A new spin on the Jumbo/Conforming loan rate differential[END_REF].

10 If h i < 0, h i is replaced with 0.

11 The size of the sample is chosen at 1000 to achieve a sufficient level of smoothing.

12 This hypothesis is probably doubtful but here the matter is only to study the consequences of a decreasing in volatility on P(0). 13 Observing the graphs we can notice that the probability of having an error on P(0) inferior to -100% is not null; it means that the option prices can be negative. This imperfection in the distribution comes from the kernel method; a better estimation would truncate this part.


Hugo Gimbert
email: hugo.gimbert@cnrs.fr

Rasmus Ibsen-Jensen

Cristian S Calude

Sanjay Jain

Bakhadyr Khoussainov

Wei Li

Frank Stephan

A short proof of correctness of the quasi-polynomial time algorithm for parity games

proposed a quasi-polynomial time algorithm for parity games [1]. These notes provide a short proof of correctness of their algorithm.

Parity games

A parity game is given by a directed graph (V, E), a starting node s ∈ V , a function which attaches to each v ∈ V a priority pty(v) from a set {1, 2, ..., m}; the main parameter of the game is n, the number of nodes, and the second parameter is m. Two players Anke and Boris move alternately in the graph with Anke moving first. A move from a node v to another node w is valid if (v, w) is an edge in the graph; furthermore, it is required that from every node one can make at least one valid move. The alternate moves by Anke and Boris define an infinite sequence of nodes which is called a play. Anke wins a play through nodes v 0 , v 1 , • • • iff lim sup t pty(v t ) is even, otherwise Boris wins the play.

We say that a player wins the parity game if she has a strategy which guarantees the play to be winning for her. Parity games are determined [3] thus either Anke or Boris wins the parity game.

Statistics

The core of the algorithm of Calude et al. is to keep track of statistics about the game, in the form of partial functions f : 0 . . . k → 1 . . . m .

The integer k is chosen such that 2 k is strictly larger than twice the number of vertices. The domain of f is denoted dom(f ) and its image im(f ). We also let dom even (f ) = {f (i) is even|i ∈ im(f )}. Statistics are assumed to be increasing, i.e. ∀i, j ∈ dom(f ), (i ≤ j =⇒ f (i) ≤ f (j)) . A statistic f can be modified by inserting a priority c at an index ℓ, which results in removing all pairs of index ≤ ℓ from f and adding the pair (ℓ, c).

The initial statistic is the empty statistic f 0 = ∅, which is updated successively by all the priorities visited during the play, thus producing a sequence of statistics. The update of a statistic f by a priority c is performed by applying successively the following two rules.

Type I update: If c is even then it is inserted at the highest index j ∈ 0 • • • k such that f is defined and even on 0 . . . j -1.

Type II update: If im(f ) contains at least one value < c then c is inserted at the highest index j ∈ dom(f ) such that f (j) < c.

Applying both rules in succession ensures that the update of an increasing statistic is increasing. If rule II triggers an insertion then we say the update is a type II update. Notice that in this case, applying or not rule I in the first place does not change the result. If rule I triggers an insertion but rule II does not then we say the update is a type I update. Anke (resp. Boris) wins the statistics game if she (resp. he) has a strategy to enforce (resp. to avoid) a visit to a statistic whose domain contains k. Similarly to the game of chess, statistics games are determined: either Anke or Boris has a winning strategy [2].

1

Correctness of the algorithm ◮ Theorem 1 (Calude et al). Anke wins the parity game iff she wins the statistics games.

Since statistics games are determined, the direct implication follows from:

◮ Lemma 2. If Boris wins the statistics games, he wins the parity game.

Proof. Every play won by Boris in the statistics game is won by Boris in the parity game because c = lim sup t c t is odd in every sequence of statistics updates

f 0 → c0 f 1 → c1 . . . such that ∀t ≥ 0, k ∈ dom(f t )
, the proof of which follows.

An easy case is when the sequence of statistics is ultimately constant equal to some f then f → c f thus c is odd because an update by an even priority always performs an insertion. In the opposite case define (ℓ, d) the maximal pair (for the dichotomic order) inserted infinitely often. Since d is inserted infinitely often then d ≤ lim sup t c t = c. And d ≥ c otherwise c would be inserted infinitely often at an index ≥ ℓ which would contradict the maximality of (ℓ, d). Since (ℓ, c) is inserted infinitely often then it is removed infinitely often, let (ℓ ′ , c ′ ) be a pair used infinitely often to remove (ℓ, c). Since (ℓ, c) is removed by the insertion of (ℓ

′ , c ′ ) then ℓ ≤ ℓ ′ hence ℓ = ℓ ′ by maximality of ℓ. Since (ℓ ′ , c ′ ) = (ℓ, c ′ ) = (ℓ, c) then c ′ < c by maximality of c. Since (ℓ, c
) is removed by the insertion of (ℓ ′ , c ′ ) and c ′ < c then this insertion is necessarily performed by a type I update and since ℓ = ℓ ′ then c is odd otherwise the insertion would occur at a higher index. ◭

The converse implication (Corollary 9) relies on several crucial properties of statistics.

◮ Definition 3 (Counter value). With every statistic f is associated its counter value

bin(f ) = j∈domeven(f ) 2 j .
In the sequel we fix a sequence f 0 → c0 f 1 . . . → cN f N +1 of statistics updates. We will first give two lemmas that gives information on what can be said when an update of type 1 and 2, respectively, is used on a date.

◮ Lemma 4. For all N if f N → cN f N +1 is a type 1 update, then bin(f N ) + 1 = bin(f N +1 )
Proof. Let ℓ be the entry of the insertion in update f N → cN f N +1 . Then, f N (ℓ) cannot be defined and even, because otherwise ℓ + 1 could also be chosen. Also, f N +1 (ℓ) is c N and thus even. On the other hand, since f N → cN f N +1 is a type 1 update, we have for j < ℓ that f N (j) is defined and even and f N +1 (j) is not defined. No index > ℓ changes on an insertion on index ℓ. Hence, bin(f

N +1 ) -bin(f N +1 ) = 2 ℓ -(1 + 2 + 4 + • • • + 2 ℓ-1 ) = 1. ◭
Next, the lemma about type 2 updates.

◮ Lemma 5. For all N if there is an update of type 2 on (ℓ, c) at date N , then there is a t < N such that 1. the update on date t is of type 1 2. the statistics

f t+1 is equal to f N +1 except that f t+1 (ℓ) = f N +1 (ℓ) and f t+1 (ℓ) is even (implying that bin(f t+1 ) = bin(f N +1 ) if c is even and bin(f t+1 ) > bin(f N +1 ) if c is odd)
3. there are no insertions at index ℓ ′ for any ℓ ′ > ℓ between date t and N . Also, t < N is the last date such that there is a type 1 update at that date on index ℓ.

Proof. Let t < N be the largest date such that there is a type 1 update at that date on index ℓ. This is well-defined, since initially, f 0 = ∅ and for the smallest t ′ , such that ℓ ∈ f t ′ +1 , we must have that the update at date t ′ is a type 1 update (by definition). We see that both f N +1 (i) and f t+1 (i) are undefined for i < ℓ because of the updates on date N and t respectively. Also, for all i > ℓ such that f t+1 (i) or f N +1 (i) is defined, we have that both are defined and f t+1 (i) = f N +1 (i). This is because, if an insertion (ℓ ′ , d) is performed for ℓ ′ > ℓ on a date t ′ between t + 1 and N , we have that f t ′ +1 (ℓ) becomes undefined and hence, there must be a date > t ′ such that ℓ is inserted again, which would use rule 1 and thus contradict the choice of t. Thus, the statistics match except that f t+1 (ℓ) < f N +1 (ℓ) (because each later time we change index ℓ we use rule 2 and the entry thus increases). Also, f t+1 (ℓ) is even because the update on date t is of type 1. ◭

We also give a corollary.

◮ Corollary 6. Fix a number i > 0. Consider the smallest date T such that bin(f T +1 ) ≥ i.

Then the update on date T is of type 1 and bin(f

T +1 ) = i Proof.
By minimality of T we get that bin(f T ) < i (because bin(f 0 ) = 0). By Lemma 5, the update on date T has type 1. By Lemma 4, we thus get that bin(f T +1 ) = i. ◭

Next, we define even factorization and then show that a long even factorization implies that Anke wins the parity game.

◮ Definition 7 (Even factorizations). An even factorization of length j is a sequence 0 ≤ t 0 < . . . < t j such that for every i ∈ 0 . . . j -1, the maximum of c ti , c ti+1 , . . . , c ti+1-1 is even.

We next show that long even sequences exists.

◮ Lemma 8. For all N , there is an even factorization of length at least bin(f N ).

◮ Corollary 9. If Anke wins the statistics game then she wins the parity game.

Proof. By definition of the statistics game, Anke can enforce the play to reach a statistic

f N +1 such that k ∈ dom(f N +1 ).
If N is chosen minimal then f N → cN f N +1 is an update of type 1 by Corollary 6 on entry k. Hence, f N +1 is defined on k and f N +1 (k) is even. This implies that bin(f N +1 ) ≥ 2 k . According to Lemma 8, such a play has an even factorization t 0 < t 1 < . . . < t j of length bin(f N +1 ) ≥ 2 k . Since 2 k is > than twice the number of vertices, the play loops on the same vertex at some dates t i and t i ′ , while having the same current player, with 0 ≤ i < i ′ ≤ j. By definition of even factorizations, the maximal priority on this loop is even. Thus Boris has no positional winning strategy in the parity game (because if he had followed it, no loop can have even maximal priority), and since parity games are positional [3], Boris has no winning strategy at all in the parity game. ◭ Proof of Lemma 8. Consider a fixed N . Let x = bin(f N ). We will show that the following sequence t 1 , . . . , t x is an even factorization.

For ease of notation, let t x+1 = N +1 (note that t x+1 is not part of the even factorization). For all j ≤ x, let t j < t j+1 be the last date T using rule 1 such that bin(f T +1 ) = j.

Sequence is well-defined. This sequence is well-defined because (1) on the first date T where bin(f T +1 ) ≥ j we use rule 1 and bin(f T +1 ) = j, by Corollary 6; and (2) bin(f tj+1 ) = j (and hence a date T < t j+1 exists where bin(f T +1 ) ≥ j), which is true for j = x by definition of t x+1 and otherwise follows from Lemma 4 because we use rule 1 on date t j+1 for j < x.

Sequence is an even factorization. Consider some fixed i < x. We will argue that the maximum priority c in c ti , c ti+1 , . . . , c ti+1-1 is even. We will do so using contradiction, so assume that c is odd. Let T ∈ {t i , t i + 1, . . . , t i+1 -1} be the smallest date such that c is seen on that date and let ℓ be the index changed on that date. Note that T > t i , since we use rule 1 on date t i which requires an even number.

◮ Claim 1. The number ℓ is well-defined and bin(f T +1 ) < i = bin(f ti+1 ).

Proof. Let ℓ ′ be the index inserted at date t i . Let ℓ ′′ be the largest index inserted at a date in t i , . . . , T -1. By definition of ℓ ′′ , we have that f T (ℓ ′′ ) is defined and by definition of T and c we have that f T (ℓ ′′ ) < c. Thus, we can perform a type 2 insertion of c at ℓ ′′ and hence ℓ is well-defined. Thus, f T +1 (i) is odd or undefined for i ≤ ℓ, and dom even (f T +1 ) ∩ ℓ + 1 . . . k = dom even (f ti+1 ) ∩ ℓ + 1 . . . k because no such entry has changed between those two dates. On the other hand f ti+1 (ℓ ′ ) is even since a rule 1 update was used on that index on that date. ◭

Let T ′ ∈ {T, . . . , t i+1 -1} be the first date such that bin(f T ′ +1 ) ≥ i. This is welldefined because we have that bin(f ti+1 ) = i by Lemma 4 (since we use rule 1 on date t i+1 ). Clearly T ′ > T since bin(f T +1 ) < i by Claim 1. This also implies that bin(f T ′ ) < i. We must thus make an update on date T ′ . We cannot make an update of type 1 on date T ′ , because bin(f T ′ ) < i ≤ bin(f T ′ +1 ) would then imply that bin(f T ′ +1 ) = i by Lemma 4, which contradicts the choice of t i (since t i < T < T ′ < t i+1 as noted). We next argue that the update on date T ′ cannot be of type 2 either which contradicts that an update have either type 1 or 2, shows that c must be even and thus completes the proof of the lemma.

◮ Claim 2. The update on date T ′ is not of type 2 Proof. Assuming towards contradiction that rule 2 is used on date T ′ . Let (ℓ ′ , c ′ ) be the update performed on date T ′ . Since bin(f T ′ ) < i ≤ bin(f T ′ +1 ), we have that c ′ is even. We will argue that there can be no such ℓ ′ . Let ℓ ′′ be the largest index changed between date T and date T ′ , both included. We thus have that ℓ ′′ ≥ ℓ, ℓ ′ . We can apply Lemma 5 and see that there is t such that t < T ′ and such that bin(f j+1 ) = bin(f T ′ +1 ), because c ′ is even. We thus just need to argue that t ≥ T to contradict that T ′ is the first date in {T, . . . , t i+1 -1} where bin(f T ′ +1 ) ≥ i.

If ℓ ′′ > ℓ ′ . Note that this is especially the case if ℓ > ℓ ′ . We see that t ≥ T because there is no insertion between date t and T ′ at a higher index than ℓ ′ by Lemma 5. This contradicts the choice of T ′ .

Otherwise, if ℓ ′′ = ℓ ′ ≥ ℓ. In this case f T +1 (ℓ ′ ) is either not defined or at least c. This is because if f T (ℓ ′ ) was defined and smaller than c, then it would be changed on date T . We have that f T ′ (ℓ ′ ) is defined and < c ′ ≤ c because otherwise we could not use rule 2 on date T ′ and insert into ℓ ′ . Consider the first date t ′ ≥ T such that f t+1 (ℓ ′ ) is defined and < c. Hence t ′ ≤ T ′ . To lower an entry or make it defined we must use rule 1 on that entry and thus, we use rule 1 on date t ′ on entry ℓ ′ . Hence t ′ = T ′ (because we use rule 2 on date T ′ ) and thus t ′ < T ′ . But then t ≥ t ′ ≥ T because t < T ′ is the last date on which rule 1 was used on index ℓ ′ by Lemma 5. This contradicts the choice of T ′ . ◭ ◭ 2

Time complexity of solving statistics games

Reachability games

A reachability game G is a tuple (V, E, ⊤), where V is a set of n vertices and E ⊆ V × V is a set of m edges. The vertex ⊤ ∈ V is a the target vertex. The play starts in some initial vertex s, player 1 and 2 alternatively select a vertex u ∈ {u | (v, u) ∈ E}. The play then continues to u. If the play is ever in w, the game ends and player 1 wins, otherwise player 2 wins.

If player 1 has a strategy to ensure a win from some vertex s, then s is called a winning vertex. The classical algorithm for reachability games G is called backward induction and computes in time O(m) the set of winning vertices.

Statistics game as a reachability game

Given a parity game G = (V, E), with M priorities, n vertices and m edges, let k = ⌈log(n + 1)⌉ be the maximum index in the corresponding statistics game. Denote S i,M the set of statistics with M priorities and i being the highest possible index.

The corresponding statistics game is the reachability game with vertices

V ×S k-1,M ∪{⊤}. For every edge (v, u) ∈ E and statistic update f → pty(u) f ′ with k ∈ dom(f ), there is an edge from (v, f ) to (u, f ′ ) if k ∈ dom(f ′ ) or to w if k ∈ dom(f ′ ).

A naïve upper complexity bound

According to Theorem 1, a vertex s is winning in the parity game if and only if the vertex (s, ∅) is winning in the statistics game.

The statistics game has ≤ n|S k-1,M | + 1 vertices and ≤ m|S k-1,M | edges and there is a naïve (M + 1) ⌈log(n+1)⌉ upper bound on |S k-1,M |. This gives a first straightforward upper bound on the complexity of solving parity games:

O m(M + 1) ⌈log(n+1)⌉ ≤ O mM 1+log(n) .

Tighter upper complexity bounds

We give tighter upper complexity bounds, starting with some bounds on |S i,M | for all i, M . ◮ Lemma 10. Let x, y ∈ Z. The number of increasing functions f : {1, . . . , x} → {1, . . . , y} is x+y-1 x Proof. Each increasing function f : {1, . . . , x} → {1, . . . , y} has a 1-to-1 correspondence with subsets of size x of {1, . . . , x + y -1} as follows: Let S f be the set {f (1),

f (2) + 1, . . . , f (x) + x -1}. Observe that since f is increasing, f (i) + i < f (i + 1) + i + 1 for all i.
Thus S f has exactly x elements. On the other hand, every set

S = {1 ≤ j 0 < • • • < j x } corresponds to the function f S (z) = j z -z + 1. The function f S is increasing because j i > j i-1 for all i.
O(m|S k-1,M |) = O m k i=0 k i • i + M -1 i .
◮ Theorem 12. Given a parity game with n vertices, m actions and max priority M , the winner of each initial vertex can be found in time

O min mn 2 2 M / M log n, mn 2.4427... n log(1+ M log n ) • 1 + M log n .
Especially, for M ≥ ǫ log 2 n, for some constant ǫ > 0, the winner can be found in

O(m • n 1.4427... n log(1+ M log n ) • (1 + M log n )) time.
For M = log n, the winner can be found in time O mn

log √ 2+1 √ 2-1
= O(mn 2.5431... ).

Proof. We will give an upper bound on O m

k i=0 k i • i+M-1 i . Let g(i) = k i • i+M-1 i . For i = k we have that g(k) = (k -1 + M )! k!(M -1)! = k -1 + M k • k -2 + M k -1 = k -1 + M k 2 • g(k -1)
For 0 < i < k we have that

g(i) = k! i!(k -i)! • (i -1 + M )! i!(M -1)! = (k -i)(i -1 + M ) i 2 • g(i -1) .
Observe that 2 k = 2 ⌈log(n+1)⌉ < 2 log(n+1)+1 = 2(n + 1).

A trivial bound on y x for all x, y is y x /x!. We thus get using Stirling's approximation that

g(k) ≤ (k + M -1) k /k! < 1/2e k ln(k+M-1) /e (k+1/2) ln k-k = 1/2e k ln(k+M-1)-(k+1/2) ln k+k = 1/2e k(1-ln k+ln(k+M-1))-(ln k)/2 = 1/2e k ln((e(k+M-1))/k)-(ln k)/2 = k -1/2 • (e(k + M -1)/k) k = k -1/2 • (2(n + 1)) log e+log(1+(M-1)/k) = O(k -1/2 • n 1.4427... n log(1+ M -1 log n ) • (1 + M -1 log n ))
We first consider the case where M ≥ ǫk 2 for some constant ǫ > 0. Observe that g(k) is a factor ǫ of g(k -1) for this choice of M . Also, for 0 < i < k we have that g(i)/g(i -1) > (ki)ǫ. Thus, g(i) is decreasing geometrically (with a constant factor of at most 1/ǫ) for k -1/ǫ > i and increasing below that. But, 1/ǫ is a constant and thus,

k i=0 g(i) is O(g(k)) = O( k-1+M k ) = O(k -1/2 • n log e+log(1+(M-1)/k) • (1 + M-1 log n )). Hence, the time complexity is O(m log -1/2 n • n 1.4427... n log(1+ M -1 log n ) • (1 + M-1 log n )) in this case. Next we consider smaller values of M ≥ k + 1. Note that y
x is geometrically increasing for a fixed y for x < y/2 and geometrically decreasing for x > y/2. Also, y y/2 ≈ 2 y / √ y.

Thus, the time complexity is

O(m|S k-1,M |) = O m k i=0 k i • i -1 + M i = O m • 2 k k i=0 i -1 + M i = O m • 2 k / √ k k -1 + M min( k-1+M 2 , k) = O min mn 2 2 M / M log n, mn 2.4427... n log(1+ M -1 log n ) • (1 + M -1 log n ) .
Note that the above argument basically finds the maximum of k i and i-1+M i independently, i.e. without using that it is the same i. Thus, one can give better bounds for especially specific values of M as a function of k. We see that g(i) keeps increasing until g(i)/g(i -1) ≤ 1. Let i * be the smallest such i.

1 ≥ g(i * )/g(i * -1) ⇔ 1 ≥ (k -i * )(i * + M -1) i 2 *
m • kg(i * ) = m • kg(i * ) = m • k • k i * • k + i * i * = m • k • k! i * !(k -i * )! (k + i * )! i * !k! = m • k • (k + i * )! (i * !) 2 (k -i * )! < m • k • e (k+i
* +1/2) ln(k+i * )-(k+i * )-2((i * +1/2) ln(i * )-i * )-((k-i * +1/2) ln(k-i * )-(k-i * )) , where we used Stirling's approximation for the inequality. We next consider the exponent of e.

(k + i * + 1/2) ln(k + i * ) -(k + i * ) -2((i * + 1/2) ln(i * ) -i * ) -((k -i * + 1/2) ln(k -i * ) -(k -i * )) =i * (ln(k + i * ) + ln(k -i * ) -2 ln(i * )) + k(ln(k + i * ) -ln(k -i * )) + 1/2(ln(k + i * ) -2 ln(i * ) -ln(k -i * )) =i * ln (k + i * )(k -i * ) i 2 * + k ln k + i * k -i * + 1/2 ln k + i * (i 2 * )(k -i * ) =i * ln k 2 -k 2 /2 k 2 /2 + k ln k + k/ √ 2 k -k/ √ 2 + 1/2 ln k + k/ √ 2 k 2 /2(k -k/ √ 2) =k ln 1 + 1/ √ 2 1 -1/ √ 2 + 1/2 ln 1 + 1/ √ 2 k 2 (1 -1/ √ 2

◮

  There arex+y-1 x subsets of size x of {1, . . . , x + y -1}.◭ Lemma 11. Let x, y ∈ Z. The number of increasing, partial functions f : {0, . . . , x} → {1, . . . , y} is partial increasing function is a increasing function in its domain. For a fixed i, there are x+1 i domains of size i. Since each domain of size i corresponds to the domain {1, . . . , i} we can apply Lemma 10 and see that there are i+y-1 i increasing functions for XX:6 A short proof of correctness of the quasi-polynomial time algorithm for parity games a fixed domain of size i. Thus, there are f : {0, . . . , x} → {1, . . . , y} in total. ◭ Hence, the time complexity of backwards induction on the statistics game is

  ⇔i 2 * ≥ (ki * )(i * + M -1) ⇔ i 2 * ≥ k(M -1) + ki * -(M -1)i *i 2 * ⇔0 ≥ k(M -1) + ki * -(M -1)i * -2i 2 * ⇔ 0 ≤ -k(M -1)ki * + (M -1)i * + 2i 2 * ⇔i * ≥ k -(M -1) + (Mk -1) 2 + 8k(M -1) 4 .We then get an upper bound onO(m|S k-1,M |) of O(m • k i=0 g(i)) = O(m • kg(i * )) .This bound is accurate upto a factor of k = O(log n). Thus, for instance, for M = k + 1, we have that i * = k √ 2 . Inserting this into O(m • kg(i * )) we get that

))+1/2(ln( TCS, 200:135-183, 1998.