Computing Tarski Fixed Points in Financial Networks

Paper: arXiv 2602.16387

Authors: Leander Besting, Martin Hoefer, Lars Huth

Abstract

Modern financial networks are highly connected and result in complex interdependencies of the involved institutions. In the prominent Eisenberg-Noe model, 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 that runs in strongly polynomial time. It applies in a broad generalization of the Eisenberg-Noe model with any monotone, piecewise-linear payment functions and default costs. Moreover, in this scenario we provide a polynomial-time algorithm to compute a maximal fixed point. For networks without default costs, we can efficiently decide the existence of fixed points in a given range. 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.

Complexity vs Empirical Score

• Math Complexity: 8.0/10
• Empirical Rigor: 1.5/10
• Quadrant: Lab Rats — theoretically deep, empirically untested

Why this score: The paper makes a strong theoretical contribution to systemic risk modeling by providing the first strongly polynomial-time algorithms for computing minimal Tarski fixed points in generalized Eisenberg-Noe networks. However, as a purely theoretical computer science/algorithmic paper, it lacks empirical data, backtesting, or real-world financial validation.

Research Flowchart

  flowchart TD
    A[Research Goal: Compute Fixed Points & Analyze Claims Trading in Financial Networks] --> B[Inputs: Network Topology, Asset Vector, Monotone Piecewise-Linear Payment Functions & Default Costs]
    B --> C[Algorithm 1: Compute Minimal Clearing Vector]
    B --> D[Algorithm 2: Compute Maximal Clearing Vector]
    C --> E[Polynomial-Time Claims Trading Analysis]
    
    C --> F[Outcome: Minimal & Maximal Fixed Points Computed in Strongly Polynomial Time]
    D --> F
    E --> G[Outcome: Decidable Range Existence & Optimal Pareto-Improving Trades Identified]

Cited References (62)

1. Improved Hardness Results for the Clearing Problem in Financial Networks with Credit Default Swaps — → 2409.18717
2. Weakly Chained Matrices, Policy Iteration, and Impulse Control (2016)
3. A Sufficient Condition for Nonvanishing of Determinants (1974)
4. Equilibria and Convergence in Fire Sale Games (2023)
5. Systemic Risk and Stability in Financial Networks (2015)
6. Systemic credit freezes in financial lending networks (2021)
7. Clearing Financial Networks with Derivatives: From Intractability to Algorithms (2023)
8. Liquidity and Solvency Risks in Financial Networks (2023)

3 of 62 cited works are in the corpus; resolved via arXiv source bundles, Semantic Scholar and OpenAlex. Corpus-wide: 2518 linked papers.