Clearing financial networks with derivatives: Complexity and Characterisation of Irrationality

This talk is about a challenging computational problem encountered in finance: There is a set of financial institutions (e.g. banks) who hold debt contracts among each other. There are two types of debt contracts: Direct ones (requiring a debtor bank to pay a certain amount to a creditor bank) and Credit Default Swaps, where the amount the creditor needs to pay to the debtor is linearly dependent on the "degree of insolvency" (or: recovery rate) of a third bank. The computational problem is to determine the payments the banks make to each other, and to determine the recovery rates. An instance of this problem can be conveniently visualised as a graph-like structure. 

The problem turns out to be complete for the complexity class FIXP; a class of seemingly challenging fixed point computation problems, capturing both combinatorial and numerical computational issues. I will sketch the proof of this fact, and subsequently I will discuss under what structural properties of the financial network graph, irrational solutions may arise. Irrationality of solutions forms one of the numerical obstacles captured by FIXP. Our results appear to almost-characterise when a given financial network has an irrational clearing solution, and from the point of view of FIXP this leads to the conjecture that under a real model of computation (such as the Blum-Shub-Smale model) taking the closure of the class PPAD under Turing reductions yields the rational-valued fragment of FIXP.  

Based on joint work with Carmine Ventre and Stavros Ioannidis.