Arbitrage any takers? C++/Java solutions Only

[doug reich]

vic,

I used modified Bellman-Ford as well. I wrote it from scratch, not using Boost, but the key features to avoid repeated currencies for me was to add a std::set to each iteration that saves those nodes visited on that path. In my implementation I could check the set in constant time, since std::set returns the elements in order. Think merge-sort.

I don't think you can modify the graph, however, because all the other paths will want to explore those edges, no?

I found that you also have to make some modifications to the algorithm if you want ALL of the best arbitrage loops. That is, if after 3 steps you reach node X through two equally-good paths, you will want to save both paths (this could happen if some currencies are pegged, e.g.). (Bellman Ford will normally break-ties arbitrarily, but you may want to allow ties) Not difficult to do, depending on your implementation, but be aware.

 

[quantyst]

Please Comment On This Solution

This problem is akin to placing n rooks on an nxn chessboard in such a way that no two of them fall within each others' line of attack. There are obviously n! ways of doing this. For each such arrangement of the rooks on the nxn chessboard, we keep track of the place address (i,j) and place value x(i,j) for all i and j. It is necessary that we reintroduce the main diagonal consisting of all 1's: that is, x(i,i)=1 for all i.

It boils down to determining all n! products of the form W=x(1,p(1))*x(2,p(2))*x(3,p(3))*...*x(n,p(n)) where the function p represents any one of the n! permutations on {1,2,...,n}. The product W is precisely the terms of the summation used in computing the determinant of an nxn matrix.

Now each permutation includes cycles. A helpful way to represent a permutation is to place the p(i) values against (or below) the i value. Each representation has a top row consisting numbers 1,2,...,n. Against and below each i in the first row is placed the number p(i). Here are some examples:

Perm A:

1 2 3 4 5 6 7 8 9
4 5 2 3 6 1 9 7 8

Here p(1)=4, p(4)=3, p(3)=2, p(2)=5, p(5)=6, p(6)=1 (<-- Back to 1).

Perm A has two cycles:

1 --> 4 --> 3 --> 2 --> 5 --> 6 --> 1

7 --> 9 --> 8 --> 7

Notice how each cycle can begin with any number and end with the same number.

Perm B:

1 2 3 4 5 6 7 8 9
4 5 2 3 6 1 7 8 9

Perm B has now four cycles:

1 --> 4 --> 3 --> 2 --> 5 --> 6 --> 1
7 --> 7
8 --> 8
9 --> 9

Every non-attacking placement of the rooks on nxn chessboard can be expressed as a permutation. Now, the Perm A is not quite useful because it commingles two sequences of transactions (or conversions). To get around this, all we need to do is to identify such commingling permutations and ignore them.

Now, Perm B has in effect only one NONTRIVIAL cycle, same as the first cycle of Perm A noted above.

If the product of the values of the nontrivial cycle of Perm B is greater than 1, then the transactions provide an arbitrage. Otherwise, no arbitrage is provided by that sequence of transactions indicated by the cycle.

Now, although Perm B has four cycles, the latter three are innocuous. For example, the cycle (9 --> 9) represents conversion of the country 9 with itself. So, the conversion of country 9 with itself results in the value 1, which does not affect the product of the conversion factors for the first six countries.

I tend to think that there already exist many software/code programs that can identify the number of cycles of a given permutation, the size of each cycle in it, etc. Obviously when the size is one, then it poses no difficulty.
-----------------------------------
As it's been pointed out to me, I do realize the above is only mathematical. But if the solution is correct, can someone code it?

 

[ExSan]

Quantyst,

what would be the output of your algorithm applied to the sample input data ?

 ARBITRAGE - Currency Trader Matrix
    WORKSHEET A[4, 4]
          <---------------------------->
                 A      B      C      D 
         1:      1    3.1 0.0023   0.35
         2:   0.21      1 0.0035    8.1
         3:    200 180.559     1     10
         4:    2.1  0.089  0.061      1
           <---------------------------->

 

[doug reich]

I tend to think that there already exist many software/code programs that can identify the number of cycles of a given permutation, the size of each cycle in it, etc. Obviously when the size is one, then it poses no difficulty.
-----------------------------------
As it's been pointed out to me, I do realize the above is only mathematical. But if the solution is correct, can someone code it?

The easy part of the algorithm is to find cycles (since it is a complete graph); the challenge is to find a lowest cost (highest return) cycle without exploring every single cycle.

 

[ExSan]

UVa 104 - Algorithmist

 

[MartinOvie]

The Problem

Arbitrage is the trading of one currency for another with the hopes of taking advantage of small differences in conversion rates among several currencies in order to achieve a profit. For example, if $1.00 in U.S. currency buys 0.7 British pounds currency, £1 in British currency buys 9.5 French francs, and 1 French franc buys 0.16 in U.S. dollars, then an arbitrage trader can start with $1.00 and earn

dollars thus earning a profit of 6.4 percent.
You will write a program that determines whether a sequence of currency exchanges can yield a profit as described above.
To result in successful arbitrage, a sequence of exchanges must begin and end with the same currency, but any starting currency may be considered.

The Input

The input file consists of one or more conversion tables. You must solve the arbitrage problem for each of the tables in the input file.
Each table is preceded by an integer n on a line by itself giving the dimensions of the table. The maximum dimension is 20; the minimum dimension is 2.
The table then follows in row major order but with the diagonal elements of the table missing (these are assumed to have value 1.0). Thus the first row of the table represents the conversion rates between country 1 and n-1 other countries, i.e., the amount of currency of country i (

) that can be purchased with one unit of the currency of country 1.
Thus each table consists of n+1 lines in the input file: 1 line containing n and n lines representing the conversion table.

The Output

For each table in the input file you must determine whether a sequence of exchanges exists that results in a profit of more than 1 percent (0.01). If a sequence exists you must print the sequence of exchanges that results in a profit. If there is more than one sequence that results in a profit of more than 1 percent you must print a sequence of minimal length, i.e., one of the sequences that uses the fewest exchanges of currencies to yield a profit.

Because the IRS (United States Internal Revenue Service) notices lengthy transaction sequences, all profiting sequences must consist of n or fewer transactions where n is the dimension of the table giving conversion rates. The sequence 1 2 1 represents two conversions.
If a profiting sequence exists you must print the sequence of exchanges that results in a profit. The sequence is printed as a sequence of integers with the integer i representing the

line of the conversion table (country i). The first integer in the sequence is the country from which the profiting sequence starts. This integer also ends the sequence.
If no profiting sequence of n or fewer transactions exists, then the line
no arbitrage sequence exists should be printed.
Sample Input


3
1.2 .89
.88 5.1
1.1 0.15
4
3.1 0.0023 0.35
0.21 0.00353 8.13
200 180.559 10.339
2.11 0.089 0.06111
2
2.0
0.45
Sample Output


1 2 1
1 2 4 1
no arbitrage sequence exists

@Andy Nguyen : I know its old, but I just had to try it. Consider the case of n = 3, where my three currencies are the dollar, euro and francs. Does the conversion matrix look like this?

Dollar Euro Francs
1 1.2 .89
.88 1 5.1
1.1 0.15 1