§ OVERVIEW

§.§ Edge-Ranking

"arbitrary (sem. pos.) with $v$" refers to (sem. pos.) swaps where $v$ is an acting node with strict profit.
.1em3cmobj. fct.swaps     sem. pos.     sem. pos. with $v$     arbitrary     arbitrary with $v$

2*max social welfare     2*NPC (approx)
(MaxIS)      2*NPC
(3-Partition)      2*NPC
(VertexCover)      2*NPC

2*max assets of $u$     2*NPC (approx)
(MaxIS)     2*NPC
(3-Partition)     2*NPC
(SetCover)     2*NPC

2*max assets of $v$     2*NPC (approx)
(MaxIS)     2*NPC
(3-Partition)     2*NPC
(SetCover)     2*NPC

2*local opt
max social welfare     2*P ?     2*P     2*PLS
(Max2SAT)     2*?

2*local opt
max assets of $u$     2*P     2*P     2*PLS
(Max2SAT)     2*?

2*local opt
max assets of $v$     2*P     2*P     2*PLS
(Max2SAT)     2*?

§.§ Proportional

.1em3cmobj. fct.swaps     sem. pos.     sem. pos. with $v$     arbitrary     arbitrary with $v$

2*max social welfare     2*NPC (approx)
(MaxIS)      2*NPC
(Partition)       2*NPC
(VertexCover)      2*NPC

2*max assets of $u$     2*NPC (approx)
(MaxIS)     2*NPC
(Partition)     2*NPC
(SetCover)     2*NPC

2*max assets of $v$     2*NPC (approx)
(MaxIS)     2*NPC
(Partition)     2*NPC
(SetCover)     2*NPC

2*local opt
max social welfare     2*?     2*?     2*PLS
(Max2SAT)     2*?

2*local opt
max assets of $u$     2*?     2*?     2*PLS
(Max2SAT)     2*?

2*local opt
max assets of $v$     2*?     2*?     2*PLS
(Max2SAT)     2*?

§.§ Reachability Problem

.1em3cmstrat.swaps     sem. pos.     sem. pos. with $v$     arbitrary     arbitrary with $v$

2*edge-ranking     2*NPC
(3-Partition)     2*NPC
(3-Partition)      2*pseudo-poly     2*

2*proportional     2*     2*     2*     2*

Remaining Todos:

* Delete todo-notes/comments

A debt swap is an elementary edge swap in a directed, weighted graph, where two edges with the same weight swap their targets. Debt swaps are a natural and appealing operation in financial networks, in which nodes are banks and edges represent debt contracts. They can improve the clearing payments and the stability of these networks. However, their algorithmic properties are not well-understood.

We analyze the computational complexity of debt swapping in networks with ranking-based clearing. Our main interest lies in semi-positive swaps, in which no creditor strictly suffers and at least one strictly profits. These swaps lead to a Pareto-improvement in the entire network. We consider network optimization via sequences of $v$-improving debt swaps from which a given bank $v$ strictly profits. We show that every sequence of semi-positive $v$-improving swaps has polynomial length. In contrast, for arbitrary $v$-improving swaps, the problem of reaching a network configuration that allows no further swaps is -complete. We identify cases in which short sequences of semi-positive swaps exist even without the $v$-improving property.

In addition, we study reachability problems, i.e., deciding if a sequence of swaps exists between given initial and final networks. We identify a polynomial-time algorithm for arbitrary swaps, show -hardness for semi-positive swaps and even -completeness for $v$-improving swaps or swaps that only maintain a lower bound on the assets of a given bank $v$. A variety of our results can be extended to arbitrary monotone clearing.

§ INTRODUCTION

Over the last decades, the international financial system has evolved into a complex and highly interconnected network. The close structural connections can give rise to devastating cascading effects, which have been a major issue in the financial crisis of 2008 and its aftermath. Recently, there has been an increasing research interest in the computational complexity of network-based interbank models for financial systems. A fundamental aspect of these models is clearing, a process of debt resolution by which solvency of banks in the system gets determined. In particular, in a financial network (where banks are nodes, and weighted, directed edges correspond to debt contracts) the clearing problem asks for a consistent assignment of payments of debtor banks to their creditors. Based on the clearing, a bank might not receive the full amount of credit it gave to others. As a consequence, it might not have sufficient funds to clear all her own debt. The solution to the clearing problem is of central importance to banks since it directly affects their assets.

Banks have a natural incentive to improve their clearing conditions. Moreover, governmental regulators, central banks, and other financial services have an interest in maintaining and improving the financial system. While payment rules for clearing are often fixed, several other suggestions for improvement exist, affecting the (external) assets of the banks or the network structure
(such as, e.g., bailouts [31], portfolio compression [42, 35], and more).

A particularly interesting variant of network improvement is debt swapping [28]: There are two debt contracts among two pairs of banks $(u_1,v_1)$ and $(u_2,v_2)$. The contracts have the same value. In a debt swap, the creditor banks $v_1$ and $v_2$ change their role as recipients of these contracts. This leaves every bank with the same amounts of debt as before – only the network is affected by the exchange of the edges. A debt swap is a local edge-swap operation and represents a small change in the network structure. Since it involves only a small number of banks, it can be executed in a distributed fashion by the participating banks. Clearly, the banks are likely to agree to this operation only if it does not deteriorate their network position, i.e., it does not decrease their assets in the clearing of the resulting network.

Debt swaps are a very natural and interesting swap operation with many conceptual advantages. For example, they are usually less demanding than the more prominent approach of portfolio compression [35, 42] (for a discussion of the relation between these two operations see [28]). From a computational perspective, debt swaps are a fascinating recent addition to the literature on edge swap operations in graphs. Numerous variants of such swaps have attracted a large interest in computer science over the decades (see related work discussed below). The computational aspects of this swap operation, however, are not well understood.

In this paper, we analyze the computational complexity of debt swaps. We conduct a broad study of network optimization problems surrounding the swap operation. Since a debt swap is a local improvement step in the network, we first focus on local optimization (e.g., from an initial network, can we reach a configuration that allows no more profitable debt swaps?). In addition, 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). We discuss all our results consistently for networks in which banks use natural ranking-based clearing payments [10, 5, 20]. Indeed, many of our results can be extended to arbitrary monotone clearing. Throughout the paper we mention the extension explicitly whenever it applies.

Contribution and Techniques
After discussing preliminaries in Section <ref>, 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 (discussed in detail in Appendix <ref>) 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. This makes semi-positive swaps very attractive. Similar results were shown before by Papp and Wattenhofer [28] for proportional payments. We here show similar conditions for ranking-based payments. Indeed, our proofs generalize to all monotone payments and substantially generalize their arguments.

Our work concentrates 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 <ref> 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 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 as well as 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 -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.

In Section <ref> we then turn to reachability problems: Given an initial and a target network on the same set of nodes $V$, the goal is to decide whether or not there is a sequence of debt swaps to turn the initial network into the target network. For arbitrary debt swaps, we show that the problem can be solved in polynomial time. In contrast, when we have to maintain a lower bound on the assets of a bank $v$ throughout, the problem becomes -complete. For semi-positive debt swaps, we show that the problem is -hard.

Moreover, in Appendix <ref>, we consider global optimization, i.e., the problem of determining the maximal assets of a given bank that can be obtained by a sequence of debt swaps from a given initial network. We show that this problem is -hard to approximate, both when considering arbitrary or only semi-positive debt swaps. Similar hardness results apply when determining the maximal sum of assets of several banks.

For spatial reasons, we defer some of the proofs to Appendix <ref>.

