21.09.2016New Working Paper "Finding Clearing Payments in Financial Networks with Credit Default Swaps is PPAD-hard"

We consider the problem of clearing a system of interconnected banks that have been exposed to a shock on their assets. Eisenberg and Noe (2001) showed that when banks can only enter into simple debt contracts with each other, then a clearing vector of payments can be computed in polynomial time. In this paper, we show that the situation changes radically when banks can also enter into credit default swaps (CDSs), i.e., financial derivative contracts that depend on the default of another bank. We prove that computing even an approximate solution to the clearing problem with polynomial accuracy is PPAD-hard. To do this, we demonstrate how financial networks with debt and CDSs can encode arithmetic operations such as addition and multiplication. Further analysis of our construction reveals that already determining which banks are in default is a PPAD-hard problem. This makes apparent the origin of the additional complexity introduced by CDSs: that banks may profit from the ill-being of other banks. [pdf]