solver_workshop_exercises.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "4828dc5b",
   "metadata": {},
   "source": [
    "# Dex aggregator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bb3ce37c",
   "metadata": {},
   "outputs": [],
   "source": [
    "class UniswapV2:\n",
    "    def __init__(self, index, r_in, r_out, token_in, token_out):\n",
    "        self.index = index\n",
    "        self.r_in = r_in\n",
    "        self.r_out = r_out\n",
    "        self.token_in = token_in\n",
    "        self.token_out = token_out\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f'u{self.index}'\n",
    "\n",
    "    # Compute amount_out from amount_in\n",
    "    # uniswap v2 invariant: (r_in + k * in ) * (r_out - out ) == rin * rout\n",
    "    def f(self, in_):\n",
    "        k = 1-0.003   # fee\n",
    "        return k * in_ * self.r_out/(k * in_ + self.r_in)\n",
    "    \n",
    "    def __hash__(self):\n",
    "        return hash(repr(self))\n",
    "\n",
    "u1 = UniswapV2(1, 2.5, 9.7, \"GNO\", \"UNI\")\n",
    "u2 = UniswapV2(2, 0.5, 4.4, \"GNO\", \"BAL\")\n",
    "u3 = UniswapV2(3, 1, 1, \"GNO\", \"COW\")\n",
    "u4 = UniswapV2(4, 0.5, 4.4, \"UNI\", \"COW\")\n",
    "u5 = UniswapV2(5, 0.5, 4.4, \"BAL\", \"COW\")\n",
    "u6 = UniswapV2(6, 1, 1, \"UNI\", \"BAL\")\n",
    "\n",
    "amms = [u1, u2, u3, u4, u5, u6]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bddad4a4",
   "metadata": {},
   "outputs": [],
   "source": [
    "amms_by_token_in = {}\n",
    "for u in amms:\n",
    "    if u.token_in not in amms_by_token_in:\n",
    "        amms_by_token_in[u.token_in] = [u]\n",
    "    else:\n",
    "        amms_by_token_in[u.token_in].append(u)\n",
    "\n",
    "print(amms_by_token_in)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9a4de32b",
   "metadata": {},
   "outputs": [],
   "source": [
    "import sympy as sym\n",
    "        \n",
    "variables = []\n",
    "fraction_in = {}\n",
    "for token_in, amms_with_token_in in amms_by_token_in.items():\n",
    "    nr_amms_with_token_in = len(amms_with_token_in)\n",
    "    assert nr_amms_with_token_in > 0\n",
    "    if nr_amms_with_token_in == 1:\n",
    "        fraction_in[amms_with_token_in[0]] = 1\n",
    "        continue\n",
    "    for amm in amms_with_token_in:\n",
    "        new_var = sym.Symbol(f'alpha{amm.index}')\n",
    "        fraction_in[amm] = new_var\n",
    "        variables.append(new_var)\n",
    "\n",
    "print(variables)\n",
    "print(fraction_in)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "55054732",
   "metadata": {},
   "outputs": [],
   "source": [
    "def compute_out_from_in_fn(token_in, token_out, amount_in):\n",
    "    if token_in == token_out:\n",
    "        return amount_in\n",
    "    return sum(\n",
    "        u.f(fraction_in[u] * compute_out_from_in_fn(token_in, u.token_in, amount_in))\n",
    "        for u in amms\n",
    "        if u.token_out == token_out\n",
    "    )\n",
    "\n",
    "in_amount = 5\n",
    "out_from_in_fn = compute_out_from_in_fn(\"GNO\", \"COW\", in_amount)\n",
    "\n",
    "print(out_from_in_fn)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0c6308df",
   "metadata": {},
   "outputs": [],
   "source": [
    "penalty_coefficient = 10\n",
    "step_rate = 0.01\n",
    "\n",
    "def gradient_ascent(fn, variables, rate):\n",
    "    eps = 0.0001\n",
    "    jacobian = {v : sym.diff(fn, v) for v in variables}\n",
    "    state = {v : 0 for v in variables}\n",
    "    \n",
    "    def compute_gradient():\n",
    "        j = {v : jacobian[v].subs(state).evalf() for v in variables}\n",
    "        for v in j.keys():\n",
    "            j[v] -= penalty_coefficient * min(0, state[v])\n",
    "            j[v] -= penalty_coefficient * max(0, state[v] - 1)\n",
    "                            \n",
    "        return j\n",
    "\n",
    "    def update_state(gradient):\n",
    "        return {v : state[v] + rate * gradient[v] for v in variables}\n",
    "\n",
    "    def get_max_delta(next_state):\n",
    "        return max(abs(state[v] - next_state[v]) for v in variables)\n",
    "    \n",
    "    def has_converged(max_delta):\n",
    "        return max_delta <= eps\n",
    "\n",
    "    print(f'{\"objective value\":20}\\tmax delta')\n",
    "    while True:\n",
    "        gradient = compute_gradient()\n",
    "        next_state = update_state(gradient)\n",
    "        max_delta = get_max_delta(next_state)\n",
    "        print(f'{fn.subs(state).evalf()}\\t{max_delta}', end='\\r')\n",
    "        if has_converged(max_delta):\n",
    "            break\n",
    "        state = next_state\n",
    "\n",
    "\n",
    "def compute_penalty(penalty_coeff):\n",
    "    return sum(penalty_coeff * (1 - sum(fraction_in[amm] for amm in amms_for_token))**2 for amms_for_token in amms_by_token_in.values() if len(amms_for_token)>1)\n",
    "\n",
    "gradient_ascent(out_from_in_fn - compute_penalty(penalty_coefficient), variables, step_rate)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0b71ee4a",
   "metadata": {},
   "source": [
    "# 2-token case"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0eb993b8",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "class SellLimitOrder:\n",
    "    def __init__(self, index, limit_xrate, max_out_amount):\n",
    "        self.index = index\n",
    "        self.limit_xrate = limit_xrate\n",
    "        self.max_out_amount = max_out_amount\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f'o{self.index}'\n",
    "\n",
    "    # Compute maximum amount_out from an xrate r\n",
    "    # r is in [out/in] units\n",
    "    def amount_out_given_xrate(self, r):\n",
    "        return self.max_out_amount if r <= self.limit_xrate else 0\n",
    "\n",
    "o1 = SellLimitOrder(1, 4, 1)\n",
    "o2 = SellLimitOrder(2, 3, 2)\n",
    "o3 = SellLimitOrder(3, 2, 2)\n",
    "o4 = SellLimitOrder(4, 3/2, 1)\n",
    "u5 = UniswapV2(5, 1, 2, \"COW\", \"GNO\")\n",
    "u6 = UniswapV2(6, 3, 2, \"COW\", \"GNO\")\n",
    "\n",
    "selling_COW = [o1, o2, o3]\n",
    "selling_GNO = [o4, u5, u6]\n",
    "\n",
    "# compute amm out amount from xrate in [out/in] units\n",
    "# uniswap v2 invariant: (r_in + k * in ) * (r_out - out ) == rin * rout\n",
    "def amount_out_given_xrate(self, r):\n",
    "    k = 1-0.003\n",
    "    return max(0, (-r * self.r_in + k * self.r_out)/(k * r))\n",
    "\n",
    "UniswapV2.amount_out_given_xrate = amount_out_given_xrate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7396e361",
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "nr_steps_for_drawing = 1000\n",
    "r_lb = 0.001\n",
    "r_ub = 2\n",
    "r_dom = [\n",
    "    r_lb + s * (r_ub - r_lb) / nr_steps_for_drawing\n",
    "    for s in range(nr_steps_for_drawing)\n",
    "]\n",
    "\n",
    "fig, ax = plt.subplots()\n",
    "\n",
    "# plot orders selling COW\n",
    "def total_amount_orders_selling_COW(r):\n",
    "    return sum(o.amount_out_given_xrate(1/r) for o in selling_COW)\n",
    "\n",
    "ax.plot(r_dom, [total_amount_orders_selling_COW(r) for r in r_dom])\n",
    "\n",
    "# plot orders + amms selling GNO\n",
    "def total_amount_orders_selling_GNO(r):\n",
    "    return sum(o.amount_out_given_xrate(r)/r for o in selling_GNO)\n",
    "\n",
    "ax.plot(r_dom, [total_amount_orders_selling_GNO(r) for r in r_dom])\n",
    "\n",
    "ax.set_xlabel(\"xrate [GNO/COW]\")\n",
    "ax.set_ylabel(\"traded amount of COW\")\n",
    "plt.ylim([0,6]);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5fdc9d17",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bisect(fn, x_lb, x_ub, eps):    \n",
    "    assert fn(x_lb) * fn(x_ub) <= 0\n",
    "    x_mid = (x_lb + x_ub) / 2\n",
    "    if x_ub - x_lb <= eps:\n",
    "        return x_mid\n",
    "    y_mid = fn(x_mid)\n",
    "    if y_mid > 0:\n",
    "        return bisect(fn, x_lb, x_mid, eps)\n",
    "    else:\n",
    "        return bisect(fn, x_mid, x_ub, eps)\n",
    "\n",
    "def token_balance_violation(r):\n",
    "    return total_amount_orders_selling_COW(r) - total_amount_orders_selling_GNO(r)\n",
    "\n",
    "r = bisect(token_balance_violation, 0.001, 2, 0.01)\n",
    "print(r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2cad5e6e",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}