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

Question

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?

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.