Abstract
Financial networks model a set of financial entities, such as firms or banks, interconnected by monetary obligations. Recent work has introduced to this model a class of obligations called Credit Default Swaps “CDS”, a well-known type of financial derivative. The main computational challenge in financial systems is the “clearing” problem. This problem involves the task of determining insolvent firms and quantifying their exposure to systemic risk. The technical term used to describe this exposure is the “clearing recovery rate”. In essence, the “clearing” problem involves computing the clearing recovery rates of all financial institutions in a given network.It is established that the “clearing” problem, is computationally tractable when dealing with simple debt contracts [EN01], while existing techniques show PPAD-hardness for finding a weak approximate ϵ-solution when CDSes are involved, within an unspecified small range for ϵ [SSB17b]. This thesis addresses the “clearing” problem in financial networks containing simple debt contracts and credit default swaps and presents results on the following aspects of the problem:
• Exact Computation: We establish that the exact computation version of the problem is FIXP-complete. We infer FIXPa-completeness for finding a strongly (or “near”) approximate solution as a direct consequence.
• Approximation Strength: We establish an improved explicit inapproximability bound for computing weak (or “almost”) approximate solutions.
• Algorithms and Heuristic: We focus on two meaningful restrictions of the class of financial networks motivated by regulations: (i) the presence of a central clearing authority; and, (ii) the restriction to covered CDSes introduced in [SSB20]. We provide the following results.
i) The PPAD-hardness for weak approximation persists when central clearing authorities are introduced.
ii) An optimisation-based method for solving the “clearing” problem with central clearing authorities.
iii) A simple polynomial-time algorithm when the two restrictions hold simultaneously.
Additionally we identify necessary structural conditions of the financial system that suffice for numerically irrational solutions to emerge. In the absence of these conditions, we study the complexity of finding an exact solution, which we show to be a problem close to, albeit outside of, PPAD.
We also present supplementary results on the computational complexity of the “clearing” problem in financial networks with derivatives, whenever payment priorities among creditors are applied. This practically relevant model has only been studied from a game-theoretic standpoint. Specifically, we examine the “clearing” problem whenever firms pay according to a Singleton Liability Priority list and prove that it is also FIXP-complete. Finally, we provide a number of NP-hardness results for the task of selecting the optimal priority list, i.e, the list that optimises specific objectives of interest.
The aim of this thesis is to contribute to the literature on the “clearing” problem with debt contracts and credit default swaps. In this direction we present progress in existing knowledge as well as new results that establish the clearing problem as an important computational challenge at the intersection of finance and computation, having both theoretical and practical interest. To facilitate this connection, we highlight the progress made on the “clearing” problem and how this progress aligns with the progress marked in the field along the period of publishing these results. This work arranges thematically and provides a unified presentation of the material published in the following research papers:
• Strong Approximations and Irrationality in Financial Networks with Derivatives [IDKV22]
• Financial Networks with Singleton Liability Priorities [IDKV23b]
• Clearing Financial Networks with Derivatives: From Intractability to Algorithms [IdKV23a
| Date of Award | 1 Aug 2024 |
|---|---|
| Original language | English |
| Awarding Institution |
|
| Supervisor | Bart De Keijzer (Supervisor) & Carmine Ventre (Supervisor) |