Арбитражная торговля (Алгоритм Беллмана — Форда)09.04.2020 15:34

Торговля на бирже обычно ассоциируется с рисками. Это совершенно верно для большинства торговых стратегий. Успешность торговли в этих случаях определяется исключительно способностью верно оценивать риски и управлять ими. Но не все торговые стратегии таковы. Существуют безрисковые стратегии, к которым относится, в частности, арбитраж. В этой статье будет рассказано, что такое арбитраж, и как реализовать его с использованием такого классического алгоритма на графе, как алгоритм Беллмана — Форда.

Что такое арбитраж

Арбитраж — это несколько логически связанных сделок, направленных на извлечение прибыли из разницы в ценах на одинаковые или связанные активы в одно и то же время на разных рынках (пространственный арбитраж), либо на одном и том же рынке в разные моменты времени (временной арбитраж).

В качестве простого примера рассмотрим пространственный арбитраж. В Нью-Йорке и Лондоне можно заключить сделки по покупке долларов за евро и евро за доллары. В Нью-Йорке это можно делать по курсу 4 доллара за 3 евро, а в Лондоне — по курсу 5 долларов за 3 евро. Такая разница курсов открывает возможность для пространственного арбитража.

Имея 4 доллара, в Нью-Йорке на них можно купить 3 евро. После этого в Лондоне купить за эти 3 евро 5 долларов. Как можно заметить, такая несложная последовательность сделок приносит 1 доллар прибыли на каждые вложенные 4 доллара. Соответственно, если изначально имеется 4 миллиона долларов, то и прибыль будет уже в миллион.

Когда обменные курсы (спред не рассматриваем) для одной и той же валютной пары отличаются, то последовательность сделок, необходимых для реализации арбитражной стратегии, очень простая. В случае, если курс для одной валютной пары фиксирован, но торгуются несколько валютных пар параллельно, арбитраж также возможен, но последовательность сделок уже будет нетривиальной. К примеру, можно купить 4 евро за 5 долларов, 3 фунта за 4 евро, а потом 6 долларов за 3 фунта. Прибыль от такой последовательности сделок составит 1 доллар на каждые 5 вложенных долларов.

На бирже могут торговаться сотни валютных пар, а обменные курсы постоянно меняются. Понять, какая последовательность сделок принесёт прибыль, без алгоритмического решения в этом случае уже невозможно.

Переход к алгоритмической задаче

Представим потенциальные сделки обмена валюты в алгоритмическом виде, а именно в виде графа. Вершины в этом графе представляют валюты, а ребра являются возможными сделками. Длина же ребра соответствует обменному курсу, по которому данную сделку можно заключить.

Далее встает вопрос, как в таком графе найти последовательность сделок, которая принесет прибыль. Очевидно, что так как в начале последовательности и в её конце должна быть одна и та же валюта, то последовательность должна соответствовать циклу в заданном графе. Далее необходимо определиться с тем, как вычисляется обменный курс между двумя валютами, если они обмениваются не напрямую, а через некую третью валюту (или произвольное количество промежуточных операций). Тут всё тоже достаточно просто. Такой обменный курс будет вычисляться как произведение обменных курсов промежуточных сделок. Прибыльной последовательность сделок становится, если это произведение принимает значение меньше нуля. Другими словами, если единицу валюты можно купить меньше, чем за единицу этой же самой валюты.

Классические алгоритмы на графах плохо подходят для работы с произведением длин ребер. Такие алгоритмы, в основном, заточены на нахождение пути, который определяется как сумма этих длин. Однако для обхода этого ограничения существует математический способ перейти от произведения к сумме. Таким способом является логарифмирование. Если под логарифмом оказывается сумма, то такой логарифм может быть преобразован в сумму логарифмов. В правой же части этого уравнения желаемым является число меньшее единицы, а значит, логарифм этого числа должен быть меньше нуля.

