Goethe University Frankfurt<EMAIL_ADDRESS>frankfurt.dehttps://orcid.org/0000-0003-0131-5605King’s College London, United
Kingdomcarmine.ventre@kcl.ac.ukhttps://orcid.org/0000-0003-1464-1215 Goethe
University Frankfurt<EMAIL_ADDRESS>frankfurt.dehttps://orcid.org/0000-0003-0845-1941 Martin Hoefer, Carmine
Ventre, Lisa Wilhelmi [500]Theory of computation Theory and algorithms for
application domains [300]Networks Network algorithms

###### Acknowledgements.

This paper was initiated at the Dagstuhl seminar 22452 “Computational Social
Dynamics”. The authors thank the organizers and participants of the seminar.
Martin Hoefer and Lisa Wilhelmi gratefully acknowledge support by DFG Research
Unit ADYN under grant DFG 411362735. 0

# Algorithms for Claims Trading

Martin Hoefer  Carmine Ventre  Lisa Wilhelmi

###### Abstract

The recent banking crisis has again emphasized the importance of understanding
and mitigating systemic risk in financial networks. In this paper, we study a
market-driven approach to rescue a bank in distress based on the idea of
_claims trading_ , a notion defined in Chapter 11 of the U.S. Bankruptcy Code.
We formalize the idea in the context of the seminal model of financial
networks by Eisenberg and Noe [5]. For two given banks $v$ and $w$, we
consider the operation that $w$ takes over some claims of $v$ and in return
gives liquidity to $v$ (or creditors of $v$) to ultimately rescue $v$ (or
mitigate contagion effects). We study the structural properties and
computational complexity of decision and optimization problems for several
variants of claims trading.

When trading incoming edges of $v$ (i.e., claims for which $v$ is the
creditor), we show that there is no trade in which _both banks $v$ and $w$
strictly_ improve their assets. We therefore consider _creditor-positive_
trades, in which $v$ profits strictly and $w$ remains indifferent. For a given
set $C$ of incoming edges of $v$, we provide an efficient algorithm to compute
payments by $w$ that result in a creditor-positive trade and maximal assets of
$v$. When the set $C$ must also be chosen, the problem becomes weakly NP-hard.
Our main result here is a bicriteria FPTAS to compute an approximate trade,
which allows for slightly increased payments by $w$. The approximate trade
results in nearly the optimal amount of assets of $v$ in any exact trade. Our
results extend to the case in which banks use general monotone payment
functions to settle their debt and the emerging clearing state can be computed
efficiently.

In contrast, for trading outgoing edges of $v$ (i.e., claims for which $v$ is
the debtor), the goal is to maximize the increase in assets for the creditors
of $v$. Notably, for these results the characteristics of the payment
functions of the banks are essential. For payments ranking creditors one by
one, we show NP-hardness of approximation within a factor polynomial in the
network size, in both problem variants when the set of claims $C$ is part of
the input or not. Instead, for payments proportional to the value of each
debt, our results indicate more favorable conditions.

###### keywords:

Financial Networks, Claims Trade, Systemic Risk

###### category:

##  1 Introduction

The global banking crisis of March 2023 caused turmoil in a market fearful of
the repeat of the Great Financial Crisis of 2007. These recent events serve as
a stark reminder of the paramount importance of the study of systemic risk in
financial networks. In this growing body of work, the focus is mainly on the
complexity of computing _clearing states_ , known to measure the exposure of
the different banks in the network to insolvencies within, see, e.g., [5, 23,
10], and strategic aspects of the banks’ behavior, cf. [1, 17, 8, 11].
However, to calm the market and prevent contagion, regulators and central
banks are more interested in finding ways to rescue banks in distress,
reassure investors that the system is stable and avoid further bank runs. In
fact, Silicon Valley Bank, Signature Bank and Credit Suisse – the three banks
at the heart of the crisis last March – were all acquired by other banks in
the network, and, by modifying the network, this has seemingly mitigated
systemic risk.

A line of research in financial networks on interventions in the network is
recently discussed in [18, 7], the main idea being that banks can swap debt
contracts. In particular, the authors of [7] study the extent to which a
sequence of debt swaps can reduce the risk in the network, in the sense that
bank assets Pareto-improve. Notably, swaps can occur anywhere in the network,
even if the focus is strict improvement of the assets of a given bank.

In this work, we build on this idea and initiate research on the computation
of a network-based “rescue package” deal for a given bank with the objective
of making it solvent. This is exactly the problem that regulators faced in
March 2023 for the aforementioned banks. However, _acquisitions_ do not seem
to be the right operations in these instances since they have two main
drawbacks from a societal perspective (as also witnessed by the reactions to
recent deals). Firstly, the acquiring bank rarely has enough time or freedom
to evaluate the purchase and make a sensible business decision. Secondly, and
consequently, it often requires a security for bailout from the central bank,
in the form of significant protection against potential losses from risks
associated with the transaction. For example, in the acquisition of Credit
Suisse, UBS had little choice in the matter, as reported by Bloomberg news
[2], and received a guarantee worth CHF 9 billion, as confirmed by the Swiss
Federal Council [3].

We instead study a market-driven approach to rescue banks in distress based on
the idea of _claims trading_. Claims trading is defined in Chapter 11 of the
U.S. Bankruptcy Code. We formalize the idea and analyze the consequences of
such trades in the context of financial networks. When a company is in
financial distress, its creditors can assert their rights to repayment by
submitting a claim. At this point, a creditor can either wait for the
positions to unwind and get (a part of) the claim once the bankruptcy is
settled, or she can sell her credit claim to a willing buyer for some
immediate liquidity. The former approach is equivalent to the mainstream work
on systemic risk since the insolvency of a bank can directly cascade through
the network via lower payments to its creditors. We want to explore ways to
find interested buyers that purchase the claims of an insolvent bank $v$ and
give liquidity to the network that ultimately rescues $v$. Ideally, the buyers
should avoid any loss so that the cash invested in buying the claim will
return via increased payments within the network; this way incentives of
buyers are aligned, and systemic risk is reduced at no extra cost to the
network.

We design efficient algorithms to compute claims trades or settle the inherent
complexity status of the problems. The importance of algorithms computing
claim trades that resolve complicated systemic issues in finance cannot be
underestimated. In practice, deals are concocted when markets are closed, and
algorithms that efficiently compute solutions in these pressurised situations
become essential.

Related Work.  Much of the work on systemic risk in financial networks,
including ours, builds upon [5]. In this seminal work, the authors propose a
model and prove existence and properties of clearing states. Moreover, they
also provide a polynomial-time algorithm for their computation. The model in
[5] has been extended along many dimensions by follow-up work; for example,
the authors of [20] add default costs whereas financial derivatives are
considered in [22]. Computation of clearing states for the latter model is
studied in [23, 10, 9] for different notions of approximation and payment
schemes adopted. The solution space of clearing states for financial networks
with derivatives is studied in [19].

The study of strategic behavior in financial networks was initiated in [1],
where banks are assumed to strategize in the way they allocate money to their
creditors. A similar approach is used in [11, 8]. A different model, featuring
derivatives, and banks strategically donating money or cancelling debts is
studied in [17]. The idea of cancelling debts is further explored in [12]. The
authors of [12, 16] consider computational complexity of computing optimal or
approximate bailout policies from the central bank external to the network. In
contrast, in our work all transfers of assets are intrinsic to the network,
and the bank providing the assets must not be harmed. In [13], the authors
study computational complexity of strategic changes to the underlying network
via debt transfers.

Debt swapping is introduced in [18] – the authors focus more on the existence
and properties of swaps with and without shocks to the system. As discussed
above, the authors of [7] share goals that are somewhat similar to ours but
use a different operation to update the network. A related line of work
considers portfolio compression, an accounting operation by means of which all
the cycles in the network are deleted. The effects on systemic risk of
portfolio compression are studied in [21, 24]. However, it is important to
note that portfolio compression can lead to a worse outcome for banks that are
not contained in the cycle [21] and consequently it is not clear why banks
should accept to modify their balance sheets in this way, as argued
empirically in [15].

To the best of our knowledge, ours is the first work to study claims trading
in the analysis of financial networks. Claims trading in bankruptcy has been
studied by law scholars, who for example argue that its effects in that
context are variegated and nuanced in general [14] but do not concern the
governance of the bankruptcy process [6].

Contribution.  We focus on the elementary setting with one given bank $v$ to
save (e.g., Credit Suisse) and one bank $w$ that may rescue it (e.g., UBS). We
consider the following problem: Are there claims of $v$ that can be sold to
$w$ so that $v$ becomes solvent (i.e., after the claims trade, $v$ can fully
pay all its liabilities)? This problem gives rise to a suite of algorithmic
questions, depending on the remit of the algorithmic decision, such as: How
many claims are we allowed to trade? Which claims of $v$ should we trade? What
are the payments that must be transferred from $w$ to $v$ to make the trade
worthwhile for $w$? Our treatment is steered by the following structural
insight: We prove that it is impossible for _both $v$ and $w$ to strictly_
profit from the claims trade. Accordingly, we restrict our attention to
creditor-positive trades that strictly improve $v$ without harming $w$.

For our first set of algorithmic results in Section 3, we fix one claim with
creditor $v$ to be traded with $w$. Does this represent a feasible (i.e.,
creditor-positive) trade? This can be decided by simply computing clearing
states that determine the payment towards each debt in the network. The
problem becomes interesting if we also determine the _haircut rate_
$\alpha\in[0,1]$ of the trade – in order to provide liquidity, $w$ may be
willing to pay an $\alpha$-fraction of the claim’s liability to $v$. Depending
on the payment functions used by banks to distribute money to their debts, we
design different polynomial-time algorithms that determine feasibility of the
trade and also $\alpha^{*}$ (if any), the value of $\alpha$ maximizing the
assets of $v$ (or a close approximation of $\alpha^{*}$ if the payment
functions are too granular vis-a-vis the input size). Let us highlight that
these results also apply to the case in which $v$ is the _debtor_ of the claim
to trade; in fact, we prove that every creditor-positive trade Pareto-improves
the clearing state – each bank in the network is (weakly) better off after the
trade. By maximizing the assets of the creditor of the traded claim we, thus,
also maximize assets of the debtor.

We consider trading multiple claims with creditor $v$ in Section 4. For a
fixed set of claims our results from Section 3 extend rather directly. The
picture becomes less benign when we also have to choose the subset of claims
to be traded. Indeed, in Section 4.2 we show that it is weakly NP-hard to
decide if there is a subset of claims along with suitable haircut rates to
obtain a creditor-positive claims trade that makes $v$ solvent. In our most
technical contribution, we show that there exists a bicriteria FPTAS for
deciding this problem. If an exact trade exists that yields total assets of
$A^{*}$ for $v$, we find an approximate trade with assets at least
$A^{*}-\delta$ for exponentially small $\delta$, which allows haircut rates of
at most $1+\varepsilon$. The FPTAS applies to all financial networks with
general monotone payment functions for which a clearing state can be computed
efficiently. On a technical level, we fix a desired value $A$ for the total
assets of $v$. Using a subroutine we determine if there is an approximate
trade that yields this asset level for $v$. En route, we discover an intricate
monotonicity property – if there is an exact trade that yields assets $A^{*}$
for $v$, then for every $A\leq A^{*}$ there is an approximate trade with
assets $A$ for $v$. Notably, monotonicity can break above $A^{*}$. Still, we
can apply binary search to find an approximate trade with assets at least
$A^{*}-\delta$.

Finally, for trading multiple claims with debtor $u$ in Section 5 – rather
than trying to save $u$ – our goal is improve conditions for the creditors of
$u$ to minimize the contagion effects by $u$’s bankruptcy. Interestingly, the
results here depend significantly on the choice of the payment functions. For
payments based on a ranking of the creditors, we show that the problem becomes
NP-hard to approximate within a factor polynomial in the network size. In
contrast, for payments proportional to the value of each debt, we can solve
the problem for a given set of claims, but it becomes strongly NP-hard when
having to choose the set of claims.

All missing proofs are deferred to the Appendix A. For our results in the
paper we assume that haircut rates can be chosen; Appendix B contains similar
results for fixed haircut rates.

##  2 Model and Preliminaries

A financial network $\mathcal{F}=(G,\bm{\ell},\mathbf{a}^{x},\mathbf{f})$ is
expressed as a directed multigraph111Claims trades in simple graphs can result
in graphs with multi-edges. This can sometimes be avoided by analyzing the
trades in equivalent simple graphs with suitable auxiliary banks. Since all
our arguments can also be applied in the context of multigraphs, we discuss
the more general model. $G=(V,E,\text{de},\text{cr})$ without self loops. We
denote $n=|V|$. Every node $v\in V$ in the graph represents a financial
institution or _bank_. Every edge $e\in E$ represents a _debt contract_ or
_claim_ involving two banks. For each edge $e\in E$, $\text{de}(e)$ specifies
the debtor (i.e., the source) and $\text{cr}(e)$ the creditor (i.e., target).
Edge $e\in E$ has a weight $\ell_{e}\in\mathbb{N}_{>0}$. In other words, in
the context of debt contract $e$, bank $\text{de}(e)$ owes $\text{cr}(e)$ an
amount of $\ell_{e}$. We denote the set of outgoing and incoming edges of a
bank $v$ by $E^{+}(v)=\\{e\in E\mid v=\text{de}(e)\\}$ and $E^{-}(v)=\\{e\in
E\mid v=\text{cr}(e)\\}$. Since we allow multi-edges, several debt contracts
with possibly different liabilities could exist between the same pair of
banks. The _total liabilities_ $L_{v}$ of $v$ are the sum of weights of all
outgoing edges of $v$, i.e., $\sum_{e\in E^{+}(v)}\ell_{e}=L_{v}$.
Furthermore, every bank $v$ holds _external assets_ $a_{v}^{x}\in\mathbb{N}$.
They can be interpreted as an amount of money the bank receives from outside
the network.

Let $b_{v}\in[a_{v}^{x},a_{v}^{x}+\sum_{e\in E^{-}(v)}\ell_{e}]$ be the total
funds of bank $v$. Bank $v$ distributes her total funds according to a given
_payment function_ $\mathbf{f}_{v}=(f_{e})_{e\in E^{+}(v)}$, where
$f_{e}:\mathbb{R}\rightarrow[0,\ell_{e}]$. For every outgoing edge, the
function $f_{e}(b_{v})$ defines the amount of money $v$ pays towards $e$. We
follow previous literature and assume the following conditions for every
payment function:

  1. (1)

Every function $f_{e}(b_{v})$ is non-decreasing and bounded by $0\leq
f_{e}(b_{v})\leq\ell_{e}$.

  2. (2)

Every bank pays all funds until all liabilities are settled: $\sum_{e\in
E^{+}(v)}f_{v}(b_{v})=\min\\{b_{v},L_{v}\\}$.

  3. (3)

The sum of payments of a bank is limited by the total funds: $\sum_{e\in
E^{+}(v)}f_{v}(b_{v})\leq b_{v}$.

Here (2) implies (3), and we mention (3) explicitly for clarity. For a
_monotone_ function $\mathbf{f}_{v}$, $v$ weakly increases the payment on
every outgoing edge when receiving additional funds.

Clearing States.  Let $\mathbf{p}=(p_{e})_{e\in E}$ be the arising payments in
the network when every bank $v$ distributes the funds according to her payment
functions $\mathbf{f}_{v}$. The _incoming payments_ of $v$ are given by
$\sum_{e\in E^{-}(v)}p_{e}$. The _total assets_ $a_{v}$ are defined as the
external assets plus the incoming payments, i.e., $a_{v}=a_{v}^{x}+\sum_{e\in
E^{-}(v)}p_{e}$. Observe that the above conditions (1), (2) and (3) are fixed-
point constraints. A vector of total assets $\mathbf{a}=(a_{v})_{v\in V}$ is
called _feasible_ if it satisfies all fixed-point constraints. More formally,
for every feasible $\mathbf{a}$ it holds that $a_{v}=a_{v}^{x}+\sum_{e\in
E^{-}(v)}f_{e}(a_{\text{de}(e)})$. The payments $\mathbf{p}$ corresponding to
a feasible vector $\mathbf{a}$ are called a _clearing state_. For fixed
payment functions, multiple clearing states may exist. We assume throughout
that every payment function $\mathbf{f}_{v}$ is _monotone_ , i.e.,
$f_{e}(x)\geq f_{e}(y)$ for all $x\geq y\geq 0$ and every $e\in E^{+}(v)$.
This implies that all clearing states form a complete lattice [1, 4]. Thus,
the point-wise minimal and maximal clearing states are unique. We follow
previous literature and assume that the _maximal_ clearing state arises in the
network.

