Dynamic Debt Swapping in Financial Networks

After discussing preliminaries in Section 2, we classify debt swaps into positive (both creditors profit strictly in the clearing after the swap), semi-positive (one creditor profits strictly, the other one remains the same), or arbitrary ones. Our characterization results in Section 3 show that in every financial network, there can be no positive swap. Semi-positive swaps can exist, and, in fact, they always represent a Pareto-improvement: After the swap no bank in the entire network suffers, every bank obtains at least as many assets as before. As such, the recovery rate of every bank weakly increases, as well as the payments towards every debt contract. This makes semi-positive swaps very attractive. Similar results were shown by Papp and Wattenhofer [15] for proportional payments. Our paper generalizes these results substantially to all monotone payments.

We then concentrate on improvement dynamics with semi-positive debt swaps. Since they Pareto-improve the assets of all banks (and strictly for a creditor bank), every sequence of semi-positive swaps is inherently acyclic and terminates in a local optimum. A natural and challenging question that we study in Section 4 is whether there are short sequences that allow to reach a local optimum in polynomial time. We further refine the characterization of semi-positive swaps for ranking-based payments into saturating, and extension swaps, and further into active, semi- and non-active extension swaps. We show that there can be at most a polynomial number of saturating, semi- and non-active extension swaps, so the core of the problem lies in the existence of short sequences of active extension swaps. When a single bank $v$ strictly profits from every semi-positive swap, then we prove that every sequence of active extension swaps has indeed a length polynomial in the size of the network (and, thus, so has every sequence of semi-positive swaps). Instead, when we consider arbitrary swaps in which a given bank $v$ strictly improves, then there are initial networks from which every sequence of such swaps has exponential length. More fundamentally, we prove that it is PLS-complete to construct any local optimum, i.e., any network where liabilities of each node are consistent with the initial network and that allows no (arbitrary) debt swap in which the assets of a given bank $v$ strictly increase.

The problem without the property of strict improvement for a single bank $v$ turns out to be extremely challenging. We also make some progress here – under a condition on the liabilities and the in-degree of partly paid edges of every bank, we can show existence of a short sequence of semi-positive swaps to a local optimum. The general problem remains as an interesting avenue for future work.

All missing proofs are deferred to the full version of this paper. Moreover, in the full version we also consider aspects of global optimization (i.e., maximize the assets of a single bank via a sequence of debt swaps) and reachability problems (i.e., decide if a target network structure can be reached using a sequence of debt swaps).

There has been a recent surge of interest in the algorithmic and game-theoretic aspects of financial networks. Most works adopt and extend the clearing model by Eisenberg and Noe [4] (discussed in more detail below), where banks are nodes, edges are debt contracts, and clearing is governed by proportional payments. Most closely related to our work is recent work by Papp and Wattenhofer [15], who introduce and study the concept of debt swaps for proportional payments. They show that positive swaps do not exist, semi-positive swaps lead to Pareto-improvement, discuss shock models and hardness of a number of optimization problems. Another network-altering operation was recently introduced by Kanellopoulos et al. [11]. A debt transfer describes the process of a bank transferring a debt claim to another creditor. Formally, this operation exchanges a path of length two by one single edge. The authors consider optimization problems and a game-theoretic model where the banks strategically decide whether or not to perform a debt transfer.

More generally, algorithmic aspects of (extensions of) the Eisenberg-Noe model have been subject to substantial recent interest, including, e.g., the computation of clearing states in networks with credit-default swaps (CDS) [20, 9, 8]. Some clearing models (e.g., using CDS’es) suffer from default ambiguity [21], and several strategies for resolving this problem have been proposed [16]. Changes of the instance in terms of adding or deleting single liabilities, donations to other banks, lending, manipulation of external assets, allocation of stimulus checks, or bailouts were analyzed in [14, 10, 3, 13]. While most works assume the clearing state to manifest as a fixed point, the impact of sequential updates is studied in [17]. Further temporal aspects are investigated in [5], where liabilities are associated with individual maturity intervals. The works investigate the complexity of allocating integral and fractional payments in order to minimize defaults.

There is a growing interest in clearing problems beyond the restriction to proportional payments, using more general classes of monotone functions to model the clearing process [2]. This extension poses many interesting algorithmic and, in particular, game-theoretic problems that are very recently starting to get explored [1, 12, 7].

A financial network $ℱ=(G,\text{de},\text{cr},𝐥,{𝐚}^x,𝐟)$ is given by a weighted, directed multi-graph $G=(V,E)$ with $|V|=n$ nodes and $|E|=m$ edges. Each node $v\in V$ resembles a financial institution or bank. Each edge $e\in E$ represents a debt contract, where a debtor bank $\text{de}(e)\in V$ owes an amount of $l_e\in {\mathbb{N}}_{>0}$ to a creditor bank $\text{cr}(e)$. Formally, $e$ is a directed edge $(\text{de}(e),\text{cr}(e))$ with weight $l_e$. We assume that there are no loops, i.e., $\text{de}(e)\ne \text{cr}(e)$. The set of incoming and outgoing edges of $v$ are denoted by $E^{-}(v)=\{e\in E\mid \text{cr}(e)=v\}$ and $E^{+}(v)=\{e\in E\mid \text{de}(e)=v\}$. The total liabilities of a bank $v$ are defined as $L_v={\sum }_{e\in E^{+}(v)}{l}_e$. Further, every bank holds external assets $a_v^x\in \mathbb{N}$, i.e., assets of $v$ that are independent of the network. The payments that a bank receives from its debtors within network are called internal assets and, together with external assets, form the available assets of a bank.