Такой простой математический трюк позволяет перейти от поиска цикла, произведение длин ребер которого меньше единицы, к поиску цикла, сумма длин ребер которого меньше нуля. Такая задача уже выглядит более решаемой классическими графовыми алгоритмами, а точнее алгоритмом Беллмана — Форда.

Алгоритм Беллмана — Форда

Алгоритм Беллмана — Форда обычно используется для нахождения расстояния от заданной вершины до всех остальных вершин некоторого графа, однако его модификация позволяет найти и циклы отрицательной длины.

Базовой операцией этого алгоритма является релаксация ребер. Суть данной операции следующая. Допустим, что имеется ребро $a \rightarrow b$ , а еще известны вычисленные ранее предварительные значения расстояний до вершин $a$ и $b$ . Для выполнения релаксации ребра требуется вычислить, какое получилось бы расстояние до вершины $b$ , если бы путь проходил через вершину $a$ и ребро $a \rightarrow b$ . Это расстояние вычисляется как сумма расстояния до вершины $a$ и длины ребра $a \rightarrow b$ . Далее, если это расстояние оказывается меньше текущего предварительного расстояния до $a$ , то это самое расстоние до $a$ переписывается и принимает новое, только что вычисленное, значение.

Остальной алгоритм тоже несложен. Необходимо $N$ раз ( $N$ — это количество вершин графа) обойти список ребер, при каждом обходе применяя операцию релаксации. Сложность алгоритма при этом получается $N*M$ (где $N$ — количество вершин, а $M$ — количество ребер). Для графа без отрицательных циклов дальнейшие релаксации ребер не приведут к изменению расстояний до вершин. В то же время, для графа, содержащего отрицательный цикл, релаксации будут уменьшать расстояние до вершин и после $N$ обходов. Это свойство может быть использовано использовано для нахождения искомого цикла.

Тем, кому привычнее разбираться с кодом, должна помочь следующая небольшая реализация описанного выше алгоритма на Kotlin’е.

fun findNegativeCycle(nodes: Int, edges: Array, source: Int): List? {
    // Initialize distances and prev arrays. All distances but the distance to
    // the source node are infinite, distance to the source node is zero.
    val distances = DoubleArray(nodes) { if (it == source) 0.0 else INFINITY }
    val prev = IntArray(nodes) { -1 }

    // Relax all edges N times where N is the number of nodes.
    repeat(nodes) {
        edges.forEach { it.relax(distances, prev) }
    }

    // Try to relax at least one more edge. If it's possible memorize the node,
    // otherwise return from the method.
    val firstRelaxedEdge = edges.firstOrNull { it.relax(distances, prev) }
    var node = firstRelaxedEdge?.to ?: return null

    // Step back N times where N is the number of nodes. As a result, the node will
    // be in the loop for sure.
    repeat(nodes) {
        node = prev[node]
    }

    // Recover the loop by the node that is inside it and prev links.
    val lastNode = node
    return buildList {
        do {
            add(node)
            node = prev[node]
        } while (node != lastNode)

        reverse()
    }
}

// Edge DTO with implemented relaxation operation.
data class Edge(val from: Int, val to: Int, val length: Double) {

    fun relax(distances: DoubleArray, prev: IntArray): Boolean {
        if (distances[from] + length >= distances[to]) {
            return false
        }

        distances[to] = distances[from] + length
        prev[to] = from
        return true
    }
}

Разберем пример с небольшим графом, в состав которого входит цикл отрицательной длины. Для работы алгоритма необходимо для каждой вершины поддерживать текущее известное расстояние до неё, а так же ссылку на её предыдущую вершину. Ссылка на предыдущая вершина в данном случае определяется успешной релаксацией ребра. Если операция релаксации прошла успешно, и дистанция до вершины была обновлена, то ссылка на предыдущую вершина этой вершины также обновляется и принимает значение вершины-источника заданного ребра.

Итак, для начала необходимо инициализировать вершины, установив дистанцию до всех вершин кроме начальной равной бесконечности. Для начальной вершины устанавливается дистанция равная нулю.

