# ~~Smart~~ Order Routing

**Definition.** (Fill function) A *fill function* $f$ specifies how much of a desired asset we can maximally get for a given amount of the provided asset.

**Lemma.** (Monotonicity) *Fill functions are monotonic*. If a fill function provided more of the desired asset for fewer of the provided, we can simply provide it fewer.

**Problem.** Given a maker asset amount $x$ and a set of fill functions $f_i$, we want to partition $x$ into $x_i$ to maximize.

$$
g(x) = \max_{\vec x} \, \sum_i f_i(x_i) \text{ subject to } \sum_i x_i \le x \text{ and } x_i \ge 0
$$

Dynamic programming: The resulting function $g$ is also a fill function. Given two fill functions, we can compute their combined function. So we only need to solve the case for two functions, and can then use this recursively.

### Solving

If the fillable function is concave, the optimization problem is a [Convex Programming](https://en.wikipedia.org/wiki/Convex_optimization) problem. In particular this means any local minimum is a global minimum and we can use any way to minimize (for example grandient descent).

Usually fillable functions are concave, with the notable exception of Kyber.

**Question.** If two fillable functions are concave, is their combination also concave?

If the fillable functions are note concave, the problem is

## 1-hop routing

Now we have more than two assets and multiple fill functions between two assets.

First, for each pair of tokens $(i,j)$ we compute the optimal fill function $f_{ij}$ using the above two-asset solution.

Define $f_{ii}$ to be the identity function.

Now the optimal $\{0,1\}$-hop routes are

$$
f'_{ij}(x) = \max_{\vec x} \, \sum_k f_{kj}(f_{ik}(x_k)) \,\,\text{ subject to }\,\, \sum_k x_k \le x
$$

Similarly, we can define 3-hop routes $f''_{ij}$ by itterating this procedure on $f'$, and 7-hop, 15-hop and so on, doubling the number of hops each time.

## ∞-hop routing

The optimal unlimited hop solutions $f^∞_{ij}$ should be invariant under adding one more hop, so it should satisfy

$$
f^∞_{ij}(x) = \max_{\vec x} \, \sum_k f^∞_{ik}(f^∞_{kj}(x_k)) \,\,\text{ subject to }\,\, \sum_k x_k \le x
$$