We are given a directed weighted graph $\mathcal{G} = (V, A)$, with $A \subseteq V^2$. The weight function is $w_{\mathcal{G}} \colon \mathcal{G}.A \to \mathcal{P}(\mathfrak{R}_{>} \times \mathfrak{R}_{\geq} \times (\mathfrak{R}_> \cup \{ \infty \}) \times \mathfrak{R})$, where $\mathfrak{R}_{\ast} = \{ x \in \mathfrak{R} \colon x \ast 0 \}$.

If $(K, r, n, t) \in \mathfrak{R}_{>} \times \mathfrak{R}_{\geq} \times (\mathfrak{R}_> \cup \{ \infty \}) \times \mathfrak{R}$, $K$ is the principal investment, $r$ is the annual interest rate, $n$ is the amount of compounding periods per year (the value of $\infty$ is allowed, which denotes continuous compounding), and $t$ is the time point at which the loan was granted. Together, the four parameters comprise a contract. Note that the weight of an arc is not a single contract, but rather a set of contracts (generalizing a bit).

For each arc $(u, v) \in \mathcal{G}.A$, $u$ is the creditor, $v$ is the debtor, and $w_{\mathcal{G}}$ is the set of contracts between the two nodes.

Equity function

We need a function $e_{\mathcal{G}} \colon \mathcal{G}.V \times \mathfrak{R} \to \mathfrak{R}$:

\begin{aligned} e_{\mathcal{G}}(u, \tau) &= \sum_{(u, v) \in \mathcal{G}.A} \Bigg( \sum_{(K, r, n, t) \in w_{\mathcal{G}}(u, v)} \mathfrak{C}_{\tau}(K, r, n, t)\Bigg) \\ &- \sum_{(v, u) \in \mathcal{G}.A} \Bigg( \sum_{(K, r, n, t) \in w_{\mathcal{G}}(v, u)} \mathfrak{C}_{\tau}(K, r, n, t) \Bigg), \end{aligned} where $$ \mathfrak{C}_{\tau}(K, r, n, t) = \begin{cases} K \bigg( 1 + \frac{r}{n} \bigg)^{\lfloor n (\tau - t) \rfloor} & \text{if } n \in \mathfrak{R}_> \\ K e^{r(\tau - t)} & \text{if } n = \infty. \end{cases} $$ (Above, $\mathfrak{C}_{\tau}(K, r, n, t)$ gives the value of a loan at time point $\tau$ taking the interest rate into account.)

Since the nodes of the input graph models the parties involved in the financial system, we allow each of them to choose for each debt a time point at which the debt may be cut. We cannot guarantee that all debts may be cut only partially, though the algorithm will try to minimize the sum of debt cuts.

Choosing debt cut moments

Also, we need another function $\mathfrak{f}_{\mathcal{G}} \colon \mathcal{G}.V \times \mathfrak{R}_> \times \mathfrak{R}_{\geq} \times (\mathfrak{R}_> \cup \infty) \times \mathfrak{R} \to \mathfrak{R}$ mapping each tuple of a debtor $v \in \mathcal{G}.V$ and its debt contract $c$ into a time point at which $v$ may cut the contract $c$.


The loan graph $\mathcal{G}$ is said to be in equilibrium at time point $\tau$ if and only if $e_{\mathcal{G}}(u, \tau) = 0$ for all $u \in \mathcal{G}.V$.

Applying the cut to a contract

Whenever a party $u \in \mathcal{G}.V$ is ready to raise $C$ units of resources for the debt cut of the contract $\mathcal{k} = (K, r, n, t)$, $\mathcal{k}$ becomes $$ \mathfrak{C}_{\tau}(\mathfrak{C}_{\mathfrak{f}_{\mathcal{G}}(u, \mathcal{k})}(K, r, n, t) - C, r, n, \mathfrak{f}_{\mathcal{G}}(u, \mathcal{k})), $$ where $\tau \geq \mathfrak{f}_{\mathcal{G}}(u, \mathcal{k})$.

The problem

Given a loan graph $\mathcal{G}$, the time points $\mathfrak{f}_{\mathcal{G}}$, and the equilibrium time point $T_{\mathcal{G}}$, find a set of debt cuts for each contract such that the state of the graph changes such that the graph attains an equilibrium at time point $T_{\mathcal{G}}$, and the sum of debt cuts is minimized.


I would not be surprised if this problem is already studied, and I would love to read about it more. The problem is that I cannot find the paper/s.

All in all, I did nothing else than merely defining the problem and eventually coming up with the solution, yet I would like to know more about it.

Auxiliary reading


Additional details

$e_{\mathcal{G}}(u, \tau)$: takes all loans issued by the node $u$, evaluate their value at time point $\tau$, sums them up, after which the sum of debts is subtracted. Basically, you can think of it as "saldo": everything other nodes own you at time $\tau$ minus everything you own to other nodes.

Each arc is associated with at least one contract. You can think of it as parallel arcs are allowed, each of which is associated with only one contract.

Cutting a debt is simply making a payment that partially cleares the debt. For example, I own you 1000 USD, I make a cut of 200 USD in order to "slow down" the accumulation of compound interest.

  • 1
    $\begingroup$ 1. Can you explain the meaning of the function $e_\mathcal{G}$? It looks complicated and it would help to explain in English what it is computing. 2. Wlog I suspect you can assume there's only one contract on each edge (replace an edge with a set of $k$ contracts by $k$ separate parallel edges). Is that right? If so, it'd help to apply this simplification to the problem statement. 3. What does it mean to "cut" a debt? What does it mean to cut a debt partially? You talk about finding a set of "debt cuts"; can you define the phrase "debt cut" precisely? $\endgroup$ – D.W. Jun 29 '16 at 15:59
  • 1
    $\begingroup$ 4. Can you ask a more specific question than "has this problem been studied?" What specifically do you want to know about the problem? Rather than asking "is there a paper about this problem?" it's usually more useful to ask something specific, e.g., "is there a polynomial-time algorithm for this problem?", "is this problem decidable?", "is there an approximation algorithm for this problem?". That way if your question is answered in the literature, you can get an answer citing the paper; or you might get an answer with a new solution never before published. $\endgroup$ – D.W. Jun 29 '16 at 16:00
  • $\begingroup$ @D.W. I added that Additional details section and added a paragraph into the Question expanding more or less my request. $\endgroup$ – coderodde Jun 29 '16 at 16:15
  • $\begingroup$ 5. Instead of adding "Additional details" at the end, please edit the question to put the information into the narrative at the logical place. For instance, where you define $e_\mathcal{G}$ would be a natural place to describe what it's trying to do. 6. I encourage you to remove unnecessary complexity. I doubt that you really need $n$ (I doubt the fundamental essence would be changed if we had $n=\infty$ for all contracts). Try to pare down your problem to the simplest you can. 7. What have you tried? What approaches have you considered? You should try to solve it yourself before asking here. $\endgroup$ – D.W. Jun 29 '16 at 18:44
  • 1
    $\begingroup$ Please do not post questions as puzzles where the reader must visit other sites to try and figure out what you meant. Your question must be self-contained to someone who knows the relevant background. $\endgroup$ – Gilles Jun 30 '16 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.