Computing Tarski Fixed Points in Financial Networks

We show that a minimal clearing state in the Eisenberg-Noe model can be computed in polynomial time. In contrast to computing the maximal one, it seems impossible to formulate the problem directly as an LP. Our approach in Section 3 is a careful adjustment of the bottom iteration for Tarski fixed points. A naive implementation of the bottom iteration (which results, e.g., from distributed clearing processes [8]) would start with the external assets at each bank and then propagate payments and assets into the system. This can take infinite time to converge to the fixed point. Instead of propagating all external assets directly, we inject external assets sequentially and simulate their (infinite) propagation by solving several carefully designed LPs. In particular, upon injection of additional assets at a node $v$, our algorithm distinguishes two cases: (1) all additional assets circulate and gradually reach a “sink” bank without any solvency event, and (2) some assets keep circulating until another bank becomes solvent. Case (1) yields a linear increase in the payments of every claim, and we compute the slopes by solving a polynomial-sized system of linear equations. Then we can inject the assets at $v$ and compute the increase in assets and payments using the slopes. Case (2) arises if any positive portion of the assets injected at $v$ eventually reaches a part $C$ of the network that we term flooded – where all outgoing paths of any node eventually return to that node. More formally, consider the strongly connected components (SCCs) of the remaining network of open claims. The graph of SCCs is a DAG, and a flooded part $C$ is exactly a sink component of the SCC graph, which contains more than one bank. In this case, we do not inject any additional assets at $v$ but instead increase the payments within the sink component $C$ by a circulation (consistent with proportional payments) until a bank becomes solvent. This can be computed using a suitable LP. We then update the SCC graph and again attempt to inject additional assets at $v$. Overall, we see that in each iteration, we either fully inject the external assets of a bank or create a solvent bank. Thus, at most $2n$ iterations are needed.

Our algorithmic ideas turn out to be very powerful to address many generalizations of the problem. First, we relax the condition of proportional payments to the class of arbitrary monotone and piecewise-linear payment functions. This class includes many important examples considered in the literature recently, including edge ranking [4, 17, 14] (or singleton liability priorities [20]), unit-ranking [8, 4, 17], or priority-proportional [22, 13]. By using appropriate granularity, we can handle arbitrary monotone payment functions via approximation with piecewise-linear ones. The extension requires applying our algorithm and the analysis in phases, where each phase ends with reaching an interval border for the payment function of any edge. In each phase, all payments behave linearly, so slopes in case (1) and circulation in case (2) can be obtained by setting up and solving appropriate systems of linear equations. The interval borders of the payment functions limit the increase in external assets of $v$ in case (1), as well as the amount of the circulation in case (2).

Second, we show how to handle an extension of the model to default costs for insolvent banks [27]. Here, the assets of each defaulting bank are additionally reduced by a constant factor. This adjustment represents a linear decrease in the assets, which can be integrated into the network. Since we monotonically increase payments and assets throughout, we (only) need to be careful when a bank $v$ becomes solvent. The challenge is that the fixed point function ceases to be continuous from below. Thus, a standard bottom iteration might fail to guarantee convergence to a minimal clearing state in the limit.

For each bank $v$, we can represent default cost using an auxiliary claim to an auxiliary individual “sink bank” such that this bank receives the default cost. When $v$ becomes solvent, the default cost vanishes, we remove the auxiliary sink bank, and inject the remaining assets as additional external assets at the out-neighbors of $v$. This view directly indicates how our approach of sequential injection of external assets can be extended to handle default cost.

More fundamentally, in Section 3.3 we show an interesting structural equivalence. Every financial network with piecewise-linear payment functions can be transformed into an equivalent network with priority-proportional payments. The transformation increases the representation by at most a polynomial factor. This shows the generality of priority-proportional payment functions. Moreover, it allows applying an existing algorithm for the computation of maximal clearing states [22] to networks with arbitrary monotone, piecewise-linear payments and default cost.

Finally, in Section 4 we study claims trades as a network adjustment to influence the minimal clearing state. The operation was recently formalized in [16]. In a claims trade, a given bank $w$ strives to buy a given claim $e=(u,v)$ from a creditor bank $v$. Formally, $w$ should pay a return $\rho$ from its external assets to $v$ and become creditor of claim $e$. The goal is to give liquidity to $v$ and raise the assets of $v$ in order to mitigate contagion effects as much as possible. In contrast to previous work, we focus on the scenario when the network is evaluated with a minimal clearing state.

