#
~~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*.

*Proof.* 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.

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 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

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