24-3 Arbitrage

Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that $1$ U.S. dollar buys $49$ Indian rupees, $1$ Indian rupee buys $2$ Japanese yen, and $1$ Japanese yen buys $0.0107$ U.S. dollars. Then, by converting currencies, a trader can start with $1$ U.S. dollar and buy $49 \times 2 \times 0.0107 = 1.0486$ U.S. dollars, thus turning a profit of $4.86$ percent.

Suppose that we are given $n$ currencies $c_1, c_2, \ldots, c_n$ and an $n \times n$ table $R$ of exchange rates, such that one unit of currency $c_i$ buys $R[i, j]$ units of currency $c_j$.

a. Give an efficient algorithm to determine whether or not there exists a sequence of currencies $\langle c_{i_1}, c_{i_2}, \ldots, c_{i_k} \rangle$ such that

$$R[i_1, i_2] \cdot R[i_2, i_3] \cdots R[i_{k - 1}, i_k] \cdot R[i_k, i_1] > 1.$$

Analyze the running time of your algorithm.

b. Give an efficient algorithm to print out such a sequence if one exists. Analyze the running time of your algorithm.

a. We can use the Bellman-Ford algorithm on a suitable weighted, directed graph $G = (V, E)$, which we form as follows. There is one vertex in $V$ for each currency, and for each pair of currencies $c_i$ and $c_j$, there are directed edges $(v_i, v_j)$ and $(v_j , v_i)$. (Thus, $|V| = n$ and $|E| = n(n - 1)$.)

We are looking for a cycle $\langle i_1, i_2, i_3, \ldots, i_k, i_1 \rangle$ such that

$$R[i_1, i_2] \cdot R[i_2, i_3] \ldots R[i_{k - 1}, i_k] \cdot R[i_k, i_1] > 1.$$

Taking logarithms of both sides of this inequality gives

$$\lg R[i_1, i_2] + \lg R[i_2, i_3] + \cdots + \lg R[i_{k - 1}, i_k] + \lg R[i_k, i_1] > 0.$$

If we negate both sides, we get

$$(-\lg R[i_1, i_2]) + (-\lg R[i_2, i_3]) + \cdots + (-\lg R[i_{k - 1}, i_k]) + (-\lg R[i_k, i_1]) < 0,$$

and so we want to determine whether $G$ contains a negative-weight cycle with these edge weights.

We can determine whether there exists a negative-weight cycle in $G$ by adding an extra vertex $v_0$ with $0$-weight edges $(v_0, v_i)$ for all $v_i \in V$, running $\text{BELLMAN-FORD}$ from $v_0$, and using the boolean result of $\text{BELLMAN-FORD}$ (which is $\text{TRUE}$ if there are no negative-weight cycles and $\text{FALSE}$ if there is a negative-weight cycle) to guide our answer. That is, we invert the boolean result of $\text{BELLMAN-FORD}$.

This method works because adding the new vertex $v_0$ with $0$-weight edges from $v_0$ to all other vertices cannot introduce any new cycles, yet it ensures that all negative-weight cycles are reachable from $v_0$ .

It takes $\Theta(n^2)$ time to create $G$, which has $\Theta(n^2)$ edges. Then it takes $O(n^3)$ time to run $\text{BELLMAN-FORD}$. Thus, the total time is $O(n^3)$.

Another way to determine whether a negative-weight cycle exists is to create $G$ and, without adding $v_0$ and its incident edges, run either of the all-pairs shortestpaths algorithms. If the resulting shortest-path distance matrix has any negative values on the diagonal, then there is a negative-weight cycle.

b. Note: The solution to this part also serves as a solution to Exercise 24.1-6.

Assuming that we ran $\text{BELLMAN-FORD}$ to solve part (a), we only need to find the vertices of a negative-weight cycle. We can do so as follows. Go through the edges once again. Once we find an edge $(u, v)$ for which $u.d + w(u, v) < v.d$, then we know that either vertex $v$ is on a negative-weight cycle or is reachable from one. We can find a vertex on the negative-weight cycle by tracing back the $v$ values from $v$, keeping track of which vertices we've visited until we reach a vertex $x$ that we've visited before. Then we can trace back $v$ values from $x$ until we get back to $x$, and all vertices in between, along with $x$, will constitute a negative-weight cycle. We can use the recursive method given by the $\text{PRINTPATH}$ procedure of Section 22.2, but stop it when it returns to vertex $x$.

The running time is $O(n^3)$ to run $\text{BELLMAN-FORD}$, plus $O(m)$ to check all the edges and $O(n)$ to print the vertices of the cycle, for a total of $O(n^3)$ time.