Technical Summary: Fair Distribution of Digital Payments

1. Problem Definition

The paper addresses the Cap-Constrained UPI problem, a regulatory challenge arising from the concentration of transactions within the Unified Payments Interface (UPI) ecosystem in India. Currently, two applications (PhonePe and Google Pay) process over 80% of transactions, creating systemic risks and uneven utilization of public subsidies. To mitigate this, the National Payments Corporation of India (NPCI) has mandated that no single UPI app may process more than 30% of total transaction volume.

The core computational challenge is to redistribute user transactions across applications to satisfy this 30% cap while minimizing user inconvenience, defined here as the number of additional app installations required. The problem is modeled as a Minimum Edge Activation Flow (MEAF) problem on a bipartite network:

• Nodes: Users ($U$) and Applications ($A$).
• Edges: Solid edges represent existing installations; dashed edges represent potential new installations.
• Constraints: Users have transaction volumes ($t_u$); apps have capacity limits ($c_a$).
• Objective: Activate the minimum subset of dashed edges (new installations) to route all transactions from a source to a sink without violating app capacities.

The problem is formalized in three variants:

1. Cap-Constrained UPI: Offline setting with known transaction logs.
2. Online Cap-Constrained UPI: Real-time setting where transactions arrive sequentially without future knowledge.
3. Fair Cap-Constrained UPI: An extension aiming to balance load distribution (minimizing Max-Min gap or Gini coefficient) alongside minimizing installations.

2. Complexity Analysis

The authors prove that the Minimum Edge Activation Flow problem is NP-Complete via a reduction from the 3-Partition problem.

• Hardness: The decision problem of finding the smallest set of activations to satisfy flow demands is NP-complete, even when restricted to three apps.
• Inapproximability: The problem generalizes the Set Cover problem, implying that unless P=NP, no polynomial-time approximation algorithm exists with a factor better than $(1-o(1))\log n$.
• Implication: Exact solutions (like Integer Linear Programming) are computationally intractable at the scale of 100 million transactions, necessitating scalable heuristic approaches.

3. Methodology

The paper proposes a suite of algorithms ranging from exact formulations to scalable heuristics for both offline and online settings.

3.1 Exact Formulations (ILP)

Two Integer Linear Programming (ILP) models are developed as baselines:

• Install-Minimization ILP: Minimizes the number of activated dashed edges subject to flow conservation and capacity constraints.
• Max-Min Fairness ILP: Uses the optimal installation count from the first model as a budget constraint and maximizes the minimum load level across applications to ensure fairness.

3.2 Offline Strategy: Decoupled Two-Stage Allocation Strategy (DTAS)

To handle large-scale offline data, the authors propose DTAS, a greedy heuristic that exploits workload skewness (where a small fraction of users generates the majority of transactions).

• Key Insight: Processing users in descending order of transaction volume (prioritizing "heavy" users) rapidly saturates high-capacity apps, forcing "light" users to install new apps unnecessarily.
• Mechanism: DTAS processes users in ascending order of transaction volume.
  • Phase 1: Allocates transactions using pre-installed apps.
  • Phase 2: Satisfies remaining demand by borrowing from a shared pool of existing apps before activating new installations.
• Result: This ordering preserves capacity flexibility for heavy users later, significantly reducing the total number of required installations.

3.3 Online Strategies

For real-time transaction routing, the paper introduces adaptive algorithms:

• Online_DTAS: An extension of DTAS for streaming data.
  • Heavy-User Detection: Uses a Space-Saving sketch algorithm to dynamically estimate user frequencies and identify "heavy" users without maintaining counters for all users.
  • Delayed Scheduling: Heavy users are temporarily stalled in a bounded priority queue. Light users are routed immediately using the three-tier strategy (pre-installed $\to$ shared pool $\to$ new install).
  • Drain Mechanism: Delayed heavy-user transactions are processed periodically to prevent queue overflow, ensuring long-term efficiency.
• Fair_DTAS: A fairness-aware extension of Online_DTAS.
  • Composite Scoring: Instead of selecting apps solely based on availability, it uses a scoring function: $Score(a) = \alpha \cdot InstallPenalty(a) + \beta \cdot \Delta Fair(a)$.
  • Fairness Term: $\Delta Fair(a)$ estimates the increase in global load imbalance (variance) if a transaction is assigned to app $a$.
  • Trade-off: The parameters $\alpha$ and $\beta$ allow regulators to tune the balance between minimizing installation costs and maximizing load balance.

4. Experimental Results

The authors evaluated their methods on a dataset of 100 million transactions derived from the Rabobank Transactions dataset, scaled to simulate UPI usage patterns.

• Efficiency vs. Optimality: DTAS achieves results within 1–2 additional installations of the ILP optimum across all tested scales, while running several orders of magnitude faster.
• Installation Overhead:
  • Online_DTAS significantly outperforms baselines (Random, Least_Used) and ablation variants (DTAS_No_Delay) in minimizing installations.
  • Fair_DTAS incurs a modest increase in installation cost (approx. 21% more than Online_DTAS) but achieves a Jain's fairness index of 0.89, compared to ~0.42 for other methods.
• Capacity Sensitivity:
  • At a strict 10% app capacity limit, ~2.25% of users require new installations, and ~65 million transactions remain unallocated.
  • At a 30% limit (NPCI's proposed cap), unallocated transactions drop significantly, and the need for new installations becomes negligible for the vast majority of users.
  • The authors note that increasing capacity limits improves feasibility but can inadvertently strengthen the duopoly by allowing dominant apps to absorb more load.

5. Significance and Claims

The paper claims to be the first work to formally model and address the problem of balancing financial transaction flows for regulatory compliance. Its significance lies in:

1. Regulatory Feasibility: It provides a concrete, algorithmic framework for enforcing the NPCI's 30% cap without disrupting user habits or causing transaction failures.
2. Cost-Benefit Analysis: It quantifies the trade-off between fairness and installation costs, offering policymakers a "concrete trade-off curve" to inform enforcement deadlines and incentive budgets (e.g., cashback programs).
3. Scalability: It demonstrates that near-optimal solutions can be achieved at the scale of 100 million transactions using scalable heuristics, making the solution viable for real-world deployment.
4. Behavioral Insight: It highlights that delaying heavy users and prioritizing lightweight users is counter-intuitive but critical for system efficiency, a finding that challenges standard load-balancing heuristics.

The authors conclude that while their current formulation focuses on transaction counts, future work could incorporate transaction values to address financial risks and richer fairness trade-offs. They emphasize that their framework serves as a decision-support tool for regulators to maintain a competitive, resilient, and equitable digital payment ecosystem.