기술 요약: 디지털 결제의 공정한 분배

1. 문제 정의

본 논문은 인도 통합 결제 인터페이스(UPI) 생태계 내에서 발생하는 규제적 과제인 캡 제한형 UPI(Cap-Constrained UPI) 문제를 다룹니다. 현재 두 개의 애플리케이션(PhonePe와 Google Pay)이 전체 거래의 80% 이상을 처리하고 있어, 이는 시스템적 리스크와 공공 보조금의 불균형한 활용을 초래합니다. 이를 완화하기 위해 인도 국립결제공사(NPCI)는 단일 UPI 앱이 전체 거래량의 30%를 초과하여 처리할 수 없도록 규정했습니다.

핵심적인 계산적 과제는 사용자의 불편함(여기서는 추가 앱 설치 횟수로 정의됨)을 최소화하면서, 30% 캡을 충족하도록 사용자 거래를 애플리케이션 간에 재분배하는 것입니다. 이 문제는 이분 네트워크(bipartite network) 상의 최소 엣지 활성화 흐름(Minimum Edge Activation Flow, MEAF) 문제로 모델링됩니다:

• 노드: 사용자($U$) 및 애플리케이션($A$).
• 엣지: 실선 엣지는 기존 설치 상태를 나타내며, 점선 엣지는 잠재적인 신규 설치를 나타냅니다.
• 제약 조건: 사용자는 거래량($t_u$)을 가지며, 앱은 용량 제한($c_a$)을 가집니다.
• 목표: 앱 용량을 위반하지 않으면서 소스(source)에서 싱크(sink)로 모든 거래를 라우팅하기 위해, 활성화되는 점선 엣지의 최소 부분 집합을 선택합니다.

문제는 세 가지 변형으로 공식화됩니다:

1. 캡 제한형 UPI: 알려진 거래 로그가 있는 오프라인 설정.
2. 온라인 캡 제한형 UPI: 미래에 대한 지식 없이 거래가 순차적으로 도착하는 실시간 설정.
3. 공정 캡 제한형 UPI: 설치 횟수를 최소화하는 것과 동시에 부하 분산(Max-Min 격차 또는 지니 계수 최소화)을 목표로 하는 확장 모델.

2. 복잡도 분석

저자들은 3-Partition 문제로부터의 환원을 통해 Minimum Edge Activation Flow 문제가 **NP-완전(NP-Complete)**임을 증명합니다.

• 난해성(Hardness): 흐름 요구량을 충족하기 위한 가장 작은 활성화 집합을 찾는 결정 문제(decision problem)는 단 3개의 앱으로 제한되더라도 NP-완전입니다.
• 근사 불가능성(Inapproximability): 이 문제는 Set Cover 문제를 일반화하며, 이는 P=NP가 아닌 한 다항 시간 내에 $(1-o(1))\log n$보다 나은 인자를 가진 근사 알고리즘이 존재할 수 없음을 의미합니다.
• 시사점: 정밀한 해법(예: 정수 선형 계획법, ILP)은 1억 건의 거래 규모에서는 계산적으로 실행 불가능하므로, 확장 가능한 휴리스틱 접근 방식이 필요합니다.

3. 방법론

본 논문은 오프라인 및 온라인 설정 모두에 대해 정밀한 공식화부터 확장 가능한 휴리스틱에 이르는 다양한 알고리즘 세트를 제안합니다.

3.1 정밀 공식화 (ILP)

두 가지 정수 선형 계획법(ILP) 모델이 베이스라인으로 개발되었습니다:

• 설치 최소화 ILP (Install-Minimization ILP): 흐름 보존 및 용량 제약 조건을 준수하면서 활성화되는 점선 엣지의 수를 최소화합니다.
• 최대-최소 공정성 ILP (Max-Min Fairness ILP): 첫 번째 모델의 최적 설치 횟수를 예산 제약으로 사용하여, 애플리케이션 간의 최소 부하 수준을 최대화함으로써 공정성을 확보합니다.

3.2 오프라인 전략: 분리된 2단계 할당 전략 (DTAS)

대규모 오프라인 데이터를 처리하기 위해 저자들은 워크로드 왜곡(소수의 사용자가 대다수의 거래를 생성하는 현상)을 활용하는 그리디 휴리스틱인 DTAS를 제안합니다.

• 핵심 통찰: 거래량이 많은 사용자(heavy users)를 우선순위로 하여 내림차순으로 처리하면, 고용량 앱이 빠르게 포화되어 가벼운 사용자(light users)들이 불필요하게 새 앱을 설치해야 하는 상황이 발생합니다.
• 메커니즘: DTAS는 거래량을 오름차순으로 처리합니다.
  • 1단계: 기존에 설치된 앱들을 사용하여 거래를 할당합니다.
  • 2단계: 새로운 설치를 활성화하기 전에, 공유된 기존 앱 풀(pool)에서 남은 수요를 충족합니다.
• 결 결과: 이러한 순서 처리는 이후의 헤비 유저들을 위한 용량 유연성을 보존함으로써, 필요한 총 설치 횟수를 크게 줄여줍니다.

3.3 온라인 전략

실시간 거래 라우팅을 위해 본 논문은 적응형 알고리즘을 도입합니다:

• Online_DTAS: 스트리밍 데이터를 위한 DTAS의 확장판입니다.
  • 헤비 유저 탐지: Space-Saving 스케치 알고리즘을 사용하여 모든 사용자에 대한 카운터를 유지하지 않고도 사용자의 빈도를 동적으로 추정하고 "헤비" 사용자를 식별합니다.
  • 지연 스케줄링 (Delayed Scheduling): 헤비 유저를 제한된 우선순위 큐에 일시적으로 대기시킵니다. 라이트 유저는 3단계 전략(기설치 $\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억 건의 거래 데이터셋을 통해 제안된 방법들을 평가했습니다.

• 효율성 vs 최적성: DTAS는 모든 테스트 규모에서 ILP 최적값 대비 1~2회의 추가 설치 차이 이내의 결과를 달encing하며, 훨씬 더 빠른 속도로 실행됩니다.
• 설치 오버헤드:
  • Online_DTAS는 베이스라인(Random, Least_Used) 및 절제 모델(DTAS_No_Delay)에 비해 설치 횟수를 최소화하는 데 있어 월등한 성능을 보였습니다.
  • Fair_DTSA는 설치 비용이 (Online_DTAS보다 약 21% 증가) 약간 늘어나지만, 다른 방법들이 ~0.42의 Jain's fairness index를 보이는 것에 비해 0.89의 지수를 달성했습니다.
• 용량 민감도:
  • 엄격한 10% 앱 용량 제한 시, 약 2.25%의 사용자가 신규 설치를 요구하며 약 6,500만 건의 거래가 할당되지 못합니다.
  • 30% 제한(NPCI 제안 캡) 시, 미할당 거래가 급격히 감소하며 대다수 사용자에게 신규 설치의 필요성이 거의 없어집니다.
  • 저자들은 용량 제한을 높이는 것이 실행 가능성을 개선하지만, 지배적인 앱이 더 많은 부하를 흡수하게 함으로써 의도치 않게 독과점을 강화할 수 있다고 언급했습니다.

5. 의의 및 주장

본 논문은 금융 거래 흐름의 균형을 맞추는 문제를 공식적으로 모델링하고 해결한 최초의 연구라고 주장합니다. 그 의의는 다음과 같습니다:

1. 규제적 실행 가능성: 사용자 습관을 저해하거나 거래 실패를 일으키지 않으면서 NPCI의 30% 캡을 강제할 수 있는 구체적인 알고리즘 프레임워크를 제공합니다.
2. 비용-편익 분석: 공정성과 설치 비용 사이의 트레이드오프를 정량화하여, 정책 입안자들에게 집행 기한이나 인센티브 예산(예: 캐시백 프로그램)을 결정할 수 있는 "구체적인 트레이드오프 곡선"을 제공합니다.
3. 확장성: 1억 건의 거래 규모에서도 근사 최적해를 얻을 수 있는 확장 가능한 휴리스틱을 입증함으로써, 실제 환경에서의 배포 가능성을 보여주었습니다.
4. 행동적 통찰: 헤비 유저를 지연시키고 라이트 유저를 우선시하는 것이 효율성 측면에서 매우 중요하다는 점을 밝혀냈는데, 이는 표준적인 부하 분산 휴리스틱에 반하는 직관적인 발견입니다.

저자들은 현재의 모델이 거래 횟수에 집중하고 있지만, 향후에는 거래 가치를 포함하여 금융 리스크와 더 풍부한 공정성 트레이드오프를 다룰 수 있다고 결론지었습니다. 이 프레임워크가 경쟁력 있고 회복 탄력적이며 형평성 있는 디지털 결제 생태계를 유지하기 위한 규제 기관의 의사결정 지원 도구 역할을 할 것임을 강조합니다.