💰 quantitative finance

Fair Distribution of Digital Payments: Balancing Transaction Flows for Regulatory Compliance

Cet article aborde le défi computationnel de la redistribution des transactions de paiements numériques afin de se conformer au plafond de 30 % de parts de marché des applications UPI en Inde, en formalisant le problème comme le problème NP-complet du flux d'activation d'arêtes minimale et en proposant une heuristique évolutive, DTAS, qui minimise efficacement l'inconvénient pour l'utilisateur tout en imposant les limites réglementaires.

Auteurs originaux : Ashlesha Hota, Shashwat Kumar, Daman Deep Singh, Abolfazl Asudeh, Palash Dey, Abhijnan Chakraborty

Publié 2026-06-04

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Ashlesha Hota, Shashwat Kumar, Daman Deep Singh, Abolfazl Asudeh, Palash Dey, Abhijnan Chakraborty

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez le système de paiement numérique de l'Inde, l'UPI, comme un immense système d'autoroutes ultra-rapide où des milliards de personnes font circuler leur argent chaque jour. En ce moment, presque tout le monde roule sur seulement deux routes spécifiques : PhonePe et Google Pay. Ces deux « applications » sont si populaires qu'elles gèrent plus de 80 % de tout le trafic.

Cela crée un problème. Si l'une de ces deux routes présente un énorme nid-de-poule (un crash de serveur) ou devient trop encombrée, tout le système peut s'embouteiller. De plus, il semble injuste que l'infrastructure gratuite du gouvernement soit principalement utilisée par seulement deux entreprises.

Pour corriger cela, le régulateur (NPCI) a une nouvelle règle : Aucune application ne peut transporter plus de 30 % du trafic total.

Le Grand Défi

Voici la partie délicate : vous ne pouvez pas simplement dire à des millions de personnes : « Arrêtez d'utiliser votre application préférée et passez à une nouvelle aujourd'hui. » Les gens sont des créatures d'habitude ; ils aiment les applications qu'ils possèdent déjà.

Si une application atteint sa limite de 30 %, le système ne peut pas simplement bloquer le paiement de l'utilisateur (ce serait impoli et causerait des erreurs). Au lieu de cela, le système doit guider doucement les utilisateurs vers d'autres applications, moins encombrées. Mais la plupart des gens n'ont qu'une ou deux applications installées. Pour en utiliser une autre, ils doivent d'abord la télécharger et l'installer.

Les chercheurs ont posé une question simple : Quel est le nombre absolument minimum de personnes qui doivent installer une nouvelle application pour que tous les paiements puissent passer sans enfreindre la règle des 30 % ?

Le « Puzzle » qu'ils ont résolu

Les auteurs ont réalisé qu'il s'agit d'un puzzle mathématique géant et complexe.

Les Joueurs : Des millions d'utilisateurs (qui ont différents montants à envoyer) et de nombreuses applications (qui ont une limite de trafic qu'elles peuvent supporter).
Le But : Connecter les utilisateurs aux applications de manière à ce qu'aucune application ne soit surchargée, tout en forçant le plus petit nombre de personnes à installer une nouvelle application.

Ils ont prouvé que résoudre cela parfaitement est incroyablement difficile — si difficile que même les supercalculateurs les plus rapides mettraient une éternité à trouver la réponse parfaite pour un scénario réel. C'est comme essayer de résoudre un Sudoku dont la grille est de la taille d'une ville, et dont les règles changent chaque seconde.

Leur Solution : Le « Gestionnaire de Trafic Intelligent »

Puisqu'ils ne pouvaient pas résoudre le puzzle parfait instantanément, ils ont construit un « Gestionnaire de Trafic Intelligent » appelé DTAS (Decoupled Two-Stage Allocation Strategy). Considérez cela comme un policier de la circulation très astucieux qui utilise quelques astuces intelligentes :

