Interesting Problem (Currency arbitrage)

user_91593 0
Viewed 29225

Arbitrage is the process of using discrepancies in currency exchange values to earn profit.
Consider a person who starts with some amount of currency X, goes through a series of exchanges and finally ends up with more amount of X(than he initially had).
Given n currencies and a table (nxn) of exchange rates, devise an algorithm that a person should use to avail maximum profit assuming that he doesn't perform one exchange more than once.

I have thought of a solution like this:

  1. Use modified Dijkstra's algorithm to find single source longest product path.
  2. This gives longest product path from source currency to each other currency.
  3. Now, iterate over each other currency and multiply to the maximum product so far, w(curr,source)(weight of edge to source).
  4. Select the maximum of all such paths.

While this appears good, i still doubt of correctness of this algorithm and the completeness of the problem.(i.e Is the problem NP-Complete?) as it somewhat resembles the traveling salesman problem.

Looking for your comments and better solutions(if any) for this problem.

Thanks.

EDIT:
Google search for this topic took me to this here, where arbitrage detection has been addressed but the exchanges for maximum arbitrage is not.This may serve a reference.

c algorithm c++
5 Answers

Dijkstra's cannot be used here because there is no way to modify Dijkstra's to return the longest path, rather than the shortest. In general, the longest path problem is in fact NP-complete as you suspected, and is related to the Travelling Salesman Problem as you suggested.

What you are looking for (as you know) is a cycle whose product of edge weights is greater than 1, i.e. w1 * w2 * w3 * ... > 1. We can reimagine this problem to change it to a sum instead of a product if we take the logs of both sides:

log (w1 * w2 * w3 ... ) > log(1)

=> log(w1) + log(w2) + log(w3) ... > 0

And if we take the negative log...

=> -log(w1) - log(w2) - log(w3) ... < 0 (note the inequality flipped)

So we are now just looking for a negative cycle in the graph, which can be solved using the Bellman-Ford algorithm (or, if you don't need the know the path, the Floyd-Warshall algorihtm)

First, we transform the graph:

for (int i = 0; i < N; ++i)
  for (int j = 0; j < N; ++j)
    w[i][j] = -log(w[i][j]);

Then we perform a standard Bellman-Ford

double dis[N], pre[N];

for (int i = 0; i < N; ++i)
   dis[i] = INF, pre[i] = -1;

dis[source] = 0;

for (int k = 0; k < N; ++k)
  for (int i = 0; i < N; ++i)
    for (int j = 0; j < N; ++j)
      if (dis[i] + w[i][j] < dis[j])
        dis[j] = dis[i] + w[i][j], pre[j] = i;

Now we check for negative cycles:

for (int i = 0; i < N; ++i)
  for (int j = 0; j < N; ++j)
    if (dis[i] + w[i][j] < dis[j])
      // Node j is part of a negative cycle

You can then use the pre array to find the negative cycles. Start with pre[source] and work your way back.

user_2358250

Take the log of the conversion rates. Then you are trying to find the cycle starting at X with the largest sum in a graph with positive, negative or zero-weighted edges. This is an NP-hard problem, as the simpler problem of finding the largest cycle in an unweighted graph is NP-hard.

Amit_Kumar_195010

Unless I totally messed this up, I believe my implementation works using Bellman-Ford algorithm:

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>


std::vector<std::vector<double>> transform_matrix(std::vector<std::vector<double>>& matrix)
{
    int n = matrix.size();
    int m = matrix[0].size();
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            matrix[i][j] = log(matrix[i][j]);
        }
    }
    return matrix;
}

bool is_arbitrage(std::vector<std::vector<double>>& currencies)
{

    std::vector<std::vector<double>> tm = transform_matrix(currencies);

    // Bellman-ford algorithm
    int src = 0;
    int n = tm.size(); 
    std::vector<double> min_dist(n, INFINITY);

    min_dist[src] = 0.0;

    for (int i = 0; i < n - 1; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            for (int k = 0; k < n; ++k)
            {
                if (min_dist[k] > min_dist[j] + tm[j][k])
                    min_dist[k] = min_dist[j] + tm[j][k];
            }
        }
    }

    for (int j = 0; j < n; ++j)
    {
        for (int k = 0; k < n; ++k)
        {
            if (min_dist[k] > min_dist[j] + tm[j][k])
                return true;
        }
    }
    return false;
}


int main()
{
    std::vector<std::vector<double>> currencies = { {1, 1.30, 1.6}, {.68, 1, 1.1}, {.6, .9, 1} };
    if (is_arbitrage(currencies))
        std::cout << "There exists an arbitrage!" << "\n";
    else
        std::cout << "There does not exist an arbitrage!" << "\n";



    std::cin.get();
}
user_77008020
Related