💰 quantitative finance

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

Este artigo aborda o desafio computacional de redistribuir transações de pagamentos digitais para cumprir o limite de 30% de participação de mercado de aplicativos UPI na Índia, formalizando o problema como o problema NP-Completo de Fluxo de Ativação Mínima de Arestas e propondo uma heurística escalável, DTAS, que minimiza eficientemente o inconveniente ao usuário enquanto impõe limites regulatórios.

Autores originais: Ashlesha Hota, Shashwat Kumar, Daman Deep Singh, Abolfazl Asudeh, Palash Dey, Abhijnan Chakraborty

Publicado 2026-06-04

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Ashlesha Hota, Shashwat Kumar, Daman Deep Singh, Abolfazl Asudeh, Palash Dey, Abhijnan Chakraborty

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine o sistema de pagamentos digitais da Índia, o UPI, como um enorme e super-rápido sistema de rodovias onde bilhões de pessoas dirigem seu dinheiro todos os dias. No momento, quase todo mundo está dirigindo em apenas duas estradas específicas: PhonePe e Google Pay. Esses dois "apps" são tão populares que estão lidando com mais de 80% de todo o tráfego.

Isso cria um problema. Se uma dessas duas estradas tiver um buraco enorme (uma queda de servidor) ou ficar muito congestionada, todo o sistema pode travar. Além disso, parece injusto que a infraestrutura gratuita do governo esteja sendo usada majoritariamente por apenas duas empresas.

Para resolver isso, o regulador (NPCI) tem uma nova regra: Nenhum app individual pode carregar mais de 30% do tráfego total.

O Grande Desafio

A parte complicada é esta: você não pode simplesmente dizer a milhões de pessoas: "Parem de usar seu app favorito e mudem para um novo hoje". As pessoas são criaturas de hábito; elas gostam dos apps que já possuem.

Se um app atingir seu limite de 30%, o sistema não pode simplesmente bloquear o pagamento do usuário (isso seria rude e causaria erros). Em vez disso, o sistema precisa guiar gentilmente os usuários para outros apps menos congestionados. Mas a maioria das pessoas tem apenas um ou dois apps instalados. Para usar um app diferente, elas precisam baixar e instalar um novo primeiro.

Os pesquisadores fizeram uma pergunta simples: Qual é o número absoluto mínimo de pessoas que precisam instalar um novo app para que os pagamentos de todos ainda possam ocorrer sem quebrar a regra dos 30%?

O "Quebra-cabeça" que Eles Resolveram

Os autores perceberam que isso é um quebra-cabeça matemático gigante e complexo.

Os Jogadores: Milhões de usuários (que têm diferentes quantidades de dinheiro para enviar) e muitos apps (que têm um limite de quanto tráfego podem suportar).
O Objetivo: Conectar usuários a apps para que nenhum app fique sobrecarregado, enquanto força o menor número possível de pessoas a baixar um novo app.

Eles provaram que resolver isso perfeitamente é incrivelmente difícil — tão difícil que até os supercomputadores mais rápidos levariam uma eternidade para encontrar a resposta perfeita para um cenário do mundo real. É como tentar resolver um Sudoku onde a grade tem o tamanho de uma cidade e as regras mudam a cada segundo.

A Solução Deles: O "Gerente de Tráfego Inteligente"

Como eles não podiam resolver o quebra-culo perfeito instantaneamente, construíram um "Gerente de Tráfego Inteligente" chamado DTAS (Decoupled Two-Stage Allocation Strategy). Pense nisso como um guarda de trânsito muito astuto que usa alguns truques inteligentes:

A Regra do "Leve Primeiro":
Imagine uma festa onde você tem que acomodar os convidados. Se você acomodar primeiro os convidados gigantes e pesados, eles ocuparão todas as mesas grandes, deixando os convidados menores sem lugar para sentar.
Os pesquisadores descobriram que, se você tentar rotear os "usuários pesados" (pessoas que fazem milhares de transações) primeiro, eles consomem toda a capacidade dos apps populares imediatamente. Isso força todos os outros a instalarem novos apps.
O truque deles: Rotear os "usuários leves" (pessoas que pagam por um café ou itens pequenos) primeiro. Eles se encaixam facilmente nos assentos vazios. Quando os "usuários pesados" chegam, ainda há espaço suficiente para que eles compartilhem a carga sem precisar instalar novos apps.
O Truque do "Espere um Segundo" (para Sistemas Online):
No mundo real, os pagamentos acontecem um por um, e o sistema não sabe quem é um usuário pesado até que eles comecem a pagar.
O sistema usa um "esboço" (sketch — um truque rápido de memória) para adivinhar quem é um usuário pesado. Se ele acha que alguém é um usuário pesado, ele coloca o pagamento em uma fila de espera por uma fração de segundo. Esse atraso permite que o sistema veja o quadro geral e direcione o pagamento para um app menos congestionado, em vez de despejá-lo no app mais popular.
A Opção de "Equidade":
Eles também construíram uma versão chamada Fair_DTAS. Esta versão se preocupa ainda mais em garantir que cada app receba uma parte justa do tráfego, não apenas em evitar o limite de 30%. É como um professor que não apenas garante que nenhum aluno seja reprovado, mas assegura que todos recebam uma atenção semelhante. Isso custa alguns outros usuários instalando novos apps, mas cria um ecossistema muito mais equilibrado.

