Optimization proposals to the payment clearing

1.   Introduction

Trade has represented one of the main reasons of humankind economic development and is nowadays, one of the most important reasons of our well-being. It became, as many other traditional concepts, more complex through the evolution of time and the market, the place where the trade takes place, became a nest of deep and complex transactions.

Contemporary economic trade, agreements and the mechanisms that hold them have, in part, become considerably complex due to the different specific technological, social, financial and logistical features of current economic environment but also to the high and varied amount of transactions taking part in the system. The system that holds all these transactions, operations and exchanges between the parties can be referred to as a market.

In these circumstances, the market main purpose is to be the container where all the commercial transactions, and, therefore, payments take place and go through. This connection mechanism role of the market lets parties to engage into an exchange process, in which basically goods or services are exchanged by money. The exchange, also referred to as trade, is simplified to occur with goods or services being exchanged by money, however, in the real world, money can be any tradable commodity and the goods or services can be anything tangible or intangible with subjective value.

As a consequence of the high amount of transactions taking place in the different types of markets and between markets, some payment compensation logistical problems appeared and with them some innovations emerged. One of these innovations was the multilateral netting service, traditionally implemented in central bank payments or by the clearing houses of some derivative markets.

The multilateral netting, or clearing, tries to add up all the payments, and then unifies them into one unique cleared payment, of debits and credits, between the different parties involved and finally compensates them, rather than performing payments in a one by one basis as in the real time gross settlements mechanisms. Even though, the advantages of multilateral netting are really useful, they are not particularly popular outside the clearing houses, international payments or interbank payments.

On the other hand, the use of digital currencies to multilaterally net payments can considerably improve the netting process and their advantages against paper based currencies are specially evidenced in the logistical process to settle an obligation. For this reason, all the payment mechanisms exposed in this paper are suitable and will be assumed for digital currencies, since implementing them using paper based currencies is logistically more difficult than using digital currencies.

Finally, we will see how the research findings will be extracted by borrowing a series of concepts based on pure graph theory concepts. We will use them in a market context with a financial interpretation useful to understand the multilateral payment scenarios, and, finally, we will define two multilateral set-off payments based on the max-flow-min-cost principle and the max-flow-all-edges principle—both centralized clearings as contrasted in (Cso´ka and Jean-Jacques, 2018). These two methods to be introduced can be used to reduce the amount of transactions in a market while keeping compensations and, therefore, be used in uncountable hypothetical scenarios —possibly even a financial contagion (Calafiore et al., 2021).

2.   Materials and method

2.1.   Payment and market nature

The payment, as defined in the introduction, is the action of transferring money, goods or services in exchange for money, goods or services in a manner previously defined and agreed. The payment, therefore, will be defined to consist of two, or more, parties that are connected by the payment agreement in a system referred to as the market.

The following concepts and notation will be frequently used in the paper (if not explicitly stated otherwise):

● The market of payments, or simply referred to as the market, will be considered to be the monetary system area in which all the different transactions take place in a specific range of time (e.g. One hour, One month, one year, etc.) and inside a specific framework (e.g. A country, trade bloc with shared monetary union, custom unions with shared monetary union, etc...). Mathematically, the market will be considered to be represented as a connected graph and the market and graph concepts might be interchangeably used or to reference each other.

● Payment payees and payers will be both mathematically considered as graph nodes, and they can be a person, a firm, a bank or any other party able to give, receive or give and receive a payment at the same time in the market.

● Payment transactions with no specified payer or payee will be referred to as undirected payment transactions or, mathematically, edges in the graph.

● Payment transactions with specified payer and payee will be referred to as directed payment transactions or, mathematically, arcs in the graph.

The graph theory pure concepts, in this paper adapted to the concepts of markets, payments and parties, were inspired by similar concepts used in Wilson et al. (1979).

For any two matrices ${\textbf{X}}, {\textbf{Y}} \in \mathbb{R}^{m \times n}$, where ${\textbf{X}}_{ij}, {\textbf{Y}}_{ij}$ are their $ij$-th matrix elements respectively, the notation $^{+}, ^{-}$ will be used with and between matrices as follows:

Note also that the following equation is true:

Notations used in equations 1, 2 and 3 are strictly limited to the use of matrices, so the notation does not apply when ${\boldsymbol{X}}$ or ${\boldsymbol{Y}}$ are sets or any other mathematical figure that are not matrices.

2.2.   Undirected simple payment

Undirected simple payments in a market $G$ will be considered to be edges in a graph $G$ made of a non-empty finite set $N(G)$ of nodes and a finite set $E(G)$ of distinct unordered pairs of distinct elements of $N(G)$, referred to as edges. Note $N(G)$ is the node set, $E(G)$ the edge set and $G(N(G), E(G))$. Finally, an edge $\{a, b\}$ is said to connect the nodes $a$ and $b$ and will be abbreviated as $ab$, so $\{a, b\} = \{b, a\} = ab = ba$.

Example 1 Let's imagine a payment scenario with four firms in which firm $a$ is involved into one payment transaction with firm $b$, firm $b$ with firm $c$ and firm $c$ with firm $a$ and firm $d$ in a market $G$. Then, $N(G) = \{a, b, c, d\}$ and $E(G) = \{ab, bc, ca, cd\}$.

Undirected simple payments represent the most primitive and simple payment transaction in this paper. Furthermore, the undirected payment, by definition, does not contemplate multiple transactions (more than one transaction) payments between two parties and, therefore, firm $d$ in Example 1 cannot have an additional payment transaction with firm $c$.

To solve the multiple payment transaction limitation in the undirected simple payment, the general payment concept will be introduced (and note it is a slightly extended version of the undirected simple payment).

2.3.   Undirected general payment

Undirected general payments in a market $G$ will be considered to be edges in a multigraph $G$ formed by a non-empty finite set $N(G)$ of nodes and a finite multiset $E(G)$ of unordered pairs of different elements of $N(G)$. The elements of $E(G)$ cannot contain identical pairs of $E(G)$, in other words, self-loops are not allowed by definition in this payment method nor in any of the definitions proposed along all the paper. Note, the undirected simple payment differs from this payment definition because it does not allow multiple payment transactions between two parties as this payment method does.

Example 2 Let's imagine a payment scenario with four persons in which person $a$ is involved into two, parallel, payment transactions with person $b$, person $b$ with person $c$ and person $c$ with person $a$ and person $d$ in a market $G$. Then, $N(G) = \{a, b, c, d\}$ and $E(G) = \{ab, ab, bc, ca, cd\}$. Note $E(G) = \{ab, ab, bc, ca, cd\} = \{ba, ba, cb, ac, dc\}$ since $E(G)$ is unordered, it does not specify the payer nor the payee.

2.4.   Directed simple payment

Directed simple payments in a market $G$ will be considered to be arcs in a digraph $G$ made of a non-empty finite set $N(G)$ of nodes and a finite set $E(G)$ of distinct ordered pairs of distinct elements of $N(G)$, referred to as arcs. Note $N(G)$ is the node set and $E(G)$ is the arc set and $G(N(G), E(G))$. The main difference with the undirected payments is that the directed payment specifies who is the payer and who the payee and that is why the pair elements of $E(G)$ are ordered.

Example 3 Let's imagine a payment scenario with four firms in which firm $a$ does a payment transaction to firm $b$, firm $b$ to firm $c$ and firm $c$ to firm $a$ and firm $d$ in a market $G$. Then, $N(G) = \{a, b, c, d\}$ and $E(G) = \{ab, bc, ca, cd\}$. Note $E(G) = \{ab, bc, ca, cd\} \neq \{bc, ab, cd, ca\}$ because the pair elements of $E(G)$ are ordered, so now it is specified who is the payer and who the payee.

2.5.   Directed general payment

Directed general payments in a market $G$ will be considered to be arcs in a directed multigraph $G$ formed by a non-empty finite set $N(G)$ of nodes and a finite multiset $E(G)$ of ordered pairs of different elements of $N(G)$. The elements of $E(G)$, again, cannot contain identical pairs of $E(G)$. Note, the directed simple payment differs from this payment definition because it does not allow multiple payment transactions between two parties as this payment method does.

Example 4 Let's imagine a payment scenario with four persons in which person $a$ does a payment transaction to person $b$, $b$ to $a$, $b$ to $c$, $c$ to $b$, $c$ to $d$, $d$ to $a$ and $a$ to $d$ in a market $G$. Then, $N(G) = \{a, b, c, d\}$ and $E(G) = \{ab, ba, bc, cb, cd, dc, da, ad\}$.

2.6.   Payment quantification

Summing up the different payments explained so far:

● Undirected simple payment is a payment in which the payer and the payee are not defined and in which multilateral payments are not allowed.

● Undirected general payment is a payment in which the payer and the payee are not defined and in which multilateral payments are allowed.

● Directed simple payment is a payment in which the payer and the payee are defined and in which multilateral payments are not allowed.

● Directed general payment is a payment in which the payer and the payee are defined and in which multilateral payments are allowed.

As we observe, the payments explained so far, do not specify in any way the amount to be paid nor the amount to be received by the payer and the payee respectively. To solve this problem, the concepts of the adjacency payment matrix, the undirected payment incidence matrix will be introduced to help label the graph, more specifically the payments, so the amount to be paid or received is quantified while keeping defined the payee and the payee.

2.7.   Undirected payment adjacency matrix

The Undirected payment adjacency matrix represents the relationship between parties with parties. It is nothing else than a $n \cdot n$ matrix ${\textbf{A}}$ where $n$ corresponds to the length and cardinality of the $N(G)$ set and equivalently to the amount of parties in the market $G$, so the ${\textbf{A}}_{ij}$ element of the matrix ${\textbf{A}}$ corresponds to the amount of payment transactions between the parties $i$ and $j$. Furthermore, the element ${\textbf{A}}_{ij}$ will be $1$ if the party $i$ has issued or received a payment transaction from party $j$ and $0$ otherwise. Thus,

Note that two parties $i$ and $j$ in a market $G$ will be considered to be adjacent if there exist at least one payment transaction $p$ between them and, in the same way, two payment transactions $x$ and $y$ in a market $G$ will be considered to be adjacent if there exist at least one party $z$ between the two payment transactions.

In Example 1, firm $c$ and $b$ are adjacent to each other because of the payment transaction $bc$ but also transactions $cb$ and $ba$ are adjacent to each other because of the firm $b$.

Example 5 The payment scenario of Example 1, where $N(G) = \{a, b, c, d\}$ and $E(G) = \{ab, bc, ca, cd\}$ in a market $G$, can be represented through an undirected payment adjacency matrix ${\textbf{A}}$ as follows:

Note $\forall i, j \in N: {\boldsymbol{A}}_{ij} \in \{x: 0 \leq x\}$ where ${\boldsymbol{A}}_{ij} = 0 \implies i = j$. Consequently, matrix ${\boldsymbol{A}}$ diagonal are zeros (Hollow matrix), because self-payments are not allowed by definition. Note also that, the matrix ${\boldsymbol{A}}$ indicates how many transactions are between the different parties of the market, but it does not quantify the payment, and it does not specify the payers and payees of the market.

2.8.   Undirected payment incidence matrix

The undirected payment incidence matrix represents a relationship between parties with payments, rather than parties with parties, as the undirected payment adjacency matrix. It is nothing else than a payment incidence matrix made of undirected payments, and note an incidence matrix made with directed payments is considerably different.

