Arbitrage any takers? C++/Java solutions Only

Wallstyouth · 8/11/07

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 · 8/11/07

Interesting problem. I'll take a crack at this in C++
Thanks for sharing Wallstyouth

alain · 8/31/07

Hi Wallstyouth,

I looked at this problem and I wanted to get an answer earlier but I didn't have time to take a crack until yesterday.

My solution was straight forward. We can look at this problem as a typical directed graph problem taking the matrix that you provide as an incomplete representation of a digraph in an adjacency matrix.

My algorithm was very simple. I converted the matrix into a graph representation in an adjacency list. This representation is basically a Hash table (map) with key-value pairs. The keys are the different currencies and the values are lists of edges coming out of a given currency representing the exchange rate to another currency. Then, I traversed the graph using a modified Depth-First-Search, looking for non-overlaping cycles.

The last step is to check the cycles and find out which ones produced arbitrage conversions.

alain · 8/31/07

Here is the output of for the 3x3 matrix.

C++:

List of possible arbitrage sequences: 
2 0 1 2 
1 0 1 
1 2 0 1 
0 1 0 
0 1 2 0

zero means the first country, 1 the second country and so forth (C style array index).

alain · 8/31/07

Here is the output of for the 4x4 matrix.

C++:

List of possible arbitrage sequences: 
3 0 1 3 
3 0 2 1 3 
3 2 0 1 3 
3 2 0 3 
3 2 1 3 
2 0 1 2 
2 0 1 3 2 
2 0 3 2 
2 1 3 0 2 
2 1 3 2 
1 2 0 1 
1 3 0 1 
1 3 0 2 1 
1 3 2 0 1 
1 3 2 1 
0 1 2 0 
0 1 3 0 
0 1 3 2 0 
0 2 1 3 0 
0 3 2 0

Here is the output of for the 2x2 matrix.

C++:

No arbitrage sequence found.

Muting · 8/31/07

alain said:
Here is the output of for the 3x3 matrix.

C++:

List of possible arbitrage sequences: 2 0 1 2 1 0 1 1 2 0 1 0 1 0 0 1 2 0

zero means the first country, 1 the second country and so forth (C style array index).

Alain:

I got the same result for m3. I havent moved on to m4 and m2.

C++:

Input Matrix: 1 1.2 0.89
0.88 1 5.1
1.1 0.15 1
0 to 1 and 1 to 0
1 to 0 and 0 to 1
0 to 1, 1 to 2 and 2 to 0
1 to 2, 2 to 0 and 0 to 1
2 to 0, 0 to 1 and 1 to 2

My method does not use that advanced skills Alain used.

My thought is: When you do currency arbitrage, the currency you buy this time is the currency you will sell next time. And currency you hold at time 0 is still the currency you hold at the final time. When I transfer this economic thought into mathematical expression, it turns out to be return = matrix[j]*matrix[j][k]*matrix[k] or return = matrix[j]*matrix[j], while i, j, k cannot be equal pairwisely. If return - matrix, which is 1, is larger than 0.01, there is arbitrage opportunity, output the result.

Muting

alain · 8/31/07

Muting said:
Alain:
My method does not use that advanced skills Alain used.

My thought is: When you do currency arbitrage, the currency you buy this time is the currency you will sell next time. And currency you hold at time 0 is still the currency you hold at the final time. When I transfer this economic thought into mathematical expression, it turns out to be return = matrix[j]*matrix[j][k]*matrix[k] or return = matrix[j]*matrix[j], while i, j, k cannot be equal pairwisely. If return - matrix, which is 1, is larger than 0.01, there is arbitrage opportunity, output the result.

Muting

Muting, how do you generalize this methodology? That will be the key.

My first idea was still to use the adjacency matrix as a graph and to come up with something similar to what you mentioned, but it is very inefficient when the matrix grows.

Soar · 11/8/08

Arbitrage: Show me the code

alain said:
Here is the output of for the 4x4 matrix.

C++:

List of possible arbitrage sequences: 3 0 1 3 3 0 2 1 3 3 2 0 1 3 3 2 0 3 3 2 1 3 2 0 1 2 2 0 1 3 2 2 0 3 2 2 1 3 0 2 2 1 3 2 1 2 0 1 1 3 0 1 1 3 0 2 1 1 3 2 0 1 1 3 2 1 0 1 2 0 0 1 3 0 0 1 3 2 0 0 2 1 3 0 0 3 2 0

Here is the output of for the 2x2 matrix.

C++:

No arbitrage sequence found.

ExSan · 11/9/08

My Output

C++:

k Arbitrage
max 25 n -> 3
Conversion Rate_ Currency 1 vs. Currency 2 -> 1.2
Conversion Rate_ Currency 1 vs. Currency 3 -> 0.89
Conversion Rate_ Currency 2 vs. Currency 1 -> 0.88
Conversion Rate_ Currency 2 vs. Currency 3 -> 5.1
Conversion Rate_ Currency 3 vs. Currency 1 -> 1.1
Conversion Rate_ Currency 3 vs. Currency 2 -> 0.15
INITIAL NET 
WORKSHEET A[3, 3]
<--------------------------------------------->
1: 1          1.2    0.89
2: 0.88        1      5.1
3: 1.1     0.15         1
>---------------------------------------------<
1 2
buy currency 2 3 1
 
 
k Arbitrage
max 25 n -> 4
Conversion Rate_ Currency 1 vs. Currency 2 -> 3.1
Conversion Rate_ Currency 1 vs. Currency 3 -> 0.0023
Conversion Rate_ Currency 1 vs. Currency 4 -> 0.35
Conversion Rate_ Currency 2 vs. Currency 1 -> 0.21
Conversion Rate_ Currency 2 vs. Currency 3 -> 0.00353
Conversion Rate_ Currency 2 vs. Currency 4 -> 8.13
Conversion Rate_ Currency 3 vs. Currency 1 -> 200
Conversion Rate_ Currency 3 vs. Currency 2 -> 180.559
Conversion Rate_ Currency 3 vs. Currency 4 -> 10.339
Conversion Rate_ Currency 4 vs. Currency 1 -> 2.11
Conversion Rate_ Currency 4 vs. Currency 2 -> 0.089
Conversion Rate_ Currency 4 vs. Currency 3 -> 0.06111
INITIAL NET 
WORKSHEET A[4, 4]
<------------------------------------------------------------>
1:     1           3.1          0.0023          0.35
2: 0.21             1       0.00353           8.13
3: 200   180.559                 1        10.339
4: 2.11      0.089      0.06111                 1
>------------------------------------------------------------<
1 2
buy currency 2 4 1
 
k Arbitrage
max 25 n -> 2
Conversion Rate_ Currency 1 vs. Currency 2 -> 2
Conversion Rate_ Currency 2 vs. Currency 1 -> 0.45
INITIAL NET 
WORKSHEET A[2, 2]
<------------------------------>
1:      1        2
2: 0.45        1
>------------------------------<
1 2
buy currency 2 2
!no arbitrage sequence exit

Soar · 11/10/08

Calculate Arbitrage Profit.

Thanks ExSan!

A Java Code as I have listed below will merely produce the matrix you stated.

But, how would you calculate the profit?

Once again, thanks a lot!

C++:

import java.util.ArrayList;
/**
 * @author Soar
 *
 */
public class Abitrage {
 /**
  * 
  */
 public Abitrage() {
  // TODO Auto-generated constructor stub
 }
 /**
  * @param args
  */
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  //double m[][][] = new double[3][3][3];
  ArrayList myList = new ArrayList();
  ArrayList myMatrix = new ArrayList();
  
  //double [] matrix = new double[3];
  
  String line = "1.2 .89";
  myList.add(line);
  
