#### 1 Introduction

In the most cost-effective loan problem, we are given a directed graph of actors where each actor may lend some amount of resources it possesses to its child nodes. In case an actor needs more than his immediate parents can lend, the parents might need to lend from their parents, adjust the interest rate to cover their own expenses, and pass the funds to the original lending actor.

Formally, we are given a directed graph $G = (V, A)$, where $V$
is the set of actors, and
$A \subseteq V^2 \setminus \{ (u, u) \in V^2 \text{ for all } u \in V\}$ is the set of directed
arcs, excluding self-loops. By $V(G)$ we denote the actor set of $G$, and, likewise, by
$A(G)$ we denote the arc set of $G$. Given an arc $(u, v) \in A$,
we call $u$ a *parent* of $v$, $v$ a *child* of $u$.
Existence of such an arc indicates that $u$ may lend some or all
of its resources to $v$. Along the graph, we are given a
*potential function* $\mathfrak{P} \colon V \to [0, \infty) = \mathbb{R}_{\geq 0}$
that maps each actor in the graph to the (non-negative) equity that that very
node has at its disposal. Finally, we are given an *interest rate function*
$\mathfrak{I} \colon A \to \mathbb{R}_{\geq 0}$ that maps each arc
$(u, v) \in A$ to the interest rate the actor $u$ can offer $v$
when $v$ decides to lend from $u$. From now on, we will call the
aforementioned amount of resources or equity simply *potential*.

Apart from the target data structure, in a problem instance, we are given an actor $a \in V$ that applies for a loan, a required potential $P \in \mathbb{R}_{> 0}$ and a maximum tolerable interest rate $i \in \mathbb{R}_{\geq 0}$. Our aim, then, is to compute a loan (which may involve more than one lending actor) with minimized interest rates.

#### 2 Interest rate model

Throughout the post, we assume a simple interest rate model. The
accumulated balance at time $t$ since the time point at which the
loan was issued, with initial principal $\mathfrak{A}$ and interest
rate $r$ is given by
\[
\mathfrak{A}(1 + r)^t.
\]
If we have in the graph, for instance, a directed acyclic path
$\langle u, v, z \rangle$ with $r_{u,v}$ being the interest rate
of $(u, v)$, and $r_{v, z}$ being the interest rate of $(v, z)$,
the interest rate equation becomes
\[
\mathfrak{A}(1 + r_{u,v})^t (1 + r_{v,z})^t = \mathfrak{A}\big[ (1 + r_{u,v})(1 + r_{v,z}) \big]^t = \mathfrak{A}(1 + R)^t.
\]
Above, $R$ is the *combined* interest rate. Dividing both
sides by $\mathfrak{A}$ and taking $t$-th root, we obtain
\begin{aligned}
(1 + r_{u,v})(1 + r_{v,z}) &= 1 + R \\
R + 1 &= 1 + r_{u,v} + r_{v,z} + r_{u,v}r_{v,z} \\
R &= r_{u,v} + r_{v,z} + r_{u,v}r_{v,z}.
\end{aligned}
In general, we write $r_1 + r_2 + r_1 r_2 = \mathfrak{C}(r_1, r_2).$

Since we may deal with entire "loan chains," we need
to define the concept of *effective interest rate*.
Effective interest rate is given by
\[
I(u, v) = \min \Bigg(\mathfrak{I}(u, v), \underset{z \in {\rm C {\small hildren}}(G, u)}{\min} \mathfrak{C}(\mathfrak{I}(u, z), I(z, v))\Bigg)
\]
where ${\rm C{\small HILDREN}}(G, u)$ is the set of child nodes
of $u$, or, formally, $\{ v \colon (u, v) \in A(G) \}.$
Also, for the above formula to be sensible, we need to set $\mathfrak{I}(u, v) = \infty$ for all missing arcs $(u, v) \not\in A(G)$, and $I(u, u) = 0$ for all $u \in V(G)$.

#### 3 Problem statement

Given a problem instance $(G, a, \mathfrak{P}, \mathfrak{I}, P, i)$,
we wish to compute two additional functions: $\pi$ and $d$.
$\pi \colon V \to \mathbb{R}_{\geq 0}$ is called a
*solution potential function* and it maps each actor
$u$ to potential $\pi(u)$ $u$ can lend, and $d \colon V \to V$
is called a *direction function* and it maps each actor
$u$ to some of its children $d(u)$ to which $\pi(u)$ worth
potential is being lent. What comes to constraints, no actor
$u$ lending some of its potential shall have $I(u, a) > i$,
since $a$ cannot afford effective interest rates above $i$.
Also, if it is not possible, due to the first constraint, to
obtain a loan worth $P$, the loan should be maximized from below
as close to $P$ as possible.

In order to implement the first constraint, we need to define the
set of *admissible* solution potential functions:
\[
\pi_{I, a, i, G} = \{ \pi \colon V(G) \to \mathbb{R}_{\geq 0} \; | \; \pi(u) = 0 \text{ if } I(u, a) > i \}.
\]
An admissible solution potential function $\pi$ is said to be *valid*
if it also satisfies
\[
\sum_{u \in V} \pi(u) \in [0, P],
\]
and we denote that by $\pi \in \mathfrak{V}$.