An undirected payment incidence matrix will be defined to be a $n \times m$ matrix ${\textbf{I}}$ where $n$ corresponds to the length and cardinality of the $N(G)$ set and equivalently to the amount of parties in a market of undirected payments $G$. Then, $m$ corresponds to the length and cardinality of the $E(G)$ set and equivalently to the amount of payment transactions in the market $G$, so if $i \in N$ and $\tau \in E(G)$ the ${\textbf{I}}_{i\tau}$ element of the matrix ${\textbf{I}}$ corresponds to the relationship between the party $i$ and the payment transaction $\tau$. Thus,

Note, the function $\Phi$ can take as arguments any two sets since it is simply an indicator function that outputs either $1$ or $0$: $\Phi: (i, \tau) \rightarrow \{0, 1\}$.

Example 6 The payment scenario of Example 1, where $N(G) = \{a, b, c, d\}$ and $E(G) = \{ab, bc, ca, cd\}$ in a market $G$, is actually a market scenario with undirected payments so $G$ can be represented through an undirected payment incidence matrix ${\textbf{I}}$ as follows:

Note $\forall i \in N(G): \forall \tau \in E(G): {\boldsymbol{I}}_{ij} \in \{0, 1\}$ and again the matrix does not quantify the payment nor specify the payers and payees of the market.

The undirected payment incidence matrix has one important drawback, since its use is limited to the markets of undirected payments, it provides no more information, per se, and in terms of quantitative market description, about the market transactions and parties than the adjacency payment matrix. This is, in part, because the undirected payment incidence matrix cannot provide additional market information that cannot be derived from the adjacency payment matrix as stated in Proposition 1 and that is why the payment incidence matrix is separated when describing undirected payments and directed payments.

Proposition 1. In a connected market $G$ of undirected general payments, with $\eta$ parties and $\tau$ payment transactions, where $\eta \geq 2$, $\tau \geq 0$ and $\eta, \tau \in \mathbb{Z}$, an adjacency payment matrix ${\boldsymbol{A}}$, an undirected payment incidence matrix ${\boldsymbol{I}}$ and an identity matrix ${\boldsymbol{Y}}_{\tau}$ of size $\eta$, it is true that

$\textrm{Note the $ (\cdot)^{+} $ notation of equation 2.}$

Proof. Let $G$ denote a connected market with a set of parties $N(G)$, a multiset of payment transactions $E(G)$ and with $\tau$ undirected payments. Let ${\textbf{I}}$ be the undirected payment incidence matrix, ${\textbf{A}}$ the adjacency payment matrix and ${\textbf{L}} = {\textbf{I}}^{\top} {\textbf{I}}$ of that market $G$. Then let $\Phi$ be the function of equation 6, ${\textbf{L}}_{ij}$ the $ij$-th element of the matrix ${\textbf{L}}$, ${\textbf{A}}_{ij}$ the $ij$-th of ${\textbf{A}}$ and ${\textbf{I}}_{ie}$ the $ie$-th of ${\textbf{I}}$.

First, note that ${\textbf{L}}_{ij}$ is actually a function of $\Phi$:

Next, note that when $i = j$ then ${\textbf{L}}_{ij}$ is the degree of the party $i$, in other words, it equals the number of payment transactions in which party $i$ is involved, as shown in equation 10:

On the other hand, when $i \neq j$ then the $ij$-th element of both matrices ${\textbf{L}}$ and ${\textbf{A}}$ are equal, as demonstrated in equation 11:

Consequently, ${\textbf{L}}_{ij} = {\textbf{A}}_{ij}$ when $i \neq j$, so all non-diagonal elements of matrix ${\textbf{L}}$ will be equal to the non-diagonal elements of matrix ${\textbf{A}}$ and, subsequently, when we convert diagonal elements of matrix ${\textbf{L}}$ to $0$'s then ${\textbf{L}} = {\textbf{A}}$ as demonstrated in equation 12—note it leads to Proposition 1. So, let ${\textbf{Y}}_{\tau}$ be a identity matrix of size $\tau \times \tau$ where $\tau = |E(G)|$, then

As a matter of curiosity, ${\boldsymbol{L}}$, which is also known as a Laplacian matrix, could have been used as a substitute for convenience purposes of the undirected payment incidence matrix but since it is easily derivable it will not be used.

The undirected payment incidence matrix describing a market of undirected payments is a function of the adjacency payment matrix and no more useful than it, but the use of a payment incidence matrix to represent directed payments gives additional and more important information in comparison with the undirected ones and that's why the directed payment incidence matrix concept will be introduced.

2.9.   Directed payment adjacency matrix

The directed payment adjacency matrix, an extension of the undirected payment adjacency matrix, is an adjacency matrix limited to the use in a market of directed payments. It is nothing else than a $n \times n$ matrix ${\textbf{A}}$, where $n$ corresponds to the length of the $N(G)$ set, and equivalently to the amount of parties in the market of directed payments $G$, and $E(G)$ corresponds to the multiset of payment transactions in the market $G$. So, if given any two parties $i, j \in N(G)$ and a payment $ij$, where $ij \in E(G)$, then ${\textbf{A}}_{ij}$, the $ij$-th element of the matrix ${\textbf{A}}$, would correspond to the number of payments from party $i$ to $j$. Let $Q_{ij}$ be the number of payments party $i$ has done to $j$— where $Q_{ij}$ is a non-negative integer—, $\Phi$ be the indicator function of equation 6 with the ordered pair $(\{ij\}, E(G))$, so $\Phi$ maps $1$ when $\{ij\} \in E(G)$, $0$ when $\{ij\} \not\in E(G)$, then:

Where, by definition, for any $i, j$ in $N(G)$:

