FR 2899001 A1 20070928 FR 0602620 A 20060327 La présente invention concerne un dispositif qui permet de développer la pratique du troc. Il est traditionnellement admis qu'un accord entre vendeur et acheteur nécessite l'usage d'un étalon de valeur unique pour équilibrer la valeur économique qui est échangée; ce qui impose l'utilisation de la monnaie dans les relations économiques. Le troc qui ne nécessite pas cette référence unique est d'ordinaire décrit comme une étape primitive de l'histoire de l'économie. Le dispositif, selon l'invention, permet la recherche d'un accord entre au moins deux acteurs économiques sans qu'un étalon unique soit nécessaire ; la mesure d'équilibre de l'échange ne dépendant que des quantités échangées. Il fait apparaître un gain économique dans les relations qu'il crée et la redistribue intégralement et équitablement entre les acteurs. Il détermine les relations à établir et les quantités à échanger en favorisant les propositions les plus généreuses et en maximisant le gain économique de ceux qui les ont faites. Stock de valeurs Les acteurs économiques qu'on nomme les participants disposent de stocks qu'ils déclarent sur le dispositif. Un stock est constitué de valeurs économiques dénombrables, ce peut être une monnaie nationale, une monnaie sociale, ou tout autre un étalon de valeur choisi par une communauté économique (1 heure de travail d'une qualification donnée, 1 Kg d'une ressource naturelle donnée, etc.). Un stock est décrit par une quantité et la référence à la description d'un étalon de valeur éventuellement associé à un standard de qualité, qu'on nomme un standard. Pour qu'un tel standard soit utilisable, il n'est pas nécessaire qu'il soit reconnu par une autorité mais seulement qu'au moins un fournisseur et un client l'admettent. Proposition Le dispositif enregistre des propositions de troc exprimées par les participants. Une telle proposition est déclarée par un participant comme le besoin d'une quantité (rq) exprimé en utilisant le standard (rn) contre la fourniture d'une autre quantité (fq) d'un stock qu'il déclare posséder lui-même, dont la nature correspond au standard (fn). Echange de troc Le dispositif propose aux participants qu'il met en relation (au moins 2) un projet d'échange composé d'un engagement pour chaque co-contractant à fournir une quantité d'une valeur donnée à un autre partenaire. Ce projet d'échange répond au mieux aux exigences exprimées par les propositions mises en relation. C'est ensuite l'affaire des participants de convenir des conditions de temps et de lieu dans lesquelles les stocks sont échangés. Chacun pourra vérifier que la fourniture correspond au standard attendu, et faire les déclarations légales nécessaires si l'échange a lieu. Selon des modes particuliers de réalisation, le dispositif met a disposition des participants des moyens leurs permettant de s'accorder plus facilement sur les modalités d'exécution de l'échange en affichant par exemple une carte situant les stocks les uns par rapport aux autres pour le choix du lieu d'échange. Dès qu'un projet d'échange est proposé, les quantités des stocks et des besoins sont diminuées par le disposition des quantités indiquées au projet. Ceci permet de ne pas créer plusieurs projets d'échange portant sur les mêmes biens. Description générale du dispositif Le dispositif est constitué, comme l'illustre la figure 2, des éléments suivants : Un guichet, Une base de troc permettant de mémoriser les informations de troc. Une unité de traitement qui exécute les demandes de traitement transmises par le guichet sur la base de troc. Guichet C'est la partie du dispositif qui permet aux participants d'interagir avec lui. Il permet aux participants : • de s'inscrire ou de : s'authentifier, • de déclarer un stock, • de déposer une proposition, • de consulter un projet d'échange. Selon le mode particulier de réalisation du dispositif, le guichet permet aussi de : • de mettre à jour un stock, • de retirer une proposition, • de refuser un stock proposé dans un projet d'échange. Selon le mode particulier de réalisation du dispositif, le guichet peut être un site internet disponible sur un PC, un téléphone portable, ou un autre média. Base de troc C'est une base de données enregistrant les informations décrivant les stocks, les propositions, les besoins exprimés dans les propositions qui n'ont pas encore été satisfaits ainsi que les standards utilisés ainsi que les projets d'échange. Unité de traitement L'unité de traitement agit sur la base de troc. A chaque fois qu'une demande de traitement est faite par le participant et qu'elle est susceptible de créer de nouveaux projets d'échange, le dispositif extrait de la base de trocs le graphe des propositions au voisinage de la demande de traitement. Il effectue ensuite une recherche de boucles. Selon le mode particulier de réalisation du dispositif, l'unité de traitement peut inclure : • un moyen d'autocorrection permettant de résoudre les boucles éventuellement détectées dans la base de troc. • un moyen de restriction de recherche permettant aux participants d'exprimer des exigences supplémentaires de limiter le volume du graphe des propositions. • Un moyen d'arrondi des quantités échangées. Graphe des propositions Pour effectuer la recherche, le dispositif utilise la notion mathématique de graphe. La proposition d'un participant à fournir une partie d'un stock qu'il possède en l'échange d'une autre valeur peut être mise en relation avec une autre proposition si le standard fourni par la première est identique au standard demandé par la seconde. La flèche du graphe représente la proposition, et le noeud auquel aboutit une flèche représente le stock associé à cette proposition. A chaque flèche est donc associé le couple (fq,rq) de la proposition, comme l'illustre la figure 1, le stock offert pour cette proposition ayant une quantité supérieure à la quantité proposée (fq). Recherche de boucles L'unité de traitement du dispositif recherche les boucles susceptibles de constituer un projet 20 d'échange. Pour chaque boucle candidate, il calcule une valeur G, égal au produit des quantités fournies (fq) divisé par le produit des quantités demandées (rq) pour toutes les flèches de la boucle trouvée. Cette quantité est sans dimension car les mêmes valeurs sont présentes au numérateur et au dénominateur. Ceci s'explique par le fait que les propositions mises en relation forment une 25 boucle. Un G inférieur à l (G 1), un accord est possible, et il produit même un avantage pour les acteurs s'il est supérieur strictement à 1 (G>1). Cette valeur G indique dans quelle mesure la relation économiquement est avantageuse, et elle est d'autant plus grande que les participants de la boucle sont généreux dans les propositions qu'ils 30 font aux autres. Les figures 3, 4 et 5 illustrent des exemples de ces trois situations. -5 L'unité de traitement calcule un gain g tel que g =G qui est utilisé pour répartir équitablement les avantages de la mise en relation entre les n acteurs de la boucle. Dès que G >1 on a aussi g >1. Ce gain g exprime le gain économique obtenu par chaque participant mis en relation'. Lorsque plusieurs boucles existent avec g >1, l'unité de traitement du dispositif choisit celle qui produit le plus grand gain g. Ce choix permet a) de privilégier les propositions les plus généreuses, b) de privilégier les échanges ayant un nombre de co-contractants faible, c) de maximiser le gain g obtenu par le participant auteur de la proposition déposée. Les participant dont les propositions ont été écartées mais qui souhaitent échangés sont incités à revoir leur proposition en fournissant plus ou bien en demandant moins. Calcul de flux Le projet d'échange proposé aux acteurs de la boucle choisie est alors déterminé en recherchant un vecteur (D, qu'on appelle le flux de valeur, dont chaque composante est la quantité fournie par un contractant. Il est établi par le dispositif de telle manière qu'un acteur qui a fait la proposition (fq,fn,rq,rn) reçoive une quantité Rq de la valeur rn et fournisse une quantité Fq de la valeur fn. Ces quantités Rq et Fq satisfont partiellement ou totalement aux propositions mises en relation et sont déterminées de manière à ce que : • Rq/Fq = g * rq/fq Défini en sorte que le produit des Rq/Fq de la boucle soit égal à 1; exprimant le fait que le gain de la mise en relation est intégralement redistribué. Ces équations déterminent une famille de solutions possibles pour lesquelles l'échange est équilibré. Elles expriment que le vecteur D doit être colinéaire à un vecteur D déterminé par les couples (fq,rq). La norme du vecteur (D sur la boucle est fixée aux maximum possible sans dépasser les besoins exprimés par les propositions mises en relation. En synthèse, le dispositif calcule la solution de la manière suivante : Pour une boucle de n propositions d'indice i dans [0,n[, soient : rq; la quantité demandée Il est choisi de telle sorte que le produit des g de la boucle soit égal à G. fq; la quantité proposée Le gain g est alors : g=(frq;/j]fq;)I' Si D est le vecteur tel que : doù1 d,=(d;_, * fq,)/ ( rq;*g) pour i dans ]0,n[ et a est le scalaire tel que : Alors la solution (D représentant les quantités du contrat est a * D. Matériellement, le gain se manifeste pour chaque co-contractant par le fait que la proportion entre 10 ce qu'il reçoit et ce qu'il fournit est plus intéressante que ce qu'il proposait, puisque g>l. Algorithme de recherche Les algorithmes qui permettent la recherche d'un chemin optimal ne peuvent fonctionner que pour des graphes sans boucle. La recherche de boucles opère sur le graphe des propositions en épuisant les boucles détectées2 par la production de projets d'échange. 15 Lorsqu'une nouvelle proposition P est déposée, la recherche de boucles recherche les chemins qui maximisent la valeur de g à partir de la proposition P, dont la valeur proposée est P.fn et la valeur fournie P.rn. Le dispositif réduit les besoins et stocks disponibles à chaque fois qu'un projet d'échange est trouvé jusqu'à épuisement des boucles créées par P. Il maintient ainsi la contrainte d'absence de boucles. 20 Comme le volume de calcul croît pour les meilleurs algorithmes comme le produit du nombre de noeuds et d'arcs, le dispositif limite la recherche aux contrats ayant un nombre de participants maximum, par exemple 5, sachant que plus le nombre de contractants est grand, plus le contrat est difficile à convenir. 25 La recherche de boucle s'effectue en trois étapes, les deux premières (facultatives) permettant de réduire encore le volume de calcul de la troisième étape: 2 On dit qu'une boucle est épuisée quand le besoin exprimé est nul pour l'une des propositions de la boucle. -7 1) du graphe des propositions, extraction d'un sous-graphe composé des arcs et noeuds connectés à P.fn. 2) extraction du sous-graphe précédent des arcs et noeuds connectés à P.rn. On obtient ainsi un graphe ne contenant que les stocks et propositions reliant P.rn à P.fn. 3) application sur le sous-graphe résultat de ces deux premières étapes d'un algorithme de recherche de chemin maximisant la valeur de g. Si une telle boucle ayant une valeur g >1 existe, un projet d'échange est créé en réduisant les besoins exprimés par les propositions et les stocks des quantités fournies dans l'échange. La recherche de boucle est de nouveau lancée jusqu'à ce que toutes les boucles avec g >1 soient 10 épuisées. On maintient ainsi un graphe sans boucles, puisqu'à chaque modification du graphe des propositions, on résorbe les boucles produites. Selon le mode particulier de réalisation du dispositif, la réduction des propositions peut aussi se 15 baser sur la capacité à fournir de chaque co-contractant plutôt que sur le besoin exprimé. Selon le mode particulier de réalisation du dispositif, la recherche du chemin maximisant g peut utiliser différents algorithmes. L 'algorithme de Disjkstra n'est pas adapté à ce problème car il ne permet que d'optimiser une fonction du chemin qui croît en même temps que le chemin est parcouru3. 20 On illustre en page suivante la réalisation du dispositif en utilisant l'algorithme de Bellman Ford4 qui autorise des fonctions qui peuvent croître ou décroître lorsque le chemin est parcouru, comme c'est le cas pour le gain g. 3 La littérature indique qu'il permet de faire une recherche avec des arcs pondérés par des distances positives. 4 Pour un exposé et la preuve de l'algorithme de Bellman Ford, voir : http://en.wikipedia.org/wiki/Bellman-Ford 15 20 25 30 -8 On note pour une proposition p: p.fn le standard fourni, p.fq la quantité fournie, p.rn le standard demandé, p.rq la quantité demandée, P est la proposition qui fait l'objet de traitement, Q est un vecteur stocké à chaque noeud qui contient l'état d'un chemin candidat aboutissant à ce noeud. Cet état comprend: la quantité G, son nombre de flèches et la proposition qui aboutit à ce noeud. pow(a,b) est la fonction qui élève a à la puissance b. // étape 1 : initialisation du graphe Pour chaque noeud v de la liste des valeurs : Si v == P.fn alors v.Q //étape 2 : répétition de ta relaxation des flèches Pour chaque noeud v de la liste des valeurs : Pour chaque flèche p de la liste des propositions : prev pow(Gn,1/np) alors : next.Q // étape 3 : vérification d'existence de boucle inattendue Pour chaque flèche p de la liste des propositions : prev pow(Gn,1/np) alors : erreur indiquant que le graphe contient un cycle passant par p. La boucle recherchée est alors lue en parcourant les noeuds depuis la valeur P.fn. Ce parcours s'effectue en utilisant à chaque noeud le vecteur Q qui contient la proposition menant au noeud précédent. Autocorrection L'application du procédé de détection de boucles permet, en principe, d'éliminer systématiquement les boucles sur le graphe dès qu'elles apparaissent, en produisant les projets d'échange et en réduisant les besoins des propositions associées, mais l'exploitation d'un graphe important ne peut exclure la possibilité d'une boucle non résolue. La recherche de boucles qui détecte les boucles inattendues déclanche la correction en soumettant de nouveau le graphe des propositions à la recherche de boucles en partant de l'une des propositions de la boucle inattendue et en ayant extrait du graphe la proposition dont la recherche de boucle était en cours. Restriction de recherche Selon le mode de réalisation du dispositif, il peut intégrer des exigences supplémentaires à la 15 recherche de relations entre propositions, en particulier : Géographie : une position géographique est donnée pour chaque stock (latitude, longitude), et chaque proposition contient une distance maximale acceptée par le participant pour réaliser l'échange. L'unité de traitement construit le graphe de recherche en éliminant les relations entre les propositions qui relient des stocks dont la distance géographique est plus grande que la 20 somme des distances maximales acceptées. Avant de soumettre le projet d'accord, l'unité de traitement vérifie qu'il existe bien un lieu géographique qui soit pour chaque proposition à une distance inférieure à la distance maximale acceptée. Quantité minimale livrable : la proposition précise alors la plus petite quantité que le participant accepte de livrer, jugeant que le déplacement ne vaut pas la peine pour une quantité plus faible. 25 L'unité de traitement construit le graphe de recherche en éliminant les relations entre propositions pour lesquelles le stock disponible est inférieur à la quantité minimale livrable. De plus, avant de soumettre l'accord, l'unité de traitement vérifie que les quantités de l'accord d'échange vérifient cette contrainte. Quantité minimale acceptable : la proposition précise alors la plus petite quantité que le -10- participant accepte de recevoir. L'unité de traitement procède comme pour la quantité minimale livrable. Refus de stock : le participant a indiqué qu'il refusait un stock proposé par un projet d'échange pour répondre à une proposition qu'il avait faite. Dans ce cas, l'unité de traitement construit le graphe en rejetant les relations entre cette proposition et le stock refusé. Arrondis Les quantités du contrat sont calculées en flottant mais les quantités de stock sont presque toujours entières. La solution entière est obtenue en recherchant celle qui est la plus proche de la solution exacte. Cette proximité est mesurée par exemple par la norme de la différence entre le vecteur el) et le même vecteur dont les coordonnées sont arrondies par les entiers les plus proches des valeurs exactes. Pour n participants au contrat, il y aura 2 cas possibles, ce qui est faible puisque n est majoré. Le participant peut spécnfier pour une proposition qu'il dépose que les quantités livrées sont multiples d'une valeur entière car les produits sont fournis par lots. L'arrondi prend en compte cette contrainte pour obtenir le vecteur du projet d'échange en utilisant le même procédé. -11- Les applications industrielles possibles de l'invention sont par exemple: 1) Système de change monétaire ne nécessitant pas le passage par une monnaie de référence, 2) Système de compensation, 3) Serveur de troc portant sur des stocks. 4) Système de transfert de valeurs entre monnaies sociales (SEL, LETS, etc.), Le dispositif peut être d'une grande utilité pour les pays où l'économie est paralysée par l'absence de ressources financières mais où, comme c'est souvent le cas, ils disposent par ailleurs de toutes les ressources humaines et naturelles qui leurs permettraient de prospérer. Il peut aussi être employé lors de difficultés d'ordre monétaire pour maintenir une activité économique. Il reste évidemment utilisable dans d'autres contextes plus ordinaires. REVENDICATIONS 1. Dispositif permettant d'établir entre des acteurs économiques des projets d'échanges, à partir de déclarations de stocks et de propositions, caractérisé en ce qu'il comporte un guichet, une base de trocs exploitée par une unité de traitement mettant en relation des propositions comme décrit en page 2, permettant d'extraire un graphe de propositions, d'y appliquer une recherche de boucles maximisant le gain g décrit en page 5 et un calcul de flux. La base de troc étant centralisée sur un serveur. 2. Dispositif identique à celui de la revendication 1, mais pour lequel la base de troc et l'unité de calcul sont répartis sur les ordinateurs des participants. Les termes écrits en italiques se réfèrent à la figure 2.