Now, we can state the objective formally: \[ \pi = \underset{\pi' \in \mathfrak{V}}{\arg \min}{\Bigg[ P - \sum_{u \in V} \pi'(u) \Bigg]}, \] and \[ d(u) = \underset{z \in {\rm C {\small HILDREN}}(G, u)}{\arg \min} \Bigg[\mathfrak{C}\big(\mathfrak{I}(u, z), I(z, a)\big)\Bigg]. \]

#### 4 Solution algorithm

Since the effective interest rate does not decrease with adding more directed arcs, we must have that for any actor $a \in V$ the most cost-efficient lender is an immediate parent. Whether the second most cost-efficient lender is an immediate parent or not depends on effective interest rates. Regardless, since we consider effective interest rates, basically we are growing a directed "minimum spanning tree" which we extend in a greedy fashion one arc at a time: In the very beginning, the tree is trivial and consists only of $a$. Then a most cost-effective parent $u_1$ is selected and the arc $(u_1, a)$ is introduced to the tree. Then $u_2$ is selected. It must not belong to $\{a, u_1\}$ while have the lowest possible effective interest rate among all nodes in $V \setminus \{ a, u_1 \}$. This procedure continues until a desired potential $P$ is collected or until there is no more nodes left with affordable effective interest rates. Below Priority-Queue-Insert$(Q, \langle a, b, c \rangle)$ stores the triple $\langle a, b, c \rangle$ in the priority queue $Q$ and uses $c$ as a priority key.

#### 5 Proof of correctness

Lemma 1 (Termination)
The algorithm terminates.

Note that each node removed from the priority queue at line 13 is
inserted into the closed set $C$ at line 18. Now, the line 23 will not
reintroduce the same node to $Q$ and so, $Q$ eventually becomes empty (unless
the algorithm terminates earlier in case the required potential is collected).

Lemma 2 (Optimality)
The algorithm finds most cost-effective loans.

The effective interest rate function $I$ implicitly defines a transitive closure
from any actor $u \neq a$ to $a$ assuming the effective interest rate of $u$ is
within the constraint $I(u, a) \leq i$. That way, $a$ loans from all affordable
parents (immediate or intermediate) in a greedy fashion: lend as much as possible
from the most affordable actor, then lend as much as possible from the second most
affordable actor, and so on until the requested potential is collected or there are
no more affordable lenders left. It is easy to see that such strategy minimizes
interest expenses.

Lemma 3 ($d$ is acyclic)
Given a solution direction function $d$,
there exist no actor sequence $\langle u_1, u_2, \dots, u_k \rangle$
such that $d(u_1) = u_2$, $d(u_2) = u_3$, $\dots$, $d(u_{k - 1}) = u_k$ and $d(u_k) = u_1$.

The only way for such a cycle to emerge is to have $\mathfrak{I}(u_1, u_2) =
\mathfrak{I}(u_2, u_3) = \dots = \mathfrak{I}(u_{k-1}, u_k) = \mathfrak{I}(u_k, u_1) = 0$, and to pass in $\infty$ as the required potential. Since it is reasonable
not to accept infinity for the requested potential, and we have the closed list around in the algorithm, this phenomenon cannot appear.
Without loss of generality, suppose the search enters the cycle via $u_1$. When $u_k$ will be
removed from the priority queue, the arc $(u_k, u_1)$ will be ignored by the line 20 since $u_1$ is in $C$, and
so, there is no way $d(u_k)$ could be mapped to $u_1$.

Lemma 4
The sum of all solution potentials cannot exceed $P$.

This is trivially guaranteed by the line 14 and the second test at line 12.

#### 6 Running time analysis

All the operations except **Priority-Queue-Insert**
and **Priority-Queue-Extract-Minimum** run in $\mathcal{O}(1)$ time.
In particular, operations on $\pi, d$ and $C$ may be expected to run in $\mathcal{O}(1)$
on average by resorting to hash-table based maps and sets. With geometric expansion
scheme **[1]**, adding an element to a hash-table based data
structure runs in **amortized** $\mathcal{O}(1)$. (If the load factor reaches its
upper bound, the underlying storage array must be made larger.)

What comes to the priority queue $Q$, it clearly stores graph actors without copies
of a same actor. Now, if we choose a binary heap, both run in $\mathcal{O}(\log V)$ time.
**Priority-Queue-Insert** is called no more than $|E|$
times, and **Priority-Queue-Extract-Minimum** is called once per
node, and so we have the running time $\mathcal{O}(E \log V + V \log V) = \mathcal{O}(E \log V)$. By deploying
a Fibonacci heap instead, we may reduce this to $\mathcal{O}(E + V \log V)$.

#### 7 Future work

We used a very simple interest rate model in our solution, and so it leaves the case where the used interest rate model is more realistic. In general, with initial principal $\mathfrak{A}$, interest rate $r > 0$, the number of compound periods $n$ per time unit, and time since the moment the loan was issued $t$, the balance grows according to \[ \mathfrak{C} = \mathfrak{A}\Bigg( 1 + \frac{r}{n} \Bigg)^{\lfloor nt \rfloor}. \] Also, as $n \to \infty$, $\mathfrak{C} \to \mathfrak{A}e^{rt}$. Combining loans with different parameters in a meaningful way seems to be a non-trivial task but we might address it later.#### 8 References

**[1]**Keeping vectors efficient (Retrieved 2018-03-09.)