Nothing Special   »   [go: up one dir, main page]
IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v64y2018i2p784-803.html
   My bibliography  Save this article

A Partitioning Algorithm for Markov Decision Processes with Applications to Market Microstructure

Author

Listed:
  • Ningyuan Chen

    (Department of Industrial Engineering and Logistics Management, Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong)

  • Steven Kou

    (Risk Management Institute, National University of Singapore, Singapore 119077)

  • Chun Wang

    (Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027)

Abstract
We propose a partitioning algorithm to solve a class of linear-quadratic Markov decision processes with inequality constraints and nonconvex stagewise cost; within each region of the partitioned state space, the value function and the optimal policy have analytical quadratic and linear forms, respectively. Compared to grid-based numerical schemes, the partitioning algorithm gives the closed-form solution without discretization error, and in many cases does not suffer from the curse of dimensionality. The algorithm is applied to two applications. In the main application, we present a model for limit order books with stochastic market depth to study the optimal order execution problem; stochastic market depth is consistent with empirical studies and necessary to accommodate various order activities. The optimal execution policy obtained by the algorithm significantly outperforms that of a deterministic market depth model in numerical examples. In the second application, we use the algorithm to compute the exact optimal solution to the renewable electricity management problem, for which previously only an approximate solution was known. As a comparison, we show that the approximate solution can be quite inaccurate for some initial states and thus demonstrate an advantage of the exact solution. The online appendix is available at https://doi.org/10.1287/mnsc.2016.2639 . This paper was accepted by Yinyu-Ye, optimization.

