# Dual Auction Tick Aggregation

## Notation

$p_{\text{min}}$
: the minimum auction price, i.e. the minimum amount of the bid asset per one unit of the ask asset

$p_{\text{max}}$
: the maximumn auction price

$\Delta p$
: the tick size, i.e. the price step

$p_i$
: the $i\text{-th}$ tick price: $p_i = p_{\text{min}} + i \cdot \Delta p$.

$a_i$
: the total ask amount at the price $p_i$, i.e. the total amount of the ask asset participants are willing to sell the minimum price $p_i$.

$b_i$
: the total bid amount at the price $p_i$, i.e. the total amount of the ask assetparticipants are willing to buy at the maximum price $p_i$.

## Aggregation

Let $k$ be the aggregation arity. We define the aggregated ask and bid amounts ${}^ja_i$ and ${}^jb_i$ recursively like this:

$$
{}^0a_i = a_i \\
{}^0b_i = b_i \\
{}^{j + 1}a_i = \sum_{l = ki}^{ki + k - 1} {}^ja_l \\
{}^{j + 1}b_i = \sum_{l = ki}^{ki + k - 1} {}^jb_l \\
$$

Such aggregation increases the complexity of the `bid` and `ask` functions from $O(1)$ to $O(log_k \frac{p_{\text{max}} - p_{\text{min}}}{\Delta p})$, but decreases the complexity of the `settle` function from $O(\frac{p_{\text{max}} - p_{\text{min}}}{\Delta p})$ to $O(k \cdot log_k \frac{p_{\text{max}} - p_{\text{min}}}{\Delta p})$. The arity $k$ should be chosen to adjust the balance between the `bid`/`ask` and `settle` complexities: