Magia algorítmica: explorando a teoria dos grafos no câmbio

Se você está familiarizado com a indústria de startups FinTech, talvez já tenha ouvido falar da Revolut, uma conhecida gigante FinTech com sede em Londres, Reino Unido. Fundada em 2015, a Revolut reuniu investimentos substanciais e tornou-se uma das startups de crescimento mais rápido no Reino Unido, prestando serviços bancários a muitos cidadãos europeus. Embora as operações bancárias sejam muitas vezes envoltas em mistério no que diz respeito à forma como geram receitas, alguns números importantes sobre a Revolut para os anos de 2020 e 2021 lançaram alguma luz sobre as suas fontes de rendimento: Conforme ilustrado, uma parte significativa da receita deste neobanco vem de câmbio (FX), gestão de patrimônio (incluindo criptomoedas) e serviços de cartão. Notavelmente, em 2021, o câmbio tornou-se o setor mais lucrativo. Um amigo meu, que também é engenheiro de software, certa vez compartilhou uma história intrigante sobre sua entrevista técnica no departamento de Engenharia de Software da Revolut, alguns anos atrás. Ele foi encarregado de desenvolver um algoritmo para identificar a forma mais lucrativa de converter duas moedas usando uma ou várias moedas intermediárias. Em outras palavras, procuravam uma estratégia de Arbitragem Cambial. é uma estratégia de negociação em que um negociante de moeda aproveita diferentes spreads oferecidos por corretores para um determinado par de moedas através de múltiplas negociações. Arbitragem de moeda Foi explicitamente mencionado na tarefa que a base do algoritmo deve estar enraizada na teoria dos grafos. Noções básicas de câmbio FX, ou Foreign Exchange, desempenha um papel fundamental no comércio global, sustentando o funcionamento do nosso mundo interligado. É evidente que o câmbio também desempenha um papel substancial em tornar os bancos algumas das organizações mais ricas. O lucro gerado pelo câmbio é principalmente a diferença ou spread entre os preços de compra (BID) e de venda (ASK). Embora esta diferença possa parecer minúscula por transação, pode acumular-se em milhões de dólares em lucros, dado o volume de operações diárias. Isto permite que algumas empresas prosperem exclusivamente com estas operações financeiras altamente automatizadas. No âmbito de FX (Foreign Exchange), trabalhamos sempre com pares de moedas, como EUR/USD. Na maioria dos casos, essas trocas são bidirecionais (ou seja, EUR/USD e USD/EUR), e o valor da taxa de câmbio difere em cada direção. Um representa uma relação numérica entre os valores de duas moedas (EUR e Dólar americano, por exemplo), determinando a taxa de câmbio entre elas. Par de Arbitragem Potencialmente, podemos usar múltiplas moedas intermediárias para negociações lucrativas, conhecidas como . aposta segura é um conjunto de pares a serem utilizados de forma circular. A aposta segura de arbitragem Consulte Mais informação Muitos fornecedores empregam modelagem matemática e análise para garantir seus próprios lucros e evitar que outros lucrem com eles. Portanto, o termo potencialmente é enfatizado aqui. refere-se ao número de pares que constituem um conjunto de oportunidades potenciais de arbitragem. A duração da aposta certa No mundo real, as taxas de câmbio podem variar entre os diferentes bancos ou plataformas de câmbio. Não é incomum que os turistas percorram uma cidade para encontrar a melhor tarifa possível. Com software de computador, esse processo pode ser realizado em milissegundos quando você tiver acesso a uma lista de provedores. Em negociações práticas e lucrativas, várias etapas podem envolver conversões através de várias moedas em diferentes plataformas de câmbio. Em outras palavras, o Círculo de Arbitragem pode ser bastante extenso. envolve adquirir uma moeda, transferi-la para outra plataforma, realizar uma troca por outras moedas e, por fim, retornar à moeda original. O Círculo de Arbitragem A taxa de câmbio entre duas moedas através de uma ou mais moedas intermediárias é calculada como . o produto das taxas de câmbio dessas transações intermediárias Um exemplo Por exemplo, vamos imaginar que queremos comprar francos suíços por dólar americano, depois trocar francos por ienes japoneses e depois vender ienes por dólar americano novamente. No outono de 2023, temos as seguintes taxas de câmbio: Podemos comprar 0,91 CHF (franco suíço) por 1 USD. Podemos comprar 163,16 ienes japoneses por 1 CHF. Podemos comprar 0,0067 USD por 1 iene japonês. Vamos apresentá-lo com uma tabela: 1 USD | 1 CHF | 1 YEN 0.91 CHF | 163.16 YEN | 0.0067 USD ----------------|-------------------|-------------- 1.098901099 | 0.006128953 | 149.2537313 Agora, precisamos de determinar um produto destes valores. Uma sequência de transações : torna-se lucrativa quando este produto rende um valor menor que um 1.098901099 * 0.006128953 * 149.2537313 = 1.005240803 Como podemos ver o resultado é maior que um, parece que perdemos 0,05% do nosso dinheiro. Mas quantos exatamente? Podemos resolver assim: 0.91 CHF * 163.16 (YEN per 1 CHF) * 0.0067 (USD per 1 YEN) = 0.99478652 US Dollars Então, depois de vender 1 dólar americano no início, obtivemos 0,994 – menos de 1 dólar americano no final. Em termos mais simples, o Ciclo de Arbitragem é lucrativo quando uma unidade monetária pode ser obtida por menos de uma unidade da mesma moeda. Vamos imaginar que encontramos uma oportunidade de receber 0,92 CHF por 1 dólar americano na transação inicial, em vez 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 Um produto será menor que 1: 1.086956522 * 0.006128953 * 149.2537313 = 0.994314272 O que significa que nas moedas reais nos dará mais 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, Agora, vamos ver como automatizar isso usando análise de gráficos. obtivemos algum LUCRO! Portanto, a fórmula para verificar lucros ou perdas em um Círculo de Arbitragem de 3 Pares de Arbitragem seria assim: USD/CHF * CHF/YEN * YEN/USD < 1.0 Representação gráfica Para automatizar esses processos podemos usar gráficos. As tabelas mencionadas anteriormente podem ser naturalmente transformadas em uma representação matricial de um gráfico, onde os nós representam moedas e as arestas representam trocas bidirecionais. Portanto, é simples representar a troca de dois pares em uma matriz como esta: EUR USD 1 1 EUR 1 1 USD Dependendo do número de pares envolvidos, nossa matriz pode se expandir: EUR USD YEN CHF 1 1 1 1 EUR 1 1 1 1 USD 1 1 1 1 YEN 1 1 1 1 CHF Consequentemente, a nossa tabela pode tornar-se consideravelmente maior, mesmo para apenas duas moedas, se tivermos em conta mais plataformas e recursos de câmbio. Para resolver problemas de arbitragem de moeda real, é frequentemente utilizado um gráfico completo que abrange todas as relações para cotações de moeda. Uma tabela de câmbio de três moedas pode ter a seguinte aparência: 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 empregar uma simples para representar nossos pares de moedas na memória: estrutura de dados gráfica class GraphNode { public: string Name; }; class Graph { public: vector > Matrix; vector Nodes; }; Agora, só precisamos descobrir como percorrer este gráfico e encontrar o círculo mais lucrativo. Mas ainda há um problema... A matemática nos salva, novamente Algoritmos de grafos clássicos não são adequados para trabalhar com o porque são projetados para encontrar caminhos definidos como (veja implementações de quaisquer algoritmos clássicos bem conhecidos de localização de caminhos ). produto de comprimentos de arestas a soma desses comprimentos BFS, DFS, Dijkstra ou mesmo A-estrela Porém, para contornar essa limitação, existe uma forma matemática de fazer a transição de um produto para uma soma: logaritmos. Se um produto aparecer sob um logaritmo, ele poderá ser convertido em uma soma de logaritmos. No lado direito desta equação, o número desejado é menor que um, indicando que o logaritmo deste número deve ser menor que zero: LogE(USD/CHF) * LogE(CHF/YEN) * LogE(YEN/USD) < 0.0 Este truque matemático simples nos permite passar da busca por um ciclo com um de comprimento de aresta menor que um para . produto a busca por um ciclo onde a soma dos comprimentos de aresta é menor que zero Nossos valores de matriz convertidos em LogE(x) e arredondados com 2 dígitos após o ponto, agora ficam assim: USD CHF YEN { 0.0, 0.1, -5.01 } USD { -0.09, 0.0, -5.1 } CHF { 5.0, 5.09, 0.0 } YEN Agora este problema se torna mais solucionável usando algoritmos gráficos clássicos. O que precisamos é percorrer o gráfico em busca do caminho de troca mais lucrativo. Algoritmos gráficos Todo algoritmo tem suas limitações. Mencionei alguns deles em . meu artigo anterior Não podemos aplicar BFS, DFS clássicos ou mesmo Dijkstra aqui porque nosso gráfico pode conter pesos negativos, o que pode levar a enquanto atravessa o gráfico. Os ciclos negativos representam um desafio para o algoritmo, uma vez que ele encontra continuamente melhores soluções em cada iteração. Ciclos Negativos Para resolver esse problema, o algoritmo Bellman-Ford simplesmente limita o número de iterações. Ele atravessa cada aresta do gráfico em um ciclo e aplica relaxamento para todas as arestas não mais do que V-1 vezes (onde V é um número de nós). Como tal, o algoritmo Bellman-Ford está no centro deste sistema de Arbitragem, pois permite a descoberta de caminhos entre dois nós no grafo que cumprem dois critérios essenciais: contêm pesos negativos e não fazem parte de ciclos negativos. Embora este algoritmo seja teoricamente simples (e você pode encontrar bilhões de vídeos sobre ele), a implementação prática para as nossas necessidades requer algum esforço. Vamos nos aprofundar nisso. Implementação do algoritmo Bellman-Ford Como o objetivo deste artigo é a informática, utilizarei taxas de câmbio imaginárias que nada têm a ver com as reais. Para uma introdução mais suave ao algoritmo, vamos usar um gráfico que não contém nenhum 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 O exemplo de código abaixo encontra um caminho entre dois nós usando o algoritmo Bellman-Ford quando o gráfico não possui 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; } } A execução deste código para o Yuan Chinês preenche a matriz e produz 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 você pode observar, ele identifica caminhos ideais entre o CNY e várias outras moedas. E, novamente, não vou me concentrar em encontrar apenas o melhor, pois é uma tarefa relativamente simples e não o objetivo do artigo. A implementação acima funciona bem em casos ideais, mas é insuficiente ao lidar com gráficos contendo ciclos negativos. Detectando ciclos negativos O que realmente precisamos é da capacidade de identificar se um gráfico contém ciclos negativos e, em caso afirmativo, identificar os segmentos problemáticos. Este conhecimento permite-nos mitigar estes problemas e, em última análise, descobrir cadeias lucrativas. O número de iterações nem sempre precisa atingir precisamente V - 1. Uma solução é considerada encontrada se, no (N+1)-ésimo ciclo, não for descoberto nenhum caminho melhor do que aquele no N-ésimo ciclo. Assim, há espaço para uma ligeira otimização. O código mencionado anteriormente pode ser aprimorado não apenas para encontrar caminhos, mas também para detectar se o gráfico contém ciclos negativos, incluindo a otimização que mencionei: 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; } E agora brincamos com um gráfico mais complexo que inclui 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 Nosso programa simplesmente para e exibe uma mensagem: Graph contains negative cycle. Conseguimos indicar o problema, porém, precisamos navegar pelos segmentos problemáticos do gráfico. Evitando ciclos negativos Para isso, marcaremos os vértices que fazem parte de ciclos negativos com um 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; } Agora, se encontrarmos NEG_INF no array _shortestPath, podemos exibir uma mensagem e pular esse segmento enquanto ainda identificamos soluções ideais para outras moedas. Por exemplo, com o Nó 0 (representando 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) Uau! Nosso código foi capaz de identificar uma série de cadeias lucrativas, apesar de nossos dados estarem “um pouco sujos”. Todos os exemplos de código mencionados acima, incluindo dados de teste, são compartilhados com você em . meu GitHub Mesmo pequenas flutuações são importantes Vamos agora consolidar o que aprendemos. Dada uma lista de taxas de câmbio para três moedas, podemos facilmente detectar 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). Contudo, mesmo pequenas alterações nas taxas de câmbio (ou seja, ajustamentos à matriz) podem levar a diferenças 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); Olha, encontramos uma rede lucrativa: 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 estes conceitos a gráficos muito maiores, envolvendo múltiplas moedas: 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, podemos encontrar vários candidatos para obter lucro: 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) Existem dois fatores importantes, no entanto: O tempo é um fator crítico na implementação de processos de arbitragem, principalmente devido às rápidas flutuações nos preços das moedas. Como resultado, a vida útil de uma aposta segura é extremamente breve. As plataformas cobram comissões para cada transação. Portanto, e são fundamentais, o que se consegue limitando a duração da aposta segura. minimizar os custos de tempo reduzir as comissões A experiência empírica sugere que uma duração aceitável de aposta segura normalmente varia de 2 a 3 pares. Além disso, os requisitos computacionais aumentam e as plataformas de negociação impõem comissões maiores. Assim, para ter renda não basta ter essas tecnologias, mas também é preciso ter acesso às comissões de baixo nível. Normalmente, apenas as grandes instituições financeiras têm esse recurso em mãos. Automação usando contratos inteligentes Mergulhei na lógica das operações cambiais e em como obter lucros delas, mas não abordei as tecnologias usadas para executar essas operações. Embora este tópico se desvie um pouco do curso, não poderia deixar de mencionar os contratos inteligentes. Usar contratos inteligentes é uma das formas mais inovadoras de conduzir operações de câmbio atualmente. Os contratos inteligentes permitem operações de câmbio em tempo real, sem atrasos ou intervenção humana (exceto para a criação do contrato inteligente). Solidity é a linguagem de programação especializada para criação de contratos inteligentes que automatizam operações financeiras envolvendo criptomoedas. O mundo dos contratos inteligentes é dinâmico e sujeito a rápidas mudanças tecnológicas e regulamentações em evolução. É uma área com considerável entusiasmo e riscos significativos relacionados com carteiras e conformidade legal. Embora existam, sem dúvida, indivíduos e equipas talentosos que lucram com este campo, também existem organismos reguladores que se esforçam para garantir que as regras do mercado sejam respeitadas. Por que estamos investigando isso? Apesar da complexidade, obscuridade e imprevisibilidade da economia global, o câmbio continua a ser uma força motriz oculta no mundo financeiro. É um elemento crucial que permite a milhares de empresas e milhões de indivíduos em todo o mundo colaborar, prestar serviços e beneficiar-se mutuamente de forma pacífica, transcendendo fronteiras. É claro que vários factores, como a política, as regulamentações e os bancos centrais, influenciam as taxas de câmbio e a eficiência cambial. Essas complexidades tornam o cenário financeiro complexo. No entanto, é essencial acreditar que estas complexidades servem um propósito maior para o bem comum. Numerosos artigos científicos investigam a existência e a determinação das taxas de câmbio na economia global, para citar alguns: Importadores, exportadores e desconexão cambial Escolha da moeda e repasse da taxa de câmbio Enigmas e políticas cambiais Esses artigos lançam luz sobre alguns mecanismos fundamentais de câmbio, que ainda são difíceis de compreender e encaixar em um modelo. Porém, brincar com o código e tentar encontrar uma solução para um problema prático me ajudou a ter mais pistas sobre ele. Espero que você tenha gostado desta pequena viagem de exploração tanto quanto eu. Fique atento! Ligações Código fonte com todos esses exemplos Sedgewick R. - Algoritmos em C, Parte 5: Algoritmos de Gráfico Implementação do código do algoritmo Bellman Ford Exemplos de GitHub de William Fiset - Bellman Ford na matriz de adjacência Exemplos de GitHub de William Fiset - Bellman Ford On Edge List Também publicado . aqui