Magia algorítmica: explotación de la teoría de grafos en el mercado de divisas

Si está familiarizado con la industria de las startups FinTech, es posible que haya oído hablar de Revolut, un conocido gigante FinTech con sede en Londres, Reino Unido. Fundada en 2015, Revolut ha obtenido importantes inversiones y se ha convertido en una de las nuevas empresas de más rápido crecimiento en el Reino Unido, proporcionando servicios bancarios a muchos ciudadanos europeos. Si bien las operaciones bancarias suelen estar envueltas en un misterio en cuanto a cómo generan ingresos, algunas cifras clave sobre Revolut para los años 2020 y 2021 han arrojado algo de luz sobre sus fuentes de ingresos: Como se ilustra, una parte importante de los ingresos de este neobanco proviene de divisas (FX), gestión patrimonial (incluidas las criptomonedas) y servicios de tarjetas. En particular, en 2021, el mercado de divisas se convirtió en el sector más rentable. Un amigo mío, que también es ingeniero de software, compartió una vez una historia intrigante sobre su entrevista técnica en el departamento de Ingeniería de Software de Revolut hace unos años. Se le asignó la tarea de desarrollar un algoritmo para identificar la forma más rentable de convertir dos monedas utilizando una o varias monedas intermedias. En otras palabras, buscaban una estrategia de arbitraje de divisas. es una estrategia comercial en la que un operador de divisas aprovecha los diferentes diferenciales ofrecidos por los corredores para un par de divisas en particular a través de múltiples operaciones. El arbitraje de divisas En la tarea se mencionó explícitamente que la base del algoritmo debe tener sus raíces en la teoría de grafos. Conceptos básicos de divisas FX, o divisas, juega un papel fundamental en el comercio global, apuntalando el funcionamiento de nuestro mundo interconectado. Es evidente que el mercado de divisas también desempeña un papel importante a la hora de convertir a los bancos en algunas de las organizaciones más ricas. El beneficio generado por las divisas es principalmente la diferencia o diferencial entre los precios de compra (BID) y de venta (ASK). Si bien esta diferencia puede parecer minúscula por transacción, puede acumularse en ganancias de millones de dólares dado el volumen de operaciones diarias. Esto permite que algunas empresas prosperen únicamente con estas operaciones financieras altamente automatizadas. En el ámbito FX (Foreign Exchange), siempre trabajamos con pares de divisas, como EUR/USD. En la mayoría de los casos, estos intercambios son bidireccionales (es decir, EUR/USD y USD/EUR) y el valor del tipo de cambio difiere en cada dirección. Un representa una relación numérica entre los valores de dos monedas (EUR y dólar estadounidense, por ejemplo), determinando el tipo de cambio entre ellas. par de arbitraje Potencialmente, podemos utilizar múltiples monedas intermedias para realizar operaciones rentables, lo que se conoce como . apuesta segura es un conjunto de pares que se utilizan de forma circular. La apuesta segura de arbitraje Leer más Muchos proveedores emplean modelos y análisis matemáticos para asegurar sus propios beneficios y evitar que otros se beneficien de ellos. Por lo tanto, aquí se enfatiza el término potencialmente. se refiere a la cantidad de pares que constituyen un conjunto de posibles oportunidades de arbitraje. La duración de la apuesta segura En el mundo real, los tipos de cambio pueden variar entre diferentes bancos o plataformas de cambio. No es raro que los turistas recorran una ciudad para encontrar la mejor tarifa posible. Con el software informático, este proceso se puede realizar en milisegundos cuando se tiene acceso a una lista de proveedores. En operaciones prácticas rentables, varios pasos pueden implicar conversiones a través de varias monedas en diferentes plataformas de intercambio. En otras palabras, el Círculo de Arbitraje puede ser bastante extenso. implica adquirir una moneda, transferirla a otra plataforma, realizar un intercambio por otras monedas y, en última instancia, regresar a la moneda original. Arbitrage Circle El tipo de cambio entre dos monedas a través de una o más monedas intermedias se calcula como . el producto de los tipos de cambio de estas transacciones intermedias Un ejemplo Por ejemplo, imaginemos que queremos comprar francos suizos por dólares estadounidenses, luego cambiar francos por yenes japoneses y luego vender yenes por dólares estadounidenses nuevamente. En otoño de 2023, tenemos los siguientes tipos de cambio: Podemos comprar 0,91 CHF (franco suizo) por 1 USD. Podemos comprar 163,16 yenes japoneses por 1 CHF. Podemos comprar 0,0067 USD por 1 yen japonés. Presentémoslo con una tabla: 1 USD | 1 CHF | 1 YEN 0.91 CHF | 163.16 YEN | 0.0067 USD ----------------|-------------------|-------------- 1.098901099 | 0.006128953 | 149.2537313 Ahora, necesitamos encontrar un producto de esos valores. Una secuencia de transacciones : se vuelve rentable cuando este producto produce un valor menor que uno 1.098901099 * 0.006128953 * 149.2537313 = 1.005240803 Como podemos ver, el resultado es mayor que uno, por lo que parece que perdimos el 0,05% de nuestro dinero. ¿Pero cuántos exactamente? Podemos ordenarlo así: 0.91 CHF * 163.16 (YEN per 1 CHF) * 0.0067 (USD per 1 YEN) = 0.99478652 US Dollars Entonces, después de vender 1 dólar estadounidense al principio, obtuvimos 0,994, menos de 1 dólar estadounidense al final. En términos más simples, el ciclo de arbitraje es rentable cuando se puede obtener una unidad monetaria por menos de una unidad de la misma moneda. Imaginemos que hemos encontrado la oportunidad de cobrar 0,92 CHF por 1 dólar estadounidense en la transacción inicial, en lugar de 0,91 CHF: 1 USD | 1 CHF | 1 YEN 0.92 CHF | 163.16 YEN | 0.0067 USD ----------------|-------------------|-------------- 1.086956522 | 0.006128953 | 149.2537313 Un producto será menor que 1: 1.086956522 * 0.006128953 * 149.2537313 = 0.994314272 Es decir, en monedas reales nos dará más de 1 dólar americano: 0.92 CHF * 163.16 (YEN per 1 CHF) * 0.0067 (USD per 1 YEN) = 1.00571824 US Dollars Wuolah, Ahora, veamos cómo automatizar esto mediante el análisis de gráficos. ¡obtuvimos algunas GANANCIAS! Entonces, la fórmula para verificar ganancias o pérdidas en un Círculo de Arbitraje de 3 Pares de Arbitraje sería la siguiente: USD/CHF * CHF/YEN * YEN/USD < 1.0 Representación gráfica Para automatizar esos procesos podemos utilizar gráficos. Las tablas mencionadas anteriormente se pueden transformar naturalmente en una representación matricial de un gráfico, donde los nodos representan monedas y los bordes representan intercambios bidireccionales. Por lo tanto, es sencillo representar el intercambio de dos pares en una matriz como esta: EUR USD 1 1 EUR 1 1 USD Dependiendo del número de pares involucrados, nuestra matriz puede expandirse: EUR USD YEN CHF 1 1 1 1 EUR 1 1 1 1 USD 1 1 1 1 YEN 1 1 1 1 CHF En consecuencia, nuestra tabla puede llegar a ser considerablemente mayor, incluso para sólo dos monedas, si tenemos en cuenta más plataformas de intercambio y recursos. Para abordar problemas reales de arbitraje de divisas, a menudo se utiliza un gráfico completo que abarca todas las relaciones de las cotizaciones de divisas. Una tabla de cambio de tres monedas podría verse así: USD CHF YEN { 1.0, 1.10, 0.0067 } USD { 0.91, 1.0, 0.0061 } CHF { 148.84, 163.16, 1.0 } YEN Podemos emplear una simple para representar nuestros pares de divisas en la memoria: estructura de datos gráfica class GraphNode { public: string Name; }; class Graph { public: vector > Matrix; vector Nodes; }; Ahora, sólo nos falta descubrir cómo recorrer este gráfico y encontrar el círculo más rentable. Pero todavía hay un problema... Las matemáticas nos salvan, otra vez Los algoritmos de gráficos clásicos no son adecuados para trabajar con el porque están diseñados para encontrar caminos definidos como (consulte las implementaciones de cualquier algoritmo clásico de búsqueda de caminos conocido ). producto de longitudes de aristas la suma de estas longitudes , BFS, DFS, Dijkstra o incluso Una estrella Sin embargo, para sortear esta limitación, existe una forma matemática de pasar de un producto a una suma: los logaritmos. Si un producto aparece debajo de un logaritmo, se puede convertir en una suma de logaritmos. En el lado derecho de esta ecuación, el número deseado es menor que uno, lo que indica que el logaritmo de este número debe ser menor que cero: LogE(USD/CHF) * LogE(CHF/YEN) * LogE(YEN/USD) < 0.0 Este sencillo truco matemático nos permite pasar de buscar un ciclo con un de longitud de arista menor que uno a . producto buscar un ciclo donde la suma de las longitudes de arista sea menor que cero Nuestros valores de matriz convertidos a LogE(x) y redondeados con 2 dígitos después del punto, ahora se ven así: USD CHF YEN { 0.0, 0.1, -5.01 } USD { -0.09, 0.0, -5.1 } CHF { 5.0, 5.09, 0.0 } YEN Ahora este problema se vuelve más solucionable utilizando algoritmos gráficos clásicos. Lo que necesitamos es recorrer el gráfico buscando la ruta de intercambio más rentable. Algoritmos gráficos Cada algoritmo tiene sus limitaciones. Mencioné algunos de ellos en . mi artículo anterior No podemos aplicar BFS, DFS o incluso Dijkstra aquí porque nuestro gráfico puede contener pesos negativos, lo que puede conducir a mientras atraviesa el gráfico. Los ciclos negativos plantean un desafío para el algoritmo, ya que continuamente encuentra mejores soluciones en cada iteración. ciclos negativos Para abordar este problema, el algoritmo Bellman-Ford simplemente limita el número de iteraciones. Atraviesa cada borde del gráfico en un ciclo y aplica relajación para todos los bordes no más de V-1 veces (donde V es un número de nodos). Como tal, el algoritmo Bellman-Ford se encuentra en el corazón de este sistema de arbitraje, ya que permite descubrir caminos entre dos nodos en el gráfico que cumplen dos criterios esenciales: contienen pesos negativos y no forman parte de ciclos negativos. Si bien este algoritmo es teóricamente sencillo (y puedes encontrar miles de millones de videos sobre él), la implementación práctica para nuestras necesidades requiere algo de esfuerzo. Profundicemos en ello. Implementación del algoritmo Bellman-Ford Como el objetivo de este artículo es informática, utilizaré tipos de cambio imaginarios que no tienen nada que ver con los reales. Para una introducción más fluida al algoritmo, usemos un gráfico que no contenga ningún ciclo negativo: graph.Nodes.push_back({ "USD" }); graph.Nodes.push_back({ "CHF" }); graph.Nodes.push_back({ "YEN" }); graph.Nodes.push_back({ "GBP" }); graph.Nodes.push_back({ "CNY" }); graph.Nodes.push_back({ "EUR" }); // Define exchange rates for pairs of currencies below // USD CHF YEN GBP CNY EUR graph.Matrix = { { 0.0, 0.41, INF, INF, INF, 0.29 }, // USD { INF, 0.0, 0.51, INF, 0.32, INF }, // CHF { INF, INF, 0.0, 0.50, INF, INF }, // YEN { 0.45, INF, INF, 0.0, INF, -0.38 }, // GBP { INF, INF, 0.32, 0.36, 0.0, INF }, // CNY { INF, -0.29, INF, INF, 0.21, 0.0 } }; // EUR El siguiente ejemplo de código encuentra una ruta entre dos nodos utilizando el algoritmo Bellman-Ford cuando el gráfico carece de ciclos negativos: vector _shortestPath; vector _previousVertex; void FindPath(Graph& graph, int start) { int verticesNumber = graph.Nodes.size(); _shortestPath.resize(verticesNumber, INF); _previousVertex.resize(verticesNumber, -1); _shortestPath[start] = 0; // For each vertex, apply relaxation for all the edges V - 1 times. for (int k = 0; k _shortestPath[from] + graph.Matrix[from][to]) { _shortestPath[to] = _shortestPath[from] + graph.Matrix[from][to]; _previousVertex[to] = from; } } Al ejecutar este código para el yuan chino se llena la matriz y se obtienen resultados como este: _previousVertex Path from 4 to 0 is : 4(CNY) 3(GBP) 0(USD) Path from 4 to 1 is : 4(CNY) 3(GBP) 5(EUR) 1(CHF) Path from 4 to 2 is : 4(CNY) 3(GBP) 5(EUR) 1(CHF) 2(YEN) Path from 4 to 3 is : 4(CNY) 3(GBP) Path from 4 to 4 is : 4(CNY) Path from 4 to 5 is : 4(CNY) 3(GBP) 5(EUR) Como puede observar, identifica rutas óptimas entre el CNY y otras monedas. Y nuevamente, no me concentraré en encontrar solo uno de los mejores, ya que es una tarea relativamente simple y no es el objetivo del artículo. La implementación anterior funciona bien en casos ideales, pero se queda corta cuando se trata de gráficos que contienen ciclos negativos. Detectando ciclos negativos Lo que realmente necesitamos es la capacidad de identificar si un gráfico contiene ciclos negativos y, de ser así, identificar los segmentos problemáticos. Este conocimiento nos permite mitigar estos problemas y, en última instancia, descubrir cadenas rentables. El número de iteraciones no siempre tiene que llegar exactamente a V - 1. Se considera encontrada una solución si, en el ciclo (N+1) no se descubre un camino mejor que el del ciclo N. Por tanto, hay margen para una ligera optimización. El código mencionado anteriormente se puede mejorar no solo para encontrar rutas sino también para detectar si el gráfico contiene ciclos negativos, incluida la optimización que mencioné: vector _shortestPath; vector _previousVertex; bool ContainsNegativeCycles(Graph& graph, int start) { int verticesNumber = graph.Nodes.size(); _shortestPath.resize(verticesNumber, INF); _previousVertex.resize(verticesNumber, -1); _shortestPath[start] = 0; // For each vertex, apply relaxation for all the edges V - 1 times. for (int k = 0; k _shortestPath[from] + graph.Matrix[from][to]) { _shortestPath[to] = _shortestPath[from] + graph.Matrix[from][to]; _previousVertex[to] = from; updated = true; } } } if (!updated) // No changes in paths, means we can finish earlier. break; } // Run one more relaxation step to detect which nodes are part of a negative cycle. if (updated) for (int from = 0; from _shortestPath[from] + graph.Matrix[from][to]) // A negative cycle has occurred if we can find a better path beyond the optimal solution. return true; return false; } Y ahora jugamos con un gráfico más complejo que incluye ciclos negativos: graph.Nodes.push_back({ "USD" }); // 1 (Index = 0) graph.Nodes.push_back({ "CHF" }); graph.Nodes.push_back({ "YEN" }); graph.Nodes.push_back({ "GBP" }); graph.Nodes.push_back({ "CNY" }); graph.Nodes.push_back({ "EUR" }); graph.Nodes.push_back({ "XXX" }); graph.Nodes.push_back({ "YYY" }); // 8 (Index = 7) // USD CHF YEN GBP CNY EUR XXX YYY graph.Matrix = { { 0.0, 1.0, INF, INF, INF, INF, INF, INF }, // USD { INF, 0.0, 1.0, INF, INF, 4.0, 4.0, INF }, // CHF { INF, INF, 0.0, INF, 1.0, INF, INF, INF }, // YEN { INF, INF, 1.0, 0.0, INF, INF, INF, INF }, // GBP { INF, INF, INF, -3.0, 0.0, INF, INF, INF }, // CNY { INF, INF, INF, INF, INF, 0.0, 5.0, 3.0 }, // EUR { INF, INF, INF, INF, INF, INF, 0.0, 4.0 }, // XXX { INF, INF, INF, INF, INF, INF, INF, 0.0 } }; // YYY Nuestro programa simplemente se detiene y muestra un mensaje: Graph contains negative cycle. Pudimos indicar el problema, sin embargo, debemos navegar por los segmentos problemáticos del gráfico. Evitar ciclos negativos Para lograr esto, marcaremos los vértices que forman parte de ciclos negativos con un valor constante, NEG_INF: bool FindPathsAndNegativeCycles(Graph& graph, int start) { int verticesNumber = graph.Nodes.size(); _shortestPath.resize(verticesNumber, INF); _previousVertex.resize(verticesNumber, -1); _shortestPath[start] = 0; for (int k = 0; k _shortestPath[from] + graph.Matrix[from][to]) { _shortestPath[to] = _shortestPath[from] + graph.Matrix[from][to]; _previousVertex[to] = from; } } bool negativeCycles = false; for (int k = 0; k _shortestPath[from] + graph.Matrix[from][to]) { _shortestPath[to] = NEG_INF; _previousVertex[to] = -2; negativeCycles = true; } } return negativeCycles; } Ahora, si encontramos NEG_INF en la matriz _shortestPath, podemos mostrar un mensaje y omitir ese segmento mientras seguimos identificando soluciones óptimas para otras monedas. Por ejemplo, con el Nodo 0 (que representa USD): Graph contains negative cycle. Path from 0 to 0 is : 0(USD) Path from 0 to 1 is : 0(USD) 1(CHF) Path from 0 to 2 is : Infinite number of shortest paths (negative cycle). Path from 0 to 3 is : Infinite number of shortest paths (negative cycle). Path from 0 to 4 is : Infinite number of shortest paths (negative cycle). Path from 0 to 5 is : 0(USD) 1(CHF) 5(EUR) Path from 0 to 6 is : 0(USD) 1(CHF) 6(XXX) Path from 0 to 7 is : 0(USD) 1(CHF) 5(EUR) 7(YYY) ¡Vaya! Nuestro código pudo identificar varias cadenas rentables a pesar de que nuestros datos estaban "un poco sucios". Todos los ejemplos de código mencionados anteriormente, incluidos los datos de prueba, se comparten con usted en . mi GitHub Incluso las pequeñas fluctuaciones importan Consolidemos ahora lo que hemos aprendido. Dada una lista de tipos de cambio para tres monedas, podemos detectar fácilmente ciclos negativos: graph.Nodes.push_back({ "USD" }); // 1 (Index = 0) graph.Nodes.push_back({ "CHF" }); graph.Nodes.push_back({ "YEN" }); // 3 (Index = 2) // LogE(x) table: USD CHF YEN graph.Matrix = { { 0.0, 0.489, -0.402 }, // USD { -0.489, 0.0, -0.891 }, // CHF { 0.402, 0.89, 0.0 } }; // YEN from = 0; FindPathsAndNegativeCycles(graph, from); Resultado: Graph contains negative cycle. Path from 0 to 0 is: Infinite number of shortest paths (negative cycle). Path from 0 to 1 is: Infinite number of shortest paths (negative cycle). Path from 0 to 2 is: Infinite number of shortest paths (negative cycle). Sin embargo, incluso cambios leves en los tipos de cambio (es decir, ajustes a la matriz) pueden generar diferencias significativas: // LogE(x) table: USD CHF YEN graph.Matrix = { { 0.0, 0.490, -0.402 }, // USD { -0.489, 0.0, -0.891 }, // CHF { 0.403, 0.891, 0.0 } }; // YEN from = 0; FindPathsAndNegativeCycles(graph, from); Mira, hemos encontrado una cadena rentable: Path from 0 to 0 is : 0(USD) Path from 0 to 1 is : 0(USD) 2(YEN) 1(CHF) Path from 0 to 2 is : 0(USD) 2(YEN) Podemos aplicar estos conceptos a gráficos mucho más grandes, que involucran múltiples monedas: graph.Nodes.push_back({ "USD" }); // 1 (Index = 0) graph.Nodes.push_back({ "CHF" }); graph.Nodes.push_back({ "YEN" }); graph.Nodes.push_back({ "GBP" }); graph.Nodes.push_back({ "CNY" }); // 5 (Index = 4) // LogE(x) table: USD CHF YEN GBP CNY graph.Matrix = { { 0.0, 0.490, -0.402, 0.7, 0.413 }, // USD { -0.489, 0.0, -0.891, 0.89, 0.360 }, // CHF { 0.403, 0.891, 0.0, 0.91, 0.581 }, // YEN { 0.340, 0.405, 0.607, 0.0, 0.72 }, // GBP { 0.403, 0.350, 0.571, 0.71, 0.0 } }; // CNY from = 0; runDetectNegativeCycles(graph, from); Como resultado, podríamos encontrar múltiples candidatos para obtener ganancias: Path from 0 to 0 is : 0(USD) Path from 0 to 1 is : 0(USD) 2(YEN) 1(CHF) Path from 0 to 2 is : 0(USD) 2(YEN) Path from 0 to 3 is : 0(USD) 2(YEN) 3(GBP) Path from 0 to 4 is : 0(USD) 2(YEN) 4(CNY) Sin embargo, hay dos factores importantes: El tiempo es un factor crítico en la implementación de procesos de arbitraje, principalmente debido a las rápidas fluctuaciones en los precios de las divisas. Como resultado, la vida útil de una apuesta segura es extremadamente breve. Las plataformas cobran comisiones por cada transacción. Por lo tanto, y es primordial, lo que se consigue limitando la duración de la apuesta segura. minimizar los costes de tiempo reducir las comisiones La experiencia empírica sugiere que una duración aceptable de apuesta segura suele oscilar entre 2 y 3 pares. Más allá de esto, los requisitos computacionales aumentan y las plataformas comerciales imponen comisiones mayores. Por lo tanto, para obtener ingresos no basta con tener este tipo de tecnologías, sino que también es necesario acceder a comisiones de bajo nivel. Por lo general, sólo las grandes instituciones financieras tienen ese recurso en sus manos. Automatización mediante contratos inteligentes He profundizado en la lógica de las operaciones FX y cómo obtener ganancias de ellas, pero no he tocado las tecnologías utilizadas para ejecutar estas operaciones. Si bien este tema se desvía ligeramente de su curso, no puedo dejar de mencionar los contratos inteligentes. El uso de contratos inteligentes es una de las formas más innovadoras de realizar operaciones de divisas en la actualidad. Los contratos inteligentes permiten operaciones FX en tiempo real sin demoras ni intervención humana (excepto para la creación del contrato inteligente). Solidity es el lenguaje de programación especializado para crear contratos inteligentes que automaticen operaciones financieras que involucran criptomonedas. El mundo de los contratos inteligentes es dinámico y está sujeto a rápidos cambios tecnológicos y regulaciones en evolución. Es un área con considerable revuelo y riesgos significativos relacionados con las billeteras y el cumplimiento legal. Si bien es indudable que hay personas y equipos talentosos que se benefician de este campo, también hay organismos reguladores que se esfuerzan por garantizar que se respeten las reglas del mercado. ¿Por qué estamos investigando esto? A pesar de la complejidad, oscuridad e imprevisibilidad de la economía global, las divisas siguen siendo una fuerza impulsora oculta en el mundo financiero. Es un elemento crucial que permite a miles de empresas y millones de personas en todo el mundo colaborar, proporcionar servicios y beneficiarse mutuamente de manera pacífica, trascendiendo fronteras. Por supuesto, varios factores, como la política, las regulaciones y los bancos centrales, influyen en los tipos de cambio y la eficiencia cambiaria. Estas complejidades hacen que el panorama financiero sea complejo. Sin embargo, es esencial creer que estas complejidades sirven a un propósito mayor para el bien común. Numerosos artículos científicos profundizan en la existencia y determinación de los tipos de cambio en la economía global, por mencionar algunos: Importadores, exportadores y desconexión cambiaria Elección de moneda y transmisión del tipo de cambio Enigmas y políticas cambiarias Estos artículos arrojan luz sobre algunos mecanismos fundamentales de las divisas, que aún son difíciles de entender y encajar en un solo modelo. Sin embargo, jugar con el código e intentar encontrar una solución a un problema práctico me ayudó a tener un poco más de idea al respecto. Espero que hayas disfrutado de este pequeño viaje de exploración tanto como yo. ¡Manténganse al tanto! Enlaces Código fuente con todos estos ejemplos. Sedgewick R. - Algoritmos en C, Parte 5: Algoritmos de gráficos Implementación del código del algoritmo Bellman Ford Ejemplos de GitHub de William Fiset: Bellman Ford en Adjacency Matrix Ejemplos de GitHub de William Fiset - Bellman Ford On Edge List También publicado . aquí