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