💰 quantitative finance

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

本文通过将该问题形式化为 NP 完全的最小边激活流问题，并提出了一种可扩展的启发式算法 DTAS，旨在高效地在执行监管限制的同时最小化用户不便，从而解决了为遵守印度 UPI 应用 30% 市场份额上限而需重新分配数字支付交易这一计算挑战。

原作者： Ashlesha Hota, Shashwat Kumar, Daman Deep Singh, Abolfazl Asudeh, Palash Dey, Abhijnan Chakraborty

发布于 2026-06-04

📖 1 分钟阅读☕ 轻松阅读

原作者： Ashlesha Hota, Shashwat Kumar, Daman Deep Singh, Abolfazl Asudeh, Palash Dey, Abhijnan Chakraborty

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下印度的数字支付系统 UPI，它就像一个巨大的、超高速的高速公路系统，每天都有数十亿人在上面运送他们的资金。目前，几乎所有人都在仅有的两条特定道路上行驶：PhonePe 和 Google Pay。这两款“应用”如此受欢迎，以至于它们处理了超过 80% 的所有交通流量。

这产生了一个问题。如果这两条路中的任何一条出现了巨大的坑洼（服务器崩溃）或者变得过于拥挤，整个系统就会发生瘫痪。此外，如果政府提供的免费基础设施主要被这两家公司使用，这也会让人觉得不公平。

为了解决这个问题，监管机构（NPCI）制定了一条新规则：没有任何单一应用可以承载超过总流量 30% 的交通量。

巨大的挑战

棘手之处在于：你不能直接告诉数百万用户，“从今天起停止使用你最喜欢的应用，换成一个新的。” 人们是习惯的生物；他们喜欢自己已经拥有的应用。

如果一个应用的流量达到了 30% 的限制，系统不能直接拦截用户的支付（这会显得很无礼并导致错误）。相反，系统需要温和地引导用户转向其他负载较低的应用。但大多数人只安装了一两个应用。要使用不同的应用，他们必须先下载并安装它。

研究人员提出了一个简单的问题：为了确保每个人的支付都能顺利进行且不违反 30% 的规则，究竟最少需要多少人安装一个新的应用？

他们解决的“谜题”

作者意识到这是一个巨大的、复杂的数学谜题。

参与者： 数百万用户（他们发送的金额各不相同）和许多应用（每个应用都有其能处理的流量上限）。
目标： 将用户连接到应用，既保证没有应用过载，又强迫尽可能少的人去下载新应用。

他们证明了完美解决这个问题是极其困难的——难到即使是最快的超级计算机也需要花费永恒的时间才能找到完美答案。这就像是在尝试解决一个规模如城市般庞大的数独谜题，而且规则每秒钟都在变化。

他们的解决方案：“智能交通管理者”

由于他们无法立即解决完美的谜题，他们构建了一个名为 DTAS（解耦两阶段分配策略）的“智能交通管理者”。你可以把它想象成一个非常聪明的交警，他使用了几个聪明的技巧：

“轻量优先”原则：
想象一场派对，你必须安排宾客入座。如果你先安排那些高大、沉重的宾客入座，他们会占满所有的宽大桌子，导致小个子的宾客无处可坐。
研究人员发现，如果你先尝试路由“重度用户”（那些进行数千笔交易的人），他们会立即吃掉热门应用上的所有容量。这会迫使其他所有人去安装新应用。
他们的技巧： 先路由“轻量级用户”（那些支付咖啡钱或小额物品的人）。他们能轻松挤进空位。等到“重度用户”到达时，系统中仍有足够的空间让他们分担负载，而无需安装新应用。
“等一下”技巧（针对在线系统）：
在现实世界中，支付是一个接一个发生的，系统在用户开始支付之前并不知道谁是“重度用户”。
该系统使用一种“草图”（一种快速记忆技巧）来猜测谁是重度用户。如果系统认为某人可能是重度用户，它会将该笔支付放入一个极短时间的等待队列中。这种延迟让系统能够看到更宏观的全貌，并将支付路由到负载较低的应用，而不是将其倾倒在最热门的应用上。
“公平性”选项：
他们还构建了一个名为 Fair_DTAS 的版本。这个版本更加关注确保每个应用都能获得公平的份额，而不仅仅是避免达到 30% 的限制。这就像一位老师，不仅确保没有学生不及格，还确保每个人都能得到类似的关注。这会多让一些人安装新应用，但它创造了一个更加平衡的生态系统。