La Règle du « Léger d'Abord » :
Imaginez une fête où vous devez placer les invités. Si vous placez d'abord les invités géants et lourds, ils prendront toutes les grandes tables, ne laissant nulle part où s'asseoir aux petits invités.
Les chercheurs ont découvert que si vous essayez d'orienter les « utilisateurs lourds » (les personnes qui effectuent des milliers de transactions) en premier, ils consomment immédiatement toute la capacité des applications populaires. Cela force tous les autres à installer de nouvelles applications.
Leur astuce : Orientez les « utilisateurs légers » (ceux qui paient pour un café ou de petits articles) en premier. Ils s'insèrent facilement dans les sièges vides. Le temps que les « utilisateurs lourds » arrivent, il reste encore assez de place pour qu'ils partagent la charge sans avoir besoin d'installer de nouvelles applications.
L'Astuce du « Attendez une Seconde » (pour les systèmes en ligne) :
Dans le monde réel, les paiements se font un par un, et le système ne sait pas qui est un utilisateur lourd avant qu'il ne commence à payer.
Le système utilise un « sketch » (une astuce de mémoire rapide) pour deviner qui est un utilisateur lourd. S'il pense que quelqu'un est un utilisateur lourd, il place son paiement dans une file d'attente pendant une fraction de seconde. Ce délai permet au système d'avoir une vision plus globale et d'orienter le paiement vers une application moins encombrée, plutôt que de le déverser sur l'application la plus populaire.
L'Option « Équité » :
Ils ont également construit une version appelée Fair_DTAS. Cette version se soucie encore plus de s'assurer que chaque application reçoit une part équitable du trafic, et pas seulement d'éviter la limite de 30 %. C'est comme un enseignant qui ne se contente pas de faire en sorte qu'aucun élève n'échoue, mais veille à ce que tout le monde reçoive une attention similaire. Cela coûte quelques installations d'applications supplémentaires à certaines personnes, mais cela crée un écosystème beaucoup plus équilibré.

Ce qu'ils ont trouvé

Ils ont testé leur système en utilisant des données de 100 millions de transactions (simulées à partir de données bancaires réelles).

Efficacité : Leur « Gestionnaire de Trafic Intelligent » était presque aussi performant que la solution mathématique parfaite, mais il tournait des millions de fois plus vite.
Coût : Il nécessitait seulement 1 ou 2 installations d'applications supplémentaires par utilisateur en moyenne par rapport au meilleur cas théorique.
Le Compromis : Ils ont montré une courbe claire : si vous voulez une distribution de trafic parfaitement équitable, vous devez faire installer de nouvelles applications à un peu plus de personnes. Si vous voulez simplement respecter la règle des 30 % avec le moins d'efforts, vous installez moins d'applications, mais le trafic est moins uniformément réparti.

La Conclusion

Ce document est le premier à traiter ce problème réglementaire comme un puzzle d'informatique. Il prouve que nous n'avons pas besoin de forcer des millions de personnes à changer leurs habitudes du jour au lendemain. Au lieu de cela, en utilisant des algorithmes intelligents pour décider qui doit installer quelle application, les régulateurs peuvent appliquer la règle des 30 % de manière fluide, permettant à l'autoroute du paiement numérique de circuler librement pour tout le monde sans causer d'embouteillage.

Résumé Technique : Distribution Équitable des Paiements Numériques

1. Définition du Problème

L'article traite du problème de l'UPI à capacité contrainte, un défi réglementaire découlant de la concentration des transactions au sein de l'écosystème Unified Payments Interface (UPI) en Inde. Actuellement, deux applications (PhonePe et Google Pay) traitent plus de 80 % des transactions, ce qui crée des risques systémiques et une utilisation inégale des subventions publiques. Pour atténuer cela, la National Payments Corporation of India (NPCI) a imposé qu'aucune application UPI ne puisse traiter plus de 30 % du volume total des transactions.

Le défi computationnel central est de redistribuer les transactions des utilisateurs entre les applications pour respecter ce plafond de 30 % tout en minimisant l'inconvénient pour l'utilisateur, défini ici comme le nombre d'installations d'applications supplémentaires requises. Le problème est modélisé comme un problème de Flux de Minimisation d'Activation d'Arêtes (MEAF) sur un réseau biparti :

