Originally written for Quadrature n° 81 (2011), p. 23-26.

Résumé. Le graphe est un objet mathématique parmi les plus utilisés pour formaliser et résoudre de nombreux problèmes algorithmiques. Ces problèmes ont des applications variées et souvent insoupçonnées. En particulier, l’algorithme de Bellman-Ford, qui permet de calculer un plus court chemin entre deux sommets d’un graphe, met en évidence des arbitrages sur le marché des devises : des opérations d’achat et de vente garantissant un profit sans risque.

I. Le graphe des devises

I.1 L’offre et la demande

Supposons qu’un acteur de marché (banque, entreprise, spéculateur, etc.) désire échanger des euros contre des dollars. À travers son courtier, il est mis en contact avec une contrepartie désirant effectuer la transaction opposée. Cette contrepartie sera bien souvent une banque assumant le rôle de teneur de marché, c’est-à-dire utilisant ses réserves de devises pour offrir un cours de change. Le teneur de marché permet au client de ne pas avoir à attendre qu’un autre acteur veuille précisément effectuer la transaction opposée. Il profite de l’écart entre le cours auquel il achète et celui auquel il vend. Supposons par exemple qu’un changeur propose d’acheter des euros pour 1,4541 dollars et de vendre des euros pour 1,4542 dollars. Si un client vient acheter un euro et, peu de temps après, un autre client vient vendre un euro, le changeur réalisera un profit de 0,0001 dollar.

I.2 Chaîne de changes

Revenons à notre acteur de marché cherchant à échanger des euros. Il peut contacter divers changeurs qui lui proposeront divers changes, plus ou moins compétitifs. Il se peut, parfois, qu’aucun n’offre le meilleur change, mais que le meilleur change consiste à établir une chaîne de transactions. Par exemple, pour échanger des euros contre des yens, il est possible d’échanger d’abord ses euros contre des francs suisses, puis d’échanger ces francs suisses contre des dollars, et enfin d’échanger ces dollars contre des yens. Dans certaines circonstances, il se peut que cela soit plus avantageux que d’établir directement l’échange souhaité.

La question naturelle est alors de savoir, en fonction de l’offre et de la demande pour chaque paire de devises, quel est le moyen le moins coûteux de convertir une devise en une autre. Pour répondre à cette question, nous pouvons représenter le problème comme un graphe. Chaque nœud du graphe représente une devise, et chaque arc représente l’action qui consiste à échanger une devise contre une autre, si une telle offre existe sur le marché. Une chaîne de change peut être représentée comme une promenade partant d’une devise et arrivant à une autre. Le taux de change associé à une telle chaîne est alors le produit des taux des arcs empruntés.

On peut même se demander s’il serait possible de partir d’une devise, et d’y revenir avec un taux total supérieur à 1. Cela voudrait dire que l’on pourrait, par exemple, échanger un euro contre plus d’un euro. Cette opération, que l’on désigne par arbitrage, consiste à effectuer une série d’échanges afin de réaliser un profit immédiat et garanti.

I.3 Arbitrages

Sur les marchés financiers, un « arbitrage » désigne un ensemble d’ordres d’achat et de vente garantissant un profit sans risque. Par exemple, s’il est possible d’échanger 1 euro contre 1,39 dollar, 1 dollar contre 82 yens, et 1 yen contre 0,0088 euro, on peut commencer avec 100 euros, acheter 139 dollars, les échanger contre 11 398 yens, avec lesquels on peut acheter 100,3024 euros ; on a alors réalisé un profit de 0,3024 €, sans prendre de risque¹.

Comment déterminer le meilleur change pour une devise, comment trouver ces arbitrages ? Pour répondre à ces questions, nous allons introduire un objet mathématique, le graphe, qui formalise le concept que nous venons d’esquisser.

II. Concepts de graphe et de chemin

II.1 Définition

Formellement, un graphe est défini comme la paire \((S,A)\), où \(S\) est un ensemble de sommets, et \(A \subset S \times S\) un ensemble d’arcs joignant certaines paires de sommets. On munit souvent le graphe d’une fonction poids \(u\), qui associe une valeur à chaque arc : \(u : A \to M\), où \(M\) est un monoïde. Le plus souvent, et pour le reste de cet article, on prendra \(M = (\mathbb{R}, +)\). On désignera par \(N\) le nombre de sommets : \(|S| = N\).

