Алгоритмическое волшебство: использование теории графов на валютной бирже

Если вы знакомы с индустрией стартапов FinTech, возможно, вы слышали о Revolut, известном гиганте FinTech, базирующемся в Лондоне, Великобритания. Основанная в 2015 году, Revolut привлекла значительные инвестиции и стала одним из самых быстрорастущих стартапов в Великобритании, предоставляя банковские услуги многим гражданам Европы. Хотя банковские операции часто окутаны тайной, когда речь идет о том, как они приносят доход, некоторые ключевые цифры Revolut за 2020 и 2021 годы пролили некоторый свет на их источники дохода: Как показано, значительная часть доходов этого необанка поступает от иностранной валюты (FX), управления активами (включая криптовалюты) и карточных услуг. Примечательно, что в 2021 году валютный рынок стал самым прибыльным сектором. Мой друг, который также является инженером-программистом, однажды поделился интригующей историей о своем техническом собеседовании в отделе разработки программного обеспечения Revolut несколько лет назад. Ему было поручено разработать алгоритм, позволяющий определить наиболее выгодный способ конвертации двух валют с использованием одной или нескольких промежуточных валют. Другими словами, они искали стратегию валютного арбитража. — это торговая стратегия, в которой валютный трейдер использует различные спреды, предлагаемые брокерами для конкретной валютной пары, посредством нескольких сделок. Валютный арбитраж В задаче явно было упомянуто, что основа алгоритма должна быть основана на теории графов. Основы Форекс FX, или иностранная валюта, играет ключевую роль в глобальной торговле, поддерживая функционирование нашего взаимосвязанного мира. Очевидно, что валютный рынок также играет существенную роль в превращении банков в одни из самых богатых организаций. Прибыль, полученная от обмена иностранной валюты, представляет собой, прежде всего, разницу или спред между ценами покупки (BID) и продажи (ASK). Хотя эта разница может показаться незначительной в расчете на транзакцию, она может накапливаться в миллионы долларов прибыли, учитывая объем ежедневных операций. Это позволяет некоторым компаниям преуспевать исключительно за счет этих высокоавтоматизированных финансовых операций. В сфере FX (иностранной валюты) мы всегда работаем с парами валют, такими как EUR/USD. В большинстве случаев эти обмены являются двунаправленными (т. е. EUR/USD и USD/EUR), и стоимость обменного курса различается в каждом направлении. представляет собой числовое соотношение стоимости двух валют (например, евро и доллара США), определяющее обменный курс между ними. Арбитражная пара Потенциально мы можем использовать несколько промежуточных валют для прибыльной торговли, известной как . верная ставка представляет собой набор пар, которые можно использовать по кругу. Арбитражная вилка Читать далее Многие поставщики используют математическое моделирование и анализ, чтобы обеспечить свою прибыль и не дать другим получить от нее прибыль. Следовательно, здесь подчеркивается термин «потенциально». относится к количеству пар, которые составляют набор потенциальных арбитражных возможностей. Длина уверенной ставки В реальном мире обменные курсы могут различаться в разных банках или обменных платформах. Туристы нередко объезжают город в поисках лучшей цены. С помощью компьютерного программного обеспечения этот процесс можно выполнить за миллисекунды, если у вас есть доступ к списку поставщиков. В практических прибыльных сделках несколько этапов могут включать конвертацию различных валют на разных биржевых платформах. Другими словами, Арбитражный Круг может быть весьма обширным. предполагает приобретение валюты, перевод ее на другую платформу, проведение обмена на другие валюты и в конечном итоге возврат к исходной валюте. Арбитражный круг Обменный курс между двумя валютами через одну или несколько промежуточных валют рассчитывается как . произведение обменных курсов этих промежуточных транзакций Пример Например, предположим, что мы хотим купить швейцарские франки за доллар США, затем обменять франки на японские иены, а затем снова продать иены за доллары США. Осенью 2023 года у нас действуют следующие курсы обмена: Мы можем купить 0,91 CHF (швейцарский франк) за 1 доллар США. Мы можем купить 163,16 японских иен за 1 швейцарский франк. Мы можем купить 0,0067 доллара США за 1 японскую иену. Представим это в виде таблицы: 1 USD | 1 CHF | 1 YEN 0.91 CHF | 163.16 YEN | 0.0067 USD ----------------|-------------------|-------------- 1.098901099 | 0.006128953 | 149.2537313 Теперь нам нужно найти произведение этих значений. Последовательность транзакций : становится прибыльной, когда этот продукт дает стоимость меньше единицы 1.098901099 * 0.006128953 * 149.2537313 = 1.005240803 Как мы видим, результат больше единицы, поэтому похоже, что мы потеряли 0,05% наших денег. Но сколько именно? Мы можем это упорядочить следующим образом: 0.91 CHF * 163.16 (YEN per 1 CHF) * 0.0067 (USD per 1 YEN) = 0.99478652 US Dollars Итак, продав 1 доллар США вначале, мы получили 0,994 – меньше 1 доллара США в итоге. Проще говоря, арбитражный цикл выгоден, когда одну единицу валюты можно получить менее чем за одну единицу той же валюты. Предположим, мы нашли возможность брать 0,92 CHF за 1 доллар США в первоначальной транзакции вместо 0,91 CHF: 1 USD | 1 CHF | 1 YEN 0.92 CHF | 163.16 YEN | 0.0067 USD ----------------|-------------------|-------------- 1.086956522 | 0.006128953 | 149.2537313 Произведение будет меньше 1: 1.086956522 * 0.006128953 * 149.2537313 = 0.994314272 Это означает, что в реальной валюте это даст нам более 1 доллара США: 0.92 CHF * 163.16 (YEN per 1 CHF) * 0.0067 (USD per 1 YEN) = 1.00571824 US Dollars Ура, Теперь давайте посмотрим, как это автоматизировать с помощью анализа графиков. мы получили ПРИБЫЛЬ! Итак, формула для проверки прибыли или убытков в арбитражном круге из 3 арбитражных пар будет выглядеть следующим образом: USD/CHF * CHF/YEN * YEN/USD < 1.0 Графическое представление Чтобы автоматизировать эти процессы, мы можем использовать графики. Упомянутые ранее таблицы можно естественным образом преобразовать в матричное представление графа, где узлы представляют валюты, а ребра представляют двунаправленный обмен. Следовательно, легко представить обмен двумя парами в матрице следующим образом: EUR USD 1 1 EUR 1 1 USD В зависимости от количества задействованных пар наша матрица может расширяться: EUR USD YEN CHF 1 1 1 1 EUR 1 1 1 1 USD 1 1 1 1 YEN 1 1 1 1 CHF Следовательно, наша таблица может стать значительно больше даже для двух валют, если мы примем во внимание больше обменных платформ и ресурсов. Для решения реальных проблем валютного арбитража часто используется полный график, охватывающий все взаимосвязи котировок валют. Таблица обмена трех валют может выглядеть следующим образом: USD CHF YEN { 1.0, 1.10, 0.0067 } USD { 0.91, 1.0, 0.0061 } CHF { 148.84, 163.16, 1.0 } YEN Мы можем использовать простую для представления наших валютных пар в памяти: структуру данных графа class GraphNode { public: string Name; }; class Graph { public: vector > Matrix; vector Nodes; }; Теперь нам осталось только узнать, как пройти этот граф и найти наиболее выгодный круг. Но есть еще одна проблема... Математика снова спасает нас Классические алгоритмы на графах плохо подходят для работы с поскольку они предназначены для поиска путей, определяемых как (см. реализации любых известных классических алгоритмов поиска путей ). произведением длин ребер, сумма этих длин BFS, DFS, Dijkstra или даже А-звезда Однако, чтобы обойти это ограничение, существует математический способ перехода от произведения к сумме: логарифмы. Если произведение стоит под логарифмом, его можно преобразовать в сумму логарифмов. В правой части этого уравнения искомое число меньше единицы, что указывает на то, что логарифм этого числа должен быть меньше нуля: LogE(USD/CHF) * LogE(CHF/YEN) * LogE(YEN/USD) < 0.0 Этот простой математический прием позволяет нам перейти от поиска цикла с длин ребер меньше единицы к . произведением поиску цикла, в котором сумма длин ребер меньше нуля Наши матричные значения, преобразованные в LogE(x) и округленные до двух цифр после точки, теперь выглядят так: USD CHF YEN { 0.0, 0.1, -5.01 } USD { -0.09, 0.0, -5.1 } CHF { 5.0, 5.09, 0.0 } YEN Теперь эта проблема становится более разрешимой с использованием классических графовых алгоритмов. Нам нужно пройти по графу в поисках наиболее выгодного пути обмена. Графовые алгоритмы Каждый алгоритм имеет свои ограничения. Некоторые из них я упомянул в . своей предыдущей статье Мы не можем применить здесь классические BFS, DFS или даже Дейкстру, потому что наш граф может содержать отрицательные веса, что может привести к при перемещении по графу. Отрицательные циклы представляют собой проблему для алгоритма, поскольку он постоянно находит лучшие решения на каждой итерации. отрицательным циклам Чтобы решить эту проблему, алгоритм Беллмана-Форда просто ограничивает количество итераций. Он обходит каждое ребро графа за цикл и применяет релаксацию для всех ребер не более V-1 раз (где V — количество узлов). Таким образом, алгоритм Беллмана-Форда лежит в основе этой арбитражной системы, поскольку он позволяет обнаруживать пути между двумя узлами в графе, которые соответствуют двум важным критериям: они содержат отрицательные веса и не являются частью отрицательных циклов. Хотя этот алгоритм теоретически прост (и о нем можно найти миллиарды видеороликов), практическая реализация для наших нужд требует некоторых усилий. Давайте углубимся в это. Реализация алгоритма Беллмана-Форда Поскольку целью этой статьи является информатика, я буду использовать воображаемые обменные курсы, не имеющие ничего общего с реальными. Для более плавного знакомства с алгоритмом воспользуемся графом, вообще не содержащим отрицательных циклов: 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 В приведенном ниже примере кода находит путь между двумя узлами с использованием алгоритма Беллмана-Форда, когда в графе отсутствуют отрицательные циклы: 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; } } Выполнение этого кода для китайского юаня заполняет массив и дает такие результаты: _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) Как вы можете заметить, он определяет оптимальные пути между юанем и различными другими валютами. И опять же, я не буду зацикливаться на поиске только одного лучшего, так как это относительно простая задача, а не цель статьи. Приведенная выше реализация хорошо работает в идеальных случаях, но не работает с графами, содержащими отрицательные циклы. Обнаружение негативных циклов Что нам действительно нужно, так это способность определять, содержит ли граф отрицательные циклы, и если да, то выявлять проблемные сегменты. Эти знания позволяют нам смягчить эти проблемы и в конечном итоге обнаружить прибыльные цепочки. Число итераций не всегда должно достигать именно V - 1. Решение считается найденным, если на (N+1)-м цикле не обнаружено лучшего пути, чем путь на N-м цикле. Таким образом, есть место для небольшой оптимизации. Упомянутый ранее код можно улучшить, чтобы он не только находил пути, но и определял, содержит ли граф отрицательные циклы, включая упомянутую мной оптимизацию: 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; } А теперь мы поиграем с более сложным графиком, включающим отрицательные циклы: 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 Наша программа просто останавливается и выводит сообщение: Graph contains negative cycle. Нам удалось указать на проблему, однако нам необходимо ориентироваться по проблемным участкам графика. Как избежать негативных циклов Для этого мы пометим вершины, являющиеся частью отрицательных циклов, постоянным значением 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; } Теперь, если мы встретим NEG_INF в массиве _shortestPath, мы можем отобразить сообщение и пропустить этот сегмент, продолжая при этом находить оптимальные решения для других валют. Например, с узлом 0 (представляющим доллар США): 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) Ого! Наш код смог выявить ряд прибыльных цепочек, несмотря на то, что наши данные были «немного грязными». Все упомянутые выше примеры кода, включая тестовые данные, доступны вам на . моем GitHub Даже небольшие колебания имеют значение Давайте теперь закрепим то, что мы узнали. Учитывая список обменных курсов трех валют, мы можем легко обнаружить отрицательные циклы: 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); Результат: 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). Однако даже незначительные изменения обменных курсов (т.е. корректировки матрицы) могут привести к существенным различиям: // 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); Смотрите, мы нашли одну прибыльную цепочку: 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) Мы можем применить эти концепции к гораздо более крупным графикам, включающим несколько валют: 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); В результате мы можем найти несколько кандидатов на получение прибыли: 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) Однако есть два важных фактора: Время является решающим фактором при реализации арбитражных процессов, в первую очередь из-за быстрых колебаний цен на валюту. В результате срок действия вилки чрезвычайно короток. Платформы взимают комиссию за каждую транзакцию. Поэтому и имеют первостепенное значение, что достигается за счет ограничения длины вилки. минимизация временных затрат снижение комиссий Эмпирический опыт показывает, что приемлемая длина вилки обычно составляет от 2 до 3 пар. Помимо этого, возрастают вычислительные требования, а торговые платформы взимают более высокие комиссии. Таким образом, для получения дохода недостаточно иметь такие технологии, вам также необходим доступ к комиссиям низкого уровня. Обычно такой ресурс есть только у крупных финансовых учреждений. Автоматизация с использованием смарт-контрактов Я углубился в логику валютных операций и способы получения от них прибыли, но не коснулся технологий, используемых для выполнения этих операций. Хотя эта тема немного отклоняется от курса, я не мог не упомянуть о смарт-контрактах. Использование смарт-контрактов сегодня является одним из самых инновационных способов проведения валютных операций. Смарт-контракты позволяют совершать валютные операции в режиме реального времени без задержек и вмешательства человека (за исключением создания смарт-контракта). Solidity — это специализированный язык программирования для создания смарт-контрактов, автоматизирующих финансовые операции с использованием криптовалют. Мир смарт-контрактов динамичен и подвержен быстрым технологическим изменениям и меняющимся правилам. Это область с большой шумихой и значительными рисками, связанными с кошельками и соблюдением законодательства. Хотя, несомненно, есть талантливые люди и команды, получающие прибыль от этой области, существуют также регулирующие органы, стремящиеся обеспечить соблюдение рыночных правил. Почему мы изучаем это? Несмотря на сложность, неясность и непредсказуемость глобальной экономики, иностранная валюта остается скрытой движущей силой финансового мира. Это важнейший элемент, который позволяет тысячам компаний и миллионам людей по всему миру сотрудничать, предоставлять услуги и приносить друг другу взаимную выгоду мирным путем, преодолевая границы. Конечно, различные факторы, такие как политика, регулирование и центральные банки, влияют на обменные курсы и эффективность валютного обмена. Эти сложности усложняют финансовый ландшафт. Тем не менее, важно верить, что эти сложности служат более великой цели - общему благу. Многочисленные научные работы посвящены существованию и определению обменных курсов в мировой экономике, и вот лишь некоторые из них: Импортеры, экспортеры и разрыв обменного курса Выбор валюты и перенос обменного курса Загадки и политика обменного курса Эти статьи проливают свет на некоторые фундаментальные механизмы валютных операций, которые до сих пор трудно понять и уместить в одну модель. Тем не менее, игра с кодом и попытка найти решение практической проблемы помогли мне получить немного больше информации о ней. Надеюсь, вам понравилось это небольшое исследовательское путешествие так же, как и мне. Следите за обновлениями! Ссылки Исходный код со всеми этими примерами Седжвик Р. - Алгоритмы на C, Часть 5: Алгоритмы графов Реализация кода алгоритма Беллмана Форда Примеры Уильяма Фисета на GitHub — Беллман Форд о матрице смежности Примеры Уильяма Фисета на GitHub — Bellman Ford On Edge List Также опубликовано . здесь