他们的发现

他们使用 1 亿笔交易的数据（模拟自真实的银行数据）测试了他们的系统。

效率： 他们的“智能交通管理者”几乎与完美的数学解一样出色，但运行速度快了数百万倍。
成本： 与理论上的最佳情况相比，平均每位用户仅需多安装 1 或 2 个应用。
权衡： 他们展示了一条清晰的曲线：如果你想要完美的流量分布，你需要让更多的人安装新应用。如果你只想满足 30% 的规则并以最小的代价实现，你会安装较少的应用，但流量分布会不够均匀。

核心启示

这篇论文首次将这一监管问题视为一个计算机科学谜题。它证明了我们不需要强迫数百万人在一夜之间改变习惯。相反，通过使用智能算法来决定谁应该安装哪个应用，监管机构可以平滑地执行 30% 的规则，让数字支付高速公路为每个人自由流动，而不会造成交通拥堵。

技术摘要：数字支付的公平分配

1. 问题定义

本文探讨了容量受限的 UPI 问题（Cap-Constrained UPI problem），这是一个由印度统一支付接口（UPI）生态系统中交易集中化引发的监管挑战。目前，两款应用程序（PhonePe 和 Google Pay）处理了超过 80% 的交易，这造成了系统性风险和公共补贴利用不均的问题。为了缓解这一情况，印度国家支付公司（NPCI）规定，任何单一 UPI 应用处理的交易总量不得超过 30%。

核心计算挑战在于如何在满足 30% 容量上限的同时，重新分配用户交易，并使用户不便程度（在此定义为所需的额外应用安装数量）最小化。该问题被建模为二分网络上的**最小边激活流（Minimum Edge Activation Flow, MEAF）**问题：

节点： 用户 ( $U$ ) 与应用程序 ( $A$ )。
边：实线边代表现有安装；虚线边代表潜在的新安装。
约束： 用户拥有交易量 ( $t_u$ )；应用拥有容量限制 ( $c_a$ )。
目标： 激活最小数量的虚线边（新安装），以在不违反应用容量的情况下，将所有交易从源端路由至汇端。

该问题被形式化为三个变体：

容量受限的 UPI： 离线设置，已知交易日志。
在线容量受限的 UPI： 实时设置，交易按顺序到达且无法预知未来信息。
公平容量受限的 UPI： 一种旨在同时平衡负载分布（最小化最大-最小差距或基尼系数）与最小化安装数量的扩展模型。

2. 复杂度分析

作者通过将 Minimum Edge Activation Flow 问题归约为 3-Partition 问题，证明了该问题是 NP 完全（NP-Complete） 的。

硬度（Hardness）： 寻找满足流量需求最小激活集合的判定问题是 NP 完全的，即使在仅有三个应用的限制下也是如此。
不可近似性（Inapproximability）： 该问题泛化了集合覆盖（Set Cover）问题，这意味着除非 P=NP，否则不存在优于 $(1-o(1))\log n$ 因子的多项式时间近似算法。
启示： 在 1 亿次交易的规模下，精确解（如整数线性规划）在计算上是难以处理的，因此需要可扩展的启发式方法。

3. 方法论

论文提出了一套涵盖从精确公式到针对离线和在线场景的可扩展启发式算法的方案。

3.1 精确公式 (ILP)

开发了两个整数线性规划（ILP）模型作为基准：

安装最小化 ILP（Install-Minimization ILP）： 在满足流量守恒和容量约束的前提下，最小化激活的虚线边数量。
最大-最小公平性 ILP（Max-Min Fairness ILP）： 以第一个模型的最佳安装数量作为预算约束，并最大化各应用间的最小负载水平，以确保公平性。

3.2 离线策略：解耦两阶段分配策略 (DTAS)

