Strong Approximations and Irrationality in Financial Networks with Derivatives

Authors Stavros D. Ioannidis , Bart de Keijzer , Carmine Ventre



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.76.pdf
  • Filesize: 0.82 MB
  • 18 pages

Document Identifiers

Author Details

Stavros D. Ioannidis
  • Department of Informatics, King’s College London, UK
Bart de Keijzer
  • Department of Informatics, King’s College London, UK
Carmine Ventre
  • Department of Informatics, King’s College London, UK

Cite AsGet BibTex

Stavros D. Ioannidis, Bart de Keijzer, and Carmine Ventre. Strong Approximations and Irrationality in Financial Networks with Derivatives. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 76:1-76:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.76

Abstract

Financial networks model a set of financial institutions (firms) interconnected by obligations. Recent work has introduced to this model a class of obligations called credit default swaps, a certain kind of financial derivatives. The main computational challenge for such systems is known as the clearing problem, which is to determine which firms are in default and to compute their exposure to systemic risk, technically known as their recovery rates. It is known that the recovery rates form the set of fixed points of a simple function, and that these fixed points can be irrational. Furthermore, Schuldenzucker et al. (2016) have shown that finding a weakly (or "almost") approximate (rational) fixed point is PPAD-complete. We further study the clearing problem from the point of view of irrationality and approximation strength. Firstly, we observe that weakly approximate solutions may misrepresent the actual financial state of an institution. On this basis, we study the complexity of finding a strongly (or "near") approximate solution, and show FIXP-completeness. We then study the structural properties required for irrationality, and we give necessary conditions for irrational solutions to emerge: The presence of certain types of cycles in a financial network forces the recovery rates to take the form of roots of non-linear polynomials. In the absence of a large subclass of such cycles, we study the complexity of finding an exact fixed point, which we show to be a problem close to, albeit outside of, PPAD.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • FIXP
  • Financial Networks
  • Systemic Risk

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Euro-parliament bans "naked" credit default swaps. EUBusiness. URL: https://www.eubusiness.com/news-eu/finance-economy-cds.dij.
  2. Lasting effects: The global economic recovery 10 years after the crisis. IMFBlogs. URL: https://blogs.imf.org/2018/10/03/lasting-effects-the-global-economic-recovery-10-years-after-the-crisis/.
  3. Daron Acemoglu, Asuman Ozdaglar, and Alireza Tahbaz-Salehi. Systemic risk and stability in financial networks. American Economic Review, 105(2):564-608, 2015. Google Scholar
  4. Nils Bertschinger, Martin Hoefer, and Daniel Schmand. Strategic payments in financial networks. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of LIPIcs, pages 46:1-46:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.46.
  5. Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale. Complexity and real computation. Springer Science & Business Media, 1998. Google Scholar
  6. Rodrigo Cifuentes, Gianluigi Ferrucci, and Hyun Song Shin. Liquidity risk and contagion. Journal of the European Economic association, 3(2-3):556-566, 2005. Google Scholar
  7. Larry Eisenberg and Thomas H Noe. Systemic risk in financial systems. Management Science, 47(2):236-249, 2001. Google Scholar
  8. Matthew Elliott, Benjamin Golub, and Matthew O Jackson. Financial networks and contagion. American Economic Review, 104(10):3115-53, 2014. Google Scholar
  9. Kousha Etessami and Mihalis Yannakakis. On the complexity of nash equilibria and other fixed points. SIAM Journal on Computing, 39(6):2531-2597, 2010. Google Scholar
  10. Aris Filos-Ratsikas, Yiannis Giannakopoulos, Alexandros Hollender, Philip Lazos, and Diogo Poças. On the complexity of equilibrium computation in first-price auctions. arXiv preprint arXiv:2103.03238, 2021. Google Scholar
  11. Aris Filos-Ratsikas, Kristoffer Arnsfelt Hansen, Kasper Høgh, and Alexandros Hollender. Fixp-membership via convex optimization: Games, cakes, and markets. arXiv preprint, 2021. URL: http://arxiv.org/abs/2111.06878.
  12. Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod. Settling the complexity of leontief and PLC exchange markets under exact and approximate equilibria. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 890-901. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055474.
  13. Paul Glasserman and H Peyton Young. How likely is contagion in financial networks? Journal of Banking & Finance, 50:383-399, 2015. Google Scholar
  14. Paul W Goldberg and Alexandros Hollender. The hairy ball problem is ppad-complete. Journal of Computer and System Sciences, 2021. Google Scholar
  15. Sebastian Heise and Reimer Kühn. Derivatives and credit contagion in interconnected networks. The European Physical Journal B, 85(4):1-19, 2012. Google Scholar
  16. Brett Hemenway and Sanjeev Khanna. Sensitivity and computational complexity in financial networks. Algorithmic Finance, 5(3-4):95-110, 2016. Google Scholar
  17. Daning Hu, J Leon Zhao, Zhimin Hua, and Michael CS Wong. Network-based modeling and analysis of systemic risk in banking systems. MIS quarterly, pages 1269-1291, 2012. Google Scholar
  18. Stavros D. Ioannidis, Bart de Keijzer, and Carmine Ventre. Strong approximations and irrationality in financial networks with financial derivatives. CoRR, abs/2109.06608, 2021. URL: http://arxiv.org/abs/2109.06608.
  19. Pál András Papp and Roger Wattenhofer. Default ambiguity: finding the best solution to the clearing problem. arXiv preprint, 2020. URL: http://arxiv.org/abs/2002.07741.
  20. Pál András Papp and Roger Wattenhofer. Network-aware strategies in financial systems. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 91:1-91:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.91.
  21. Leonard CG Rogers and Luitgard AM Veraart. Failure and rescue in an interbank network. Management Science, 59(4):882-898, 2013. Google Scholar
  22. Steffen Schuldenzucker, Sven Seuken, and Stefano Battiston. Clearing payments in financial networks with credit default swaps. In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 759-759, 2016. Google Scholar
  23. Steffen Schuldenzucker, Sven Seuken, and Stefano Battiston. Finding clearing payments in financial networks with credit default swaps is PPAD-complete. LIPIcs: Leibniz International Proceedings in Informatics, 67, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail