betaFeedback

WorksComputer Science

Payment Scheduling in the Interval Debt Model

Abstract

The network-based study of financial systems has received considerable attention in recent years but has seldom explicitly incorporated the dynamic aspects of such systems. We consider this problem setting from the temporal point of view and introduce the Interval Debt Model (IDM) and some scheduling problems based on it, namely: Bankruptcy Minimization/Maximization, in which the aim is to produce a payment schedule with at most/at least a given number of bankruptcies; Perfect Scheduling, the special case of the minimization variant where the aim is to produce a schedule with no bankruptcies (that is, a perfect schedule); and Bailout Minimization, in which a financial authority must allocate a smallest possible bailout package to enable a perfect schedule. We show that each of these problems is NP-complete, in many cases even on very restricted input instances. On the positive side, we provide for Perfect Scheduling a polynomial-time algorithm on (rooted) out-trees although in contrast we prove NP-completeness on directed acyclic graphs, as well as on instances with a constant number of nodes (and hence also constant treewidth). When we allow non-integer payments, we show by a linear programming argument that the problem Bailout Minimization can be solved in polynomial time.

Introduction

A natural problem in the study of financial networks is that of whether and where a failure will occur if no preventative action is taken. We focus specifically on the flexibility that financial entities are afforded as regards the precise timing of their outgoings and for this purpose introduce the Interval Debt Model (IDM) in which a set of financial entities is interconnected by debts due within specific time intervals. In the IDM, a payment schedule specifies timings of payments to serve the debts. We examine the computational hardness of determining the existence of a schedule of payments with “good” properties, e.g., no or few bankruptcies, or minimizing the scale of remedial action. In particular, we establish how hardness depends on variations in the exact formalism of the model (to allow some small number of bankruptcies or insist on none at all) and on restrictions on the structure or lifetime of the input instance. A unique and novel feature of the IDM is its capacity to capture the temporal aspects of real-world financial systems; previous work has seldom explicitly dealt with this intrinsic facet of real-world debt.

Financial Networks

Graph theory provides models for many problems of practical interest for analyzing (or administering) financial systems. For example, Eisenberg and Noe’s work [1] abstracts a financial system to be a weighted digraph (in which each node is additionally labeled according to the corresponding entity’s assets). The authors of that work are focused on the existence and computation of a clearing vector, which is essentially a set of payments among nodes of the graph which can be executed synchronously without violating some validity constraints. Their model provides the basis for much subsequent work in the network-based analysis of financial systems: it has been adapted to incorporate default costs [2], Credit Default Swaps [3] (CDSs) (that is, derivatives through which banks can bet on the default of another bank in the system) and the sequential behavior of bank defaulting in real-world financial networks [4].

An axiomatic aspect of Eisenberg and Noe’s model is the so-called principle of proportionality: that a defaulting bank pays off each of its creditors proportionally to the amount it is owed. Some recent work has considered alternative payment schemes, which allow, for example, paying some debts in full and others not at all (so-called non-proportional payments). For example, Bertschinger, Hoefer and Schmand [5] study financial networks in a setting where each node is a rational agent which aims to maximize flow through itself by allocating its income to its debts. The focus of that work is on game-theoretic questions, such as the price of anarchy, or the existence, properties, and computability of equilibria. Papp and Wattenhoffer [6] also study a non-proportional setting, additionally incorporating CDSs.

Complementing the decentralized, game-theoretic approach is the question of the (centralized) computability of a globally “good” outcome through bailout allocation [7] (also called cash injection [8]), or timing default announcements [4], among other operations. In such works, the prototypical objective is to minimize the number of bankruptcies; related measures include total market value [7], or systemic liquidity [8]. Egressy and Wattenhoffer [7] focus solely on computational complexity of leveraging bailouts to optimize a range of objectives, in a setting which incorporates proportional payments and default costs. Kanellopoulos, Kyropoulou and Zhou [8, 9] apply both a game-theoretic and a classical complexity perspective to two mechanisms: debt forgiveness (deletion of edges in the financial network) and cash injection (bailouts). Notably, in this work the central authority may remove debts in a way which may be detrimental to certain individuals, but beneficial to the total systemic liquidity.

Previous research on financial networks has also drawn from ecology [10], statistical physics [11] and Boolean networks [12].

A central motivation of financial network analysis is to inform central banks’ and regulators’ policies. The concepts of solvency and liquidity are core to this task: a bank is said to be solvent if it has enough assets (including, e.g., debts owed to it) to meet all its obligations; and it is said to be liquid if it has enough liquid assets (that is, cash) to meet its obligations on time. An illiquid but solvent bank may exist even in modern interbank markets [13]. In such cases, a central bank may act as a lender of last resort and extend loans to such banks to prevent them defaulting on debts [13, 14]. The optimal allocation of bailouts to a system in order to minimize damage has also been studied as an extension of Eisenberg and Noe’s model [15]. Here, bailouts refer to funds provided by a third party (such as a government) to entities to help them avoid bankruptcy.

Temporal Graphs

Temporal graphs are graphs whose underlying connectivity structure changes over time. Such graphs allow us to model real-world networks which have inherent dynamic properties, such as transportation networks [16], contact networks in an epidemic [17, 18] and communication networks; for an overview see [19, 20]. Most commonly, following the formulation introduced by Kempe, Kleinberg and Kumar [21], a temporal graph has a fixed set of vertices together with edges that appear and disappear at integer times up to an (integer) lifetime. Often, a natural extension of a problem on static graphs to the temporal setting yields a computationally harder problem; for example, finding node-disjoint paths in a temporal graph remains NP-complete even when the underlying graph is itself a path [22], and finding a temporal vertex cover remains NP-complete even on star temporal graphs [23].

Contributions

In this paper we present a novel framework, the Interval Debt Model (IDM), for considering problems of bailout allocation and payment scheduling in financial networks by using temporal graphs to account for the isochronal aspect of debts between financial entities (previous work has almost exclusively focused on static financial networks). In particular, the IDM offers the flexibility that entities can pay debts earlier or later, within some agreed interval. We introduce several natural problems and problem variants in this model and show that the tractability of such problems depends greatly on the network topology and on the restrictions on payments (i.e., the admission or exclusion of partial and fractional payments on debts).

Our work explores the natural question of whether and how payments can be scheduled to avert large-scale failures in financial networks. Broadly, we establish that computing a zero-failure schedule (a perfect schedule) is NP-complete even when the network topology is highly restricted, unless we admit fractional payments, in which case determining the existence of a perfect schedule is tractable in general. Interestingly, if we allow a small number kk of bankruptcies to occur then every problem variant is computationally hard even on inputs with O(1)O(1) nodes. This can be thought of analogously to Max 2SAT being strictly harder than 2SAT (unless P=NP) despite being a “relaxation”: in Max 2SAT we allow up to kk clauses to not be satisfied. Furthermore, in the setting where we insist not only on payments being for integer amounts but more strongly that any payment is for the full amount of the corresponding debt, finding a perfect schedule is NP-complete even if there are only four nodes.

We begin by introducing, first by example and then formally, the Interval Debt Model in § 2. In § 3 we present our results: in § 3.1–§ 4.1 we establish some sufficient criteria for NP-hardness for each of the problems we consider; and in § 4.3 we present two polynomial-time algorithms. Our conclusions and directions for further research are given in § 5.

The Interval Debt Model

In this section, we introduce (first by example and then formally) the Interval Debt Model, a framework in which temporal graphs are used to represent the collection of debts in a financial system.

An illustrative example

As an example, consider a tiny financial network consisting of the 3 banks uu, vv and ww with €30, €20 and €10, respectively, in initial external assets and where there are the following inter-bank financial obligations:

  • bank uu owes bank vv €20 which it must pay by time 3 and €15 which it must pay at time 4 or time 5 (note that all payments must be made at integer times)

  • bank vv must pay bank ww a debt of €25 at time 2 exactly

  • bank ww must pay €25 to bank vv between times 4 and 6 (that is, at time 4, 5 or 6).

A graphical representation of this system is shown in Figure 1 (the descriptive notation used should be obvious and is retained throughout the paper).

A simple instance of the Interval Debt Model

Figure 1. A simple instance of the Interval Debt Model (IDM). Numbers in square boxes represent the initial external assets of the node (for example, €30 for node uu), directed edges represent debts, and the label on an edge represents the terms of the associated debt (for example, uu must pay vv €20 between time 1 and time 3).

Several points can be made about this system: node uu is insolvent as its €30 in initial external assets are insufficient to pay all its debts; node vv may be illiquid for it may default on part of its debt to ww, e.g., if uu pays all of its first debt at time 3, or may remain liquid, e.g., if it receives at least €5 from uu by time 2; and node ww is solvent and certain to remain liquid in any case. The choices made by the various banks, in the form of a (payment) schedule, clearly affect the status of the overall financial system. Note that solvency is determined solely by whether sufficient funds exist whereas liquidity depends upon when debts are paid and owed.

One may ask several questions about our toy financial system such as: Are partial payments allowed (e.g., uu paying €18 of the €20 debt at time 1, and the rest later)? If so, are non-integer payments allowed? Can money received be immediately forwarded (e.g., uu paying vv €20 at time 2 and vv paying ww €25 at time 2)? Does vv necessarily have to pay its debt to ww at time 2 if it has the liquid assets to do so? We now expand upon these questions and specify in detail the setting we consider in the remainder of the paper. Note that throughout the paper we use the euro € as our monetary unit of resource even though, as we will see, we have a variant of the Interval Debt Model within which payments can be made for any rational fraction of a euro. We often prefix monetary payments with the symbol € to make our proofs more readable.

Formal setting

Formally, an Interval Debt Model (IDM) instance is a 3-tuple (G,D,A0)(G,D,A^0) as follows.

  • G=(V,E)G=(V,E) is a finite digraph with the set of nn nodes (or, alternatively, banks) V={vi:i=1,2,…,n}V=\{v_i : i=1,2,\ldots,n\} and the set of mm directed labelled edges E⊆V×V×NE\subseteq V\times V\times\mathbb{N}, with the edge (u,v,id)∈E(u,v,id)\in E denoting that

there is an edge, or debt, whose label is idid, from the debtor uu to the creditor vv. We can have multi-edges but the labels of the edges from some node uu to some node vv must be distinct and form a contiguous integer sequence 0,1,2,…0,1,2,\ldots. We refer to the subset of edges directed out of or in to some specific node vv by Eout(v)E_{\mathrm{out}}(v) and Ein(v)E_{\mathrm{in}}(v), respectively. We also refer to the undirected graph obtained from GG by ignoring the orientations on directed edges as the footprint of GG.

  • D:E→{(a,t1,t2):a,t1,t2∈N∖{0},t1≤t2}D:E\to\{(a,t_1,t_2):a,t_1,t_2\in\mathbb{N}\setminus\{0\},t_1\le t_2\} is the debt function which associates terms to every debt (ordinarily, we abbreviate D((u,v,id))D((u,v,id)) as D(u,v,id)D(u,v,id)). Here, if ee is a debt with terms D(e)=(a,t1,t2)D(e)=(a,t_1,t_2) then aa is the monetary amount (or monetary debt) to be paid and t1t_1 (resp. t2t_2) is the first (resp. last) time at which (any portion of) this amount can be paid. For any debt e∈Ee\in E, we also write D(e)=(Da(e),Dt1(e),Dt2(e))D(e)=(D_a(e),D_{t_1}(e),D_{t_2}(e)). For simplicity of notation, we sometimes denote the terms D(e)=(a,t1,t2)D(e)=(a,t_1,t_2) by a@[t1,t2]a@[t_1,t_2] or by a@t1a@t_1 when t1=t2t_1=t_2 (as we did in Figure 1); also, for simplicity, we sometimes just refer to a@[t1,t2]a@[t_1,t_2] as the debt.

  • A0=(cv10,cv20,…cvn0)∈NnA^0=(c^0_{v_1},c^0_{v_2},\ldots c^0_{v_n})\in\mathbb{N}^n is a tuple with cvi0c^0_{v_i} denoting the initial external assets (i.e. starting cash) of bank viv_i.

We refer to the greatest time-stamp TT that appears in any debt for a given instance as the lifetime and assume that all network activity ceases after time TT. The instance shown in Figure 1, which has lifetime T=6T=6, is formally given by: V={u,v,w}V=\{u,v,w\}, E={(u,v,0),(u,v,1),(v,w,0),(w,v,0)}E=\{(u,v,0),(u,v,1),(v,w,0),(w,v,0)\}, D(u,v,0)=(20,1,3)D(u,v,0)=(20,1,3), D(u,v,1)=(15,4,5)D(u,v,1)=(15,4,5), D(v,w,0)=(25,2,2)D(v,w,0)=(25,2,2), D(w,v,0)=(25,4,6)D(w,v,0)=(25,4,6) and A0=(cu0,cv0,cw0)A^0=(c^0_u,c^0_v,c^0_w), where cu0=30c^0_u=30, cv0=20c^0_v=20 and cw0=10c^0_w=10. Similarly, the instance shown in Figure 2 has lifetime T=2T=2 and is given by V={u,v,w}V=\{u,v,w\}, E={(u,v,0),(v,w,0)}E=\{(u,v,0),(v,w,0)\}, D(u,v,0)=(1,1,2)D(u,v,0)=(1,1,2), D(v,w,0)=(1,1,1)D(v,w,0)=(1,1,1) and A0=(cu0,cv0,cw0)A^0=(c^0_u,c^0_v,c^0_w), where cu0=1c^0_u=1, cv0=0c^0_v=0 and cw0=0c^0_w=0.

IDM instance graph

Figure 2. An IDM instance for which every schedule is described by four payment values p(u,v,0)1p^1_{(u,v,0)}, p(v,w,0)1p^1_{(v,w,0)}, p(u,v,0)2p^2_{(u,v,0)} and p(v,w,0)2p^2_{(v,w,0)}.

The size of the instance (G,D,A0)(G,D,A^0) is defined as n+m+log⁡(T)+bn+m+\log(T)+b, where bb is the maximum number of bits needed to encode any of the (integer) numeric values appearing as the monetary amounts in the debts. Note that in what follows, we usually do not mention the label idid of a debt (u,v,id)(u,v,id) but just refer to the debt as (u,v)(u,v) when this causes no confusion.

Schedules

