Interessantes Problem (Währungsarbitrage)

Lesezeit: 8 Minuten

Benutzer-Avatar
sud03r

Arbitrage ist der Prozess, bei dem Diskrepanzen in den Wechselkursen genutzt werden, um Gewinne zu erzielen.
Stellen Sie sich eine Person vor, die mit einem gewissen Betrag der Währung X beginnt, eine Reihe von Umtauschvorgängen durchläuft und schließlich mit mehr Betrag X endet (als er ursprünglich hatte).
Entwickeln Sie bei gegebenen n Währungen und einer Tabelle (nxn) von Wechselkursen einen Algorithmus, den eine Person verwenden sollte, um den maximalen Gewinn zu erzielen, vorausgesetzt, dass sie einen Tausch nicht mehr als einmal durchführt.

Ich habe an eine Lösung wie diese gedacht:

  1. Verwenden Sie den modifizierten Dijkstra-Algorithmus, um den längsten Produktpfad einer einzelnen Quelle zu finden.
  2. Dies ergibt den längsten Produktpfad von der Quellwährung zu jeder anderen Währung.
  3. Iterieren Sie nun über jede andere Währung und multiplizieren Sie bis zum maximalen Produkt, w(curr,source)(Gewicht der Kante zur Quelle).
  4. Wählen Sie das Maximum aller solcher Pfade.

Obwohl dies gut erscheint, bezweifle ich immer noch die Korrektheit dieses Algorithmus und die Vollständigkeit des Problems (dh ist das Problem NP-vollständig?), da es dem Problem des Handlungsreisenden etwas ähnelt.

Suchen Sie nach Ihren Kommentaren und besseren Lösungen (falls vorhanden) für dieses Problem.

Vielen Dank.

BEARBEITEN:

Die Google-Suche nach diesem Thema führte mich zu diesem hierwo die Arbitrageerkennung angesprochen wurde, der Austausch für maximale Arbitrage jedoch nicht. Dies kann als Referenz dienen.

  • Ist das eine Hausaufgabe? Ich weiß mit Sicherheit, dass dies ein Problem im Lehrbuch für den Algorithmuskurs war, den ich vor ein paar Jahren TA gemacht habe.

    – Tyler McHenry

    17. Februar 2010 um 16:32 Uhr

  • Ja, es ist von Dasgupta’s Algorithms (was nicht heißt, dass dies der einzige Ort ist, an dem es auftaucht). Und ich sehe keine Verbindung zu Travelling Salesman. Sie versuchen nicht, jede Währung zu besuchen.

    – Matthäus Flaschen

    17. Februar 2010 um 16:35 Uhr


  • Definitiv Hausaufgaben. Auch das Thema ist nicht hilfreich.

    – Select0r

    17. Februar 2010 um 16:35 Uhr

  • Ich bin mir nicht sicher, was Sie mit “Produktpfad” meinen

    – amit kumar

    17. Februar 2010 um 16:49 Uhr

  • Mit Produktpfad meint er, dass das Gewicht des Pfades das Produkt seiner Kantengewichte ist und nicht die (übliche) Summe.

    – Peter Alexander

    17. Februar 2010 um 17:21 Uhr

Benutzer-Avatar
Peter Alexander

Dijkstra’s kann hier nicht verwendet werden, da es keine Möglichkeit gibt, Dijkstra’s zu modifizieren, um den längsten Weg anstatt den kürzesten zurückzugeben. Im Allgemeinen ist die längstes Pfadproblem ist tatsächlich NP-vollständig, wie Sie vermutet haben, und hängt mit dem Problem des Handlungsreisenden zusammen, wie Sie vorgeschlagen haben.

Was Sie suchen (wie Sie wissen) ist ein Zyklus, dessen Produkt der Kantengewichte größer als 1 ist, dh w1 * m2 * m3 * … > 1. Wir können uns dieses Problem neu vorstellen, um es in eine Summe statt in ein Produkt umzuwandeln, wenn wir die Protokolle beider Seiten nehmen:

anmelden (w1 * m2 * m3 … ) > log(1)

=> log(w1) + log(w2) + log(w3) … > 0

Und wenn wir das negative Protokoll nehmen…

=> -log(w1) – Protokoll (w2) – Protokoll (w3) … < 0 (beachte die umgedrehte Ungleichung)

Also suchen wir jetzt nur nach einem negativen Zyklus im Diagramm, der mit dem Bellman-Ford-Algorithmus gelöst werden kann (oder, wenn Sie den Pfad nicht kennen müssen, dem Floyd-Warshall-Algorithmus).