Example 7 The payment scenario of Example 4, where $N(G) = \{a, b, c, d\}$ and $E(G) = \{ab, ba, bc, cb, cd, dc, da, ad\}$ in a market $G$, is actually a market scenario with directed payments. Consequently, $G$ can be represented through a directed payment adjacency matrix ${\textbf{A}}$ as follows:

As we see, matrix ${\textbf{A}}$ describes Figure 2 of Example 4 payment scenario.

Finally, and to summarize:

● Undirected adjacency payment matrix: It can be used to describe a market of either simple or general undirected payments.

● Undirected payment incidence matrix: It can also be used to describe a market of either simple or general undirected payments, as the undirected adjacency payment matrix, but with its own respective differences explained in sections 2.7 and 2.8.

● Directed payment adjacency matrix: It can be used to describe a market of either, simple or general, directed payments.

2.9.1.   Weighted payment adjacency matrix

The weighted payment adjacency matrix, an extension of the directed payment adjacency matrix, is a matrix that quantifies the amount of money each party receives and gives as payment in the market. It is a $n \times n$ matrix ${\textbf{W}}$, where $n$ corresponds to the length and cardinality of the $N(G)$ set and equivalently to the amount of parties in a market of directed payments $G$. The ${\textbf{W}}_{ij}$ element of the matrix ${\textbf{W}}$ corresponds, not to the number of payments, but to the total payment amount, measured in any monetary unit, paid by a party $i$ to $j$, where $i, j \in N(G)$. Finally, let $P_{ij}$ be the total payment amount, measured in monetary units to be paid by party $i$ to $j$, it will be given by $\gamma(i, j)$, where $\gamma: (i, j) \rightarrow \{x \in \mathbb{Z}: x \geq 0\}$, so:

Example 8 Suppose, again, the market $G$ of Example 4 but now imagine it is quantified, so party $a$ pays $2$ monetary units to $b$, $b$ $4$ to $a$, $b$ $6$ to $c$, $c$ $2$ to $b$, $c$ $4$ to $d$, $d$ $6$ to $c$, $d$ $2$ to $a$ and $a$ $4$ to $d$. Therefore, this market $G$ can be described by the following weighted payment adjacency matrix ${\bf{W}}$:

Note that since, for instance, party a pays 2 monetary units to b, then ${\textbf{W}}_{ab} = \gamma(a, b) = P_{ab} = 2$.

2.9.2.   Payments under a bilateral netting system

Payments under a bilateral netting system will be considered to be directed simple payments in a market $G$, with a set of $N(G)$ parties, where directed general payments between any two parties are set-off on a bilateral basis to take specific directed simple payment form in the bilateral netting system of payments. If $\gamma$ is the function of equation 16, then every payment under a bilateral netting system between any two parties $i$, $j \in N(G)$ is given by the function $\mu$ as a function of the ordered set $(i, j)$, where $\mu: (i, j) \rightarrow \{x \in \mathbb{Z}: x \geq 0\}$. So, if $\gamma$ is the function of equation 16, then:

In consequence, a market of directed general payments can be set-off on a bilateral basis in the bilateral netting system, with every payment transaction taking a directed simple payment form. For that reason, if ${\bf{W}}$ is the weighted incidence matrix of market $G$ and ${\bf{W}}^\prime$ is the weighted adjacency matrix of the market $G$, where every payment transaction was set-off on a bilateral basis, then ${\bf{W}}^\prime$ can be derived as defined in equation 18, so for any party $i, j \in N(G)$:

Since, by definition, as stated in equation 18:

Example 9 Let $G$ be the market of Example 4 and, consequently, ${\bf{W}}$ its weighted payment adjacency matrix.

The weighted payment adjacency matrix of market $G$ where every payment was bilaterally set-off, so every payment is a directed simple payment, is given by matrix ${\bf{W}}^\prime$:

Note that since, for instance, party $a$ pays $2$ monetary units to $b$ and $b$ pays $4$ to $a$, then ${\boldsymbol{W}}^{\prime}_{ab} = \frac{1}{2} (|{\boldsymbol{W}}_{ab} - {\boldsymbol{W}}_{ba}| + {\boldsymbol{W}}_{ab} - {\boldsymbol{W}}_{ba}) = 0$.

The directed simple payment under a bilateral netting system of a market $G$ with $\eta$ parties is really useful since it reduces the maximum possible compensation payments to just $3^{\binom{\tau}{2}}$, in other words, the maximum possible combination of payments in the market $G$ is $3^{\binom{\tau}{2}}$, which implies, market $G$ has $3^{\binom{\tau}{2}}$ maximum possible forms (Guichard, 2017) as proposition 3 shows.

Proposition 2. In a connected market $G$ of directed general payments, with $\eta$ parties, where $\eta \geq 2$, $\eta \in \mathbb{Z}$, $\tau$ payments, where $\tau \geq 0$, $\tau \in \mathbb{Z}$, $3$ possible payment forms—positive payment, $0$ payment and negative payment—it is true that the maximum possible combination of payments and the maximum possible forms $G^{*}$ of $G$ is $3^{\binom{\eta}{2}}$.

Proof. Let $G$ denote a connected market with a set of parties $N(G)$ with $\eta$ parties, where $\eta \geq 2$, $\eta \in \mathbb{Z}$, a multiset of payment transactions $E(G)$ and $K_{\eta}$ maximum possible amount of unique possible undirected simple payments between $\eta$ parties.

We know that when there are $2$ parties, the maximum amount of unique possible undirected simple payments between parties in the market is $1$, so $K_{2} = 1$;

Next, we assume equation 23 holds true for $x$ where $x \in \mathbb{Z}$, $x \geq 2$ and, where, consequently, we assume equation 24 is true as an induction hypothesis, so:

Then, we know that for a given market with $x$ parties, there will be a maximum of $K_x$ possible unique undirected simple payments. If we add $1$ additional party to the market with $x$ parties, then there will be $K_{x} + x$ payments because $1$ additional party would create $x$ additional possible unique undirected simple payments in the market, so

So, under the assumption of equation 24, we proved that it holds true for $\eta = x + 1$ in equation 25 and by the principle of mathematical induction it will also hold true for any integer equal or bigger than $2$, so:

Now, once equation 26 was proved to be true, note it is equivalent to $\binom{\tau}{2}$ as shown in equation 27

Finally, it is just missing to show where the $3$ in $3^{\binom{\eta}{2}}$ comes from. When defining a directed simple payment in section 2.4, it was defined to be either negative or positive, depending on who is the payer and the payee, and zero, if there is no payment between the two parties. So, for every payment there are $3$ possible forms, and consequently, in the market G with $\binom{\eta}{2}$ payments and $\eta$ parties there will be $3^{\binom{\eta}{2}}$ possible combinations of unique undirected simple payments between the parties and consequently $3^{\binom{\eta}{2}}$ possible market forms $G^{*}$. Naturally, for every payment $p$ in $E(G)$:

Example 10 Let G be the market of Example 3 where there are $4$ firms, $4$ payments, so $N(G) = \{a, b, c, d\}$ and $E(G) = \{ab, bc, ca, cd\}$, respectively.

Even though market $G$ has $4$ payment transactions, market $G$ can have $\binom{4}{2} = 6$ maximum possible unique undirected simple payments and $G^{*} = 3^{\binom{4}{2}} = 729$ possible combinations of unique directed simple payment combinations and, consequently, $729$ possible market forms.

2.10.   Payments under a multilateral netting system

Payments under a multilateral netting system will be considered to be directed simple payments, given a set of payments $E(G)$ and a set of parties $N(G)$, in a market $G$ where directed general payments between parties are set-off on a multilateral basis in the multilateral netting system, so payments take specific directed simple payment forms. Every payment between any two parties $i, j \in N(G)$ under a multilateral netting system will be associated with a capacity function $c$, where $c: (i, j) \rightarrow \{x \in \mathbb{Z}: x \geq 0\}$, a payment flow $f$, where $f: (i, j) \rightarrow \{x \in \mathbb{Z}: x \geq 0\}$ and a payment in monetary units $\gamma$, where $\gamma(i, j)$ is the function of equation 16.

The main point of the multilateral netting system is to define a series of payments that satisfies the full compensation in the market under a multilateral netting system. In order to get the solution for the compensation of the market, two new optimization problems will be introduced.

The first optimization problem will be algorithmically based on the minimum cost maximum flow method, it is inspired on the method proposed by (Simic´ and Milanovic´, 1992) and it will be presented in a general form to be solved by either a greedy algorithm or a linear programming method. The second optimization problem will be a variant inspired by the minimum cost flow problem proposed by (Fleischman and Dini, 2021) {to set-off obligations and it will be presented just for linear programming methods.}

The existence of bilateral payments will be handled \emph{ex-ante}. This, because mainstream greedy algorithms to compute maximum flows in a graph, as the Ford-Fulkerson or the Edmonds–Karp method, are designed to expect directional edges Ford and (Fulkerson, 1956) rather than bidirectional edges and bidirectional payments—bidirectional edges in graph theory—are defined as an essential concept of the market compensation solution. Note that a payment is considered to be bidirectional if given a market $G$ and two parties $i, j \in N(G)$ there exist a payment $\{i, j\} \in E(G)$ and a payment $\{j, i\} \in E(G)$. Furthermore, both $\{i, j\}$ and $\{j, i\}$ will be considered bidirectional payments, and where both $\{i, j\}$ and $\{j, i\}$ are reversed payments of each other.

A well known solution, to handle bidirectional edges in greedy algorithms to maximize flows, is to create additional edges as discussed in rsampaths16's (2016). So, for every two parties $i, j \in E(G)$ with bidirectional payments there will be created (for computation purposes) one additional party $z_{ij}$, two payment transactions $\{z_{ij}, i\}, \{z_{ij}, z\}$ and the reversed payment $\{j, i\}$ will be momentarily removed from the market $G$. After the multilateral set-off system discharged all the payments, all these created payments will disappear and the removed reversed payments will be put back again.

Therefore, without loss of generality, if the market $G$ contains bidirectional payments, or equivalently if $\forall\{i, j\} \in E(G): \exists\{i, j\}\:(\{i, j\} \in E(G)) \land \exists\{i, j\}\:(\{j, i\} \in E(G))$, then $B(G)$ will contain those bidirectional payments $\{i, j\}$ without its respective reversed payment, so every bidirectional payment $\{i, j\}$ will be in $B(G)$ but not its respective reversed payment $\{j, i\}$, so:

Note that by definition of equation 29, all bidirectional payments—elements of $B(G)$— are a subset of the set of payments $E(G)$, so:

So, if there are bidirectional payments in $E(G)$, or equivalently $|E(G)| > 0$, then $E^{\prime}(G)$ will be the new set of payments of the market $G$, $N^{\prime}(G)$ will be the new set of parties, such that, for every element $\{i, j\}$ of $B(G)$ a new party $z_{(i, j)}$ specific to every specific element $\{i, j\} \in B(G)$ will be created, so $E^{\prime}(G)$ and $N^{\prime}(G)$ are defined as:

As expected by the definition of $E^{\prime}(G)$, the quantity of payments in the set $B(G)$, and, consequently, the cardinality of $B(G)$, is the double of the quantity of payments that are in $E^{\prime}(G)$ but not in $E(G)$, so:

Finally, every element of the set $E(G)$ is associated with a payment $P_{ij}$ given by the function $\gamma(i, j)$, where $\{i, j\}$ are any two parties of $N^{\prime}(G)$, and every payment of the set $E^{\prime}(G)$ is either a payment in the set $E(G)$ but not in $B(G)$ or a payment that is in $E^{\prime}(G)$ but not in $E(G)$. So, the payment amount to be paid when the payment is in $E(G)$ but not in $B(G)$ is given by the payment amount $P_{ij}$ associated with the payment in $E(G)$, such that:

On the other hand, the payment amount to be paid, when the payment is in the set $E^{\prime}(G)$ but not in $E(G)$, is by definition given by a payment amount associated with a payment that is in $E(G)$, as equation 30 implies by definition, such that for any three payments $\alpha, \nu, \kappa \in E^{\prime}(G)$:

To generalize it even more and due to the possibility of having bidirectional payments in the market $G$, a new set of payments $E^{\prime\prime}(G)$ will be defined, such that:

In the same way:

Note the payment amount $\gamma(i, j)$ associated for any payment $\{i, j\}$ in $E^{\prime\prime}(G)$ will be $P_{ij}$ (where $P_{ij}$ is the payment amount associated with the payment $\{i, j\} \in E(G)$) if $\{i, j\} \in E(G)$ and $0$ if $\{i, j\} \in B(G)$, so:

As suggested by equation 34, the existence of bilateral payments in the market $G$ does not affect what each party in $N(G)$ gives or receives in total, as proposition 3 states.

Proposition 3. Let $G$ be a market with connected directed simple payments, with $\eta$ parties, where $\eta \geq 2$, $\eta \in \mathbb{Z}$, $\tau$ payments, where $\tau \geq 0$, $\tau \in \mathbb{Z}$ and with at least one bidirectional payment so $|B(G)| \geq 2$. Then, the set of payments $E(G)$, $E^\prime(G)$ or $E^{\prime\prime}(G)$ will not affect how much money each party in $N(G)$ gives in total to other parties nor how much money the party receives in total from other parties.

Proof. Assume, for the proof, that the use of $E(G)$ or $E^{\prime}(G)$ affects the net position—i.e. how much money a party gives in total to other parties and how much money the party receives in total from other parties—of parties in $N(G)$. Then, let $U_{z}$ be the new payments created when there are bidirectional payments, so:

From equation 31 we know that the set of payments $E^{\prime}(G)$ is $E(G)$ minus the set $B(G)$ plus all the elements of $U_z$, so $E^{\prime}(G)$ can be rewritten as:

Which implies that, if all parties of $N(G)$ have the same net position in $U_z$ and in $B(G)$, then the use of $E(G)$ or $E^\prime(G)$ does not affect the net position of parties in $N(G)$. Subsequently, it would imply it does not exist any party in $N(G)$ for which the net position is different in $B(G)$ than in $U_z$.

From equation 34 we know that every two elements $\nu, \kappa$ created in $U_z$ by element $\alpha$ in $B(G)$, the payments are the same so $\gamma(\nu) = \gamma(\kappa) = \gamma(\alpha)$.

Then, by definition of equation 39, we know that if there exist a party in $N(G)$ for which the net position in $B(G)$ is different from $U_z$, then the net position of parties in $N(G)$ will not change if the payments of the market are given by $E(G)$ or $E^{\prime}(G)$ and it would imply the proposition is true and otherwise false. Note also that if $E(G)$ or $E^{\prime}(G)$ don't change the net position of parties in $N(G)$, neither will $E^{\prime\prime}(G)$ because it is, by definition of equation 35, $E(G)$ or $E^{\prime}(G)$.

Furthermore, if we assume, by contradiction, that there exists a party $\rho \in N(G)$ for which the net position is different in $B(G)$ than in $U_z$, it would imply that there exists a payment $\alpha \in B(G)$, where $\rho \in \alpha \ni$

Finally, if the set $B(G)$ is not empty (by definition of preposition 3) and from equation 38 we know $B(G)$ not empty implies the set of payments $U_z$ are also not empty, then equation 40 raises a contradiction that proves proposition 3 is true by reductio ad adsurdum.

Note, the possibility of having bidirectional payments in the market $G$ is not a problem anymore, therefore, the next step is to define the role of parties in a market $G$ under a multilateral netting system. To do so, two optimization problems will be introduced, with specific characteristics, in sections 2.10.1 and 2.10.2.

2.10.1.   Multilateral set-off by the max-flow-min-cost principle

For the multilateral set-off by the max-flow-min-cost principle to work, it needs two parties to provide liquidity to the market and absorb the liquidity excess of the market.

Consequently, before defining any payment flow of the multilateral payment system, two parties will be added to the market $G$ payments to form a new set of parties $N_{st}(G)$. Consequently, if the market $G$ contains bilateral payments, then the market payments will be given by $N_{st}(G)$ such that $N_{st}(G) = N(G) \cup \{n_s, n_t\}$. However, if there are no bilateral payments in the market, the market payments will also be given by $N_{st}(G)$.

In consequence, regardless of the existence of bilateral payments in the market $G$:

The payments of the market under a bilateral netting system will be given by the set of payments $E_{st}(G)$, where the two new parties $n_s$ and $n_t$ will be involved in payments with some of the other parties. So, if $\tilde{N}(G)$ is a randomly ordered tuple that contains the parties of $N(G)$, i.e. $N(G) = \{\eta_1, \dots, \eta_n\}$ then $\tilde{N}(G) = (\eta_1, \dots, \eta_n)$, and:

Note that elements of $E_{st}(G)$ depend on the order of $N(G)$, but since $N(G)$ is unordered, then $E_{st}(G)$ will be unordered too.

The payment amount for all the payments in which $n_s$ or $n_t$ are involved will be defined by the net internal debt concept given by Fleischman and Dini (2021). So, let $\|\delta\|_{1}$ be the net internal debt—where $\|\delta\|_{1}$ is the $L^1$-norm of $\delta$—, ${\textbf{R}}_i(\Lambda) \in \mathbb{R}^n$ be the $i$-th row of a given matrix $\Lambda$ and let $G$ be a market with a set of parties $N_{st}(G)$, as defined in equation 40, with a $n \times n$ adjacency matrix ${\bf{A}}$. Therefore, ${\bf{A}} \in \mathbb{R}^{n \times n}$, such that $\|\delta\|_{1}$ and $\delta$ are defined as:

Then, the payment amount for every payment $\rho \in E_{st}(G)$ where party $n_s \in \rho$ or $n_t \in E_{st}(G)$ will be $\|\delta\|_{1}$, so

Note $\delta \in \mathbb{R}^{n}$, $\left\|\delta\right\|_{1} \in \mathbb{R}$ and that there will not be any positive number in the row matrix $\delta$, due to the negative {only notation $(\cdot)^{-}$, so, if $\delta = (a_1, \ldots, a_{n})$ where $\{a_1, \ldots, a_{n}\}$ are all the elements of $\delta$, it is true that:}

In consequence, $2 \cdot \|\delta\|_{1}$ will be then defined as the total amount of money, and therefore liquidity, that the liquidity provider $n_s$ needs to inject in the market of payments and $\|\delta\|_{1}$ as the total amount of money the party $n_t$ needs to withdraw from the market for the multilateral system to work in the market.

Accordingly, the total payment flow in the market will be defined as the payment amount that, specified individually for every firm, can be set-off on a multilateral basis using the liquidity provider party $n_s$ and the liquidity excess absorber $n_t$.

The payment amount that can be set-off for every payment in the market —payment flow— will be given by the maximization problem of equation 45 where the maximization solution will be all flows $f(i, j)$ associated with every payment $\{i, j\} \in E_{st}(G)$.

The maximization solution will therefore define what should be the coordination and amount of payments each firm should discharge in the system of multilateral set-off, so:

Note, this optimization problem is generalized for the use of some greedy algorithms, as the Ford-Fulkerson method or the Edmonds–Karp method. Evidently, the source node would be $n_s$ and the sink node will be $n_t$.

With the solution to the optimization problem, a weighted payment adjacency matrix ${\bf{S}}$ will be created. ${\bf{S}}$ will be a $n \times n$ matrix where $n$ corresponds to the length and cardinality of the $N_{st}(G)$ set.

The ${\textbf{S}}_{ij}$ element of the matrix ${\textbf{S}}$ corresponds to the total payment flow, measured in any monetary unit, defined to be discharged by party $i$ to $j$ by the maximization problem, where $i, j \in N_{st}(G)$, so if $f(i, j)$ is the flow to be discharged from firm $i$ to $j$ {defined by the optimization problem in equation 45, then:}

Finally, to compute the minimum payment transactions to satisfy all the payment obligations of the market, it is just necessary to subtract ${\bf{S}}$ from the weighted payment adjacency matrix ${\bf{A}}_{st}$ that is formed from the set of payments $E_{st}(G)$ and the set of parties $N_{st}(G)$. ${\bf{A}}_{st}$ is the matrix that is taken as reference of payments to solve the optimization problem of equation 46.

If $\Lambda$ is the weighted payment adjacency matrix that defines the minimum payments transactions to satisfy all the payment obligations of the market, then:

Matrix $\Lambda$ defines all the payments that could not be fully or partially set-off by the multilateral netting system and the payments.

Note, both $\Lambda$ and $S$ depend on $A_{st}$ which depends on $E_{st}(G)$ which is by definition a randomly made set. Consequently, the elements of $\Lambda$ and $S$ will also be random by definition.

Even though, elements of matrix $\Lambda$ are random, the possible forms and elements of $\Lambda$ are limited and predefined since, by definition of equation 41, the possible combinations for the set $E_{st}(G)$ are clearly limited.

Example 11 Let G be the market of banks, with a multilateral set-off system by the max-flow-min-cost principle, where bank $a$ does a payment transaction of $3.5$ monetary units to bank $b$, $b$ $2.5$ to $c$ and $c$ $2$ to $d$. Then, $\|\delta\|_1 = 1.5$ and ${\bf{A}}$ is defined as:

Then, if ${\bf{A}}_{st}$ is selected to be

matrix ${\textbf{S}}$ will be

Since $\Lambda = {\bf{A}}_{st} - {\bf{S}}$ then

2.10.2.   Multilateral set-off by a max-flow-all-edges principle

The multilateral set-off by the max-flow-all-edges, in contrast to the first multilateral system, will only need one additional party to provide liquidity in the market and that same party will absorb the liquidity excess of the market.

Consequently, as before, before defining any payment flow of the multilateral payment system, one party will be added to the market $G$ payments to form a new set of parties $N_{s_*}(G)$. Now, however, if the market $G$ contains bilateral payments, these payments will not suppose any problem and, therefore, any prior action will be needed. Market payments will be given by $N_{s_*}(G)$, where $N_{s_*}(G) : = N(G) \cup \{n_*\}$ and if there are no bilateral payments in the market, the market payments will also be given by $N_{s_*}(G)$.

In consequence, regardless of the existence of bilateral payments in the market $G$:

The payments of the market under this bilateral netting system will be given by the set of payments $E_{s_*}(G)$, where the party $n_*$ will be involved in payments with all the other parties, such that:

The payment amount for all the payments in which $n_*$ is involved is again given by the net internal debt defined in equation 43. Then, as before, the payment amount for every payment $\rho \in E_{s_*}(G)$, where party $n_* \in \rho$ is given by $\|\delta\|_1$ so