Figure 1 - Graphe d’exemple de la section II.1.

Dans cet exemple, \(S = \{a, \ldots, g\}\) et \(A = \{(a,f), (b,g), (c,d), (d,e), (d,c), (e,a), (g,g)\}\). Nous avons aussi attribué des poids à chaque arc².

II.2 Chemins dans un graphe

Intuitivement, un chemin dans un graphe consiste à partir d’un sommet et à se déplacer pas à pas vers d’autres sommets adjacents³. La liste des sommets parcourus est ce que l’on appelle un chemin. Formellement, un chemin \((s_i)_{i \in [1 \ldots r]} \in S^r\) vérifie, pour tout \(i \in [1 \ldots r - 1]\), la condition \((s_i, s_{i+1}) \in A\).

On peut définir le poids total d’un chemin comme la somme des poids des arcs qui le composent⁴. S’il existe au moins un chemin reliant les sommets \(x\) et \(y\), on appelle « chemin minimal » tout chemin ayant un poids minimal parmi ceux qui relient \(x\) à \(y\). Nous allons voir qu’un tel chemin n’existe pas forcément.

II.3 Cycles négatifs

Un cycle est un chemin qui part et aboutit au même sommet. On appelle cycle absorbant tout cycle ayant un poids négatif. S’il existe un chemin entre \(x\) et \(y\) contenant un cycle négatif, c’est-à-dire

et

on peut construire des chemins entre \(x\) et \(y\) de poids arbitrairement bas. Il suffit de parcourir le cycle entre \(s_p\) et \(s_q\) plusieurs fois pour diminuer arbitrairement le poids du chemin.

Réciproquement,

Théorème 1. S’il n’existe pas de cycle négatif, et s’il existe au moins un chemin reliant \(x\) et \(y\), alors il existe un chemin minimal entre \(x\) et \(y\).

Démonstration. Tout chemin reliant \(x\) à \(y\) et contenant un cycle peut être simplifié en supprimant ce cycle. Comme le graphe ne contient aucun cycle négatif, cette suppression n’augmente pas le poids du chemin ; elle le diminue si le cycle est de poids strictement positif, et le laisse inchangé s’il est de poids nul. En répétant l’opération, on obtient donc un chemin sans cycle. Un tel chemin ne peut contenir plus de \(N\) sommets distincts, sans quoi il contiendrait un cycle. Il n’existe donc qu’un nombre fini de chemins sans cycle reliant \(x\) à \(y\) ; l’ensemble de leurs poids est fini, et admet par conséquent un minimum. Ce minimum est aussi celui de l’ensemble de tous les chemins reliant \(x\) à \(y\).

III. Recherche de chemins minimaux

III.1 Arbre des chemins minimaux

Dans ce qui suit, on considère un graphe sans cycles nuls ni négatifs, ayant \(N\) sommets et une fonction de poids \(u\). On suppose également qu’il existe un chemin entre le sommet \(x\) et tous les autres sommets.

Pour chaque sommet \(y \neq x\), considérons un chemin minimal reliant \(x\) à \(y\) et notons \(d(y)\) son poids.

Théorème 2. Il existe une fonction prédécesseur \(p : S \setminus \{x\} \to S\) telle que, pour tout \(y \in S \setminus \{x\}\), il existe un entier \(L \ge 1\) vérifiant \(p^{(L)}(y) = x\), et le chemin

est minimal.

La fonction \(p\), dite « prédécesseur », associe à chaque sommet un sommet visité juste avant de l’atteindre en empruntant un chemin minimal partant de \(x\). Elle suffit à construire un chemin minimal entre \(x\) et n’importe quel autre sommet. Pour le montrer, on prouve d’abord le lemme suivant.

Lemme 3. \(\forall y \neq x,\ \exists r < N,\quad p^{(r)}(y) = x.\)

Démonstration. Raisonnons par l’absurde. Supposons qu’il existe un sommet \(y \neq x\) tel que les itérés \(y, p(y), p^{(2)}(y), \ldots, p^{(N)}(y)\) n’atteignent jamais \(x\) avant l’étape \(N\). Comme le graphe possède seulement \(N\) sommets, deux de ces sommets coïncident nécessairement : il existe donc \(0 \le m < n < N\) tels que \(p^{(m)}(y) = p^{(n)}(y)\). La chaîne des prédécesseurs contient alors un cycle.

Or, par définition de \(p\), pour tout entier \(k\) tel que \(p^{(k+1)}(y)\) soit défini, on a

En sommant ces égalités pour \(k = m, \ldots, n - 1\), on obtient

ce qui contredit l’hypothèse d’absence de cycles nuls. Le lemme est donc démontré.

Les itérations de la fonction prédécesseur permettent donc de rejoindre \(x\) depuis n’importe quel sommet, à rebours, en suivant

et les chemins ainsi obtenus sont minimaux. L’ensemble \(\{(p(z), z),\ z \in S \setminus \{x\}\}\) forme un arbre enraciné en \(x\), les enfants de chaque nœud étant les sommets du graphe ayant ce nœud pour prédécesseur.

III.2 Relaxation

Le concept principal dans la recherche de chemins minimaux est celui de relaxation. La relaxation repose sur la propriété

C’est l’équivalent de l’inégalité triangulaire dans les graphes : la distance de \(x\) à \(z\) est au plus la distance d’un chemin minimal entre \(x\) et \(y\), suivie de l’arc \((y,z)\).

Un algorithme de recherche de plus court chemin apparaît alors naturellement. On initialise \(d_0(x) = 0\) et, pour tout \(y \neq x\), \(d_0(y) = +\infty\), puis on calcule récursivement des approximations de \(d\). Si nous disposions d’une fonction de prédécesseur \(p\), il suffirait de considérer la partition du graphe \(S_0, S_1, \ldots, S_r\), avec \(S_0 = \{x\}\) et, pour tout \(i\), \(S_{i+1} = p^{-1}(S_i)\). On effectuerait les relaxations suivant les arcs \(A_1\), puis \(A_2\), etc., où \(A_i = \{(p(y),y),\ y \in S_i\}\) pour \(i \ge 1\). Pour tout \(y \in S_{i+1}\),

tandis que, pour les autres sommets, \(d_{i+1}(y) = d_i(y)\). À l’étape \(i\), on a alors \(d_i(y) = d(y)\) pour tout \(y \in S_i\), c’est-à-dire que le poids d’un chemin minimal est connu exactement.

III.3 Algorithme de Bellman-Ford

Bien entendu, nous ne connaissons pas la fonction \(p\) : ce serait trop facile. Cependant, on remarque que l’introduction de relaxations supplémentaires dans l’algorithme précédent ne change rien au résultat final. En particulier, si une suite de relaxations contient la séquence de relaxation décrite ci-dessus comme sous-suite, on obtient une méthode pour calculer \(d\).

C’est le principe sous-jacent à l’algorithme développé par Richard Bellman et Lester Ford Jr. Si l’on relaxe tous les arcs, dans un ordre quelconque, \(N - 1\) fois, on est certain de contenir une sous-suite qui relaxe les arcs dans l’ordre \(A_1, A_2, \ldots\). Notons que l’algorithme permet également de construire la fonction \(p\) : il suffit de retenir, à chaque relaxation réussie, l’arc emprunté pour raccourcir le chemin reliant \(x\) à \(z\).

Algorithme 4 - Bellman-Ford

1
2
3
4
5
6
7
8
9
10
11
12
13
14
d[x] <- 0
for y in S \ {x} do
    d[y] <- +∞
    p[y] <- ⊥
end for

for i in [1 ... N - 1] do
    for all (y,z) in A do
        if d[y] + u(y,z) < d[z] then
            d[z] <- d[y] + u(y,z)
            p[z] <- y
        end if
    end for
end for

III.4 Recherche de cycles négatifs

Dans ce qui précède, nous sommes partis de l’hypothèse que le graphe ne contenait pas de cycle absorbant. Que se passe-t-il lorsque ce n’est pas le cas ? Supposons qu’il existe un cycle absorbant accessible depuis \(x\) ; après les \(N - 1\) passes de Bellman-Ford, au moins une relaxation supplémentaire réduira encore l’approximation \(d(z)\) pour un certain arc \((y,z)\). Le cycle absorbant se situe alors sur un chemin allant de \(x\) à \(z\).

Réciproquement, si une relaxation supplémentaire diminue \(d(z)\), c’est qu’il existe un cycle absorbant sur un chemin calculé entre \(x\) et \(z\). Pour détecter les cycles absorbants accessibles depuis \(x\), il suffit donc d’ajouter un tour de relaxations à la suite de l’algorithme de Bellman-Ford.

Algorithme 5 - Recherche de cycles absorbants

1
2
3
4
5
6
7
8
9
10
Exécuter l'algorithme de Bellman-Ford.

for all (y,z) in A do
    if d[y] + u(y,z) < d[z] then
        p[z] <- y
        return "Il y a un cycle absorbant"
    end if
end for

return "Pas de cycle absorbant"

Le cycle peut alors être retracé en remontant la fonction \(p\) à l’envers. Lorsque l’on passe deux fois par le même sommet, c’est que l’on a atteint le cycle. Pour détecter un cycle absorbant quelconque dans le graphe, indépendamment d’un sommet source, il suffit d’ajouter une source fictive reliée à tous les sommets par des arcs de poids nul.

III.5 Un mot sur la complexité

Le temps nécessaire pour calculer une solution au problème de Bellman-Ford dépend bien entendu du graphe et de la machine sur laquelle il est calculé, mais sa complexité temporelle est \(O(|S||A|)\).

Il existe de nombreux autres algorithmes de plus court chemin, adaptés à des cas spéciaux, par exemple lorsque tous les arcs sont positifs, ou lorsque le graphe possède une structure particulière. En général, l’idée est toujours de calculer des relaxations, mais de choisir leur ordre judicieusement⁵.

IV. Application à la recherche d’arbitrages

Figure 2 - Graphe d’offres de change utilisé dans la section IV.

Revenons à nos devises. Le graphe ci-dessus représente différentes offres de change. Par clarté, et par souci de généralité, tous les changes ne sont pas directement possibles dans ce graphe. Par exemple, il n’y a pas d’offre de change directe entre le franc suisse (CHF) et le yen (JPY) dans cet exemple. Pour chaque arc \((y,z)\), notons \(\tau(y,z)\) le nombre d’unités de \(z\) obtenues pour une unité de \(y\). Ainsi, on lit sur la figure \(\tau(\mathrm{EUR}, \mathrm{USD}) \approx 1.45444\) et \(\tau(\mathrm{USD}, \mathrm{EUR}) \approx 0.6875\).

Pour une chaîne de change \(\gamma\), le taux total obtenu est le produit des taux de chacun des arcs qui la composent :

Un arbitrage correspond donc à un cycle \(\gamma\) tel que \(\tau(\gamma) > 1\).

Pour revenir au cadre additif de Bellman-Ford, il suffit de poser

Alors, pour toute chaîne de change \(\gamma\),

Ainsi, un arbitrage correspond exactement à un cycle de poids négatif⁶. L’algorithme de Bellman-Ford permet donc de calculer la chaîne la plus avantageuse pour convertir une devise en une autre, mais aussi de découvrir des opportunités d’arbitrage.

Conclusion

En pratique, un algorithme utilisé sur les marchés financiers devrait être un peu plus complexe. Il y a des considérations de volume à prendre en compte : une offre d’achat ou de vente n’est valable que pour une quantité donnée. Il faut également gérer le risque qu’une aubaine disparaisse pendant le calcul. De tels algorithmes sont parfois utilisés par les places de marché pour fournir à un client le meilleur prix possible.

Références

1. Bellman, R., On a routing problem, Quarterly of Applied Mathematics 16: 87-90, 1958.
2. Ford, L. R. Jr., Fulkerson, D. R., Flows in Networks, Princeton University Press, 1962.