# Factoring a constant into a graph's edge weights for triangular arbitrage

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?

• 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/… Jun 1, 2013 at 1:03

$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.