Computing Tarski Fixed Points in Financial Networks

DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

Abstract

Modern financial networks are highly connected and result in complex interdependencies of the involved institutions. In the prominent Eisenberg-Noe model [Eisenberg and Noe, 2001], a fundamental aspect is clearing - to determine the amount of assets available to each financial institution in the presence of potential defaults and bankruptcy. A clearing state represents a fixed point that satisfies a set of natural axioms. Existence can be established (even in broad generalizations of the model) using Tarski’s theorem. While a maximal fixed point can be computed in polynomial time, the complexity of computing other fixed points is open. In this paper, we provide an efficient algorithm to compute a minimal fixed point. Our algorithm applies in a broad generalization of the Eisenberg-Noe model with any monotone, piecewise-linear payment functions and default costs. We also study claims trading, a local network adjustment to improve clearing, when networks are evaluated with minimal clearing. We provide an efficient algorithm to decide existence of Pareto-improving trades and compute optimal ones if they exist.

Authors 3

1. Leander Besting Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Department of Computer Science, RWTH Aachen University, Germany

2. Martin Hoefer Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Department of Computer Science, RWTH Aachen University, Germany

3. Lars Huth Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Department of Computer Science, RWTH Aachen University, Germany