An allocation rule is a collection $𝐟={({𝐟}_v)}_{v\in V}$, where for bank $v$ ${𝐟}_v={(f_e)}_{e\in E^{+}(v)}$ determines a distribution of the available assets $b_v\in {ℝ}_{\ge 0}$ towards her liabilities. $f_e:{ℝ}_{\ge 0}\to [0,l_e]$ is the payment function for edge $e\in E^{+}(v)$. For every bank $v$, the payment functions satisfy the following properties: (1) $f_e$ is continuous¹¹1Monotonicity, edge capacity, and limited flow conservation together imply continuity. We postulate it explicitly for convenience. and non-decreasing in $b_v$ (monotonicity), (2) each bank pays at most the respective liability, i.e., $f_e(b_v)\le l_e$ (edge capacity), and (3) every bank spends all assets until all liabilities are paid off, i.e., ${\sum }_{e\in E^{+}(v)}{f}_e(b_v)=\min \{b_v,L_v\}$ (limited flow conservation). The available assets of $v$ are the sum of external and internal assets $b_v=a_v^x+{\sum }_{e\in E^{-}(v)}{f}_e(b_{\text{de}(e)})\ge 0$.

These constraints give rise to a fixed-point problem. A vector of assets ${(b_v)}_{v\in V}$ that fulfills all constraints is called feasible. For every allocation rule $𝐟$, the set of feasible vectors forms a complete lattice w.r.t. coordinate-wise comparison [1, 2]. Consequently, for every allocation rule $𝐟$ there exists a supremum ${(a_v)}_{v\in V}$ of feasible assets and resulting payments $𝐩={(p_e)}_{e\in E}$ with $p_e=f_e(a_{\text{de}(e)})$ that pointwise maximize the assets of each bank and the payments on each edge. The clearing settles on these maximal payments, which we term the clearing state. In the clearing state, bank $v$ receives total incoming assets of ${\sum }_{e\in E^{-}(v)}{p}_e$ and holds total assets of $a_v=a_v^x+{\sum }_{e\in E^{-}(v)}{p}_e$.

In this paper, we will discuss all our results consistently in the context of a natural class of edge-ranking rules [1, 2, 9]: For each bank $v$, her outgoing edges $E^{+}(v)$ are ordered by a permutation ${\pi }_v$. First, $v$ directs all her payments towards edge ${\pi }_v(1)$ until the edge is completely paid off or $v$ has no remaining assets. Then, she pays off edge ${\pi }_v(2)$ until the edge is completely paid off or $v$ has no remaining assets. This process continues until either all debt is settled or $v$ runs out of funds.

Apart from being natural and well-motivated in applications, edge-ranking rules also have appealing computational properties. Given a financial network with edge-ranking rules, a maximal clearing state can be computed in strongly polynomial time [1]. Moreover, these favorable properties extend to general monotone integral [2, 1] allocation rules in explicit representation by using edge-rankings over a suitable set of auxiliary edges [1]. In this way, all our statements generalize to unit-ranking rules with edge-ranking representation.

Other classes of payments have also been of interest in the literature (e.g., proportional payments, where every bank allocates her total assets in proportion to her total liabilities, or combinations of ranking and proportional). Indeed, many of our results extend even to arbitrary monotone allocation rules.

For a given financial network $ℱ$, a debt swap $\sigma$ is a structural change to the network. For two edges $e_1,e_2$ among four distinct banks with the same liability (i.e., $l_{e_1}=l_{e_2}=:\mathrm{\ell }$) we exchange their creditors. The result can be described by an adjustment in the creditor function by swapping the entries of $e_1$ and $e_2$. Note that the allocation rule $𝐟$ of the banks remains unaffected by the swap, since the debtor function remains unchanged. However, due to the structural change, a debt swap may change the payments in the clearing state. We denote the resulting financial network, creditor function, clearing state, and total assets of a bank $v$ after the swap by ${ℱ}^{\sigma }$, ${\text{cr}}^{\sigma }$, ${𝐩}^{\sigma }$ and $a_v^{\sigma }$, respectively.

Observe that a debt swap may introduce multi-edges even in initially simple graphs. We proceed with a small example that shows some of the interesting effects of debt swaps.

A debt swap of two edges $e_1$ and $e_2$ maintains the local network properties of the debtors $u_1$ and $u_2$. It has no effect on the set of liability values. Moreover, it does not impact their incoming edges. As such, we are interested in the gains and losses in total assets of the creditors $v_1$ and $v_2$, since (arguably) they are the key actors to implement a debt swap. The following classification of debt swaps slightly extends the one in [15]. Observe that the debt swap explained in Example 2 is semi-positive and Pareto-improving.