Payment Functions.  In the seminal work of Eisenberg and Noe [5] and the
majority of subsequent works, all banks are assumed to allocate their assets
using _proportional_ payment functions. The _recovery rate_
$r_{v}=\min\\{a_{v}/L_{v},1\\}$ is the fraction of total liabilities $v$ can
pay off, and the payments on edge $e\in E^{+}(v)$ are defined proportionally
by $f_{e}(a_{v})=r_{v}\cdot\ell_{e}$. Hence, if $r_{v}=1$, then $v$ will fully
settle all liabilities. Otherwise, $v$ is in default, $r_{v}<1$, and the
liabilities are settled partially in proportion to their weight. These
payments are often used when all debt contracts fall due at the same date. If,
on the other hand, different debt contracts are assigned different priorities
or maturity dates, payments are more suitably expressed by _edge-ranking_
payment functions. Then, the debt contracts in $E^{+}(v)$ are ordered by a
permutation $\bm{\pi}_{v}$. First, $v$ makes payments towards the highest
ranked edge $\pi_{v}(1)$ until the edge is saturated or $v$ has no remaining
assets. Once $\pi_{v}(1)$ is fully paid off, $v$ pays off the second highest
ranked edge $\pi_{v}(2)$ until the edge is saturated or $v$ has no remaining
assets. The process continues and ends when either all liabilities are settled
or $v$ exhausted all assets.

Both proportional and edge-ranking payments are monotone. For proportional
payments, the clearing state can be computed in polynomial time [5]; for edge-
ranking payments in strongly polynomial time [1].

In this paper, we obtain some results explicitly for networks with
proportional and edge-ranking payment functions. Most of our results, however,
generalize to arbitrary monotone payment functions when there is an efficient
_clearing oracle_ , i.e., there exists an algorithm that receives a network
$\mathcal{F}$ as input and outputs the clearing state $\mathbf{p}$ in
polynomial time.

Claims Trades.  When a bank $u$ is in default and unable to settle all debt,
this introduces risk into the network. In particular, the creditors of $u$ do
not receive their full liabilities. This could lead to further defaults of the
creditor banks. In order to reduce the risk of spreading default, the
creditors of $u$ can sell claims they make towards $u$. More in detail,
consider banks $u,v$ and $w$ with edge $e$ with $\text{de}(e)=u$ and
$\text{cr}(e)=v$, $\ell_{e}\geq 0$. Suppose $u$ is in default. If $v$ and $w$
perform a claims trade, $w$ becomes the new creditor of bank $u$ with the same
liability. Consequently, any payment from $u$ towards the claim will be
received by $w$. In return for the traded claim, $v$ receives a _return_
$\rho$ from $w$, i.e., an immediate payment of $\rho=\alpha\cdot\ell_{e}$, for
some $\alpha\in[0,1]$. We call $\alpha$ the _haircut rate_. To separate the
return from the payments in the clearing state, we model the return by a
transfer of external assets from $w$ to $v$. Note that $w$ can invest at most
her external assets as a return, so every trade must satisfy
$\alpha\ell_{e}\leq a_{w}^{x}$. After a trade the external assets of $v$ and
$w$ might no longer be integer values.

We proceed to define three variants of claims trades. We are given a financial
network with distinct banks $u,v,w\in V$, an edge $e\in E$ with
$(\text{de}(e),\text{cr}(e))=(u,v)$ and haircut rate $\alpha\in[0,1]$. For a
_(single) claims trade_ of $e$ to $w$ we perform the following adjustments to
the network: (1) change the creditor of $e$ to $\text{cr}^{\prime}(e)=w$, (2)
change external assets of $v$ to $a^{x}_{v}+\alpha\cdot\ell_{e}$ and (3)
change external assets of $w$ to $a^{x}_{w}-\alpha\cdot\ell_{e}\geq 0$. We
denote the resulting _post-trade network_ by
$\mathcal{F}^{\prime}=(G^{\prime},\bm{\ell},\mathbf{a}^{\prime
x},\mathbf{f})$, and the resulting clearing state in $\mathcal{F}^{\prime}$ by
$\mathbf{p}^{\prime}$. For a given trade of $e$ to $w$, we call $v$ the
_creditor_ and $w$ the _buyer_. Observe that the total assets of $v$ after the
trade are given by
$a^{\prime}_{v}=a^{x}_{v}+\alpha\cdot\ell_{e}+\sum_{e^{\prime}\in{E^{\prime}}^{-}(v)}p^{\prime}_{e^{\prime}}$.
Similarly, the total assets of $w$ after the trade are
$a^{\prime}_{w}=a^{x}_{w}-\alpha\cdot\ell_{e}+\sum_{e^{\prime}\in{E^{\prime}}^{-}(w)}p^{\prime}_{e^{\prime}}$.

The claims trade operation can be directly extended to a trade of multiple
edges. As outlined in the introduction, we are interested in the effects when
a single bank (in default) trades claims with another bank $w$ (such as a
central bank). We study the differences when trading incoming or outgoing
edges. Observe that both generalize single claims trades.

For a _multi-trade of incoming edges_ , there are distinct banks $v,w$ in a
network $\mathcal{F}$, a set $C$ of $k$ distinct incoming edges
$e_{1},\ldots,e_{k}\in E^{-}(v)$, and haircut rates
$\alpha_{1},\ldots,\alpha_{k}$, such that $\text{de}(e_{i})\neq w$, for all
$i$. After the trade, a new network $\mathcal{F}^{\prime}$ emerges: We change
$\text{cr}^{\prime}(e_{i})=w$, for all $i=1,\ldots,k$, adjust external assets
for $v$ to $a^{x}_{v}+\sum_{i=1}^{k}\alpha_{i}\ell_{e_{i}}$, and for $w$ to
$a^{x}_{w}-\sum_{i=1}^{k}\alpha_{i}\ell_{e_{i}}\geq 0$.

For a _multi-trade of outgoing edges_ , there are distinct banks $u,w$ in a
network $\mathcal{F}$, a set $C$ of $k$ distinct outgoing edges
$e_{1},\ldots,e_{k}\in E^{+}(v)$ with $\text{cr}(e_{i})=v_{i}$, and haircut
rates $\alpha_{1},\ldots,\alpha_{k}$, such that $\text{cr}(e_{i})\neq w$, for
all $i$. After the trade, a new network $\mathcal{F}^{\prime}$ emerges: We
change $\text{cr}^{\prime}(e_{i})=w$, for all $i=1\ldots,k$, adjust external
assets for each $v_{i}$ to $a^{x}_{v_{i}}+\alpha_{i}\ell_{e_{i}}$, and for $w$
to $a^{x}_{w}-\sum_{i=1}^{k}\alpha_{i}\ell_{e_{i}}\geq 0$.

We proceed with a small example of trading a single claim.

######  Example 2.1.

$v$$u$$y$$w$$0$$1$$2$Y1.0e0]pt$1$Y1.0e0]pt$1$

$v$$u$$y$$w$$2$$1$$0$$1$$2$$2$Y1.0e0]pt$2$

Figure 1: The network from Example 2.1 before the trade is depicted left, and
right after the trade. All liabilities equal 2. Edges are labeled with
positive payments (if any) in the clearing state.

Consider the example network depicted in Figure 1 (left) on a simple directed
graph. The liability of every edge is 2. The only banks with non-zero external
assets are $u$ and $w$, where $a^{x}_{u}=1$ and $a^{x}_{w}=2$. $a^{x}_{v}=0$
is also explicitly displayed for convenience. Banks $u,w$ and $y$ each have at
most one outgoing edge. They pay all their assets (if any) to the unique
outgoing edge until it is saturated. This implies payments of $1$ on edge
$(u,v)$. $v$ is the only bank with a non-trivial payment function – suppose it
uses an edge-ranking function with priority $\pi_{v}(1)=(v,w)$ and
$\pi_{v}(2)=(v,y)$. Then, $v$ pays the incoming assets of $1$ to $w$, and
there are no payments on the cycle of $v$ and $y$. To see this, assume
$p_{(y,v)}=x>0$. By the edge-ranking function, from these additional assets
$v$ allocates a portion of $\min(x,1)$ to $(v,w)$ and the rest to $(v,y)$.
Hence, the total assets of $y$ are $\max(x-1,0)$ while the outgoing payments
are $x$, which contradicts the feasibility constraint (3). Overall, in the
clearing state, the total assets are $a_{u}=a_{v}=1,a_{w}=3$ and $a_{y}=0$.

Suppose we perform the trade of edge $e=(u,v)$ to $w$ with $\alpha=1$, see
Fig. 1 (right) for the resulting network. $w$ buys edge $e$ and pays the full
liability $\ell_{e}$ to $v$. The external assets of $v$ increase to 2 and
allow $v$ to settle all debt. The total assets become $1$ for $u$, $2$ for
$y$, $3$ for $w$ and $4$ for $v$. The total assets of $u$ and $w$ are
unaffected by the trade, the total assets of $v$ and $y$ strictly increase.
Overall, the clearing state is point-wise non-decreasing.

A similar observation can be made when $v$ uses proportional payments. Before
the trade, $v$ pays 1 to $y$ and $w$. After the trade, both edges can be paid
fully. $\blacksquare$

Properties of Claims Trades.  In Example 2.1, $v$ strictly benefits from the
trade while $w$ is indifferent. Interestingly, it is impossible for both
creditor and buyer to strictly profit from a single trade. This property holds
true for the more general class of multi-trades of incoming edges, and it
applies in any network $\mathcal{F}$ with monotone payment functions.

The proof builds on a connection with _debt swaps_ studied in [18, 7]. A debt
swap exchanges the creditors of two edges with the same liabilities. We show
that a claims trade and the resulting payments can be represented by a debt
swap in an auxiliary network.

######  Definition 2.2 (Debt Swap).

Consider a financial network $\mathcal{F}$ with four distinct nodes
$u_{1},u_{2},v_{1},v_{2}\in V$ and edges $e_{1},e_{2}\in E$, where
$u_{1}=\text{de}(e_{1}),v_{1}=\text{cr}(e_{1})$ and
$u_{2}=\text{de}(e_{2}),v_{2}=\text{cr}(e_{2})$. Suppose the liabilities are
$\ell_{e_{1}}=\ell_{e_{2}}$. A debt swap $\sigma$ of $e_{1}$ and $e_{2}$
creates a new network $\mathcal{F}^{\sigma}$ with
$G^{\sigma}=(V,E,\text{de},\text{cr}^{\sigma})$ where
$\text{cr}^{\sigma}(e_{1})=v_{2}$, $\text{cr}^{\sigma}(e_{2})=v_{1}$ and
$\text{cr}^{\sigma}(e)=\text{cr}(e)$ for all $e\in
E\setminus\\{e_{1},e_{2}\\}$.

######  Proposition 2.3.

For every financial network with monotone payment functions, there exists no
multi-trade of incoming edges such that both creditor $v$ and buyer $w$
strictly improve their total assets.

######  Proof 2.4.

For a given network $\mathcal{F}$, consider a multi-trade of incoming edges
and construct a new network $\hat{\mathcal{F}}$ by adding an auxiliary bank
$\hat{v}$ to $\mathcal{F}$ without external assets. $\hat{v}$ serves as an
“accumulator” for the payments along the edges $e_{i}$. We change the targets
of the edges in $C$ to $\text{cr}(e_{i})=\hat{v}$. We add an edge $\hat{e}$
with $\text{de}(\hat{e})=\hat{v}$ and $\text{cr}(\hat{e})=v$ and liability
$\ell_{\hat{e}}=\sum_{i=1}^{k}\ell_{e_{i}}$. Every payment that gets paid to
$v$ via $e_{i}$ in $\mathcal{F}$ now first goes to $\hat{v}$, and then gets
forwarded from $\hat{v}$ to $v$, since $\hat{e}$ has sufficiently high
liability. Consider the clearing state $\hat{\mathbf{p}}$ in the resulting
network $\hat{\mathcal{F}}$. Obviously, for the new edge
$\hat{p}_{\hat{e}}=\sum_{i=1}^{k}\hat{p}_{e_{i}}$. As such, every (non-
auxiliary) bank from $\mathcal{F}$ receives the same external assets and
eventually the same incoming and outgoing payments in $\hat{\mathcal{F}}$.
Consequently, both $\mathcal{F}$ and $\hat{\mathcal{F}}$ give rise to the same
clearing state, i.e., $p_{e}=\hat{p}_{e}$, for all $e\in E$, and the same
assets for every (non-auxiliary) bank.

The new network $\hat{\mathcal{F}}$ allows to conveniently route all payments
along edges in $C$ to $w$ by trading the single accumulator edge $\hat{e}$ to
$w$. Thus, the multi-trade of incoming edges $C$ in $\mathcal{F}$ is
equivalent to trading the single claim $\hat{e}$ to $w$ in
$\hat{\mathcal{F}}$, for a suitably chosen haircut rate $\hat{\alpha}$ such
that
$\hat{\alpha}\cdot\sum_{i=1}^{k}\ell_{e_{i}}=\sum_{i=1}^{k}\alpha_{i}\cdot\ell_{e_{i}}$.

Now let us further adjust $\hat{\mathcal{F}}$ to $\tilde{\mathcal{F}}$ by
introducing an auxiliary bank $\tilde{w}$. Intuitively, we “outsource” parts
of external assets from $w$ to $\tilde{w}$. Formally, external assets of $w$
are reduced to $a^{x}_{w}-\sum_{i=1}^{k}\alpha_{i}\cdot\ell_{e_{i}}\geq 0$,
external assets of $\tilde{w}$ are
$\sum_{i=1}^{k}\alpha_{i}\cdot\ell_{e_{i}}$. We add an edge $\tilde{e}$ with
$\text{de}(\tilde{e})=\tilde{w}$ and $\text{cr}(\tilde{e})=w$ as well as
liabilities $\ell_{\tilde{e}}=\ell_{\hat{e}}=\sum_{i=1}^{k}\ell_{e_{i}}$. The
clearing state $\tilde{\mathbf{p}}$ in the resulting network
$\tilde{\mathcal{F}}$ is
$\tilde{p}_{\tilde{e}}=\sum_{i=1}^{k}\alpha_{i}\ell_{e_{i}}$, since
$\tilde{e}$ is the only outgoing edge of $\tilde{w}$ and $\ell_{\tilde{e}}\geq
a^{x}_{\tilde{w}}$. Hence, $w$ and (consequently) every non-auxiliary bank
from $\mathcal{F}$ receives the same total assets in $\tilde{\mathbf{p}}$.
Indeed, $\mathcal{F}$, $\hat{\mathcal{F}}$ and $\tilde{\mathcal{F}}$ yield
equivalent clearing states with $p_{e}=\hat{p}_{e}=\tilde{p}_{e}$, for all
$e\in E$.

In $\tilde{\mathcal{F}}$ we can implement the return payments from $w$ to $v$
by re-routing the “outsource” edge $e^{\prime}$ to $v$ instead of $w$. Thus,
the claim trade of $\hat{e}$ in $\hat{\mathcal{F}}$ can be expressed by a swap
of creditors of $\hat{e}$ and $\tilde{e}$ in $\tilde{\mathcal{F}}$. Now since
$\ell_{\tilde{e}}=\ell_{\hat{e}}$, this swap of creditors represents a debt
swap. Thus, the multi-trade in $\mathcal{F}$ is equivalent to single trade in
$\hat{\mathcal{F}}$ and a debt swap in $\tilde{\mathcal{F}}$. No debt swap can
strictly improve both creditor banks [7, Corollary 6]. Thus, no multi-trade of
incoming edges can strictly improve both creditor and buyer.

The above proof implies a structural equivalence. Using the network
$\hat{\mathcal{F}}$, we reduced a multi-trade of incoming edges to a single
claim trade.

######  Corollary 2.5.

For every multi-trade of incoming edges in a network $\mathcal{F}$, there is
an adjusted network $\hat{\mathcal{F}}$ such that the result of the multi-
trade in $\mathcal{F}$ is the result of a single trade in $\hat{\mathcal{F}}$.

Our motivation is to analyze claims trades to improve the situation of a
creditor in default by trading claims with a buyer. Since it is impossible to
strictly improve the conditions of both banks, we focus on strictly improving
the creditor and weakly improving the buyer. Note that the trade performed in
Example 2.1 satisfies this property.

######  Definition 2.6 (Creditor-positive trade).

A multi-edge trade of incoming edges of bank $v$ to bank $w$ is called
creditor-positive if $a^{\prime}_{v}>a_{v}$ and $a^{\prime}_{w}\geq a_{w}$.

For the proof of Proposition 2.3, we express the multi-trade by a debt swap in
an auxiliary network. For a creditor-positive trade, the associated debt swap
satisfies the same property, i.e., it is a so-called _semi-positive_ debt
swap. In any network $\mathcal{F}$ with monotone payment functions, a semi-
positive debt swap Pareto-improves the clearing state and, hence, the total
assets of _every_ bank [7]. This directly implies the next corollary.

######  Corollary 2.7.

In every financial network with monotone payments, every creditor-positive
trade Pareto-improves the clearing state.

A creditor-positive trade reduces the impact of a defaulting debtor on the
creditor. No bank in the entire network suffers. Hence, these trades
contribute to the stabilization of the entire financial network. We focus on
creditor-positive trades for the remainder of the paper.

##  3 Trading a Single Claim

In this section, we study a given single creditor-positive trade and optimize
the effects on the assets in the network. For exposition, we mostly focus on
financial networks with proportional or edge-ranking payments. There are two
natural problem variants depending on whether the haircut rate $\alpha$ is
fixed a priori or can be chosen as part of the trade.

The variant with fixed $\alpha\leavevmode\nobreak\ \in[0,1]$ is simple (see
Appendix B). Instead, suppose $\alpha$ (and, hence, return $\rho$) is chosen
as part of the trade. The choice of $\alpha$ affects the external assets of
$v$ and, thus, payments throughout the network. If a given trade is creditor-
positive for some $\alpha\in[0,1]$, we say that $\alpha$ is creditor-positive.
Can we efficiently decide the existence of a creditor-positive $\alpha$? What
is the _optimal_ $\alpha$ to maximize the improvement $a^{\prime}_{v}-a_{v}$
of $v$? Clearly, a trade with optimal $\alpha$ maximizes the total assets
$a^{\prime}_{v}$. Since $a^{\prime}_{w}=a_{w}$ in every creditor-positive
trade, maximizing $a^{\prime}_{v}$ also maximizes the payments of $v$, the
incoming payments of $v$’s creditors, and, inductively, the payments and
assets of every edge and bank in the network. A creditor-positive $\alpha$
that maximizes $a^{\prime}_{v}$ also simultaneously maximizes (1) the Pareto-
improvement of payments for each edge in the network, and (2) the return
$\rho$ by $w$. This holds for all networks with monotone payment functions.

To answer the above questions, we modify $\mathcal{F}$ into a _return network_
$\mathcal{F}^{\text{ret}}$ defined as follows. We switch edge $e$ to
$\text{cr}(e)=w$ and add a _return edge_ $e_{r}$ with $\text{de}(e_{r})=w$ and
$\text{cr}(e_{r})=v$. The payment on this edge models the return from $w$ to
$v$, so the liability is $\ell_{e_{r}}=\min\\{\ell_{e},a^{x}_{w}\\}$. Since we
consider creditor-positive trades, we modify the payment function of $w$ as
follows. For all $e^{\prime}\in E^{+}(w)\setminus\\{e_{r}\\}$, we set
$f^{\text{ret}}_{e^{\prime}}(x)=f_{e^{\prime}}(x)$ for all $x\leq a_{w}$ and
$f^{\text{ret}}_{e^{\prime}}(x)=f_{e^{\prime}}(a_{w})$ for all $x\geq a_{w}$.
For $e_{r}$ we set $f^{\text{ret}}_{e_{r}}(x)=0$ for all $x\leq a_{w}$ and
$f^{\text{ret}}_{e_{r}}(x)=x-a_{w}$ for all $x\geq a_{w}$. Similarly, we
modify the liabilities to $\ell_{e^{\prime}}=f_{e^{\prime}}(a_{w})$.
Intuitively, in $\mathcal{F}^{\text{ret}}$ $w$ maintains its payments up to a
total outgoing assets of $a_{w}$. It forwards any assets exceeding $a_{w}$ as
return via $e_{r}$ to $v$.

######  Lemma 3.1.

Consider the clearing state $\mathbf{p}^{\text{ret}}$ in
$\mathcal{F}^{\text{ret}}$.

  * (a)

Suppose there is an optimal creditor-positive $\alpha$ with return
$\rho=\alpha\ell_{e}$. Then $\mathcal{F}^{\text{ret}}$ has $a^{x}_{w}>p_{e}$.
In $\mathbf{p}^{\text{ret}}$ we obtain assets of
$a^{\text{ret}}_{w}\in(a_{w},a_{w}+\ell_{e_{r}}]$ and
$a^{\text{ret}}_{v}>a_{v}$, and $p^{\text{ret}}_{e_{r}}=\rho$.

  * (b)

If $a^{x}_{w}>p_{e}$ and $\mathbf{p}^{\text{ret}}$ yields assets of
$a^{\text{ret}}_{w}\in(a_{w},a_{w}+\ell_{e_{r}}]$ and
$a^{\text{ret}}_{v}>a_{v}$, then payment $p_{e_{r}}$ represents a return of an
optimal creditor-positive trade.

######  Proof 3.2.

We first show (a). Suppose there is an optimal creditor-positive $\alpha$. It
results in a return
$\rho=\alpha\ell_{e}\leq\min\\{\ell_{e},a^{x}_{w}\\}=\ell_{e_{r}}$, assets of
$a_{w}$ for $w$, and $a^{\prime}_{v}>a_{v}$ for $v$. When we assign payments
$\hat{p}_{e}=p^{\prime}_{e}$ for all $e^{\prime}\in E$ and set the payment on
$e_{r}$ to $\hat{p}_{e_{r}}=\rho$, we obtain a vector of payments
$\hat{\mathbf{p}}$ in $\mathcal{F}^{\text{ret}}$ that satisfies all fixed-
point conditions.

We first show that this implies $a^{x}_{w}>p_{e}$, the payment on $e$ in
$\mathbf{p}$ before the trade. Consider the assets of $w$. We have
$\hat{a}_{v}=a^{\prime}_{v}>a_{v}$. Recall $\mathbf{p}^{\prime}\geq\mathbf{p}$
by Corollary 2.7, so

$\displaystyle\hat{a}_{v}$ $\displaystyle=a_{v}^{x}+\rho+\sum_{e^{\prime}\in
E^{-}(v)\setminus\\{e\\}}\hat{p}_{e^{\prime}}=a^{x}_{v}+\rho+\sum_{e^{\prime}\in
E^{-}(v)\setminus\\{e\\}}p^{\prime}_{e^{\prime}}$ $\displaystyle\geq
a^{x}_{v}+\rho+\sum_{e^{\prime}\in
E^{-}(v)\setminus\\{e\\}}p_{e^{\prime}}=a_{v}+\rho-p_{e}$

Hence $a^{x}_{w}\geq\rho>p_{e}$, as desired.

For the other conditions, consider the clearing state
$\mathbf{p}^{\text{ret}}$ in $\mathcal{F}^{\text{ret}}$. Due to maximality of
the clearing state, $\mathbf{p}^{\text{ret}}\geq\hat{\mathbf{p}}$. Thus,
$a_{w}^{\text{ret}}>a_{w}$, $a^{\text{ret}}>a_{v}$ and
$p^{\text{ret}}_{e_{r}}\geq\rho$. We show that, indeed,
$\hat{\mathbf{p}}=\mathbf{p}^{\text{ret}}$, and that the condition
$a_{w}+\ell_{e_{r}}\geq\hat{a}_{w}$ is satisfied.

Case 1:

The clearing state satisfies $a_{w}+\ell_{e_{r}}\geq a^{\text{ret}}_{w}$. Then
we prove below that $\mathbf{p}^{\text{ret}}$ is equivalent to a creditor-
positive trade with payments that Pareto-dominate $\hat{\mathbf{p}}$ and,
consequently, higher assets for $v$ with $\hat{a}_{v}\geq a^{\text{ret}}_{v}$.
As such, $\mathbf{p}^{\text{ret}}$ represents a better creditor-positive
trade, a contradiction to $\hat{\mathbf{p}}$ stemming from an optimal one.

Case 2:

The clearing state satisfies $a_{w}+\ell_{e_{r}}<a^{\text{ret}}_{w}$. Then
$a^{\text{ret}}_{v}>a_{v}$, and $w$ is solvent in $\mathcal{F}^{\text{ret}}$.
Indeed, $w$ could transfer even more assets to the edges of
$E^{+}(w)\setminus\\{e_{r}\\}$. This implies that with return $\ell_{e_{r}}$,
there is a clearing state in $\mathcal{F}^{\prime}$ that can _strictly improve
both_ $v$ and $w$. This is a contradiction to Corollary 2.3.

To prove (b), suppose $\mathbf{p}^{\text{ret}}$ fulfills the conditions. Then,
clearly, the payment $p^{\text{ret}}_{e_{r}}$ represents a feasible return.
The payments $p^{\text{ret}}_{e^{\prime}}$ on the other edges $e^{\prime}\in
E\setminus\\{e_{r}\\}$ fulfill the fixed-point conditions in
$\mathcal{F}^{\prime}$. Now for contradiction assume that
$p^{\prime}_{e^{\prime}}>p^{\text{ret}}_{e^{\prime}}$ for some $e^{\prime}$.
Then $e^{\prime}\neq e_{r}$, since we assume $p^{\text{ret}}_{e_{r}}$ is the
return used to construct $\mathcal{F}^{\prime}$. Hence, any strict increase in
$\mathbf{p}^{\prime}$ could be manifested in $\mathbf{p}^{\text{ret}}$ as
well, which contradicts the maximality of $\mathbf{p}^{\text{ret}}$ in
$\mathcal{F}^{\text{ret}}$.

######  Corollary 3.3.

Consider a given single claims trade of $e$ to $w$.

  1. (a)

A return of $a^{x}_{w}\geq\rho>p_{e}$ is necessary to make the trade creditor-
positive. For $\rho=p_{e}$, we obtain $\mathbf{p}^{\prime}=\mathbf{p}$.

  2. (b)

Consider all creditor-positive $\alpha$. A value $\alpha$ with return
$\rho=\alpha\ell_{e}$ maximizes the assets of $v$ if and only if it maximizes
the payment on every single edge in $\mathcal{F}^{\prime}$, the assets of
every single bank, as well as the value of $\rho$ and $\alpha$.

######  Proposition 3.4.

For a given financial network with edge-ranking payments and a single claims
trade, there is an efficient algorithm to compute an optimal creditor-positive
$\alpha^{*}\in[0,1]$ or decide that none exists.

######  Proof 3.5.

We construct network $\mathcal{F}^{\text{ret}}$ as described above. Observe
that the adjusted payment function $\mathbf{f}^{\text{ret}}_{w}$ is again an
edge-ranking function – it first fills edges according to $\mathbf{f}_{w}$
until assets $a_{w}$ are paid. Thus, at most one edge $e^{\prime}\in E^{+}(w)$
is paid partially. For this edge, the liabilities are reduced to
$f_{e^{\prime}}(a_{w})$. For all other edges, the liabilities either remain
untouched or are decreased to 0. Then the additional assets are directed to
$e_{r}$. Thus, $\mathbf{f}^{\text{ret}}_{w}$ can be represented by the same
ranking as $\mathbf{f}_{w}$ up to (and including) edge $e^{\prime}$, and then
using $e_{r}$ as the next (and last) edge in the order. Hence, we can compute
$\mathcal{F}^{\text{ret}}$ in strongly polynomial time. By checking the
conditions of Lemma 3.1, we can verify in polynomial time whether or not a
creditor-positive trade exists and obtain the optimal return as the payment on
$e_{r}$.

######  Proposition 3.6.

For a given financial network with proportional payments and a single claims
trade, there is an efficient algorithm to compute an optimal creditor-positive
$\alpha^{*}\in[0,1]$ or decide that none exists.

Finally, our main result in this section shows that for general monotone
payments with efficient clearing oracle, we can obtain an approximately
optimal solution via binary search.

######  Theorem 3.7.

Consider a given financial network with monotone payment functions and
efficient clearing oracle. For a given single claims trade, there exists an
additive FPTAS for approximating the optimal improvement of $v$ from any
creditor-positive $\alpha$.

Our algorithm uses binary search. Towards this end, we first show, for a given
target value $A\geq a_{v}$, how to verify the existence of a trade that
achieves at least a value $A$ for the total assets of $v$. For intuition, we
use a _split network_ $\mathcal{F}^{\text{sp}}$ obtained from
$\mathcal{F}^{\prime}$ after the trade as follows: We replace $v$ and $w$ by
source and sink banks $v_{in},v_{out}$, and $w_{in},w_{out}$. $v_{in}$ has the
incoming edges of $v$, $w_{in}$ the ones of $w$ (including $e$). The outgoing
edges of $v$ ($w$) are attached to $v_{out}$ ($w_{out}$). We set the external
assets of $v_{out}$ and $w_{out}$ to $A$ and $a_{w}$, and these banks use the
payment functions of $v$ and $w$, respectively. As such, the clearing state
$\mathbf{p}^{\text{sp}}$ in $\mathcal{F}^{\text{sp}}$ can be computed using
the clearing oracle.

Consider the incoming payments of $\mathbf{p}^{\text{sp}}$ at $v_{in}$ and
$w_{in}$. These payments shall exactly recover the expenses at $v_{out}$ and
$w_{out}$ – modulo external assets and the return payment from $w$ to $v$. We
define the _budget difference_ by

$d^{\text{sp}}_{w}=\left(a^{x}_{w}+\sum_{e^{\prime}\in
E^{-}(w_{in})}p^{\text{sp}}_{e^{\prime}}\right)-a_{w}\qquad\text{and}\qquad
d^{\text{sp}}_{v}=A-\left(a^{x}_{v}+\sum_{e^{\prime}\in
E^{-}(v_{in})}p^{\text{sp}}_{e^{\prime}}\right)\;.$

$d^{\text{sp}}_{w}$ is the surplus money earned by $w_{in}$ that shall be
invested into the return, $d^{\text{sp}}_{v}$ is the excess money spent by
$v_{out}$ that must be recovered through the return.

######  Lemma 3.8.

For a given single claims trade and a given target value $A>a_{v}$, there is a
creditor-positive trade with a value at least $A$ for $v$ if and only if
$d^{\text{sp}}_{v}=d^{\text{sp}}_{w}>0$.

######  Proof 3.9.

We first show that if $d^{\text{sp}}_{v}=d^{\text{sp}}_{w}>0$, then there
exists a creditor-positive trade with asset at least $A$ for $v$. Suppose we
consider $\mathbf{p}^{\text{sp}}$ in the network $\mathcal{F}^{\prime}$ using
return $\rho=d^{\text{sp}}_{v}=d^{\text{sp}}_{w}$. This exactly equilibrates
the budgets of $v$ and $w$ – $v$ receives $d^{\text{sp}}_{v}$, the money
needed to obtain total assets of $A$. Also, $w$ spends exactly
$d^{\text{sp}}_{w}$, the money needed to obtain total assets of $a_{w}$.
Hence, $\mathbf{p}^{\text{sp}}$ satisfies all fixed-point conditions in
$\mathcal{F}^{\prime}$. As such,
$\mathbf{p}^{\prime}\geq\mathbf{p}^{\text{sp}}$ coordinate-wise due to
maximality of the clearing state. This implies that using return $\rho$, the
clearing state $\mathbf{p}^{\prime}$ yields $a_{v}^{\prime}\geq A>a_{v}$ and
$a^{\prime}_{w}\geq a_{w}$. A creditor-positive trade with return $\rho$
exists.

Now for the other direction, consider an optimal creditor-positive trade,
which yields the highest asset level $A^{*}$ and consider any
$A\in(a_{v},A^{*}]$. We show that in this case
$d^{\text{sp}}_{v}=d^{\text{sp}}_{w}>0$ holds in the clearing state
$\mathbf{p}^{\text{sp}}$ of $\mathcal{F}^{\text{sp}}$ with external assets $A$
for $v_{out}$.

Consider the optimal trade, its return $\rho^{*}>0$ and the emerging payments
$\mathbf{p}^{*}$ in $\mathcal{F}^{\prime}$ after this trade. Now in the
corresponding split network $\mathcal{F}^{*,\text{sp}}$ with external assets
of $A^{*}$ for $v_{out}$, the payments $\mathbf{p}^{*}$ yield
$d^{*}_{v}=d^{*}_{w}=\rho^{*}$, by definition of $\mathbf{p}^{*}$. The
previous paragraph and maximality of $A^{*}$ then imply that $\mathbf{p}^{*}$
must also be the clearing state $\mathbf{p}^{*,\text{sp}}=\mathbf{p}^{*}$ of
$\mathcal{F}^{*,\text{sp}}$.

Now suppose in $\mathcal{F}^{*,\text{sp}}$ we reduce the external assets of
$v_{out}$ by $\varepsilon=A^{*}-A>0$. Then $\mathcal{F}^{\text{sp}}$ evolves.
Since we reduce the assets of a single source $v_{out}$ by $\varepsilon$, we
obtain $\mathbf{p}^{*,\text{sp}}\geq\mathbf{p}^{\text{sp}}$. Moreover, by non-
expansivity [7, Lemma 33], the total incoming assets of all sinks must reduce
by _at most_ $\varepsilon$. For the sinks $v_{in}$ and $w_{in}$ we set

$\varepsilon_{v}=a^{*,\text{sp}}_{v_{in}}-a^{\text{sp}}_{v_{in}}=\sum_{e^{\prime}\in
E^{-}(v_{in})}p^{*}_{e^{\prime}}-p^{\text{sp}}_{e^{\prime}}\hskip
42.67912pt\varepsilon_{w}=a^{*,\text{sp}}_{w_{in}}-a^{\text{sp}}_{w_{in}}=\sum_{e^{\prime}\in
E^{-}(w_{in})}p^{*}_{e^{\prime}}-p^{\text{sp}}_{e^{\prime}}$

and, thus, $d_{v}^{\text{sp}}=d^{*}_{v}-(\varepsilon-\varepsilon_{v})$ and
$d_{w}^{\text{sp}}=d^{*}_{w}-\varepsilon_{w}$. Non-expansivity implies
$\varepsilon_{v}+\varepsilon_{w}\leq\varepsilon$.

First, we observe that $\varepsilon_{v}+\varepsilon_{w}<\varepsilon$ is
impossible. Then $\varepsilon_{w}<\varepsilon-\varepsilon_{v}$, so
$d_{w}^{\text{sp}}>d_{v}^{\text{sp}}$, i.e., $w$ has more excess money in
$\mathbf{p}^{\text{sp}}$ than required by $v$. Consider a return of
$\rho=d_{v}^{\text{sp}}$ and $\mathbf{p}^{\text{sp}}$ as payment vector in the
resulting network $\mathcal{F}^{\prime}$. Then all banks are feasible w.r.t.
the fixed-point conditions, except for $w$ which has strictly more income than
outgoing assets. Hence, the clearing state satisfies
$\mathbf{p}^{\prime}\geq\mathbf{p}^{\text{sp}}$, $a^{\prime}_{v}\geq A>a_{v}$,
and $a^{\prime}_{w}>a_{w}$, a contradiction to Proposition 2.3.

Second, suppose that $\varepsilon_{v}+\varepsilon_{w}=\varepsilon$, then
$d_{v}^{\text{sp}}=d_{w}^{\text{sp}}$. Then the clearing state
$\mathbf{p}^{\text{sp}}$ exactly fulfills the fixed-point conditions for all
banks in $\mathcal{F}^{\prime}$ and yields assets $A>a_{v}$ for $v$ and
$a_{w}$ for $w$ with $\rho=d_{v}^{\text{sp}}$. Note that $\rho>0$, since
otherwise we contradict the maximality of the initial clearing state
$\mathbf{p}$. Therefore, the existence of a creditor-positive trade with
assets $A^{*}>A$ for $v$ implies that $d_{v}^{\text{sp}}=d_{w}^{\text{sp}}>0$
for $\mathbf{p}^{\text{sp}}$ in $\mathcal{F}^{\text{sp}}$ emerging from $A$.

We are now ready to prove Theorem 3.7.

######  Proof 3.10 (Proof of Theorem 3.7).

Our algorithm works by testing different target values $A$ for the total
assets of $v$. For a given target value $A$, we then use Lemma 3.8 to verify
existence of a return $\rho$ achieving at least assets $A$ for $v$. The
maximum achievable assets for $v$ are $M_{v}=\sum_{e^{\prime}\in
E^{-}(v)\setminus e}\ell_{e^{\prime}}+a^{x}_{v}+\min\\{a^{x}_{w},\ell_{e}\\}$.
We determine the maximal achievable $A$ using binary search on the interval
$(a_{v},M_{v}]$.

More formally, we choose $\delta>0$ and apply binary search over the set
$\\{a_{v}+\delta,a_{v}+2\delta,\dots,M_{v}\\}$. Verifying the condition in
Lemma 3.8 can be done in polynomial time via a call to the clearing oracle in
$\mathcal{F}^{\text{sp}}$. If the algorithm discovers that the condition does
not hold for all tested values, then no creditor-positive trade with asset
level at least $a_{v}+\delta$ for $v$ exists. Otherwise, let $\hat{A}$ be
largest discovered value for which the test is positive. Then, any value of at
least $\hat{A}+\varepsilon$ cannot be achieved for any return $\rho$. Hence,
the optimal achievable total assets of $v$ in any creditor-positive trade are
bounded by $A^{*}\in[\hat{A},\hat{A}+\delta]$, and the additive approximation
follows $\hat{A}-a_{v}\geq(A^{*}-a_{v})-\delta$.

For the running time, we require at most
$\lceil\log_{2}(1+(M_{v}-a_{v})/\delta)\rceil$ oracle calls, which is
polynomial in the input size and $1/\delta$.

Since the number of possible (single) claims trades in a network is limited by
$|E|\cdot|V|$, we can use the algorithm above to compute every creditor-
positive trade with an (approximately) optimized haircut rate for a given
network in polynomial time.

##  4 Multi-Trades of Incoming Edges

###  4.1 Fixed Set of Claims

In this section, we are interested in multi-trades of incoming edges of a
creditor bank $v$ to a buyer bank $w$. This arises naturally, for example,
when a high fraction of $v$’s debtors are in default or $v$ is “too big to
fail”. Then bankruptcy of $v$ would cause significant damage to the entire
network.

We are given a financial network $\mathcal{F}$ with two distinct banks $v$ and
$w$, and a set $C$ of $k$ incoming edges of $v$. Suppose the haircut rates
$\alpha_{i}$ can be chosen individually for each $e_{i}\in C$ as part of the
trade (for fixed rates, see Appendix B). We call a vector
$\bm{\alpha}=(\alpha_{1},\dots,\alpha_{k})$ of haircut rates _creditor-
positive_ if the resulting multi-trade is creditor-positive. Our goal is to
select creditor-positive $\alpha_{i}\in[0,1]$, for every $i\in[k]$, in order
to maximize the improvement of $v$, i.e.,
$a^{\prime}_{v}-a_{v}=\sum_{i=1}^{k}\alpha_{i}\cdot\ell_{e_{i}}+\sum_{e^{\prime}\in
E^{\prime-}(v)}p^{\prime}_{e^{\prime}}-\sum_{e^{\prime}\in
E^{-}(v)}p_{e^{\prime}}$. Observe that we can restrict our attention to
vectors with uniform $\alpha_{i}=\alpha^{\prime}$ for all $i\in[k]$ and some
$\alpha^{\prime}\in[0,1]$ – given any $\bm{\alpha}$, choose
$\bm{\alpha}^{\prime}$ with $\alpha^{\prime}_{i}=\alpha^{\prime}$ such that
$\alpha^{\prime}\cdot\sum_{i=1}^{k}\ell_{e_{i}}=\sum_{i=1}^{k}\alpha^{\prime}_{i}\cdot\ell_{e_{i}}$.
This results in $\alpha^{\prime}\in[0,1]$, the same return, and the same
assets of $v$ as for $\bm{\alpha}$.

Our result is a reduction to single trades.

######  Proposition 4.1.

Consider a financial network with monotone payment functions and efficient
clearing oracle. For a given multi-trade of incoming edges, there is an
additive FPTAS for approximating the optimal improvement of $v$ from any
creditor-positive $\bm{\alpha}$.

######  Proof 4.2.

Consider a financial network $\mathcal{F}$ with banks $v$ and $w$ and edges
$C$, where $|C|=k$. By Corollary 2.5, the multi-trade in $\mathcal{F}$ can be
modeled by a single claims trade with edge $\hat{e}$ in adjusted network
$\hat{\mathcal{F}}$. Invoke the FPTAS to compute a haircut rate $\alpha$ for
the single claim in $\hat{\mathcal{F}}$. This results in assets of
$\alpha\cdot\sum_{i=1}^{k}\ell_{e_{i}}+\sum_{e\in
E^{\prime-}(v)}p^{\prime}_{e}$ for $v$ in $\hat{\mathcal{F}}$. Clearly, the
same value is obtained with the multi-trade when all haircut rates are set to
$\alpha$, i.e., $\alpha_{i}=\alpha\;\forall i\in[k]$. Clearly, this choice of
haircut rates also yields an (approximately) optimal solution for the multi-
trade.

Combining the insight with Propositions 3.6 and 3.4, we obtain the following
corollary.

######  Corollary 4.3.

Consider a financial network with proportional or edge-ranking payments. For a
given multi-trade of incoming edges, there are efficient algorithms to compute
an optimal creditor-positive $\bm{\alpha}^{*}$ or decide that none exists.

###  4.2 Choosing Subsets of Claims

For a fixed pair of creditor $v$ and buyer $w$, the incoming edges of $v$
yield an exponential number of different edge sets $C$ that might be used for
a multi-trade. Thus, a creditor-positive multi-trade _cannot_ be derived
trivially by checking feasibility for all sets $C$. For improving the assets
of $v$ by a multi-trade with buyer $w$, the selection of claims to be traded
is critical. How can we compute a (near-)optimal set of incoming edges
$C\subseteq(E^{-}(v)\setminus E^{+}(w))$ for a creditor-positive multi-trade
with $w$ such that we maximize the improvement of $v$?

Again, we study the problem when the haircut rates are chosen as part of the
trade (see Appendix B for the problem when haircut rates are fixed in
advance). The challenge is to find a set of claims $C$ with creditor $v$ and
appropriate individual haircut rates $\alpha_{i}$, for $e_{i}\in C$. The
resulting multi-trade shall be creditor-positive and yield the maximal
improvement for $v$ (over all creditor-positive multi-trades of incoming edges
of $v$).

We show that this problem is NP-hard, for every set of monotone payment
functions. Formally, we show it is NP-hard to decide whether creditor $v$ can
be _saved_ by a creditor-positive multi-trade of incoming edges, i.e., whether
total assets of $L_{v}$ can be achieved. We call this problem IncomingSave-VR
(for variable haircut rates).

In the class of networks we construct for the reduction, every bank has at
most one outgoing edge. Hence, all payments will be independent of the payment
function that is used. Moreover, once a set of claims $C$ is chosen, finding
optimal haircut rates for the multi-trade of $C$ to $w$ is trivial in this
class of networks. Hardness arises from the choice of $C$.

######  Theorem 4.4.

IncomingSave-VR is weakly NP-hard.

####  4.2.1 Approximate Claims Trades

Contrasting NP-hardness, we show that the problem to compute a multi-trade
improving $v$ by a given amount can be solved efficiently when slightly
relaxing the liability condition.

######  Definition 4.5 ($\varepsilon$-Approximate Multi-Trade).

A multi-trade $C$ with creditor $v$, buyer $w$, return $\rho>0$ and haircut
rates $\alpha_{i}\in[0,1+\varepsilon]$, for all $e_{i}\in C$, is called
$\varepsilon$-approximate if $\rho\leq(1+\varepsilon)\cdot\sum_{e_{i}\in
C}\ell_{e_{i}}$.

Consider a _creditor-positive $\varepsilon$-approximate_ trade. Such a trade
(1) strictly increases the assets of $v$ and exactly maintains the ones of
$w$, (2) is affordable by $w$, i.e., $\rho=\sum_{e_{i}\in
C}\alpha_{i}\ell_{e_{i}}\leq a_{w}^{x}$, and (3) satisfies exact fixed-point
conditions in the emerging clearing state. It is approximate only in the
liability condition of the trade.

We construct a bicriteria FPTAS to compute a creditor-positive multi-trade of
incoming edges. Suppose $\varepsilon,\delta>0$ such that $1/\varepsilon$ is
polynomial and $1/\delta$ is exponential in the representation size of
$\mathcal{F}$. Our FPTAS guarantees that the computed trade is
$\varepsilon$-approximate and yields assets of at least $A^{*}-\delta$ for
$v$, where $A^{*}$ are the assets of $v$ resulting from an _optimal exact_
creditor-positive trade. The FPTAS uses a connection to the Knapsack problem.

We proceed in several steps: First, we consider computing an (exact) trade
that achieves a target asset value $A$ for the creditor. For this problem, we
derive Knapsack-style constraints capturing a set of three necessary and
sufficient conditions of a valid creditor-positive trade. We then adapt the
dynamic program for Knapsack to construct an FPTAS to compute an
$\varepsilon$-approximate multi-trade with assets value at least $A$ for $v$
in polynomial time. Finally, we show how to use binary search to find a trade
with asset level at least $A^{*}-\delta$.

Necessary and Sufficient Conditions.  As a first step, we consider exact
trades that achieve assets of at least $A$ for $v$. Suppose there is such a
trade with a set $C$ of traded edges, and let $k=|C|$. Consider
$\mathcal{F}^{\prime}$ after trade $C$ has occurred with a suitably chosen
return. Since $C$ is fixed, by Corollary 2.5 we can express the outcome of the
trade using a single claims trade. Now apply the split network
$\mathcal{F}^{\text{sp}}$ and Lemma 3.8. Hence, using

$d_{v}^{\text{sp}}=A-\left(a^{x}_{v}+\sum_{e^{\prime}\in(E^{-}(v)\setminus
C)}p^{\prime}_{e^{\prime}}\right)\quad\text{ and }\quad
d_{w}^{\text{sp}}=\left(a^{x}_{w}+\sum_{e^{\prime}\in(E^{-}(w)\cup
C)}p^{\prime}_{e^{\prime}}\right)-a_{w}\enspace,$

a creditor-positive trade with set $C$ and asset value at least $A$ exists if
and only if $d_{v}^{\text{sp}}=d_{w}^{\text{sp}}>0$. This implies that

$(A-a_{v}^{x})+(a_{w}-a_{w}^{x})=\sum_{e\in E^{-}(v)\cup
E^{-}(w)}p^{\prime}_{e}$ (1)

must hold. This condition is _independent_ of the set $C$ of traded edges. As
such (1) is a necessary condition that any creditor-positive trade with asset
level at least $A$ for $v$ can exist.

With return $\rho=d_{v}^{\text{sp}}$ for the given set $C$, we satisfy the
fixed-point conditions in $\mathcal{F}^{\prime}$. By Lemma 3.8 the optimal
trade using the given set $C$ only yields a larger return, i.e., $\rho\geq
d_{v}^{\text{sp}}>0$. Moreover, the liabilities of the traded edges must be
high enough to allow the return $\rho$, i.e., $\sum_{e_{i}\in
C}\ell_{e_{i}}\geq\rho$. Using $P^{\prime}=\sum_{e\in E^{-}(v)}p^{\prime}_{e}$
this necessary condition is expressed by

$\sum_{e\in C}\ell_{e}\geq d_{v}^{\text{sp}}=A-a_{v}^{x}-P^{\prime}+\sum_{e\in
C}p^{\prime}_{e}\quad\Longleftrightarrow\quad\sum_{e\in
C}(\ell_{e}-p^{\prime}_{e})\geq A-a^{x}_{v}-P^{\prime}\;.$ (2)

$w$ must be able to pay the required return. Since the return is solely funded
by external assets, we obtain the necessary condition

$a^{x}_{w}\geq\rho=d_{v}^{\text{sp}}\quad\Longleftrightarrow\quad\sum_{e\in
C}p^{\prime}_{e}\leq a^{x}_{w}-A+a_{v}^{x}+P^{\prime}\;.$ (3)

While each condition (1)-(3) is necessary, it is easy to see that in
combination they are sufficient. Indeed, if they hold, then there is a
creditor-positive trade of set $C$ with return $\rho\geq
d_{v}^{\text{sp}}=d_{w}^{\text{sp}}>0$ that respects the exact liabilities of
traded edges, is affordable by $w$, and achieves asset level at least $A$ for
$v$. We summarize the argument in the following lemma:

######  Lemma 4.6.

For a given set $C$ of incoming edges of $v$, the following are equivalent:

  1. 1.

There is a multi-trade of $C$ to $w$ that achieves an asset level at least $A$
for $v$.

  2. 2.

Equation (1) holds, and the set $C$ satisfies (2) and (3).

Knapsack-Style FPTAS.  While condition (1) can be checked directly after
computing the clearing state $\mathbf{p}^{\prime}$, determining the existence
of a set $C$ that satisfies conditions (2) and (3) can be cast as a Knapsack
decision problem: For each edge $e\in E^{-}(v)$ the payments $p^{\prime}_{e}$
are the non-negative _weight_ of $e$, and the residual
$\ell_{e}-p^{\prime}_{e}$ is the non-negative _value_ of $e$. Decide the
existence of a subset of edges with total value lower bounded by (2) and total
weight upper bounded by (3).

We next adapt the standard FPTAS for Knapsack to compute an _approximate_
multi-trade. We _round up_ the residual $\ell_{e}-p^{\prime}_{e}$ of every
edge to the next multiple of a parameter $s$. This can be interpreted as
increasing the liabilities $\ell_{e}$ by a small amount. We then determine if
(2) and (3) allow a feasible solution by using the standard dynamic program
for Knapsack in polynomial time. We term this procedure the Level-FPTAS.

######  Lemma 4.7 (Level-FPTAS).

For a given number $A$, suppose there exists a creditor-positive multi-trade
of incoming edges that yields assets at least $A$ for $v$. Then, for every
$\varepsilon>0$, there is an algorithm to compute an $\varepsilon$-approximate
creditor-positive trade with assets at least $A$ for $v$ in time polynomial in
the size of $\mathcal{F}$ and $1/\varepsilon$.

######  Proof 4.8.

First, check feasibility of condition (1) since otherwise the desired trade
does not exist. Then, consider all incoming edges $e\in E^{-}(v)$ of $v$ and
define $m=|E^{-}(v)|$. We denote by $r_{e}=\ell_{e}-p^{\prime}_{e}$ the
residual of $e$. Let $r_{max}$ be the maximal residual capacity with respect
to $\mathbf{p}^{\prime}$ of any edge that satisfies the weight constraint,
i.e., $r_{max}=\max\\{r_{e}\mid e\in E^{-}(v),p^{\prime}_{e}\leq
a_{w}^{x}-A+a_{v}^{x}+P^{\prime}\\}$. Round the residual capacities _up_ using
a scaling factor $s=\frac{\varepsilon\cdot r_{max}}{m}$. Then determine the
optimal solution $C^{*}$ for the rounded values
$\tilde{r}_{e}=s\cdot\lceil(r_{e})/s\rceil$ via the standard dynamic program
for Knapsack. The running time is bounded by $O(m^{3}/\varepsilon)$.

Using a return of $\rho=A-\left(a_{v}^{x}+\sum_{e\in E^{-}(v)\setminus
C^{*}}p^{\prime}_{e}\right)$ the trade of $C^{*}$ yields a clearing state in
$\mathcal{F}^{\prime}$ with assets at least $A$ for $v$. By definition,
$C^{*}$ satisfies (3), and since the instance satisfies (1), $\rho\leq
a^{x}_{w}$ is also guaranteed.

Regarding the liabilities, note that

$\sum_{e\in C^{*}}\tilde{r}_{e}\;\leq\;\sum_{e\in
C^{*}}r_{e}+s\;\leq\;\varepsilon r_{max}+\sum_{e\in
C^{*}}r_{e}\;\leq\;(1+\varepsilon)\sum_{e\in C^{*}}r_{e}\;\leq\;\sum_{e\in
C^{*}}\ell_{e}(1+\varepsilon)-p^{\prime}_{e}\enspace.$

There exists an exact trade $C$ with assets at least $A$ for $v$, so the trade
with $C$ satisfies (2) and (3). As such,

$\sum_{e\in C^{*}}\tilde{r}_{e}\quad\geq\quad\sum_{e\in
C}\tilde{r}_{e}\quad\geq\quad\sum_{e\in C}r_{e}\quad\geq\quad
A-a_{v}^{x}-P^{\prime}\enspace,$

so the optimal solution $C^{*}$ satisfies (2) using the rounded residuals.
Hence,

$\displaystyle\rho\quad$ $\displaystyle=\quad A-\left(a_{v}^{x}+\sum_{e\in
E^{-}(v)\setminus C^{*}}p^{\prime}_{e}\right)\quad=\quad
A-a_{v}^{x}-P^{\prime}+\sum_{e\in C^{*}}p^{\prime}_{e}\quad\leq\quad\sum_{e\in
C^{*}}\tilde{r}_{e}+p^{\prime}_{e}$
$\displaystyle\leq\quad(1+\varepsilon)\sum_{e\in C^{*}}\ell_{e}\enspace,$

so the return generated by $C^{*}$ violates the liability condition by at most
a factor of $1+\varepsilon$.

The lemma gives rise to an efficient algorithm computing an
$\varepsilon$-approximate multi-trade with assets at least $A$, whenever an
exact trade with assets at least $A$ exists. Similar to Theorem 3.7, we use
this test to construct a bicriteria FPTAS.

Bicriteria-FPTAS.  As our main result for multi-trades of incoming edges, we
obtain a bicriteria FPTAS. Suppose assets $A^{*}$ for $v$ are achievable by an
exact creditor-positive multi-trade of incoming edges. We will compute an
$\varepsilon$-approximate one resulting in assets at least $A^{*}-\delta$ for
$v$, for any $\varepsilon,\delta>0$. We say such a trade is _$\delta$
-optimal_.

######  Theorem 4.9.

Consider a financial network with monotone payment functions and efficient
clearing oracle, creditor $v$ and buyer $w$. If there exists a creditor-
positive multi-trade of incoming edges, then an $\varepsilon$-approximate
$\delta$-optimal trade can be computed in time polynomial in the size of
$\mathcal{F}$, $1/\varepsilon$ and $\log 1/\delta$, for every
$\varepsilon,\delta>0$,

######  Proof 4.10.

We use the binary search idea put forward in Theorem 3.7. We choose $\delta>0$
and apply binary search over the set
$\\{a_{v}+\delta,a_{v}+2\delta,\dots,M_{v}\\}$ of potential asset values for
$v$. Recall that $M_{v}$ is an upper bound for maximal achievable assets of
$v$. For multi-trades, $M_{v}$ is upper bounded by
$a^{x}_{v}+a^{x}_{w}+\sum_{e\in E^{-}(v)}\ell_{e}$. The goal is to find an
asset value that is as large as possible.

Running the Level-FPTAS with any value from the interval
$A^{\prime}\in(a_{v},A^{*}]$, we are guaranteed to receive an approximate
multi-trade with asset level at least $A^{\prime}$ for $v$ in polynomial time.
As such, the binary search will never terminate with a value of
$A^{\prime}\leq A^{*}-\delta$. The search terminates in at most
$\lceil\log_{2}(1+(M_{v}-a_{v})/\delta)\rceil$ steps.

When called with an asset level $A^{\prime}>A^{*}$, the Level-FPTAS might or
might not return a corresponding multi-trade – rounding up the residuals can
introduce non-monotone behavior. As such, using binary search our algorithm
does not necessarily return an optimal asset value of $v$ for any creditor-
positive $\varepsilon$-approximate multi-trade. However, since the Level-FPTAS
never fails to return a multi-trade for any asset level $A^{\prime}\leq
A^{*}$, we are guaranteed that assets of more than $A^{*}-\delta$ for $v$ are
achieved.

Ranking Payments.  For edge-ranking payments, the set of meaningful values to
be tested for $A^{*}$ in the binary search can be restricted to a grid of at
most exponential precision in the input size. This allows to compute an
$\varepsilon$-approximate multi-trade with assets at least $A^{*}$, i.e., such
a trade is $\delta$-optimal with $\delta=0$.

######  Corollary 4.11.

Consider a financial network with edge-ranking functions, creditor $v$ and
buyer $w$. If there exists a creditor-positive multi-trade of incoming edges,
then an $\varepsilon$-approximate 0-optimal trade can be computed in time
polynomial in the size of $\mathcal{F}$ and $1/\varepsilon$.

######  Proof 4.12.

Consider an optimal exact multi-trade $C$ with return $\rho$ that achieves
optimal assets of $A^{*}$ for $v$. Recall that all liabilities and external
assets are integers, and so is $M_{v}$. If $A^{*}$ is integral, then we can
run the binary search with $\delta=1$ and obtain an approximate trade with
assets of (more than $A^{*}-1$ and, thus) at least $A^{*}$ for $v$.

To show that $A^{*}$ is integral, consider an optimal creditor-positive trade
$C$ achieving assets $A^{*}$. We resort to the equivalent representation as a
single claims trade (Corollary 2.5). For this single trade, consider the
return network $\mathcal{F}^{\text{ret}}$. An optimal return $\rho$ for a
trade of edge set $C$ evolves as the payment $p_{e_{r}}^{\text{ret}}$ on
$e_{r}$ in the clearing state $\mathbf{p}^{\text{ret}}$. Recall that the
payment function of $w$ in the return network is also an edge-ranking function
(c.f. Proposition 3.4). For edge-ranking payments, if all liabilities and
external assets are integers, then the clearing state has integral payments
[1]. The assets of every bank in $\mathbf{p}^{\text{ret}}$ (and $A^{*}$) are
integral.

##  5 Multi-Trades of Outgoing Edges

In this section, we study multi-trades of _outgoing_ edges of a bankrupt bank
$u$. We strive to improve the assets of $u$’s creditors directly (and not
indirectly via $u$ through trades of incoming edges). It might not be feasible
to save a particular bank $u$, e.g., when its debt is too high in relation to
the claims. In such cases, we attempt to minimize the _contagion_ of
bankruptcy from $u$ to her creditors by conducting multi-trades of outgoing
edges of $u$. We execute multi-trades that _maximize_ the total profit of all
creditors, not just those involved in the trade. No creditor nor buyer $w$
should be harmed by the trade.

######  Definition 5.1 (Pareto-positive trade).

Let $v_{1},v_{2},\dots,v_{l}$ be $u$’s creditors. A multi-trade of outgoing
edges of $u$ to $w$ is called Pareto-positive, if
$a^{\prime}_{v_{i}}>a_{v_{i}}$ for at least one creditor $v_{i}$,
$a^{\prime}_{v_{i}}\geq a_{v_{i}}$ for all creditors and $a^{\prime}_{w}\geq
a_{w}$.

Suppose we are given a financial network with banks $u,w$ and a set $C$ of $k$
outgoing edges of $u$. Denote the creditors of edges $C$ by
$V_{C}=\\{v_{i}\mid e_{i}\in C,\text{cr}(e_{i})=v_{i}\\}$. A collection of
haircut rates $\bm{\alpha}=(\alpha_{1},\alpha_{2},\dots,\alpha_{k})$ is called
_Pareto-positive_ if $C$ together with $\bm{\alpha}$ forms a Pareto-positive
multi-trade. The objective is to derive the optimal values of $\bm{\alpha}$
which maximize the sum of profit of creditors $v_{1},v_{2},\dots,v_{l}$, i.e.,
$\max\sum_{i=1}^{l}a^{\prime}_{v_{i}}-a_{v_{i}}$. Appendix B contains a
discussion for the scenario where $\bm{\alpha}$ is fixed and part of the
input.

Consider the problem where set $C$ is not given as part of the input but is
chosen as part of the solution. The goal is to select a subset of $u$’s
outgoing edges $C\subseteq E^{+}(v)$ together with a vector of haircut rates
$\bm{\alpha}=(\alpha_{1},\alpha_{2},\dots,\alpha_{|C|})$ such that the multi-
trade is Pareto-positive and maximizes the improvement of $u$’s creditors,
i.e., $\sum_{i=1}^{l}a^{\prime}_{v_{i}}-a_{v_{i}}$.

In the previous section, we obtained a bicriteria FPTAS for this problem when
we trade incoming edges of an insolvent bank. Interestingly, the results hold
for all monotone payment functions for which there is an efficient clearing
oracle (e.g., edge-ranking or proportional payments). Our results here show a
strong contrast – depending on the payment functions trading outgoing edges
can be much harder. For edge-ranking functions (and variable haircut rates),
we denote the problem by OutgoingER-VR.

######  Theorem 5.2.

OutgoingER-VR is strongly NP-hard. For any constant $\varepsilon>0$ there
exists no efficient $n^{1/2-\varepsilon}$-approximation algorithm for
OutgoingER-VR unless P = NP.

Now suppose the set of traded edges $C$ is given as part of the input.
Interestingly, the hardness for edge-ranking payments continues to apply when
$C$ is fixed a priori.

######  Corollary 5.3.

Consider a financial network with banks $u,w$, a set of outgoing edges $C$ of
$u$ and edge-ranking payment rules. It is strongly NP-hard to determine
Pareto-positive haircut rates that maximize the sum of profits of $u$’s
creditors. For any constant $\varepsilon>0$, there exists no efficient
$n^{1/2-\varepsilon}$-approximation algorithm unless NP = P.

Finally, we briefly observe that these problems for outgoing edges depend
crucially on the set of payment functions. For proportional payments (and
variable $\bm{\alpha}$), the problem for a given set $C$ can be solved
efficiently (even if the set $C$ of edges involves different debtors). When
the set $C$ of outgoing edges is chosen as part of the solution, we refer to
the problem as OutgoingPROP-VR and obtain NP-hardness. The approximability
status of these problems for different payment functions is an interesting
direction for future work.

######  Proposition 5.4.

For a given financial network with proportional payments and a set $C$ of $k$
edges, there exists an efficient algorithm that computes an optimal Pareto-
positive $\bm{\alpha}^{*}\in[0,1]^{k}$ or decides that none exists.

######  Theorem 5.5.

OutgoingPROP-VR is strongly NP-hard.

## References

  * [1] 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.
  * [2] Bloomberg.  URL: https://www.bloomberg.com/news/features/2023-03-20/credit-suisse-ubs-takeover-how-a-166-year-old-bank-collapsed.
  * [3] Swiss Federal Council.  URL: https://www.admin.ch/gov/en/start/documentation/media-releases.msg-id-93793.html.
  * [4] Péter Csóka and Jean-Jacques Herings.  Decentralized clearing in financial networks.  Manag. Sci., 64(10):4681–4699, 2018.
  * [5] Larry Eisenberg and Thomas Noe.  Systemic risk in financial systems.  Manag. Sci., 47(2):236–249, 2001.
  * [6] Jared Ellias.  Bankruptcy claims trading.  J. Empirical Legal Stud., 15(4):772––799, 2018.
  * [7] Henri Froese, Martin Hoefer, and Lisa Wilhelmi.  The complexity of debt swapping.  arXiv preprint arXiv:2302.11250, 2023.
  * [8] 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.
  * [9] Stavros Ioannidis, Bart de Keijzer, and Carmine Ventre.  Financial networks with singleton liability priorities.  In Proc. 15th Symp. Algorithmic Game Theory (SAGT), pages 205–222, 2022.
  * [10] Stavros Ioannidis, Bart de Keijzer, and Carmine Ventre.  Strong approximations and irrationality in financial networks with derivatives.  In Proc. 49th Int. Colloq. Autom. Lang. Programming (ICALP), pages 76:1–76:18, 2022.
  * [11] Panagiotis Kanellopoulos, Maria Kyropoulou, and Hao Zhou.  Financial network games.  In Proc. 2nd Int. Conf. AI in Finance (ICAIF), pages 26:1–26:9, 2021.
  * [12] Panagiotis Kanellopoulos, Maria Kyropoulou, and Hao Zhou.  Forgiving debt in financial network games.  In Proc. 31st Int. Joint Conf. Artif. Intell. (IJCAI), pages 335–341, 2022.
  * [13] Panagiotis Kanellopoulos, Maria Kyropoulou, and Hao Zhou.  Debt transfers in financial networks: Complexity and equilibria.  In Proc. 22nd Conf. Auton. Agents and Multi-Agent Syst. (AAMAS), pages 260–268, 2023.
  * [14] Adam Levitin.  Bankruptcy markets: Making sense of claims trading.  Brooklyn J. Corporate, Financial & Commercial Law, 4(1), 2009\.
  * [15] Katherine Mayo and Michael P. Wellman.  A strategic analysis of portfolio compression.  In Proc. 2nd Int. Conf. AI in Finance (ICAIF), pages 20:1–20:8, 2021.
  * [16] Marios Papachristou and Jon Kleinberg.  Allocating stimulus checks in times of crisis.  In Proc. 31th World Wide Web Conf. (WWW), pages 16–26, 2022.
  * [17] Pál András Papp and Roger Wattenhofer.  Network-aware strategies in financial systems.  In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, Proc. 47th Int. Colloq. Autom. Lang. Programming (ICALP), pages 91:1–91:17, 2020.
  * [18] 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, 2021\.
  * [19] Pál András Papp and Roger Wattenhofer.  Default ambiguity: Finding the best solution to the clearing problem.  In Proc. 17th Conf. Web and Internet Econ. (WINE), pages 391–409, 2021.
  * [20] Leonard Rogers and Luitgard Veraart.  Failure and rescue in an interbank network.  Manag. Sci., 59(4):882–898, 2013.
  * [21] Steffen Schuldenzucker and Sven Seuken.  Portfolio compression in financial networks: Incentives and systemic risk.  In Proc. 21st Conf. Econ. Comput. (EC), page 79, 2020.
  * [22] Steffen Schuldenzucker, Sven Seuken, and Stefano Battiston.  Clearing payments in financial networks with credit default swaps.  In Proc. 17th Conf. Econ. Comput. (EC), page 759, 2016.
  * [23] 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.
  * [24] Luitgard Veraart.  When does portfolio compression reduce systemic risk?  Math. Finance, 32(3):727–778, 2022.
  * [25] David Zuckerman.  Linear degree extractors and the inapproximability of max clique and chromatic number.  Theory Comput., 3(1):103–128, 2007.