Nœuds : Utilisateurs ( $U$ ) et Applications ( $A$ ).
Arêtes : Les arêtes pleines représentent les installations existantes ; les arêtes pointillées représentent les nouvelles installations potentielles.
Contraintes : Les utilisateurs ont des volumes de transaction ( $t_u$ ) ; les applications ont des limites de capacité ( $c_a$ ).
Objectif : Activer le sous-ensemble minimal d'arêtes pointillées (nouvelles installations) pour acheminer toutes les transactions d'une source vers un puits sans violer les capacités des applications.

Le problème est formalisé en trois variantes :

UPI à capacité contrainte : Cadre hors ligne (offline) avec des journaux de transactions connus.
UPI à capacité contrainte en ligne (online) : Cadre en temps réel où les transactions arrivent séquentiellement sans connaissance du futur.
UPI à capacité contrainte équitable : Une extension visant à équilibrer la distribution de la charge (en minimisant l'écart Max-Min ou le coefficient de Gini) parallèlement à la minimisation des installations.

2. Analyse de Complexité

Les auteurs prouvent que le problème du flux de minimisation d'activation d'arêtes est NP-complet via une réduction du problème de la 3-Partition.

Dureté : Le problème de décision consistant à trouver le plus petit ensemble d'activations pour satisfaire les demandes de flux est NP-complet, même lorsqu'il est restreint à trois applications.
Inapproximabilité : Le problème généralise le problème de la Couverture d'Ensembles (Set Cover), impliquant que, sauf si P=NP, aucun algorithme d'approximation en temps polynomial n'existe avec un facteur meilleur que $(1-o(1))\log n$ .
Implication : Les solutions exactes (comme la programmation linéaire en nombres entiers - ILP) sont computationnellement intraçables à l'échelle de 100 millions de transactions, nécessitant des approches heuristiques scalables.

3. Méthodologie

L'article propose une suite d'algorithmes allant des formulations exactes aux heuristiques scalables pour les contextes hors ligne et en ligne.

3.1 Formulations Exactes (ILP)

Deux modèles de programmation linéaire en nombres entiers (ILP) sont développés comme références :

ILP de Minimisation d'Installation : Minimise le nombre d'arêtes pointillées activées sous réserve de conservation du flux et de contraintes de capacité.
ILP de l'Équité Max-Min : Utilise le nombre optimal d'installations du premier modèle comme une contrainte de budget et maximise le niveau de charge minimum entre les applications pour assurer l'équité.

3.2 Stratégie Hors Ligne : Stratégie d'Allocation Découplée en Deux Étapes (DTAS)

Pour gérer des données hors ligne à grande échelle, les auteurs proposent la DTAS, une heuristique gloutonne qui exploite l'asymétrie de la charge de travail (où une petite fraction d'utilisateurs génère la majorité des transactions).

Idée clé : Traiter les utilisateurs dans l'ordre décroissant de leur volume de transaction (en priorisant les utilisateurs "lourds") sature rapidement les applications à haute capacité, forçant les utilisateurs "légers" à installer de nouvelles applications inutilement.
Mécanisme : La DTAS traite les utilisateurs dans l'ordre croissant de leur volume de transaction.
- Phase 1 : Alloue les transactions en utilisant les applications pré-installées.
- Phase 2 : Satisfait la demande restante en empruntant à un pool partagé d'applications existantes avant d'activer de nouvelles installations.
Résultat : Cet ordonnancement préserve la flexibilité de la capacité pour les utilisateurs lourds ultérieurement, réduisant considérablement le nombre total d'installations requises.

3.3 Stratégies En Ligne

Pour le routage des transactions en temps réel, l'article introduit des algorithmes adaptatifs :

Online_DTAS : Une extension de la DTAS pour les données en flux (streaming).
- Détection d'Utilisateurs Lourds : Utilise un algorithme de schéma Space-Saving pour estimer dynamiquement les fréquences des utilisateurs et identifier les utilisateurs "lourds" sans maintenir des compteurs pour tous les utilisateurs.
- Planification Différée (Delayed Scheduling) : Les utilisateurs lourds sont temporairement mis en attente dans une file de priorité bornée. Les utilisateurs légers sont routés immédiatement selon la stratégie à trois niveaux (pré-installé $\to$ pool partagé $\to$ nouvelle installation).
- Mécanisme de Vidage (Drain) : Les transactions des utilisateurs lourds différées sont traitées périodiquement pour éviter le débordement de la file, garantissant l'efficacité à long terme.
Fair_DTAS : Une extension de Online_DTAS axée sur l'équité.
- Score Composé : Au lieu de sélectionner les applications uniquement sur la base de la disponibilité, il utilise une fonction de score : $Score(a) = \alpha \cdot InstallPenalty(a) + \beta \cdot \Delta Fair(a)$ .
- Terme d'Équité : $\Delta Fair(a)$ estime l'augmentation du déséquilibre de la charge globale (variance) si une transaction est assignée à l'application $a$ .
- Compromis : Les paramètres $\alpha$ et $\beta$ permettent aux régulateurs d'ajuster l'équilibre entre la minimisation des coûts d'installation et la maximisation de l'équilibre de la charge.

4. Résultats Expérimentaux

Les auteurs ont évalué leurs méthodes sur un ensemble de données de 100 millions de transactions dérivé du jeu de données de transactions Rabobank, mis à l'échelle pour simuler les modèles d'utilisation de l'UPI.

Efficacité vs Optimalité : La DTAS atteint des résultats à seulement 1 à 2 installations supplémentaires de l'optimum de l'ILP sur toutes les échelles testées, tout en s'exécutant plusieurs ordres de grandeur plus rapidement.
Surcharge d'Installation :
- Online_DTAS surpasse considérablement les bases (Random, Least_Used) et les variantes d'ablation (DTAS_No_Delay) en minimisant les installations.
- Fair_DTAS entraîne une augmentation modeste du coût d'installation (environ 21 % de plus que Online_DTAS) mais atteint un indice d'équité de Jain de 0,89, contre environ 0,42 pour les autres méthodes.
Sensibilité à la Capacité :
- À une limite de capacité d'application stricte de 10 %, environ 2,25 % des utilisateurs nécessitent de nouvelles installations, et environ 65 millions de transactions restent non allouées.
- À une limite de 30 % (le plafond proposé par la NPCI), les transactions non allouées chutent considérablement, et le besoin de nouvelles installations devient négligeable pour la grande majorité des utilisateurs.
- Les auteurs notent qu'augmenter les limites de capacité améliore la faisabilité mais peut involontairement renforcer le duopole en permettant aux applications dominantes d'absorber plus de charge.

5. Signification et Revendications

L'article affirme être le premier travail à modéliser et traiter formellement le problème de l'équilibrage des flux de transactions financières pour la conformité réglementaire. Sa signification réside dans :

Faisabilité Réglementaire : Il fournit un cadre algorithmique concret pour appliquer le plafond de 30 % de la NPCI sans perturber les habitudes des utilisateurs ou causer des échecs de transaction.
Analyse Coût-Bénéfice : Il quantifie le compromis entre l'équité et les coûts d'installation, offrant aux décideurs une « courbe de compromis concrète » pour informer les délais d'application et les budgets d'incitation (ex: programmes de cashback).
Scalabilité : Il démontre que des solutions quasi-optimales peuvent être obtenues à l'échelle de 100 millions de transactions grâce à des heuristiques scalables, rendant la solution viable pour un déploiement réel.
Aperçu Comportemental : Il souligne que différer les utilisateurs lourds et prioriser les utilisateurs légers est contre-intuitif mais crucial pour l'efficacité du système, une découverte qui défie les heuristiques standards de répartition de charge.

Les auteurs concluent que bien que leur formulation actuelle se concentre sur le nombre de transactions, les travaux futurs pourraient incorporer la valeur des transactions pour traiter les risques financiers et des compromis d'équité plus riches. Ils soulignent que leur cadre sert d'outil d'aide à la décision pour les régulateurs afin de maintenir un écosystème de paiement numérique compétitif, résilient et équitable.