References

  1. [1]Eisenberg, L., Noe, T.H.: Systemic risk in financial systems. Management Science 47(2), 236–249 (2001)DOI
  2. [2]Rogers, L.C., Veraart, L.A.: Failure and rescue in an interbank network. Management Science 59(4), 882–898 (2013)DOI
  3. [3]Schuldenzucker, S., Seuken, S., Battiston, S.: Finding clearing payments in financial networks with credit default swaps: PPAD-complete. In: 8th Innovations in Theoretical Computer Science Conference, ITCS. LIPIcs, vol. 67 (2017)
  4. [4]Papp, P.A., Wattenhofer, R.: Sequential defaulting in financial networks. In: 12th Innovations in Theoretical Computer Science Conference, ITCS. LIPIcs, vol. 185 (2021)
  5. [5]Bertschinger, N., Hoefer, M., Schmand, D.: Flow allocation games. Mathematics of Operations Research (2024)arxiv.org/abs/1908.01714
  6. [6]Papp, P.A., Wattenhofer, R.: Network-Aware Strategies in Financial Systems. In: ICALP 2020, vol. 168 (2020). https://doi.org/10.4230/LIPIcs.ICALP.2020.91
  7. [7]Egressy, B., Wattenhofer, R.: Bailouts in financial networks. CoRR abs/2106.12315 (2021) 2106.12315arxiv.org/abs/2106.12315
  8. [8]Kanellopoulos, P., Kyropoulou, M., Zhou, H.: Forgiving debt in financial network games. In: IJCAI-22 (2022). https://doi.org/10.24963/ijcai.2022/48
  9. [9]Kanellopoulos, P., Kyropoulou, M., Zhou, H.: On priority-proportional payments in financial networks. Theoretical Computer Science 1014, 114767 (2024) https://doi.org/10.1016/j.tcs.2024.114767
  10. [10]Haldane, A.G., May, R.M.: Systemic risk in banking ecosystems. Nature 469(7330), 351–355 (2011)DOI
  11. [11]Bardoscia, M., Barucca, P., Battiston, S., Caccioli, F., Cimini, G., Garlaschelli, D., Saracco, F., Squartini, T., Caldarelli, G.: The physics of financial networks. Nature Reviews Physics 3(7), 490–507 (2021)DOI
  12. [12]Eisenberg, L.: A summary: Boolean networks applied to systemic risk. Neural Networks in Financial Engineering, 436–449 (1996)
  13. [13]Rochet, J.-C., Vives, X.: Coordination failures and the lender of last resort: was Bagehot right after all? Journal of the European Economic Association 2(6), 1116–1147 (2004)
  14. [14]Bagehot, W.: Lombard Street: a Description of the Money Market. HS King & Company, London (1873)
  15. [15]Papachristou, M., Kleinberg, J.: Allocating stimulus checks in times of crisis. In: Proceedings of the ACM Web Conference 2022, pp. 16–26 (2022)DOI
  16. [16]Tesfaye, B., Augsten, N., Pawlik, M., Böhlen, M., Jensen, C.: Speeding up reachability queries in public transport networks using graph partitioning. Information Systems Frontiers 24, 11–29 (2022)DOI
  17. [17]Enright, J., Meeks, K., Mertzios, G.B., Zamaraev, V.: Deleting edges to restrict the size of an epidemic in temporal networks. Journal of Computer and System Sciences 119, 60–77 (2021)arxiv.org/abs/1805.06836
  18. [18]Kutner, D.C., Larios-Jones, L.: Temporal reachability dominating sets: Contagion in temporal graphs. In: Georgiou, K., Kranakis, E. (eds.) Algorithmics of Wireless Networks, pp. 101–116. Springer, Cham (2023)
  19. [19]Holme, P., Saramäki, J. (eds.): Temporal Networks. Springer, London (2013)
  20. [20]Michail, O.: An introduction to temporal graphs: An algorithmic perspective. Internet Mathematics 12(4), 239–280 (2016)
  21. [21]Kempe, D., Kleinberg, J.M., Kumar, A.: Connectivity and inference problems for temporal networks. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC), pp. 504–513 (2000)
  22. [22]Klobas, N., Mertzios, G.B., Molter, H., Niedermeier, R., Zschoche, P.: Interference-free walks in time: Temporally disjoint paths. In: Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), pp. 4090–4096 (2021)
  23. [23]Akrida, E.C., Mertzios, G.B., Spirakis, P.G., Zamaraev, V.: Temporal vertex cover with a sliding time window. Journal of Computer and System Sciences 107, 108–123 (2020)arxiv.org/abs/1802.07103
  24. [24]Audience participation at the Cambridge LIPNE Workshop on Computational complexity and economic decision making (2024)
  25. [25]Tovey, C.A.: A simplified NP-complete satisfiability problem. Discrete Applied Mathematics 8, 85–89 (1984)DOI
  26. [26]Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations. The IBM Research Symposia Series, pp. 85–103. Plenum Press, New York, New York (1972)
  27. [27]Garey, M.R., Johnson, D.S. (eds.): Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, United States (1979)

Paper details

vlnc:W_rp3hn9bg
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents