###### tags: `zip` `zip-1` `proposal` `arbitrage`

# ZIP-1: Automated Arbitrage

:::info
Author: Dr. Malte Kliemann
Version: 1.3 (Oct-15-2022)
:::

## Changelog

### 1.3

- Fixed maximum iterations estimate.

## Introduction

Zeitgeist currently uses the [Balancer AMM design](https://balancer.fi/whitepaper.pdf), a variant of the classical constant product market maker (CPMM), to facilitate trading of outcome tokens. The liquidity pool for a market contains outcome tokens as well as the base asset (currently ZTG), and the Balancer AMM calculates prices of tokens as functions of these balances and the _weights_ of these assets.

As early as the [Kusama Derby](https://github.com/zeitgeistpm/zeitgeist/issues/143), a design problem in our AMM has become apparent: The sum of the spot prices of the outcome tokens (the _total spot price_) is not always equal to $1$ ZTG. Instead, it will usually be higher than $1$ as a result of users buying the outcome tokens from the pool. This yields an arbitrage opportunity for traders. They can mint complete sets of outcome tokens for the price of $1$ ZTG per set and then sell these sets to the market at a price _higher_ than $1$ ZTG per set until the balances of the pool have evened out and the total spot price has returned to $1$.

This has led to multiple users developing competing bots to take advantage of this opportunity. This is very unfortunate, as the tokens the arbitrageurs siphon from the liquidity pool belonged to the liquidity providers before. This creates the impression that the bots "steal" from the liquidity pool, disincentivizing users from joining a pool.

Arbitrage is usually just a fact a life when multiple markets exist for the same asset. In this case, it is completely avoidable. The long-term fix is to change the AMM, which will remove the arbitrage opportunity completely and double the efficiency of liquidity by removing the base asset from the pool.

But in order to quickly address the problem, we propose a short-term fix that can be deployed in the next update by automating the arbitrage in the chain code and passing the profit to the liquidity providers.

## Background

### Balancer pools

A _Balancer pool_ consists of assets $A_0, \ldots, A_n$, normalized weights $w_0, \ldots, w_n$ with $\sum_i w_i = 1$ and the asset balances $b_0, \ldots, b_n$. The pool also has a _swap fee_ $F \in [0, 1)$. The asset $A_0$ is referred to as _base asset_. We will assume $F = 0$ (no swap fees) for now and later address the changes necessary if swap fees are used.

Balancer pools are constant product market makers in the sense that balances in the pool can only be changed in ways that keep the _value function_ unchanged:
$$
V = \prod_i b_i^{w_i}.
$$
If the pool uses swap fees, the value function actually _increases_ with every trade.

The _spot price_ $s_i$ of $A_i$ is defined as the spot price for swapping $A_0$ in and $A_i$ out:
$$
s_i = \frac{w_i}{w_0} \cdot \frac{b_0}{b_i}.
$$

The _total spot price_ is defined as
$$
T = \sum_{i = 1}^n s_i = \sum_{i=1}^n \frac{w_i}{w_0} \cdot \frac{b_0}{b_i}.
$$

The exact cost calculations when performing trades are more complex.

### The arbitrage process

The arbitrage process may be interpreted as arbitrage between two pools offering the same asset at different prices: You buy from the pool offering the better price and sell to the other pool for profit. In this case, the two pools are the _prize pool_ (which _always_ offers $1$ complete set for $1$ ZTG) and the _liquidity pool_ (which may offer high or lower prices). The direction of the arbitrage depends on whether $T > 1$ or $T < 1$.

If $T > 1$ (the more commonly observed case), then the arbitrageur buys $a$ full sets from the prize pool (increasing the size of the prize pool by $a$) and sells $a$ full sets to the liquidity pool. Ignoring slippage, the arbitrageurs profit is $a \cdot (T - 1)$, where $T$ denotes the total spot price _before_ the trade. We call this _mint-sell arbitrage_.

As long as the total spot price after the trade is $\geq 1$, the trade was profitable (although the bot has to take into account transaction fees). In particular, the trade is ideal if the total spot price _after_ the trade is equal to $1$. Determining the ideal value of $a$ is actually the most difficult part of the whole process.

If $T < 1$ (this case occurs if morewhen users sell their outcome tokens back to the liquidity providers), we just switch the process around: Buy full sets from the liquidity pool and sell to the prize pool. This is called _buy-burn arbitrage_.

#### Example

Let's take a simple liquidity pool with two outcome assets $A$ and $B$. The pool is provided with
100 units of each asset:

Value: 100.0
Total spot price: 1.0 ZTG

Asset      Weight    Balance    Spot Price
-------  --------  ---------  ------------
A               1        100           0.5
B               1        100           0.5
ZTG             2        100           1

Now Alice swaps in 10 ZTG for $A$ tokens, leaving the pool in the following state:

Value: 100.0
Total spot price: 1.2155 ZTG

Asset      Weight    Balance    Spot Price
-------  --------  ---------  ------------
A               1    82.6446        0.6655
B               1   100             0.55
ZTG             2   110             1

Now an arbitrageur steps in, buys 9.2398225 complete sets of outcome tokens from the prize pool and sells them to the liquidity pool for 10.1867 ZTG, making a profit of roughly 1 ZTG and leaving the pool in the following state:

Value: 100.00000000000001
Total spot price: 0.9999999510745528

Asset      Weight    Balance    Spot Price
-------  --------  ---------  ------------
A               1    91.8845      0.543146
B               1   109.24        0.456854
ZTG             2    99.8133      1

## Automated Arbitrage

### In simple terms

In the scenario $T > 1$, the arbitrage trade moves ZTG from the liquidity pool into the prize pool and mints complete sets of outcome tokens which are placed in the liquidity pool. But the liquidity providers also lose a premium to the arbitrageurs for executing the trade.

The _automated arbitrage_ will have the same effect, but the liquidity providers will be the arbitrageur, meaning that they will pay the premium to themselves, saving them a significant part of their capital. The automated arbitrage algorithm for $T > 1$ is:

- Calculate the arbitrage amount so that performing arbitrage results in $T = 1$
- Remove $a$ ZTG from the liquidity pool
- Add $a$ ZTG to the prize pool
- Add $a$ of each outcome token to the liquidity pool

This algorithm will regularly clean up all the arbitrage opportunities on the chain, ideally every block. Unfortunately, it will still be possible for bots to scrape the transaction pool and slip in arbitrage trades mid-block, but this is currently a minor concern.

There are two difficulties:

- Calculating the arbitrage amount $a$
- Managing on-chain resources

Before we approach these problems, let's take a look at how much sense this solution makes for each of the parties involved.

### Economic Justification

The current players in our system are (roughly) _traders_, _liquidity providers_ and _arbitrageurs_. The traders are "normal" users: They buy outcome tokens to hold them until market resolution. The liquidity providers provider liquidity to markets either trying to make money off these markets or in order to liquidate the information discovery process. The arbitrageurs execute arbitrage trades as described in the introduction, either manually or in an automated may.

We already mentioned that the arbitrageurs take a premium from the liquidity pool for their "services". The question is: Who pays this premium? Considering the premium comes from the liquidity pool, the naive answer is "the liquidity providers". But this is not necessarily correct. For example, if we change the AMM to include the arbitrage trade in every swap that a trader executes, then the traders receive the premium when they interact with the pool, resulting in a discount. Liquidity providers would make less than they do now. If this is considered the "canonical fix", then the current situation might be described as follows: The liquidity providers are charging too much from the traders due to the inefficient AMM, and the arbitrageurs "steal" this premium from the liquidity pool.

That's the point: Who's getting "robbed" depends on how we end up solving the problem. But whether or not the liquidity providers are the ones getting stiffed, public opinion certainly veers in that direction. So there's good reason to fix this problem, even if the long-term solution benefits the liquidity providers only emotionally.

The short-term solution, however, will prevent the arbitrageurs from robbing the liquidity providers, but won't fix the high prices for traders (so the liquidity providers keep the premium). This should be good for those who take the risk of joining a liquidity pool. In fact, the automated arbitrage never decreases the value function of the pool, and most often actually increases the value (proofs below). This ensures that liquidity providers always profit from the automated arbitrage.

You might wonder what it means that it actually _increases_ the value of the pool in some circumstances. Well, that's because the liquidity providers essentially become the arbitrageurs and perform the arbitrage for their own benefit, resulting in the pool slowly gaining in value. Swapping ZTG for full sets of outcome tokens or vice versa is no black magic. The liquidity providers could do this anyways, if they had control over the pool account. One way to look at this value increase is to think of the value flowing into the pool as swap fees paid by the traders. (This sort of proves the point made earlier: By "fixing" the problem we've made it more apparent that traders are overpaying.)

#### Proofs

Suppose we have a pool with the parameters defined above, and suppose that $T > 1$. Without automated arbitrage, an arbitrageur would step in and execute the arbitrage. Let's call this _user arbitrage_. Denote by $\tilde s_i$ the spot price of $A_i$ after user arbitrage, and by $\tilde b_i$ the balances in the pool after user arbitrage. With automated arbitrage, the algorithm above would change the balances of the liquidity and prize pool. Denote by $\bar s_i$ the spot price of $A_i$ after automated arbitrage and by $\bar b_i$ the balances in the pool after automated arbitrage.

Furthermore, denote by $\tilde a$ the amount of complete sets the arbitrageur would sell to the liquidity pool and let $z$ be the amount of ZTG the arbitrageur would swap out of the liquidity pool. Denote by $\bar a$ the arbitrage amount of the automated arbitrage. Denote the total spot price _after arbitrage_ by $f(a)$. According to the equations above, we have
$$
f(a) = \sum_{i \neq 0} \frac{w_i}{w_0} \cdot \frac{b_0 - a}{b_i + a}.
$$

:::info
**Lemma.** ($\alpha$) $f$ is strictly decreasing.
($\beta$) $z > \bar a$, i.e. the arbitrageurs remove more ZTG from the pool than the automated arbitrage.
($\gamma$) $\bar a > \tilde a$, i.e. the arbitrageurs add fewer complete sets to the pool than the automated arbitrage.
:::

_Proof._ ($\alpha$) Clearly $f \colon (0, b_0) \rightarrow \mathrm{R}$ is a differentiable function with derivative
$$
f'(a)
=
- \sum_i \frac{w_i}{w_0} \frac{(b_i - a) + (b_0 + a)}{(b_i + a)^2}
=
- \sum_i \frac{w_i}{w_0} \frac{b_i + b_0}{(b_i + a)^2}
<
0
.
$$

($\beta$) Using $z > \tilde a$, we get
$$
\tilde s_i
= \frac{w_i}{w_0} \frac{\tilde b_0}{\tilde b_i}
= \frac{w_i}{w_0} \frac{b_0 - z}{b_i + \tilde a}
> \frac{w_i}{w_0} \frac{b_0 - z}{b_i + z}.
$$
When we sum all up $\tilde s_i$, we get the total spot price after user arbitrage, which is $1$. This implies
$$
1 = \sum_i \tilde s_i > \sum_i \frac{w_i}{w_0} \frac{b_0 - z}{b_i + z} = f(z).
$$
But we also have $f(\bar a) = 1$. Thus, $f(\bar a) > f(z)$. According to ($\alpha$), $f$ is strictly decreasing, so we have $\bar a < z$.

($\gamma$) Using $z > \tilde a$, we get
$$
\tilde s_i
= \frac{w_i}{w_0} \frac{\tilde b_0}{\tilde b_i}
= \frac{w_i}{w_0} \frac{b_0 - z}{b_i + \tilde a}
< \frac{w_i}{w_0} \frac{b_0 - \tilde a}{b_i + \tilde a}.
$$
When we sum up all $\tilde s_i$, we get the total spot price after user arbitrage, which is $1$. This implies
$$
1 = \sum_i \tilde s_i < \sum_i \frac{w_i}{w_0} \frac{b_0 - \tilde a}{b_i + \tilde a} = f(\tilde a).
$$
But we also have $f(\bar a) = 1$. Thus, $f(\bar a) < f(\tilde a)$. According to ($\alpha$), $f$ is strictly decreasing, so we have $\bar a > \tilde a$. QED

:::info
**Theorem.** Automated arbitrage never decreases the pool's value function.
:::

_Proof._ Let $V$ denote the value function before arbitrage, $\tilde V$ the value function after user arbitrage and $\bar V$ the value function after automated arbitrage. Recall that trading never decreases the value function, so $V \leq \tilde V$. Using ($\beta$) and ($\gamma$) of the lemma above, we get
$$
V
\leq \tilde V
= \prod_{i=0}^n \tilde b_i^{w_i}
= (b_0 - z)^{w_0} \cdot \prod_{i=1} (b_i + \tilde a)^{w_i}
\leq (b_0 - \bar a) \prod_{i=1}^n (b_i + \bar a)
= \bar V.
$$
In total, we get $V \leq \bar V$, i.e. executing the automated arbitrage _never_ decreases the value of the pool. The same type of argument can be made for arbitrage if $T < 1$. QED

**Note.** We ignore swap fees in parts of the proof above. In fact, swap fees play a role in user arbitrage. For example, user arbitrage is not profitable if the end result is a total spot price of $1$ (see below). In particular, $1 = \sum_i \tilde s_i$ wil no longer hold. The proof can be adapted to work with swap fees by replacing $\tilde s_i$ with the spot price _without_ swap fees. You can then see that ideal user arbitrage will bring the sum of these spot prices _without_ swap fees to $1$. Then we're back to $1 = \sum_i \tilde s_i$.

### Calculating the arbitrage amount

In this section, we discuss techniques for approximating the correct arbitrage amount. We concentrate on the case $T > 1$. The function $f$ defined above will be very useful here.

The spot prices $s_i$ and the total spot price $T$ are, of course, functions of the pool state. Let's say a couple of trades happened and now the _current_ total spot price is $T > 1$. As before, we denote the total spot price _after arbitrage_ by $f(a)$. Recall that
$$
f(a) = \sum_{i \neq 0} \frac{w_i}{w_0} \cdot \frac{b_0 - a}{b_i + a}.
$$
The correct arbitrage amount $a_0$ is defined by the equation $f(a_0) = 1$. Note that $f$ is well-defined on $I = [0, \infty)$.

:::info
**Lemma.** There exists exactly one $a_0 \in (0, b_0)$ with $f(a_0) = 1$.
:::

_Proof._ We also have $f(0) = T > 1$ and $\lim_{a \rightarrow b_0} f(a) = 0$. By the intermediate value theorem, there exists $a_0$ with $f(a_0) = 1$. QED

There seems to be no useful formula for $a_0$ (more on that later), but the value can be approximated using a _root-finding algorithm_. The basic idea of these algorithms is to approximate a root $r$ of a function with a sequence of numbers $(x_n)_{n \in \mathbb{N}}$. (Recall that a root of a function $f$ is an element of the domain of $f$ with $f(r) = 0$.) By modifying $f$ by a constant factor, we can use root-finding algorithms to solve any equation of the form $f(r) = y$.

Straightforward root-finding algorithms are the [bisection method](https://en.wikipedia.org/wiki/Bisection_method) and [Newton's method](https://en.wikipedia.org/wiki/Newton%27s_method).
There are other, more intricate algorithms: https://en.wikipedia.org/wiki/List_of_algorithms#Root_finding. In particular, [TOMS748](https://www.boost.org/doc/libs/1_65_1/libs/math/doc/html/math_toolkit/roots/roots_noderiv/TOMS748.html) comes to mind. All of these offer different worst-case, average and best-case convergence properties. We don't expect to have to handle many arbitrage calculations per block, so we should go for numerical stability, good convergence criteria and ease of implementation rather than convergence speed. The bisection method ticks those boxes.

### The bisection method

Consider a continuous function $f\colon I \rightarrow \mathbb{R}$ which is strictly increasing or decreasing (we'll assume it's decreasing). Let $r \in I$ be a root of $f$ and suppose that $r \in [x, y] \subseteq I$.

We define a sequence $(m_i)$ of numbers so that $\lim_{i \rightarrow \infty} m_i = r$. Let $m = (x + y) / 2$ (the _midpoint_ between $x$ and $y$); this is the first member of the sequence. If $f(m) < 0$, then we repeat the process with $m$ in place of $x$, and if $f(m) > 0$ we repeat the process with $m$ in place of $y$, to get the second member of the sequence, and so on.

The bisection method is not ideal in terms of computation time, but it does give us a very useful worst-case estimate. If we want to approximate $r$ up to a precision of $\varepsilon > 0$, then we need at most
$$
\left\lceil \log_2\frac{y - x}{\varepsilon} \right\rceil
$$
iterations. This will be very useful when benchmarking the method for on-chain usage.

Another upside of using this method is that it's fairly easy to implement, numerically very stable
(provided that calculating $f$ doesn't cause any problems) and always converges, provided that the interval $[x, y]$ actually contains a root. So there is one difficulty: Selecting the initial range $[x, y]$.

In the $T > 1$ case, taking $[0, b_0]$ carries the risk of having to calculate $f$ close to $b_0$, which is numerically unsafe due to division by small numbers. So we opt for something safer like $[0, b_0/2]$. Similarly, for the $T < 1$ case, we use $[0, \min_{i=1}^n b_i / 2]$.

This results in the the minor problem that the root might lie _outside_ of the range, which (in our application) means that we would only arbitrage some, but not all of the required volume. For example, consider this liquidity pool:

Value: 31.622776601683796
Total spot price: 0.00505 ZTG

Asset      Weight    Balance    Spot Price
-------  --------  ---------  ------------
A               1      10000         5e-05
B               1        100         0.005
ZTG             2          1         1

This needs to be arbitraged in two steps when using the ranges described above. The intermediate result is

Value: 189.663324731346
Total spot price: 0.5125628140703518 ZTG

Asset      Weight    Balance    Spot Price
-------  --------  ---------  ------------
A               1       9950    0.00256281
B               1         50    0.51
ZTG             2         51    1

There is also the slight risk of overshooting the target a little bit. However, this will only happen to very small, negligible degrees.

**Note.** It is virtually impossible to find balances as shown above in "nature". It's unlikely that any real-life trading will require more than one pass of arbitrage per block.

### Arbitrage in the presence of swap fees

#### A short explanation of swap fees

What often surprises people about the Balancer swap fees is that they are taken not by charging extra, but by swapping out smaller amounts. For example, when Alice swaps in 10 ZTG for an outcome asset $A$ in a pool with $10\%$ fees, instead of receiving the amount of $A$ that she would on a pool without swap fees, 1 ZTG in fees would be subtracted from the 10 ZTG and Alice would receive the amount of $A$ tokens she would receive when trading 9 ZTG into a pool with no swap fees. In particular, this means that the spot price "contains" the fees.

This leads to a fairly confusing situation. Suppose we have a pool with no swap fees, and that the spot price of $A$ is 0.5 ZTG. As you would expect, the swap price for swapping $A$ to ZTG is $2$ $A$. But in the presence of swap fees, this all changes.

Suppose we raise the swap fees in this pool to $10\%$. This means that the spot price of $A$ is now $0.555\ldots$ ZTG. But the spot price for swapping $A$ to ZTG is not $1 / 0.555\ldots A = 1.8A$ (so you do not get $0.555\ldots$ ZTG when swapping in $1A$), but rather $2.222\ldots A$ (so you get $\approx 0.45$ ZTG for each $A$).

In fact, the spot price for swapping $A_i$ in and $A_o$ out is
$$
s_{io} = \frac{1}{1 - F} \cdot \frac{w_o}{w_i} \cdot \frac{b_i}{b_o}.
$$
Recall that $F \in [0, 1)$ denotes the swap fee; if $F = 1/10$, this means a $10\%$ swap fee. Under normal circumstances, you would expect $s_{oi} = s_{io}^{-1}$ to hold true. If $F \neq 0$, this is not the case. Instead,
\begin{align*}
s_{io}
&=
\frac{1}{1 - F} \cdot \frac{w_o}{w_i} \cdot \frac{b_i}{b_o}
\\
&=
\frac{1}{(1 - F)^2} \cdot (1 - F) \cdot \frac{w_o}{w_i} \cdot \frac{b_i}{b_o}
\\
&=
\frac{1}{(1 - F)^2} \cdot \left( \frac{1}{1 - F} \cdot \frac{w_i}{w_o} \cdot \frac{b_o}{b_i} \right)^{-1}
\\
&=
\frac{1}{(1 - F)^2} \cdot s_{oi}^{-1}
.
\end{align*}

This leads to the formation of something akin to the bid-ask spread on order book AMMs. You can _buy_ at the price of $0.555\ldots$ ZTG, but you can only sell for $0.45$ ZTG.

#### The bid-ask spread and arbitrage

User arbitrageurs need to be very careful how they configure their bots to trade on markets with swap fees. Define the _total ask_ of a pool as $T_a = \sum_i s_{0i}$ (the sum of all ask prices) and the _total bid_ as $T_b = \sum_i s_{i0}^{-1}$ (the sum of all bid prices). Define the _total bid-ask spread_ as $[T_b, T_a]$.

In the absence of swap fees, the arbitrageur can profit if the total spot price $T$ is not equal to $1$ (ignoring transaction fees). But with swap fees, it gets a bit more complicated.

:::info
**Proposition.** Mint-sell arbitrage is only profitable if $T_b > 1$ and buy-burn arbitrage is only profitable if $T_a < 1$.
:::

_Proof._ In mint-sell arbitrage, you buy $x$ complete sets for $x$ ZTG from the prize pool and sell it to the liquidity pool. The amount received per unit of complete set is equal to $T_b$, so you get $xT_b$ for $x$ complete ests. Thus, mint-sell is not profitable if $T_b \leq 1$.

The proof for buy-burn is symmetric. QED

This gives us a canonical "target" for arbitraging pools with swap fees. The more the bid-ask spread is centered around $1$, the farther the pool is away from offering profitable arbitrage. This can be formalized as follows.

Denote by
$$
\hat s_{io} = \frac{w_o}{w_i} \cdot \frac{b_i}{b_o}
$$
the swap price _without_ swap fees. Note that $\hat s_{io} = (1 - F) s_{io}$. Define
$$
T = \sum_i \hat s_{0i}.
$$
(This is basically the $T$ that we've been using throughout this bulletin.) Then we have the following equations.
\begin{align*}
T_a &= \sum_i s_{0i} = \frac{1}{1 - F} \sum_i \hat s_{0i} = \frac{1}{1 - F} \cdot T, \\
T_b &= \sum_i s_{i0}^{-1} = \sum_i (1 - F)^2 s_{0i} = (1 - F) \sum_i \hat s_{0i} = (1 - F) \cdot T.
\end{align*}
In other words, the bid-ask spread is $\left[(1 - F) \cdot T, \frac{1}{1 -F}\cdot T\right]$, centered around $T$, the classical total spot price.

Thus, it could be argued that the best bid-ask spread is obtained when $T = 1$. This is consistent with our economic justification: Executing arbitrage always _increases_ the value of the pool.

In summary: Regardless of swap fees, the goal of automated arbitrage is to exchange pool balances back and forth in order to bring $T$ very close to $1$.

## Remarks

### Closed-formula approach

You might get the idea that there _must_ be a formula for the inverse function $f^{-1}$, or at least for $f^{-1}(1)$. There is, but it depends on the number of assets, with rising complexity as $n$ increases. Here's one of the solutions for $n = 2$ (using $x, y$ as indices for outcome assets and $z$ as index for the base asset):
\begin{align*}
a &= \frac{1}{2 \cdot (w_x + w_y + w_z)} \cdot \Big( (w_y + w_z) \cdot x + (w_x + w_z) \cdot y - (w_x + w_y) \cdot z \\
&\qquad - \sqrt{(w_y^2 + 2 \cdot w_y \cdot w_z + w_z^2} \cdot x^2 + 2 \cdot (w_x \cdot w_y - (w_x + w_y) \cdot w_z - w_z^2) \cdot x \cdot y \\
&\qquad + (w_x^2 + 2 \cdot w_x \cdot w_z + w_z^2) \cdot y^2 + (w_x^2 + 2 \cdot w_x \cdot w_y + w_y^2) \cdot z^2 \\
&\qquad + 2 \cdot ((w_x \cdot w_y + w_y^2 - (w_x - w_y) \cdot w_z) \cdot x + (w_x^2 + w_x \cdot w_y + (w_x - w_y) \cdot w_z) \cdot y) \cdot z)\Big)
\end{align*}

It only gets worse from here. With a current `MaxAssets` of `64`, there is absolutely no way this approach will work.

### Future Proposals

We already alluded to the development of an entirely new AMM. This AMM will be built upon the Balancer pools, but will incorporate arbitrage into each trade.

## Implementation

The on-chain arbitrage will be executed in a chain hook of `zrml_swaps`. Using `on_idle` or `on_finalize` is preferable, as this will result in lower latency than using `on_initialize`. The limited amount of resources available on the block chain poses a challenge: We need to carefully benchmark the weight that arbitrage requires and may not always be able to arbitrage all open pools. Caching the pools which require arbitrage will significantly reduce the workload.

### Cacheing pools

Instead of just iterating over all pools and checking if their total spot price is sufficiently close to $1$, we add a set to storage which tracks which pools might require arbitrage. Whenever a trade is executed on a pool, the pool id is pushed onto the set. When the arbitrage is executed, the pool id is removed from the set.

### How many iterations?

The big question when using approximations is: How many iterations can we afford and how precise will the result be? The bisection method offers us a very useful worst-case estimate for obtaining a certain precision. For example, if the balances in the pool do not exceed 1M (for ZTG, that's a little less than 1% of the total issuance) and we require a precision of $\varepsilon = 0.001$, then the maximum number of iterations required is
$$
\left\lceil \log_2 \frac{1,\!000,\!000}{0.001} \right\rceil = 30.
$$

### Experiments

We ran an experiment with a Python prototype implementation, testing 64,000 liquidity pools with varying balances, with and without swap fees. The maximum ratio between balances was 10,000. The bisection method always converged within the number of expected iterations, the value function of the pool never decreased and it was never necessary to repeat arbitrage more than once to achieve a total spot price of $1$ up to a precision of 0.001.