O Que Eles Descobriram

Eles testaram seu sistema usando dados de 100 milhões de transações (simuladas a partir de dados bancários reais).

Eficiência: O "Gerente de Tráfego Inteligente" deles foi quase tão bom quanto a solução matemática perfeita, mas rodou milhões de vezes mais rápido.
Custo: Exigiu apenas 1 ou 2 instalações extras de apps por usuário, em média, comparado ao melhor caso teórico.
O Equilíbrio (Trade-off): Eles mostraram uma curva clara: Se você quer uma distribuição de tráfego perfeitamente justa, você precisa de mais pessoas instalando novos apps. Se você quer apenas cumprir a regra dos 30% com o menor esforço, você instala menos apps, mas o tráfego é menos uniformemente distribuído.

A Conclusão

Este artigo é o primeiro a tratar este problema regulatório como um quebra-cabeça de ciência da computação. Ele prova que não precisamos forçar milhões de pessoas a mudar seus hábitos da noite para o dia. Em vez disso, ao usar algoritmos inteligentes para decidir quem deve instalar qual app, os reguladores podem aplicar a regra dos 30% de forma suave, mantendo a rodovia de pagamentos digitais fluindo livremente para todos sem causar um congestionamento.

Resumo Técnico: Distribuição Justa de Pagamentos Digitais

1. Definição do Problema

O artigo aborda o problema do UPI com Restrição de Capacidade, um desafio regulatório decorrente da concentração de transações dentro do ecossistema da Unified Payments Interface (UPI) na Índia. Atualmente, dois aplicativos (PhonePe e Google Pay) processam mais de 80% das transações, criando riscos sistêmicos e uma utilização desigual de subsídios públicos. Para mitigar isso, a National Payments Corporation of India (NPCI) determinou que nenhum aplicativo UPI individual pode processar mais de 30% do volume total de transações.

O desafio computacional central é redistribuir as transações dos usuários entre os aplicativos para satisfazer esse limite de 30%, minimizando o inconveniente ao usuário, definido aqui como o número de instalações de novos aplicativos necessárias. O problema é modelado como um problema de Fluxo de Ativação Mínima de Arestas (MEAF) em uma rede bipartida:

Nós: Usuários ( $U$ ) e Aplicativos ( $A$ ).
Arestas: Arestas sólidas representam instalações existentes; arestas tracejadas representam potenciais novas instalações.
Restrições: Usuários possuem volumes de transação ( $t_u$ ); aplicativos possuem limites de capacidade ( $c_a$ ).
Objetivo: Ativar o subconjunto mínimo de arestas tracejadas (novas instalações) para rotear todas as transações de uma origem para um destino sem violar as capacidades dos aplicativos.

O problema é formalizado em três variantes:

UPI com Restrição de Capacidade (Offline): Configuração offline com logs de transações conhecidos.
UPI com Restrição de Capacidade (Online): Configuração em tempo real onde as transações chegam sequencialmente sem conhecimento futuro.
UPI com Restrição de Capacidade Justa: Uma extensão que visa equilibrar a distribuição de carga (minimizando a lacuna Máximo-Mínimo ou o coeficiente de Gini) juntamente com a minimização de instalações.

2. Análise de Complexidade

Os autores provam que o problema de Fluxo de Ativação Mínima de Arestas é NP-Completo via uma redução do problema da Partição de 3 (3-Partition).

Dureza: O problema de decisão de encontrar o menor conjunto de ativações para satisfazer as demandas de fluxo é NP-completo, mesmo quando restrito a três aplicativos.
Inaproximabilidade: O problema generaliza o problema de Cobertura de Conjuntos (Set Cover), implicando que, a menos que P=NP, não existe um algoritmo de aproximação em tempo polinomial com um fator melhor que $(1-o(1))\log n$ .
Implicação: Soluções exatas (como Programação Linear Inteira) são computacionalmente intratáveis na escala de 100 milhões de transações, necessitando de abordagens heurísticas escaláveis.

3. Metodologia

O artigo propõe um conjunto de algoritmos que variam de formulações exatas a heurísticas escaláveis para configurações tanto offline quanto online.

3.1 Formulações Exatas (ILP)

Dois modelos de Programação Linear Inteira (ILP) são desenvolvidos como bases de comparação:

ILP de Minimização de Instalação: Minimiza o número de arestas tracejadas ativadas sujeito à conservação de fluxo e restrições de capacidade.
ILP de Equidade Máximo-Mínimo: Utiliza a contagem de instalação ótima do primeiro modelo como uma restrição de orçamento e maximiza o nível de carga mínimo entre os aplicativos para garantir a equidade.

3.2 Estratégia Offline: Estratégia de Alocação Desacoplada em Dois Estágios (DTAS)

Para lidar com dados offline de grande escala, os autores propõem a DTAS, uma heurística gulosa que explora a assimetria da carga de trabalho (onde uma pequena fração de usuários gera a maioria das transações).

