Towards understanding the predictability of stock markets from the perspective of computational complexity

James Aspnes*, David F. Fischer, Michael J. Fischer, Ming Yang Kao, Alok Kumar

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)

Abstract

This paper initiates a study into the century-old issue of market predictability from the perspective of computational complexity. We develop a simple agent-based model for a stock market where the agents are traders equipped with simple trading strategies, and their trades together determine the stock prices. Computer simulations show that a basic case of this model is already capable of generating price graphs which are visually similar to the recent price movements of high tech stocks. In the general model, we prove that if there are a large number of traders but they employ a relatively small number of strategies, then there is a polynomial-time algorithm for predicting future price movements with high accuracy. On the other hand, if the number of strategies is large, market prediction becomes complete in two new computational complexity classes CPP and BCPP, where P NP [&Ogr;(log n)] e BCPP e CPP = PP. These computational completeness results open up a novel possibility that the price graph of a actual stock could be sufficiently deterministic for various prediction goals but appear random to all polynomial-time prediction algorithms.

Original languageEnglish (US)
Title of host publicationProceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms
Pages745-754
Number of pages10
StatePublished - Dec 1 2001
Event2001 Operating Section Proceedings, American Gas Association - Dallas, TX, United States
Duration: Apr 30 2001May 1 2001

Other

Other2001 Operating Section Proceedings, American Gas Association
CountryUnited States
CityDallas, TX
Period4/30/015/1/01

Fingerprint

Predictability
Stock Market
Computational complexity
Computational Complexity
Polynomials
Prediction
Trading Strategies
Complexity Classes
Agent-based Model
Stock Prices
Graph in graph theory
Polynomial-time Algorithm
Completeness
Polynomial time
High Accuracy
Computer Simulation
Computer simulation
Financial markets
Model
Movement

Keywords

  • Algorithms
  • Management
  • Measurement
  • Performance
  • Theory
  • Verification

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this

Aspnes, J., Fischer, D. F., Fischer, M. J., Kao, M. Y., & Kumar, A. (2001). Towards understanding the predictability of stock markets from the perspective of computational complexity. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 745-754)
Aspnes, James ; Fischer, David F. ; Fischer, Michael J. ; Kao, Ming Yang ; Kumar, Alok. / Towards understanding the predictability of stock markets from the perspective of computational complexity. Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 2001. pp. 745-754
@inproceedings{ae57d6ab60924d3c91ca153a4115a1a9,
title = "Towards understanding the predictability of stock markets from the perspective of computational complexity",
abstract = "This paper initiates a study into the century-old issue of market predictability from the perspective of computational complexity. We develop a simple agent-based model for a stock market where the agents are traders equipped with simple trading strategies, and their trades together determine the stock prices. Computer simulations show that a basic case of this model is already capable of generating price graphs which are visually similar to the recent price movements of high tech stocks. In the general model, we prove that if there are a large number of traders but they employ a relatively small number of strategies, then there is a polynomial-time algorithm for predicting future price movements with high accuracy. On the other hand, if the number of strategies is large, market prediction becomes complete in two new computational complexity classes CPP and BCPP, where P NP [&Ogr;(log n)] e BCPP e CPP = PP. These computational completeness results open up a novel possibility that the price graph of a actual stock could be sufficiently deterministic for various prediction goals but appear random to all polynomial-time prediction algorithms.",
keywords = "Algorithms, Management, Measurement, Performance, Theory, Verification",
author = "James Aspnes and Fischer, {David F.} and Fischer, {Michael J.} and Kao, {Ming Yang} and Alok Kumar",
year = "2001",
month = "12",
day = "1",
language = "English (US)",
isbn = "0898714907",
pages = "745--754",
booktitle = "Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms",

}

Aspnes, J, Fischer, DF, Fischer, MJ, Kao, MY & Kumar, A 2001, Towards understanding the predictability of stock markets from the perspective of computational complexity. in Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 745-754, 2001 Operating Section Proceedings, American Gas Association, Dallas, TX, United States, 4/30/01.

Towards understanding the predictability of stock markets from the perspective of computational complexity. / Aspnes, James; Fischer, David F.; Fischer, Michael J.; Kao, Ming Yang; Kumar, Alok.

Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 2001. p. 745-754.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Towards understanding the predictability of stock markets from the perspective of computational complexity

AU - Aspnes, James

AU - Fischer, David F.

AU - Fischer, Michael J.

AU - Kao, Ming Yang

AU - Kumar, Alok

PY - 2001/12/1

Y1 - 2001/12/1

N2 - This paper initiates a study into the century-old issue of market predictability from the perspective of computational complexity. We develop a simple agent-based model for a stock market where the agents are traders equipped with simple trading strategies, and their trades together determine the stock prices. Computer simulations show that a basic case of this model is already capable of generating price graphs which are visually similar to the recent price movements of high tech stocks. In the general model, we prove that if there are a large number of traders but they employ a relatively small number of strategies, then there is a polynomial-time algorithm for predicting future price movements with high accuracy. On the other hand, if the number of strategies is large, market prediction becomes complete in two new computational complexity classes CPP and BCPP, where P NP [&Ogr;(log n)] e BCPP e CPP = PP. These computational completeness results open up a novel possibility that the price graph of a actual stock could be sufficiently deterministic for various prediction goals but appear random to all polynomial-time prediction algorithms.

AB - This paper initiates a study into the century-old issue of market predictability from the perspective of computational complexity. We develop a simple agent-based model for a stock market where the agents are traders equipped with simple trading strategies, and their trades together determine the stock prices. Computer simulations show that a basic case of this model is already capable of generating price graphs which are visually similar to the recent price movements of high tech stocks. In the general model, we prove that if there are a large number of traders but they employ a relatively small number of strategies, then there is a polynomial-time algorithm for predicting future price movements with high accuracy. On the other hand, if the number of strategies is large, market prediction becomes complete in two new computational complexity classes CPP and BCPP, where P NP [&Ogr;(log n)] e BCPP e CPP = PP. These computational completeness results open up a novel possibility that the price graph of a actual stock could be sufficiently deterministic for various prediction goals but appear random to all polynomial-time prediction algorithms.

KW - Algorithms

KW - Management

KW - Measurement

KW - Performance

KW - Theory

KW - Verification

UR - http://www.scopus.com/inward/record.url?scp=35248887420&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35248887420&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:35248887420

SN - 0898714907

SP - 745

EP - 754

BT - Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms

ER -

Aspnes J, Fischer DF, Fischer MJ, Kao MY, Kumar A. Towards understanding the predictability of stock markets from the perspective of computational complexity. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 2001. p. 745-754