Ideally, one would want to compute a return $\rho$ such that both $v$ and $w$ strictly benefit from the trade (w.r.t. the minimal clearing state). We show that this is impossible for all networks with strictly monotone payment functions. This result uses a novel characterization for banks, for which the clearing state is not unique (Lemma 14). Our interest then lies in creditor-positive trades, in which $v$ strictly profits but $w$ stays at least indifferent. For networks with piecewise-linear payment functions, we show how to decide in polynomial time if a creditor-positive claims trade exists, and how to compute one that maximizes the post-trade assets of $v$ if it exists. Our proof shows that the set of returns that yield creditor-positive trades forms a consecutive interval. The largest such return maximizes the assets of $v$, and we can find it by a combination of binary search and maximization of suitable LPs.

For spatial reasons, all missing proofs are deferred to the full version of the paper.

Algorithmic aspects of the Eisenberg-Noe model for financial networks have become a popular topic in recent years. A maximal clearing state can be computed in polynomial time for proportional payments [12], even more generally in networks with default cost [27] and with priority-proportional payments [22]. It is known that decentralized update procedures (which essentially implement a bottom-iteration) converge to the minimal clearing state [8], but these approaches do not necessarily run in polynomial time. Up to our knowledge, an efficient algorithm for minimal clearing has been derived only for networks with edge-ranking payments without default cost [4].

The complexity of computing clearing states has also been considered in an extension of the model to credit-default swaps [29, 30], where clearing states exist but their entries are not necessarily rational. Some notions of approximation yield PPAD-hardness results [29], even for constant approximation factors [10, 19]. Stronger notions of approximation even give rise to FIXP-hardness [18, 20].

Claims trades have recently been studied in the Eisenberg-Noe model without default cost and with maximal clearing [16]. Since a claims trade can be interpreted as a debt swap operation [14, 25], it is impossible that both creditor and buyer banks profit strictly. An optimal creditor-positive trade can be computed in polynomial time for proportional and edge-ranking payment functions. For general functions, it is possible to compute approximately optimal trades in polynomial time. When trading either multiple incoming or multiple outgoing claims of a single bank, finding optimal trades becomes NP-hard. For incoming claims, there is a bicriteria approximation for all monotone payment functions, for outgoing the problem is NP-hard to approximate within polynomial factors even for edge-ranking functions. These results were recently extended and improved in a model with fractional claims trades, for networks with proportional payments and default cost [15].

Our paper is related to a growing body of work that studies structural and algorithmic properties of game-theoretic scenarios based on the Eisenberg-Noe model. Aspects that have received attention include, for example, strategic payment allocation [4, 22, 17, 24], forgiving, cancelling or forwarding debt [23, 21, 33], donations [34], prepayments [36], lending [11], and more [3]. With the exception of [17], all these works consider only maximal clearing states.

More generally, there is work on the complexity of improvement measures for the clearing properties in Eisenberg-Noe financial networks, such as debt swapping [25, 14] or portfolio compression. In portfolio compression, a debt cycle is eliminated from the network. For proportional payments, this can have counter-intuitive effects [28, 35], and many optimization problems surrounding this operation are NP-hard [1].

We define a financial network $ℱ=(V,E,\mathrm{\ell },{𝐚}^{𝐱})$. There is a set $V$ of $n$ banks, and a set $E$ of $m$ directed edges. Each edge $e=(u,v)\in E$ has a non-negative edge weight ${\mathrm{\ell }}_e$ that represents the liability of a claim with debtor $u$ and creditor $v$. Each bank $v$ has non-negative external assets $a_v^{(x)}\ge 0$. For simplicity, we assume that the network has no self-loops or multi-edges²²2These aspects can be incorporated by increasing the notational overhead. We leave the straightforward extension to the interested reader.. We define the set of outgoing and incoming claims of $v$ by $E^{+}(v)=\{e=(v,u)\in E\mid u\in V\}$ and $E^{-}(v):=\{e=(u,v)\in E\mid u\in V\}$, respectively. The total outgoing and incoming liabilities of bank $v$ are $L^{+}(v)={\sum }_{e\in E^{+}(v)}{\mathrm{\ell }}_e$ and $L^{-}(v)={\sum }_{e\in E^{-}(v)}{\mathrm{\ell }}_e$, respectively.

The basic solution concept in the Eisenberg-Noe model is a clearing state, which defines a consistent set of assets $a_u\ge 0$ for each bank $u\in V$. In the standard model, each bank is assumed to clear debt proportionally. Thus, with assets $a_u$, we have a recovery rate $\min (1,a_v/L^{+}(v))$, such that each claim $e=(u,v)$ is cleared to the same fractional extent, i.e., $p_e(a_u)=\min (1,a_v/L^{+}(v))\cdot {\mathrm{\ell }}_e$. Using these payments, the assets have to satisfy the natural asset axioms: The (total) assets of each bank are given by the external assets plus the incoming payments of other banks

