Computation and its Limitation in Financial Network Models
Recent work focuses on understanding economic risk in financial markets using classical tools from complexity theory. Modern financial networks consist of economic entities interconnected by debt obligations and derivatives, where the latter are contracts issued upon existing debt obligations in the network. The most used derivatives are the Interest Swap Rate, the Collateralised Debt Obligation (CDO) and the Credit Default Swap (CDS; a derivative connected to the 2008 crisis).
Theoretical computer science branches of algorithmic game theory and mechanism design became the backbone theory for understanding incentivised agents and their interactions in strategic games (markets, internet etc.). Landmark results, such as the characterisation of the complexity of computing a Nash equilibrium in strategic games, reinforce the importance of previously introduced concepts in complexity theory like the PPAD complexity class, and gave birth to new concepts and fields in computational economics (including the study of the price of anarchy and algorithmic mechanism design etc). It is this interaction between the theory of computation and economics that inspired our research regarding the hardness of computing the exposure of economic firms to systemic risk. This computational problem is also known also as the clearing problem.
Our Research
Our work concentrates on financial networks consisting of two types of debts. An unconditional debt obligation defined as a debt contract from one entity to another and a conditional debt obligation that models a CDS, which is a debt obligation among two firms that arises under the condition that a third firm, called the reference entity, cannot pay off its debts. We answer the question of whether it is difficult to compute the proper payments for each firm in the network. Efficiently computing such payments could potentially be used as a tool to predict and prevent an economic crisis outburst. To answer this question, we first define a proper payment scheme that assumes that each firm has a priority list of its debt obligations and pays off one contract after the other until either it pays off its full debts or it has no other available assets. We call such a list a singleton liability priority list. We define the problem of computing the proper payments in a financial network with singleton liability priority lists as CDS-PRIORITY-clearing.
Our paper provides a fixed-point computation framework thus transforming a real-world financial problem into a well-defined computational one. The main theorem proves that CDS-PRIORITY-clearing is a FIXP-complete problem, where FIXP is a computationally hard complexity class that is known to contain various other prominent computational problems that are “similarly” difficult to solve, such as the problem of computing a Nash equilibrium in a strategic game with more than 3 players. Part of our proof involves constructing a financial network that essentially simulates the computation of a fixed point of any given algebraic expression on the operators {+,*,min,max}. Additionally, we prove that a financial regulator cannot efficiently determine the priority lists for each economic firm so as to achieve specific objectives, for example to maximise the income of a particular bank, or to minimise the number of firms that are in default, or to maximise the liquidity in the network (total amount of money that is being transacted). We provide a set of computational hardness results that prove those claims.
Future work
Our research leaves open the problem of constructing alternative payment mechanisms (i.e., payment schemes other than those following a singleton liability priority list) that enable us to efficiently compute the proper payments of each economic firm. On the other hand, if such mechanisms do not exist, then proving that no efficiently computed payment mechanism exists would be an alternative interesting result. Finally, are there payment rules for which the clearing problem falls into a different complexity class than the well-known classes PPAD or FIXP? Insights into this question would also be of great importance and interest.
The above article refers to the paper “Financial Networks with Singleton Liability Priorities” by Stavros Ioannidis, Bart de Keijzer and Carmine Ventre. The paper has been accepted for presentation at the 15th Symposium of Algorithmic Game Theory (SAGT) and received the Best Paper Award. The published version of the paper can be found here.
A similar framework for studying financial networks with derivatives is studied in the paper “Strong Approximations and Irrationality in Financial Networks with Derivatives”, by the same authors, presented at the 49th International Colloquium for Automata Languages and Programming (ICALP) 2022 conference. The paper is available here.