Suggested Citation

  • Ningyuan Chen & Steven Kou & Chun Wang, 2018. "A Partitioning Algorithm for Markov Decision Processes with Applications to Market Microstructure," Management Science, INFORMS, vol. 64(2), pages 784-803, February.
    • Handle: RePEc:inm:ormnsc:v:64:y:2018:i:2:p:784-803
    DOI: mnsc.2016.2639
    as

    Download full text from publisher

    File URL: https://doi.org/mnsc.2016.2639
    Download Restriction: no
    File URL: https://libkey.io/mnsc.2016.2639?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Arthur Henriot, 2014. "Market Design with Centralized Wind Power Management: Handling Low-predictability in Intraday Markets," The Energy Journal, International Association for Energy Economics, vol. 0(Number 1).
    2. Hee‐Joon Ahn & Kee‐Hong Bae & Kalok Chan, 2001. "Limit Orders, Depth, and Volatility: Evidence from the Stock Exchange of Hong Kong," Journal of Finance, American Finance Association, vol. 56(2), pages 767-788, April.
    3. Aur'elien Alfonsi & Antje Fruth & Alexander Schied, 2007. "Optimal execution strategies in limit order books with general shape functions," Papers 0708.1756, arXiv.org, revised Feb 2010.
    4. Foucault, Thierry, 1998. "Order Flow Composition and Trading Costs in Dynamic Limit Order Markets," CEPR Discussion Papers 1817, C.E.P.R. Discussion Papers.
    5. Thierry Foucault & Ohad Kadan & Eugene Kandel, 2005. "Limit Order Book as a Market for Liquidity," The Review of Financial Studies, Society for Financial Studies, vol. 18(4), pages 1171-1217.
    6. Kenneth A. Kavajecz, 1999. "A Specialist's Quoted Depth and the Limit Order Book," Journal of Finance, American Finance Association, vol. 54(2), pages 747-771, April.
    7. Obizhaeva, Anna A. & Wang, Jiang, 2013. "Optimal trading strategy and supply/demand dynamics," Journal of Financial Markets, Elsevier, vol. 16(1), pages 1-32.
    8. Martin D. Gould & Mason A. Porter & Stacy Williams & Mark McDonald & Daniel J. Fenn & Sam D. Howison, 2010. "Limit Order Books," Papers 1012.0349, arXiv.org, revised Apr 2013.
    9. Rama Cont & Sasha Stoikov & Rishi Talreja, 2010. "A Stochastic Model for Order Book Dynamics," Operations Research, INFORMS, vol. 58(3), pages 549-563, June.
    10. repec:bla:jfinan:v:59:y:2004:i:2:p:869-898 is not listed on IDEAS
    11. Biais, Bruno & Hillion, Pierre & Spatt, Chester, 1995. "An Empirical Analysis of the Limit Order Book and the Order Flow in the Paris Bourse," Journal of Finance, American Finance Association, vol. 50(5), pages 1655-1689, December.
    12. Martin D. Gould & Mason A. Porter & Stacy Williams & Mark McDonald & Daniel J. Fenn & Sam D. Howison, 2013. "Limit order books," Quantitative Finance, Taylor & Francis Journals, vol. 13(11), pages 1709-1742, November.
    13. Aurelien Alfonsi & Antje Fruth & Alexander Schied, 2010. "Optimal execution strategies in limit order books with general shape functions," Quantitative Finance, Taylor & Francis Journals, vol. 10(2), pages 143-157.
    14. Kempf, Alexander & Korn, Olaf, 1999. "Market depth and order size1," Journal of Financial Markets, Elsevier, vol. 2(1), pages 29-48, February.
    15. Richard Ehrhardt, 1984. "( s , S ) Policies for a Dynamic Inventory Model with Stochastic Lead Times," Operations Research, INFORMS, vol. 32(1), pages 121-132, February.
    16. Jonathan Brogaard & Terrence Hendershott & Ryan Riordan, 2014. "High-Frequency Trading and Price Discovery," The Review of Financial Studies, Society for Financial Studies, vol. 27(8), pages 2267-2306.
    17. Saar, Gideon, 2001. "Price Impact Asymmetry of Block Trades: An Institutional Trading Explanation," The Review of Financial Studies, Society for Financial Studies, vol. 14(4), pages 1153-1181.
    18. Thakor, Anjan V. & Boot, Arnoud (ed.), 2008. "Handbook of Financial Intermediation and Banking," Elsevier Monographs, Elsevier, edition 1, number 9780444515582.
    19. Tse & Forsyth & Kennedy & Windcliff, 2013. "Comparison Between the Mean-Variance Optimal and the Mean-Quadratic-Variation Optimal Trading Strategies," Applied Mathematical Finance, Taylor & Francis Journals, vol. 20(5), pages 415-449, November.
    20. Francois V. Louveaux, 1980. "A Solution Method for Multistage Stochastic Programs with Recourse with Application to an Energy Investment Problem," Operations Research, INFORMS, vol. 28(4), pages 889-902, August.
    21. Ronald L. Goettler & Christine A. Parlour & Uday Rajan, 2005. "Equilibrium in a Dynamic Limit Order Market," Journal of Finance, American Finance Association, vol. 60(5), pages 2149-2192, October.
    22. Fabien Guilbaud & Huyên Pham, 2013. "Optimal high-frequency trading with limit and market orders," Quantitative Finance, Taylor & Francis Journals, vol. 13(1), pages 79-94, January.
    23. René Aïd & P. Gruet & H. Pham, 2016. "An optimal trading problem in intraday electricity markets," Post-Print hal-01609481, HAL.
    24. Ranaldo, Angelo, 2004. "Order aggressiveness in limit order book markets," Journal of Financial Markets, Elsevier, vol. 7(1), pages 53-74, January.
    25. Antje Fruth & Torsten Schöneborn & Mikhail Urusov, 2014. "Optimal Trade Execution And Price Manipulation In Order Books With Time-Varying Liquidity," Mathematical Finance, Wiley Blackwell, vol. 24(4), pages 651-695, October.
    26. Foucault, Thierry, 1999. "Order flow composition and trading costs in a dynamic limit order market1," Journal of Financial Markets, Elsevier, vol. 2(2), pages 99-134, May.
    27. Jingnan Chen & Liming Feng & Jiming Peng & Yinyu Ye, 2014. "Analytical Results and Efficient Algorithm for Optimal Portfolio Deleveraging with Market Impact," Operations Research, INFORMS, vol. 62(1), pages 195-206, February.
    28. LOUVEAUX, François V., 1980. "A solution method for multistage stochastic programs with recourse with application to an energy investment problem," LIDAM Reprints CORE 415, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    29. Glosten, Lawrence R. & Milgrom, Paul R., 1985. "Bid, ask and transaction prices in a specialist market with heterogeneously informed traders," Journal of Financial Economics, Elsevier, vol. 14(1), pages 71-100, March.
    30. Kyle, Albert S, 1985. "Continuous Auctions and Insider Trading," Econometrica, Econometric Society, vol. 53(6), pages 1315-1335, November.
    31. Bertsimas, Dimitris & Lo, Andrew W., 1998. "Optimal control of execution costs," Journal of Financial Markets, Elsevier, vol. 1(1), pages 1-50, April.
    32. Charles Cao & Oliver Hansch & Xiaoxin Wang, 2008. "Order Placement Strategies In A Pure Limit Order Book Market," Journal of Financial Research, Southern Finance Association;Southwestern Finance Association, vol. 31(2), pages 113-140, June.
    33. Goettler, Ronald L. & Parlour, Christine A. & Rajan, Uday, 2009. "Informed traders and limit order markets," Journal of Financial Economics, Elsevier, vol. 93(1), pages 67-87, July.
    34. Ravi Anupindi & Thomas E. Morton & David Pentico, 1996. "The Nonstationary Stochastic Lead-Time Inventory Problem: Near-Myopic Bounds, Heuristics, and Testing," Management Science, INFORMS, vol. 42(1), pages 124-129, January.
    35. Richard Schmalensee, 2012. "Evaluating Policies to Increase Electricity Generation from Renewable Energy," Review of Environmental Economics and Policy, Association of Environmental and Resource Economists, vol. 6(1), pages 45-64.
    36. James R. Bradley & Lawrence W. Robinson, 2005. "Improved Base-Stock Approximations for Independent Stochastic Lead Times with Order Crossover," Manufacturing & Service Operations Management, INFORMS, vol. 7(4), pages 319-329, November.
    37. Gur Huberman & Werner Stanzl, 2004. "Price Manipulation and Quasi-Arbitrage," Econometrica, Econometric Society, vol. 72(4), pages 1247-1275, July.
    38. Forsyth, P.A. & Kennedy, J.S. & Tse, S.T. & Windcliff, H., 2012. "Optimal trade execution: A mean quadratic variation approach," Journal of Economic Dynamics and Control, Elsevier, vol. 36(12), pages 1971-1991.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Da Fonseca, José & Malevergne, Yannick, 2021. "A simple microstructure model based on the Cox-BESQ process with application to optimal execution policy," Journal of Economic Dynamics and Control, Elsevier, vol. 128(C).
    2. Ulrich Horst & Evgueni Kivman, 2024. "Optimal trade execution under small market impact and portfolio liquidation with semimartingale strategies," Finance and Stochastics, Springer, vol. 28(3), pages 759-812, July.
    3. Marjolein E. Verhulst & Philippe Debie & Stephan Hageboeck & Joost M. E. Pennings & Cornelis Gardebroek & Axel Naumann & Paul van Leeuwen & Andres A. Trujillo‐Barrera & Lorenzo Moneta, 2021. "When two worlds collide: Using particle physics tools to visualize the limit order book," Journal of Futures Markets, John Wiley & Sons, Ltd., vol. 41(11), pages 1715-1734, November.
    4. Ulrich Horst & Evgueni Kivman, 2021. "Optimal trade execution under small market impact and portfolio liquidation with semimartingale strategies," Papers 2103.05957, arXiv.org, revised Jul 2023.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Martin D. Gould & Mason A. Porter & Stacy Williams & Mark McDonald & Daniel J. Fenn & Sam D. Howison, 2010. "Limit Order Books," Papers 1012.0349, arXiv.org, revised Apr 2013.
    2. Martin D. Gould & Mason A. Porter & Stacy Williams & Mark McDonald & Daniel J. Fenn & Sam D. Howison, 2013. "Limit order books," Quantitative Finance, Taylor & Francis Journals, vol. 13(11), pages 1709-1742, November.
    3. Danny Lo, 2015. "Essays in Market Microstructure and Investor Trading," PhD Thesis, Finance Discipline Group, UTS Business School, University of Technology, Sydney, number 4-2015, January-A.
    4. Obizhaeva, Anna A. & Wang, Jiang, 2013. "Optimal trading strategy and supply/demand dynamics," Journal of Financial Markets, Elsevier, vol. 16(1), pages 1-32.
    5. Danny Lo, 2015. "Essays in Market Microstructure and Investor Trading," PhD Thesis, Finance Discipline Group, UTS Business School, University of Technology, Sydney, number 22, July-Dece.
    6. Sadoghi, Amirhossein & Vecer, Jan, 2022. "Optimal liquidation problem in illiquid markets," European Journal of Operational Research, Elsevier, vol. 296(3), pages 1050-1066.
    7. Amirhossein Sadoghi & Jan Vecer, 2022. "Optimal liquidation problem in illiquid markets," Post-Print hal-03696768, HAL.
    8. Murphy Jun Jie Lee, 2013. "The Microstructure of Trading Processes on the Singapore Exchange," PhD Thesis, Finance Discipline Group, UTS Business School, University of Technology, Sydney, number 4, July-Dece.
    9. Yamamoto, Ryuichi, 2019. "Dynamic Predictor Selection And Order Splitting In A Limit Order Market," Macroeconomic Dynamics, Cambridge University Press, vol. 23(5), pages 1757-1792, July.
    10. Alberto Ciacci & Takumi Sueshige & Hideki Takayasu & Kim Christensen & Misako Takayasu, 2020. "The microscopic relationships between triangular arbitrage and cross-currency correlations in a simple agent based model of foreign exchange markets," PLOS ONE, Public Library of Science, vol. 15(6), pages 1-19, June.
    11. Menkhoff, Lukas & Osler, Carol L. & Schmeling, Maik, 2010. "Limit-order submission strategies under asymmetric information," Journal of Banking & Finance, Elsevier, vol. 34(11), pages 2665-2677, November.
    12. Hai-Chuan Xu & Wei Chen & Xiong Xiong & Wei Zhang & Wei-Xing Zhou & H Eugene Stanley, 2016. "Limit-order book resiliency after effective market orders: Spread, depth and intensity," Papers 1602.00731, arXiv.org, revised Feb 2017.
    13. Dimitri Vayanos & Jiang Wang, 2012. "Market Liquidity -- Theory and Empirical Evidence," NBER Working Papers 18251, National Bureau of Economic Research, Inc.
    14. Olivier Guéant, 2016. "The Financial Mathematics of Market Liquidity: From Optimal Execution to Market Making," Post-Print hal-01393136, HAL.
    15. Siu, Chi Chung & Guo, Ivan & Zhu, Song-Ping & Elliott, Robert J., 2019. "Optimal execution with regime-switching market resilience," Journal of Economic Dynamics and Control, Elsevier, vol. 101(C), pages 17-40.
    16. Murphy Jun Jie Lee, 2013. "The Microstructure of Trading Processes on the Singapore Exchange," PhD Thesis, Finance Discipline Group, UTS Business School, University of Technology, Sydney, number 2-2013, January-A.
    17. Kashyap, Ravi, 2020. "David vs Goliath (You against the Markets), A dynamic programming approach to separate the impact and timing of trading costs," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 545(C).
    18. Lo, Ingrid & Sapp, Stephen G., 2010. "Order aggressiveness and quantity: How are they determined in a limit order market?," Journal of International Financial Markets, Institutions and Money, Elsevier, vol. 20(3), pages 213-237, July.
    19. Schnaubelt, Matthias, 2022. "Deep reinforcement learning for the optimal placement of cryptocurrency limit orders," European Journal of Operational Research, Elsevier, vol. 296(3), pages 993-1006.
    20. Roberto Pascual & David Veredas, 2010. "Does the Open Limit Order Book Matter in Explaining Informational Volatility?," Journal of Financial Econometrics, Oxford University Press, vol. 8(1), pages 57-87, Winter.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:64:y:2018:i:2:p:784-803. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.