  line = ".88 5.1";
  myList.add(line);
  
  line = "1.1 0.15";
  myList.add(line);
  
  /*
   String myline = (String) myList.get(i);
   //System.out.println("myline = " + myline);
   String [] strInputArray = myline.split(" ");
   
   final int sizeOfMatrix = strInputArray.length + 1;
   */
  final int sizeOfMatrix = 3;
  //String [] strInputArray = null;
  
  for (int i = 0; i < myList.size(); i++){
   String myline = (String) myList.get(i);
   //System.out.println("myline = " + myline);
   String [] strInputArray = myline.split(" ");
   
   //System.out.println("strInputArray[0] = " + strInputArray[0]);
   //System.out.println("strInputArray[1] = " + strInputArray[1]);
   
   double [] matrix = new double[sizeOfMatrix];
   for (int k = 0; k < matrix.length; k++){
    /*
    if ((k == 0) && (i == 0)){
    
      matrix[k] = 1;
      matrix[k + 1] = Double.parseDouble(strInputArray[k]);
      ++k;
    
    }else */
    if(k < strInputArray.length){
     if (i == k){
      matrix[k] = 1;
      matrix[k + 1] = Double.parseDouble(strInputArray[k]);
      ++k;
     }else{
      matrix[k] = Double.parseDouble(strInputArray[k]);
     }
    }else{
     if (i == k){
      matrix[k] = 1;
     }else{
      matrix[k] = Double.parseDouble(strInputArray[k - 1]);
     }
    }
    
    /*
    System.out.print(matrix[k] + " ");
    
    if (k == matrix.length - 1){
     System.out.println("");
    }
    */
   }
   myMatrix.add(matrix);
  }
  //myList.add()
  /*
   1.2 .89
  .88 5.1
  1.1 0.15
   */
  
  for (int i = 0; i < myMatrix.size(); i++){
   double [] localMatrix = new double[sizeOfMatrix];
   localMatrix = (double [])myMatrix.get(i);
   for (int k = 0; k < localMatrix.length; k++){
    System.out.print(localMatrix[k] + " ");
    
    if (k == localMatrix.length - 1){
     System.out.println("");
    }
   }
  }
  
 }
}

ExSan · 11/10/08

more arbitrage data matrix

Challenging your code:

C++:

  k Arbitrage 
    Currency Trader Matrix
    WORKSHEET A[5, 5]
        <----------------------------------->
               A      B      C      D      E 
       1:      1    1.3    2.3   0.14   0.17
       2:   0.94      1   0.42    2.6    3.1
       3:   0.33   0.44      1    3.1    2.2
       4:     95     34    3.1      1     13
       5:    3.4    6.1    3.5    3.6      1
        >-----------------------------------<
     1  3
 
     buy currency 3   4   1
   
 
  k Arbitrage
    max 25     n -> 5
    Currency Trader Matrix
    WORKSHEET A[5, 5]
        <----------------------------------->
               A      B      C      D      E 
       1:      1    1.2   0.55   0.17   0.17
       2:   0.97      1  0.001    2.3    3.1
       3:    2.3    1.6      1    3.4      3
       4:      4      3   0.14      1   0.14
       5:   0.14   0.15   0.15   0.17      1
        >-----------------------------------<
     1  2
     buy currency 2   5   5   5   5
   !no arbitrage sequence exists
 
  k Arbitrage
    max 25     n -> 4
    Currency Trader Matrix
    WORKSHEET A[4, 4]
        <---------------------------->
               A      B      C      D 
       1:        1    3.1   0.46   0.46
       2:   0.47      1      2    3.5
       3:    5.5    3.5      1    2.6
       4:    1.2   0.16   0.16      1
        >----------------------------<
     1  2
      buy currency 2   4   1

ExSan · 11/10/08

Soar said:
Thanks ExSan!

A Java Code as I have listed below will merely produce the matrix you stated.

But, how would you calculate the profit?

Once again, thanks a lot!

Wallstyouth said:
.....
.....

track arbitrage index loop - this case 6.4%

ExSan · 11/10/08

ARBITRAGE

