Comercio de Arbitraje (Algoritmo Bellman-Ford)

El comercio en el intercambio generalmente se asocia con riesgos. Esto es absolutamente cierto para la mayoría de las estrategias comerciales. El éxito del comercio en estos casos está determinado únicamente por la capacidad de evaluar correctamente los riesgos y gestionarlos. Pero no todas las estrategias comerciales son. Existen estrategias libres de riesgos, que incluyen, en particular, el arbitraje. Este artículo explicará qué es el arbitraje y cómo implementarlo utilizando un algoritmo gráfico tan clásico como el algoritmo Bellman-Ford.

¿Qué es el arbitraje?

El arbitraje consiste en algunas transacciones relacionadas lógicamente destinadas a obtener ganancias de la diferencia de precios para los mismos activos o activos relacionados al mismo tiempo en diferentes mercados (arbitraje espacial), o en el mismo mercado en diferentes momentos (arbitraje temporal) .

Como un ejemplo simple, considere el arbitraje espacial. En Nueva York y Londres, se pueden hacer tratos para comprar dólares por euros y euros por dólares. En Nueva York, esto se puede hacer a razón de 4 dólares por 3 euros, y en Londres, a razón de 5 dólares por 3 euros. Esta diferencia en las tasas abre la posibilidad de arbitraje espacial.



Con 4 dólares, en Nueva York puedes comprar 3 euros. Después de eso, en Londres, compre por estos 3 euros 5 dólares. Como puede ver, una secuencia tan simple de transacciones genera una ganancia de 1 dólar por cada 4 dólares invertidos. En consecuencia, si inicialmente hay $ 4 millones, la ganancia ya estará en un millón.

Cuando los tipos de cambio (no consideramos el diferencial) para el mismo par de divisas difieren, la secuencia de transacciones requerida para implementar la estrategia de arbitraje es muy simple. Si el tipo de cambio para un par de divisas es fijo, pero varios pares de divisas se negocian en paralelo, también es posible el arbitraje, pero la secuencia de transacciones ya no será trivial. Por ejemplo, puede comprar 4 euros por 5 dólares, 3 libras por 4 euros y luego 6 dólares por 3 libras. El beneficio de dicha secuencia de transacciones será de $ 1 por cada 5 dólares invertidos.



Cientos de pares de divisas pueden negociarse en el intercambio, y los tipos de cambio cambian constantemente. Ya es imposible entender qué secuencia de transacciones generará ganancias sin una solución algorítmica.

Transición al problema algorítmico

Imagine posibles transacciones de cambio de divisas en forma algorítmica, es decir, en forma de gráfico. Los vértices en este gráfico representan monedas, y los bordes son operaciones potenciales. La longitud de la costilla corresponde al tipo de cambio al que se puede concluir la transacción.


La siguiente pregunta es cómo encontrar una secuencia de transacciones en una columna que genere ganancias. Obviamente, dado que al comienzo de la secuencia y al final debe ser la misma moneda, la secuencia debe corresponder al ciclo en el gráfico dado. A continuación, debe determinar cómo se calcula el tipo de cambio entre las dos monedas, si no se intercambian directamente, sino a través de una determinada tercera moneda (o un número arbitrario de operaciones intermedias). Todo aquí también es bastante simple. Tal tipo de cambio se calculará como el producto de los tipos de cambio de las transacciones intermedias. Se convierte en una secuencia rentable de transacciones si este producto toma un valor menor que uno. En otras palabras, si una unidad de moneda se puede comprar menos que una unidad de la misma moneda.


Los algoritmos gráficos clásicos son poco adecuados para trabajar con productos de longitudes de borde. Dichos algoritmos están orientados principalmente a encontrar una ruta que se define como la suma de estas longitudes. Sin embargo, para evitar esta limitación, hay una forma matemática de pasar de un producto a una suma. De esta manera es el logaritmo. Si el producto aparece debajo del logaritmo, entonces dicho logaritmo se puede convertir en la suma de los logaritmos. En el lado derecho de esta ecuación, el número deseado es menor que uno, lo que significa que el logaritmo de este número debe ser menor que cero.




Un truco matemático tan simple le permite pasar de buscar un ciclo cuyo producto de longitudes de arista sea menor que uno a encontrar un ciclo cuya suma de longitudes de arista sea menor que cero. Tal tarea ya parece más solucionable mediante algoritmos gráficos clásicos, y más precisamente el algoritmo Bellman-Ford.

Bellman - Algoritmo de Ford

El algoritmo de Bellman-Ford se usa generalmente para encontrar la distancia desde un vértice dado a todos los demás vértices de un gráfico, pero su modificación permite encontrar ciclos de longitud negativa.

La operación básica de este algoritmo es la relajación del borde. La esencia de esta operación es la siguiente. Supongamos que hay un borde$$$a \rightarrow b$, y también se conocen los valores preliminares calculados previamente de las distancias a los picos $$$a$y $$$b$. Para realizar la relajación del borde, es necesario calcular cuál sería la distancia a la cima$$$b$si el camino pasara por la cima $$$a$y costilla $$$a \rightarrow b$. Esta distancia se calcula como la suma de la distancia a la cima.$$$a$ y longitudes de costilla $$$a \rightarrow b$. Además, si esta distancia es menor que la distancia preliminar actual a$$$a$entonces esta es la distancia a $$$a$Corresponde y toma un nuevo valor, recién calculado.

El resto del algoritmo también es sencillo. Necesario$$$N$ veces ($$$N$Es el número de vértices del gráfico) omite la lista de aristas, aplicando una operación de relajación para cada ronda. Se obtiene la complejidad del algoritmo.$$$N*M$ (Dónde $$$N$- el número de vértices, y $$$M$- número de costillas). Para un gráfico sin ciclos negativos, una mayor relajación del borde no conducirá a un cambio en la distancia a los vértices. Al mismo tiempo, para un gráfico que contiene un ciclo negativo, la relajación reducirá la distancia a los vértices y después$$$N$desvíos Esta propiedad se puede usar para encontrar el ciclo deseado.

La siguiente implementación pequeña del algoritmo descrito anteriormente en Kotlin debería ayudar a aquellos que están más familiarizados con la clasificación del 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
    }
}

Examinemos un ejemplo con un gráfico pequeño, que incluye un ciclo de longitud negativa. Para que el algoritmo funcione, es necesario que cada vértice mantenga la distancia conocida actual a él, así como un enlace a su vértice anterior. La referencia al vértice anterior en este caso está determinada por la relajación exitosa de la costilla. Si la operación de relajación fue exitosa y la distancia al vértice se actualizó, entonces el enlace al vértice anterior de este vértice también se actualiza y toma el valor del vértice de origen del borde especificado.

Entonces, primero debe inicializar los vértices configurando la distancia a todos los vértices, excepto el infinito inicial igual. Para el vértice inicial, se establece una distancia de cero.


Sigue la primera ronda de todas las costillas y se realiza su relajación. Casi toda la relajación no da ningún resultado, excepto la relajación de las costillas.$$$a \rightarrow b$. La relajación de esta costilla le permite actualizar la distancia a$$$b$.


Esto es seguido por la segunda ronda de todos los bordes del gráfico y la relajación correspondiente. Esta vez, el resultado es la relajación de las costillas.$$$b \rightarrow c$y $$$b \rightarrow d$. Las distancias a los picos se actualizan.$$$c$ y $$$d$. Cabe señalar aquí que el resultado depende del orden en que se atraviesan los bordes.


En la tercera ronda de costillas, es posible relajar con éxito tres costillas, a saber, las costillas. $$$\rightarrow d$, $$$d \rightarrow e$, $$$d \rightarrow b$. En este caso, cuando las costillas están relajadas$$$\rightarrow d$ y $$$d \rightarrow b$distancias ya registradas a $$$d$y $$$b$, así como los enlaces correspondientes a vértices anteriores.


En la cuarta ronda, las operaciones de relajación de costillas se completan con éxito. $$$b \rightarrow c$y $$$b \rightarrow a$. En este caso, los valores ya registrados de distancias a los picos se actualizan nuevamente.$$$a$ y $$$c$, así como los enlaces correspondientes a vértices anteriores.


La quinta ronda es la última. Las costillas se relajan durante esta caminata$$$\rightarrow d$, $$$d \rightarrow b$, $$$d \rightarrow e$. Aquí puede ver que la presencia de un ciclo de longitud negativa ya hace ciertos ajustes a los valores de las distancias a los picos.


Después de este recorrido, si el gráfico no contuviera un ciclo de longitud negativa, el algoritmo se completaría, ya que la relajación de cualquier borde no habría hecho ningún cambio. Sin embargo, para este gráfico, debido a la presencia de un ciclo de longitud negativa, todavía se puede encontrar un borde cuya relajación actualizará la distancia a uno de los vértices.


Se encuentra un borde cuya relajación actualiza la distancia a la cumbre. Esto confirma la presencia de un ciclo de longitud negativa. Ahora necesita encontrar este ciclo en sí mismo. Es importante que el vértice, la distancia a la que ahora se actualiza, pueda estar tanto dentro del ciclo como fuera de él. En el ejemplo, esta es la parte superior$$$e$y ella está fuera de ciclo. A continuación, debe consultar los enlaces a los vértices anteriores, que se actualizaron cuidadosamente en todos los pasos del algoritmo. Para garantizar la entrada en el ciclo, debe retroceder$$$N$picos usando estos enlaces.

En este ejemplo, las transiciones serán las siguientes:$$$e \rightarrow d \rightarrow c \rightarrow b \rightarrow d \rightarrow c$. Entonces la parte superior está ubicada$$$c$, que está garantizado en un ciclo de longitud negativa.


Además, una cuestión de tecnología. Para devolver el ciclo deseado, debe iterar nuevamente utilizando los enlaces a los vértices anteriores hasta que el vértice se encuentre nuevamente$$$c$. Esto significará que el ciclo se ha cerrado. Todo lo que queda es invertir el orden, ya que la iteración se invirtió durante las iteraciones sobre enlaces a vértices anteriores.

El algoritmo anterior supone la presencia de algún vértice inicial a partir del cual se calculan las distancias. La presencia de tal vértice no es necesaria para que el algoritmo funcione, pero se introdujo en mayor medida para que coincida con el algoritmo original de Bellman - Ford. Si el tema de interés es un ciclo de longitud negativa, entonces podemos suponer que todos los vértices de un gráfico dado son iniciales. En otras palabras, que la distancia a todos los vértices es inicialmente cero.

Conclusión

El uso del algoritmo Bellman-Ford en el problema del comercio de arbitraje es un excelente ejemplo de cómo los algoritmos clásicos pueden resolver problemas comerciales reales, en particular, en el ámbito financiero. Complejidad asintótica del algoritmo, igual a$$$N^3$para un gráfico completamente conectado, puede resultar bastante grande. Esto realmente necesita ser recordado. Sin embargo, en muchos casos, como el cambio de divisas, esta complejidad no crea ningún problema debido al número relativamente pequeño de nodos en el gráfico.