Analytical Arbitrage Optimization

Analytical solutions for optimizing arbitrages greatly outperform iterative approaches. How are they derived? What are the benefits, and are there any potential trade-offs? Find out more in this analysis.

Table of Contents

• Arbitrage Challenges
• What Closed Form Formulas Provide
• Uniswap V2
• Evaluation
• Conclusion

Arbitrage Challenges

One of the main challenges of arbitraging is to find the optimal trade size. Trade too little and fees will eat up any profit. Trade too much and slippage and price changes will make the arbitrage unprofitable. This is where blockchain AMMs, especially the Uniswap V2 constant product formula provide a great opportunity for optimal arbitrages. It has the very simple formula $x \cdot y = k$, where $x$ and $y$ are the amounts of tokens in a given pool. The amounts traded solely depend on the current blockchain state which is publicly available, and follow clear rules.

However, even with the price being very predictable, finding optimal trade size is not a trivial problem at all. Take for example Curve’s stable swap formula. There is no closed formula for the trade size, it requires an iterative algorithm to solve it numerically, using Newton’s method. Even on-chain it is solved like that.

What Closed Form Formulas Provide

In general, the approach is to use numerical optimization. The issue is that any such solution requires multiple function evaluations, i.e. quoting the price $\bigo{k}$ times, and it is only an approximation of the optimum. This is a clear disadvantage, since there are many millions of possible arbitrage routes, and on faster chains only half a second passes between blockchain state updates. In such a competitive and complex environment, closed form, analytical solutions are a clear advantage. They can be calculated in $\bigo{1}$ without quoting the price, and give the true optimum.

Uniswap V2

While in general, such solutions are not feasible, we can derive one for Uniswap V2’s constant product formula $x\cdot y = k$. When trading $\delta x$ of token $x$ for $\delta y$ of $y$, the pool must satisfy $(x+\delta x)(y-\delta y)= x\cdot y$, i.e the product of the liquidities must stay constant. This allows us to calculate the amount out, given our amount in for any pool:

If we define $o_i(\delta x)$ as the output of trade $i$ with the size $\delta x$, we can chain these functions together. Given that the output currency of trade $i$ is the same as the input currency of trade $i+1$. Further, with $n$ trades, requiring the first trade’s input currency is the same as the last trade’s output currency, we have an arbitrage. The arbitrage profit can then be defined as

where $\circ$ denotes function composition.

The maximum of this expression can be found for arbitrary $n$, by (tedious) calculation of the derivative, and setting the derivative to zero. This is omitted here for simplicity. Using the derived solution, we only need to know the liquidities of each of the pools included in the trade, and it outputs the trade size $x^*$ that maximizes the profit function.

Evaluation

The improved speed and precision are a game changer. There is one tradeoff: the analytical solution is over the reals, whereas the on-chain implementation uses integers. With small liquidities, or if the trade sizes are close to zero, the formula does not accommodate for the rounding effects, thus the numerically optimized solutions can be better. In general however, the approximation yields measurably lower profits. One issue the numerical optimizer faces is the non-smoothness of the quoted amounts, due to integer rounding.

The graphs show the convergence to the analytical optimum of two different methods. A pure numerical optimization, and a guided optimization (called combined in the plot). Guided is the same as pure optimization but with limits set at $\pm 50\%$ of the analytical solution. The numerical optimizer used is SciPys minimize_scalar, which implements Brent’s method.

Figure 1 shows the (absolute) convergence of the optimized trade input size. The $y$-axis is logarithmic, and all values used are in Wei. If the token used has 18 decimals, a difference of $10^{18}$ equals one token difference. The guided optimization needs 20 iterations to find its optimum, while the regular optimization requires 40. Both improve the solution by a factor of $\sim 1.5$ per iteration.

Figure 2 shows the convergence to the optimal profit. Depending on the decimals and price of a token, this shows a less pessimistic outlook for iterative solutions. If we have a good starting range, we don’t need that many iterations for a relatively good solution. For example, if the token used was DAI, a difference in the order of $10^{15}$, as reached in under ten iterations by the combined method, would merely be a fraction of cents that the arbitrage would miss out on.

Conclusion

Optimization in our example can take from 10 up to 40 iterations to settle close to the actual optimum. Compared to a zero iteration, true optimum, the analytical solution can be a game changer in a fast-paced environment like the blockchain. While both approaches suffer from integer math issues, analytical solutions experience them in low-liquidity, small trade size settings, whereas the numerical optimization suffers in other settings. So in practice, if analytical solutions are even available, the best results will probably be had with a combined approach.