为了处理大规模离线数据，作者提出了 DTAS，这是一种利用工作负载偏斜性（即极少数用户产生大部分交易）的贪心启发式算法。

关键洞察： 按交易量降序处理用户（优先处理“重度”用户）会迅速饱和高容量应用，从而迫使“轻度”用户进行不必要的应用安装。
机制： DTAS 按交易量的升序处理用户。
- 第一阶段： 使用预装应用分配交易。
- 第二阶段： 在激活新安装之前，通过从现有的共享应用池中“借用”容量来满足剩余需求。
结果： 这种排序为后续的重度用户保留了容量灵活性，显著减少了所需的总安装量。

3.3 在线策略

针对实时交易路由，论文引入了自适应算法：

Online_DTAS： DTAS 在流式数据下的扩展。
- 重度用户检测： 使用 Space-Saving 算法（Sketch 算法） 动态估计用户频率，并识别“重度”用户，而无需为所有用户维护计数器。
- 延迟调度： 重度用户被暂时缓存在一个有界优先队列中。轻度用户则使用三层策略（预装 $\to$ 共享池 $\to$ 新安装）立即进行路由。
- 排空机制（Drain Mechanism）： 定期处理延迟的重度用户交易，以防止队列溢出，确保长期效率。
Fair_DTAS： Online_DTAS 的公平性增强版。
- 复合评分： 它不再仅根据可用性选择应用，而是使用评分函数： $Score(a) = \alpha \cdot InstallPenalty(a) + \beta \cdot \Delta Fair(a)$ 。
- 公平性项： $\Delta Fair(a)$ 用于估算如果将交易分配给应用 $a$ ，全球负载失衡度（方差）会增加多少。
- 权衡： 参数 $\alpha$ 和 $\beta$ 允许监管机构在最小化安装成本与最大化负载平衡之间进行调节。

4. 实验结果

作者在源自 Rabobank 交易数据集、并经过缩放以模拟 UPI 使用模式的 1 亿次交易 数据集上评估了其方法。

效率与最优性： 在所有测试规模下，DTAS 的结果与 ILP 最优解仅差 1–2 次额外安装，同时运行速度快了数个数量级。
安装开销：
- Online_DTAS 在最小化安装方面显著优于基准方法（Random, Least_Used）以及消融变体（DTAS_No_Delay）。
- Fair_DTAS 虽然会导致安装成本略微增加（比 Online_DTAS 高约 21%），但实现了 0.89 的 Jain 公平指数，而其他方法的指数仅约为 0.42。
容量敏感性：
- 在严格的 10% 应用容量限制下，约 2.25% 的用户需要新安装，且约 6500 万次交易无法被分配。
- 在 30% 的限制下（NPCI 提出的上限），未分配的交易显著减少，且对于绝大多数用户而言，新安装的需求变得微乎其微。
- 作者指出，提高容量限制虽然能提高可行性，但也可能通过允许主导应用吸收更多负载，从而在无意中强化双头垄断。

5. 意义与主张

论文声称这是首个正式建模并解决平衡金融交易流以实现监管合规问题的研究。其重要性在于：

监管可行性： 它提供了一个具体的算法框架，用于在不破坏用户习惯或导致交易失败的情况下，强制执行 NPCI 的 30% 上限。
成本效益分析： 它量化了公平性与安装成本之间的权衡，为政策制定者提供了“具体的权衡曲线”，以指导执行期限和激励预算（如返现计划）。
可扩展性： 它证明了利用可扩展的启发式算法可以在 1 亿次交易的规模下实现接近最优的解，使该方案具备实际部署的可能性。
行为洞察： 它强调了延迟重度用户并优先处理轻度用户是反直觉但对系统效率至关重要的，这一发现挑战了标准的负载均衡启发式算法。

作者总结道，虽然目前的公式侧重于交易次数，但未来的工作可以纳入交易金额，以应对金融风险和更丰富的公平性权衡。他们强调，该框架可作为监管机构的决策支持工具，以维持一个竞争激烈、具有韧性且公平的数字支付生态系统。