Zuerst transformieren wir den Graphen:

for (int i = 0; i < N; ++i)
  for (int j = 0; j < N; ++j)
    w[i][j] = -log(w[i][j]);

Dann führen wir einen Standard-Bellman-Ford durch

double dis[N], pre[N];

for (int i = 0; i < N; ++i)
   dis[i] = INF, pre[i] = -1;

dis[source] = 0;

for (int k = 0; k < N; ++k)
  for (int i = 0; i < N; ++i)
    for (int j = 0; j < N; ++j)
      if (dis[i] + w[i][j] < dis[j])
        dis[j] = dis[i] + w[i][j], pre[j] = i;

Jetzt prüfen wir auf negative Zyklen:

for (int i = 0; i < N; ++i)
  for (int j = 0; j < N; ++j)
    if (dis[i] + w[i][j] < dis[j])
      // Node j is part of a negative cycle

Sie können dann die verwenden pre Array, um die negativen Zyklen zu finden. Beginnen mit pre[source] und arbeite dich zurück.

  • Entschuldigung, ich habe die Frage falsch verstanden. Ah, Sie suchen also nach einem Gelegenheitszyklus in der Grafik. Das erfordert den Bellman-Ford-Algorithmus, bei dem die Kantengewichte so transformiert werden, dass die w' = -ln(w). Der Grund für diese Transformation ist, dass sie das Problem auf das Finden eines negativen Zyklus im Diagramm reduziert. Ich werde meine Lösung mit dem richtigen Code aktualisieren.

    – Peter Alexander

    17. Februar 2010 um 17:04 Uhr

  • @Neeraj: Aber das ist ziemlich bekannt log (A*B) = log A + log B

    – kennytm

    17. Februar 2010 um 17:22 Uhr

  • @Neeraj, ich wusste von der Protokolltransformation, weil dies ein bekanntes Problem mit einer bekannten Lösung ist. Wie Kenny sagt, ist es auch bekannt, dass man Produkte mit Logarithmen in Summen umwandeln kann.

    – Peter Alexander

    17. Februar 2010 um 17:25 Uhr

  • @Neeraj, ich kann Ihnen versichern, dass dies die richtige Lösung ist und die Auswertung der Zyklen nicht NP Complete ist. Sie haben Recht, wenn Sie sagen, dass es keinen kürzesten Weg gibt, wenn es negative Zyklen gibt, aber wenn es keine negativen Zyklen gibt, lautet die Antwort auf Ihre Frage, einfach keinen Umtausch durchzuführen, da Sie einen Zyklus benötigen (um zur ursprünglichen Währung zurückzukehren). und alles andere als ein negativer Zyklus wäre unrentabel. Wenn Sie mir nicht glauben, googeln Sie einfach “Arbitrage-Problem” und überzeugen Sie sich selbst. Wie gesagt, das ist ein altbekanntes Problem und das ist die Lösung.

    – Peter Alexander

    17. Februar 2010 um 17:40 Uhr

  • cs.ucdavis.edu/~amenta/f05/hw5.pdf Der Unterschied besteht darin, dass Sie nicht jeden Zyklus auswerten, sondern nur einzelne auswählen.

    – Peter Alexander

    17. Februar 2010 um 18:13 Uhr