In particular, this implies that no bank will conduct fraud by generating money or holding back assets from paying its open claims.

We consider several extensions of the model. First, we consider the model with default cost [27]. Each bank $v$ has a default rate ${\rho }_v\in [0,1]$. If the bank is insolvent, the available assets $a_v$ that can be used to clear debt are reduced to ${\rho }_v\cdot a_v$. The asset axioms for the vector of total assets $𝐚={(a_v)}_{v\in V}$ of the banks become

with the incoming assets of $v$ (before default cost reduction) given by

We recover the standard model without default cost when ${\rho }_v=1$ for all $v\in V$.

Second, we address a general class of monotone payments [4]. Each bank $u$ has a payment function $p_e:ℝ\to ℝ$ for each claim $e=(u,v)$. A payment function satisfies, for each $e\in E$, $u\in U$ and $a_u,\epsilon >0$

These constraints imply that all $p_e$ must be continuous (since $p_e(a+\rho )-p_e(a)⩽\rho$ for any $\rho >0$). The axioms are trivially fulfilled for proportional payments. Many other natural examples of payment functions from this class have been considered, e.g., priority/edge-ranking [4, 8] (rank edges in an order and pay them sequentially until running out of assets), constrained equal awards or losses [9] (all claims receive the same payment or the same non-payment, up their liability) or priority-proportional [22] (partition edges into sets, rank sets in an order, pay edges proportionally within each set, and sequentially over sets until running out of assets). All these examples share a natural property – they are piecewise-linear. In this paper, we concentrate on the class of monotone, piecewise-linear payment functions.

Note that $p_e(a)={\mathrm{\ell }}_e$ when $a\ge L^{+}(v)=x_{e,k_e}$. Thus $m_{e,k_e+1}=0$. We further define $m_e(a)$ as the slope $m_{e,i}$ that applies for argument $a$, i.e., $m_e(a)=m_{e,i}$ such that $a\in [x_{e,i},x_{e,i+1})$. This implies that, for every $v\in V$,

For each bank’s available assets, we define the additional amount of assets until a new interval is reached by ${\delta }_e(a)=\min \{x_{e,i}-a\mid x_{e,i}>a\}$. We denote the total number of interval borders in $ℱ$ by $k={\sum }_{e\in E}{k}_e\ge m$. Finally, for a given vector of total assets $𝐚$, we call an edge $e=(u,v)$ active if $m_e(a_u)>0$. More generally, the set of active edges for $𝐚$ is $E_{𝐚}=\{e\in E\mid e$ is active for $𝐚\}$, and the active graph is $G_{𝐚}=(V,E_{𝐚})$. For each active edge $e\in E_{𝐚}$, the active interval is the index $i$ such that $p_e(a_v)\in [x_{e,i},x_{e,i+1})$.

Given a financial network $ℱ$ and piecewise-linear payment functions $𝐩={(p_e)}_{e\in E}$, a clearing state is simply a vector of assets $𝐚={(a_v)}_{v\in V}$ such that all asset axioms (1) are fulfilled. These axioms are fixed point conditions, since the value of $a_v$ depends on other $a_u$ (and potentially vice versa). Consider the space of all potential asset vectors $𝒜=\underset{v\in V}{⨉}[0,L^{-}(v)+a_v^{(x)}]$. We define a function ${\mathrm{\Phi }}_{{𝐚}^{(x)}}(𝐚):𝒜\to 𝒜$ resulting from applying the map defined by the asset axioms (1). ${\mathrm{\Phi }}_{{𝐚}^{(x)}}$ is monotone since all $p_e$ are monotone. More formally, if ${𝐚}^{\prime }\ge 𝐚$ coordinate-wise, then ${\mathrm{\Phi }}_{{𝐚}^{(x)}}({𝐚}^{\prime })\ge {\mathrm{\Phi }}_{{𝐚}^{(x)}}(𝐚)$ coordinate-wise. The fixed points of $\mathrm{\Phi }$ are the clearing states. Applying the Knaster-Tarski theorem, we see that the set ${𝒜}_f$ of fixed points and the coordinate-wise $\ge$-operation form a complete lattice.

We denote by $\widehat{𝐚}$ the minimal fixed point and by $\check{𝐚}$ the maximal one. A natural attempt towards computation of $\widehat{𝐚}$ is a bottom iteration: Starting from any ${𝐚}^0\le \widehat{𝐚}$ (say, $a_v^0=a_v^{(x)}$ for all $v\in V$) we iteratively compute ${𝐚}^{i+1}={\mathrm{\Phi }}_{{𝐚}^{(x)}}({𝐚}^i)\le \widehat{𝐚}$. Monotonicity directly implies that ${𝐚}^{i+1}\ge {𝐚}^i$. In the model without default cost (all default rates ${\rho }_v=1$) and arbitrary monotone payment functions, it is easy to see that ${lim}_{i\to \mathrm{\infty }}{𝐚}^i=\widehat{𝐚}$, but there are simple instances where ${𝐚}^i\ne \widehat{𝐚}$ for every $i\ge 0$. More generally, when for some $v\in V$, there are simple instances where ${lim}_{i\to \mathrm{\infty }}{𝐚}^i\ne \widehat{𝐚}$. For example, bank $v$ can be solvent in $\widehat{𝐚}$ but insolvent in ${𝐚}^i$, for every $i\ge 0$. Then the limit of the total assets of $v$ is .

An operation to improve clearing states are claims trades. In a claims trade, we are given a claim $e=(u,v)$ and a potential buyer bank $w$. The bank $w$ buys the claim by paying an amount of external assets $\rho$ to $v$. We call $\rho$ the return. In turn, the creditor of the claim $e$ is changed from $v$ to $w$. We assume that the return is upper bounded by $\rho \le \min \{a_w^{(x)},{\mathrm{\ell }}_{(u,v)}\}$. After the trade, the external assets of $w$ are $a_w^{(x)}-\rho$ and the ones of $v$ are $a_v^{(x)}+\rho$. A claims trade can represent a donation, in which $w$ only transfers $\rho$ external assets without changing any edges in the network³³3To formulate donations as special cases of claims trades, we may simply assume that $w$ trades an auxiliary claim $(u,v)$ with liability $a_w^{(x)}$ and no existing payments from an auxiliary debtor bank $u$ of $v$..

We consider claims trades when the network is evaluated with $\widehat{𝐚}$. A claims trade is called creditor-positive if there exists a return $\rho$ such that the assets of creditor bank $v$ are strictly improved and the assets of buyer bank $w$ remain at least the same. We call $\rho$ a creditor-positive return. If it exists, we look for an optimal one, i.e., a creditor-positive return ${\rho }^{\ast }$ that maximizes the post-trade assets of $v$. Note that any creditor-positive trade Pareto-improves the assets in the entire network.

Let $d_u={\check{a}}_u-{\widehat{a}}_u$ be the difference in payments between the greatest and least fixed point. Moreover, let $d_e=p_e({\check{a}}_u)-p_e({\widehat{a}}_u)$ for every edge $e=(u,w)\in E$. Consider any bank $v$ with $d_v>0$. Then every node $u$ reachable from $v$ in the active graph $G_{\widehat{𝐚}}$ must have $d_u>0$. Moreover, $d$ represents a circulation, so ${\sum }_{e\in E^{+}(u)}{d}_e=d_u={\sum }_{e\in E^{-}(u)}{d}_e$ for every bank $u\in V$. This shows that at the end of Algorithm 1, $v$ must be part of a non-sink SCC. Since all payment functions are strictly monotone, the active graph $G_{𝐛}$ is monotonically getting sparser during the execution of Algorithm 1 due to solvency of banks. Moreover, since there is no default cost, the set of sinks in the network is monotonically growing. Thus, if $v$ is part of a non-sink SCC in the end, it must be part of a non-sink SCC throughout the entire execution of the algorithm. However, once assets of $v$ get raised, all non-sink SCCs reachable from $v$ must be flooded. As a consequence, $v$ can only be part of such an SCC at the end of the algorithm when ${\widehat{a}}_v=0$. $◀$

Consider a claims trade with claim $(u,v)$ and buyer $w$. In order to pay any return, $w$ must have external assets $a_w^{(x)}>0$. By Lemma 14, this implies ${\widehat{a}}_w={\check{a}}_w$.

First, suppose that . Then, Lemma 14 implies ${\widehat{a}}_v=0$. As discussed in the proof of the lemma, $v$ is part of a non-sink SCC in $G_{\widehat{𝐚}}$. Moreover, $w$ must be unreachable from $v$ in $G_{\widehat{𝐚}}$. Since all payment functions are strictly monotonic, the active graph becomes only sparser for larger payments. Hence, $w$ remains unreachable from $v$ even when $v$ has higher assets. Consequently, it is impossible for $w$ to recover any portion of the return $\rho$ paid to $v$ by larger incoming payments. Thus, there cannot be a creditor-positive trade when .

Second, suppose that ${\widehat{a}}_v={\check{a}}_v$. Now, if there was such a trade, w.r.t. $\widehat{𝐚}$, this trade would also strictly improve the assets of both parties w.r.t. $\check{𝐚}$. This is impossible [16]. $◀$