C++:

                                               Mon Nov 10 20:37:45 2008
    EXSAN v3.18.kk - [EMAIL="exsan.software@gmail.com"]exsan.software@gmail.com[/EMAIL]   [EMAIL="exsan@uio.satnet.net"]exsan@uio.satnet.net[/EMAIL]
 
 
    E X S A N     M E N U
    Forum Solver Menu
  k Arbitrage
    INPUT DATA: 1
    0 ---> exit 
    Your Data File in c:\exsan\     Data file  ---> arb10
    Data will be read from File ---> c:\exsan\arb10.txt
    Loading WorkSheet A
    ARBITRAGE - Currency Trader Matrix
    WORKSHEET A[10, 10]
          <---------------------------------------------------------------------->
                 A      B      C      D      E      F      G      H      I      J 
         1:      1    1.1      7   0.52    2.9    1.2   0.12    3.6    1.4    2.3
         2:    0.9      1    1.7     25      2  0.016    5.9    1.3    1.2    1.1
         3:   0.14    0.6      1   0.77    1.6   0.78      8    1.4    2.2    2.5
         4:    1.9   0.04    1.3      1    1.6      1    1.1     14    2.1    1.2
         5:   0.35    0.5   0.63   0.61      1      4   0.36    1.8     41    1.9
         6:   0.83     63    1.3   0.97   0.25      1    1.4    1.6   0.97    2.3
         7:    8.3   0.17   0.13   0.88    2.8   0.71      1    4.3   0.89    0.7
         8:   0.28   0.75   0.75  0.071   0.56   0.64   0.23      1    1.3    3.5
         9:   0.71   0.85   0.45   0.47  0.025      1    1.1   0.79      1      3
        10:   0.43   0.91    0.4   0.86   0.53   0.44    1.4   0.29   0.34      1
          >----------------------------------------------------------------------<
    ARBITRAGE - Currency Sequence Matrix
    ROW1:   ID CURRENCY  ROW2:   CURRENCY TRADE PRICE
    WORKSHEET B[2, 11]
          <----------------------------------------------------------------------------->
                 A      B      C      D      E      F      G      H      I      J      K 
         1:      1      3      7      1      0      0      0      0      0      0      0
         2:      1      7      8    8.3      0      0      0      0      0      0      0
          >-----------------------------------------------------------------------------<
    Profit = 46173.26%
 
 
 
    E X S A N     M E N U
    Forum Solver Menu
  k Arbitrage
    INPUT DATA: 1
    0 ---> exit 
    Your Data File in c:\exsan\     Data file  ---> arb9
    Data will be read from File ---> c:\exsan\arb9.txt
    Loading WorkSheet A
    ARBITRAGE - Currency Trader Matrix
    WORKSHEET A[9, 9]
          <--------------------------------------------------------------->
                 A      B      C      D      E      F      G      H      I 
         1:      1    1.4   0.65  0.054   0.37    1.2    3.1    0.7      5
         2:    0.7      1    3.6   0.43    2.2    1.1    1.1    1.4    4.2
         3:    1.5   0.27      1     13   0.07    3.3    3.1    1.3    1.2
         4:     19    2.3  0.075      1    1.7   0.11    6.9    3.4    2.4
         5:    2.7   0.46     14   0.59      1    1.9    1.6      2  0.062
         6:   0.87   0.87    0.3    8.9   0.52      1     11    3.6      1
         7:   0.32   0.93   0.32   0.15   0.63  0.095      1      2    4.4
         8:    1.4   0.71   0.76    0.3   0.51   0.27    0.5      1    1.8
         9:    0.2   0.24   0.84   0.42     16   0.98   0.23   0.55      1
          >---------------------------------------------------------------<
    ARBITRAGE - Currency Sequence Matrix
    ROW1:   ID CURRENCY  ROW2:   CURRENCY TRADE PRICE
    WORKSHEET B[2, 10]
          <---------------------------------------------------------------------->
                 A      B      C      D      E      F      G      H      I      J 
         1:      1      9      5      3      4      1      0      0      0      0
         2:      1      5     16     14     13     19      0      0      0      0
          >----------------------------------------------------------------------<
    Profit = 28706178%
 
 
    E X S A N     M E N U
    Forum Solver Menu
  k Arbitrage
    INPUT DATA: 1
    0 ---> exit 
    Your Data File in c:\exsan\     Data file  ---> arb8
    Data will be read from File ---> c:\exsan\arb8.txt
    Loading WorkSheet A
    ARBITRAGE - Currency Trader Matrix
    WORKSHEET A[8, 8]
          <-------------------------------------------------------->
                 A      B      C      D      E      F      G      H 
         1:      1    1.5      2   0.38    1.1     10    2.9    4.7
         2:   0.65      1      2     13   0.37    1.1   0.39      8
         3:   0.51   0.51      1    3.4    1.4    4.2    1.3    1.3
         4:    2.7  0.078   0.29      1    1.6    1.8   0.76    1.2
         5:   0.88    2.7   0.72   0.63      1   0.37    2.1    1.3
         6:  0.098   0.93   0.24   0.57    2.7      1    1.8  0.092
         7:   0.35    2.6   0.76    1.3   0.48   0.55      1    1.7
         8:   0.21   0.12   0.79   0.81   0.79     11    0.6      1
          >--------------------------------------------------------<
    ARBITRAGE - Currency Sequence Matrix
 
    ROW1:   ID CURRENCY  ROW2:   CURRENCY TRADE PRICE
    WORKSHEET B[2, 9]
          <--------------------------------------------------------------->
                 A      B      C      D      E      F      G      H      I 
         1:      1      6      5      2      4      1      0      0      0
         2:      1     10    2.7    2.7     13    2.7      0      0      0
          >---------------------------------------------------------------<
    Profit = 253220.31%
 
 
    E X S A N     M E N U
    Forum Solver Menu
  k Arbitrage
    INPUT DATA: 1
    0 ---> exit 
    Your Data File in c:\exsan\     Data file  ---> arb7
    Data will be read from File ---> c:\exsan\arb7.txt
    Loading WorkSheet A
    ARBITRAGE - Currency Trader Matrix
    WORKSHEET A[7, 7]
          <------------------------------------------------->
                 A      B      C      D      E      F      G 
         1:      1   0.07      5    1.5    8.4    7.6    2.2
         2:     14      1    2.7  0.057    1.9     17    3.1
         3:    0.2   0.37      1     11  0.023    3.9   0.24
         4:   0.68     18  0.091      1    1.5    1.6    2.1
         5:   0.12   0.54     44   0.68      1    2.3    1.3
         6:   0.13  0.058   0.26   0.62   0.44      1    2.6
         7:   0.46   0.32    4.1   0.48   0.78   0.38      1
          >-------------------------------------------------<
    ARBITRAGE - Currency Sequence Matrix
    ROW1:   ID CURRENCY  ROW2:   CURRENCY TRADE PRICE
    WORKSHEET B[2, 8]
          <-------------------------------------------------------->
                 A      B      C      D      E      F      G      H 
         1:      1      5      3      4      2      6      7      3
         2:      1    8.4     44     11     18     17    2.6    4.1
          >--------------------------------------------------------<
    ! There Is No Arbitrage Sequence
    Forum Solver Menu
    E X S A N     M E N U
    MAIN MENU
    Main M E N U
  0 Exit From   Pixsan/Exsan M E N U
    EXSAN v3.18.k - [EMAIL="exsan.software@gmail.com"]exsan.software@gmail.com[/EMAIL]   [EMAIL="exsan@uio.satnet.net"]exsan@uio.satnet.net[/EMAIL]
    Once in a while recycle  unwanted files from c:\exsan\ 
 
    EXIT FROM EXSAN                            Mon Nov 10 20:41:49 2008

Soar · 11/12/08

Arbitrage Decision

Thanks a million times, ExSan!

I am still learning this routine.

Just to make sure I understand you correctly, we calculate the profit in each and every row independently; correct?

E.g.:

C++:

         col1    col2  col3           &Profit
row1      1       2      3         (((1 * 2 * 3) - 1)/1) * 100%
row2      2       1      3         (((2 * 1 * 3) - 2)/2) * 100%
row3      3       2      1         (((3 * 2 * 1) - 3)/3) * 100%

Now, could you please, educate me on how you make the decision of what currencies to buy.

E.g.: How did they make these decisions in the sample code below?

This is hoping that those decisions were rightly made! Thanks!!

C++:

<----------------------------------------------------------------------------------
[SIZE=2]1.0000 1.3908 2475.0000 1.4304 3.4519 1.4394 0.9982 2.1677[/SIZE]
[SIZE=2]0.7047 1.0000 1761.7050 1.0182 2.4571 1.0245 0.7105 1.5430[/SIZE]
[SIZE=2]0.0004 0.0006 1.0000 0.0006 0.0014 0.0006 0.0004 0.0009[/SIZE]
[SIZE=2]0.6852 0.9626 1712.9475 1.0000 2.3890 0.9962 0.6908 1.5003[/SIZE]
[SIZE=2]0.2839 0.3989 709.8300 0.4102 1.0000 0.4128 0.2863 0.6217[/SIZE]
[SIZE=2]0.6809 0.9566 1702.3050 0.9838 2.3742 1.0000 0.6866 1.4910[/SIZE]
[SIZE=2]0.9819 1.3794 2454.7050 1.4187 3.4236 1.4276 1.0000 2.1499[/SIZE]
[SIZE=2]0.4521 0.6352 1130.3325 0.6533 1.5765 0.6574 0.4559 1.0000[/SIZE]
 
[SIZE=2]buy currency 3 2 3[/SIZE]
[SIZE=2]----------------------------------------------------------->[/SIZE]
 
[SIZE=2][SIZE=2]1.0000 4.0657 4.2003 0.9612 0.2156[/SIZE]
[SIZE=2]0.2411 1.0000 1.0098 0.2311 0.0539[/SIZE]
[SIZE=2]0.2333 0.9705 1.0000 0.2209 0.0515[/SIZE]
[SIZE=2]1.0196 4.2409 4.4369 1.0000 0.2278[/SIZE]
[SIZE=2]4.5448 18.1970 19.0401 4.3024 1.0000[/SIZE]
 
 
[FONT=Times New Roman]buy currency 5 1 4 3 2 5[/FONT]
 
[FONT=Times New Roman]---------------------------------------------------------------------------------------------------------->[/FONT]
 
[FONT=Times New Roman][SIZE=2]1.0000  0.5300   0.9789     0.2388   77.3438[/SIZE][/FONT]
[SIZE=2][FONT=Times New Roman]1.8491  1.0000   1.8284     0.4460   144.4597[/FONT][/SIZE]
[SIZE=2][FONT=Times New Roman]1.0012   0.5360  1.0000     0.2415   78.2198[/FONT][/SIZE]
[SIZE=2][FONT=Times New Roman]4.1045   2.1975   4.0585   1.0000    320.6623[/FONT][/SIZE]
[SIZE=2][FONT=Times New Roman]0.0127   0.0068   0.0125    0.0031   1.0000[/FONT][/SIZE]
 
[/SIZE]!no arbitrage sequence exists

ExSan · 11/12/08

ref views 1200
..............
working out SOAR ARBITRAGE data

