I wrote a program which finds negative weight cycles in a graph to find triangular arbitrage opportunities, using the bellman ford algorithm.

The basic principle is this, given three currencies ($x$, $y$, $z$), and the exchange rates between the three ( $x_r$, $y_r$, $z_r$), if $ x_r * y_r * z_r > 1 $ then an arbitrage opportunity exists.

This can then be phrased in terms of a graph by first inverting

$$ 1 / (x_r * y_r * z_r) < 1 $$

and then taking the natural log, which gives

$$ log(1 / x_r ) + log(1 / y_r) + log( 1/ z_r) < 0 $$

I can then weight the edges of the graph with these values and expect it to give me the correct result.

The trouble I'm having is factoring trade fees (which is a constant percentage e.g. 0.02%) into this. What I've figured is if

$$ (x_r - x_r*fee)* (y_r - y_r*fee) * (z_r - z_r*fee) > 1 $$

then there is an opportunity. So it follows that

$$ log(1 / (x_r *(1 - fee)) ) + log(1 /( y_r*(1 - fee))) + log( 1/ (z_r*(1 - fee)) ) < 0 $$ However using these values as my edge weights gives the wrong results.

How can I properly take fees into account?

  • 1
    $\begingroup$ I asked a somewhat similar question, but never received any replies. Not sure if what I have so far helps or not, I can try posting a more thorough answer tomorrow. Essentially you need to treat the edge weights as functions and a path as a composition of those functions. See: math.stackexchange.com/questions/370310/… $\endgroup$ Jun 1, 2013 at 1:03

1 Answer 1


Interestingly, you can ignore the fees. All the fees do is increase the minimum starting amount necessary to have an arbitrage for a given negative-weight cycle.

Determine if any negative-weight cycles exist without fees. If a negative-weight cycle exists without fees, you can determine the minimum starting amount needed to have a negative weight cycle with the fees included by solving:

$f_{x_r}\circ f_{y_r}\circ f_{z_r}(n_0) = 0$ where $f_{x_r}$,$f_{y_r}$,and $f_{z_r}$ represent the edge-weight functions: $f_a(n)=a*(n-fee)$

Also, keep in mind that arbitrage opportunities may exist in cycles of lengths 2 to $\infty$, not just 3.

  • $\begingroup$ This does not seem true to me. Say I have euro, usd and gbp and the exchange rates between them are 1, 1 and 1.1, if there is a cumulative fee greater then 10% then no matter my starting value I would come out with less money, yet this would be returned as a negative weight cycle. $\endgroup$
    – Loourr
    Jun 5, 2013 at 17:01
  • $\begingroup$ Sorry, I misunderstood the fee - I assumed it was a fixed amount. If the fee is a percentage, not fixed, then you subtract that percentage from each rate. So, if the cumulative fee is 12%, your rates are 0.96, 0.96, 1.06, and there is no negative weight cycle. $\endgroup$ Jun 6, 2013 at 11:02
  • $\begingroup$ That's what I figured, but thats what I think I'm doing, and it is still giving me false positives $\endgroup$
    – Loourr
    Jun 6, 2013 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.