Далее следует первый обход всех ребер и выполняются их релаксации. Практически все релаксации не дают никакого результата, кроме релаксации ребра $a \rightarrow b$ . Релаксация данного ребра позволяет обновить расстояние до $b$ .

Далее следует второй обход всех рёбер графа и соответствующие релаксации. На этот раз результат дают релаксации ребер $b \rightarrow c$ , а также $b \rightarrow d$ . Обновляются расстояния до вершин $c$ и $d$ . Тут следует заметить, что результат зависит от того, в каком порядке происходит обход ребер.

При третьем обходе ребер удается успешно релаксировать уже три ребра, а именно ребра $с \rightarrow d$ , $d \rightarrow e$ , $d \rightarrow b$ . При этом, при релаксации ребер $с \rightarrow d$ и $d \rightarrow b$ обновляются уже записанные ранее расстояния до $d$ и $b$ , а так же соответствующие ссылки на предыдущие вершины.

При четвертом обходе успешно заканчиваются операции релаксации ребер $b \rightarrow c$ и $b \rightarrow a$ . При этом опять обновляются уже записанные значения расстояний до вершин $a$ и $c$ , как и соответствующие ссылки на предыдущие вершины.

Пятый обход является последним. При этом обходе релаксируются ребра $с \rightarrow d$ , $d \rightarrow b$ , $d \rightarrow e$ . Тут можно заметить, что наличие цикла отрицательной длины уже вносит определенные корректировки в значения расстояний до вершин.

После этого обхода, если бы граф не содержал цикла отрицательной длины, алгоритм был бы закончен, так как релаксация любого ребра уже не внесла бы никаких изменений. Однако для данного графа из-за наличия цикла отрицательной длины, все еще можно найти ребро, релаксация которого обновит значения расстояния до одной из вершин.

Ребро, релаксация которого обновляет расстояние до вершины, найдено. Это подтверждает наличие цикла отрицательной длины. Теперь необходимо найти сам этот цикл. Важно, что вершина, расстояние до которой сейчас обновилось, может быть как внутри цикла, так и вне него. В примере это вершина $e$ и она вне цикла. Далее необходимо обратиться к ссылкам на предыдущие вершины, которые аккуратно обновлялись на всех шагах алгоритма. Чтобы гарантированно попасть в цикл, необходимо отступить назад на $N$ вершин, пользуясь этими ссылками.

В данном примере переходы будут следующие: $e \rightarrow d \rightarrow c \rightarrow b \rightarrow d \rightarrow c$ . Таким образом находится вершина $c$ , которая гарантированно лежит в цикле отрицательной длины.

Далее дело техники. Чтобы вернуть искомый цикл, нужно опять итерироваться по ссылкам на предыдущие вершины, пока опять не встретится вершина $c$ . Это будет значить, что цикл замкнулся. Остается только изменить порядок на обратный, так как при итерациях по ссылкам на предыдущие вершины порядок был инвертирован.

В приведенном алгоритме предполагается наличие некоторой изначальной вершины, от которой рассчитываются расстояния. Наличие такой вершины не является обязательным для работы алгоритма, а введена она в большей степени для соответствия изначальному алгоритму Беллмана — Форда. Если же предметом интереса является цикл отрицательной длины, то можно считать, что все вершины заданного графа являются начальными. Другими словами, что дистанция до всех вершин изначально равна нулю.

Заключение

Использование алгоритма Беллмана — Форда в задаче арбитражной торговли является отличным примером того, как классические алгоритмы позволяют решать реальные проблемы бизнеса, в частности, в финансовой сфере. Асимптотическая сложность алгоритма, равная $N^3$ для полносвязного графа, может оказаться достаточно большой. Об этом действительно нужно помнить. Однако во многих случаях, таких как обмен валюты, эта сложность не создает никаких проблем в связи с относительно малым количеством узлов в графе.