{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Crypto Trading and March 29th @ Slash Hackathon 2019 Questions? Contact: roman@celo.org \n",
"Table of Contents \n",
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Representations of a Market"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Assume that there is a market with $N$ currencies. Also assume for simplicity that every possible pair can be traded (not a necessary assumption for the depicted representations). The exchange rates can be displayed by a source-to-target exchange rate matrix. Let us generate and analyze an exemplary such matrix and translate it into a graph representation."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"code_folding": []
},
"outputs": [
{
"data": {
"application/vnd.jupyter.widget-view+json": {
"model_id": "9cd395e026aa41f9bd34d24c2bc40212",
"version_major": 2,
"version_minor": 0
},
"text/plain": [
"Button(description='New Example', style=ButtonStyle())"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# set things up and create button"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"code_folding": []
},
"outputs": [],
"source": [
"# set some parameters, generate exchange rate matrix and the corresponding graph\n",
"N = 6 # number of currencies\n",
"max_spread_pct = 0.05 # maximum bid-ask spread in pct of bid, 0.05 for 5%"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exchange Rate Matrix Representation"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The exchange rate matrix takes the current best bids and best asks in the market and generates a matrix of multipliers that shows how many units of the target currency one would receive for a unit of the source currency."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"code_folding": [],
"scrolled": false
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"
\n",
" \n",
" \n",
" target \n",
" \n",
" \n",
" 0 \n",
" 1 \n",
" 2 \n",
" 3 \n",
" 4 \n",
" 5 \n",
" \n",
" \n",
" \n",
" \n",
" source \n",
" 0 \n",
" 1.00 \n",
" 0.58 \n",
" 0.63 \n",
" 0.27 \n",
" 0.17 \n",
" 0.20 \n",
" \n",
" \n",
" 1 \n",
" 1.68 \n",
" 1.00 \n",
" 0.39 \n",
" 0.74 \n",
" 0.47 \n",
" 0.79 \n",
" \n",
" \n",
" 2 \n",
" 1.57 \n",
" 2.48 \n",
" 1.00 \n",
" 0.04 \n",
" 0.15 \n",
" 0.11 \n",
" \n",
" \n",
" 3 \n",
" 3.64 \n",
" 1.35 \n",
" 22.94 \n",
" 1.00 \n",
" 0.22 \n",
" 0.23 \n",
" \n",
" \n",
" 4 \n",
" 5.84 \n",
" 2.02 \n",
" 6.84 \n",
" 4.40 \n",
" 1.00 \n",
" 0.49 \n",
" \n",
" \n",
" 5 \n",
" 4.76 \n",
" 1.21 \n",
" 8.59 \n",
" 4.41 \n",
" 1.97 \n",
" 1.00 \n",
" \n",
" \n",
"
\n",
"
"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# display corresponding directed graph"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"An arbitrage is a cylce for which the **cumulative product** of the edge weights in an exchange rate graph is bigger than one. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Log-Transformed Representations"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"There are many well known graph algorithms that deal with cycle lengths - the **cumulative sum** of the edge weights. Fortunately, one can easily translate a cumulative product optimization problem into a convex cumulative sum optimzation problem by taking logs. To see this, note that for $a>0\n",
"\n",
"\n",
" \n",
" \n",
" target \n",
" \n",
" \n",
" 0 \n",
" 1 \n",
" 2 \n",
" 3 \n",
" 4 \n",
" 5 \n",
" \n",
" \n",
" \n",
" \n",
" source \n",
" 0 \n",
" -ln(1.0) \n",
" -ln(0.58) \n",
" -ln(0.63) \n",
" -ln(0.27) \n",
" -ln(0.17) \n",
" -ln(0.2) \n",
" \n",
" \n",
" 1 \n",
" -ln(1.68) \n",
" -ln(1.0) \n",
" -ln(0.39) \n",
" -ln(0.74) \n",
" -ln(0.47) \n",
" -ln(0.79) \n",
" \n",
" \n",
" 2 \n",
" -ln(1.57) \n",
" -ln(2.48) \n",
" -ln(1.0) \n",
" -ln(0.04) \n",
" -ln(0.15) \n",
" -ln(0.11) \n",
" \n",
" \n",
" 3 \n",
" -ln(3.64) \n",
" -ln(1.35) \n",
" -ln(22.94) \n",
" -ln(1.0) \n",
" -ln(0.22) \n",
" -ln(0.23) \n",
" \n",
" \n",
" 4 \n",
" -ln(5.84) \n",
" -ln(2.02) \n",
" -ln(6.84) \n",
" -ln(4.4) \n",
" -ln(1.0) \n",
" -ln(0.49) \n",
" \n",
" \n",
" 5 \n",
" -ln(4.76) \n",
" -ln(1.21) \n",
" -ln(8.59) \n",
" -ln(4.41) \n",
" -ln(1.97) \n",
" -ln(1.0) \n",
" \n",
" \n",
"
\n",
""
],
"text/plain": [
" target \n",
" 0 1 2 3 4 5\n",
"source 0 -ln(1.0) -ln(0.58) -ln(0.63) -ln(0.27) -ln(0.17) -ln(0.2)\n",
" 1 -ln(1.68) -ln(1.0) -ln(0.39) -ln(0.74) -ln(0.47) -ln(0.79)\n",
" 2 -ln(1.57) -ln(2.48) -ln(1.0) -ln(0.04) -ln(0.15) -ln(0.11)\n",
" 3 -ln(3.64) -ln(1.35) -ln(22.94) -ln(1.0) -ln(0.22) -ln(0.23)\n",
" 4 -ln(5.84) -ln(2.02) -ln(6.84) -ln(4.4) -ln(1.0) -ln(0.49)\n",
" 5 -ln(4.76) -ln(1.21) -ln(8.59) -ln(4.41) -ln(1.97) -ln(1.0)"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"\n",
"...results in:\n"
]
},
{
"data": {
"text/html": [
"\n",
"\n",
"
\n",
" \n",
" \n",
" target \n",
" \n",
" \n",
" 0 \n",
" 1 \n",
" 2 \n",
" 3 \n",
" 4 \n",
" 5 \n",
" \n",
" \n",
" \n",
" \n",
" source \n",
" 0 \n",
" 0.000000 \n",
" 0.544727 \n",
" 0.462035 \n",
" 1.309333 \n",
" 1.771957 \n",
" 1.609438 \n",
" \n",
" \n",
" 1 \n",
" -0.518794 \n",
" 0.000000 \n",
" 0.941609 \n",
" 0.301105 \n",
" 0.755023 \n",
" 0.235722 \n",
" \n",
" \n",
" 2 \n",
" -0.451076 \n",
" -0.908259 \n",
" 0.000000 \n",
" 3.218876 \n",
" 1.897120 \n",
" 2.207275 \n",
" \n",
" \n",
" 3 \n",
" -1.291984 \n",
" -0.300105 \n",
" -3.132882 \n",
" 0.000000 \n",
" 1.514128 \n",
" 1.469676 \n",
" \n",
" \n",
" 4 \n",
" -1.764731 \n",
" -0.703098 \n",
" -1.922788 \n",
" -1.481605 \n",
" 0.000000 \n",
" 0.713350 \n",
" \n",
" \n",
" 5 \n",
" -1.560248 \n",
" -0.190620 \n",
" -2.150599 \n",
" -1.483875 \n",
" -0.678034 \n",
" 0.000000 \n",
" \n",
" \n",
"
\n",
"
"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# display log-transformed exchange rate matrix and corresponding graph"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Every cycle of **negative length** in the above graph with negative-log-transformed weights is an arbitrage cylce. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Identifying Arbitrage Cycles"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Finding an Arbitrage Cycle with Bellman-Ford"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"One can check if an arbitrage cylce exists and if so, **identify one such a cylce** in the log-transformed graph representation using a slighlty adjusted [Bellman-Ford algorithm](https://en.wikipedia.org/wiki/Bellman-Ford_algorithm) which has a complexity of $\\mathcal{O}(|V||E|)$ where $|V|$ denotes the number of vertices and $|E|$ denotes the number of edges. A neat visualization of how the Bellman-Ford algorithm works can be found [here](https://www-m9.ma.tum.de/graph-algorithms/spp-bellman-ford/index_en.html). \n",
"\n",
"The Bellman-Ford algorithm itself only gives the shortest distance from a prespecified source node to all other nodes in the graph. It needs to be adjusted to:\n",
"- show if there is a negative cycle\n",
"- to output a negative cycle\n",
"- to always find a negative cycle (if there is one) even the graph is not connected"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"code_folding": []
},
"outputs": [],
"source": [
"# The Bellman-Ford function used in this notebook\n",
"def bf_negative_cycle(G):\n",
"\n",
" # Remove nan edges\n",
" n = len(G.nodes()) + 1\n",
" edges = [edge for edge in G.edges().data() if ~np.isnan(edge[2]['weight'])]\n",
"\n",
" # Add a starting node and add edges with zero weight to all other nodes\n",
" start_node_edges = [(n-1, i, {'weight': 0}) for i in range(n-1)]\n",
" edges = edges + start_node_edges\n",
"\n",
" # Initialize node distances and predecessors\n",
" d = np.ones(n) * np.inf\n",
" d[n - 1] = 0 # Starting node has zero distance\n",
" p = np.ones(n) * -1\n",
"\n",
" # Relax n times\n",
" for i in range(n): \n",
" x = -1\n",
" for e in edges:\n",
" if d[int(e[0])] + e[2]['weight'] < d[int(e[1])]:\n",
" d[int(e[1])] = d[int(e[0])] + e[2]['weight']\n",
" p[int(e[1])] = int(e[0])\n",
" x = int(e[1])\n",
" if x == -1: # If no relaxation possible, no negative cycle\n",
" return None\n",
" \n",
" # Identify negative cycle\n",
" for i in range(n):\n",
" x = p[int(x)]\n",
" cycle = []\n",
" v = x\n",
" while True:\n",
" cycle.append(int(v))\n",
" if v == x and len(cycle) > 1:\n",
" break\n",
" v = p[int(v)]\n",
" return list(reversed(cycle))"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"code_folding": []
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"At least one arbitrage cycle exists! One such cycle is [2, 1, 5, 3, 2] with cycle length -5.2893 which implies and arbitrage multiplier of 198.2033.\n"
]
},
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAeQAAAE/CAYAAACXV7AVAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAIABJREFUeJzs3Xl4TOfbwPHvJJmsRCSWRGyREoqKPaggiKo1pIhqSNBqq0VRVYraW6W0/dEqkdi3xq5Ra621r0FtJRFbIovInsx5/5g3U6nQqCQny/25rl7MmTNn7mNOn/s8z3kWjaIoCkIIIYRQlZHaAQghhBBCErIQQghRIEhCFkIIIQoASchCCCFEASAJWQghhCgAJCELIYQQBYAkZCGEEKIAkIQshBBCFACSkIUQQogCQBKyEEIIUQBIQhZCCCEKAEnIQgghRAEgCVkIIYQoACQhCyGEEAWAJGQhhBCiAJCELIQQQhQAkpCFEEKIAkASshBCCFEASEIWQgghCgATtQMQIkcUBVJSQacDIyMwMwWNRu2ohMh9cq0XW5KQRcGVlg4PouHBQ0hK0W/TaPQFlgJYmkE5OyhvCyZyKYtCTK51AWgURVHUDkKILHQ6CL8PEff1rxVFXzg9WUtQlL+3AziWh0rl9TUKIQoLudbFEyQhi4IlJRVCr0NyMqDJWVOdogAKmJtDbWd9E58QBZ1c6+IfJCGLgiMlFc7+qW+++2ct4d9k1iK0JlDPRQoqUbDJtS6yIW0eomDQ6fS1hbR0fVPci3Zi0Wj0n0tL1x9Hp8ubOIV4WXKti2eQhCwKhvD7kJzy8r1JNRp9E+Dt+7kTlxC5Ta518QySkIX60tL/7tSSTSGVmpbGJ/O+obF/X6r36kK7j99jz4lj2R9LowE0+kIqPT3vYs6hkJAQatasSY0aNfjqq6+eej8sLIx27dpRr149PDw8uHPnTpb34+PjqVSpEh9//LFh2/jx46lcuTLW1tZPHW/t2rXUrl2bunXr0q9fP8P2oKAgatSogYuLC0uXLjVsX7NmDfXq1aNu3bqMHTs2y7Hu3btHhw4dnvqO1NRU+vTpQ/Xq1WnWrBlhYWHZnvu8efOoW7cudevW5bvvvjNsj4mJwdPTExcXFzp06EBcXBwAjx49omvXrri6ulK3bl0CAwMBOHv2LM2bN6du3bq4urqydu1aw7H8/PyoVq0a9evXp0GDBpw7dw6A2NhYevToQb169XBzc+PixYvZxpjv/uVaX7J1I2+M+IAqXh0ZPvfr5x+rgF3r4uVJQhbqexCt//MZNYb0jHQcy5YjeMYc/ly9iTH9BvDe11MIv38v++NlHud+dB4Em3M6nY6hQ4eyY8cOQkNDWbVqFZcvX86yz6hRoxgwYABnz55lwoQJfPbZZ1ne/+KLL2jVqlWWbV27duX48eNPfd+1a9f46quvOHLkCOfPn2fu3LmAPgFOnjyZ48ePc/ToUb788kvi4uKIjo7m008/Ze/evZw/f5579+6xd+9ew/FCQkJ44403nvqexYsXY2try9WrVxk+fDiffvrpU/uEhoayePFiTpw4wZkzZ9iyZQs3btwAYObMmbRr144///wTDw8PZsyYAcD//vc/ateuzZkzZ9i7dy8jR44kPT0dS0tLli1bxvnz5/n1118ZPnw4jx49MnzX7NmzOX36NKdOneK1114DYPr06dSvX5+zZ88SFBSU5YZGVf9yrZe3tWN477fxaf/0v3u2Csi1LnKHJGShvgcP/7/3aPYszS0Y2deXSuXtMTIyon2TZlQu78C5a1eefUxF0R9XRceOHaN69epUqVIFrVZLnz592LRpU5Z9Ll68SJs2bQBo3bp1lvdPnjzJgwcP8PT0zPKZJk2aUL58+ae+7+eff+bDDz801JzLlCkDwI4dO/D09KRUqVLY2Njg6elJSEgIN27coEaNGtja2gLQtm1bfvnlF8PxQkJC6Nix41Pfs2nTJvr37w+At7c3u3fvfmqfS5cu0bRpU8zMzDA2NqZVq1YEBwc/9fn+/fuzceNGADQaDfHx8YC+ZcDOzg4TExOqV6+Os7MzAA4ODpQrV47IyEjDd+myeYZ68eJFPDw8AHBxceHmzZtZPpPXJk2aREhICE/1mf2Xa/3N5i15w60FpUs+3frxTAXgWhe5QxKyUJei6CdCeIHnaZEx0VyPCMelStVn76TR6I+r4iCCiIgIKlWqZHhdsWJFIiIisuzj6upqSFTBwcE8fvyYmJgYFEVh1KhRfPPNN08X6s9w5coV/vzzT15//XWaN2/Ojh07so3D0dGRiIgIXnnlFf7880/CwsJIT09n48aNhIeHA/okd+XKFWrWrPnc8zI2NsbGxobo6Kw1tDp16nDgwAFiYmJITExk+/bthmPfv3/fcENhb2/PgwcPABg6dCgXL16kQoUK1KtXj3nz5j313ceOHSMtLc2QoEHfhO/q6srIkSNJS0sDoF69eoZ/12PHjhEWFsbt27dz9O+YGxYtWkS/fv1o0qTJ34n5P1zrOVIArnWRO2TKF6GulFT9nzkopFJSUoh79Ih3Z02lawt37KxKEhMT88z9jTQaJn3wIVGP43Mr2mcqWbIkc+fOxdT0xYagzJo1i6FDhxIYGIi7uzuOjo4YGxszf/58OnXqRIUKFQBylJTT09O5du0a+/fvJywsDHd3dy5cuPDM/W1sbFiwYAG9evXC2NiY5s2bc/36dQCOHj1K06ZNc3QO2cVWs2ZNxowZQ/v27SlRogT169fH2Ng4289r/v+3DwkJoX79+uzZs4fr16/Tvn17zp07R4kSJQC4e/cuvr6+LFu2zPDZmTNnUr58edLS0hg8eDBfffUV48eP57PPPmPYsGE0aNCAunXrZvv9ycnJDB48OEfn+KKio6NRFIVz587RtWtXypQpw1+X/sRMf8L/+vm09LRsa/7ZypzRKyUVzM1eKm6hLknIQl06XY5rDEbGxoxbNB8LcwumD/kYbQ6mEHyrpzeJ5P2wEK1W+1SB7+jomKXD0+3bt3F0dMyyj4ODg6GZOCEhgV9++QVra2uOHDnCwYMHmT9/PvHx8aSlpVGyZEmmT5/+zBgqVqyIm5sbRkZGVK1alRo1anD16lUcHR3Zt29fljgym8k7depEp06dAH2Td+Y5/Prrr4bnx+PHj2fbtm1oNBpOnTqFo6Mj4eHhVKhQgYyMDB49emRo9n6Sn58ffn5+AIwbN85Qq7a3tzfUku/du0e5cuUACAwMNHQsc3Z2xsnJicuXL9OoUSMePXpE586dmTFjBo0bNzZ8R2ZNW6vV4ufnx+zZswH9DVJAQIBhPycnJ6pVq5YlPhMTE0PTeW4LCQkhOTkZY2NjSpQowbvvvoupiUmOr/WM9IycJ2QADTL8qQiQhCzUZWSUdVrAZ1AUhU//9y0x8fEsnzgNc7Mc1AQUheZuLVSrNTRu3Jhr165x69YtHBwcWL16NatWrcqyz8OHD7G1tUWj0TBjxgz8/f0BWL58uWGfoKAgTp48+VQy/mfNtHv37qxatYr+/fsTFRXF1atXqVatGtWqVWPcuHHExcWh0+nYuXMnM2fOBCAyMpKyZcsSExPD/PnzWb9+PQC7d+9mzJgxAEydOpWpU6cavqdr164EBQXRtGlT1q1bZ3hW+0+Zxw4LC2PDhg388ccfhs8HBgYyZswYAgMD6datGwCVK1dm165dtGjRgvv373PlyhWqVatGWloaXl5e9O/fHy8vryzfce/ePezt7VEUhY0bN1KnTh0A4uLisLS0RKvV8vPPP9OqVStDTTuTiYkJ7dq1yzb2l1WqVClKly7NhAkT6N27N1qtVj/UKQfX+n+iIFNpFgGSkIW6MmcZ+peC6rP587gaHsaaKV/nOBlnOb4KjI2N+eGHH/D09ESn0zFw4EBq1arFxIkTady4MZ07d2bfvn2MHTsWIyMj3N3d+d///vevxx0zZgwrV64kKSmJypUrM2jQICZMmECHDh347bffqF27NiYmJnzzzTeULl0a0PfWbtSoERqNhokTJ2JjYwPAsGHDOHv2rGG7s7MzUVFRWFhYYGVlle33Dxw4kHfeeYfq1atjZ2fH6tWrAX2T8uDBg9m6dSsAPXv2JDo6Gq1Wy/z58w2dzcaMGUOvXr0ICAigSpUqhmFMX3zxBQMGDDD0lP7666+xtbVlxYoVHDx4kJiYGJYsWYJGoyEwMJDXXnuNt99+m6ioKBRFwdXVlR9//BHQdyrr378/RkZG1K5dm8WLF//Xn/E/2b59O05OTvpEnCkH13p6ejoZOh0ZugwydDpSUlMxNjLC5HmtQQXgWhe5Q6bOFOo7fQkSk595h3/7wX2aDOqHqYkJJsZ/F0xffzicHq3bZn9MnQ4szaF+rbyIuEhbsWIFERER2Q5nEi/pX6712SuXMnv1MpT/f5Sj0WgY2ecdRvb1ffYx5VovMiQhC/VFPIBbd3K3KU9RoEoFcCyXe8cU4mXl8FqPi4vD1NQUCwuLfz+mXOtFhjx0EOor//8dgnLr3jDzOOWf7mgkhKrkWhfPIQlZqM/ERL/GK8rLF1SZy9NVLC8LuYuCR6518RySkEXBUKm8fo3X3CikzM31hZQQBZFc6+IZJCGLgsHICGo7o2hN9J1UXrSwUhT957Qm+oXbZQiIKKj+/1pHrnXxD/JLigLh5MmTtPBoQ+OBb4OFOS/UpJfZdGdhLgu2i8LBzFR/rcq1Lp4gCVmoav/+/Xh6euLp6cmRI0coX7kSuLpARXv9Dpm1gX8WWP/cXtFe/zkpoERhYWYq17rIQnoCCNXExsbSq1cvHj16RHp6OlZWVnTp0kXfBFfZASqU1S8r9+Dh35Pna9DPSgT6sZfl7PQ9TKVTiyiMnnGtZ87vbUjCcq0XCzIOWajq3LlzuLu7k5KSgo2NDRs2bMDNze3pHTMnz9fp9IWYmWneTEEohNoUhcnjv6Cha306deks13oxIrdaQlWHDh2iUaNGmJqacvToUerWrZv9jhqNrGQjigeNhpjEBOIz0uSaL2YkIQvVHDx4kJ9++olt27Zhb2/PhQsXnjl/shBCFHWSkIUq7ty5w9ChQ/nhhx8MSxLWq1dP5aiEEEI90sta5DtFUUhKSmLYsGG8/vrraocjhBAFgiRkke80Gg1VqlRhwIABaocihBAFhiRkkafS0tIMf3+yQ7+JicnfQzuEEELIM2SRNy5cuMDs2bPRarVUrFiRCRMmSAIWQojnkBqyyHUpKSkMGjSImjVr4u3tzblz51i1ahWQtZYshBDib1JDFrlu1qxZNG3alDFjxgBw5coVjhw5go+Pj9SShRDiGaSGLHJNZu23ZcuW+Pj4GLZ36NCBS5cuGV6fPn0632MTQoiCTmrIItfcv38fExMTGjRoQMmSJQ3b7ezsiIiIICkpiWXLlhEcHMyvv/4qtWUhhHiCJGSRK27evIm3tzf16tUjMTGR77//Hjs7OzQaDba2trRt25bFixcTFBTE8uXL0Wg0KIoiSVkIIf6fNFmLXNGvXz/eeecdJk2aRNmyZXn8+DGhoaGG962srBgxYgTjx4/HxcUFnU4nyVgIIZ4gNWTx0u7evUuVKlUYNmwYALt27SIsLIzExERKly7NsmXLaNq0KV9++SXdunUDwMhI7gWFEOJJkpDFSytRogQ3btyge/fuJCUl4ezsTHBwMLGxsQwdOpSdO3fi5eWFl5cXgDRVCyFENiQhi/8sPDyc1NRU7Ozs2LdvH6tWrSIuLg4XFxeMjIywtbWlSpUqnDlzhk6dOhkSsSRjIYR4miRk8Z9ERUXRt29fSpcuTdmyZfnhhx8YMGAAv/32G59//jmmpqZUrlyZkJAQFi1aBCCJWAghnkMe5In/xM/Pj27durFu3ToSEhIICQnh2rVruLm58dlnn9GvXz9Gjx7Nu+++S8OGDdHpdGqHLIQQBZrUkMULi4qKwszMjN69e2NmZsbt27dZtGgRVlZW2NjYMGXKFC5duoSiKNjY2ADSiUsIIf6NlJLihZUpU4ZatWrx2muv4e3tTWJiItu2bWPixIlYWFjw66+/UqpUKUMyFkII8e8kIYscS0lJIT4+HoApU6awadMmunbtSqdOnQCoXbs2Tk5OHDx4kIyMDDVDFUKIQkcSssiR1NRU3nrrLT788EPc3NwIDw/H3d2dzp07c+PGDaZOncrFixf5+eef8fHxwdjYWO2QhRCiUJGELHKkb9++VKtWje+++w4PDw8++eQTkpKSKFWqFH369OHChQuMHTuW999/n7Zt28oyi0II8YKkU5f4VwcOHECn0zF37lwAhg4dyuDBg0lISMDCwoJOnTrRpUsXoqOjsbW1BWSIkxBCvCipIYt/5ezszEcffQToZ9mqUKEC1tbW3Lx5E4D9+/eTkZFhSMZCCCFenCRk8UyPHj0iOjqa9PR02rRpA/y95rGlpSWhoaGcOXMGX19fwsLC1AxVCCEKPWmyFs/k4+ODvb09d+/eZfjw4Xh6ehrGE3fr1o1NmzYRGBjInDlzcHJyQqfTyXhjIYT4j6T0FNkaPHgwFStWZM6cObRo0YKHDx9y+/ZtEhISAHBycmLJkiW0bt0ab29vQCb/EEKIlyE1ZPGUU6dOkZaWRmBgIADHjh0jODiYAwcOcOrUKX744Qdq1KjB1KlT+fzzzwFZwUkIIV6WJGTxlAYNGjBr1iwADh8+jKmpKQcPHsTMzIxp06axfft2GjVqZEjG0lQthBAvT0pRka2yZcsC0KRJExYuXIiFhQVGRkbUrFmTGzdukJaWZlgwQpKxEEK8PClJhcHkyZO5fv264XV6ejomJiaULl3asO3HH3+kZcuWaLVaScRCCJGLpEQVAIwYMYJ58+bh7e3Nhg0bADAxMTHMSR0TE0Pfvn2pWbMmAwcOVDNUIYQokuQZsuDhw4fExsayb98+wsPDGTduHOfOnWPixImGOalLly7N22+/bVhIQjpxCSFE7pKELLCzs2POnDkYGxtTt25dKleuzMiRI+nVqxdr167l2rVr/PXXX5KMhRAiD0mTtQD0NWBra2sA6tSpw7Jly6hUqRL16tWjYcOGWVZvkmQshBC5TxJyMfesVZnKlSvH7NmzuXfvHp999hkeHh6ygpMQQuQhScjFnEajMQxf+qcffviBNm3aMHbsWMO+Qggh8oY8Qy6G9u3bx5kzZ7h58yYjR46kUqVKwN+15czE6+PjwwcffGB4TxKyEELkHakhFzO3bt3ik08+wdTUlLS0NAICAgzvaTQaNBoNly9f5ty5c9jZ2WFkZCTJWAgh8oEk5GJm+PDhvPPOO3zwwQd07tyZ48eP89VXXzFt2jTDPqdPnyY8PNzwWpKxEELkPWmyLkaioqLo168fPXv2BGDevHnY29vTrFkzhg0bxuXLl1m6dCk+Pj4qRyqEEMWP1JCLkTJlyuDl5QVAREQEAwYMIDAwEHd3d7Zu3YqFhcUzO3gJIYTIW5KQi4nMKTAz5592dHSkT58+hvcPHz7M5cuXSU9PVyU+IYQo7iQhF3EJCQn89ddfhok9/jmWWFEUzp8/z5dffsmsWbMwMzOT8cZCCKECSchF3L59+xg1ahR3794F/k7IQUFBXLhwgcePH7N69WpGjx5N06ZNpUe1EEKoRDp1FXEeHh6EhoZy4cIFHBwcMDIy4ujRo0ycOJHdu3dTsmRJxo0bh6WlJSA9qoUQQi1SQy6iUlJSALCwsOC1115j0qRJ7Ny5E4BDhw6xaNEinJ2dSUtLMyRjIYQQ6pEachF06dIldu3ahY+PD2XKlOGNN95Aq9WyfPlynJyc+PjjjzEx0f/0Wq1W5WiFEEKA1JCLnLS0NLy8vDA3N6dMmTKG7W3btqVx48bs37/fkIxliJMQQhQcUkMuYgICAmjYsCGDBw9Gp9Oxbds2YmNjefXVV+nTpw9vvfUWKSkpvP/++4YhUEIIIdQnJXIRU69ePRwcHADw8/NjyZIlnD9/ngEDBnDkyBGWLVvG77//zr59+9QNVAghRBZSQy4ikpKSsLCwoESJEuzZs4cpU6ZgZ2dHUFAQAK1atWLPnj106tSJbt264eLionLEQgghniQ15CIgLCyMvn37kpiYSJ06dfjmm29Ys2YNe/bsMexjYWHBqVOnSE9Pp2fPnoZatBBCiIJBEnIRMGTIEPbu3cu7775LXFwcHh4ebNy4kbS0NNq2bUtwcDCjRo3i3XffxcTERHpWC1HA+fv78/rrr6sdhshnkpALucGDB/PKK68QHh6Oubk5V65cAeCVV14hNDQULy8v0tPT+eSTTwyrOMnkH0IUbHXr1qVixYpqhyHymTxDLsQOHz5MVFQUGzZsAMDa2pqhQ4fy22+/UapUKQCGDh2a5TMyNaYQQhRMGkVWEii0oqOjMTY2NiRf0NeYy5Urx8SJEzE2NjYsKiGEEKJgkybrQigxMZEjR45w6tQpQzLOXDbRx8eHCxcuEB4eLslYCCEKEUnIhZCXlxcLFy7E19eX2bNnAxhm3/Lw8MDZ2ZkePXoQFxcnSykKIUQhIU3Whcy0adM4deoUv/zyC2fOnGHbtm24urpSr149QyeQuLg4du3aRc+ePVWOVgghRE5JDbmQKVWqFB4eHgAsWrSI5cuXs379ejw8PNi8ebNhn8xkLPdbQhR84eHh9OnTh5YtWzJ9+nTS0tIM73Xv3l3FyER+koRcyNSsWZONGzfi5+fH5s2bOXnyJEuWLGH69Ol89dVXxMfHZ9lfelQLUfD5+/vTunVrvv/+e+7evUurVq14+PAhALdu3VI5OpFfZNhTIZCRkcGWLVtITU2lS5cuzJs3D3Nzc6ytrUlNTcXS0hJPT0++++47UlJSKFmypNohCyFeQGRkJEOGDAHg+++/Z/ny5bi7u7N582a5qS5GJCEXAn5+fjx69IgyZcpw+fJlJkyYAOibo8ePH0/37t2ZNWsW7du3z7LkohCicEhLSyM5ORlzc3MA+vXrh729PR06dCAhIUHl6ER+MZ40adIktYMQzxYYGMihQ4fYvn07FStWZPv27VhZWXH27FmGDh3K1q1buXXrFo6OjkyZMkXtcIUQ/0Fqaio6nY6qVasatlWrVo2WLVty9uxZfH191QtO5BupIRdwpUuXpkmTJgBs27aNEydO4OLiws6dOzl06BA//fRTlv1lJi4hCp8RI0Zku71+/frs3Lkzn6MRapFOXQVcnTp1WLJkCX379mXOnDns2rWLcePGsWLFCu7fv09sbGyW/SUZC1H4bNiwgejoaED/PNnX15e6devSu3dvbt++rXJ0Ir9IDbmAc3Z2JiwsjMjISOzt7Q3bS5QoQWhoKGFhYdjY2KgYoRDiZY0bN46LFy8C+vnn3dzcmD59Ort27cLPz09qycWE1JALoEmTJvH1118bXmu1WipUqICDgwNt2rRh+fLl+Pr60qFDB1577TUVIxVC5IaMjAzD369du8aIESOoWLEiAwYMIDIyUsXIRH6ShFzALFiwgJ9++omLFy8yZMgQHjx4YHhv9OjRfPbZZ+zZs4dmzZoxc+ZMQCb/EKKwa926NRMmTCApKYnWrVsbVnDbu3dvlsVjRNEmU2cWMPPnz8fMzAwPDw/mz5/P9evXGT16NM2aNct2f51Oh5GR3FcJUZilpaUxbdo0AgICALh9+zZWVlZ06dKFmTNnUrlyZZUjFPlBEnIBlJCQgJWVFREREWzYsIHt27fz3nvv4ebmxpo1a3jvvfcwMzNTO0whRB6Ii4sjPT0dOzs7tUMR+Uw6dRUQN2/eJCoqikaNGmFlZQWAo6MjPj4+1KhRg4ULF+Lt7c3MmTMlGQtRBMXFxRESEkJERASg//+/Q4cO0mmzGJEacgHwxRdfcOTIEaytrTE2NmbhwoWULl06yz6tWrXilVdeYfHixSpFKYTIK0uXLuXLL7/E09MTR0dHQN9svXPnTiZOnCgTgxQTUkNW2Zo1awgJCWHz5s0YGxszefJkDh8+TKdOnQz7nDhxAmNjY0Mylsk/hChapk2bxsmTJ5+qDcfExNC0aVNJyMWE9AZSUXJyMqdOnWL69Ok4ODhQrlw5KleuzNKlS7Ps16hRI7Zt2wboO3FJMhaiaHnWTbaRkZGMoihGpIasInNzcwYNGoRWqzVs8/Ly4tChQwBERUURGBjIqFGjMDU1BZAe1UIUQePGjaNBgwZ4enpSqVIlAMLCwti5cydffPGFytGJ/CKlu0p0Oh0A1atXzzKhfOnSpXn06BGKojBo0CDDQuXGxsZqhCmEyAf9+/fnxIkTtGrVCjMzM8zMzGjdujUnTpxgwIABaocn8ol06ipg0tPT6dKlC9HR0bi4uDzVfC2EKNpiYmIwNjbG2tpa7VBEPpMacj47efIk8+bNIzg42LAwxJP3RCYmJrzyyisAWTpxCSGKrjt37uDr60upUqUoU6YMderUoXLlykyaNMnQSiaKPknI+SgiIgJfX1+ioqL4/PPP2bRpE/D0Ck0DBw5k5cqVaLVa6cQlRDHQr18//P39iYuLY926dfTs2ZNLly6Rnp7Ohx9+qHZ4Ip9Ik3U+atmyJd26dWPUqFFs2bKFjRs3UqdOHWrWrEmTJk2ws7Nj06ZNdOnSxdC7UpKxEEVfvXr1OHv2rOF1w4YNOXnyJAA1a9bk8uXLaoUm8pH0ss4nGRkZ+Pn54e/vD8DIkSNp164dsbGxhISEcO/ePerUqUNCQoKhJ7UkYyGKh7Jly7J8+XLatGlDcHCwoaOnoiiGDqCi6JMasgqSk5NZtGgRQ4cOBWDlypVs3bqVlStXqhyZEEINYWFhjBo1iosXL+Lq6sqsWbNwcHDg4cOH7Nu3j549e6odosgHkpALgF27djF79mw2btwo81QLIUQxJZ26VHb+/HlGjRrF2LFjMTMzkx7VQogsJk+erHYIIp9IDVlFMTExzJ07l7JlyzJ06FDpxCWEeErlypUJCwtTOwyRDyQh56Pk5GS0Wm2WWbcSExOxtLRUMSohhNqeNQmIoigkJSWRnp6ezxEJNUiTdT755Zdf8PHxeWq7JGMhhI2NDVevXuXRo0dZ/ouPj8fBwUHt8EQ+kWFP+eDixYtMnDiRdevWyZzUQoin+Pr6cuvWLcqXL//Ue3379lUhIqEGabLOY3FxcXTs2JEUgEHMAAAgAElEQVTRo0fj5eWldjhCCCEKKEnIeUin09G/f3+cnJykp6QQQojnkmfIeejbb7/l8ePHsp6pEOI/a9CggdohiHwiNeQXpSiQkgo6HRgZgZkpZDNUaffu3YwePZqQkBDKlSunQqBCCCFyJIflel6ThJwTaenwIBoePISkFP02jUb/IyqApRmUs4PytmBiws2bN+natSsBAQE0atRI1dCFEIXH/fv3iYiIAMDR0THbTl4il7xguZ4fJCE/j04H4fch4r7+taLof7An75wU5e/tQFp5Wzq/P4g+Pj74+fmpELQQorA5c+YMQ4YMIS4uDkdHRwBu376NjY0N8+fPl2br3PQfynUcy0Ol8vracx6ShPwsKakQeh2SkwFNjpovFEXh8ePHPHwcT5U3PdCYy7zUQoh/5+rqyk8//UTTpk2zbP/jjz947733sizNKF7CfyjXURRAAXNzqO2sb87OI9KpKzspqXD2T0h6gR8NSEpKIiU1lcrlyqM5d0V/HCGE+BcJCQlPJWMANzc3EhISVIioCPqP5bp+P43+c2f/zNNyXSYG+SedTn8HlZb+Qs0TqWmpPE5IwNbWFiNjY/3nQ6+Dq0ueN3MIIQq3jh070qlTJ3x9falUqRIA4eHhLF26lDfeeEPl6IqA/1iuG2Q2aedxuS5N1v906+7fzxZyeAeVodMR/fAh1tbWfy+fmNnMUdEeKsvUd0KI5/v111/ZtGlTlk5dXbt25c0331Q5siLgP5Tr2crjcl0S8pPS0uH4Bf3fn/OjDZ09g4PnTpOYnExZm9L079CZvp4dKVGiRNYdM/9pm9TJt156Qoii4d69e9jb26sdRuGXg3I9Nv4Rn3w3m99Pn8TW2prP+w/Cq5VH9sfLw3Jd2lKf9CBa/+e/3EF95O3DsUUruLJmMz+M+IzvflnF9Xt3nt4x8zj3o3M5UCFEUSc141ySg3J97I/fY6rVcm7ZOv43aiyfLZjHn7duZr9zHpbrkpCf9ODh33c/z+FSpSqmWi1JycmkpaVhYmzCrbvZJGTQH+/Bw1wOVAhR1EnjZS75l3I9MTmJ7YcP8unbA7CysKDJq3XxbNKM9Xt3PvuYeVSuSztqJkXRDw7P4fOFT/83lzW7QkhLT6dOtVdo2+jpHpKA/nhJKVnHtAkhxL8YPHiw2iEUfjko129ERGBsbEQ1x4qGba9WrcYfoeeefdw8KtclIWfK7Mqe04Tcux8TBgzi4q2/OHz+LKbaZ/xTZs78kpIKMi5ZCJGNhg0b8vrrr9OxY0dat26Nubk5H3zwgdphFX45KNcTkpMoaWmVZZu1lRWPk5Kefdw8KtelyTqTTvdCdzo2NjaUsCpBk1frcjcqiqW/bn32zpr/P74QQmTj6NGjeHl5sW/fPlq1asWbb77JvHnzuHLlitqhFW45KNetzC2IT8w61js+MZESFhbPP3YelOtSQ85kZPRCzQ8mT/SuS8/I4OazniGDfl5UGYsshHgGExMTWrduTevWrQG4c+cOISEhjB8/nmvXruHm5sb8+fPVDbIwykG5Xs3RkYwMHX/dicCpgn7a0ot/3aBGpSrPP3YelOuSJTJlTof2Lx0pomJj2LR/LwlJSWRkZLDv1HE27t9Ly3r1s/9A5vHycLo1IUTRUqFCBfz9/Vm7di0nTpzg7bffVjukwikH5bqluQUdm7Xg6xWBJCYncfziBXYcO4x3m/bPPm4elesyDvlJpy9BYvJz73oexsUyeOZkLv51A52io2LZ8gzs0p23O3TK/gM6HViaQ/1aZGRk8PjxY+Li4rC2tsbGxiaPTkQIUZhkZGSwaNEibt++zRtvvEGLFi0M702dOpXx48erGF0hl4NyPTb+ESPmfcP+M6cobW3NuOeNQ4Ys5XpukoT8pIgHcOtO7vaGVhTmb9/IqDlfY2xsjJmZGenp6XTv3p3AwMDc+x4hRKE1aNAgEhMTadKkCcuWLaNVq1bMmTMHgAYNGnDq1CmVIyzE8qhcp0oFcMzdte6lyfpJ5W31f+bWPcr/H+f1Hl0xNTUlKSmJx48fA+Dt7Z073yGEKPSOHTvGypUrGT58OEePHuXx48f06NGDlJQUGY/8svKoXDccNxdJQn6SiYl+3UuUl//xDHOelue1Bg3YsmULtra2aLVadDodY8eOZcaMGdy585zOYEKIYiE19e8VhExMTFi4cCGurq54eHgYbuLFf5RH5XpeTIcsCfmfKpXXr3uZGz+cubn+hwNatmzJN998g6IoTJs2jU2bNpGYmEi7du0YPHgwhw8fljthIYqpRo0aERISkmXbhAkT8PPz4+bNm+oEVZTkUbme2+QZcnYy181MS/972a2cUv7/LkxrAvVcnuqFt3nzZtq0aUPJkiUBePz4MevXr2fJkiWYmJjg5+dHjx49sLS0zM0zEkKI4i0Py/XcIgn5WVJS9eteJr/AYtaZzRnm5lDb+YV+NEVROHToEIsXL+bYsWP06tWLAQMGUKXKv4yFE0IUCY8ePSIyMhJnZ+cs28+dO8drr72mUlRFTD6X6y9KEvLz6HRw+77+P/h7gPmTP2LmnVPmtorl9f+9xIDx8PBwgoKCWL16NQ0aNMDf3x93d3eMZHIRIYqktWvXMnz4cMqVK0daWhqBgYE0btwYkF7WuU6lcj0nJCHnRHq6fqmtBw/1E4qDftq0zH85CzMoZ6fvdZeLD/qTk5PZuHEjixcvJikpCT8/P3r16mVo7hZCFA2urq78+uuvODg4cOzYMXx9fZkxYwZeXl7Ur1+f06dPqx1i0aNSuf48kpBfVOaE4jqd/m7JzDTPV3FSFIXjx48TEBDA77//jpeXF35+flSvXj1Pv1cIkT/q1q3L+fPnDa/v3r1L586d6d+/P4GBgVJDzmsqlOvZkYRcyNy7d49ly5axfPlyatasib+/P+3atcPY2Fjt0IQQ/1Hz5s1ZtmxZlufH8fHxdO/enYMHD5KSkqJidCK/SEIupFJTU9m6dSsBAQFERkbSv39/+vbtK9NxClEInT17FktLy6davdLS0li7dq3MZV1MSEIuAs6cOcOSJUvYsWMHnTp1YuDAgbz66qtqhyWEEOIFSEIuQqKioli5ciVBQUFUqlQJf39/OnbsiFarVTs0IcRz2Nra0qNHD3x8fPDw8ECjwvNLoT5JyEVQeno6O3bsICAggBs3buDr60u/fv0oW7as2qEJIbLh4uLCRx99xKpVq7h58ybe3t74+Pjg5uamdmgiH0lCLuIuXbpEQEAAW7ZsoX379vj5+dGgQQO1wxJCPOHJscZhYWGsXr2a1atXExsbS58+fZg+fbrKEYr8IAm5mIiLi2PVqlUEBgZia2uLv78/XbvqV6ESQqjrWWONL1++zJo1a5g4caIKUYn8Jgm5mMnIyGDPnj0EBAQQGhrK22+/ja+vLw4ODmqHJkSx9cknnxjWPxbFlyTkYuz69essWbKEX375hZYtW+Lv70/Tpk2lQ4kQQqhAErIgPj6e9evXExAQgKmpKf7+/vTo0QMLCwu1QxOiWIiKiqJMmTKG18uXL+fYsWPUqVOHwYMHy01yMSEJWRgoisKBAwcICAjg+PHj9O7dm/79+8uKU0LksSc7dU2dOpUDBw7Qt29ftm7dSsWKFfn2229VjlDkB0nIIlthYWGGFacaNWpkWHFK7tSFyH1Pdupq0KABBw4cwMrKirS0NBo0aJBlnmtRdMl6fiJblStX5osvvuDEiRN06NCByZMn4+7uzpIlS4iPj1c7PCGKlKSkJE6fPs3JkyfJyMjAysoKAK1WK/PUFyNSQxY5oigKx44dIyAggP3799OjRw/8/f2fWkxdCPHi2rRpk+X1ypUrcXBw4OHDh3To0IETJ06oFJnIT5KQxQu7e/cuy5YtY8WKFdSqVYuBAwfi4eEhd/JC5LKMjAxSUlKwtLRUOxSRDyQhi/8sNTWVzZs3ExAQQHR0NP3798fHx0dWnBLiP7h37x4A9vb2REZGcuDAAVxcXKhdu7bKkYn8Is+QxX9mamqKt7c327dvZ8GCBVy8eBE3NzdGjRrFpUuX1A5PiELjp59+olmzZri5ubFgwQI6d+7Mtm3b6NGjB4sXL1Y7PJFPpIYsclVkZCQrVqxg6dKlVK1aFX9/fzp06CArTgnxHHXr1uXo0aMkJSVRpUoVrl27hr29PTExMbRp04YzZ86oHaLIB1JDFrmqbNmyDB8+nKNHj+Ln58fixYtxc3Nj3rx5REVFqR2eEAWSVqvF0tISOzs7nJ2dsbe3B6B06dIy1LAYkYQs8oRWq6VLly5s2LCBZcuWER4ezuuvv87HH38sd/tC/INGoyEtLQ2Abdu2GbYnJyej0+nUCkvkM2myFvkmNjaWlStXEhQURJkyZfD396dLly6y4pQo9sLCwnBwcHjq0U5ERASXLl2iXbt2KkUm8pMkZJHvMjIy2L17N4sXL+by5cuGFacym+mEEKI4kiZrke+MjY3x9PRkzZo1rF+/nri4ONq0acOQIUM4evQoOblHjIyMpG3btgwbNozo6Oh8iFqIvBMeHk6fPn1o2bIl06dPNzRfA3Tv3l3FyER+koQsVFW9enWmTZvGsWPHaNKkCSNHjqR9+/asXLmSpKSkZ34uJSWFzz//nKVLlxISEpKPEQuR+/z9/WndujXff/89d+/epVWrVjx8+BCAW7duqRydyC/SZC0KFJ1Ox/79+1myZAknT55k8uTJdO/eHSOjp+8dQ0ND8fX15fDhw5iZmaEoivRIFYWSq6trls6Oy5cvZ8aMGWzevJm33nrLsBKUKNpM1A5AiCcZGRnRunVrWrduzc2bNzE3N882GYN+MgV3d3fMzMzIyMh4aupOSdCisEhLSyM5ORlzc3MA+vXrh729PR06dCAhIUHl6ER+kSZrUWBVrVr1mR297ty5w/79+xkyZAhAtok3ISGBn3/+mbZt2xIZGZmnsQrxMgYNGsTRo0ezbGvXrh3r1q2jTp06KkUl8ps0WYtCae7cuezdu5dNmzZlqQln/v3IkSNs2bKFbdu2Ua1aNWbPnk21atVUjloIIZ5NasiiUPnpp584cOAA27dvZ9y4cYB+GFV6ejoAMTEx7Nixgy+++IK2bdvSsGFDevToQbly5QA4c+YMs2fPZtiwYbLouygUtm7dqnYIIp9IQhaFhqIopKam4ufnx65du7h58yYAJiYmmJjou0N8/PHH/PHHH+zatYuqVauSnp6Oi4sLJUqU4Pz58/Tv359y5cphbW1N165d2b17t4pnJMS/O378uNohiHwiTdaiUPrll184ePAgr7/+OjY2NrRo0QJjY2MGDRrE/v376d69OwkJCbi6uvLBBx8QHh7O/PnzAZgxYwYASUlJKIqCpaUlly9f5tChQ3h7e1OqVCk1T00UU5cvX2bTpk1EREQA4OjoSNeuXalVq5bKkYn8IjVkUahkzuvbs2dPvv32W9q2bcvjx48JDw9Hq9USFBTE6dOniYuLY9myZaxbt4779+9z+vRptm7dyp9//kmPHj3Ys2cPFhYWWFpa8u233/Lhhx/y+++/07p1a5YvX67yWYri5quvvqJPnz4oikKTJk1o0qQJiqLg4+PDzJkz1Q5P5BOpIYtCKbshTYqikJ6ejlarZe7cuTx48IC6devSqlUrFi9ezMGDB9mxYwdBQUHs2bOHoKAgAOrXr8+cOXNo06YNa9as4ebNm4wZM0aGTYl8U6NGDUJDQ5+ayzo1NZXatWtz9epVlSIT+UlqyKJQyi5RajQatFotqamppKWlUb9+fXx8fKhQoQJ79uzh008/BfRrzyYnJ3Pz5k2uXr1KYmIibdq0AcDJyYnw8HBiY2PRaDTs3buXMWPGMH78eBk6JfKMkZERd+7ceWr73bt3nzkOXxQ9MjGIKHJMTU0ZPXq0YT7gtLQ0mjdvTnJyMgAnT57E2toa0E/d2b59e0aOHMkbb7zBnDlzqFy5MjY2Nqxbt46pU6cybdo0tm/fTps2bdi8ebMMnxK5bu7cubRt25bq1atTqVIlQL8C1LVr1/jhhx9Ujk7kF2myFsXCoUOH+PDDD7GyssLZ2ZnevXvTqVMnQL/E3XfffUeJEiVYunQpK1asIDExkQ0bNtCmTRvD5P4RERE4Ojpy5coVRowYQe/evfH19VXztEQRotPpOHbsWJZOXY0bN35qBjpRdElCFsXKhQsXKFu2LOXLl+f06dMoikKDBg0AWLRoEVu2bGHTpk188sknXLx4ERMTE0qUKMHMmTOpWrWq4Thbt25l/fr1nDp1it69ezNs2DBKlCih0lkJIYoCeTghioXM3tl16tQxTBISERHBe++9xxtvvMFbb73F5cuXmTZtGvfv3ycyMpLGjRuzdetWatWqxfr167Mcr3PnzgQGBuLi4sKmTZu4ePFivp+TKLoSExNJTU1VOwyRz+QZsigWnuwYk9khrHPnznTu3JnVq1djY2ND27Zt0Wq1xMXFkZqayjvvvANAmTJl+P333wEMi1g8fvyYLVu2cO3aNdavX4+zszOKorBu3Tp27dpF7dq1+eijj6RDjvhPFi9ezKuvvkrbtm3VDkXkI0nIotjS6XQYGRnRp0+fp7ZnZGQYXh86dIhWrVqRlJSEhYUFAD///DOnTp1i+PDhODs7Ex4ezs8//8y5c+fw9/cnKCjIME2nra2tDKESL+TGjRuULVtW7TBEPpOELIqtzNrrP5OljY0N3bp144033qBmzZrY2dnRq1cvLCwsUBSFEydOMHfuXIKCgmjZsiUACxYsICYmhvnz51OhQgW6du3KjRs3sLW1BfS18hMnTtCoUaP8P1EhRKEgnbqEeI5Lly5RuXJlrKysAFi/fj07duzAycmJzz//HNBP3tC0aVNcXV158OABzs7OzJgxA0tLS0OiX7VqFQsWLGD//v2qnYsoPEaMGEHTpk2far0RRZs84BIiG5mdwGrVqmVIxgCffvopzZo1Y/jw4YZtmzZtws7ODm9vb1atWkVycjInT540JOPNmzdz+vRppkyZApClOTxzbLQQQkhCFiIbz+qMdf78efz9/bG0tDRs0+l0eHp60rZtW6ytrVEUhdWrVwNw9OhR1q9fj5eXF61atQLIMq7066+/pkWLFuzatSsPz0YIURhIQhYih3Q6HVZWVvzzKU+9evU4duwYKSkpKIrCrl27GDBgAADz5s2jRYsWNGvWDMAwexhAeno6HTp0oFKlSsybN4+YmJh8OxchRMEjnbqEyKHMWvOTHcAURaFixYq4uLjQoEED6tevj5eXF40aNWLevHlUrVqV9957j9jYWGxsbAyLByiKgomJCQ4ODjRo0AAjIyNKly6tynkJIQoGqSEL8RI0Gg0lSpRg2rRphIaGMmvWLObMmcOUKVOIj49nyJAhACxduhRXV1eWLFli+BxAaGgoV69eNYw3lT6WQhRfUkMWIhfodDrMzc1xcnLi6tWrBAcHs2/fPkOt9+OPP8bV1ZWrV6/y6NEjrK2tefjwIRcuXKBMmTLUr18feHoVq8yJSB48eMDBgwfx8PDAxsYm389PCJH3pIYsRC54shNY9erVWbFiBaVLl0an0xlqve7u7gwcOJCSJUsC+skfrl+/TosWLYC/e3Y/ydjYmEuXLjFp0iS8vb0NazgLIYoeqSELkQfq1KkDZE3UmbXdGzdusG7dOkqVKoWdnR2dO3fOsm/mDGJxcXEEBwdz/PhxateuTcOGDfHz8wMgNjaWhQsXUqVKFXr37p3PZyeEyAtSQxYin2QOd0pNTWXbtm2MGzeOLVu2EB8fn2U/IyMjMjIy+OCDD1AUhenTpxMWFkbjxo2xtrYmNDSUcePG8ddff7FmzRoaNmzI5cuX1TglIUQukoQsRD6rVasWBw4c4MKFCzRv3py1a9cCEB4ebthn3bp1rFq1isqVK1OqVCk2btzIqFGjAH0NOjY2lgkTJhAcHIy7uztbtmwB9MtLHjhwIP9PSgjx0iQhC5HPFEVBp9NRoUIFfvzxRwYOHAjo58PeuXMnAH369GHlypV88803ODo6kpCQQLVq1dDpdFhbWxMeHs6XX37J6dOnDatNgT6pDxs2jBYtWrBx40bVzlEI8eJkLmshVJL5v96TPatTU1MxNTXNsl+dOnWwsLDgm2++ISwsjLNnz+Lo6MilS5c4ceIE06ZNo2PHjlk+s3//fv73v//x3XffUb58+bw/GZGrZC7r4klqyEKoRKPRGJJxZnL+ZzLevXs3CQkJHD9+HDc3N1avXk3r1q0ZMWIECxcupHTp0piZmRn2P3fuHAC1a9fmt99+M7wXHBzMBx98wI4dO/Lj1IQQ/4EkZCEKgOzWSlYUhbZt2/Lrr78C+s5edevW5e7duwDExMSQkZFhqAFnZGSwYcMGjIyMGDJkCB9++CE2NjYsWLCASZMm0bhxY2bMmIGfn59MQCJEASQJWYgCKjNJ16xZEwCtVsurr77K999/z5AhQ3j//fepWLEiTk5OgL4X98SJE9m/fz/ly5dn4sSJAFy8eJEBAwbg5+fHnDlzMDY2Ji4ujhs3bjBp0iSuXr2qzgkKIbKQcchCFCK+vr50796dhQsX4uTkhKenJ3FxcWRkZBgmHImPjycyMhKtVktkZCQ1a9ZkypQpJCQkEB0djbm5OdHR0Tg5OWFkZISvry8VKlRg0KBBdOzYEUVRsq2xCyHyltSQhShEMntZjxo1ip49e1KyZEnOnDmDu7s706dP5/79+8yePZvGjRtz48YNJk6cSFRUFBs3bmT//v0oisI333xDtWrV0Gg0TJgwgSNHjmBjY4OPjw/79+9Ho9GQmpqq9qkKUexIQhaiEMmczevJZ8AdO3Zk+fLl3L59G19fX5o3b87QoUNJTk5m7969DB8+HDc3Nz766CMURTFMPJJ5jMOHD3P//n2+//573N3duX//Ps7OzgwePJgLFy6ocp5CFEfSZC1EIfTPJSBr167N/PnzycjIAPTPk2NiYqhQoQKlSpUC9EOqwsLCMDExMST206dPM3HiRNq0acM777wDwIYNG6hRowb16tVj8ODBeHp6MmnSJGnGFiKPSUIWopDTaDQoioKiKIbpOQHq1auHs7Mzr732GjVr1sTKyoru3bsbkvHVq1eZMmUKzZo1Y+zYsQAkJSWxZMkS5syZQ4sWLRg6dCg3b940fIckZSHyjiRkIYqAJ8c0ZypRogQLFy7kr7/+IiQkBC8vL8qUKQPA/fv3GTt2LI6OjkyYMAGNRoNOpyM8PJzbt28zffp03n33Xbp160bVqlUN3yGEyDvyDFmIIiqz1uzk5MT777+Pvb09JiYmxMbGMmLECKysrJg+fTomJvr7ciMjI2rUqEFERATvvfcea9euJTIyUuWzEKL4kIQsRBGVXa0ZwMbGhokTJ/Lll18ahkrpdDpSUlIM+3Tt2pVLly5x5MiRfItXiOJOErIQxZCLi4uhKRogIiKCmTNnGqbWvHTpEiVLljRMSiKEyHvyDFkIQaVKlahRowYzZszgiy++wMHBgddff50aNWpk2U+n0xk6hQkhcpckZCEEAD4+Pvj4+HDq1ClsbGyy1KAzJSUlMXr0aPr160ezZs2ko5cQuUgSshAC+Lv226BBg2fuo9Vqady4MZ999hlarRY/Pz969OiBpaVlPkYqRNEkbU9CCIAcNUWbmpri5+fH77//zqRJk9i9ezeNGzfmyy+/5ObNm3kfpBBFmCRkIcQL02g0tGzZkiVLlhASEoKxsTGdO3fG19eXffv2odPp1A5RiEJHErIQ4qVUqlSJ8ePHc/z4cTp27MjUqVNxd3dn8eLFxMfHqx2eEIWGJGQhRK6wsLDAx8eHnTt3Mnv2bI4fP06TJk34/PPPZc1lIXJAErIQIldpNBqaNm3Kjz/+yN69e7GxscHb25vevXuzY8cOwwIYQoisJCELIfKMvb09n376KcePH6dXr158//33NG/enPnz5xMTE6N2eEIUKJKQhRB5ztTUlJ49e7J161Z++uknLl++TLNmzRg5ciShoaFqhydEgSAJWQiRr1xdXfnuu+84ePAglStX5p133qF79+5s3ryZtLQ0tcMTQjWSkIUQqihTpgzDhg3j6NGjDBo0iMDAQJo0acK3334rq0yJYkkSshBCVVqtls6dOxMcHMyKFSu4c+cOLVu25KOPPuLUqVNqhydEvpGELIQoMF599VVmzZrFH3/8wauvvsr777/Pm2++ybp160hNTVU7PCHylCRkIUSBY2Njw/vvv8/hw4cZMWIEwcHBNGrUiK+++oq7d++qHZ4QeUISshCiwDI2NqZ9+/asWrWK4OBgHj16hIeHB++++y5//PEHiqKoHaIQuUYSshCiUHjllVeYNm0ax44do1mzZowePZp27dqxYsUKkpKS1A5PiJcmCVkIUaiULFnSsOLUxIkT+e2332jUqBGTJ0/m1q1baocnxH8mCVkIUSgZGRnh7u5OUFAQ27dvB+DNN9+kf//+/P7779KcLQodSchCiEKvSpUqTJgwgRMnTuDp6cnkyZNxd3dnyZIlsuKUKDQkIQshigwLCwvefvttdu3axaxZszhy5AhNmjRh3LhxXLt2Te3whHguSchCiCJHo9Hg5ubGwoUL2bNnD9bW1vTo0YM+ffqwc+dOWXFKFEiSkIUQRZqDgwNjxozh+PHjeHt78+2339KiRQsWLFhAbGys2uEJYaBRpOeDEKKYOXXqFEuWLGHnzp107tyZgQMHUqtWLbXDYs6cOUyePJmkpCSMjY0xNzdny5YttGjRQu3QRD6QhCyEKLYiIyNZvnw5S5cuxcnJCX9/fzp06IBWq1UlntDQUFq3bk1iYiLGxsbY2tpy6dIlLCwsVIlH5C9pshZCFFtly5ZlxIgRHDt2jAEDBrB48WLc3NyYN28eUVFR+R5P7dq18fDwMDzj/vTTTyUZFyNSQxZCiCeEhoYSEBDAtm3b8PT0xN/fH1dX13z9/kaNGjiC7W0AAAaKSURBVFGiRAnCwsIkIRcjkpCFECIbsbGxrFy5kqCgIMqUKYO/vz9dunTB1NQ0z7+7YcOGtGrVijlz5uT5d4mCQxKyKBwUBVJSQacDIyMwMwWNRu2oRDGQkZHB7t27Wbx4MZcvX+btt9/G19cXe3v7vPlCRUFJTkGjKHKtFzOSkEXBlZYOD6LhwUNIStFv02j0yVkBLM2gnB2UtwUTE1VDFcXD1atXCQwMJDg4mFatWuHn50eTJk3QvGzClGtdIAlZFEQ6HYTfh4j7+teKoi+cniz0FOXv7QCO5aFSeX2NQog89ujRI9atW0dAQAAWFhYMHDiQ7t27v/jzXrnWxRMkIYuCJSUVQq9DcjKgyVlTnaIACpibQ+3/a+/+Q6Ou4ziOv+52232/7mDi6aZzLrFAQsGIGkUaiWA/SegwhobhVhEV+IdQZAiJEOV/Qn/sn7wd5B8SmEX1R0HRGhrIRFErQ8v5YzWxWav9uO32/fbHt9Mp90s3vPeu5wOO2427N/fHm8/rvp/v9/P53hlM8QG3ged56urqUjKZVE9Pj1pbW7Vp0yY1NzcX/zC9jhsQyLAjPSYdOxVM3914lFBM9iiiOiKtWMpAhdvu7NmzSqVS2rdvn1paWtTe3q6VK1fmns6m15EDgQwbPE86ekoaGZ3aVJznSa4j3bOUKT2UxfDwsPbv3689e/Yok8lo8+bNWr9+vWKxWPAGeh15EMiwofe3a+fRpnKBTHZKr2m+1LxgWr4acCt839ehQ4eUTCbV3d2tRCKhtrY2Laly6XXkRCCj/MYz0uETwd9FBqhf+y5q9Wsv6KmHHtb7W9/M/aZsS7cs54pUmNDX16dUKqXPPj6gL3bskuO6qolGlavbE9u2quenHxSpCnp3fjyu7o7O3IXp9YpCIKP8Ll6SevtKOlpo3f6GRsfSaqpvyB/IUjBQ3dEoLayfxi8KTM14b58mzpzT0PCwPN/XLNeV67oKT5pyTmzbqsQja7Rh7ROlFaXXKwYnHlB+l/649ku/gE+6vlFdLKZVK+4tXtP3g7qAIdUDf8mJRjUnHlddXZ3GMxldvnxZg4ODGs9kbq0ovV4xCGSUl+8HGyEUOTr+e2hIu/Z26u32l0urGwoFdZkAghWTej0kqaa6WrPr6hSfO1fhcFh/XrmigYEBTUxM6J3UB1q28Rk9/foWHTx+tHBder1icNIB5ZUeC56LBPKuvZ3asPZxLZg7r7S62V2O0mOSE53adwSmQ55erwqHFYvFVFtbq3Q6rS2JVi2e36j6efP0+cEuPb9zu77a3aHFCxbmrkuvVwyOkFFenlc0jE/+clrfHTuil9Ylbq526L/6gAVFej0UCslxHK1ueUCLGhvlOo6eXfOo7r97mb7uOVy4Nr1eEThCRnmFw9dvC5jDwePHdL6/X/e1bZQkDY2MaMKb0M/nevXl7o78tX2xPhN2lNDrWZFJV0yHQiEVvfaWXq8IBDLKK7vLUIGB6rnHntS6Vauvvu448JHO9/+ud1/Zkr9udgBjFyNYUUKvDw79oyOnftSDy1eoKhzWp93f6vsTx7XzxVfz16XXKwaBjPIKhSQ3Kg2P5h2k3KgjN+pcfV3ruIrW1CheNzt/Xd+XZjnctg52lNDr45mM3vuwU6cvnFNVuEp3NS1S8q0dWrKwKX9der1isA4Z5XcT65BLxtpMWESvowBOOqD8GuYEz9P12zBbJ1sXsIJeRwEEMsovEgnu8Sp/6gPV1f19G9hKEPbQ6yiAQIYNixqCe7xOxyDlOMEgBVhEryMPAhk2hMPBDderI8F6ypsdrHw/+Fx1JKjDEhBYRa8jDy7qgi3pMenkGWl0VFKJN27PTt05TjBAsfwDMwG9jhsQyLDH86QL/cFDurZuc/KA5fvXr+dsaggeHC1gJqHXMQmBDLsyGal/ILiTzUg6+F9Iwa5EUrCmsz4eXGHKRS2Yyeh1iEDGTJHdPN/zgiODaA0bIaAy0ev/WwQyAAAGcBICAAADCGQAAAwgkAEAMIBABgDAAAIZAAADCGQAAAwgkAEAMIBABgDAAAIZAAADCGQAAAwgkAEAMIBABgDAAAIZAAADCGQAAAwgkAEAMIBABgDAAAIZAAADCGQAAAwgkAEAMIBABgDAAAIZAAADCGQAAAwgkAEAMIBABgDAAAIZAAADCGQAAAwgkAEAMIBABgDAAAIZAAADCGQAAAwgkAEAMIBABgDAAAIZAAADCGQAAAwgkAEAMOBfkf64VI4toOsAAAAASUVORK5CYII=\n",
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# Check if arbitrage cycle exists using Bellman-Ford. If so, output an arbitrage cycle"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Finding an \"Optimal\" Set of Cycles "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Identifying the cycle with an arbitrary number of vertices with the **largest** arbitrage multiplier is NP-hard in general. Finding this cycle with many tradable pairs thus quickly becomes computationally infeasible and one has to resort to approximate/heuristic algorithms.\n",
"\n",
"Observe that finding the cycle with the largest multiplier (i.e. the cycle with the most negative cycle length in the graph with negative-log-transformed weights) of all cycles that visit each vertex exactly once is equivalent to the (asymmetric) [Travelling Salesman Problem](https://en.wikipedia.org/wiki/Travelling_salesman_problem) - a well known NP-hard problem. The Travelling Salesman Problem (TSP) with $n+1$ cities can be formulated as an integer linear program for a distance matrix $C$ as follows\n",
"\\begin{align}\n",
"\\min &\\sum_{i=0}^n \\sum_{j\\ne i,j=0}^nc_{ij}x_{ij} && \\\\\n",
" & 0 \\le x_{ij} \\le 1 && i,j=0, \\cdots, n \\\\\n",
" & u_{i} \\in \\mathbf{Z} && i=0, \\cdots, n \\\\\n",
" & \\sum_{i=0,i\\ne j}^n x_{ij} = 1 && j=0, \\cdots, n \\\\\n",
" & \\sum_{j=0,j\\ne i}^n x_{ij} = 1 && i=0, \\cdots, n \\\\\n",
"&u_i-u_j +nx_{ij} \\le n-1 && 1 \\le i \\ne j \\le n\n",
"\\end{align}\n",
"\n",
"\n",
"\n",
"The TSP is only **NP-hard because we are asking for a single roundtrip solution** that covers all cities / currencies (the last two sets of constraints in the above formulation). But **subtours are fine in the arbitrage finding task** and even skipping some assets completely (a self-cylce) is not a problem! "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"If we remove the \"no-subtours\" constaints of the TSP and also account for the diagonal of $X$ in the objective function, we arrive at the linear programming relaxation of the [assignment problem](https://en.wikipedia.org/wiki/Assignment_problem) \n",
"\\begin{align}\n",
"\\min &\\sum_{i=0}^n \\sum_{j=0}^nc_{ij}x_{ij} && \\\\\n",
" & 0 \\le x_{ij} \\le 1 && i,j=0, \\cdots, n \\\\\n",
" & \\sum_{i=0}^n x_{ij} = 1 && j=0, \\cdots, n \\\\\n",
" & \\sum_{j=0}^n x_{ij} = 1 && i=0, \\cdots, n \\\\\n",
"\\end{align}\n",
"This linear program always has an integer solution (due to the totally unimodular linear constraint matrix) and thus solves the assignment problem. You can use a very specialized solver for the assignment problem (this notebook uses [this one](https://developers.google.com/optimization/assignment/simple_assignment) - extremely fast and exact solutions!) or just solve the linear program above - [CVXPY](https://www.cvxpy.org/) makes this very easy. "
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"code_folding": [
0
]
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"status: optimal\n",
"optimal value -5.965679824113291\n"
]
},
{
"data": {
"text/html": [
"\n",
"\n",
"
\n",
" \n",
" \n",
" 0 \n",
" 1 \n",
" 2 \n",
" 3 \n",
" 4 \n",
" 5 \n",
" \n",
" \n",
" \n",
" \n",
" 0 \n",
" 1.0 \n",
" -0.0 \n",
" 0.0 \n",
" -0.0 \n",
" 0.0 \n",
" 0.0 \n",
" \n",
" \n",
" 1 \n",
" -0.0 \n",
" -0.0 \n",
" -0.0 \n",
" 0.0 \n",
" 0.0 \n",
" 1.0 \n",
" \n",
" \n",
" 2 \n",
" 0.0 \n",
" 1.0 \n",
" -0.0 \n",
" -0.0 \n",
" -0.0 \n",
" -0.0 \n",
" \n",
" \n",
" 3 \n",
" -0.0 \n",
" 0.0 \n",
" 1.0 \n",
" -0.0 \n",
" 0.0 \n",
" 0.0 \n",
" \n",
" \n",
" 4 \n",
" 0.0 \n",
" 0.0 \n",
" -0.0 \n",
" 1.0 \n",
" -0.0 \n",
" -0.0 \n",
" \n",
" \n",
" 5 \n",
" 0.0 \n",
" 0.0 \n",
" 0.0 \n",
" 0.0 \n",
" 1.0 \n",
" -0.0 \n",
" \n",
" \n",
"
\n",
"
"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# Find best set of arbitrage cycles by solving the assignment problem"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Beyond Arbitrage Cycles - Maximize wrt. Quantities (EXPERIMENTAL!)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Assume that we start out with one quantity in each currency. Let us find the set of trades that maximize the quantity in currency $k$ without changing the other quantities. For two matrices $A$ and $B$ of the same dimensions, let $A\\circ B$ denote the element-wise product (also denoted [Hadamard product](https://en.wikipedia.org/wiki/Hadamard_product_(matrices))). \n",
"\n",
"Let $C$ denote the exchange rate matrix (not log-transformed) and $Q$ a matrix of the same size as $C$ where the entry $Q_{i,j}$ denotes the number of $i$ coins that flow from currency $i$ to currency $j$. Let $\\mathbb{1}$ denote a vector of ones of size $N\\times 1$, then vector of outflows from the respective currency inventories is\n",
"\n",
"\\begin{align}\n",
"\\text{outflows} = Q \\mathbb{1}.\n",
"\\end{align}\n",
"The vector of inflows (also in currency $i$ units) is\n",
"\n",
"\\begin{align}\n",
"\\text{inflows} = (Q \\circ C)' \\mathbb{1}\n",
"\\end{align}\n",
"and hence the delta inventory is\n",
"\n",
"\\begin{align}\n",
"\\Delta\\! I = (Q \\circ C)' \\mathbb{1} - Q \\mathbb{1}.\n",
"\\end{align}\n",
"\n",
"Let $I_{init}$ denote the initial inventory the maximizre \n",
"\n",
"\\begin{align}\n",
"\\max_{Q} \\Delta\\! I_k && \\\\\n",
" & \\Delta\\! I_{\\neq k} =0 && \\text{| No change in inventory in other assets}\\\\\n",
" & \\Delta\\! I_k \\leq 1000 && \\text{| Problem would be unbounded in case of arb-cycle}\\\\ \\\\\n",
"\\end{align}\n",
"\n",
"The nice thing about this setup is that it allows to easily incorperate new constraints like the blocksize of the observed quotes. The drawback is that this is numerically extremely challenging!"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"code_folding": []
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"
\n",
" \n",
" \n",
" target \n",
" \n",
" \n",
" 0 \n",
" 1 \n",
" 2 \n",
" 3 \n",
" 4 \n",
" 5 \n",
" \n",
" \n",
" \n",
" \n",
" source \n",
" 0 \n",
" 1.00 \n",
" 0.58 \n",
" 0.63 \n",
" 0.27 \n",
" 0.17 \n",
" 0.20 \n",
" \n",
" \n",
" 1 \n",
" 1.68 \n",
" 1.00 \n",
" 0.39 \n",
" 0.74 \n",
" 0.47 \n",
" 0.79 \n",
" \n",
" \n",
" 2 \n",
" 1.57 \n",
" 2.48 \n",
" 1.00 \n",
" 0.04 \n",
" 0.15 \n",
" 0.11 \n",
" \n",
" \n",
" 3 \n",
" 3.64 \n",
" 1.35 \n",
" 22.94 \n",
" 1.00 \n",
" 0.22 \n",
" 0.23 \n",
" \n",
" \n",
" 4 \n",
" 5.84 \n",
" 2.02 \n",
" 6.84 \n",
" 4.40 \n",
" 1.00 \n",
" 0.49 \n",
" \n",
" \n",
" 5 \n",
" 4.76 \n",
" 1.21 \n",
" 8.59 \n",
" 4.41 \n",
" 1.97 \n",
" 1.00 \n",
" \n",
" \n",
"
\n",
"
\n",
"\n",
"
\n",
" \n",
" \n",
" inventory_start \n",
" \n",
" \n",
" currency \n",
" \n",
" \n",
" \n",
" \n",
" 0 \n",
" 1.0 \n",
" \n",
" \n",
" 1 \n",
" 1.0 \n",
" \n",
" \n",
" 2 \n",
" 1.0 \n",
" \n",
" \n",
" 3 \n",
" 1.0 \n",
" \n",
" \n",
" 4 \n",
" 1.0 \n",
" \n",
" \n",
" 5 \n",
" 1.0 \n",
" \n",
" \n",
"
\n",
"
\n",
"\n",
"
\n",
" \n",
" \n",
" target \n",
" \n",
" \n",
" 0 \n",
" 1 \n",
" 2 \n",
" 3 \n",
" 4 \n",
" 5 \n",
" \n",
" \n",
" \n",
" \n",
" source \n",
" 0 \n",
" 0 \n",
" 0.55526 \n",
" 1.18114 \n",
" 1.05574 \n",
" 0.823924 \n",
" 0.642941 \n",
" \n",
" \n",
" 1 \n",
" 33.4973 \n",
" 0 \n",
" 1.31654 \n",
" 0.516985 \n",
" 13.0599 \n",
" 95.599 \n",
" \n",
" \n",
" 2 \n",
" 70.3751 \n",
" 47.2097 \n",
" 0 \n",
" 0.352497 \n",
" 12.2592 \n",
" 12.3467 \n",
" \n",
" \n",
" 3 \n",
" 82.1541 \n",
" 17.0369 \n",
" 5.91057 \n",
" 0 \n",
" 0.519886 \n",
" 0.254038 \n",
" \n",
" \n",
" 4 \n",
" 70.0033 \n",
" 0.260328 \n",
" 0.330315 \n",
" 17.5992 \n",
" 0 \n",
" 1.1418 \n",
" \n",
" \n",
" 5 \n",
" 27.2338 \n",
" 2.53042 \n",
" 0.400214 \n",
" 6.29415 \n",
" 41.1693 \n",
" 0 \n",
" \n",
" \n",
"
\n",
"
\n",
"\n",
"
\n",
" \n",
" \n",
" inventory_start \n",
" inventory_delta \n",
" inventory_after_trades \n",
" \n",
" \n",
" currency \n",
" \n",
" \n",
" \n",
" \n",
" 0 \n",
" 1.0 \n",
" 9.999983e+02 \n",
" 1000.998327 \n",
" \n",
" \n",
" 1 \n",
" 1.0 \n",
" 8.605809e-09 \n",
" 1.000000 \n",
" \n",
" \n",
" 2 \n",
" 1.0 \n",
" 1.377347e-06 \n",
" 1.000001 \n",
" \n",
" \n",
" 3 \n",
" 1.0 \n",
" 7.083011e-08 \n",
" 1.000000 \n",
" \n",
" \n",
" 4 \n",
" 1.0 \n",
" -1.618656e-07 \n",
" 1.000000 \n",
" \n",
" \n",
" 5 \n",
" 1.0 \n",
" -1.211123e-07 \n",
" 1.000000 \n",
" \n",
" \n",
"
\n",
"
"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# Maximize inventory"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Live Arbitrage Identification"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In this part, we are looking for live arbitrage opportunities on some centralized exchanges. The main tool we use for this is [CCXT](https://github.com/ccxt/ccxt) - an open source JavaScript / Python / PHP cryptocurrency trading library with support for more than 130 crypto exchanges.\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The Binance fee structure can be found [here](https://www.binance.com/en/fee/schedule)."
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {
"code_folding": []
},
"outputs": [],
"source": [
"# set some parameters"
]
},
{
"cell_type": "code",
"execution_count": 54,
"metadata": {
"code_folding": []
},
"outputs": [
{
"data": {
"application/javascript": [
"IPython.notebook.execute_cells_below()"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"application/vnd.jupyter.widget-view+json": {
"model_id": "bbff30b178634ef39a4e2a0f8938804a",
"version_major": 2,
"version_minor": 0
},
"text/plain": [
"Button(description='Find Arbitrage Cycles', style=ButtonStyle())"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# set things up and create button"
]
},
{
"cell_type": "code",
"execution_count": 55,
"metadata": {
"code_folding": []
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Updating all quotes (496 pairs overall) took 0.9450349807739258 seconds.\n"
]
}
],
"source": [
"# create real time exchange rate matrix"
]
},
{
"cell_type": "code",
"execution_count": 56,
"metadata": {
"code_folding": [],
"scrolled": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Bellmann-Ford took 0.22376108169555664 seconds.\n",
"At least one arbitrage cycle exists! One such cycle is ['BTC', 'CDT', 'ETH', 'BTC'] with cycle length -0.000546627229625 which implies and arbitrage multiplier of 1.0005467766575147.\n"
]
},
{
"data": {
"text/html": [
"\n",
"\n",
"
\n",
" \n",
" \n",
" Node \n",
" 0 \n",
" 1 \n",
" 2 \n",
" \n",
" \n",
" \n",
" \n",
" Ticker \n",
" BTC \n",
" CDT \n",
" ETH \n",
" \n",
" \n",
"
\n",
"
"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# Check if arbitrage cycle exists using Bellman-Ford. If so, output an arbitrage cycle"
]
},
{
"cell_type": "code",
"execution_count": 57,
"metadata": {
"code_folding": []
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Solving assignment problem took 0.053289175033569336 seconds.\n",
"\n",
" Assignment problem multiplier is 1.0006195840057635.\n"
]
},
{
"data": {
"text/html": [
"\n",
"\n",
"
\n",
" \n",
" \n",
" Node \n",
" 0 \n",
" 1 \n",
" 2 \n",
" 3 \n",
" 4 \n",
" 5 \n",
" \n",
" \n",
" \n",
" \n",
" Ticker \n",
" ADA \n",
" BTC \n",
" CDT \n",
" ETH \n",
" NEO \n",
" USDT \n",
" \n",
" \n",
"
\n",
"
"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# Find best set of arbitrage cycles by solving the assignment problem "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Practical Challenges of Arbitrage Trading"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Aspects to consider:\n",
"* Speed, speed, speed!\n",
"* Timing issues\n",
"* Costs of inventory (opportunity cost, market risk, custody risk)\n",
"* Available liqudity\n",
"* Precision of quantities\n",
"* Error handling\n",
"* ..."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"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.7.0"
},
"latex_envs": {
"LaTeX_envs_menu_present": true,
"autoclose": false,
"autocomplete": true,
"bibliofile": "biblio.bib",
"cite_by": "apalike",
"current_citInitial": 1,
"eqLabelWithNumbers": true,
"eqNumInitial": 1,
"hotkeys": {
"equation": "Ctrl-E",
"itemize": "Ctrl-I"
},
"labels_anchors": false,
"latex_user_defs": false,
"report_style_numbering": false,
"user_envs_cfg": false
},
"toc": {
"base_numbering": 1,
"nav_menu": {},
"number_sections": true,
"sideBar": true,
"skip_h1_title": false,
"title_cell": "Table of Contents",
"title_sidebar": "Contents",
"toc_cell": true,
"toc_position": {
"height": "720px",
"left": "27.9943px",
"top": "110.994px",
"width": "271.528px"
},
"toc_section_display": true,
"toc_window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 1
}
![](\"https://3mgj4y44nc15fnv8d303d8zb-wpengine.netdna-ssl.com/wp-content/uploads/2018/06/celo-696x449.jpg\")
\n",
"