##  Appendix A Missing Proofs

See 3.6

######  Proof A.1.

We derive the desired value for $\alpha$ using a linear program constructed as
follows. We use $E^{\prime}$, $L^{\prime}$ and $r^{\prime}$ to refer to the
edge sets, total liabilities and recovery rates after the trade, respectively.

For a creditor-positive trade we need to strictly raise the recovery rate
$r_{v}$ and keep $r_{w}$ unchanged, i.e., $r^{\prime}_{v}>r_{v}$ and
$r^{\prime}_{w}=r_{w}$. We relax the condition for $v$ to $r^{\prime}_{v}\geq
r_{v}$, since we will discover a solution with strict improvement whenever it
exists. Moreover, the return of $w$ is bounded by the external assets of $w$
and the liability of $e$ (since $\alpha\leq 1$), i.e.,
$\rho\leq\min\\{a^{x}_{w},\ell_{e}\\}$.

The clearing state is governed by fixed-point constraints. We reformulate them
using the recovery rates. The recovery rate of any bank
$b\in(V\setminus\\{v,w\\})$ must satisfy
$r^{\prime}_{b}\leq(a^{x}_{b}+\sum_{e^{\prime}\in
E^{\prime-}(b)}r^{\prime}_{\text{de}(e^{\prime})}\cdot\ell_{e^{\prime}})/L^{\prime}_{b}$.
Accounting for the trade, the recovery rate of $v$ is bounded by
$r^{\prime}_{v}\leq(a^{x}_{v}+\rho+\sum_{e^{\prime}\in
E^{\prime-}(v)}r^{\prime}_{\text{de}(e^{\prime})}\cdot\ell_{e^{\prime}})/L^{\prime}_{v}$
and similarly $r^{\prime}_{w}\leq(a^{x}_{w}-\rho+\sum_{e^{\prime}\in
E^{\prime-}(w)}r^{\prime}_{\text{de}(e^{\prime})}\cdot\ell_{e^{\prime}})/L^{\prime}_{w}$.

Finally, as discussed above, we capture the objective by maximizing the total
payments in the network after the trade $\max\sum_{e^{\prime}\in
E^{\prime}}r^{\prime}_{\text{de}(e^{\prime})}\cdot\ell_{e^{\prime}}$.

Overall, the following LP captures the problem of finding an optimal return
$\rho$.

Max. $\displaystyle\displaystyle\sum\limits_{e^{\prime}\in
E^{\prime}}r^{\prime}_{\text{de}(e^{\prime})}\cdot\ell_{e^{\prime}}$ s.t.
$\displaystyle\displaystyle r^{\prime}_{v}\geq r_{v},$ $\displaystyle
r^{\prime}_{w}=r_{w},$ $\displaystyle\rho\leq a^{x}_{w},$
$\displaystyle\rho\leq\ell_{e},$ $\displaystyle
r^{\prime}_{v}\leq(a^{x}_{v}+\rho+\sum_{e^{\prime}\in
E^{\prime-}(v)}r^{\prime}_{\text{de}(e^{\prime})}\cdot\ell_{e^{\prime}})/L^{\prime}_{v},$
$\displaystyle r^{\prime}_{w}\leq(a^{x}_{w}-\rho+\sum_{e^{\prime}\in
E^{\prime-}(w)}r^{\prime}_{\text{de}(e^{\prime})}\cdot\ell_{e^{\prime}})/L^{\prime}_{w},$
$\displaystyle r^{\prime}_{b}\leq(a^{x}_{b}+\sum_{e^{\prime}\in
E^{\prime-}(b)}r^{\prime}_{\text{de}(e^{\prime})}\cdot\ell_{e^{\prime}})/L^{\prime}_{b}$
$\displaystyle\forall b\in(V\setminus\\{v,w\\}),$ $\displaystyle
r^{\prime}_{b}\in[0,1]$ $\displaystyle\forall b\in V$

The LP is polynomial in the size of $\mathcal{F}$. An optimal creditor-
positive $\alpha$ exists iff the optimal LP solution yields $\rho>p_{e}$. Then
the optimal $\alpha=\rho/\ell_{e}$.

See 4.4

######  Proof A.2.

We show the statement with reduction from Subset Sum. An instance of Subset
Sum is given by a multiset $S=\\{b_{1},b_{2},\dots,b_{n}\\}$ of positive
integers, i.e., $b_{i}\in\mathbb{N}_{>0}$, and a target value $T\in\mathbb{N}$
with $T\leq\sum_{i=1}^{k}b_{i}$. The goal is to decide whether there exists a
subset of $S^{\prime}\subseteq[n]$ with sum of elements exactly $T$, i.e.,
$\sum_{i\in S^{\prime}}b_{i}=T$.

The graph $G$ consists of $n+2$ banks where
$V=\\{v,w,b_{1},b_{2},\dots,b_{n}\\}$. We introduce edge $e_{i}$ with
$\text{cr}(e_{i})=v$ and $\text{de}(e_{i})=b_{i}$ and liability $2b_{i}$, for
all $i\in[n]$. Additionally include edge $e$ with debtor $v$ and creditor $w$
with liability $\ell_{e}=T+\sum_{i=1}^{n}b_{i}$. Note that we use $b_{i}$ both
to refer to bank $b_{i}$ as well as to integer $b_{i}$. Lastly, set the
external assets of $w$ to $2T$. For every bank $b_{i}$, the external assets
are the integer $b_{i}$. Observe that bank $b_{i}$ pays $b_{i}$ to $v$. Hence,
$v$ receives incoming payments of $\sum_{i=1}^{n}b_{i}$ and forwards the same
amount to $w$.

We claim that there exists a subset $S^{\prime}\subseteq[n]$ with sum of
elements exactly $T$ if and only if there exists a creditor-positive multi-
trade of incoming edges and individual haircut rates that saves $v$.

Assume there exists a subset $S^{\prime}\subseteq[n]$ with sum of elements
exactly $T$. Then, a creditor-positive multi-trade can be constructed as
follows. For every $i\in S^{\prime}$, add $e_{i}$ to $C$ and assign
$\alpha_{i}=1$. Thus, the return is given by $\rho=\sum_{i\in
S^{\prime}}\alpha_{i}\cdot\ell_{e_{i}}=\sum_{i\in S^{\prime}}2b_{i}=2T\leq
a^{x}_{w}$, for $|C|=k$. Because the payments of the remaining incoming edges
of $v$ are not affected by the multi-trade, the total assets of $v$ equal

$a^{\prime}_{v}=\sum_{i\in S^{\prime}}\alpha_{i}\cdot\ell_{e_{i}}+\sum_{e\in
E^{\prime-}(v)}p^{\prime}_{e}=2T+\sum_{e\in E^{-}(v)}p_{e}-\sum_{i\in
S^{\prime}}p_{e_{i}}=2T+a_{v}-T=a_{v}+T\;.$

Consequently, $v$’s total assets are increased by $T$, pays all debt, all
these payments reach $w$, leaving $w$ indifferent.

For the other direction, assume there exists a creditor-positive multi-trade
given by $C\subseteq E^{-}(v)$, with $|C|=k$, and an $\alpha_{i}$, for every
$e_{i}\in C$. Furthermore, assume $v$ improves by $T$. We show that
$S^{\prime}=\\{i\mid e_{i}\in C\\}$ is a solution for Subset Sum. Again, since
no cycles can evolve, $v$ has to receive additional funds via the return
$\rho$. It can be decomposed into two parts: First, $\sum_{e_{i}\in
C}p_{e_{i}}$ can be interpreted as reimbursement for the traded edges, whose
payments $v$ no longer receives; Second, $\rho-\sum_{e_{i}\in C}p_{e_{i}}$ is
the surplus that helps to make $v$ solvent. Since the payment on edges
${E^{\prime}}^{-}(v)$ are unaffected by the multi-trade, $\rho-\sum_{e_{i}\in
C}p_{e_{i}}$ is exactly the improvement of $v$. Since $v$ becomes solvent
$\rho-\sum_{e_{i}\in C}p_{e_{i}}=T$, and since $\rho\leq\sum_{e_{i}\in
C}\ell_{e_{i}}$, this implies $\rho-\sum_{e_{i}\in
C}p_{e_{i}}\leq\sum_{e_{i}\in C}\ell_{e_{i}}-\sum_{e_{i}\in C}p_{e_{i}}$.
Intuitively, the surplus is bounded by the sum of residual debt on the traded
edges. $w$ pays surplus of $T$ and has external assets of $2T$, so $\rho\leq
a^{x}_{w}=2T$ implies $\sum_{i\in S^{\prime}}b_{i}=\sum_{e_{i}\in
C}p_{e_{i}}\leq T$. Assume $\sum_{e_{i}\in C}p_{e_{i}}<T$, i.e., $w$ buys
claims with debtors $b_{i}$ such that $\sum_{i\in S^{\prime}}b_{i}<T$. Then,
by construction, the residual debt of the traded edges sums up to less than
$T$ and, thus, do not allow for a surplus of $T$. Thus, $\sum_{i\in
S^{\prime}}b_{i}\geq T$ and, hence, $\sum_{i\in S^{\prime}}b_{i}=T$. Thus,
$S^{\prime}$ is a solution to the instance of Subset Sum.

See 5.2

######  Proof A.3.

$v$$S_{1}$$S_{2}$$S_{3}$$\cdots$$S_{l}$$u_{3}$$u_{2}$$u_{1}$$u_{4}$$\cdots$$u_{m}$$w$$k(M+m)$$M+d_{1}$$M+d_{2}$$M+d_{3}$$M+d_{l}$Y1.0e0]pt$1$Y1.0e0]pt$1$$1$$1$Y1.0e0]pt$1$$1$Y1.0e0]pt$1$Y1.0e0]pt$1$Y1.0e0]pt$1$$M$Y1.0e0]pt$M$Y1.0e0]pt$M$$M$Y1.0e0]pt$1$Y1.0e0]pt$1$$1$Y1.0e0]pt$1$Y1.0e0]pt$1$
Figure 2: Schematic visualisation of the constructed network in proof of
Theorem 5.2. The dashed edges are paid off last with respect to the edge-
ranking rules.

We first show NP-hardness and then observe inapproximability as a consequence.

NP-hardness.  We perform a reduction from Set Packing. In such an instance, we
are given a graph universe $U=\\{u_{1},u_{2},\dots,u_{m}\\}$, a family
$\mathcal{S}=(S_{i})_{i\in[l]}$ of sets $S_{i}\subset U$. We denote the
cardinality of set $S_{i}$ by $d_{i}=|S_{i}|$. For a given value $k\leq l$,
the goal is to decide whether there exists a set packing $P\subseteq[l]$ of
$k$ pair-wise disjoint sets, i.e., $S_{i}\cap S_{j}=\emptyset$ for all $i,j\in
P$ and $|P|=k$.

We construct a financial network $\mathcal{F}$ with banks
$V=\\{v,w,S_{1},S_{2},\dots,S_{l},u_{1},u_{2},\dots,u_{m}\\}$ as shown in
Figure 2. Note that we use $S_{i}$ and $u_{j}$ to both refer to the set or
element, respectively, as well as the corresponding node in the financial
network. For every set $S_{i}$, add an edge $e_{i}$ with $\text{de}(e_{i})=v$,
$\text{cr}(e_{i})=S_{i}$ and liability $\ell_{e_{i}}=M+d_{i}$, where
$M=m^{3}$. Furthermore, include an edge $e$ with $\text{de}(e)=S_{i}$ and
$\text{cr}(e)=u_{j}$ if $u_{j}\in S_{i}$ and set the liability to
$\ell_{e}=1$. Moreover, every bank $S_{i}$ has an additional outgoing edge $e$
with liability $M$ and $\text{cr}(e)=w$. Finally, add an edge $e_{j}$ with
$\text{de}(e_{j})=u_{j}$ and $\text{cr}(e_{j})=w$ and liability 1. $w$ is the
only bank with non-zero external assets $k(M+m)$.

We assume $v$ and banks $u_{j}$ have arbitrary edge-ranking payment functions.
Since $v$ has no external and no incoming assets, she will never make any
positive payments. Banks $u_{j}$ each have a unique outgoing edge and thus
will direct all assets towards this edge. Each bank $S_{i}$ has an arbitrary
edge-ranking rule with the condition that edge $e$ with creditor $w$ is paid
last. In other words, $S_{i}$ will only pay positive assets to $e$ if her
total assets are sufficient to saturate all other outgoing edges.

We claim that there exists a set packing of size $k$ if and only if there is a
multi-trade of outgoing edges such that the creditors of $v$ profit by a total
amount of at least $k(M+m)$.

First assume that there exists a set packing $P$ of size $k$. Then, perform a
multi-trade of edges $e_{i}$, where
$\text{de}(e_{i})=v,\text{cr}(e_{i})=S_{i}$ and $S_{i}\in P$, and set all
haircut rates to 1. Hence, the trade consists of $k$ edges and $w$ pays a
return of $M+d_{i}$ to every bank $S_{i}$. Clearly, all banks $S_{i}$ are able
to saturate all outgoing edges. Since $P$ is a set packing, every bank $u_{j}$
receives incoming payments of at most $1$ and forwards the assets to $w$.
Consequently, the incoming payments of buyer $w$ equal the total return of
$kM+\sum_{S_{i}\in P}d_{i}$. Hence, the multi-trade is Pareto-positive and the
creditors of $v$ profit by a total amount of $kM+\sum_{S_{i}\in P}d_{i}$.

For the other direction, assume there exists a Pareto-positive multi-trade
where $v$’s creditors profit by a total amount of at least $kM$, i.e.,
$\sum_{i=1}^{l}a^{\prime}_{S_{i}}\geq kM+\sum_{i=1}^{l}a_{S_{i}}$. Observe
that no bank $S_{i}$ can receive positive incoming payments from $v$ for every
multi-trade of outgoing edges and, thus, all assets of $S_{i}$ must stem from
the received return. Simultaneously, since $w$ is not harmed by the multi-
trade, she must receive the full return as incoming payments. As $k\leq n$ and
$M=m^{3}$, this is only possible if there are positive payments on at least
$k$ edges with liability $M$. This directly implies that at least $k$ banks
$S_{i}$ settled all debt towards all their creditors $u_{j}$ and all assets
were forwarded to $w$. Consequently, all $k$ banks have liabilities towards
pair-wise disjoint subsets of $U$.

Inapproximability.  For contradiction, we assume a
$n^{1/2-\varepsilon}$-approximation algorithm for the problem exists. We use
this algorithm to construct an efficient approximation algorithm for
Independent Set with a sublinear approximation ratio, which implies P = NP
[25].

An instance of Independent Set is given by an undirected graph and an integer
$k$. We resort to the standard interpretation as an instance of Set Packing,
i.e., the universe is the set of edges, and each vertex corresponds to a set
of incident edges. Note that this implies $l\leq 2m$ and $m<l^{2}$. Now
construct the corresponding financial network for OutgoingER-VR as described
in the reduction of Theorem 5.2. Note that the network has a number of nodes
that is $n=l+m+2\leq 3m+2$. With foresight, we set $M$ in the reduction to
$M=(3m+2)^{3}\geq n^{3}$. Observe that this does not change the correctness of
the reduction.

Suppose the optimal solution for the constructed network is given by a multi-
trade with a total return of $k^{*}M+\beta^{*}$. By assumption, the
approximation algorithm computes a solution with total return at least
$kM+\beta$ satisfying $n^{1/2-\varepsilon}\cdot(kM+\beta)\geq
k^{*}M+\beta^{*}$. We know that $1\leq k,k^{*}\leq m<n$, so
$1\leq\beta,\beta^{*}\leq m^{2}<n^{2}$. Since $M=n^{3}$, it holds that
$kM+\beta\leq(k+1/n)M$. Combining these observations yields
$n^{1/2-\varepsilon}(k+1/n)M\geq k^{*}M$ and hence
$n^{1/2-\varepsilon}>k^{*}/(k+1/n)$.

If the optimal solution for the instance of OutgoingER-VR achieves
$k^{*}M+\beta^{*}$, clearly there exists a set packing of size $k^{*}$ but not
of size $k^{*}+1$. Hence, $k^{*}$ is the maximal cardinality of a feasible set
packing in the given Set Packing instance. Moreover, with the reduction to
OutgoingER-VR we obtain a feasible set packing of at least size $k$. In other
words, we receive a $k^{*}/k$ approximation for Set Packing and, thus, for
Independent Set. This results in a approximation factor of

$\frac{k^{*}}{k}=\frac{k^{*}}{k+1/n}\cdot\frac{k+1/n}{k}\leq
n^{1/2-\varepsilon}\cdot\frac{k+1/n}{k}<n^{1/2-\varepsilon}+1\;.$

Now observe that
$n^{1/2-\varepsilon}+1\leq(3m+2)^{1/2-\varepsilon}+1<(3l+2)^{1-\varepsilon}+1<l^{1-\delta}$
for a suitably small constant $\delta=\delta(\varepsilon)>0$ and any $l$
larger than a suitable constant $l_{0}(\varepsilon)$. Recall that $l$ is the
number of nodes in the underlying instance of Independent Set. Hence, we
obtain an algorithm with a sublinear approximation ratio for Independent Set.

See 5.3

######  Proof A.4.

To observe this, consider the constructed network as described in proof of
Theorem 5.2 and add an additional edge from every bank $S_{i}$ to an auxiliary
node each with liability 1. Moreover, include an edge from the auxiliary node
to $w$ and set the liability to $l$. Adjust the edge-ranking rules of all
$S_{i}$ so that the new edge has highest priority and increase $w$’s external
assets by $l$. Raise the liability of all outgoing edges of $v$ from $M+d$ to
$M+d+1$. Finally, fix $C=E^{+}(v)$. Recall that initially no bank receives any
incoming payments. A trivial solution would be to set $\alpha_{i}=0$, for all
$i\in[l]$, which implies a return of 0 for every creditor. In order to
maximize the sum of returns, it is optimal to increase the haircut rate to 1
for the maximal set of edges $C^{\prime}\subseteq C$ where all associated
banks $S_{i}$ have disjoint creditors.

See 5.4

######  Proof A.5.

We compute the optimal solution for $\bm{\alpha}$ via an LP, if it exists.
Recall that the set of edges, recovery rates and total assets after the multi-
trade are denoted by $E^{\prime},L^{\prime}$ and $r^{\prime}$, respectively.

For a Pareto-positive trade, none of $u$’s creditors should be harmed while at
least one creditor strictly profits. Formally, we have $r^{\prime}_{v_{i}}\geq
r_{v_{i}}$, for all $i\in[l]$, and $\sum_{i:v_{i}\in
V_{C}}\rho_{i}+\sum_{i=1}^{l}(a^{x}_{v_{i}}+\sum_{e^{\prime}\in
E^{\prime-}(v_{i})}r^{\prime}_{\text{de}(e^{\prime})}\cdot
l_{e^{\prime}})>\sum_{i=1}^{l}a_{v_{i}}$. Similarly, $w$ should be indifferent
after the trade, i.e., $r^{\prime}_{w}=r_{w}$. Moreover, all returns are upper
bounded by the respective liabilities and $w$’s external assets must suffice
to cover the sum of returns, i.e., $\rho_{i}\leq\ell_{e_{i}}$, for all
$e_{i}\in C$, and $\sum_{i:e_{i}\in C}\rho_{i}\leq a^{x}_{w}$.

The recovery rates $r^{\prime}$ of all banks must be consistent with the
clearing state which arises in the network after the trade. For all creditors
we have $r^{\prime}_{v_{i}}\leq(a^{x}_{v_{i}}+\rho_{i}+\sum_{e^{\prime}\in
E^{\prime-}(v_{i})}r^{\prime}_{\text{de}(e^{\prime})}\cdot\ell_{e^{\prime}})/L^{\prime}_{v_{i}}$,
where $V_{C}$ is the set of creditors incident to the edges in $C$. Similarly,
$r^{\prime}_{w}\leq(a^{x}_{w}-\sum_{i:e_{i}\in C}\rho_{i}+\sum_{e^{\prime}\in
E^{\prime-}(w)}r^{\prime}_{\text{de}(e^{\prime})}\cdot\ell_{e^{\prime}})/L^{\prime}_{w}$
must be fulfilled for $w$. For all other banks it must be true that
$r^{\prime}_{b}\leq(a^{x}_{b}+\sum_{e^{\prime}\in
E^{\prime-}(b)}r^{\prime}_{\text{de}(e^{\prime})}\cdot\ell_{e^{\prime}})/L^{\prime}_{b}$.

The objective is to maximize the sum of profits of all creditors $v_{1},\dots
v_{l}$. Every creditor $v_{i}$ can profit in two ways: (i) by the return, in
case $e_{i}\in C$ and the return is chosen as $\rho_{i}>0$, and (ii) by
increased incoming payments in the resulting clearing state. Hence, we set the
objective function to

$\sum\limits_{i:v_{i}\in V_{C}}\rho_{i}+a_{v_{i}}^{x}+\sum_{e^{\prime}\in
E^{\prime-}(v_{i})}r^{\prime}_{\text{de}(e^{\prime})}\cdot\ell_{e^{\prime}}\enspace.$

Observe that maximizing the objective function will also maximize the incoming
payments of $u$’s creditors. However, the LP might not derive the correct
clearing state for the network after the trade. The clearing state can be
determined efficiently upon solving the LP.

Combining all constraints yields the following LP.

Max. $\displaystyle\displaystyle\sum\limits_{i:v_{i}\in
V_{C}}\rho_{i}+a_{v_{i}}^{x}+\sum_{e^{\prime}\in
E^{\prime-}(v_{i})}r^{\prime}_{\text{de}(e^{\prime})}\cdot\ell_{e^{\prime}}$
s.t. $\displaystyle\displaystyle\sum_{i:v_{i}\in
V_{C}}\rho_{i}+\sum_{i=1}^{l}(a^{x}_{v_{i}}+\sum_{e^{\prime}\in
E^{\prime-}(v_{i})}r^{\prime}_{\text{de}(e^{\prime})}\cdot
l_{e^{\prime}})\geq\sum_{i=1}^{l}a_{v_{i}},$ $\displaystyle
r^{\prime}_{v_{i}}\geq r_{v_{i}}$ $\displaystyle\forall i\in[l],$
$\displaystyle r^{\prime}_{w}=r_{w},$ $\displaystyle\sum_{i:e_{i}\in
C}\rho_{i}\leq a^{x}_{w},$ $\displaystyle\rho_{i}\leq\ell_{e_{i}},$
$\displaystyle\forall e_{i}\in C,$ $\displaystyle
r^{\prime}_{v_{i}}\leq(a^{x}_{v_{i}}+\rho_{i}+\sum_{e^{\prime}\in
E^{\prime-}(v_{i})}r^{\prime}_{\text{de}(e^{\prime})}\cdot\ell_{e^{\prime}})/L^{\prime}_{v_{i}},$
$\displaystyle\forall v_{i}\in V_{C},$ $\displaystyle
r^{\prime}_{w}\leq(a^{x}_{w}-\sum_{i:e_{i}\in C}\rho_{i}+\sum_{e^{\prime}\in
E^{\prime-}(w)}r^{\prime}_{\text{de}(e^{\prime})}\cdot\ell_{e^{\prime}})/L^{\prime}_{w},$
$\displaystyle r^{\prime}_{b}\leq(a^{x}_{b}+\sum_{e^{\prime}\in
E^{\prime-}(b)}r^{\prime}_{\text{de}(e^{\prime})}\cdot\ell_{e^{\prime}})/L^{\prime}_{b}$
$\displaystyle\forall b\in(V\setminus(\\{w\\}\cup V_{C})),$ $\displaystyle
r^{\prime}_{b}\in[0,1]$ $\displaystyle\forall b\in V$

The LP has polynomial size in . An Pareto-positive multi-trade exists if

$\sum_{i:v_{i}\in
V_{C}}\rho_{i}+\sum_{i=1}^{l}(a^{x}_{v_{i}}+\sum_{e^{\prime}\in
E^{\prime-}(v_{i})}r^{\prime}_{\text{de}(e^{\prime})}\cdot
l_{e^{\prime}})>\sum_{i=1}^{l}a_{v_{i}}$

is satisfied. The optimal haircut rates are defined by
$\alpha_{i}=\rho_{i}/\ell_{e_{i}}$, for all $e_{i}\in C$.

See 5.5

######  Proof A.6.

$v$$S_{1}$$S_{2}$$S_{3}$$\cdots$$S_{l}$$u_{3}$$u_{2}$$u_{1}$$u_{4}$$\cdots$$u_{m}$$w$$lM$$k(M+d)$$M+d$$M+d$$M+d$$M+d$Y1.0e0]pt$M^{\prime}$$M^{\prime}$$M^{\prime}$$M^{\prime}$Y1.0e0]pt$M^{\prime}$$M^{\prime}$Y1.0e0]pt$M^{\prime}$Y1.0e0]pt$M^{\prime}$Y1.0e0]pt$M^{\prime}$$\text{oc}^{\prime}_{1}+1$$\text{oc}^{\prime}_{2}+1$$\text{oc}_{3}^{\prime}+1$$\text{oc}_{4}^{\prime}+1$$\text{oc}^{\prime}_{m}+1$
Figure 3: Schematic visualisation of the constructed network in proof of
Theorem 5.5. Black edge labels indicate liabilities. Due to lack of space we
define $M^{\prime}:=M/d+1$ and $\text{oc}^{\prime}_{j}:=\text{oc}_{j}\cdot
M/d+1$.

We prove NP-hardness with a reduction from $d$-Set Packing. Every instance
consists of a universe $U=\\{u_{1},u_{2},\dots,u_{m}\\}$ and a family
$\mathcal{S}=(S_{i})_{i\in[l]}$ of sets $S_{i}\subset U$. All sets have the
same cardinality $d$, i.e., $|S_{i}|=d$ for all $i\in[l]$. For a given value
$k\leq l$, the goal is to decide whether there exists a set packing
$P\subseteq[l]$ of $k$ pair-wise disjoint sets, i.e., $S_{i}\cap
S_{j}=\emptyset$ for all $i,j\in P$ and $|P|=k$. Let $\text{oc}_{j}$ denote
the number of occurrences of element $u_{j}$ in sets $S_{i}$, i.e.,
$\text{oc}_{j}=|\\{i\mid u_{j}\in S_{i}\\}|$.

We construct a financial network $\mathcal{F}$ with banks
$V=\\{v,w,S_{1},S_{2},\dots,S_{l},u_{1},u_{2},\dots,u_{m}\\}$ as shown in
Figure 3. Note that we use $S_{i}$ and $u_{j}$ to both refer to the set or
element, respectively, as well as the corresponding node in the financial
network. For every set $S_{i}$, add an edge $e_{i}$ with $\text{de}(e_{i})=v$,
$\text{cr}(e_{i})=S_{i}$ and liability $\ell_{e_{i}}=M+d$, where $M\gg m$.
Furthermore, include an edge $e$ with $\text{de}(e)=S_{i}$ and
$\text{cr}(e)=u_{j}$ if $u_{j}\in S_{i}$ and set the liability to
$\ell_{e}=M/d+1$. Finally, add an edge $e_{j}$ with $\text{de}(e_{j})=u_{j}$
and $\text{cr}(e_{j})=w$ and liability $\text{oc}_{j}\cdot M/d+1$. $v$ and $w$
are the only bank with non-zero external assets, where $a^{x}_{v}=l\cdot M$
and $a^{x}_{w}=k(M+d)$. All banks distribute their assets proportionally which
gives rise to the following clearing state. $v$ pays $M$ to every bank $S_{i}$
who pass $M/d$ to their creditors, respectively. This results in incoming
payments of $\text{oc}_{j}\cdot M/d$ for every $u_{j}$ and, hence, incoming
payments of $\sum_{j=1}^{m}\text{oc}_{j}\cdot M/d$ for $w$.

We claim that there exists a set packing of size $k$ if and only if there is a
Pareto-positive multi-trade of outgoing edges such that the creditors of $v$
profit by a total amount of at least $k\cdot d$.

First, assume that there exists a set packing $P$ of size $k$. Then, perform a
multi-trade of edges $e_{i}$, where
$\text{de}(e_{i})=v,\text{cr}(e_{i})=S_{i}$ and $i\in P$, and set all haircut
rates to 1. Hence, the trade consists of $k$ edges and $w$ pays a return of
$M+d$ to every bank $S_{i}$. Clearly, all $k$ banks $S_{i}$ are able to
saturate all outgoing edges. Since $P$ is a set packing, every bank $u_{j}$
receives incoming payments of at most $\text{oc}_{j}\cdot M/d+1$ and forwards
the assets to $w$. Consequently, the incoming payments of buyer $w$ equal the
total return of $k(M+d)$. Hence, the multi-trade is Pareto-positive and the
creditors of $v$ profit by a total amount of $k\cdot d$.

For the other direction, assume there exists a Pareto-positive multi-trade
where $v$’s creditors profit by a total amount of at least $k\cdot d$, i.e.,
$\sum_{i=1}^{l}a^{\prime}_{S_{i}}\geq k\cdot d+\sum_{i=1}^{l}a_{S_{i}}$.
Observe that no bank $S_{i}$ can receive increased incoming payments from $v$
for every multi-trade of outgoing edges and, thus, all additional assets of
$S_{i}$ must stem from the received return. Consider a bank $S_{i}$ whose
incoming edge was traded. Before the trade, $S_{i}$ receives payments of $M$,
hence, $\rho_{i}\geq M$. The return is upper bounded by $\ell_{e_{i}}=M+d$,
thus, bank $S_{i}$ profits by at most $d$. By definition of $M$, $w$ is only
able to refund payments of at most $k$ edges. Hence, the total profit of
$k\cdot d$ is only possible, if $w$ buys $k$ edges with haircut rates 1.
Simultaneously, since $w$ is not harmed by the multi-trade, she must receive
the full return as incoming payments. This implies that all banks $S_{i}$ with
$e_{i}\in C$ pass additional assets of 1 to each creditor $u_{j}$ who forward
the payments to $w$. Due to the limited liabilities of $u_{j}$ towards $w$,
all $S_{i}$ must have pair-wise disjoint creditors. In conclusion, there exist
at least $k$ sets $S_{i}$ with disjoint elements.

##  Appendix B Fixed Haircut Rates

###  B.1 Single Claims Trades

When $\alpha\in[0,1]$ is fixed, the problem reduces to deciding whether the
given trade is creditor-positive. This problem can be solved trivially in
polynomial time whenever there is an oracle that can compute the clearing
state $\mathbf{p}$ in polynomial time. First, check if $\alpha\ell_{e}\leq
a_{w}^{x}$, since otherwise the trade is impossible. Then call the oracle with
networks $\mathcal{F}$ and $\mathcal{F}^{\prime}$ (before and after the trade)
and check if the assets fulfill Definition 2.6. Recall that the oracle for
computing the clearing state can be implemented in polynomial time for
proportional or edge-ranking payments.

###  B.2 Multi-Trades of Incoming Edges

Consider a multi-trade of incoming edges. If the set $C$ of edges to be traded
is given (along with a haircut rate $\alpha_{i}$ for each $e_{i}\in C$), then
the problem is to decide whether the given trade is creditor-positive or not.
This is again straightforward by computing the emerging clearing state and
checking (1) whether $w$ can fund the return, $\sum_{e_{i}\in
C}\alpha_{i}\ell_{e_{i}}\leq a_{w}^{x}$, and (2) $v$ strictly profits after
the trade, $a^{\prime}_{v}>a_{v}$.

More interestingly, consider the problem of selecting the incoming edges.
Suppose there is a vector of given haircut rates
$\bm{\alpha}=(\alpha_{e})_{e\in E^{-}(v)}$ for all incoming edges of $v$. We
need to choose a set $C\subseteq E^{-}(v)$ of edges that yields a creditor-
positive trade with maximal improvement for creditor $v$ (over all creditor-
positive multi-trades of incoming edges of $v$ with given rate vector
$\bm{\alpha}$). We first prove a hardness result for this problem.

Similar to our result above, we show it is NP-hard to decide whether creditor
$v$ can be _saved_ by a creditor-positive multi-trade of incoming edges, i.e.,
whether total assets of $L_{v}$ can be achieved. We call this problem
IncomingSave-FR (for fixed haircut rates).

######  Theorem B.1.

IncomingSave-FR is weakly NP-hard.

######  Proof B.2.

We use Subset Sum, where an instance consists of positive integers
$S=\\{b_{1},\dots,b_{n}\\}$ and a target value $T\leq\sum_{i=1}^{n}b_{i}$.
W.l.o.g. we assume $b_{i}>1$, for all $i\in[n]$.

For a given Subset Sum instance, we construct a corresponding financial
network as follows. The graph $G$ consists of $n+3$ banks where
$V=\\{u,v,w,b_{1},b_{2},\dots,b_{n}\\}$. Then, add edge $e_{i}$ with
$\text{de}(e_{i})=b_{i}$ and $\text{cr}(e_{i})=v$, for every $i\in[n]$. Set
the liability $\ell_{i}$ to $b_{i}$. Note that we use $b_{i}$ to both denote
bank $b_{i}$ as well as the respective integer value. Add edges $e$ and
$e^{\prime}$ with $\text{de}(e)=v,\text{cr}(e)=w$ and
$\text{de}(e^{\prime})=u,\text{cr}(e^{\prime})=v$ with liabilities
$\ell_{e}=T$ and $\ell_{e^{\prime}}=T-1$. Banks $u$ and $w$ are the only banks
with non-zero external assets $a^{x}_{u}=T-1$ and $a^{x}_{w}=T$. Finally, we
fix $\alpha_{e_{i}}=1$, for $i\in[n]$, and $\alpha_{e^{\prime}}=0$.

We claim that there exists a subset $S^{\prime}\subseteq[n]$ with sum of
elements exactly $T$ if and only if there exists a creditor-positive multi-
trade with $\bm{\alpha}$ that saves $v$.

First, assume there exists a subset $S^{\prime}\subseteq[n]$ with $\sum_{i\in
S^{\prime}}b_{i}=T$. For every $i\in S^{\prime}$, add $e_{i}$ as well as
$e^{\prime}$ to the set $C$. Since $\sum_{e\in
C}\alpha_{e}\cdot\ell_{e}=0+\sum_{e_{i}\in
C\setminus\\{e^{\prime}\\}}\alpha_{e_{i}}\cdot\ell_{e_{i}}=T$, the return of
the multi-trade is given by $\rho=T=a^{x}_{w}$. Additionally due to the trade
of edge $e^{\prime}$, the return $\rho$ equals the total assets of $v$. For
this return, $v$ is able to exactly settle all debt and pays all assets back
to $w$. Hence, the multi-trade is creditor-positive and $v$ obtains total
assets of $T=L_{v}$.

For the other direction, assume there exists a trade that saves $v$. As no
cycles can evolve by a multi-trade, the missing assets of $v$ must be received
by the return. Since there exists no edge $e_{i}$ with
$\alpha_{e_{i}}\cdot\ell_{e_{i}}=1$, edge $e^{\prime}$ must be part of the
trade. This reduces the incoming payments of $v$ to zero and implies that all
assets of $T$ must stem from the return $\rho=T$. Thus, there exists a set of
incoming edges $C\subseteq E^{-}(v)$ such that $\rho=\sum_{e\in
C}\alpha_{e}\cdot\ell_{e}=0+\sum_{e_{i}\in
C\setminus\\{e^{\prime}\\}}\alpha_{e_{i}}\cdot\ell_{e_{i}}=\sum_{e_{i}\in
C\setminus\\{e^{\prime}\\}}\ell_{e_{i}}\geq T$. Since $w$ must not suffer from
the trade, all funds transferred to $v$ must return to $w$, which implies
$\rho=\sum_{e_{i}\in C\setminus\\{e^{\prime}\\}}\ell_{e_{i}}\leq T$. Hence,
$S^{\prime}=\\{i\mid e_{i}\in C\setminus\\{e^{\prime}\\}\\}$ is a solution to
Subset Sum.

The proof can easily adapted to the special case with uniform fixed haircut
rates $\alpha_{e}=\alpha\in[0,1]$ for all $e\in E^{-}(v)$, by removing bank
$u$ and edge $e^{\prime}$.

For the constructed network in proof of Theorem B.1, consider any creditor-
positive multi-trade. Since $v$ is strictly profiting, her total assets must
increase to $a^{\prime}_{v}\geq T$. On the other hand, $w$ is not suffering
and hence receives the full return $\rho$ as incoming payments. This implies
$a^{\prime}_{v}\leq T$. Combing both observations, every creditor-positive
multi-trade saves $v$.

######  Corollary B.3.

For a given financial network with banks $v$ and $w$ and fixed haircut rates,
deciding whether a creditor-positive multi-trade of incoming edges exists is
weakly NP-hard.

Towards approximation, we proceed roughly as for variable haircut rates above,
with some notable differences. We lack the freedom to choose a suitable return
for a set of edges. Instead, the return is fixed for each edge. Formally, we
are given fixed haircut rates $\alpha_{e}$ for each $e\in E^{-}(v)$, so each
edge has an associated return of $\rho_{e}=\alpha_{e}\ell_{e}$. Towards
approximation, in Definition 4.5 we relaxed the liability condition. Here,
such a relaxation is not effective because of absent monotonicity properties.
Instead, we resort to an approximate trade involving subsidies. Below, we
formulate an FPTAS for approximate trades with limited subsidies. The variant
with fixed returns again yields a certain Knapsack problem. However, upon
rounding objective function parameters we alter return payments, which might
destroy existence of any feasible trade.222As an example, consider a network
where $v$ has $p$ incoming edge $e_{i}$ with debtor $u_{i}$, for $i\in[p]$,
with sufficiently large liabilities. $v$ has an outgoing edge to $w$ with
liability $q$. $u_{1}$ and $w$ are the only banks with non-zero external
assets of $a^{x}_{u_{1}}=q-1$ and $a^{x}_{w}=q$. The fixed returns are given
by $\rho_{e_{1}}=0,\rho_{e_{2}}=q$ and
$\rho_{e_{3}}=\rho_{e_{4}}=\cdots=\rho_{e_{p}}=0$. Trading
$C=\\{e_{1},e_{2}\\}$ is a feasible solution. Clearly there exists an
$\epsilon$ and $p$ such that $\lceil r_{e_{2}}/s\rceil\cdot s>q$ for
$s=(\epsilon\cdot q)/p$. As a consequence, we rely on two roundings tailored
to $v$ and $w$, where rounding errors can be interpreted as small subsidies to
support a trade.

More formally, suppose there is an _exact trade_ of edge set $C$ achieving
asset level _exactly_ $A$ for $v$. By repeating our arguments for Lemma 4.6 we
see that the return must be equal to the differences in assets emerging at
both $v$ and $w$, i.e.,

$\sum_{e\in C}\rho_{e}=d_{v}^{\text{sp}}=d_{w}^{\text{sp}}>0\;.$

Therefore, equation (1) must again hold, which is independent of the traded
set $C$ – but depends on the asset level $A$ and the resulting payments
$p^{\prime}_{e}$. Unfortunately, fixed returns destroy the monotonicity
property w.r.t. $A$ from Lemma 3.8, since the property crucially relies on
adjusting returns for smaller values of $A$ (c.f. B.1). This also complicates
searching for an optimal asset level $A$, since our adjustment of binary
search is not applicable.

Instead, for our FPTAS, we define a step size $s=\sum_{e\in
E^{-}(v)}\ell_{e}\cdot\delta/n$, for any $\delta>0$. We iterate over all asset
values $\hat{A}=a_{v}+i\cdot s$, for $i=1,\ldots,n/\delta$, which is
polynomial in the network size and $1/\delta$. Note that we can set $\delta$
as a _polynomially_ small precision parameter (in contrast to exponentially
small precision via binary search for variable returns above).

Now suppose there exists an exact trade with asset level $A$. Consider
$\hat{A}$ as the unique value with $A\leq\hat{A}<A+s$, and $\hat{p}^{\prime}$
as the payments in $\mathcal{F}^{sp}$ with outgoing assets $\hat{A}$ for $v$.
Due to monotonicity, for all $e\in E$ we have $\hat{p}^{\prime}_{e}\geq
p^{\prime}_{e}$, the payments resulting from outgoing assets $A$ for $v$.
Thus,

$\displaystyle\sum_{e\in
C}\rho_{e}=d_{v}^{\text{sp}}=A-\left(a_{v}^{x}+\sum_{e\in E^{-}(v)\setminus
C}p_{e}^{\prime}\right)\;\geq\;\hat{A}-s-\left(a_{v}^{x}+\sum_{e\in
E^{-}(v)\setminus C}\hat{p}^{\prime}_{e}\right)$

and

$\displaystyle\sum_{e\in
C}\rho_{e}=d_{w}^{\text{sp}}=\left(a_{w}^{x}+\sum_{e\in E^{-}(w)\cup
C}p_{e}^{\prime}\right)-a_{w}\;\leq\;\left(a_{w}^{x}+\sum_{e\in
E^{-}(v)\setminus C}\hat{p}^{\prime}_{e}\right)-a_{w}$

Now let $r_{e}=\rho_{e}-\hat{p}^{\prime}_{e}$ be the net payments333Observe
that $C$ might be required to include edges for which $r_{e}$ is negative! B.1
received by $v$ from $w$ for $e\in C$. Then

$\displaystyle\sum_{e\in C}r_{e}$
$\displaystyle\geq\hat{A}-s-a_{v}^{x}-\sum_{e\in
E^{-}(v)}\hat{p}_{e}^{\prime}$ (4) $\displaystyle\sum_{e\in C}r_{e}$
$\displaystyle\leq a_{w}^{x}+\sum_{e\in
E^{-}(w)}\hat{p}_{e}^{\prime}-a_{w},\text{ and}$ (5) $\displaystyle\sum_{e\in
C}\rho_{e}$ $\displaystyle\leq a_{w}^{x},\text{ the standard bound on return
payments.}$ (6)

When considering a rounded asset level $\hat{A}$, an exact trade for that
asset level might not exist. Our construction shows that if an exact trade
exists for level $A$, then an _approximate trade_ exists for the next-higher
level $\hat{A}$. An approximate trade is one that satisfies (4)-(6). It
achieves asset level $\hat{A}$ for $v$, but only assets of at least
$\hat{A}-s$ must be obtained using return payments from $w$ (with a total
amount of at most $a_{w}^{x}$). Thus, a set $C$ that satisfies (4)-(6)
represents an exact trade after a subsidy of (at most) $s$.

For fixed asset level $\hat{A}$, the system (4)-(6) gives rise to a Knapsack
problem444More precisely, the system (4)-(6) represents the decision problem
of an instance of the 2-dimensional Knapsack problem. and remains NP-hard to
solve. Towards a Level-FPTAS, we introduce a second step size
$s^{\prime}=\sum_{e\in E^{-}(v)}|r_{e}|\cdot\delta/n^{2}$. Observe that
$n\cdot s^{\prime}\leq s$. Then, for each $e\in E$, we round all values of
$r_{e}$ (1) up to the next multiple of $s^{\prime}$ to obtain $r_{e}^{+}$, and
(2) down to the next multiple of $s^{\prime}$ to obtain $r_{e}^{-}$. For
simplicity, the Level-FPTAS again follows closely the standard Knapsack
template. We fill a dynamic programming table with entries for all triples in

$\displaystyle\\{1,2,\ldots,|E^{-}(v)|\\}$
$\displaystyle\times\left\\{-\sum_{e\in
E^{-}(v)}|r_{e}^{+}/s^{\prime}|,\ldots,-1,0,1,\ldots,\sum_{e\in
E^{-}(v)}|r_{e}^{+}/s^{\prime}|\right\\}$
$\displaystyle\times\left\\{-\sum_{e\in
E^{-}(v)}|r_{e}^{-}/s^{\prime}|\ldots,-1,0,1,\ldots,\sum_{e\in
E^{-}(v)}|r_{e}^{-}/s^{\prime}|\right\\}$

This table has $O(n\cdot(n^{2}/\delta)^{2})$ many entries. In each entry
$DP(i,x,y)$, we store the minimum amount of return payment required to
implement any trade with edges from
$C\subseteq\\{e_{1},\ldots,e_{i}\\}\subseteq E^{-}(v)$ that has $\sum_{e\in
C}r_{e}^{+}=x\cdot s^{\prime}$ and $\sum_{e\in C}r_{e}^{-}=y\cdot s^{\prime}$.
The update of entry $(i,x,y)$ is clearly

$DP(i,x,y)=\min\\{DP(i-1,x-(r_{e_{i}}^{+}/s^{\prime}),y-(r_{e_{i}}^{-}/s^{\prime}))+\rho_{e_{i}},DP(i-1,x,y)\\}$

with a base case of
$DP(1,(r_{e_{1}}^{+}/s^{\prime}),(r_{e_{1}}^{-}/s^{\prime}))=\rho_{e_{1}}$ and
$DP(1,x,y)=\infty$ otherwise. We search for a solution by inspecting the
entries $(|E^{-}(v)|,x,y)$ such that $x\cdot
s^{\prime}\geq\hat{A}-s-a_{v}^{x}-\sum_{e\in E^{-}(v)}\hat{p}_{e}^{\prime}$
and $y\cdot s^{\prime}\leq a_{w}^{x}+\sum_{e\in
E^{-}(w)}\hat{p}_{e}^{\prime}-a_{w}$ for one that has value at most
$a_{w}^{x}$. If there is such an entry, then we found an approximate solution
to (4) and (5) that exactly satisfies (6). The corresponding trade $C$
violates the each of the constraints (4) and (5) by at most $|C|\cdot
s^{\prime}<s$. As such, we need to subsidize $v$ by at most another $s$ and
subsidize $w$ by at most $s$ to obtain feasible conditions for an exact trade
w.r.t. $\hat{A}$.

Hence, a solution $C$ for the Level-FPTAS for a given asset level $\hat{A}$
yields an exact trade with asset level at least $\hat{A}$ for $v$ when we give
subsidies of at most $2s$ to $v$ and at most $s$ to $w$. We call such a trade
_$\delta$ -subsidized_. Now if the instance allows an exact trade $C$ with
optimal assets $A^{*}$ for $v$, then $C$ also represents a $\delta$-subsidized
trade with the corresponding subsidies and asset level $\hat{A}\geq A^{*}$ for
$v$. As such, by running our Level-FPTAS for all (polynomially many) values of
$\hat{A}$, we obtain a 0-optimal $\delta$-subsidized trade. The running time
is clearly polynomial in the representation of $\mathcal{F}$ and $1/\delta$.

######  Theorem B.4.

Consider a financial network with monotone payment functions and efficient
clearing oracle, creditor $v$ and buyer $w$. If there exists a creditor-
positive multi-trade of incoming edges, then an $\delta$-subsidized 0-optimal
trade with subsidies can be computed in time polynomial in the size of
$\mathcal{F}$, and $1/\delta$, for every $\delta>0$.

###  B.3 Multi-Trades of Outgoing Edges

Consider a financial network with banks $u$ and $w$ where every outgoing edge
$e\in E^{+}(u)$ of $u$ is assigned a predetermined haircut rate
$\alpha_{e}\in[0,1]$. For a given subset of outgoing edges $C\subseteq
E^{+}(v)$, the goal is to decide whether $C$ together with
$\bm{\alpha}=(\alpha_{i})_{e_{i}\in C}$ is a Pareto-positive multi-trade. If
the clearing state of the network can be derived efficiently, e.g., via a
given efficient clearing oracle, the problem lies in P. First, verify if $w$
is able to fund the return, i.e., $a^{x}_{w}\geq\sum_{e_{i}\in
C}\alpha_{i}\cdot\ell_{e_{i}}$. Then, perform the given multi-trade, derive
the resulting clearing state $\mathbf{p}$ and check whether $w$ is not harmed
while all creditors strictly profit, i.e., $a^{\prime}_{w}\geq a_{w}$ and
$a^{\prime}_{v_{i}}>a_{v_{i}}$ for all $v_{i}$ with an incoming edge $e_{i}\in
C$.

The problem becomes more challenging if the set of trading edges is not fixed
but can be chosen as part of the solution. Formally, we are given a financial
network with monotone payment functions and efficient clearing oracle.
Consider banks $u$ and $w$ and haircut rates $\bm{\alpha}$ for all outgoing
edges of $u$. The objective is to compute a set $C\subseteq E^{+}(v)$ such
that (1) the multi-trade $C$ together with $\bm{\alpha}$ is Pareto-positive
and (2) maximizes the sum of profits of $u$’s creditors. This problem is
denoted by Outgoing-FR.

######  Theorem B.5.

Outgoing-FR is strongly NP-hard. For any constant $\varepsilon>0$, there
exists no efficient $n^{1/2-\varepsilon}$-approximation algorithm unless P =
NP.

######  Proof B.6.

We show the statement by slightly adapting the proof of Theorem 5.2.

For an instance of Set Packing, construct a corresponding financial network as
described in proof of Theorem 5.2 and depicted in Figure 2. Fix all haircut
rates to 1. Then there exists a feasible set packing of size at least $k$ if
and only if there exists a Pareto-positive multi-trade in the corresponding
network where $v$’s creditors profit by at least $kM$ in total.

Conceptually, a fixed haircut rate of 1 implies that each creditor $S_{i}$ of
a traded edge fully pays all outgoing edges, independent of the payment
function used for clearing. As such, sufficiently large payments can only
feasibly flow back throught the gadget to $w$ if the traded edges correspond
to non-overlapping sets. This is the key property that was implemented in
Theorem 5.2 by placing an edge of large liability $M$ towards $w$ in the last
position of the edge ranking of each bank $S_{i}$.

As a consequence, the arguments in the proofs of Theorem 5.2 can be repeated
almost verbatim to obtain the same results for fixed haircut rates and
arbitrary monotone clearing.