Strong Approximations and Irrationality in Financial Networks with Derivatives

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 well-known type of financial derivative. The main computational challenge for such systems is known as 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. We address the clearing problem in financial networks containing simple debt contracts and credit default swaps. Our work builds on the model proposed by Schuldenzucker et al. [ACM EC (2016); ITCS (2017); ACM EC (2020)], who analyzed the complexity of the \(ε\) -weak (almost)-approximation version of the problem. In this paper, we study the complexity of the problem from the point of view of exact computation, approximation strength and numerically irrational solutions. Our main result establishes FIXP -completeness for the exact computation version of the problem. Consequently, we infer FIXP \({}ₐ\) -completeness for finding a strongly (or “near”) approximate solution as a direct consequence of our main result, while we legitimise the significance of the strong approximation variant through an observation that weakly approximate solutions may “severely” misrepresent the actual financial state of an institution. Finally we study the structural properties required for irrationality, and we identify necessary conditions for numerically 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 second- or higher-degree polynomials. In the absence of a large subclass of such cycles, we study the complexity of finding an exact solution, which we show to be a problem close to, albeit outside of, PPAD .