A Computational View of Market Efficiency

I prove that if markets are weak-form efficient, meaning current prices fully reflect all information available in past prices, then P = NP, meaning every computational problem whose solution can be verified in polynomial time can also be solved in polynomial time. I also prove the converse by showing how we can "program" the market to solve NP-complete problems. Since P probably does not equal NP, markets are probably not efficient. Specifically, markets become increasingly ...

We consider a simple binary market model containing $N$ competitive agents. The novel feature of our model is that it incorporates the tendency shown by traders to look for patterns in past price movements over multiple time scales, i.e. {\em multiple memory-lengths}. In the regime where these memory-lengths are all small, the average winnings per agent exceed those obtained for either (1) a pure population where all agents have equal memory-length, or (2) a mixed population ...

Markets have internal dynamics leading to excess volatility and other phenomena that are difficult to explain using rational expectations models. This paper studies these using a nonequilibrium price formation rule, developed in the context of trading with market orders. Because this is so much simpler than a standard inter-temporal equilibrium model, it is possible to study multi-period markets analytically. There price dynamics have second order oscillatory terms. Value i...

It has been assumed that arbitrage profits are not possible in efficient markets, because future prices are not predictable. Here we show that predictability alone is not a sufficient measure of market efficiency. We instead propose to measure inefficiencies of markets in terms of the maximal profit an ideal trader can take out from a market. In a stock market model with an evolutionary selection of agents this method reveals that the mean relative amount of realizable profit...

Before the massive spread of computer technology, information was far from complex. The development of technology shifted the paradigm: from individuals who faced scarce and costly information to individuals who face massive amounts of information accessible at low costs. Nowadays we are living in the era of big data and investors deal every day with a huge flow of information. In the spirit of the modern idea that economic agents have limited computational capacity, we propo...

A non-Bayesian time-varying model is developed by introducing the concept of the degree of market efficiency that varies over time. This model may be seen as a reflection of the idea that continuous technological progress alters the trading environment over time. With new methodologies and a new measure of the degree of market efficiency, we examine whether the US stock market evolves over time. In particular, a time-varying autoregressive (TV-AR) model is employed. Our main ...

The purpose of this article is to propose a new "theory," the Strategic Analysis of Financial Markets (SAFM) theory, that explains the operation of financial markets using the analytical perspective of an enlightened gambler. The gambler understands that all opportunities for superior performance arise from suboptimal decisions by humans, but understands also that knowledge of human decision making alone is not enough to understand market behavior --- one must still model how...

We propose a prediction model based on the minority game in which traders continuously evaluate a complete set of trading strategies with different memory lengths using the strategies' past performance. Based on the chosen trading strategy they determine their prediction of the movement for the following time period of a single asset. We find empirically using stocks from the S&P500 that our prediction model yields a high success rate of over 51.5% and produces higher returns...

Empirical evidence suggests that even the most competitive markets are not strictly efficient. Price histories can be used to predict near future returns with a probability better than random chance. Many markets can be considered as {\it favorable games}, in the sense that there is a small probabilistic edge that smart speculators can exploit. We propose to identify this probability using conditional entropy concept. A perfect random walk has this entropy maximized, and depa...

In speculative markets, risk-free profit opportunities are eliminated by traders exploiting them. Markets are therefore often described as "informationally efficient", rapidly removing predictable price changes, and leaving only residual unpredictable fluctuations. This classical view of markets absorbing information and otherwise operating close to an equilibrium is challenged by extreme price fluctuations, in particular since they occur far more frequently than can be accou...