Related Work
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 [13] (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 [28], 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.

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) [36, 20, 21]. Some clearing models (e.g., using CDS'es) suffer from default ambiguity [37], and several strategies for resolving this problem have been proposed [29]. Changes of the instance in terms of adding or deleting single liabilities, donations to other banks, manipulation of external assets, or bailouts were analyzed in [27, 24]. While most works assume the clearing state to manifest as a fixed point, the influence of sequential updates in the emergence of the clearing is studied in [30].

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 [10]. This extension poses many interesting algorithmic and, in particular, game-theoretic problems that are very recently starting to get explored [5, 23, 19].

On a conceptual level, debt swaps are closely related to other variants of edge swaps that have attracted a lot of interest in the literature. Similar edge swaps have been used for several decades in the area of edge-switching Markov chains for graphs with a given degree sequence (see e.g., [7] as well as, e.g., [4] and the references therein). In contrast to our work, the Markov chains are random processes to generate random graphs, and there is usually no utility or value for individual nodes resulting from the network.

Edge swaps in networks, where individual nodes obtain value from the network, are studied prominently in matching markets. Dynamics based on blocking pairs have been analyzed prominently for stable matchings in [25, 32, 12, 1, 17, 18]. Resolving a blocking pair is not a swap since we insert a single new (preferred) edge while removing up to two existing ones. True swaps that re-match four nodes have also attracted interest in various scenarios [2, 8, 9, 11, 6, 15]. The analysis concentrates on aspects we also study here: Are the swap dynamics acyclic? Or is there at least a path to stability, i.e., a sequence of profitable swaps for the nodes resulting in a network where no more profitable swap exists? How long are these swap sequences? Can we compute them in polynomial time? Can they be found by distributed dynamics?

Finally, reachability problems are studied in the area of network reconfiguration, which has attracted interest for decades (for some early works, see, e.g., [39, 40]; for surveys on this area see [22, 41]). Closely related to our paper is recent work on turning multigraphs into simple graphs via sequences of double edge swaps [38].

§ MODEL AND PRELIMINARIES

Financial Networks, Clearing, and Ranking
We follow previous literature and define financial networks as follows. A financial network $\F=(G, \vecl, \veca^x, \vecf)$ is given by a weighted, directed 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 $(u,v) \in E$ with weight $l_{(u,v)} \in \NN_{>0}$ indicates that bank $u$ owes $v$ the amount of $l_{(u,v)}$. We assume that there are no multi-edges and no loops, i.e., no bank has liabilities towards herself. The set of incoming and outgoing edges of $v$ are denoted by $E^-(v)$ and $E^+(v)$, respectively. 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^x_v \in \NN$, i.e., assets of $v$ that are independent of the network.

An allocation rule is a collection $\vecf=(\vecf_v)_{v\in V}$, where $\vecf_v = (f_e)_{e \in E^+(v)}$ determines a distribution of the available assets $b_v \in \RR_{\geq 0}$ for bank $v$ towards her liabilities. $f_e : \RR_{\geq 0} \rightarrow [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[In fact, continuity can be shown as a consequence of the combination of monotonicity, edge capacity and limited flow conservation constraints. We mention 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) \leq 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^x_v + \sum_{e=(u,v) \in E-(v)}f_e(b_u) \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 $\vecf$, the set of feasible vectors forms a complete lattice w.r.t. coordinate-wise comparison [5, 10]. Consequently, for every allocation rule $\vecf$ there exists a supremum $(a_v)_{v \in V}$ of feasible assets and resulting payments $\vecp =(p_e)_{e\in E}$ with $p_{(v,u)} = f_{(v,u)}(a_v)$ 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^x_v + \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 [5, 10, 20]: 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 [5]. Moreover, these favorable properties extend to general monotone integral [10] (also termed unit-ranking [5]) allocation rules in explicit representation by using edge-rankings over a suitable set of auxiliary edges [5]. 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[In this case, every bank distributes her total assets in proportion to her total liabilities, i.e., the payments of $v$ towards edge $e$ are given by $f_e(b_v) = \min\{b_v\cdot \frac{l_e}{L_v}, l_e\}$.] or combinations of ranking and proportional). Indeed, many of our results extend even to arbitrary monotone allocation rules.

Debt Swaps
For a given financial network $\F$, a debt swap $\sigma$ is a structural change to the network. For two edges $(u_1,v_1),\,(u_2,v_2)$ with the same liability (i.e., $l_{(u_1, v_1)} = l_{(u_2, v_2)} =: \ell$) we exchange their endpoints. The result are the edges $(u_1, v_2)$ and $(u_2, v_1)$, both with liability $\ell$. The allocation rule $\vecf$ of the banks is unaffected by the swap (i.e., $(u_1,v_2)$ plays the role of $(u_1,v_1)$ for bank $u_1$, and similarly for $u_2$). However due to the structural change, the debt swap may change the payments in the clearing state. We denote the resulting financial network and the corresponding graph, clearing state, and total assets of a bank $v$ after the swap by $\sig{\F}$, $\sig{G}$, $\sig{\vecp}$ and $\sig{a}_v$, respectively.

Suppose we are given a financial network $\F$ with edges $e_1=(u_1, v_1), e_2=(u_2,v_2)\in E$ and liabilities $l_{(u_1, v_1)} = l_{(u_2, v_2)}$ among pairwise distinct nodes $u_1,v_1,u_2,v_2 \in V$. A debt swap $\sigma$ of $e_1$ and $e_2$ creates a new network $\sig{\F}=(\sig{G},\sig{\vecl},\veca^x,\sig{\vecf})$ where (1) in $\sig{G}$ we remove $e_1$ and $e_2$, and add $\sig{e}_2 = (u_1, v_2)$ and $\sig{e}_1 = (u_2,v_1)$ with liabilities $l_{\sig{e}_2} = l_{\sig{e}_1} = l_{e_1}$ , (2) we set $\sig{f}_{\sig{e}_2} = f_{e_1}$ and $\sig{f}_{\sig{e}_1} = f_{e_2}$, and (3) all remaining edges, liabilities and payment functions remain unaffected.

Throughout the paper, we denote by $(p_e)_{e \in E}$ and $(\sig{p}_e)_{e \in \sig{E}}$ the clearing payments before and after the swap, respectively. We proceed with a small example showing some of the interesting effects of debt swaps.

[>=stealth', shorten >=1pt, auto,
node distance=1cm,
transform shape, align=center,
bank/.style=circle, draw, inner sep = 1]
[bank] (u1) at (0,0) $u_1$;
[bank] (v1) [right = of u1] $v_1$;
[bank] (u2) [above = of u1] $u_2$;
[bank] (v2) [above = of v1] $v_2$;
[bank] (w1) [right = of v1] $w_1$;
[bank] (w2) [right = of v2] $w_2$;
[rectangle, draw=black, inner sep=2.5pt] (xv2) [above=0.1cm of v2] $1$;

[->] (u1) to (v1);
[->] (u2) to (v2);
[->] (v1) to[in=240, out=210, looseness=2.8] (u2);
[->,dashed] (v1) to[bend right] (w1);
[->] (w1) to[bend right] (v1);
[->] (v2) to node[above, midway] $1$ (w2);

[>=stealth', shorten >=1pt, auto,
node distance=1cm,
transform shape, align=center,
bank/.style=circle, draw, inner sep = 1]
[bank] (u1) at (0,0) $u_1$;
[bank] (v1) [right = of u1] $v_1$;
[bank] (u2) [above = of u1] $u_2$;
[bank] (v2) [above = of v1] $v_2$;
[bank] (w1) [right = of v1] $w_1$;
[bank] (w2) [right = of v2] $w_2$;
[rectangle, draw=black, inner sep=2.5pt] (xv2) [above=0.1cm of v2] $1$;

[->] (u1) to (v2);
[->] (u2) to node[below=2pt, pos=0.1] $1$ (v1);
[->] (v1) to[in=240, out=210, looseness=2.8] node[below=2pt, at start] $1$ (u2);
[->,dashed] (v1) to[bend right] node[below, midway] $1$ (w1);
[->] (w1) to[bend right] node[above, midway] $1$ (v1);
[->] (v2) to node[above, midway] $1$ (w2);

The figures visualize a financial network $\F$  before (left) and $\sig{\F}$ after a debt swap (right). All edges have unit weight and edge labels indicate payments. For $v_1$, the solid edge is the preferred outgoing edge. $v_2$ has external assets of 1 as shown in the node label.

Consider the initial financial network in Figure <ref> (left) with edge-ranking allocation rules. Bank $v_1$ first pays off all debt to $u_2$ before directing payments to $w_1$, i.e, $\pi_{v_1}(1)=(v_1,u_2), \pi_{v_1}(2)=(v_1,w_1)$. All other banks pay towards their unique outgoing edge. Consider the clearing state. For bank $v_2$ the external assets of 1 equal her total liabilities $L_{v_2}$. Thus, $v_2$ can settle all her debt towards $w_2$. For the other edges, suppose there are positive payments on edge $(u_2,v_2)$. Then, by definition, $u_2$ has to have these assets available, so $v_1$ must pay this amount to $u_2$. By the same argument, $u_1$ must have positive total assets and pay them to $v_1$. However, $u_1$ obviously has no assets, and there are no payments on these edges. Due to the allocation rule of $v_1$, there are no payments in the cycle of $v_1$ and $w_1$, unless $v_1$ fully pays off $(v_1,u_2)$ first (for which she needs assets from $u_1$). The clearing state yields a payment of 1 on $(v_2,w_2)$. The total assets are 1 for $v_2$ and $w_2$, and 0 otherwise.

Now consider the financial network in Figure <ref> (right) after the swap of edges $(u_1,v_1)$ and $(u_2,v_2)$ to $(u_1,v_2)$ and $(u_2,v_1)$. Obviously, $v_2$ can still pay off her single outgoing edge. After the swap, there is a cycle including $v_1$ and $u_2$ over prioritized edges. When the payments on both edges are raised to 1, the fixed-point properties remain satisfied. Since $v_1$ pays off all debt on the edge with highest priority, she will direct any additional assets towards the edge of her second priority to $w_1$. Here a new cycle with $w_1$ over prioritized edges arises, and the fixed-point conditions allow to further raise payments along that cycle to 1.

The additional payments after the swap result from the emergence of the cycle between $u_2$ and $v_1$. The total assets of $v_1,u_2$ and $w_1$ are increased to $a_{v_1}=2, a_{u_2}=1$ and $a_{w_1}=1$ after the swap. For the total assets of the other banks the swap is inconsequential.

A debt swap of two edges $(u_1,v_1)$ and $(u_2,v_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 [28]. Observe that the debt swap explained in Example <ref> is semi-positive and Pareto-improving.

A debt swap of $\sigma$ in a financial network $\F$ is called (1) positive if $\sig{a}_{v_1} > a_{v_1}$ and $\sig{a}_{v_2} > a_{v_2}$, (2) semi-positive if $\sig{a}_{v_1} \geq a_{v_1}$ and $\sig{a}_{v_2} \geq a_{v_2}$ and exactly one inequality is strict, (3) Pareto-improving if $\sig{a}_{v} \geq a_{v}$ for all $v\in V$ and at least one inequality is strict.

§.§ Swap-Subtract Problem

For local search via debt swaps, the core complexity is encapsulated in a neat tree reconfiguration problem, which we term the  problem. To the best of our knowledge, this problem has not been considered before. We are given a directed, weighted rooted in-tree $T=(V,E)$ with root $r$. Each edge $e \in E$ has a non-negative weight $w_e \in \NN$ and a color $c_e \in \C$. A swap-to-root switches the endpoints of an edge $e_1=(u_1,v)$ in the tree with an edge $e_2=(u_2,r)$ incident to the root. A swap-to-root can only be performed when $e_1$ and $e_2$ have the same color and $w_{e_1} > w_{e_2}$. Upon performing the swap, we remove $e_1$ and $e_2$ and add edges $e'_1=(u_1,r)$ and $e'_2=(u_2,v)$ with weight $w_{e'_1} = w_{e_1}$ and $w_{e'_2} = w_{e_2}$. They both have the same color as $e_1$ and $e_2$. Further, the weight of every edge $e$ on the unique path from $v$ to $r$ is decreased by $w_{e_1}-w_{e_2}$. A swap-to-root is called feasible if all decreased edge weights remain non-negative. Note that, as a consequence, in every swap-to-root the total weight of edges incident to $r$ remains constant.

Starting from an initial in-tree, we are interested in computing a short sequence of feasible swaps to a tree for which no further feasible swaps exist.

In a variation Min-$v$-, we can swap edges $e_1=(u_1,v_1)$ and $e_2=(u_2,v_2)$ when $v_1$ is in the subtree of $v_2$. Again, the swap can only be performed when $e_1$ and $e_2$ have the same color and $w_{e_1} > w_{e_2}$. Upon performing the swap, we remove $e_1$ and $e_2$ and add edges $e'_1=(u_1,v_2)$ and $e'_2=(u_2,v_1)$ with weight $w_{e'_1} = w_{e_1}$ and $w_{e'_2} = w_{e_2}$. They both have the same color as $e_1$ and $e_2$. The weight of every edge $e$ on the unique path from $v_1$ to $v_2$ is decreased by $w_{e_1}-w_{e_2}$. A swap is called feasible if all decreased edge weights remain non-negative. It is $v$-improving if the total weight of node $v$ strictly decreases after the swap (i.e., $v$ is a node on the $v_1$-$v_2$-path, but not $v_2$).

[circle, draw=black, inner sep = 3] $r$ [grow = down]

child node [circle, draw=black, inner sep = 1] $u_1$
edge from parent[stealth-, blue] node [right] $2$

child node [circle, draw=black, inner sep = 3] $v$

child node [circle, draw=black, inner sep = 1] $u_3$

child node [circle, draw=black, inner sep = 1] $u_5$
edge from parent[stealth-, blue] node [right] $5$
child node [circle, draw=black, inner sep = 1] $u_4$
edge from parent[stealth-, blue] node [right] $12$
edge from parent[stealth-, red] node [right] $5$

child node [circle, draw=black, inner sep = 1] $u_2$
edge from parent[stealth-, blue] node [right] $6$
edge from parent[stealth-] node [right] $8$;

[circle, draw=black, inner sep = 3] $r$ [grow = down]

child node [circle, draw=black, inner sep = 1] $u_2$
edge from parent[stealth-, blue] node [right] $6$

child node [circle, draw=black, inner sep = 3] $v$

child node [circle, draw=black, inner sep = 1] $u_3$

child node [circle, draw=black, inner sep = 1] $u_5$
edge from parent[stealth-, blue] node [right] $5$
child node [circle, draw=black, inner sep = 1] $u_4$
edge from parent[stealth-, blue] node [right] $12$
edge from parent[stealth-, red] node [right] $5$

child node [circle, draw=black, inner sep = 1] $u_1$
edge from parent[stealth-, blue] node [right] $2$
edge from parent[stealth-] node [right] $4$;

[circle, draw=black, inner sep = 3] $r$ [grow = down]

child node [circle, draw=black, inner sep = 1] $u_5$
edge from parent[stealth-, blue] node [right] $5$

child node [circle, draw=black, inner sep = 3] $v$

child node [circle, draw=black, inner sep = 1] $u_3$

child node [circle, draw=black, inner sep = 1] $u_1$
edge from parent[stealth-, blue] node [right] $2$
child node [circle, draw=black, inner sep = 1] $u_4$
edge from parent[stealth-, blue] node [right] $12$
edge from parent[stealth-, red] node [right] $2$

child node [circle, draw=black, inner sep = 1] $u_2$
edge from parent[stealth-, blue] node [right] $6$
edge from parent[stealth-] node [right] $5$;

[circle, draw=black, inner sep = 3] $r$ [grow = down]

child node [circle, draw=black, inner sep = 1] $u_2$
edge from parent[stealth-, blue] node [right] $6$

child node [circle, draw=black, inner sep = 3] $v$

child node [circle, draw=black, inner sep = 1] $u_3$

child node [circle, draw=black, inner sep = 1] $u_1$
edge from parent[stealth-, blue] node [right] $2$
child node [circle, draw=black, inner sep = 1] $u_4$
edge from parent[stealth-, blue] node [right] $12$
edge from parent[stealth-, red] node [right] $2$

child node [circle, draw=black, inner sep = 1] $u_5$
edge from parent[stealth-, blue] node [right] $5$
edge from parent[stealth-] node [right] $4$;

Visualization of Example <ref>. Left: Initial tree. Second from left: Tree after swap of $(u_2,v),(u_1,r)$. Right: Trees after swaps of $(u_5,u_3),(u_1,r)$ and then $(u_2,v),(u_5,r)$. Black edge labels indicate edge weights.

Consider the  for the left tree in Fig. <ref>. The black and the red edge cannot be swapped. For the blue edges, the swap-to-root $(u_2,v),(u_1,r)$ decreases the edge weight of $(v,r)$ by $w_{(u_2,v)}-w_{(u_1,r)} = 6-2=4$. No further feasible swap-to-root is possible, since the only candidate swap with $(u_2,r),(u_4,u_3)$ would decrease the weight of $(u_3,v)$ to a negative number. A local optimum is reached. If instead we first swap the edges $(u_5,u_3),(u_1,r)$, then we reduce the weights along the path from $u_3$ to $r$ by $w_{(u_5,u_3)}-w_{(u_1,r)}=5-2=3$ (second from right in Fig. <ref>). Afterwards, $(u_2,v),(u_5,r)$ can be swapped, since the weight reduction on $(v,r)$ is only $6-5=1$ (right in Fig. <ref>). In this state, no more swaps-to-root are feasible. It represents another local optimum that can be reached.

Observe that for the node $v$, in the initial network the only feasible $v$-improving swap is $(u_5,u_3),(u_1,r)$. Afterwards, the tree is in a local optimum (w.r.t. feasible $v$-improving swaps).

§.§ Characterization

To reason about debt swaps, we first provide a structural analysis of the clearing payments before and after debt swaps. We obtain a characterization of semi-positive and positive swaps. The analysis substantially generalizes techniques from [28] and yields two major insights. First, there are no positive swaps. Second, every semi-positive debt swap yields a Pareto-improvement in the entire network, i.e., no bank in the financial network is harmed while at least one bank strictly profits. Interestingly, the converse also holds: Every Pareto-improving debt swap is semi-positive. For detailed proofs see Appendix <ref>.

A financial network with edge-ranking rules allows no positive debt swap.

For a financial network with edge-ranking rules, a debt swap is semi-positive if and only if it is Pareto-improving.

Similar to [28], we use an auxiliary network with the same payments as the resulting network after the debt swap. In this auxiliary network, we replace the swap edges with auxiliary sources and sinks for the involved nodes with appropriate assets representing the payments on the swap edges. For a contradiction, we assume that the debt swap is positive. Then, by tracing the payments in the auxiliary network, we show that payments in the original network before the debt swap did not correspond to the maximum clearing state. This yields a contradiction and shows that positive swaps cannot exist. As a rather direct consequence from this characterization, we obtain that semi-positive swaps lead to a Pareto-improvement in the entire network.

The main distinction from the proof for proportional payments in [28] is that these payments are limited to a particular structure in the auxiliary network and, as such, easier to handle. Instead, our proof for edge-ranking rules turns out to rely only on  monotonicity of the allocation rule. By arguing about a broad range of possibilities and dependencies of potential payments, we can show that the result indeed applies to finanical networks with any monotone payment rules.

A financial network with monotone allocation rules allows no positive debt swap. In such a network a debt swap is semi-positive if and only if it is Pareto-improving.

§ DEBT SWAP DYNAMICS

When two creditors perform a debt swap, the structure of the underlying graph changes. This might enable further swaps which potentially further increase the assets of the involved banks. In this way, the debt swap operation naturally gives rise to dynamics where, in each step, a pair of creditors agree to perform a debt swap in the current network. Conceptually, semi-positive swaps are very attractive – they are equivalent to Pareto-improving swaps and improve the situation not only for the creditors but for the entire network.

In this section, we consider natural distributed dynamics of debt swaps. Given an initial financial network with monotone allocation rules, our goal is to find a small number of semi-positive debt swaps to reach a local optimum, i.e., a network structure without semi-positive swaps. We denote this as the  problem. While all banks (weakly) profit from a semi-positive swap, we are interested in semi-positive swaps that are $v$-improving, i.e., strictly increase the assets of a given bank $v$. This is natural, e.g., when $v$ is a creditor that profits strictly in every such swap, or $v$ is a bank that is “too big to fail” and should strictly profit from network changes. We denote the problem with semi-positive $v$-improving swaps by . Given a financial network, can we reach a local optimum using a sequence of polynomial many semi-positive $v$-improving debt swaps?

We consider this question for the broad class of edge-ranking rules. In a given network with $m$ edges, there are at most $m \choose 2$ edge swaps. Recall that we can compute the clearing state for edge-ranking rules in strongly polynomial time [5]. Hence, for a given network, we can also enumerate all semi-positive debt swaps in strongly polynomial time.

[>=stealth', shorten >=1pt, auto,
node distance=1cm, scale=1,
transform shape, align=center,
bank/.style=circle, draw, inner sep=0.1cm]
[bank] (1) at (0,0) $v_1$;
[bank] (2) [right = of 1] $v_2$;
[bank] (3) [right = of 2] $v_3$;
[bank] (4) [right = of 3] $v_4$;
[bank] (5) [below = of 1] $v_5$;
[bank] (6) [below = of 2] $v_6$;
[bank] (7) [below = of 3] $v_7$;
[bank] (8) [below = of 4] $v_8$;

[->] (1) to node[above, midway] $1$ (2);
[->] (5) to node[above, midway] $1$ (6);
[->] (6) to node[above, midway] $2$ (7);
[->] (3) to node[above, midway] $3$ (4);
[->] (7) to node[above, midway] $3$ (8);
[->] (4) to[bend right] node[above, midway] $4$ (1);

[>=stealth', shorten >=1pt, auto,
node distance=1cm, scale=1,
transform shape, align=center,
bank/.style=circle, draw, inner sep=0.1cm]
[bank] (1) at (0,0) $v_1$;
[bank] (2) [right = of 1] $v_2$;
[bank] (3) [right = of 2] $v_3$;
[bank] (4) [right = of 3] $v_4$;
[bank] (5) [below = of 1] $v_5$;
[bank] (6) [below = of 2] $v_6$;
[bank] (7) [below = of 3] $v_7$;
[bank] (8) [below = of 4] $v_8$;

[->] (1) to node[right=0.1cm, pos=0.1] $1$,$1$ (6);
[->] (5) to node[right=0.1cm, pos=0.1] $1$ (2);
[->] (6) to node[above, midway] $2$,$1$ (7);
[->] (3) to node[right=0.1, pos=0.1] $3$ (8);
[->] (7) to node[right=0.1, pos=0.1] $3$,$1$ (4);
[->] (4) to[bend right] node[above, midway] $4$,$1$ (1);

Two financial networks with the same set of banks where no bank holds external assets. Blue edge labels indicate edge weights while black edge labels indicate payments. In both networks no semi-positive debt swap exists.

Consider the problem for the financial network in Figure <ref> on the left. Since every bank has at most one outgoing edge, every bank pays all assets towards its single creditor. No bank holds external assets and there exists no cycle in the network. For these reasons, no payments can emerge that satisfy the fixed point constraint. Hence, the total assets of every bank are zero. Observe that the edges $(v_1,v_2),(v_5,v_6)$ and $(v_3,v_4),(v_7,v_8)$ have the same edge weights and thus can be swapped. When one of the possible debt swaps is performed, there still exists no cycle in the network. Hence, no debt swap is a Pareto-improvement and the considered financial network is a local optimum.

Now consider the network on the right side of Figure <ref> where both debt swaps were applied. The resulting network has a cycle including $v_1,v_6,v_7$ and $v_4$ where payments of 1 can emerge on each edge in the cycle. This network is a global optimum with respect to total assets.

§.§ Sequences of Semi-Positive Swaps

Characterization Consider a bank $v$ with edge-ranking rule. $v$ pays her outgoing edges in the order of a permutation $\pi_v$ until she runs out of funds. Assume $v$ cannot settle all debt. Let $e$ denote the unique highest-ranked outgoing edge of $v$ that is not fully paid. We call $e$ the active edge of $v$. Clearly, all edges $e'$ with higher priority than $e$ are fully paid for, i.e., they are saturated. Additionally, all edges $e'$ with lower priority than $e$ receive no payments. Note that the set of all active edges is acyclic – we can strictly increase the feasible payments along any cycle, which is impossible when the clearing state has maximal feasible payments.

A semi-positive swap Pareto-improves the total assets of all banks. It can only increase the number of saturated edges. If a semi-positive swap saturates at least one additional edge, we call it a saturating swap. As a second class, let us consider extension swaps, which are non-saturating swaps with an interesting structural property.

Consider a semi-positive debt swap $\sigma$ of edges $e_1$ and $e_2$ with $p_{e_1}<p_{e_2}$. The swap is called extension swap if (1) no additional edge gets saturated and (2) in $\F$ there is an active path $P$, i.e., a path of active edges from $v_1$ to $v_2$, (3) $l_e - p_e > p_{e_2}-p_{e_1}$ for every $e \in P$, (4) in the clearing state $p_{e_1} = \sig{p}_{e_2}$ and $p_{e_2} = \sig{p}_{e_1}$.

In an extension swap, creditors $v_1$ and $v_2$ swap two edges $e_1$ and $e_2$ with different payments, where w.l.o.g. we assume $p_{e_2}>p_{e_1}$. The swap does not create a cycle of active edges, it would result in a new saturated edge along this cycle. As a consequence, $v_1$ receives in $\sig{\F}$ additional incoming assets of $\delta_{v_1} = p_{e_2}-p_{e_1}>0$. Since there exists a path $P$ from $v_1$ to $v_2$ of active edges, each with residual liability of more than $\delta_{v_1}$, the additional assets get routed completely to $v_2$. The total assets of $v_2$ after the swap remain the same (see Figure <ref> for an example).

[>=stealth', shorten >=1pt, auto,
node distance=1cm, scale=1,
transform shape, align=center,
bank/.style=circle, draw, inner sep=0.1cm]

[bank] (u1) at (0,0) $u_1$;
[bank] (u2) [right= of u1] $u_2$;
[bank] (v1) [below= of u1] $v_1$;
[bank] (v2) [right= of v1] $v_2$;
[rectangle, draw=black, inner sep=2.5pt] (xu2) [right=0.15cm of u2] $k$;

[->] (u1) – (v1);
[->] (u2) – node[right, midway] $k$ (v2);
[->] (v1) to[bend right] (v2);

[>=stealth', shorten >=1pt, auto,
node distance=1cm, scale=1,
transform shape, align=center,
bank/.style=circle, draw, inner sep=0.1cm]

[bank] (u1) at (0,0) $u_1$;
[bank] (u2) [right= of u1] $u_2$;
[bank] (v1) [below= of u1] $v_1$;
[bank] (v2) [right= of v1] $v_2$;
[rectangle, draw=black, inner sep=2.5pt] (xu2) [right=0.15cm of u2] $k$;

[->] (u1) – (v2);
[->] (u2) – node[right=0.1, pos=0.3] $k$ (v1);
[->] (v1) to[bend right] node[below, midway] $k$ (v2);

Minimal example of an extension swap where all edges have weight $M>k$. Edges without label have no payments in the clearing state. Conceptually, the swap extends the path taken by payments of $u_2$ to reach $v_2$, thereby increasing the total assets of $v_1$ along the way.

The next proposition proves an interesting and very useful characterization.

For a given financial network with edge-ranking rules, every semi-positive debt swap is either a saturating or an extension swap.

We further classify extension swaps based on the activation status of the involved edges.

Consider extension swap $\sigma$ of edges $e_1$ and $e_2$ with $p_{e_1} < p_{e_2}$. In a non-active swap both edges are nonactive. In a semi-active swap, $e_1$ is active and $e_2$ is non-active. In a fully-active swap, both $e_1$ and $e_2$ are active.

Observe that in a non-active swap, the edges $e_1$ and $e_2$ are each either fully saturated or receive no payments. Since $p_{e_1}<p_{e_2}$, we have both $p_{e_1}=0$ and $p_{e_2} = l_{e_2}$. In a semi-active swap, either $p_{e_1} = 0$ or $p_{e_2} = l_{e_2}$. Finally, in a fully-active swap, $0 \le p_{e_1} < p_{e_2} < l_{e_2}$.

Periods, Phases, and Active Extension Swaps

We now discuss constructing short sequences of swaps. Let us first consider saturating swaps.

Given an initial financial network with edge-ranking rules and $m$ edges, every sequence of semi-positive debt swaps can contain at most $m$ saturating ones.

We define a period as a sequence of consecutive extension swaps. Clearly, every sequence of semi-positive swaps has at most $m+1$ periods. We turn attention to non-active and semi-active extension swaps.

Given an initial financial network with edge-ranking rules and a sequence of semi-positive debt swaps.
In a single period, there can be at most $2 \cdot |E^-(v)|$ many non-active or semi-active extension swaps such that $v$ is the non-profiting creditor, for every $v \in V$.

For each semi-active swap of this kind, one of two possible events occurs: Either (1) an incoming non-active saturated edge of $v$ is changed to an active (non-saturated) one, or (2) an incoming active edge of $v$ with positive payment is changed to a non-active one with 0 payment. In a non-active swap, a sequential composition of both events occurs: An incoming non-active saturated edge of $v$ is changed directly to a non-active one with 0 payments.

In a semi-positive swap, the payment on every edge can only weakly increase. No edge gets saturated (this would end the period). Hence, no active edge can become non-active (neither saturated, nor with 0 payments). Thus, events (1) and (2) cannot re-occur for an incoming edge of $v$. As such, there can be at most $2 \cdot |E^-(v)|$ events for node $v$ in the period and, hence, at most $2 \cdot |E^-(v)|$ many non-active or semi-active extension swaps with $v$ as the non-profiting creditor.

As a consequence, from an initial network with $m$ edges, there are at most $O(m^2)$ saturating, non-active, or semi-active extension swaps. The challenge lies in bounding the number of active extension swaps. We define a phase as a sequence of consecutive active extension swaps. For bounding the length of swap sequences to a polynomial, Observation <ref> and Lemma <ref> allow to restrict attention to the number of swaps in a single phase.

Recall that the set of active edges is cycle-free. Moreover, every node has at most one outgoing active edge. Consequently, the set of active edges forms a forest of in-trees. We denote the set of these in-trees by $\mathcal{T}$. In an active extension swap, the active path $P$ runs from $v_1$ to $v_2$. As such, we can only have extension swaps where all four banks involved in the swap are in the same tree $T \in \mathcal{T}$, and the non-profiting creditor $v_2 \in T$ is an ancestor of all $v_1, u_1, u_2 \in T$.

We first focus on sequences of active extension swaps that strictly improve a given bank $v$. Afterwards, we consider the more general case of arbitrary active extension swaps.

§.§.§ Improvement for a Given Bank

We analyze sequences of semi-positive swaps that are $v$-improving for a given bank $v$, i.e., in every swap $v$ strictly profits. Note that $v$ may not be involved in the swap as a creditor bank herself. Our main result is the following.

For every bank $v$ in a financial network with edge-ranking rules, every sequence of $v$-improving semi-positive swaps has polynomial length.  can be solved in polynomial time.

[>=stealth', shorten >=1pt, auto,
node distance=1cm, scale=1,
transform shape, align=center,
bank/.style=circle, draw, inner sep=1,
triangle/.style = regular polygon, regular polygon sides=3, rotate=297, draw, inner sep=4pt,
btriangle/.style = regular polygon, regular polygon sides=3, rotate=0, draw, inner sep=4pt]

[circle, draw, inner sep=5pt] (v) at (0,0) ;
[circle, draw, inner sep=3pt] (u1) [above right=0.1cm and 1cm of v] $v$;
[circle, draw, inner sep=5pt] (u2) [above right=0.1cm and 1cm of u1] ;
[bank] (v2) [above right=0.1cm and 1cm of u2] $v_2$;
[btriangle] (tu1) [below=0.75cm of u1] ;
[btriangle] (tu2) [below=0.75cm of u2] ;

[btriangle] (tv2) [below=0.75cm of v2] ;
[bank] (v1) [below left =0.1cm and 1cm of v] $v_1$;
[regular polygon, regular polygon sides=3, rotate=63, draw, inner sep=4pt] (tv) [below right=0.6cm and 1cm of v1] ;
[triangle] (tv1) [below left=0.6cm and 1cm of v1] ;
[btriangle] (tv12) [below=0.75cm of v1] ;

[->, line width=0.04cm] (v1) to (v);
[->, line width=0.04cm] (v) to (u1);
[->, line width=0.04cm] (u1) to (u2);
[->, line width=0.04cm] (u2) to (v2);
[->] (tv1) to (v1);
[->] (tv12) to (v1);
[->] (tv) to (v1);
[->, thick, blue!50!white] (tv1) to node[below=0.1cm, midway] $p_{e_1}$ (v1);
[->] (tu1) to (u1);
[->] (tu2) to (u2);

[->, thick, blue!50!white] (tv2) to node[right=0.1cm, pos=0.4] $p_{e_2}$ (v2);

Schematic picture of a $v$-improving semi-positive swap of active edges where payments $p_{e_2}>p_{e_1}$. Triangles indicate subtrees. When the blue edges are swapped then payments on the thick black edges strictly increase.

It suffices to prove the result for active extension swaps in a single phase. Consider the tree $T$ containing $v$. Suppose there is an active extension swap, then the set of banks that strictly profit lie on the active path $P$, with the exception of creditor $v_2$. Hence, if such a swap is also $v$-improving, $v$ is a node on the active path, the creditor $v_1$ is $v$ or a descendant of $v$, and the creditor $v_2$ is an ancestor of $v$. As such, all active edges on the path $P_v$ from $v$ to the root of $T$ cannot be swapped. In terms of payments, the edges whose payments are strictly increased by the swap are located in $T_v$ or on the path $P_v$. The swap keeps all other payments the same.

Note that for the swap, $p_{e_1} < p_{e_2}$, i.e., the edge $e_2$ with higher payment is incoming to the ancestor $v_2$ of $v$ and gets swapped to $v_1 = v$ or a descendant $v_1$ of $v$. For $v_2$, the only incoming edge that increases in payment is the one on $P_v$. All other incoming edges of $v_2$ only keep their payments (when not being swapped) or are replaced by ones with strictly decreased payments (when being swapped). In contrast, for each edge, payments are non-decreasing over time. This implies that if edge $e_2$ is swapped away from $v_2$, the same edge cannot re-appear at $v_2$ at a later stage. For a schematic illustration see Figure <ref>.

Hence, a single phase contains at most $m^2$ many $v$-improving active extension swaps.

This result is potentially surprising, since for other allocation rules there are indeed extremely long sequences of such swaps. In Appendix <ref> we prove that with proportional rules there are exponentially long sequences of $v$-improving semi-positive swaps.

There is an initial financial network with $n$ banks, $n$ edges, and proportional allocation rule, from which there is a sequence of $\Omega(2^n)$ many $v$-improving semi-positive swaps.

§.§.§ Beyond Improvement for a Given Bank

In the remainder of the section, we concentrate on arbitrary active extension swaps (without the property that they are $v$-improving). Bounding the length of such sequences represents a very challenging problem. We make some initial progress on this problem: For a non-trivial class of instances, we construct a single short sequence of such swaps in each phase.

For the remainder of the section, we focus on instances with two network conditions. First, suppose that throughout every node has at most $d$ incoming active edges, for some constant $d$. For example, $d=1$ means that every network created in the sequence has at most one incoming active edge for each $v \in V$. This is fulfilled, in particular, when every node has an indegree of at most $d$.

Given an initial financial network with edge-ranking rules. Every sequence of semi-positive swaps, during which every node has at most $d=1$ active incoming edges, has polynomial length.

In an active extension swap, the non-profiting creditor $v_2$ has two incoming active edges. If every node has at most one incoming active edge, there can be no active extension swap. All swaps are saturation, semi-active or non-active swaps, whose number is bounded by $O(m^2)$.

When $d \ge 2$, we consider a second condition – the network should have sufficient residuals.

In a financial network $\F$, a potential active swap is a pair of active edges $e_1 = (u_1,v_1)$ and $e_2 =(u_2,v_2)$ such that $l_{e_1} = l_{e_2}$, $p_{e_1} < p_{e_2}$, and there is a path of active edges from $v_1$ to $v_2$. The network $\F$ has sufficient residuals if for every potential active swap, $l_e - p_e \ge p_{e_2} - p_{e_1}$ for all $e \in P$, i.e., the potential active swap is an active extension swap.

Intuitively, in a potential active swap all conditions for an extension swap are fulfilled, with the exception of the residual liabilities on the path $P$ of active edges. If a network has sufficient residuals, then a potential active swap is indeed an active extension swap, since there is sufficient residual liability on $P$ to forward the marginal increase of total assets for $v_1$ towards $v_2$. For example, if the liabilities of active edges are sufficiently high compared to clearing payments, then the increases in payments will not “exhaust” the liabilities, and we are guaranteed to maintain the property of sufficient residuals throughout the swap sequence.

Let us examine active extension swaps in networks with sufficient residuals.

For a financial network with edge-ranking rules, the pair $e_1$ and $e_2$ represents an active extension swap if and only if all conditions hold: (1) $l_{e_1}=l_{e_2}$, (2) $p_{e_1} < p_{e_2}$, (3) $v_2$ is an ancestor of $v_1, u_1$ and $u_2$ in an in-tree $T$ of active edges, and (4) $u_1$ is not an ancestor of $v_1$ in $T$.

Clearly, if $v_2$ is an ancestor of $v_1$, there is a path $P$ of active edges, so conditions (1)-(4) characterize potential active swaps (and hence, active extension swaps). As a consequence, our goal now is to swap edges with small payments as high as possible in the tree. In particular, consider edges classified by their liability values. For each class, we intend to swap the active edges with lowest payments to the root of the in-tree. Whenever there are active edges from the same class at the root and anywhere deeper in the tree, and the root edge has strictly more payments, then Corollary <ref> implies there still exists an active extension swap.

Formally, we construct a sequence of active extension swaps in a single phase “top-down” in each in-tree. In the first stage, we only execute active swaps involving a node $v \in V_1$, where $V_1$ is the set containing the root of every $T \in \mathcal{T}$. If there are no more such active extension swaps (or there is a swap from another class and the phase can be ended), then the first stage ends. In the second stage, for every $v \in V_1$ with $v$ root of $T$, the set $V_2$ contains all direct children of $v$ in $T$. We consider active extension swaps that involve a node $v \in V_2$. The stage ends when no more such active extension swaps exist (or the phase can be ended by a swap of another class). More generally, in stage $i$ we consider active extension swaps involving nodes of depth $i-1$ in the trees.

Suppose we are given an initial financial network with edge-ranking rules and constant $d$.
For every $v \in V_i$ there is no active extension swap involving $v$ in any stage $j > i$.

We prove the lemma by induction. Consider stage 1 and $V_1$. Since $v \in V_1$ is the root of some in-tree $T$, it has no outgoing active edge. It can only be part of an extension swap as a non-profiting creditor. At the end of stage 1 there is no active extension swap with $v \in V_1$. Consider a liability value and suppose $v$ has $\ell$ incoming edges of this liability. Then, by Corollary <ref>, the $\ell - 1$ edges with lowest payments in this liability class in $T$ must be incident to $v$. If the edge with $\ell$-smallest payment in the class is not incident to $v$, it must be located in a different subtree than the $\ell-1$ other edges (otherwise there is an active extension swap with the remaining incoming edge of $v$ from that liability class). This property holds for each class of edges with the same liabilities.

For contradiction, consider the first time at which an extension swap involving $v$ arises in a subsequent stage $j > i$. This means there is an edge incident to $v$ that can be swapped with one that is deeper in the tree and has less payment. However, this is impossible: In any previous extension swap the edges that received strictly increased payments lie on the path $P$ between the creditors. Since $v$ was not involved in any extension swap, the edges incident to $v$ still have the payments they had at the end of stage 1. Moreover, all active edges get swapped only in the respective subtrees. As such, no active extension swap with the edges of $v$ can arise. This proves the base case.

For the hypothesis, assume the lemma holds for all stages $k = 1,\ldots,i-1$. Consider stage $i$ and a node $v \in V_i$. At the end of stage $i$, there are no extension swaps involving node $v \in V_i$. Again, consider the first time at which an extension swap involving $v$ arises in a subsequent stage $j > i$. By hypothesis, there are no extension swaps involving nodes from stages $k < i$ in this time period. Hence, in the extension swap $v$ must be the non-profiting creditor. All other nodes must be from the subtree $T_v$ rooted at $v$. We can repeat the arguments from the base case with the root and $T$ for $v$ and $T_v$. This proves the inductive step.

It remains to construct a short sequence of active extension swaps within a single stage $i$. By Lemma <ref>, for each $v \in V_i$, no ancestor is involved in any extension swap of stage $i$. Hence, we restrict attention to the subtree rooted in $v$. We assume $v$ is a root of a separate subtree $T$, and we must bound the number of active extensions swaps involving $v$.

For any financial network with edge-ranking rules, if every $v \in V_i$ has at most constantly many incoming active edges, then there can be at most a polynomial number of active extension swaps in stage $i$.

Consider $v \in V_i$ with $d$ incoming active edges, for some constant $d$. Active extension swaps always keep this number the same for every node. Since $v$ is a non-profiting creditor in every swap of stage $i$, the total assets of $v$ do not change during the stage. However, in each swap, there is at least one incoming edge of $v$ (on the active path of the swap) that strictly increases in payments. Since payments on each edge do not decrease, a subset of $d$ incoming active edges cannot repeat during the stage. As a consequence, at the end of each swap, $v$ has a different subset of neighbors for its incoming active edges. The number of different sets of neighbors is bounded by $n \choose d$, which is polynomial for constant $d$.

Together these insights prove Theorem <ref>, which summarizes our result.

The  problem for financial networks with edge-ranking rules can be solved in polynomial time if, for all financial networks encountered during the sequence, the network has sufficient residuals and every node has at most a constant number of active incoming edges.

Let the set of saturated edges be fixed. There exists no cycle over active edges since otherwise the payments on the cycle could be raised until one edge is saturated. Moreover, every bank has at most one active outgoing edge but might have several incoming active edges. Considering all banks with a path to $v$ together with the outgoing edges, the corresponding subgraph forms an in-tree with root $v$. Applying Proposition <ref>, every extension swap with creditor $v$ swaps one incoming edge of $v$ with an edge located in the in-tree with less payments. Thus, an iterative application of extension swaps leads to edges with high payments moving further away and edges with low payments moving closer to the root. Assume that the extension swaps are first executed for a bank $v$ that is not contained in any other in-tree. The swaps with $v$ end when no incoming edge of $v$ can be swapped with an edge in the in-tree with higher payments. Now continue with a node $u$ with edge $(u,v)$. Again, the edges incident to $u$ are exchanged with those in the in-tree with root $u$, but never with incoming edges of $v$. Since the in-tree with root $u$ is a subtree of the in-tree with root $v$, no swap with creditor $v$ needs to be considered in the current phase. In the following, we thus focus on constructing a sequence of extension swaps in a given in-tree.

A swap is denoted an activation swap if at least one of the edges $e_1$ or $e_2$ is inactive. Assume $e$ is inactive and saturated then, by definition, this must be the edge with higher payments. Hence, $e$ is an incoming edge of $v$ and swaps with an edge $\hat{e}=(u,w)$ in the in-tree of $v$ where $w$ has depth of at least one. Since there exists no edge with the same capacity as $e$ and higher payments and the payments on $e$ will remain the same throughout the phase, $\sig{e}$ will never be swapped back to $v$. More specifically, in any further swap $\sig{e}$ will only be swapped with an edge in the in-tree of $w$. On the other hand, if $e$ is inactive and not saturated it is swapped with an incoming edge $\hat{e}$ of $v$ with payments greater zero. By similar arguments as before, $\sig{e}$ will never again be swapped with an edge in the in-tree.

Given an initial financial network with $m$ edges, the number of activation swaps in every sequence of non-saturating semi-positive debt swaps is at most polynomial in $m$.

Therefore, it suffices to restrict our attention to extension swaps with active edges.

Extension swaps switch the endpoints of two edges with same edge weights, or in other words two edges of the same type or color. Moreover, the capacity constraint (3) of an extension swap is satisfied, if...

Recall that, for every extension swap $\sigma$, the additional assets of the profiting creditor are payed along a path to the second creditor. This is only possible when every edge on this path has sufficiently large remaining capacities. If one edge on the path does not satisfy the capacity constraint the edge is blocking the swap. However, it is possible that a sequence of swaps lead to decrease payments on the blocking edge providing sufficient remaining capacity for $\sigma$.
Do we need an example for this?
Let us start by constructing short sequences of extension swaps when every edge has sufficiently large capacities and no blocking edges exist.

§.§ Sequences of Arbitrary Swaps

In this section, we consider sequences of arbitrary swaps. In contrast to semi-positive ones, these swaps have no natural criterion of progress. We again focus on swaps in which a single bank $v$ has to improve strictly. Unfortunately, sequences of such arbitrary $v$-improving swaps can be very long, for every monotone allocation rule (including edge-ranking and proportional rules). Our results show that there are initial networks from which every sequence of $v$-improving swaps to a local optimum (in which no such swaps exist) is exponentially long.

Indeed, we obtain a more general statement. Consider a  maximization problem for the total assets of a given bank $v$ defined as follows. In an instance of the  problem, we are given a set of banks $V$. For each bank $v \in V$ we are given a non-negative value for the external assets as well as a number of incoming and outgoing half-edges or stubs. For each such stub $i$ of $v$, we have a positive weight $l_i > 0$. Clearly, these stubs shall be consistent with at least one set of edges $E$ among $V$, i.e., there must be a feasible underlying graph $G=(V,E)$ in the sense that the stubs can be matched to form $G$. In particular, each incoming stub of weight $l_i$ of each node $v$ can be matched to some outgoing stub of weight $l_i$ of some node $u \neq v$ to form an edge $(u,v) \in E$. Consistency of stubs with at least one set $E$ can be tested in polynomial time by solving a straightforward bipartite matching problem. For the remainder, we assume that it holds.

Furthermore, an instance of  has an edge-ranking rule $\vecf$ that specifies the order in which banks pay their outgoing stubs. We assume that the rule is given implicitly by a clearing oracle $\mathcal{O}$. A clearing oracle for rule $\vecf$ receives as input the remaining financial network $(G,\vecl,\veca^x)$ and outputs the clearing state. Note that a clearing oracle $\mathcal{O}$ can be computed in polynomial time for edge-ranking rules [5].

Observe that any set of edges $E$ that is consistent with the stubs gives rise to a financial network and a clearing state (where the latter can be computed using $\mathcal{O}$). The goal is to find such a consistent set to maximize the total assets of a given bank $v$ in the resulting clearing state. The objective function in the instance are the total assets for a given bank $v$.

Finally, to express edge swaps, we define a neighborhood over the set of financial networks whose edges are consistent with the stubs in the input. For a given financial network $\F$, the  neighborhood $\mathcal{N}(\F)$ contains all networks $\F'$ that can be obtained by performing an arbitrary debt swap in $\F$. Observe that a debt swap merely exchanges the matching of two pairs of stubs with the same weights and thereby maintains consistency.

with  neighborhood is in the class  whenever the clearing oracle can be computed in polynomial time.

Clearly, as noted above, we can obtain an initial network by computing a bipartite matching (indeed, every network consistent with the stubs represents a bipartite matching of the stubs and vice versa). The  neighborhood of a network contains $O(m^2)$ other networks. For each of these networks, the corresponding clearing state can be determined using oracle $\mathcal{O}$. Hence, the  neighborhood $\N(\F)$ for a given network $\F$ can be searched efficiently.

When locally maximizing  we do not necessarily restrict attention to a sequence of $v$-improving swaps from a given initial network to a local optimum. Instead, when given an initial network, we obtain an instance of  by breaking all edges into stubs. The goal is merely to find any arbitrary local optimum network consistent with the stubs derived from the initial network. We show that this problem is -complete. For a proof of the following result, see Appendix <ref>

There is a tight -reduction from  with flip neighborhood to  with  neighborhood.

This shows that  with  neighborhood is -complete. Moreover, the reduction implies that there exist initial states from which every execution of the standard local search algorithm requires exponentially many steps to reach a local optimum [34]. The standard local search algorithm for  yields a sequence of debt swaps.

It is -complete to compute a local optimum for  with the  neighborhood. There exists an instance of  and an initial network $\F$ such that every sequence of arbitrary $v$-improving swaps from $\F$ to a local optimum has exponential length.

For the instances constructed in the proof of Theorem <ref>, each possible network has the property that a bank has either 0 assets or enough assets to fully pay all outgoing stubs.
The clearing oracle in these networks is trivial, and all payments are completely independent of the allocation rule.

The results of Corollary <ref> generalize to  with the  neighborhood for any monotone allocation rule with efficient clearing oracle.

§ REACHABILITY

A debt swap changes the underlying graph structure of the corresponding financial network. It is a natural reachability question whether, for two given networks, one network can be transformed into the other via a sequence of debt swaps.

More formally, in the  problem we are given an initial network $\F$ and a target network $\G$. Both networks have the same set $V$ of nodes and are consistent with the stubs from an instance of . For convenience, we introduce an explicit term for this property. Every node $v \in V$ has the same incidence profile in both networks (i.e., for each value $l_i$ the same number of outgoing edges with weight $l_i$ in both $\F$ and $\G$ and the same number of incoming edges with $l_i$ in both $\F$ and $\G$). Moreover, $\F$ and $\G$ have the same monotone allocation rule, i.e., $v$ uses the same edge ranking to allocate assets to outgoing stubs, for each $v \in V$. Overall, we say the networks $\F$ and $\G$ are consistent with each other. In Section <ref> we observed that any debt swap maintains network consistency. Hence, if $\F$ and $\G$ are not consistent with each other, then the answer to every reachability problem considered in this section is trivially negative. For the remainder of the section, we assume that $\F$ and $\G$ are consistent with each other. To avoid trivialities, we assume that $\F$ and $\G$ have different edge sets.

When applying a finite sequence of debt swaps $\bsigma=(\sigma_1,\sigma_2,\dots)$ to $\F$, we first execute swap $\sigma_1$ in $\F$ and denote the resulting network by $\F^{\sigma_1}$. We again assume to have access to an efficient clearing oracle $\mathcal{O}$ to compute the clearing state. Then we perform $\sigma_2$ in $\F^{\sigma_1}$, then $\sigma_3$ in $\F^{\sigma_2}$, etc. The process ends when all debt swaps in the sequence were applied. The resulting network is denoted by $\F^{\bsigma}$. Every financial network created during this sequence is called an intermediate network. We say that $\G$ is reachable from $\F$ if there exists a sequence of debt swaps $\bsigma$ such that $\F^{\bsigma}=\G$. The sequence $\bsigma$ is called a reaching sequence.
In the  problem, we are interested in reaching sequences of arbitrary debt swaps. If we only consider sequences of $v$-improving arbitrary debt swaps, then the problem is denoted by . Intuitively, instead of strict profits for a given bank $v$ it might be sufficient that $v$ stays solvent. Formally, in the  problem we are given consistent networks $\F$ and $\G$ such that $v$ has the same amount $\ell$ of total assets in both networks. Decide whether there exists a reaching sequence of debt swaps such that the total assets of $v$ are at least $\ell$ in every intermdeiate network.

Our reachability problems can be interpreted as instances of the $s$-$t$-Connectivity (Stcon) problem in a transition graph. The nodes of this transition graph are the networks consistent with $\F$ and $\G$. There is a directed edge between networks $\F'$ and $\F''$ if and only if there is a debt swap that turns $\F'$ into $\F''$. Stcon is solveable in poly-logarithmic space [33]. In our case, there are less than $2^{n^2}$ consistent networks, so the transition graph has at most exponential size. As such, all our reachability problems lie in .

Our first result shows that for arbitrary swaps, the problem is much easier. The consistency property is necessary and sufficient for reachability. A reaching sequence of polynomially many swaps can be computed in polynomial time if it exists.

The  problem with monotone allocation rules can be solved in time polynomial in the input size.

Let $\mathcal{D}$ be the set of desired edges that are in $\G$ and not in $\F$, i.e., $\mathcal{D}=E^{\G}\setminus E^{\F}$. There are exactly $|\mathcal{D}| > 0$ edges in $E^{\F}\setminus E^{\G}$. First, observe that $|\mathcal{D}|>1$. To see this, assume for a contradiction that $\mathcal{D} =\{e=(u,v)\}$ for $u,v \in V$ with weight $l_e>0$. Since $\F$ and $\G$ are consistent with each other, in $\F$ bank $v$ must have an incoming edge $(x,v)$, and $u$ must have an outgoing edge $(u,y)$ each with weight $l_e$, and both these edges are not in $E^{\G}$. Since $|\mathcal{D}|=1$, banks $x$ and $y$ have more incident edges in $\F$ than $\G$, a contradiction. We assume $|\mathcal{D}|\geq 2$ for the remaining proof.

We construct a sequence of debt swaps that in each step replaces an edge in $E^{\F}\setminus E^{\G}$ by one in $\mathcal{D}$.
Choose an arbitrary edge $\hat{e}=(w,v) \in \mathcal{D}$. By consistency there exists an edge $e=(u,v) \in E^{\F} \setminus E^{\G}$ with weight $l_e=l_{\hat{e}}$. Further, $w$ has at least one outgoing edge $e'=(w,x)$ in $\F$ that is not in $\G$ with weight $l_{e'}=l_e$. Clearly, all banks $u,v,w$ and $x$ are pairwise different.
Perform a swap $\sigma$ of edges $e$ and $\hat{e}$. The resulting network $\F^{\sigma}$ contains the desired edge $(w,v) \in \mathcal{D}$ and one edge in $E^{\F}\setminus E^{\G}$ was removed. We repeat this step until two desired edges in $\mathcal{D}$ have not been included.

For the final step with $|\mathcal{D}|=2$, observe that there are exactly two edges in $E^{\F}\setminus E^{\G}$. Choose an arbitrary edge $\hat{e}=(w,v) \in \mathcal{D}$. By the same argument as before, there exist edges $(u,v), (w,x) \in E^{\F}\setminus E^{\G}$ each with the same weight as $\hat{e}$. By consistency, bank $u$ must have an outgoing edge with weight $l_{\hat{e}}$ that is not in $\F$. $x$ must have an incoming edge with weight $l_{\hat{e}}$ that is not in $\F$. Since $|\mathcal{D}|=2$, this implies the existence of edge $(u,x)$ in $\G$. Then, $\G$ is reachable from $\F$ with the debt swap of edges $(u,v)$ and $(w,x)$ creating the edges in $\mathcal{D}$.

This proves that the network $\G$ can indeed be reached via a sequence of debt swaps. In every step of this sequence, a debt swap of edges not in $\G$ is performed to create a new desired edge in $\mathcal{D}$. This means that a desired edge created in a previous step will never be swapped again. Thus, the number of swaps in the resulting sequence is bounded by $O(m)$ where $m=|E^{\F}|=|E^{\G}|$ and $m \leq|\mathcal{D}|$.

The greedy algorithm described in the proof of Theorem <ref> arbitrarily chooses an edge from the target network and performs a debt swap to include the edge into the current network. Note that this approach can lead to devastating losses of assets of a single bank $v$ in the intermediate networks, which is not aligned with incentives of the involved banks and potentially problematic for the financial stability of the system.
Instead, if we restrict to $v$-improving swaps, in which a given bank $v$ must strictly profit in every step, then the tight -reduction in Theorem <ref> directly yields the following result [34, 26].

The  problem with monotone allocation rules is -complete.

We strengthen this result in the following way. Instead of guaranteeing a strict profit for $v$ in every step, we require only that the total assets of $v$ are at least $\ell$ in the initial, final, and every intermediate network. Deciding whether there exists a reaching sequence of arbitrary debt swaps so that $v$ never has strictly less assets in any step is -hard (and, hence, -complete).

The  problem with monotone allocation rules is -complete.

Finally, we briefly consider sequences of semi-positive debt swaps. Indeed, since they are Pareto-improving, the motivation here is similar as in the previous theorem. Deciding whether a reaching sequence exists where no bank is harmed is already challenging, even for edge-ranking rules.

Given initial network $\F$ and a target network $\G$ with edge-ranking rules that are consistent with each other, it is strongly -hard to decide whether $\G$ is reachable from $\F$ via any sequence of semi-positive swaps.

[1]
Heiner Ackermann, Paul Goldberg, Vahab Mirrokni, Heiko Röglin, and Berthold
Uncoordinated two-sided matching markets.
SIAM J. Comput., 40(1):92–106, 2011.

[2]
José Alcalde.
Exchange-proofness or divorce-proofness? Stability in one-sided
matching markets.
Economic Design, 1:275––287, 1994.

[3]
Paola Alimonti and Viggo Kann.
Some APX-completeness results for cubic graphs.
Theor. Comput. Sci., 237(1-2):123–134, 2000.

[4]
Daniel Allendorf, Ulrich Meyer, Manuel Penschuck, and Hung Tran.
Parallel global edge switching for the uniform sampling of simple
graphs with prescribed degrees.
In Proc. 36th Int. Parallel Distrib. Process. Symp.  (IPDPS), pages 269–279, 2022.

[5]
Nils Bertschinger, Martin Hoefer, and Daniel Schmand.
Strategic payments in financial networks.
In Proc. 11th Symp. Innov. Theoret. Comput. Sci. (ITCS),
pages 46:1–46:16, 2020.

[6]
Felix Brandt and Anaëlle Wilczynski.
On the convergence of swap dynamics to Pareto-optimal matchings.
In Proc. 15th Conf. Web and Internet Econ. (WINE), pages
100–113, 2019.

[7]
Corrie Jacobien Carstens.
Topology of Complex Networks: Models and Analysis.
PhD thesis, RMIT University, 2016.

[8]
Katarina Cechlárová.
On the complexity of exchange-stable roommates.
Discret. Appl. Math., 116(3):279––287, 2002.

[9]
Katarina Cechlárová and David Manlove.
The exchange-stable marriage problem.
Discret. Appl. Math., 152(1–3):109––122, 2005.

[10]
Péter Csóka and P Jean-Jacques Herings.
Decentralized clearing in financial networks.
Manag. Sci., 64(10):4681–4699, 2018.

[11]
Anastasia Damamme, Aurélie Beynier, Yann Chevaleyre, and Nicolas Maudet.
The power of swap deals in distributed resource allocation.
In Proc. 14th Conf. Auton. Agents and Multi-Agent Syst.  (AAMAS), pages 625–633, 2015.

[12]
Effrosyni Diamantoudi, Eiichi Miyagawa, and Licun Xue.
Random paths to stability in the roommates problem.
Games Econ. Behav., 48(1):18–28, 2004.

[13]
Larry Eisenberg and Thomas Noe.
Systemic risk in financial systems.
Manag. Sci., 47(2):236–249, 2001.

[14]
Parikshit Gopalan, Phokion Kolaitis, Elitza Maneva, and Christos Papadimitriou.
The connectivity of Boolean satisfiability: Computational and
structural dichotomies.
SIAM J. Comput., 38(6):2330–2355, 2009.

[15]
Laurent Gourvès, Julien Lesca, and Anaëlle Wilczynski.
Object allocation via swaps along a social network.
In Proc. 26th Int. Joint Conf. Artif. Intell. (IJCAI),
pages 213–219, 2017.

[16]
Johan Håstad.
Clique is hard to approximate within n 1-c.
Acta Math., 182:105–142, 1999.

[17]
Martin Hoefer.
Local matching dynamics in social networks.
In Proc. 38th Int. Colloq. Autom. Lang. Programming
(ICALP), volume 2, pages 113–124, 2011.

[18]
Martin Hoefer, Daniel Vaz, and Lisa Wagner.
Dynamics in matching and coalition formation games with structural
Artif. Intell., 262:222–247, 2018.

[19]
Martin Hoefer and Lisa Wilhelmi.
Seniorities and minimal clearing in financial network games.
In Proc. 15th Symp. Algorithmic Game Theory (SAGT), pages
187–204, 2022.

[20]
Stavros Ioannidis, Bart De Keijzer, and Carmine Ventre.
Financial networks with singleton liability priorities.
In Proc. 15th Symp. Algorithmic Game Theory (SAGT), 2022.
To appear.

[21]
Stavros Ioannidis, Bart De Keijzer, and Carmine Ventre.
Strong approximations and irrationality in financial networks with
In Proc. 49th Int. Colloq. Autom. Lang. Programming
(ICALP), pages 76:1–76:18, 2022.

[22]
Takehiro Ito, Erik Demaine, Nicholas Harvey, Christos Papadimitriou, Martha
Sideri, Ryuhei Uehara, and Yushi Uno.
On the complexity of reconfiguration problems.
Theor. Comput. Sci., 412(12-14):1054–1065, 2011.

[23]
Panagiotis Kanellopoulos, Maria Kyropoulou, and Hao Zhou.
Financial network games.
In Proc. 2nd Int. Conf. AI in Finance (ICAIF), pages 1–9,

[24]
Panagiotis Kanellopoulos, Maria Kyropoulou, and Hao Zhou.
Forgiving debt in financial network games.
In Proc. 21st Conf. Auton. Agents and Multi-Agent Syst.  (AAMAS), pages 1651–1653, 2022.

[25]
Donald Knuth.
Marriage stables et leurs relations avec d’autres probl`emes
Les Presses de l’Universit´e de Montr´eal, 1976.

[26]
Christos Papadimitriou, Alejandro Schäffer, and Mihalis Yannakakis.
On the complexity of local search.
In Proc. 22nd Symp. Theory Comput. (STOC), pages 438–445,

[27]
Pál András Papp and Roger Wattenhofer.
Network-aware strategies in financial systems.
In Proc. 47th Int. Colloq. Autom. Lang. Programming
(ICALP), page 91, 2020.

[28]
Pál András Papp and Roger Wattenhofer.
Debt swapping for risk mitigation in financial networks.
In Proc. 22nd Conf. Econ. Comput. (EC), pages 765–784,

[29]
Pál András Papp and Roger Wattenhofer.
Default ambiguity: Finding the best solution to the clearing
In Proc. 17th Conf. Web and Internet Econ. (WINE), pages
391–409, 2021.

[30]
Pál András Papp and Roger Wattenhofer.
Sequential defaulting in financial networks.
In Proc. 12th Symp. Innov. Theoret. Comput. Sci. (ITCS),
pages 52:1–52:20, 2021.

[31]
Leonard Rogers and Luitgard Veraart.
Failure and rescue in an interbank network.
Manag. Sci., 59(4):882–898, 2013.

[32]
Alvin Roth and John Vande Vate.
Random paths to stability in two-sided matching.
Econometrica, pages 1475–1480, 1990.

[33]
Walter Savitch.
Relationships between nondeterministic and deterministic tape
J. Comput. Syst. Sci., 4(2):177–192, 1970.

[34]
Alejandro Schäffer.
Simple local search problems that are hard to solve.
SIAM J. Comput., 20(1):56–87, 1991.

[35]
Steffen Schuldenzucker and Sven Seuken.
Portfolio compression in financial networks: Incentives and systemic
In Proc. 21st Conf. Econ. Comput. (EC), page 79, 2020.

[36]
Steffen Schuldenzucker, Sven Seuken, and Stefano Battiston.
Finding clearing payments in financial networks with credit default
swaps is PPAD-complete.
In Proc. 8th Symp. Innov. Theoret. Comput. Sci. (ITCS),
pages 32:1–32:20, 2017.

[37]
Steffen Schuldenzucker, Sven Seuken, and Stefano Battiston.
Default ambiguity: Credit default swaps create new systemic risks in
financial networks.
Manag. Sci., 66(5):1981–1998, 2020.

[38]
Jonas Sjöstrand.
Making multigraphs simple by a sequence of double edge swaps.
Discret. Math., 344:112328, 2021.

[39]
Richard Taylor.
Constrained switchings in graphs.
In Combinatorial Mathematics VIII, pages 314–336. Springer,

[40]
Richard Taylor.
Switchings constrained to 2-connectivity in simple graphs.
SIAM J. Algebraic Disc. Meth., 3(1):114–121, 1982.

[41]
Jan van den Heuvel.
The complexity of change.
Surveys in Combinatorics, 409(2013):127–160, 2013.

[42]
Luitgard Veraart.
When does portfolio compression reduce systemic risk?
Mathematical Finance, 32(3):727–778, 2019.

§ MISSING PROOFS

Consider a semi-positive swap $\sigma$ with edges $e_1,e_2$ in a financial network $\F$. W.l.o.g. assume $\sig{a}_{v_1} > a_{v_1}$ and $\sig{a}_{v_2} = a_{v_2}$. Suppose $\sigma$ is not a saturating swap. We show that $\sigma$ is an extension swap by proving properties (1)-(4) of the definition.

Property (1) is trivial. As a consequence, $\sigma$ does not close a new cycle of active edges; otherwise, since the set of active edges in $\sig{\F}$ is acyclic, an additional edge is saturated after the swap.

Construct the auxiliary network $\HH$ by applying source-sink equivalency to edges $e_1,e_2$ and nodes $v_1,v_2$ and simulate the debt swap by increasing the external assets of $s_{v_1}$ and $s_{v_2}$ by $\delta_{v_1}=\sig{a}_{v_1}-a_{v_1}$ and $\delta_{v_2}=0$, respectively. Due to Lemma <ref> (3), $s_{v_1}$ routes the entire additional assets of $\delta_{v_1}$ to $\tvo,\tvt,t_{u_1}$ and $t_{u_2}$. Every bank has at most one active outgoing edge. Hence, before the swap there is exactly one path $P = \{(s_{v_1},w_1),(w_1,w_2),\ldots \}$ of active edges that ends in exactly one of the four sinks. Since no edge gets saturated, $s_{v_1}$ forwards all additional assets along $P$ to that sink.

This sink must be either $\tvt$ or $t_{u_2}$ due to Lemma <ref>, (2). Suppose it is $t_{u_2}$. Then $(u_2,v_2)$ is not active in $\F$, since otherwise $(P \setminus \{(s_{v_1},w_1)\}) \cup \{ (v_1,w_1), (u_2,v_1)\}$ would be a cycle of active edges in $\sig{\F}$. However, if $(u_2,v_2)$ is not active in $\F$, then neither is $(u_2,t_{u_2})$ in $\HH$. Hence, $t_{u_2}$ cannot be the sink of $P$.

As a consequence, $\tvt$ must be the sink of $P$. This implies existence of the active path and shows property (2). Since $t_{u_1}$ and $t_{u_2}$ are not involved in $P$ and there is no new cycle of active edges, these sinks receive the same assets as before the swap. This implies the same payments on swapped edges, $p_{e_1} = \sig{p}_{e_2}$ and $p_{e_2} = \sig{p}_{e_1}$. As such, property (4) holds.

Since there are no new cycles of active edges, we see that $\delta_{v_1} = \sig{p}_{e_1} - p_{e_1} = p_{e_2} - p_{e_1}$, so indeed $p_{e_1} < p_{e_2}$. Thus, $v_1$ gains additional assets of $\delta_{v_1}$ from the swapped edge. Similarly, $v_2$ looses assets of $\delta_{v_1}$ from the swapped edge. Since $\delta_{v_2} = 0$, this implies that in $\HH$ all additional assets of $\delta_{v_1}$ must get routed completely from $s_{v_1}$ along $P$ to $\tvt$. Since no additional edge gets saturated, we must have $\ell_e - p_e > p_{e_2} - p_{e_1}$, i.e., property (3) follows. As a conclusion, $\sigma$ must be an extension swap.

[>=stealth', shorten >=1pt, auto,
node distance=1.5cm, scale=1,
transform shape, align=center,
bank/.style=circle, draw, inner sep=1]

[circle, draw, inner sep=3pt] (v) at (0,0) $v$;
[bank] (w0) [right=of v] $w_0$;
[bank] (w1) [above=of v] $w_1$;
[bank] (u0) [right=of w1] $u_0$;
[bank] (u1) [right=of u0] $u_1$;
(dots) [right=of u1] $\cdots$;
[bank] (um) [right=of dots] $u_{m}$;
[rectangle, draw=black, inner sep=2.5pt] (xu0) [above=0.1cm of u0] $2^0$;
[rectangle, draw=black, inner sep=2.5pt] (xu1) [above=0.1cm of u1] $2^1$;
[rectangle, draw=black, inner sep=2.5pt] (xum) [above=0.1cm of um] $2^{m}$;

[->] (v) to[bend left] (w0);
[->] (w0) to[bend left] (v);
[->] (v) to[bend left] (w1);
[->] (w1) – (u0);
[->] (u0) to node[below, midway] $2^1-1$ (u1);
[->] (u1) to node[below, pos=0.6] $2^2-1$ (5.5,2.05);
[->] (7,2.05) to node[below, pos=0.4] $2^{m}-1$ (um);

Financial network with proportional allocation rules that admits a sequence of debt swaps with exponential length, where $m=n-4$. Each edge has weight $2^n$ and edge labels indicate payments.

We construct the initial network as follows. There are $n$ nodes and $n$ edges. Every node has at most one incoming edge. For simplicity, all edges have a sufficiently large liability of $2^n$. There is a single node $v$ with out-degree 2, a single node with outdegree 0. All nodes have in-degree 1. The node $v$ is involved in exactly one directed cycle of two banks $v$ and $w_0$ and edges $(v,w_0)$, $(w_0,v)$. These banks have no external assets. The second outgoing edge of $v$ leads into a path with the remaining $n-2$ nodes. We denote the nodes in the path by $v,w_1,u_0,u_1,\ldots,u_{n-4}$ in the order of their occurrence. Bank $u_i$ has external assets of $2^i$, for every $i=0,\ldots,n-4$. In the initial clearing state, there are no payments on cycle edges $(v,w_0)$, $(w_0,v)$, and on edges $(v,w_1)$ $(w_1,u_0)$. Edge $(u_i,u_{i+1})$ has payment $\sum_{j=0}^i 2^j = 2^{i+1} - 1$, for every $i=0,\ldots,n-5$. A visualization can be seen in Figure <ref>.

We outline the first four steps of an exponentially long sequence for clarity. Our sequence maintains the structural invariant that the network has a single cycle involving $v$ and a path from $v$ to $u_{n-4}$. The nodes $w_0$ and $w_1$ always remain the two out-neighbors of $v$. They alternate in being in the cycle or on the path. The assets of $v$ strictly improve by 2 in every swap.

First, swap edges $(u_0,u_1)$ and $(w_0,v)$. Then the path is $v,w_0,u_1,u_2,\ldots,u_{n-4}$, and the cycle is $v, w_1, u_0$. Since $u_0$ pays its external assets of 1 in the cycle, and $v$ splits its assets evenly among $(v,w_0)$ and $(v,w_1)$, the clearing state has a payment of 2 on edge $(u_0,v)$, a payment of 1 on $(v,w_0)$, $(v,w_1)$ and $(w_1,u_1)$, and a payment of $2^{i+1}-1$ on every edge $(u_i,u_{i+1})$. Clearly, this is a $v$-improving, semi-positive swap.

Second, swap edges $(u_0,v)$ and $(u_1,u_2)$. Then the the path is $v,w_1,u_0,u_2,\ldots,u_{n-4}$, and the cycle is $v, w_0, u_1$. Since $u_1$ pays its external assets of 2 in the cycle, the clearing state has a payment of 4 on edge $(u_1,v)$, a payment of 2 on $(v,w_0)$, $(v,w_1)$ and $(w_1,u_0)$, a payment of 3 on $(u_0,u_2)$, and $2^{i+1}-1$ on every other edge $(u_i,u_{i+1})$. Clearly, this is a $v$-improving, semi-positive swap.

Third, swap edges $(w_0,u_1)$ and $(u_0,u_2)$. Then the path is $v,w_0,u_2,\ldots,u_{n-4}$, and cycle is $v, w_1, u_0, u_1$. The clearing state has a payment of 6 on edge $(u_1,v)$, a payment of 3 on $(v,w_0)$, $(v,w_1)$ and $(w_1,u_0)$, payment 4 on $(u_0,u_1)$. Finally, we have a payment of $2^{i+1}-1$ on every other edge $(u_i,u_{i+1})$.

Forth, swap edges $(u_1,v)$ and $(u_2,u_3)$. Then the path is $v,w_0,u_0,u_1,u_3,\ldots,u_{n-4}$, and the cycle is $v, w_1, u_2$. The clearing state has a payment of 8 on edge $(u_2,v)$, a payment of 4 on $(v,w_1)$, $(w_1,u_2)$ and $(v,w_0)$, $(w_0,u_0)$. There is a payment of 5 on $(u_0,u_1)$, 7 on $(u_1,u_3)$ and $2^{i+1}-1$ on every other edge $(u_i,u_{i+1})$.

Now at this point, we have moved $u_2$ into the cycle, and reset $u_0$ and $u_1$ to their original positions as the first $u$-nodes on the path. Thus, by repeating steps 1-3, we can bring $u_0, u_1$ in front of $u_2$ in the cycle, thus arriving at a stage with payment 14 on edge $(u_2,v)$ and 7 on both $(v,w_0)$ and $(v,w_1)$. Then, by swapping $(u_2,v)$ and $(u_3,u_4)$, we move $u_3$ in the cycle and reset $u_0$, $u_1$ and $u_2$. Thus, we can again repeat the entire sequence. In each swap, the payment on $(v,w_0)$ and $(v,w_1)$ increases by exactly 1.

More generally, suppose we have nodes $v, w_1, u_0, u_1, \ldots, u_j$ in the cycle in that order, and we have nodes $v, w_0, u_{j+1},\ldots,u_{n-4}$ on the path in that order. At this point, we have payments of $2^{j+1}-1$ on both $(v,w_0)$ and $(v,w_1)$. Now by swapping $(u_j,v)$ and $(u_{j+1}, u_{j+2})$, we have nodes $v, w_0, u_{j+1}$ in the cycle and reset $u_0,\ldots,u_j$ on the path $v, w_1, u_0,\ldots, u_j, u_{j+2},\ldots,u_{n-4}$. Then we can repeat the entire sequence executed so far and move to $v, w_1, u_0, \ldots, u_{j+1}$ in the cycle and $v, w_0, u_{j+2},\ldots,u_{n-4}$ on the path. The last doubling step in this exponential construction occurs when $u_{n-3}$ moves into the cycle, and the sequence ends when the cycle is $v,w_1,u_0,\ldots,u_{n-5}$ and the path $v, w_0, u_{n-4}$. At this point, we have made $2^{n-4}-1$ semi-positive $v$-improving swaps.

[>=stealth', shorten >=1pt, auto,
node distance=1cm, scale=1,
transform shape, align=center,
bank/.style=circle, draw, inner sep=3.1pt]

[bank] (x1) at (0,0) $x_1$;
[bank] (s1) [right=of x1] $s_1$;
[bank] (x2) [right=of s1] $x_2$;
[bank] (s2) [right=of x2] $s_2$;
(udots) [right=of s2] $\dots$;
[bank] (xk) [right=of udots] $x_k$;
[bank] (sk) [right=of xk] $s_k$;
[circle, draw, inner sep=1pt] (x1t) [below=of x1] $x_1^T$;
[circle, draw, inner sep=1pt] (x1f) [right=of x1t] $x_1^F$;
[circle, draw, inner sep=1pt] (x2t) [right=of x1f] $x_2^T$;
[circle, draw, inner sep=1pt] (x2f) [right=of x2t] $x_2^F$;
(mdots) [right=of x2f] $\cdots$;
[circle, draw, inner sep=1pt] (xkt) [right=of mdots] $x_k^T$;
[circle, draw, inner sep=1pt] (xkf) [right=of xkt] $x_k^F$;
(anchor) [below=2cm of x2f] ;
[bank] (k2) [left=0.75cm of anchor] $\kappa_2$;
[bank] (k1) [left=1.5cm of k2] $\kappa_1$;
(ldots) [right=0.75cm of anchor] $\cdots$;
[bank] (kl) [right=1.5cm of ldots] $\kappa_{\ell}$;
[circle, draw, inner sep=3.5pt] (v) [below=2cm of anchor] $v$;
[rectangle, draw=black, inner sep=2.5pt] (ex1) [above=0.1cm of x1] $kM_1$;
[rectangle, draw=black, inner sep=2.5pt] (ex2) [above=0.1cm of x2] $kM_2$;
[rectangle, draw=black, inner sep=2.5pt] (exk) [above=0.1cm of xk] $kM_k$;

[->] (x1) to node[left, midway] $kM_1$ (x1t);
[->] (s1) to node[left, midway] $kM_1$ (x1f);
[->] (x2) to node[left, midway] $kM_2$ (x2t);
[->] (s2) to node[left, midway] $kM_2$ (x2f);
[->] (xk) to node[left, midway] $kM_k$ (xkt);
[->] (sk) to node[left, midway] $kM_k$ (xkf);
[->] (x1t) to node[left=0.1cm, pos=0.2] $M_1^T$ (k1);
[->] (x1f) to node[left=0.1cm, pos=0.2] $M_1^F$ (k2);

[->] (x2f) to node[right, pos=0.2] $M_2^F$ (k1);
[->] (x2f) to node[right=0.1cm, pos=0.2] $M_2^F$ (kl);
[->] (xkt) to node[left=0.5cm, pos=0.2] $M_2^T$ (kl);
[->] (xkf) to node[right=0.2cm, pos=0.2] $M_2^F$ (k2);
[->] (k1) to node[left=0.2cm, pos=0.2] $w_{\kappa_1}$ (v);
[->] (k2) to node[right=0.2cm, pos=0.2] $w_{\kappa_2}$ (v);
[->] (kl) to node[right=0.2cm, pos=0.2] $w_{\kappa_{\ell}}$ (v);

Example construction for reduction with  where edge labels indicate liabilities.

Consider an instance $\varphi$ of  with the flip neighborhood. Formula $\varphi$ consists of $k$ variables $x_1,x_2\dots,x_k$ and $\ell$ clauses $\kappa_1,\ldots,\kappa_{\ell}$ where each clause is assigned a weight $w_{\kappa_j}$. We construct an input instance to  as follows. First, include banks $x_i, x_i^T$ and $x_i^F$ for every variable and a bank $\kappa_j$ for every clause. Additionally add bank $v$ and auxiliary bank $s_i$ for all $i\in[k]$.

Before specifying the stubs and their weights for every bank, we describe a binary encoding for every bank corresponding to a literal. Choose integer $\ell$ such that $2^{\ell}\geq w_{\kappa_j}$ for all $j$ and $\ell > 1+\log k$. Then, set the $\ell$-th lowest bit to 1. Use the bits $2$ to $1+\log k$ to encode the index $i$ of the literal and set the first bit from the right to $0$ if the literal is $\neg x_i$ and to $1$ otherwise. All other bits are set to $0$. Observe that the weights assigned to each literal are pairwise different and at least $w_{\kappa_j}$ for all $j$. For simplicity, denote the resulting value for each bank $x_i^T$ by $M_i^T$, and for each $x_i^F$ by $M_i^F$.

We construct the stubs as follows. Bank $v$ has outdegree zero and $\ell$ incoming stubs such that there exists exactly one with weight $w_{\kappa_j}$. Each bank $\kappa_j$ has exactly one outgoing stub with weight $w_{\kappa_j}$. Furthermore, if literal $x_i$ appears in the clause, then we add an incoming stub with weight $M_i^T$ – or a stub with weight $M_i^F$ if $\neg x_i$ appears. For every bank $x_i^T$, there is a stub for each clause the literal $x_i$ appears in, each with weight $M_i^T$. The analogous condition holds for $x_i^F$. Using $M_i = \max\{M_i^T,M_i^F\}$, we create a single incoming stub with weight $kM_i$ for each $x_i^T$ and $x_i^F$. Lastly, for every bank $x_i$ and $s_i$, we set the indegree to zero and create one outgoing stub with weight $kM_i$.

Finally, bank $x_i$ has external assets of $kM_i$, for every $i \in [k]$.

Overall, the construction of the  instance is polynomial in the size of the instance of . For an example construction see Figure <ref>.

For the clearing oracle, each bank with at most one outgoing stub has a trivial clearing payment – simply assign all assets to the outgoing stub (if any) until it is fully paid. The banks $x_i^T$ and $x_i^F$ can have multiple outgoing stubs. We argue below that in all consistent networks each of these banks has either 0 assets or enough assets to fully pay all outgoing stubs. This implies that for a given consistent network and a given bank, the payments of the bank are the same, for every allocation rule (edge-ranking, proportional, etc., even for non-monotone ones).

It is straightforward to see whether a bank has 0 assets or can pay all edges fully. Thus, defining a clearing payment is possible in polynomial time for every bank in every consistent network, for every (or, more precisely, independent of the specific) allocation rule.

We now prove correctness of the reduction. Observe that, by construction, every consistent set of edges must contain edge $(\kappa_j,v)$ since for each $w_{\kappa_j}$ there exists exactly one bank with an outgoing and one bank with an incoming stub. Similarly, $x_i^T$ is the only bank that has outgoing stubs with weight $M_i^T$. Additionally, for every bank $\kappa_j$ with an incoming stub with weight $M_i^T$ the corresponding clause includes literal $x_i$. Hence, there is an edge $(x_i^T,\kappa_j)$ in every consistent set of edges if and only if $x_i$ appears in clause $\kappa_j$. The same argument extends to literals $x_i^F$. Thus, the consistent sets of edges only vary in the edges of banks $x_i$ and $s_i$ to $x_i^T$ and $x_i^F$. Note that for every $i$ it is possible to either choose (1) edges $(x_i,x_i^T)$ and $(s_i,x_i^F)$ or (2) $(x_i,x_i^F)$ and $(s_i,x_i^T)$, each with the same edge weight $kM_i$. In case (1) we interpret literal $x_i$ to be assigned with value TRUE and $\neg x_i$ with value FALSE. On the other hand, in case (2) literal $\neg x_i$ is interpreted as TRUE and $x_i$ as FALSE. In conclusion, every consistent set of edges corresponds to a truth assignment of variables in $\varphi$ and vice versa.

By construction, exactly one of the banks $x_i^T$ or $x_i^F$ has strictly positive incoming assets. This bank defines the corresponding assignment for the variable. By construction, this bank is then able to settle all debt (while the other one settles no debt at all). As a consequence, bank $\kappa_j$ has a fully saturated incoming edge if and only if there exists a satisfying literal in the corresponding clause. Then, by construction, $\kappa_j$ can settle all debt towards $v$. As a result, for any consistent network, the incoming assets of $v$ equal the sum of weights of satisfied clauses in $\varphi$ for the corresponding assignment. In other words, the local optima for the given instance of  correspond exactly to the local optimal networks w.r.t. $v$-improving debt swaps.

The -reduction is tight since it preserves solutions, neighborhoods, and objective values.

An instance of  consists of a CNF formula $\varphi$ with $k$ variables $x_i$ and $\ell$ clauses where every clause $\kappa_j$ consists of at most three variables. Every satisfying assignment of $\varphi$ is represented by a node in the graph $G(\varphi)$ where two assignments are adjacent if the assignments differ for exactly one variable. For two given assignments, the objective is to decide whether there exists a path connecting the corresponding nodes in $G(\varphi)$. Equivalently, this requires to decide whether there is a sequence of flips between these satisfying assignments changing the truth assignment of exactly one variable in each step. The authors in [14] show -completeness for .

For a reduction, use a slight adaptation of the construction illustrated in Figure <ref> described in proof of Theorem <ref> where all values $w_j$ are set to one. Also, choose edges $(x_i,x_i^T)$ and $(s_i,x_i^F)$ if variable $x_i$ is TRUE in the initial assignment, otherwise choose $(x_i,x_i^F)$ and $(s_i,x_i^T)$. Observe that every debt swap switches the incoming edges of a pair of banks $x_i^T$ and $x_i^F$ where the bank with incoming payments from $x_i$ is interpreted as TRUE. As a result, every sequence of flips in the assignment translates directly to a sequence of debt swaps and vice versa.

The total assets of bank $v$ equal the number of banks $\kappa_j$ with incoming assets. Hence, if $v$ has assets of at least $l$ then every $\kappa_j$ has incoming payments and the associated assignment is satisfying. As an implication, there exists a sequence of flips in the assignment, where every intermediate assignment is satisfying, if and only if there exists a sequence of debt swaps turning the initial into the target network, where $v$ has assets of $\ell$ in every intermediate network. This concludes the proof.

The statement follows by reduction from . As initial network we choose the construction in proof of Theorem <ref> below (see Figure <ref> in Appendix <ref>). The target is the network where all incoming edges with weight $c$ of $v$ and $r$ are switched.
By the same arguments as in proof of Theorem <ref> there exists a desired sequence of semi-positive debt swaps if and only if there exists a solution to the instance of .

§ PROPERTIES AND EXISTENCE OF DEBT SWAPS

§.§ Structural Properties

Monotonicity of the allocation rule implies that when the total assets of bank $v$ increase, then payments on each $e \in E^+(v)$ do not decrease. Intuitively, for this reason, every clearing state of a financial network can be decomposed into two clearing states of appropriate networks. We proceed in two steps: First, each bank $v$ is assigned reduced external assets $\hat{a}^x_v \leq a^x_v$. This results in a new financial network, for which we get the first clearing state. In this state, $v$ (partially) pays her liabilities. For the second step, we reduce each liability by the payment in the first step, and $v$ receives external assets of $a^x_v-\hat{a}^x_v$. This again results in a new financial network, for which we get the second clearing state. The sum the two clearing states is clearing state of the original network.

Consider a financial network $\F$ with external assets $\veca^x$ and a non-negative vector $\hat{\veca}^x \leq \veca^x$, where $\hat{a}^x_v < a^x_v$ for at least one $v\in V$. The network $\F$ can be separated into two networks: $\pre{\F} = (G, \vecl, \hat{\veca}^x, \vecf)$ is called a pre-network of $\F$; $\diff{\F} = (G, \diff{\vecl}, \veca^x-\hat{\veca}^x, \diff{\vecf})$ is the difference network of $\F$ and $\pre{\F}$. The liabilities in $\diff{\F}$ are given by the remaining liabilities after clearing in $\pre{\F}$, (i.e., $\diff{l}_{(u,v)} = l_{(u,v)} - \pre{p}_{(u,v)}$), and the allocation rule is defined as $\diff{f}_{(u,v)}(b_u) = f_{u,v}(\pre{a}_u + b_u) - f_{u,v}(\pre{a}_u)$.

The clearing state in $\F$ equals the sum of clearing states in pre- and difference networks.

Suppose $\pre{\F}$ is a pre-network of $\F$ and $\diff{\F}$ the corresponding difference network. The clearing state of $\F$ is given by the sum of clearing states in $\pre{\F}$ and $\diff{\F}$, i.e., $\vecp = \pre{\vecp} + \diff{\vecp}$.

As mentioned in Section <ref>, the feasible asset vectors for a financial network $\F$ are solutions of a fixed point problem. We reformulate this property for the feasible payments – they are fixed points of a function $g$ with $g_{(u,v)}(\vecc) = f_{(u,v)}(a^x_u + \sum_{e\in E^-(u)}c_e)$ mapping the convex, compact set $\{ \vecc \mid 0 \le c_e \le l_e\}$ to itself. The fixed points of $\pre{g}_{(u,v)}(\vecc)= f_{(u,v)}(\hat{a}^x_u + \sum_{e \in E^-(u)} c_e)$ are the feasible payments in $\pre{\F}$, the fixed points of $\diff{g}_{(u,v)}(\vecc)= \diff{f}_{(u,v)}(a^x_u - \hat{a}^x_u + \sum_{e \in E^-(u)} c_e)$ the feasible payments in $\diff{\F}$.

For the maximal fixed point $\diff{\vecp}$ of $\diff{g}$ it holds that

\begin{align*}
\diff{g}_{(u,v)}(\vecp) &= \diff{f}_{(u,v)}\left(a^x_u - \hat{a}^x_u + \sum_{e\in E^-(u)}p_e\right)  \\
&= f_{(u,v)}\left(\pre{a}_u + a^x_u - \hat{a}^x_u + \sum_{e\in E^-(u)}p_e\right) - f_{(u,v)}\left(\pre{a}_u\right) \\
&= f_{(u,v)}\left(\hat{a}^x_u + \sum_{e \in E^-(u)}\pre{p}_e + a^x_u - \hat{a}^x_u + \sum_{e\in E^-(u)}p_{e}\right) - f_{(u,v)}\left(\hat{a}^x_u + \sum_{e \in E^-(u)}\pre{p}_e\right) \\
&= f_{(u,v)}\left(a^x_u + \sum_{e\in E^-(u)}(p_e + \pre{p}_e)\right) - \pre{p}_e \enspace.
\end{align*}

The second equality follows from the definition of $\diff{f}_{(u,v)}$. The last equality follows since $\pre{\vecp}$ is the maximal fixed point of $\pre{g}$.

The clearing state of $\F$ satisfies $\vecp \geq \pre{\vecp}$ due to monotonicity of all $f_e$. Indeed, for every fixed point $\vecc$ of $g$ it holds that $\vecc \geq \pre{\vecc}$, since $a^x_v > \hat{a}^x_v$ for at least one $v$. As a consequence, every fixed point $\vecc$ can be separated into $\pre{\vecp}$ and $\bar{\vecc}$ such that $\vecc = \pre{\vecp}+\bar{\vecc}$. Now consider $\bar{\vecc}$. Since $\vecc = \pre{\vecp}+\bar{\vecc}$ is a fixed point, we have $\pre{p}_{(u,v)}+\bar{c}_{(u,v)} = f_{(u,v)}(a^x_v + \sum_{e \in E^-(u)} (\pre{p}_e + \bar{c}_e))$ for all $(u,v) \in E$. Equivalently,

\pre{p}_{(u,v)} = f_{(u,v)}\left(a^x_v + \sum_{e \in E^-(u)} (\pre{p}_e + \bar{c}_e)\right) - \bar{c}_{(u,v)}

and, thus, $\bar{\vecc}$ is a fixed point of $\diff{g}$. Hence, every fixed point of $g$ can be separated into $\pre{\vecp}$ and a fixed point for $\diff{g}$. Since the clearing state $\vecp$ is the maximal fixed point of $g$, it must use the maximal fixed point of $\diff{g}$, i.e., $\vecp = \pre{\vecp} + \diff{\vecp}$.

Note that whenever edge $e\in E$ gets saturated in $\pre{\F}$ (i.e., $c_e=\pre{p}_e$), then $\diff{l}_e=0$ in $\diff{\F}$.

If $\pre{\F}$ is a pre-network of $\F$, then for the clearing payments $p_e \geq \pre{p}_e$, for all $e\in E$, and the total assets $a_v \geq \pre{a}_v$, for every bank $v\in V$.

Separability can be used to show that increasing the external assets of one bank Pareto-improves the total assets of every bank. The following lemma extends a similar result from [28] for proportional payments.

Suppose two financial networks $\F$ and $\hat{\F}$ differ only in the external assets of a single bank $v$ such that $a^x_v > \hat{a}^x_v$. For every bank $u \in V$ the total assets in the clearing state satisfy $a_u \geq \hat{a}_u$.

The network $\F$ can be seperated into the pre-network $\pre{\F} = \hat{\F}$ and difference network $\diff{\F}$. The external assets in $\diff{\F}$ are given by $a^x_v-\hat{a}^x_v$ for $v$ and 0 for all other banks $u \neq v, u \in V$. By separability, the clearing state of $\F$ is the sum of clearing states of $\pre{\F}$ and $\diff{\F}$, i.e., $\vecp = \pre{\vecp} + \diff{\vecp}$. Since the total assets of every bank are non-negative, we have $a_u = \pre{a}_u + \diff{a}_u \geq \pre{a}_u = \hat{a}_u$.

The payments in a financial network emerge due to a combination of external assets and cyclic money flow. Clearly, a sink node $t$ (with $E^+(t) = \emptyset$) is not included in any cycle. Thus, all incoming payments of a sink node originated from external assets of other banks. The next definition is due to [28] and establishes a relationship between the external assets of a node $v$ and the incoming assets of a sink.

If an increase of the external assets $a^x_v$ of a node $v \in V$ by $\Delta > 0$ results in total assets $a'_t = a_t + \Delta$ for a sink $t \in V$, then $v$ is $t$-linear on $[a^x_v, a^x_v + \Delta]$. If the increase leads to $\sum_{t \in U} a'_t = \sum_{t \in U} a_t + \Delta$ for a set $U$ of sink nodes, then $v$ is $U$-linear on $[a^x_s, a^x_s + \Delta]$.

If $v$ is $t$-linear, then the benefit of $t$ due to the increase of external assets of $v$ is maximal. We show that the increase of $\Delta>0$ in external assets of a source node $s$ (with $E^-(s) = \emptyset$) raises the total assets of all sinks in sum by at most $\Delta$. Our proof slightly adapts a similar argument in [28].

For a given financial network, let $T\subset V$ be the set of all sinks. If the external assets of a source $s\in V \setminus T$ are increased to $a'^x_s = a^x_s + \Delta$, then the total assets of all sinks increase by at most $\Delta$, i.e., $\sum_{t \in T} a'_t \leq \Delta + \sum_{t \in T} a_t$.

By slight abuse of notation, we use $\F$ to denote the resulting financial network after raising the external assets of $s$ to $a^x_s + \Delta$. By separability, we define $\pre{\F}$ as the pre-network with external assets $a^x_u$ for every bank $u \in V$, i.e., the one before raising the external assets of $s$. Then, the external assets in the difference network $\diff{\F}$ are given by $\Delta$ for $s$ and 0 for all other banks $u\neq s$. The statement follows when $\sum_{t \in T} \diff{a}_t \leq \Delta$.

We use $p^-_u$ and $p^+_u$ to denote the incoming and outgoing assets of $u$ in the clearing state of $\diff{\F}$, i.e., $p^-_u = \sum_{e \in E^-(u)} \diff{p}_e$ and $p^+_u = \sum_{e \in E^+(u)} \diff{p}_e$. Then, $\sum_{u \in V} p^-_u = \sum_{u \in V} p^+_u$, as both are the sum of all payments in the network. Dividing the banks into sinks, source $s$ and all other banks, it holds that

\begin{equation}\label{eq:non-expan}
\sum_{u \in V\setminus (T\cup \{s\})} p^-_u + \sum_{t \in T} p^-_t + p^-_s = \sum_{u \in V\setminus (T\cup \{s\})} p^+_u + \sum_{t \in T} p^+_t + p^+_s \;.
\end{equation}

Since $s$ is a source and the banks in $T$ are sinks, $p^-_s = 0$ and $\sum_{t \in T} p^+_t = 0$. Equation (<ref>) simplifies to

\[
\sum_{t \in T} p^-_t = \sum_{u \in V\setminus (T\cup \{s\})} (p^+_u - p^-_u) + p^+_s \;.
\]

Every bank $u \in V \setminus (T \cup \{s\})$ has external assets of 0 and, thus, the outgoing payments of $u$ are upper bounded by the incoming ones, i.e., $p^+_u \leq p^-_u$. As a direct consequence is $\sum_{t \in T} p^-_t \leq p^+_s \leq \Delta$. Hence, $\sum_{t \in T} \diff{a}_t = \sum_{t \in T} p^-_t \leq \Delta$.

A similar property can be shown if $s$ is not a source bank. The argument uses an auxiliary construction that externalizes the incoming payments of bank $s = v$ by splitting $v$ into two separate nodes $s_v$ and $t_v$. The sink $t_v$ holds the same incoming edges as $v$ in the original graph. Similarly, source $s_v$ has the same outgoing edges as $v$. Setting the external assets of $s_v$ to the total assets $a_v$ of $v$ in the clearing state ensures that the payments of $s_v$ and $v$ are equal. We can then verify that the modified network has the same clearing state as the original network, and, in particular, $t_v$ has the same incoming payments as $v$. Clearly, the nodes representing $v$ are not contained in any cycle.

[>=stealth', shorten >=1pt, auto,
node distance=1cm, scale=1,
transform shape, align=center,
bank/.style=circle, draw, minimum size=2.5pt]
[bank] (u1) at (0,0) $u_1$;
[bank] (v1) [below = of u1] $v_1$;
[bank] (u2) [right = of u1] $u_2$;
[bank] (v2) [right = of v1] $v_2$;
[bank] (w1) [below = of v1] $w_1$;
[bank] (w2) [below = of v2] $w_2$;
[rectangle, draw=black, inner sep=2.5pt] (xv2) [right=0.1cm of v2] $1$;

[->] (u1) to (v2);
[->] (u2) to node[below=2pt, pos=0.1] $1$ (v1);
[->] (v1) to[in=120, out=150, looseness=2] node[above=2pt, midway] $1$ (u2);
[->,dashed] (v1) to[bend right] node[right, midway] $1$ (w1);
[->] (w1) to[bend right] node[right, midway] $1$ (v1);
[->] (v2) to node[right, midway] $1$ (w2);

[>=stealth', shorten >=1pt, auto,
node distance=0.5cm, scale=1,
transform shape, align=center,
bank/.style=circle, draw, inner sep=0.1cm]
[bank] (u1) at (0,0) $u_1$;
[circle, draw=black, inner sep=0.05cm] (tv1) [below = of u1] $t_{v_1}$;
[circle, draw=black, inner sep=0.05cm] (sv1) [below = of tv1] $s_{v_1}$;
[bank] (u2) [right = of u1] $u_2$;
[circle, draw=black, inner sep=0.05cm] (tv2) [below = of u2] $t_{v_2}$;
[circle, draw=black, inner sep=0.05cm] (sv2) [below = of tv2] $s_{v_2}$;
[bank] (w1) [below = of sv1] $w_1$;
[bank] (w2) [below = of sv2] $w_2$;
[rectangle, draw=black, inner sep=2.5pt] (xv1) [left=0.15cm of sv1] $2$;
[rectangle, draw=black, inner sep=2.5pt] (xv2) [right=0.1cm of sv2] $1$;

[->] (u1) to (tv2);
[->] (u2) to node[right, pos=0.3] $1$ (tv1);
[->] (sv1) to[in=140, out=150, looseness=1.9] node[left, midway] $1$ (u2);
[->,dashed] (sv1) to[bend right] node[right, midway] $1$ (w1);
[->] (w1) to[bend right] node[right, midway] $1$ (tv1);
[->] (sv2) to node[right, midway] $1$ (w2);

[>=stealth', shorten >=1pt, auto,
node distance=0.5cm, scale=1,
transform shape, align=center,
bank/.style=circle, draw, inner sep=0.1cm]

[bank] (u1) at (0,0) $u_1$;
[circle, draw=black, inner sep=0.05cm] (tu1) [below = of u1] $t_{u_1}$;
[bank] (v1) [below = of tu1] $v_1$;
[bank] (u2) [right = of u1] $u_2$;
[circle, draw=black, inner sep=0.05cm] (tu2) [below = of u2] $t_{u_2}$;
[bank] (v2) [right = of v1] $v_2$;
[bank] (w1) [below = of v1] $w_1$;
[bank] (w2) [below = of v2] $w_2$;
[rectangle, draw=black, inner sep=2.5pt] (xv1) [left=0.15cm of v1] $1$;
[rectangle, draw=black, inner sep=2.5pt] (xv2) [right=0.1cm of v2] $1$;

[->] (u1) to (tu1);
[->] (u2) to node[right, midway] $1$ (tu2);
[->] (v1) to[in=140, out=150, looseness=1.9] node[left, midway] $1$ (u2);
[->,dashed] (v1) to[bend right] node[right, midway] $1$ (w1);
[->] (w1) to[bend right] node[right, midway] $1$ (v1);
[->] (v2) to node[right, midway] $1$ (w2);

The network on the left corresponds to the network $\sig{\F}$ in Example <ref>. Black edge labels indicate payments. The middle network results from applying source-sink equivalency to $v_1$ and $v_2$, whereas the right network results from applying source-sink equivalency for edges $(u_2,v_1)$ and $(v_2,u_1)$.

For a given financial network $\F$ with bank $v$, we define an adjusted network $\HH$ as follows. Replace $v$ by a source node $s_v$ and a sink node $t_v$. Sink $t_v$ has external assets 0 and the same set of incoming edges as $v$, i.e., $E^-(v)={E_{\HH}}^-(t_v)$. Source $s_v$ has external assets $a_v$ and the same outgoing edges as $v$, i.e., ${E_{\HH}}^+(s_v)=E^+(v)$.
The allocation rule is adjusted to $f^{\HH}_{(s_v, w)} = f_{(v,w)}$ for all $w\in E^+(v)$ and $f^{\HH}_{(u, t_v)} = f_{(u, v)}$ for all $u \in E^-(v)$.

An example construction can be seen in Figure <ref>, where banks $v_1$ and $v_2$ are replaced by sources and sinks.

The next lemma shows that the clearing state in the auxiliary network is equivalent to the one in the original network.

For a given financial network $\F$ and an adjusted network $\HH$ it holds that

(1) the networks have equivalent clearing states, i.e., $p^{\HH}_e = p_e$ for all $e \in (E_{\HH} \cap E)$, $p^{\HH}_{u, t_v} = p_{u,v}$ for all edges $(u,v)\in E^- (v)$ and $p^{\HH}_{s_v, w} = p_{v, w}$ for all edges $(v, w) \in E^+(v)$.

(2) the sink $t_v$ has total assets $a_v - a^x_v$.

First, observe that (2) follows directly from (1). Hence, it remains to show property (1).
As in the proof of Lemma <ref>, we use that the clearing state of $\F$ is the maximal fixed point of $g$ with $g_{(u,w)}(\vecc) = f_{(u,w)}(a^x_u + \sum_{e\in E^-(u)}c_e)$, and the clearing state of $\HH$ is the maximal fixed point of $g^{\HH}$ with $g^{\HH}_{(u,w)}(\vecc^{\HH}) = f^{\HH}_{(u,w)}(a^x_u + \sum_{e\in {E_{\HH}}^-(u)}c^{\HH}_e)$.

First, suppose $\vecp$ is the maximal clearing state of $\F$. Now consider $\vecp^{\HH}$ defined as in property (1) of the lemma. Then. for all edges $(u,w) \in E$ with $u \neq v \neq w$, clearly $g_{(u,w)}(\vecp) = g^{\HH}_{(u,w)}(\vecp^{\HH})$ is true. Similarly for incoming edges of $v$,

\[
g_{(u, v)}(\vecp) = f_{(u, v)}\left( a^x_u + \sum_{e\in E^-(u)} p_e \right) = f^{\HH}_{(u, t_v)} \left( a^x_u + \sum_{e\in E_{\HH}^-(u)} p_e^{\HH} \right) = g_{(u,t_v)}(\vecp^{\HH}).
\]

Now consider the outgoing edges $(v, w) \in E^+(v)$. It holds that

\begin{align*}
p_e = g_{(v, w)}(\vecp) &= f_{(v, w)}\left(a^x_v + \sum_{e\in E^-(v)} p_e \right) = f_{(v,w)} (a_v) =  f^{\HH}_{(s_v, w)}(a_{s_v}) = g_{(s_v,w)}(\vecp^{\HH})\;.
\end{align*}

Hence, $g^{\HH}_{(v,w)}(c)$ is a fixed point for the network $\HH$ and evaluates all payments as in the maximal fixed point $\vecp$ of $g$.

Now, for the converse, suppose that $\vecp^{\HH}$ is the clearing state for $\HH$. Then, by the same equations, we obtain an equivalent fixed point of $g$. In conclusion, this proves (1).

A very similar construction can be used to externalize the payments on an edge.

For a given financial network $\F$ with edge $e=(u,v)$, add the sink $t_v$ and replace $e$ by the edge $(u,t_v)$. Increase the external assets of $v$ by $p_e$. Then, the resulting network $\G$ has the same clearing state as $\F$, i.e., $p^{\G}_{(u, t_v)} = p_{(u,v)}$, and $p^{\G}_e = p_e$ for all other edges.

§.§ Existence of Debt Swaps

Example <ref> shows that semi-positive and Pareto-improving debt swaps can exist, for both proportional and edge-ranking rules.

For proportional payments and edge-ranking rules, financial networks with semi-positive and Pareto-improving debt swaps exist.

Our main result in this section shows that every financial network with a monotone allocation rule does not have a positive debt swap. The theorem substantially generalizes an earlier result for proportional payments [28]. Let us note that the proof in the full version of [28] relies on a Lemma B.1 which is incorrect. The lemma claims the following: For two financial networks $\F^1$ and $\F^2$ with proportional payments on the same set of nodes, suppose there exists one source node $s$ with external assets $a^x_s$ while $a^x_u=0$ for all other banks in $\F^1$ and $\F^2$. If $l^{\F^1}_e \leq l^{\F^2}_e$ for every edge, then $a^{\F^1} \leq a^{\F^2}$ follows.

As a counterexample to this claim, consider a financial network over the three banks $s,w_1$ and $w_2$ and edges $(s,w_1)$ and $(s,w_2)$ with $l_{(s,w_1)}=1$ and $l_{(s,w_2)}=2$. Let the external assets be given by $a^x_s = 2$ and $a^x_{w_1}=a^x_{w_2}=0$. Then, $s$ pays $\frac{1}{1+2}\cdot 2= \frac{2}{3}$ towards $w_1$ and $\frac{2}{1+2}\cdot 2= \frac{4}{3}$ towards $w_2$. Now assume the edge weight $l_{(s,w_1)}$ is raised to $2$. Then, the payments from $s$ to $w_1$ as well as $w_2$ are changed to $\frac{2}{2+2}\cdot 2 = 1 < \frac 43$.

Despite this issue, the result indeed holds true, even for all monotone allocation rules.

[>=stealth', shorten >=1pt, auto,
node distance=1cm, scale=1,
transform shape, align=center,
bank/.style=circle, draw, inner sep=0.1cm]
[bank] (u1) at (0,0) $u_1$;
[bank] (v1) [below = of u1] $v_1$;
[bank] (u2) [right = of u1] $u_2$;
[bank] (v2) [below = of u2] $v_2$;
[rectangle, draw=black, inner sep=2.5pt] (xv1) [left=0.1cm of v1] $a^x_{v_1}$;
[rectangle, draw=black, inner sep=2.5pt] (xv2) [right=0.1cm of v2] $a^x_{v_2}$;

[->] (u1) to  node[right, midway] $p_{e_1}$ (v1);
[->] (u2) to node[right, midway] $p_{e_2}$ (v2);
[->] (-0.6,0.6) to (u1);
[->] (0.6,0.6) to (u1);
[->] (1.1,0.6) to (u2);
[->] (2.3,0.6) to (u2);
[->] (-0.6,-1) to (v1);
[->] (0.6,-1) to (v1);
[->] (1.1,-1) to (v2);
[->] (2.3,-1) to (v2);
[->] (v1) to (-0.6,-2.4);
[->] (v1) to (0.6,-2.4);
[->] (v2) to (1.1,-2.4);
[->] (v2) to (2.3,-2.4);

[>=stealth', shorten >=1pt, auto,
node distance=1cm, scale=1,
transform shape, align=center,
bank/.style=circle, draw, inner sep=0.1cm]
[bank] (u1) at (0,0) $u_1$;
[circle, draw=black, inner sep=0.05cm] (tu1) [below = of u1] $t_{u_1}$;
[bank] (v1) [below = of tu1] $v_1$;
[bank] (u2) [right = of u1] $u_2$;
[circle, draw=black, inner sep=0.05cm] (tu2) [below = of u2] $t_{u_2}$;
[bank] (v2) [below = of tu2] $v_2$;
[rectangle, draw=black, inner sep=2.5pt] (xv1) [left=0.1cm of v1] $a^x_{v_1}+p_{e_1}$;
[rectangle, draw=black, inner sep=2.5pt] (xv2) [right=0.1cm of v2] $a^x_{v_2}+p_{e_2}$;

[->] (u1) to  node[right, midway] $p_{e_1}$ (tu1);
[->] (u2) to node[right, midway] $p_{e_2}$ (tu2);
[->] (-0.6,0.6) to (u1);
[->] (0.6,0.6) to (u1);
[->] (1.1,0.6) to (u2);
[->] (2.3,0.6) to (u2);
[->] (-0.6,-2.8) to (v1);
[->] (0.6,-2.8) to (v1);
[->] (1.1,-2.8) to (v2);
[->] (2.3,-2.8) to (v2);
[->] (v1) to (-0.6,-4);
[->] (v1) to (0.6,-4);
[->] (v2) to (1.1,-4);
[->] (v2) to (2.3,-4);

[>=stealth', shorten >=1pt, auto,
node distance=0.7cm, scale=1,
transform shape, align=center,
bank/.style=circle, draw, inner sep=0.1cm]
[bank] (u1) at (0,0) $u_1$;
[circle, draw=black, inner sep=0.05cm] (tu1) [below = of u1] $t_{u_1}$;
[circle, draw=black, inner sep=0.05cm] (tv1) [below = of tu1] $t_{v_1}$;
[circle, draw=black, inner sep=0.05cm] (sv1) [below = of tv1] $s_{v_1}$;
[bank] (u2) [right = of u1] $u_2$;
[circle, draw=black, inner sep=0.05cm] (tu2) [below = of u2] $t_{u_2}$;
[circle, draw=black, inner sep=0.05cm] (tv2) [below = of tu2] $t_{v_2}$;
[circle, draw=black, inner sep=0.05cm] (sv2) [below = of tv2] $s_{v_2}$;
[rectangle, draw=black, inner sep=2.5pt] (xv1) [left=0.1cm of sv1] $a_{v_1}$;
[rectangle, draw=black, inner sep=2.5pt] (xv2) [right=0.1cm of sv2] $a_{v_2}$;

[->] (u1) to  node[right, midway] $p_{e_1}$ (tu1);
[->] (u2) to node[right, midway] $p_{e_2}$ (tu2);
[->] (-0.63,0.63) to (u1);
[->] (0.63,0.63) to (u1);
[->] (0.8,0.63) to (u2);
[->] (2,0.63) to (u2);
[->] (-0.63,-2.2) to (tv1);
[->] (0.63,-2.2) to (tv1);
[->] (0.8,-2.2) to (tv2);
[->] (2,-2.2) to (tv2);
[->] (sv1) to (-0.63,-4.8);
[->] (sv1) to (0.63,-4.8);
[->] (sv2) to (0.8,-4.8);
[->] (sv2) to (2,-4.8);

Schematic illustration of networks $\G$ and $\HH$ for a financial network $\F$.

[>=stealth', shorten >=1pt, auto,
node distance=1cm, scale=1,
transform shape, align=center,
bank/.style=circle, draw, inner sep=0.1cm]

[bank] (u1) at (0,0) $u_1$;
[circle, draw=black, inner sep=0.05cm] (tu1) [below = of u1] $t_{u_1}$;
[bank] (v1) [below = of tu1] $v_1$;
[bank] (u2) [right = of u1] $u_2$;
[circle, draw=black, inner sep=0.05cm] (tu2) [below = of u2] $t_{u_2}$;
[bank] (v2) [below = of tu2] $v_2$;
[bank] (w1) [below = of v1] $w_1$;
[bank] (w2) [below = of v2] $w_2$;
[rectangle, draw=black, inner sep=2.5pt] (xv2) [right=0.1cm of v2] $1$;

[->] (u1) to (tu1);
[->] (u2) to (tu2);
[->, line width=0.05cm] (v1) to[in=140, out=150, looseness=1.9] (u2);
[->] (v1) to[bend right] (w1);
[->] (w1) to[bend right] (v1);
[->] (v2) to node[right, midway] $1$ (w2);

[>=stealth', shorten >=1pt, auto,
node distance=0.5cm, scale=1,
transform shape, align=center,
bank/.style=circle, draw, inner sep=0.1cm]

[bank] (u1) at (0,0) $u_1$;
[circle, draw=black, inner sep=0.05cm] (tu1) [below = of u1] $t_{u_1}$;
[circle, draw=black, inner sep=0.05cm] (tv1) [below = of tu1] $t_{v_1}$;
[circle, draw=black, inner sep=0.05cm] (sv1) [below = of tv1] $s_{v_1}$;
[bank] (u2) [right = of u1] $u_2$;
[circle, draw=black, inner sep=0.05cm] (tu2) [below = of u2] $t_{u_2}$;
[circle, draw=black, inner sep=0.05cm] (tv2) [below = of tu2] $t_{v_2}$;
[circle, draw=black, inner sep=0.05cm] (sv2) [below = of tv2] $s_{v_2}$;
[bank] (w1) [below = of sv1] $w_1$;
[bank] (w2) [below = of sv2] $w_2$;
[rectangle, draw=black, inner sep=2.5pt] (xv2) [right=0.1cm of sv2] $1$;

[->] (u1) to (tu1);
[->] (u2) to (tu2);
[->, line width=0.05cm] (sv1) to[in=140, out=150, looseness=1.9] (u2);
[->] (sv1) to[bend right] (w1);
[->] (w1) to[bend right] (tv1);
[->] (sv2) to node[right, midway] $1$ (w2);

[>=stealth', shorten >=1pt, auto,
node distance=1cm, scale=1,
transform shape, align=center,
bank/.style=circle, draw, inner sep=0.1cm]

[bank] (u1) at (0,0) $u_1$;
[circle, draw=black, inner sep=0.05cm] (tu1) [below = of u1] $t_{u_1}$;
[bank] (v1) [below = of tu1] $v_1$;
[bank] (u2) [right = of u1] $u_2$;
[circle, draw=black, inner sep=0.05cm] (tu2) [below = of u2] $t_{u_2}$;
[bank] (v2) [right = of v1] $v_2$;
[bank] (w1) [below = of v1] $w_1$;
[bank] (w2) [below = of v2] $w_2$;
[rectangle, draw=black, inner sep=2.5pt] (xv1) [left=0.15cm of v1] $1$;
[rectangle, draw=black, inner sep=2.5pt] (xv2) [right=0.1cm of v2] $1$;

[->] (u1) to (tu1);
[->] (u2) to node[right, midway] $1$ (tu2);
[->, line width=0.05cm] (v1) to[in=140, out=150, looseness=1.9] node[right, midway] $1$ (u2);
[->] (v1) to[bend right] node[right, midway] $1$ (w1);p
[->] (w1) to[bend right] node[right, midway] $1$ (v1);
[->] (v2) to node[right, midway] $1$ (w2);

[>=stealth', shorten >=1pt, auto,
node distance=0.5cm, scale=1,
transform shape, align=center,
bank/.style=circle, draw, inner sep=0.1cm]

[bank] (u1) at (0,0) $u_1$;
[circle, draw=black, inner sep=0.05cm] (tu1) [below = of u1] $t_{u_1}$;
[circle, draw=black, inner sep=0.05cm] (tv1) [below = of tu1] $t_{v_1}$;
[circle, draw=black, inner sep=0.05cm] (sv1) [below = of tv1] $s_{v_1}$;
[bank] (u2) [right = of u1] $u_2$;
[circle, draw=black, inner sep=0.05cm] (tu2) [below = of u2] $t_{u_2}$;
[circle, draw=black, inner sep=0.05cm] (tv2) [below = of tu2] $t_{v_2}$;
[circle, draw=black, inner sep=0.05cm] (sv2) [right = of sv1] $s_{v_2}$;
[bank] (w1) [below = of sv1] $w_1$;
[bank] (w2) [below = of sv2] $w_2$;
[rectangle, draw=black, inner sep=2.5pt] (xv1) [left=0.15cm of sv1] $2$;
[rectangle, draw=black, inner sep=2.5pt] (xv2) [right=0.1cm of sv2] $1$;

[->] (u1) to (tu1);
[->] (u2) to node[right, midway] $1$ (tu2);
[->, line width=0.05cm] (sv1) to[in=140, out=150, looseness=1.9] node[right, midway] $1$ (u2);
[->] (sv1) to[bend right] node[right, midway] $1$ (w1);
[->] (w1) to[bend right] node[right, pos=0.17] $1$ (tv1);
[->] (sv2) to node[right, midway] $1$ (w2);

The networks $\G$ and $\sig{\G}$ depict $\F$ and $\sig{\F}$ from Example <ref> after applying source-sink equivalency to edges $(u_1,v_1), (u_2,v_2)$ and $(u_1,v_2), (u_2,v_1)$, respectively. The networks $\HH$ and $\sig{\HH}$ are obtained when applying source-sink equivalency to $v_1$ and $v_2$ both for $\G$ and $\sig{\G}$.

To prove the theorem, we assume for a contradiction there exists a network $\F$ with a positive swap of edges $e_1=(u_1,v_1)$ and $e_2=(u_2,v_2)$. To analyze the payments in $\F$, source-sink-equivalency is applied to the swap edges. Let $\G$ denote the resulting network, see Figure <ref> for an illustration. To accommodate for the reduced incoming payments $a_{v_1} - a^x_{v_1} - p_{e_1}$ of $v_1$, the external assets are set to $a^x_{v_1} + p_{e_1}$. The external assets of $v_2$ are set analogously.
The network $\HH$ is derived by additionally applying source-sink equivalency to $v_1$ and $v_2$ in $\G$. Then, $t_{v_1}$ and $t_{v_2}$ receive incoming payments of $a_{v_1} - a^x_{v_1} - p_{e_1}$ and $a_{v_2} - a^x_{v_2} - p_{e_2}$, respectively. Note that the construction has no impact on the payments in the clearing state. Analogously, the networks $\sig{\G}$ and $\sig{\HH}$ are constructed for the network $\sig{\F}$ after the debt swap. Note that the networks $\G, \sig{\G}$ and $\HH, \sig{\HH}$ have the same cycles but differ in external assets, respectively.

The next lemma introduces a useful connection between $\HH$ and $\sig{\HH}$.

Consider the financial networks $\F$ before and $\sig{\F}$ after a debt swap. If $\atvo \geq \aovo$ and $\atvt \geq \aovt$, then the following hold:

(1) $\HH$ and $\sig{\HH}$ only differ in the external assets at $\svo$ and $\svt$ (and thus in their clearing state).

(2) $\HH$ is a pre-network of $\sig{\HH}$.

(3) $s_{v_1}$ and $s_{v_2}$ are $(t_{u_1}, t_{u_2}, \tvo, \tvt)$-linear in $\HH$ on intervals $[\aovo,\,\, \atvo]$ and $[\aovt,\,\, \atvt]$, respectively.

By definition, the underlying graphs of $\F$ and $\sig{\F}$ only differ in the liabilities of $u_1$ and $u_2$ to $v_1$ and $v_2$. When applying source-sink equivalency to these edges, all other edges remain the same. The resulting networks $\G$ and $\sig{\G}$ only differ in external assets of $v_1$ and $v_2$. This still holds when applying source-sink equivalency to $v_1$ and $v_2$ to $\G$ and $\sig{\G}$. Hence, (1) is satisfied. By definition, (1) directly implies (2).

Towards (3), consider the pre-network $\HH$. Suppose the external assets at the sources $\svo$ and $\svt$ are increased by $\atvo - \aovo$ and $\atvt - \aovt$, respectively. In total, the external assets of both banks are raised by $(\atvo + \atvt) - (\aovo + \aovt).$

By (1), every bank now has the same external assets and liabilities as in $\sig{\HH}$ and, thus, the clearing state is $\sig{\vecp}$. For $\sig{\HH}$ we use the notation $\sig{e}_1 = (u_1,t_{u_2})$ and $\sig{e}_2 = (u_2,t_{u_1})$ for the swapped edges. Then, the total assets of the sinks $t_{u_1}$, $t_{u_2}$, $\tvo$, and $\tvt$ increase by a total amount of

\begin{align*}
&(\sig{a}_{t_{u_1}} + \sig{a}_{t_{u_2}} + \sig{a}_{t_{v_1}} + \sig{a}_{t_{v_2}}) - (a_{t_{u_1}} + a_{t_{u_2}} + a_{t_{v_1}} + a_{t_{v_2}})\\
=\;& \left( \sig{p}_{\sig{e}_2} + \sig{p}_{\sig{e}_1} + (\atvo - a^x_{v_1} - \sig{p}_{\sig{e}_2}) + (\atvt - a^x_{v_2} - \sig{p}_{\sig{e}_1}) \right) \\
& \hspace{0.5cm} - \left( p_{e_1} + p_{e_2} + (\aovo - a^x_{v_1} - p_{e_1}) + (\aovt - a^x_{v_2} - p_{e_2})  \right) \\
=\;& (\atvo + \atvt) - (\aovo + \aovt).
\end{align*}

Consequently, sources $\svo$ and $\svt$ are $(t_{u_1}, t_{u_2}, \tvo, \tvt)$-linear on $[\aovo,\,\, \atvo]$ and $[\aovt,\,\, \atvt]$, respectively.

The next technical lemma characterizes the effects of increasing external assets of $\svo$ and $\svt$ in $\HH$.

Let $\HH_{\Delta}$ be the resulting network when increasing the external assets of $\svo$ and $\svt$ in $\HH$ by $\delta_{\svo} \in [0, \atvo - \aovo]$ and $\delta_{\svt} \in [0, \atvt - \aovt]$, respectively. We use $\Delta_{w}$ to denote the increase in total assets of bank $w$, i.e., $\Delta_w = a^{\HH_{\Delta}}_w - a_w$. We use $\F_{\Delta}$ to denote the network when reversing the source-sink equivalency both for $t_{v_1}, s_{v_1}$ and $t_{v_2}, s_{v_2}$ as well as for $t_{u_1}$ and $t_{u_2}$.

For $\HH_{\Delta}$ and $\F_{\Delta}$ the following are true:

(1) $\delta_{\svo} + \delta_{\svt} = \Delta_{\tvo} + \Delta_{\tvt} + \Delta_{t_{u_1}} + \Delta_{t_{u_2}}$.

(2) If $\delta_{\svo}> 0$ or $\delta_{\svt}>0$, then $\delta_{\svo} \neq \Delta_{\tvo} + \Delta_{t_{u_1}}$ and $\delta_{\svt} \neq \Delta_{\tvt} + \Delta_{t_{u_2}}$.

(1) directly follows from $(t_{u_1}, t_{u_2}, \tvo, \tvt)$-linearity of $\svo$ and $\svt$ on intervals $[\aovo, \atvo]$ and $[\aovt, \atvt]$ (Lemma <ref>).
For (2), assume that $\delta_{\svo}> 0$ or $\delta_{\svt}>0$ and $\delta_{\svo} = \Delta_{\tvo} + \Delta_{t_{u_1}}$. Then, by (1) it follows that $\delta_{\svt} = \Delta_{\tvt} + \Delta_{t_{u_2}}$.

Intuitively, the additional external assets of $v_1$ are forwarded through the network and, eventually, are payed back to $v_1$. The same holds for the additional external assets of $v_2$. To determine the external assets of $v_1$ in $\F_{\Delta}$, first, observe that the incoming assets of $v_1$ are at least the incoming assets of $v_1$ in $\F$ of $a_{v_1} - a^x_{v_1}$. In $\F_{\Delta}$, the bank receives additional payments of $\Delta_{\tvo} + \Delta_{t_{u_1}}$. Furthermore, the raised external assets could enable payments in new cycles where all payments from $v_1$ towards the cycle are forwarded back to $v_1$.

Formally, recall that the total assets of $s_{v_1}$ in $\HH_{\Delta}$ equal the total assets of $v_1$ in $\F_{\Delta}$. The incoming payments of $v_1$ in $\F_{\Delta}$ are the sum of total assets of $t_{u_1}$ and $t_{v_1}$ in $\HH_{\Delta}$. Since $\HH$ is a pre-network of $\HH_{\Delta}$ with clearing state equivalent to $\F$, this sum is given by $(a_v - a_v^x) + \Delta_{t_{v_1}} + \Delta_{t_{u_1}}$. Now the external assets of $v_1$ in $\F_{\Delta}$ are the total assets of $s_{v_1}$ minus the sum of total assets of $t_{u_1}$ and $t_{v_1}$ in $\HH_{\Delta}$, i.e.,

\begin{align*}
& a_{v_1} + \delta_{v_1} - \left((a_{v_1} - a^x_{v_1}) + \Delta_{\tvo} + \Delta_{t_{u_1}}\right)\\
=\;& a^x_{v_1} + \delta_{v_1} - \Delta_{\tvo} - \Delta_{t_{u_1}}\\
=\;& a^x_{v_1}
\end{align*}

where the last equality follows by assumption.