Insight Chave: Processar usuários em ordem decrescente de volume de transação (priorizando usuários "pesados") satura rapidamente aplicativos de alta capacidade, forçando usuários "leves" a instalar novos aplicativos desnecessariamente.
Mecanismo: A DTAS processa usuários em ordem ascendente de volume de transação.
- Fase 1: Aloca transações usando aplicativos pré-instalados.
- Fase 2: Satisfaz a demanda restante pegando emprestado de um pool compartilhado de aplicativos existentes antes de ativar novas instalações.
Resultado: Esta ordenação preserva a flexibilidade de capacidade para usuários pesados posteriormente, reduzindo significativamente o número total de instalações exigidas.

3.3 Estratégias Online

Para o roteamento de transações em tempo real, o artigo introduz algoritmos adaptativos:

Online_DTAS: Uma extensão da DTAS para dados de streaming.
- Detecção de Usuário Pesado: Utiliza um algoritmo de esboço Space-Saving para estimar dinamicamente as frequências dos usuários e identificar usuários "pesados" sem manter contadores para todos os usuários.
- Agendamento Retardado: Transações de usuários pesados são temporariamente retidas em uma fila de prioridade limitada. Usuários leves são roteados imediatamente usando a estratégia de três níveis (pré-instalado $\to$ pool compartilhado $\to$ nova instalação).
- Mecanismo de Drenagem: As transações de usuários pesados atrasadas são processadas periodicamente para evitar o transbordamento da fila, garantindo eficiência a longo prazo.
Fair_DTAS: Uma extensão da Online_DTAS focada em equidade.
- Pontuação Composta: Em vez de selecionar aplicativos baseando-se apenas na disponibilidade, utiliza uma função de pontuação: $Score(a) = \alpha \cdot InstallPenalty(a) + \beta \cdot \Delta Fair(a)$ .
- Termo de Equidade: $\Delta Fair(a)$ estima o aumento no desequilíbrio de carga global (variância) se uma transação for atribuída ao aplicativo $a$ .
- Trade-off: Os parâmetros $\alpha$ e $\beta$ permitem que os reguladores ajustem o equilíbrio entre minimizar os custos de instalação e maximizar o equilíbrio de carga.

4. Resultados Experimentais

Os autores avaliaram seus métodos em um conjunto de dados de 100 milhões de transações derivado do dataset de transações Rabobank, escalado para simular padrões de uso do UPI.

Eficiência vs. Otimalidade: A DTAS alcança resultados dentro de 1 a 2 instalações adicionais do ótimo do ILP em todas as escalas testadas, enquanto roda várias ordens de magnitude mais rápido.
Sobrecarga de Instalação:
- A Online_DTAS supera significativamente os baselines (Random, Least_Used) e variantes de ablação (DTAS_No_Delay) na minimização de instalações.
- A Fair_DTAS incorre em um aumento modesto no custo de instalação (aprox. 21% a mais que a Online_DTAS), mas alcança um índice de equidade de Jain de 0,89, comparado a ~0,42 para outros métodos.
Sensibilidade de Capacidade:
- Em um limite estrito de 10% de capacidade do aplicativo, ~2,25% dos usuários requerem novas instalações, e ~65 milhões de transações permanecem não alocadas.
- Com um limite de 30% (o teto proposto pela NPCI), as transações não alocadas caem significativamente, e a necessidade de novas instalações torna-se negligenciável para a vasta maioria dos usuários.
- Os autores observam que aumentar os limites de capacidade melhora a viabilidade, mas pode inadvertidamente fortalecer o duopólio ao permitir que os aplicativos dominantes absorvam mais carga.

5. Significância e Alegações

O artigo afirma ser o primeiro trabalho a modelar e abordar formalmente o problema de equilibrar fluxos de transações financeiras para conformidade regulatória. Sua significância reside em:

Viabilidade Regulatória: Fornece um framework algorítmico concreto para aplicar o limite de 30% da NPCI sem interromper os hábitos dos usuários ou causar falhas de transação.
Análise de Custo-Benefício: Quantifica o trade-off entre equidade e custos de instalação, oferecendo aos formuladores de políticas uma "curva de trade-off concreta" para informar prazos de aplicação e orçamentos de incentivos (ex: programas de cashback).
Escalabilidade: Demonstra que soluções próximas do ótimo podem ser alcançadas na escala de 100 milhões de transações usando heurísticas escaláveis, tornando a solução viável para implantação no mundo real.
Insight Comportamental: Destaca que atrasar usuários pesados e priorizar usuários leves é contraintuitivo, mas crítico para a eficiência do sistema, um achado que desafia heurísticas padrão de balanceamento de carga.

Os autores concluem que, embora sua formulação atual foque em contagens de transações, trabalhos futuros poderiam incorporar valores de transação para abordar riscos financeiros e trade-offs de equidade mais ricos. Eles enfatizam que seu framework serve como uma ferramenta de suporte à decisão para reguladores manterem um ecossistema de pagamentos digitais competitivo, resiliente e equitativo.