The total payment flow in the market, as in the first system, will be defined as the payment amount that, specified individually for every firm, can be set-off on a multilateral basis using the liquidity provider and absorber party $n_*$.

So, the payment amount that can be set-off for every payment in the market—payment flow—will now be by the maximization problem of equation 56 where the maximization solution, as before, all flows $f(i, j)$ associated with every payment $\{i, j\} \in E_{s_*}(G)$ but with the new conditions of equation 56.

The maximization solution will, therefore, define what should be the coordination and amount of payments each firm should discharge in the system of multilateral set-off, so:

Note this optimization problem is generalized to be solved by some linear programming methods, specially by the revised simplex method—which was used to solve all the problems in this paper since the graphs made to describe are rank-deficient because some rows are linear combinations of some others— and note it is not generalized for the use of any greedy algorithm.

With the solution to the optimization problem, a weighted payment adjacency matrix ${\bf{S}}$ will be created. ${\bf{S}}$ will be a $n \times n$ matrix where $n$ corresponds to the length and cardinality of the $N_{s_*}(G)$ set.

As before, the ${\textbf{S}}_{ij}$ element of the matrix ${\textbf{S}}$ corresponds to the total payment flow, measured in any monetary unit, defined to be discharged by party $i$ to $j$ but now by the maximization problem 56, where $i, j \in N_{s_*}(G)$, so if $f(i, j)$ is the flow to be discharged from firm $i$ to $j$ defined by the same optimization problem in equation 56, then:

Finally, as in the first multilateral system, to compute the minimum payment transactions to satisfy all the payment obligations of the market it is just necessary to subtract ${\bf{S}}$ from the weighted payment adjacency matrix ${\bf{A}}_{s_*}$ that is formed from the set of payments $E_{s_*}(G)$ and the set of parties $N_{s_*}(G)$, where ${\bf{A}}_{s_*}$ is the matrix that is taken as reference of payments to solve the optimization problem of equation 56.

Again $\Lambda$ will be the weighted payment adjacency matrix that defines the minimum quantity of payment transactions and payment amounts to satisfy all the payment obligations of the market, so:

In consequence, $\Lambda$ will define all the payments that could not be fully or partially set-off by the multilateral netting system but now by the set of payments $E_{s_*}(G)$.

Since $\Lambda$ depends on $A_{s_*}$ which at the same time depends on $E_{s_*}(G)$ which is by definition a not randomly made set, the elements of $\Lambda$ will not be random by definition. Note, the elements of $S$ will not be randomly given anymore.

In this multilateral system, the elements of matrix $\Lambda$ are not random anymore and the possible forms and elements of $\Lambda$ are predefined. In consequence, if ${\bf{A}}_{s_*}$ is given or not, the procedure is standard, comparable and, therefore, replicable.

Example 12 Let G be, again, the market of banks of example 2.10.1 and, consequently, $\|\delta\|_{1} = 1.5$, but now with a multilateral set-off system by the max-flow-all-edges principle, so

Now, ${\bf{A}}_{s_*}$ corresponds to

Note, elements of the matrix ${\bf{A}}_{s_*}$ will not vary if this problem is replicated, and, therefore, this exercise will be comparable and replicable regardless if the matrix ${\bf{A}}_{s_*}$ is given or not.

Consequently, the matrix ${\textbf{S}}$ will be

Since $\Lambda = {\bf{A}}_{s_*} - {\bf{S}}$ then

3.   Results

In this paper, two new optimization problems, partially inspired by the multilateral proposals by Fleischman and Dini (2021) and Simic´ and Milanovic´ (1992), were presented as theoretically interesting to reduce the amount of payment transactions and payment amounts in a market of payments under a multilateral set-off system.

The advantages of the optimization problems proposed in this paper can help to reduce the payment transactions between parties. These reductions of payment transactions, while keeping the market compensations, can bring many benefits to the economies. In part, because transactions of money are costly in economic terms but also in opportunity terms, logistic terms, effort terms, risk terms, etc. In consequence, reducing the amount of money transacted without interfering the compensation can be interpreted as a cost saved.

However, there is also room for improvement. In this paper, payments were assumed to be already done by parties in the market, and, therefore, it was just a matter of reducing the payments that already took part in the multilateral set-off system, but this was in order to avoid dealing with the risk cost from failure when payments are not yet done. If instead of already done payments, were considered compensation set-offs by payment promises or some sort of payment promise, then the market parties would have accumulated a considerable higher risk (Chakravorti, 2000).

In conclusion, the multilateralization of payments in a market is economically powerful, it entails many advantages that contemporary monetary system of payments usually ignore —making them interesting to study and worthy to test beyond theory—.

Acknowledgments

This work was supervised the Dr. Alexandra Simon, who helped me in some aspects along the project and to whom I am quite grateful.

Conflict of interest

All authors declare no conflicts of interest in this paper.

Appendix

A.   Exponential time complexity

The complexity is a really important drawback in the Ford-Fulkerson method and the Edmonds–Karp method, but also in the revised simplex method of the linear programming solution since all of them have exponential time complexities in common. This implies a considerably limitation of the application of the optimization problems proposed in this paper to markets with really large amounts of parties due to to the current computational capacity constraints (Arora and Barak, 2009).

B.   Example 10 statement

Example 10 states the market $G$ can have $729$ possible different combinations of directed payments and, consequently, $729$ market forms. Then, let $G_1$ be the first combination and $G_{729}$ the last possible market combination and, then:

Note the market combination $G_9$ corresponds to the market described in Example 10 and Example 3. The market combination $G_{729}$ is an empty set and it can be understood as a market in which does not take place any payment between the parties.