coefficient isconstrained to be the same in every case. Their results indicate a marginal rejectionof the null hypothesis of joint nonmean reversion at conventional significance levels,which they interpret as evidence in favor of long-run PPP. In a more recent paneldata study on Euro exchange rates, [267] found strong rejections of the random walkhypothesis. Taylor and Sarno [384], however, issued an important warning in interpreting these findings. The tests typically applied in these panel-data studies test thenull hypothesis that none of the real exchange rates under consideration are meanreverting. If this null hypothesis is rejected, then the most that can be inferred isthat at least one of the rates is mean reverting. However, researchers tended to drawa much stronger inference that all of the real exchange rates were mean revertingand this broader inference is not valid. Some researchers have sought to remedy thisshortcoming by designing alternative tests. For example, [384] suggested testing thehypothesis that at least one of the real exchange rates is nonmean reverting, rejection of which would indeed imply that they are all mean reverting. However, suchalternative tests are generally less powerful, so that their application has not led toclear-cut conclusions [356, 384].Another important stage in PPP literature was initialized in the mid-1980s when[199] and others began to notice that even the studies that were interpreted as
3.1 Purchasing Power Parity Theorem
19
supporting the thesis that PPP holds in the long run, suggested that the speed atwhich the real exchange rates adjusted to PPP was extremely slow. This involvedthe computation of the so-called half-life of shocks to the real exchange rate, whichdescribes how long it would take for the effect of a shock to die out by 50%. Byincluding both long-span investigations and panel unit root tests of long-run PPP,[342] finds that estimated half-lives of adjustment mostly tend to fall into the rangeof 3–5 years. Some more recent studies have argued that half-lives are even longerif estimation is not based on OLS (for example, [71, 302]). The apparently veryslow speed of adjustment of real exchange rates paired with further criticism on theinsufficiency of traditional linear statistical testing procedures led to an interestingbody of research which argues that failure to accept the long-run PPP hypothesiscould also be due to a different reason: the existence of nonlinear dynamics in thereal exchange rate. If nonlinear dynamics existed then the exchange rate would become increasingly mean reverting with the size of the deviation from equilibrium[106, 227].To summarize, if exchange rates do tend to converge to PPP, economists have –at least so far – had a hard time presenting strong evidence to support the claim. Thedifficulty for validating PPP empirically has been captured in two PPP puzzles:1. The disconnect puzzle states that the difficulty of detecting evidence for longrun PPP suggests that the exchange rate is disconnected from PPP and thereforeviolates the PPP theorem [312, 385, 386].2. The excess volatility puzzle states that the enormous short-term volatility ofreal exchange rates is contradicting to the extremely slow rate of adjustment([342], p. 647).Current consensus view on PPP research supports the hypothesis that only relativePPP seems to hold in the long run. Structural and transitory effects influence thereal exchange rate permanently and make absolute PPP obsolete. PPP is generallyconsidered to be a meaningful element of macroeconomics for an open economyin the long-run, at least as a benchmark for over- or undervaluation of a currency.However, it offers no explanation for short term exchange rate variation. A secondstylized fact is that PPP seems to hold better for countries with relatively high ratesof inflation and underdeveloped capital markets [385].
3.1.4 Explanations for Deviations from PPPThe empirical failure to validate PPP has been subject to various explanations. Froman empirical perspective it has been argued that it is difficult to find a price indexthat accurately measures the inflation rate for the countries being studied [136,254].The problem of simultaneous determination of both price and the foreign exchangerate is noted by [178]. Pippenger [325] claims that one obstacle to finding empiricalsupport for PPP may be due to the statistical procedures applied.
20
3 Equilibrium Relationships
From a theoretical perspective, macroeconomic literature has explained long rundepartures from PPP by the Harrod–Balassa–Samuelson hypothesis which dependson inter-country differences in the relative productivity of the tradable and nontradable sectors [23, 184, 353]. Another important explanation addressing short-rundepartures from PPP was given by Dornbusch’s theory on how expansionary monetary policy may lead to overshooting nominal exchange rates [102]. In short, priceson goods are assumed to be sticky in the short-run while the exchange rate as a financial market price quickly adjusts to disturbances initiated by monetary policy,i.e., increases or decreases in the money supply. In the short-run, the exchange rateis therefore determined by the supply and demand of financial assets. The portfoliobalance theory [101] extends Dornbusch’s sticky price monetary model by incorporating another important macroeconomic variable: the current account balance.According to this theory, a monetary shock (e.g., increase in money supply) is expected to affect (increase) prices which affects net exports and hence influences thecurrent account balance. In turn, this will affect the level of wealth which feeds backinto the asset market, affecting the exchange rate during the adjustment to long-runequilibrium. The general tenor on these traditional exchange rate theories is that,although plausible, empirical work has neither favored a particular theory nor produced related models that are sufficiently statistically satisfactory to be consideredreliable and robust (see references in [357], Chap. 4). This shortcoming has led to arapid development of new open-economy models which avoid the formal simplicityof the traditional models by offering a more rigorous analytical foundation throughfully specified microfoundations (see for instance [311]). In this spirit, [66] showedthat in a small open economy with sticky prices (i.e., prices exhibiting resistance tochange) and a nontraded sector, small monetary shocks can generate high levels ofexchange rate volatility. This could be an explanation for the second PPP puzzle.However, the problem with open-economy models is that they are less universal androbust. In addition they require assumptions which are difficult to test (see references in [357], Chap. 5).Econometric literature distinguishes between permanent (structural) or temporary (transitory) shocks to the exchange rate fashion by focusing on the employmentof vector autoregression (VAR) analyses, an econometric technique which intends tocapture the evolution and the interdependencies between multiple time series [42].Overall, literature on identifying the source of structural and transitory shocks driving exchange rates has provided mixed results. While both nominal shocks (e.g.,monetary shocks) and real shocks (initiated by real factors such as real income, factor endowment, productivity levels, interest rates, etc.) were shown to be sourcesof exchange rate volatility leading to departures from PPP, their relative importancevaries across studies (see for instance [88, 244, 340]).A promising avenue of research addressing both PPP puzzles at once investigates the role of nonlinearities in real exchange rate dynamics. If adjustment tolong-run equilibrium occurs in a nonlinear fashion, then the speed of adjustmentvaries depending on the magnitude of disequilibrium. Thus, while small shocks tothe real exchange rate around equilibrium will be highly persistent, larger shocks
3.2 Interest Rate Parity (IRP) Theorem
21
mean-revert much faster. This behavior may be motivated economically by marketfrictions such as• Barriers of international trade including transport costs , tariffs, nontariff barriers[128, 342]• Transaction costs [33, 106, 419]• Heterogeneity of opinion [227]• Central bank interventions [368, 383]The nonlinear nature of the adjustment process has been investigated in terms of thethreshold autoregressive (TAR) model [313, 393] the smooth transition autoregressive (STAR) model [174, 292, 386] and Markov switching models [232, 383].
3.2 Interest Rate Parity (IRP) TheoremWhen an asset market is taken into account, then equilibrium theory follows theessence of international manifestations of the law of one price. The interest rateparity (IRP) theorem is an arbitrage condition which illustrates the idea that, in theabsence of market imperfections, risk-adjusted expected real returns on financialassets will be the same in foreign markets as in domestic markets. Hence, returnsgenerated from borrowing in domestic currency, exchanging that currency for foreign currency and investing in interest-bearing foreign currency denominated assets,while simultaneously purchasing forward contracts to convert the foreign currencyback at the end of the investment period should be equal to the returns from purchasing and holding similar interest-bearing instruments of the domestic currency.Let Ft,k denote the k-period forward rate, i.e., the rate agreed now for an exchange∗ the nominal interest ratesof currencies k periods ahead. Let further be it,k and it,kavailable on similar domestic and foreign securities respectively with k periods tomaturity. Formally, IRP states that the ratio of the forward and spot exchange ratesshould be∗1 + it,kFt,k=(3.7)St1 + it,kIRP thus holds, if the ratio of the forward and spot exchange rates equals the ratioof foreign and domestic nominal interest rates. If (3.7) does not hold, investors cantheoretically arbitrage and make risk-free returns. Academic literature commonlydistinguishes between two versions of the identity: covered interest rate parity (CIP)and uncovered interest rate parity (UIP).
3.2.1 Covered Interest Rate Parity (CIP)CIP is an arbitrage condition which postulates, that the interest rate difference between two countries’ currencies, is equal to the percentage difference between the
22
3 Equilibrium Relationships
forward exchange rate and the spot exchange rate. This requires the assumptionsthat financial assets are perfectly mobile and similarly risky. Taking the natural logarithm in (3.7) and using the approximation ln(1 + x) ≈ x, CIP holds if∗ft,k − st = it,k − it,k
(3.8)
where ft,k is the logarithm of the k-period forward rate, st denotes the logarithm of∗ are the nominal interest rates availablethe spot exchange rate at time t, it,k and it,kon similar domestic and foreign securities, respectively, with k periods to maturity.A direct implication of (3.8) is, that when the domestic interest rate is lower than∗ < 0 the forward price of the foreign currency willthe foreign interest rate it,k − it,kbe below the spot price ft,k − st < 0, i.e., the foreign currency is selling forward ata premium. Conversely, if domestic interest rate is higher than the foreign interest∗ > 0, the forward price of the foreign currency will be above the spotrate it,k − it,kprice ft,k − st > 0, i.e., the foreign currency is selling forward at a discount. Hence,the national interest rate difference should be equal to, but opposite in sign, to theforward rate premium or discount for the foreign currency.
3.2.2 Uncovered Covered Interest Rate Parity (UIP)UIP postulates that the return on domestic currency deposit should be equal to theexpected return from converting the domestic currency into foreign currency, investing it in a foreign currency denominated asset and then converting the proceedsback into the domestic currency at the future expected exchange rate. Formally, theinterest rate difference between two countries’ currencies is equal to the percentagedifference between the expected exchange rate and the spot exchange rate∗E(st+k ) − st = it,k − it,k
(3.9)
where E(st+k ) denotes the market expectation for st in k periods based on information at t. Unlike CIP, UIP is not an arbitrage condition since the expected exchangerate E(st+k ) is unknown at time t and therefore nonzero deviations from UIP do notnecessarily imply the existence of arbitrage profits due to the foreign exchange riskassociated with future exchange rate movements.
3.2.3 Empirical EvidenceIn reality, spot and forward markets are not always in a state of equilibrium as described by IRP. As a consequence, arbitrage opportunities exist. Arbitrageurs whorecognize a state of disequilibrium can borrow in the currencies exhibiting relativelylow interest rates and convert the proceeds into currencies which offer higher interest rates. In case that the investor is hedged against any risk of the currency deviating
3.2 Interest Rate Parity (IRP) Theorem
23
by selling the currency forward, this is known as covered interest arbitrage (CIA). Ifthe investor does not sell the currency forward, thus remaining exposed to the riskof the currency deviating, this is known as uncovered interest arbitrage (UIA). Themotivation for entering into UIA is seeking to profit from expected changes in theexchange rate, i.e., rational speculation.CIA can be tested in two ways. The first approach relies on computing the actualdeviations from IRP to see if they differ significantly from zero. The significanceof departures from CIP is often defined with respect to a neutral band, which is determined by transaction costs. Frenkel and Levich [138] calculated a band aroundthe IRP line within which no arbitrage is possible. Using weekly data for the period1962–1975 and for three sub-periods, they found that around 80% of observationsare within the neutral band. They conclude that, after allowing for transaction costsand ensuring that the arbitraged assets are comparable, CIA does not seem to entailunexploited opportunities for profit. This finding is confirmed by [79] who showsthat deviations from CIP should be no greater than the minimum transaction costsin one of three markets. On the basis of analysis of data for five major currenciesagainst the US dollar, Clinton finds that the neutral band should be within +0.06%per annum from parity and that although the hypothesis of zero profitable deviationsfrom parity can be rejected,empirically, profitable trading opportunities are neither large enough nor long-lived enoughto yield a flow of excess returns
over time to any factor. However, there also exists contrary evidence in favor of arbitrage opportunities in the foreign exchange markets. By questioning the qualityof the data used by [138], various researchers have often arrived at different conclusions. Taylor [380, 381]), for instance, argues that in order to provide a propertest of CIP it is important to have data on the appropriate exchange rate and interest rates recorded at the same instant in time at which a dealer could have dealt.For this purpose, he uses high-quality, high-frequency, contemporaneously sampleddata for spot and forward exchange rates and corresponding interest rates for a number of maturities and makes allowance for bid-offer spreads and brokerage costs inhis calculations. He finds that there are few profitable violations of CIP, even duringperiods of market uncertainty and turbulence. In a more recent study, [25] examinedthe dynamics of deviations from CIP using daily data on the GBP/USD spot andforward exchange rates and interest rates over the period January 1974 to September 1993. They find, as opposed to [138] that a substantial number of instances inthe sample in which the CIP condition exceeds the transaction costs band, implyarbitrage profit opportunities. In addition, [283] identified significant arbitrage opportunities from ten markets over a 12-day period. Some of these opportunities wereeven observed to be persistent for a long time. Persistent interest rate arbitrage opportunities were also revealed by [79] and [1]. An alternative approach for testingthe validity of CIP is to estimate the regression coefficients offt,k − st = α + β (it − it∗ ) + εt
(3.10)
24
3 Equilibrium Relationships
which are required to be (α , β ) = (0, 1) and an uncorrelated error. Equation (3.10)has been tested by a number of researchers for a variety of currencies and time periods (see, e.g., the early study by [59]). The main conclusion to be drawn from thisline of research is that, CIP is supported. Although there are significant deviationsfrom the condition α = 0 which might reflect the existence of nonzero transactioncosts, the estimates of b usually differ insignificantly from 1.Assuming that CIP holds and market participants have rational expectations, UIPimplies that forward premium should be an unbiased predictor of the expectedchange in the spot exchange rate. UIP can therefore be tested by estimating a regression of the form:st+k − st = α + β ( ftk − st ) + εt+k
(3.11)
Under UIP, (α , β ) = (0, 1) and the rational expectations forecast error εt+k mustbe uncorrelated with information available at time t [125]. Empirical studies generally report results which reject UIP (e.g., see the references in the surveys of[193, 263, 357]) suggesting that it would have been possible to make speculativegains in certain markets over certain periods of time. One reason is the empiricalfinding that the spot exchange rate change on mostly free floating nominal exchangerates up until 1990s appears to be negatively correlated (b < 0) with the lagged forward premium or forward discount [143]. This observation implies that the morethe foreign currency is at a premium in the forward market, the less the home currency is predicted to depreciate, which has been referred to as the forward premiumanomaly or forward premium puzzle [20]. Fama [125] finds further but different empirical evidence against UIP: forward rates are not unbiased but biased predictors offuture spot rates because a nonnegative interest rate differential would, on average,result in an appreciating currency for the high interest rate country. This observationhas been referred to as forward bias puzzle ([263]). A simple rule to capitalize ona forward rate bias would be to enter into a forward hedge whenever the foreigncurrency is offered at a premium and never hedge when it is at a discount ([233]).
3.2.4 Explanations for Deviations from IRPDifferent theoretical explanations have been proposed to explain empirical deviations from CIP and UIP and the related rejection of the efficient markets hypothesis.For instance, the existences of a risk premium due to risk-averse market participants is one prominent attempt to explain the UIP forward bias puzzle. If foreignexchange market participants are risk-averse, the UIP condition may be distorted bya risk premium ρt,k , because agents demand a higher rate of return than the interestdifferential in return for the risk of holding foreign currency [125]. The differencebetween the forward exchange rate and the spot exchange rate has always been usedas the measure of the risk premium that the marginal investor would be willing topay in order to reduce his exposure to exchange risk. The message which emerges
3.2 Interest Rate Parity (IRP) Theorem
25
from the empirical analysis of risk-premium models is that it is hard to explainexcess returns in forward foreign exchange by an appeal to risk premiums alone[30, 31, 269, 275]. Chinn [74] and McCallum [285] therefore propose to link the behavior of UIP deviations with monetary policy reaction functions.A second explanation for the forward bias puzzle is that there is a failure of therational expectations component underlying the notion of market efficiency. Literature identifies several possible explanations for volatile expectations or departures from rational expectations that generate nonzero and potentially predictableexcess returns even when agents are risk neutral: for instance, learning about regimeshifts [261, 262] or about fundamentals, such as learning about the interest rateprocess [169], the peso problem originally suggested by [341], or inefficient information processing [37]. This literature is well covered in several surveys (e.g.,[114, 263, 357]).Third, it could be possible that both the risk-aversion of market participants and adeparture from the rational expectations hypothesis are responsible for the rejectionof the efficient markets hypothesis. Important contributions in this area include thework by [135] and [141].A more general argument referring to the rejection of both CIP and UIP is thatthe relationship between exchange rate and interest rate is not a linear, but a nonlinear one. This could be for reasons such as transaction costs [24, 195, 363], centralbank intervention [277], limits to speculation ([270], pp. 206–220), or informationcosts ([21], p. 50).
Chapter 4
Market Efficiency Concepts
4.1 Informational EfficiencyThe theoretical concepts of informational and speculative market efficiency areclosely related to the IRP Theorem. According to [124] and [126], a financial market is said to be (informationally) efficient, if prices in that market fully reflect allthe available and relevant information. The intuition is, that, if the market processesthat information immediately, price changes can only be caused by the arrival ofnew information. However, since future information cannot be predicted, it is alsoimpossible to predict future price changes. Depending on the information set available, there are different forms of the market efficiency hypothesis (MEH):1• Weak-form efficiency. No investor can earn excess returns by developing tradingrules based on historical price or return information. In other words, the information in past prices or returns is not useful or relevant in achieving excess returns.• Semistrong-form efficiency. No investor can earn excess returns by developingtrading rules based on publicly available information. Examples of publicly available information are annual reports of companies, investment advisory data, orticker tape information on TV.• Strong-form efficiency. No investor can earn excess returns using any information, whether publicly available or not. In other words, the information set contains all information, including private or insider information.If applied to the foreign exchange markets, informational efficiency means that thecurrent spot rate has to reflect all currently available information. This has one important implication: if expectations about the future exchange rate are rational [304]they should all be incorporated in the forward rate. Hence, if the efficient market1 Latham [245] and Rubinstein [349] have extended the definition of market efficiency by pointingout that it is possible that people might disagree about the implications of a piece of informationso that some buy an asset and others sell in such a way that the market price remains unaffected.As a consequence, they require not only that there be no price change but also that there be notransactions. Still, theoretical and applied literature focuses on the efficiency definition as given by[124] and [126], which will provide the foundation for the following considerations, too.
C. Ullrich, Forecasting and Hedging in the Foreign Exchange Markets, Lecture Notesin Economics and Mathematical Systems 623, DOI: 10.1007/978-3-642-00495-7 4,c Springer-Verlag Berlin Heidelberg 2009
27
28
4 Market Efficiency Concepts
hypothesis holds true, the forward rate must be an “unbiased predictor” for the expected exchange rate ([137]). When the forward rate is termed an unbiased predictor,then it over or underestimates the future spot rate with relatively equal frequency andamount. It therefore misses the spot rate in a regular and orderly manner such thatthe sum of the errors equals zero. As a direct consequence, it is not possible to makearbitrage profits since active investment agents will exploit any arbitrage opportunity in a financial market and thus will deplete it as soon as it may arise. Empiricaltests for a bias in forward rates have been based on testing the two principles of CIAand UIA which have been referred to in Sect. 3.2.
4.2 Speculative EfficiencyA different concept of efficiency is speculative efficiency ([37, 54], p. 67), which, incontrast to informational efficiency does not imply that expectations about the futureexchange rate must be rational and should all be incorporated in the forward rate.Instead, departures from the rational expectations hypothesis are allowed. The supply of speculative funds is infinitely elastic at the forward price, i.e., equal to the expected future spot price. The expected future spot price is a market price determinedas the solution to the underlying irrational expectations model. The speculative efficiency hypothesis is tested by formulating a trading strategy and then calculatingits profitability in simulated trading.
Chapter 5
Views from Complexity Theory
5.1 IntroductionThe behavior of exchange rates is puzzling and hard to explain. While all of the potential explanations for deviations from equilibrium conditions appear fairly reasonable and have theoretical merit, PPP and IRP (forward premium anomaly) puzzleshave not yet been convincingly explained and continue to puzzle the internationaleconomics and finance profession. However, this inexplicability has nothing to dowith economic and financial theorists being not capable enough but rather with thecomplex dynamics that drive exchange rates and therefore, with the nature of complexity itself. Shiller [366] notes that all economic models have one major flaw:a gross oversimplification that is based on the assumption that economic agentsknow the true state of economic structure and make rational decisions for their consumption and investment. In a similar way, [351] argues that the inexplicability ofsuch complex systems may have to do with the existence of fundamental limits toknowledge:This would suggest that financial theory cannot hope to provide much more than a disjoint collection of highly simplified “toy models” which are either sufficiently stylized to besolved analytically, or are simple enough to be approximately solved on digital computers.In fact, conventional economic and financial theory does not choose to study the unfoldingof the patterns its agents create. By assuming behavioral equilibrium, it rather simplifies itsquestions in order to seek analytical solutions. For example, standard theories of financialmarkets assume rational expectations and ask: what forecasts (or expectations) are consistent with – are on average validated by – the prices these forecasts and expectations togethercreate. But it does not account for actual market “anomalies” such as unexpected price bubbles and crashes, random periods of high and low volatility, and the use of heavy technicaltrading.
Hence, it is legitimate to ask whether economic and financial theory can providesufficient explanations for reality.Complex systems theory with regards to markets has its origins in the classicaleighteenth century political economy of the Scottish Enlightenment which realizedthat order in market systems is spontaneous or emergent in that it is the result ofC. Ullrich, Forecasting and Hedging in the Foreign Exchange Markets, Lecture Notesin Economics and Mathematical Systems 623, DOI: 10.1007/978-3-642-00495-7 5,c Springer-Verlag Berlin Heidelberg 2009
29
30
5 Views from Complexity Theory
human action and not the execution of human design. This early observation, wellknown also from the Adam Smith metaphor of the invisible hand, premises a disjunction between system wide outputs, the modeling capabilities of individuals at amicro level, and the distinct absence of an external organizing force. It is thereforepostulated that macroscopic properties cannot be formally or analytically deducedfrom the properties of its parts. This distinguishes the sciences of complexity theoryfrom traditional economic and financial science which relies on deductive formalistic and analytical methods.It was not until the twentieth century with two significant developments in thefoundations of mathematics and advances in computer technology that complexadaptive systems could be investigated and formulated. First, [168, 329, 398] established logical impossibility limits to formalistic calculation or deductive methodsproviding first results on incompleteness, algorithmically unsolvable problems, andthe notion of computational complexity. Usually problems solvable by a deterministic algorithm in polynomial time (i.e., the number of elementary computation stepsis polynomial in the size of the input) are considered to be “good” solutions. On thecontrary, a problem is considered as computationally intractable, if it is so hard thatno polynomial time algorithm can possibly solve it.Definition 5.1. A polynomial time algorithm is defined to be one whose time complexity function is O(p(n)) for some polynomial function p, where n is used todenote the input length. Any algorithm whose time complexity function cannot beso bounded is called an exponential time algorithm (although this definition includescertain nonpolynomial time complexity functions which are not normally regardedas exponential functions).Problems that can be solved by a polynomial time algorithm are tractable in a sensethat they coincide with those that can be realistically solved by computers, and itis held that every practical and efficient algorithm can be rendered as a polynomialtime bounded Turing machine (see [152, 320]). On the other hand, one of the earliest and most popular intractability results are the classical undecidability results of[398], who proved that it is impossible to specify any algorithm which given an arbitrary computer program and an arbitrary input to that program, can decide whetheror not the program will eventually halt when applied to that input.Parallel efforts to the search of powerful methods for proving problems intractable have been made by focusing on learning more about the ways in whichvarious problems are interrelated with respect to their difficulty. The theory of NPcompleteness has introduced a variety of complexity classes with respect to certainproblem formulations [152]. There are two important classes of problems which canbe met in many areas of practical application.Definition 5.2. The complexity class P is the set of decision problems that can besolved by a deterministic algorithm in polynomial time in the size of the input.This class corresponds to an intuitive idea of the problems which can be effectivelysolved in the worst cases.
5.1 Introduction
31
Definition 5.3. The complexity class NP is the set of decision problems that can besolved by a nondeterministic algorithm in polynomial time.A nondeterministic algorithm is composed of two stages. The first stage is a guessing stage where, given a problem instance I, a structure S is guessed. The secondstage is a checking stage, where given I and S as inputs, the algorithm behaves ina deterministic manner and halts with either an answer “yes” or “no.” The classNP contains many problems that people would like to be able to solve effectively.Most of the apparently intractable problems encountered in practice, when phrasedas decision problems, belong to this class.Definition 5.4. A problem is NP-hard, if each problem in NP is reducible to it inpolynomial time.Definition 5.5. A problem is NP-complete, if it is NP-hard and inside the class NPof problems.Hence, the NP-complete problems are the hardest problems among all those that canbe solved by a nondeterministic algorithm in polynomial time and until today therehas not been any solution for such a problem by a deterministic algorithm in polynomial time concerning the size of the input. The question of whether P is the sameset as NP has been called the most important open question in theoretical computerscience.Apart from computational complexity, the second significant methodological development is dynamic complexity which considers the use of computer based artificial environments to simulate dynamics from large numbers of interacting agentswith varying levels of computational and adaptive intelligence [14, 22, 194]. Theseminal work of [358] is one of the earliest examples of the use of computer simulation to demonstrate how simple microbehavioral rules result in a self-organizedmacro outcome, an undesirable one of racial segregation, which could not have beendeduced from the initial rules. More recently, a number of economists and physicistshave got involved in the new computational agent based modeling in economics giving rise to very interesting and important new streams of literature called adaptivecomputational economics [346] and econophysics [211].In the following, it is not our purpose to provide an extensive summary on theselively disciplines of research. Instead, we want to create awareness in the economicand financial community, that both the computational and dynamic complexity ofeconomic calculations are proveably fundamental sources for real-world phenomena such as disequilibrium and market inefficiencies. We think that this perspectiveis important as it sheds some light on the feasibility of economic concepts suchas the equilibrium concept. Thus, if a Turing machine cannot efficiently computeequilibrium then neither can a market. As we will show in the following, there areprovable results on the impossibility for market agents to behave according to traditional economic concepts such as equilibrium, rationality, and efficiency.
32
5 Views from Complexity Theory
5.2 Calculating Fixed Point Market Equilibrium5.2.1 Computational Complexity of Centralized EquilibriumThe existence of equilibrium does not imply that it can actually be achieved. Inthe classic Walrasian model [413], the price formation mechanism (Tâtonnement) issimple and has the following properties:• Agents truthfully reveal their preferences• No trading takes place before the market-clearing price