C++:

                                               Wed Nov 12 14:38:16 2008
    EXSAN v3.18.kk - [EMAIL="exsan.software@gmail.com"]exsan.software@gmail.com[/EMAIL]   [EMAIL="exsan@uio.satnet.net"]exsan@uio.satnet.net[/EMAIL]
    E X S A N     M E N U
    Forum Solver Menu
  k Arbitrage
    INPUT DATA: 1
    0 ---> exit 
    Your Data File in c:\exsan\     Data file  ---> soar1
    Data will be read from File ---> c:\exsan\soar1.txt
    Loading WorkSheet A
    ARBITRAGE - Currency Trader Matrix
    WORKSHEET A[8, 8]
          <-------------------------------------------------------->
                 A      B      C      D      E      F      G      H 
         1:      1    1.4 2.5e+003    1.4    3.5    1.4      1    2.2
         2:    0.7      1 1.8e+003      1    2.5      1   0.71    1.5
         3: 0.0004 0.0006      1 0.0006 0.0014 0.0006 0.0004 0.0009
         4:   0.69   0.96 1.7e+003      1    2.4      1   0.69    1.5
         5:   0.28    0.4 7.1e+002   0.41      1   0.41   0.29   0.62
         6:   0.68   0.96 1.7e+003   0.98    2.4      1   0.69    1.5
         7:   0.98    1.4 2.5e+003    1.4    3.4    1.4      1    2.1
         8:   0.45   0.64 1.1e+003   0.65    1.6   0.66   0.46      1
          >--------------------------------------------------------<
    - BEST ARBITRAGE SEQUENCE MATRIX Index ---> 3
    ROW1: Currency Sequence  ROW2:  Price Of Change
    WORKSHEET B[2, 9]
          <--------------------------------------------------------------->
                 A      B      C      D      E      F      G      H      I 
         1:      3      5      3      0      0      0      0      0      0
         2:      1 0.0014 7.1e+002    0      0      0      0      0      0
          >---------------------------------------------------------------<
    Profit = -0.6238%
 -  !INVESTMENT WARNING!, better keep your money in a safe place
 
    [1..8]  Arbitrage Currency Index Id -> 1
    ARBITRAGE - Currency Sequence Matrix Selected Index --->1
    ROW1: Currency Sequence  ROW2:  Price Of Change
    WORKSHEET B[2, 9]
          <--------------------------------------------------------------->
                 A      B      C      D      E      F      G      H      I 
         1:      1      3      5      3      5      3      5      3      5
         2:      1 2.5e+003 0.0014 7.1e+002 0.0014 7.1e+002 0.0014 7.1e+002 0.0014
          >---------------------------------------------------------------<
    ! There Is No Arbitrage Sequence
    0 EXIT Arbitrage Again (1-y-Y | N-n-0) ? --->   no
 
 
    Forum Solver Menu
  k Arbitrage
    INPUT DATA: 1
    0 ---> exit 
    Your Data File in c:\exsan\     Data file  ---> soar2
    Data will be read from File ---> c:\exsan\soar2.txt
    Loading WorkSheet A
    ARBITRAGE - Currency Trader Matrix
    WORKSHEET A[5, 5]
          <----------------------------------->
                 A      B      C      D      E 
         1:      1    4.1    4.2   0.96   0.22
         2:   0.24      1      1   0.23  0.054
         3:   0.23   0.97      1   0.22  0.051
         4:      1    4.2    4.4      1   0.23
         5:    4.5     18     19    4.3      1
          >-----------------------------------<
    - BEST ARBITRAGE SEQUENCE MATRIX Index ---> 2
    ROW1: Currency Sequence  ROW2:  Price Of Change
    WORKSHEET B[2, 6]
          <------------------------------------------>
                 A      B      C      D      E      F 
         1:      2      3      2      0      0      0
         2:      1      1   0.97      0      0      0
          >------------------------------------------<
    Profit = -1.99891%
 -  !INVESTMENT WARNING!, better keep your money in a safe place
 
    [1..5]  Arbitrage Currency Index Id -> 1
    ARBITRAGE - Currency Sequence Matrix Selected Index --->1
    ROW1: Currency Sequence  ROW2:  Price Of Change
    WORKSHEET B[2, 6]
          <------------------------------------------>
                 A      B      C      D      E      F 
         1:      1      3      2      3      2      3
         2:      1    4.2   0.97      1   0.97      1
          >------------------------------------------<
    ! There Is No Arbitrage Sequence
    0 EXIT Arbitrage Again (1-y-Y | N-n-0) ? --->   no
 
 
 
    Forum Solver Menu
  k Arbitrage
    INPUT DATA: 1
    0 ---> exit 
    Your Data File in c:\exsan\     Data file  ---> soar3
    Data will be read from File ---> c:\exsan\soar3.txt
    Loading WorkSheet A
    ARBITRAGE - Currency Trader Matrix
    WORKSHEET A[5, 5]
          <----------------------------------->
                 A      B      C      D      E 
         1:      1   0.53   0.98   0.24     77
         2:    1.8      1    1.8   0.45 1.4e+002
         3:      1   0.54      1   0.24     78
         4:    4.1    2.2    4.1      1 3.2e+002
         5:  0.013 0.0068  0.013 0.0031      1
          >-----------------------------------<
    - BEST ARBITRAGE SEQUENCE MATRIX Index ---> 1
    ROW1: Currency Sequence  ROW2:  Price Of Change
    WORKSHEET B[2, 6]
          <------------------------------------------>
                 A      B      C      D      E      F 
         1:      1      5      1      0      0      0
         2:      1     77  0.013      0      0      0
          >------------------------------------------<
    Profit = -1.773374%
 -  !INVESTMENT WARNING!, better keep your money in a safe place
 
------------->  FULL ANNALYSiS OF soar3   index  1..5
    [1..5]  Arbitrage Currency Index Id -> 1
    ARBITRAGE - Currency Sequence Matrix Selected Index --->1
    ROW1: Currency Sequence  ROW2:  Price Of Change
    WORKSHEET B[2, 6]
          <------------------------------------------>
                 A      B      C      D      E      F 
         1:      1      5      1      0      0      0
         2:      1     77  0.013      0      0      0
          >------------------------------------------<
    Profit = -1.773374%
 -  !INVESTMENT WARNING!, better keep your money in a safe place
    0 EXIT Arbitrage Again (1-y-Y | N-n-0) ? --->   yes
    [1..5]  Arbitrage Currency Index Id -> 2
    ARBITRAGE - Currency Sequence Matrix Selected Index --->2
    ROW1: Currency Sequence  ROW2:  Price Of Change
    WORKSHEET B[2, 6]
          <------------------------------------------>
                 A      B      C      D      E      F 
         1:      2      5      1      5      1      5
         2:      1 1.4e+002  0.013     77  0.013     77
          >------------------------------------------<
    ! There Is No Arbitrage Sequence
    0 EXIT Arbitrage Again (1-y-Y | N-n-0) ? --->   yes
    [1..5]  Arbitrage Currency Index Id -> 3
    ARBITRAGE - Currency Sequence Matrix Selected Index --->3
    ROW1: Currency Sequence  ROW2:  Price Of Change
    WORKSHEET B[2, 6]
          <------------------------------------------>
                 A      B      C      D      E      F 
         1:      3      5      1      5      1      5
         2:      1     78  0.013     77  0.013     77
          >------------------------------------------<
    ! There Is No Arbitrage Sequence
    0 EXIT Arbitrage Again (1-y-Y | N-n-0) ? --->   yes
    [1..5]  Arbitrage Currency Index Id -> 4
    ARBITRAGE - Currency Sequence Matrix Selected Index --->4
    ROW1: Currency Sequence  ROW2:  Price Of Change
    WORKSHEET B[2, 6]
          <------------------------------------------>
                 A      B      C      D      E      F 
         1:      4      5      1      5      1      5
         2:      1 3.2e+002  0.013     77  0.013     77
          >------------------------------------------<
    ! There Is No Arbitrage Sequence
    0 EXIT Arbitrage Again (1-y-Y | N-n-0) ? --->   yes
    [1..5]  Arbitrage Currency Index Id -> 5
    ARBITRAGE - Currency Sequence Matrix Selected Index --->5
    ROW1: Currency Sequence  ROW2:  Price Of Change
    WORKSHEET B[2, 6]
          <------------------------------------------>
                 A      B      C      D      E      F 
         1:      5      1      5      0      0      0
         2:      1  0.013     77      0      0      0
          >------------------------------------------<
    Profit = -1.773374%
 -  !INVESTMENT WARNING!, better keep your money in a safe place
    0 EXIT Arbitrage Again (1-y-Y | N-n-0) ? --->   yes
    [1..5]  Arbitrage Currency Index Id ->     Try a smaller Index ...
    Forum Solver Menu
    E X S A N     M E N U
    MAIN MENU
    Main M E N U
  0 Exit From   Pixsan/Exsan M E N U
    EXSAN v3.18.kk - [EMAIL="exsan.software@gmail.com"]exsan.software@gmail.com[/EMAIL]   [EMAIL="exsan@uio.satnet.net"]exsan@uio.satnet.net[/EMAIL]
    Once in a while recycle  unwanted files from c:\exsan\ 
 
    EXIT FROM EXSAN                            Wed Nov 12 14:42:33 2008

ExSan · 11/13/08

1250

Soar said:
Just to make sure I understand you correctly, we calculate the profit in each and every row independently; correct?

No

C++:

                                               Thu Nov 13 06:11:49 2008
    EXSAN v3.18.kk - [EMAIL="exsan.software@gmail.com"]exsan.software@gmail.com[/EMAIL]   [EMAIL="exsan@uio.satnet.net"]exsan@uio.satnet.net[/EMAIL]
    E X S A N     M E N U
    Forum Solver Menu
 
  k Arbitrage
    INPUT DATA: 1
    0 ---> exit 
    Your Data File in c:\exsan\     Data file  ---> arb
    Data will be read from File ---> c:\exsan\arb.txt
    Loading WorkSheet A
    ARBITRAGE - Currency Trader Matrix
    WORKSHEET A[5, 5]
          <----------------------------------->
                 A      B      C      D      E 
         1:      1   0.53   0.98   0.24    2.9
         2:    1.9      1    1.8   0.45   0.94
         3:      1   0.54      1   0.24     78
         4:    4.1    2.2    4.1      1    3.4
         5:   0.01   0.01   0.01      0      1
          >-----------------------------------<
    This data should be different of 1 or 0,  at this coord    (3, 1)
    Type in the correct val ---> 0.66
    Page has been modified
    WORKSHEET A[5, 5]
          <----------------------------------->
                 A      B      C      D      E 
         1:      1   0.53   0.98   0.24    2.9
         2:    1.9      1    1.8   0.45   0.94
         3:   0.66   0.54      1   0.24     78
         4:    4.1    2.2    4.1      1    3.4
         5:   0.01   0.01   0.01      0      1
          >-----------------------------------<
    This data should be different of 1 or 0,  at this coord    (5, 4)
    Type in the correct val ---> 0.3
    Page has been modified
    WORKSHEET A[5, 5]
          <----------------------------------->
                 A      B      C      D      E 
         1:      1   0.53   0.98   0.24    2.9
         2:    1.9      1    1.8   0.45   0.94
         3:   0.66   0.54      1   0.24     78
         4:    4.1    2.2    4.1      1    3.4
         5:   0.01   0.01   0.01    0.3      1
          >-----------------------------------<
    Save Edited Arbitrage Matrix to file (1-y-Y | N-n-0) ? --->   no
    - BEST ARBITRAGE SEQUENCE MATRIX Index ---> 1
    ROW1: Currency Sequence  ROW2:  Price Of Change
    WORKSHEET B[2, 6]
          <------------------------------------------>
                 A      B      C      D      E      F 
         1:      1      5      4      1      0      0
         2:      1    2.9    0.3    4.1      0      0
          >------------------------------------------<
    BEST Profit =  256.7%
[B][SIZE=4]---> math calc for profit [/SIZE][/B]
[B][SIZE=4]     ((2.9*0.3*4.1) - 1 ) * 100 = 256.7[/SIZE][/B]   
 
    [1..5]  Arbitrage Currency Index Id -> 
    Forum Solver Menu
    E X S A N     M E N U
    MAIN MENU
    Main M E N U
  0 Exit From   Pixsan/Exsan M E N U
    EXSAN v3.18.kk - [EMAIL="exsan.software@gmail.com"]exsan.software@gmail.com[/EMAIL]   [EMAIL="exsan@uio.satnet.net"]exsan@uio.satnet.net[/EMAIL]
    Once in a while recycle  unwanted files from c:\exsan\ 
 
    EXIT FROM EXSAN                            Thu Nov 13 06:16:21 2008

ExSan · 11/17/08

ref:1380

Code Improvement
Real Data market is provided by bloomberg.com in a different format
Updated: New York, Nov 17 05:02 London, Nov 17 10:02 Tokyo, Nov 17 19:02
"Arbitrage" matrix looks like:

C++:

Bloomberg.com
Updated:  New York, Nov 17 05:04London, Nov 17 10:04Tokyo, Nov 17 19:04  
 
        USD      EUR     JPY      GBP           CHF        CAD        AUD        HKD 
HKD 7.7502   9.8129   0.0801         11.5632     6.5015   6.3084    5.0593   
AUD 1.5319   1.9396   0.0158         2.2855     1.2851    1.2469                  0.1977 
CAD 1.2286   1.5555   0.0127         1.833       1.0306                0.802     0.1585 
CHF 1.192     1.5093   0.0123         1.7785               0.9703      0.7782    0.1538 
GBP 0.6702   0.8486   0.0069                    0.5623    0.5456       0.4375    0.0865 
JPY  96.78    122.538               144.3958    81.1879  78.7758       63.178    12.4875 
EUR 0.7898                 0.0082   1.1784      0.6626    0.6429       0.5156    0.1019 
USD              1.2662   0.0103   1.492        0.8389    0.814       0.6528     0.129

Is it possible to make some money at this moment?

C++:

                                               Mon Nov 17 05:11:27 2008
    EXSAN v3.18.kk - [EMAIL="exsan.software@gmail.com"]exsan.software@gmail.com[/EMAIL]   [EMAIL="exsan@uio.satnet.net"]exsan@uio.satnet.net[/EMAIL]
    E X S A N     M E N U
  3 Matrix Operations->  Load [A] and [b]
    M E N U    - MATRIX -  
  c (C)holesky Factorization 
  + (A)dd 
  - (S)ubstraction
  * (M)ultiply
  t (T)ranspose -At-
  i (I)nverse  -Ai- 
  d (D)eterminant |A|
  l (L)inear System Eq.
  x (X) Multiply peer to peer A x B
  y (Y) Divide peer to peer   A / B
  1 |A| scalar add  
  2 |A| scalar minus 
  3 |A| scalar *  
  4 |A| scalar / 
  5 |A| Rotate Clock Wise
  6 |A| Rotate Counter Clock Wise
  7 |A| Flip Horizontal <-->
  8 |A| Flip Vertical |  
  9 |A| Rotate Vertical
  0 EXIT [Back to Previous Menu]  Option ---> 7
    MATRIX  C = A Flip Horizontal <--->
    MATRIX A
    INPUT DATA: 
    1 From File
    0 ---> exit 
    Your Data File in c:\exsan\     Data file  ---> bn17_05_04x
    Data will be read from File ---> c:\exsan\bn17_05_04x.txt
    File/Matrix A  rows: 8   cols: 8
    WORKSHEET A[8, 8]
        <-------------------------------------------------------->
                 A       B       C       D       E       F       G       H 
       1:    7.75    9.81  0.0801    11.6     6.5    6.31    5.06       1
       2:    1.53    1.94  0.0158    2.29    1.29    1.25       1   0.198
       3:    1.23    1.56  0.0127    1.83    1.03       1   0.802   0.159
       4:    1.19    1.51  0.0123    1.78       1    0.97   0.778   0.154
       5:    0.67   0.849  0.0069       1   0.562   0.546   0.438  0.0865
       6:    96.8     123       1     144    81.2    78.8    63.2    12.5
       7:    0.79       1  0.0082    1.18   0.663   0.643   0.516   0.102
       8:       1    1.27  0.0103    1.49   0.839   0.814   0.653   0.129
        >--------------------------------------------------------<
    WORKSHEET B[8, 8]
         <-------------------------------------------------------->
                  A       B       C       D       E       F       G       H 
        1:       1     5.1     6.3     6.5      12    0.08     9.8     7.8
        2:     0.2       1     1.2     1.3     2.3   0.016     1.9     1.5
        3:    0.16     0.8       1       1     1.8   0.013     1.6     1.2
        4:    0.15    0.78    0.97       1     1.8   0.012     1.5     1.2
        5:   0.086    0.44    0.55    0.56       1  0.0069    0.85    0.67
        6:      12      63      79      81 1.4e+002       1 1.2e+002      97
        7:     0.1    0.52    0.64    0.66     1.2  0.0082       1    0.79
        8:    0.13    0.65    0.81    0.84     1.5    0.01     1.3       1
         >--------------------------------------------------------< (1-y-Y | N-n-0) ? --->   yes
    0 ---> exit 
    Your Data File in c:\exsan\     Data file  ---> x
    M E N U    - MATRIX -  
  c (C)holesky Factorization 
  + (A)dd 
  - (S)ubstraction
  * (M)ultiply
  t (T)ranspose -At-
  i (I)nverse  -Ai- 
  d (D)eterminant |A|
  l (L)inear System Eq.
  x (X) Multiply peer to peer A x B
  y (Y) Divide peer to peer   A / B
  1 |A| scalar add  
  2 |A| scalar minus 
  3 |A| scalar *  
  4 |A| scalar / 
  5 |A| Rotate Clock Wise
  6 |A| Rotate Counter Clock Wise
  7 |A| Flip Horizontal <-->
  8 |A| Flip Vertical |  
  9 |A| Rotate Vertical
  0 EXIT [Back to Previous Menu]  Option ---> 0
    E X S A N     M E N U
  F Forum Solver
    Forum Solver Menu
  k Arbitrage
    INPUT DATA: 
    1 From File
    0 ---> exit 
    Your Data File in c:\exsan\     Data file  ---> x
    Data will be read from File ---> c:\exsan\x.txt
    Loading WorkSheet A
    ARBITRAGE - Currency Trader Matrix
    WORKSHEET A[8, 8]
          <-------------------------------------------------------->
                 A      B      C      D      E      F      G      H 
         1:      1    5.1    6.3    6.5     12   0.08    9.8    7.8
         2:    0.2      1    1.2    1.3    2.3  0.016    1.9    1.5
         3:   0.16    0.8      1      1    1.8  0.013    1.6    1.2
         4:   0.15   0.78   0.97      1    1.8  0.012    1.5    1.2
         5:  0.086   0.44   0.55   0.56      1 0.0069   0.85   0.67
         6:     12     63     79     81 1.4e+002      1 1.2e+002     97
         7:    0.1   0.52   0.64   0.66    1.2 0.0082      1   0.79
         8:   0.13   0.65   0.81   0.84    1.5   0.01    1.3      1
          >--------------------------------------------------------<
    - BEST ARBITRAGE SEQUENCE MATRIX Index ---> 5
    ROW1: Currency Sequence  ROW2:  Price Of Change
    WORKSHEET B[2, 9]
          <--------------------------------------------------------------->
                 A      B      C      D      E      F      G      H      I 
         1:      5      7      5      0      0      0      0      0      0
         2:      1   0.85    1.2      0      0      0      0      0      0
          >---------------------------------------------------------------<
    BEST Profit = -0.000976%
 -  !INVESTMENT WARNING!, better keep your money in a safe place
 
    [1..8]  Arbitrage Currency Index Id -> 0
    Forum Solver Menu
  0 Exit Solver
     E X S A N     M E N U
  0 Exit From   E X S A N 
 
    MAIN MENU
    Main M E N U
  0 Exit From   Pixsan/Exsan M E N U
    EXSAN v3.18.kk - [EMAIL="exsan.software@gmail.com"]exsan.software@gmail.com[/EMAIL]   [EMAIL="exsan@uio.satnet.net"]exsan@uio.satnet.net[/EMAIL]
    Once in a while recycle  unwanted files from c:\exsan\ 
 
    EXIT FROM EXSAN                            Mon Nov 17 05:24:06 2008

INDEX ID
1 HKD 2 AUD 3 CAD 4 CHF 5 GBP 6 JPY 7 EUR 8 USD

CERTAINLY NOT AT THIS EXACT MOMENT --->Updated: New York, Nov 17 05:02 London, Nov 17 10:02 Tokyo, Nov 17 19:02

BN17_05_04 ---> BLOOMBERG NOV 17, 05:04 ET

Victor · 11/17/08

Expanding on alain's idea, here is what I did:
I took -ln(conversion rate) for weights of the edges, and used modified Bellman-Ford algorithm to locate negative weight cycles. Also, I added one zero vertex with zero-weight edge to every real vertex to make sure all negative-weight cycles are accessible from the source. Bellman-Ford runs in 0(n^3) and calculates shortest paths from given vertex to the rest and conveniently allows for negative weights and detects negative-weight cycles. To actually figure out which vertexes belong to negative weight cycle I had to modify BF to save all vertex shortest-path lengths(weights?) and run through every edge one more time and see if any of them change. If one does, I just follow the chain of its parents generated by BF to find the actual cycle.
I mostly used the code from Boost Graph Library examples and modified Boost's code for BF to do extra run. I also used custom comparison operator instead of std::less to allow for transaction cost.
I am still not sure about the best way to handle situations with several such cycles. Maybe somehow disable certain edges and run it again ? Suggestions, anybody ? Also, right now it prints out all duplicate cycles, that can be improved too... It is just something I quickly put together from the example code from Boost. I used the same file format as ExSan.
Wallstyouth, thanks for the interesting problem.

Victor · 11/18/08

some examples
transaction cost at 1%, not used when calculating displayed rate of return, only used when finding paths.

C++:

1 1.2 0.55 0.17 0.17 
0.97 1 0.001 2.3 3.1 
2.3 1.6 1 3.4 3 
4 3 0.14 1 0.14 
0.14 0.15 0.15 0.17 1 
4->2->4 Rate of return: 6.9
2->4->2 Rate of return: 6.9
2->4->2 Rate of return: 6.9
4->2->4 Rate of return: 6.9
2->4->2 Rate of return: 6.9

1 1.1065 6.9559 0.5164 2.8782 1.2162 0.1199 3.6096 1.4135 2.3389 
0.9047 1 1.6694 25.067 1.9985 0.0158 5.918 1.3442 1.1827 1.0966 
0.1438 0.6025 1 0.7659 1.5893 0.7842 7.978 1.3506 2.2446 2.5233 
1.9369 0.0399 1.31 1 1.6363 1.0322 1.1365 14.0669 2.1144 1.1778 
0.3475 0.5007 0.631 0.612 1 4.0235 0.3589 1.7951 40.8707 1.8797 
0.8279 63.0211 1.2835 0.9699 0.2489 1 1.4077 1.5608 0.9681 2.2535 
8.3384 0.169 0.1254 0.8827 2.7858 0.7135 1 4.329 0.8884 0.6981 
0.2771 0.7495 0.7458 0.0711 0.5591 0.6418 0.2312 1 1.2707 3.514 
0.7107 0.8479 0.447 0.4735 0.0245 1.0413 1.1255 0.7925 1 2.9558 
0.4287 0.9138 0.3974 0.856 0.533 0.4443 1.4348 0.2852 0.3387 1 
10->5->9->10 Rate of return: 64.3894
10->5->9->10 Rate of return: 64.3894
10->5->9->10 Rate of return: 64.3894
10->5->9->10 Rate of return: 64.3894
5->9->10->5 Rate of return: 64.3894
10->5->9->10 Rate of return: 64.3894
10->5->9->10 Rate of return: 64.3894
10->5->9->10 Rate of return: 64.3894
9->10->5->9 Rate of return: 64.3894
10->5->9->10 Rate of return: 64.3894

1 4.0657 4.2003 0.9612 0.2156 
0.2411 1 1.0098 0.2311 0.0539 
0.2333 0.9705 1 0.2209 0.0515 
1.0196 4.2409 4.4369 1 0.2278 
4.5448 18.197 19.0401 4.3024 1 
1->4->3->2->5->1 Rate of return: 1.01389
5->1->4->3->2->5 Rate of return: 1.01389

1 3.1 0.0023 0.35 
0.21 1 0.00353 8.13 
200 180.559 1 10.339 
2.11 0.089 0.06111 1 
4->3->2->4 Rate of return: 89.7061
2->4->3->2 Rate of return: 89.7061
3->2->4->3 Rate of return: 89.7061
4->3->2->4 Rate of return: 89.7061

1 0.53 0.9789 0.2388 77.3438 
1.8491 1 1.8284 0.446 144.46 
1.0012 0.536 1 0.2415 78.2198 
4.1045 2.1975 4.0585 1 320.662 
0.0127 0.0068 0.0125 0.0031 1 
No arbitrage sequence exists.

Interestingly, If I set transaction cost to 50%, it finds a different sequence for this matrix:

C++:

1 1.1065 6.9559 0.5164 2.8782 1.2162 0.1199 3.6096 1.4135 2.3389 
0.9047 1 1.6694 25.067 1.9985 0.0158 5.918 1.3442 1.1827 1.0966 
0.1438 0.6025 1 0.7659 1.5893 0.7842 7.978 1.3506 2.2446 2.5233 
1.9369 0.0399 1.31 1 1.6363 1.0322 1.1365 14.0669 2.1144 1.1778 
0.3475 0.5007 0.631 0.612 1 4.0235 0.3589 1.7951 40.8707 1.8797 
0.8279 63.0211 1.2835 0.9699 0.2489 1 1.4077 1.5608 0.9681 2.2535 
8.3384 0.169 0.1254 0.8827 2.7858 0.7135 1 4.329 0.8884 0.6981 
0.2771 0.7495 0.7458 0.0711 0.5591 0.6418 0.2312 1 1.2707 3.514 
0.7107 0.8479 0.447 0.4735 0.0245 1.0413 1.1255 0.7925 1 2.9558 
0.4287 0.9138 0.3974 0.856 0.533 0.4443 1.4348 0.2852 0.3387 1 
7->8->10->7 Rate of return: 21.8263
10->7->8->10 Rate of return: 21.8263
10->7->8->10 Rate of return: 21.8263
10->7->8->10 Rate of return: 21.8263
10->7->8->10 Rate of return: 21.8263
10->7->8->10 Rate of return: 21.8263
7->8->10->7 Rate of return: 21.8263
8->10->7->8 Rate of return: 21.8263
10->7->8->10 Rate of return: 21.8263
10->7->8->10 Rate of return: 21.8263

ExSan · 11/18/08

think different

?

.... weights of the edges,
... modified Bellman-Ford algorithm to locate negative weight cycles.
... added one zero vertex with zero-weight edge to every real vertex to make sure all
... negative-weight cycles are accessible from the source.
... Boost Graph Library examples and modified Boost's code for BF to do extra run.
... custom comparison operator instead of std::less to allow for transaction cost.
I am still not sure about the best way to handle situations with several such cycles. Maybe somehow disable certain edges and run it again ? Suggestions, anybody ? Also, right now it prints out all duplicate cycles, that can be improved too... It is just something I quickly put together from the example code from Boost.

?