Die Tatsache, dass es sich um ein NP-schweres Problem handelt, spielt keine Rolle, wenn es nur etwa 150 sind derzeit existierende Währungen, und ich vermute, Ihr FX-Broker wird Sie sowieso nur mit höchstens 20 Paaren handeln lassen. Mein Algorithmus für n Währungen ist daher:

  1. Machen Sie einen Baum der Tiefe n und Verzweigungsfaktor n. Die Knoten des Baums sind Währungen und die Wurzel des Baums ist Ihre Startwährung X. Jede Verbindung zwischen zwei Knoten (Währungen) hat Gewicht wwo w ist der Wechselkurs zwischen den beiden Währungen.
  2. An jedem Knoten sollten Sie auch den kumulativen Wechselkurs speichern (berechnet durch Multiplizieren aller Wechselkurse darüber im Baum). Dies ist der Wechselkurs zwischen der Wurzel (Währung X) und die Währung dieses Knotens.
  3. Durchlaufen Sie alle Knoten im Baum, die die Währung darstellen X (Vielleicht sollten Sie eine Liste von Zeigern auf diese Knoten führen, um diese Phase des Algorithmus zu beschleunigen). Es wird nur geben n^n von diesen (sehr ineffizient in Bezug auf die Big-O-Notation, aber denken Sie an Ihre n ist etwa 20). Derjenige mit dem höchsten kumulativen Wechselkurs ist Ihr bester Wechselkurs und (wenn er positiv ist) stellt der Pfad durch den Baum zwischen diesen Knoten einen Arbitragezyklus dar, der bei der Währung beginnt und endet X.
  4. Beachten Sie, dass Sie den Baum beschneiden können (und so die Komplexität von reduzieren können O(n^n) zu O(n) indem Sie beim Generieren des Baums in Schritt 1 diese Regeln befolgen:
    1. Wenn Sie zu einem Währungsknoten kommen Xkeine untergeordneten Knoten generieren.
    2. So reduzieren Sie den Verzweigungsfaktor ab n auf 1, bei jedem Knoten alle erzeugen n untergeordnete Knoten und fügen Sie nur den untergeordneten Knoten mit dem größten kumulativen Wechselkurs hinzu (bei Rückrechnung in Währung). X).

  • Der Verzweigungsfaktor sollte n-1 sein

    – Gewur

    2. Juni 2017 um 0:03 Uhr

Imho gibt es eine einfache mathematische Struktur für dieses Problem, die sich für einen sehr einfachen O (N ^ 3) -Algorithmus eignet. Bei einer gegebenen NxN-Tabelle von Währungspaaren ist die reduzierte Zeilenstufenform der Tabelle sollte nur 1 linear unabhängige Zeile ergeben (dh alle anderen Zeilen sind Vielfache/Linearkombinationen der ersten Zeile), wenn keine Arbitrage möglich ist.

Wir können einfach Gaußsche Elimination durchführen und prüfen Sie, ob wir nur 1 linear unabhängige Zeile erhalten. Wenn nicht, geben die zusätzlichen linear unabhängigen Zeilen Informationen über die Anzahl der für Arbitrage verfügbaren Währungspaare.

  • Dies kann ein Algorithmus für eine andere Form von Arbitrage sein, aber mit ziemlicher Sicherheit nicht für die hier diskutierte Cross-Currency-Arbitrage. Oder übersehe ich hier etwas?

    – Dmitrij I.

    2. Juni 2017 um 6:36 Uhr

Nehmen Sie das Protokoll der Umrechnungskurse. Dann versuchen Sie, den bei X beginnenden Zyklus mit der größten Summe in einem Diagramm mit positiven, negativen oder nullgewichteten Kanten zu finden. Dies ist ein NP-schweres Problem, da das einfachere Problem, den größten Zyklus in einem ungewichteten Graphen zu finden, NP-schwer ist.

Wenn ich das nicht völlig durcheinander gebracht habe, glaube ich, dass meine Implementierung mit dem Bellman-Ford-Algorithmus funktioniert:

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>


std::vector<std::vector<double>> transform_matrix(std::vector<std::vector<double>>& matrix)
{
    int n = matrix.size();
    int m = matrix[0].size();
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            matrix[i][j] = log(matrix[i][j]);
        }
    }
    return matrix;
}

bool is_arbitrage(std::vector<std::vector<double>>& currencies)
{

    std::vector<std::vector<double>> tm = transform_matrix(currencies);

    // Bellman-ford algorithm
    int src = 0;
    int n = tm.size(); 
    std::vector<double> min_dist(n, INFINITY);

    min_dist[src] = 0.0;

    for (int i = 0; i < n - 1; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            for (int k = 0; k < n; ++k)
            {
                if (min_dist[k] > min_dist[j] + tm[j][k])
                    min_dist[k] = min_dist[j] + tm[j][k];
            }
        }
    }

    for (int j = 0; j < n; ++j)
    {
        for (int k = 0; k < n; ++k)
        {
            if (min_dist[k] > min_dist[j] + tm[j][k])
                return true;
        }
    }
    return false;
}


int main()
{
    std::vector<std::vector<double>> currencies = { {1, 1.30, 1.6}, {.68, 1, 1.1}, {.6, .9, 1} };
    if (is_arbitrage(currencies))
        std::cout << "There exists an arbitrage!" << "\n";
    else
        std::cout << "There does not exist an arbitrage!" << "\n";



    std::cin.get();
}

1282940cookie-checkInteressantes Problem (Währungsarbitrage)

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy