Negociação de arbitragem (algoritmo de Bellman-Ford)

A negociação na bolsa geralmente está associada a riscos. Isso é absolutamente verdade para a maioria das estratégias de negociação. O sucesso do comércio nesses casos é determinado apenas pela capacidade de avaliar e gerenciar corretamente os riscos. Mas nem todas as estratégias de negociação são. Existem estratégias sem risco, que incluem, em particular, arbitragem. Este artigo explicará o que é a arbitragem e como implementá-la usando um algoritmo gráfico clássico como o algoritmo Bellman-Ford.

O que é arbitragem?

Arbitragem são algumas transações logicamente relacionadas que visam lucrar com a diferença de preços para os mesmos ativos ou ativos relacionados ao mesmo tempo em diferentes mercados (arbitragem espacial) ou no mesmo mercado em diferentes momentos (arbitragem temporária) .

Como um exemplo simples, considere a arbitragem espacial. Em Nova York e Londres, é possível fazer acordos para comprar dólares por euros e euros por dólares. Em Nova York, isso pode ser feito à taxa de 4 dólares por 3 euros e em Londres - à taxa de 5 dólares por 3 euros. Essa diferença de taxas abre a possibilidade de arbitragem espacial.



Com 4 dólares, em Nova York você pode comprar 3 euros. Depois disso, em Londres, compre por esses 3 euros e 5 dólares. Como você pode ver, uma sequência tão simples de transações gera lucro de 1 dólar por cada 4 dólares investidos. Assim, se inicialmente houver US $ 4 milhões, o lucro já será de um milhão.

Quando as taxas de câmbio (não consideramos o spread) para o mesmo par de moedas diferem, a sequência de transações necessária para implementar a estratégia de arbitragem é muito simples. Se a taxa de câmbio de um par de moedas é fixa, mas vários pares de moedas são negociados em paralelo, a arbitragem também é possível, mas a sequência de transações já não será trivial. Por exemplo, você pode comprar 4 euros por 5 dólares, 3 libras por 4 euros e 6 dólares por 3 libras. O lucro dessa sequência de transações será de US $ 1 para cada 5 dólares investidos.



Centenas de pares de moedas podem ser negociados na bolsa, e as taxas de câmbio estão mudando constantemente. Já é impossível entender qual sequência de transações trará lucro sem uma solução algorítmica.

Transição para o problema algorítmico

Imagine possíveis transações de câmbio de moeda em uma forma algorítmica, ou seja, na forma de um gráfico. Os vértices neste gráfico representam moedas e as arestas são transações em potencial. O comprimento da nervura corresponde à taxa de câmbio na qual a transação pode ser concluída.


A próxima pergunta é como encontrar uma sequência de transações em uma coluna que trará lucro. Obviamente, uma vez que no início da sequência e no final deve ser a mesma moeda, a sequência deve corresponder ao ciclo no gráfico fornecido. Em seguida, você precisa determinar como a taxa de câmbio entre as duas moedas é calculada, se não forem trocadas diretamente, mas por meio de uma determinada terceira moeda (ou um número arbitrário de operações intermediárias). Tudo aqui também é bastante simples. Essa taxa de câmbio será calculada como o produto das taxas de câmbio das transações intermediárias. Uma sequência lucrativa de transações se torna se este produto tiver um valor menor que um. Em outras palavras, se uma unidade de moeda puder ser comprada menos que uma unidade da mesma moeda.


Os algoritmos clássicos de gráficos são pouco adequados para trabalhar com produtos de comprimentos de arestas. Esses algoritmos são direcionados principalmente para encontrar um caminho definido como a soma desses comprimentos. No entanto, para contornar essa limitação, existe uma maneira matemática de passar de um produto para uma soma. Desta forma é logaritmo. Se o produto aparecer no logaritmo, esse logaritmo poderá ser convertido na soma dos logaritmos. No lado direito desta equação, o número desejado é menor que um, o que significa que o logaritmo desse número deve ser menor que zero.




Um truque matemático simples permite que você passe da pesquisa de um ciclo cujo produto dos comprimentos da borda seja menor que um para encontrar um ciclo cuja soma dos comprimentos da borda seja menor que zero. Essa tarefa já parece mais solucionável pelos algoritmos clássicos de grafos e, mais precisamente, pelo algoritmo Bellman-Ford.

Bellman - Algoritmo de Ford

O algoritmo de Bellman-Ford é geralmente usado para encontrar a distância de um determinado vértice a todos os outros vértices de um gráfico, mas sua modificação permite encontrar ciclos de comprimento negativo.

A operação básica deste algoritmo é o relaxamento da borda. A essência desta operação é a seguinte. Suponha que exista uma vantagem$$$a \rightarrow b$, e também os valores preliminares calculados anteriormente das distâncias aos picos são conhecidos $$$a$e $$$b$. Para realizar o relaxamento da borda, é necessário calcular qual seria a distância até o topo$$$b$se o caminho passou pelo topo $$$a$e costela $$$a \rightarrow b$. Esta distância é calculada como a soma da distância até o topo.$$$a$ e comprimentos de costela $$$a \rightarrow b$. Além disso, se essa distância for menor que a distância preliminar atual para$$$a$então esta é a mesma distância para $$$a$Corresponde e assume um novo valor, apenas calculado.

O restante do algoritmo também é simples. Necessário$$$N$ vezes ($$$N$É o número de vértices do gráfico) ignora a lista de arestas, aplicando uma operação de relaxamento para cada rodada. A complexidade do algoritmo é obtida$$$N*M$ (Onde $$$N$- o número de vértices, e $$$M$- número de costelas). Para um gráfico sem ciclos negativos, um maior relaxamento da aresta não levará a uma alteração na distância dos vértices. Ao mesmo tempo, para um gráfico contendo um ciclo negativo, o relaxamento reduzirá a distância dos vértices e depois$$$N$desvios. Esta propriedade pode ser usada para encontrar o ciclo desejado.

A pequena implementação a seguir do algoritmo descrito acima no Kotlin deve ajudar aqueles que estão mais familiarizados com a classificação do código.

fun findNegativeCycle(nodes: Int, edges: Array<Edge>, source: Int): List<Int>? {
    // 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
    }
}

Vamos examinar um exemplo com um pequeno gráfico, que inclui um ciclo de comprimento negativo. Para que o algoritmo funcione, é necessário que cada vértice mantenha a distância conhecida atual, bem como um link para o vértice anterior. A referência ao vértice anterior, neste caso, é determinada pelo relaxamento bem-sucedido da costela. Se a operação de relaxamento foi bem-sucedida e a distância para o vértice foi atualizada, o link para o vértice anterior desse vértice também é atualizado e assume o valor do vértice de origem da aresta especificada.

Portanto, primeiro você precisa inicializar os vértices, definindo a distância para todos os vértices, exceto o infinito inicial igual. Para o vértice inicial, uma distância de zero é definida.


A primeira rodada de todas as costelas segue e seu relaxamento é realizado. Quase todo relaxamento não produz nenhum resultado, exceto o relaxamento das costelas$$$a \rightarrow b$. O relaxamento dessa costela permite que você atualize a distância para$$$b$.


Isto é seguido pela segunda rodada de todas as arestas do gráfico e o relaxamento correspondente. Desta vez, o resultado é relaxamento das costelas.$$$b \rightarrow c$e $$$b \rightarrow d$. As distâncias para os picos são atualizadas.$$$c$ e $$$d$. Deve-se notar aqui que o resultado depende da ordem em que as arestas são atravessadas.


Na terceira rodada de costelas, é possível relaxar com sucesso três costelas, ou seja, as costelas $$$\rightarrow d$, $$$d \rightarrow e$, $$$d \rightarrow b$. Nesse caso, quando as costelas estão relaxadas$$$\rightarrow d$ e $$$d \rightarrow b$distâncias já registradas $$$d$e $$$b$, bem como links correspondentes para vértices anteriores.


Na quarta rodada, as operações de relaxamento das costelas são concluídas com sucesso. $$$b \rightarrow c$e $$$b \rightarrow a$. Nesse caso, os valores já registrados das distâncias para os picos são novamente atualizados.$$$a$ e $$$c$, bem como os links correspondentes aos vértices anteriores.


A quinta rodada é a última. Costelas relaxam durante esta caminhada$$$\rightarrow d$, $$$d \rightarrow b$, $$$d \rightarrow e$. Aqui você pode ver que a presença de um ciclo de comprimento negativo já faz alguns ajustes nos valores das distâncias aos picos.


Após esse passeio, se o gráfico não contivesse um ciclo de comprimento negativo, o algoritmo seria concluído, pois o relaxamento de qualquer aresta não teria feito nenhuma alteração. No entanto, para este gráfico, devido à presença de um ciclo de comprimento negativo, ainda é possível encontrar uma aresta cujo relaxamento atualizará a distância para um dos vértices.


Uma aresta cujo relaxamento atualiza a distância até o cume é encontrada. Isso confirma a presença de um ciclo de duração negativa. Agora você precisa encontrar esse próprio ciclo. É importante que o vértice, cuja distância agora é atualizada, possa estar dentro e fora do ciclo. No exemplo, este é o topo$$$e$e ela está fora de ciclo. Em seguida, é necessário consultar os links para os vértices anteriores, que foram cuidadosamente atualizados em todas as etapas do algoritmo. Para garantir a entrada no ciclo, você deve voltar atrás$$$N$picos usando esses links.

Neste exemplo, as transições serão as seguintes:$$$e \rightarrow d \rightarrow c \rightarrow b \rightarrow d \rightarrow c$. Então o topo está localizado$$$c$, o que é garantido como um ciclo de duração negativa.


Além disso, uma questão de tecnologia. Para retornar o ciclo desejado, você precisa iterar novamente usando os links dos vértices anteriores até que o vértice se encontre novamente$$$c$. Isso significa que o ciclo foi fechado. Tudo o que resta é reverter a ordem, pois a iteração foi revertida durante as iterações nos links para os vértices anteriores.

O algoritmo acima pressupõe a presença de algum vértice inicial a partir do qual as distâncias são calculadas. A presença de um vértice desse tipo não é necessária para o algoritmo funcionar, mas foi introduzida em maior extensão para corresponder ao algoritmo original de Bellman-Ford. Se o assunto de interesse é um ciclo de comprimento negativo, podemos assumir que todos os vértices de um determinado gráfico são iniciais. Em outras palavras, que a distância para todos os vértices é inicialmente zero.

Conclusão

O uso do algoritmo Bellman-Ford no problema da negociação de arbitragem é um excelente exemplo de como os algoritmos clássicos podem resolver problemas reais de negócios, em particular na esfera financeira. Complexidade assintótica do algoritmo, igual a$$$N^3$para um gráfico totalmente conectado, pode ser bastante grande. Isso realmente precisa ser lembrado. No entanto, em muitos casos, como a troca de moeda, essa complexidade não cria problemas devido ao número relativamente pequeno de nós no gráfico.