<jupyter_start><jupyter_text>Characteristics of Autonomous Market MakersDate: 2021-03-26 (Date started: December 2020 Christmas holidays)Author: [@mattmcd](https://twitter.com/mattmcd)This notebook describes an approach using [method of characteristics](https://en.wikipedia.org/wiki/Method_of_characteristics) solutions of partial differential equations (PDEs) to examine existing AMM invariants such as Uniswap, Balancer and Curve (a.k.a. Stableswap).<jupyter_code>from IPython.display import HTML
# Hide code cells https://gist.github.com/uolter/970adfedf44962b47d32347d262fe9be  
def hide_code():
    return HTML('''<script>
    code_show=true; 
    function code_toggle() {
        if (code_show){
        $("div.input").hide();
        } else {
        $("div.input").show();
        }
    code_show = !code_show
    } 
    $( document ).ready(code_toggle);
    </script>
    The raw code for this IPython notebook is by default hidden for easier reading.
    To toggle on/off the raw code, click <a href="javascript:code_toggle()">here</a>.''')
import sympy as sp
import matplotlib.pyplot as plt
import numpy as np
import seaborn as sns

%matplotlib inline
hide_code()<jupyter_output><empty_output><jupyter_text>From the [Balancer whitepaper](https://balancer.finance/whitepaper/):> The bedrock of Balancer’s exchange functions is a surface defined by constraining a value function $V$ — a function of the pool’s weights and balances — to a constant. We will prove that this surface implies a spot price at each point such that, no matter what exchanges are carried out, the share of value of each token in the pool remains constant. The [Balancer whitepaper](https://balancer.finance/whitepaper/) shows that the value function$$V = \sum_{i=1}^{n} x_{i}^{w_{i}}$$is related to the token spot prices by the ratio of partial derivative.    Starting from the ConstraintsThe idea of constant level sets of a value function creating constraints on system state (including prices) is discussed in ['From Curved Bonding to Configuration Spaces'](https://epub.wu.ac.at/7385/) by Zargham, Shorish, and Paruch (2020).  The existing Balancer value function implicit state constraint is 'the share of value of each token in the pool remains constant'.  In this section we look at starting from a set of constraints and see if it is possible to derive the corresponding value function.  We can then use this value function to determine allowed state changes e.g. for a swap the number of output tokens for an initial state and given number of input tokens.This approach feels familiar to the Lagrangian dynamics approach in classical physics (the author's background).  In economics the standard approach seems to be start from a value function (a.k.a. utility function) and derive substitution functions that give prices.  Here we attempt to solve the inverse problem. As a starting point, we consider deriving the Balancer value function (a [Cobb-Douglas Utility Function](https://www.wikiwand.com/en/Cobb%E2%80%93Douglas_production_function)) from the set of constraints for swaps 'the share of value of each token in the pool remains constant'.  We consider below two and three asset pools with tokens $X, Y, Z$.  The state of the system can be defined by three token balances $x$, $y$, $z$, and three weights $w_x$, $w_y$, $w_z$.  UniswapThe two asset case is a generalized form of [Uniswap](https://uniswap.org/docs/v2/protocol-overview/how-uniswap-works/) having token weights $w_x$ and $w_y$ summing to 1.  Uniswap uses $w_x = w_y = \frac{1}{2}$.  Here we use $x$ and $y$ to represent the token X and token Y balances.The total value of the pool in tems of token X is  $$v_{x}(x,y) = x + p_{x}^{y}y = x - \frac{\partial{x}}{\partial{y}}y$$i.e. number of tokens X plus the spot price of converting Y tokens into X tokens.The constant share of value constraint is hence represented by the equations: $$w_{x} = \frac{x}{x - \frac{\partial{x}}{\partial{y}}y} \\w_y = \frac{- \frac{\partial{x}}{\partial{y}}y}{x - \frac{\partial{x}}{\partial{y}}y}$$where in the two asset case the second equation is redundant since the weights sum to 1.<jupyter_code>x, y, w_x, w_y = sp.symbols('x y w_x w_y', positive=True)
k = sp.symbols('k', real=True)
X, Y = map(sp.Function, 'XY')
V = sp.Function('V')<jupyter_output><empty_output><jupyter_text>We can specify that swaps happen on some invariant surface $V(x,y)$ which allows us to replace the spot price $-\frac{\partial{x}}{\partial{y}}$ in  $x - y\frac{\partial{x}}{\partial{y}} = w_x$, subsitituting $-\frac{\partial{x}}{\partial{y}} = \frac{\partial{V}}{\partial{y}}/\frac{\partial{V}}{\partial{x}}$ via the [implicit function theorem](https://en.wikipedia.org/wiki/Implicit_function_theorem).<jupyter_code>sp.Eq(x/(x + y*V(x,y).diff(y)/V(x,y).diff(x)), w_x)<jupyter_output><empty_output><jupyter_text>SymPy's PDE solver balks at this equation as written, so multiply through to make things easier.<jupyter_code>const_share_eq = sp.Eq(x*V(x,y).diff(x), w_x*(x*V(x,y).diff(x) + y*V(x,y).diff(y)))
const_share_eq<jupyter_output><empty_output><jupyter_text>It turns out that SymPy is capable of solving the PDE directly to give a general solution.<jupyter_code>V_sol = sp.pdsolve(const_share_eq).subs({(1-w_x): w_y})
V_sol<jupyter_output><empty_output><jupyter_text>We can simplify the solution:<jupyter_code>sp.Eq(V(x,y), V_sol.rhs.simplify())<jupyter_output><empty_output><jupyter_text>We show below that the spot price is as expected regardless of the exact form of $F$ and if a specific form is chosen we achieve the desired Cobb-Douglas form.<jupyter_code>sp.Eq((V(x,y).diff(y)/V(x,y).diff(x)), V_sol.rhs.diff(y)/V_sol.rhs.diff(x))<jupyter_output><empty_output><jupyter_text>By taking the exponential of the constant we obtain the general Uniswap invariant.<jupyter_code>sp.Eq(V(x,y), sp.exp(w_y*V_sol.rhs.args[0]).simplify())<jupyter_output><empty_output><jupyter_text>Interestingly, the general solution offers the opportunity to use different functional forms to achieve the same constant share of value contraint.<jupyter_code>sp.Eq(V(x,y), (w_y*V_sol.rhs.args[0]).expand())<jupyter_output><empty_output><jupyter_text>We could derive the swap formulae for each form.  Would the formulae from log form of invariant be easier to implement on the Ethererum blockchain?  This is left as an exercise for the reader.  BalancerWe now consider the general case of a Balancer pool with $n$ assets and weights summing to 1.  Here we examine the three asset case and identify the geometric constraints imposed by the share of value conditions$$w_x = \frac{x}{x - \frac{\partial{x}}{\partial{y}}y - \frac{\partial{x}}{\partial{z}}z}\\w_y = \frac{-\frac{\partial{x}}{\partial{y}}y}{x - \frac{\partial{x}}{\partial{y}}y - \frac{\partial{x}}{\partial{z}}z}\\w_z = \frac{-\frac{\partial{x}}{\partial{z}}z}{x - \frac{\partial{x}}{\partial{y}}y - \frac{\partial{x}}{\partial{z}}z}$$for tokens X, Y and Z having total value $v_x(x,y,z) = x + p_{x}^{y}y + p_{x}^{z}z = x - \frac{\partial{x}}{\partial{y}}y - \frac{\partial{x}}{\partial{z}}z$.As before we can replace the spot prices given by the partial derivatives with expressions for the invariant surface V.  Below we show the $w_x$ condition, the others are similar.  The weight sum to 1 condition again allows us to eliminate one of the constraint equations.<jupyter_code>x, y, z, w_x, w_y, w_z = sp.symbols('x y z w_x w_y w_z', positive=True)
u, v, w = sp.symbols('u v w', positive=True)
xi = sp.Function('xi')
eta = sp.Function('eta')
zeta = sp.Function('zeta')
V = sp.Function('V')
V_d = sp.Function('\mathcal{V}')
const_share_eq_3_1 = sp.Eq(x*V(x,y,z).diff(x), w_x*(x*V(x,y,z).diff(x) + y*V(x,y,z).diff(y) + z*V(x,y,z).diff(z)))
const_share_eq_3_1<jupyter_output><empty_output><jupyter_text>We can simplify this to a constant coefficient first order PDE by the change of variables $$u = \xi(x) = \log{x}\\v = \eta(y) = \log{y}\\w = \zeta(z) = \log{z}$$ The general form for the the change of variables is given by<jupyter_code>const_share_eq_3_1.subs({
    V(x,y,z): V(xi(x),eta(y),zeta(z)),
}).simplify().subs({V(xi(x),eta(y),zeta(z)): V_d })<jupyter_output><empty_output><jupyter_text>where $\mathcal{V} = V(\xi(x), \eta(y), \zeta(z))$ Substituting the logarithmic functional form for the transformed variables gives<jupyter_code>const_share_eq_3_1.subs({
    V(x,y,z): V(xi(x),eta(y),zeta(z)),
    xi(x): sp.log(x),
    eta(y): sp.log(y), 
    zeta(z): sp.log(z)
}).simplify()<jupyter_output><empty_output><jupyter_text>The share of value weight constraints can written as a matrix equation:<jupyter_code>balancer_constraints = sp.ImmutableMatrix([
    [1-w_x, -w_x, -w_x],
    [-w_y, 1-w_y, -w_y],
    [-w_z, -w_z, 1-w_z]
])
v_grad = sp.ImmutableMatrix([V(u,v,w).diff(i) for i in [u,v,w]])
sp.Eq(sp.MatMul(balancer_constraints, sp.UnevaluatedExpr(v_grad), evaluate=False).subs({V(u,v,w): V_d }),
      (balancer_constraints*v_grad).subs({V(u,v,w): V_d }), 
     evaluate=False)<jupyter_output><empty_output><jupyter_text>We can use the weights summing to 1 condition to eliminate one of these equations.  The nullspace of the constraint matrix then defines a plane of constant value of the invariant in $u,v,w$ space which we can then map back to the original X, Y, Z token balances.<jupyter_code>(sp.simplify(sp.ImmutableMatrix([
#     [1-w_x, -w_x, -w_x],
    [-w_y, 1-w_y, -w_y],
    [-w_z, -w_z, 1-w_z]
]).nullspace()[0]).subs({(1-w_y-w_z): w_x})*w_z
).T*sp.ImmutableMatrix([sp.log(x), sp.log(y), sp.log(z)])<jupyter_output><empty_output><jupyter_text>It can be seen by inspection that exponentiating this invariant results in the original Balancer form.  As for the two asset case it is also possible to retain the value function in this form and derive new forms for the trading functions, which is again an exercise left to the reader.  Curve Curve uses the [StableSwap](https://www.curve.fi/stableswap-paper.pdf) invariant to reduce slippage for stablecoins all having equivalent value.  For example a pool could consist of USDC, USDT, BUSD and DAI, all of which are designed to track USD.  Pools tracking other assets are possible e.g. a BTC pool backed by sBTC, renBTC, wBTC.  The market maker token pool ideally consists of a balanced mix of each token type.  We consider a two asset pool below, this analysis extends to an arbitrary number of assets.The StableSwap invariant is designed to act as a constant sum market maker $x+y=1$ for small imbalances, and a constant product Uniswap market maker $xy=k$ as the pool becomes more imbalanced.  These are the price constraints defining the system i.e.* at small imbalance $-\frac{\partial{x}}{\partial{y}}=1$ and tokens are freely interchangeable* at larger imbalance $-\frac{\partial{x}}{\partial{y}}=x/y$ as for Uniswap (or in general an equal weight Balancer pool)The StableSwap invariant can be written as $V{\left(x,y \right)} = s \left(x + y\right) + x^{w_{x}} y^{w_{y}}$ where $s$ is an amplification parameter that determines the transition between constant sum and constant product behaviour.<jupyter_code>s = sp.symbols('s', positive=True)
V_ss = s*(x+y) + x**w_x*y**w_y
sp.Eq(V(x,y), V_ss)<jupyter_output><empty_output><jupyter_text>Below we show the spot price of Y tokens in terms of X tokens that results from this invariant function.  We can see that the limit $s \rightarrow \infty$ gives the constant sum behaviour while the $s \rightarrow 0$ limit gives constant product behaviour.<jupyter_code>V_x = (V_ss).diff(x).subs({w_x: sp.Rational(1,2), w_y: sp.Rational(1,2)}).simplify()
V_y = (V_ss).diff(y).subs({w_x: sp.Rational(1,2), w_y: sp.Rational(1,2)}).simplify()
ss_spot = V_y/V_x.simplify()
ss_spot_eq = sp.Eq(V(x,y).diff(y)/V(x,y).diff(x), ss_spot)
ss_spot_eq
sp.Eq(sp.Limit(ss_spot, s, sp.oo), (ss_spot).limit(s, sp.oo))
sp.Eq(sp.Limit(ss_spot, s, 0), (ss_spot).limit(s, 0))<jupyter_output><empty_output><jupyter_text>Following the previous procedure we'd hope to be able to solve the PDE for $V(x,y)$ from the spot price constraint:$$\left(s + \frac{\sqrt{y}}{2 \sqrt{x}}\right) \frac{\partial}{\partial y} V{\left(x,y \right)} = \left(s + \frac{\sqrt{x}}{2 \sqrt{y}}\right) \frac{\partial}{\partial x} V{\left(x,y \right)}$$Attempting this with the actual StableSwap spot price above doesn't immediately work although it should be possible to solve numerically.<jupyter_code>ss_spot_denom = sp.denom(ss_spot_eq.rhs)* sp.denom(ss_spot_eq.lhs)
sp.Eq(ss_spot_eq.lhs * ss_spot_denom, ss_spot_eq.rhs * ss_spot_denom)<jupyter_output><empty_output><jupyter_text>A new CurveWe can look at the form of the PDE from the StableSwap constraint and explore related functional forms.  It looks like the same limiting behaviour could be achieved with any ratio of $x/y$ i.e. without requiring the $\surd$.  We hence try $$\left(s x y + y\right) \frac{\partial}{\partial y} V{\left(x,y \right)} = \left(s x y + x\right) \frac{\partial}{\partial x} V{\left(x,y \right)}$$which is easily solvable by SymPy and results in a new Curve invariant:<jupyter_code>sol2 = sp.pdsolve((s*x*y + y)*V(x,y).diff(y) - (s*x*y + x)*V(x,y).diff(x), V(x,y)).rhs
V_ss_new = sp.log(sol2.args[0]).expand()
sp.Eq(V(x,y),V_ss_new)<jupyter_output><empty_output><jupyter_text>We see that the spot price has the same desired limiting behaviour:<jupyter_code>ss_spot_new = (V_ss_new.diff(y)/V_ss_new.diff(x)).simplify()
ss_spot_new
sp.Eq(sp.Limit(ss_spot_new, s, sp.oo), (ss_spot_new).limit(s, sp.oo))
sp.Eq(sp.Limit(ss_spot_new, s, 0), (ss_spot_new).limit(s, 0))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.13796672828096118, 'fraction_numerical': 0.0068022181146025875, 'mean_word_length': 5.215992647058823, 'pattern_counts': {'":': 0, '<': 81, '<?xml version=': 0, '>': 82, 'https://': 10, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '19', 'dir': 'jupyter-structured-clean-dedup', 'id': '473741', 'license': 'Apache-2.0', 'n_tokens_mistral': 4732, 'n_tokens_neox': 4599, 'n_words': 1467, 'path': 'scripts/amm_math_20210308.ipynb', 'repo_name': 'mattmcd/PyBayes', 'size': '13525'}