C++:

                                               Tue Nov 18 13:50:54 2008
    EXSAN v3.18.kk - [EMAIL="exsan.software@gmail.com"]exsan.software@gmail.com[/EMAIL]      E X S A N     M E N U
  9 Forum Solver
    Forum Solver Menu
  k Arbitrage
    INPUT DATA:       2 From Keyboard    Rows ---> 0 
    Forum Solver Menu
  k Arbitrage
    INPUT DATA: 
    1 From File
    0 ---> exit 
    Your Data File in c:\exsan\     Data file  ---> v5
    Data will be read from File ---> c:\exsan\v5.txt
    Loading WorkSheet A
    ARBITRAGE - Currency Trader Matrix
    WORKSHEET A[5, 5]
          <----------------------------------->
                 A      B      C      D      E 
         1:      1    1.2   0.55   0.17   0.17
         2:   0.97      1  0.001    2.3    3.1
         3:    2.3    1.6      1    3.4      3
         4:      4      3   0.14      1   0.14
         5:   0.14   0.15   0.15   0.17      1
          >-----------------------------------<
    - BEST ARBITRAGE SEQUENCE MATRIX Index ---> 5
    ROW1: Currency Sequence  ROW2:  Price Of Change
    WORKSHEET B[2, 6]
          <------------------------------------------>
                 A      B      C      D      E      F 
         1:      5      4      1      2      5      0
         2:      1   0.17      4    1.2    3.1      0
          >------------------------------------------<
    BEST Profit = 152.96%
 
    [1..5]  Arbitrage Currency Index Id -> 4
    ARBITRAGE - Currency Sequence Matrix Selected Index --->4
    ROW1: Currency Sequence  ROW2:  Price Of Change
    WORKSHEET B[2, 6]
                  <------------------------------>
                     A    B    C    D    E    F 
                 1:    4    1    2    5    4    0
                 2:    1    4  1.2  3.1 0.17    0
                  >------------------------------<
    Profit = 152.96%
    0 EXIT Arbitrage Again (1-y-Y | N-n-0) ? --->   yes
    [1..5]  Arbitrage Currency Index Id -> 2
    ARBITRAGE - Currency Sequence Matrix Selected Index --->2
    ROW1: Currency Sequence  ROW2:  Price Of Change
    WORKSHEET B[2, 6]
                  <------------------------------>
                     A    B    C    D    E    F 
                 1:    2    5    4    1    2    0
                 2:    1  3.1 0.17    4  1.2    0
                  >------------------------------<
    Profit = 152.96%
    0 EXIT Arbitrage Again (1-y-Y | N-n-0) ? --->   no
    Forum Solver Menu
  k Arbitrage
    INPUT DATA: 
    1 From File
    0 ---> exit 
    Your Data File in c:\exsan\     Data file  ---> v10
    Data will be read from File ---> c:\exsan\v10.txt
    Loading WorkSheet A
    ARBITRAGE - Currency Trader Matrix
    WORKSHEET A[10, 10]
          <---------------------------------------------------------------------->
                 A      B      C      D      E      F      G      H      I      J 
         1:      1    1.1      7   0.52    2.9    1.2   0.12    3.6    1.4    2.3
         2:    0.9      1    1.7     25      2  0.016    5.9    1.3    1.2    1.1
         3:   0.14    0.6      1   0.77    1.6   0.78      8    1.4    2.2    2.5
         4:    1.9   0.04    1.3      1    1.6      1    1.1     14    2.1    1.2
         5:   0.35    0.5   0.63   0.61      1      4   0.36    1.8     41    1.9
         6:   0.83     63    1.3   0.97   0.25      1    1.4    1.6   0.97    2.3
         7:    8.3   0.17   0.13   0.88    2.8   0.71      1    4.3   0.89    0.7
         8:   0.28   0.75   0.75  0.071   0.56   0.64   0.23      1    1.3    3.5
         9:   0.71   0.85   0.45   0.47  0.025      1    1.1   0.79      1      3
        10:   0.43   0.91    0.4   0.86   0.53   0.44    1.4   0.29   0.34      1
          >----------------------------------------------------------------------<
    - BEST ARBITRAGE SEQUENCE MATRIX Index ---> 1
    ROW1: Currency Sequence  ROW2:  Price Of Change
    WORKSHEET B[2, 11]
          <----------------------------------------------------------------------------->
                 A      B      C      D      E      F      G      H      I      J      K 
         1:      1      3      7      1      0      0      0      0      0      0      0
         2:      1      7      8    8.3      0      0      0      0      0      0      0
          >-----------------------------------------------------------------------------<
    BEST Profit = 46173.259%
 
    [1..10]  Arbitrage Currency Index Id -> 10
    ARBITRAGE - Currency Sequence Matrix Selected Index --->10
    ROW1: Currency Sequence  ROW2:  Price Of Change
    WORKSHEET B[2, 11]
                  <------------------------------------------------------->
                     A    B    C    D    E    F    G    H    I    J    K 
                 1:   10    7    1    3    7    1    3    7    1    3    7
                 2:    1  1.4  8.3    7    8  8.3    7    8  8.3    7    8
                  >-------------------------------------------------------<
    ! There Is No Arbitrage Sequence
    0 EXIT Arbitrage Again (1-y-Y | N-n-0) ? --->   yes
    [1..10]  Arbitrage Currency Index Id -> 10
    ARBITRAGE - Currency Sequence Matrix Selected Index --->10
    ROW1: Currency Sequence  ROW2:  Price Of Change
    WORKSHEET B[2, 11]
                  <------------------------------------------------------->
                     A    B    C    D    E    F    G    H    I    J    K 
                 1:   10    7    1    3    7    1    3    7    1    3    7
                 2:    1  1.4  8.3    7    8  8.3    7    8  8.3    7    8
                  >-------------------------------------------------------<
    ! There Is No Arbitrage Sequence
    0 EXIT Arbitrage Again (1-y-Y | N-n-0) ? --->   yes
    [1..10]  Arbitrage Currency Index Id -> 9
    ARBITRAGE - Currency Sequence Matrix Selected Index --->9
    ROW1: Currency Sequence  ROW2:  Price Of Change
    WORKSHEET B[2, 11]
                  <------------------------------------------------------->
                     A    B    C    D    E    F    G    H    I    J    K 
                 1:    9   10    7    1    3    7    1    3    7    1    3
                 2:    1    3  1.4  8.3    7    8  8.3    7    8  8.3    7
                  >-------------------------------------------------------<
    ! There Is No Arbitrage Sequence
    0 EXIT Arbitrage Again (1-y-Y | N-n-0) ? --->   yes
    [1..10]  Arbitrage Currency Index Id -> 5
    ARBITRAGE - Currency Sequence Matrix Selected Index --->5
    ROW1: Currency Sequence  ROW2:  Price Of Change
    WORKSHEET B[2, 11]
                  <------------------------------------------------------->
                     A    B    C    D    E    F    G    H    I    J    K 
                 1:    5    9   10    7    1    3    7    1    3    7    1
                 2:    1   41    3  1.4  8.3    7    8  8.3    7    8  8.3
                  >-------------------------------------------------------<
    ! There Is No Arbitrage Sequence
    0 EXIT Arbitrage Again (1-y-Y | N-n-0) ? --->   no
    Forum Solver Menu
  k Arbitrage
    INPUT DATA: 
    1 From File
    0 ---> exit 
    Your Data File in c:\exsan\     Data file  ---> v5_b
    Data will be read from File ---> c:\exsan\v5_b.txt
    Loading WorkSheet A
    ARBITRAGE - Currency Trader Matrix
    WORKSHEET A[5, 5]
          <----------------------------------->
                 A      B      C      D      E 
         1:      1    4.1    4.2   0.96   0.22
         2:   0.24      1      1   0.23  0.054
         3:   0.23   0.97      1   0.22  0.051
         4:      1    4.2    4.4      1   0.23
         5:    4.5     18     19    4.3      1
          >-----------------------------------<
    - BEST ARBITRAGE SEQUENCE MATRIX Index ---> 2
    ROW1: Currency Sequence  ROW2:  Price Of Change
    WORKSHEET B[2, 6]
          <------------------------------------------>
                 A      B      C      D      E      F 
         1:      2      3      2      0      0      0
         2:      1      1   0.97      0      0      0
          >------------------------------------------<
    BEST Profit = -1.99891%
 -  !INVESTMENT WARNING!, better keep your money in a safe place
 
    [1..5]  Arbitrage Currency Index Id -> 1
    ARBITRAGE - Currency Sequence Matrix Selected Index --->1
    ROW1: Currency Sequence  ROW2:  Price Of Change
    WORKSHEET B[2, 6]
                  <------------------------------>
                     A    B    C    D    E    F 
                 1:    1    3    2    3    2    3
                 2:    1  4.2 0.97    1 0.97    1
                  >------------------------------<
    ! There Is No Arbitrage Sequence
    0 EXIT Arbitrage Again (1-y-Y | N-n-0) ? --->   yes
    [1..5]  Arbitrage Currency Index Id -> 5
    ARBITRAGE - Currency Sequence Matrix Selected Index --->5
    ROW1: Currency Sequence  ROW2:  Price Of Change
    WORKSHEET B[2, 6]
                  <------------------------------>
                     A    B    C    D    E    F 
                 1:    5    3    2    3    2    3
                 2:    1   19 0.97    1 0.97    1
                  >------------------------------<
    ! There Is No Arbitrage Sequence
    0 EXIT Arbitrage Again (1-y-Y | N-n-0) ? --->   no
    Forum Solver Menu
  0 Exit Solver
  0 Exit Solver
    E X S A N     M E N U
  0 Exit From   E X S A N 
 
    MAIN MENU
    Main M E N U
  0 Exit From   Pixsan/Exsan M E N U
    EXSAN v3.18.kk - [EMAIL="exsan.software@gmail.com"]exsan.software@gmail.com[/EMAIL]   
    Once in a while recycle  unwanted files from c:\exsan\ 
 
    EXIT FROM EXSAN                            Tue Nov 18 13:56:34 2008

Arbitrage any takers? C++/Java solutions Only

Wallstyouth

Vice President

Andy Nguyen

alain

Older and Wiser

alain

Older and Wiser

alain

Older and Wiser

Muting

alain

Older and Wiser

Soar

ExSan

Soar

ExSan

ExSan

ExSan

Attachments

Soar

ExSan

Attachments

ExSan

Attachments

ExSan

Attachments

Victor

Attachments

Victor

ExSan