Im Anschluss an meine früheren Bemühungen spiele ich weiterhin mit Graphen und Graph-Traversal-Algorithmen auf der Suche nach einer Möglichkeit für einen profitablen Währungsumtausch.
Wenn Sie mit der FinTech-Startup-Branche vertraut sind, haben Sie vielleicht schon von Revolut gehört, einem bekannten FinTech-Riesen mit Sitz in London, Großbritannien. Revolut wurde 2015 gegründet, hat erhebliche Investitionen eingesammelt und ist zu einem der am schnellsten wachsenden Startups im Vereinigten Königreich geworden, das vielen europäischen Bürgern Bankdienstleistungen anbietet.
Während Bankgeschäfte oft im Dunkeln liegen, wenn es darum geht, wie sie Einnahmen generieren, geben einige Schlüsselzahlen zu Revolut für die Jahre 2020 und 2021 Aufschluss über ihre Einnahmequellen:
Wie dargestellt, stammt ein erheblicher Teil der Einnahmen dieser Neobank aus Devisen (FX), Vermögensverwaltung (einschließlich Kryptowährungen) und Kartendienstleistungen. Bemerkenswert ist, dass Devisen im Jahr 2021 zum profitabelsten Sektor wurden.
Ein Freund von mir, der auch Software-Ingenieur ist, erzählte einmal eine interessante Geschichte über sein technisches Vorstellungsgespräch in der Software-Engineering-Abteilung von Revolut vor ein paar Jahren. Er wurde damit beauftragt, einen Algorithmus zu entwickeln, um die profitabelste Methode zur Umrechnung zweier Währungen mithilfe einer oder mehrerer Zwischenwährungen zu ermitteln. Mit anderen Worten, sie suchten nach einer Strategie für Währungsarbitrage.
Währungsarbitrage ist eine Handelsstrategie, bei der ein Devisenhändler durch mehrere Geschäfte unterschiedliche Spreads nutzt, die von Brokern für ein bestimmtes Währungspaar angeboten werden.
In der Aufgabe wurde ausdrücklich erwähnt, dass die Grundlage des Algorithmus in der Graphentheorie verwurzelt sein muss.
FX-Grundlagen
Devisen oder Devisen spielen eine zentrale Rolle im globalen Handel und untermauern das Funktionieren unserer vernetzten Welt. Es ist offensichtlich, dass Devisen auch eine wesentliche Rolle dabei spielen, Banken zu den reichsten Organisationen zu machen.
Der aus dem Devisenhandel erzielte Gewinn ist in erster Linie die Differenz oder Spanne zwischen den Kauf- (BID) und Verkaufspreisen (ASK). Während dieser Unterschied pro Transaktion winzig erscheinen mag, kann er sich angesichts des täglichen Geschäftsvolumens zu Gewinnen in Millionenhöhe summieren. Dies ermöglicht es einigen Unternehmen, ausschließlich von diesen hochautomatisierten Finanzvorgängen zu profitieren.
Im Bereich FX (Foreign Exchange) arbeiten wir immer mit Währungspaaren, wie zum Beispiel EUR/USD. In den meisten Fällen sind diese Börsen bidirektional (d. h. EUR/USD und USD/EUR), und der Wechselkurswert ist in jede Richtung unterschiedlich.
Ein Arbitrage-Paar stellt ein numerisches Verhältnis zwischen den Werten zweier Währungen (z. B. EUR und US-Dollar) dar und bestimmt den Wechselkurs zwischen ihnen.
Potenziell können wir mehrere Zwischenwährungen für einen profitablen Handel nutzen, was als sichere Wette bezeichnet wird.
Bei einer Arbitrage-Sure-Wette handelt es sich um eine Reihe von Paaren, die kreisförmig verwendet werden.
Viele Anbieter nutzen mathematische Modelle und Analysen, um ihre eigenen Gewinne zu sichern und zu verhindern, dass andere davon profitieren. Daher wird der Begriff potenziell hier hervorgehoben.
Die sichere Einsatzlänge bezieht sich auf die Anzahl der Paare, die eine Reihe potenzieller Arbitragemöglichkeiten darstellen.
In der realen Welt können die Wechselkurse zwischen verschiedenen Banken oder Börsenplattformen variieren. Es ist nicht ungewöhnlich, dass Touristen eine Stadt durchqueren, um den bestmöglichen Tarif zu finden. Mit Computersoftware kann dieser Vorgang innerhalb von Millisekunden durchgeführt werden, wenn Sie Zugriff auf eine Liste von Anbietern haben. Bei praktischen, gewinnbringenden Geschäften können mehrere Schritte Umrechnungen in verschiedene Währungen auf verschiedenen Börsenplattformen umfassen. Mit anderen Worten: Der Arbitrage-Kreis kann recht umfangreich sein.
Beim Arbitrage Circle geht es darum, eine Währung zu erwerben, sie auf eine andere Plattform zu übertragen, einen Umtausch gegen andere Währungen durchzuführen und schließlich zur ursprünglichen Währung zurückzukehren.
Der Wechselkurs zwischen zwei Währungen über eine oder mehrere Zwischenwährungen wird als Produkt der Wechselkurse dieser Zwischentransaktionen berechnet.
Ein Beispiel
Stellen wir uns zum Beispiel vor, wir möchten Schweizer Franken für US-Dollar kaufen, dann Franken in japanische Yen umtauschen und dann Yen wieder für US-Dollar verkaufen. Im Herbst 2023 gelten folgende Wechselkurse:
Wir können 0,91 CHF (Schweizer Franken) für 1 USD kaufen.
Wir können 163,16 japanische Yen für 1 CHF kaufen.
Wir können 0,0067 USD für 1 japanischen Yen kaufen.
Jetzt müssen wir ein Produkt dieser Werte finden. Eine Folge von Transaktionen wird profitabel, wenn dieses Produkt einen Wert kleiner als eins ergibt :
Wie wir sehen können, ist das Ergebnis größer als eins, es sieht also so aus, als hätten wir 0,05 % unseres Geldes verloren. Aber wie viele genau? Wir können es so regeln:
0.91 CHF * 163.16 (YEN per 1 CHF) * 0.0067 (USD per 1 YEN) = 0.99478652 US Dollars
Nachdem wir also am Anfang 1 US-Dollar verkauft haben, haben wir 0,994 erhalten – am Ende also weniger als 1 US-Dollar.
Einfacher ausgedrückt ist der Arbitrage-Zyklus dann profitabel, wenn eine Währungseinheit für weniger als eine Einheit derselben Währung erhalten werden kann.
Stellen wir uns vor, wir hätten eine Möglichkeit gefunden, bei der ersten Transaktion 0,92 CHF pro 1 US-Dollar zu nehmen, statt 0,91 CHF:
Das heißt, in den realen Währungen erhalten wir mehr als 1 US-Dollar:
0.92 CHF * 163.16 (YEN per 1 CHF) * 0.0067 (USD per 1 YEN) = 1.00571824 US Dollars
Wuolah, wir haben etwas GEWINN! Sehen wir uns nun an, wie man dies mithilfe der Diagrammanalyse automatisieren kann.
Die Formel zur Prüfung auf Gewinne oder Verluste in einem Arbitrage-Kreis aus 3 Arbitrage-Paaren würde also wie folgt aussehen:
USD/CHF * CHF/YEN * YEN/USD < 1.0
Diagrammdarstellung
Um diese Prozesse zu automatisieren, können wir Diagramme verwenden. Die zuvor erwähnten Tabellen können auf natürliche Weise in eine Matrixdarstellung eines Diagramms umgewandelt werden, wobei Knoten Währungen und Kanten bidirektionale Börsen darstellen.
Daher ist es einfach, den Austausch zweier Paare in einer Matrix wie folgt darzustellen:
EUR USD 1 1 EUR 1 1 USD
Abhängig von der Anzahl der beteiligten Paare kann sich unsere Matrix erweitern:
Folglich kann unsere Tabelle auch für nur zwei Währungen erheblich größer werden, wenn wir mehr Börsenplattformen und Ressourcen berücksichtigen.
Um reale Währungsarbitrageprobleme zu lösen, wird häufig ein vollständiges Diagramm verwendet, das alle Beziehungen für Währungskurse umfasst. Eine Wechselkurstabelle mit drei Währungen könnte wie folgt aussehen:
Wir können eine einfache verwenden, um unsere Währungspaare im Speicher darzustellen:
class GraphNode { public: string Name; }; class Graph { public: vector<vector<double>> Matrix; vector<GraphNode> Nodes; };
Jetzt müssen wir nur noch herausfinden, wie wir diesen Graphen durchlaufen und den profitabelsten Kreis finden. Aber es gibt immer noch ein Problem...
Mathe rettet uns wieder einmal
Klassische Graphalgorithmen eignen sich nicht gut für die Arbeit mit dem Produkt von Kantenlängen, da sie darauf ausgelegt sind, Pfade zu finden, die als Summe dieser Längen definiert sind (siehe Implementierungen aller bekannten klassischen Pfadfindungsalgorithmen ).
Um diese Einschränkung zu umgehen, gibt es jedoch einen mathematischen Weg, von einem Produkt zu einer Summe überzugehen: Logarithmen. Wenn ein Produkt unter einem Logarithmus erscheint, kann es in eine Summe von Logarithmen umgewandelt werden.
Auf der rechten Seite dieser Gleichung ist die gewünschte Zahl kleiner als eins, was bedeutet, dass der Logarithmus dieser Zahl kleiner als Null sein muss:
Dieser einfache mathematische Trick ermöglicht es uns, von der Suche nach einem Kreis mit einem Kantenlängenprodukt kleiner als eins zur Suche nach einem Kreis überzugehen, bei dem die Summe der Kantenlängen kleiner als Null ist .
Unsere in LogE(x) umgewandelten und mit 2 Nachkommastellen gerundeten Matrixwerte sehen nun so aus:
Dieses Problem lässt sich nun mithilfe klassischer Graphalgorithmen besser lösen. Was wir brauchen, ist, den Graphen zu durchqueren und nach dem profitabelsten Austauschweg zu suchen.
Graphalgorithmen
Jeder Algorithmus hat seine Grenzen. Einige davon habe ich in erwähnt.
Wir können hier kein klassisches BFS, DFS oder sogar Dijkstra anwenden, da unser Diagramm möglicherweise negative Gewichte enthält, die beim Durchlaufen des Diagramms zu negativen Zyklen führen können. Negative Zyklen stellen eine Herausforderung für den Algorithmus dar, da er bei jeder Iteration kontinuierlich bessere Lösungen findet.
Um dieses Problem zu lösen, begrenzt der Bellman-Ford-Algorithmus einfach die Anzahl der Iterationen. Es durchläuft jede Kante des Diagramms in einem Zyklus und wendet die Entspannung für alle Kanten nicht mehr als V-1-mal an (wobei V die Anzahl der Knoten ist).
Daher ist der Bellman-Ford-Algorithmus das Herzstück dieses Arbitrage-Systems, da er die Entdeckung von Pfaden zwischen zwei Knoten im Diagramm ermöglicht, die zwei wesentliche Kriterien erfüllen: Sie enthalten negative Gewichte und sind nicht Teil negativer Zyklen.
Während dieser Algorithmus theoretisch einfach ist (und es gibt Milliarden Videos darüber), erfordert die praktische Umsetzung für unsere Bedürfnisse einige Anstrengungen. Lassen Sie uns näher darauf eingehen.
Implementierung des Bellman-Ford-Algorithmus
Da das Ziel dieses Artikels die Informatik ist, werde ich imaginäre Wechselkurse verwenden, die nichts mit den realen zu tun haben.
Für einen reibungsloseren Einstieg in den Algorithmus verwenden wir ein Diagramm, das überhaupt keine negativen Zyklen enthält:
Das folgende Codebeispiel findet mithilfe des Bellman-Ford-Algorithmus einen Pfad zwischen zwei Knoten, wenn im Diagramm keine negativen Zyklen vorhanden sind:
vector<double> _shortestPath; vector<int> _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 < verticesNumber - 1; k++) for (int from = 0; from < verticesNumber; from++) for (int to = 0; to < verticesNumber; to++) if (_shortestPath[to] > _shortestPath[from] + graph.Matrix[from][to]) { _shortestPath[to] = _shortestPath[from] + graph.Matrix[from][to]; _previousVertex[to] = from; } }
Das Ausführen dieses Codes für den chinesischen Yuan füllt das Array _ previousVertex und liefert Ergebnisse wie diese:
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)
Wie Sie sehen können, identifiziert es optimale Pfade zwischen CNY und verschiedenen anderen Währungen.
Und noch einmal: Ich werde mich nicht darauf konzentrieren, nur das Beste zu finden, da dies eine relativ einfache Aufgabe und nicht das Ziel des Artikels ist.
Die obige Implementierung funktioniert im Idealfall gut, ist jedoch unzureichend, wenn es um Diagramme geht, die negative Zyklen enthalten.
Negative Zyklen erkennen
Was wir wirklich brauchen, ist die Fähigkeit, zu erkennen, ob ein Diagramm negative Zyklen enthält, und wenn ja, die problematischen Segmente zu lokalisieren. Dieses Wissen ermöglicht es uns, diese Probleme zu entschärfen und letztendlich profitable Ketten zu entdecken.
Die Anzahl der Iterationen muss nicht immer genau V - 1 erreichen. Eine Lösung gilt als gefunden, wenn im (N+1)-ten Zyklus kein besserer Pfad als im N-ten Zyklus gefunden wird. Es besteht also Spielraum für leichte Optimierungen.
Der zuvor erwähnte Code kann erweitert werden, um nicht nur Pfade zu finden, sondern auch zu erkennen, ob das Diagramm negative Zyklen enthält, einschließlich der von mir erwähnten Optimierung:
vector<double> _shortestPath; vector<int> _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 < verticesNumber - 1; k++) { updated = false; for (int from = 0; from < verticesNumber; from++) { for (int to = 0; to < verticesNumber; to++) { if (_shortestPath[to] > _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 < verticesNumber; from++) for (int to = 0; to < verticesNumber; to++) if (_shortestPath[to] > _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; }
Und jetzt spielen wir mit einem komplexeren Diagramm, das negative Zyklen enthält:
Unser Programm stoppt einfach und zeigt eine Meldung an:
Graph contains negative cycle.
Wir konnten das Problem angeben, müssen jedoch um problematische Segmente des Diagramms herum navigieren.
Negative Zyklen vermeiden
Um dies zu erreichen, markieren wir Scheitelpunkte, die Teil negativer Zyklen sind, mit einem konstanten Wert, 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 < verticesNumber - 1; k++) for (int from = 0; from < verticesNumber; from++) for (int to = 0; to < verticesNumber; to++) { if (graph.Matrix[from][to] == INF) // Edge not exists { continue; } if (_shortestPath[to] > _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 < verticesNumber - 1; k++) for (int from = 0; from < verticesNumber; from++) for (int to = 0; to < verticesNumber; to++) { if (graph.Matrix[from][to] == INF) // Edge not exists { continue; } if (_shortestPath[to] > _shortestPath[from] + graph.Matrix[from][to]) { _shortestPath[to] = NEG_INF; _previousVertex[to] = -2; negativeCycles = true; } } return negativeCycles; }
Wenn wir nun im Array _shortestPath auf NEG_INF stoßen, können wir eine Meldung anzeigen und dieses Segment überspringen und gleichzeitig optimale Lösungen für andere Währungen ermitteln. Zum Beispiel mit Knoten 0 (der USD darstellt):
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)
Whoala! Unser Code konnte eine Reihe profitabler Ketten identifizieren, obwohl unsere Daten „etwas schmutzig“ waren. Alle oben genannten Codebeispiele einschließlich Testdaten werden auf mit Ihnen geteilt.
Auch kleine Schwankungen sind wichtig
Lassen Sie uns nun das Gelernte festigen. Anhand einer Liste von Wechselkursen für drei Währungen können wir negative Zyklen leicht erkennen:
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).
Allerdings können bereits geringfügige Änderungen der Wechselkurse (d. h. Anpassungen der Matrix) zu erheblichen Unterschieden führen:
Infolgedessen finden wir möglicherweise mehrere Kandidaten, um Gewinn zu erzielen:
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)
Es gibt jedoch zwei wichtige Faktoren:
Zeit ist ein entscheidender Faktor bei der Umsetzung von Arbitrageprozessen, vor allem aufgrund der schnellen Schwankungen der Währungspreise. Daher ist die Lebensdauer einer sicheren Wette äußerst kurz.
Plattformen erheben Provisionen für jede Transaktion.
Daher sind die Minimierung der Zeitkosten und die Reduzierung der Provisionen von größter Bedeutung, was durch die Begrenzung der Dauer der sicheren Wette erreicht wird.
Empirische Erfahrungen legen nahe, dass eine akzeptable sichere Wettlänge typischerweise zwischen 2 und 3 Paaren liegt. Darüber hinaus steigen die Rechenanforderungen und Handelsplattformen erheben höhere Provisionen.
Um ein Einkommen zu erzielen, reicht es also nicht aus, über solche Technologien zu verfügen, sondern man braucht auch Zugang zu den niedrigen Provisionen. Normalerweise verfügen nur große Finanzinstitute über eine solche Ressource.
Automatisierung durch Smart Contracts
Ich habe mich mit der Logik von FX-Operationen und der Erzielung von Gewinnen aus ihnen befasst, aber ich habe nicht auf die Technologien eingegangen, die zur Ausführung dieser Operationen verwendet werden. Obwohl dieses Thema etwas vom Kurs abweicht, konnte ich es nicht unterlassen, intelligente Verträge zu erwähnen.
Die Verwendung intelligenter Verträge ist heute eine der innovativsten Methoden zur Durchführung von Devisengeschäften. Intelligente Verträge ermöglichen FX-Operationen in Echtzeit ohne Verzögerungen oder menschliches Eingreifen (mit Ausnahme der Erstellung des intelligenten Vertrags).
Solidity ist die spezialisierte Programmiersprache für die Erstellung intelligenter Verträge, die Finanztransaktionen mit Kryptowährungen automatisieren. Die Welt der Smart Contracts ist dynamisch und unterliegt schnellen technologischen Veränderungen und sich weiterentwickelnden Vorschriften. Es handelt sich um einen Bereich mit erheblichem Hype und erheblichen Risiken im Zusammenhang mit Geldbörsen und der Einhaltung gesetzlicher Vorschriften.
Während es zweifellos talentierte Einzelpersonen und Teams gibt, die von diesem Bereich profitieren, gibt es auch Regulierungsbehörden, die dafür sorgen, dass die Marktregeln eingehalten werden.
Warum untersuchen wir das?
Trotz der Komplexität, Unklarheit und Unvorhersehbarkeit der globalen Wirtschaft bleiben Devisen eine verborgene treibende Kraft in der Finanzwelt. Es ist ein entscheidendes Element, das es Tausenden von Unternehmen und Millionen von Einzelpersonen weltweit ermöglicht, auf friedliche Weise und über Grenzen hinweg zusammenzuarbeiten, Dienstleistungen anzubieten und sich gegenseitig zu nutzen.
Natürlich beeinflussen verschiedene Faktoren wie Politik, Vorschriften und Zentralbanken die Wechselkurse und die FX-Effizienz. Diese Komplexität macht die Finanzlandschaft kompliziert. Dennoch ist es wichtig zu glauben, dass diese Komplexität einem größeren Zweck für das Gemeinwohl dient.
Zahlreiche wissenschaftliche Arbeiten befassen sich mit der Existenz und Bestimmung von Wechselkursen in der Weltwirtschaft, um nur einige zu nennen:
Diese Papiere beleuchten einige grundlegende Mechanismen des Devisenhandels, die immer noch schwer zu verstehen und in ein Modell zu integrieren sind.
Allerdings hat mir das Experimentieren mit Code und der Versuch, eine Lösung für ein praktisches Problem zu finden, geholfen, etwas mehr Ahnung davon zu bekommen. Ich hoffe, Ihnen hat diese kleine Erkundungsreise genauso viel Spaß gemacht wie mir. Bleiben Sie dran!
Links
Sedgewick R. – Algorithmen in C, Teil 5: Graphalgorithmen