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